`nx_recip64.nx` source

1// nx_recip64.nx -- the TRUE 64-bit Goldschmidt/Newton reciprocal divider as a
2// GATE-NETWORK. Mirrors the bit-exact scalar (nx_recip64_scalar_test) op-for-op,
3// using ONLY gate-sim cells + the proven 64x64->128 wide multiplier for mulh. No
4// 128-bit datapath: the normalized reciprocal keeps every value in 64 bits and
5// uses the high word of each product (mulhu = nx_mul_wide hi). Requires the sim's
6// LOGICAL SHR (the quotient can have bit 63 set). license_tier: ORIGINAL
7
8import "nx_mul_wide.nx"
9
10const R64_ITERS: i64 = 7
11const R64_KCORR: i64 = 6
12
13// returns the HI net (mulhu) of a*b.
14func r64_mulhu(g: *NxGsim, a: i64, b: i64) -> i64 {
15    let hio: *i64 = sys_mmap(8) as *i64
16    hio[0] = 0
17    nx_mul_wide_synth(g, a, b, hio)
18    return hio[0]
19}
20
21// 64-bit priority encoder: net p with 2^p <= D < 2^(p+1), D in [1, 2^64).
22func r64_msb(g: *NxGsim, nd: i64) -> i64 {
23    let c1: i64 = div_const(g, 1)
24    var p: i64 = div_const(g, 0)
25    var k: i64 = 1
26    while k < 64 {
27        let pow: i64 = div_const(g, 1 << k)
28        let lt: i64 = div_op2(g, NX_GATE_KIND_LTU, nd, pow)
29        let ge: i64 = div_op2(g, NX_GATE_KIND_XOR, lt, c1)
30        p = div_op2(g, NX_GATE_KIND_ADD, p, ge)
31        k = k + 1
32    }
33    return p
34}
35
36func nx_recip64_synth(g: *NxGsim, na: i64, nb: i64, rem_out: *i64) -> i64 {
37    let c0: i64 = div_const(g, 0)
38    let c1: i64 = div_const(g, 1)
39    let c63: i64 = div_const(g, 63)
40    let half: i64 = div_const(g, 1 << 63)      // 2^63  (x = 1.0 in Q63)
41    let allones: i64 = div_const(g, 0 - 1)
42
43    let p: i64 = r64_msb(g, nb)
44    let s: i64 = div_op2(g, NX_GATE_KIND_SUB, c63, p)
45    let Dn: i64 = div_op2(g, NX_GATE_KIND_SHL, nb, s)
46    var X: i64 = half
47
48    var it: i64 = 0
49    while it < R64_ITERS {
50        let dx: i64 = r64_mulhu(g, Dn, X)
51        let t: i64 = div_op2(g, NX_GATE_KIND_SUB, c0, dx)        // 2^64 - dx
52        let Xm: i64 = r64_mulhu(g, X, t)
53        let lt: i64 = div_op2(g, NX_GATE_KIND_LTU, Xm, half)     // Xm < 2^63 ?
54        let xshl: i64 = div_op2(g, NX_GATE_KIND_SHL, Xm, c1)
55        X = div_mux(g, lt, xshl, allones)                        // cap at ALLONES
56        it = it + 1
57    }
58
59    let nxhi: i64 = r64_mulhu(g, na, X)
60    var q: i64 = div_op2(g, NX_GATE_KIND_SHR, nxhi, p)           // LOGICAL >> msb(D)
61
62    var kc: i64 = 0
63    while kc < R64_KCORR {
64        let phi: i64 = r64_mulhu(g, q, nb)
65        let qD: i64 = div_op2(g, NX_GATE_KIND_MUL, q, nb)
66        let phigt: i64 = div_op2(g, NX_GATE_KIND_NEQ, phi, c0)   // q*D >= 2^64
67        let nlt: i64 = div_op2(g, NX_GATE_KIND_LTU, na, qD)      // N < q*D (low)
68        let toobig: i64 = div_op2(g, NX_GATE_KIND_OR, phigt, nlt)
69        let qdec: i64 = div_op2(g, NX_GATE_KIND_SUB, q, c1)
70        // up branch: (q+1) doesn't wrap, (q+1)*D fits, and <= N
71        let qp1: i64 = div_op2(g, NX_GATE_KIND_ADD, q, c1)
72        let qp1nz: i64 = div_op2(g, NX_GATE_KIND_NEQ, qp1, c0)
73        let phu: i64 = r64_mulhu(g, qp1, nb)
74        let phuz: i64 = div_op2(g, NX_GATE_KIND_EQ, phu, c0)
75        let qp1D: i64 = div_op2(g, NX_GATE_KIND_MUL, qp1, nb)
76        let nle: i64 = div_op2(g, NX_GATE_KIND_LTU, na, qp1D)    // N < qp1*D
77        let nge: i64 = div_op2(g, NX_GATE_KIND_XOR, nle, c1)     // qp1*D <= N
78        let f1: i64 = div_op2(g, NX_GATE_KIND_AND, qp1nz, phuz)
79        let fits: i64 = div_op2(g, NX_GATE_KIND_AND, f1, nge)
80        let qinc: i64 = div_mux(g, fits, qp1, q)
81        q = div_mux(g, toobig, qdec, qinc)
82        kc = kc + 1
83    }
84
85    let qDf: i64 = div_op2(g, NX_GATE_KIND_MUL, q, nb)
86    let r: i64 = div_op2(g, NX_GATE_KIND_SUB, na, qDf)
87    rem_out[0] = r
88    return q
89}
nx_recip64.nx source

`nx_recip64.nx` source
