nx_sketch_counting_bloom.nx source
↩ module page · 253 lines · 9037 B
1// sketch_counting_bloom.nx -- Counting Bloom filter (Fan-Cao-Almeida-Broder 1998).
2//
3// Bloom filter where each "bit" is a c-bit COUNTER instead of a single
4// bit. Insert increments k counters; delete decrements them. Query
5// returns "present" iff all k counters > 0.
6//
7// Compared to other set-membership primitives we ship:
8// - sketch_bloom (v2): bits only; no delete; smallest memory
9// - sketch_cuckoo: stores fingerprints in buckets; supports delete;
10// constant-time lookups; preferred when FPR < 3%
11// - sketch_counting_bloom (this): COUNTERS not bits; supports delete;
12// simpler than Cuckoo when FPR matters less;
13// supports MULTI-SET membership (counter > N tests)
14//
15// FPR is the same as classic Bloom: (1 - e^(-kn/m))^k. Memory is
16// k * c times Bloom's (c is counter width in bits).
17//
18// COUNTER SATURATION: caps at 2^c - 1. Once saturated, subsequent
19// decrements DO NOT restore the original count (information loss).
20// We use c=4 (saturation at 15), trading slight FPR overcount risk
21// for memory.
22//
23// LOSSLESS-LANGUAGE DISCIPLINE:
24// nx_cbloom_query returns ApproxI64 with NX_ENV_ABS, param_a tracking
25// saturation events (so caller knows whether the filter has reached
26// information-loss territory).
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "nx_syscalls.nx"
35import "nx_murmur3.nx"
36import "nx_sketch_types.nx"
37
38const NX_CB_COUNTER_MAX: i64 = 15 // 4-bit counters; saturates at 15
39const NX_CB_COUNTERS_PER_BYTE: i64 = 2 // 4-bit packed two per byte
40
41struct CountingBloom {
42 counters: *u8, // packed 4-bit counters
43 cap_counters: i64, // total counter slots (power of 2)
44 mask: i64, // cap_counters - 1
45 k: i64, // hash functions
46 n_inserted: i64,
47 saturations: i64, // count of saturation events (information loss)
48}
49
50// === counter access (4 bits per slot, 2 per byte) ================
51
52func nx_cb_counter_get(cb: *CountingBloom, idx: i64) -> i64 {
53 let byte_idx: i64 = idx >> 1
54 let high: i64 = idx & 1
55 let b: i64 = cb.counters[byte_idx]
56 if high == 0 { return b & 0x0F }
57 return (b >> 4) & 0x0F
58}
59
60func nx_cb_counter_set(cb: *CountingBloom, idx: i64, value: i64) -> i64 {
61 let byte_idx: i64 = idx >> 1
62 let high: i64 = idx & 1
63 let b: i64 = cb.counters[byte_idx]
64 var v: i64 = value & 0x0F
65 if high == 0 {
66 cb.counters[byte_idx] = (b & 0xF0) | v
67 }
68 if high == 1 {
69 cb.counters[byte_idx] = (b & 0x0F) | (v << 4)
70 }
71 return 0
72}
73
74// === alloc =======================================================
75
76func nx_cb_is_pow2(n: i64) -> i64 {
77 if n < 16 { return 0 }
78 if (n & (n - 1)) != 0 { return 0 }
79 return 1
80}
81
82func nx_cb_alloc(cap_counters: i64, k: i64) -> *CountingBloom {
83 if nx_cb_is_pow2(cap_counters) != 1 { return 0 as *CountingBloom }
84 if k < 1 { return 0 as *CountingBloom }
85 if k > 16 { return 0 as *CountingBloom }
86 let raw: *u8 = sys_mmap(56)
87 let cb: *CountingBloom = raw as *CountingBloom
88 let bytes: i64 = cap_counters / NX_CB_COUNTERS_PER_BYTE
89 cb.counters = sys_mmap(bytes)
90 var i: i64 = 0
91 while i < bytes {
92 cb.counters[i] = 0
93 i = i + 1
94 }
95 cb.cap_counters = cap_counters
96 cb.mask = cap_counters - 1
97 cb.k = k
98 cb.n_inserted = 0
99 cb.saturations = 0
100 return cb
101}
102
103// === insert / contains / delete ==================================
104//
105// Insert: increment k counters; if any reaches NX_CB_COUNTER_MAX,
106// the saturation counter ticks (counters stick at max thereafter).
107//
108// Delete: decrement k counters by 1, with floor at 0. CAUTION: if
109// any counter is at NX_CB_COUNTER_MAX (saturated), it stays there
110// (information loss). Caller should track via nx_cb_saturations.
111
112func nx_cb_insert(cb: *CountingBloom, key: *u8, len: i64) -> i64 {
113 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
114 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
115 var i: i64 = 0
116 while i < cb.k {
117 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
118 let idx: i64 = combined & cb.mask
119 let cur: i64 = nx_cb_counter_get(cb, idx)
120 if cur >= NX_CB_COUNTER_MAX {
121 cb.saturations = cb.saturations + 1
122 }
123 if cur < NX_CB_COUNTER_MAX {
124 nx_cb_counter_set(cb, idx, cur + 1)
125 }
126 i = i + 1
127 }
128 cb.n_inserted = cb.n_inserted + 1
129 return 0
130}
131
132func nx_cb_contains(cb: *CountingBloom, key: *u8, len: i64) -> i64 {
133 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
134 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
135 var i: i64 = 0
136 while i < cb.k {
137 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
138 let idx: i64 = combined & cb.mask
139 if nx_cb_counter_get(cb, idx) == 0 { return 0 }
140 i = i + 1
141 }
142 return 1
143}
144
145func nx_cb_delete(cb: *CountingBloom, key: *u8, len: i64) -> i64 {
146 // Caller responsibility: only call delete on items that were
147 // inserted. Decrement all k counters by 1 (with floor 0, and
148 // saturated counters STAY at saturation).
149 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
150 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
151 var i: i64 = 0
152 while i < cb.k {
153 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
154 let idx: i64 = combined & cb.mask
155 let cur: i64 = nx_cb_counter_get(cb, idx)
156 if cur == 0 {
157 // Item was never inserted (or already deleted).
158 return -1
159 }
160 if cur < NX_CB_COUNTER_MAX {
161 nx_cb_counter_set(cb, idx, cur - 1)
162 }
163 // If saturated, leave at saturation -- info already lost.
164 i = i + 1
165 }
166 cb.n_inserted = cb.n_inserted - 1
167 return 0
168}
169
170// === minimum-counter ESTIMATE of element multiplicity =============
171//
172// MULTI-SET CAPABILITY (beyond classic Bloom):
173// For multi-sets (same item inserted N times), the minimum of the
174// k counters lower-bounds the true multiplicity. This works
175// because each insertion increments k counters by 1, so even the
176// MINIMUM counter for an item must have at least mult(item).
177//
178// Returns 0 if item not present.
179
180func nx_cb_estimate_multiplicity(cb: *CountingBloom, key: *u8, len: i64) -> i64 {
181 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
182 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
183 let combined0: i64 = h1 & cb.mask
184 var min_count: i64 = nx_cb_counter_get(cb, combined0)
185 var i: i64 = 1
186 while i < cb.k {
187 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
188 let idx: i64 = combined & cb.mask
189 let c: i64 = nx_cb_counter_get(cb, idx)
190 if c < min_count { min_count = c }
191 i = i + 1
192 }
193 return min_count
194}
195
196// === FPR (same formula as Bloom) ==================================
197
198func nx_cb_fpr_ppb(cb: *CountingBloom) -> i64 {
199 if cb.n_inserted == 0 { return 0 }
200 let m_over_n: i64 = cb.cap_counters / cb.n_inserted
201 if m_over_n <= 0 { return 1000000000 }
202 if m_over_n == 1 { return 618500000 }
203 if m_over_n == 2 { return 382500000 }
204 if m_over_n == 4 { return 146300000 }
205 if m_over_n == 8 { return 21420000 }
206 if m_over_n == 16 { return 458000 }
207 if m_over_n == 32 { return 216 }
208 return 0
209}
210
211func nx_cb_query(cb: *CountingBloom, key: *u8, len: i64) -> *ApproxI64 {
212 let present: i64 = nx_cb_contains(cb, key, len)
213 let fpr: i64 = nx_cb_fpr_ppb(cb)
214 return nx_approx_new(present, NX_ENV_ABS, cb.saturations,
215 1000000000 - fpr,
216 NX_MATURITY_REFERENCE_IMPL,
217 NX_ADV_HONEST)
218}
219
220// === merge ========================================================
221//
222// Counter-wise addition (with saturation). Both filters must have
223// matching cap + k.
224
225func nx_cb_merge(a: *CountingBloom, b: *CountingBloom) -> *CountingBloom {
226 if a.cap_counters != b.cap_counters { return 0 as *CountingBloom }
227 if a.k != b.k { return 0 as *CountingBloom }
228 let out: *CountingBloom = nx_cb_alloc(a.cap_counters, a.k)
229 var i: i64 = 0
230 while i < a.cap_counters {
231 let va: i64 = nx_cb_counter_get(a, i)
232 let vb: i64 = nx_cb_counter_get(b, i)
233 var sum: i64 = va + vb
234 if sum > NX_CB_COUNTER_MAX {
235 sum = NX_CB_COUNTER_MAX
236 out.saturations = out.saturations + 1
237 }
238 nx_cb_counter_set(out, i, sum)
239 i = i + 1
240 }
241 out.n_inserted = a.n_inserted + b.n_inserted
242 return out
243}
244
245// === introspection ================================================
246
247func nx_cb_saturations(cb: *CountingBloom) -> i64 {
248 return cb.saturations
249}
250
251func nx_cb_memory_bytes(cb: *CountingBloom) -> i64 {
252 return 56 + cb.cap_counters / NX_CB_COUNTERS_PER_BYTE
253}