rhdl_ed25519_scalable_core/

fe17.rs

//! Radix-`2^17` field arithmetic units for the field machines.
//!
//! A [`Fe17`] holds fifteen 17-bit digits, least significant first, and is
//! always **canonical** (strictly below `p = 2^255 - 19`) at unit boundaries.
//! Fifteen digits of 17 bits are exactly 255 bits, so `2^255 = 19 (mod p)`
//! folds column `k + 15` onto column `k` with a factor of 19.
//!
//! [`FieldMulPar`] computes the fifteen folded columns
//! `c_k = sum_i a_i * b'_{k-i}` with `b'_j = b_j` or `19 b_j` (wrapped), as
//! fifteen 15-deep multiply-accumulate chains. Every product is
//! `17 x 22` bits, which fits the DSP48E2's `18 x 27` signed multiplier, and
//! every chain stage has the shape `P = PCIN + A * B`, which maps to a DSP
//! cascade without fabric adders. Operands are skewed by delay registers so
//! chain stage `i` sees its operands exactly `i` cycles after stage 0.
//! Three lazy carry passes, one 256-bit carry-propagate, and a two-candidate
//! final reduction return a canonical result after [`MUL_LATENCY`] cycles.
//!
//! [`FieldAddSub`] adds or subtracts two canonical elements in
//! [`ADD_LATENCY`] cycles. Subtraction adds `p - b` instead of negating, so
//! both operations share one adder and one final reduction.
//!
//! Both units accept a new request every clock and have a fixed latency with
//! no stalls. Each request carries an opaque 16-bit tag that comes back with
//! its result, which is how the field machine routes write-backs.

use rhdl::prelude::*;
use rhdl_fpga::core::dff::DFF;

use super::host::Fp;

/// Canonical field element in fifteen 17-bit digits (255 bits).
///
/// Value is `sum_k d[k] * 2^(17 k)`, always below `p` where a unit produces
/// or consumes it. Radix `2^17` matches the 17-bit unsigned operand that a
/// DSP48E2's 18-bit signed port accepts.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct Fe17 {
    /// Digits, least significant first.
    pub d: [b17; 15],
}

impl Fe17 {
    /// The field element zero (all digits zero).
    pub fn zero() -> Self {
        Fe17 { d: [b17(0); 15] }
    }
    /// Convert from the host model [`Fp`] by splitting it into 17-bit digits.
    pub fn from_fp(value: Fp) -> Self {
        let digits = value.digits17();
        Fe17 {
            d: digits.map(|x| b17(u128::from(x))),
        }
    }
    /// Convert back to the host model [`Fp`].
    pub fn to_fp(self) -> Fp {
        Fp::from_digits17(&self.d.map(|x| x.raw() as u32))
    }
}

/// Multiplier latency in clock edges: a request presented to
/// [`FieldMulPar`] before clock edge `t` (captured at `t`) is visible on the
/// output after edge `t + 22`, i.e. it occupies 23 register stages. The
/// field machine relies on this being fixed, because it routes results only
/// by tag and never waits for them.
pub const MUL_LATENCY: usize = 23;
/// Fixed add/subtract latency, counted the same way as [`MUL_LATENCY`]: five
/// register stages, so a request captured at edge `t` is on the output after
/// edge `t + 4`. The field machine routes results by tag and its barrel
/// (32 contexts) hides any latency up to the multiplier's, so this is free.
pub const ADD_LATENCY: usize = 5;

/// Multiplier request, sampled every clock (no handshake: the unit is
/// initiation-interval one).
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct FieldMulIn {
    /// Request valid. Invalid requests still flow through the datapath, but
    /// their result is not flagged valid.
    pub valid: bool,
    /// First factor (canonical).
    pub a: Fe17,
    /// Second factor (canonical).
    pub b: Fe17,
    /// Opaque tag returned with the product. The field machine packs the
    /// context and destination register into it.
    pub tag: b16,
}

/// Multiplier result, [`MUL_LATENCY`] cycles after the request.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct FieldMulOut {
    /// Result valid (the delayed request `valid`).
    pub valid: bool,
    /// Canonical product `a * b mod p`.
    pub r: Fe17,
    /// Tag captured with the request.
    pub tag: b16,
}

/// Operand row held by one chain stage: `a[0]` is this stage's multiplier
/// digit, `v[k]` the factor for column `k`, and `w` the 19-fold digits that
/// rotate in at column 0 as the stages advance.
///
/// Stage `s` multiplies `a_s` by `v[k] = b_{k-s}` for `k >= s` and by
/// `v[k] = 19 b_{k+15-s}` for `k < s`, which is the wrapped schoolbook
/// product folded with `2^255 = 19 (mod p)`. Each stage shifts the row by
/// one place, so no stage needs a multiplexer to pick its operands.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct MulRow {
    /// Remaining multiplier digits (this stage's digit first; consumed
    /// digits shift out and the tail fills with zeros).
    pub a: [b17; 15],
    /// Column factors `b_{k-s}` or `19 b_{k+15-s}`, 22 bits wide because
    /// `19 * (2^17 - 1) < 2^22`.
    pub v: [b22; 15],
    /// 19-fold digits still to enter, highest first: `w[0]` becomes `v[0]`
    /// at the next stage.
    pub w: [b22; 15],
}

/// Input and output of one [`MulStage`]: the previous stage's registered
/// row and partial sums.
///
/// The two halves are skewed by one clock: the `row` belonging to a request
/// arrives one cycle before its `acc`. A stage registers the row first and
/// then, on the next cycle, combines that registered row with the arriving
/// sums, so each stage's multiply operands come straight from its own
/// registers.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct MulStageIo {
    /// Operand row (one cycle ahead of `acc`).
    pub row: MulRow,
    /// Column partial sums `c_k` accumulated so far. 43 bits hold the full
    /// sum of fifteen `17 x 22`-bit products.
    pub acc: [b43; 15],
}

/// Registers of one [`MulStage`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct MulStageRegs {
    /// Shifted operand row for the request whose sums arrive next cycle.
    row: MulRow,
    /// Partial sums after this stage's products were added.
    acc: [b43; 15],
}

/// One multiply-accumulate stage of all fifteen column chains.
///
/// Every column adds `a[0] * v[k]` to the incoming partial sum: one DSP per
/// column with `PCIN` from the previous stage. The row advances by one digit.
/// Output is the registered state, so each stage is one clock of latency.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct MulStage {
    /// Row and partial-sum registers.
    regs: DFF<MulStageRegs>,
}

/// Resets every register to zero.
impl Default for MulStage {
    fn default() -> Self {
        Self {
            regs: DFF::new(MulStageRegs {
                row: MulRow {
                    a: [b17(0); 15],
                    v: [b22(0); 15],
                    w: [b22(0); 15],
                },
                acc: [b43(0); 15],
            }),
        }
    }
}

/// Port types: a stage passes a [`MulStageIo`] down the chain.
impl SynchronousIO for MulStage {
    type I = MulStageIo;
    type O = MulStageIo;
    type Kernel = mul_stage_kernel;
}

/// State transition for [`MulStage`].
///
/// `i.acc` belongs to the same request as the registered row `q.regs.row`
/// (see [`MulStageIo`]), so the product uses the registered row while the
/// incoming `i.row` is only shifted and stored for the next request.
#[kernel]
pub fn mul_stage_kernel(_cr: ClockReset, i: MulStageIo, q: MulStageQ) -> (MulStageIo, MulStageD) {
    let r = q.regs;
    // One MACC per column: P = PCIN + A * B with A = this stage's digit.
    let mut acc = [b43(0); 15];
    for k in 0..15 {
        acc[k] = i.acc[k] + r.row.a[0].resize::<43>() * r.row.v[k].resize::<43>();
    }
    // Shift the incoming row for the next stage: drop the consumed digit
    // a[0], move every column factor up one column, and feed the next
    // 19-fold digit into column 0. The vacated tail slots stay zero.
    let mut a = [b17(0); 15];
    let mut w = [b22(0); 15];
    let mut v = [b22(0); 15];
    for j in 0..14 {
        a[j] = i.row.a[j + 1];
        w[j] = i.row.w[j + 1];
        v[j + 1] = i.row.v[j];
    }
    v[0] = i.row.w[0];
    // Output the registered state (row still one cycle ahead of the sums).
    (
        MulStageIo {
            row: r.row,
            acc: r.acc,
        },
        MulStageD {
            regs: MulStageRegs {
                row: MulRow { a: a, v: v, w: w },
                acc: acc,
            },
        },
    )
}

/// Seven chained [`MulStage`]s (kept small so every kernel's port bundle
/// lowers to Verilog constants that common front ends can scan).
#[derive(Clone, Debug, Synchronous, SynchronousDQ, Default)]
pub struct MulChain7 {
    /// Stages in order; `stages[0]` takes the chain input.
    stages: [MulStage; 7],
}

/// Port types: the chain has the same interface as one stage, with seven
/// clocks of latency.
impl SynchronousIO for MulChain7 {
    type I = MulStageIo;
    type O = MulStageIo;
    type Kernel = mul_chain7_kernel;
}

/// Wiring for [`MulChain7`]: each stage feeds the next, and the last
/// stage's output is the chain output.
#[kernel]
pub fn mul_chain7_kernel(_cr: ClockReset, i: MulStageIo, q: MulChain7Q) -> (MulStageIo, MulChain7D) {
    // Outputs of the seven stages (already registered inside each stage).
    let st = q.stages;
    (
        st[6],
        MulChain7D {
            stages: [i, st[0], st[1], st[2], st[3], st[4], st[5]],
        },
    )
}

/// Pipeline registers of [`MulNorm`], one group per stage.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct MulNormRegs {
    /// Stage 1: columns after the first carry pass. Column 0 receives 19
    /// times the large carry out of column 14, hence 32 bits.
    pass1: [b32; 15],
    /// Stage 2: columns after the second carry pass; the carries are now
    /// small, so 18 bits suffice.
    pass2: [b18; 15],
    /// Stage 3: columns after the third pass, each at most one bit above 17.
    pass3: [b18; 15],
    /// Stages 4 and 5: `low + over` and `low + over + 19` (see the kernel)
    /// after limb 0 and after limb 1.
    w4: NormWave,
    w5: NormWave,
    /// Stage 6: canonical product digits.
    result: [b17; 15],
}

/// The limb-serial final add of [`MulNorm`]: operands, the two sums' low
/// limbs so far and their carries.
#[derive(Copy, Clone, Debug, PartialEq, Digital, Default)]
#[doc(hidden)]
pub struct NormWave {
    /// `low` as limbs.
    pub low: [b85; 3],
    /// `over` as limbs (`over + 19` differs only in limb 0).
    pub over: [b85; 3],
    /// `low + over`, low limbs so far.
    pub s: [b85; 3],
    /// `low + over + 19`, low limbs so far.
    pub s19: [b85; 3],
    /// Carry into the next limb of `s`.
    pub c_s: bool,
    /// Carry into the next limb of `s19`.
    pub c_s19: bool,
}

/// Carry normalization and canonical reduction of the fifteen column sums.
///
/// Six register stages: three lazy carry passes, then the carry-propagate
/// add and the final reduction together, one 85-bit limb per stage
/// (stages 4-6). Each pass is fifteen independent small adds; the final
/// add forms `V = low + over` and `V + 19` side by side, and the canonical
/// value is the low 255 bits of `V + 19` when either sum reaches `2^255`,
/// else `V`. So no stage holds more than one 85-bit carry chain. (Until
/// 2026-10-17 stages 4 and 5 were whole 255-bit chains, 33 CARRY8 levels:
/// the fixed-base machine's worst routed path once the adder was split.)
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct MulNorm {
    /// Stage registers.
    regs: DFF<MulNormRegs>,
}

/// Resets every register to zero.
impl Default for MulNorm {
    fn default() -> Self {
        Self {
            regs: DFF::new(MulNormRegs {
                pass1: [b32(0); 15],
                pass2: [b18(0); 15],
                pass3: [b18(0); 15],
                w4: NormWave::default(),
                w5: NormWave::default(),
                result: [b17(0); 15],
            }),
        }
    }
}

/// Port types: fifteen 43-bit column sums in, fifteen canonical digits out.
impl SynchronousIO for MulNorm {
    type I = [b43; 15];
    type O = [b17; 15];
    type Kernel = mul_norm_kernel;
}

/// State transition for [`MulNorm`]: three lazy carry passes (column 14
/// wraps with a factor of 19), then a limb-serial carry-propagate and
/// canonical result.
#[kernel]
pub fn mul_norm_kernel(_cr: ClockReset, c: [b43; 15], q: MulNormQ) -> ([b17; 15], MulNormD) {
    let r = q.regs;
    let mut n = r;
    // Pass 1 (from the chain output): keep each column's low 17 bits and add
    // the carry from the column below. Column 0 takes column 14's carry
    // times 19, because that carry has weight 2^255 = 19 (mod p).
    // (h << 4) + (h << 1) + h is 19 h without a multiplier.
    for k in 0..15 {
        let carry = if k == 0 {
            let h = (c[14] >> 17).resize::<32>();
            (h << 4) + (h << 1) + h
        } else {
            (c[k - 1] >> 17).resize::<32>()
        };
        n.pass1[k] = (c[k] & b43(0x1ffff)).resize::<32>() + carry;
    }
    // Pass 2 (from the registered pass 1): the same step on smaller values.
    for k in 0..15 {
        let carry = if k == 0 {
            let h = (r.pass1[14] >> 17).resize::<18>();
            (h << 4) + (h << 1) + h
        } else {
            (r.pass1[k - 1] >> 17).resize::<18>()
        };
        n.pass2[k] = (r.pass1[k] & b32(0x1ffff)).resize::<18>() + carry;
    }
    // Pass 3 (from the registered pass 2): leaves every column at most one
    // bit above 17.
    for k in 0..15 {
        let carry = if k == 0 {
            let h = (r.pass2[14] >> 17).resize::<18>();
            (h << 4) + (h << 1) + h
        } else {
            (r.pass2[k - 1] >> 17).resize::<18>()
        };
        n.pass3[k] = (r.pass2[k] & b18(0x1ffff)).resize::<18>() + carry;
    }
    // Stage 4 (from the registered pass 3): split each column into its low
    // 17 bits (`low`) and its overflow bit, moved up one column (`over`;
    // column 14's overflow folds to column 0 times 19). `V = low + over`
    // equals the value mod p, and `V < 2^255 + 2^239` (`over` is small).
    let mut low = [b17(0); 15];
    let mut over = [b17(0); 15];
    for k in 0..15 {
        low[k] = (r.pass3[k] & b18(0x1ffff)).resize::<17>();
        let h = (r.pass3[k] >> 17).resize::<17>();
        if k == 14 {
            over[0] = over[0] + (h << 4) + (h << 1) + h;
        } else {
            over[k + 1] = h;
        }
    }
    // Limb 0 of V and of V + 19 (over[0] <= 19, so + 19 stays in limb 0).
    let mut w = r.w4;
    w.low = limbs_from_digits(low);
    w.over = limbs_from_digits(over);
    let (s0, c_s) = add_limb(w.low[0], w.over[0], false);
    let (t0, c_s19) = add_limb(w.low[0], w.over[0] + b85(19), false);
    w.s[0] = s0;
    w.s19[0] = t0;
    w.c_s = c_s;
    w.c_s19 = c_s19;
    n.w4 = w;
    // Stage 5: limb 1 of both sums.
    let mut w = r.w4;
    let (s1, c_s) = add_limb(w.low[1], w.over[1], w.c_s);
    let (t1, c_s19) = add_limb(w.low[1], w.over[1], w.c_s19);
    w.s[1] = s1;
    w.s19[1] = t1;
    w.c_s = c_s;
    w.c_s19 = c_s19;
    n.w5 = w;
    // Stage 6: limb 2 and the choice. If V >= 2^255, V mod p = low255(V) +
    // 19 = low255(V + 19) (canonical: low255(V) < 2^239); if V < 2^255
    // and V + 19 >= 2^255, V >= p and V - p = low255(V + 19); else V.
    let w = r.w5;
    let (s2, top) = add_limb(w.low[2], w.over[2], w.c_s);
    let (t2, top19) = add_limb(w.low[2], w.over[2], w.c_s19);
    n.result = if top || top19 {
        digits_from_limbs([w.s19[0], w.s19[1], t2])
    } else {
        digits_from_limbs([w.s[0], w.s[1], s2])
    };
    (r.result, MulNormD { regs: n })
}

/// Registers of [`FieldMulPar`] outside the chain and normalizer.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct MulRegs {
    /// Valid shift register; `valid[s]` is the request captured `s` edges ago.
    valid: [bool; 23],
    /// Tag shift register, aligned with `valid`.
    tag: [b16; 23],
    /// Captured first factor (edge 1).
    a0: [b17; 15],
    /// Captured second factor (edge 1).
    b0: [b17; 15],
    /// Stage-0 operand row built from `a0`/`b0` (edge 2).
    row0: MulRow,
    /// Stage-0 products `a_0 * b_k` (edge 3), the start of every column chain.
    acc0: [b43; 15],
}

/// Reset value of [`MulRegs`]: everything zero and no valid requests.
fn mul_reset() -> MulRegs {
    MulRegs {
        valid: [false; 23],
        tag: [b16(0); 23],
        a0: [b17(0); 15],
        b0: [b17(0); 15],
        row0: MulRow {
            a: [b17(0); 15],
            v: [b22(0); 15],
            w: [b22(0); 15],
        },
        acc0: [b43(0); 15],
    }
}

/// Initiation-interval-one, 225-DSP canonical field multiplier.
///
/// Edge 1 captures the operands, edge 2 forms stage 0's row (with the
/// 19-fold digits), edges 3..17 run the fifteen chain stages (stage 0 here,
/// stages 1..14 in two [`MulChain7`] children), and [`MulNorm`] finishes at 23.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
#[rhdl(dq_no_prefix)]
pub struct FieldMulPar {
    /// Operand capture, stage 0, and the valid/tag delay line.
    regs: DFF<MulRegs>,
    /// Chain stages 1..7 (`chains[0]`) and 8..14 (`chains[1]`).
    chains: [MulChain7; 2],
    /// Carry normalization and final reduction (six stages).
    norm: MulNorm,
}

/// Resets every register to zero.
impl Default for FieldMulPar {
    fn default() -> Self {
        Self {
            regs: DFF::new(mul_reset()),
            chains: [MulChain7::default(), MulChain7::default()],
            norm: MulNorm::default(),
        }
    }
}

/// Port types: [`FieldMulIn`] in, [`FieldMulOut`] out.
impl SynchronousIO for FieldMulPar {
    type I = FieldMulIn;
    type O = FieldMulOut;
    type Kernel = field_mul_par_kernel;
}

/// `x * 19` for a 17-bit digit, as `16x + 2x + x` (shifts and adds, no DSP).
/// The result is below `2^22`.
#[kernel]
pub fn times19_digit(x: b17) -> b22 {
    let w = x.resize::<22>();
    (w << 4) + (w << 1) + w
}

/// Three 85-bit limbs (five digits each) of a 255-bit integer.
///
/// Pure rewiring: limb `m` is digits `5m..5m+4` concatenated. Wide adds use
/// limbs so each carry chain is three 85-bit pieces rather than 15 digits.
#[kernel]
pub fn limbs_from_digits(d: [b17; 15]) -> [b85; 3] {
    // Digit 5m + j sits at bit 17 j of limb m.
    let mut out = [b85(0); 3];
    for m in 0..3 {
        for j in 0..5 {
            out[m] = out[m] | (d[5 * m + j].resize::<85>() << ((17 * j) as u128));
        }
    }
    out
}

/// Inverse of [`limbs_from_digits`] (also pure rewiring).
#[kernel]
pub fn digits_from_limbs(l: [b85; 3]) -> [b17; 15] {
    let mut out = [b17(0); 15];
    for m in 0..3 {
        for j in 0..5 {
            out[5 * m + j] = (l[m] >> ((17 * j) as u128)).resize::<17>();
        }
    }
    out
}

/// 255-bit addition of limb vectors; returns the sum modulo `2^255` and bit 255.
///
/// Combinational. Inputs are unsigned 255-bit integers, so the sum is below
/// `2^256` and bit 255 is the only carry out.
#[kernel]
pub fn add255(a: [b85; 3], b: [b85; 3]) -> ([b85; 3], bool) {
    let mut out = [b85(0); 3];
    // Carry between limbs, 0 or 1 (86 bits only to match the sum width).
    let mut carry = b86(0);
    for m in 0..3 {
        let s = a[m].resize::<86>() + b[m].resize::<86>() + carry;
        out[m] = s.resize::<85>();
        carry = s >> 85;
    }
    (out, carry != b86(0))
}

/// Canonical value of `lo + hi * 2^255` for `lo + 19 * hi < 2p`.
///
/// `w1 = lo + 19 hi` and `w2 = w1 + 19` are formed in parallel; when `w2`
/// reaches `2^255`, `w1 >= p` and the answer is `w2 - 2^255 = w1 - p`.
///
/// Combinational. `hi` is the overflow above bit 255 (3 bits wide, callers
/// pass 0 or 1). Computing both candidates at once avoids a compare before
/// the subtraction.
#[kernel]
pub fn canonical255(lo: [b85; 3], hi: b3) -> [b17; 15] {
    // 19 * hi: the value of hi * 2^255 mod p.
    let h = hi.resize::<85>();
    let fold = (h << 4) + (h << 1) + h;
    let w1 = add255(lo, [fold, b85(0), b85(0)]);
    let w2 = add255(lo, [fold + b85(19), b85(0), b85(0)]);
    let (w1_low, w1_top) = w1;
    let (w2_low, w2_top) = w2;
    // w1_top means w1 >= 2^255 > p; w2_top alone means p <= w1 < 2^255.
    // Either way w2 mod 2^255 = w1 - p, which is canonical given the bound.
    if w1_top || w2_top {
        digits_from_limbs(w2_low)
    } else {
        digits_from_limbs(w1_low)
    }
}

/// State transition for [`FieldMulPar`].
///
/// Only stage 0 and the operand capture live here; stages 1..14 are the two
/// [`MulChain7`] children and the reduction is [`MulNorm`].
#[kernel]
pub fn field_mul_par_kernel(_cr: ClockReset, i: FieldMulIn, q: Q) -> (FieldMulOut, D) {
    let r = q.regs;
    let mut n = r;
    // Valid and tag ride a 22-entry shift register alongside the data, so
    // the output flags line up with the product without any counters.
    n.valid[0] = i.valid;
    n.tag[0] = i.tag;
    for s in 1..23 {
        n.valid[s] = r.valid[s - 1];
        n.tag[s] = r.tag[s - 1];
    }
    // Edge 1: capture the operands.
    n.a0 = i.a.d;
    n.b0 = i.b.d;
    // Edge 2: stage-0 row: v[k] = b_k, and the 19-fold digits enter highest first.
    let mut v = [b22(0); 15];
    let mut w = [b22(0); 15];
    for k in 0..15 {
        v[k] = r.b0[k].resize::<22>();
        w[k] = times19_digit(r.b0[14 - k]);
    }
    n.row0 = MulRow { a: r.a0, v: v, w: w };
    // Edge 3: stage-0 products a_0 * b_k start every column (no PCIN).
    for k in 0..15 {
        n.acc0[k] = r.row0.a[0].resize::<43>() * r.row0.v[k].resize::<43>();
    }
    // The chain receives row0 one cycle before acc0 of the same request,
    // matching the row/sum skew described in MulStageIo: r.row0 here already
    // belongs to the next request when r.acc0 belongs to this one.
    let ch = q.chains;
    let d = D {
        regs: n,
        chains: [
            MulStageIo {
                row: r.row0,
                acc: r.acc0,
            },
            ch[0],
        ],
        // Only the final sums enter the normalizer; the row is spent.
        norm: ch[1].acc,
    };
    // Edge 23: normalizer output with the delayed valid and tag.
    let out = FieldMulOut {
        valid: r.valid[22],
        r: Fe17 { d: q.norm },
        tag: r.tag[22],
    };
    (out, d)
}

/// Add/subtract request, sampled every clock (initiation interval one).
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct FieldAddIn {
    /// Request valid.
    pub valid: bool,
    /// Subtract (`a - b`) instead of add.
    pub sub: bool,
    /// First operand (canonical).
    pub a: Fe17,
    /// Second operand (canonical).
    pub b: Fe17,
    /// Opaque tag returned with the result.
    pub tag: b16,
}

/// Add/subtract result, [`ADD_LATENCY`] cycles after the request.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct FieldAddOut {
    /// Result valid (the delayed request `valid`).
    pub valid: bool,
    /// Canonical `a + b` or `a - b` mod `p`.
    pub r: Fe17,
    /// Tag captured with the request.
    pub tag: b16,
}

/// One limb step of a 255-bit addition: `x + y + c` over 85 bits, with the
/// carry out. Combinational; one 85-bit carry chain.
#[kernel]
pub fn add_limb(x: b85, y: b85, c: bool) -> (b85, bool) {
    let s = x.resize::<86>() + y.resize::<86>() + if c { b86(1) } else { b86(0) };
    (s.resize::<85>(), (s >> 85) != b86(0))
}

/// A limb (the `low` one or a higher one) of the constant added to `x`
/// (`b`, or `!b` for subtraction) to form `nb`: `!b + (2^255 - 18) = p - b` mod `2^255`, or `b + 0`.
#[kernel]
pub fn nb_const(sub: bool, low: bool) -> b85 {
    let mask = ((b86(1) << 85) - b86(1)).resize::<85>();
    if sub {
        if low { ((b86(1) << 85) - b86(18)).resize::<85>() } else { mask }
    } else {
        b85(0)
    }
}

/// A limb of the constant added to `x` to form `nb + 19`:
/// `!b + 1 = 2^255 - b = p - b + 19`, or `b + 19`.
#[kernel]
pub fn nb19_const(sub: bool, low: bool) -> b85 {
    if low {
        if sub { b85(1) } else { b85(19) }
    } else {
        b85(0)
    }
}

/// One stage of the limb-serial add/subtract wavefront. Fields fill in limb
/// by limb as the request moves down the pipeline; limbs not yet formed
/// (and the operands once spent) are don't-care.
#[derive(Copy, Clone, Debug, PartialEq, Digital, Default)]
#[doc(hidden)]
pub struct AddWave {
    /// Subtract (`a - b`) instead of add.
    pub sub: bool,
    /// First operand as limbs.
    pub a: [b85; 3],
    /// `b`, or `!b` (255 bits) for subtraction.
    pub x: [b85; 3],
    /// `nb` = `b`, or `p - b` for subtraction (mod `2^255`).
    pub nb: [b85; 3],
    /// `nb + 19` mod `2^255`: `b + 19`, or `2^255 - b`.
    pub n19: [b85; 3],
    /// Carry into the next limb of `nb`.
    pub c_nb: bool,
    /// Carry into the next limb of `n19`.
    pub c_19: bool,
    /// Bit 255 of `nb + 19` (set only when subtracting `b = 0`: `2^255`).
    pub n19_top: bool,
    /// `a + nb`, low limbs so far.
    pub s: [b85; 3],
    /// `a + nb + 19`, low limbs so far.
    pub s19: [b85; 3],
    /// Carry into the next limb of `s`.
    pub c_s: bool,
    /// Carry into the next limb of `s19`.
    pub c_s19: bool,
}

/// Pipeline registers of [`FieldAddSub`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct AddRegs {
    /// Valid shift register; `valid[s]` is the request captured `s` edges ago.
    valid: [bool; 5],
    /// Tag shift register, aligned with `valid`.
    tag: [b16; 5],
    /// Edge 1: the captured request.
    sub: bool,
    a0: [b85; 3],
    b0: [b85; 3],
    /// Edges 2-4: the wavefront after limb 0, 1 and 2 of `nb`.
    w2: AddWave,
    w3: AddWave,
    w4: AddWave,
    /// Edge 5: canonical result digits.
    result: [b17; 15],
}

/// Five-cycle canonical modular add/subtract with no carry chain longer
/// than one 85-bit limb per stage.
///
/// `a + b` and `a - b = a + (p - b)` are both `a + nb` with `nb <= p`, so
/// the sum is below `2p` and the canonical result is `a + nb` or
/// `a + nb - p`. The unit forms `nb` and `nb + 19` limb by limb (edges
/// 2-4), and from them `a + nb` and `a + nb + 19` one limb behind (edges
/// 3-5). `a + nb >= p` exactly when `a + nb + 19 >= 2^255`, and then the
/// result is the low 255 bits of `a + nb + 19`; no compare is needed.
/// (Before 2026-10-17 each of three stages held a whole 255-bit chain; that
/// chain was the worst path of DSig v8's in-chip route, -0.351 ns.)
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct FieldAddSub {
    /// Pipeline registers.
    regs: DFF<AddRegs>,
}

/// Resets every register to zero.
impl Default for FieldAddSub {
    fn default() -> Self {
        Self {
            regs: DFF::new(AddRegs {
                valid: [false; 5],
                tag: [b16(0); 5],
                sub: false,
                a0: [b85(0); 3],
                b0: [b85(0); 3],
                w2: AddWave::default(),
                w3: AddWave::default(),
                w4: AddWave::default(),
                result: [b17(0); 15],
            }),
        }
    }
}

/// Port types: [`FieldAddIn`] in, [`FieldAddOut`] out.
impl SynchronousIO for FieldAddSub {
    type I = FieldAddIn;
    type O = FieldAddOut;
    type Kernel = field_add_sub_kernel;
}

/// `p - b` for canonical `b`, computed as `!b - 18` over 255 bits.
///
/// `!b = 2^255 - 1 - b`, so `!b - 18 = 2^255 - 19 - b = p - b`. Combinational.
/// For `b = 0` the result is `p` itself, which is not canonical; callers
/// that need a canonical negation must special-case zero (see the machine's
/// `field_neg`).
#[kernel]
pub fn p_minus(b: [b85; 3]) -> [b85; 3] {
    // 85 one bits; the complement is taken at 86 bits and masked back.
    let mask = (b86(1) << 85) - b86(1);
    let nb = [
        (!b[0].resize::<86>() & mask).resize::<85>(),
        (!b[1].resize::<86>() & mask).resize::<85>(),
        (!b[2].resize::<86>() & mask).resize::<85>(),
    ];
    // Adding 2^255 - 18 modulo 2^255 subtracts 18.
    let minus18 = [
        ((b86(1) << 85) - b86(18)).resize::<85>(),
        mask.resize::<85>(),
        mask.resize::<85>(),
    ];
    let (out, _) = add255(nb, minus18);
    out
}

/// State transition for [`FieldAddSub`].
#[kernel]
pub fn field_add_sub_kernel(
    _cr: ClockReset,
    i: FieldAddIn,
    q: FieldAddSubQ,
) -> (FieldAddOut, FieldAddSubD) {
    let r = q.regs;
    let mut n = r;
    // Valid and tag delay line, aligned with the data stages.
    n.valid[0] = i.valid;
    n.tag[0] = i.tag;
    for s in 1..5 {
        n.valid[s] = r.valid[s - 1];
        n.tag[s] = r.tag[s - 1];
    }
    // Edge 1: capture (digits to limbs is only rewiring).
    n.sub = i.sub;
    n.a0 = limbs_from_digits(i.a.d);
    n.b0 = limbs_from_digits(i.b.d);
    // Edge 2: x = b or !b; limb 0 of nb and nb + 19.
    // Every field of the wave is written before it is read downstream.
    let mut w = r.w2;
    w.sub = r.sub;
    w.a = r.a0;
    for m in 0..3 {
        w.x[m] = if r.sub { !r.b0[m] } else { r.b0[m] };
    }
    let (nb0, c_nb) = add_limb(w.x[0], nb_const(r.sub, true), false);
    let (n190, c_19) = add_limb(w.x[0], nb19_const(r.sub, true), false);
    w.nb[0] = nb0;
    w.n19[0] = n190;
    w.c_nb = c_nb;
    w.c_19 = c_19;
    n.w2 = w;
    // Edge 3: limb 1 of nb and nb + 19; limb 0 of the two sums.
    let mut w = r.w2;
    let (nb1, c_nb) = add_limb(w.x[1], nb_const(w.sub, false), w.c_nb);
    let (n191, c_19) = add_limb(w.x[1], nb19_const(w.sub, false), w.c_19);
    let (s0, c_s) = add_limb(w.a[0], w.nb[0], false);
    let (t0, c_s19) = add_limb(w.a[0], w.n19[0], false);
    w.nb[1] = nb1;
    w.n19[1] = n191;
    w.c_nb = c_nb;
    w.c_19 = c_19;
    w.s[0] = s0;
    w.s19[0] = t0;
    w.c_s = c_s;
    w.c_s19 = c_s19;
    n.w3 = w;
    // Edge 4: limb 2 of nb (its carry out is dropped: mod 2^255) and of
    // nb + 19 (carry out = bit 255, set only for b = 0 in a subtraction);
    // limb 1 of the sums.
    let mut w = r.w3;
    let (nb2, _) = add_limb(w.x[2], nb_const(w.sub, false), w.c_nb);
    let (n192, top) = add_limb(w.x[2], nb19_const(w.sub, false), w.c_19);
    let (s1, c_s) = add_limb(w.a[1], w.nb[1], w.c_s);
    let (t1, c_s19) = add_limb(w.a[1], w.n19[1], w.c_s19);
    w.nb[2] = nb2;
    w.n19[2] = n192;
    w.n19_top = top;
    w.s[1] = s1;
    w.s19[1] = t1;
    w.c_s = c_s;
    w.c_s19 = c_s19;
    n.w4 = w;
    // Edge 5: limb 2 of the sums and the choice. a + nb + 19 < 2^256, so
    // its bit 255 is the limb-2 carry or nb + 19's own bit 255 (never
    // both); when set, a + nb >= p and the low 255 bits are a + nb - p.
    let w = r.w4;
    let (s2, _) = add_limb(w.a[2], w.nb[2], w.c_s);
    let (t2, c_top) = add_limb(w.a[2], w.n19[2], w.c_s19);
    n.result = if c_top || w.n19_top {
        digits_from_limbs([w.s19[0], w.s19[1], t2])
    } else {
        digits_from_limbs([w.s[0], w.s[1], s2])
    };
    let out = FieldAddOut {
        valid: r.valid[4],
        r: Fe17 { d: r.result },
        tag: r.tag[4],
    };
    (out, FieldAddSubD { regs: n })
}

/// Cycle-level tests of both units against the host model.
#[cfg(test)]
mod tests {
    use super::*;
    use crate::simulation::CycleSim;

    /// `n` test elements: edge cases (0, 1, -1, -19, and the raw-limb
    /// constant `2^255 - 20 = p - 1`) followed by xorshift-generated values.
    fn sample(n: usize) -> Vec<Fp> {
        // xorshift64 state; fixed seed so failures reproduce.
        let mut s = 0x9e37_79b9_7f4a_7c15u64;
        let mut next = || {
            s ^= s << 13;
            s ^= s >> 7;
            s ^= s << 17;
            s
        };
        let mut v = vec![
            Fp::ZERO,
            Fp::ONE,
            Fp::ZERO.sub(Fp::ONE),
            Fp::ZERO.sub(Fp([19, 0, 0, 0])),
            Fp([u64::MAX, u64::MAX, u64::MAX, 0x7fff_ffff_ffff_ffec]),
        ];
        while v.len() < n {
            let bytes: [u8; 32] = std::array::from_fn(|_| next() as u8);
            v.push(Fp::from_bytes(&bytes));
        }
        v
    }

    /// Feeds one request per clock to both units (subtracting on odd
    /// cycles) and checks every result, matched by tag, against [`Fp`].
    /// Back-to-back issue checks that the pipelines keep requests separate.
    #[test]
    fn mul_and_addsub_match_host_back_to_back() {
        let xs = sample(40);
        let pairs: Vec<(Fp, Fp)> = xs
            .iter()
            .flat_map(|a| xs.iter().take(8).map(move |b| (*a, *b)))
            .collect();
        // 40 extra idle cycles drain both pipelines.
        let mut mul = CycleSim::new(FieldMulPar::default());
        let mut add = CycleSim::new(FieldAddSub::default());
        let mut got_m = Vec::new();
        let mut got_a = Vec::new();
        for cycle in 0..pairs.len() + 40 {
            let (valid, a, b) = match pairs.get(cycle) {
                Some((a, b)) => (true, Fe17::from_fp(*a), Fe17::from_fp(*b)),
                None => (false, Fe17::zero(), Fe17::zero()),
            };
            let tag = b16((cycle & 0xffff) as u128);
            let o = mul.tick(FieldMulIn { valid, a, b, tag });
            if o.valid {
                got_m.push((o.tag.raw() as usize, o.r.to_fp()));
            }
            let o = add.tick(FieldAddIn {
                valid,
                sub: cycle % 2 == 1,
                a,
                b,
                tag,
            });
            if o.valid {
                got_a.push((o.tag.raw() as usize, o.r.to_fp()));
            }
        }
        assert_eq!(got_m.len(), pairs.len());
        assert_eq!(got_a.len(), pairs.len());
        for (idx, r) in got_m {
            let (a, b) = pairs[idx];
            assert_eq!(r, a.mul(b), "mul {idx}");
        }
        for (idx, r) in got_a {
            let (a, b) = pairs[idx];
            let want = if idx % 2 == 1 { a.sub(b) } else { a.add(b) };
            assert_eq!(r, want, "addsub {idx}");
        }
    }

    /// Both operations on every pair of edge values and a few random ones
    /// (so `a - 0`, `0 - 0`, `(p-1) + (p-1)` and sums landing on `p`), and
    /// the result exactly [`ADD_LATENCY`] cycles after the request.
    #[test]
    fn addsub_edges_and_latency() {
        let mut xs = sample(12);
        // a + b = p and a - b = 0 cases: p - 19 + 19, p - 1 + 1.
        xs.push(Fp([19, 0, 0, 0]));
        let mut reqs = Vec::new();
        for a in &xs {
            for b in &xs {
                reqs.push((*a, *b, false));
                reqs.push((*a, *b, true));
            }
        }
        let mut add = CycleSim::new(FieldAddSub::default());
        let mut got = Vec::new();
        for cycle in 0..reqs.len() + 10 {
            let (valid, sub, a, b) = match reqs.get(cycle) {
                Some((a, b, sub)) => (true, *sub, Fe17::from_fp(*a), Fe17::from_fp(*b)),
                None => (false, false, Fe17::zero(), Fe17::zero()),
            };
            let o = add.tick(FieldAddIn { valid, sub, a, b, tag: b16((cycle & 0xffff) as u128) });
            if o.valid {
                let idx = o.tag.raw() as usize;
                // CycleSim reports the output after each edge; the request edge is idx.
                assert_eq!(cycle - idx, ADD_LATENCY - 1, "latency of {idx}");
                got.push((idx, o.r));
            }
        }
        assert_eq!(got.len(), reqs.len());
        for (idx, r) in got {
            let (a, b, sub) = reqs[idx];
            let want = if sub { a.sub(b) } else { a.add(b) };
            assert_eq!(r, Fe17::from_fp(want), "{} {idx}: digits must be canonical", if sub { "sub" } else { "add" });
        }
    }

    /// The adder lowers to Verilog (kernel restrictions bite only here).
    #[test]
    fn addsub_lowers_to_verilog() -> Result<(), RHDLError> {
        let text = FieldAddSub::default().descriptor("field_add_sub".into())?.hdl_unchecked()?.modules.pretty();
        assert!(text.contains("module field_add_sub"));
        Ok(())
    }

    /// The normalizer's final add and reduction on column sums placed at the
    /// edges: values just below, at and above `p`, just below `2^255`, and
    /// with a carry out of column 14 (worth 19) or every column overflowing.
    #[test]
    fn normalizer_edges() {
        use num_bigint::BigUint;
        let p = (BigUint::from(1u8) << 255u32) - BigUint::from(19u8);
        let digits = |v: &BigUint| -> [b43; 15] {
            std::array::from_fn(|k| b43(((v >> (17 * k as u32)) & BigUint::from(0x1ffffu32)).iter_u64_digits().next().unwrap_or(0) as u128))
        };
        let top = BigUint::from(1u8) << 255u32;
        let mut cases: Vec<([b43; 15], BigUint)> = Vec::new();
        for v in [
            BigUint::from(0u8),
            p.clone() - 1u8,
            p.clone(),
            p.clone() + 1u8,
            p.clone() + 18u8,
            top.clone() - 1u8,
        ] {
            cases.push((digits(&v), v % &p));
        }
        // Column 14 carries 3 (3 * 2^255 = 57 mod p) on top of p - 1.
        let mut c = digits(&(p.clone() - 1u8));
        c[14] = c[14] + (b43(3) << 17);
        cases.push((c, (p.clone() - 1u8 + 57u8) % &p));
        // Every column at its largest 43-bit value.
        let max = [b43((1u128 << 43) - 1); 15];
        let mut v = BigUint::from(0u8);
        for k in 0..15u32 {
            v += BigUint::from((1u64 << 43) - 1) << (17 * k);
        }
        cases.push((max, v % &p));
        let mut norm = CycleSim::new(MulNorm::default());
        let lat = 6;
        let mut outs = Vec::new();
        for cycle in 0..cases.len() + lat + 2 {
            let input = cases.get(cycle).map_or([b43(0); 15], |c| c.0);
            outs.push(norm.tick(input));
        }
        for (k, (_, want)) in cases.iter().enumerate() {
            let got = outs[k + lat - 1];
            let mut v = BigUint::from(0u8);
            for (j, d) in got.iter().enumerate() {
                v += BigUint::from(d.raw() as u64) << (17 * j as u32);
            }
            assert_eq!(&v, want, "case {k}");
        }
    }

    /// Checks that a single multiply comes out exactly [`MUL_LATENCY`] cycles
    /// after it is presented, which the field machine depends on.
    #[test]
    fn mul_latency_is_fixed() {
        let mut mul = CycleSim::new(FieldMulPar::default());
        let one = Fe17::from_fp(Fp::ONE);
        let mut seen = None;
        for cycle in 0..40 {
            let o = mul.tick(FieldMulIn {
                valid: cycle == 0,
                a: one,
                b: one,
                tag: b16(7),
            });
            if o.valid {
                seen = Some(cycle);
            }
        }
        // CycleSim reports the output after each edge; the request edge is 0.
        assert_eq!(seen, Some(MUL_LATENCY - 1));
    }
}