rhdl_ed25519_scalable_core/

fe17_kara.rs

//! The 150-DSP field multiplier: three-way subtractive Karatsuba.
//!
//! [`FieldMulKara`] is a drop-in for [`FieldMulPar`](super::fe17::FieldMulPar):
//! the same ports, the same initiation interval of one and the same
//! [`MUL_LATENCY`], with 150 DSPs instead of 225.
//!
//! # The split
//!
//! The fifteen 17-bit digits of each factor form three blocks of five,
//! `A = A0 + A1 X + A2 X^2` with `X = 2^85`. Schoolbook needs nine block
//! products; Karatsuba needs six, all of five by five digits:
//!
//! - `P00 = A0 B0`, `P11 = A1 B1`, `P22 = A2 B2`;
//! - `D01 = (A0 - A1)(B0 - B1)`, `D02 = (A0 - A2)(B0 - B2)`,
//!   `D12 = (A1 - A2)(B1 - B2)`, digit by digit.
//!
//! The coefficients of `X^u` are then `G0 = P00`, `G1 = P00 + P11 - D01`,
//! `G2 = P00 + P11 + P22 - D02`, `G3 = P11 + P22 - D12` and `G4 = P22`.
//! The differences are digit-wise, so each difference digit is within
//! `±(2^17 - 1)`: an 18-bit signed operand, which is exactly what a
//! DSP48E2's 18-bit port takes, and each product (`18 x 18` signed) is one
//! DSP. Six block products of 25 digit products are the 150 DSPs.
//!
//! # Pipeline
//!
//! | Edge | Step |
//! |---|---|
//! | 1 | capture `a`, `b` |
//! | 2 | form the six operand rows (the differences are fabric subtracts) |
//! | 3..7 | five multiply-accumulate stages ([`KaraStage`]); stage `s` adds `x_s y_j` to columns `s + j` |
//! | 8 | `S = P00 + P11`, `T = P11 + P22` |
//! | 9 | `G1 = S - D01`, `G2' = S + P22`, `G3 = T - D12` |
//! | 10 | `G2 = G2' - D02` |
//! | 11 | the 29 product columns `C_t` from the overlapping `G_u` |
//! | 12 | fold: `c_k = C_k + 19 C_{k+15}` (`2^255 = 19 mod p`) |
//! | 13..18 | [`MulNorm`], shared with the 225-DSP unit |
//! | 19..23 | result delay, so the latency matches the 225-DSP unit |
//!
//! Every true column `C_t` is a sum of digit products, so it is
//! non-negative and below `15 (2^17 - 1)^2 < 2^38`, whatever signs the
//! intermediate Karatsuba terms take; the folded columns are below `2^43`,
//! the normalizer's input width.

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

use super::fe17::{FieldMulIn, FieldMulOut, Fe17, MUL_LATENCY, MulNorm};

/// Operand row of one block product: the multiplier digits still to use
/// (this stage's first) and the five multiplicand digits.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct KaraRow {
    /// Multiplier digits; `x[0]` is this stage's, the rest shift down.
    pub x: [s18; 5],
    /// Multiplicand digits, the same at every stage.
    pub y: [s18; 5],
}

/// What one [`KaraStage`] passes to the next, for all six block products.
///
/// Stage `s` owns columns `s..s + 4` of each block product in `win` (window
/// position `j` is column `s + j`). After its products, column `s` is
/// complete and moves to `done`, which fills from the top, and the window
/// moves up one column.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct KaraIo {
    /// Operand rows.
    pub rows: [KaraRow; 6],
    /// Column sums in progress.
    pub win: [[s40; 5]; 6],
    /// Finished columns, oldest (column 0) at index 0 after five stages.
    pub done: [[s40; 5]; 6],
}

/// One multiply-accumulate stage of all six block products (30 DSPs).
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct KaraStage {
    /// The stage's output (data only: validity rides beside the pipeline).
    regs: DFF<KaraIo>,
}

/// Payload registers need no reset.
impl Default for KaraStage {
    fn default() -> Self {
        Self { regs: DFF::resetless() }
    }
}

/// Port types: a stage passes a [`KaraIo`] down the chain.
impl SynchronousIO for KaraStage {
    type I = KaraIo;
    type O = KaraIo;
    type Kernel = kara_stage_kernel;
}

/// State transition for [`KaraStage`]: `win[j] += x[0] * y[j]` (one DSP each,
/// an exact `18 x 18` signed product), then retire column 0 and shift.
#[kernel]
pub fn kara_stage_kernel(_cr: ClockReset, i: KaraIo, q: KaraStageQ) -> (KaraIo, KaraStageD) {
    let mut o = i;
    for m in 0..6 {
        let x = i.rows[m].x[0];
        let mut win = i.win[m];
        for j in 0..5 {
            let p: s36 = x.xmul(i.rows[m].y[j]).as_signed_bits();
            win[j] = i.win[m][j] + p.resize::<40>();
        }
        // Column s is complete: it enters `done` at the top, the older
        // columns move down, and the window moves up one column.
        let mut done = i.done[m];
        for j in 0..4 {
            done[j] = i.done[m][j + 1];
        }
        done[4] = win[0];
        let mut next = [s40(0); 5];
        for j in 0..4 {
            next[j] = win[j + 1];
        }
        let mut x_next = [s18(0); 5];
        for j in 0..4 {
            x_next[j] = i.rows[m].x[j + 1];
        }
        o.rows[m].x = x_next;
        o.win[m] = next;
        o.done[m] = done;
    }
    (q.regs, KaraStageD { regs: o })
}

/// Registers of [`FieldMulKara`] outside the stages and the normalizer.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct KaraData {
    /// Edge 1: captured factors.
    a0: [b17; 15],
    /// Edge 1.
    b0: [b17; 15],
    /// Edge 2: the six operand rows (zeroed sums).
    rows: KaraIo,
    /// Edge 8: `S = P00 + P11`, `T = P11 + P22`, and the terms still needed
    /// (`P00`, `P22`, `D01`, `D02`, `D12`), nine columns each.
    sum8: [[s42; 9]; 7],
    /// Edge 9: `G0, G1, G2', G3, G4` and `D02`.
    sum9: [[s42; 9]; 6],
    /// Edge 10: `G0..G4`.
    g: [[s42; 9]; 5],
    /// Edge 11: product columns `C_0..C_28`.
    cols: [b39; 29],
    /// Edge 12: folded columns, the normalizer input.
    folded: [b43; 15],
    /// Edges 19..23: the normalized result, delayed.
    delay: [[b17; 15]; 5],
}

/// Validity and tags, the only registers that reset.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct KaraCtl {
    /// `valid[s]`: a request was captured `s + 1` edges ago.
    valid: [bool; 23],
    /// Tags, aligned with `valid`.
    tag: [b16; 23],
}

/// Initiation-interval-one, 150-DSP canonical field multiplier (see the
/// module documentation).
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
#[rhdl(dq_no_prefix)]
pub struct FieldMulKara {
    /// Valid/tag delay line (reset).
    ctl: DFF<KaraCtl>,
    /// Datapath registers (no reset).
    data: DFF<KaraData>,
    /// The five multiply-accumulate stages.
    stages: [KaraStage; 5],
    /// Carry normalization and final reduction (six stages).
    norm: MulNorm,
}

/// Resets the valid/tag line; the datapath needs no reset.
impl Default for FieldMulKara {
    fn default() -> Self {
        assert!(MUL_LATENCY == 23);
        Self {
            ctl: DFF::new(KaraCtl { valid: [false; 23], tag: [b16(0); 23] }),
            data: DFF::resetless(),
            stages: std::array::from_fn(|_| KaraStage::default()),
            norm: MulNorm::default(),
        }
    }
}

/// Port types: [`FieldMulIn`] in, [`FieldMulOut`] out, as for
/// [`FieldMulPar`](super::fe17::FieldMulPar).
impl SynchronousIO for FieldMulKara {
    type I = FieldMulIn;
    type O = FieldMulOut;
    type Kernel = field_mul_kara_kernel;
}

/// A 17-bit digit as a non-negative 18-bit signed operand.
#[kernel]
pub fn digit_s18(x: b17) -> s18 {
    x.resize::<18>().as_signed()
}

/// `19 x` for a product column (`16x + 2x + x`).
#[kernel]
pub fn times19_col(x: b39) -> b43 {
    let w = x.resize::<43>();
    (w << 4) + (w << 1) + w
}

/// State transition for [`FieldMulKara`].
#[kernel]
pub fn field_mul_kara_kernel(_cr: ClockReset, i: FieldMulIn, q: Q) -> (FieldMulOut, D) {
    let c = q.ctl;
    let r = q.data;
    let mut nc = c;
    let mut n = r;
    nc.valid[0] = i.valid;
    nc.tag[0] = i.tag;
    for s in 1..23 {
        nc.valid[s] = c.valid[s - 1];
        nc.tag[s] = c.tag[s - 1];
    }
    // Edge 1: capture.
    n.a0 = i.a.d;
    n.b0 = i.b.d;
    // Edge 2: operand rows. Block u is digits 5u..5u+4. Rows 0..2 are the
    // diagonal products, rows 3..5 the differences (0,1), (0,2), (1,2).
    let mut rows = r.rows;
    for j in 0..5 {
        for u in 0..3 {
            rows.rows[u].x[j] = digit_s18(r.a0[5 * u + j]);
            rows.rows[u].y[j] = digit_s18(r.b0[5 * u + j]);
        }
        rows.rows[3].x[j] = digit_s18(r.a0[j]) - digit_s18(r.a0[5 + j]);
        rows.rows[3].y[j] = digit_s18(r.b0[j]) - digit_s18(r.b0[5 + j]);
        rows.rows[4].x[j] = digit_s18(r.a0[j]) - digit_s18(r.a0[10 + j]);
        rows.rows[4].y[j] = digit_s18(r.b0[j]) - digit_s18(r.b0[10 + j]);
        rows.rows[5].x[j] = digit_s18(r.a0[5 + j]) - digit_s18(r.a0[10 + j]);
        rows.rows[5].y[j] = digit_s18(r.b0[5 + j]) - digit_s18(r.b0[10 + j]);
    }
    rows.win = [[s40(0); 5]; 6];
    rows.done = [[s40(0); 5]; 6];
    n.rows = rows;
    // Edges 3..7 are the stages. Their output: columns 0..4 in `done`,
    // columns 5..8 in `win[0..3]`.
    let st = q.stages[4];
    let mut p = [[s42(0); 9]; 6];
    for m in 0..6 {
        for k in 0..5 {
            p[m][k] = st.done[m][k].resize::<42>();
        }
        for k in 0..4 {
            p[m][5 + k] = st.win[m][k].resize::<42>();
        }
    }
    // Edge 8: S, T and the five terms still needed.
    for k in 0..9 {
        n.sum8[0][k] = p[0][k] + p[1][k];
        n.sum8[1][k] = p[1][k] + p[2][k];
        n.sum8[2][k] = p[0][k];
        n.sum8[3][k] = p[2][k];
        n.sum8[4][k] = p[3][k];
        n.sum8[5][k] = p[4][k];
        n.sum8[6][k] = p[5][k];
    }
    // Edge 9: G0, G1, G2' = S + P22, G3, G4, and D02 for edge 10.
    for k in 0..9 {
        n.sum9[0][k] = r.sum8[2][k];
        n.sum9[1][k] = r.sum8[0][k] - r.sum8[4][k];
        n.sum9[2][k] = r.sum8[0][k] + r.sum8[3][k];
        n.sum9[3][k] = r.sum8[1][k] - r.sum8[6][k];
        n.sum9[4][k] = r.sum8[3][k];
        n.sum9[5][k] = r.sum8[5][k];
    }
    // Edge 10: G2 = G2' - D02.
    for k in 0..9 {
        n.g[0][k] = r.sum9[0][k];
        n.g[1][k] = r.sum9[1][k];
        n.g[2][k] = r.sum9[2][k] - r.sum9[5][k];
        n.g[3][k] = r.sum9[3][k];
        n.g[4][k] = r.sum9[4][k];
    }
    // Edge 11: column t = 5u + s gets G_u[s] and the tail G_{u-1}[s + 5]
    // (columns 25..28 are G4's tail alone). Each sum is a true product
    // column, so non-negative and below 2^38.
    let mut cv = [s42(0); 29];
    for u in 0..5 {
        for s in 0..5 {
            cv[5 * u + s] = r.g[u][s];
        }
    }
    for u in 1..5 {
        for s in 0..4 {
            cv[5 * u + s] = cv[5 * u + s] + r.g[u - 1][s + 5];
        }
    }
    for s in 0..4 {
        cv[25 + s] = r.g[4][s + 5];
    }
    for t in 0..29 {
        n.cols[t] = cv[t].as_unsigned().resize::<39>();
    }
    // Edge 12: fold columns 15..28 onto 0..13 with the factor 19.
    for k in 0..14 {
        n.folded[k] = r.cols[k].resize::<43>() + times19_col(r.cols[k + 15]);
    }
    n.folded[14] = r.cols[14].resize::<43>();
    // Edges 13..18: the normalizer. Edges 19..23: delay.
    n.delay[0] = q.norm;
    for s in 1..5 {
        n.delay[s] = r.delay[s - 1];
    }
    let d = D { ctl: nc, data: n, stages: [r.rows, q.stages[0], q.stages[1], q.stages[2], q.stages[3]], norm: r.folded };
    let out = FieldMulOut { valid: c.valid[22], r: Fe17 { d: r.delay[4] }, tag: c.tag[22] };
    (out, d)
}

/// Cycle-level tests against the host model and the 225-DSP unit.
#[cfg(test)]
mod tests {
    use super::*;
    use crate::fe17::FieldMulPar;
    use crate::host::Fp;
    use crate::simulation::CycleSim;

    /// Edge cases and pseudo-random elements (fixed seed).
    fn sample(n: usize) -> Vec<Fp> {
        let mut s = 0x2545_f491_4f6c_dd1du64;
        let mut next = || {
            s ^= s << 13;
            s ^= s >> 7;
            s ^= s << 17;
            s
        };
        // 0, 1, p - 1, p - 19, and every digit at its maximum in one block
        // (the Karatsuba differences at their extremes).
        let max_block = |u: usize| {
            let mut d = [0u32; 15];
            for j in 0..5 {
                d[5 * u + j] = 0x1ffff;
            }
            Fp::from_digits17(&d)
        };
        let mut v = vec![
            Fp::ZERO,
            Fp::ONE,
            Fp::ZERO.sub(Fp::ONE),
            Fp::ZERO.sub(Fp([19, 0, 0, 0])),
            max_block(0),
            max_block(1),
            max_block(2),
        ];
        while v.len() < n {
            let bytes: [u8; 32] = std::array::from_fn(|_| next() as u8);
            v.push(Fp::from_bytes(&bytes));
        }
        v
    }

    /// One request per clock, every pair checked by tag against [`Fp`] and
    /// against [`FieldMulPar`] cycle for cycle (same latency, same outputs).
    #[test]
    fn kara_matches_host_and_the_225_dsp_unit() {
        let xs = sample(48);
        let pairs: Vec<(Fp, Fp)> = xs.iter().flat_map(|a| xs.iter().take(10).map(move |b| (*a, *b))).collect();
        let mut kara = CycleSim::new(FieldMulKara::default());
        let mut par = CycleSim::new(FieldMulPar::default());
        let mut got = 0;
        for cycle in 0..pairs.len() + 40 {
            // A gap every seventh cycle, so idle slots pass through too.
            let (valid, a, b) = match pairs.get(cycle) {
                Some((a, b)) if cycle % 7 != 3 => (true, Fe17::from_fp(*a), Fe17::from_fp(*b)),
                _ => (false, Fe17::zero(), Fe17::zero()),
            };
            let input = FieldMulIn { valid, a, b, tag: b16((cycle & 0xffff) as u128) };
            let k = kara.tick(input);
            let p = par.tick(input);
            assert_eq!(k.valid, p.valid, "cycle {cycle}: valid");
            if k.valid {
                assert_eq!(k.tag, p.tag, "cycle {cycle}: tag");
                let idx = k.tag.raw() as usize;
                let (a, b) = pairs[idx];
                assert_eq!(k.r.to_fp(), a.mul(b), "pair {idx}");
                assert_eq!(k.r, p.r, "pair {idx}: same digits as FieldMulPar");
                got += 1;
            }
        }
        assert_eq!(got, (0..pairs.len()).filter(|c| c % 7 != 3).count());
    }

    /// The unit lowers to Verilog.
    #[test]
    fn kara_lowers_to_verilog() -> Result<(), RHDLError> {
        let text = FieldMulKara::default().descriptor("field_mul_kara".into())?.hdl_unchecked()?.modules.pretty();
        assert!(text.contains("module field_mul_kara"));
        Ok(())
    }
}