nx_bigint_lib.nx source
↩ module page · 174 lines · 5884 B
1// nx_bigint_lib.nx -- multi-precision integer PRIMITIVES (unsigned), the IMPORTABLE library.
2//
3// Split 2026-07-09 from the nx_bigint.nx / bigint.nx twins (which were code-identical and BOTH carried a
4// main() KAT battery, making them unimportable into any main-bearing binary -- the nx_qa_score_lib precedent).
5// The twins now import THIS lib and keep their main() gates; new consumers (e.g. nx_swcompare_bench) import
6// the lib directly. ZERO imports by design: every primitive is pure limb math on caller-owned buffers (BI3),
7// so this lib is syscall-module-agnostic (safe under both syscalls.nx and nx_syscalls.nx import chains).
8//
9// Representation: array of u32 limbs in LITTLE-ENDIAN order (limb 0 is least-significant 32 bits), stored in
10// i64 slots (low 32 bits used) so 32x32 products and carried sums fit in i64 without overflow.
11//
12// Invariants (from the original):
13// BI1 Limbs past the declared length are never read; callers pass explicit lengths.
14// BI2 Results are written with LENGTH HINTS the caller allocates for (bi_add output needs n+1 limbs).
15// BI3 No heap allocation inside primitives -- caller owns limb buffers.
16// BI4 Comparison returns -1 / 0 / +1 like strcmp.
17// BI5 Arithmetic is UNSIGNED; signed lives at the caller's layer.
18// license_tier: ORIGINAL
19
20const LIMB_BITS: i64 = 32
21const LIMB_MASK: i64 = 0xFFFFFFFF
22
23// Copy `n` limbs from src to dst.
24func bi_copy(dst: *i64, src: *i64, n: i64) -> i64 {
25 var i: i64 = 0
26 while i < n { dst[i] = src[i]; i = i + 1 }
27 return 0
28}
29
30// Zero `n` limbs.
31func bi_zero(dst: *i64, n: i64) -> i64 {
32 var i: i64 = 0
33 while i < n { dst[i] = 0; i = i + 1 }
34 return 0
35}
36
37// Compare: returns -1 if a < b, 0 if equal, +1 if a > b. Both
38// operands treated as n-limb unsigned; caller normalises lengths.
39func bi_cmp(a: *i64, b: *i64, n: i64) -> i64 {
40 var i: i64 = n - 1
41 while i >= 0 {
42 let av: i64 = a[i] & LIMB_MASK
43 let bv: i64 = b[i] & LIMB_MASK
44 if av < bv { return -1 }
45 if av > bv { return 1 }
46 i = i - 1
47 }
48 return 0
49}
50
51// Add two n-limb unsigned: r = a + b. `r` must hold n+1 limbs
52// (the top limb captures the final carry, 0 or 1).
53func bi_add(r: *i64, a: *i64, b: *i64, n: i64) -> i64 {
54 var carry: i64 = 0
55 var i: i64 = 0
56 while i < n {
57 let s: i64 = (a[i] & LIMB_MASK) + (b[i] & LIMB_MASK) + carry
58 r[i] = s & LIMB_MASK
59 carry = (s >> 32) & 1
60 i = i + 1
61 }
62 r[n] = carry
63 return 0
64}
65
66// Subtract: r = a - b. Returns borrow (0 or 1). Requires a >= b
67// for a meaningful result (borrow==0); borrow==1 signals caller to
68// treat as "wraparound" / a < b.
69func bi_sub(r: *i64, a: *i64, b: *i64, n: i64) -> i64 {
70 var borrow: i64 = 0
71 var i: i64 = 0
72 while i < n {
73 let d: i64 = (a[i] & LIMB_MASK) - (b[i] & LIMB_MASK) - borrow
74 r[i] = d & LIMB_MASK
75 // Borrow if d went negative before masking.
76 if d < 0 { borrow = 1 } else { borrow = 0 }
77 i = i + 1
78 }
79 return borrow
80}
81
82// Shift left by 1 bit (multiply by 2). Returns the bit shifted
83// out of the top (0 or 1).
84func bi_shl1(r: *i64, n: i64) -> i64 {
85 var carry: i64 = 0
86 var i: i64 = 0
87 while i < n {
88 let v: i64 = r[i] & LIMB_MASK
89 r[i] = ((v << 1) | carry) & LIMB_MASK
90 carry = (v >> 31) & 1
91 i = i + 1
92 }
93 return carry
94}
95
96// Shift right by 1 bit (divide by 2, unsigned). Carry-in is a
97// single bit to OR into the top after shift.
98func bi_shr1(r: *i64, n: i64, carry_in: i64) -> i64 {
99 var carry: i64 = carry_in & 1
100 var i: i64 = n - 1
101 while i >= 0 {
102 let v: i64 = r[i] & LIMB_MASK
103 r[i] = ((carry << 31) | (v >> 1)) & LIMB_MASK
104 carry = v & 1
105 i = i - 1
106 }
107 return carry
108}
109
110// Multiply: r = a * b. a has `a_len` limbs, b has `b_len`, r
111// holds a_len + b_len limbs. Schoolbook O(n*m) -- fine up to
112// ~4096-bit operands. For larger, Karatsuba (O(n^1.58)) is a
113// future optimization.
114func bi_mul(r: *i64, a: *i64, a_len: i64, b: *i64, b_len: i64) -> i64 {
115 // Zero the output.
116 bi_zero(r, a_len + b_len)
117 var i: i64 = 0
118 while i < a_len {
119 let ai: i64 = a[i] & LIMB_MASK
120 var carry: i64 = 0
121 var j: i64 = 0
122 while j < b_len {
123 let bj: i64 = b[j] & LIMB_MASK
124 let rij: i64 = r[i + j] & LIMB_MASK
125 let prod: i64 = ai * bj + rij + carry
126 r[i + j] = prod & LIMB_MASK
127 carry = (prod >> 32) & LIMB_MASK
128 j = j + 1
129 }
130 r[i + b_len] = r[i + b_len] + carry
131 i = i + 1
132 }
133 return 0
134}
135
136// ---- byte <-> limb conversions -----------------------------------
137
138// Load big-endian bytes into little-endian limbs. bytes[0] is the
139// MOST-significant byte of the number; r[0] is the LEAST-
140// significant limb. `n_bytes` need not be a multiple of 4; the
141// remaining bytes of the top limb become zero.
142func bi_from_bytes_be(r: *i64, n_limbs: i64,
143 bytes: *u8, n_bytes: i64) -> i64 {
144 bi_zero(r, n_limbs)
145 var i: i64 = 0
146 while i < n_bytes {
147 let b: i64 = bytes[n_bytes - 1 - i]
148 let limb_idx: i64 = i / 4
149 let bit_off: i64 = (i % 4) * 8
150 if limb_idx < n_limbs {
151 r[limb_idx] = r[limb_idx] | (b << bit_off)
152 }
153 i = i + 1
154 }
155 return 0
156}
157
158// Serialize an n-limb little-endian bignum to big-endian bytes.
159func bi_to_bytes_be(out: *u8, n_bytes: i64,
160 r: *i64, n_limbs: i64) -> i64 {
161 var i: i64 = 0
162 while i < n_bytes {
163 let byte_idx_from_lsb: i64 = n_bytes - 1 - i
164 let limb_idx: i64 = byte_idx_from_lsb / 4
165 let bit_off: i64 = (byte_idx_from_lsb % 4) * 8
166 var b: i64 = 0
167 if limb_idx < n_limbs {
168 b = (r[limb_idx] >> bit_off) & 0xFF
169 }
170 out[i] = b
171 i = i + 1
172 }
173 return 0
174}