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