fnv.ha (5004B)
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 };