hash.bend source
hash.bend on the hub · documented module
# 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/hashimport Base# bend-kit-bytes@0.3.0.0import 0x49814d83de8f70993a43e1002be29ecd/bytes.bend as Bytes# Each hash hands the buffer back beside its value. A buffer's bytes at or past len are 0.# Each hash also has a .str form over a byte string (one Char per octet), copied to Bytes first.# import bend-kit-hash@0.1.0.0/hash.bend as Hash# A 64-bit value as two halves. Base has no native U64, and int's U64 is a bit list.type W64 is Data: W64{hi: U32, lo: U32}def W64.xor(a: W64, b: W64) -> W64: match a b: case W64{ah, al} W64{bh, bl}: W64{U32.xor(ah, bh), U32.xor(al, bl)}def W64.add.of(+ah: U32, +bh: U32, +al: U32, +lo: U32) -> W64: W64{(ah + bh + Bool.pick(U32, U32.is_lt(lo, al), 1, 0) : U32), lo}def W64.add(a: W64, b: W64) -> W64: match a b: case W64{+ah, +al} W64{+bh, +bl}: W64.add.of(ah, bh, al, (al + bl : U32))# The full 64-bit product of two U32, from four 16-bit partial products.def mul32.of(+p00: U32, +p01: U32, +p10: U32, +p11: U32) -> W64: +mid = ((p00 >> 16n) + (p01 .&. 65535) + (p10 .&. 65535) : U32) W64{(p11 + (p01 >> 16n) + (p10 >> 16n) + (mid >> 16n) : U32), ((p00 .&. 65535) .|. (mid << 16n) : U32)}def mul32(+x: U32, +y: U32) -> W64: +x0 = (x .&. 65535 : U32) +x1 = (x >> 16n : U32) +y0 = (y .&. 65535 : U32) +y1 = (y >> 16n : U32) mul32.of((x0 * y0 : U32), (x0 * y1 : U32), (x1 * y0 : U32), (x1 * y1 : U32))def W64.mul.of(+cross: U32, p: W64) -> W64: W64{+h, +l} = p W64{(h + cross : U32), l}def W64.mul(a: W64, b: W64) -> W64: match a b: case W64{+ah, +al} W64{+bh, +bl}: W64.mul.of(((al * bh) + (ah * bl) : U32), mul32(al, bl))# Rotate left by k, for 0 < k < 32; j is 32 - k.def W64.rotl(+k: Nat, +j: Nat, a: W64) -> W64: match a: case W64{+h, +l}: W64{((h << k) .|. (l >> j) : U32), ((l << k) .|. (h >> j) : U32)}def W64.swap(a: W64) -> W64: match a: case W64{h, l}: W64{l, h}# Shift right by k, for 0 < k < 32; j is 32 - k.def W64.shr(+k: Nat, +j: Nat, a: W64) -> W64: match a: case W64{+h, +l}: W64{(h >> k : U32), ((l >> k) .|. (h << j) : U32)}def W64.lo(a: W64) -> U32: match a: case W64{h, l}: ldef rotl32(+x: U32, +k: Nat, +j: Nat) -> U32: ((x << k) .|. (x >> j) : U32)# Folds f over n words from word i on. r holds the array and word i.def wfold(~T: Type, ~f: T -> @+c: U32 -> T, n: Nat, r: Array<U32> & U32, +i: U32, acc: T) -> Array<U32> & T: match n: case 0n: (a, w) = r (a, acc) case 1n+p: (a, +w) = r +j = (i + 1 : U32) wfold(~T, ~f, p, Array.get(U32, a, j), j, f(acc, w))def wfrom(~T: Type, ~f: T -> @+c: U32 -> T, n: Nat, a: Array<U32>, +i: U32, acc: T) -> Array<U32> & T: wfold(~T, ~f, n, Array.get(U32, a, i), i, acc)# Words i and i + 1 as one little-endian 64-bit lane.def get2.of(+lo: U32, r: Array<U32> & U32) -> Array<U32> & W64: (a, +hi) = r (a, W64{hi, lo})def get2.lo(+i: U32, r: Array<U32> & U32) -> Array<U32> & W64: (a, +lo) = r get2.of(lo, Array.get(U32, a, (i + 1 : U32)))def get2(a: Array<U32>, +i: U32) -> Array<U32> & W64: get2.lo(i, Array.get(U32, a, i))# Folds f over n 64-bit lanes from word i on. r holds the array and the lane at i.def dfold(~T: Type, ~f: T -> @+m: W64 -> T, n: Nat, r: Array<U32> & W64, +i: U32, acc: T) -> Array<U32> & T: match n: case 0n: (a, m) = r (a, acc) case 1n+p: (a, +m) = r +j = (i + 2 : U32) dfold(~T, ~f, p, get2(a, j), j, f(acc, m))def dfrom(~T: Type, ~f: T -> @+m: W64 -> T, n: Nat, a: Array<U32>, +i: U32, acc: T) -> Array<U32> & T: dfold(~T, ~f, n, get2(a, i), i, acc)# Folds f over the low k bytes of w, lowest first.def tail(~T: Type, ~f: T -> @+c: U32 -> T, k: Nat, +w: U32, acc: T) -> T: match k: case 0n: acc case 1n+p: tail(~T, ~f, p, (w >> 8n : U32), f(acc, (w .&. 255 : U32)))def bytewise.last(~T: Type, ~byte: T -> @+c: U32 -> T, +len: U32, acc: T, r: Array<U32> & U32) -> Bytes.Bytes & T: (a, +w) = r (Bytes.Bytes{len, a}, tail(~T, ~byte, U32.to_nat((len .&. 3 : U32)), w, acc))def bytewise.rest(~T: Type, ~byte: T -> @+c: U32 -> T, +len: U32, r: Array<U32> & T) -> Bytes.Bytes & T: (a, acc) = r bytewise.last(~T, ~byte, len, acc, Array.get(U32, a, (len >> 2n : U32)))# A hash that eats one byte at a time: word takes the four bytes of a word, byte one.def bytewise(~T: Type, ~byte: T -> @+c: U32 -> T, ~word: T -> @+c: U32 -> T, b: Bytes.Bytes, acc: T) -> Bytes.Bytes & T: Bytes.Bytes{+len, buf} = b bytewise.rest(~T, ~byte, len, wfrom(~T, ~word, U32.to_nat((len >> 2n : U32)), buf, 0, acc))# FNV-1a (draft-eastlake-fnv), 32 and 64 bits.def fnv32.byte(h: U32, +c: U32) -> U32: ((h .^. c) * 16777619 : U32)def fnv32.word(h: U32, +w: U32) -> U32: fnv32.byte(fnv32.byte(fnv32.byte(fnv32.byte(h, (w .&. 255 : U32)), ((w >> 8n) .&. 255 : U32)), ((w >> 16n) .&. 255 : U32)), (w >> 24n : U32))def fnv1a32(b: Bytes.Bytes) -> Bytes.Bytes & U32: bytewise(~U32, ~fnv32.byte, ~fnv32.word, b, 2166136261)def fnv64.byte(h: W64, +c: U32) -> W64: match h: case W64{hi, lo}: W64.mul(W64{hi, (lo .^. c : U32)}, W64{256, 435})def fnv64.word(h: W64, +w: U32) -> W64: fnv64.byte(fnv64.byte(fnv64.byte(fnv64.byte(h, (w .&. 255 : U32)), ((w >> 8n) .&. 255 : U32)), ((w >> 16n) .&. 255 : U32)), (w >> 24n : U32))def fnv1a64(b: Bytes.Bytes) -> Bytes.Bytes & W64: bytewise(~W64, ~fnv64.byte, ~fnv64.word, b, W64{3421674724, 2216829733})# CRC-32 (ISO-HDLC, as in gzip and zlib): reflected, polynomial 0xEDB88320.def crc.bit(+c: U32) -> U32: Bool.pick(U32, U32.is_eq((c .&. 1 : U32), 1), ((c >> 1n) .^. 3988292384 : U32), (c >> 1n : U32))def crc.bits(k: Nat, +c: U32) -> U32: match k: case 0n: c case 1n+p: crc.bits(p, crc.bit(c))def crc.fill(k: Nat, +i: U32, a: Array<U32>) -> Array<U32>: match k: case 0n: a case 1n+p: crc.fill(p, (i + 1 : U32), Array.set(U32, a, i, crc.bits(8n, i)))# The table and the running register.type Crc is Type: Crc{t: Array<U32>, h: U32}def crc.mix(+c: U32, r: Array<U32> & U32) -> Crc: (a, +t) = r Crc{a, (t .^. (c >> 8n) : U32)}def crc.byte(st: Crc, +c: U32) -> Crc: Crc{a, +h} = st crc.mix(h, Array.get(U32, a, ((h .^. c) .&. 255 : U32)))def crc.word(st: Crc, +w: U32) -> Crc: crc.byte(crc.byte(crc.byte(crc.byte(st, (w .&. 255 : U32)), ((w >> 8n) .&. 255 : U32)), ((w >> 16n) .&. 255 : U32)), (w >> 24n : U32))def crc.fin(r: Bytes.Bytes & Crc) -> Bytes.Bytes & U32: (b, Crc{t, +h}) = r (b, (h .^. 4294967295 : U32))def crc32(b: Bytes.Bytes) -> Bytes.Bytes & U32: crc.fin(bytewise(~Crc, ~crc.byte, ~crc.word, b, Crc{crc.fill(256n, 0, Array.new(U32, 8n, 0)), 4294967295}))# Adler-32 (RFC 1950 §9). The state is the checksum itself: s2 << 16 | s1.# A word takes mod 65521 once, after four bytes; no sum reaches 2^32 first.def adler.of(+s1: U32, +s2: U32) -> U32: (((s2 % 65521) << 16n) .|. (s1 % 65521) : U32)def adler.byte(h0: U32, +c: U32) -> U32: +h = h0 +s1 = ((h .&. 65535) + c : U32) adler.of(s1, ((h >> 16n) + s1 : U32))def adler.word(h0: U32, +w: U32) -> U32: +h = h0 +a0 = ((h .&. 65535) + (w .&. 255) : U32) +a1 = (a0 + ((w >> 8n) .&. 255) : U32) +a2 = (a1 + ((w >> 16n) .&. 255) : U32) +a3 = (a2 + (w >> 24n) : U32) adler.of(a3, ((h >> 16n) + a0 + a1 + a2 + a3 : U32))def adler32(b: Bytes.Bytes) -> Bytes.Bytes & U32: bytewise(~U32, ~adler.byte, ~adler.word, b, 1)# xxHash32 (XXH32, xxHash spec 0.1.1).type V4 is Data: V4{a: U32, b: U32, c: U32, d: U32}def x32.round(+acc: U32, +x: U32) -> U32: (rotl32((acc + x * 2246822519 : U32), 13n, 19n) * 2654435761 : U32)# The four accumulators take lanes in turn: v1 eats this word and moves to the back.def x32.lane(v: V4, +w: U32) -> V4: match v: case V4{a, b, c, d}: V4{b, c, d, x32.round(a, w)}def x32.merge(r: Array<U32> & V4) -> Array<U32> & U32: (buf, V4{+a, +b, +c, +d}) = r (buf, (rotl32(a, 1n, 31n) + rotl32(b, 7n, 25n) + rotl32(c, 12n, 20n) + rotl32(d, 18n, 14n) : U32))def x32.word(h: U32, +w: U32) -> U32: (rotl32((h + w * 3266489917 : U32), 17n, 15n) * 668265263 : U32)def x32.byte(h: U32, +c: U32) -> U32: (rotl32((h + c * 374761393 : U32), 11n, 21n) * 2654435761 : U32)def x32.aval.c(+h: U32) -> U32: (h .^. (h >> 16n) : U32)def x32.aval.b(+h: U32) -> U32: x32.aval.c(((h .^. (h >> 13n)) * 3266489917 : U32))def x32.aval(+h: U32) -> U32: x32.aval.b(((h .^. (h >> 15n)) * 2246822519 : U32))def x32.tail(+len: U32, +h: U32, r: Array<U32> & U32) -> Bytes.Bytes & U32: (a, +w) = r (Bytes.Bytes{len, a}, x32.aval(tail(~U32, ~x32.byte, U32.to_nat((len .&. 3 : U32)), w, h)))def x32.rest(+len: U32, r: Array<U32> & U32) -> Bytes.Bytes & U32: (a, +h) = r x32.tail(len, h, Array.get(U32, a, (len >> 2n : U32)))def x32.mid(+len: U32, r: Array<U32> & U32) -> Bytes.Bytes & U32: (a, +h) = r x32.rest(len, wfrom(~U32, ~x32.word, U32.to_nat(((len .&. 15) >> 2n : U32)), a, ((len >> 4n) << 2n : U32), (h + len : U32)))def x32.start(big: Bool, +len: U32, +seed: U32, a: Array<U32>) -> Array<U32> & U32: match big: case True{}: 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)})) case False{}: (a, (seed + 374761393 : U32))def xxh32(b: Bytes.Bytes, +seed: U32) -> Bytes.Bytes & U32: Bytes.Bytes{+len, buf} = b x32.mid(len, x32.start(U32.is_le(16, len), len, seed, buf))# xxHash64 (XXH64, xxHash spec 0.1.1).type V64 is Data: V64{a: W64, b: W64, c: W64, d: W64}def x64.P1() -> W64: W64{2654435761, 2246822535}def x64.P2() -> W64: W64{3266489917, 668265295}def x64.P3() -> W64: W64{374761393, 2654435833}def x64.P4() -> W64: W64{2246822519, 3266489955}def x64.P5() -> W64: W64{668265263, 374761413}def x64.round(acc: W64, x: W64) -> W64: W64.mul(W64.rotl(31n, 1n, W64.add(acc, W64.mul(x, x64.P2()))), x64.P1())def x64.lane(v: V64, +m: W64) -> V64: match v: case V64{a, b, c, d}: V64{b, c, d, x64.round(a, m)}def x64.fold(h: W64, v: W64) -> W64: W64.add(W64.mul(W64.xor(h, x64.round(W64{0, 0}, v)), x64.P1()), x64.P4())def x64.merge(r: Array<U32> & V64) -> Array<U32> & W64: (buf, V64{+a, +b, +c, +d}) = r +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))) (buf, x64.fold(x64.fold(x64.fold(x64.fold(h, a), b), c), d))def x64.word(h: W64, +m: W64) -> W64: W64.add(W64.mul(W64.rotl(27n, 5n, W64.xor(h, x64.round(W64{0, 0}, m))), x64.P1()), x64.P4())def x64.byte(h: W64, +c: U32) -> W64: W64.mul(W64.rotl(11n, 21n, W64.xor(h, W64.mul(W64{0, c}, x64.P5()))), x64.P1())def x64.four(h: W64, +w: U32) -> W64: W64.add(W64.mul(W64.rotl(23n, 9n, W64.xor(h, W64.mul(W64{0, w}, x64.P1()))), x64.P2()), x64.P3())def x64.aval.c(h: W64) -> W64: match h: case W64{+hi, lo}: W64{hi, (lo .^. hi : U32)}def x64.aval.b(+h: W64) -> W64: x64.aval.c(W64.mul(W64.xor(h, W64.shr(29n, 3n, h)), x64.P3()))def x64.aval(h: W64) -> W64: match h: case W64{+hi, lo}: x64.aval.b(W64.mul(W64{hi, (lo .^. (hi >> 1n) : U32)}, x64.P2()))# The last len % 8 bytes: a 4-byte lane when there is one, then single bytes.def x64.bytes(four: Bool, +k: Nat, h: W64, m: W64) -> W64: match four: case True{}: match m: case W64{+hi, +lo}: tail(~W64, ~x64.byte, k, hi, x64.four(h, lo)) case False{}: match m: case W64{hi, +lo}: tail(~W64, ~x64.byte, k, lo, h)def x64.tail(+len: U32, +h: W64, r: Array<U32> & W64) -> Bytes.Bytes & W64: (a, m) = r (Bytes.Bytes{len, a}, x64.aval(x64.bytes(U32.is_ne((len .&. 4 : U32), 0), U32.to_nat((len .&. 3 : U32)), h, m)))def x64.rest(+len: U32, r: Array<U32> & W64) -> Bytes.Bytes & W64: (a, h) = r x64.tail(len, h, get2(a, ((len >> 3n) << 1n : U32)))def x64.mid(+len: U32, r: Array<U32> & W64) -> Bytes.Bytes & W64: (a, h) = r 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})))def x64.start(big: Bool, +len: U32, +seed: W64, a: Array<U32>) -> Array<U32> & W64: match big: case True{}: 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})})) case False{}: (a, W64.add(seed, x64.P5()))def xxh64(b: Bytes.Bytes, +seed: W64) -> Bytes.Bytes & W64: Bytes.Bytes{+len, buf} = b x64.mid(len, x64.start(U32.is_le(32, len), len, seed, buf))# SipHash-1-3 (Aumasson and Bernstein, 2012): one round per block, three to finish.type S4 is Data: S4{v0: W64, v1: W64, v2: W64, v3: W64}def sip.round(s: S4) -> S4: S4{v0, +v1, v2, +v3} = s +a0 = W64.add(v0, v1) +b1 = W64.xor(W64.rotl(13n, 19n, v1), a0) +a2 = W64.add(v2, v3) +b3 = W64.xor(W64.rotl(16n, 16n, v3), a2) +c0 = W64.add(W64.swap(a0), b3) +c2 = W64.add(a2, b1) S4{c0, W64.xor(W64.rotl(17n, 15n, b1), c2), W64.swap(c2), W64.xor(W64.rotl(21n, 11n, b3), c0)}def sip.post(+m: W64, s: S4) -> S4: S4{v0, v1, v2, v3} = s S4{W64.xor(v0, m), v1, v2, v3}def sip.block(s: S4, +m: W64) -> S4: S4{v0, v1, v2, v3} = s sip.post(m, sip.round(S4{v0, v1, v2, W64.xor(v3, m)}))def sip.fin(s: S4) -> W64: S4{v0, v1, v2, v3} = s W64.xor(W64.xor(v0, v1), W64.xor(v2, v3))def sip.end(s: S4) -> W64: S4{v0, v1, v2, v3} = s sip.fin(sip.round(sip.round(sip.round(S4{v0, v1, W64.xor(v2, W64{0, 255}), v3}))))# The last block: the len % 8 bytes left, and len mod 256 in the top byte.def sip.last(+len: U32, r: Array<U32> & W64, s: S4) -> Bytes.Bytes & W64: (a, W64{+hi, +lo}) = r +k = (len .&. 7 : U32) +top = ((len .&. 255) << 24n : U32) (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)})))def sip.rest(+len: U32, r: Array<U32> & S4) -> Bytes.Bytes & W64: (a, s) = r sip.last(len, get2(a, ((len >> 3n) << 1n : U32)), s)def siphash13(b: Bytes.Bytes, +k0: W64, +k1: W64) -> Bytes.Bytes & W64: Bytes.Bytes{+len, buf} = b 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})}))# The same hashes over a byte string. ponytail: copies to Bytes; hash short strings in place if the copy shows up in profiles.def v32(r: Bytes.Bytes & U32) -> U32: (b, h) = r hdef v64(r: Bytes.Bytes & W64) -> W64: (b, h) = r hdef fnv1a32.str(+s: String) -> U32: v32(fnv1a32(Bytes.from_string(s)))def fnv1a64.str(+s: String) -> W64: v64(fnv1a64(Bytes.from_string(s)))def xxh32.str(+s: String, +seed: U32) -> U32: v32(xxh32(Bytes.from_string(s), seed))def xxh64.str(+s: String, +seed: W64) -> W64: v64(xxh64(Bytes.from_string(s), seed))def siphash13.str(+s: String, +k0: W64, +k1: W64) -> W64: v64(siphash13(Bytes.from_string(s), k0, k1))def crc32.str(+s: String) -> U32: v32(crc32(Bytes.from_string(s)))def adler32.str(+s: String) -> U32: v32(adler32(Bytes.from_string(s)))