rhdl_ed25519_fast_core/
point_compress.rs

1//! Parallel pair compression for extended Edwards points.
2//!
3//! One batch inversion converts two projective points to affine form. Fourteen
4//! contexts rotate through one initiation-interval-one field multiplier, hiding
5//! most of its 17-cycle latency. Pairing halves the inversion cost per signing
6//! request and keeps point encoding below the fixed-message signing budget.
7
8use rhdl::prelude::*;
9use rhdl_fpga::core::dff::DFF;
10
11use crate::{
12    field_parallel::{FieldElement51, FieldMulIn, FieldMulPipe},
13    multicomb::ExtendedPoint,
14};
15
16const ST_FREE: u128 = 0;
17const ST_READY: u128 = 1;
18const ST_WAIT: u128 = 2;
19
20/// Canonical compressed Edwards-Y encoding.
21#[derive(Copy, Clone, Debug, PartialEq, Digital)]
22pub struct CompressedPoint {
23    /// Little-endian 256-bit encoding; the top bit is the affine-X sign.
24    pub words: [b64; 4],
25}
26
27impl CompressedPoint {
28    /// All-zero placeholder used when an output is not valid.
29    pub fn zero() -> Self {
30        Self { words: [b64(0); 4] }
31    }
32}
33
34/// Two points accepted by [`PointCompressPair`].
35#[derive(Copy, Clone, Debug, PartialEq, Digital)]
36pub struct PointCompressPairIn {
37    /// Marks both points and the tag valid.
38    pub valid: bool,
39    /// First projective point.
40    pub first: ExtendedPoint,
41    /// Second projective point.
42    pub second: ExtendedPoint,
43    /// Caller-defined transaction tag.
44    pub tag: b16,
45}
46
47/// Flow control and compressed pair returned by [`PointCompressPair`].
48#[derive(Copy, Clone, Debug, PartialEq, Digital)]
49pub struct PointCompressPairOut {
50    /// High when a context is available for a new pair.
51    pub ready: bool,
52    /// High for one cycle when the compressed pair and tag are valid.
53    pub valid: bool,
54    /// Compressed first point.
55    pub first: CompressedPoint,
56    /// Compressed second point.
57    pub second: CompressedPoint,
58    /// Delayed caller tag.
59    pub tag: b16,
60    /// Number of occupied inversion contexts.
61    pub occupancy: b4,
62    /// Sticky completion-buffer overflow (always false in a single engine).
63    pub error: bool,
64}
65
66#[derive(Copy, Clone, Debug, PartialEq, Digital)]
67#[doc(hidden)]
68pub struct CompressControlContext {
69    state: b2,
70    tag: b16,
71    step: b5,
72    squares_left: b8,
73    after_square: b4,
74    first_sign: bool,
75    second_sign: bool,
76}
77
78#[derive(Copy, Clone, Debug, PartialEq, Digital)]
79#[doc(hidden)]
80pub struct CompressPoints {
81    first: ExtendedPoint,
82    second: ExtendedPoint,
83}
84
85#[derive(Copy, Clone, Debug, PartialEq, Digital)]
86#[doc(hidden)]
87pub struct CompressWork {
88    base: FieldElement51,
89    temp0: FieldElement51,
90    temp1: FieldElement51,
91    temp2: FieldElement51,
92    operand_a: FieldElement51,
93    operand_b: FieldElement51,
94}
95
96#[derive(Copy, Clone, Debug, PartialEq, Digital)]
97#[doc(hidden)]
98pub struct CompressContexts {
99    control: [CompressControlContext; 14],
100    points: [CompressPoints; 14],
101    work: [CompressWork; 14],
102}
103
104#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
105#[doc(hidden)]
106pub struct CompressPointStore {
107    first_x: DFF<[FieldElement51; 14]>,
108    first_y: DFF<[FieldElement51; 14]>,
109    first_z: DFF<[FieldElement51; 14]>,
110    first_t: DFF<[FieldElement51; 14]>,
111    second_x: DFF<[FieldElement51; 14]>,
112    second_y: DFF<[FieldElement51; 14]>,
113    second_z: DFF<[FieldElement51; 14]>,
114    second_t: DFF<[FieldElement51; 14]>,
115}
116
117impl Default for CompressPointStore {
118    fn default() -> Self {
119        let identity = ExtendedPoint::identity();
120        Self {
121            first_x: DFF::new([identity.x; 14]),
122            first_y: DFF::new([identity.y; 14]),
123            first_z: DFF::new([identity.z; 14]),
124            first_t: DFF::new([identity.t; 14]),
125            second_x: DFF::new([identity.x; 14]),
126            second_y: DFF::new([identity.y; 14]),
127            second_z: DFF::new([identity.z; 14]),
128            second_t: DFF::new([identity.t; 14]),
129        }
130    }
131}
132
133impl SynchronousIO for CompressPointStore {
134    type I = [CompressPoints; 14];
135    type O = [CompressPoints; 14];
136    type Kernel = compress_point_store_kernel;
137}
138
139#[kernel]
140#[doc(hidden)]
141pub fn compress_point_store_kernel(
142    _cr: ClockReset,
143    i: [CompressPoints; 14],
144    q: CompressPointStoreQ,
145) -> ([CompressPoints; 14], CompressPointStoreD) {
146    let mut output = [CompressPoints {
147        first: ExtendedPoint {
148            x: FieldElement51 { limbs: [b51(0); 5] },
149            y: FieldElement51 { limbs: [b51(0); 5] },
150            z: FieldElement51 { limbs: [b51(0); 5] },
151            t: FieldElement51 { limbs: [b51(0); 5] },
152        },
153        second: ExtendedPoint {
154            x: FieldElement51 { limbs: [b51(0); 5] },
155            y: FieldElement51 { limbs: [b51(0); 5] },
156            z: FieldElement51 { limbs: [b51(0); 5] },
157            t: FieldElement51 { limbs: [b51(0); 5] },
158        },
159    }; 14];
160    for context in 0..14 {
161        output[context] = CompressPoints {
162            first: ExtendedPoint {
163                x: q.first_x[context],
164                y: q.first_y[context],
165                z: q.first_z[context],
166                t: q.first_t[context],
167            },
168            second: ExtendedPoint {
169                x: q.second_x[context],
170                y: q.second_y[context],
171                z: q.second_z[context],
172                t: q.second_t[context],
173            },
174        };
175    }
176    let mut first_x = [FieldElement51 { limbs: [b51(0); 5] }; 14];
177    let mut first_y = first_x;
178    let mut first_z = first_x;
179    let mut first_t = first_x;
180    let mut second_x = first_x;
181    let mut second_y = first_x;
182    let mut second_z = first_x;
183    let mut second_t = first_x;
184    for context in 0..14 {
185        first_x[context] = i[context].first.x;
186        first_y[context] = i[context].first.y;
187        first_z[context] = i[context].first.z;
188        first_t[context] = i[context].first.t;
189        second_x[context] = i[context].second.x;
190        second_y[context] = i[context].second.y;
191        second_z[context] = i[context].second.z;
192        second_t[context] = i[context].second.t;
193    }
194    let mut d = CompressPointStoreD::dont_care();
195    d.first_x = first_x;
196    d.first_y = first_y;
197    d.first_z = first_z;
198    d.first_t = first_t;
199    d.second_x = second_x;
200    d.second_y = second_y;
201    d.second_z = second_z;
202    d.second_t = second_t;
203    (output, d)
204}
205
206#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
207#[doc(hidden)]
208pub struct CompressWorkStore {
209    base: DFF<[FieldElement51; 14]>,
210    temp0: DFF<[FieldElement51; 14]>,
211    temp1: DFF<[FieldElement51; 14]>,
212    temp2: DFF<[FieldElement51; 14]>,
213    operand_a: DFF<[FieldElement51; 14]>,
214    operand_b: DFF<[FieldElement51; 14]>,
215}
216
217impl Default for CompressWorkStore {
218    fn default() -> Self {
219        let zero = [FieldElement51::zero(); 14];
220        Self {
221            base: DFF::new(zero),
222            temp0: DFF::new(zero),
223            temp1: DFF::new(zero),
224            temp2: DFF::new(zero),
225            operand_a: DFF::new(zero),
226            operand_b: DFF::new(zero),
227        }
228    }
229}
230
231impl SynchronousIO for CompressWorkStore {
232    type I = [CompressWork; 14];
233    type O = [CompressWork; 14];
234    type Kernel = compress_work_store_kernel;
235}
236
237#[kernel]
238#[doc(hidden)]
239pub fn compress_work_store_kernel(
240    _cr: ClockReset,
241    i: [CompressWork; 14],
242    q: CompressWorkStoreQ,
243) -> ([CompressWork; 14], CompressWorkStoreD) {
244    let zero = FieldElement51 { limbs: [b51(0); 5] };
245    let mut output = [CompressWork {
246        base: zero,
247        temp0: zero,
248        temp1: zero,
249        temp2: zero,
250        operand_a: zero,
251        operand_b: zero,
252    }; 14];
253    let mut base = [zero; 14];
254    let mut temp0 = [zero; 14];
255    let mut temp1 = [zero; 14];
256    let mut temp2 = [zero; 14];
257    let mut operand_a = [zero; 14];
258    let mut operand_b = [zero; 14];
259    for context in 0..14 {
260        output[context] = CompressWork {
261            base: q.base[context],
262            temp0: q.temp0[context],
263            temp1: q.temp1[context],
264            temp2: q.temp2[context],
265            operand_a: q.operand_a[context],
266            operand_b: q.operand_b[context],
267        };
268        base[context] = i[context].base;
269        temp0[context] = i[context].temp0;
270        temp1[context] = i[context].temp1;
271        temp2[context] = i[context].temp2;
272        operand_a[context] = i[context].operand_a;
273        operand_b[context] = i[context].operand_b;
274    }
275    let mut d = CompressWorkStoreD::dont_care();
276    d.base = base;
277    d.temp0 = temp0;
278    d.temp1 = temp1;
279    d.temp2 = temp2;
280    d.operand_a = operand_a;
281    d.operand_b = operand_b;
282    (output, d)
283}
284
285fn reset_contexts() -> CompressContexts {
286    let zero = FieldElement51::zero();
287    let point = ExtendedPoint::identity();
288    CompressContexts {
289        control: [CompressControlContext {
290            state: b2(ST_FREE),
291            tag: b16(0),
292            step: b5(0),
293            squares_left: b8(0),
294            after_square: b4(0),
295            first_sign: false,
296            second_sign: false,
297        }; 14],
298        points: [CompressPoints {
299            first: point,
300            second: point,
301        }; 14],
302        work: [CompressWork {
303            base: zero,
304            temp0: zero,
305            temp1: zero,
306            temp2: zero,
307            operand_a: zero,
308            operand_b: zero,
309        }; 14],
310    }
311}
312
313/// Split context storage keeps generated reset literals and register banks
314/// small enough for ordinary RTL simulators.
315#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
316#[doc(hidden)]
317pub struct CompressContextStore {
318    control: DFF<[CompressControlContext; 14]>,
319    points: CompressPointStore,
320    work: CompressWorkStore,
321}
322
323impl Default for CompressContextStore {
324    fn default() -> Self {
325        let reset = reset_contexts();
326        Self {
327            control: DFF::new(reset.control),
328            points: CompressPointStore::default(),
329            work: CompressWorkStore::default(),
330        }
331    }
332}
333
334impl SynchronousIO for CompressContextStore {
335    type I = CompressContexts;
336    type O = CompressContexts;
337    type Kernel = compress_context_store_kernel;
338}
339
340#[kernel]
341#[doc(hidden)]
342pub fn compress_context_store_kernel(
343    _cr: ClockReset,
344    i: CompressContexts,
345    q: CompressContextStoreQ,
346) -> (CompressContexts, CompressContextStoreD) {
347    let output = CompressContexts {
348        control: q.control,
349        points: q.points,
350        work: q.work,
351    };
352    let mut d = CompressContextStoreD::dont_care();
353    d.control = i.control;
354    d.points = i.points;
355    d.work = i.work;
356    (output, d)
357}
358
359#[derive(Copy, Clone, Debug, PartialEq, Digital)]
360#[doc(hidden)]
361pub struct CompressScheduler {
362    free_fifo: [b4; 14],
363    free_read: b4,
364    free_write: b4,
365    free_count: b4,
366    issue_rr: b4,
367    issue_valid: [bool; 17],
368    issue_context: [b4; 17],
369}
370
371fn reset_scheduler() -> CompressScheduler {
372    CompressScheduler {
373        free_fifo: [
374            b4(0),
375            b4(1),
376            b4(2),
377            b4(3),
378            b4(4),
379            b4(5),
380            b4(6),
381            b4(7),
382            b4(8),
383            b4(9),
384            b4(10),
385            b4(11),
386            b4(12),
387            b4(13),
388        ],
389        free_read: b4(0),
390        free_write: b4(0),
391        free_count: b4(14),
392        issue_rr: b4(0),
393        issue_valid: [false; 17],
394        issue_context: [b4(0); 17],
395    }
396}
397
398/// Fourteen-context batch-inversion point compressor.
399#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
400#[rhdl(dq_no_prefix)]
401pub struct PointCompressPair {
402    scheduler: DFF<CompressScheduler>,
403    contexts: CompressContextStore,
404    multiplier: FieldMulPipe,
405}
406
407impl Default for PointCompressPair {
408    fn default() -> Self {
409        Self {
410            scheduler: DFF::new(reset_scheduler()),
411            contexts: CompressContextStore::default(),
412            multiplier: FieldMulPipe::default(),
413        }
414    }
415}
416
417impl SynchronousIO for PointCompressPair {
418    type I = PointCompressPairIn;
419    type O = PointCompressPairOut;
420    type Kernel = point_compress_pair_kernel;
421}
422
423#[kernel]
424fn next_context(value: b4) -> b4 {
425    if value == b4(13) {
426        b4(0)
427    } else {
428        value + b4(1)
429    }
430}
431
432#[kernel]
433fn context_index(start: b4, offset: b4) -> b4 {
434    let sum = start.resize::<5>() + offset.resize::<5>();
435    if sum >= b5(14) {
436        (sum - b5(14)).resize::<4>()
437    } else {
438        sum.resize::<4>()
439    }
440}
441
442#[kernel]
443fn compress_field(value: FieldElement51, sign: bool) -> CompressedPoint {
444    let limb0 = value.limbs[0].resize::<64>();
445    let limb1 = value.limbs[1].resize::<64>();
446    let limb2 = value.limbs[2].resize::<64>();
447    let limb3 = value.limbs[3].resize::<64>();
448    let limb4 = value.limbs[4].resize::<64>();
449    CompressedPoint {
450        words: [
451            limb0 | (limb1 << 51),
452            (limb1 >> 13) | (limb2 << 38),
453            (limb2 >> 26) | (limb3 << 25),
454            (limb3 >> 39) | (limb4 << 12) | if sign { b64(1) << 63 } else { b64(0) },
455        ],
456    }
457}
458
459/// State transition for [`PointCompressPair`].
460#[kernel]
461pub fn point_compress_pair_kernel(
462    _cr: ClockReset,
463    i: PointCompressPairIn,
464    q: Q,
465) -> (PointCompressPairOut, D) {
466    let r = q.scheduler;
467    let current = q.contexts;
468    let mut contexts = current;
469    let mut n = r;
470    let zero = FieldElement51 { limbs: [b51(0); 5] };
471    let mut output = PointCompressPairOut {
472        error: false,
473        ready: r.free_count != b4(0),
474        valid: false,
475        first: CompressedPoint { words: [b64(0); 4] },
476        second: CompressedPoint { words: [b64(0); 4] },
477        tag: b16(0),
478        occupancy: b4(14) - r.free_count,
479    };
480
481    let mut issue_found = false;
482    let mut issue_context = b4(0);
483    for offset in 0..14 {
484        let candidate = context_index(r.issue_rr, b4(offset as u128));
485        if !issue_found && current.control[candidate].state == b2(ST_READY) {
486            issue_found = true;
487            issue_context = candidate;
488        }
489    }
490    let issue_work = current.work[issue_context];
491    let multiply_input = FieldMulIn {
492        valid: issue_found,
493        a: if issue_found {
494            issue_work.operand_a
495        } else {
496            zero
497        },
498        b: if issue_found {
499            issue_work.operand_b
500        } else {
501            zero
502        },
503    };
504    if issue_found {
505        contexts.control[issue_context].state = b2(ST_WAIT);
506        n.issue_rr = next_context(issue_context);
507    } else {
508        n.issue_rr = next_context(r.issue_rr);
509    }
510    n.issue_valid[0] = issue_found;
511    n.issue_context[0] = issue_context;
512    for stage in 1..17 {
513        n.issue_valid[stage] = r.issue_valid[stage - 1];
514        n.issue_context[stage] = r.issue_context[stage - 1];
515    }
516
517    let mut release = false;
518    let mut release_context = b4(0);
519    if r.issue_valid[16] && q.multiplier.valid {
520        let context = r.issue_context[16];
521        let control = current.control[context];
522        let result = q.multiplier.result;
523        if control.squares_left != b8(0) {
524            if control.squares_left > b8(1) {
525                contexts.control[context].squares_left = control.squares_left - b8(1);
526                contexts.work[context].operand_a = result;
527                contexts.work[context].operand_b = result;
528            } else {
529                contexts.control[context].squares_left = b8(0);
530                contexts.work[context].operand_a = result;
531                if control.after_square == b4(0) {
532                    contexts.work[context].operand_b = current.work[context].temp1;
533                    contexts.control[context].step = b5(7);
534                } else if control.after_square == b4(1) {
535                    contexts.work[context].operand_b = current.work[context].temp1;
536                    contexts.control[context].step = b5(8);
537                } else if control.after_square == b4(2) {
538                    contexts.work[context].operand_b = current.work[context].temp2;
539                    contexts.control[context].step = b5(9);
540                } else if control.after_square == b4(3) {
541                    contexts.work[context].operand_b = current.work[context].temp1;
542                    contexts.control[context].step = b5(10);
543                } else if control.after_square == b4(4) {
544                    contexts.work[context].operand_b = current.work[context].temp2;
545                    contexts.control[context].step = b5(11);
546                } else if control.after_square == b4(5) {
547                    contexts.work[context].operand_b = current.work[context].temp1;
548                    contexts.control[context].step = b5(12);
549                } else if control.after_square == b4(6) {
550                    contexts.work[context].operand_b = current.work[context].temp2;
551                    contexts.control[context].step = b5(13);
552                } else {
553                    contexts.work[context].operand_b = current.work[context].temp0;
554                    contexts.control[context].step = b5(14);
555                }
556            }
557            contexts.control[context].state = b2(ST_READY);
558        } else if control.step == b5(31) {
559            contexts.work[context].base = result;
560            contexts.work[context].operand_a = result;
561            contexts.work[context].operand_b = result;
562            contexts.control[context].step = b5(0);
563            contexts.control[context].state = b2(ST_READY);
564        } else if control.step == b5(0) {
565            contexts.work[context].temp0 = result;
566            contexts.work[context].operand_a = result;
567            contexts.work[context].operand_b = result;
568            contexts.control[context].step = b5(1);
569            contexts.control[context].state = b2(ST_READY);
570        } else if control.step == b5(1) {
571            contexts.work[context].operand_a = result;
572            contexts.work[context].operand_b = result;
573            contexts.control[context].step = b5(2);
574            contexts.control[context].state = b2(ST_READY);
575        } else if control.step == b5(2) {
576            contexts.work[context].operand_a = current.work[context].base;
577            contexts.work[context].operand_b = result;
578            contexts.control[context].step = b5(3);
579            contexts.control[context].state = b2(ST_READY);
580        } else if control.step == b5(3) {
581            contexts.work[context].temp1 = result;
582            contexts.work[context].operand_a = current.work[context].temp0;
583            contexts.work[context].operand_b = result;
584            contexts.control[context].step = b5(4);
585            contexts.control[context].state = b2(ST_READY);
586        } else if control.step == b5(4) {
587            contexts.work[context].temp0 = result;
588            contexts.work[context].operand_a = result;
589            contexts.work[context].operand_b = result;
590            contexts.control[context].step = b5(5);
591            contexts.control[context].state = b2(ST_READY);
592        } else if control.step == b5(5) {
593            contexts.work[context].operand_a = current.work[context].temp1;
594            contexts.work[context].operand_b = result;
595            contexts.control[context].step = b5(6);
596            contexts.control[context].state = b2(ST_READY);
597        } else if control.step == b5(6) {
598            contexts.work[context].temp1 = result;
599            contexts.control[context].squares_left = b8(5);
600            contexts.control[context].after_square = b4(0);
601            contexts.work[context].operand_a = result;
602            contexts.work[context].operand_b = result;
603            contexts.control[context].state = b2(ST_READY);
604        } else if control.step == b5(7) {
605            contexts.work[context].temp1 = result;
606            contexts.control[context].squares_left = b8(10);
607            contexts.control[context].after_square = b4(1);
608            contexts.work[context].operand_a = result;
609            contexts.work[context].operand_b = result;
610            contexts.control[context].state = b2(ST_READY);
611        } else if control.step == b5(8) {
612            contexts.work[context].temp2 = result;
613            contexts.control[context].squares_left = b8(20);
614            contexts.control[context].after_square = b4(2);
615            contexts.work[context].operand_a = result;
616            contexts.work[context].operand_b = result;
617            contexts.control[context].state = b2(ST_READY);
618        } else if control.step == b5(9) {
619            contexts.control[context].squares_left = b8(10);
620            contexts.control[context].after_square = b4(3);
621            contexts.work[context].operand_a = result;
622            contexts.work[context].operand_b = result;
623            contexts.control[context].state = b2(ST_READY);
624        } else if control.step == b5(10) {
625            contexts.work[context].temp2 = result;
626            contexts.control[context].squares_left = b8(50);
627            contexts.control[context].after_square = b4(4);
628            contexts.work[context].operand_a = result;
629            contexts.work[context].operand_b = result;
630            contexts.control[context].state = b2(ST_READY);
631        } else if control.step == b5(11) {
632            contexts.work[context].temp1 = result;
633            contexts.control[context].squares_left = b8(100);
634            contexts.control[context].after_square = b4(5);
635            contexts.work[context].operand_a = result;
636            contexts.work[context].operand_b = result;
637            contexts.control[context].state = b2(ST_READY);
638        } else if control.step == b5(12) {
639            contexts.control[context].squares_left = b8(50);
640            contexts.control[context].after_square = b4(6);
641            contexts.work[context].operand_a = result;
642            contexts.work[context].operand_b = result;
643            contexts.control[context].state = b2(ST_READY);
644        } else if control.step == b5(13) {
645            contexts.control[context].squares_left = b8(5);
646            contexts.control[context].after_square = b4(7);
647            contexts.work[context].operand_a = result;
648            contexts.work[context].operand_b = result;
649            contexts.control[context].state = b2(ST_READY);
650        } else if control.step == b5(14) {
651            contexts.work[context].temp2 = result;
652            contexts.work[context].operand_a = result;
653            contexts.work[context].operand_b = current.points[context].second.z;
654            contexts.control[context].step = b5(15);
655            contexts.control[context].state = b2(ST_READY);
656        } else if control.step == b5(15) {
657            contexts.work[context].temp0 = result;
658            contexts.work[context].operand_a = current.work[context].temp2;
659            contexts.work[context].operand_b = current.points[context].first.z;
660            contexts.control[context].step = b5(16);
661            contexts.control[context].state = b2(ST_READY);
662        } else if control.step == b5(16) {
663            contexts.work[context].temp1 = result;
664            contexts.work[context].operand_a = current.points[context].first.x;
665            contexts.work[context].operand_b = current.work[context].temp0;
666            contexts.control[context].step = b5(17);
667            contexts.control[context].state = b2(ST_READY);
668        } else if control.step == b5(17) {
669            contexts.control[context].first_sign = result.limbs[0].resize::<1>() == b1(1);
670            contexts.work[context].operand_a = current.points[context].first.y;
671            contexts.work[context].operand_b = current.work[context].temp0;
672            contexts.control[context].step = b5(18);
673            contexts.control[context].state = b2(ST_READY);
674        } else if control.step == b5(18) {
675            contexts.work[context].base = result;
676            contexts.work[context].operand_a = current.points[context].second.x;
677            contexts.work[context].operand_b = current.work[context].temp1;
678            contexts.control[context].step = b5(19);
679            contexts.control[context].state = b2(ST_READY);
680        } else if control.step == b5(19) {
681            contexts.control[context].second_sign = result.limbs[0].resize::<1>() == b1(1);
682            contexts.work[context].operand_a = current.points[context].second.y;
683            contexts.work[context].operand_b = current.work[context].temp1;
684            contexts.control[context].step = b5(20);
685            contexts.control[context].state = b2(ST_READY);
686        } else {
687            output.valid = true;
688            output.tag = control.tag;
689            output.first = compress_field(current.work[context].base, control.first_sign);
690            output.second = compress_field(result, control.second_sign);
691            contexts.control[context].state = b2(ST_FREE);
692            release = true;
693            release_context = context;
694        }
695    }
696
697    let accept = i.valid && r.free_count != b4(0);
698    if accept {
699        let context = r.free_fifo[r.free_read];
700        contexts.control[context] = CompressControlContext {
701            state: b2(ST_READY),
702            tag: i.tag,
703            step: b5(31),
704            squares_left: b8(0),
705            after_square: b4(0),
706            first_sign: false,
707            second_sign: false,
708        };
709        contexts.points[context] = CompressPoints {
710            first: i.first,
711            second: i.second,
712        };
713        contexts.work[context].operand_a = i.first.z;
714        contexts.work[context].operand_b = i.second.z;
715        n.free_read = next_context(r.free_read);
716    }
717    if release {
718        n.free_fifo[r.free_write] = release_context;
719        n.free_write = next_context(r.free_write);
720    }
721    if accept && !release {
722        n.free_count = r.free_count - b4(1);
723    } else if release && !accept {
724        n.free_count = r.free_count + b4(1);
725    }
726
727    let mut d = D::dont_care();
728    d.scheduler = n;
729    d.contexts = contexts;
730    d.multiplier = multiply_input;
731    (output, d)
732}
733
734#[cfg(test)]
735mod tests {
736    use super::*;
737    use curve25519_dalek::{constants::ED25519_BASEPOINT_POINT, scalar::Scalar};
738    use num_bigint::BigUint;
739    use std::iter;
740
741    fn to_field(value: &BigUint) -> FieldElement51 {
742        let mask = (BigUint::from(1u8) << 51) - BigUint::from(1u8);
743        let mut limbs = [b51(0); 5];
744        for (index, limb) in limbs.iter_mut().enumerate() {
745            let digits = ((value >> (51 * index)) & &mask).to_u64_digits();
746            *limb = b51(digits.first().copied().unwrap_or(0) as u128);
747        }
748        FieldElement51 { limbs }
749    }
750
751    fn affine_point(scalar: Scalar) -> (ExtendedPoint, [u8; 32]) {
752        let compressed = (scalar * ED25519_BASEPOINT_POINT).compress().to_bytes();
753        let p = (BigUint::from(1u8) << 255) - BigUint::from(19u8);
754        let d = BigUint::parse_bytes(
755            b"37095705934669439343138083508754565189542113879843219016388785533085940283555",
756            10,
757        )
758        .unwrap();
759        let sign = compressed[31] >> 7;
760        let mut y_bytes = compressed;
761        y_bytes[31] &= 0x7f;
762        let y = BigUint::from_bytes_le(&y_bytes);
763        let y2 = (&y * &y) % &p;
764        let numerator = (&y2 + &p - BigUint::from(1u8)) % &p;
765        let denominator: BigUint = (&d * &y2 + BigUint::from(1u8)) % &p;
766        let inverse = denominator.modpow(&(&p - BigUint::from(2u8)), &p);
767        let x2 = numerator * inverse % &p;
768        let mut x = x2.modpow(&((&p + BigUint::from(3u8)) >> 3), &p);
769        if (&x * &x) % &p != x2 {
770            let sqrt_m1 = BigUint::parse_bytes(
771                b"19681161376707505956807079304988542015446066515923890162744021073123829784752",
772                10,
773            )
774            .unwrap();
775            x = x * sqrt_m1 % &p;
776        }
777        let x_odd = (&x & BigUint::from(1u8)) == BigUint::from(1u8);
778        if x_odd != (sign != 0) {
779            x = &p - x;
780        }
781        (
782            ExtendedPoint {
783                x: to_field(&x),
784                y: to_field(&y),
785                z: FieldElement51::one(),
786                t: to_field(&((&x * &y) % &p)),
787            },
788            compressed,
789        )
790    }
791
792    fn bytes(point: CompressedPoint) -> [u8; 32] {
793        let mut result = [0u8; 32];
794        for (index, word) in point.words.iter().enumerate() {
795            result[index * 8..index * 8 + 8].copy_from_slice(&(word.raw() as u64).to_le_bytes());
796        }
797        result
798    }
799
800    fn idle() -> PointCompressPairIn {
801        PointCompressPairIn {
802            valid: false,
803            first: ExtendedPoint::identity(),
804            second: ExtendedPoint::identity(),
805            tag: b16(0),
806        }
807    }
808
809    #[test]
810    fn batch_inversion_matches_dalek_encodings() {
811        std::thread::Builder::new()
812            .name("point-compress-sim".into())
813            .stack_size(128 * 1024 * 1024)
814            .spawn(batch_inversion_body)
815            .unwrap()
816            .join()
817            .unwrap();
818    }
819
820    fn batch_inversion_body() {
821        let cases: Vec<_> = (0u64..8)
822            .map(|index| {
823                let first = affine_point(Scalar::from(index * 17 + 1));
824                let second = affine_point(Scalar::from(index * 29 + 2));
825                (first, second)
826            })
827            .collect();
828        let inputs = cases
829            .iter()
830            .enumerate()
831            .map(|(tag, case)| PointCompressPairIn {
832                valid: true,
833                first: case.0.0,
834                second: case.1.0,
835                tag: b16(tag as u128),
836            });
837        let outputs: Vec<_> = PointCompressPair::default()
838            .run(
839                iter::once(idle())
840                    .chain(inputs)
841                    .chain(iter::repeat_n(idle(), 6_000))
842                    .with_reset(1)
843                    .clock_pos_edge(100),
844            )
845            .synchronous_sample()
846            .map(|sample| sample.output)
847            .filter(|output| output.valid)
848            .collect();
849        assert_eq!(outputs.len(), cases.len());
850        for output in outputs {
851            let case = &cases[output.tag.raw() as usize];
852            assert_eq!(bytes(output.first), case.0.1);
853            assert_eq!(bytes(output.second), case.1.1);
854        }
855    }
856
857    #[test]
858    fn compiles_to_native_rhdl_netlist() -> miette::Result<()> {
859        // The pretty-printed export is linted separately; RHDL's temporary
860        // single-line testbench exceeds Icarus's scanner buffer for this array kernel.
861        unsafe { std::env::set_var("RHDL_SKIP_IVERILOG_CHECK", "1") };
862        PointCompressPair::default()
863            .descriptor(ScopedName::top())?
864            .hdl()?;
865        Ok(())
866    }
867
868    #[test]
869    fn sustained_pair_service_preserves_signing_throughput() {
870        std::thread::Builder::new()
871            .name("point-compress-throughput".into())
872            .stack_size(128 * 1024 * 1024)
873            .spawn(sustained_pair_service_body)
874            .unwrap()
875            .join()
876            .unwrap();
877    }
878
879    fn sustained_pair_service_body() {
880        let request = PointCompressPairIn {
881            valid: true,
882            first: ExtendedPoint::identity(),
883            second: ExtendedPoint::identity(),
884            tag: b16(1),
885        };
886        let cycles: Vec<_> = PointCompressPair::default()
887            .run(
888                iter::once(idle())
889                    .chain(iter::repeat_n(request, 14_000))
890                    .with_reset(1)
891                    .clock_pos_edge(100),
892            )
893            .synchronous_sample()
894            .enumerate()
895            .filter_map(|(cycle, sample)| sample.output.valid.then_some(cycle))
896            .collect();
897        assert!(cycles.len() >= 28, "only {} completed pairs", cycles.len());
898        let steady = &cycles[14..];
899        let pair_interval =
900            (steady.last().unwrap() - steady.first().unwrap()) as f64 / (steady.len() - 1) as f64;
901        println!(
902            "pair compressor sustained: pairs={} pair_interval={pair_interval:.3} point_interval={:.3}",
903            cycles.len(),
904            pair_interval / 2.0,
905        );
906        assert!(
907            pair_interval / 2.0 <= 202.0,
908            "{:.3}-cycle point interval misses signing budget",
909            pair_interval / 2.0,
910        );
911    }
912}
rhdl_ed25519_fast_core/point_compress.rs

rhdl_ed25519_fast_core/
point_compress.rs
