rhdl_ed25519_scalable_core/

scalar_ring.rs

//! Eight-context digit-serial scalar multiply-add modulo the group order `l`.
//!
//! A job computes `(X * Y + Z) mod l` for a 527-bit `X` (31 digits of 17
//! bits, stored least significant first and consumed most significant
//! first), a multiplier `Y < l`, and an addend `Z < l`. Signing uses two
//! jobs per signature:
//!
//! - `r = H(prefix || M) mod l` with `Y = 1`, `Z = 0`;
//! - `S = H(R || A || M) * a + r mod l`, which equals `k * a + r` for
//!   `k = H(R || A || M) mod l` without a separate reduction.
//!
//! Each Horner step is `u = acc * 2^17 + x_d * Y`, then, with
//! `l = 2^252 + c`, `acc' = (u mod 2^252) + l - (u >> 252) * c`. Because
//! `2^252 = -c (mod l)`, `acc'` is congruent to `u`. The invariant
//! `acc < 2^254` keeps every quantity bounded: `u < 2^271 + 2^17 * l < 2^272`
//! (sixteen digits), so `t = u >> 252 < 2^20` and `t * c < 2^145 < l`, which
//! makes `l - t * c` positive and `acc' < 2^252 + l < 2^254`. A step is an
//! eight-stage pipeline, and eight independent contexts circulate through
//! it, so the datapath retires one step per cycle: 15 + 8 DSP-sized products
//! and no wide fabric multiply.
//!
//! # Final reduction
//!
//! After 31 steps the finisher forms `S = acc + Z` (below `2^254 + l`) in
//! one clock and reduces it modulo `l` in two more. Because `l = 2^252 + c` with `c < 2^125`, the
//! estimate `k0 = S >> 252` is the true quotient or one more, so the first
//! clock computes `S - k0·l` (one 256-bit subtraction; `k0·l` is a small
//! constant table, see [`k_times_l_low`]) and the second adds `l` back if
//! that went negative. The earlier single-clock version subtracted four
//! multiples of `l` at 340 bits and picked one, which Vivado routed at
//! 5.13 ns, 0.27 ns over the 205 MHz period; it was the only failing path in
//! the small core.
//!
//! The finisher holds one job at a time. A context that completes its last
//! step while the finisher is busy *parks*: it keeps its slot and its final
//! accumulator, and retries each time it comes around to stage 8.

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

/// One multiply-add job `(X * Y + Z) mod l`, presented on [`ScalarRingIn::job`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ScalarJob {
    /// A job is being presented this cycle.
    pub valid: bool,
    /// Opaque tag, returned unchanged with the result so the caller can match
    /// results to jobs (results can leave in a different order than jobs
    /// entered, because contexts park while the finisher is busy).
    pub tag: b16,
    /// Multiplicand digits, least significant first (31 x 17 = 527 bits,
    /// enough for a 512-bit hash). The ring consumes `x[30]` first.
    pub x: [b17; 31],
    /// Multiplier `Y < l`, least significant digit first.
    pub y: [b17; 15],
    /// Addend `Z < l`, least significant digit first.
    pub z: [b17; 15],
}

/// Completed result, held until `out_ready`.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ScalarDone {
    /// A result is present and has not been accepted yet.
    pub valid: bool,
    /// Tag of the job this result belongs to.
    pub tag: b16,
    /// Canonical result `< l`, least significant digit first.
    pub s: [b17; 15],
}

/// Ring inputs.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ScalarRingIn {
    /// New job; accepted when [`ScalarRingOut::ready`].
    pub job: ScalarJob,
    /// Consumer accepts the result presented on [`ScalarRingOut::done`].
    pub out_ready: bool,
}

/// Ring outputs.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ScalarRingOut {
    /// A job may be presented: the pipeline slot entering stage 1 this cycle
    /// is free. Derived from registered state only, so it does not depend on
    /// this cycle's inputs.
    pub ready: bool,
    /// Result, valid until the cycle `out_ready` is high.
    pub done: ScalarDone,
}

/// One context: the state of a job as it circulates through the eight
/// pipeline stages.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct ScalarCtx {
    /// The slot holds a job.
    valid: bool,
    /// All 31 steps are done but the finisher was busy; the context keeps
    /// its slot and final `acc` until the finisher frees up.
    parked: bool,
    /// Horner steps still to run (31 at admission).
    remaining: b5,
    /// The job's tag.
    tag: b16,
    /// Running accumulator, `< 2^254`, least significant digit first.
    acc: [b17; 15],
    /// Remaining multiplicand digits; `x[30]` is the next digit, and the
    /// array shifts up by one digit each step.
    x: [b17; 31],
    /// Multiplier `Y`.
    y: [b17; 15],
    /// Addend `Z`, used only by the finisher.
    z: [b17; 15],
}

/// All pipeline registers. `sK` is the context entering stage `K`, and the
/// `sK_*` fields are the intermediate values stage `K` consumes.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct ScalarRegs {
    /// Context entering stage 1.
    s1: ScalarCtx,
    /// Context entering stage 2.
    s2: ScalarCtx,
    /// The fifteen 34-bit products `x_d * y_j` from stage 1.
    s2_p: [b34; 15],
    /// Context entering stage 3.
    s3: ScalarCtx,
    /// Limbs 0 and 1 of `u` (bits 0..170), complete.
    s3_lo: [b85; 2],
    /// Carry from limb 1 into limb 2 (0..=2).
    s3_cin: b2,
    /// Limbs 2 and 3 of the three digit vectors, each summed on its own
    /// (no carry between them yet).
    s3_hi: [b87; 2],
    /// Context entering stage 4.
    s4: ScalarCtx,
    /// `t = u >> 252` (below `2^20`).
    s4_t: b20,
    /// `u mod 2^252`.
    s4_low: [b85; 4],
    /// Context entering stage 5.
    s5: ScalarCtx,
    /// The eight 37-bit products `t * c_j`.
    s5_q: [b37; 8],
    /// `u mod 2^252`, carried along.
    s5_low: [b85; 4],
    /// Context entering stage 6.
    s6: ScalarCtx,
    /// Sum of product rows 0 and 1 (170 bits).
    s6_s: [b85; 2],
    /// Product row 2, added in stage 6.
    s6_row2: [b85; 2],
    /// `u mod 2^252`, carried along.
    s6_low: [b85; 4],
    /// Context entering stage 7.
    s7: ScalarCtx,
    /// `t * c` (below `2^145`).
    s7_tc: [b85; 2],
    /// `u mod 2^252`, carried along.
    s7_low: [b85; 4],
    /// Context entering stage 8.
    s8: ScalarCtx,
    /// Stage 8 inputs. `acc' = low + l - tc`, with `low + l` precomputed in
    /// stage 7: its low two limbs, and its high two limbs for a borrow of 0
    /// (`s8_hp`) or 1 (`s8_hm`) out of `low - tc`'s low limbs.
    s8_lo: [b85; 2],
    s8_tc: [b85; 2],
    s8_hp: [b85; 2],
    s8_hm: [b85; 2],
    /// Finisher entry holds a job (its final `acc` and its `Z`).
    f0_valid: bool,
    /// Tag of the job at the finisher entry.
    f0_tag: b16,
    /// The job's final accumulator.
    f0_acc: [b85; 4],
    /// The job's addend `Z`.
    f0_z: [b85; 4],
    /// Finisher stage 1 holds a job.
    f1_valid: bool,
    /// Tag of the job in finisher stage 1.
    f1_tag: b16,
    /// `S = acc + Z` (below `2^254 + l`).
    f1_sum: [b85; 4],
    /// Finisher stage 2 holds a job.
    f2_valid: bool,
    /// Tag of the job in finisher stage 2.
    f2_tag: b16,
    /// `S - k0 * l mod 2^256` as two 128-bit words (low, high).
    f2_d: [b128; 2],
    /// `S - k0 * l` was negative, so stage 2 must add `l` back.
    f2_negative: bool,
    /// Output register, held until `out_ready`.
    done: ScalarDone,
}

/// An empty (invalid) context, used for reset and to fill free slots.
fn empty_ctx() -> ScalarCtx {
    ScalarCtx {
        valid: false,
        parked: false,
        remaining: b5(0),
        tag: b16(0),
        acc: [b17(0); 15],
        x: [b17(0); 31],
        y: [b17(0); 15],
        z: [b17(0); 15],
    }
}

/// Digit-serial scalar ring: eight contexts, one Horner step per cycle, and
/// a two-clock finisher.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
#[rhdl(dq_no_prefix)]
pub struct ScalarRing {
    /// Every pipeline and finisher register, in one flip-flop bundle.
    regs: DFF<ScalarRegs>,
}

/// Reset state: every slot empty, every intermediate zero.
impl Default for ScalarRing {
    fn default() -> Self {
        let e = empty_ctx();
        Self {
            regs: DFF::new(ScalarRegs {
                s1: e,
                s2: e,
                s2_p: [b34(0); 15],
                s3: e,
                s3_lo: [b85(0); 2],
                s3_cin: b2(0),
                s3_hi: [b87(0); 2],
                s4: e,
                s4_t: b20(0),
                s4_low: [b85(0); 4],
                s5: e,
                s5_q: [b37(0); 8],
                s5_low: [b85(0); 4],
                s6: e,
                s6_s: [b85(0); 2],
                s6_row2: [b85(0); 2],
                s6_low: [b85(0); 4],
                s7: e,
                s7_tc: [b85(0); 2],
                s7_low: [b85(0); 4],
                s8: e,
                s8_lo: [b85(0); 2],
                s8_tc: [b85(0); 2],
                s8_hp: [b85(0); 2],
                s8_hm: [b85(0); 2],
                f0_valid: false,
                f0_tag: b16(0),
                f0_acc: [b85(0); 4],
                f0_z: [b85(0); 4],
                f1_valid: false,
                f1_tag: b16(0),
                f1_sum: [b85(0); 4],
                f2_valid: false,
                f2_tag: b16(0),
                f2_d: [b128(0); 2],
                f2_negative: false,
                done: ScalarDone {
                    valid: false,
                    tag: b16(0),
                    s: [b17(0); 15],
                },
            }),
        }
    }
}

/// Binds the ring's input, output and kernel types.
impl SynchronousIO for ScalarRing {
    type I = ScalarRingIn;
    type O = ScalarRingOut;
    type Kernel = scalar_ring_kernel;
}

/// `c = l - 2^252` in eight 17-bit digits, least significant first.
/// The top digit is 41, so `c < 2^(7 * 17 + 6) = 2^125`.
#[kernel]
pub fn order_c_digits() -> [b17; 8] {
    [
        b17(119789),
        b17(77434),
        b17(39110),
        b17(51970),
        b17(96717),
        b17(62743),
        b17(97255),
        b17(41),
    ]
}

/// `l` in fifteen 17-bit digits: the digits of `c` plus `2^252`, which is
/// bit 14 of digit 14 (`252 = 14 * 17 + 14`).
#[kernel]
pub fn order_l_digits() -> [b17; 15] {
    let c = order_c_digits();
    let mut l = [b17(0); 15];
    for j in 0..8 {
        l[j] = c[j];
    }
    l[14] = b17(16384);
    l
}

/// Sixteen digits into four 85-bit limbs (the last limb holds one digit).
///
/// Five digits fill a limb exactly, so the limbs are the same binary number
/// in a wider radix. Wide additions run on limbs, which needs one carry per
/// 85 bits instead of one per digit.
#[kernel]
pub fn pack16(d: [b17; 16]) -> [b85; 4] {
    let mut out = [b85(0); 4];
    for m in 0..4 {
        for j in 0..5 {
            if 5 * m + j < 16 {
                out[m] = out[m] | (d[5 * m + j].resize::<85>() << ((17 * j) as u128));
            }
        }
    }
    out
}

/// Inverse of [`pack16`]: bits above 272 are dropped.
#[kernel]
pub fn unpack16(l: [b85; 4]) -> [b17; 16] {
    let mut out = [b17(0); 16];
    for m in 0..4 {
        for j in 0..5 {
            if 5 * m + j < 16 {
                out[5 * m + j] = (l[m] >> ((17 * j) as u128)).resize::<17>();
            }
        }
    }
    out
}

/// Fifteen digits widened to sixteen (top digit zero), so a 255-bit value
/// can go through [`pack16`].
#[kernel]
pub fn widen15(d: [b17; 15]) -> [b17; 16] {
    let mut out = [b17(0); 16];
    for k in 0..15 {
        out[k] = d[k];
    }
    out
}

/// Four-limb addition modulo `2^340`.
#[kernel]
pub fn add_l4(a: [b85; 4], b: [b85; 4]) -> [b85; 4] {
    let mut out = [b85(0); 4];
    // Carry out of the previous limb (0 or 1), in a width that matches `s`.
    let mut carry = b86(0);
    for m in 0..4 {
        // 86 bits: one limb sum plus its carry-out in bit 85.
        let s = a[m].resize::<86>() + b[m].resize::<86>() + carry;
        out[m] = s.resize::<85>();
        carry = s >> 85;
    }
    out
}

/// Four-limb subtraction; returns `a - b mod 2^340` and whether it borrowed.
#[kernel]
pub fn sub_l4(a: [b85; 4], b: [b85; 4]) -> ([b85; 4], bool) {
    let mut out = [b85(0); 4];
    // Borrow into the current limb (0 or 1).
    let mut borrow = b86(0);
    for m in 0..4 {
        // The 86-bit difference wraps when it goes negative, which sets
        // bit 85: that bit is the borrow into the next limb.
        let s = a[m].resize::<86>() - b[m].resize::<86>() - borrow;
        out[m] = s.resize::<85>();
        borrow = (s >> 85) & b86(1);
    }
    (out, borrow != b86(0))
}

/// Two-limb addition modulo `2^170`.
#[kernel]
pub fn add_l2(a: [b85; 2], b: [b85; 2]) -> [b85; 2] {
    // Low limb with its carry in bit 85, which feeds the high limb.
    let s0 = a[0].resize::<86>() + b[0].resize::<86>();
    let s1 = a[1].resize::<86>() + b[1].resize::<86>() + (s0 >> 85);
    [s0.resize::<85>(), s1.resize::<85>()]
}

/// Bits 0..256 of four 85-bit limbs as two 128-bit words.
#[kernel]
pub fn limbs_to_w256(l: [b85; 4]) -> [b128; 2] {
    // Bits 0..128: all of limb 0 and the low 43 bits of limb 1.
    let lo = l[0].resize::<128>() | (l[1].resize::<128>() << 85);
    // Bits 128..256: the top 42 bits of limb 1, all of limb 2 (bits
    // 170..254) and bit 0 of limb 3 (bit 255).
    let hi = (l[1] >> 43).resize::<128>() | (l[2].resize::<128>() << 42) | (l[3].resize::<128>() << 127);
    [lo, hi]
}

/// Low 128 bits of `k * l` for `k = 0..8` (the high 128 bits are `k << 124`).
///
/// `k * l = k * 2^252 + k * c`, and `k * c < 8 * 2^125 = 2^128`, so the low
/// word is exactly `k * c` and the high word is `k * 2^252 / 2^128`. Entry 1
/// is `c` itself, which the finisher's add-back step reuses.
#[kernel]
pub fn k_times_l_low(k: b3) -> b128 {
    match k {
        Bits::<3>(0) => b128(0),
        Bits::<3>(1) => b128(0x14def9dea2f79cd65812631a5cf5d3ed),
        Bits::<3>(2) => b128(0x29bdf3bd45ef39acb024c634b9eba7da),
        Bits::<3>(3) => b128(0x3e9ced9be8e6d6830837294f16e17bc7),
        Bits::<3>(4) => b128(0x537be77a8bde735960498c6973d74fb4),
        Bits::<3>(5) => b128(0x685ae1592ed6102fb85bef83d0cd23a1),
        Bits::<3>(6) => b128(0x7d39db37d1cdad06106e529e2dc2f78e),
        _ => b128(0x9218d51674c549dc6880b5b88ab8cb7b),
    }
}

/// Fifteen 17-bit digits of a value below `2^255` held in two 128-bit words.
#[kernel]
pub fn w256_to_digits15(w: [b128; 2]) -> [b17; 15] {
    let mut out = [b17(0); 15];
    for k in 0..15 {
        if 17 * k + 17 <= 128 {
            // Digit entirely inside the low word.
            out[k] = (w[0] >> ((17 * k) as u128)).resize::<17>();
        } else if 17 * k >= 128 {
            // Digit entirely inside the high word.
            out[k] = (w[1] >> ((17 * k - 128) as u128)).resize::<17>();
        } else {
            // Digit 7 (bits 119..136) straddles the two words: its low bits
            // come from the top of `w[0]` and its high bits from the bottom
            // of `w[1]`.
            let low = (w[0] >> ((17 * k) as u128)).resize::<17>();
            let high = (w[1] << ((128 - 17 * k) as u128)).resize::<17>();
            out[k] = low | high;
        }
    }
    out
}

/// State transition for [`ScalarRing`].
///
/// Each cycle every stage advances its context by one register: stage `K`
/// reads `sK` and its intermediates and writes `s(K+1)`, and stage 8 writes
/// back to `s1`. The finisher runs alongside on its own registers.
#[kernel]
pub fn scalar_ring_kernel(_cr: ClockReset, i: ScalarRingIn, q: Q) -> (ScalarRingOut, D) {
    let r = q.regs;
    // Next state starts as a copy of the current one; each stage overwrites
    // the registers it owns.
    let mut n = r;

    // ---- Result handshake and finishing pipeline.
    // The consumer took the result presented this cycle (`r.done`).
    if i.out_ready {
        n.done.valid = false;
    }
    // Reduction of S = acc + Z (< 2^254 + l < 2^255) modulo l in two
    // clocks. With l = 2^252 + c (c < 2^125), k0 = S >> 252 is at least the
    // true quotient and at most one above it, so S - k0*l lies in (-l, l):
    // f1 subtracts k0*l, f2 adds l back if that went negative. Each clock
    // has one 256-bit carry chain.
    //
    // Finisher stage 2: moves into `done` only when the output register is
    // empty (checked on the registered value, so a result accepted this
    // cycle frees the output register next cycle).
    if r.f2_valid && !r.done.valid {
        // Low word plus c (the low word of 1 * l) when the difference was
        // negative; the result is reduced mod 2^256 either way.
        let lo = r.f2_d[0] + if r.f2_negative { k_times_l_low(b3(1)) } else { b128(0) };
        // The low-word addition overflowed exactly when the sum wrapped
        // below its input.
        let carry = if r.f2_negative && lo < r.f2_d[0] { b128(1) } else { b128(0) };
        // High word plus 2^252 / 2^128 = 2^124, plus the carry. Wrapping
        // mod 2^128 cancels the two's-complement negative value.
        let hi = r.f2_d[1] + if r.f2_negative { b128(1) << 124 } else { b128(0) } + carry;
        n.done = ScalarDone {
            valid: true,
            tag: r.f2_tag,
            s: w256_to_digits15([lo, hi]),
        };
        n.f2_valid = false;
    }
    // Finisher entry: S = acc + Z. The finisher holds one job, so stage 1
    // is empty whenever the entry is full. (Until 2026-10-17 stage 8 formed
    // S itself, right after acc' = low + m: two 254-bit adds in series, the
    // small signer's worst routed path once the field adder was split.)
    if r.f0_valid {
        n.f1_valid = true;
        n.f1_tag = r.f0_tag;
        n.f1_sum = add_l4(r.f0_acc, r.f0_z);
        n.f0_valid = false;
    }
    // Finisher stage 1: advances when stage 2 is empty or is moving out this
    // cycle.
    if r.f1_valid && (!r.f2_valid || !r.done.valid) {
        // S as two 128-bit words.
        let a = limbs_to_w256(r.f1_sum);
        // k0 = S >> 252: bits 124..127 of the high word, at most 3 bits
        // because S < 2^255.
        let k0 = (a[1] >> 124).resize::<3>();
        // k0 * l split into low and high words.
        let b_lo = k_times_l_low(k0);
        let b_hi = k0.resize::<128>() << 124;
        // 256-bit subtraction S - k0 * l as two 128-bit word subtractions
        // with an explicit borrow.
        let borrow = a[0] < b_lo;
        let lo = a[0] - b_lo;
        let hi = a[1] - b_hi - if borrow { b128(1) } else { b128(0) };
        // The full 256-bit difference is negative (S < k0 * l).
        let negative = a[1] < b_hi || (a[1] == b_hi && borrow);
        n.f2_valid = true;
        n.f2_tag = r.f1_tag;
        n.f2_d = [lo, hi];
        n.f2_negative = negative;
        n.f1_valid = false;
    }
    // A context may enter the finisher only when the whole finisher,
    // including the output register, is empty, so it holds one job at a
    // time and a new S is never stalled inside it.
    let finish_free = !r.f0_valid && !r.f1_valid && !r.f2_valid && !r.done.valid;

    // ---- Stage 1: x_d * Y (fifteen 17 x 17 products).
    let c1 = r.s1;
    // The current (most significant remaining) multiplicand digit.
    let xd = c1.x[30];
    for j in 0..15 {
        n.s2_p[j] = xd.resize::<34>() * c1.y[j].resize::<34>();
    }
    n.s2 = c1;

    // ---- Stage 2: acc * 2^17 + low halves.
    let c2 = r.s2;
    // acc * 2^17: acc moved up one digit.
    let mut shifted = [b17(0); 16];
    // Low 17 bits of product j, at digit j.
    let mut lo = [b17(0); 16];
    // High 17 bits of product j, at digit j + 1.
    let mut hi = [b17(0); 16];
    for j in 0..15 {
        shifted[j + 1] = c2.acc[j];
        lo[j] = r.s2_p[j].resize::<17>();
        hi[j + 1] = (r.s2_p[j] >> 17).resize::<17>();
    }
    // Splitting each product into halves turns the sum of fifteen
    // overlapping products into three non-overlapping digit vectors. All
    // three are added here for limbs 0 and 1 with the carry between them;
    // limbs 2 and 3 are summed on their own, and stage 3 carries into them.
    // (Until 2026-10-17 this stage added two vectors over all 340 bits and
    // stage 3 the third: a 272-bit carry chain into the t * c DSPs, the
    // 8,0,2,1 signer's worst routed path, -0.373 ns.)
    let a = pack16(shifted);
    let b = pack16(lo);
    let h = pack16(hi);
    let s0 = a[0].resize::<87>() + b[0].resize::<87>() + h[0].resize::<87>();
    let s1 = a[1].resize::<87>() + b[1].resize::<87>() + h[1].resize::<87>() + (s0 >> 85);
    n.s3_lo = [s0.resize::<85>(), s1.resize::<85>()];
    n.s3_cin = (s1 >> 85).resize::<2>();
    n.s3_hi = [
        a[2].resize::<87>() + b[2].resize::<87>() + h[2].resize::<87>(),
        a[3].resize::<87>() + b[3].resize::<87>() + h[3].resize::<87>(),
    ];
    n.s3 = c2;

    // ---- Stage 3: u, then t = u >> 252 and u mod 2^252.
    // u = acc * 2^17 + x_d * Y, below 2^272 (sixteen digits).
    // Only bits 170..272 are left to carry (u < 2^272).
    let v2 = r.s3_hi[0] + r.s3_cin.resize::<87>();
    let v3 = r.s3_hi[1] + (v2 >> 85);
    let u = unpack16([r.s3_lo[0], r.s3_lo[1], v2.resize::<85>(), v3.resize::<85>()]);
    // Bit 252 is bit 14 of digit 14: t takes the top 3 bits of digit 14 and
    // all 17 bits of digit 15 (20 bits).
    n.s4_t = (u[14] >> 14).resize::<20>() | (u[15].resize::<20>() << 3);
    // u mod 2^252: clear bits 252 and up.
    let mut low = u;
    low[14] = u[14] & b17(0x3fff);
    low[15] = b17(0);
    n.s4_low = pack16(low);
    n.s4 = r.s3;

    // ---- Stage 4: t * c (eight 20 x 17 products).
    let c = order_c_digits();
    for j in 0..8 {
        n.s5_q[j] = r.s4_t.resize::<37>() * c[j].resize::<37>();
    }
    n.s5_low = r.s4_low;
    n.s5 = r.s4;

    // ---- Stage 5: three non-overlapping product rows (offsets 0, 17, 34).
    // t * c = sum_j q_j * 2^(17 j). Row `row` collects products
    // j = row, row + 3, row + 6. Within a row the offsets are 51 bits apart
    // and each product is 37 bits wide, so the products do not overlap and
    // can be OR-ed into place; only the three rows need real additions.
    let qv = r.s5_q;
    // Each row as a 170-bit two-limb value.
    let mut rows = [[b85(0); 2]; 3];
    for row in 0..3 {
        for step in 0..3 {
            let j = 3 * step + row;
            if j < 8 {
                let q85 = qv[j].resize::<85>();
                // Bit position of product j in t * c.
                let offset = 17 * j;
                if offset < 85 {
                    // Starts in limb 0; the bits above bit 85 spill into
                    // limb 1.
                    rows[row][0] = rows[row][0] | (q85 << (offset as u128));
                    if offset + 37 > 85 {
                        rows[row][1] = rows[row][1] | (q85 >> ((85 - offset) as u128));
                    }
                } else {
                    // Entirely in limb 1.
                    rows[row][1] = rows[row][1] | (q85 << ((offset - 85) as u128));
                }
            }
        }
    }
    n.s6_s = add_l2(rows[0], rows[1]);
    n.s6_row2 = rows[2];
    n.s6_low = r.s5_low;
    n.s6 = r.s5;

    // ---- Stage 6: tc.
    // The third row completes t * c.
    n.s7_tc = add_l2(r.s6_s, r.s6_row2);
    n.s7_low = r.s6_low;
    n.s7 = r.s6;

    // ---- Stage 7: low + l, split for stage 8 (tc < 2^145 < l).
    // Adding l before subtracting t * c keeps acc' positive, so the ring
    // never needs a sign or a conditional correction per step. tc spans two
    // limbs, so stage 8 subtracts it from the low half only and picks the
    // high half by its borrow: hp = high(low + l), hm = hp - 1 (l's limb 2
    // holds bit 252, so l_hi - 1 does not borrow into limb 3).
    // Why: a whole four-limb add in stage 8 (low + (l - tc)) placed as four
    // carry chains far apart; it was the 12-machine signer's worst routed
    // path (-0.358 ns, 2026-10-18), into stage 1 and the finisher entry.
    let l = pack16(widen15(order_l_digits()));
    let low = r.s7_low;
    let p0 = low[0].resize::<86>() + l[0].resize::<86>();
    let p1 = low[1].resize::<86>() + l[1].resize::<86>() + (p0 >> 85);
    let c = p1 >> 85;
    let h2 = low[2].resize::<86>() + l[2].resize::<86>() + c;
    let h3 = low[3].resize::<86>() + l[3].resize::<86>() + (h2 >> 85);
    let m2 = low[2].resize::<86>() + (l[2] - b85(1)).resize::<86>() + c;
    let m3 = low[3].resize::<86>() + l[3].resize::<86>() + (m2 >> 85);
    n.s8_lo = [p0.resize::<85>(), p1.resize::<85>()];
    n.s8_tc = r.s7_tc;
    n.s8_hp = [h2.resize::<85>(), h3.resize::<85>()];
    n.s8_hm = [m2.resize::<85>(), m3.resize::<85>()];
    n.s8 = r.s7;

    // ---- Stage 8: acc' = low + m; advance, finish, park, or admit.
    let c8 = r.s8;
    // acc' = (u mod 2^252) + l - t * c, below 2^254.
    let d0 = r.s8_lo[0].resize::<86>() - r.s8_tc[0].resize::<86>();
    let d1 = r.s8_lo[1].resize::<86>() - r.s8_tc[1].resize::<86>() - ((d0 >> 85) & b86(1));
    let hi = if (d1 >> 85) & b86(1) != b86(0) { r.s8_hm } else { r.s8_hp };
    let acc_next = unpack16([d0.resize::<85>(), d1.resize::<85>(), hi[0], hi[1]]);
    // The context written back to stage 1.
    let mut next = c8;
    // The context hands its accumulator to the finisher this cycle.
    let mut leaving = false;
    if c8.valid && !c8.parked {
        // A step completed: commit acc' and shift the next digit into
        // x[30].
        for k in 0..15 {
            next.acc[k] = acc_next[k];
        }
        for k in 1..31 {
            next.x[k] = c8.x[k - 1];
        }
        next.x[0] = b17(0);
        next.remaining = c8.remaining - b5(1);
        if c8.remaining == b5(1) {
            // That was the last step: finish now, or park and keep the
            // final accumulator until the finisher is free.
            if finish_free {
                leaving = true;
            } else {
                next.parked = true;
            }
        }
    } else if c8.valid && c8.parked && finish_free {
        // A parked context retries each lap; its `acc` is already final.
        leaving = true;
    }
    if leaving {
        // The finisher entry forms S = acc + Z (below 2^254 + l) next cycle.
        n.f0_valid = true;
        n.f0_tag = c8.tag;
        n.f0_acc = pack16(widen15(next.acc));
        n.f0_z = pack16(widen15(c8.z));
    }
    // The slot being written to stage 1 is empty or just emptied, so a new
    // job can take it.
    let slot_free = !c8.valid || leaving;
    if slot_free {
        next.valid = false;
        if i.job.valid {
            // Admit: 31 steps from acc = 0.
            next = ScalarCtx {
                valid: true,
                parked: false,
                remaining: b5(31),
                tag: i.job.tag,
                acc: [b17(0); 15],
                x: i.job.x,
                y: i.job.y,
                z: i.job.z,
            };
        }
    }
    n.s1 = next;
    let out = ScalarRingOut {
        ready: slot_free,
        done: r.done,
    };
    (out, D { regs: n })
}

/// Host helper: split little-endian bytes into `D` 17-bit digits, least
/// significant first. Bits past the end of `bytes` read as zero.
pub fn digits17<const D: usize>(bytes: &[u8]) -> [b17; D] {
    std::array::from_fn(|k| {
        let mut v = 0u128;
        for b in 0..17 {
            // Absolute bit index of bit `b` of digit `k`.
            let bit = 17 * k + b;
            if bit / 8 < bytes.len() && (bytes[bit / 8] >> (bit % 8)) & 1 == 1 {
                v |= 1 << b;
            }
        }
        b17(v)
    })
}

/// Host helper: digits back to 32 little-endian bytes. Fifteen digits
/// cover bits 0..255, so the `bit < 256` guard never drops a set bit.
pub fn bytes_from_digits(d: &[b17; 15]) -> [u8; 32] {
    let mut out = [0u8; 32];
    for (k, digit) in d.iter().enumerate() {
        for b in 0..17 {
            // Absolute bit index of bit `b` of digit `k`.
            let bit = 17 * k + b;
            if (digit.raw() >> b) & 1 == 1 && bit < 256 {
                out[bit / 8] |= 1 << (bit % 8);
            }
        }
    }
    out
}

/// Cycle-level check of the ring against big-integer arithmetic.
#[cfg(test)]
mod tests {
    use super::*;
    use crate::simulation::CycleSim;
    use num_bigint::BigUint;

    /// The group order as a big integer.
    fn l() -> BigUint {
        BigUint::from_bytes_le(&crate::host::L_BYTES)
    }

    /// Forty jobs with random and edge-case operands (an all-ones 512-bit
    /// `X`, `Y = l - 1`, `Z = l - 1`), with `out_ready` low every fourth
    /// cycle so results back up and contexts park. Every result must match
    /// `(X * Y + Z) mod l` and arrive exactly once under its tag.
    #[test]
    fn ring_matches_bignum_with_backpressure() {
        // xorshift64 state; a fixed seed keeps the test deterministic.
        let mut state = 0x243f_6a88_85a3_08d3u64;
        let mut rand_bytes = |n: usize| -> Vec<u8> {
            (0..n)
                .map(|_| {
                    state ^= state << 13;
                    state ^= state >> 7;
                    state ^= state << 17;
                    state as u8
                })
                .collect()
        };
        // l - 1, the largest allowed Y and Z.
        let lm1 = (l() - 1u32).to_bytes_le();
        let mut jobs = Vec::new();
        for k in 0..40 {
            let x = if k == 0 { vec![0xff; 64] } else { rand_bytes(64) };
            let y = if k % 5 == 1 {
                lm1.clone()
            } else {
                (BigUint::from_bytes_le(&rand_bytes(32)) % l()).to_bytes_le()
            };
            let z = if k % 7 == 2 {
                lm1.clone()
            } else {
                (BigUint::from_bytes_le(&rand_bytes(32)) % l()).to_bytes_le()
            };
            jobs.push((x, y, z));
        }
        let mut sim = CycleSim::new(ScalarRing::default());
        let idle = ScalarJob {
            valid: false,
            tag: b16(0),
            x: [b17(0); 31],
            y: [b17(0); 15],
            z: [b17(0); 15],
        };
        let mut out = sim.tick(ScalarRingIn {
            job: idle,
            out_ready: false,
        });
        // Index of the next job to present.
        let mut next = 0;
        // Result per tag; a second result for the same tag fails the test.
        let mut got = vec![None; jobs.len()];
        for cycle in 0..40_000 {
            let mut job = idle;
            // Present a job only when the ring reported ready on the
            // previous output.
            if out.ready && next < jobs.len() {
                let (x, y, z) = &jobs[next];
                job = ScalarJob {
                    valid: true,
                    tag: b16(next as u128),
                    x: digits17::<31>(x),
                    y: digits17::<15>(y),
                    z: digits17::<15>(z),
                };
                next += 1;
            }
            // Backpressure: refuse results one cycle in four.
            let out_ready = cycle % 4 != 0;
            if out.done.valid && out_ready {
                let tag = out.done.tag.raw() as usize;
                assert!(got[tag].is_none());
                got[tag] = Some(bytes_from_digits(&out.done.s));
            }
            out = sim.tick(ScalarRingIn { job, out_ready });
        }
        for (k, (x, y, z)) in jobs.iter().enumerate() {
            let want = (BigUint::from_bytes_le(x) * BigUint::from_bytes_le(y)
                + BigUint::from_bytes_le(z))
                % l();
            let mut w = [0u8; 32];
            let b = want.to_bytes_le();
            w[..b.len()].copy_from_slice(&b);
            assert_eq!(got[k].expect("missing"), w, "job {k}");
        }
    }
}