| 1 |
// SPDX-License-Identifier: MPL-2.0 |
| 2 |
// (c) Hare authors <https://harelang.org> |
| 3 |
|
| 4 |
use endian; |
| 5 |
use hash; |
| 6 |
use io; |
| 7 |
use strings; |
| 8 |
|
| 9 |
def PRIME32: u32 = 16777619; |
| 10 |
def PRIME64: u64 = 1099511628211; |
| 11 |
|
| 12 |
export def BASIS32: u32 = 2166136261; |
| 13 |
export def BASIS64: u64 = 14695981039346656037; |
| 14 |
|
| 15 |
export type state32 = struct { |
| 16 |
hash::hash, |
| 17 |
v: u32, |
| 18 |
}; |
| 19 |
|
| 20 |
export type state64 = struct { |
| 21 |
hash::hash, |
| 22 |
v: u64, |
| 23 |
}; |
| 24 |
|
| 25 |
// Hashes a string, returning a 32-bit key. |
| 26 |
export fn string32(s: str) u32 = { |
| 27 |
let hash = fnv32a(); |
| 28 |
hash::write(&hash, strings::toutf8(s)); |
| 29 |
return sum32(&hash); |
| 30 |
}; |
| 31 |
|
| 32 |
// Hashes a string, returning a 64-bit key. |
| 33 |
export fn string64(s: str) u64 = { |
| 34 |
let hash = fnv64a(); |
| 35 |
hash::write(&hash, strings::toutf8(s)); |
| 36 |
return sum64(&hash); |
| 37 |
}; |
| 38 |
|
| 39 |
const fnv32_vtable: io::vtable = io::vtable { |
| 40 |
writer = &fnv32_write, |
| 41 |
... |
| 42 |
}; |
| 43 |
|
| 44 |
// Creates a [[hash::hash]] which computes the FNV-1 32-bit hash function. This |
| 45 |
// hash does not allocate any state, so you do not need to call [[hash::close]] |
| 46 |
// when you're done with it. |
| 47 |
// |
| 48 |
// Unless you have a reason to use this, [[fnv32a]] is recommended instead. |
| 49 |
export fn fnv32(basis: u32 = BASIS32) state32 = state32 { |
| 50 |
stream = &fnv32_vtable, |
| 51 |
sum = &fnv32_sum, |
| 52 |
reset = &fnv32_reset, |
| 53 |
sz = 4, |
| 54 |
v = basis, |
| 55 |
... |
| 56 |
}; |
| 57 |
|
| 58 |
const fnv32a_vtable: io::vtable = io::vtable { |
| 59 |
writer = &fnv32a_write, |
| 60 |
... |
| 61 |
}; |
| 62 |
|
| 63 |
// Creates a [[hash::hash]] which computes the FNV-1a 32-bit hash function. This |
| 64 |
// hash does not allocate any state, so you do not need to call [[hash::close]] |
| 65 |
// when you're done with it. |
| 66 |
export fn fnv32a(basis: u32 = BASIS32) state32 = state32 { |
| 67 |
stream = &fnv32a_vtable, |
| 68 |
sum = &fnv32_sum, |
| 69 |
reset = &fnv32_reset, |
| 70 |
sz = 4, |
| 71 |
v = basis, |
| 72 |
... |
| 73 |
}; |
| 74 |
|
| 75 |
const fnv64_vtable: io::vtable = io::vtable { |
| 76 |
writer = &fnv64_write, |
| 77 |
... |
| 78 |
}; |
| 79 |
|
| 80 |
// Creates a [[hash::hash]] which computes the FNV-1 64-bit hash function. This |
| 81 |
// hash does not allocate any state, so you do not need to call [[hash::close]] |
| 82 |
// when you're done with it. |
| 83 |
// |
| 84 |
// Unless you have a reason to use this, [[fnv64a]] is recommended instead. |
| 85 |
export fn fnv64(basis: u64 = BASIS64) state64 = state64 { |
| 86 |
stream = &fnv64_vtable, |
| 87 |
sum = &fnv64_sum, |
| 88 |
reset = &fnv64_reset, |
| 89 |
sz = 8, |
| 90 |
v = basis, |
| 91 |
... |
| 92 |
}; |
| 93 |
|
| 94 |
const fnv64a_vtable: io::vtable = io::vtable { |
| 95 |
writer = &fnv64a_write, |
| 96 |
... |
| 97 |
}; |
| 98 |
|
| 99 |
// Creates a [[hash::hash]] which computes the FNV-1a 64-bit hash function. This |
| 100 |
// hash does not allocate any state, so you do not need to call [[hash::close]] |
| 101 |
// when you're done with it. |
| 102 |
export fn fnv64a(basis: u64 = BASIS64) state64 = state64 { |
| 103 |
stream = &fnv64a_vtable, |
| 104 |
sum = &fnv64_sum, |
| 105 |
reset = &fnv64_reset, |
| 106 |
sz = 8, |
| 107 |
v = basis, |
| 108 |
... |
| 109 |
}; |
| 110 |
|
| 111 |
fn fnv32_write(s: *io::stream, buf: const []u8) (size | io::error) = { |
| 112 |
let s = s: *state32; |
| 113 |
for (let i = 0z; i < len(buf); i += 1) { |
| 114 |
s.v *= PRIME32; |
| 115 |
s.v ^= buf[i]; |
| 116 |
}; |
| 117 |
return len(buf); |
| 118 |
}; |
| 119 |
|
| 120 |
fn fnv32a_write(s: *io::stream, buf: const []u8) (size | io::error) = { |
| 121 |
let s = s: *state32; |
| 122 |
for (let i = 0z; i < len(buf); i += 1) { |
| 123 |
s.v ^= buf[i]; |
| 124 |
s.v *= PRIME32; |
| 125 |
}; |
| 126 |
return len(buf); |
| 127 |
}; |
| 128 |
|
| 129 |
fn fnv32_reset(h: *hash::hash) void = { |
| 130 |
let h = h: *state32; |
| 131 |
h.v = BASIS32; |
| 132 |
}; |
| 133 |
|
| 134 |
fn fnv32_sum(h: *hash::hash, buf: []u8) void = { |
| 135 |
let h = h: *state32; |
| 136 |
endian::host.putu32(buf, h.v); |
| 137 |
}; |
| 138 |
|
| 139 |
fn fnv64_write(s: *io::stream, buf: const []u8) (size | io::error) = { |
| 140 |
let s = s: *state64; |
| 141 |
for (let i = 0z; i < len(buf); i += 1) { |
| 142 |
s.v *= PRIME64; |
| 143 |
s.v ^= buf[i]; |
| 144 |
}; |
| 145 |
return len(buf); |
| 146 |
}; |
| 147 |
|
| 148 |
fn fnv64a_write(s: *io::stream, buf: const []u8) (size | io::error) = { |
| 149 |
let s = s: *state64; |
| 150 |
for (let i = 0z; i < len(buf); i += 1) { |
| 151 |
s.v ^= buf[i]; |
| 152 |
s.v *= PRIME64; |
| 153 |
}; |
| 154 |
return len(buf); |
| 155 |
}; |
| 156 |
|
| 157 |
fn fnv64_reset(h: *hash::hash) void = { |
| 158 |
let h = h: *state64; |
| 159 |
h.v = BASIS64; |
| 160 |
}; |
| 161 |
|
| 162 |
fn fnv64_sum(h: *hash::hash, buf: []u8) void = { |
| 163 |
let h = h: *state64; |
| 164 |
endian::host.putu64(buf, h.v); |
| 165 |
}; |
| 166 |
|
| 167 |
// Returns the sum of a 32-bit FNV hash. |
| 168 |
export fn sum32(h: *hash::hash) u32 = { |
| 169 |
assert(h.reset == &fnv32_reset); |
| 170 |
let h = h: *state32; |
| 171 |
return h.v; |
| 172 |
}; |
| 173 |
|
| 174 |
// Returns the sum of a 64-bit FNV hash. |
| 175 |
export fn sum64(h: *hash::hash) u64 = { |
| 176 |
assert(h.reset == &fnv64_reset); |
| 177 |
let h = h: *state64; |
| 178 |
return h.v; |
| 179 |
}; |
| 180 |
|
| 181 |
@test fn fnv32() void = { |
| 182 |
// TODO: Expand these tests |
| 183 |
// I am too tired |
| 184 |
const vectors: [_](str, u32) = [ |
| 185 |
("", 2166136261), |
| 186 |
("hello world", 1418570095), |
| 187 |
("Hare is a cool language", 2663852071), |
| 188 |
("'UNIX was not designed to stop its users from doing stupid things, as that would also stop them from doing clever things' - Doug Gwyn", 1203174417), |
| 189 |
("'Life is too short to run proprietary software' - Bdale Garbee", 493463614), |
| 190 |
("'The central enemy of reliability is complexity.' - Geer et al", 3263526736), |
| 191 |
("'A language that doesn’t have everything is actually easier to program in than some that do.' - Dennis Ritchie", 3069348265), |
| 192 |
]; |
| 193 |
|
| 194 |
let hash = fnv32(); |
| 195 |
let s: [4]u8 = [0...]; |
| 196 |
|
| 197 |
for (let i = 0z; i < len(vectors); i += 1) { |
| 198 |
let vec = vectors[i]; |
| 199 |
|
| 200 |
hash::reset(&hash); |
| 201 |
hash::write(&hash, strings::toutf8(vec.0)); |
| 202 |
hash::sum(&hash, s); |
| 203 |
|
| 204 |
assert(endian::host.getu32(s) == vec.1); |
| 205 |
assert(sum32(&hash) == vec.1); |
| 206 |
}; |
| 207 |
}; |