nx_alu_divider_r4.nx source

1// nx_alu_divider_r4.nx -- the divider's QUANTITATIVE exceed: a RADIX-4 divider 2// that resolves 2 quotient bits per iteration, so W/2 subtract-stages instead of 3// the radix-2 restoring divider's W -- ~half the sequential latency depth. 4// 5// This is the QUANT half of the full exceed (the QUAL half = exhaustive 100% 6// verification, nx_alu_divider_exhaustive_test). A full S-class exceed needs 7// BOTH: radix-4 must be FASTER (fewer stages, measured) AND still 100%-correct 8// (exhaustively verified) -- faster AND more capable. 9// 10// Algorithm (radix-4 restoring, MSB-first, width even): 11// precompute b, 2b, 3b; rem=0, quo=0; for s in 0..W/2-1: 12// rem4 = (rem<<2) | next-2-bits(a) 13// q in {0,1,2,3} = count of {rem4>=b, rem4>=2b, rem4>=3b} (rem4<4b => q<=3) 14// rem = rem4 - q*b ; quo = (quo<<2) | q 15// Reuses nx_alu_divider's div_const/div_op2/div_mux gate-builders. 16// Research: radix-4 SRT/restoring division -- Parhami, Computer Arithmetic; 17// Hennessy & Patterson. [CANON] license_tier: ORIGINAL 18 19import "nx_alu_divider.nx" 20 21// Synthesize a radix-4 divider for nets na (dividend) / nb (divisor), width even. 22// rem_out[0] := remainder net; returns the quotient net. 23func nx_div_synth_r4(g: *NxGsim, na: i64, nb: i64, width: i64, rem_out: *i64) -> i64 { 24 let c0: i64 = div_const(g, 0) 25 let c1: i64 = div_const(g, 1) 26 let c2: i64 = div_const(g, 2) 27 let c3: i64 = div_const(g, 3) 28 let b1: i64 = nb 29 let b2: i64 = div_op2(g, NX_GATE_KIND_SHL, nb, c1) // 2b 30 let b3: i64 = div_op2(g, NX_GATE_KIND_ADD, b2, nb) // 3b 31 var rem: i64 = c0 32 var quo: i64 = c0 33 let stages: i64 = width / 2 34 var s: i64 = 0 35 while s < stages { 36 let shamt: i64 = width - 2 - 2 * s 37 let cs: i64 = div_const(g, shamt) 38 let shifted: i64 = div_op2(g, NX_GATE_KIND_SHL, rem, c2) // rem << 2 39 let abits_sh: i64 = div_op2(g, NX_GATE_KIND_SHR, na, cs) // a >> shamt 40 let abits: i64 = div_op2(g, NX_GATE_KIND_AND, abits_sh, c3) // & 3 (2 bits) 41 let rem4: i64 = div_op2(g, NX_GATE_KIND_OR, shifted, abits) // (rem<<2)|bits 42 // ge_k = (rem4 >= k*b) = !(rem4 < k*b) 43 let lt1: i64 = div_op2(g, NX_GATE_KIND_LTU, rem4, b1) 44 let ge1: i64 = div_op2(g, NX_GATE_KIND_XOR, lt1, c1) 45 let lt2: i64 = div_op2(g, NX_GATE_KIND_LTU, rem4, b2) 46 let ge2: i64 = div_op2(g, NX_GATE_KIND_XOR, lt2, c1) 47 let lt3: i64 = div_op2(g, NX_GATE_KIND_LTU, rem4, b3) 48 let ge3: i64 = div_op2(g, NX_GATE_KIND_XOR, lt3, c1) 49 // q*b = largest fitting multiple: ge3? 3b : (ge2? 2b : (ge1? b : 0)) 50 let m1: i64 = div_mux(g, ge1, b1, c0) 51 let m2: i64 = div_mux(g, ge2, b2, m1) 52 let qb: i64 = div_mux(g, ge3, b3, m2) 53 let rem_next: i64 = div_op2(g, NX_GATE_KIND_SUB, rem4, qb) // the ONE subtract per stage 54 // q = ge1 + ge2 + ge3 (in {0..3}); quo = (quo<<2) | q 55 let q01: i64 = div_op2(g, NX_GATE_KIND_ADD, ge1, ge2) 56 let qd: i64 = div_op2(g, NX_GATE_KIND_ADD, q01, ge3) 57 let quo_sh: i64 = div_op2(g, NX_GATE_KIND_SHL, quo, c2) 58 let quo_next: i64 = div_op2(g, NX_GATE_KIND_OR, quo_sh, qd) 59 rem = rem_next 60 quo = quo_next 61 s = s + 1 62 } 63 rem_out[0] = rem 64 return quo 65}