nx_fpga_shift.nx source

1// nx_fpga_shift.nx -- LIB: RUNG 8c -- the ALU SHIFTS (SLL/SRL/SRA) as a BARREL SHIFTER on the LUT4 fabric. 2// The classic log-depth structure: log2(W)=6 stages (for W=64), stage k conditionally shifts by 2^k iff 3// shamt bit k is set. Two control bits unify all three shifts: `right` (0=left SLL, 1=right) and `arith` 4// (right-shift fill = original sign bit for SRA, else 0 for SRL/SLL). Per bit per stage = 2 MUX LUT4s 5// (pick the shifted source by direction, then pick shifted-vs-passthrough by shamt bit). Builds on nx_fpga_lut. 6// 7// FABRIC (npi = W+8): PI 0..W-1 = a, W..W+5 = shamt[0..5] (= b&0x3f), W+6 = right, W+7 = arith. ncells = 2+12W: 8// cell 0 = const0 (init 0) cell 1 = fill = MUX(arith, 0, a_sign) [right-shift in-bit] 9// stage k (k=0..5) cells [2+k*2W, 2+(k+1)*2W): per bit i: shifted_src = MUX(right, left_src, right_src), 10// out = MUX(shamt_k, in_i, shifted_src); where left_src_i = (i>=2^k)? in(i-2^k):0, 11// right_src_i = (i+2^k<W)? in(i+2^k):fill. Stage k's `in` vector = stage k-1's outputs (a for k=0). 12// POs = stage-5 outputs. NEVER-BRICK (#26): pure integer, bounded (2+12W cells), total, deterministic, no hw write. 13// license_tier: ORIGINAL 14import "nx_fpga_lut.nx" 15import "nx_fpga_fabric.nx" 16import "nx_syscalls.nx" 17 18func fab_build_shifter(width: i64, inits: *i64, src: *i64, po_src: *i64) -> i64 { 19 let npi: i64 = width + 8 20 let right_pi: i64 = width + 6 21 let arith_pi: i64 = width + 7 22 let a_sign_pi: i64 = width - 1 23 let kMUX: i64 = fl_gate_to_lut4(FL_MUX) 24 // const0 (cell 0), fill (cell 1) = MUX(arith, const0, a_sign) 25 inits[0] = 0; src[0]=0; src[1]=0; src[2]=0; src[3]=0 26 inits[1] = kMUX; src[4]=arith_pi; src[5]=npi+0; src[6]=a_sign_pi; src[7]=npi+0 27 let const0_src: i64 = npi + 0 28 let fill_src: i64 = npi + 1 29 // current input-vector wire sources (stage 0 input = a PIs) 30 let inwire: *i64 = sys_mmap(8 * (width + 4)) as *i64 31 let outwire: *i64 = sys_mmap(8 * (width + 4)) as *i64 32 var i: i64 = 0 33 while i < width { inwire[i] = i; i = i + 1 } 34 var base: i64 = 2 35 var k: i64 = 0 36 while k < 6 { 37 let d: i64 = 1 << k 38 let sel: i64 = width + k // shamt bit k PI 39 i = 0 40 while i < width { 41 let ss_cell: i64 = base + 2*i 42 let out_cell: i64 = base + 2*i + 1 43 var left_src: i64 = const0_src 44 if i >= d { left_src = inwire[i - d] } 45 var right_src: i64 = fill_src 46 if i + d < width { right_src = inwire[i + d] } 47 // shifted_src = MUX(right, left_src, right_src) = right ? right_src : left_src 48 inits[ss_cell]=kMUX; src[ss_cell*4+0]=right_pi; src[ss_cell*4+1]=left_src; src[ss_cell*4+2]=right_src; src[ss_cell*4+3]=left_src 49 // out = MUX(shamt_k, in_i, shifted_src) = shamt_k ? shifted_src : in_i 50 inits[out_cell]=kMUX; src[out_cell*4+0]=sel; src[out_cell*4+1]=inwire[i]; src[out_cell*4+2]=npi+ss_cell; src[out_cell*4+3]=inwire[i] 51 outwire[i] = npi + out_cell 52 i = i + 1 53 } 54 i = 0 55 while i < width { inwire[i] = outwire[i]; i = i + 1 } 56 base = base + 2*width 57 k = k + 1 58 } 59 i = 0 60 while i < width { po_src[i] = inwire[i]; i = i + 1 } 61 return npi 62} 63 64// run; assemble the W-bit shifted result. right=0->SLL, right=1&arith=0->SRL, right=1&arith=1->SRA. shamt = b & 0x3f. 65func fab_shift_run(width: i64, npi: i64, inits: *i64, src: *i64, po_src: *i64, pi: *i64, co: *i64, a: i64, shamt: i64, right: i64, arith: i64) -> i64 { 66 var i: i64 = 0 67 while i < width { pi[i] = (a >> i) & 1; i = i + 1 } 68 i = 0 69 while i < 6 { pi[width+i] = (shamt >> i) & 1; i = i + 1 } 70 pi[width+6] = right & 1 71 pi[width+7] = arith & 1 72 fab_eval(2 + 12*width, npi, inits, src, pi, co) 73 var s: i64 = 0 74 i = 0 75 while i < width { s = s | (fab_po(po_src[i], npi, pi, co) << i); i = i + 1 } 76 return s 77}