1	import 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	
10	def phi32() -> U32:
11	  2654435761
12	
13	def mix(+h: U32, +c: U32) -> U32:
14	  U32.mul(U32.xor(h, c), phi32())
15	
16	def fold(+x: U32, +mask: U32) -> U32:
17	  U32.and(U32.xor(x, U32.shrn(x, 16n)), mask)
18	
19	def bucket(+w: U32, +mask: U32) -> U32:
20	  fold(U32.mul(w, phi32()), mask)