nx_bitops.nx source

1// nx_bitops.nx -- 64-bit bitwise helpers (gold-standard reference). 2// Delegates to nx_bits.nx for FAST intrinsic dispatch (rolq/rorq / 3// rol/ror Zbb) while preserving the math-correctness phrasing of the 4// soft fallback as in-place documentation. 5 6import "nx_bits.nx" 7 8// 9// NishiLang's `>>` operator is ARITHMETIC right shift -- it sign-extends 10// the high bit. For any 64-bit value where the high bit can be set 11// (hash state lanes, crypto rotation primitives, etc.) a naive `x >> n` 12// will corrupt the result with sign-extended 1s. 13// 14// This file is the GOLD STANDARD for shift / rotate idioms. Per the 15// Pillar 4 doctrine (NISHI_INTELLIGENT_CAPABILITY_LAYER.md) and per 16// memory entry [[feedback-nishilang-shift-arith-not-logical]], the 17// `bench/bench_shift_audit.sh` grader scans every runtime/*.nx file 18// against the patterns DEFINED HERE. 19// 20// WAT-target note: cross-module imports drag in atomics IR that the 21// WAT backend doesn't lower; substrate-WASM crypto modules therefore 22// inline these helpers VERBATIM. The grader verifies each inlined 23// copy matches the gold standard. If you change a function here, the 24// downstream crypto modules must be re-synchronised + re-KAT'd. 25// 26// Verified callers (all KAT-green at https://nishifamily.com/video/substrate.html): 27// nx_sha256_wasm.nx (32-bit, but rotation idiom matches) 28// nx_sha384_wasm.nx (64-bit lanes) 29// nx_sha512_wasm.nx (64-bit lanes) 30// nx_hmac_sha512_wasm.nx (composes sha512) 31// nx_hkdf_sha512_wasm.nx (composes hmac) 32// nx_sha3_256_wasm.nx (64-bit lanes; canonical _rotl64 source) 33// nx_shake128_wasm.nx (Keccak shares _rotl64) 34// nx_shake256_wasm.nx (Keccak shares _rotl64) 35// nx_poly1305_wasm.nx (26-bit limbs; safe-by-construction) 36// nx_x25519_wasm.nx (26/25-bit limbs; safe-by-construction) 37// 38// license_tier: INDEPENDENT_REDERIVE 39// genealogy_id: nishi-core/substrate-discipline 40// lineage_id: nishi_bitops_q1 41// safe_shift_audit: gold_standard 42 43// === nx_lshr64 -- logical right shift (treat x as unsigned 64-bit) === 44// Mask AFTER the arithmetic shift to clear sign-extended high bits. 45// 46// Correct mask: (1 << (64 - n)) - 1 keeps the bits that ACTUALLY 47// moved into low positions 48// 49// Wait -- read that again carefully: 50// * arithmetic shift right by `n` moves `(64-n)` real bits down, 51// and fills the top `n` bits with sign extension 52// * the low `(64-n)` bits are the bits we want to keep 53// * mask = (1 << (64-n)) - 1 keeps those bits 54// 55// !! THIS IS THE BUG SHAPE !! The mask formula above looks right but 56// only works when shifting by a SMALL amount. When `n = 63` (the 57// extreme case in rotl(x, 1)), `(1 << (64-63)) - 1 = 0x1` -- correct. 58// When `n = 1` (the extreme case in rotl(x, 63)), 59// `(1 << (64-1)) - 1 = (1 << 63) - 1 = 0x7FFF_FFFF_FFFF_FFFF` 60// -- which has all 63 low bits set, which is correct for n=1 shift. 61// 62// So `(1 << (64-n)) - 1` is actually CORRECT for lshr64. The bug 63// from feedback-nishilang-shift-arith-not-logical is specific to 64// the ROTATION-COMPOSITION case below, where we already split into 65// two halves -- not to a bare logical shift. 66// 67// For nx_lshr64 we use the simpler equivalent: 68func nx_lshr64(x: i64, n: i64) -> i64 { 69 let nn: i64 = n & 63 70 if nn == 0 { return x } 71 return (x >> nn) & ((1 << (64 - nn)) - 1) 72} 73 74// === nx_rotl64 -- rotate left, canonical idiom === 75// 76// Naive rotl is `(x << n) | (x >> (64 - n))` but the right-shift half 77// must be logical, not arithmetic. Substitute nx_lshr64-style mask. 78// 79// The shift-distance for the right half is `(64 - n)`; the count of 80// surviving real bits is therefore `64 - (64 - n) = n`. 81// Hence the right-mask exponent is `n`, not `64 - n`. 82// 83// ROTL(x, n) = (x << n) | ((x >> (64-n)) & ((1 << n) - 1)) 84// 85// !! GOLD STANDARD !! Any deviation will silently break >50% of inputs. 86// Delegated to nx_bits_rotl64 (rolq on x86_64 / rol on rv64 Zbb) -- 87// 1 cycle vs ~5 ops of the mask-shift phrasing. 88func nx_rotl64(x: i64, n: i64) -> i64 { 89 return nx_bits_rotl64(x, n) 90} 91 92func nx_rotr64(x: i64, n: i64) -> i64 { 93 return nx_bits_rotr64(x, n) 94} 95 96// === Self-KAT helper (callable from smokes) === 97// Returns 0 on full pass, non-zero bitmap of which subtest failed. 98// (Single-result self-test so a smoke can call once + check zero.) 99func nx_bitops_self_test() -> i64 { 100 var fail_mask: i64 = 0 101 // rotl(0x8000000000000001, 1) should be 3 102 if nx_rotl64(0x8000000000000001, 1) != 0x0000000000000003 { 103 fail_mask = fail_mask | 1 104 } 105 // rotl(0x8000000000000000, 32) should be 0x80000000 106 if nx_rotl64(0x8000000000000000, 32) != 0x0000000080000000 { 107 fail_mask = fail_mask | 2 108 } 109 // rotl(0xff00ff00ff00ff00, 4) should be 0xf00ff00ff00ff00f 110 if nx_rotl64(0xff00ff00ff00ff00, 4) != 0xf00ff00ff00ff00f { 111 fail_mask = fail_mask | 4 112 } 113 // rotr(0x3, 1) = 0x8000000000000001 114 if nx_rotr64(0x3, 1) != 0x8000000000000001 { 115 fail_mask = fail_mask | 8 116 } 117 // lshr(-1, 1) = 0x7FFFFFFFFFFFFFFF 118 if nx_lshr64(0xffffffffffffffff, 1) != 0x7fffffffffffffff { 119 fail_mask = fail_mask | 16 120 } 121 return fail_mask 122}