nx_alu_from_gates_test.nx source

1// nx_alu_from_gates_test.nx -- the team builds ARITHMETIC from BITS UP. The same gate-level 2// superoptimizer that minimizes boolean functions SYNTHESIZES the full adder itself: sum = 3// a^b^cin (truth table 0x96) and carry = majority(a,b,cin) (0xE8). The team then COMPOSES 4// those synthesized gates into an N-bit ripple adder and VERIFIES it computes real N-bit 5// addition over many inputs. Bits -> gates -> full adder -> ALU, every step synthesized and 6// verified by the team. The autonomous find-minimal-verify loop, operating at the HARDWARE/ 7// gate level, not just machine-code codegen. 8 9import "nx_boolsynth.nx" 10 11func ag_puts(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 12func ag_num(v: i64) -> i64 { 13 let bb: *u8 = sys_mmap(28); var m: i64 = v; if m < 0 { m = 0 - m } 14 let t: *u8 = sys_mmap(28); var k: i64 = 0 15 if m == 0 { t[0] = 48; k = 1 } 16 while m > 0 { t[k] = 48 + (m % 10); m = m / 10; k = k + 1 } 17 var i: i64 = 0; while i < k { bb[i] = t[k - 1 - i]; i = i + 1 } 18 sys_write(1, bb, k); return 0 19} 20func tally(r: *i64, n: i64) -> i64 { var ec: i64 = 0; var i: i64 = 0; while i < n { if r[i] != 1 { if ec == 0 { ec = i + 1 } } i = i + 1 } return ec } 21 22// evaluate a synthesized boolean circuit on single-BIT inputs (x0,x1,x2) -> output bit. 23func ag_eval1(op: *i64, a: *i64, b: *i64, L: i64, x0: i64, x1: i64, x2: i64) -> i64 { 24 let sv: *i64 = sys_mmap(8 * (L + 6)) as *i64 25 sv[0] = x0; sv[1] = x1; sv[2] = x2 26 var t: i64 = 0 27 while t < L { sv[t + 3] = bl_eval(op[t], sv[a[t]], sv[b[t]]); t = t + 1 } 28 return sv[L + 2] & 1 29} 30 31// an N-bit ripple adder built ENTIRELY from the synthesized full-adder gates. 32func ag_ripple_add(sop: *i64, sa: *i64, sb: *i64, sL: i64, cop: *i64, ca: *i64, cb: *i64, cL: i64, 33 x: i64, y: i64, N: i64) -> i64 { 34 var res: i64 = 0 35 var cin: i64 = 0 36 var i: i64 = 0 37 while i < N { 38 let ai: i64 = (x >> i) & 1 39 let bi: i64 = (y >> i) & 1 40 let si: i64 = ag_eval1(sop, sa, sb, sL, ai, bi, cin) 41 let co: i64 = ag_eval1(cop, ca, cb, cL, ai, bi, cin) 42 res = res | (si << i) 43 cin = co 44 i = i + 1 45 } 46 return res 47} 48 49func ag_main(r: *i64) -> i64 { 50 ag_puts("=== BITS UP: the team SYNTHESIZES a full adder from gates, composes an N-bit ALU, verifies ===\n" as *u8) 51 let sop: *i64 = sys_mmap(8*12) as *i64; let sa: *i64 = sys_mmap(8*12) as *i64; let sb: *i64 = sys_mmap(8*12) as *i64 52 let cop: *i64 = sys_mmap(8*12) as *i64; let ca: *i64 = sys_mmap(8*12) as *i64; let cb: *i64 = sys_mmap(8*12) as *i64 53 let sL: i64 = bl_find(150, sop, sa, sb, 6) // sum = a^b^cin (0x96) 54 let cL: i64 = bl_find(232, cop, ca, cb, 6) // carry= maj(a,b,cin) (0xE8) 55 ag_puts(" team synthesized FULL ADDER from gates: sum=" as *u8); ag_num(sL); ag_puts(" gates, carry=" as *u8); ag_num(cL); ag_puts(" gates\n" as *u8) 56 r[0] = 0; if sL > 0 { if cL > 0 { r[0] = 1 } } 57 58 // VERIFY the composed 8-bit ripple adder against native addition over many input pairs. 59 let N: i64 = 8 60 let mask: i64 = (1 << N) - 1 61 var bad: i64 = 0 62 var t: i64 = 0 63 while t < 600 { 64 let x: i64 = (t * 37 + 11) & mask 65 let y: i64 = (t * 53 + 7) & mask 66 let got: i64 = ag_ripple_add(sop, sa, sb, sL, cop, ca, cb, cL, x, y, N) 67 let want: i64 = (x + y) & mask 68 if got != want { bad = bad + 1 } 69 t = t + 1 70 } 71 ag_puts(" composed " as *u8); ag_num(N); ag_puts("-bit ripple ALU from those gates; verified over 600 input pairs: mismatches=" as *u8); ag_num(bad); ag_puts("\n" as *u8) 72 r[1] = 0; if bad == 0 { r[1] = 1 } 73 ag_puts("----------------------------------------------------------------\n" as *u8) 74 ag_puts(" same find-minimal-verify loop, now at the GATE/BITS level: arithmetic synthesized from gates, bottom-up.\n" as *u8) 75 return 2 76} 77 78func main() -> i64 { 79 let r: *i64 = sys_mmap(8 * 8) as *i64 80 let n: i64 = ag_main(r) 81 let ec: i64 = tally(r, n) 82 sys_exit(ec) 83 return ec 84}