nx_bloom.nx source
↩ module page · 145 lines · 5693 B
1// bloom.nx -- Bloom filter (Burton Howard Bloom, 1970).
2//
3// Probabilistic set membership: "probably present" or
4// "definitely absent". Uses k independent hash functions to
5// set k bits per insert; a query returns "absent" iff any of
6// k bits is unset.
7//
8// Used for: cache-miss avoidance (Bigtable, Cassandra), spell-
9// checkers, network protocol scoping (BitTorrent peer exchange),
10// password leak detection (HIBP k-anonymity prefix).
11//
12// Trade-off: memory + time efficient at the cost of allowing
13// false positives (no false negatives). For target false-
14// positive rate p, expected items n:
15// m = -n * ln(p) / (ln(2)^2) bits of bitmap
16// k = (m / n) * ln(2) hash functions
17// Caller picks (m, k) at construction.
18//
19// Invariants:
20// BL1 False NEGATIVE rate is exactly 0. If a key was
21// inserted, query returns true.
22// BL2 False positive rate depends on (m, k, n) per the
23// formula above. Caller responsibility.
24// BL3 Capacity (cap_bits) must be a power of two so we can
25// mask instead of modulo. Hash bits map to bit indices
26// via & (cap_bits - 1).
27// BL4 Two hash functions are mixed via the "Kirsch-Mitzenmacher
28// double hashing" trick (h1 + i*h2 for i = 0..k-1) to
29// cheaply produce k independent-enough hashes from two.
30//
31// nx_safety_envelope:
32// intended_use: "Bloom filter -- probabilistic set-membership
33// for dedup, cache lookup, malware-hash check"
34// sil_target: SIL1 (probabilistic; false-positive rate
35// is documented)
36// asil_target: QM
37// dal_target: NONE
38// evidence: [Bloom_1970_canonical_basis,
39// Kirsch_Mitzenmacher_2006_double_hashing,
40// sealed_verdict_enum, no_FP]
41// hazard_register: [bug-tape-false-positive-rate-not-documented,
42// bug-tape-hash-collision-amplification,
43// bug-tape-bit-array-overflow-attack]
44// residual_risk: "Bloom filters NEVER produce false negatives
45// but CAN produce false positives; caller MUST
46// verify positive matches against authoritative
47// source when correctness matters. Substrate
48// documents the FPR formula but cannot enforce
49// it on misconfigured callers."
50// verdict: NOT_YET_EVALUATED
51
52import "nx_syscalls.nx"
53import "nx_murmur3.nx"
54const K_MAGIC_1024: i64 = 1024
55
56struct Bloom {
57 bits: *u8,
58 cap: i64, // bitmap size in bits (power of 2)
59 mask: i64, // cap - 1, for modulo-by-mask
60 k: i64, // number of hash functions
61}
62
63func bl_is_pow2(n: i64) -> i64 {
64 if n < 8 { return 0 }
65 if (n & (n - 1)) != 0 { return 0 }
66 return 1
67}
68
69// Allocate a Bloom filter with `cap_bits` bitmap (must be power
70// of 2, >= 8) and k hash functions per insert/query.
71func bloom_new(cap_bits: i64, k: i64) -> *Bloom {
72 if bl_is_pow2(cap_bits) != 1 { return 0 as *Bloom }
73 if k < 1 { return 0 as *Bloom }
74 let bf_raw: *u8 = sys_mmap(64)
75 let bf: *Bloom = bf_raw as *Bloom
76 bf.bits = sys_mmap(cap_bits / 8)
77 var i: i64 = 0
78 while i < cap_bits / 8 { bf.bits[i] = 0; i = i + 1 }
79 bf.cap = cap_bits
80 bf.mask = cap_bits - 1
81 bf.k = k
82 return bf
83}
84
85// Set bit at position `bit_idx`.
86func bl_set_bit(bf: *Bloom, bit_idx: i64) -> i64 {
87 let byte_idx: i64 = (bit_idx >> 3) & ((bf.cap >> 3) - 1)
88 let bit_pos: i64 = bit_idx & 7
89 bf.bits[byte_idx] = bf.bits[byte_idx] | (1 << bit_pos)
90 return 0
91}
92
93// Test bit at position. Returns 0 or 1.
94func bl_get_bit(bf: *Bloom, bit_idx: i64) -> i64 {
95 let byte_idx: i64 = (bit_idx >> 3) & ((bf.cap >> 3) - 1)
96 let bit_pos: i64 = bit_idx & 7
97 return (bf.bits[byte_idx] >> bit_pos) & 1
98}
99
100// Insert a key. Sets k bits derived from two-hash double-hashing.
101func bloom_insert(bf: *Bloom, key: *u8, key_len: i64) -> i64 {
102 let h1: i64 = murmur3_32(0, key, key_len)
103 let h2: i64 = murmur3_32(1, key, key_len)
104 var i: i64 = 0
105 while i < bf.k {
106 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
107 let bit_idx: i64 = combined & bf.mask
108 bl_set_bit(bf, bit_idx)
109 i = i + 1
110 }
111 return 0
112}
113
114// Query a key. Returns 1 if all k bits are set ("probably
115// present"); 0 if any bit is unset ("definitely absent").
116func bloom_contains(bf: *Bloom, key: *u8, key_len: i64) -> i64 {
117 let h1: i64 = murmur3_32(0, key, key_len)
118 let h2: i64 = murmur3_32(1, key, key_len)
119 var i: i64 = 0
120 while i < bf.k {
121 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
122 let bit_idx: i64 = combined & bf.mask
123 if bl_get_bit(bf, bit_idx) == 0 { return 0 }
124 i = i + 1
125 }
126 return 1
127}
128
129// Compile-only smoke.
130func main() -> i64 {
131 let bf: *Bloom = bloom_new(K_MAGIC_1024, 4)
132 if bf == (0 as *Bloom) { return 1 }
133 bloom_insert(bf, "alice", 5)
134 bloom_insert(bf, "bob", 3)
135 if bloom_contains(bf, "alice", 5) != 1 { return 2 }
136 if bloom_contains(bf, "bob", 3) != 1 { return 3 }
137 // "carol" should be ABSENT (not inserted).
138 if bloom_contains(bf, "carol", 5) != 0 {
139 // could be a false positive at 1024 bits with 2 inserts
140 // -- vanishingly unlikely but technically allowed. Only
141 // fail if it consistently returns true for many absent
142 // keys (smoke is a single check; tolerate).
143 }
144 return 0
145}