rhdl_ed25519_scalable_core/microcode.rs
1//! Microcode for the barrel field machine: ISA, compiler, and interpreter.
2//!
3//! A field machine executes one VLIW *bundle* per issue slot. A bundle has
4//! three independent slots:
5//!
6//! - **M**: one modular multiplication `dst = a * b`;
7//! - **A**: one modular addition/subtraction, or `OUT`, which emits a value;
8//! - **T**: one constant-address scan step of the fixed-base table.
9//!
10//! The machine interleaves `K` independent contexts (barrel multithreading).
11//! Each context issues one bundle every `K` issue slots, and `K` is at least
12//! the longest unit latency. A bundle's results are therefore always visible
13//! to the context's next bundle, and **no program needs latency scheduling**.
14//! The compiler only packs operations into bundles, respecting dependencies.
15//!
16//! Registers live in banks named after their single writer, so each bank has
17//! exactly one write port: `M` (multiplier results), `A` (add/sub results),
18//! `I` (job inputs, written by the loader), `L` (the selected Niels point,
19//! written by the T slot), and `C` (read-only constants).
20//!
21//! Every operation is data independent: secret digits only choose between
22//! already-read table entries; they never form an address or skip a bundle.
23//!
24//! The flow is: a program is written against [`Builder`] as straight-line
25//! code over virtual values ([`V`]); [`Builder::compile`] list-schedules the
26//! operations into bundles and then allocates physical registers in banks M
27//! and A by value lifetime; [`interpret`] runs the result with the exact
28//! read-before-write semantics of the hardware, which is how programs are
29//! tested; [`concat()`] merges several programs into one ROM.
30
31use std::collections::HashMap;
32
33use super::host::{Fp, Niels, basepoint_table, digit_entries, table_row};
34
35/// Register bank. Each bank has one writer, so it needs only one write port.
36#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
37pub enum Bank {
38 /// Multiplier results.
39 M,
40 /// Add/subtract results.
41 A,
42 /// Loader-written job inputs.
43 I,
44 /// Selected lookup point: index `4 * slot + coordinate`, coordinate
45 /// 0 = `y+x`, 1 = `y-x`, 2 = `2dxy`.
46 L,
47 /// Read-only constants.
48 C,
49}
50
51/// A physical operand: a register in one bank of the issuing context.
52#[derive(Copy, Clone, Debug, PartialEq, Eq)]
53pub struct Operand {
54 /// Bank.
55 pub bank: Bank,
56 /// Register index inside the bank, per context.
57 pub index: u8,
58}
59
60/// Multiply slot.
61#[derive(Copy, Clone, Debug, PartialEq, Eq)]
62pub struct MSlot {
63 /// Destination register in bank M.
64 pub dst: u8,
65 /// First factor (any bank except L).
66 pub a: Operand,
67 /// Second factor (any bank). Bank L is readable only here.
68 pub b: Operand,
69}
70
71/// Add/subtract slot operation.
72#[derive(Copy, Clone, Debug, PartialEq, Eq)]
73pub enum AOp {
74 /// `dst = a + b`.
75 Add,
76 /// `dst = a - b`.
77 Sub,
78 /// Emit `a` on the output port with the given output index.
79 Out(u8),
80}
81
82/// Add/subtract slot.
83#[derive(Copy, Clone, Debug, PartialEq, Eq)]
84pub struct ASlot {
85 /// Operation.
86 pub op: AOp,
87 /// Destination register in bank A (ignored for `Out`).
88 pub dst: u8,
89 /// First operand (any bank except L).
90 pub a: Operand,
91 /// Second operand (any bank except L; a dummy `C[0]` for `Out`).
92 pub b: Operand,
93}
94
95/// Table-scan slot.
96///
97/// Reads the two public entries `2*pair+1` and `2*pair+2` of table
98/// `digit` (one table per digit, stored at table row `row`). The context's
99/// accumulator takes an entry exactly when the digit magnitude equals that
100/// entry number. `clear` first resets the
101/// accumulator to the identity; `finish` afterwards writes the accumulator,
102/// negated when the digit is negative, into bank L.
103///
104/// A lookup is therefore a fixed sequence of scan steps whose rows depend
105/// only on the digit's position, never on its value. A zero digit matches no
106/// entry and leaves the identity.
107#[derive(Copy, Clone, Debug, PartialEq, Eq)]
108pub struct TSlot {
109 /// Digit index, 0..[`DIGITS`](super::host::DIGITS).
110 pub digit: u8,
111 /// Entry pair, 0..8 (radix 32) or 0..4 (radix 16).
112 pub pair: u8,
113 /// Table row of this pair (`table_row(digit) + pair`).
114 pub row: u16,
115 /// Reset the accumulator before scanning.
116 pub clear: bool,
117 /// Commit the (conditionally negated) accumulator to bank L.
118 pub finish: bool,
119 /// Bank-L slot (0 or 1) the lookup commits to.
120 pub l_slot: u8,
121 /// Scan the per-key table (verification key) instead of the base-point
122 /// table. Key lookups read digits `64..64 + DIGITS`.
123 pub key: bool,
124}
125
126/// One VLIW bundle.
127#[derive(Copy, Clone, Debug, Default, PartialEq, Eq)]
128pub struct Bundle {
129 /// Multiply slot.
130 pub m: Option<MSlot>,
131 /// Add/subtract/output slot.
132 pub a: Option<ASlot>,
133 /// Table slot.
134 pub t: Option<TSlot>,
135 /// Last bundle of a program: the context retires after it.
136 pub end: bool,
137}
138
139/// Compiled, register-allocated program.
140#[derive(Clone, Debug)]
141pub struct Program {
142 /// Human-readable name.
143 pub name: &'static str,
144 /// Bundles in issue order; the context retires after the last one.
145 pub bundles: Vec<Bundle>,
146 /// Bank-M registers per context.
147 pub regs_m: usize,
148 /// Bank-A registers per context.
149 pub regs_a: usize,
150 /// Bank-I registers per context (one past the highest input read).
151 pub regs_i: usize,
152 /// Constant bank contents. Never empty: entry 0 is the dummy second
153 /// operand of `Out`.
154 pub consts: Vec<Fp>,
155 /// Number of `Out` operations.
156 pub outputs: usize,
157 /// Multiply operations (for utilization accounting).
158 pub mul_ops: usize,
159 /// Add/sub/out operations.
160 pub add_ops: usize,
161 /// Scan operations.
162 pub scan_ops: usize,
163}
164
165/// A virtual value used by the [`Builder`].
166#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
167pub enum V {
168 /// Result of an earlier operation, by value id.
169 Val(u32),
170 /// Constant bank entry.
171 Const(u8),
172 /// Job input register.
173 Input(u8),
174 /// Selected lookup coordinate: `4 * slot + coordinate` (0 `y+x`,
175 /// 1 `y-x`, 2 `2dxy`) of one of the two bank-L slots.
176 L(u8),
177}
178
179/// One operation in the builder's straight-line program.
180#[derive(Copy, Clone, Debug)]
181enum Kind {
182 /// `a * b`.
183 Mul(V, V),
184 /// `a + b`.
185 Add(V, V),
186 /// `a - b`.
187 Sub(V, V),
188 /// Emit a value with an output index.
189 Out(V, u8),
190 /// One table-scan step.
191 Scan(TSlot),
192}
193
194impl Kind {
195 /// Values the operation reads. A scan reads no virtual value; its
196 /// ordering is handled separately in [`Builder::compile`].
197 fn uses(&self) -> Vec<V> {
198 match *self {
199 Kind::Mul(a, b) | Kind::Add(a, b) | Kind::Sub(a, b) => vec![a, b],
200 Kind::Out(a, _) => vec![a],
201 Kind::Scan(_) => vec![],
202 }
203 }
204 /// Bundle slot the operation occupies: 0 = M, 1 = A, 2 = T.
205 fn slot(&self) -> usize {
206 match self {
207 Kind::Mul(..) => 0,
208 Kind::Add(..) | Kind::Sub(..) | Kind::Out(..) => 1,
209 Kind::Scan(_) => 2,
210 }
211 }
212}
213
214/// Straight-line program builder over virtual values.
215///
216/// Each method appends one operation (or, for lookups, a run of scan steps)
217/// in program order and returns the virtual value it defines. Nothing is
218/// scheduled until [`Self::compile`].
219#[derive(Default)]
220pub struct Builder {
221 /// Operations in program order, with the value id each defines
222 /// (`None` for `Out` and scan steps).
223 ops: Vec<(Kind, Option<u32>)>,
224 /// Next value id to hand out.
225 next: u32,
226 /// Constant bank, deduplicated.
227 consts: Vec<Fp>,
228 /// Number of `Out` operations so far.
229 outputs: u8,
230 /// Number of lookups so far; its low bit picks the bank-L slot.
231 lookups: u8,
232}
233
234impl Builder {
235 /// Create an empty builder.
236 pub fn new() -> Self {
237 Self::default()
238 }
239
240 /// Reference a constant, deduplicated.
241 pub fn constant(&mut self, value: Fp) -> V {
242 if let Some(i) = self.consts.iter().position(|c| *c == value) {
243 return V::Const(i as u8);
244 }
245 self.consts.push(value);
246 V::Const((self.consts.len() - 1) as u8)
247 }
248
249 /// Append a value-defining operation and return its new value id.
250 fn push(&mut self, kind: Kind) -> V {
251 let id = self.next;
252 self.next += 1;
253 self.ops.push((kind, Some(id)));
254 V::Val(id)
255 }
256
257 /// `a * b`. Bank L can feed only the second factor, so `a` must not be
258 /// a lookup coordinate.
259 pub fn mul(&mut self, a: V, b: V) -> V {
260 assert!(!matches!(a, V::L(_)), "L may only be the second factor");
261 self.push(Kind::Mul(a, b))
262 }
263 /// `a^2`.
264 pub fn sqr(&mut self, a: V) -> V {
265 self.mul(a, a)
266 }
267 /// `a^(2^k)`: `k` successive squarings.
268 pub fn pow2k(&mut self, a: V, k: u32) -> V {
269 let mut x = a;
270 for _ in 0..k {
271 x = self.sqr(x);
272 }
273 x
274 }
275 /// `a + b`. The add unit cannot read bank L.
276 pub fn add(&mut self, a: V, b: V) -> V {
277 assert!(!matches!(a, V::L(_)) && !matches!(b, V::L(_)));
278 self.push(Kind::Add(a, b))
279 }
280 /// `a - b`. The add unit cannot read bank L.
281 pub fn sub(&mut self, a: V, b: V) -> V {
282 assert!(!matches!(a, V::L(_)) && !matches!(b, V::L(_)));
283 self.push(Kind::Sub(a, b))
284 }
285 /// Emit `a` with output index `index`; outputs keep program order.
286 pub fn out(&mut self, a: V, index: u8) {
287 self.outputs += 1;
288 self.ops.push((Kind::Out(a, index), None));
289 }
290 /// Constant-address lookup of signed digit `digit` into bank L.
291 pub fn lookup(&mut self, digit: u8) -> [V; 3] {
292 self.lookup_in(digit, false)
293 }
294
295 /// Constant-address lookup of digit `digit` of the second scalar (digit
296 /// slot `64 + digit`) in the per-key table.
297 pub fn lookup_key(&mut self, digit: u8) -> [V; 3] {
298 self.lookup_in(digit, true)
299 }
300
301 /// Append the scan steps of one lookup and return the three bank-L
302 /// coordinates it commits (`y+x`, `y-x`, `2dxy`).
303 fn lookup_in(&mut self, digit: u8, key: bool) -> [V; 3] {
304 // One scan step per entry pair: 8 for a radix-32 digit, 4 for a
305 // radix-16 one.
306 let pairs = (digit_entries(digit as usize) / 2) as u8;
307 // Lookups alternate between the two bank-L slots, so one lookup can
308 // commit while the previous one is still being consumed.
309 let l_slot = self.lookups & 1;
310 self.lookups += 1;
311 for pair in 0..pairs {
312 self.ops.push((
313 Kind::Scan(TSlot {
314 digit: if key { 64 + digit } else { digit },
315 pair,
316 // Row from the digit position alone, never its value.
317 row: (table_row(digit as usize) + pair as usize) as u16,
318 // The first step resets the accumulator, the last commits.
319 clear: pair == 0,
320 finish: pair + 1 == pairs,
321 l_slot,
322 key,
323 }),
324 None,
325 ));
326 }
327 [V::L(4 * l_slot), V::L(4 * l_slot + 1), V::L(4 * l_slot + 2)]
328 }
329
330 /// `a^(p-2)` with Dalek's 254-square, 11-multiply addition chain.
331 /// Inversion by Fermat's little theorem uses only the multiplier and
332 /// runs in a fixed number of bundles; zero maps to zero.
333 pub fn invert(&mut self, x: V) -> V {
334 // t19 = x^(2^250 - 1), t3 = x^11.
335 let (t19, t3) = self.pow22501(x);
336 // x^(2^255 - 32) * x^11 = x^(2^255 - 21) = x^(p - 2).
337 let t20 = self.pow2k(t19, 5);
338 self.mul(t20, t3)
339 }
340
341 /// `a^((p-5)/8)` (`(x^(2^250-1))^4 * x`), for square roots.
342 pub fn pow_p58(&mut self, x: V) -> V {
343 let (t19, _) = self.pow22501(x);
344 let t20 = self.pow2k(t19, 2);
345 self.mul(t20, x)
346 }
347
348 /// `(x^(2^250 - 1), x^11)`, the shared prefix of [`Self::invert`] and
349 /// [`Self::pow_p58`].
350 ///
351 /// Each `tN` comment gives the exponent of `x` it holds.
352 fn pow22501(&mut self, x: V) -> (V, V) {
353 // 2
354 let t0 = self.sqr(x);
355 // 8
356 let t1 = self.pow2k(t0, 2);
357 // 9
358 let t2 = self.mul(x, t1);
359 // 11
360 let t3 = self.mul(t0, t2);
361 // 22
362 let t4 = self.sqr(t3);
363 // 31 = 2^5 - 1
364 let t5 = self.mul(t2, t4);
365 // 2^10 - 2^5
366 let t6 = self.pow2k(t5, 5);
367 // 2^10 - 1
368 let t7 = self.mul(t6, t5);
369 // 2^20 - 2^10
370 let t8 = self.pow2k(t7, 10);
371 // 2^20 - 1
372 let t9 = self.mul(t8, t7);
373 // 2^40 - 2^20
374 let t10 = self.pow2k(t9, 20);
375 // 2^40 - 1
376 let t11 = self.mul(t10, t9);
377 // 2^50 - 2^10
378 let t12 = self.pow2k(t11, 10);
379 // 2^50 - 1
380 let t13 = self.mul(t12, t7);
381 // 2^100 - 2^50
382 let t14 = self.pow2k(t13, 50);
383 // 2^100 - 1
384 let t15 = self.mul(t14, t13);
385 // 2^200 - 2^100
386 let t16 = self.pow2k(t15, 100);
387 // 2^200 - 1
388 let t17 = self.mul(t16, t15);
389 // 2^250 - 2^50
390 let t18 = self.pow2k(t17, 50);
391 // 2^250 - 1
392 let t19 = self.mul(t18, t13);
393 (t19, t3)
394 }
395
396 /// Schedule into bundles and allocate bank registers.
397 ///
398 /// Three passes: build ordering constraints between operations,
399 /// list-schedule them into bundles by critical-path height, then assign
400 /// physical M and A registers from the scheduled value lifetimes. Because
401 /// the barrel makes every result visible to the next bundle, a dependency
402 /// only needs the consumer to sit in a later bundle than the producer.
403 pub fn compile(self, name: &'static str) -> Program {
404 let n = self.ops.len();
405 // Value id -> index of the operation that defines it.
406 let mut def_op: HashMap<u32, usize> = HashMap::new();
407 for (i, (_, d)) in self.ops.iter().enumerate() {
408 if let Some(d) = d {
409 def_op.insert(*d, i);
410 }
411 }
412 // Static ordering constraints: (earlier op, later op, strict).
413 // `preds[i]` lists `(p, strict)`: op `i` must be in a later bundle
414 // than op `p` when `strict`, or in the same bundle or later when not.
415 let mut preds: Vec<Vec<(usize, bool)>> = vec![Vec::new(); n];
416 // Per bank-L slot: the scan step that last committed to it.
417 let mut last_finish: [Option<usize>; 2] = [None; 2];
418 // Per bank-L slot: ops that read the current committed value, which
419 // the next commit to that slot must not overtake.
420 let mut l_readers: [Vec<usize>; 2] = [Vec::new(), Vec::new()];
421 // Scans share one accumulator per context, so they run in program
422 // order.
423 let mut last_scan: Option<usize> = None;
424 // Outputs leave in program order (the controller counts them).
425 let mut last_out: Option<usize> = None;
426 // One past the highest input register read: the program's bank-I size.
427 let mut max_input = 0usize;
428 for i in 0..n {
429 let kind = self.ops[i].0;
430 for u in kind.uses() {
431 match u {
432 // Read-after-write on a computed value.
433 V::Val(v) => preds[i].push((def_op[&v], true)),
434 // Read-after-write on bank L: after the lookup's commit.
435 V::L(k) => {
436 let slot = (k >> 2) as usize;
437 let f = last_finish[slot].expect("L read before any lookup");
438 preds[i].push((f, true));
439 l_readers[slot].push(i);
440 }
441 V::Input(k) => max_input = max_input.max(k as usize + 1),
442 V::Const(_) => {}
443 }
444 }
445 match kind {
446 Kind::Scan(t) => {
447 if let Some(s) = last_scan {
448 preds[i].push((s, true));
449 }
450 last_scan = Some(i);
451 if t.finish {
452 // Write-after-read on bank L: the bundle may coincide
453 // with the final read because reads precede writes.
454 let slot = t.l_slot as usize;
455 for &r in &l_readers[slot] {
456 preds[i].push((r, false));
457 }
458 l_readers[slot].clear();
459 last_finish[slot] = Some(i);
460 }
461 }
462 Kind::Out(..) => {
463 if let Some(o) = last_out {
464 preds[i].push((o, true));
465 }
466 last_out = Some(i);
467 }
468 _ => {}
469 }
470 }
471
472 // Critical-path list scheduling: the ready operation with the
473 // longest dependent chain to the end of the program goes first.
474 // `height[i]` is the number of bundles from op `i` to the end along
475 // its longest constraint chain. Predecessors always come earlier in
476 // program order, so one reverse pass finalizes each height before it
477 // is propagated. A non-strict edge adds no bundle.
478 let mut height = vec![1usize; n];
479 for i in (0..n).rev() {
480 for &(p, strict) in &preds[i] {
481 let h = height[i] + usize::from(strict);
482 if h > height[p] {
483 height[p] = h;
484 }
485 }
486 }
487 // Bundle each op was placed in.
488 let mut at: Vec<Option<usize>> = vec![None; n];
489 // Ops not yet placed.
490 let mut remaining: Vec<usize> = (0..n).collect();
491 // Per bundle, the op in each of the M, A and T slots.
492 let mut bundles: Vec<[Option<usize>; 3]> = Vec::new();
493 // Fill one bundle at a time, greedily.
494 while !remaining.is_empty() {
495 // Index of the bundle being filled.
496 let b = bundles.len();
497 let mut slots = [None; 3];
498 // Slots are filled M, A, then T. The only non-strict edges go
499 // from bank-L readers (M or A slot) to a scan, so the readers
500 // placed in this bundle are already recorded when the scan is
501 // tested.
502 for slot in 0..3 {
503 let mut best: Option<usize> = None;
504 for &i in &remaining {
505 if self.ops[i].0.slot() != slot || at[i].is_some() {
506 continue;
507 }
508 // Every predecessor is in an earlier bundle, or in this
509 // one for a non-strict edge.
510 let ready = preds[i].iter().all(|&(p, strict)| match at[p] {
511 Some(pb) => pb < b || (!strict && pb == b),
512 None => false,
513 });
514 // Highest wins; ties go to the earliest op in program order.
515 if ready && best.is_none_or(|j| height[i] > height[j]) {
516 best = Some(i);
517 }
518 }
519 if let Some(i) = best {
520 slots[slot] = Some(i);
521 at[i] = Some(b);
522 }
523 }
524 assert!(slots.iter().any(Option::is_some), "scheduler deadlock");
525 remaining.retain(|&i| at[i].is_none());
526 bundles.push(slots);
527 }
528
529 // Value lifetimes and bank register allocation.
530 // Value id -> last bundle that reads it.
531 let mut last_use: HashMap<u32, usize> = HashMap::new();
532 for i in 0..n {
533 for u in self.ops[i].0.uses() {
534 if let V::Val(v) = u {
535 let e = last_use.entry(v).or_insert(0);
536 *e = (*e).max(at[i].unwrap());
537 }
538 }
539 }
540 // Value id -> physical register in its bank (M or A by defining slot).
541 let mut phys: HashMap<u32, u8> = HashMap::new();
542 // Registers used in banks M and A (high-water marks).
543 let mut banks_used = [0usize; 2];
544 // Free-at bundle for each physical register in banks M and A.
545 let mut busy: [Vec<usize>; 2] = [Vec::new(), Vec::new()];
546 // Linear scan in bundle order. A register is reusable in bundle `b`
547 // once its last read is in bundle `b` or earlier: reads precede
548 // writes within a bundle, so the new value can overwrite it there.
549 for (b, slots) in bundles.iter().enumerate() {
550 // Only the M and A slots define values.
551 for slot in 0..2 {
552 let Some(i) = slots[slot] else { continue };
553 let Some(v) = self.ops[i].1 else { continue };
554 // A value that is never read is free again after its own
555 // bundle.
556 let end = *last_use.get(&v).unwrap_or(&b);
557 let regs = &mut busy[slot];
558 // First free register, or a new one.
559 let reg = match regs.iter().position(|&free| free <= b) {
560 Some(r) => r,
561 None => {
562 regs.push(0);
563 regs.len() - 1
564 }
565 };
566 regs[reg] = end.max(b);
567 phys.insert(v, reg as u8);
568 banks_used[slot] = banks_used[slot].max(reg + 1);
569 }
570 }
571 // Virtual value -> physical operand. A computed value lives in the
572 // bank of the unit that produced it.
573 let operand = |u: V| -> Operand {
574 match u {
575 V::Val(v) => {
576 let kind = self.ops[def_op[&v]].0;
577 Operand {
578 bank: if kind.slot() == 0 { Bank::M } else { Bank::A },
579 index: phys[&v],
580 }
581 }
582 V::Const(c) => Operand {
583 bank: Bank::C,
584 index: c,
585 },
586 V::Input(k) => Operand {
587 bank: Bank::I,
588 index: k,
589 },
590 V::L(k) => Operand {
591 bank: Bank::L,
592 index: k,
593 },
594 }
595 };
596 // Dummy second operand for `Out`, which reads only `a`.
597 let zero = Operand {
598 bank: Bank::C,
599 index: 0,
600 };
601 // Emit the physical bundles and count operations per slot.
602 let mut out = Vec::with_capacity(bundles.len());
603 let (mut mul_ops, mut add_ops, mut scan_ops) = (0, 0, 0);
604 for slots in &bundles {
605 let mut bundle = Bundle::default();
606 if let Some(i) = slots[0] {
607 let Kind::Mul(a, b) = self.ops[i].0 else {
608 unreachable!()
609 };
610 bundle.m = Some(MSlot {
611 dst: phys[&self.ops[i].1.unwrap()],
612 a: operand(a),
613 b: operand(b),
614 });
615 mul_ops += 1;
616 }
617 if let Some(i) = slots[1] {
618 add_ops += 1;
619 bundle.a = Some(match self.ops[i].0 {
620 Kind::Add(a, b) | Kind::Sub(a, b) => ASlot {
621 op: if matches!(self.ops[i].0, Kind::Add(..)) {
622 AOp::Add
623 } else {
624 AOp::Sub
625 },
626 dst: phys[&self.ops[i].1.unwrap()],
627 a: operand(a),
628 b: operand(b),
629 },
630 Kind::Out(a, index) => ASlot {
631 op: AOp::Out(index),
632 dst: 0,
633 a: operand(a),
634 b: zero,
635 },
636 _ => unreachable!(),
637 });
638 }
639 if let Some(i) = slots[2] {
640 let Kind::Scan(t) = self.ops[i].0 else {
641 unreachable!()
642 };
643 bundle.t = Some(t);
644 scan_ops += 1;
645 }
646 out.push(bundle);
647 }
648 if let Some(last) = out.last_mut() {
649 last.end = true;
650 }
651 // The dummy `Out` operand reads C[0], so the bank needs an entry.
652 let mut consts = self.consts;
653 if consts.is_empty() {
654 consts.push(Fp::ZERO);
655 }
656 Program {
657 name,
658 bundles: out,
659 regs_m: banks_used[0],
660 regs_a: banks_used[1],
661 regs_i: max_input,
662 consts,
663 outputs: self.outputs as usize,
664 mul_ops,
665 add_ops,
666 scan_ops,
667 }
668 }
669}
670
671/// Per-context architectural state for [`interpret`].
672#[derive(Clone, Debug)]
673pub struct Context {
674 /// Bank M.
675 pub m: Vec<Fp>,
676 /// Bank A.
677 pub a: Vec<Fp>,
678 /// Bank I (inputs).
679 pub i: Vec<Fp>,
680 /// Bank L: the two lookup slots.
681 pub l: [Niels; 2],
682 /// Scan accumulator: the entry selected so far by the current lookup.
683 pub acc: Niels,
684 /// Signed mixed-radix digits ([`recode`](super::host::recode)): slots
685 /// `0..64` for the base-point scalar, `64..128` for the key scalar.
686 pub digits: [i8; 128],
687 /// The per-key table for key lookups.
688 pub key_table: Option<Vec<Vec<Niels>>>,
689}
690
691impl Context {
692 /// Fresh context with the given inputs and digits. Registers start at
693 /// zero, bank L and the accumulator at the identity, key digits at zero.
694 pub fn new(program: &Program, inputs: &[Fp], digits: [i8; 64]) -> Self {
695 // Bank I sized for whichever is larger: what the program reads or
696 // what the caller loads.
697 let mut i = vec![Fp::ZERO; program.regs_i.max(inputs.len())];
698 i[..inputs.len()].copy_from_slice(inputs);
699 Context {
700 m: vec![Fp::ZERO; program.regs_m],
701 a: vec![Fp::ZERO; program.regs_a],
702 i,
703 l: [Niels::identity(); 2],
704 acc: Niels::identity(),
705 digits: std::array::from_fn(|k| if k < 64 { digits[k] } else { 0 }),
706 key_table: None,
707 }
708 }
709
710 /// Context for a two-scalar program: base-point digits, key digits and
711 /// the key's table ([`point_table`](super::host::point_table)).
712 pub fn with_key(
713 program: &Program,
714 inputs: &[Fp],
715 base_digits: [i8; 64],
716 key_digits: [i8; 64],
717 key_table: Vec<Vec<Niels>>,
718 ) -> Self {
719 let mut ctx = Context::new(program, inputs, base_digits);
720 ctx.digits[64..].copy_from_slice(&key_digits);
721 ctx.key_table = Some(key_table);
722 ctx
723 }
724}
725
726/// Bit-exact reference execution of one context; returns `(index, value)` outputs.
727///
728/// Runs the bundles in order from the first and does not stop at an
729/// intermediate `end` flag, so it is meant for single programs rather than a
730/// [`concat()`] ROM.
731pub fn interpret(program: &Program, ctx: &mut Context) -> Vec<(u8, Fp)> {
732 let table = basepoint_table();
733 let mut outputs = Vec::new();
734 for bundle in &program.bundles {
735 // Register read for one operand.
736 let read = |o: Operand, ctx: &Context| -> Fp {
737 match o.bank {
738 Bank::M => ctx.m[o.index as usize],
739 Bank::A => ctx.a[o.index as usize],
740 Bank::I => ctx.i[o.index as usize],
741 Bank::C => program.consts[o.index as usize],
742 Bank::L => {
743 // Index is `4 * slot + coordinate`.
744 let l = ctx.l[(o.index >> 2) as usize];
745 match o.index & 3 {
746 0 => l.ypx,
747 1 => l.ymx,
748 _ => l.xy2d,
749 }
750 }
751 }
752 };
753 // All reads precede all writes inside one bundle.
754 // M slot: destination and product, computed from pre-bundle state.
755 let m = bundle
756 .m
757 .map(|s| (s.dst, read(s.a, ctx).mul(read(s.b, ctx))));
758 // A slot: operands read now, the result applied after the scan.
759 let a = bundle.a.map(|s| {
760 let (x, y) = (read(s.a, ctx), read(s.b, ctx));
761 (s.op, s.dst, x, y)
762 });
763 // T slot: runs after the reads above, so a commit to bank L is not
764 // seen by this bundle's M and A operands.
765 if let Some(t) = bundle.t {
766 let d = ctx.digits[t.digit as usize];
767 let mag = d.unsigned_abs();
768 if t.clear {
769 ctx.acc = Niels::identity();
770 }
771 // Table index: key digit slots `64 + i` use row `i` of the key table.
772 let row = (t.digit & 63) as usize;
773 // Both entries of the pair are examined; at most one matches.
774 for e in [2 * t.pair + 1, 2 * t.pair + 2] {
775 if mag == e {
776 ctx.acc = if t.key {
777 ctx.key_table.as_ref().expect("key lookup without a key table")[row][(e - 1) as usize]
778 } else {
779 table[row][(e - 1) as usize]
780 };
781 }
782 }
783 if t.finish {
784 ctx.l[t.l_slot as usize] = if d < 0 { ctx.acc.neg() } else { ctx.acc };
785 }
786 }
787 // Writes.
788 if let Some((dst, v)) = m {
789 ctx.m[dst as usize] = v;
790 }
791 if let Some((op, dst, x, y)) = a {
792 match op {
793 AOp::Add => ctx.a[dst as usize] = x.add(y),
794 AOp::Sub => ctx.a[dst as usize] = x.sub(y),
795 AOp::Out(index) => outputs.push((index, x)),
796 }
797 }
798 }
799 outputs
800}
801
802/// Several programs in one ROM: concatenated bundles, a shared constant
803/// bank (deduplicated), and the entry bundle of each program.
804///
805/// The machine addresses constants through bank I at `CONST_BASE + c`, above
806/// every program's inputs, so inputs keep their indices and only constant
807/// operands are re-indexed into the merged bank. Each program keeps its own
808/// `end` flag, so a context started at an entry retires at the end of that
809/// program. Register counts and `outputs` are the maximum over the programs
810/// (one context runs one program at a time); operation counts are sums.
811pub fn concat(name: &'static str, programs: &[&Program]) -> (Program, Vec<usize>) {
812 let regs_i = programs.iter().map(|p| p.regs_i).max().unwrap_or(0);
813 let mut consts: Vec<Fp> = Vec::new();
814 let mut bundles = Vec::new();
815 // First bundle of each program in the merged ROM.
816 let mut entries = Vec::new();
817 for p in programs {
818 // This program's constant index -> merged constant index, adding
819 // constants not yet in the merged bank.
820 let remap: Vec<u8> = p
821 .consts
822 .iter()
823 .map(|c| {
824 let at = consts.iter().position(|x| x == c).unwrap_or_else(|| {
825 consts.push(*c);
826 consts.len() - 1
827 });
828 at as u8
829 })
830 .collect();
831 // Rewrites constant operands; every other bank is per-context and
832 // unchanged.
833 let fix = |o: Operand| -> Operand {
834 if o.bank == Bank::C {
835 Operand { bank: Bank::C, index: remap[o.index as usize] }
836 } else {
837 o
838 }
839 };
840 entries.push(bundles.len());
841 for b in &p.bundles {
842 let mut b = *b;
843 if let Some(m) = &mut b.m {
844 m.a = fix(m.a);
845 m.b = fix(m.b);
846 }
847 if let Some(a) = &mut b.a {
848 a.a = fix(a.a);
849 a.b = fix(a.b);
850 }
851 bundles.push(b);
852 }
853 }
854 let program = Program {
855 name,
856 bundles,
857 regs_m: programs.iter().map(|p| p.regs_m).max().unwrap_or(0),
858 regs_a: programs.iter().map(|p| p.regs_a).max().unwrap_or(0),
859 regs_i,
860 consts,
861 outputs: programs.iter().map(|p| p.outputs).max().unwrap_or(0),
862 mul_ops: programs.iter().map(|p| p.mul_ops).sum(),
863 add_ops: programs.iter().map(|p| p.add_ops).sum(),
864 scan_ops: programs.iter().map(|p| p.scan_ops).sum(),
865 };
866 (program, entries)
867}