`nx_fpga_cmp.nx` source

1// nx_fpga_cmp.nx -- LIB: RUNG 8b -- the ALU COMPARE ops (SLT signed, SLTU unsigned) on the LUT4 fabric. New
2// mechanic: derive a result from a subtractor's INTERNAL signals (carry-out + sign bit), and use CONSTANT LUTs
3// (init 0xffff = always 1, the carry-in; init 0 = always 0, the fill). Computes a-b = a + ~b + 1, then:
4//   SLTU = NOT(carry-out)                              -- unsigned a<b iff the subtraction borrows.
5//   SLT  = (a_sign XOR b_sign) ? a_sign : (a-b)_sign   -- signed a<b, overflow-correct (differ-signs -> a is neg;
6//                                                          same-signs -> the (non-overflowing) diff's sign).
7// A control bit `unsigned` selects which (result in bit 0; bits 1..W-1 are 0). Verified vs nx_rv64im_alu_compute.
8//
9// FABRIC (npi = 2W+1: PI 0..W-1=a, W..2W-1=b, 2W=unsigned). ncells = 3W+6:
10//   cell 0 = const1 (init 0xffff)   cell 1 = const0 (init 0)
11//   cells 2..W+1   = notb_i = NOT(b_i)
12//   cells W+2..3W+1 = ripple adder a_i + notb_i, carry_0 = const1 (sum cell W+2+2i, carry cell W+2+2i+1)
13//   cell 3W+2 = sltu = NOT(carry-out)    3W+3 = diffsign = XOR(a_sign,b_sign)
14//   cell 3W+4 = slt = MUX(diffsign, subsign, a_sign)   3W+5 = res = MUX(unsigned, slt, sltu)
15// NEVER-BRICK (#26): pure integer, bounded, total, deterministic, zero hardware writes.
16// license_tier: ORIGINAL
17import "nx_fpga_adder.nx"
18import "nx_fpga_fabric.nx"
19import "nx_fpga_lut.nx"
20import "nx_syscalls.nx"
21const K_MAGIC_65535: i64 = 65535
22
23func fab_build_cmp(width: i64, inits: *i64, src: *i64, po_src: *i64) -> i64 {
24    let npi: i64 = 2*width + 1
25    let uns_pi: i64 = 2*width
26    let kNOT: i64 = fl_gate_to_lut4(FL_NOT)
27    let kXOR: i64 = fl_gate_to_lut4(FL_XOR)
28    let kMUX: i64 = fl_gate_to_lut4(FL_MUX)
29    let par: i64 = fab_parity3_init()
30    let maj: i64 = fab_maj3_init()
31    // constant LUTs (inputs = PI0, value independent of inputs)
32    inits[0] = K_MAGIC_65535; src[0]=0; src[1]=0; src[2]=0; src[3]=0       // const1 (always 1)
33    inits[1] = 0;     src[4]=0; src[5]=0; src[6]=0; src[7]=0       // const0 (always 0)
34    // NOT-b layer
35    var i: i64 = 0
36    while i < width {
37        let c: i64 = 2 + i
38        inits[c]=kNOT; src[c*4+0]=width+i; src[c*4+1]=width+i; src[c*4+2]=width+i; src[c*4+3]=width+i
39        i = i + 1
40    }
41    // ripple adder a_i + notb_i, carry-in = const1
42    i = 0
43    while i < width {
44        let sumc: i64 = width + 2 + 2*i
45        let cryc: i64 = width + 2 + 2*i + 1
46        let notb: i64 = npi + 2 + i
47        var carry: i64 = npi + 0                       // const1 cell -> cin = 1
48        if i > 0 { carry = npi + (width + 2 + 2*(i-1) + 1) }
49        inits[sumc]=par; src[sumc*4+0]=i; src[sumc*4+1]=notb; src[sumc*4+2]=carry; src[sumc*4+3]=i
50        inits[cryc]=maj; src[cryc*4+0]=i; src[cryc*4+1]=notb; src[cryc*4+2]=carry; src[cryc*4+3]=i
51        i = i + 1
52    }
53    let subsign_src: i64 = npi + (width + 2 + 2*(width-1))         // sub sum cell of bit W-1
54    let carryout_src: i64 = npi + (width + 2 + 2*(width-1) + 1)    // carry cell of bit W-1
55    let a_sign_pi: i64 = width - 1
56    let b_sign_pi: i64 = 2*width - 1
57    let sltu_c: i64 = 3*width + 2
58    let diff_c: i64 = 3*width + 3
59    let slt_c:  i64 = 3*width + 4
60    let res_c:  i64 = 3*width + 5
61    inits[sltu_c]=kNOT; src[sltu_c*4+0]=carryout_src; src[sltu_c*4+1]=carryout_src; src[sltu_c*4+2]=carryout_src; src[sltu_c*4+3]=carryout_src
62    inits[diff_c]=kXOR; src[diff_c*4+0]=a_sign_pi; src[diff_c*4+1]=b_sign_pi; src[diff_c*4+2]=a_sign_pi; src[diff_c*4+3]=a_sign_pi
63    // slt = MUX(sel=diffsign, in0=subsign, in1=a_sign) = diffsign ? a_sign : subsign
64    inits[slt_c]=kMUX; src[slt_c*4+0]=npi+diff_c; src[slt_c*4+1]=subsign_src; src[slt_c*4+2]=a_sign_pi; src[slt_c*4+3]=subsign_src
65    // res = MUX(sel=unsigned, in0=slt, in1=sltu) = unsigned ? sltu : slt
66    inits[res_c]=kMUX; src[res_c*4+0]=uns_pi; src[res_c*4+1]=npi+slt_c; src[res_c*4+2]=npi+sltu_c; src[res_c*4+3]=npi+slt_c
67    po_src[0] = npi + res_c
68    i = 1
69    while i < width { po_src[i] = npi + 1; i = i + 1 }             // const0 for the upper bits
70    return npi
71}
72
73// run; return the comparison bit (0/1) -- bit 0 of the result. unsigned=0 -> SLT, unsigned=1 -> SLTU.
74func fab_cmp_run(width: i64, npi: i64, inits: *i64, src: *i64, po_src: *i64, pi: *i64, co: *i64, a: i64, b: i64, unsigned: i64) -> i64 {
75    var i: i64 = 0
76    while i < width { pi[i] = (a >> i) & 1; pi[width+i] = (b >> i) & 1; i = i + 1 }
77    pi[2*width] = unsigned & 1
78    fab_eval(3*width + 6, npi, inits, src, pi, co)
79    return fab_po(po_src[0], npi, pi, co)
80}
nx_fpga_cmp.nx source

`nx_fpga_cmp.nx` source
