nx_bitset.nx source
↩ module page · 191 lines · 5445 B
1// bitset.nx -- packed bit array with O(1) get / set / clear.
2//
3// Stores N boolean flags in ceil(N/64) i64 words. 8x denser
4// than bool[] (which nxc stores as i64 per element). Used for:
5// - SSA liveness (each block × each variable)
6// - garbage-collection mark bits (one bit per object)
7// - compiler dominance-frontier frontier sets
8// - simple set<i64> for small universes (port/file-descriptor tables)
9// - bloom filter internals (bitset + k hashes)
10//
11// Not a drop-in Set<K> -- that's what map.nx is for. Bitset is
12// for dense bit-vectors where the universe is bounded and small.
13//
14// Operations:
15// bitset_new(n) allocate n-bit bitset (all zeros)
16// bitset_set(bs, i) set bit i
17// bitset_clear(bs, i) clear bit i
18// bitset_get(bs, i) read bit i (0 or 1)
19// bitset_count(bs) popcount over all bits
20// bitset_union(dst, src) dst |= src, same capacity
21// bitset_intersect(dst, src) dst &= src
22// bitset_equal(a, b) byte-exact compare
23//
24// Invariants:
25// BS1 bitset_new zeros the backing store -- no uninit reads.
26// BS2 get/set do NOT bounds-check (hot path); caller ensures
27// i < capacity. Debug wrapper could add that.
28// BS3 All *_in-place ops require both bitsets to share the
29// same capacity (word count).
30
31// nx_safety_envelope:
32// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
33// sil_target: SIL1
34// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
35// verdict: NOT_YET_EVALUATED
36
37import "nx_syscalls.nx"
38
39struct Bitset {
40 bits: *i64, // packed storage
41 cap: i64, // capacity in bits
42 words: i64, // ceil(cap / 64)
43}
44
45// Allocate an n-bit bitset initialised to all zeros.
46func bitset_new(n: i64) -> *Bitset {
47 let bs_raw: *u8 = sys_mmap(32)
48 let bs: *Bitset = bs_raw as *Bitset
49 let words: i64 = (n + 63) / 64
50 bs.bits = sys_mmap(words * 8 + 16) as *i64
51 bs.cap = n
52 bs.words = words
53 var i: i64 = 0
54 while i < words {
55 bs.bits[i] = 0
56 i = i + 1
57 }
58 return bs
59}
60
61// Set bit i to 1.
62func bitset_set(bs: *Bitset, i: i64) -> i64 {
63 let w: i64 = i / 64
64 let b: i64 = i % 64
65 bs.bits[w] = bs.bits[w] | (1 << b)
66 return 0
67}
68
69// Clear bit i.
70func bitset_clear(bs: *Bitset, i: i64) -> i64 {
71 let w: i64 = i / 64
72 let b: i64 = i % 64
73 let mask: i64 = 1 << b
74 bs.bits[w] = bs.bits[w] & (mask ^ (0 - 1)) // ~mask
75 return 0
76}
77
78// Read bit i (0 or 1).
79func bitset_get(bs: *Bitset, i: i64) -> i64 {
80 let w: i64 = i / 64
81 let b: i64 = i % 64
82 return (bs.bits[w] >> b) & 1
83}
84
85// Hamming weight of a single 64-bit word (Kernighan loop;
86// keeps code small, branchless popcount is a future win).
87func bitset_popcount_word(x: i64) -> i64 {
88 var v: i64 = x
89 var c: i64 = 0
90 while v != 0 {
91 v = v & (v - 1)
92 c = c + 1
93 }
94 return c
95}
96
97// Count set bits across the whole bitset.
98func bitset_count(bs: *Bitset) -> i64 {
99 var total: i64 = 0
100 var w: i64 = 0
101 while w < bs.words {
102 total = total + bitset_popcount_word(bs.bits[w])
103 w = w + 1
104 }
105 return total
106}
107
108// In-place union: dst |= src. Requires dst.words == src.words.
109func bitset_union(dst: *Bitset, src: *Bitset) -> i64 {
110 if dst.words != src.words { return -1 }
111 var w: i64 = 0
112 while w < dst.words {
113 dst.bits[w] = dst.bits[w] | src.bits[w]
114 w = w + 1
115 }
116 return 0
117}
118
119// In-place intersection: dst &= src.
120func bitset_intersect(dst: *Bitset, src: *Bitset) -> i64 {
121 if dst.words != src.words { return -1 }
122 var w: i64 = 0
123 while w < dst.words {
124 dst.bits[w] = dst.bits[w] & src.bits[w]
125 w = w + 1
126 }
127 return 0
128}
129
130// Byte-exact equality. Returns 1 if equal, 0 otherwise.
131func bitset_equal(a: *Bitset, b: *Bitset) -> i64 {
132 if a.cap != b.cap { return 0 }
133 var w: i64 = 0
134 while w < a.words {
135 if a.bits[w] != b.bits[w] { return 0 }
136 w = w + 1
137 }
138 return 1
139}
140
141// Clear every bit.
142func bitset_zero(bs: *Bitset) -> i64 {
143 var w: i64 = 0
144 while w < bs.words {
145 bs.bits[w] = 0
146 w = w + 1
147 }
148 return 0
149}
150
151// Compile-only smoke.
152func main() -> i64 {
153 let bs: *Bitset = bitset_new(200)
154 if bs.cap != 200 { return 1 }
155 if bs.words != 4 { return 2 } // ceil(200/64) = 4
156
157 bitset_set(bs, 0)
158 bitset_set(bs, 63)
159 bitset_set(bs, 64)
160 bitset_set(bs, 199)
161
162 if bitset_get(bs, 0) != 1 { return 3 }
163 if bitset_get(bs, 1) != 0 { return 4 }
164 if bitset_get(bs, 63) != 1 { return 5 }
165 if bitset_get(bs, 64) != 1 { return 6 }
166 if bitset_get(bs, 199) != 1 { return 7 }
167 if bitset_count(bs) != 4 { return 8 }
168
169 bitset_clear(bs, 63)
170 if bitset_get(bs, 63) != 0 { return 9 }
171 if bitset_count(bs) != 3 { return 10 }
172
173 // Union / intersect.
174 let b2: *Bitset = bitset_new(200)
175 bitset_set(b2, 0)
176 bitset_set(b2, 100)
177
178 let b_union_raw: *Bitset = bitset_new(200)
179 bitset_union(b_union_raw, bs)
180 bitset_union(b_union_raw, b2)
181 // Bits set: 0, 64, 100, 199 -> 4.
182 if bitset_count(b_union_raw) != 4 { return 11 }
183
184 // Intersect bs with b2: both have bit 0.
185 let inter: *Bitset = bitset_new(200)
186 bitset_union(inter, bs)
187 bitset_intersect(inter, b2)
188 if bitset_count(inter) != 1 { return 12 }
189 if bitset_get(inter, 0) != 1 { return 13 }
190 return 0
191}