Debian Codegraph @

hash/fnv/fnv.ha

raw
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 };