src/math/hash.bend

bend-collections-laws-containers@1.0.0.0 · 20 lines · 0 definitions

1import Base
2
3# 32-bit hashing primitives for open-addressing tables.
4#
5#   mix(h, c)          one step of a multiply-xor string hash: (h ^ c) * phi32
6#   bucket(w, mask)    the home bucket of check word w in a table of mask + 1
7#                      buckets: Fibonacci hashing, then the high half folded
8#                      into the low bits before masking
9
10def phi32() -> U32:
11  2654435761
12
13def mix(+h: U32, +c: U32) -> U32:
14  U32.mul(U32.xor(h, c), phi32())
15
16def fold(+x: U32, +mask: U32) -> U32:
17  U32.and(U32.xor(x, U32.shrn(x, 16n)), mask)
18
19def bucket(+w: U32, +mask: U32) -> U32:
20  fold(U32.mul(w, phi32()), mask)