rhdl_ed25519_scalable_core/
sha_client.rs

1//! Port to a shared SHA-512 pipeline.
2//!
3//! The shared line (`rhdl_sha512_pipelined`) is either the full pipeline,
4//! which takes a block every cycle with a fixed latency, or a folded core,
5//! which takes a block when its `ready` is high (`S / 80` blocks per clock)
6//! and returns it 82 cycles after it enters its ring. Both return blocks in
7//! the order they took them, and the arbiter relies on nothing else. Several
8//! modules share it through a [`ShaArbiter`]; each module talks to the
9//! arbiter through a [`ShaClient`], which offers exactly the interface of a
10//! [`ShaRing`](crate::sha_ring::ShaRing) (`ShaRingIn`/`ShaRingOut`), so a
11//! core can swap its rings for one client.
12//!
13//! ```text
14//!  core ──ShaRingIn──> ShaClient ──PipeIn/grant──> ShaArbiter ──> pipeline
15//!  core <─ShaRingOut── ShaClient <──PipeOut──────  ShaArbiter <── pipeline
16//! ```
17//!
18//! # Client
19//!
20//! - **Credits.** The line cannot hold a result, so every block in flight must
21//!   have room waiting at its client. A client holds [`CLIENT_CREDITS`]
22//!   credits, one per entry of its result FIFO; issuing a block takes one,
23//!   and the core taking a digest returns one.
24//! - **Two-block jobs.** A job with `second_pad` (a 128-byte message, as in
25//!   the challenge `H(R || A || M)`) comes back from its first block marked
26//!   *first*; the client resubmits the constant padding block with that
27//!   state as the chain, ahead of new jobs. The entry's credit carries over.
28//! - **Order.** The pipeline returns blocks in order, so a small ring of
29//!   *first* flags, written at issue and read at return, tells the two kinds
30//!   apart; tags pass through untouched.
31//!
32//! # Arbiter
33//!
34//! Round-robin over the clients' requests (each client's request depends
35//! only on its registers), granting only while the line's `ready` input is
36//! high. Results are routed by a FIFO of client numbers written at issue and
37//! read when a result returns (the line keeps order), so the pipeline's tag
38//! stays the client's own and the line's latency may vary.
39//!
40//! # Combinational paths
41//!
42//! A client's `req` and ring outputs come from its registers only. The
43//! arbiter's grants and result routing are combinational from those
44//! requests and from the pipeline's output. So the client -> arbiter ->
45//! client path that the grant takes in one cycle contains no loop, and the
46//! request to the pipeline also depends only on registers.
47
48use rhdl::prelude::*;
49use rhdl_fpga::core::{
50    dff::DFF,
51    ram::synchronous::{SyncBRAM, Write as RamWrite},
52};
53
54use crate::{
55    sha_ring::{ShaDone, ShaJob, ShaRingIn, ShaRingOut, pad_block_128},
56    sign_core::ram_read,
57};
58
59/// Jobs a client may have issued and not yet drained, which is also the
60/// depth of its result FIFO.
61///
62/// A two-block job holds a single credit for both of its blocks. The value
63/// must match the FIFO's 5-bit address (32 entries) and the 32-entry flag
64/// ring in `ClientRegs`.
65pub const CLIENT_CREDITS: usize = 32;
66/// Cycles from a request entering the pipeline to its result
67/// (`rhdl_sha512_pipelined::LATENCY`).
68///
69/// The arbiter's owner ring has 128 entries, so this must stay below 128.
70pub const PIPE_LATENCY: usize = 82;
71
72/// One block for the pipeline (field for field `rhdl_sha512_pipelined::ShaIn`).
73#[derive(Copy, Clone, Debug, PartialEq, Digital)]
74pub struct PipeIn {
75    /// A block is presented. The arbiter presents one only while the line is
76    /// ready, so the line takes every block it sees.
77    pub valid: bool,
78    /// Returned with the result; the client's own job tag.
79    pub tag: b16,
80    /// One 128-byte message block as 16 big-endian words.
81    pub block: [b64; 16],
82    /// Start from the SHA-512 IV instead of `chain`.
83    pub use_iv: bool,
84    /// Chaining value when `use_iv` is low.
85    pub chain: [b64; 8],
86}
87
88/// One finished block (field for field `rhdl_sha512_pipelined::ShaOut`).
89#[derive(Copy, Clone, Debug, PartialEq, Digital)]
90pub struct PipeOut {
91    /// Present this cycle; must be taken (the pipeline cannot hold it).
92    pub valid: bool,
93    /// The request's tag.
94    pub tag: b16,
95    /// New chaining value (`chain` plus the compressed block, big-endian
96    /// words).
97    pub state: [b64; 8],
98}
99
100/// An idle request (no block, all fields zero).
101#[kernel]
102pub fn idle_pipe_in() -> PipeIn {
103    PipeIn { valid: false, tag: b16(0), block: [b64(0); 16], use_iv: false, chain: [b64(0); 8] }
104}
105
106/// No result (all fields zero).
107#[kernel]
108pub fn idle_pipe_out() -> PipeOut {
109    PipeOut { valid: false, tag: b16(0), state: [b64(0); 8] }
110}
111
112/// Inputs of [`ShaClient`].
113#[derive(Copy, Clone, Debug, PartialEq, Digital)]
114pub struct ShaClientIn {
115    /// From the core, as for a ring.
116    pub ring: ShaRingIn,
117    /// The arbiter took [`ShaClientOut::req`] this cycle.
118    pub grant: bool,
119    /// A result for this client; when valid it must be stored this cycle.
120    pub resp: PipeOut,
121}
122
123/// Outputs of [`ShaClient`].
124#[derive(Copy, Clone, Debug, PartialEq, Digital)]
125pub struct ShaClientOut {
126    /// To the core, as for a ring.
127    pub ring: ShaRingOut,
128    /// Request to the arbiter (depends only on registers).
129    pub req: PipeIn,
130}
131
132/// One result in the client's FIFO.
133#[derive(Copy, Clone, Debug, PartialEq, Digital)]
134#[doc(hidden)]
135pub struct Entry {
136    /// The job's tag.
137    tag: b16,
138    /// The result of the first block of a two-block job: `state` is a
139    /// chaining value for the padding block, not a digest.
140    first: bool,
141    /// Chaining value returned by the pipeline.
142    state: [b64; 8],
143}
144
145/// Registers of [`ShaClient`].
146#[derive(Copy, Clone, Debug, PartialEq, Digital)]
147#[doc(hidden)]
148pub struct ClientRegs {
149    /// One-entry job buffer from the core; the ring-side `ready` is
150    /// `!job.valid`.
151    job: ShaJob,
152    /// Credits left (0..=[`CLIENT_CREDITS`]): [`CLIENT_CREDITS`] minus the
153    /// jobs issued and not yet taken by the core. Each such job keeps one FIFO
154    /// entry reserved, wherever it is (pipeline, FIFO or `head`).
155    credits: b6,
156    /// In-order ring of *first* flags, one per block in the pipeline.
157    flags: [bool; 32],
158    /// Next flag to write (at grant).
159    flag_wr: b5,
160    /// Next flag to read (at result).
161    flag_rd: b5,
162    /// FIFO write pointer.
163    wr: b5,
164    /// FIFO read pointer: the next entry to fetch into `head`.
165    rd: b5,
166    /// Entries in the FIFO, not counting one being fetched or in `head`.
167    count: b6,
168    /// A FIFO read was issued last cycle; its data arrives this cycle.
169    fetching: bool,
170    /// `head` holds the oldest result.
171    head_valid: bool,
172    /// Oldest result, out of the FIFO so it can be offered without a read
173    /// latency.
174    head: Entry,
175}
176
177/// Client of the shared SHA-512 pipeline, with a ring's interface.
178///
179/// Buffers one job from the core at a time, issues blocks to the arbiter,
180/// and buffers results (first halves and digests) in a FIFO. Results leave the
181/// FIFO in pipeline order, so digests reach the core in the order their last
182/// blocks finished, not in job order.
183#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
184pub struct ShaClient {
185    /// Control state.
186    regs: DFF<ClientRegs>,
187    /// Result FIFO, [`CLIENT_CREDITS`] entries (one-cycle read latency).
188    fifo: SyncBRAM<Entry, 5>,
189}
190
191/// Reset state: no job, full credits, empty FIFO.
192impl Default for ShaClient {
193    /// Builds the reset state.
194    fn default() -> Self {
195        let entry = Entry { tag: b16(0), first: false, state: [b64(0); 8] };
196        Self {
197            regs: DFF::new(ClientRegs {
198                job: ShaJob { valid: false, tag: b16(0), block: [b64(0); 16], second_pad: false },
199                credits: b6(CLIENT_CREDITS as u128),
200                flags: [false; 32],
201                flag_wr: b5(0),
202                flag_rd: b5(0),
203                wr: b5(0),
204                rd: b5(0),
205                count: b6(0),
206                fetching: false,
207                head_valid: false,
208                head: entry,
209            }),
210            fifo: SyncBRAM::default(),
211        }
212    }
213}
214
215/// Ports and kernel of [`ShaClient`].
216impl SynchronousIO for ShaClient {
217    /// Input port bundle.
218    type I = ShaClientIn;
219    /// Output port bundle.
220    type O = ShaClientOut;
221    /// Kernel computing the outputs and the next state.
222    type Kernel = sha_client_kernel;
223}
224
225/// State transition for [`ShaClient`].
226#[kernel]
227pub fn sha_client_kernel(_cr: ClockReset, i: ShaClientIn, q: ShaClientQ) -> (ShaClientOut, ShaClientD) {
228    let r = q.regs;
229    let mut n = r;
230    let mut d = ShaClientD::dont_care();
231    // The FIFO always reads at `rd`; the data is used only when a fetch was
232    // started, one cycle later. No write unless a result arrives below.
233    d.fifo = ram_read::<Entry, 5>(r.rd, q.fifo);
234
235    // Head of the result FIFO: one-cycle read, then held in `head`.
236    // `count` collects this cycle's FIFO pops and pushes.
237    let mut count = r.count;
238    if r.fetching {
239        n.head = q.fifo;
240        n.head_valid = true;
241        n.fetching = false;
242    }
243    // Start a fetch when the head is empty and nothing is on its way.
244    if !r.head_valid && !r.fetching && r.count != b6(0) {
245        n.fetching = true;
246        n.rd = r.rd + b5(1);
247        count = count - b6(1);
248    }
249
250    // Request: the padding block of a first half before any new job.
251    // Serving first halves first keeps the head moving, and the padding
252    // block needs no credit: its job already holds one.
253    // The head is a first half, to be resubmitted with the padding block.
254    let head_pad = r.head_valid && r.head.first;
255    // The head is a finished digest for the core.
256    let head_done = r.head_valid && !r.head.first;
257    let mut req = idle_pipe_in();
258    // The block requested now is the first of two, so its result must come
259    // back marked *first*.
260    let mut req_first = false;
261    if head_pad {
262        // Chain from the first block's state, not from the IV.
263        req = PipeIn { valid: true, tag: r.head.tag, block: pad_block_128(), use_iv: false, chain: r.head.state };
264    } else if r.job.valid && r.credits != b6(0) {
265        // A new job needs a credit: a FIFO entry reserved for its result.
266        req = PipeIn { valid: true, tag: r.job.tag, block: r.job.block, use_iv: true, chain: [b64(0); 8] };
267        req_first = r.job.second_pad;
268    }
269    let mut credits = r.credits;
270    if req.valid && i.grant {
271        // Record, in issue order, whether this block's result is a first
272        // half; the pipeline returns this client's blocks in the same order.
273        n.flags[r.flag_wr] = req_first;
274        n.flag_wr = r.flag_wr + b5(1);
275        if head_pad {
276            // The first half leaves the head; its credit carries over to the
277            // padding block's result.
278            n.head_valid = false;
279        } else {
280            n.job.valid = false;
281            credits = credits - b6(1);
282        }
283    }
284
285    // Finished digests to the core. Taking one frees its FIFO reservation.
286    if head_done && i.ring.out_ready {
287        n.head_valid = false;
288        credits = credits + b6(1);
289    }
290
291    // New job from the core, accepted while the buffer is empty (`ready`).
292    if i.ring.job.valid && !r.job.valid {
293        n.job = i.ring.job;
294    }
295
296    // Results from the pipeline (room guaranteed by the credits). The oldest
297    // outstanding flag says whether this result is a first half.
298    if i.resp.valid {
299        d.fifo.write = RamWrite::<Entry, 5> {
300            addr: r.wr,
301            value: Entry { tag: i.resp.tag, first: r.flags[r.flag_rd], state: i.resp.state },
302            enable: true,
303        };
304        n.wr = r.wr + b5(1);
305        n.flag_rd = r.flag_rd + b5(1);
306        count = count + b6(1);
307    }
308    n.count = count;
309    n.credits = credits;
310    d.regs = n;
311    let out = ShaClientOut {
312        ring: ShaRingOut {
313            ready: !r.job.valid,
314            done: ShaDone { valid: head_done, tag: r.head.tag, state: r.head.state },
315        },
316        req: req,
317    };
318    (out, d)
319}
320
321/// Inputs of [`ShaArbiter`].
322#[derive(Copy, Clone, Debug, PartialEq, Digital)]
323pub struct ArbiterIn<const N: usize> {
324    /// Requests of the clients (each from registers only).
325    pub reqs: [PipeIn; N],
326    /// Line result this cycle, for the oldest block still in flight.
327    pub pipe: PipeOut,
328    /// The line takes a block presented this cycle (always high for the
329    /// full pipeline; a folded core's `ready`). Must depend only on the
330    /// line's registers.
331    pub pipe_ready: bool,
332}
333
334/// Outputs of [`ShaArbiter`].
335#[derive(Copy, Clone, Debug, PartialEq, Digital)]
336pub struct ArbiterOut<const N: usize> {
337    /// Client `k`'s request was taken.
338    pub grants: [bool; N],
339    /// Client `k`'s result (valid for at most one client per cycle).
340    pub resps: [PipeOut; N],
341    /// Request to the pipeline: the granted client's request, or idle.
342    pub pipe: PipeIn,
343}
344
345/// Registers of [`ShaArbiter`].
346#[derive(Copy, Clone, Debug, PartialEq, Digital)]
347#[doc(hidden)]
348pub struct ArbiterRegs {
349    /// Round-robin pointer: the client searched first next cycle.
350    next: b4,
351    /// Owner FIFO: the client of each block in flight, oldest at `rd`.
352    owner: [b4; 128],
353    /// Owner FIFO write position (next issue).
354    wr: b7,
355    /// Owner FIFO read position (next result).
356    rd: b7,
357}
358
359/// Round-robin arbiter of up to 16 clients onto one pipeline.
360///
361/// Client numbers are 4 bits wide, hence the limit of 16.
362#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
363pub struct ShaArbiter<const N: usize> {
364    /// Round-robin pointer and owner ring.
365    regs: DFF<ArbiterRegs>,
366}
367
368/// Reset state; checks `1 <= N <= 16` and that the owner FIFO covers the
369/// full pipeline's [`PIPE_LATENCY`] (a folded core holds at most 42 blocks).
370impl<const N: usize> Default for ShaArbiter<N> {
371    /// Builds the reset state.
372    fn default() -> Self {
373        assert!(N >= 1 && N <= 16 && PIPE_LATENCY < 128);
374        Self { regs: DFF::new(ArbiterRegs { next: b4(0), owner: [b4(0); 128], wr: b7(0), rd: b7(0) }) }
375    }
376}
377
378/// Ports and kernel of [`ShaArbiter`].
379impl<const N: usize> SynchronousIO for ShaArbiter<N> {
380    /// Input port bundle.
381    type I = ArbiterIn<N>;
382    /// Output port bundle.
383    type O = ArbiterOut<N>;
384    /// Kernel computing the outputs and the next state.
385    type Kernel = sha_arbiter_kernel<N>;
386}
387
388/// State transition for [`ShaArbiter`].
389#[kernel]
390pub fn sha_arbiter_kernel<const N: usize>(_cr: ClockReset, i: ArbiterIn<N>, q: ShaArbiterQ<N>) -> (ArbiterOut<N>, ShaArbiterD<N>) {
391    let r = q.regs;
392    let mut n = r;
393    let mut d = ShaArbiterD::<N>::dont_care();
394    // First valid request at or after `next`, else the first before it.
395    // `found`: some client is granted; `pick`: which one.
396    let mut found = false;
397    let mut pick = b4(0);
398    for k in 0..N {
399        if !found && i.pipe_ready && i.reqs[k].valid && b4(k as u128) >= r.next {
400            found = true;
401            pick = b4(k as u128);
402        }
403    }
404    for k in 0..N {
405        if !found && i.pipe_ready && i.reqs[k].valid {
406            found = true;
407            pick = b4(k as u128);
408        }
409    }
410    let mut grants = [false; N];
411    let mut pipe = idle_pipe_in();
412    for k in 0..N {
413        if found && pick == b4(k as u128) {
414            grants[k] = true;
415            pipe = i.reqs[k];
416        }
417    }
418    // The client after the one granted is searched first next time, so
419    // every requesting client is served within N grants.
420    if found {
421        n.next = if pick == b4((N - 1) as u128) { b4(0) } else { pick + b4(1) };
422    }
423    // Owner FIFO: the granted client is pushed at issue and popped when a
424    // result returns. The line keeps order, so the oldest entry owns it,
425    // and the client's tag passes through the line unchanged.
426    if found {
427        n.owner[r.wr] = pick;
428        n.wr = r.wr + b7(1);
429    }
430    let owner = r.owner[r.rd];
431    if i.pipe.valid {
432        n.rd = r.rd + b7(1);
433    }
434    // Route the result to its owner only; every other client sees idle.
435    let mut resps = [idle_pipe_out(); N];
436    for k in 0..N {
437        if i.pipe.valid && owner == b4(k as u128) {
438            resps[k] = i.pipe;
439        }
440    }
441    d.regs = n;
442    (ArbiterOut::<N> { grants: grants, resps: resps, pipe: pipe }, d)
443}
444
445/// Inputs of [`SharedShaPort`].
446#[derive(Copy, Clone, Debug, PartialEq, Digital)]
447pub struct SharedShaIn<const N: usize> {
448    /// Each module's ring-style requests.
449    pub rings: [ShaRingIn; N],
450    /// Pipeline result this cycle (`rhdl_sha512_pipelined::ShaOut`).
451    pub pipe: PipeOut,
452    /// The line takes a block this cycle (`ShaCoreOut::ready`; always high
453    /// for the full pipeline).
454    pub pipe_ready: bool,
455}
456
457/// Outputs of [`SharedShaPort`].
458#[derive(Copy, Clone, Debug, PartialEq, Digital)]
459pub struct SharedShaOut<const N: usize> {
460    /// Each module's ring-style outputs.
461    pub rings: [ShaRingOut; N],
462    /// Request to the pipeline (depends only on registers).
463    pub pipe: PipeIn,
464}
465
466/// `N` clients and their arbiter: everything between `N` modules and one
467/// shared SHA-512 pipeline.
468#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
469pub struct SharedShaPort<const N: usize> {
470    /// One client per module; module `k` uses client `k`.
471    clients: [ShaClient; N],
472    /// Arbiter of the clients' requests.
473    arbiter: ShaArbiter<N>,
474}
475
476/// Reset state of all clients and the arbiter.
477impl<const N: usize> Default for SharedShaPort<N> {
478    /// Builds the reset state.
479    fn default() -> Self {
480        Self { clients: std::array::from_fn(|_| ShaClient::default()), arbiter: ShaArbiter::default() }
481    }
482}
483
484/// Ports and kernel of [`SharedShaPort`].
485impl<const N: usize> SynchronousIO for SharedShaPort<N> {
486    /// Input port bundle.
487    type I = SharedShaIn<N>;
488    /// Output port bundle.
489    type O = SharedShaOut<N>;
490    /// Kernel computing the outputs and the next state.
491    type Kernel = shared_sha_port_kernel<N>;
492}
493
494/// Wiring for [`SharedShaPort`].
495///
496/// Clients' requests go to the arbiter; the arbiter's grants and results go
497/// back to the clients in the same cycle. That is loop-free because the
498/// clients' outputs depend only on their registers.
499#[kernel]
500pub fn shared_sha_port_kernel<const N: usize>(_cr: ClockReset, i: SharedShaIn<N>, q: SharedShaPortQ<N>) -> (SharedShaOut<N>, SharedShaPortD<N>) {
501    let mut d = SharedShaPortD::<N>::dont_care();
502    let mut reqs = [idle_pipe_in(); N];
503    // Initialized with client 0's value only to have a value of the right
504    // type; every element is overwritten below.
505    let mut rings = [q.clients[0].ring; N];
506    for k in 0..N {
507        reqs[k] = q.clients[k].req;
508        rings[k] = q.clients[k].ring;
509    }
510    d.arbiter = ArbiterIn::<N> { reqs: reqs, pipe: i.pipe, pipe_ready: i.pipe_ready };
511    for k in 0..N {
512        d.clients[k] = ShaClientIn { ring: i.rings[k], grant: q.arbiter.grants[k], resp: q.arbiter.resps[k] };
513    }
514    (SharedShaOut::<N> { rings: rings, pipe: q.arbiter.pipe }, d)
515}
516
517/// Cycle tests of the shared port against a software pipeline model.
518/// `Pipe` and `idle_out` are also used by the crate's `tests` module.
519#[cfg(test)]
520pub(crate) mod tests {
521    use super::*;
522    use crate::simulation::CycleSim;
523    use std::collections::VecDeque;
524
525    /// SHA-512 round constants for the reference compression.
526    const K: [u64; 80] = [
527        0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc, 0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118,
528        0xd807aa98a3030242, 0x12835b0145706fbe, 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2, 0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 0xc19bf174cf692694,
529        0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65, 0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5,
530        0x983e5152ee66dfab, 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4, 0xc6e00bf33da88fc2, 0xd5a79147930aa725, 0x06ca6351e003826f, 0x142929670a0e6e70,
531        0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df, 0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b,
532        0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30, 0xd192e819d6ef5218, 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8,
533        0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8, 0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3,
534        0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec, 0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b,
535        0xca273eceea26619c, 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178, 0x06f067aa72176fba, 0x0a637dc5a2c898a6, 0x113f9804bef90dae, 0x1b710b35131c471b,
536        0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c, 0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817,
537    ];
538    /// SHA-512 initial chaining value for the reference compression.
539    pub(crate) const IV: [u64; 8] = [
540        0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1, 0x510e527fade682d1, 0x9b05688c2b3e6c1f, 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179,
541    ];
542
543    /// Reference SHA-512 compression.
544    pub fn compress(chain: [u64; 8], block: [u64; 16]) -> [u64; 8] {
545        let mut w = [0u64; 80];
546        w[..16].copy_from_slice(&block);
547        for t in 16..80 {
548            let s0 = w[t - 15].rotate_right(1) ^ w[t - 15].rotate_right(8) ^ (w[t - 15] >> 7);
549            let s1 = w[t - 2].rotate_right(19) ^ w[t - 2].rotate_right(61) ^ (w[t - 2] >> 6);
550            w[t] = w[t - 16].wrapping_add(s0).wrapping_add(w[t - 7]).wrapping_add(s1);
551        }
552        let mut v = chain;
553        for t in 0..80 {
554            let [a, b, c, dd, e, f, g, h] = v;
555            let t1 = h
556                .wrapping_add(e.rotate_right(14) ^ e.rotate_right(18) ^ e.rotate_right(41))
557                .wrapping_add((e & f) ^ (!e & g))
558                .wrapping_add(K[t])
559                .wrapping_add(w[t]);
560            let t2 = (a.rotate_right(28) ^ a.rotate_right(34) ^ a.rotate_right(39)).wrapping_add((a & b) ^ (a & c) ^ (b & c));
561            v = [t1.wrapping_add(t2), a, b, c, dd.wrapping_add(t1), e, f, g];
562        }
563        std::array::from_fn(|k| chain[k].wrapping_add(v[k]))
564    }
565
566    /// Hardware words to host words.
567    fn words<const M: usize>(x: [b64; M]) -> [u64; M] {
568        x.map(|w| w.raw() as u64)
569    }
570
571    /// Fixed-latency pipeline model.
572    pub(crate) struct Pipe {
573        /// One slot per pipeline stage; the front leaves this cycle.
574        line: VecDeque<Option<PipeOut>>,
575    }
576
577    /// Construction and stepping of the model.
578    impl Pipe {
579        /// An empty pipeline of [`PIPE_LATENCY`] stages.
580        pub(crate) fn new() -> Self {
581            Pipe { line: (0..PIPE_LATENCY).map(|_| None).collect() }
582        }
583        /// Present `req` this cycle; returns the result leaving this cycle.
584        pub(crate) fn step(&mut self, req: PipeIn) -> PipeOut {
585            let out = self.line.pop_front().unwrap();
586            let next = req.valid.then(|| {
587                let chain = if req.use_iv { IV } else { words(req.chain) };
588                PipeOut { valid: true, tag: req.tag, state: compress(chain, words(req.block)).map(|w| b64(w as u128)) }
589            });
590            self.line.push_back(next);
591            out.unwrap_or(PipeOut { valid: false, tag: b16(0), state: [b64(0); 8] })
592        }
593    }
594
595    /// A SHA-512 line as the shared port sees it, one cycle at a time:
596    /// [`ready`](Line::ready) and [`out`](Line::out) are this cycle's outputs
597    /// (from the line's state), and [`take`](Line::take) latches this cycle's
598    /// request at the edge.
599    pub(crate) trait Line {
600        /// The line takes a block presented this cycle.
601        fn ready(&self) -> bool;
602        /// The result leaving this cycle.
603        fn out(&mut self) -> PipeOut;
604        /// Latch this cycle's request (presented only while ready).
605        fn take(&mut self, req: PipeIn);
606        /// Blocks inside the line (for stall reports).
607        fn held(&self) -> usize {
608            0
609        }
610    }
611
612    /// The full pipeline never refuses a block.
613    impl Line for Pipe {
614        fn ready(&self) -> bool {
615            true
616        }
617        fn out(&mut self) -> PipeOut {
618            self.line.pop_front().unwrap().unwrap_or(PipeOut { valid: false, tag: b16(0), state: [b64(0); 8] })
619        }
620        fn take(&mut self, req: PipeIn) {
621            let next = req.valid.then(|| {
622                let chain = if req.use_iv { IV } else { words(req.chain) };
623                PipeOut { valid: true, tag: req.tag, state: compress(chain, words(req.block)).map(|w| b64(w as u128)) }
624            });
625            self.line.push_back(next);
626        }
627    }
628
629    /// Model of a folded core with `S` round stages (`rhdl_sha512_pipelined::
630    /// folded`): it holds at most `S + 1` blocks, is ready while it has room,
631    /// returns blocks in order no earlier than 82 cycles after they enter, and
632    /// at most one every `ceil(80 / S)` cycles, so its latency grows under load.
633    pub(crate) struct Folded {
634        cap: usize,
635        interval: u64,
636        now: u64,
637        last: u64,
638        held: VecDeque<(u64, PipeOut)>,
639    }
640
641    /// Construction of the folded model.
642    impl Folded {
643        /// A folded core of `stages` round stages.
644        pub(crate) fn new(stages: usize) -> Self {
645            Folded { cap: stages + 1, interval: 80_u64.div_ceil(stages as u64), now: 0, last: 0, held: VecDeque::new() }
646        }
647    }
648
649    /// Stepping of the folded model.
650    impl Line for Folded {
651        fn ready(&self) -> bool {
652            self.held.len() < self.cap
653        }
654        fn out(&mut self) -> PipeOut {
655            self.now += 1;
656            if let Some(&(at, result)) = self.held.front() {
657                if at <= self.now && self.now >= self.last + self.interval {
658                    self.held.pop_front();
659                    self.last = self.now;
660                    return result;
661                }
662            }
663            PipeOut { valid: false, tag: b16(0), state: [b64(0); 8] }
664        }
665        fn held(&self) -> usize {
666            self.held.len()
667        }
668        fn take(&mut self, req: PipeIn) {
669            if req.valid {
670                assert!(self.held.len() < self.cap, "block presented while the folded core was not ready");
671                let chain = if req.use_iv { IV } else { words(req.chain) };
672                let state = compress(chain, words(req.block)).map(|w| b64(w as u128));
673                self.held.push_back((self.now + 82, PipeOut { valid: true, tag: req.tag, state }));
674            }
675        }
676    }
677
678    /// Deterministic pseudo-random block for job `k`, and whether it is a
679    /// two-block job.
680    fn job(k: u64, two: bool) -> ([u64; 16], bool) {
681        let mut block = [0u64; 16];
682        for (j, w) in block.iter_mut().enumerate() {
683            *w = (k + 1).wrapping_mul(0x9e3779b97f4a7c15).rotate_left(j as u32 * 7) ^ j as u64;
684        }
685        (block, two)
686    }
687
688    /// Reference final state of a job: one compression from the IV, then the
689    /// 128-byte padding block if `two`.
690    fn expected(block: [u64; 16], two: bool) -> [u64; 8] {
691        let s = compress(IV, block);
692        if two {
693            let mut pad = [0u64; 16];
694            pad[0] = 0x8000000000000000;
695            pad[15] = 0x400;
696            compress(s, pad)
697        } else {
698            s
699        }
700    }
701
702    /// Three clients with different job mixes and stalls share one
703    /// pipeline; every digest matches the reference and no client loses a
704    /// result.
705    #[test]
706    fn clients_share_one_pipeline() {
707        share(&mut Pipe::new(), 40_000);
708    }
709
710    /// The same three clients behind folded cores of 2, 10 and 40 stages:
711    /// the arbiter waits for `ready`, results come back later and later
712    /// under load, and still every digest reaches its client.
713    #[test]
714    fn clients_share_a_folded_core() {
715        for stages in [2, 10, 40] {
716            share(&mut Folded::new(stages), 400_000);
717        }
718    }
719
720    /// Runs the three-client workload against `line` (at most `limit`
721    /// cycles) and checks every digest.
722    fn share(line: &mut dyn Line, limit: u64) {
723        /// Number of clients sharing the pipeline in this test.
724        const N: usize = 3;
725        let mut sim = CycleSim::new(SharedShaPort::<N>::default());
726        let pipe = line;
727        let jobs_per_client = 120u64;
728        let mut sent = [0u64; N];
729        let mut got: Vec<Vec<(u64, [u64; 8])>> = vec![Vec::new(); N];
730        let idle_ring = ShaRingIn { job: ShaJob { valid: false, tag: b16(0), block: [b64(0); 16], second_pad: false }, out_ready: false };
731        let mut out = sim.tick(SharedShaIn::<N> { rings: [idle_ring; N], pipe: idle_pipe_out_value(), pipe_ready: false });
732        let mut cycle = 0u64;
733        while got.iter().map(Vec::len).sum::<usize>() < N * jobs_per_client as usize {
734            cycle += 1;
735            assert!(cycle < limit, "stalled: {:?}", got.iter().map(Vec::len).collect::<Vec<_>>());
736            // The line's outputs this cycle come from its state; the request
737            // it latches is the port's value before the edge, which already
738            // saw this cycle's `ready`.
739            let ready = pipe.ready();
740            let pipe_out = pipe.out();
741            let mut rings = [idle_ring; N];
742            for k in 0..N {
743                // Client k offers a job at most every (k + 1)-th cycle;
744                // even and odd ids alternate between one and two blocks.
745                if sent[k] < jobs_per_client && out.rings[k].ready && (cycle + k as u64) % (k as u64 + 1) == 0 {
746                    let id = sent[k];
747                    let (block, two) = job(id * 7 + k as u64, (id + k as u64) % 2 == 0);
748                    rings[k].job = ShaJob { valid: true, tag: b16(id as u128), block: block.map(|w| b64(w as u128)), second_pad: two };
749                    sent[k] += 1;
750                }
751                // Client 2 drains only every fifth cycle.
752                rings[k].out_ready = k != 2 || cycle % 5 == 0;
753                if out.rings[k].done.valid && rings[k].out_ready {
754                    got[k].push((out.rings[k].done.tag.raw() as u64, words(out.rings[k].done.state)));
755                }
756            }
757            let (before, after) = sim.tick_both(SharedShaIn::<N> { rings, pipe: pipe_out, pipe_ready: ready });
758            pipe.take(before.pipe);
759            out = after;
760        }
761        for k in 0..N {
762            for (tag, state) in &got[k] {
763                let (block, two) = job(tag * 7 + k as u64, (tag + k as u64) % 2 == 0);
764                assert_eq!(*state, expected(block, two), "client {k} tag {tag}");
765            }
766            let mut tags: Vec<u64> = got[k].iter().map(|g| g.0).collect();
767            tags.sort();
768            assert_eq!(tags, (0..jobs_per_client).collect::<Vec<_>>());
769        }
770        println!("shared SHA: {} blocks in {cycle} cycles", N as u64 * jobs_per_client * 3 / 2);
771    }
772
773    /// No pipeline result, for other test modules.
774    pub(crate) fn idle_out() -> PipeOut {
775        idle_pipe_out_value()
776    }
777
778    /// No pipeline result (host-side twin of [`idle_pipe_out`]).
779    fn idle_pipe_out_value() -> PipeOut {
780        PipeOut { valid: false, tag: b16(0), state: [b64(0); 8] }
781    }
782
783    /// The reference compression gives SHA-512("abc").
784    #[test]
785    fn reference_compress_matches_sha2() {
786        use sha2::{Digest, Sha512};
787        let msg = [0x61u8, 0x62, 0x63];
788        let mut block = [0u64; 16];
789        block[0] = 0x6162638000000000;
790        block[15] = 24;
791        let want = Sha512::digest(msg);
792        let got: Vec<u8> = compress(IV, block).iter().flat_map(|w| w.to_be_bytes()).collect();
793        assert_eq!(&got[..], &want[..]);
794    }
795}
796
rhdl_ed25519_scalable_core/sha_client.rs

rhdl_ed25519_scalable_core/
sha_client.rs
