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