nx_alu_divider_r8.nx source

1// nx_alu_divider_r8.nx -- radix-8 divider (3 quotient bits/iteration => W/3 2// subtract-stages). Bottom-up latency iteration on the divider car (don't move 3// up until S-class): radix-2 (W) -> radix-4 (W/2) -> radix-8 (W/3) -> ... toward 4// the multiplicative frontier (Goldschmidt ~log W). Same proven digit-recurrence 5// invariant, q-digit in {0..7} via 7 compare-multiples + a cascade. Reuses 6// nx_alu_divider_r4 (radix-2 + radix-4) helpers. width must be a multiple of 3. 7// license_tier: ORIGINAL 8 9import "nx_alu_divider_r4.nx" 10 11func nx_div_synth_r8(g: *NxGsim, na: i64, nb: i64, width: i64, rem_out: *i64) -> i64 { 12 let c0: i64 = div_const(g, 0) 13 let c1: i64 = div_const(g, 1) 14 let c3: i64 = div_const(g, 3) // shift by 3 (radix-8) 15 let c7: i64 = div_const(g, 7) // low-3-bit mask 16 // precompute b*1 .. b*7 17 let bmul: *i64 = sys_mmap(8 * 8) as *i64 18 var k: i64 = 1 19 while k <= 7 { 20 let ck: i64 = div_const(g, k) 21 bmul[k] = div_op2(g, NX_GATE_KIND_MUL, nb, ck) 22 k = k + 1 23 } 24 var rem: i64 = c0 25 var quo: i64 = c0 26 let stages: i64 = width / 3 27 var s: i64 = 0 28 while s < stages { 29 let shamt: i64 = width - 3 - 3 * s 30 let cs: i64 = div_const(g, shamt) 31 let shifted: i64 = div_op2(g, NX_GATE_KIND_SHL, rem, c3) // rem << 3 32 let sh: i64 = div_op2(g, NX_GATE_KIND_SHR, na, cs) // a >> shamt 33 let abits: i64 = div_op2(g, NX_GATE_KIND_AND, sh, c7) // 3 bits 34 let rem8: i64 = div_op2(g, NX_GATE_KIND_OR, shifted, abits) // (rem<<3)|bits ; < 8b 35 var qsum: i64 = c0 36 var qb: i64 = c0 37 var j: i64 = 1 38 while j <= 7 { 39 let lt: i64 = div_op2(g, NX_GATE_KIND_LTU, rem8, bmul[j]) // rem8 <u j*b 40 let ge: i64 = div_op2(g, NX_GATE_KIND_XOR, lt, c1) // ge_j = !lt 41 qsum = div_op2(g, NX_GATE_KIND_ADD, qsum, ge) // q = sum ge_j (0..7) 42 qb = div_mux(g, ge, bmul[j], qb) // cascade: largest j*b <= rem8 43 j = j + 1 44 } 45 let rem_next: i64 = div_op2(g, NX_GATE_KIND_SUB, rem8, qb) // ONE subtract per stage 46 let quo_sh: i64 = div_op2(g, NX_GATE_KIND_SHL, quo, c3) 47 let quo_next: i64 = div_op2(g, NX_GATE_KIND_OR, quo_sh, qsum) 48 rem = rem_next 49 quo = quo_next 50 s = s + 1 51 } 52 rem_out[0] = rem 53 return quo 54}