rhdl_sha512_pipelined/

lib.rs

//! A fully unrolled, fully pipelined SHA-512 compression function in RHDL:
//! **one 128-byte block per clock**, shared by DSig and Ed25519.
//!
//! # Building for Wolverine's U280
//!
//! This crate is a reusable RHDL compression pipeline, not a standalone XRT
//! card kernel. `cargo build --locked -p rhdl_sha512_pipelined` builds its Rust
//! library; it does not produce a `.xclbin`. Include the pipeline in an enclosing
//! kernel and generate that kernel's RTL before packaging and linking with
//! Vivado/Vitis 2023.2 for the installed U280 platform.
//!
//! For the existing card flows, follow the front-page instructions for
//! [Ed25519](../rhdl_ed25519_scalable_core/index.html#building-for-wolverines-u280)
//! or [DSig](../rhdl_dsig_scalable_core/index.html#building-for-wolverines-u280).
//! Resource and timing acceptance belongs to the complete routed kernel.
//!
//! Run commands from the workspace root. Before compilation or RTL generation,
//! record ownership in `PROJECT_COORDINATION.md` and
//! `/home/sahasta/Development/FPGA_COORDINATION.md`, and use the applicable
//! nonblocking `local-heavy.lock`; `crates/ed25519/tools/bounded.sh` wraps local
//! Cargo commands with that lock and resource limits. Reserve Wolverine builds
//! in both ledgers too, then use `crates/dsig/tools/with-u280-lock.sh` to hold
//! `u280.lock`. Do not bypass a busy lock.
//!
//! ```text
//!   ShaIn ──▶ [input] ──▶ g0 ─▶ g1 ─▶ … ─▶ g7 ──▶ [final add] ──▶ ShaOut
//!             p₀ = h+K₀+W₀    (8 groups × 10 round stages = 80 rounds)
//! ```
//!
//! Every SHA-512 round has its own pipeline stage, so a new block can enter
//! every cycle and leaves [`LATENCY`] cycles later. There is no back-pressure:
//! [`ShaCoreOut::ready`] is always high and the output must be taken when it
//! appears (clients keep a credit counter; see the Ed25519 crate's
//! `CompressStage` for the pattern).
//!
//! # Why this crate exists
//!
//! **Problem.** Ed25519 hashes with SHA-512: three blocks per signature and
//! two per verification. Its first design gave each module a small private
//! SHA ring that needs many cycles per block. Eleven such rings cost about
//! 50k LUTs and still ran slowly.
//!
//! **Reasoning.** SHA-512 is 80 rounds of the same simple step. Unrolling
//! every round into its own pipeline stage costs more LUTs in one place, but
//! then a single unit finishes a block every clock. One fast unit, shared
//! by every client, beats many slow private ones.
//!
//! **Decision.** One fully pipelined core, on its own *SHA line* whose
//! allowance comes out of the chip budget. Lines that need less than a
//! block per clock use [`folded`] cores instead (rings of 2–40 stages, 1/40
//! to ½ block per clock), and the planner sizes the line to what the chip
//! wants by default (a manual line is 65,000 LUTs and 20 DSPs by default; the 100 % budget of 485k LUTs and
//! 4,520 DSPs is the engines' 420k / 4,500 plus this default). Ed25519 signing and verification share it through an arbiter.
//! DSig's SHA-512 chain profile (`DSIG_CHAIN=sha512` in
//! `rhdl_dsig_scalable_core`) instantiates its own copies inside its slices,
//! because each slice needs three blocks per clock.
//!
//! **Status.** Bit-exact against `sha2` in simulation at full rate. The LUT
//! cost (about 43,200 for one core) is an **estimate** until synthesized.
//!
//! # Making one round fit one clock
//!
//! A round is
//!
//! ```text
//! T1 = h + Σ1(e) + Ch(e, f, g) + K_t + W_t        T2 = Σ0(a) + Maj(a, b, c)
//! a' = T1 + T2                                    e' = d + T1
//! ```
//!
//! Five operands feed `T1`. Three of them, `h + K_t + W_t`, are known one
//! round early: `h` of round `t` is `g` of round `t − 1`, `K_t` is a constant
//! and `W_t` is already in the message window. So each stage also computes
//! `p = g + K_{t+1} + W_{t+1}` for the *next* stage ([`Stage::p`]), and the
//! critical path of a round is only `p + Σ1(e) + Ch` followed by one more add.
//!
//! The message schedule is a 16-word window that shifts one word per round;
//! word `t + 16` is computed in the stage that consumes word `t`. Constant
//! inputs (for example DSig's zero-padded chain blocks) and unused late
//! schedule words are removed by synthesis.
//!
//! # Ports
//!
//! [`ShaIn`]: `valid`, a 16-bit `tag`, the block as 16 big-endian 64-bit
//! words, and the chaining value: the standard IV when `use_iv`, else `chain`
//! (so a multi-block message is resubmitted block by block). [`ShaOut`]: the
//! new chaining value `chain + compress(chain, block)` and the tag, in order.
//!
//! # Validation
//!
//! `tests/compress.rs` compares every output with `sha2::compress512` on random
//! blocks, chained two-block messages, and a block every cycle (full rate),
//! and checks [`LATENCY`].
//!
//! # Where to go next
//!
//! | You want to… | Start here |
//! |---|---|
//! | understand one round | [`round_kernel`], then [`Stage`] |
//! | see how rounds become a pipeline | [`RoundGroup`], [`Sha512Pipeline`] |
//! | change the line's size in the planner | [`planner`] (feature `planner`) |
//! | share the core between clients | the Ed25519 crate's `sha_client` (arbiter) |
//! | hash DSig chain steps with it | `rhdl_dsig_scalable_core::chain_lane` |
//! | build a line smaller than one block per clock | [`folded`]: rings of 2–40 stages, 1/40 to 1/2 block per clock |
//! | reach above one block per clock | open problem: a fixed-length single-block variant, DSP adders |
#![forbid(unsafe_code)]

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

pub mod folded;
#[cfg(feature = "planner")]
pub mod planner;

/// Cycles from accepting a block to presenting its result: one input
/// register, 80 round stages and one output register (the final addition).
pub const LATENCY: usize = 82;

/// SHA-512 initial chaining value.
pub const IV: [b64; 8] = [
    b64(0x6a09e667f3bcc908),
    b64(0xbb67ae8584caa73b),
    b64(0x3c6ef372fe94f82b),
    b64(0xa54ff53a5f1d36f1),
    b64(0x510e527fade682d1),
    b64(0x9b05688c2b3e6c1f),
    b64(0x1f83d9abfb41bd6b),
    b64(0x5be0cd19137e2179),
];

/// Round constants `K_0..K_79`, plus a zero `K_80` so the last stage's
/// look-ahead has something to read.
pub const K: [b64; 81] = [
    b64(0x428a2f98d728ae22), b64(0x7137449123ef65cd), b64(0xb5c0fbcfec4d3b2f), b64(0xe9b5dba58189dbbc),
    b64(0x3956c25bf348b538), b64(0x59f111f1b605d019), b64(0x923f82a4af194f9b), b64(0xab1c5ed5da6d8118),
    b64(0xd807aa98a3030242), b64(0x12835b0145706fbe), b64(0x243185be4ee4b28c), b64(0x550c7dc3d5ffb4e2),
    b64(0x72be5d74f27b896f), b64(0x80deb1fe3b1696b1), b64(0x9bdc06a725c71235), b64(0xc19bf174cf692694),
    b64(0xe49b69c19ef14ad2), b64(0xefbe4786384f25e3), b64(0x0fc19dc68b8cd5b5), b64(0x240ca1cc77ac9c65),
    b64(0x2de92c6f592b0275), b64(0x4a7484aa6ea6e483), b64(0x5cb0a9dcbd41fbd4), b64(0x76f988da831153b5),
    b64(0x983e5152ee66dfab), b64(0xa831c66d2db43210), b64(0xb00327c898fb213f), b64(0xbf597fc7beef0ee4),
    b64(0xc6e00bf33da88fc2), b64(0xd5a79147930aa725), b64(0x06ca6351e003826f), b64(0x142929670a0e6e70),
    b64(0x27b70a8546d22ffc), b64(0x2e1b21385c26c926), b64(0x4d2c6dfc5ac42aed), b64(0x53380d139d95b3df),
    b64(0x650a73548baf63de), b64(0x766a0abb3c77b2a8), b64(0x81c2c92e47edaee6), b64(0x92722c851482353b),
    b64(0xa2bfe8a14cf10364), b64(0xa81a664bbc423001), b64(0xc24b8b70d0f89791), b64(0xc76c51a30654be30),
    b64(0xd192e819d6ef5218), b64(0xd69906245565a910), b64(0xf40e35855771202a), b64(0x106aa07032bbd1b8),
    b64(0x19a4c116b8d2d0c8), b64(0x1e376c085141ab53), b64(0x2748774cdf8eeb99), b64(0x34b0bcb5e19b48a8),
    b64(0x391c0cb3c5c95a63), b64(0x4ed8aa4ae3418acb), b64(0x5b9cca4f7763e373), b64(0x682e6ff3d6b2b8a3),
    b64(0x748f82ee5defb2fc), b64(0x78a5636f43172f60), b64(0x84c87814a1f0ab72), b64(0x8cc702081a6439ec),
    b64(0x90befffa23631e28), b64(0xa4506cebde82bde9), b64(0xbef9a3f7b2c67915), b64(0xc67178f2e372532b),
    b64(0xca273eceea26619c), b64(0xd186b8c721c0c207), b64(0xeada7dd6cde0eb1e), b64(0xf57d4f7fee6ed178),
    b64(0x06f067aa72176fba), b64(0x0a637dc5a2c898a6), b64(0x113f9804bef90dae), b64(0x1b710b35131c471b),
    b64(0x28db77f523047d84), b64(0x32caab7b40c72493), b64(0x3c9ebe0a15c9bebc), b64(0x431d67c49c100d4c),
    b64(0x4cc5d4becb3e42b6), b64(0x597f299cfc657e2a), b64(0x5fcb6fab3ad6faec), b64(0x6c44198c4a475817),
    b64(0),
];

/// One block request.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct ShaIn {
    /// A block is presented this cycle (always accepted).
    pub valid: bool,
    /// Returned unchanged with the result.
    pub tag: b16,
    /// The 128-byte block as 16 big-endian words.
    pub block: [b64; 16],
    /// Start from the standard [`IV`] instead of `chain`.
    pub use_iv: bool,
    /// Chaining value when `use_iv` is low.
    pub chain: [b64; 8],
}

/// One finished block.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct ShaOut {
    /// Present this cycle (must be taken; there is no back-pressure).
    pub valid: bool,
    /// The request's tag.
    pub tag: b16,
    /// New chaining value (the digest after the final block).
    pub state: [b64; 8],
}

/// Core outputs.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct ShaCoreOut {
    /// A request is accepted this cycle (always true for this core).
    pub ready: bool,
    /// The block that entered [`LATENCY`] cycles ago.
    pub done: ShaOut,
}

/// The state carried between round stages.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct Stage {
    /// A block occupies this stage.
    pub valid: bool,
    /// Its tag.
    pub tag: b16,
    /// The chaining value, kept for the final addition.
    pub chain: [b64; 8],
    /// Working variables `a..h`.
    pub work: [b64; 8],
    /// Message window: `w[0]` is this round's `W_t`.
    pub w: [b64; 16],
    /// `h + K_t + W_t` for this round, computed by the previous stage.
    pub p: b64,
}

/// `Σ0(a) = rotr(a,28) ^ rotr(a,34) ^ rotr(a,39)`.
#[kernel]
pub fn big_sigma0(a: b64) -> b64 {
    ((a >> 28) | (a << 36)) ^ ((a >> 34) | (a << 30)) ^ ((a >> 39) | (a << 25))
}

/// `Σ1(e) = rotr(e,14) ^ rotr(e,18) ^ rotr(e,41)`.
#[kernel]
pub fn big_sigma1(e: b64) -> b64 {
    ((e >> 14) | (e << 50)) ^ ((e >> 18) | (e << 46)) ^ ((e >> 41) | (e << 23))
}

/// `σ0(x) = rotr(x,1) ^ rotr(x,8) ^ (x >> 7)`.
#[kernel]
pub fn small_sigma0(x: b64) -> b64 {
    ((x >> 1) | (x << 63)) ^ ((x >> 8) | (x << 56)) ^ (x >> 7)
}

/// `σ1(x) = rotr(x,19) ^ rotr(x,61) ^ (x >> 6)`.
#[kernel]
pub fn small_sigma1(x: b64) -> b64 {
    ((x >> 19) | (x << 45)) ^ ((x >> 61) | (x << 3)) ^ (x >> 6)
}

/// One SHA-512 round on `s`, plus the look-ahead `p` for the next round
/// (whose constant is `k_next`).
#[kernel]
pub fn round_kernel(s: Stage, k_next: b64) -> Stage {
    // The eight working variables, named as in FIPS 180-4. `h` is not
    // needed here: it already sits inside `s.p = h + K_t + W_t`.
    let a = s.work[0];
    let b = s.work[1];
    let c = s.work[2];
    let d = s.work[3];
    let e = s.work[4];
    let f = s.work[5];
    let g = s.work[6];
    // "Choose": each bit of e picks f (1) or g (0).
    let ch = (e & f) ^ (!e & g);
    // "Majority": each bit is the majority of a, b and c.
    let maj = (a & b) ^ (a & c) ^ (b & c);
    // Only three operands remain on the critical path thanks to `p`.
    let t1 = s.p + big_sigma1(e) + ch;
    let t2 = big_sigma0(a) + maj;
    // Message schedule: W_{t+16} = σ1(W_{t+14}) + W_{t+9} + σ0(W_{t+1}) + W_t.
    // Late rounds compute words nobody reads; synthesis deletes them.
    let next_word = small_sigma1(s.w[14]) + s.w[9] + small_sigma0(s.w[1]) + s.w[0];
    // Shift the 16-word window by one and append the new word.
    let w = [
        s.w[1], s.w[2], s.w[3], s.w[4], s.w[5], s.w[6], s.w[7], s.w[8], s.w[9], s.w[10], s.w[11],
        s.w[12], s.w[13], s.w[14], s.w[15], next_word,
    ];
    Stage {
        valid: s.valid,
        tag: s.tag,
        chain: s.chain,
        work: [t1 + t2, a, b, c, d + t1, e, f, g],
        w,
        // Next round: h is this round's g, and W is the window's new head.
        p: g + k_next + w[0],
    }
}

/// One registered round.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct RoundStage {
    /// The pipeline register holding this round's result.
    reg: DFF<Stage>,
}

impl Default for RoundStage {
    fn default() -> Self {
        Self {
            reg: DFF::new(Stage::default()),
        }
    }
}

/// A round stage's input: the state and the next round's constant.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct RoundIn {
    /// State entering the round.
    pub stage: Stage,
    /// `K_{t+1}`.
    pub k_next: b64,
}

impl SynchronousIO for RoundStage {
    type I = RoundIn;
    type O = Stage;
    type Kernel = round_stage_kernel;
}

/// Compute the round and register it.
#[kernel]
pub fn round_stage_kernel(_cr: ClockReset, input: RoundIn, q: RoundStageQ) -> (Stage, RoundStageD) {
    (
        q.reg,
        RoundStageD {
            reg: round_kernel(input.stage, input.k_next),
        },
    )
}

/// Ten consecutive rounds, `10·G .. 10·G + 10`.
#[derive(Clone, Debug, Synchronous, SynchronousDQ, Default)]
pub struct RoundGroup<const G: usize> {
    // Rounds 10·G + 0 … 10·G + 9, in order. Groups of ten keep each RHDL
    // struct small (RHDL handles about eleven synchronous children per
    // struct comfortably), and eight groups make the 80 rounds.
    /// Round `10·G`.
    r0: RoundStage,
    /// Round `10·G + 1`.
    r1: RoundStage,
    /// Round `10·G + 2`.
    r2: RoundStage,
    /// Round `10·G + 3`.
    r3: RoundStage,
    /// Round `10·G + 4`.
    r4: RoundStage,
    /// Round `10·G + 5`.
    r5: RoundStage,
    /// Round `10·G + 6`.
    r6: RoundStage,
    /// Round `10·G + 7`.
    r7: RoundStage,
    /// Round `10·G + 8`.
    r8: RoundStage,
    /// Round `10·G + 9`.
    r9: RoundStage,
}

impl<const G: usize> SynchronousIO for RoundGroup<G> {
    type I = Stage;
    type O = Stage;
    type Kernel = round_group_kernel<G>;
}

/// Wire the ten rounds in series, each with its look-ahead constant.
#[kernel]
pub fn round_group_kernel<const G: usize>(
    _cr: ClockReset,
    input: Stage,
    q: RoundGroupQ<G>,
) -> (Stage, RoundGroupD<G>) {
    let d = RoundGroupD::<G> {
        r0: RoundIn { stage: input, k_next: K[10 * G + 1] },
        r1: RoundIn { stage: q.r0, k_next: K[10 * G + 2] },
        r2: RoundIn { stage: q.r1, k_next: K[10 * G + 3] },
        r3: RoundIn { stage: q.r2, k_next: K[10 * G + 4] },
        r4: RoundIn { stage: q.r3, k_next: K[10 * G + 5] },
        r5: RoundIn { stage: q.r4, k_next: K[10 * G + 6] },
        r6: RoundIn { stage: q.r5, k_next: K[10 * G + 7] },
        r7: RoundIn { stage: q.r6, k_next: K[10 * G + 8] },
        r8: RoundIn { stage: q.r7, k_next: K[10 * G + 9] },
        r9: RoundIn { stage: q.r8, k_next: K[10 * G + 10] },
    };
    (q.r9, d)
}

/// The whole core: input stage, 80 rounds, final addition.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct Sha512Pipeline {
    /// Input register: the block, its chaining value and the first `p`.
    input: DFF<Stage>,
    /// Rounds 0 … 9.
    g0: RoundGroup<0>,
    /// Rounds 10 … 19.
    g1: RoundGroup<1>,
    /// Rounds 20 … 29.
    g2: RoundGroup<2>,
    /// Rounds 30 … 39.
    g3: RoundGroup<3>,
    /// Rounds 40 … 49.
    g4: RoundGroup<4>,
    /// Rounds 50 … 59.
    g5: RoundGroup<5>,
    /// Rounds 60 … 69.
    g6: RoundGroup<6>,
    /// Rounds 70 … 79.
    g7: RoundGroup<7>,
    /// Output register: the chaining value plus the working variables.
    out: DFF<ShaOut>,
}

impl Default for Sha512Pipeline {
    fn default() -> Self {
        Self {
            input: DFF::new(Stage::default()),
            g0: RoundGroup::default(),
            g1: RoundGroup::default(),
            g2: RoundGroup::default(),
            g3: RoundGroup::default(),
            g4: RoundGroup::default(),
            g5: RoundGroup::default(),
            g6: RoundGroup::default(),
            g7: RoundGroup::default(),
            out: DFF::new(ShaOut::default()),
        }
    }
}

impl SynchronousIO for Sha512Pipeline {
    type I = ShaIn;
    type O = ShaCoreOut;
    type Kernel = sha512_pipeline_kernel;
}

/// Load a block, run the groups in series, add the chaining value.
#[kernel]
pub fn sha512_pipeline_kernel(
    cr: ClockReset,
    input: ShaIn,
    q: Sha512PipelineQ,
) -> (ShaCoreOut, Sha512PipelineD) {
    // During reset no block may enter or leave, so stale stages drain out
    // as invalid.
    let resetting = cr.reset.any();
    // The chaining value: the standard IV for a message's first block,
    // otherwise the previous block's result supplied by the client.
    let chain = if input.use_iv { IV } else { input.chain };
    // Round 0 starts with a..h = chain, and its look-ahead
    // p = h + K_0 + W_0 is computed here, one stage early.
    let entering = Stage {
        valid: input.valid && !resetting,
        tag: input.tag,
        chain,
        work: chain,
        w: input.block,
        p: chain[7] + K[0] + input.block[0],
    };
    // The block leaving round 79, and the feed-forward addition that turns
    // the working variables into the new chaining value.
    let last = q.g7;
    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],
    ];
    let d = Sha512PipelineD {
        input: entering,
        g0: q.input,
        g1: q.g0,
        g2: q.g1,
        g3: q.g2,
        g4: q.g3,
        g5: q.g4,
        g6: q.g5,
        g7: q.g6,
        out: ShaOut {
            valid: last.valid && !resetting,
            tag: last.tag,
            state,
        },
    };
    (
        ShaCoreOut {
            ready: true,
            done: q.out,
        },
        d,
    )
}