hash.bend
bend-kit-hash@0.1.0.0 · 436 lines · 0 definitions
1# Non-cryptographic hashes over Bytes: FNV-1a, xxHash, SipHash-1-3, CRC-32, and Adler-32. Source: https://github.com/paymog/bend-kit/tree/main/hash
2import Base
3# bend-kit-bytes@0.3.0.0
4import bend-kit-bytes@0.3.0.0/bytes.bend as Bytes
5
6# Each hash hands the buffer back beside its value. A buffer's bytes at or past len are 0.
7# Each hash also has a .str form over a byte string (one Char per octet), copied to Bytes first.
8# import bend-kit-hash@0.1.0.0/hash.bend as Hash
9
10# A 64-bit value as two halves. Base has no native U64, and int's U64 is a bit list.
11type W64 is Data:
12 W64{hi: U32, lo: U32}
13
14def W64.xor(a: W64, b: W64) -> W64:
15 match a b:
16 case W64{ah, al} W64{bh, bl}:
17 W64{U32.xor(ah, bh), U32.xor(al, bl)}
18
19def W64.add.of(+ah: U32, +bh: U32, +al: U32, +lo: U32) -> W64:
20 W64{(ah + bh + Bool.pick(U32, U32.is_lt(lo, al), 1, 0) : U32), lo}
21
22def W64.add(a: W64, b: W64) -> W64:
23 match a b:
24 case W64{+ah, +al} W64{+bh, +bl}:
25 W64.add.of(ah, bh, al, (al + bl : U32))
26
27# The full 64-bit product of two U32, from four 16-bit partial products.
28def mul32.of(+p00: U32, +p01: U32, +p10: U32, +p11: U32) -> W64:
29 +mid = ((p00 >> 16n) + (p01 .&. 65535) + (p10 .&. 65535) : U32)
30 W64{(p11 + (p01 >> 16n) + (p10 >> 16n) + (mid >> 16n) : U32), ((p00 .&. 65535) .|. (mid << 16n) : U32)}
31
32def mul32(+x: U32, +y: U32) -> W64:
33 +x0 = (x .&. 65535 : U32)
34 +x1 = (x >> 16n : U32)
35 +y0 = (y .&. 65535 : U32)
36 +y1 = (y >> 16n : U32)
37 mul32.of((x0 * y0 : U32), (x0 * y1 : U32), (x1 * y0 : U32), (x1 * y1 : U32))
38
39def W64.mul.of(+cross: U32, p: W64) -> W64:
40 W64{+h, +l} = p
41 W64{(h + cross : U32), l}
42
43def W64.mul(a: W64, b: W64) -> W64:
44 match a b:
45 case W64{+ah, +al} W64{+bh, +bl}:
46 W64.mul.of(((al * bh) + (ah * bl) : U32), mul32(al, bl))
47
48# Rotate left by k, for 0 < k < 32; j is 32 - k.
49def W64.rotl(+k: Nat, +j: Nat, a: W64) -> W64:
50 match a:
51 case W64{+h, +l}:
52 W64{((h << k) .|. (l >> j) : U32), ((l << k) .|. (h >> j) : U32)}
53
54def W64.swap(a: W64) -> W64:
55 match a:
56 case W64{h, l}:
57 W64{l, h}
58
59# Shift right by k, for 0 < k < 32; j is 32 - k.
60def W64.shr(+k: Nat, +j: Nat, a: W64) -> W64:
61 match a:
62 case W64{+h, +l}:
63 W64{(h >> k : U32), ((l >> k) .|. (h << j) : U32)}
64
65def W64.lo(a: W64) -> U32:
66 match a:
67 case W64{h, l}:
68 l
69
70def rotl32(+x: U32, +k: Nat, +j: Nat) -> U32:
71 ((x << k) .|. (x >> j) : U32)
72
73# Folds f over n words from word i on. r holds the array and word i.
74def wfold(~T: Type, ~f: T -> @+c: U32 -> T, n: Nat, r: Array<U32> & U32, +i: U32, acc: T) -> Array<U32> & T:
75 match n:
76 case 0n:
77 (a, w) = r
78 (a, acc)
79 case 1n+p:
80 (a, +w) = r
81 +j = (i + 1 : U32)
82 wfold(~T, ~f, p, Array.get(U32, a, j), j, f(acc, w))
83
84def wfrom(~T: Type, ~f: T -> @+c: U32 -> T, n: Nat, a: Array<U32>, +i: U32, acc: T) -> Array<U32> & T:
85 wfold(~T, ~f, n, Array.get(U32, a, i), i, acc)
86
87# Words i and i + 1 as one little-endian 64-bit lane.
88def get2.of(+lo: U32, r: Array<U32> & U32) -> Array<U32> & W64:
89 (a, +hi) = r
90 (a, W64{hi, lo})
91
92def get2.lo(+i: U32, r: Array<U32> & U32) -> Array<U32> & W64:
93 (a, +lo) = r
94 get2.of(lo, Array.get(U32, a, (i + 1 : U32)))
95
96def get2(a: Array<U32>, +i: U32) -> Array<U32> & W64:
97 get2.lo(i, Array.get(U32, a, i))
98
99# Folds f over n 64-bit lanes from word i on. r holds the array and the lane at i.
100def dfold(~T: Type, ~f: T -> @+m: W64 -> T, n: Nat, r: Array<U32> & W64, +i: U32, acc: T) -> Array<U32> & T:
101 match n:
102 case 0n:
103 (a, m) = r
104 (a, acc)
105 case 1n+p:
106 (a, +m) = r
107 +j = (i + 2 : U32)
108 dfold(~T, ~f, p, get2(a, j), j, f(acc, m))
109
110def dfrom(~T: Type, ~f: T -> @+m: W64 -> T, n: Nat, a: Array<U32>, +i: U32, acc: T) -> Array<U32> & T:
111 dfold(~T, ~f, n, get2(a, i), i, acc)
112
113# Folds f over the low k bytes of w, lowest first.
114def tail(~T: Type, ~f: T -> @+c: U32 -> T, k: Nat, +w: U32, acc: T) -> T:
115 match k:
116 case 0n:
117 acc
118 case 1n+p:
119 tail(~T, ~f, p, (w >> 8n : U32), f(acc, (w .&. 255 : U32)))
120
121def bytewise.last(~T: Type, ~byte: T -> @+c: U32 -> T, +len: U32, acc: T, r: Array<U32> & U32) -> Bytes.Bytes & T:
122 (a, +w) = r
123 (Bytes.Bytes{len, a}, tail(~T, ~byte, U32.to_nat((len .&. 3 : U32)), w, acc))
124
125def bytewise.rest(~T: Type, ~byte: T -> @+c: U32 -> T, +len: U32, r: Array<U32> & T) -> Bytes.Bytes & T:
126 (a, acc) = r
127 bytewise.last(~T, ~byte, len, acc, Array.get(U32, a, (len >> 2n : U32)))
128
129# A hash that eats one byte at a time: word takes the four bytes of a word, byte one.
130def bytewise(~T: Type, ~byte: T -> @+c: U32 -> T, ~word: T -> @+c: U32 -> T, b: Bytes.Bytes, acc: T) -> Bytes.Bytes & T:
131 Bytes.Bytes{+len, buf} = b
132 bytewise.rest(~T, ~byte, len, wfrom(~T, ~word, U32.to_nat((len >> 2n : U32)), buf, 0, acc))
133
134# FNV-1a (draft-eastlake-fnv), 32 and 64 bits.
135def fnv32.byte(h: U32, +c: U32) -> U32:
136 ((h .^. c) * 16777619 : U32)
137
138def fnv32.word(h: U32, +w: U32) -> U32:
139 fnv32.byte(fnv32.byte(fnv32.byte(fnv32.byte(h, (w .&. 255 : U32)), ((w >> 8n) .&. 255 : U32)), ((w >> 16n) .&. 255 : U32)), (w >> 24n : U32))
140
141def fnv1a32(b: Bytes.Bytes) -> Bytes.Bytes & U32:
142 bytewise(~U32, ~fnv32.byte, ~fnv32.word, b, 2166136261)
143
144def fnv64.byte(h: W64, +c: U32) -> W64:
145 match h:
146 case W64{hi, lo}:
147 W64.mul(W64{hi, (lo .^. c : U32)}, W64{256, 435})
148
149def fnv64.word(h: W64, +w: U32) -> W64:
150 fnv64.byte(fnv64.byte(fnv64.byte(fnv64.byte(h, (w .&. 255 : U32)), ((w >> 8n) .&. 255 : U32)), ((w >> 16n) .&. 255 : U32)), (w >> 24n : U32))
151
152def fnv1a64(b: Bytes.Bytes) -> Bytes.Bytes & W64:
153 bytewise(~W64, ~fnv64.byte, ~fnv64.word, b, W64{3421674724, 2216829733})
154
155# CRC-32 (ISO-HDLC, as in gzip and zlib): reflected, polynomial 0xEDB88320.
156def crc.bit(+c: U32) -> U32:
157 Bool.pick(U32, U32.is_eq((c .&. 1 : U32), 1), ((c >> 1n) .^. 3988292384 : U32), (c >> 1n : U32))
158
159def crc.bits(k: Nat, +c: U32) -> U32:
160 match k:
161 case 0n:
162 c
163 case 1n+p:
164 crc.bits(p, crc.bit(c))
165
166def crc.fill(k: Nat, +i: U32, a: Array<U32>) -> Array<U32>:
167 match k:
168 case 0n:
169 a
170 case 1n+p:
171 crc.fill(p, (i + 1 : U32), Array.set(U32, a, i, crc.bits(8n, i)))
172
173# The table and the running register.
174type Crc is Type:
175 Crc{t: Array<U32>, h: U32}
176
177def crc.mix(+c: U32, r: Array<U32> & U32) -> Crc:
178 (a, +t) = r
179 Crc{a, (t .^. (c >> 8n) : U32)}
180
181def crc.byte(st: Crc, +c: U32) -> Crc:
182 Crc{a, +h} = st
183 crc.mix(h, Array.get(U32, a, ((h .^. c) .&. 255 : U32)))
184
185def crc.word(st: Crc, +w: U32) -> Crc:
186 crc.byte(crc.byte(crc.byte(crc.byte(st, (w .&. 255 : U32)), ((w >> 8n) .&. 255 : U32)), ((w >> 16n) .&. 255 : U32)), (w >> 24n : U32))
187
188def crc.fin(r: Bytes.Bytes & Crc) -> Bytes.Bytes & U32:
189 (b, Crc{t, +h}) = r
190 (b, (h .^. 4294967295 : U32))
191
192def crc32(b: Bytes.Bytes) -> Bytes.Bytes & U32:
193 crc.fin(bytewise(~Crc, ~crc.byte, ~crc.word, b, Crc{crc.fill(256n, 0, Array.new(U32, 8n, 0)), 4294967295}))
194
195# Adler-32 (RFC 1950 §9). The state is the checksum itself: s2 << 16 | s1.
196# A word takes mod 65521 once, after four bytes; no sum reaches 2^32 first.
197def adler.of(+s1: U32, +s2: U32) -> U32:
198 (((s2 % 65521) << 16n) .|. (s1 % 65521) : U32)
199
200def adler.byte(h0: U32, +c: U32) -> U32:
201 +h = h0
202 +s1 = ((h .&. 65535) + c : U32)
203 adler.of(s1, ((h >> 16n) + s1 : U32))
204
205def adler.word(h0: U32, +w: U32) -> U32:
206 +h = h0
207 +a0 = ((h .&. 65535) + (w .&. 255) : U32)
208 +a1 = (a0 + ((w >> 8n) .&. 255) : U32)
209 +a2 = (a1 + ((w >> 16n) .&. 255) : U32)
210 +a3 = (a2 + (w >> 24n) : U32)
211 adler.of(a3, ((h >> 16n) + a0 + a1 + a2 + a3 : U32))
212
213def adler32(b: Bytes.Bytes) -> Bytes.Bytes & U32:
214 bytewise(~U32, ~adler.byte, ~adler.word, b, 1)
215
216# xxHash32 (XXH32, xxHash spec 0.1.1).
217type V4 is Data:
218 V4{a: U32, b: U32, c: U32, d: U32}
219
220def x32.round(+acc: U32, +x: U32) -> U32:
221 (rotl32((acc + x * 2246822519 : U32), 13n, 19n) * 2654435761 : U32)
222
223# The four accumulators take lanes in turn: v1 eats this word and moves to the back.
224def x32.lane(v: V4, +w: U32) -> V4:
225 match v:
226 case V4{a, b, c, d}:
227 V4{b, c, d, x32.round(a, w)}
228
229def x32.merge(r: Array<U32> & V4) -> Array<U32> & U32:
230 (buf, V4{+a, +b, +c, +d}) = r
231 (buf, (rotl32(a, 1n, 31n) + rotl32(b, 7n, 25n) + rotl32(c, 12n, 20n) + rotl32(d, 18n, 14n) : U32))
232
233def x32.word(h: U32, +w: U32) -> U32:
234 (rotl32((h + w * 3266489917 : U32), 17n, 15n) * 668265263 : U32)
235
236def x32.byte(h: U32, +c: U32) -> U32:
237 (rotl32((h + c * 374761393 : U32), 11n, 21n) * 2654435761 : U32)
238
239def x32.aval.c(+h: U32) -> U32:
240 (h .^. (h >> 16n) : U32)
241
242def x32.aval.b(+h: U32) -> U32:
243 x32.aval.c(((h .^. (h >> 13n)) * 3266489917 : U32))
244
245def x32.aval(+h: U32) -> U32:
246 x32.aval.b(((h .^. (h >> 15n)) * 2246822519 : U32))
247
248def x32.tail(+len: U32, +h: U32, r: Array<U32> & U32) -> Bytes.Bytes & U32:
249 (a, +w) = r
250 (Bytes.Bytes{len, a}, x32.aval(tail(~U32, ~x32.byte, U32.to_nat((len .&. 3 : U32)), w, h)))
251
252def x32.rest(+len: U32, r: Array<U32> & U32) -> Bytes.Bytes & U32:
253 (a, +h) = r
254 x32.tail(len, h, Array.get(U32, a, (len >> 2n : U32)))
255
256def x32.mid(+len: U32, r: Array<U32> & U32) -> Bytes.Bytes & U32:
257 (a, +h) = r
258 x32.rest(len, wfrom(~U32, ~x32.word, U32.to_nat(((len .&. 15) >> 2n : U32)), a, ((len >> 4n) << 2n : U32), (h + len : U32)))
259
260def x32.start(big: Bool, +len: U32, +seed: U32, a: Array<U32>) -> Array<U32> & U32:
261 match big:
262 case True{}:
263 x32.merge(wfrom(~V4, ~x32.lane, U32.to_nat(((len >> 4n) << 2n : U32)), a, 0, V4{(seed + 606290984 : U32), (seed + 2246822519 : U32), seed, (seed + 1640531535 : U32)}))
264 case False{}:
265 (a, (seed + 374761393 : U32))
266
267def xxh32(b: Bytes.Bytes, +seed: U32) -> Bytes.Bytes & U32:
268 Bytes.Bytes{+len, buf} = b
269 x32.mid(len, x32.start(U32.is_le(16, len), len, seed, buf))
270
271# xxHash64 (XXH64, xxHash spec 0.1.1).
272type V64 is Data:
273 V64{a: W64, b: W64, c: W64, d: W64}
274
275def x64.P1() -> W64:
276 W64{2654435761, 2246822535}
277
278def x64.P2() -> W64:
279 W64{3266489917, 668265295}
280
281def x64.P3() -> W64:
282 W64{374761393, 2654435833}
283
284def x64.P4() -> W64:
285 W64{2246822519, 3266489955}
286
287def x64.P5() -> W64:
288 W64{668265263, 374761413}
289
290def x64.round(acc: W64, x: W64) -> W64:
291 W64.mul(W64.rotl(31n, 1n, W64.add(acc, W64.mul(x, x64.P2()))), x64.P1())
292
293def x64.lane(v: V64, +m: W64) -> V64:
294 match v:
295 case V64{a, b, c, d}:
296 V64{b, c, d, x64.round(a, m)}
297
298def x64.fold(h: W64, v: W64) -> W64:
299 W64.add(W64.mul(W64.xor(h, x64.round(W64{0, 0}, v)), x64.P1()), x64.P4())
300
301def x64.merge(r: Array<U32> & V64) -> Array<U32> & W64:
302 (buf, V64{+a, +b, +c, +d}) = r
303 +h = W64.add(W64.add(W64.rotl(1n, 31n, a), W64.rotl(7n, 25n, b)), W64.add(W64.rotl(12n, 20n, c), W64.rotl(18n, 14n, d)))
304 (buf, x64.fold(x64.fold(x64.fold(x64.fold(h, a), b), c), d))
305
306def x64.word(h: W64, +m: W64) -> W64:
307 W64.add(W64.mul(W64.rotl(27n, 5n, W64.xor(h, x64.round(W64{0, 0}, m))), x64.P1()), x64.P4())
308
309def x64.byte(h: W64, +c: U32) -> W64:
310 W64.mul(W64.rotl(11n, 21n, W64.xor(h, W64.mul(W64{0, c}, x64.P5()))), x64.P1())
311
312def x64.four(h: W64, +w: U32) -> W64:
313 W64.add(W64.mul(W64.rotl(23n, 9n, W64.xor(h, W64.mul(W64{0, w}, x64.P1()))), x64.P2()), x64.P3())
314
315def x64.aval.c(h: W64) -> W64:
316 match h:
317 case W64{+hi, lo}:
318 W64{hi, (lo .^. hi : U32)}
319
320def x64.aval.b(+h: W64) -> W64:
321 x64.aval.c(W64.mul(W64.xor(h, W64.shr(29n, 3n, h)), x64.P3()))
322
323def x64.aval(h: W64) -> W64:
324 match h:
325 case W64{+hi, lo}:
326 x64.aval.b(W64.mul(W64{hi, (lo .^. (hi >> 1n) : U32)}, x64.P2()))
327
328# The last len % 8 bytes: a 4-byte lane when there is one, then single bytes.
329def x64.bytes(four: Bool, +k: Nat, h: W64, m: W64) -> W64:
330 match four:
331 case True{}:
332 match m:
333 case W64{+hi, +lo}:
334 tail(~W64, ~x64.byte, k, hi, x64.four(h, lo))
335 case False{}:
336 match m:
337 case W64{hi, +lo}:
338 tail(~W64, ~x64.byte, k, lo, h)
339
340def x64.tail(+len: U32, +h: W64, r: Array<U32> & W64) -> Bytes.Bytes & W64:
341 (a, m) = r
342 (Bytes.Bytes{len, a}, x64.aval(x64.bytes(U32.is_ne((len .&. 4 : U32), 0), U32.to_nat((len .&. 3 : U32)), h, m)))
343
344def x64.rest(+len: U32, r: Array<U32> & W64) -> Bytes.Bytes & W64:
345 (a, h) = r
346 x64.tail(len, h, get2(a, ((len >> 3n) << 1n : U32)))
347
348def x64.mid(+len: U32, r: Array<U32> & W64) -> Bytes.Bytes & W64:
349 (a, h) = r
350 x64.rest(len, dfrom(~W64, ~x64.word, U32.to_nat(((len .&. 31) >> 3n : U32)), a, ((len >> 5n) << 3n : U32), W64.add(h, W64{0, len})))
351
352def x64.start(big: Bool, +len: U32, +seed: W64, a: Array<U32>) -> Array<U32> & W64:
353 match big:
354 case True{}:
355 x64.merge(dfrom(~V64, ~x64.lane, U32.to_nat(((len >> 5n) << 2n : U32)), a, 0, V64{W64.add(seed, W64{1625958382, 2915087830}), W64.add(seed, x64.P2()), seed, W64.add(seed, W64{1640531534, 2048144761})}))
356 case False{}:
357 (a, W64.add(seed, x64.P5()))
358
359def xxh64(b: Bytes.Bytes, +seed: W64) -> Bytes.Bytes & W64:
360 Bytes.Bytes{+len, buf} = b
361 x64.mid(len, x64.start(U32.is_le(32, len), len, seed, buf))
362
363# SipHash-1-3 (Aumasson and Bernstein, 2012): one round per block, three to finish.
364type S4 is Data:
365 S4{v0: W64, v1: W64, v2: W64, v3: W64}
366
367def sip.round(s: S4) -> S4:
368 S4{v0, +v1, v2, +v3} = s
369 +a0 = W64.add(v0, v1)
370 +b1 = W64.xor(W64.rotl(13n, 19n, v1), a0)
371 +a2 = W64.add(v2, v3)
372 +b3 = W64.xor(W64.rotl(16n, 16n, v3), a2)
373 +c0 = W64.add(W64.swap(a0), b3)
374 +c2 = W64.add(a2, b1)
375 S4{c0, W64.xor(W64.rotl(17n, 15n, b1), c2), W64.swap(c2), W64.xor(W64.rotl(21n, 11n, b3), c0)}
376
377def sip.post(+m: W64, s: S4) -> S4:
378 S4{v0, v1, v2, v3} = s
379 S4{W64.xor(v0, m), v1, v2, v3}
380
381def sip.block(s: S4, +m: W64) -> S4:
382 S4{v0, v1, v2, v3} = s
383 sip.post(m, sip.round(S4{v0, v1, v2, W64.xor(v3, m)}))
384
385def sip.fin(s: S4) -> W64:
386 S4{v0, v1, v2, v3} = s
387 W64.xor(W64.xor(v0, v1), W64.xor(v2, v3))
388
389def sip.end(s: S4) -> W64:
390 S4{v0, v1, v2, v3} = s
391 sip.fin(sip.round(sip.round(sip.round(S4{v0, v1, W64.xor(v2, W64{0, 255}), v3}))))
392
393# The last block: the len % 8 bytes left, and len mod 256 in the top byte.
394def sip.last(+len: U32, r: Array<U32> & W64, s: S4) -> Bytes.Bytes & W64:
395 (a, W64{+hi, +lo}) = r
396 +k = (len .&. 7 : U32)
397 +top = ((len .&. 255) << 24n : U32)
398 (Bytes.Bytes{len, a}, sip.end(sip.block(s, W64{(Bool.pick(U32, U32.is_lt(4, k), hi, 0) .|. top : U32), Bool.pick(U32, U32.is_lt(0, k), lo, 0)})))
399
400def sip.rest(+len: U32, r: Array<U32> & S4) -> Bytes.Bytes & W64:
401 (a, s) = r
402 sip.last(len, get2(a, ((len >> 3n) << 1n : U32)), s)
403
404def siphash13(b: Bytes.Bytes, +k0: W64, +k1: W64) -> Bytes.Bytes & W64:
405 Bytes.Bytes{+len, buf} = b
406 sip.rest(len, dfrom(~S4, ~sip.block, U32.to_nat((len >> 3n : U32)), buf, 0, S4{W64.xor(k0, W64{1936682341, 1886610805}), W64.xor(k1, W64{1685025377, 1852075885}), W64.xor(k0, W64{1819895653, 1852142177}), W64.xor(k1, W64{1952801890, 2037671283})}))
407
408# The same hashes over a byte string. ponytail: copies to Bytes; hash short strings in place if the copy shows up in profiles.
409def v32(r: Bytes.Bytes & U32) -> U32:
410 (b, h) = r
411 h
412
413def v64(r: Bytes.Bytes & W64) -> W64:
414 (b, h) = r
415 h
416
417def fnv1a32.str(+s: String) -> U32:
418 v32(fnv1a32(Bytes.from_string(s)))
419
420def fnv1a64.str(+s: String) -> W64:
421 v64(fnv1a64(Bytes.from_string(s)))
422
423def xxh32.str(+s: String, +seed: U32) -> U32:
424 v32(xxh32(Bytes.from_string(s), seed))
425
426def xxh64.str(+s: String, +seed: W64) -> W64:
427 v64(xxh64(Bytes.from_string(s), seed))
428
429def siphash13.str(+s: String, +k0: W64, +k1: W64) -> W64:
430 v64(siphash13(Bytes.from_string(s), k0, k1))
431
432def crc32.str(+s: String) -> U32:
433 v32(crc32(Bytes.from_string(s)))
434
435def adler32.str(+s: String) -> U32:
436 v32(adler32(Bytes.from_string(s)))