rhdl_ed25519_fast_core/
multicomb_table.rs

1//! Constant-pattern multi-comb lookup backed entirely by inferred BRAM.
2//!
3//! The Ed25519 basepoint table has four logical banks and 128 entries per
4//! bank. Each 765-bit entry stores three radix-`2^51` field coordinates. Eight
5//! physical read replicas per bank fetch eight public scan groups each cycle,
6//! so every request scans all 32 groups in four cycles. Secret candidate bits
7//! select only registered return data; they never drive a BRAM address or
8//! enable.
9//!
10//! The logical table payload is 391,680 bits (48,960 bytes). The eight-way
11//! read replication occupies 3,133,440 initialized bits, corresponding to 96
12//! BRAM36 primitives before implementation packing.
13
14use rhdl::prelude::*;
15use rhdl_fpga::core::ram::synchronous::{In as RamIn, SyncBRAM, Write as RamWrite};
16
17use crate::field_parallel::FieldElement51;
18
19/// Projective-Niels coordinates consumed by the fixed-base mixed-add formula.
20#[derive(Copy, Clone, Debug, PartialEq, Digital)]
21pub struct NielsPoint {
22    /// `Y + X` modulo `2^255 - 19`.
23    pub y_plus_x: FieldElement51,
24    /// `Y - X` modulo `2^255 - 19`.
25    pub y_minus_x: FieldElement51,
26    /// `2dXY` modulo `2^255 - 19`.
27    pub xy2d: FieldElement51,
28}
29
30impl NielsPoint {
31    /// All-zero placeholder used while no lookup result is valid.
32    pub fn zero() -> Self {
33        Self {
34            y_plus_x: FieldElement51::zero(),
35            y_minus_x: FieldElement51::zero(),
36            xy2d: FieldElement51::zero(),
37        }
38    }
39}
40
41include!(concat!(env!("OUT_DIR"), "/multicomb_table_data.rs"));
42
43#[derive(Copy, Clone, Debug, PartialEq, Digital)]
44#[doc(hidden)]
45pub struct ScanBank8In {
46    addresses: [b7; 8],
47}
48
49#[derive(Copy, Clone, Debug, PartialEq, Digital)]
50#[doc(hidden)]
51pub struct ScanBank8Out {
52    words: [NielsPoint; 8],
53}
54
55/// Eight physically independent read replicas of one table bank.
56#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
57#[doc(hidden)]
58pub struct ScanBank8 {
59    port0: SyncBRAM<NielsPoint, 7>,
60    port1: SyncBRAM<NielsPoint, 7>,
61    port2: SyncBRAM<NielsPoint, 7>,
62    port3: SyncBRAM<NielsPoint, 7>,
63    port4: SyncBRAM<NielsPoint, 7>,
64    port5: SyncBRAM<NielsPoint, 7>,
65    port6: SyncBRAM<NielsPoint, 7>,
66    port7: SyncBRAM<NielsPoint, 7>,
67}
68
69impl ScanBank8 {
70    fn new(initial: Vec<(b7, NielsPoint)>) -> Self {
71        Self {
72            port0: SyncBRAM::new(initial.clone()),
73            port1: SyncBRAM::new(initial.clone()),
74            port2: SyncBRAM::new(initial.clone()),
75            port3: SyncBRAM::new(initial.clone()),
76            port4: SyncBRAM::new(initial.clone()),
77            port5: SyncBRAM::new(initial.clone()),
78            port6: SyncBRAM::new(initial.clone()),
79            port7: SyncBRAM::new(initial),
80        }
81    }
82}
83
84impl SynchronousIO for ScanBank8 {
85    type I = ScanBank8In;
86    type O = ScanBank8Out;
87    type Kernel = scan_bank8_kernel;
88}
89
90#[kernel]
91#[doc(hidden)]
92pub fn scan_bank8_kernel(
93    _cr: ClockReset,
94    i: ScanBank8In,
95    q: ScanBank8Q,
96) -> (ScanBank8Out, ScanBank8D) {
97    let output = ScanBank8Out {
98        words: [
99            q.port0, q.port1, q.port2, q.port3, q.port4, q.port5, q.port6, q.port7,
100        ],
101    };
102    let disabled = RamWrite::<NielsPoint, 7> {
103        addr: b7(0),
104        value: NielsPoint {
105            y_plus_x: FieldElement51 { limbs: [b51(0); 5] },
106            y_minus_x: FieldElement51 { limbs: [b51(0); 5] },
107            xy2d: FieldElement51 { limbs: [b51(0); 5] },
108        },
109        enable: false,
110    };
111    let mut d = ScanBank8D::dont_care();
112    d.port0 = RamIn::<NielsPoint, 7> {
113        read_addr: i.addresses[0],
114        write: disabled,
115    };
116    d.port1 = RamIn::<NielsPoint, 7> {
117        read_addr: i.addresses[1],
118        write: disabled,
119    };
120    d.port2 = RamIn::<NielsPoint, 7> {
121        read_addr: i.addresses[2],
122        write: disabled,
123    };
124    d.port3 = RamIn::<NielsPoint, 7> {
125        read_addr: i.addresses[3],
126        write: disabled,
127    };
128    d.port4 = RamIn::<NielsPoint, 7> {
129        read_addr: i.addresses[4],
130        write: disabled,
131    };
132    d.port5 = RamIn::<NielsPoint, 7> {
133        read_addr: i.addresses[5],
134        write: disabled,
135    };
136    d.port6 = RamIn::<NielsPoint, 7> {
137        read_addr: i.addresses[6],
138        write: disabled,
139    };
140    d.port7 = RamIn::<NielsPoint, 7> {
141        read_addr: i.addresses[7],
142        write: disabled,
143    };
144    (output, d)
145}
146
147/// Request accepted by [`MultiCombLookup`].
148#[derive(Copy, Clone, Debug, PartialEq, Digital)]
149pub struct MultiCombLookupIn {
150    /// Marks the request valid. A request is accepted when [`MultiCombLookupOut::ready`] is set.
151    pub valid: bool,
152    /// Public comb block, from zero through three.
153    pub block: b2,
154    /// Secret seven-bit absolute table candidate.
155    pub candidate: b7,
156    /// Secret sign bit applied after the constant-address scan.
157    pub sign: bool,
158    /// Caller-defined transaction tag.
159    pub tag: b16,
160}
161
162/// Response and flow control from [`MultiCombLookup`].
163#[derive(Copy, Clone, Debug, PartialEq, Digital)]
164pub struct MultiCombLookupOut {
165    /// High when a new request can be accepted.
166    pub ready: bool,
167    /// High for one cycle when [`Self::point`] and [`Self::tag`] are valid.
168    pub valid: bool,
169    /// Signed projective-Niels table result.
170    pub point: NielsPoint,
171    /// Delayed caller tag.
172    pub tag: b16,
173}
174
175#[derive(Copy, Clone, Debug, PartialEq, Digital)]
176#[doc(hidden)]
177pub struct MultiCombLookupRegs {
178    active: bool,
179    phase: b2,
180    block: b2,
181    candidate: b7,
182    sign: bool,
183    tag: b16,
184    groups: [b5; 8],
185    selected: NielsPoint,
186}
187
188/// Four-cycle constant-address signed multi-comb table lookup.
189#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
190#[rhdl(dq_no_prefix)]
191pub struct MultiCombLookup {
192    regs: rhdl_fpga::core::dff::DFF<MultiCombLookupRegs>,
193    bank0: ScanBank8,
194    bank1: ScanBank8,
195    bank2: ScanBank8,
196    bank3: ScanBank8,
197}
198
199impl Default for MultiCombLookup {
200    fn default() -> Self {
201        Self {
202            regs: rhdl_fpga::core::dff::DFF::new(MultiCombLookupRegs {
203                active: false,
204                phase: b2(0),
205                block: b2(0),
206                candidate: b7(0),
207                sign: false,
208                tag: b16(0),
209                groups: [b5(0); 8],
210                selected: NielsPoint::zero(),
211            }),
212            bank0: ScanBank8::new(table_bank_0()),
213            bank1: ScanBank8::new(table_bank_1()),
214            bank2: ScanBank8::new(table_bank_2()),
215            bank3: ScanBank8::new(table_bank_3()),
216        }
217    }
218}
219
220impl SynchronousIO for MultiCombLookup {
221    type I = MultiCombLookupIn;
222    type O = MultiCombLookupOut;
223    type Kernel = multicomb_lookup_kernel;
224}
225
226#[kernel]
227fn negate_field(value: FieldElement51) -> FieldElement51 {
228    let mask = b52(0x7ffffffffffff);
229    let p0 = b52(0x7ffffffffffed);
230    let d0 = p0 + b52(0x8000000000000) - value.limbs[0].resize::<52>();
231    let borrow0 = (d0 >> 51) == b52(0);
232    let d1 = mask + b52(0x8000000000000)
233        - value.limbs[1].resize::<52>()
234        - if borrow0 { b52(1) } else { b52(0) };
235    let borrow1 = (d1 >> 51) == b52(0);
236    let d2 = mask + b52(0x8000000000000)
237        - value.limbs[2].resize::<52>()
238        - if borrow1 { b52(1) } else { b52(0) };
239    let borrow2 = (d2 >> 51) == b52(0);
240    let d3 = mask + b52(0x8000000000000)
241        - value.limbs[3].resize::<52>()
242        - if borrow2 { b52(1) } else { b52(0) };
243    let borrow3 = (d3 >> 51) == b52(0);
244    let d4 = mask + b52(0x8000000000000)
245        - value.limbs[4].resize::<52>()
246        - if borrow3 { b52(1) } else { b52(0) };
247    let is_zero = value.limbs[0] == b51(0)
248        && value.limbs[1] == b51(0)
249        && value.limbs[2] == b51(0)
250        && value.limbs[3] == b51(0)
251        && value.limbs[4] == b51(0);
252    if is_zero {
253        FieldElement51 { limbs: [b51(0); 5] }
254    } else {
255        FieldElement51 {
256            limbs: [
257                d0.resize::<51>(),
258                d1.resize::<51>(),
259                d2.resize::<51>(),
260                d3.resize::<51>(),
261                d4.resize::<51>(),
262            ],
263        }
264    }
265}
266
267/// State transition for the constant-address lookup.
268#[kernel]
269pub fn multicomb_lookup_kernel(
270    _cr: ClockReset,
271    i: MultiCombLookupIn,
272    q: Q,
273) -> (MultiCombLookupOut, D) {
274    let r = q.regs;
275    let mut n = r;
276    let mut selected = r.selected;
277    let mut output = MultiCombLookupOut {
278        ready: !r.active,
279        valid: false,
280        point: NielsPoint {
281            y_plus_x: FieldElement51 { limbs: [b51(0); 5] },
282            y_minus_x: FieldElement51 { limbs: [b51(0); 5] },
283            xy2d: FieldElement51 { limbs: [b51(0); 5] },
284        },
285        tag: r.tag,
286    };
287
288    let mut addresses = [b7(0); 8];
289    let address_block = if !r.active { i.block } else { r.block };
290    let address_phase = if !r.active { b2(0) } else { r.phase + b2(1) };
291    for port in 0..8 {
292        let group = address_phase.resize::<7>() * b7(8) + b7(port as u128);
293        addresses[port] = (address_block.resize::<7>() << 5) | group;
294    }
295
296    if i.valid && !r.active {
297        n.active = true;
298        n.phase = b2(0);
299        n.block = i.block;
300        n.candidate = i.candidate;
301        n.sign = i.sign;
302        n.tag = i.tag;
303        n.selected = NielsPoint {
304            y_plus_x: FieldElement51 { limbs: [b51(0); 5] },
305            y_minus_x: FieldElement51 { limbs: [b51(0); 5] },
306            xy2d: FieldElement51 { limbs: [b51(0); 5] },
307        };
308        for port in 0..8 {
309            n.groups[port] = b5(port as u128);
310        }
311    } else if r.active {
312        for port in 0..8 {
313            let bank_word = if r.candidate.resize::<2>() == b2(0) {
314                q.bank0.words[port]
315            } else if r.candidate.resize::<2>() == b2(1) {
316                q.bank1.words[port]
317            } else if r.candidate.resize::<2>() == b2(2) {
318                q.bank2.words[port]
319            } else {
320                q.bank3.words[port]
321            };
322            if (r.candidate >> 2).resize::<5>() == r.groups[port] {
323                selected = bank_word;
324            }
325        }
326        n.selected = selected;
327        if r.phase == b2(3) {
328            n.active = false;
329            output.valid = true;
330            output.tag = r.tag;
331            output.point = if r.sign {
332                NielsPoint {
333                    y_plus_x: selected.y_minus_x,
334                    y_minus_x: selected.y_plus_x,
335                    xy2d: negate_field(selected.xy2d),
336                }
337            } else {
338                selected
339            };
340        } else {
341            n.phase = r.phase + b2(1);
342            for port in 0..8 {
343                n.groups[port] = r.groups[port] + b5(8);
344            }
345        }
346    }
347
348    let ram_input = ScanBank8In { addresses };
349    let mut d = D::dont_care();
350    d.regs = n;
351    d.bank0 = ram_input;
352    d.bank1 = ram_input;
353    d.bank2 = ram_input;
354    d.bank3 = ram_input;
355    (output, d)
356}
357
358#[cfg(test)]
359mod tests {
360    use super::*;
361    use std::iter;
362
363    fn idle() -> MultiCombLookupIn {
364        MultiCombLookupIn {
365            valid: false,
366            block: b2(0),
367            candidate: b7(0),
368            sign: false,
369            tag: b16(0),
370        }
371    }
372
373    fn neg(value: FieldElement51) -> FieldElement51 {
374        negate_field(value)
375    }
376
377    #[test]
378    fn scans_every_table_entry_and_applies_sign() {
379        let banks = [
380            table_bank_0(),
381            table_bank_1(),
382            table_bank_2(),
383            table_bank_3(),
384        ];
385        let mut inputs = vec![idle()];
386        let mut expected = Vec::new();
387        for block in 0usize..4 {
388            for candidate in 0usize..128 {
389                for sign in [false, true] {
390                    let request = MultiCombLookupIn {
391                        valid: true,
392                        block: b2(block as u128),
393                        candidate: b7(candidate as u128),
394                        sign,
395                        tag: b16((block * 256 + candidate * 2 + usize::from(sign)) as u128),
396                    };
397                    inputs.push(request);
398                    inputs.extend(iter::repeat_n(idle(), 5));
399                    let table_point = banks[candidate & 3][block * 32 + (candidate >> 2)].1;
400                    let point = if sign {
401                        NielsPoint {
402                            y_plus_x: table_point.y_minus_x,
403                            y_minus_x: table_point.y_plus_x,
404                            xy2d: neg(table_point.xy2d),
405                        }
406                    } else {
407                        table_point
408                    };
409                    expected.push((request.tag, point));
410                }
411            }
412        }
413        inputs.extend(iter::repeat_n(idle(), 8));
414        let outputs: Vec<_> = MultiCombLookup::default()
415            .run(inputs.into_iter().with_reset(1).clock_pos_edge(100))
416            .synchronous_sample()
417            .map(|sample| sample.output)
418            .filter(|output| output.valid)
419            .collect();
420        assert_eq!(outputs.len(), expected.len());
421        for (output, (tag, point)) in outputs.into_iter().zip(expected) {
422            assert_eq!(output.tag, tag);
423            assert_eq!(output.point, point);
424        }
425    }
426
427    #[test]
428    fn compiles_to_native_rhdl_netlist() -> miette::Result<()> {
429        MultiCombLookup::default()
430            .descriptor(ScopedName::top())?
431            .hdl()?;
432        Ok(())
433    }
434}
rhdl_ed25519_fast_core/multicomb_table.rs

rhdl_ed25519_fast_core/
multicomb_table.rs
