rhdl_ed25519_scalable_core/

sha_ring.rs

//! Three-context interleaved SHA-512 ring.
//!
//! One SHA-512 round is split into three registered stages, and three
//! independent compression contexts circulate through them, so the round
//! logic completes one round every cycle (one block per ~80 cycles). A
//! single-context three-phase unit would finish one round every three
//! cycles; the ring triples throughput for the same round datapath.
//!
//! The message schedule is a 16-word shift register with fixed taps, so no
//! word is ever selected by a dynamic index. A job may request a second,
//! constant padding block (used for the 128-byte challenge `R || A || M`).
//!
//! # Stages
//!
//! ```text
//!   x ──A──> y ──B──> z ──C──> x
//! ```
//!
//! - **A** reads context `x` and forms the round's partial sums
//!   (`h + K[t] + W[t]`, `Σ1(e) + Ch`, `Σ0(a) + Maj`) and the two halves of
//!   the next schedule word.
//! - **B** adds them into `T1`, `T2` and `W[t+16]`.
//! - **C** commits the round to the working variables and shifts the
//!   schedule. After round 79 it adds the chaining value (feed-forward) and
//!   then starts the padding block, emits the digest, or parks.
//!
//! Each stage boundary is a register, so a context completes a round every
//! three cycles and each adder chain is at most two 64-bit additions deep.
//!
//! # Output and parking
//!
//! A finished digest goes to a single output register that the consumer
//! drains with `out_ready`. If that register is full when a context
//! finishes, the context *parks*: it keeps its slot in the ring, does no more
//! rounds, and retries each time it passes stage C. A parked context blocks
//! its slot, so a slow consumer throttles admission instead of losing a
//! digest.

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

use crate::digest::{big_sigma0, big_sigma1, round_constant, small_sigma0, small_sigma1};

/// Compression job: one message of one block, or of exactly 128 bytes.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ShaJob {
    /// A job is presented this cycle.
    pub valid: bool,
    /// Opaque tag returned with the digest. Callers pack routing data into
    /// it (for example a context number and key slot).
    pub tag: b16,
    /// Big-endian message words of the first block (already padded if final).
    /// The job starts from the SHA-512 IV.
    pub block: [b64; 16],
    /// Follow with the constant padding block of a 128-byte message
    /// ([`pad_block_128`]); `block` then holds the full 128 message bytes.
    pub second_pad: bool,
}

/// Completed digest; held until `out_ready`.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ShaDone {
    /// A digest is presented this cycle.
    pub valid: bool,
    /// Job tag, as given in [`ShaJob::tag`].
    pub tag: b16,
    /// Final chaining state `H0..H7` (big-endian words); see
    /// [`digest_words`](crate::digest::digest_words) for the byte string.
    pub state: [b64; 8],
}

/// Ring inputs.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ShaRingIn {
    /// New job; accepted when [`ShaRingOut::ready`] in the same cycle.
    pub job: ShaJob,
    /// Consumer accepts [`ShaRingOut::done`] this cycle.
    pub out_ready: bool,
}

/// Ring outputs.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct ShaRingOut {
    /// A job may be presented this cycle: the slot leaving stage C is empty
    /// or retires now. Depends only on registers.
    pub ready: bool,
    /// Completed digest, from the output register.
    pub done: ShaDone,
}

/// One compression context as it travels around the ring.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct ShaCtx {
    /// The slot holds a job.
    valid: bool,
    /// The job has finished but the output register was full; the context
    /// does no rounds and `chain` holds the final state.
    parked: bool,
    /// The constant padding block still follows the current block.
    second_pad: bool,
    /// Job tag.
    tag: b16,
    /// Round `t` (0..80) this context performs on its next pass.
    round: b7,
    /// Chaining value at the start of the current block (the IV, or the
    /// first block's result), added back after round 79.
    chain: [b64; 8],
    /// Working variables `a..h`.
    work: [b64; 8],
    /// Message-schedule window: `w[j]` is `W[t + j]`, so `w[0]` is the
    /// current round's word.
    w: [b64; 16],
}

/// Registers of [`ShaRing`]: one context per stage plus the values each
/// stage hands to the next.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct ShaRingRegs {
    /// Context entering stage A.
    x: ShaCtx,
    /// Context entering stage B.
    y: ShaCtx,
    /// `h + K[t] + W[t]` of context `y`.
    y_hk: b64,
    /// `Σ1(e) + Ch(e, f, g)` of context `y`.
    y_sig1ch: b64,
    /// `Σ0(a) + Maj(a, b, c)` of context `y` (all of `T2`).
    y_sig0maj: b64,
    /// `σ1(W[t+14]) + W[t+9]`, first half of `W[t+16]`.
    y_sa: b64,
    /// `σ0(W[t+1]) + W[t]`, second half of `W[t+16]`.
    y_sb: b64,
    /// Context entering stage C.
    z: ShaCtx,
    /// `T1` of context `z`.
    z_t1: b64,
    /// `T2` of context `z`.
    z_t2: b64,
    /// `W[t+16]` of context `z`.
    z_wnew: b64,
    /// Stage C's context is empty (registered in stage B, so `ready` is a
    /// function of registers and one LUT).
    z_empty: bool,
    /// Stage C's context finishes its last block this pass (round 79, no
    /// padding block to follow).
    z_last: bool,
    /// Stage C's context is parked.
    z_parked: bool,
    /// Output register.
    done: ShaDone,
}

/// An empty ring slot (reset value of every stage).
fn empty_ctx() -> ShaCtx {
    ShaCtx {
        valid: false,
        parked: false,
        second_pad: false,
        tag: b16(0),
        round: b7(0),
        chain: [b64(0); 8],
        work: [b64(0); 8],
        w: [b64(0); 16],
    }
}

/// Interleaved SHA-512 compression ring.
///
/// Throughput is one block per about 80 cycles across the three contexts. A
/// one-block job takes about 240 cycles (80 rounds of three cycles), a
/// two-block job about 480.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
#[rhdl(dq_no_prefix)]
pub struct ShaRing {
    /// All ring state; the ring has no memories.
    regs: DFF<ShaRingRegs>,
}

/// Reset state: three empty slots and an empty output register.
impl Default for ShaRing {
    /// Builds the reset state.
    fn default() -> Self {
        Self {
            regs: DFF::new(ShaRingRegs {
                x: empty_ctx(),
                y: empty_ctx(),
                y_hk: b64(0),
                y_sig1ch: b64(0),
                y_sig0maj: b64(0),
                y_sa: b64(0),
                y_sb: b64(0),
                z: empty_ctx(),
                z_t1: b64(0),
                z_t2: b64(0),
                z_empty: true,
                z_last: false,
                z_parked: false,
                z_wnew: b64(0),
                done: ShaDone {
                    valid: false,
                    tag: b16(0),
                    state: [b64(0); 8],
                },
            }),
        }
    }
}

/// Ports and kernel of [`ShaRing`].
impl SynchronousIO for ShaRing {
    /// Input port bundle.
    type I = ShaRingIn;
    /// Output port bundle.
    type O = ShaRingOut;
    /// Kernel computing the outputs and the next state.
    type Kernel = sha_ring_kernel;
}

/// SHA-512 initial chaining value `H(0)` (FIPS 180-4 section 5.3.5).
#[kernel]
pub fn sha512_iv() -> [b64; 8] {
    [
        b64(0x6a09e667f3bcc908),
        b64(0xbb67ae8584caa73b),
        b64(0x3c6ef372fe94f82b),
        b64(0xa54ff53a5f1d36f1),
        b64(0x510e527fade682d1),
        b64(0x9b05688c2b3e6c1f),
        b64(0x1f83d9abfb41bd6b),
        b64(0x5be0cd19137e2179),
    ]
}

/// Padding block that ends a message of exactly 128 bytes.
///
/// A 128-byte message fills its first block, so the `0x80` terminator and
/// the 128-bit length field go into a second block that is the same for
/// every such message.
#[kernel]
pub fn pad_block_128() -> [b64; 16] {
    let mut block = [b64(0); 16];
    // The single `1` bit that follows the message.
    block[0] = b64(0x8000000000000000);
    // Message length in bits: 128 * 8 = 1024.
    block[15] = b64(0x400);
    block
}

/// State transition for [`ShaRing`].
///
/// All three stages run every cycle on the three contexts `x`, `y`, `z`;
/// stage C's result becomes the next `x`, or a new job takes its place.
#[kernel]
pub fn sha_ring_kernel(_cr: ClockReset, i: ShaRingIn, q: Q) -> (ShaRingOut, D) {
    // `r` is this cycle's registers, `n` the next cycle's.
    let r = q.regs;
    let mut n = r;

    // Output register handshake. A completion enters only an empty output
    // register, so `ready` never depends combinationally on `out_ready`.
    let done_free = !r.done.valid;
    if i.out_ready {
        n.done.valid = false;
    }

    // Stage A: partial sums for round t of context x. They are formed for an
    // empty or parked context too; stage C ignores them.
    let x = r.x;
    let a = x.work[0];
    let b = x.work[1];
    let c = x.work[2];
    let e = x.work[4];
    let f = x.work[5];
    let g = x.work[6];
    n.y = x;
    // h + K[t] + W[t]: the part of T1 that does not depend on e.
    n.y_hk = x.work[7] + round_constant(x.round) + x.w[0];
    // Ch(e, f, g) picks f where e is 1 and g where e is 0.
    n.y_sig1ch = big_sigma1(e) + ((e & f) ^ ((!e) & g));
    // Maj(a, b, c) is the bitwise majority.
    n.y_sig0maj = big_sigma0(a) + ((a & b) ^ (a & c) ^ (b & c));
    // W[t+16] = σ1(W[t+14]) + W[t+9] + σ0(W[t+1]) + W[t], split in two sums.
    // The word is computed every round; after round 63 it is never used.
    n.y_sa = small_sigma1(x.w[14]) + x.w[9];
    n.y_sb = small_sigma0(x.w[1]) + x.w[0];

    // Stage B: finish T1 and W[t+16]; T2 is complete already.
    n.z = r.y;
    // What stage C will decide about r.y, registered here so the ring's
    // `ready` comes straight from flip-flops. (Until 2026-10-17 `ready` was
    // decoded from z.round in stage C; in DSig's v9 routed chip that round
    // bit drove the signer's ready and DSig's capture logic, -3.3 ns.)
    n.z_empty = !r.y.valid;
    n.z_last = r.y.valid && !r.y.parked && r.y.round == b7(79) && !r.y.second_pad;
    n.z_parked = r.y.valid && r.y.parked;
    n.z_t1 = r.y_hk + r.y_sig1ch;
    n.z_t2 = r.y_sig0maj;
    n.z_wnew = r.y_sa + r.y_sb;

    // Stage C: commit the round; finish, chain, park, or retire.
    let z = r.z;
    let t1 = r.z_t1;
    // The context that will be in stage A next cycle (unless a new job
    // replaces it).
    let mut next = z;
    if z.valid && !z.parked {
        // a' = T1 + T2, e' = d + T1; the others shift down by one.
        next.work = [
            t1 + r.z_t2,
            z.work[0],
            z.work[1],
            z.work[2],
            z.work[3] + t1,
            z.work[4],
            z.work[5],
            z.work[6],
        ];
        // Slide the schedule window by one word: fixed taps, no indexing.
        for k in 0..15 {
            next.w[k] = z.w[k + 1];
        }
        next.w[15] = r.z_wnew;
        next.round = z.round + b7(1);
        if z.round == b7(79) {
            // Last round of the block: feed-forward of the chaining value.
            let mut state = [b64(0); 8];
            for k in 0..8 {
                state[k] = z.chain[k] + next.work[k];
            }
            if z.second_pad {
                // Second block: chain from the first block's result and
                // compress the constant padding block in the same slot.
                next.chain = state;
                next.work = state;
                next.w = pad_block_128();
                next.round = b7(0);
                next.second_pad = false;
            } else if done_free {
                // Output register empty: emit the digest and free the slot.
                n.done = ShaDone {
                    valid: true,
                    tag: z.tag,
                    state: state,
                };
            } else {
                // Output register full: keep the digest in `chain` and park.
                next.chain = state;
                next.parked = true;
            }
        }
    } else if z.valid && z.parked && done_free {
        // A parked context passes stage C and finds the output register
        // empty: emit its digest now.
        n.done = ShaDone {
            valid: true,
            tag: z.tag,
            state: z.chain,
        };
    }
    // The slot passing stage C is empty or retires now, so a new job may take
    // it. This is also `ready`: empty, or emitting its digest this cycle, from the
    // flags registered in stage B and the output register.
    let slot_free = r.z_empty || ((r.z_last || r.z_parked) && done_free);
    if slot_free {
        next.valid = false;
        if i.job.valid {
            // A new job enters stage A at round 0 from the IV.
            next = ShaCtx {
                valid: true,
                parked: false,
                second_pad: i.job.second_pad,
                tag: i.job.tag,
                round: b7(0),
                chain: sha512_iv(),
                work: sha512_iv(),
                w: i.job.block,
            };
        }
    }
    n.x = next;
    let out = ShaRingOut {
        ready: slot_free,
        done: r.done,
    };
    (out, D { regs: n })
}

/// Cycle tests of [`ShaRing`] against the `sha2` crate.
#[cfg(test)]
mod tests {
    use super::*;
    use crate::simulation::CycleSim;
    use sha2::{Digest, Sha512};

    /// Standard SHA-512 padding of `message` split into big-endian blocks.
    fn padded_blocks(message: &[u8]) -> Vec<[b64; 16]> {
        let mut bytes = message.to_vec();
        bytes.push(0x80);
        while bytes.len() % 128 != 112 {
            bytes.push(0);
        }
        bytes.extend_from_slice(&((message.len() as u128) * 8).to_be_bytes());
        bytes
            .chunks(128)
            .map(|chunk| {
                std::array::from_fn(|k| {
                    b64(u64::from_be_bytes(chunk[k * 8..k * 8 + 8].try_into().unwrap()) as u128)
                })
            })
            .collect()
    }

    /// Digests match `sha2` for one- and two-block messages while the
    /// consumer stalls, so contexts park; every tag arrives exactly once.
    #[test]
    fn ring_matches_sha2_with_backpressure() {
        // Messages of 32, 96 (one block) and 128 bytes (second constant block).
        let messages: Vec<Vec<u8>> = (0..12)
            .map(|k| {
                let len = [32, 96, 128][k % 3];
                (0..len).map(|i| (i * 7 + k * 13) as u8).collect()
            })
            .collect();
        let mut sim = CycleSim::new(ShaRing::default());
        let mut next = 0;
        let mut done = vec![None; messages.len()];
        let mut out = sim.tick(ShaRingIn {
            job: ShaJob {
                valid: false,
                tag: b16(0),
                block: [b64(0); 16],
                second_pad: false,
            },
            out_ready: false,
        });
        for cycle in 0..20_000 {
            let mut job = ShaJob {
                valid: false,
                tag: b16(0),
                block: [b64(0); 16],
                second_pad: false,
            };
            if out.ready && next < messages.len() {
                let blocks = padded_blocks(&messages[next]);
                job = ShaJob {
                    valid: true,
                    tag: b16(next as u128),
                    block: blocks[0],
                    second_pad: blocks.len() == 2,
                };
                next += 1;
            }
            // Stall the consumer two cycles out of three.
            let out_ready = cycle % 3 == 0;
            if out.done.valid && out_ready {
                let tag = out.done.tag.raw() as usize;
                assert!(done[tag].is_none());
                done[tag] = Some(out.done.state);
            }
            out = sim.tick(ShaRingIn { job, out_ready });
        }
        for (k, m) in messages.iter().enumerate() {
            let want = Sha512::digest(m);
            let got = done[k].expect("digest missing");
            let bytes: Vec<u8> = got
                .iter()
                .flat_map(|w| (w.raw() as u64).to_be_bytes())
                .collect();
            assert_eq!(bytes.as_slice(), want.as_slice(), "message {k}");
        }
    }

    /// With a consumer that never stalls and a job offered whenever `ready`,
    /// the ring completes about one block per 80 cycles.
    #[test]
    fn ring_issues_one_round_per_cycle() {
        let block = padded_blocks(&[0u8; 32])[0];
        let mut sim = CycleSim::new(ShaRing::default());
        let mut accepted = 0;
        let mut completed = 0;
        let mut out = sim.tick(ShaRingIn {
            job: ShaJob {
                valid: false,
                tag: b16(0),
                block,
                second_pad: false,
            },
            out_ready: true,
        });
        let cycles = 3000;
        for _ in 0..cycles {
            let valid = out.ready;
            accepted += usize::from(valid);
            out = sim.tick(ShaRingIn {
                job: ShaJob {
                    valid,
                    tag: b16(0),
                    block,
                    second_pad: false,
                },
                out_ready: true,
            });
            completed += usize::from(out.done.valid);
        }
        // Three contexts, 80 rounds each, three cycles per round: 3 blocks / 240 cycles.
        assert!(completed * 81 >= cycles - 300, "completed {completed} of {accepted}");
    }
}