nx_bit.nx source

1// nx_bit.nx -- low-level bit primitives. 2// 3// FOUNDATION LAYER. Every crypto module, every bitmap, every 4// CRC-style checksum, every compressed-encoding parser eventually 5// wants: popcount, count-leading-zeros, count-trailing-zeros, 6// byte-swap, rotate-left/right. Today every module re-implements 7// these via shift+mask loops. Centralising matches: 8// 9// * R1 cache-conscious: one canonical implementation per primitive 10// means one inlining decision the optimiser sees everywhere 11// * R2 attestable: SHA-256 + ChaCha20 + others share the same 12// few primitives -- audit once instead of N copies 13// * Future: lower to RV64 Zbb (bit-manipulation extension) when 14// the target supports it; ~2-5x speedup over scalar fallback 15// 16// Bit primitives shipped: 17// 18// nx_popcount32 / nx_popcount64 Hamming weight 19// nx_clz32 / nx_clz64 leading zero count 20// nx_ctz32 / nx_ctz64 trailing zero count 21// nx_bswap32 / nx_bswap64 byte-reverse 22// nx_rotl32 / nx_rotl64 rotate left 23// nx_rotr32 / nx_rotr64 rotate right 24// nx_log2_floor log2 floor (= 63 - clz) 25// nx_is_pow2 power-of-two check 26// nx_align_up round up to align (must be POT) 27// 28// Algorithm references: 29// 30// * popcount: Hamming weight via parallel-prefix (folklore; 31// Knuth TAoCP Vol 4A 7.1.3). Constant 12 ops for 64-bit. 32// * clz / ctz: branch-free de Bruijn sequence multiply 33// (Leiserson et al, "Using De Bruijn sequences to index a 1 34// in a computer word", 1998 unpublished). Constant 8-10 ops. 35// * bswap: 4-step shuffle (Schneier, Practical Cryptography 2003). 36// 37// Forward path: when nxc2 grows the Zbb intrinsic, lower these to 38// `cpop`, `clz`, `ctz`, `rev8`, `rori`, `rorw` instructions. 39// Estimated 3-5x speedup on hot crypto / hashing paths. 40 41// nx_safety_envelope: 42// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 43// sil_target: SIL1 44// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 45// verdict: NOT_YET_EVALUATED 46 47import "syscalls.nx" 48import "nx_bits.nx" 49 50// ---- popcount ----------------------------------------------------- 51 52// Delegated to nx_bits for substrate-wide consolidation. The nx_bits 53// FAST path dispatches to popcntq (x86_64) / cpop (rv64 Zbb), giving 54// a measured 2x speedup over the SWAR fallback at no correctness cost. 55func nx_popcount32(x: i64) -> i64 { 56 return nx_bits_popcount32(x) 57} 58 59func nx_popcount64(x: i64) -> i64 { 60 return nx_bits_popcount64(x) 61} 62 63// ---- count leading zeros ------------------------------------------ 64// Delegated to nx_bits_clz32/64 (intrinsic dispatch -- bsr+xor on 65// x86_64, clzw/clz on rv64 Zbb). Returns 32 for clz32(0), 64 for 66// clz64(0); intrinsic-correct on both ISAs. 67 68func nx_clz32(x: i64) -> i64 { 69 return nx_bits_clz32(x) 70} 71 72func nx_clz64(x: i64) -> i64 { 73 return nx_bits_clz64(x) 74} 75 76// ---- count trailing zeros ----------------------------------------- 77// Delegated to nx_bits_ctz32/64 (bsf+zero / ctzw). 78 79func nx_ctz32(x: i64) -> i64 { 80 return nx_bits_ctz32(x) 81} 82 83func nx_ctz64(x: i64) -> i64 { 84 return nx_bits_ctz64(x) 85} 86 87// ---- byte-swap (endian flip) -------------------------------------- 88 89// Delegated to nx_bits_bswap32/64 (bswapq / rev8 intrinsic). 1 90// cycle vs the 6-op byte-shuffle / 13-op SWAR. 91func nx_bswap32(x: i64) -> i64 { 92 return nx_bits_bswap32(x) 93} 94 95func nx_bswap64(x: i64) -> i64 { 96 return nx_bits_bswap64(x) 97} 98 99// ---- rotates ------------------------------------------------------ 100 101// Delegated to nx_bits for substrate-wide consolidation. 64-bit 102// rotates now use rolq/rorq (x86_64) or rol/ror (rv64 Zbb) -- 1 103// cycle vs ~5 ops. Also fixes a latent bug in the legacy 64-bit 104// body where (x >> (64-nn)) sign-extends for negative x. 105 106func nx_rotl32(x: i64, n: i64) -> i64 { 107 return nx_bits_rotl32(x, n) 108} 109 110func nx_rotr32(x: i64, n: i64) -> i64 { 111 return nx_bits_rotr32(x, n) 112} 113 114func nx_rotl64(x: i64, n: i64) -> i64 { 115 return nx_bits_rotl64(x, n) 116} 117 118func nx_rotr64(x: i64, n: i64) -> i64 { 119 return nx_bits_rotr64(x, n) 120} 121 122// ---- log2 / power-of-two helpers ---------------------------------- 123 124// Floor of log2(x). Returns -1 if x <= 0. 125func nx_log2_floor(x: i64) -> i64 { 126 if x <= 0 { return -1 } 127 return 63 - nx_clz64(x) 128} 129 130// True (1) if x is a power of two AND > 0. 131func nx_is_pow2(x: i64) -> i64 { 132 if x <= 0 { return 0 } 133 if (x & (x - 1)) == 0 { return 1 } 134 return 0 135} 136 137// Round x up to the nearest multiple of `align`. align MUST be a 138// power-of-two (callers should assert). 139func nx_align_up(x: i64, align: i64) -> i64 { 140 let mask: i64 = align - 1 141 return (x + mask) & (~mask) 142} 143 144// ---- self-test ---------------------------------------------------- 145 146func main() -> i64 { 147 // popcount 148 if nx_popcount32(0) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) } 149 if nx_popcount32(1) != 1 { return __syscall(93, 11, 0, 0, 0, 0, 0) } 150 if nx_popcount32(0xF) != 4 { return __syscall(93, 12, 0, 0, 0, 0, 0) } 151 if nx_popcount32(0xFF) != 8 { return __syscall(93, 13, 0, 0, 0, 0, 0) } 152 if nx_popcount32(0xFFFFFFFF) != 32 { return __syscall(93, 14, 0, 0, 0, 0, 0) } 153 if nx_popcount64(0xFFFFFFFFFFFFFFFF) != 64 { return __syscall(93, 15, 0, 0, 0, 0, 0) } 154 if nx_popcount64(0x8000000000000000) != 1 { return __syscall(93, 16, 0, 0, 0, 0, 0) } 155 156 // clz 157 if nx_clz32(0) != 32 { return __syscall(93, 20, 0, 0, 0, 0, 0) } 158 if nx_clz32(1) != 31 { return __syscall(93, 21, 0, 0, 0, 0, 0) } 159 if nx_clz32(0xFFFFFFFF) != 0 { return __syscall(93, 22, 0, 0, 0, 0, 0) } 160 if nx_clz32(0x80000000) != 0 { return __syscall(93, 23, 0, 0, 0, 0, 0) } 161 if nx_clz32(0x40000000) != 1 { return __syscall(93, 24, 0, 0, 0, 0, 0) } 162 if nx_clz64(0) != 64 { return __syscall(93, 25, 0, 0, 0, 0, 0) } 163 if nx_clz64(1) != 63 { return __syscall(93, 26, 0, 0, 0, 0, 0) } 164 if nx_clz64(0x8000000000000000) != 0 { return __syscall(93, 27, 0, 0, 0, 0, 0) } 165 166 // ctz 167 if nx_ctz32(0) != 32 { return __syscall(93, 30, 0, 0, 0, 0, 0) } 168 if nx_ctz32(1) != 0 { return __syscall(93, 31, 0, 0, 0, 0, 0) } 169 if nx_ctz32(2) != 1 { return __syscall(93, 32, 0, 0, 0, 0, 0) } 170 if nx_ctz32(0x80000000) != 31 { return __syscall(93, 33, 0, 0, 0, 0, 0) } 171 if nx_ctz64(0) != 64 { return __syscall(93, 34, 0, 0, 0, 0, 0) } 172 173 // bswap 174 if nx_bswap32(0x12345678) != 0x78563412 { return __syscall(93, 40, 0, 0, 0, 0, 0) } 175 if nx_bswap32(0xDEADBEEF) != 0xEFBEADDE { return __syscall(93, 41, 0, 0, 0, 0, 0) } 176 177 // rotl / rotr 178 if nx_rotl32(0x80000000, 1) != 1 { return __syscall(93, 50, 0, 0, 0, 0, 0) } 179 if nx_rotl32(1, 31) != 0x80000000 { return __syscall(93, 51, 0, 0, 0, 0, 0) } 180 if nx_rotr32(1, 1) != 0x80000000 { return __syscall(93, 52, 0, 0, 0, 0, 0) } 181 182 // log2 / pow2 183 if nx_log2_floor(0) != -1 { return __syscall(93, 60, 0, 0, 0, 0, 0) } 184 if nx_log2_floor(1) != 0 { return __syscall(93, 61, 0, 0, 0, 0, 0) } 185 if nx_log2_floor(8) != 3 { return __syscall(93, 62, 0, 0, 0, 0, 0) } 186 if nx_log2_floor(0x80000000) != 31 { return __syscall(93, 63, 0, 0, 0, 0, 0) } 187 if nx_is_pow2(0) != 0 { return __syscall(93, 70, 0, 0, 0, 0, 0) } 188 if nx_is_pow2(1) != 1 { return __syscall(93, 71, 0, 0, 0, 0, 0) } 189 if nx_is_pow2(8) != 1 { return __syscall(93, 72, 0, 0, 0, 0, 0) } 190 if nx_is_pow2(7) != 0 { return __syscall(93, 73, 0, 0, 0, 0, 0) } 191 192 // align_up 193 if nx_align_up(0, 8) != 0 { return __syscall(93, 80, 0, 0, 0, 0, 0) } 194 if nx_align_up(1, 8) != 8 { return __syscall(93, 81, 0, 0, 0, 0, 0) } 195 if nx_align_up(7, 8) != 8 { return __syscall(93, 82, 0, 0, 0, 0, 0) } 196 if nx_align_up(8, 8) != 8 { return __syscall(93, 83, 0, 0, 0, 0, 0) } 197 if nx_align_up(9, 8) != 16 { return __syscall(93, 84, 0, 0, 0, 0, 0) } 198 199 return 0 200}