code wiki / _hdl_build / nx_recip_div_w.nx
nx_recip_div_w.nx source
↩ module page · 120 lines · 4902 B
1// nx_recip_div_w.nx -- the Newton/Goldschmidt reciprocal divider as a WIDTH-
2// PARAMETERIZED gate-network generator (W in [17,30]) -- the Seed-style "emit the
3// optimal form for the target", generalised from the W=24 instance. Composes the
4// proven 64x64->128 wide multiplier for the only product that overflows i64 (x*t).
5//
6// Envelope: W in [17,30]. The upper bound is where 2F^2 = 2^(2W+1) still fits i64
7// (W=30 -> 2^61 < 2^63; W=31 -> 2^63 = INT_MIN, breaks). Below it every product but
8// x*t fits a single MUL; x*t (<= 2^(3W+2)) is built 128-bit and shifted >>2W via
9// x = (hi << (64-2W)) | ((lo >> 2W) & ((1<<(64-2W)) - 1)).
10// Seed = the minimax (48F-32Dn)/17 (~4 bits, scale-invariant), 3 Newton iters
11// (-> ~32 bits >= W), KCORR=3 (maxcorr<=1 over the envelope). license_tier: ORIGINAL
12
13import "nx_mul_wide.nx"
14
15const RDW_ITERS: i64 = 3
16const RDW_KCORR: i64 = 3
17
18// priority encoder: net = p with 2^p <= D < 2^(p+1), for D in [1, 2^W).
19func rdw_msb_synth(g: *NxGsim, nd: i64, W: i64) -> i64 {
20 let c1: i64 = div_const(g, 1)
21 var p: i64 = div_const(g, 0)
22 var k: i64 = 1
23 while k < W {
24 let pow: i64 = div_const(g, 1 << k)
25 let lt: i64 = div_op2(g, NX_GATE_KIND_LTU, nd, pow)
26 let ge: i64 = div_op2(g, NX_GATE_KIND_XOR, lt, c1)
27 p = div_op2(g, NX_GATE_KIND_ADD, p, ge)
28 k = k + 1
29 }
30 return p
31}
32
33// exact floor(num/17): `stages` MSB-first restoring stages (num < 2^stages).
34func rdw_div17(g: *NxGsim, num: i64, stages: i64) -> i64 {
35 let c0: i64 = div_const(g, 0)
36 let c1: i64 = div_const(g, 1)
37 let c17: i64 = div_const(g, 17)
38 var rem: i64 = c0
39 var quo: i64 = c0
40 var i: i64 = stages - 1
41 while i >= 0 {
42 let ci: i64 = div_const(g, i)
43 let sh: i64 = div_op2(g, NX_GATE_KIND_SHL, rem, c1)
44 let absh: i64 = div_op2(g, NX_GATE_KIND_SHR, num, ci)
45 let abit: i64 = div_op2(g, NX_GATE_KIND_AND, absh, c1)
46 let remin: i64 = div_op2(g, NX_GATE_KIND_OR, sh, abit)
47 let lt: i64 = div_op2(g, NX_GATE_KIND_LTU, remin, c17)
48 let ge: i64 = div_op2(g, NX_GATE_KIND_XOR, lt, c1)
49 let sub: i64 = div_op2(g, NX_GATE_KIND_SUB, remin, c17)
50 let remn: i64 = div_mux(g, ge, sub, remin)
51 let qbit: i64 = div_op2(g, NX_GATE_KIND_SHL, ge, ci)
52 let quon: i64 = div_op2(g, NX_GATE_KIND_OR, quo, qbit)
53 rem = remn
54 quo = quon
55 i = i - 1
56 }
57 return quo
58}
59
60// Newton reciprocal divider at width W. rem_out[0]=remainder net; returns quotient.
61func nx_recip_div_w_synth(g: *NxGsim, na: i64, nb: i64, W: i64, rem_out: *i64) -> i64 {
62 let hio: *i64 = sys_mmap(8) as *i64
63 let F: i64 = 1 << W
64 let twoFF: i64 = 1 << (2 * W + 1)
65 let hishift: i64 = 64 - 2 * W
66 let c1: i64 = div_const(g, 1)
67 let cF48: i64 = div_const(g, 48 * F)
68 let c32: i64 = div_const(g, 32)
69 let cFF2: i64 = div_const(g, twoFF)
70 let cWm1: i64 = div_const(g, W - 1)
71 let cWp1: i64 = div_const(g, W + 1)
72 let chi: i64 = div_const(g, hishift)
73 let cshift: i64 = div_const(g, 2 * W)
74 let cmask: i64 = div_const(g, (1 << hishift) - 1)
75
76 let p: i64 = rdw_msb_synth(g, nb, W)
77 let s: i64 = div_op2(g, NX_GATE_KIND_SUB, cWm1, p)
78 let dn: i64 = div_op2(g, NX_GATE_KIND_SHL, nb, s)
79
80 let t32: i64 = div_op2(g, NX_GATE_KIND_MUL, c32, dn)
81 let num: i64 = div_op2(g, NX_GATE_KIND_SUB, cF48, t32)
82 var x: i64 = rdw_div17(g, num, W + 6)
83
84 var it: i64 = 0
85 while it < RDW_ITERS {
86 let dx: i64 = div_op2(g, NX_GATE_KIND_MUL, dn, x)
87 let t: i64 = div_op2(g, NX_GATE_KIND_SUB, cFF2, dx)
88 hio[0] = 0
89 let xtlo: i64 = nx_mul_wide_synth(g, x, t, hio)
90 let xthi: i64 = hio[0]
91 let hipart: i64 = div_op2(g, NX_GATE_KIND_SHL, xthi, chi)
92 let loshr: i64 = div_op2(g, NX_GATE_KIND_SHR, xtlo, cshift)
93 let lopart: i64 = div_op2(g, NX_GATE_KIND_AND, loshr, cmask)
94 x = div_op2(g, NX_GATE_KIND_OR, hipart, lopart)
95 it = it + 1
96 }
97
98 let nx_p: i64 = div_op2(g, NX_GATE_KIND_MUL, na, x)
99 let amt: i64 = div_op2(g, NX_GATE_KIND_ADD, cWp1, p)
100 var q: i64 = div_op2(g, NX_GATE_KIND_SHR, nx_p, amt)
101
102 var kc: i64 = 0
103 while kc < RDW_KCORR {
104 let qp1: i64 = div_op2(g, NX_GATE_KIND_ADD, q, c1)
105 let qp1D: i64 = div_op2(g, NX_GATE_KIND_MUL, qp1, nb)
106 let nlt: i64 = div_op2(g, NX_GATE_KIND_LTU, na, qp1D)
107 let le: i64 = div_op2(g, NX_GATE_KIND_XOR, nlt, c1)
108 let qD: i64 = div_op2(g, NX_GATE_KIND_MUL, q, nb)
109 let high: i64 = div_op2(g, NX_GATE_KIND_LTU, na, qD)
110 let qup: i64 = div_op2(g, NX_GATE_KIND_ADD, q, le)
111 let qdn: i64 = div_op2(g, NX_GATE_KIND_SUB, q, high)
112 q = div_mux(g, le, qup, div_mux(g, high, qdn, q))
113 kc = kc + 1
114 }
115
116 let qDf: i64 = div_op2(g, NX_GATE_KIND_MUL, q, nb)
117 let r: i64 = div_op2(g, NX_GATE_KIND_SUB, na, qDf)
118 rem_out[0] = r
119 return q
120}