rhdl_sha512_pipelined/

folded.rs

//! A folded SHA-512 core: **S round stages in a ring**, `S / 80` blocks per
//! clock, for lines smaller than one full pipeline.
//!
//! ```text
//!            ┌──────────────────── recirculate (round < 80) ───────────────┐
//!            ▼                                                             │
//!  ShaIn ─▶ [skid] ─▶ mux ─▶ round ─▶ round ─▶ … ─▶ round ──┬─────────────┘
//!                            stage 0  stage 1      stage S−1 └─▶ [final add] ─▶ ShaOut
//!                                                                (round = 80)
//! ```
//!
//! # Why this exists
//!
//! **Problem.** The full [`Sha512Pipeline`](crate::Sha512Pipeline) gives one
//! block per clock for ~43k LUTs. The Ed25519 modules need far less: the
//! default Ed25519 chip hashes about 25M blocks per second, an eighth of a
//! block per clock. Before this core the line came only in whole and half
//! blocks per clock (the half-rate "folded" core was a plan), so most of its
//! LUTs bought nothing, and a line shrunk below ~23k could not be built.
//!
//! **Reasoning.** All 80 rounds are the same step with a different constant.
//! A block does not need 80 stages of its own: it can go round a ring of `S`
//! stages `80 / S` times. Every stage carries the block's round counter, and
//! the constant `K_t` is read from a 128-entry ROM by that counter (a 7-input
//! function per bit, two LUT6 each), so a stage serves any round. The ring
//! holds `S` blocks at once, each for 80 cycles: **`S / 80` blocks per
//! clock**, and the latency stays 82 cycles.
//!
//! **Decision.** One core per stage count `S` that divides 80:
//! [`Sha512Folded2`], [`Sha512Folded4`], [`Sha512Folded5`],
//! [`Sha512Folded8`], [`Sha512Folded10`], [`Sha512Folded16`],
//! [`Sha512Folded20`] and [`Sha512Folded40`] ([`FOLDS`]). `S = 80` would be
//! a full pipeline with a ROM per stage, so the line uses
//! [`Sha512Pipeline`](crate::Sha512Pipeline) there. The cores share one
//! control kernel ([`fold_control`]) and differ only in their ring segment
//! ([`FoldSeg10`] and friends: at most ten children each, every stage wired
//! as one expression, because RHDL lowers array-element writes to
//! whole-array copies).
//! The planner ([`crate::planner`]) builds the line from any mix of folded
//! cores and full pipelines, the fastest that fits the line's LUTs, so the
//! line's rate moves in steps of 1/40 block per clock instead of 1/2.
//!
//! **Status.** Every size is bit-exact against `sha2::compress512` in RHDL
//! simulation at its full rate and under back-pressure, and lowers to
//! Verilog that passes RHDL's syntax check; the 2-, 5- and 10-stage Verilog
//! matches the Rust model cycle by cycle in Icarus (`tests/folded.rs`). Every
//! core routes out of context at 4.878 ns (205 MHz) with positive slack;
//! the planner uses those routed LUTs (`planner::ROUTED_LUT`), and
//! [`folded_lut`] remains the older Yosys estimate.
//!
//! # Ports and flow control
//!
//! The same [`ShaIn`] and [`ShaOut`] as the full pipeline, but with
//! back-pressure: [`ShaCoreOut::ready`] is low while the ring is full. A
//! client presents a block and holds it until `ready` is high in that
//! cycle (a block presented while `ready` is low is ignored).
//!
//! Inside, a one-entry **skid buffer** holds the accepted block until the
//! slot arriving at stage 0 is free. A slot is busy while its block still
//! has rounds to do; it frees the cycle its block finishes round 79, and the
//! buffered block takes it. Blocks finish in the order they entered.
//!
//! # Where to go next
//!
//! | You want to… | Start here |
//! |---|---|
//! | see one stage | [`FoldRound`], [`fold_round_kernel`] |
//! | see the ring and the skid buffer | [`fold_control`] |
//! | change what the planner thinks a fold costs | [`folded_lut`], [`crate::planner`] |

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

use crate::{IV, K, ShaCoreOut, ShaIn, ShaOut, Stage, round_kernel};

/// The round constants padded to 128 entries, so a 7-bit round counter can
/// index them (entries 80–127 are zero and never used).
pub const K128: [b64; 128] = {
    let mut k = [b64(0); 128];
    let mut i = 0;
    while i < 81 {
        k[i] = K[i];
        i += 1;
    }
    k
};

/// Cycles from accepting a block (into the skid buffer) to presenting its
/// result when the ring has room: the buffer, 80 rounds and the output
/// register. The same as the full pipeline's [`LATENCY`](crate::LATENCY).
pub const FOLDED_LATENCY: usize = 82;

/// Estimated LUTs of a core with a ring of `stages` round stages: 1,020 per
/// stage (round, schedule step, constant ROM, counter) plus 3,450 for the
/// skid buffer, the stage-0 mux and the final addition. Fitted to Yosys
/// `synth_xilinx -family xcup` of the 2-, 5- and 10-stage cores (5,491,
/// 8,550 and 13,654 LUTs). An **estimate**: Yosys is not Vivado, and
/// nothing here is placed or timed.
#[must_use]
pub const fn folded_lut(stages: u32) -> u32 {
    1_020 * stages + 3_450
}

/// A block's state between stages, with its round counter.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct FoldStage {
    /// The block's state (valid, tag, chain, working variables, window and
    /// the look-ahead `p`).
    pub stage: Stage,
    /// The round this state performs next (0–79), or 80 when done.
    pub t: b7,
}

/// One registered ring stage: performs round `t` of whatever block arrives.
///
/// Only the valid bit is reset. The 2,136-bit payload is a
/// [`DFF::resetless`] register: it needs no reset (an invalid stage's data
/// is never used), and keeping it off the reset net is what lets the tools
/// meet 205 MHz (DSig's build v5 failed timing with every datapath register
/// on the reset).
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct FoldRound {
    /// A block occupies the stage (reset to empty).
    valid: DFF<bool>,
    /// The block's state (no reset).
    data: DFF<FoldStage>,
}

impl Default for FoldRound {
    fn default() -> Self {
        Self {
            valid: DFF::new(false),
            data: DFF::resetless(),
        }
    }
}

impl SynchronousIO for FoldRound {
    type I = FoldStage;
    type O = FoldStage;
    type Kernel = fold_round_kernel;
}

/// Round `t` with `K_{t+1}` from the ROM for the next round's look-ahead.
#[kernel]
pub fn fold_round_kernel(_cr: ClockReset, input: FoldStage, q: FoldRoundQ) -> (FoldStage, FoldRoundD) {
    let k_next = K128[input.t + b7(1)];
    let mut out = q.data;
    out.stage.valid = q.valid;
    (
        out,
        FoldRoundD {
            valid: input.stage.valid,
            data: FoldStage {
                stage: round_kernel(input.stage, k_next),
                t: input.t + b7(1),
            },
        },
    )
}

/// One ring segment: `$first` takes the segment's input, every later stage
/// the previous one's output, and the segment presents its last stage. Each
/// child is written as one expression (no array element assignments, which
/// RHDL lowers to whole-array copies). Segments of round stages hold at most
/// five: a kernel's child inputs become one Verilog literal (5 × 2,136 bits),
/// and Icarus cannot scan a token over 16 KB, so larger rings are built from
/// segments of segments.
macro_rules! segment {
    ($(#[$meta:meta])* $name:ident, $q:ident, $d:ident, $kernel:ident, $child:ty,
     [$first:ident $(, $field:ident)*], [$($prev:ident),*], $last:ident) => {
        $(#[$meta])*
        #[derive(Clone, Debug, Synchronous, SynchronousDQ, Default)]
        pub struct $name {
            $first: $child,
            $($field: $child,)*
        }

        impl SynchronousIO for $name {
            type I = FoldStage;
            type O = FoldStage;
            type Kernel = $kernel;
        }

        #[doc = concat!("Chain the stages of [`", stringify!($name), "`] in series.")]
        #[kernel]
        pub fn $kernel(_cr: ClockReset, input: FoldStage, q: $q) -> (FoldStage, $d) {
            (q.$last, $d { $first: input, $($field: q.$prev,)* })
        }
    };
}

segment!(
    /// Two ring stages.
    FoldSeg2, FoldSeg2Q, FoldSeg2D, fold_seg2_kernel, FoldRound, [r0, r1], [r0], r1
);
segment!(
    /// Four ring stages.
    FoldSeg4, FoldSeg4Q, FoldSeg4D, fold_seg4_kernel, FoldRound, [r0, r1, r2, r3], [r0, r1, r2], r3
);
segment!(
    /// Five ring stages.
    FoldSeg5, FoldSeg5Q, FoldSeg5D, fold_seg5_kernel, FoldRound, [r0, r1, r2, r3, r4], [r0, r1, r2, r3], r4
);
segment!(
    /// Eight ring stages (two four-stage segments).
    FoldSeg8, FoldSeg8Q, FoldSeg8D, fold_seg8_kernel, FoldSeg4, [a, b], [a], b
);
segment!(
    /// Ten ring stages (two five-stage segments).
    FoldSeg10, FoldSeg10Q, FoldSeg10D, fold_seg10_kernel, FoldSeg5, [a, b], [a], b
);
segment!(
    /// Sixteen ring stages (two eight-stage segments).
    FoldSeg16, FoldSeg16Q, FoldSeg16D, fold_seg16_kernel, FoldSeg8, [a, b], [a], b
);
segment!(
    /// Twenty ring stages (two ten-stage segments).
    FoldSeg20, FoldSeg20Q, FoldSeg20D, fold_seg20_kernel, FoldSeg10, [a, b], [a], b
);
segment!(
    /// Forty ring stages (four ten-stage segments).
    FoldSeg40, FoldSeg40Q, FoldSeg40D, fold_seg40_kernel, FoldSeg10, [a, b, c, d], [a, b, c], d
);

/// What the ring control decides in one cycle.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct FoldControl {
    /// The core's outputs (`ready` and the finished block).
    pub out: ShaCoreOut,
    /// The skid buffer's next value.
    pub skid: FoldStage,
    /// What enters stage 0.
    pub first: FoldStage,
    /// The output register's next value.
    pub done: ShaOut,
}

/// The ring control, the same for every stage count. `leaving` is the state
/// leaving the last stage this cycle: it recirculates into stage 0 while it
/// has rounds left, and is added to its chaining value when it has done
/// round 79. A free slot takes the buffered block; the buffer takes the
/// client's block when it is empty or being placed (`ready`).
#[kernel]
pub fn fold_control(cr: ClockReset, input: ShaIn, skid: FoldStage, leaving: FoldStage, out: ShaOut) -> FoldControl {
    let resetting = cr.reset.any();
    let busy = leaving.stage.valid && leaving.t != b7(80);
    let finished = leaving.stage.valid && leaving.t == b7(80);
    // Stage 0 takes the recirculating block, else the buffered one.
    let admit = skid.stage.valid && !busy;
    let mut first = skid;
    if busy {
        first = leaving;
    }
    first.stage.valid = (busy || admit) && !resetting;
    // The buffer keeps a block it could not place; otherwise it takes the
    // client's (if any).
    let keep = skid.stage.valid && !admit;
    let chain = if input.use_iv { IV } else { input.chain };
    let entering = FoldStage {
        stage: Stage {
            valid: input.valid && !resetting,
            tag: input.tag,
            chain,
            work: chain,
            w: input.block,
            p: chain[7] + K[0] + input.block[0],
        },
        t: b7(0),
    };
    let mut next_skid = entering;
    if keep {
        next_skid = skid;
    }
    next_skid.stage.valid = next_skid.stage.valid && !resetting;
    // The feed-forward addition for a finished block.
    let last = leaving.stage;
    let state = [
        last.chain[0] + last.work[0],
        last.chain[1] + last.work[1],
        last.chain[2] + last.work[2],
        last.chain[3] + last.work[3],
        last.chain[4] + last.work[4],
        last.chain[5] + last.work[5],
        last.chain[6] + last.work[6],
        last.chain[7] + last.work[7],
    ];
    FoldControl {
        out: ShaCoreOut {
            ready: !keep && !resetting,
            done: out,
        },
        skid: next_skid,
        first,
        done: ShaOut {
            valid: finished && !resetting,
            tag: last.tag,
            state,
        },
    }
}

/// A folded core: the skid buffer, one ring segment and the output register.
macro_rules! folded_core {
    ($(#[$meta:meta])* $name:ident, $q:ident, $d:ident, $kernel:ident, $seg:ty, $stages:expr) => {
        $(#[$meta])*
        #[derive(Clone, Debug, Synchronous, SynchronousDQ)]
        pub struct $name {
            // Valid bits reset; payloads do not (see `FoldRound`).
            skid_valid: DFF<bool>,
            skid: DFF<FoldStage>,
            ring: $seg,
            out_valid: DFF<bool>,
            out: DFF<ShaOut>,
        }

        impl $name {
            /// Ring stages: the core finishes this many blocks every 80
            /// cycles.
            pub const STAGES: u32 = $stages;
        }

        impl Default for $name {
            fn default() -> Self {
                Self {
                    skid_valid: DFF::new(false),
                    skid: DFF::resetless(),
                    ring: <$seg>::default(),
                    out_valid: DFF::new(false),
                    out: DFF::resetless(),
                }
            }
        }

        impl SynchronousIO for $name {
            type I = ShaIn;
            type O = ShaCoreOut;
            type Kernel = $kernel;
        }

        #[doc = concat!("The ring control around [`", stringify!($name), "`]'s segment.")]
        #[kernel]
        pub fn $kernel(cr: ClockReset, input: ShaIn, q: $q) -> (ShaCoreOut, $d) {
            let mut skid = q.skid;
            skid.stage.valid = q.skid_valid;
            let mut out = q.out;
            out.valid = q.out_valid;
            let c = fold_control(cr, input, skid, q.ring, out);
            (
                c.out,
                $d {
                    skid_valid: c.skid.stage.valid,
                    skid: c.skid,
                    ring: c.first,
                    out_valid: c.done.valid,
                    out: c.done,
                },
            )
        }
    };
}

folded_core!(
    /// 2 stages: 1/40 block per clock.
    Sha512Folded2, Sha512Folded2Q, Sha512Folded2D, sha512_folded2_kernel, FoldSeg2, 2
);
folded_core!(
    /// 4 stages: 1/20 block per clock.
    Sha512Folded4, Sha512Folded4Q, Sha512Folded4D, sha512_folded4_kernel, FoldSeg4, 4
);
folded_core!(
    /// 5 stages: 1/16 block per clock.
    Sha512Folded5, Sha512Folded5Q, Sha512Folded5D, sha512_folded5_kernel, FoldSeg5, 5
);
folded_core!(
    /// 8 stages: 1/10 block per clock.
    Sha512Folded8, Sha512Folded8Q, Sha512Folded8D, sha512_folded8_kernel, FoldSeg8, 8
);
folded_core!(
    /// 10 stages: 1/8 block per clock.
    Sha512Folded10, Sha512Folded10Q, Sha512Folded10D, sha512_folded10_kernel, FoldSeg10, 10
);
folded_core!(
    /// 16 stages: 1/5 block per clock.
    Sha512Folded16, Sha512Folded16Q, Sha512Folded16D, sha512_folded16_kernel, FoldSeg16, 16
);
folded_core!(
    /// 20 stages: 1/4 block per clock.
    Sha512Folded20, Sha512Folded20Q, Sha512Folded20D, sha512_folded20_kernel, FoldSeg20, 20
);
folded_core!(
    /// 40 stages: 1/2 block per clock.
    Sha512Folded40, Sha512Folded40Q, Sha512Folded40D, sha512_folded40_kernel, FoldSeg40, 40
);

/// Ring stage counts that have a core, smallest first.
pub const FOLDS: [u32; 8] = [2, 4, 5, 8, 10, 16, 20, 40];