nx_murmur3.nx source
↩ module page · 103 lines · 3301 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
24// nx_safety_envelope:
25// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
26// sil_target: SIL1
27// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
28// verdict: NOT_YET_EVALUATED
29
30import "nx_syscalls.nx"
31
32const MM_C1: i64 = 0xCC9E2D51
33const MM_C2: i64 = 0x1B873593
34const U32_BITS: i64 = 0xFFFFFFFF
35
36// 32-bit left rotate.
37func mm_rotl32(x: i64, r: i64) -> i64 {
38 let low: i64 = (x << r) & U32_BITS
39 let high: i64 = (x & U32_BITS) >> (32 - r)
40 return low | high
41}
42
43// Read 4 bytes little-endian.
44func mm_load_u32_le(buf: *u8, off: i64) -> i64 {
45 let b0: i64 = buf[off + 0]
46 let b1: i64 = buf[off + 1]
47 let b2: i64 = buf[off + 2]
48 let b3: i64 = buf[off + 3]
49 return (b0 | (b1 << 8) | (b2 << 16) | (b3 << 24)) & U32_BITS
50}
51
52// MurmurHash3_x86_32. Given seed + input bytes, returns 32-bit
53// hash in the low bits of an i64.
54func murmur3_32(seed: i64, key: *u8, len: i64) -> i64 {
55 var h: i64 = seed & U32_BITS
56 let n_blocks: i64 = len / 4
57
58 // Body: 4-byte chunks.
59 var i: i64 = 0
60 while i < n_blocks {
61 var k: i64 = mm_load_u32_le(key, i * 4)
62 k = (k * MM_C1) & U32_BITS
63 k = mm_rotl32(k, 15)
64 k = (k * MM_C2) & U32_BITS
65 h = h ^ k
66 h = mm_rotl32(h, 13)
67 h = ((h * 5) + 0xE6546B64) & U32_BITS
68 i = i + 1
69 }
70
71 // Tail: 1-3 leftover bytes.
72 let tail_off: i64 = n_blocks * 4
73 let rem: i64 = len - tail_off
74 var k1: i64 = 0
75 if rem >= 3 { k1 = k1 ^ (key[tail_off + 2] << 16) }
76 if rem >= 2 { k1 = k1 ^ (key[tail_off + 1] << 8) }
77 if rem >= 1 {
78 k1 = k1 ^ key[tail_off + 0]
79 k1 = (k1 * MM_C1) & U32_BITS
80 k1 = mm_rotl32(k1, 15)
81 k1 = (k1 * MM_C2) & U32_BITS
82 h = h ^ k1
83 }
84
85 // Finalisation mix.
86 h = h ^ len
87 h = h ^ ((h >> 16) & U32_BITS)
88 h = (h * 0x85EBCA6B) & U32_BITS
89 h = h ^ ((h >> 13) & U32_BITS)
90 h = (h * 0xC2B2AE35) & U32_BITS
91 h = h ^ ((h >> 16) & U32_BITS)
92 return h & U32_BITS
93}
94
95// Compile-only smoke.
96func main() -> i64 {
97 let key: *u8 = "Hello, World!"
98 let h: i64 = murmur3_32(0, key, 13)
99 // Reference KAT: murmur3_32("Hello, World!", seed=0) =
100 // 0x24884CBA. Can't verify exact value without execution.
101 if h == 0 { return 1 }
102 return 0
103}