nx_sketch_bloom.nx source
↩ module page · 168 lines · 5897 B
1// sketch_bloom.nx -- Bloom filter v2 (sovereign-tier with typed envelope).
2//
3// Burton Howard Bloom 1970. Tracks n_inserted so the FPR envelope
4// reflects ACTUAL load, not just design-time spec. Companion to the
5// older runtime/bloom.nx (which lacks the envelope + counted state +
6// proper FPR-by-load reporting).
7//
8// FPR FORMULA (Bloom 1970):
9// FPR = (1 - e^(-kn/m))^k
10// For k = (m/n) ln(2) optimal: FPR = 0.6185^(m/n)
11//
12// We can't compute exp / pow in i64-only. Conservative approach:
13// tabulate FPR-by-(m/n) at integer ratios assuming OPTIMAL k. If the
14// caller chose non-optimal k, real FPR is worse than reported -- we
15// document this. v2 will swap in a tighter integer approximation.
16//
17// LOSSLESS-LANGUAGE DISCIPLINE (doc 20):
18// contains -> 1 means "probably present" with envelope FPR; 0 means
19// "definitely absent" with envelope FPR = 0. Both cases ship the
20// ApproxI64 with NX_ENV_ABS / conf_ppb = 1e9 - fpr_ppb.
21//
22// Complements sketch_cuckoo.nx (which supports delete). Bloom is more
23// space-efficient at high FPR; Cuckoo wins below ~3% FPR with delete.
24
25// nx_safety_envelope:
26// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
27// sil_target: SIL1
28// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
29// verdict: NOT_YET_EVALUATED
30
31import "nx_syscalls.nx"
32import "nx_murmur3.nx"
33import "nx_sketch_types.nx"
34
35struct BloomS {
36 bits: *u8,
37 cap_bits: i64, // power of 2
38 mask: i64, // cap_bits - 1
39 k: i64, // hash functions
40 n_inserted: i64,
41}
42
43// === alloc =======================================================
44
45func nx_bs_is_pow2(n: i64) -> i64 {
46 if n < 64 { return 0 }
47 if (n & (n - 1)) != 0 { return 0 }
48 return 1
49}
50
51func nx_bloom_alloc(cap_bits: i64, k: i64) -> *BloomS {
52 if nx_bs_is_pow2(cap_bits) != 1 { return 0 as *BloomS }
53 if k < 1 { return 0 as *BloomS }
54 if k > 32 { return 0 as *BloomS }
55 let raw: *u8 = sys_mmap(48)
56 let bf: *BloomS = raw as *BloomS
57 let bytes: i64 = cap_bits / 8
58 bf.bits = sys_mmap(bytes)
59 var i: i64 = 0
60 while i < bytes {
61 bf.bits[i] = 0
62 i = i + 1
63 }
64 bf.cap_bits = cap_bits
65 bf.mask = cap_bits - 1
66 bf.k = k
67 bf.n_inserted = 0
68 return bf
69}
70
71// === bit helpers ================================================
72
73func nx_bloom_set_bit(bf: *BloomS, bit_idx: i64) -> i64 {
74 let byte_idx: i64 = bit_idx >> 3
75 let bit_pos: i64 = bit_idx & 7
76 bf.bits[byte_idx] = bf.bits[byte_idx] | (1 << bit_pos)
77 return 0
78}
79
80func nx_bloom_get_bit(bf: *BloomS, bit_idx: i64) -> i64 {
81 let byte_idx: i64 = bit_idx >> 3
82 let bit_pos: i64 = bit_idx & 7
83 return (bf.bits[byte_idx] >> bit_pos) & 1
84}
85
86// === insert / contains ==========================================
87//
88// Kirsch-Mitzenmacher double hashing: derive k bit positions from
89// two base hashes via (h1 + i*h2) for i in 0..k-1.
90
91func nx_bloom_insert(bf: *BloomS, key: *u8, len: i64) -> i64 {
92 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
93 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
94 var i: i64 = 0
95 while i < bf.k {
96 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
97 let bit_idx: i64 = combined & bf.mask
98 nx_bloom_set_bit(bf, bit_idx)
99 i = i + 1
100 }
101 bf.n_inserted = bf.n_inserted + 1
102 return 0
103}
104
105func nx_bloom_contains(bf: *BloomS, key: *u8, len: i64) -> i64 {
106 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
107 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
108 var i: i64 = 0
109 while i < bf.k {
110 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
111 let bit_idx: i64 = combined & bf.mask
112 if nx_bloom_get_bit(bf, bit_idx) == 0 { return 0 }
113 i = i + 1
114 }
115 return 1
116}
117
118// === FPR estimation =============================================
119//
120// Assuming OPTIMAL k (= (m/n) ln(2)), FPR = 0.6185^(m/n). We
121// tabulate by integer m/n ratio. Non-optimal k -> WORSE FPR.
122//
123// Real load: m/n where n = n_inserted, m = cap_bits. If n == 0,
124// FPR = 0.
125
126func nx_bloom_fpr_ppb(bf: *BloomS) -> i64 {
127 if bf.n_inserted == 0 { return 0 }
128 let m_over_n: i64 = bf.cap_bits / bf.n_inserted
129 if m_over_n <= 0 { return 1000000000 } // overloaded -> ~100% FPR
130 if m_over_n == 1 { return 618500000 } // 61.85%
131 if m_over_n == 2 { return 382500000 } // 38.25%
132 if m_over_n == 3 { return 236600000 } // 23.66%
133 if m_over_n == 4 { return 146300000 } // 14.63%
134 if m_over_n == 5 { return 90500000 } // 9.05%
135 if m_over_n == 6 { return 55960000 } // 5.60%
136 if m_over_n == 7 { return 34630000 } // 3.46%
137 if m_over_n == 8 { return 21420000 } // 2.14%
138 if m_over_n == 10 { return 8160000 } // 0.816%
139 if m_over_n == 12 { return 3110000 } // 0.311%
140 if m_over_n == 16 { return 458000 } // 0.0458%
141 if m_over_n == 20 { return 67500 } // 0.00675%
142 if m_over_n == 24 { return 9930 } // 0.000993%
143 if m_over_n == 32 { return 216 } // 2.16e-7
144 // m/n above 32: vanishing.
145 return 0
146}
147
148// === typed query ================================================
149
150func nx_bloom_query(bf: *BloomS, key: *u8, len: i64) -> *ApproxI64 {
151 let present: i64 = nx_bloom_contains(bf, key, len)
152 let fpr: i64 = nx_bloom_fpr_ppb(bf)
153 return nx_approx_new(present, NX_ENV_ABS, 0,
154 1000000000 - fpr,
155 NX_MATURITY_REFERENCE_IMPL,
156 NX_ADV_HONEST)
157}
158
159// === introspection ==============================================
160
161func nx_bloom_memory_bytes(bf: *BloomS) -> i64 {
162 return 48 + bf.cap_bits / 8
163}
164
165func nx_bloom_load_ppt(bf: *BloomS) -> i64 {
166 if bf.cap_bits == 0 { return 0 }
167 return (bf.n_inserted * 1000) / bf.cap_bits
168}