nx_multsynth.nx source

1// nx_multsynth.nx -- GATE-LEVEL search space #1: synthesize a MULTIPLIER from gates (the 2// Vedic / array-multiplier domain). A 2x2 bit-multiplier's four output bits are each a 3// 4-input boolean function; the team finds the minimal circuit for each and verifies it 4// EXACTLY over all 16 input combinations (the truth-table-as-bitmask trick at 4 inputs: 5// columns a0=0xAAAA, a1=0xCCCC, b0=0xF0F0, b1=0xFF00 -> a program's 16-bit output IS its 6// truth table). This is where exhaustive gate-level search competes with hardware multiplier 7// designs (Urdhva Tiryagbhyam etc.) -- the team's bits-up substrate, feeding the ALU upward. 8// license_tier: ORIGINAL 9 10import "nx_boolsynth.nx" // bl_eval, bl_is_unary, BL_AND/OR/XOR/NOT 11 12const B4_A0: i64 = 43690 // 0xAAAA 13const B4_A1: i64 = 52428 // 0xCCCC 14const B4_B0: i64 = 61680 // 0xF0F0 15const B4_B1: i64 = 65280 // 0xFF00 16const B4_MASK: i64 = 65535 // 0xFFFF 17 18// 4-input exhaustive synth: slots 0..3 = inputs, op t writes slot t+4; result = slot L+3. 19func bl4_enum(op: *i64, a: *i64, b: *i64, t: i64, L: i64, sv: *i64, target: i64) -> i64 { 20 if t == L { if (sv[L + 3] & B4_MASK) == target { return 1 } return 0 } 21 let nav: i64 = t + 4 22 let rslot: i64 = t + 4 23 var o: i64 = 0 24 while o < 4 { 25 if bl_is_unary(o) == 1 { 26 var i: i64 = 0 27 while i < nav { sv[rslot] = bl_eval(o, sv[i], 0); op[t]=o; a[t]=i; b[t]=i; if bl4_enum(op,a,b,t+1,L,sv,target) == 1 { return 1 } i = i + 1 } 28 } else { 29 var i: i64 = 0 30 while i < nav { var j: i64 = i; while j < nav { sv[rslot] = bl_eval(o, sv[i], sv[j]); op[t]=o; a[t]=i; b[t]=j; if bl4_enum(op,a,b,t+1,L,sv,target) == 1 { return 1 } j = j + 1 } i = i + 1 } 31 } 32 o = o + 1 33 } 34 return 0 35} 36func bl4_find(target: i64, op: *i64, a: *i64, b: *i64, maxL: i64) -> i64 { 37 let sv: *i64 = sys_mmap(8 * (maxL + 8)) as *i64 38 sv[0]=B4_A0; sv[1]=B4_A1; sv[2]=B4_B0; sv[3]=B4_B1 39 if (B4_A0 & B4_MASK) == target { return 0 } 40 if (B4_A1 & B4_MASK) == target { return 0 } 41 if (B4_B0 & B4_MASK) == target { return 0 } 42 if (B4_B1 & B4_MASK) == target { return 0 } 43 var L: i64 = 1 44 while L <= maxL { if bl4_enum(op, a, b, 0, L, sv, target) == 1 { return L } L = L + 1 } 45 return 0 - 1 46} 47 48// the 16-bit truth table for output bit k of the 2x2 product (2*a1+a0)*(2*b1+b0). 49func mult_tt(k: i64) -> i64 { 50 var tt: i64 = 0 51 var p: i64 = 0 52 while p < 16 { 53 let a0: i64 = (B4_A0 >> p) & 1; let a1: i64 = (B4_A1 >> p) & 1 54 let b0: i64 = (B4_B0 >> p) & 1; let b1: i64 = (B4_B1 >> p) & 1 55 let prod: i64 = (2 * a1 + a0) * (2 * b1 + b0) 56 if ((prod >> k) & 1) == 1 { tt = tt | (1 << p) } 57 p = p + 1 58 } 59 return tt 60} 61 62// re-evaluate a synthesized circuit on the 4 columns -> its 16-bit truth table (exact check). 63func bl4_reeval(op: *i64, a: *i64, b: *i64, L: i64) -> i64 { 64 let sv: *i64 = sys_mmap(8 * (L + 8)) as *i64 65 sv[0]=B4_A0; sv[1]=B4_A1; sv[2]=B4_B0; sv[3]=B4_B1 66 var t: i64 = 0; while t < L { sv[t+4] = bl_eval(op[t], sv[a[t]], sv[b[t]]); t = t + 1 } return sv[L+3] & B4_MASK 67}