nx_sketch_bit_vector.nx source
↩ module page · 249 lines · 6357 B
1// sketch_bit_vector.nx -- dense bit vector with popcount + bitwise ops.
2//
3// Foundational primitive for bitmap indices, finite-universe set ops,
4// Bloom variants, sparse-index compression, etc.
5//
6// API:
7// set(i) bit i := 1
8// clear(i) bit i := 0
9// toggle(i) bit i := ~bit i
10// get(i) return bit i (0 or 1)
11// popcount() count of set bits (cached on mutation)
12// popcount_range(lo, hi) count over [lo, hi)
13// ffs() find first set bit (-1 if none)
14// ffc() find first clear bit
15// bv_and / bv_or / bv_xor / bv_not in-place bitwise ops
16//
17// Production tier; exact semantics.
18
19// nx_safety_envelope:
20// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
21// sil_target: SIL1
22// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
23// verdict: NOT_YET_EVALUATED
24
25import "nx_syscalls.nx"
26import "nx_sketch_types.nx"
27
28const NX_BV_MIN_BITS: i64 = 8
29const NX_BV_MAX_BITS: i64 = 1073741824 // 1G bits = 128 MB
30
31struct BitVector {
32 bits: *u8, // ceil(n_bits / 8) bytes
33 n_bits: i64,
34 n_bytes: i64,
35 pop: i64, // cached popcount
36 pop_valid: i64, // 1 if pop is fresh
37}
38
39// === construction =================================================
40
41func nx_bv_alloc(n_bits: i64) -> *BitVector {
42 if n_bits < NX_BV_MIN_BITS { return 0 as *BitVector }
43 if n_bits > NX_BV_MAX_BITS { return 0 as *BitVector }
44 let raw: *u8 = sys_mmap(48)
45 let v: *BitVector = raw as *BitVector
46 let n_bytes: i64 = (n_bits + 7) / 8
47 v.bits = sys_mmap(n_bytes)
48 var i: i64 = 0
49 while i < n_bytes {
50 v.bits[i] = 0
51 i = i + 1
52 }
53 v.n_bits = n_bits
54 v.n_bytes = n_bytes
55 v.pop = 0
56 v.pop_valid = 1
57 return v
58}
59
60// === bit operations ==============================================
61
62func nx_bv_set(v: *BitVector, i: i64) -> i64 {
63 if i < 0 { return -1 }
64 if i >= v.n_bits { return -1 }
65 let byte_idx: i64 = i >> 3
66 let bit_pos: i64 = i & 7
67 let prev: i64 = v.bits[byte_idx]
68 let mask: i64 = 1 << bit_pos
69 if (prev & mask) == 0 {
70 v.bits[byte_idx] = prev | mask
71 if v.pop_valid == 1 { v.pop = v.pop + 1 }
72 }
73 return 0
74}
75
76func nx_bv_clear(v: *BitVector, i: i64) -> i64 {
77 if i < 0 { return -1 }
78 if i >= v.n_bits { return -1 }
79 let byte_idx: i64 = i >> 3
80 let bit_pos: i64 = i & 7
81 let prev: i64 = v.bits[byte_idx]
82 let mask: i64 = 1 << bit_pos
83 if (prev & mask) != 0 {
84 v.bits[byte_idx] = prev & ~mask
85 if v.pop_valid == 1 { v.pop = v.pop - 1 }
86 }
87 return 0
88}
89
90func nx_bv_toggle(v: *BitVector, i: i64) -> i64 {
91 if i < 0 { return -1 }
92 if i >= v.n_bits { return -1 }
93 let byte_idx: i64 = i >> 3
94 let bit_pos: i64 = i & 7
95 let prev: i64 = v.bits[byte_idx]
96 let mask: i64 = 1 << bit_pos
97 if (prev & mask) == 0 {
98 v.bits[byte_idx] = prev | mask
99 if v.pop_valid == 1 { v.pop = v.pop + 1 }
100 }
101 if (prev & mask) != 0 {
102 v.bits[byte_idx] = prev & ~mask
103 if v.pop_valid == 1 { v.pop = v.pop - 1 }
104 }
105 return 0
106}
107
108func nx_bv_get(v: *BitVector, i: i64) -> i64 {
109 if i < 0 { return 0 }
110 if i >= v.n_bits { return 0 }
111 let byte_idx: i64 = i >> 3
112 let bit_pos: i64 = i & 7
113 return (v.bits[byte_idx] >> bit_pos) & 1
114}
115
116// === popcount ====================================================
117
118func nx_bv_popcount_byte(b: i64) -> i64 {
119 var n: i64 = 0
120 var t: i64 = b & 0xFF
121 while t > 0 {
122 n = n + (t & 1)
123 t = t >> 1
124 }
125 return n
126}
127
128func nx_bv_recompute_popcount(v: *BitVector) -> i64 {
129 var n: i64 = 0
130 var i: i64 = 0
131 while i < v.n_bytes {
132 n = n + nx_bv_popcount_byte(v.bits[i])
133 i = i + 1
134 }
135 v.pop = n
136 v.pop_valid = 1
137 return 0
138}
139
140func nx_bv_popcount(v: *BitVector) -> i64 {
141 if v.pop_valid == 0 {
142 nx_bv_recompute_popcount(v)
143 }
144 return v.pop
145}
146
147func nx_bv_popcount_range(v: *BitVector, lo: i64, hi: i64) -> i64 {
148 if lo < 0 { return 0 }
149 if hi > v.n_bits { return 0 }
150 if lo >= hi { return 0 }
151 var n: i64 = 0
152 var i: i64 = lo
153 while i < hi {
154 n = n + nx_bv_get(v, i)
155 i = i + 1
156 }
157 return n
158}
159
160// === find first set / clear ======================================
161
162func nx_bv_ffs(v: *BitVector) -> i64 {
163 var i: i64 = 0
164 while i < v.n_bits {
165 if nx_bv_get(v, i) == 1 { return i }
166 i = i + 1
167 }
168 return -1
169}
170
171func nx_bv_ffc(v: *BitVector) -> i64 {
172 var i: i64 = 0
173 while i < v.n_bits {
174 if nx_bv_get(v, i) == 0 { return i }
175 i = i + 1
176 }
177 return -1
178}
179
180// === bitwise ops (in-place into dst) =============================
181//
182// Both vectors must have matching n_bits.
183
184func nx_bv_and(dst: *BitVector, src: *BitVector) -> i64 {
185 if dst.n_bits != src.n_bits { return -1 }
186 var i: i64 = 0
187 while i < dst.n_bytes {
188 dst.bits[i] = dst.bits[i] & src.bits[i]
189 i = i + 1
190 }
191 dst.pop_valid = 0
192 return 0
193}
194
195func nx_bv_or(dst: *BitVector, src: *BitVector) -> i64 {
196 if dst.n_bits != src.n_bits { return -1 }
197 var i: i64 = 0
198 while i < dst.n_bytes {
199 dst.bits[i] = dst.bits[i] | src.bits[i]
200 i = i + 1
201 }
202 dst.pop_valid = 0
203 return 0
204}
205
206func nx_bv_xor(dst: *BitVector, src: *BitVector) -> i64 {
207 if dst.n_bits != src.n_bits { return -1 }
208 var i: i64 = 0
209 while i < dst.n_bytes {
210 dst.bits[i] = dst.bits[i] ^ src.bits[i]
211 i = i + 1
212 }
213 dst.pop_valid = 0
214 return 0
215}
216
217func nx_bv_not(v: *BitVector) -> i64 {
218 var i: i64 = 0
219 while i < v.n_bytes {
220 v.bits[i] = (~v.bits[i]) & 0xFF
221 i = i + 1
222 }
223 v.pop_valid = 0
224 return 0
225}
226
227// === typed envelope ==============================================
228
229func nx_bv_query_popcount(v: *BitVector) -> *ApproxI64 {
230 let p: i64 = nx_bv_popcount(v)
231 return nx_approx_new(p, NX_ENV_ABS, 0, 1000000000,
232 NX_MATURITY_PRODUCTION,
233 NX_ADV_HONEST)
234}
235
236func nx_bv_memory_bytes(v: *BitVector) -> i64 {
237 return 48 + v.n_bytes
238}
239
240func nx_bv_clear_all(v: *BitVector) -> i64 {
241 var i: i64 = 0
242 while i < v.n_bytes {
243 v.bits[i] = 0
244 i = i + 1
245 }
246 v.pop = 0
247 v.pop_valid = 1
248 return 0
249}