murmur3.nx source
↩ module page · 97 lines · 3144 B
1// murmur3.nx -- MurmurHash3 (Austin Appleby 2008/2011).
2//
3// Fast non-cryptographic hash. Distributes well across the
4// output range, fast (4-byte chunks), suitable for hash tables
5// when adversarial inputs aren't a concern (otherwise use
6// siphash.nx).
7//
8// Used by: ClickHouse, Cassandra, Hadoop, Lucene, RocksDB
9// secondary indices, Bloom filters, sketch data structures.
10//
11// We ship only the 32-bit variant (MurmurHash3_x86_32) because
12// it's the most widely deployed. 64-bit and 128-bit variants
13// exist (x86_128, x64_128) and produce different output.
14//
15// Invariants:
16// MM1 Pure function: hash(seed, bytes) is deterministic; no
17// global state, no random.
18// MM2 Output is exactly 32 bits packed into i64's low half.
19// MM3 NOT cryptographically secure. An attacker can craft
20// keys that collide; never use as a MAC or to defend
21// against algorithmic-complexity attacks on hash tables
22// in adversarial contexts.
23
24import "syscalls.nx"
25
26const MM_C1: i64 = 0xCC9E2D51
27const MM_C2: i64 = 0x1B873593
28const U32_BITS: i64 = 0xFFFFFFFF
29
30// 32-bit left rotate.
31func mm_rotl32(x: i64, r: i64) -> i64 {
32 let low: i64 = (x << r) & U32_BITS
33 let high: i64 = (x & U32_BITS) >> (32 - r)
34 return low | high
35}
36
37// Read 4 bytes little-endian.
38func mm_load_u32_le(buf: *u8, off: i64) -> i64 {
39 let b0: i64 = buf[off + 0]
40 let b1: i64 = buf[off + 1]
41 let b2: i64 = buf[off + 2]
42 let b3: i64 = buf[off + 3]
43 return (b0 | (b1 << 8) | (b2 << 16) | (b3 << 24)) & U32_BITS
44}
45
46// MurmurHash3_x86_32. Given seed + input bytes, returns 32-bit
47// hash in the low bits of an i64.
48func murmur3_32(seed: i64, key: *u8, len: i64) -> i64 {
49 var h: i64 = seed & U32_BITS
50 let n_blocks: i64 = len / 4
51
52 // Body: 4-byte chunks.
53 var i: i64 = 0
54 while i < n_blocks {
55 var k: i64 = mm_load_u32_le(key, i * 4)
56 k = (k * MM_C1) & U32_BITS
57 k = mm_rotl32(k, 15)
58 k = (k * MM_C2) & U32_BITS
59 h = h ^ k
60 h = mm_rotl32(h, 13)
61 h = ((h * 5) + 0xE6546B64) & U32_BITS
62 i = i + 1
63 }
64
65 // Tail: 1-3 leftover bytes.
66 let tail_off: i64 = n_blocks * 4
67 let rem: i64 = len - tail_off
68 var k1: i64 = 0
69 if rem >= 3 { k1 = k1 ^ (key[tail_off + 2] << 16) }
70 if rem >= 2 { k1 = k1 ^ (key[tail_off + 1] << 8) }
71 if rem >= 1 {
72 k1 = k1 ^ key[tail_off + 0]
73 k1 = (k1 * MM_C1) & U32_BITS
74 k1 = mm_rotl32(k1, 15)
75 k1 = (k1 * MM_C2) & U32_BITS
76 h = h ^ k1
77 }
78
79 // Finalisation mix.
80 h = h ^ len
81 h = h ^ ((h >> 16) & U32_BITS)
82 h = (h * 0x85EBCA6B) & U32_BITS
83 h = h ^ ((h >> 13) & U32_BITS)
84 h = (h * 0xC2B2AE35) & U32_BITS
85 h = h ^ ((h >> 16) & U32_BITS)
86 return h & U32_BITS
87}
88
89// Compile-only smoke.
90func main() -> i64 {
91 let key: *u8 = "Hello, World!"
92 let h: i64 = murmur3_32(0, key, 13)
93 // Reference KAT: murmur3_32("Hello, World!", seed=0) =
94 // 0x24884CBA. Can't verify exact value without execution.
95 if h == 0 { return 1 }
96 return 0
97}