nx_bits.nx source
↩ module page · 335 lines · 10783 B
1// nx_bits.nx -- bit-manipulation primitives, dispatching to hardware
2// intrinsics on supported backends with portable software fallbacks.
3//
4// Inspired by Hacker's Delight (Henry S. Warren Jr.) -- the canonical
5// reference for bit-twiddling. Every soft path is BRANCHLESS or
6// minimally-branched, FIXED-CYCLE, and CROSS-ARCH PORTABLE.
7//
8// Dispatch model:
9// nx_bits_popcount64 / nx_bits_clz32 / nx_bits_ctz32 -> backend
10// intrinsic on x86_64 (popcntq/bsrl+xor/bsfl) and rv64 with Zbb
11// (cpop/clzw/ctzw). One machine instruction. Used by hot paths
12// (sketches, hashing, bitmap iteration).
13//
14// nx_bits_popcount64_soft / nx_bits_clz32_soft / nx_bits_ctz32_soft
15// -- pure-NishiLang SWAR + binary-search variants. Cross-arch
16// portable to backends without bit-count opcodes. Used by paired
17// correctness oracles and any caller targeting an exotic ISA.
18//
19// Substrate "get off C" trajectory: this module is pure NishiLang.
20
21import "syscalls.nx"
22
23// === popcount FAST: dispatches to backend intrinsic ==============
24
25func nx_bits_popcount64(x: i64) -> i64 {
26 return __popcnt64(x)
27}
28
29func nx_bits_popcount32(x: i64) -> i64 {
30 return __popcnt64(x & 0xFFFFFFFF)
31}
32
33// === clz32 / ctz32 FAST: backend intrinsic =======================
34// __clz32(0) and __ctz32(0) both return 32 on both backends (x86
35// uses a tested fallback to set the result; rv64 Zbb returns 32 by
36// spec) so the wrapper is a thin pass-through.
37
38func nx_bits_clz32(x: i64) -> i64 {
39 return __clz32(x)
40}
41
42func nx_bits_ctz32(x: i64) -> i64 {
43 return __ctz32(x)
44}
45
46// 64-bit clz / ctz: composed from two 32-bit intrinsics. Until the
47// backend grows OP_CLZ64 / OP_CTZ64 these are still ~3-instruction
48// hot paths vs the legacy 64-iteration loops, so they replace those
49// substrate-wide. clz(0) = 64; ctz(0) = 64.
50
51func nx_bits_clz64(x: i64) -> i64 {
52 let hi: i64 = (x >> 32) & 0xFFFFFFFF
53 if hi != 0 { return __clz32(hi) }
54 return 32 + __clz32(x & 0xFFFFFFFF)
55}
56
57func nx_bits_ctz64(x: i64) -> i64 {
58 let lo: i64 = x & 0xFFFFFFFF
59 if lo != 0 { return __ctz32(lo) }
60 if x == 0 { return 64 }
61 return 32 + __ctz32((x >> 32) & 0xFFFFFFFF)
62}
63
64// === rotate left / right FAST: backend intrinsic ================
65// Hardware native via rolq/rorq (x86_64, 1985) and rol/ror (rv64
66// Zbb). Mask the count to 0..63 so the substrate exposes
67// "rotate-mod-64" semantics on both ISAs (x86_64 already masks; rv64
68// behaviour is identical with the explicit mask).
69
70func nx_bits_rotl64(x: i64, n: i64) -> i64 {
71 return __rotl64(x, n & 63)
72}
73
74func nx_bits_rotr64(x: i64, n: i64) -> i64 {
75 return __rotr64(x, n & 63)
76}
77
78// 32-bit rotate (no native intrinsic emitted; we pre-mask the value
79// to its low 32 bits so the i64 arithmetic shift right doesn't
80// contaminate with sign bits, then mask the result back to 32 bits).
81// ~3 ops vs 5-7 in inline rotr32/rotl32 callsites scattered across
82// crypto modules (SHA-256, ChaCha20, MurmurHash, etc.).
83
84func nx_bits_rotl32(x: i64, n: i64) -> i64 {
85 let v: i64 = x & 0xFFFFFFFF
86 let nn: i64 = n & 31
87 if nn == 0 { return v }
88 return ((v << nn) | (v >> (32 - nn))) & 0xFFFFFFFF
89}
90
91func nx_bits_rotr32(x: i64, n: i64) -> i64 {
92 let v: i64 = x & 0xFFFFFFFF
93 let nn: i64 = n & 31
94 if nn == 0 { return v }
95 return ((v >> nn) | (v << (32 - nn))) & 0xFFFFFFFF
96}
97
98// === byte-reverse FAST: backend intrinsic =========================
99// bswapq (x86_64, i486 1989+, universal) and rev8 (rv64 Zbb). 1
100// cycle vs the 13-op SWAR phrasing. Used by every endian flip,
101// every network/header parse, SHA-256 big-endian word loads.
102
103func nx_bits_bswap64(x: i64) -> i64 {
104 return __bswap64(x)
105}
106
107// 32-bit byte-reverse: mask to low 32 (zero-extends the i64), bswap
108// the whole register -- the four low bytes get reversed into the top
109// half -- then shift down to recover them. Mask after shift to
110// discard the sign extension on inputs where bit 31 of the bswapped
111// low half is set (which becomes bit 63 of the 64-bit register).
112func nx_bits_bswap32(x: i64) -> i64 {
113 return (__bswap64(x & 0xFFFFFFFF) >> 32) & 0xFFFFFFFF
114}
115
116// === SOFT fallbacks: pure NishiLang, cross-arch portable =========
117
118func nx_bits_popcount64_soft(x: i64) -> i64 {
119 var v: i64 = x
120 v = v - ((v >> 1) & 0x5555555555555555)
121 v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333)
122 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0F
123 return ((v * 0x0101010101010101) >> 56) & 0xFF
124}
125
126func nx_bits_popcount32_soft(x: i64) -> i64 {
127 var v: i64 = x & 0xFFFFFFFF
128 v = v - ((v >> 1) & 0x55555555)
129 v = (v & 0x33333333) + ((v >> 2) & 0x33333333)
130 v = (v + (v >> 4)) & 0x0F0F0F0F
131 return ((v * 0x01010101) >> 24) & 0xFF
132}
133
134func nx_bits_clz32_soft(x: i64) -> i64 {
135 let lo: i64 = x & 0xFFFFFFFF
136 if lo == 0 { return 32 }
137 var t: i64 = lo
138 var n: i64 = 0
139 if (t & 0xFFFF0000) == 0 { n = n + 16; t = t << 16; t = t & 0xFFFFFFFF }
140 if (t & 0xFF000000) == 0 { n = n + 8; t = t << 8; t = t & 0xFFFFFFFF }
141 if (t & 0xF0000000) == 0 { n = n + 4; t = t << 4; t = t & 0xFFFFFFFF }
142 if (t & 0xC0000000) == 0 { n = n + 2; t = t << 2; t = t & 0xFFFFFFFF }
143 if (t & 0x80000000) == 0 { n = n + 1 }
144 return n
145}
146
147// 64-bit rotate soft fallback (pure NishiLang -- shift+or, ~5 ops).
148// Used by paired correctness oracle and by backends without rotate
149// opcodes. Note: shifting by 0 is the identity; explicit branch
150// avoids the undefined-behaviour case of `x >> 64` on some ISAs.
151
152// The signed >> arithmetic-shifts sign bits in for negative x, so the
153// shifted-right half must be masked to the actual m / (64-m) low bits
154// to discard the sign extension.
155
156func nx_bits_rotl64_soft(x: i64, n: i64) -> i64 {
157 let m: i64 = n & 63
158 if m == 0 { return x }
159 let top: i64 = (x >> (64 - m)) & ((1 << m) - 1)
160 return (x << m) | top
161}
162
163func nx_bits_rotr64_soft(x: i64, n: i64) -> i64 {
164 let m: i64 = n & 63
165 if m == 0 { return x }
166 let low: i64 = (x >> m) & ((1 << (64 - m)) - 1)
167 return low | (x << (64 - m))
168}
169
170// bswap SOFT (Hacker's Delight 7-1, 13-op SWAR). Used by paired
171// oracle and exotic backends.
172
173func nx_bits_bswap64_soft(x: i64) -> i64 {
174 var v: i64 = x
175 v = ((v & 0x00FF00FF00FF00FF) << 8) | ((v >> 8) & 0x00FF00FF00FF00FF)
176 v = ((v & 0x0000FFFF0000FFFF) << 16) | ((v >> 16) & 0x0000FFFF0000FFFF)
177 v = ((v & 0x00000000FFFFFFFF) << 32) | ((v >> 32) & 0x00000000FFFFFFFF)
178 return v
179}
180
181func nx_bits_bswap32_soft(x: i64) -> i64 {
182 let v: i64 = x & 0xFFFFFFFF
183 let b0: i64 = (v >> 24) & 0xFF
184 let b1: i64 = (v >> 16) & 0xFF
185 let b2: i64 = (v >> 8) & 0xFF
186 let b3: i64 = (v ) & 0xFF
187 return (b3 << 24) | (b2 << 16) | (b1 << 8) | b0
188}
189
190// 32-bit rotate SOFT (identical body to FAST; no separate intrinsic
191// path) -- kept as the named-soft for the consolidation paired-oracle
192// convention.
193func nx_bits_rotl32_soft(x: i64, n: i64) -> i64 {
194 return nx_bits_rotl32(x, n)
195}
196func nx_bits_rotr32_soft(x: i64, n: i64) -> i64 {
197 return nx_bits_rotr32(x, n)
198}
199
200// 64-bit soft fallbacks (Knuth TAOCP 4A linear-scan). O(64) iterations
201// in the worst case; used by the paired oracle and by exotic backends.
202
203func nx_bits_clz64_soft(x: i64) -> i64 {
204 if x == 0 { return 64 }
205 var v: i64 = x
206 var n: i64 = 0
207 var mask: i64 = 0x8000000000000000
208 var done: i64 = 0
209 while done == 0 {
210 if (v & mask) != 0 { done = 1 }
211 if done == 0 {
212 n = n + 1
213 mask = mask >> 1
214 if mask == 0 { done = 1 }
215 }
216 }
217 return n
218}
219
220func nx_bits_ctz64_soft(x: i64) -> i64 {
221 if x == 0 { return 64 }
222 var v: i64 = x
223 var n: i64 = 0
224 var done: i64 = 0
225 while done == 0 {
226 if (v & 1) != 0 { done = 1 }
227 if done == 0 {
228 n = n + 1
229 v = v >> 1
230 if n >= 64 { done = 1 }
231 }
232 }
233 return n
234}
235
236func nx_bits_ctz32_soft(x: i64) -> i64 {
237 let lo: i64 = x & 0xFFFFFFFF
238 if lo == 0 { return 32 }
239 var t: i64 = lo
240 var n: i64 = 0
241 if (t & 0x0000FFFF) == 0 { n = n + 16; t = t >> 16 }
242 if (t & 0x000000FF) == 0 { n = n + 8; t = t >> 8 }
243 if (t & 0x0000000F) == 0 { n = n + 4; t = t >> 4 }
244 if (t & 0x00000003) == 0 { n = n + 2; t = t >> 2 }
245 if (t & 0x00000001) == 0 { n = n + 1 }
246 return n
247}
248
249// === isolate lowest set bit (Hacker's Delight 2-1) ================
250//
251// x & -x selects only the lowest 1-bit of x. Useful for iterating
252// set bits in a bitmap (faster than testing each bit).
253// for bitmap != 0:
254// bit = nx_bits_lowest(bitmap)
255// // process bit
256// bitmap = bitmap ^ bit // clear it
257
258func nx_bits_lowest(x: i64) -> i64 {
259 return x & (0 - x)
260}
261
262// === reset lowest set bit (Hacker's Delight 2-1) ==================
263//
264// x & (x-1) clears the lowest 1-bit. When combined with popcount,
265// gives O(popcount) bit-traversal loops -- faster than O(width)
266// when the bitmap is sparse.
267
268func nx_bits_clear_lowest(x: i64) -> i64 {
269 return x & (x - 1)
270}
271
272// === is power of 2 (Hacker's Delight 2-1) =========================
273//
274// x > 0 AND (x & (x-1)) == 0. One subtract + one and + one compare.
275
276func nx_bits_is_pow2(x: i64) -> i64 {
277 if x <= 0 { return 0 }
278 if (x & (x - 1)) == 0 { return 1 }
279 return 0
280}
281
282// === next power of 2 (Hacker's Delight 3-2) =======================
283//
284// Round up to next power of 2. For x already pow2, returns x.
285// For x = 0, returns 1. Standard "smear high bit" pattern.
286
287func nx_bits_next_pow2_32(x: i64) -> i64 {
288 if x <= 1 { return 1 }
289 var v: i64 = (x - 1) & 0xFFFFFFFF
290 v = v | (v >> 1)
291 v = v | (v >> 2)
292 v = v | (v >> 4)
293 v = v | (v >> 8)
294 v = v | (v >> 16)
295 return (v + 1) & 0xFFFFFFFF
296}
297
298// === parity (Hacker's Delight 5-1) ================================
299//
300// Returns 1 if odd number of set bits, 0 if even. Two-and-XOR
301// reduction, branchless.
302
303func nx_bits_parity64(x: i64) -> i64 {
304 var v: i64 = x
305 v = v ^ (v >> 32)
306 v = v ^ (v >> 16)
307 v = v ^ (v >> 8)
308 v = v ^ (v >> 4)
309 return (0x6996 >> (v & 15)) & 1
310}
311
312// === floor(log2(x)) ===============================================
313//
314// Equivalent to (31 - clz(x)) for x > 0. Returns -1 for x <= 0.
315
316func nx_bits_floor_log2(x: i64) -> i64 {
317 if x <= 0 { return -1 }
318 if x <= 0xFFFFFFFF {
319 return 31 - nx_bits_clz32(x)
320 }
321 // High 32 bits set: 32 + log2(x >> 32)
322 return 63 - nx_bits_clz32(x >> 32)
323}
324
325// === bit-field extract (BMI BEXTR semantics) ======================
326//
327// Extract `len` bits starting at `start` from x.
328// Equivalent to (x >> start) & ((1 << len) - 1).
329
330func nx_bits_bextr(x: i64, start: i64, len: i64) -> i64 {
331 if len <= 0 { return 0 }
332 if len >= 64 { return x >> start }
333 let mask: i64 = (1 << len) - 1
334 return (x >> start) & mask
335}