nx_p256_solinas_fast.nx source

1// nx_p256_solinas_fast.nx -- a FASTER NIST P-256 Solinas reducer, bit-exact with the production 2// _p256_solinas_reduce. The production version issues ~60 _r_addw FUNCTION CALLS, each propagating 3// a carry up a 9-limb memory accumulator on every word add. This version DEFERS the carry: it sums 4// each limb as a wide 64-bit value (max ~6*(2^32-1) < 2^35, no overflow) with plain array adds (no 5// calls, no per-add carry loop), then does ONE normalization pass before the identical reduce/subtract 6// tail. Same S-term table, same _r_reduce9 / _r_cmp8 helpers, same final POS-NEG mod p -> the result 7// is identical (proven by nx_p256_solinas_fast_difftest). Uses NO compiler intrinsic, so it builds 8// with the live compiler; kept SEPARATE so the production reducer is untouched until measured+greenlit. 9// license_tier: ORIGINAL 10import "nx_p256_field_mul.nx" // _r_reduce9, _r_cmp8, u256_alloc, p256_field_load_p, nx_scratch, constants 11 12func _p256_solinas_reduce_fast(out8: *i64, c: *i64) -> i64 { 13 let p: *i64 = u256_alloc() 14 p256_field_load_p(p) 15 let sc: *i64 = (nx_scratch(18 * 8)) as *i64 16 var z: i64 = 0 17 while z < 18 { sc[z] = 0; z = z + 1 } 18 let POS: *i64 = sc 19 let NEG: *i64 = (sc as i64 + 9 * 8) as *i64 20 21 let c0: i64 = c[0] & NX_U256_LIMB_MASK 22 let c1: i64 = c[1] & NX_U256_LIMB_MASK 23 let c2: i64 = c[2] & NX_U256_LIMB_MASK 24 let c3: i64 = c[3] & NX_U256_LIMB_MASK 25 let c4: i64 = c[4] & NX_U256_LIMB_MASK 26 let c5: i64 = c[5] & NX_U256_LIMB_MASK 27 let c6: i64 = c[6] & NX_U256_LIMB_MASK 28 let c7: i64 = c[7] & NX_U256_LIMB_MASK 29 let c8: i64 = c[8] & NX_U256_LIMB_MASK 30 let c9: i64 = c[9] & NX_U256_LIMB_MASK 31 let c10: i64 = c[10] & NX_U256_LIMB_MASK 32 let c11: i64 = c[11] & NX_U256_LIMB_MASK 33 let c12: i64 = c[12] & NX_U256_LIMB_MASK 34 let c13: i64 = c[13] & NX_U256_LIMB_MASK 35 let c14: i64 = c[14] & NX_U256_LIMB_MASK 36 let c15: i64 = c[15] & NX_U256_LIMB_MASK 37 38 // ---- POS = s1 + 2*s2 + 2*s3 + s4 + s5, accumulated WIDE (deferred carry) ---- 39 POS[0] = c0; POS[1] = c1; POS[2] = c2; POS[3] = c3 40 POS[4] = c4; POS[5] = c5; POS[6] = c6; POS[7] = c7; POS[8] = 0 41 // 2*s2 = (c15,c14,c13,c12,c11,0,0,0) doubled -> limbs 3..7 42 POS[3] = POS[3] + c11 + c11; POS[4] = POS[4] + c12 + c12; POS[5] = POS[5] + c13 + c13 43 POS[6] = POS[6] + c14 + c14; POS[7] = POS[7] + c15 + c15 44 // 2*s3 = (0,c15,c14,c13,c12,0,0,0) doubled -> limbs 3..6 45 POS[3] = POS[3] + c12 + c12; POS[4] = POS[4] + c13 + c13; POS[5] = POS[5] + c14 + c14; POS[6] = POS[6] + c15 + c15 46 // s4 = (c15,c14,0,0,0,c10,c9,c8) 47 POS[0] = POS[0] + c8; POS[1] = POS[1] + c9; POS[2] = POS[2] + c10; POS[6] = POS[6] + c14; POS[7] = POS[7] + c15 48 // s5 = (c8,c13,c15,c14,c13,c11,c10,c9) 49 POS[0] = POS[0] + c9; POS[1] = POS[1] + c10; POS[2] = POS[2] + c11; POS[3] = POS[3] + c13 50 POS[4] = POS[4] + c14; POS[5] = POS[5] + c15; POS[6] = POS[6] + c13; POS[7] = POS[7] + c8 51 52 // ---- NEG = s6 + s7 + s8 + s9 ---- 53 // s6 = (c10,c8,0,0,0,c13,c12,c11) 54 NEG[0] = c11; NEG[1] = c12; NEG[2] = c13; NEG[3] = 0; NEG[4] = 0; NEG[5] = 0; NEG[6] = c8; NEG[7] = c10; NEG[8] = 0 55 // s7 = (c11,c9,0,0,c15,c14,c13,c12) 56 NEG[0] = NEG[0] + c12; NEG[1] = NEG[1] + c13; NEG[2] = NEG[2] + c14; NEG[3] = NEG[3] + c15; NEG[6] = NEG[6] + c9; NEG[7] = NEG[7] + c11 57 // s8 = (c12,0,c10,c9,c8,c15,c14,c13) 58 NEG[0] = NEG[0] + c13; NEG[1] = NEG[1] + c14; NEG[2] = NEG[2] + c15; NEG[3] = NEG[3] + c8 59 NEG[4] = NEG[4] + c9; NEG[5] = NEG[5] + c10; NEG[7] = NEG[7] + c12 60 // s9 = (c13,0,c11,c10,c9,0,c15,c14) 61 NEG[0] = NEG[0] + c14; NEG[1] = NEG[1] + c15; NEG[3] = NEG[3] + c9; NEG[4] = NEG[4] + c10; NEG[5] = NEG[5] + c11; NEG[7] = NEG[7] + c13 62 63 // ---- ONE normalization pass each (wide 64-bit limbs -> canonical 32-bit + top carry) ---- 64 var cr: i64 = 0 65 var i: i64 = 0 66 while i < 9 { let t: i64 = POS[i] + cr; POS[i] = t & NX_U256_LIMB_MASK; cr = t >> NX_U256_LIMB_BITS; i = i + 1 } 67 cr = 0; i = 0 68 while i < 9 { let t: i64 = NEG[i] + cr; NEG[i] = t & NX_U256_LIMB_MASK; cr = t >> NX_U256_LIMB_BITS; i = i + 1 } 69 70 // ---- identical tail: reduce each to [0,p), then out = (POS - NEG) mod p ---- 71 _r_reduce9(POS, p) 72 _r_reduce9(NEG, p) 73 74 if _r_cmp8(POS, NEG) >= 0 { 75 var borrow: i64 = 0 76 var j: i64 = 0 77 while j < NX_U256_LIMBS { 78 let d: i64 = (POS[j] & NX_U256_LIMB_MASK) - (NEG[j] & NX_U256_LIMB_MASK) - borrow 79 if d < 0 { out8[j] = (d + (1 << NX_U256_LIMB_BITS)) & NX_U256_LIMB_MASK; borrow = 1 } 80 else { out8[j] = d & NX_U256_LIMB_MASK; borrow = 0 } 81 j = j + 1 82 } 83 } else { 84 let t: *i64 = (nx_scratch(9 * 8)) as *i64 85 var z2: i64 = 0 86 while z2 < 9 { t[z2] = 0; z2 = z2 + 1 } 87 var carry: i64 = 0 88 var k: i64 = 0 89 while k < NX_U256_LIMBS { 90 let v: i64 = (POS[k] & NX_U256_LIMB_MASK) + (p[k] & NX_U256_LIMB_MASK) + carry 91 t[k] = v & NX_U256_LIMB_MASK 92 carry = v >> NX_U256_LIMB_BITS 93 k = k + 1 94 } 95 t[8] = carry 96 var borrow: i64 = 0 97 var j: i64 = 0 98 while j < NX_U256_LIMBS { 99 let d: i64 = (t[j] & NX_U256_LIMB_MASK) - (NEG[j] & NX_U256_LIMB_MASK) - borrow 100 if d < 0 { t[j] = (d + (1 << NX_U256_LIMB_BITS)) & NX_U256_LIMB_MASK; borrow = 1 } 101 else { t[j] = d & NX_U256_LIMB_MASK; borrow = 0 } 102 j = j + 1 103 } 104 t[8] = (t[8] & NX_U256_LIMB_MASK) - borrow 105 _r_reduce9(t, p) 106 var m: i64 = 0 107 while m < NX_U256_LIMBS { out8[m] = t[m] & NX_U256_LIMB_MASK; m = m + 1 } 108 } 109 return 0 110} 111 112// Public framed entry (mirrors p256_field_reduce_solinas) for differential validation on arbitrary 113// 512-bit inputs. 114func p256_field_reduce_solinas_fast(out_8: *i64, c_16: *i64) -> i64 { 115 let _fm: i64 = nx_scratch_save() 116 _p256_solinas_reduce_fast(out_8, c_16) 117 nx_scratch_restore(_fm) 118 return 0 119}