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