rhdl_ed25519_scalable_core/

sign_core.rs

//! The controller: how requests flow through the engines, and why the flow
//! cannot deadlock.
//!
//! [`ScalableSignCore`] instantiates `NFB` fixed-base machines, `NSHA`
//! SHA-512 rings, `NSC` scalar rings and `NCP` (0 or 1) batch-compress
//! machines, and moves every request through them:
//!
#![doc = concat!("<div style=\"overflow-x:auto\">", include_str!("../docs/images/dataflow.svg"), "</div>")]
//!
//! # Handshakes and parking
//!
//! Every arrow is a ready/valid handshake. A producer that cannot hand off
//! *parks*: rings keep the finished job circulating, machines retry their
//! `OUT` bundle. Nothing is dropped and no queue can overflow.
//!
//! # Credits: the deadlock argument
//!
//! The SHA-512 and scalar rings are shared by the first half of signing
//! (nonce hash, `r`) and the second (challenge hash, `S`). Without care, the
//! loop SHA → scalar → fixed-base → compress → SHA can fill up and stop.
//! The rule that prevents it: **a request is admitted only with a credit**, a
//! reserved batch-compress slot (in fused mode, a fixed-base context),
//! returned when the request leaves that stage. With its slot reserved,
//! every fixed-base output has somewhere to go, the fixed-base machines always
//! drain, and every remaining wait points strictly downstream.
//!
//! # Credits: the throughput limit
//!
//! A credit is held from admission until its compress batch retires: about
//! 12.5k cycles of fixed-base program (392 bundles × 32 contexts), 27k of
//! batch compression (423 bundles × 64 contexts) and ~8k of hashing,
//! queueing and filling. By Little's law the credit pool caps throughput at
//! *credits ÷ hold time*: with 2,048 credits, about one signature per 23
//! cycles. (With the first design's 1,024 credits and longer hold, the cap
//! was ~44 cycles, which is why 12/6/2/1 and 13/8/2/1 measured 45.7 and 44.1
//! however many machines they had.)
//!
//! # Contexts
//!
//! Messages, `r`, `R` and user tags live in BRAM indexed by a sign context.
//! There are `2^CB` contexts: [`CTX_BITS`] = 11 (2,048) for throughput
//! profiles; [`Ed25519SignCore`](crate::ed25519_sign_core::Ed25519SignCore) uses 7, since fused
//! mode never admits more than `32 · NFB` requests.
//!
//! # Other behaviour
//!
//! - Fixed-base outputs fill one compress batch of [`COMPRESS_BATCH`] points
//!   at a time; a partial batch is flushed after 64 idle cycles when enough
//!   credits remain to pay for its empty slots, so a trickle still completes.
//! - Key expansion uses the same SHA ring, scalar ring and fixed-base
//!   machine; `load_key_ready` requires an idle signer with no key loaded.
//! - Scalars are recoded in hardware by [`recode_mixed`].
//! - A single request takes ~22k cycles on 1/1/1/0 and ~45–50k on 15/11/3/1;
//!   throughput needs many requests in flight.
//!
//! # Job tags
//!
//! Every SHA-512, scalar, fixed-base and compress job carries a 16-bit tag:
//! bits 15..11 are the job kind (`KIND_NONCE` = 0, `KIND_CHALLENGE` = 1,
//! `KIND_KEY` = 2) and bits 10..0 the sign context. A completion therefore
//! says which step finished and where its request's state lives, so no
//! engine needs to finish in order. Key jobs use context 0; they only run
//! while no request is in flight, so they cannot collide with a request.
//!
//! # Steps of one request
//!
//! 1. Admission: take a free context and a credit, store `M` and the user
//!    tag, start `SHA-512(prefix || M)` (kind nonce).
//! 2. Scalar ring: `r = digest mod l`; `r` is stored for step 5.
//! 3. Fixed-base machine: `[r]B`, then either affine conversion in the same
//!    machine (fused, `NCP = 0`) or batch conversion in the compress stage.
//! 4. The encoding `R` is stored and `SHA-512(R || A || M)` starts (kind
//!    challenge).
//! 5. Scalar ring: `S = k * a + r mod l`.
//! 6. Output `R || S` with the user tag and return the context.
//!
//! Key loading runs the same engines with kind key: `SHA-512(seed)`,
//! `a mod l`, `[a]B`, and the encoding becomes the cached public key.

use rhdl::prelude::*;
use rhdl_fpga::core::{
    dff::DFF,
    ram::synchronous::{In as RamIn, SyncBRAM, Write as RamWrite},
};

use super::{
    compress_stage::{CompressIn, CompressStage, PointIn},
    fe17::Fe17,
    machine::{DigitsWrite, FieldMachine, InputWrite, MachineIn, StartReq, TableWrite, no_key},
    programs::{fixed_base, fixed_base_affine},
    scalar_ring::{ScalarJob, ScalarRing, ScalarRingIn},
    sha_ring::{ShaDone, ShaJob, ShaRing, ShaRingIn, ShaRingOut},
};
use crate::{
    digest::{prefix_from_digest, reverse_bytes, secret_from_digest, words256},
    wire::{ScalarWords, SignRequest, Words512},
};

/// Fixed-base machine: 32 contexts (`KB = 5`), a 1024-bundle program ROM
/// (`PB = 10`) and a `TB = 9` table scanner.
///
/// Bank widths follow [`FieldMachine`]'s `index * K + ctx` addressing:
/// `RA = 9` gives 16 bank-M/A registers per context and `IA = 5` one bank-I
/// register per context (the fixed-base program takes no inputs; its scalar
/// arrives as scan digits).
pub type FbMachine = FieldMachine<5, 32, 9, 5, 10, 9, 1>;
// Compress-stage sizes and machine type, re-exported so users of the
// controller need not import `compress_stage`.
pub use crate::compress_stage::{COMPRESS_BATCH, COMPRESS_CONTEXTS, CpMachine};
/// Sign-context index width of the throughput profiles (2048 requests in
/// flight); the `CB` parameter of [`ScalableSignCore`] may be smaller.
/// Context fields in registers and tags stay 11 bits wide regardless of
/// `CB`; they are resized to `CB` only at the memory ports.
pub const CTX_BITS: usize = 11;

/// Tag kind (bits 15..11): `SHA-512(prefix || M)`, then `r` and `[r]B`.
const KIND_NONCE: u128 = 0;
/// Tag kind: `SHA-512(R || A || M)`, then `S`.
const KIND_CHALLENGE: u128 = 1;
/// Tag kind: key expansion, `SHA-512(seed)`, then `a` and `A = [a]B`.
const KIND_KEY: u128 = 2;

/// Public input of [`ScalableSignCore`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ScalableSignIn {
    /// Load and expand `key_seed` when `load_key_ready` is high in the same
    /// cycle.
    pub load_key_valid: bool,
    /// Secret Ed25519 seed, sampled in the cycle the load is accepted.
    pub key_seed: ScalarWords,
    /// Clear the cached key (prefix, `a`, public key) at the next edge.
    pub clear_key: bool,
    /// Sign `request` when `ready` is high in the same cycle.
    pub valid: bool,
    /// Signing request.
    pub request: SignRequest,
    /// The shared SHA-512 port (`SH = 1`; ignored otherwise), as a ring's
    /// outputs: see [`crate::sha_client::SharedShaPort`].
    pub sha_ext: ShaRingOut,
}

/// Public output of [`ScalableSignCore`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ScalableSignOut {
    /// A key load may be presented: the signer is idle, no key is loaded and
    /// a SHA-512 port can take the seed block this cycle. Combinational.
    pub load_key_ready: bool,
    /// A key is cached.
    pub key_loaded: bool,
    /// Cached public key (valid while `key_loaded`).
    pub public_key: ScalarWords,
    /// A signing request may be presented. Combinational: it needs a cached
    /// key, a free context, a credit, a SHA-512 port ready this cycle, and no
    /// challenge hash waiting for that port.
    pub ready: bool,
    /// One-cycle completion pulse.
    pub valid: bool,
    /// Tag of the completed request.
    pub tag: b16,
    /// `R || S`: words 0..4 are `R`, words 4..8 are `S`.
    pub signature: Words512,
    /// Sticky internal invariant violation: the credit count left its pool
    /// (only checked invariant so far).
    pub internal_error: bool,
    /// Sign contexts currently in use (admitted, not yet output). A key load
    /// is not counted.
    pub in_flight: b12,
    /// Jobs for the shared SHA-512 port (`SH = 1`; idle otherwise).
    pub sha_ext: ShaRingIn,
}

/// Challenge-hash stage: holds `R` for one request until a SHA-512 port
/// takes `R || A || M`.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct H2Stage {
    /// The stage holds a request.
    valid: bool,
    /// [`Self::msg`] has been loaded; the `msg` BRAM read issued when the
    /// stage was filled returns one cycle later.
    has_msg: bool,
    /// Sign context of the request.
    ctx: b11,
    /// Encoded `R`, little-endian words.
    r_enc: [b64; 4],
    /// The request's 64-byte message.
    msg: Words512,
}

/// Scalar-ring dispatch stage: one `(x * y + z) mod l` job waiting for a
/// free scalar ring.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct ScStage {
    /// The stage holds a job.
    valid: bool,
    /// Challenge job still waiting for its addend `r` from the `r_sc` BRAM
    /// (read issued the cycle the stage was filled); blocks dispatch.
    needs_r: bool,
    /// Job tag (kind and sign context).
    tag: b16,
    /// Multiplicand, 31 little-endian 17-bit digits (527 bits): the
    /// 512-bit digest, or the 255-bit clamped secret for a key job.
    x: [b17; 31],
    /// Multiplier is the cached secret `a` (challenge jobs); otherwise 1.
    y_is_a: bool,
    /// Addend: `r` for challenge jobs, zero otherwise.
    z: [b17; 15],
}

/// Fixed-base dispatch stage: one recoded scalar waiting for a free
/// fixed-base context.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct FbStage {
    /// The stage holds a scalar.
    valid: bool,
    /// Job tag (kind nonce or key, and the sign context).
    tag: b16,
    /// Signed digits from [`recode_mixed`]; entries 54..64 are zero.
    digits: [b6; 64],
}

/// Signature output stage: lasts exactly one cycle, while the `r_out` and
/// `user_tag` reads issued the cycle before return.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct FinStage {
    /// A signature is output this cycle.
    valid: bool,
    /// Sign context, returned to the free list this cycle.
    ctx: b11,
    /// `S`, fifteen 17-bit digits (canonical, below `l`).
    s: [b17; 15],
}

/// Fused-mode (`NCP = 0`) point stage: affine `y` of `[r]B` or `[a]B`
/// waiting for its `x` sign and then for the challenge stage. Its layout
/// mirrors the compress stage's output register; `has_tag` here means the
/// sign of `x` has been read.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct CpOutStage {
    /// The stage holds a point.
    valid: bool,
    /// [`Self::x_negative`] has been loaded from the `xsign` BRAM (one cycle
    /// after the read was issued).
    has_tag: bool,
    /// Fixed-base job tag (kind and sign context).
    tag: b16,
    /// Set to true on load and not read by this controller.
    keep: bool,
    /// Sign of affine `x`.
    x_negative: bool,
    /// Canonical affine `y`.
    y: Fe17,
}

/// All controller registers of [`ScalableSignCore`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct SignRegs<const NFB: usize> {
    // Key cache.
    /// A key is cached and requests may be admitted.
    key_loaded: bool,
    /// Key expansion is running (seed accepted, public key not yet encoded).
    keygen: bool,
    /// A key clear arrived while an expansion was running: until the
    /// expansion ends, everything it writes is wiped each cycle and its
    /// result is discarded.
    key_cancel: bool,
    /// Nonce prefix: upper half of `SHA-512(seed)`.
    prefix: ScalarWords,
    /// Secret scalar `a mod l`, multiplier of every challenge job.
    a_digits: [b17; 15],
    /// Encoded public key `A`, little-endian words.
    public_key: [b64; 4],
    // Free sign-context FIFO (BRAM storage).
    /// [`Self::free_head`] holds a free context ready for the next admission.
    free_head_valid: bool,
    /// The next context to hand out; kept in a register so admission does
    /// not wait for a BRAM read.
    free_head: b11,
    /// A `free_list` read was issued last cycle; its data arrives this cycle.
    free_fetching: bool,
    /// FIFO read pointer. Only its low `CB` bits address the memory, so the
    /// 11-bit counter wraps correctly for any `CB`.
    free_rd: b11,
    /// FIFO write pointer, same wrapping as [`Self::free_rd`].
    free_wr: b11,
    /// Entries in FIFO storage, not counting the head or a fetch in flight.
    free_count: b12,
    /// Number of contexts, `2^CB`; constant after reset.
    ctx_total: b12,
    // Pipeline stages.
    /// Challenge-hash stage.
    h2: H2Stage,
    /// Scalar-ring dispatch stage.
    sc: ScStage,
    /// Fixed-base dispatch stage.
    fb: FbStage,
    /// Signature output stage.
    fin: FinStage,
    // Fixed-base contexts (bit set = free) and compress-slot credits.
    /// Per fixed-base machine, bit `c` set when context `c` is free.
    fb_free: [b32; NFB],
    /// Admission credits left: free fixed-base contexts (fused mode) or
    /// unreserved compress slots (compress mode).
    credits: b12,
    // Fused-mode point stage (named after the batch-compress output stage
    // it replaces).
    /// Fused-mode point stage.
    cpo: CpOutStage,
    /// Sticky error flag behind `internal_error`; reset to false and not
    /// set by the current kernel.
    error: bool,
}


/// Controller memories (all inferred BRAM), each `2^CB` deep and indexed by
/// sign context, except `free_list`, which is indexed by FIFO position.
/// Every read has one cycle of latency, which is why several stages wait a
/// cycle (`has_msg`, `needs_r`, `has_tag`) before using read data.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct SignMems<const CB: usize>
where
    rhdl::bits::W<CB>: BitWidth,
{
    /// Message of each request, read again for the challenge hash.
    msg: SyncBRAM<Words512, CB>,
    /// Nonce scalar `r`, written by the nonce job, read as the challenge
    /// job's addend.
    r_sc: SyncBRAM<[b17; 15], CB>,
    /// Encoded `R`, written before the challenge hash, read at output.
    r_out: SyncBRAM<[b64; 4], CB>,
    /// The caller's tag, written at admission, read at output.
    user_tag: SyncBRAM<b16, CB>,
    /// Free-context FIFO storage, preloaded with every context.
    free_list: SyncBRAM<b11, CB>,
    /// Fused mode: sign of affine `x`, written when `x` leaves a fixed-base
    /// machine and read when `y` follows.
    xsign: SyncBRAM<bool, CB>,
}

/// Port bundle of [`SignMems`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct SignMemsIn<const CB: usize>
where
    rhdl::bits::W<CB>: BitWidth,
{
    /// Messages by sign context.
    pub msg: RamIn<Words512, CB>,
    /// Nonce scalars `r`.
    pub r_sc: RamIn<[b17; 15], CB>,
    /// Encoded `R`.
    pub r_out: RamIn<[b64; 4], CB>,
    /// User tags.
    pub user_tag: RamIn<b16, CB>,
    /// Free-context FIFO storage.
    pub free_list: RamIn<b11, CB>,
    /// Fused mode: sign of affine x by sign context.
    pub xsign: RamIn<bool, CB>,
}

/// Read data of [`SignMems`], valid one cycle after the read address.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct SignMemsOut {
    /// Message.
    pub msg: Words512,
    /// Nonce scalar.
    pub r_sc: [b17; 15],
    /// Encoded `R`.
    pub r_out: [b64; 4],
    /// User tag.
    pub user_tag: b16,
    /// Free-list entry.
    pub free_list: b11,
    /// Sign of x.
    pub xsign: bool,
}

/// Binds the memory ports and their wiring kernel.
impl<const CB: usize> SynchronousIO for SignMems<CB>
where
    rhdl::bits::W<CB>: BitWidth,
{
    type I = SignMemsIn<CB>;
    type O = SignMemsOut;
    type Kernel = sign_mems_kernel<CB>;
}

/// Wiring for [`SignMems`]: ports pass straight to the six BRAMs.
#[kernel]
pub fn sign_mems_kernel<const CB: usize>(
    _cr: ClockReset,
    i: SignMemsIn<CB>,
    q: SignMemsQ<CB>,
) -> (SignMemsOut, SignMemsD<CB>)
where
    rhdl::bits::W<CB>: BitWidth,
{
    let mut d = SignMemsD::<CB>::dont_care();
    d.msg = i.msg;
    d.r_sc = i.r_sc;
    d.r_out = i.r_out;
    d.user_tag = i.user_tag;
    d.free_list = i.free_list;
    d.xsign = i.xsign;
    (
        SignMemsOut {
            msg: q.msg,
            r_sc: q.r_sc,
            r_out: q.r_out,
            user_tag: q.user_tag,
            free_list: q.free_list,
            xsign: q.xsign,
        },
        d,
    )
}

/// Resource-scalable cached-key Ed25519 signer with `2^CB` sign contexts
/// (`CB <= 11`; [`CTX_BITS`] for the throughput profiles).
///
/// - `NFB`: fixed-base machines (32 contexts each).
/// - `NSHA`: SHA-512 rings (still instantiated when `SH = 1`, but unused).
/// - `NSC`: scalar rings.
/// - `NCP`: batch-compress stages, 0 (fused: each fixed-base machine converts
///   its own result to affine) or 1.
/// - `CB`: sign-context index width.
/// - `SH`: 1 sends all hashing to the external port `sha_ext`.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
#[rhdl(dq_no_prefix)]
pub struct ScalableSignCore<
    const NFB: usize,
    const NSHA: usize,
    const NSC: usize,
    const NCP: usize,
    const CB: usize,
    const SH: usize,
> where
    rhdl::bits::W<CB>: BitWidth,
{
    /// Controller registers.
    regs: DFF<SignRegs<NFB>>,
    /// Per-context BRAMs and the free-context FIFO.
    mems: SignMems<CB>,
    /// Fixed-base machines.
    fb: [FbMachine; NFB],
    /// SHA-512 rings.
    sha: [ShaRing; NSHA],
    /// Scalar multiply-add rings modulo `l`.
    sc: [ScalarRing; NSC],
    /// Batch-compress stage (zero or one).
    cp: [CompressStage; NCP],
}

/// Reset state: no key, every context in the free list, all credits
/// available, and each fixed-base machine loaded with the program for the
/// chosen mode. Panics if the parameters break the credit invariants.
impl<const NFB: usize, const NSHA: usize, const NSC: usize, const NCP: usize, const CB: usize, const SH: usize>
    Default for ScalableSignCore<NFB, NSHA, NSC, NCP, CB, SH>
where
    rhdl::bits::W<CB>: BitWidth,
{
    fn default() -> Self {
        assert!(NFB >= 1 && NSHA >= 1 && NSC >= 1 && NCP <= 1 && SH <= 1);
        assert!(CB <= CTX_BITS);
        // Admission credits must never exceed the sign contexts: 32 per
        // fixed-base machine in fused mode, 2,048 compress slots otherwise.
        assert!(NFB * 32 <= 1 << CB);
        assert!(NCP == 0 || COMPRESS_CONTEXTS * COMPRESS_BATCH <= 1 << CB);
        // Fused mode ends each fixed-base program with its own inversion
        // and outputs affine x, y; compress mode outputs projective X, Y, Z.
        let fb_program = if NCP == 0 {
            fixed_base_affine()
        } else {
            fixed_base()
        };
        Self {
            regs: DFF::new(SignRegs {
                key_loaded: false,
                keygen: false,
                key_cancel: false,
                prefix: ScalarWords { words: [b64(0); 4] },
                a_digits: [b17(0); 15],
                public_key: [b64(0); 4],
                free_head_valid: false,
                free_head: b11(0),
                free_fetching: false,
                free_rd: b11(0),
                free_wr: b11(0),
                free_count: b12(1 << CB),
                ctx_total: b12(1 << CB),
                h2: H2Stage {
                    valid: false,
                    has_msg: false,
                    ctx: b11(0),
                    r_enc: [b64(0); 4],
                    msg: Words512::zero(),
                },
                sc: ScStage {
                    valid: false,
                    needs_r: false,
                    tag: b16(0),
                    x: [b17(0); 31],
                    y_is_a: false,
                    z: [b17(0); 15],
                },
                fb: FbStage {
                    valid: false,
                    tag: b16(0),
                    digits: [b6(0); 64],
                },
                fin: FinStage {
                    valid: false,
                    ctx: b11(0),
                    s: [b17(0); 15],
                },
                fb_free: [b32(0xffff_ffff); NFB],
                // One credit per fixed-base context (fused) or per compress
                // slot (compress mode).
                credits: b12(if NCP == 0 {
                    (32 * NFB) as u128
                } else {
                    (COMPRESS_CONTEXTS * COMPRESS_BATCH) as u128
                }),
                cpo: CpOutStage {
                    valid: false,
                    has_tag: false,
                    tag: b16(0),
                    keep: false,
                    x_negative: false,
                    y: Fe17::zero(),
                },
                error: false,
            }),
            mems: SignMems {
                msg: SyncBRAM::default(),
                r_sc: SyncBRAM::default(),
                r_out: SyncBRAM::default(),
                user_tag: SyncBRAM::default(),
                // Entry k holds context k: the FIFO starts full.
                free_list: SyncBRAM::new((0..1u128 << CB).map(|k| (bits::<CB>(k), b11(k)))),
                xsign: SyncBRAM::default(),
            },
            // The first `URAM_MACHINES` machines keep their banks in
            // UltraRAM; the rest take the block-RAM fallback (the planner's
            // placement when a build runs out of UltraRAM).
            fb: std::array::from_fn(|k| FbMachine::with_memory(&fb_program, crate::machine::placement(k))),
            sha: std::array::from_fn(|_| ShaRing::default()),
            sc: std::array::from_fn(|_| ScalarRing::default()),
            cp: std::array::from_fn(|_| CompressStage::default()),
        }
    }
}

/// Binds the public ports and the controller kernel.
impl<const NFB: usize, const NSHA: usize, const NSC: usize, const NCP: usize, const CB: usize, const SH: usize>
    SynchronousIO for ScalableSignCore<NFB, NSHA, NSC, NCP, CB, SH>
where
    rhdl::bits::W<CB>: BitWidth,
{
    type I = ScalableSignIn;
    type O = ScalableSignOut;
    type Kernel = scalable_sign_kernel<NFB, NSHA, NSC, NCP, CB, SH>;
}

/// Little-endian 64-bit words to thirty-one 17-bit digits.
///
/// Digit `k` is bits `17k .. 17k + 17` of the 512-bit value (527 bits of
/// digits, the top 15 zero). This is the multiplicand format of the scalar
/// ring.
#[kernel]
pub fn words_to_digits31(w: [b64; 8]) -> [b17; 31] {
    let mut out = [b17(0); 31];
    for k in 0..31 {
        for word in 0..8 {
            // Digit k starts in this word. The loop bounds are constants, so
            // after unrolling exactly one word matches per digit.
            if 17 * k >= 64 * word && 17 * k < 64 * word + 64 {
                let offset = 17 * k - 64 * word;
                // Join this word with the next so a digit that crosses the
                // word boundary is extracted in one shift.
                let low = w[word].resize::<128>();
                let high = if word + 1 < 8 {
                    w[word + 1].resize::<128>()
                } else {
                    b128(0)
                };
                out[k] = ((low | (high << 64)) >> (offset as u128)).resize::<17>();
            }
        }
    }
    out
}

/// Four little-endian words (bits 0..255) to fifteen digits (bit 255 dropped).
///
/// Fifteen 17-bit digits hold 255 bits, the format of field elements and of
/// scalars below `l`.
#[kernel]
pub fn words_to_digits15(w: [b64; 4]) -> [b17; 15] {
    // Zero-extend to 512 bits and reuse the 31-digit split.
    let mut wide = [b64(0); 8];
    for k in 0..4 {
        wide[k] = w[k];
    }
    let d = words_to_digits31(wide);
    let mut out = [b17(0); 15];
    for k in 0..15 {
        out[k] = d[k];
    }
    out
}

/// Fifteen digits to four little-endian words.
///
/// Inverse of [`words_to_digits15`]; bit 255 of the result is zero.
#[kernel]
pub fn digits15_to_words(d: [b17; 15]) -> [b64; 4] {
    let mut out = [b64(0); 4];
    for k in 0..15 {
        for word in 0..4 {
            // Digit k starts in this word (one match per digit after
            // unrolling).
            if 17 * k >= 64 * word && 17 * k < 64 * word + 64 {
                let offset = 17 * k - 64 * word;
                // Shift in 128 bits; the part above bit 63 spills into the
                // next word.
                let wide = d[k].resize::<128>() << (offset as u128);
                out[word] = out[word] | wide.resize::<64>();
                if word + 1 < 4 {
                    out[word + 1] = out[word + 1] | (wide >> 64).resize::<64>();
                }
            }
        }
    }
    out
}

/// Signed mixed-radix recoding ([`super::host::recode`]) of a scalar below
/// `2^253`: digits 0..39 are radix 32, 39..54 radix 16, sign-magnitude
/// (bit 5 = sign); entries 54..64 are zero.
///
/// Carry `c[i+1] = (n[i] >= h) | (n[i] == h - 1 & c[i])` with `h` half the
/// digit's radix is evaluated as the carry chain of `(g | p) + g`, i.e. one
/// ordinary 64-bit addition.
///
/// The digit radixes match the fixed-base tables: each digit selects a
/// signed multiple of a precomputed point, so a radix-32 digit uses magnitudes
/// 0..=16 and a radix-16 digit 0..=8.
#[kernel]
pub fn recode_mixed(s: [b17; 15]) -> [b6; 64] {
    let w = digits15_to_words(s);
    // Unsigned digits before carries: 39 five-bit digits (bits 0..195), then
    // 15 four-bit digits (bits 195..255).
    let mut nib = [b6(0); 54];
    for k in 0..54 {
        // Bit position of digit k.
        let offset = if k < 39 { 5 * k } else { 195 + 4 * (k - 39) };
        for word in 0..4 {
            if offset >= 64 * word && offset < 64 * word + 64 {
                let low = w[word].resize::<128>();
                let high = if word + 1 < 4 {
                    w[word + 1].resize::<128>()
                } else {
                    b128(0)
                };
                let shift = offset - 64 * word;
                let raw = ((low | (high << 64)) >> (shift as u128)).resize::<6>();
                nib[k] = if k < 39 { raw & b6(31) } else { raw & b6(15) };
            }
        }
    }
    // Carry generate and propagate, one bit per digit: digit k generates a
    // carry if it is at least half its radix (it will be made negative), and
    // propagates an incoming carry if it is exactly one below half (adding
    // the carry makes it reach half).
    let mut g = b64(0);
    let mut p = b64(0);
    for k in 0..54 {
        let half = if k < 39 { b6(16) } else { b6(8) };
        if nib[k] >= half {
            g = g | (b64(1) << (k as u128));
        }
        if nib[k] == half - b6(1) {
            p = p | (b64(1) << (k as u128));
        }
    }
    let a = g | p;
    // carry_in[i]: bit i of (a + g) ^ a ^ g.
    let carry_in = (a + g) ^ a ^ g;
    let mut out = [b6(0); 64];
    for k in 0..54 {
        let half = if k < 39 { b6(16) } else { b6(8) };
        let cin = ((carry_in >> (k as u128)) & b64(1)).resize::<6>();
        // Digit value after its incoming carry, 0..=2 * half.
        let v = nib[k] + cin;
        // The top digit never carries out: the scalar is below 2^253, so it
        // is at most 3 + 1, below half = 8.
        let cout = if k < 53 { v >= half } else { false };
        out[k] = if cout {
            // v - radix is negative; store its magnitude with the sign bit.
            // v == radix gives zero, which is stored without a sign.
            let magnitude = half + half - v;
            if magnitude == b6(0) {
                b6(0)
            } else {
                magnitude | b6(32)
            }
        } else {
            v
        };
    }
    out
}

/// Base-point digits in slots 0..64 of the machine's 128 digit slots.
///
/// Slots 64..128 are for a second (key) scalar, which the fixed-base
/// program does not use, so they stay zero.
#[kernel]
pub fn widen_digits(d: [b6; 64]) -> [b6; 128] {
    let mut out = [b6(0); 128];
    for k in 0..64 {
        out[k] = d[k];
    }
    out
}

/// No key-table write.
///
/// The fixed-base and compress machines never load key tables; this idle
/// value ties off their `table` port.
#[kernel]
pub fn idle_table_write() -> TableWrite {
    TableWrite {
        valid: false,
        row: bits(0),
        odd: false,
        coord: b2(0),
        value: Fe17 { d: [b17(0); 15] },
    }
}

/// Encoded `R` from canonical affine `y` and the sign of `x`.
///
/// RFC 8032 point encoding: `y` little-endian with the sign of `x` in bit
/// 255 (free because `y < p < 2^255`).
#[kernel]
pub fn encode_point(y: Fe17, x_negative: bool) -> [b64; 4] {
    let mut w = digits15_to_words(y.d);
    if x_negative {
        w[3] = w[3] | b64(0x8000000000000000);
    }
    w
}

/// Big-endian SHA words of `prefix || M` with padding (96-byte message).
///
/// The 96 bytes fit one 128-byte block together with SHA-512 padding, so
/// the nonce hash needs a single compression.
#[cfg(not(feature = "msg1"))]
#[kernel]
pub fn nonce_block(prefix: ScalarWords, msg: Words512) -> [b64; 16] {
    let mut block = [b64(0); 16];
    // Words 0..4: the 32-byte prefix.
    let p = words256(prefix);
    for k in 0..4 {
        block[k] = p[k];
    }
    // Words 4..12: the 64-byte message, byte-swapped to SHA order.
    for k in 0..8 {
        block[k + 4] = reverse_bytes(msg.words[k]);
    }
    // The 0x80 end marker at byte 96, then the bit length 768 in the last
    // word of the 128-bit length field.
    block[12] = b64(0x8000000000000000);
    block[15] = b64(0x300);
    block
}

/// Big-endian SHA words of `R || A || M` (first of two blocks).
///
/// The 128 bytes fill the block exactly; the ring appends the constant
/// padding block of a 1,024-bit message when the job sets `second_pad`.
#[cfg(not(feature = "msg1"))]
#[kernel]
pub fn challenge_block(r_enc: [b64; 4], a: [b64; 4], msg: Words512) -> [b64; 16] {
    let mut block = [b64(0); 16];
    for k in 0..4 {
        block[k] = reverse_bytes(r_enc[k]);
        block[k + 4] = reverse_bytes(a[k]);
    }
    for k in 0..8 {
        block[k + 8] = reverse_bytes(msg.words[k]);
    }
    block
}

/// The challenge hash needs the ring's second (padding) block: `R‖A‖M` is
/// exactly 128 bytes for a 64-byte message.
#[cfg(not(feature = "msg1"))]
#[kernel]
pub fn challenge_second_pad() -> bool {
    true
}

// ---------------------------------------------------------------------
// Benchmark specialization `msg1`: one-byte messages, the input size of
// ubft_new's HLS Ed25519 wrappers, so the two can be compared doing the
// same work. M is byte 0 of the request's message (the low byte of word
// 0). `prefix‖M` (33 bytes) and `R‖A‖M` (65 bytes) each fit one padded
// SHA-512 block, so the challenge takes one compression, not two. Off by
// default; never a protocol build.

/// `prefix ‖ M` for a one-byte M, padded: one block, bit length 264.
#[cfg(feature = "msg1")]
#[kernel]
pub fn nonce_block(prefix: ScalarWords, msg: Words512) -> [b64; 16] {
    let mut block = [b64(0); 16];
    let p = words256(prefix);
    for k in 0..4 {
        block[k] = p[k];
    }
    let m: b64 = msg.words[0] & b64(0xff);
    block[4] = (m << b64(56)) | b64(0x0080_0000_0000_0000);
    block[15] = b64(264);
    block
}

/// `R ‖ A ‖ M` for a one-byte M, padded: one block, bit length 520.
#[cfg(feature = "msg1")]
#[kernel]
pub fn challenge_block(r_enc: [b64; 4], a: [b64; 4], msg: Words512) -> [b64; 16] {
    let mut block = [b64(0); 16];
    for k in 0..4 {
        block[k] = reverse_bytes(r_enc[k]);
        block[k + 4] = reverse_bytes(a[k]);
    }
    let m: b64 = msg.words[0] & b64(0xff);
    block[8] = (m << b64(56)) | b64(0x0080_0000_0000_0000);
    block[15] = b64(520);
    block
}

/// A one-byte challenge is a single padded block: no second block.
#[cfg(feature = "msg1")]
#[kernel]
pub fn challenge_second_pad() -> bool {
    false
}

/// Padded single block of a 32-byte seed.
#[kernel]
pub fn seed_block(seed: ScalarWords) -> [b64; 16] {
    let mut block = [b64(0); 16];
    let s = words256(seed);
    for k in 0..4 {
        block[k] = s[k];
    }
    // The 0x80 end marker at byte 32 and the bit length 256.
    block[4] = b64(0x8000000000000000);
    block[15] = b64(0x100);
    block
}

/// Digest (big-endian state words) to the little-endian 512-bit integer.
///
/// RFC 8032 reads the 64-byte digest as a little-endian integer; swapping
/// the bytes of each word gives that integer in this crate's word order.
#[kernel]
pub fn digest_le(state: [b64; 8]) -> [b64; 8] {
    let mut out = [b64(0); 8];
    for k in 0..8 {
        out[k] = reverse_bytes(state[k]);
    }
    out
}

/// Memory port that reads `addr` and writes nothing.
///
/// `filler` only gives the disabled write a value of the right type; callers
/// pass the memory's current read data.
#[kernel]
pub fn ram_read<T: Digital, const N: usize>(addr: Bits<N>, filler: T) -> RamIn<T, N>
where
    rhdl::bits::W<N>: BitWidth,
{
    RamIn::<T, N> {
        read_addr: addr,
        write: RamWrite::<T, N> {
            addr: addr,
            value: filler,
            enable: false,
        },
    }
}

/// State transition for [`ScalableSignCore`].
///
/// One pass per cycle through every step, in the order below. Later steps
/// read the `r` (current) registers and so see the state before this
/// cycle's earlier steps, except where they explicitly use `n` or a local
/// such as `credits`, `free_count` or the `*_free` flags, which carry
/// this cycle's earlier decisions forward.
#[kernel]
pub fn scalable_sign_kernel<
    const NFB: usize,
    const NSHA: usize,
    const NSC: usize,
    const NCP: usize,
    const CB: usize,
    const SH: usize,
>(
    _cr: ClockReset,
    i: ScalableSignIn,
    q: Q<NFB, NSHA, NSC, NCP, CB, SH>,
) -> (ScalableSignOut, D<NFB, NSHA, NSC, NCP, CB, SH>)
where
    rhdl::bits::W<CB>: BitWidth,
{
    let r = q.regs;
    let mut n = r;
    let mut d = D::<NFB, NSHA, NSC, NCP, CB, SH>::dont_care();
    // The scalar 1, multiplier of nonce and key jobs (which only reduce
    // their input mod l).
    let one15 = {
        let mut o = [b17(0); 15];
        o[0] = b17(1);
        o
    };

    // Default memory ports: read address 0, no writes. Steps below override
    // the read address or the write of the port they use. The free list
    // always reads at its read pointer, so a fetch only has to wait for
    // the data.
    let zero_ctx = bits::<CB>(0);
    d.mems.msg = ram_read::<Words512, CB>(zero_ctx, q.mems.msg);
    d.mems.r_sc = ram_read::<[b17; 15], CB>(zero_ctx, q.mems.r_sc);
    d.mems.r_out = ram_read::<[b64; 4], CB>(zero_ctx, q.mems.r_out);
    d.mems.user_tag = ram_read::<b16, CB>(zero_ctx, q.mems.user_tag);
    d.mems.free_list = ram_read::<b11, CB>(r.free_rd.resize::<CB>(), q.mems.free_list);
    d.mems.xsign = ram_read::<bool, CB>(zero_ctx, q.mems.xsign);

    // ================= Free sign-context FIFO =================
    // The head register is refilled in the background: a read issued one
    // cycle lands in free_head the next. A context taken in cycle t is
    // replaced by cycle t + 3, so admissions run at most one per three
    // cycles.
    let mut free_count = r.free_count;
    if r.free_fetching {
        n.free_head = q.mems.free_list;
        n.free_head_valid = true;
        n.free_fetching = false;
    }
    // Head empty and storage nonempty: the read at free_rd is on the port
    // this cycle, so advance the pointer and count the entry as removed.
    if !r.free_head_valid && !r.free_fetching && r.free_count != b12(0) {
        n.free_fetching = true;
        n.free_rd = r.free_rd + b11(1);
        free_count = free_count - b12(1);
    }

    // ================= SHA ring availability =================
    // At most one SHA-512 job is issued per cycle, to the lowest-numbered
    // ready ring, or to the external port when SH = 1 (the internal rings
    // are then never picked). sha_pick == NSHA denotes the external port.
    let mut sha_any = false;
    let mut sha_pick = b8(0);
    let shared = SH == 1;
    for k in 0..NSHA {
        if q.sha[k].ready && !sha_any && !shared {
            sha_any = true;
            sha_pick = b8(k as u128);
        }
    }
    if shared && i.sha_ext.ready {
        sha_any = true;
        sha_pick = b8(NSHA as u128);
    }
    // The one job this cycle, chosen by priority below: challenge hash, then
    // key seed, then a new request.
    let mut sha_job = ShaJob {
        valid: false,
        tag: b16(0),
        block: [b64(0); 16],
        second_pad: false,
    };

    // H2 stage: wait one cycle for the message, then dispatch.
    // The challenge hash has first claim on the SHA-512 port: it belongs to a
    // request that already holds a context and a credit, and draining such
    // work first keeps new admissions from starving it.
    if r.h2.valid && !r.h2.has_msg {
        n.h2.msg = q.mems.msg;
        n.h2.has_msg = true;
    }
    // The challenge block can be offered this cycle.
    let h2_ready = r.h2.valid && r.h2.has_msg;
    // A job other than a new request has claimed the SHA port this cycle.
    let mut sha_taken = false;
    if h2_ready && sha_any {
        sha_job = ShaJob {
            valid: true,
            tag: (b16(KIND_CHALLENGE) << 11) | r.h2.ctx.resize::<16>(),
            block: challenge_block(r.h2.r_enc, r.public_key, r.h2.msg),
            // R || A || M is exactly one block; the ring adds the padding
            // block (none for the one-byte benchmark build).
            second_pad: challenge_second_pad(),
        };
        sha_taken = true;
        n.h2.valid = false;
    }

    // Key load: one seed block.
    // Contexts in use: all contexts minus those in FIFO storage, in the head
    // register, or being fetched into it.
    let in_flight = r.ctx_total - r.free_count - if r.free_head_valid {
        b12(1)
    } else {
        b12(0)
    } - if r.free_fetching { b12(1) } else { b12(0) };
    // No request or key expansion anywhere in the pipeline. A request holds
    // its context until output, so in_flight == 0 covers every engine.
    let idle = in_flight == b12(0) && !r.keygen && !r.h2.valid && !r.sc.valid && !r.fb.valid;
    // Credit count, updated in place through the cycle: admissions take one,
    // fixed-base completions (fused) or the compress stage give them back.
    let mut credits = r.credits;
    let load_key_ready = idle && !r.key_loaded && sha_any && !sha_taken;
    if i.load_key_valid && load_key_ready {
        // The key's point passes through a fixed-base context and, in
        // compress mode, a compress slot, so it pays a credit like a request.
        credits = credits - b12(1);
        sha_job = ShaJob {
            valid: true,
            tag: b16(KIND_KEY) << 11,
            block: seed_block(i.key_seed),
            second_pad: false,
        };
        sha_taken = true;
        n.keygen = true;
        n.key_loaded = false;
    }

    // New signing request (lowest SHA priority).
    // Requires a cached key, no key expansion, a free context in the head
    // register, a credit, and a SHA port that the challenge hash does not
    // want this cycle. It cannot coincide with a key load, which needs
    // key_loaded low.
    let sign_ready = r.key_loaded
        && !r.keygen
        && r.free_head_valid
        && r.credits != b12(0)
        && sha_any
        && !h2_ready;
    if i.valid && sign_ready {
        credits = credits - b12(1);
        // Take the head context; the FIFO logic above refills it.
        let ctx = r.free_head;
        n.free_head_valid = false;
        // Store the message (needed again for the challenge hash) and the
        // caller's tag (needed at output).
        d.mems.msg.write = RamWrite::<Words512, CB> {
            addr: ctx.resize::<CB>(),
            value: i.request.message,
            enable: true,
        };
        d.mems.user_tag.write = RamWrite::<b16, CB> {
            addr: ctx.resize::<CB>(),
            value: i.request.tag,
            enable: true,
        };
        sha_job = ShaJob {
            valid: true,
            tag: (b16(KIND_NONCE) << 11) | ctx.resize::<16>(),
            block: nonce_block(r.prefix, i.request.message),
            second_pad: false,
        };
    }
    // Broadcast the job to every SHA port; only the picked one sees valid.
    // out_ready is set later when a digest is taken.
    let mut sha_ext = ShaRingIn {
        job: ShaJob {
            valid: sha_job.valid && shared && sha_pick == b8(NSHA as u128),
            tag: sha_job.tag,
            block: sha_job.block,
            second_pad: sha_job.second_pad,
        },
        out_ready: false,
    };
    for k in 0..NSHA {
        d.sha[k] = ShaRingIn {
            job: ShaJob {
                valid: sha_job.valid && b8(k as u128) == sha_pick,
                tag: sha_job.tag,
                block: sha_job.block,
                second_pad: sha_job.second_pad,
            },
            out_ready: false,
        };
    }

    // ================= SHA completions -> scalar stage =================
    // A challenge job's addend r was requested from r_sc last cycle; it is
    // on the read port now.
    if r.sc.valid && r.sc.needs_r {
        n.sc.z = q.mems.r_sc;
        n.sc.needs_r = false;
    }
    // Lowest-numbered scalar ring that can take a job.
    let mut sc_any = false;
    let mut sc_pick = b8(0);
    for k in 0..NSC {
        if q.sc[k].ready && !sc_any {
            sc_any = true;
            sc_pick = b8(k as u128);
        }
    }
    let sc_dispatch = r.sc.valid && !r.sc.needs_r && sc_any;
    // Broadcast the stage's job; only the picked ring sees valid. out_ready
    // is set below when a result is taken.
    for k in 0..NSC {
        d.sc[k] = ScalarRingIn {
            job: ScalarJob {
                valid: sc_dispatch && b8(k as u128) == sc_pick,
                tag: r.sc.tag,
                x: r.sc.x,
                y: if r.sc.y_is_a { r.a_digits } else { one15 },
                z: r.sc.z,
            },
            out_ready: false,
        };
    }
    if sc_dispatch {
        n.sc.valid = false;
    }
    // The scalar stage can be refilled this cycle (empty, or emptied now).
    let sc_stage_free = !r.sc.valid || sc_dispatch;
    // The first finished digest: a ring's, or the shared port's.
    // At most one digest is taken per cycle, and only when the scalar stage
    // has room; other rings keep theirs circulating (parked) until a later
    // cycle.
    let mut done = ShaDone { valid: false, tag: b16(0), state: [b64(0); 8] };
    for k in 0..NSHA {
        let ring_done = q.sha[k].done;
        if ring_done.valid && sc_stage_free && !done.valid {
            done = ring_done;
            d.sha[k].out_ready = true;
        }
    }
    if shared && i.sha_ext.done.valid && sc_stage_free && !done.valid {
        done = i.sha_ext.done;
        sha_ext.out_ready = true;
    }
    if done.valid {
        // Tag layout: kind in bits 15..11, sign context in bits 10..0.
        let kind = done.tag >> 11;
        let ctx = done.tag.resize::<11>();
        // The digest as the little-endian 512-bit integer RFC 8032 reduces.
        let le = digest_le(done.state);
        if kind == b16(KIND_KEY) {
            // SHA-512(seed): the clamped low half is the secret scalar, the
            // high half the nonce prefix. The job computes a mod l (y = 1,
            // z = 0).
            let secret = secret_from_digest(done.state);
            n.prefix = prefix_from_digest(done.state);
            let mut x = [b64(0); 8];
            for w in 0..4 {
                x[w] = secret.words[w];
            }
            n.sc = ScStage {
                valid: true,
                needs_r: false,
                tag: b16(KIND_KEY) << 11,
                x: words_to_digits31(x),
                y_is_a: false,
                z: [b17(0); 15],
            };
        } else if kind == b16(KIND_NONCE) {
            // r = SHA-512(prefix || M) mod l.
            n.sc = ScStage {
                valid: true,
                needs_r: false,
                tag: done.tag,
                x: words_to_digits31(le),
                y_is_a: false,
                z: [b17(0); 15],
            };
        } else {
            // Challenge: S = k * a + r mod l with k the digest. Fetch r now;
            // needs_r holds the job one cycle until it arrives.
            d.mems.r_sc.read_addr = ctx.resize::<CB>();
            n.sc = ScStage {
                valid: true,
                needs_r: true,
                tag: done.tag,
                x: words_to_digits31(le),
                y_is_a: true,
                z: [b17(0); 15],
            };
        }
    }

    // ================= Scalar completions =================
    // Fixed-base dispatch stage drains first.
    // Pick the lowest-numbered machine with any free context.
    let mut fb_any = false;
    let mut fb_pick = b8(0);
    for k in 0..NFB {
        if r.fb_free[k] != b32(0) && !fb_any {
            fb_any = true;
            fb_pick = b8(k as u128);
        }
    }
    let fb_dispatch = r.fb.valid && fb_any;
    for k in 0..NFB {
        // Lowest free context of the chosen machine.
        let mask = r.fb_free[k];
        let mut ctx = b5(0);
        let mut found = false;
        for c in 0..32 {
            if !found && ((mask >> (c as u128)) & b32(1)) != b32(0) {
                found = true;
                ctx = b5(c as u128);
            }
        }
        // Start the context and write its digits in the same cycle; the
        // job tag travels with the context to its outputs.
        let go = fb_dispatch && b8(k as u128) == fb_pick;
        d.fb[k] = MachineIn::<5> {
            start: StartReq::<5> {
                valid: go,
                ctx: ctx,
                tag: r.fb.tag,
                key: no_key(), entry: b12(0),
            },
            digits: DigitsWrite::<5> {
                valid: go,
                ctx: ctx,
                digits: widen_digits(r.fb.digits),
            },
            input: InputWrite::<5> {
                valid: false,
                ctx: b5(0),
                index: b7(0),
                value: Fe17 { d: [b17(0); 15] },
            },
            table: idle_table_write(),
            out_accept: false,
        };
        // Mark the context busy; it is freed by the machine's done pulse.
        if go {
            n.fb_free[k] = mask & !(b32(1) << (ctx.resize::<32>()));
        }
    }
    if fb_dispatch {
        n.fb.valid = false;
    }
    // The fixed-base stage takes a scalar result only when it was empty at
    // the start of the cycle. Refilling it in the cycle it dispatches would
    // chain the 8 x 32-bit free search into the 255-bit r_sc write (routed
    // -0.37 ns); the stage sees about one job per 46 cycles, so the extra
    // cycle costs nothing.
    let fb_stage_free = !r.fb.valid;

    // Signature output stage.
    // fin was filled last cycle together with the r_out and user_tag reads,
    // so R and the caller's tag are on the read ports now. The output has
    // no backpressure, so the stage always empties.
    let mut out_valid = false;
    let mut out_tag = b16(0);
    let mut out_sig = Words512 { words: [b64(0); 8] };
    let mut push_free = false;
    let mut push_ctx = b11(0);
    if r.fin.valid {
        out_valid = true;
        out_tag = q.mems.user_tag;
        let rw = q.mems.r_out;
        let sw = digits15_to_words(r.fin.s);
        out_sig = Words512 {
            words: [rw[0], rw[1], rw[2], rw[3], sw[0], sw[1], sw[2], sw[3]],
        };
        // The request is finished: return its context to the free list.
        push_free = true;
        push_ctx = r.fin.ctx;
        n.fin.valid = false;
    }
    // Take at most one scalar result per cycle (lowest ring first).
    let mut sc_done_taken = false;
    for k in 0..NSC {
        let done = q.sc[k].done;
        let kind = done.tag >> 11;
        let ctx = done.tag.resize::<11>();
        // Where the result goes: S to the output stage, which is always free
        // because it lasts one cycle; r and a to the fixed-base stage.
        let target_free = if kind == b16(KIND_CHALLENGE) {
            true
        } else {
            fb_stage_free
        };
        if done.valid && target_free && !sc_done_taken {
            sc_done_taken = true;
            d.sc[k].out_ready = true;
            if kind == b16(KIND_CHALLENGE) {
                // Read R and the user tag now for output next cycle.
                d.mems.r_out.read_addr = ctx.resize::<CB>();
                d.mems.user_tag.read_addr = ctx.resize::<CB>();
                n.fin = FinStage {
                    valid: true,
                    ctx: ctx,
                    s: done.s,
                };
            } else {
                // Keep a for challenge jobs, or store r as this request's
                // challenge addend; either way compute its point next.
                if kind == b16(KIND_KEY) {
                    n.a_digits = done.s;
                } else {
                    d.mems.r_sc.write = RamWrite::<[b17; 15], CB> {
                        addr: ctx.resize::<CB>(),
                        value: done.s,
                        enable: true,
                    };
                }
                n.fb = FbStage {
                    valid: true,
                    tag: done.tag,
                    digits: recode_mixed(done.s),
                };
            }
        }
    }

    // ================= Free-list push =================
    // free_wr runs free_count entries ahead of free_rd (mod 2^CB), and at
    // most 2^CB contexts exist, so a push never overwrites an entry that is
    // still waiting to be read.
    if push_free {
        d.mems.free_list.write = RamWrite::<b11, CB> {
            addr: r.free_wr.resize::<CB>(),
            value: push_ctx,
            enable: true,
        };
        n.free_wr = r.free_wr + b11(1);
        free_count = free_count + b12(1);
    }
    n.free_count = free_count;

    // ================= Fixed-base completions and outputs =================
    // A done pulse frees the context's bit (after any dispatch this cycle,
    // since it updates n). In fused mode the credit is the fixed-base
    // context, so it is returned here.
    for k in 0..NFB {
        let o = q.fb[k];
        if o.done {
            n.fb_free[k] = n.fb_free[k] | (b32(1) << (o.done_ctx.resize::<32>()));
            if NCP == 0 {
                credits = credits + b12(1);
            }
        }
    }
    // ================= Fixed-base outputs =================
    // Fused mode: affine x (its sign) then y go to the output stage.
    // Compress mode: X, Y, Z go to the compress stage, which only takes X
    // when a batch slot is free.
    // The compress stage's registered X acceptance (false without one).
    let mut accept_x = false;
    for c in 0..NCP {
        accept_x = q.cp[c].accept_x;
    }
    // Coordinate forwarded to the compress stage this cycle.
    let mut point = PointIn {
        valid: false,
        tag: b16(0),
        index: b2(0),
        value: Fe17 { d: [b17(0); 15] },
    };
    // At most one machine output per cycle (lowest machine first); a
    // machine whose output is not accepted holds it for a later cycle.
    let mut fb_out_taken = false;
    for k in 0..NFB {
        let o = q.fb[k].out;
        let is_x = o.index == b6(0);
        if NCP == 0 {
            // Fused: x only records its sign, so it is always accepted; y
            // needs the single-entry point stage to be empty.
            if o.valid && !fb_out_taken && (is_x || !r.cpo.valid) {
                fb_out_taken = true;
                d.fb[k].out_accept = true;
                let sign_ctx = o.tag.resize::<11>();
                // x is canonical, so its least significant bit is the sign.
                if is_x {
                    d.mems.xsign.write = RamWrite::<bool, CB> {
                        addr: sign_ctx.resize::<CB>(),
                        value: (o.value.d[0] & b17(1)) != b17(0),
                        enable: true,
                    };
                } else {
                    // y follows its x, so the sign is stored; read it back
                    // for next cycle.
                    d.mems.xsign.read_addr = sign_ctx.resize::<CB>();
                    n.cpo = CpOutStage {
                        valid: true,
                        has_tag: false,
                        tag: o.tag,
                        keep: true,
                        x_negative: false,
                        y: o.value,
                    };
                }
            }
        } else if o.valid && !fb_out_taken && (!is_x || accept_x) {
            // Compress mode: X needs a batch slot; Y and Z are always taken.
            // The credit held since admission guarantees the slot exists.
            fb_out_taken = true;
            d.fb[k].out_accept = true;
            point = PointIn {
                valid: true,
                tag: o.tag,
                index: o.index.resize::<2>(),
                value: o.value,
            };
        }
    }

    // ================= Encoded R -> challenge hash =================
    // The challenge stage can be refilled: empty, or its job was issued to
    // SHA this cycle.
    let h2_free = !r.h2.valid || (sha_taken && h2_ready);
    let mut cpo_done = false;
    if NCP == 0 {
        // Fused: the xsign read issued when y arrived returns now.
        if r.cpo.valid && !r.cpo.has_tag {
            n.cpo.x_negative = q.mems.xsign;
            n.cpo.has_tag = true;
        }
        if r.cpo.valid && r.cpo.has_tag {
            let kind = r.cpo.tag >> 11;
            let ctx = r.cpo.tag.resize::<11>();
            let r_enc = encode_point(r.cpo.y, r.cpo.x_negative);
            if kind == b16(KIND_KEY) {
                // Key expansion ends: [a]B is the public key.
                n.public_key = r_enc;
                n.key_loaded = true;
                n.keygen = false;
                // A cancelled expansion ends here; the key clear below
                // still wipes this cycle's result.
                n.key_cancel = false;
                cpo_done = true;
            } else if h2_free {
                // Store R for the signature and start the challenge hash;
                // the message is read now and lands in h2 next cycle.
                d.mems.r_out.write = RamWrite::<[b64; 4], CB> {
                    addr: ctx.resize::<CB>(),
                    value: r_enc,
                    enable: true,
                };
                n.h2 = H2Stage {
                    valid: true,
                    has_msg: false,
                    ctx: ctx,
                    r_enc: r_enc,
                    msg: Words512 { words: [b64(0); 8] },
                };
                d.mems.msg.read_addr = ctx.resize::<CB>();
                cpo_done = true;
            }
        }
        if cpo_done {
            n.cpo.valid = false;
        }
    }
    // Compress mode: the same hand-off from the compress stage's encoded
    // output. `take` is its out_ready; an untaken encoding stays held.
    for c in 0..NCP {
        let done = q.cp[c].done;
        let mut take = false;
        if done.valid {
            let kind = done.tag >> 11;
            let ctx = done.tag.resize::<11>();
            if kind == b16(KIND_KEY) {
                n.public_key = done.enc;
                n.key_loaded = true;
                n.keygen = false;
                n.key_cancel = false;
                take = true;
            } else if h2_free {
                d.mems.r_out.write = RamWrite::<[b64; 4], CB> {
                    addr: ctx.resize::<CB>(),
                    value: done.enc,
                    enable: true,
                };
                n.h2 = H2Stage {
                    valid: true,
                    has_msg: false,
                    ctx: ctx,
                    r_enc: done.enc,
                    msg: Words512 { words: [b64(0); 8] },
                };
                d.mems.msg.read_addr = ctx.resize::<CB>();
                take = true;
            }
        }
        // The stage sees the registered credits (before this cycle's
        // admission) to decide whether a partial batch may flush, and keeps
        // a margin for the admissions its registered spend lags; its spend
        // and return are applied afterwards.
        d.cp[c] = CompressIn {
            point: point,
            credits: r.credits,
            out_ready: take,
        };
        credits = credits - q.cp[c].credit_spend + q.cp[c].credit_return;
    }
    n.credits = credits;
    // Invariant: credits stay within the pool (at most 2,048). An underflow
    // would wrap the 12-bit count above it. Sticky.
    if credits > b12(2048) {
        n.error = true;
    }

    // ================= Key clear =================
    // Last, so it overrides any key update made above this cycle. A clear
    // during an expansion (running, or starting this cycle) cancels it: the
    // expansion still runs to completion so its contexts and credits come
    // back, but every key value it writes meanwhile is wiped here, and its
    // result is discarded.
    if i.clear_key && (r.keygen || n.keygen) {
        n.key_cancel = true;
    }
    if i.clear_key || r.key_cancel {
        n.key_loaded = false;
        n.prefix = ScalarWords { words: [b64(0); 4] };
        n.a_digits = [b17(0); 15];
        n.public_key = [b64(0); 4];
    }

    d.regs = n;
    // ready and load_key_ready are this cycle's combinational decisions;
    // key_loaded and public_key are the registered values.
    let output = ScalableSignOut {
        load_key_ready: load_key_ready,
        key_loaded: r.key_loaded,
        public_key: ScalarWords {
            words: r.public_key,
        },
        ready: sign_ready,
        valid: out_valid,
        tag: out_tag,
        signature: out_sig,
        internal_error: r.error,
        in_flight: in_flight,
        sha_ext: sha_ext,
    };
    (output, d)
}

/// The one-byte benchmark blocks hash to exactly SHA-512 of the bytes they
/// stand for: `prefix ‖ M` and `R ‖ A ‖ M`, for every one of the 256 values
/// of M and several prefixes, points and keys. Checked with an independent
/// software compression against the `sha2` crate.
#[cfg(all(test, feature = "msg1"))]
mod msg1_tests {
    use super::*;
    use crate::sha_client::tests::{IV, compress};
    use sha2::{Digest, Sha512};

    fn words_from(bytes: [u8; 32]) -> [b64; 4] {
        std::array::from_fn(|k| b64(u128::from(u64::from_le_bytes(bytes[8 * k..8 * k + 8].try_into().unwrap()))))
    }

    fn digest(block: [b64; 16]) -> [u8; 64] {
        let s = compress(IV, block.map(|w| w.raw() as u64));
        let mut out = [0u8; 64];
        for k in 0..8 {
            out[8 * k..8 * k + 8].copy_from_slice(&s[k].to_be_bytes());
        }
        out
    }

    #[test]
    fn every_one_byte_message_hashes_like_sha512() {
        assert!(!challenge_second_pad());
        for key in 0..4u8 {
            let prefix: [u8; 32] = std::array::from_fn(|i| (i as u8).wrapping_mul(37).wrapping_add(key * 61));
            let r_enc: [u8; 32] = std::array::from_fn(|i| (i as u8).wrapping_mul(11) ^ key);
            let a: [u8; 32] = std::array::from_fn(|i| (i as u8).wrapping_mul(7).wrapping_add(key));
            for m in 0..=255u8 {
                let mut msg = Words512 { words: [b64(0); 8] };
                // Upper bytes of the message word must be ignored.
                msg.words[0] = b64(u128::from(m) | 0xdead_beef_0000_0000);
                msg.words[1] = b64(0x1234);
                let nb = nonce_block(ScalarWords { words: words_from(prefix) }, msg);
                let mut want = Sha512::new();
                want.update(prefix);
                want.update([m]);
                assert_eq!(digest(nb)[..], want.finalize()[..], "nonce, key {key}, m {m}");
                let cb = challenge_block(words_from(r_enc), words_from(a), msg);
                let mut want = Sha512::new();
                want.update(r_enc);
                want.update(a);
                want.update([m]);
                assert_eq!(digest(cb)[..], want.finalize()[..], "challenge, key {key}, m {m}");
            }
        }
    }
}