rhdl_ed25519_fast_core/
field_parallel.rs

1//! Fully pipelined arithmetic modulo `2^255 - 19`.
2//!
3//! Values use five little-endian radix-`2^51` limbs at module boundaries. Each
4//! limb product is a reusable six-stage cell containing six independent
5//! `26 x 17` multiplies. Zero-extending these operands fits the DSP48E2's
6//! signed `27 x 18` multiplier. Five cells form a row and five rows form the
7//! complete 150-multiply matrix. This hierarchy keeps RHDL compilation bounded while
8//! exposing the same DSP-level parallelism as the high-throughput datapath.
9
10use rhdl::prelude::*;
11use rhdl_fpga::core::dff::DFF;
12
13/// Canonical field element in five little-endian radix-`2^51` limbs.
14#[derive(Copy, Clone, Debug, PartialEq, Digital)]
15pub struct FieldElement51 {
16    /// Limbs zero through four, least significant first.
17    pub limbs: [b51; 5],
18}
19
20impl FieldElement51 {
21    /// The additive identity.
22    pub fn zero() -> Self {
23        Self { limbs: [b51(0); 5] }
24    }
25
26    /// The multiplicative identity.
27    pub fn one() -> Self {
28        let mut value = Self::zero();
29        value.limbs[0] = b51(1);
30        value
31    }
32}
33
34/// Decode four little-endian words into radix-`2^51` limbs.
35///
36/// Bit 255 is ignored so this function can directly consume compressed
37/// Edwards-Y encodings after the caller records the sign bit.
38#[kernel]
39pub fn field_from_words_kernel(words: [b64; 4]) -> FieldElement51 {
40    FieldElement51 {
41        limbs: [
42            words[0].resize::<51>(),
43            ((words[0] >> 51).resize::<51>() | (words[1].resize::<51>() << 13)),
44            ((words[1] >> 38).resize::<51>() | (words[2].resize::<51>() << 26)),
45            ((words[2] >> 25).resize::<51>() | (words[3].resize::<51>() << 39)),
46            (words[3] >> 12).resize::<51>(),
47        ],
48    }
49}
50
51/// Encode canonical radix-`2^51` limbs as four little-endian words.
52#[kernel]
53pub fn field_to_words_kernel(value: FieldElement51) -> [b64; 4] {
54    [
55        value.limbs[0].resize::<64>() | (value.limbs[1].resize::<64>() << 51),
56        (value.limbs[1] >> 13).resize::<64>() | (value.limbs[2].resize::<64>() << 38),
57        (value.limbs[2] >> 26).resize::<64>() | (value.limbs[3].resize::<64>() << 25),
58        (value.limbs[3] >> 39).resize::<64>() | (value.limbs[4].resize::<64>() << 12),
59    ]
60}
61
62/// Return true when two canonical field elements are equal.
63#[kernel]
64pub fn field_eq_kernel(a: FieldElement51, b: FieldElement51) -> bool {
65    a.limbs[0] == b.limbs[0]
66        && a.limbs[1] == b.limbs[1]
67        && a.limbs[2] == b.limbs[2]
68        && a.limbs[3] == b.limbs[3]
69        && a.limbs[4] == b.limbs[4]
70}
71
72/// Input transaction for [`FieldMulPipe`].
73#[derive(Copy, Clone, Debug, PartialEq, Digital)]
74pub struct FieldMulIn {
75    /// Marks `a` and `b` valid in this cycle.
76    pub valid: bool,
77    /// First canonical factor.
78    pub a: FieldElement51,
79    /// Second canonical factor.
80    pub b: FieldElement51,
81}
82
83/// Output transaction from [`FieldMulPipe`].
84#[derive(Copy, Clone, Debug, PartialEq, Digital)]
85pub struct FieldMulOut {
86    /// Marks [`Self::result`] valid in this cycle.
87    pub valid: bool,
88    /// Canonical product modulo `2^255 - 19`.
89    pub result: FieldElement51,
90}
91
92#[derive(Copy, Clone, Debug, PartialEq, Digital)]
93#[doc(hidden)]
94pub struct Mul51CellIn {
95    a: b51,
96    b: b51,
97}
98
99#[derive(Copy, Clone, Debug, PartialEq, Digital)]
100#[doc(hidden)]
101pub struct Mul51CellOut {
102    product: b105,
103}
104
105#[derive(Copy, Clone, Debug, PartialEq, Digital)]
106#[doc(hidden)]
107pub struct Mul51CellRegs {
108    a_part: [b26; 2],
109    b_part: [b17; 3],
110    partial: [[b43; 3]; 2],
111    row_low: [b60; 2],
112    row_high: [b43; 2],
113    row_product: [b77; 2],
114    product: b105,
115    limb_product: b105,
116}
117
118fn cell_reset() -> Mul51CellRegs {
119    Mul51CellRegs {
120        a_part: [b26(0); 2],
121        b_part: [b17(0); 3],
122        partial: [[b43(0); 3]; 2],
123        row_low: [b60(0); 2],
124        row_high: [b43(0); 2],
125        row_product: [b77(0); 2],
126        product: b105(0),
127        limb_product: b105(0),
128    }
129}
130
131#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
132#[doc(hidden)]
133pub struct Mul51Cell {
134    regs: DFF<Mul51CellRegs>,
135}
136
137impl Default for Mul51Cell {
138    fn default() -> Self {
139        Self {
140            regs: DFF::new(cell_reset()),
141        }
142    }
143}
144
145impl SynchronousIO for Mul51Cell {
146    type I = Mul51CellIn;
147    type O = Mul51CellOut;
148    type Kernel = mul51_cell_kernel;
149}
150
151#[kernel]
152#[doc(hidden)]
153pub fn mul51_cell_kernel(
154    _cr: ClockReset,
155    i: Mul51CellIn,
156    q: Mul51CellQ,
157) -> (Mul51CellOut, Mul51CellD) {
158    let r = q.regs;
159    let mut n = r;
160    n.a_part = [i.a.resize::<26>(), (i.a >> 26).resize::<26>()];
161    n.b_part = [
162        i.b.resize::<17>(),
163        (i.b >> 17).resize::<17>(),
164        (i.b >> 34).resize::<17>(),
165    ];
166    for a_part in 0..2 {
167        for b_part in 0..3 {
168            n.partial[a_part][b_part] =
169                r.a_part[a_part].resize::<43>() * r.b_part[b_part].resize::<43>();
170        }
171        // Each row is a 26-bit digit times a 51-bit number, hence < 2^77.
172        n.row_low[a_part] =
173            r.partial[a_part][0].resize::<60>() + (r.partial[a_part][1].resize::<60>() << 17);
174        n.row_high[a_part] = r.partial[a_part][2];
175        n.row_product[a_part] =
176            r.row_low[a_part].resize::<77>() + (r.row_high[a_part].resize::<77>() << 34);
177    }
178    n.product = r.row_product[0].resize::<105>() + (r.row_product[1].resize::<105>() << 26);
179    // Keep the six-edge cell contract and all downstream valid/tag delays.
180    n.limb_product = r.product;
181    (
182        Mul51CellOut {
183            product: r.limb_product,
184        },
185        Mul51CellD { regs: n },
186    )
187}
188
189#[derive(Copy, Clone, Debug, PartialEq, Digital)]
190#[doc(hidden)]
191pub struct Mul51RowIn {
192    a: b51,
193    b: [b51; 5],
194}
195
196#[derive(Copy, Clone, Debug, PartialEq, Digital)]
197#[doc(hidden)]
198pub struct Mul51RowOut {
199    products: [b105; 5],
200}
201
202#[derive(Clone, Debug, Synchronous, SynchronousDQ, Default)]
203#[doc(hidden)]
204pub struct Mul51Row {
205    cell0: Mul51Cell,
206    cell1: Mul51Cell,
207    cell2: Mul51Cell,
208    cell3: Mul51Cell,
209    cell4: Mul51Cell,
210}
211
212impl SynchronousIO for Mul51Row {
213    type I = Mul51RowIn;
214    type O = Mul51RowOut;
215    type Kernel = mul51_row_kernel;
216}
217
218#[kernel]
219#[doc(hidden)]
220pub fn mul51_row_kernel(_cr: ClockReset, i: Mul51RowIn, q: Mul51RowQ) -> (Mul51RowOut, Mul51RowD) {
221    let output = Mul51RowOut {
222        products: [
223            q.cell0.product,
224            q.cell1.product,
225            q.cell2.product,
226            q.cell3.product,
227            q.cell4.product,
228        ],
229    };
230    let mut d = Mul51RowD::dont_care();
231    d.cell0 = Mul51CellIn { a: i.a, b: i.b[0] };
232    d.cell1 = Mul51CellIn { a: i.a, b: i.b[1] };
233    d.cell2 = Mul51CellIn { a: i.a, b: i.b[2] };
234    d.cell3 = Mul51CellIn { a: i.a, b: i.b[3] };
235    d.cell4 = Mul51CellIn { a: i.a, b: i.b[4] };
236    (output, d)
237}
238
239#[derive(Copy, Clone, Debug, PartialEq, Digital)]
240#[doc(hidden)]
241pub struct FieldMulRegs {
242    valid: [bool; 17],
243    coefficient_pair0: [b110; 5],
244    coefficient_pair1: [b110; 5],
245    coefficient_single: [b109; 5],
246    coefficient_four: [b111; 5],
247    coefficient_single_q: [b109; 5],
248    coefficient_pipe: [b111; 5],
249    carry_first: [[b111; 5]; 4],
250    carry_second: [[b52; 5]; 4],
251}
252
253fn multiplier_reset() -> FieldMulRegs {
254    FieldMulRegs {
255        valid: [false; 17],
256        coefficient_pair0: [b110(0); 5],
257        coefficient_pair1: [b110(0); 5],
258        coefficient_single: [b109(0); 5],
259        coefficient_four: [b111(0); 5],
260        coefficient_single_q: [b109(0); 5],
261        coefficient_pipe: [b111(0); 5],
262        carry_first: [[b111(0); 5]; 4],
263        carry_second: [[b52(0); 5]; 4],
264    }
265}
266
267/// Seventeen-stage, initiation-interval-one field multiplier.
268///
269/// One transaction may enter every cycle. The fixed 17-cycle latency consists
270/// of six limb-product stages, three coefficient stages, and eight carry stages.
271#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
272#[rhdl(dq_no_prefix)]
273pub struct FieldMulPipe {
274    regs: DFF<FieldMulRegs>,
275    row0: Mul51Row,
276    row1: Mul51Row,
277    row2: Mul51Row,
278    row3: Mul51Row,
279    row4: Mul51Row,
280}
281
282impl Default for FieldMulPipe {
283    fn default() -> Self {
284        Self {
285            regs: DFF::new(multiplier_reset()),
286            row0: Mul51Row::default(),
287            row1: Mul51Row::default(),
288            row2: Mul51Row::default(),
289            row3: Mul51Row::default(),
290            row4: Mul51Row::default(),
291        }
292    }
293}
294
295impl SynchronousIO for FieldMulPipe {
296    type I = FieldMulIn;
297    type O = FieldMulOut;
298    type Kernel = field_mul_kernel;
299}
300
301#[kernel]
302fn weighted(value: b105, wrap: bool) -> b109 {
303    let wide = value.resize::<109>();
304    if wrap {
305        (wide << 4) + (wide << 1) + wide
306    } else {
307        wide
308    }
309}
310
311#[kernel]
312fn first_carry_step(input: [b111; 5], limb: b3) -> [b111; 5] {
313    let mut output = input;
314    let current = input[limb].resize::<112>();
315    output[limb] = current.resize::<51>().resize::<111>();
316    if limb == b3(4) {
317        output[0] = input[0] + ((current >> 51).resize::<111>() * b111(19));
318    } else {
319        let next = limb + b3(1);
320        output[next] = input[next] + (current >> 51).resize::<111>();
321    }
322    output
323}
324
325#[kernel]
326fn second_carry_step(input: [b52; 5], limb: b3) -> [b52; 5] {
327    let mut output = input;
328    let carry = input[limb] >> 51;
329    output[limb] = input[limb].resize::<51>().resize::<52>();
330    if limb == b3(4) {
331        output[0] =
332            input[0].resize::<51>().resize::<52>() + if carry != b52(0) { b52(19) } else { b52(0) };
333    } else {
334        let next = limb + b3(1);
335        output[next] = input[next].resize::<51>().resize::<52>() + carry;
336    }
337    output
338}
339
340#[kernel]
341fn canonicalize(limbs: [b52; 5]) -> FieldElement51 {
342    let max = b51(0x7ffffffffffff);
343    let low = limbs[0].resize::<51>();
344    let high_ones = limbs[1].resize::<51>() == max
345        && limbs[2].resize::<51>() == max
346        && limbs[3].resize::<51>() == max
347        && limbs[4].resize::<51>() == max
348        && (low >> 5) == b51(0x3fffffffffff);
349    let low_five = low.resize::<5>();
350    let low_ge_13 = (low_five & b5(0x10)) != b5(0)
351        || ((low_five & b5(0x0c)) == b5(0x0c) && (low_five & b5(0x03)) != b5(0));
352    if high_ones && low_ge_13 {
353        let corrected = low_five.resize::<6>() + b6(19);
354        FieldElement51 {
355            limbs: [
356                corrected.resize::<5>().resize::<51>(),
357                b51(0),
358                b51(0),
359                b51(0),
360                b51(0),
361            ],
362        }
363    } else {
364        FieldElement51 {
365            limbs: [
366                limbs[0].resize::<51>(),
367                limbs[1].resize::<51>(),
368                limbs[2].resize::<51>(),
369                limbs[3].resize::<51>(),
370                limbs[4].resize::<51>(),
371            ],
372        }
373    }
374}
375
376/// State transition for [`FieldMulPipe`].
377#[kernel]
378pub fn field_mul_kernel(_cr: ClockReset, i: FieldMulIn, q: Q) -> (FieldMulOut, D) {
379    let products = [
380        q.row0.products,
381        q.row1.products,
382        q.row2.products,
383        q.row3.products,
384        q.row4.products,
385    ];
386    let r = q.regs;
387    let mut n = r;
388    n.valid[0] = i.valid;
389    for stage in 1..17 {
390        n.valid[stage] = r.valid[stage - 1];
391    }
392
393    n.coefficient_pair0[0] =
394        (weighted(products[0][0], false) + weighted(products[1][4], true)).resize::<110>();
395    n.coefficient_pair1[0] =
396        (weighted(products[2][3], true) + weighted(products[3][2], true)).resize::<110>();
397    n.coefficient_single[0] = weighted(products[4][1], true);
398    n.coefficient_pair0[1] =
399        (weighted(products[0][1], false) + weighted(products[1][0], false)).resize::<110>();
400    n.coefficient_pair1[1] =
401        (weighted(products[2][4], true) + weighted(products[3][3], true)).resize::<110>();
402    n.coefficient_single[1] = weighted(products[4][2], true);
403    n.coefficient_pair0[2] =
404        (weighted(products[0][2], false) + weighted(products[1][1], false)).resize::<110>();
405    n.coefficient_pair1[2] =
406        (weighted(products[2][0], false) + weighted(products[3][4], true)).resize::<110>();
407    n.coefficient_single[2] = weighted(products[4][3], true);
408    n.coefficient_pair0[3] =
409        (weighted(products[0][3], false) + weighted(products[1][2], false)).resize::<110>();
410    n.coefficient_pair1[3] =
411        (weighted(products[2][1], false) + weighted(products[3][0], false)).resize::<110>();
412    n.coefficient_single[3] = weighted(products[4][4], true);
413    n.coefficient_pair0[4] =
414        (weighted(products[0][4], false) + weighted(products[1][3], false)).resize::<110>();
415    n.coefficient_pair1[4] =
416        (weighted(products[2][2], false) + weighted(products[3][1], false)).resize::<110>();
417    n.coefficient_single[4] = weighted(products[4][0], false);
418    for limb in 0..5 {
419        n.coefficient_four[limb] =
420            r.coefficient_pair0[limb].resize::<111>() + r.coefficient_pair1[limb].resize::<111>();
421        n.coefficient_single_q[limb] = r.coefficient_single[limb];
422        n.coefficient_pipe[limb] =
423            r.coefficient_four[limb] + r.coefficient_single_q[limb].resize::<111>();
424    }
425    let first0 = r.coefficient_pipe[0].resize::<112>();
426    let first1 = r.coefficient_pipe[1].resize::<112>() + (first0 >> 51);
427    n.carry_first[0] = [
428        first0.resize::<51>().resize::<111>(),
429        first1.resize::<51>().resize::<111>(),
430        r.coefficient_pipe[2] + (first1 >> 51).resize::<111>(),
431        r.coefficient_pipe[3],
432        r.coefficient_pipe[4],
433    ];
434    n.carry_first[1] = first_carry_step(r.carry_first[0], b3(2));
435    n.carry_first[2] = first_carry_step(r.carry_first[1], b3(3));
436    n.carry_first[3] = first_carry_step(r.carry_first[2], b3(4));
437    let second0 = r.carry_first[3][0].resize::<58>();
438    let second1 =
439        r.carry_first[3][1].resize::<51>().resize::<52>() + (second0 >> 51).resize::<52>();
440    n.carry_second[0] = [
441        second0.resize::<51>().resize::<52>(),
442        second1.resize::<51>().resize::<52>(),
443        r.carry_first[3][2].resize::<51>().resize::<52>() + (second1 >> 51),
444        r.carry_first[3][3].resize::<51>().resize::<52>(),
445        r.carry_first[3][4].resize::<51>().resize::<52>(),
446    ];
447    n.carry_second[1] = second_carry_step(r.carry_second[0], b3(2));
448    n.carry_second[2] = second_carry_step(r.carry_second[1], b3(3));
449    n.carry_second[3] = second_carry_step(r.carry_second[2], b3(4));
450
451    let output = FieldMulOut {
452        valid: r.valid[16],
453        result: canonicalize(r.carry_second[3]),
454    };
455    let mut d = D::dont_care();
456    d.regs = n;
457    d.row0 = Mul51RowIn {
458        a: i.a.limbs[0],
459        b: i.b.limbs,
460    };
461    d.row1 = Mul51RowIn {
462        a: i.a.limbs[1],
463        b: i.b.limbs,
464    };
465    d.row2 = Mul51RowIn {
466        a: i.a.limbs[2],
467        b: i.b.limbs,
468    };
469    d.row3 = Mul51RowIn {
470        a: i.a.limbs[3],
471        b: i.b.limbs,
472    };
473    d.row4 = Mul51RowIn {
474        a: i.a.limbs[4],
475        b: i.b.limbs,
476    };
477    (output, d)
478}
479
480/// Input transaction for [`FieldAddSubPipe`].
481#[derive(Copy, Clone, Debug, PartialEq, Digital)]
482pub struct FieldAddSubIn {
483    /// Marks this operation valid.
484    pub valid: bool,
485    /// Selects `a - b`; otherwise computes `a + b`.
486    pub subtract: bool,
487    /// Left operand.
488    pub a: FieldElement51,
489    /// Right operand.
490    pub b: FieldElement51,
491}
492
493/// Output transaction from [`FieldAddSubPipe`].
494#[derive(Copy, Clone, Debug, PartialEq, Digital)]
495pub struct FieldAddSubOut {
496    /// Marks [`Self::result`] valid.
497    pub valid: bool,
498    /// Canonical modular sum or difference.
499    pub result: FieldElement51,
500}
501
502#[derive(Copy, Clone, Debug, PartialEq, Digital)]
503struct AddSubStage1 {
504    subtract: bool,
505    lower: [b51; 4],
506    status: bool,
507    a_tail: [b51; 3],
508    b_tail: [b51; 3],
509}
510
511#[derive(Copy, Clone, Debug, PartialEq, Digital)]
512struct AddSubStage2 {
513    subtract: bool,
514    lower: [b51; 4],
515    status: bool,
516    a4: b51,
517    b4: b51,
518}
519
520#[derive(Copy, Clone, Debug, PartialEq, Digital)]
521struct AddSubStage3 {
522    subtract: bool,
523    correction: bool,
524    raw: [b51; 5],
525}
526
527#[derive(Copy, Clone, Debug, PartialEq, Digital)]
528#[doc(hidden)]
529pub struct FieldAddSubRegs {
530    valid: [bool; 4],
531    stage1: AddSubStage1,
532    stage2: AddSubStage2,
533    stage3: AddSubStage3,
534    result: FieldElement51,
535}
536
537fn addsub_reset() -> FieldAddSubRegs {
538    FieldAddSubRegs {
539        valid: [false; 4],
540        stage1: AddSubStage1 {
541            subtract: false,
542            lower: [b51(0); 4],
543            status: false,
544            a_tail: [b51(0); 3],
545            b_tail: [b51(0); 3],
546        },
547        stage2: AddSubStage2 {
548            subtract: false,
549            lower: [b51(0); 4],
550            status: false,
551            a4: b51(0),
552            b4: b51(0),
553        },
554        stage3: AddSubStage3 {
555            subtract: false,
556            correction: false,
557            raw: [b51(0); 5],
558        },
559        result: FieldElement51::zero(),
560    }
561}
562
563/// Four-stage modular adder/subtractor with one-operation-per-cycle issue.
564#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
565pub struct FieldAddSubPipe {
566    regs: DFF<FieldAddSubRegs>,
567}
568
569impl Default for FieldAddSubPipe {
570    fn default() -> Self {
571        Self {
572            regs: DFF::new(addsub_reset()),
573        }
574    }
575}
576
577impl SynchronousIO for FieldAddSubPipe {
578    type I = FieldAddSubIn;
579    type O = FieldAddSubOut;
580    type Kernel = field_addsub_kernel;
581}
582
583#[kernel]
584fn corrected_field(stage: AddSubStage3) -> FieldElement51 {
585    let base = b52(0x8000000000000);
586    let limbs = if !stage.correction {
587        stage.raw
588    } else if stage.subtract {
589        let d0 = stage.raw[0].resize::<52>() + base - b52(19);
590        let borrow0 = (d0 >> 51) == b52(0);
591        let d1 = stage.raw[1].resize::<52>() + base - if borrow0 { b52(1) } else { b52(0) };
592        let borrow1 = (d1 >> 51) == b52(0);
593        let d2 = stage.raw[2].resize::<52>() + base - if borrow1 { b52(1) } else { b52(0) };
594        let borrow2 = (d2 >> 51) == b52(0);
595        let d3 = stage.raw[3].resize::<52>() + base - if borrow2 { b52(1) } else { b52(0) };
596        let borrow3 = (d3 >> 51) == b52(0);
597        let d4 = stage.raw[4].resize::<52>() + base - if borrow3 { b52(1) } else { b52(0) };
598        [
599            d0.resize::<51>(),
600            d1.resize::<51>(),
601            d2.resize::<51>(),
602            d3.resize::<51>(),
603            d4.resize::<51>(),
604        ]
605    } else {
606        let s0 = stage.raw[0].resize::<52>() + b52(19);
607        let s1 = stage.raw[1].resize::<52>() + (s0 >> 51);
608        let s2 = stage.raw[2].resize::<52>() + (s1 >> 51);
609        let s3 = stage.raw[3].resize::<52>() + (s2 >> 51);
610        let s4 = stage.raw[4].resize::<52>() + (s3 >> 51);
611        [
612            s0.resize::<51>(),
613            s1.resize::<51>(),
614            s2.resize::<51>(),
615            s3.resize::<51>(),
616            s4.resize::<51>(),
617        ]
618    };
619    canonicalize([
620        limbs[0].resize::<52>(),
621        limbs[1].resize::<52>(),
622        limbs[2].resize::<52>(),
623        limbs[3].resize::<52>(),
624        limbs[4].resize::<52>(),
625    ])
626}
627
628/// Canonical field addition in a single combinational RHDL kernel.
629///
630/// Latency-sensitive datapaths should use [`FieldAddSubPipe`]. This helper is
631/// intended for registered scheduler preparation steps and equality logic.
632#[kernel]
633pub fn field_add_kernel(a: FieldElement51, b: FieldElement51) -> FieldElement51 {
634    let s0 = a.limbs[0].resize::<52>() + b.limbs[0].resize::<52>();
635    let s1 = a.limbs[1].resize::<52>() + b.limbs[1].resize::<52>() + (s0 >> 51);
636    let s2 = a.limbs[2].resize::<52>() + b.limbs[2].resize::<52>() + (s1 >> 51);
637    let s3 = a.limbs[3].resize::<52>() + b.limbs[3].resize::<52>() + (s2 >> 51);
638    let s4 = a.limbs[4].resize::<52>() + b.limbs[4].resize::<52>() + (s3 >> 51);
639    corrected_field(AddSubStage3 {
640        subtract: false,
641        correction: (s4 >> 51) != b52(0),
642        raw: [
643            s0.resize::<51>(),
644            s1.resize::<51>(),
645            s2.resize::<51>(),
646            s3.resize::<51>(),
647            s4.resize::<51>(),
648        ],
649    })
650}
651
652/// Canonical field subtraction in a single combinational RHDL kernel.
653#[kernel]
654pub fn field_sub_kernel(a: FieldElement51, b: FieldElement51) -> FieldElement51 {
655    let base = b52(0x8000000000000);
656    let d0 = a.limbs[0].resize::<52>() + base - b.limbs[0].resize::<52>();
657    let d1 = a.limbs[1].resize::<52>() + base
658        - b.limbs[1].resize::<52>()
659        - if (d0 >> 51) == b52(0) { b52(1) } else { b52(0) };
660    let d2 = a.limbs[2].resize::<52>() + base
661        - b.limbs[2].resize::<52>()
662        - if (d1 >> 51) == b52(0) { b52(1) } else { b52(0) };
663    let d3 = a.limbs[3].resize::<52>() + base
664        - b.limbs[3].resize::<52>()
665        - if (d2 >> 51) == b52(0) { b52(1) } else { b52(0) };
666    let d4 = a.limbs[4].resize::<52>() + base
667        - b.limbs[4].resize::<52>()
668        - if (d3 >> 51) == b52(0) { b52(1) } else { b52(0) };
669    corrected_field(AddSubStage3 {
670        subtract: true,
671        correction: (d4 >> 51) == b52(0),
672        raw: [
673            d0.resize::<51>(),
674            d1.resize::<51>(),
675            d2.resize::<51>(),
676            d3.resize::<51>(),
677            d4.resize::<51>(),
678        ],
679    })
680}
681
682/// Canonical additive inverse.
683#[kernel]
684pub fn field_neg_kernel(value: FieldElement51) -> FieldElement51 {
685    field_sub_kernel(FieldElement51 { limbs: [b51(0); 5] }, value)
686}
687
688/// State transition for [`FieldAddSubPipe`].
689#[kernel]
690pub fn field_addsub_kernel(
691    _cr: ClockReset,
692    i: FieldAddSubIn,
693    q: FieldAddSubPipeQ,
694) -> (FieldAddSubOut, FieldAddSubPipeD) {
695    let base = b52(0x8000000000000);
696    let r = q.regs;
697    let mut n = r;
698    n.valid = [i.valid, r.valid[0], r.valid[1], r.valid[2]];
699
700    n.stage1.subtract = i.subtract;
701    n.stage1.a_tail = [i.a.limbs[2], i.a.limbs[3], i.a.limbs[4]];
702    n.stage1.b_tail = [i.b.limbs[2], i.b.limbs[3], i.b.limbs[4]];
703    if i.subtract {
704        let d0 = i.a.limbs[0].resize::<52>() + base - i.b.limbs[0].resize::<52>();
705        let borrow0 = (d0 >> 51) == b52(0);
706        let d1 = i.a.limbs[1].resize::<52>() + base
707            - i.b.limbs[1].resize::<52>()
708            - if borrow0 { b52(1) } else { b52(0) };
709        n.stage1.lower[0] = d0.resize::<51>();
710        n.stage1.lower[1] = d1.resize::<51>();
711        n.stage1.status = (d1 >> 51) == b52(0);
712    } else {
713        let s0 = i.a.limbs[0].resize::<52>() + i.b.limbs[0].resize::<52>();
714        let s1 = i.a.limbs[1].resize::<52>() + i.b.limbs[1].resize::<52>() + (s0 >> 51);
715        n.stage1.lower[0] = s0.resize::<51>();
716        n.stage1.lower[1] = s1.resize::<51>();
717        n.stage1.status = (s1 >> 51) != b52(0);
718    }
719
720    n.stage2.subtract = r.stage1.subtract;
721    n.stage2.lower[0] = r.stage1.lower[0];
722    n.stage2.lower[1] = r.stage1.lower[1];
723    n.stage2.a4 = r.stage1.a_tail[2];
724    n.stage2.b4 = r.stage1.b_tail[2];
725    if r.stage1.subtract {
726        let d2 = r.stage1.a_tail[0].resize::<52>() + base
727            - r.stage1.b_tail[0].resize::<52>()
728            - if r.stage1.status { b52(1) } else { b52(0) };
729        let borrow2 = (d2 >> 51) == b52(0);
730        let d3 = r.stage1.a_tail[1].resize::<52>() + base
731            - r.stage1.b_tail[1].resize::<52>()
732            - if borrow2 { b52(1) } else { b52(0) };
733        n.stage2.lower[2] = d2.resize::<51>();
734        n.stage2.lower[3] = d3.resize::<51>();
735        n.stage2.status = (d3 >> 51) == b52(0);
736    } else {
737        let s2 = r.stage1.a_tail[0].resize::<52>()
738            + r.stage1.b_tail[0].resize::<52>()
739            + if r.stage1.status { b52(1) } else { b52(0) };
740        let s3 = r.stage1.a_tail[1].resize::<52>() + r.stage1.b_tail[1].resize::<52>() + (s2 >> 51);
741        n.stage2.lower[2] = s2.resize::<51>();
742        n.stage2.lower[3] = s3.resize::<51>();
743        n.stage2.status = (s3 >> 51) != b52(0);
744    }
745
746    n.stage3.subtract = r.stage2.subtract;
747    n.stage3.raw[0] = r.stage2.lower[0];
748    n.stage3.raw[1] = r.stage2.lower[1];
749    n.stage3.raw[2] = r.stage2.lower[2];
750    n.stage3.raw[3] = r.stage2.lower[3];
751    if r.stage2.subtract {
752        let d4 = r.stage2.a4.resize::<52>() + base
753            - r.stage2.b4.resize::<52>()
754            - if r.stage2.status { b52(1) } else { b52(0) };
755        n.stage3.raw[4] = d4.resize::<51>();
756        n.stage3.correction = (d4 >> 51) == b52(0);
757    } else {
758        let s4 = r.stage2.a4.resize::<52>()
759            + r.stage2.b4.resize::<52>()
760            + if r.stage2.status { b52(1) } else { b52(0) };
761        n.stage3.raw[4] = s4.resize::<51>();
762        n.stage3.correction = (s4 >> 51) != b52(0);
763    }
764    n.result = corrected_field(r.stage3);
765
766    (
767        FieldAddSubOut {
768            valid: r.valid[3],
769            result: r.result,
770        },
771        FieldAddSubPipeD { regs: n },
772    )
773}
774
775#[cfg(test)]
776mod tests {
777    use super::*;
778    use num_bigint::BigUint;
779    use std::iter;
780
781    fn limb_vectors() -> Vec<Mul51CellIn> {
782        let mask = (1u64 << 51) - 1;
783        let edges = [0, 1, (1 << 17) - 1, 1 << 26, (1 << 26) - 1, mask];
784        let mut values = Vec::new();
785        for a in edges {
786            for b in edges {
787                values.push(Mul51CellIn {
788                    a: b51(a as u128),
789                    b: b51(b as u128),
790                });
791            }
792        }
793        let mut state = 0x7a89_751d_6b35_93afu64;
794        for _ in 0..512 {
795            state ^= state << 13;
796            state ^= state >> 7;
797            state ^= state << 17;
798            let a = state & mask;
799            state = state.wrapping_mul(0x9e37_79b9_7f4a_7c15);
800            values.push(Mul51CellIn {
801                a: b51(a as u128),
802                b: b51((state & mask) as u128),
803            });
804        }
805        values
806    }
807
808    #[test]
809    fn asymmetric_cell_matches_u128_at_six_stages() {
810        let values = limb_vectors();
811        let mut regs = cell_reset();
812        let idle = Mul51CellIn {
813            a: b51(0),
814            b: b51(0),
815        };
816        for (cycle, input) in values
817            .iter()
818            .copied()
819            .chain(iter::repeat_n(idle, 6))
820            .enumerate()
821        {
822            let (output, next) =
823                mul51_cell_kernel(ClockReset::dont_care(), input, Mul51CellQ { regs });
824            if cycle >= 6 {
825                let expected = values[cycle - 6];
826                assert_eq!(
827                    output.product.raw(),
828                    expected.a.raw() * expected.b.raw(),
829                    "cycle {cycle}"
830                );
831            }
832            regs = next.regs;
833        }
834    }
835
836    #[test]
837    fn asymmetric_cell_rtl_matches_native() -> miette::Result<()> {
838        let cell = Mul51Cell::default();
839        let inputs = limb_vectors().into_iter().chain(iter::repeat_n(
840            Mul51CellIn {
841                a: b51(0),
842                b: b51(0),
843            },
844            8,
845        ));
846        let tb = cell
847            .run(inputs.with_reset(1).clock_pos_edge(100))
848            .collect::<SynchronousTestBench<_, _>>();
849        tb.rtl(&cell, &Default::default())?.run_iverilog()?;
850        tb.ntl(&cell, &Default::default())?.run_iverilog()?;
851        Ok(())
852    }
853
854    fn to_field(value: &BigUint) -> FieldElement51 {
855        let mask = (BigUint::from(1u8) << 51) - BigUint::from(1u8);
856        let mut limbs = [b51(0); 5];
857        for (index, limb) in limbs.iter_mut().enumerate() {
858            let digits = ((value >> (index * 51)) & &mask).to_u64_digits();
859            *limb = b51(digits.first().copied().unwrap_or(0) as u128);
860        }
861        FieldElement51 { limbs }
862    }
863
864    fn from_field(value: FieldElement51) -> BigUint {
865        value
866            .limbs
867            .iter()
868            .enumerate()
869            .fold(BigUint::from(0u8), |sum, (index, limb)| {
870                sum + (BigUint::from(limb.raw()) << (index * 51))
871            })
872    }
873
874    #[test]
875    fn pipeline_matches_big_integer_modular_products() {
876        let p = (BigUint::from(1u8) << 255) - BigUint::from(19u8);
877        let values: Vec<_> = (0u64..32)
878            .map(|index| {
879                let a = (BigUint::from(0x9e3779b97f4a7c15u64) * BigUint::from(index + 3)
880                    + (BigUint::from(index) << 190))
881                    % &p;
882                let b = (BigUint::from(0xd1b54a32d192ed03u64) * BigUint::from(index + 11)
883                    + (BigUint::from(index * 7 + 1) << 231))
884                    % &p;
885                (a, b)
886            })
887            .collect();
888        let inputs = values.iter().map(|(a, b)| FieldMulIn {
889            valid: true,
890            a: to_field(a),
891            b: to_field(b),
892        });
893        let idle = FieldMulIn {
894            valid: false,
895            a: FieldElement51::zero(),
896            b: FieldElement51::zero(),
897        };
898        let outputs: Vec<_> = FieldMulPipe::default()
899            .run(
900                iter::once(idle)
901                    .chain(inputs)
902                    .chain(iter::repeat_n(idle, 24))
903                    .with_reset(1)
904                    .clock_pos_edge(100),
905            )
906            .synchronous_sample()
907            .map(|sample| sample.output)
908            .filter(|output| output.valid)
909            .collect();
910        assert_eq!(outputs.len(), values.len());
911        for (output, (a, b)) in outputs.into_iter().zip(values) {
912            assert_eq!(from_field(output.result), (a * b) % &p);
913        }
914    }
915
916    #[test]
917    fn compiles_to_rhdl_netlist() -> miette::Result<()> {
918        FieldMulPipe::default()
919            .descriptor(ScopedName::top())?
920            .hdl()?;
921        FieldAddSubPipe::default()
922            .descriptor(ScopedName::top())?
923            .hdl()?;
924        Ok(())
925    }
926
927    #[test]
928    fn addsub_pipeline_matches_big_integer_arithmetic() {
929        let p = (BigUint::from(1u8) << 255) - BigUint::from(19u8);
930        let values: Vec<_> = (0u64..48)
931            .map(|index| {
932                let a = (BigUint::from(0x94d049bb133111ebu64) * BigUint::from(index + 17)
933                    + (BigUint::from(index * 5 + 2) << 225))
934                    % &p;
935                let b = (BigUint::from(0xbf58476d1ce4e5b9u64) * BigUint::from(index + 31)
936                    + (BigUint::from(index * 11 + 7) << 188))
937                    % &p;
938                (a, b, index & 1 == 1)
939            })
940            .collect();
941        let inputs = values.iter().map(|(a, b, subtract)| FieldAddSubIn {
942            valid: true,
943            subtract: *subtract,
944            a: to_field(a),
945            b: to_field(b),
946        });
947        let idle = FieldAddSubIn {
948            valid: false,
949            subtract: false,
950            a: FieldElement51::zero(),
951            b: FieldElement51::zero(),
952        };
953        let outputs: Vec<_> = FieldAddSubPipe::default()
954            .run(
955                iter::once(idle)
956                    .chain(inputs)
957                    .chain(iter::repeat_n(idle, 8))
958                    .with_reset(1)
959                    .clock_pos_edge(100),
960            )
961            .synchronous_sample()
962            .map(|sample| sample.output)
963            .filter(|output| output.valid)
964            .collect();
965        assert_eq!(outputs.len(), values.len());
966        for (output, (a, b, subtract)) in outputs.into_iter().zip(values) {
967            let expected = if subtract {
968                (a + &p - b) % &p
969            } else {
970                (a + b) % &p
971            };
972            assert_eq!(from_field(output.result), expected);
973        }
974    }
975}
rhdl_ed25519_fast_core/field_parallel.rs

rhdl_ed25519_fast_core/
field_parallel.rs
