sp1_recursion_executor/
lib.rs

1pub mod analyzed;
2mod block;
3pub mod instruction;
4mod memory;
5mod opcode;
6mod program;
7mod public_values;
8mod record;
9pub mod shape;
10
11pub use analyzed::AnalyzedInstruction;
12pub use public_values::PV_DIGEST_NUM_WORDS;
13
14// Avoid triggering annoying branch of thiserror derive macro.
15use backtrace::Backtrace as Trace;
16pub use block::Block;
17use cfg_if::cfg_if;
18pub use instruction::Instruction;
19use instruction::{
20    FieldEltType, HintAddCurveInstr, HintBitsInstr, HintExt2FeltsInstr, HintInstr, PrintInstr,
21};
22use itertools::Itertools;
23use memory::*;
24pub use opcode::*;
25pub use program::*;
26pub use public_values::{RecursionPublicValues, NUM_PV_ELMS_TO_HASH, RECURSIVE_PROOF_NUM_PV_ELTS};
27pub use record::*;
28use serde::{Deserialize, Serialize};
29use slop_algebra::{
30    AbstractExtensionField, AbstractField, ExtensionField, PrimeField32, PrimeField64,
31};
32use slop_maybe_rayon::prelude::*;
33use slop_poseidon2::{Poseidon2, Poseidon2ExternalMatrixGeneral};
34use slop_symmetric::{CryptographicPermutation, Permutation};
35use sp1_derive::AlignedBorrow;
36use sp1_hypercube::{
37    operations::poseidon2::air::{external_linear_layer_mut, internal_linear_layer_mut},
38    septic_curve::SepticCurve,
39    septic_extension::SepticExtension,
40    MachineRecord,
41};
42use std::{
43    array,
44    borrow::Borrow,
45    cell::UnsafeCell,
46    collections::VecDeque,
47    fmt::Debug,
48    io::{stdout, Write},
49    iter::zip,
50    marker::PhantomData,
51    sync::{Arc, Mutex},
52};
53use thiserror::Error;
54use tracing::debug_span;
55
56/// The width of the Poseidon2 permutation.
57pub const PERMUTATION_WIDTH: usize = 16;
58pub const POSEIDON2_SBOX_DEGREE: u64 = 3;
59pub const HASH_RATE: usize = 8;
60
61/// The current verifier implementation assumes that we are using a 256-bit hash with 32-bit
62/// elements.
63pub const DIGEST_SIZE: usize = 8;
64
65pub const NUM_BITS: usize = 31;
66
67pub const D: usize = 4;
68
69#[derive(
70    AlignedBorrow, Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize, Default,
71)]
72#[repr(transparent)]
73pub struct Address<F>(pub F);
74
75impl<F: PrimeField64> Address<F> {
76    #[inline]
77    pub fn as_usize(&self) -> usize {
78        self.0.as_canonical_u64() as usize
79    }
80}
81
82// -------------------------------------------------------------------------------------------------
83
84/// The inputs and outputs to an operation of the base field ALU.
85#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
86#[repr(C)]
87pub struct BaseAluIo<V> {
88    pub out: V,
89    pub in1: V,
90    pub in2: V,
91}
92
93pub type BaseAluEvent<F> = BaseAluIo<F>;
94
95/// An instruction invoking the extension field ALU.
96#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
97#[repr(C)]
98pub struct BaseAluInstr<F> {
99    pub opcode: BaseAluOpcode,
100    pub mult: F,
101    pub addrs: BaseAluIo<Address<F>>,
102}
103
104// -------------------------------------------------------------------------------------------------
105
106/// The inputs and outputs to an operation of the extension field ALU.
107#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
108#[repr(C)]
109pub struct ExtAluIo<V> {
110    pub out: V,
111    pub in1: V,
112    pub in2: V,
113}
114
115pub type ExtAluEvent<F> = ExtAluIo<Block<F>>;
116
117/// An instruction invoking the extension field ALU.
118#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
119#[repr(C)]
120pub struct ExtAluInstr<F> {
121    pub opcode: ExtAluOpcode,
122    pub mult: F,
123    pub addrs: ExtAluIo<Address<F>>,
124}
125
126// -------------------------------------------------------------------------------------------------
127
128/// The inputs and outputs to the manual memory management/memory initialization table.
129#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
130#[repr(C)]
131pub struct MemIo<V> {
132    pub inner: V,
133}
134
135#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
136pub struct MemInstr<F> {
137    pub addrs: MemIo<Address<F>>,
138    pub vals: MemIo<Block<F>>,
139    pub mult: F,
140    pub kind: MemAccessKind,
141}
142
143pub type MemEvent<F> = MemIo<Block<F>>;
144
145// -------------------------------------------------------------------------------------------------
146
147#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
148pub enum MemAccessKind {
149    Read,
150    Write,
151}
152
153/// The inputs and outputs to a Poseidon2 permutation.
154#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
155#[repr(C)]
156pub struct Poseidon2Io<V> {
157    pub input: [V; PERMUTATION_WIDTH],
158    pub output: [V; PERMUTATION_WIDTH],
159}
160
161/// An instruction invoking the Poseidon2 permutation.
162#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
163#[repr(C)]
164pub struct Poseidon2Instr<F> {
165    pub addrs: Poseidon2Io<Address<F>>,
166    pub mults: [F; PERMUTATION_WIDTH],
167}
168
169pub type Poseidon2Event<F> = Poseidon2Io<F>;
170
171/// The inputs and outputs to a Poseidon2 permutation linear layers.
172/// The `4` here is calculated from `PERMUTATION_WIDTH / D`.
173#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
174#[repr(C)]
175pub struct Poseidon2LinearLayerIo<V> {
176    pub input: [V; 4],
177    pub output: [V; 4],
178}
179
180/// An instruction invoking the Poseidon2 permutation linear layers.
181#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
182#[repr(C)]
183pub struct Poseidon2LinearLayerInstr<F> {
184    pub addrs: Poseidon2LinearLayerIo<Address<F>>,
185    pub mults: [F; 4],
186    pub external: bool,
187}
188
189pub type Poseidon2LinearLayerEvent<F> = Poseidon2LinearLayerIo<Block<F>>;
190
191/// The inputs and outputs to an SBOX operation.
192#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
193#[repr(C)]
194pub struct Poseidon2SBoxIo<V> {
195    pub input: V,
196    pub output: V,
197}
198
199/// An instruction invoking the SBOX operation.
200#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
201#[repr(C)]
202pub struct Poseidon2SBoxInstr<F> {
203    pub addrs: Poseidon2SBoxIo<Address<F>>,
204    pub mults: F,
205    pub external: bool,
206}
207
208pub type Poseidon2SBoxEvent<F> = Poseidon2SBoxIo<Block<F>>;
209
210/// An instruction invoking the ext2felt or felt2ext operation.
211/// This `5` is derived from `D + 1`. The first address is the extension, and the rest are felts.
212#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
213#[repr(C)]
214pub struct ExtFeltInstr<F> {
215    pub addrs: [Address<F>; 5],
216    pub mults: [F; 5],
217    pub ext2felt: bool,
218}
219
220/// An event recording an ext2felt or felt2ext operation.
221#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
222#[repr(C)]
223pub struct ExtFeltEvent<F> {
224    pub input: Block<F>,
225}
226
227/// The inputs and outputs to a select operation.
228#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
229#[repr(C)]
230pub struct SelectIo<V> {
231    pub bit: V,
232    pub out1: V,
233    pub out2: V,
234    pub in1: V,
235    pub in2: V,
236}
237
238/// An instruction invoking the select operation.
239#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
240#[repr(C)]
241pub struct SelectInstr<F> {
242    pub addrs: SelectIo<Address<F>>,
243    pub mult1: F,
244    pub mult2: F,
245}
246
247/// The event encoding the inputs and outputs of a select operation.
248pub type SelectEvent<F> = SelectIo<F>;
249
250/// The inputs and outputs to the operations for prefix sum checks.
251#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
252pub struct PrefixSumChecksIo<V> {
253    pub zero: V,
254    pub one: V,
255    pub x1: Vec<V>,
256    pub x2: Vec<V>,
257    pub accs: Vec<V>,
258    pub field_accs: Vec<V>,
259}
260
261/// An instruction invoking the PrefixSumChecks operation.
262#[derive(Clone, Debug, Serialize, Deserialize)]
263pub struct PrefixSumChecksInstr<F> {
264    pub addrs: PrefixSumChecksIo<Address<F>>,
265    pub acc_mults: Vec<F>,
266    pub field_acc_mults: Vec<F>,
267}
268
269/// The event encoding the inputs and outputs of an PrefixSumChecks operation.
270#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
271#[repr(C)]
272pub struct PrefixSumChecksEvent<F> {
273    pub x1: F,
274    pub x2: Block<F>,
275    pub zero: F,
276    pub one: Block<F>,
277    pub acc: Block<F>,
278    pub new_acc: Block<F>,
279    pub field_acc: F,
280    pub new_field_acc: F,
281}
282
283/// An instruction that will save the public values to the execution record and will commit to
284/// it's digest.
285#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
286#[repr(C)]
287pub struct CommitPublicValuesInstr<F> {
288    pub pv_addrs: RecursionPublicValues<Address<F>>,
289}
290
291/// The event for committing to the public values.
292#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
293#[repr(C)]
294pub struct CommitPublicValuesEvent<F> {
295    pub public_values: RecursionPublicValues<F>,
296}
297
298type Perm<F, Diffusion> = Poseidon2<
299    F,
300    Poseidon2ExternalMatrixGeneral,
301    Diffusion,
302    PERMUTATION_WIDTH,
303    POSEIDON2_SBOX_DEGREE,
304>;
305
306/// TODO fully document.
307/// Taken from [`sp1_recursion_executor::executor::Runtime`].
308/// Many missing things (compared to the old `Runtime`) will need to be implemented.
309pub struct Executor<'a, F: PrimeField32, EF: ExtensionField<F>, Diffusion> {
310    /// The program.
311    pub program: Arc<RecursionProgram<F>>,
312
313    /// Memory. From canonical usize of an Address to a MemoryEntry.
314    pub memory: MemVec<F>,
315
316    /// The execution record.
317    pub record: ExecutionRecord<F>,
318
319    pub witness_stream: VecDeque<Block<F>>,
320
321    /// The stream that print statements write to.
322    pub debug_stdout: Box<dyn Write + Send + 'a>,
323
324    /// Entries for dealing with the Poseidon2 hash state.
325    perm: Option<Perm<F, Diffusion>>,
326
327    _marker_ef: PhantomData<EF>,
328
329    _marker_diffusion: PhantomData<Diffusion>,
330}
331
332#[derive(Error, Debug)]
333pub enum RuntimeError<F: Debug, EF: Debug> {
334    #[error(
335        "attempted to perform base field division {in1:?}/{in2:?}\n\
336        \tin instruction {instr:#?}\n\
337        \tnearest backtrace:\n{trace:#?}"
338    )]
339    DivFOutOfDomain { in1: F, in2: F, instr: BaseAluInstr<F>, trace: Option<Trace> },
340    #[error(
341        "attempted to perform extension field division {in1:?}/{in2:?}\n\
342        \tin instruction {instr:#?}\n\
343        \tnearest backtrace:\n{trace:#?}"
344    )]
345    DivEOutOfDomain { in1: EF, in2: EF, instr: ExtAluInstr<F>, trace: Option<Trace> },
346    #[error("failed to print to `debug_stdout`: {0}")]
347    DebugPrint(#[from] std::io::Error),
348    #[error("attempted to read from empty witness stream")]
349    EmptyWitnessStream,
350}
351
352impl<F: PrimeField32, EF: ExtensionField<F>, Diffusion> Executor<'_, F, EF, Diffusion>
353where
354    Poseidon2<
355        F,
356        Poseidon2ExternalMatrixGeneral,
357        Diffusion,
358        PERMUTATION_WIDTH,
359        POSEIDON2_SBOX_DEGREE,
360    >: CryptographicPermutation<[F; PERMUTATION_WIDTH]>,
361{
362    pub fn new(
363        program: Arc<RecursionProgram<F>>,
364        perm: Poseidon2<
365            F,
366            Poseidon2ExternalMatrixGeneral,
367            Diffusion,
368            PERMUTATION_WIDTH,
369            POSEIDON2_SBOX_DEGREE,
370        >,
371    ) -> Self {
372        let record = ExecutionRecord::<F> { program: program.clone(), ..Default::default() };
373        let memory = MemVec::with_capacity(program.total_memory);
374        Self {
375            program,
376            memory,
377            record,
378            witness_stream: VecDeque::new(),
379            debug_stdout: Box::new(stdout()),
380            perm: Some(perm),
381            _marker_ef: PhantomData,
382            _marker_diffusion: PhantomData,
383        }
384    }
385
386    pub fn print_stats(&self) {
387        if tracing::event_enabled!(tracing::Level::DEBUG) {
388            let mut stats = self.record.stats().into_iter().collect::<Vec<_>>();
389            stats.sort_unstable();
390            tracing::debug!("total events: {}", stats.iter().map(|(_, v)| *v).sum::<usize>());
391            for (k, v) in stats {
392                tracing::debug!("  {k}: {v}");
393            }
394        }
395    }
396
397    /// # Safety
398    ///
399    /// Safety is guaranteed if calls to this function (with the given `env` argument) obey the
400    /// happens-before relation defined in the documentation of [`RecursionProgram::new_unchecked`].
401    ///
402    /// This function makes use of interior mutability of `env` via `UnsafeCell`.
403    /// All of this function's unsafety stems from the `instruction` argument that indicates'
404    /// whether/how to read and write from the memory in `env`. There must be a strict
405    /// happens-before relation where reads happen before writes, and memory read from must be
406    /// initialized.
407    unsafe fn execute_one(
408        state: &mut ExecState<F, Diffusion>,
409        record: &UnsafeRecord<F>,
410        witness_stream: Option<&mut VecDeque<Block<F>>>,
411        analyzed_instruction: &AnalyzedInstruction<F>,
412    ) -> Result<(), RuntimeError<F, EF>> {
413        let ExecEnv { memory, perm, debug_stdout } = state.env;
414        let instruction = &analyzed_instruction.inner;
415        let offset = analyzed_instruction.offset;
416
417        match *instruction {
418            Instruction::BaseAlu(ref instr @ BaseAluInstr { opcode, mult: _, addrs }) => {
419                let in1 = memory.mr_unchecked(addrs.in1).val[0];
420                let in2 = memory.mr_unchecked(addrs.in2).val[0];
421                // Do the computation.
422                let out = match opcode {
423                    BaseAluOpcode::AddF => in1 + in2,
424                    BaseAluOpcode::SubF => in1 - in2,
425                    BaseAluOpcode::MulF => in1 * in2,
426                    BaseAluOpcode::DivF => match in1.try_div(in2) {
427                        Some(x) => x,
428                        None => {
429                            // Check for division exceptions and error. Note that 0/0 is defined
430                            // to be 1.
431                            if in1.is_zero() {
432                                AbstractField::one()
433                            } else {
434                                return Err(RuntimeError::DivFOutOfDomain {
435                                    in1,
436                                    in2,
437                                    instr: *instr,
438                                    trace: state.resolve_trace().cloned(),
439                                });
440                            }
441                        }
442                    },
443                };
444                memory.mw_unchecked(addrs.out, Block::from(out));
445                // Write the event to the record.
446                UnsafeCell::raw_get(record.base_alu_events[offset].as_ptr()).write(BaseAluEvent {
447                    out,
448                    in1,
449                    in2,
450                });
451            }
452            Instruction::ExtAlu(ref instr @ ExtAluInstr { opcode, mult: _, addrs }) => {
453                let in1 = memory.mr_unchecked(addrs.in1).val;
454                let in2 = memory.mr_unchecked(addrs.in2).val;
455                // Do the computation.
456                let in1_ef = EF::from_base_fn(|i| in1.0[i]);
457                let in2_ef = EF::from_base_fn(|i| in2.0[i]);
458                let out_ef = match opcode {
459                    ExtAluOpcode::AddE => in1_ef + in2_ef,
460                    ExtAluOpcode::SubE => in1_ef - in2_ef,
461                    ExtAluOpcode::MulE => in1_ef * in2_ef,
462                    ExtAluOpcode::DivE => match in1_ef.try_div(in2_ef) {
463                        Some(x) => x,
464                        None => {
465                            // Check for division exceptions and error. Note that 0/0 is defined
466                            // to be 1.
467                            if in1_ef.is_zero() {
468                                AbstractField::one()
469                            } else {
470                                return Err(RuntimeError::DivEOutOfDomain {
471                                    in1: in1_ef,
472                                    in2: in2_ef,
473                                    instr: *instr,
474                                    trace: state.resolve_trace().cloned(),
475                                });
476                            }
477                        }
478                    },
479                };
480                let out = Block::from(out_ef.as_base_slice());
481                memory.mw_unchecked(addrs.out, out);
482
483                // Write the event to the record.
484                UnsafeCell::raw_get(record.ext_alu_events[offset].as_ptr()).write(ExtAluEvent {
485                    out,
486                    in1,
487                    in2,
488                });
489            }
490            Instruction::Mem(MemInstr {
491                addrs: MemIo { inner: addr },
492                vals: MemIo { inner: val },
493                mult: _,
494                kind,
495            }) => match kind {
496                MemAccessKind::Read => {
497                    let mem_entry = memory.mr_unchecked(addr);
498                    assert_eq!(
499                        mem_entry.val, val,
500                        "stored memory value should be the specified value"
501                    );
502                }
503                MemAccessKind::Write => memory.mw_unchecked(addr, val),
504            },
505            Instruction::ExtFelt(ExtFeltInstr { addrs, mults: _, ext2felt }) => {
506                if ext2felt {
507                    let in_val = memory.mr_unchecked(addrs[0]).val;
508                    for (addr, value) in addrs[1..].iter().zip_eq(in_val.0) {
509                        memory.mw_unchecked(*addr, Block::from(value));
510                    }
511                    // Write the event to the record.
512                    UnsafeCell::raw_get(record.ext_felt_conversion_events[offset].as_ptr())
513                        .write(ExtFeltEvent { input: in_val });
514                } else {
515                    let in_val = Block([
516                        memory.mr_unchecked(addrs[1]).val.0[0],
517                        memory.mr_unchecked(addrs[2]).val.0[0],
518                        memory.mr_unchecked(addrs[3]).val.0[0],
519                        memory.mr_unchecked(addrs[4]).val.0[0],
520                    ]);
521                    memory.mw_unchecked(addrs[0], in_val);
522                    // Write the event to the record.
523                    UnsafeCell::raw_get(record.ext_felt_conversion_events[offset].as_ptr())
524                        .write(ExtFeltEvent { input: in_val });
525                }
526            }
527            Instruction::Poseidon2(ref instr) => {
528                let Poseidon2Instr { addrs: Poseidon2Io { input, output }, mults: _ } =
529                    instr.as_ref();
530                let in_vals = std::array::from_fn(|i| memory.mr_unchecked(input[i]).val[0]);
531                let perm_output = perm.permute(in_vals);
532
533                perm_output.iter().zip(output).for_each(|(&val, addr)| {
534                    memory.mw_unchecked(*addr, Block::from(val));
535                });
536
537                // Write the event to the record.
538                UnsafeCell::raw_get(record.poseidon2_events[offset].as_ptr())
539                    .write(Poseidon2Event { input: in_vals, output: perm_output });
540            }
541            Instruction::Poseidon2LinearLayer(ref instr) => {
542                let Poseidon2LinearLayerInstr {
543                    addrs: Poseidon2LinearLayerIo { input, output },
544                    mults: _,
545                    external,
546                } = instr.as_ref();
547                let mut state = [F::zero(); PERMUTATION_WIDTH];
548                let mut io_input = [Block::from(F::zero()); PERMUTATION_WIDTH / D];
549                let mut io_output = [Block::from(F::zero()); PERMUTATION_WIDTH / D];
550                for i in 0..PERMUTATION_WIDTH / D {
551                    io_input[i] = memory.mr_unchecked(input[i]).val;
552                    for j in 0..D {
553                        state[i * D + j] = io_input[i].0[j];
554                    }
555                }
556                if *external {
557                    external_linear_layer_mut(&mut state);
558                } else {
559                    internal_linear_layer_mut(&mut state);
560                }
561                for i in 0..PERMUTATION_WIDTH / D {
562                    io_output[i] = Block(state[i * D..i * D + D].try_into().unwrap());
563                    memory.mw_unchecked(output[i], io_output[i]);
564                }
565
566                // Write the event to the record.
567                UnsafeCell::raw_get(record.poseidon2_linear_layer_events[offset].as_ptr())
568                    .write(Poseidon2LinearLayerEvent { input: io_input, output: io_output });
569            }
570            Instruction::Poseidon2SBox(Poseidon2SBoxInstr {
571                addrs: Poseidon2SBoxIo { input, output },
572                mults: _,
573                external,
574            }) => {
575                let io_input = memory.mr_unchecked(input).val;
576                let pow7 = |x: F| -> F { x * x * x };
577
578                let io_output = if external {
579                    Block([
580                        pow7(io_input.0[0]),
581                        pow7(io_input.0[1]),
582                        pow7(io_input.0[2]),
583                        pow7(io_input.0[3]),
584                    ])
585                } else {
586                    Block([pow7(io_input.0[0]), io_input.0[1], io_input.0[2], io_input.0[3]])
587                };
588                memory.mw_unchecked(output, io_output);
589
590                // Write the event to the record.
591                UnsafeCell::raw_get(record.poseidon2_sbox_events[offset].as_ptr())
592                    .write(Poseidon2SBoxEvent { input: io_input, output: io_output });
593            }
594            Instruction::Select(SelectInstr {
595                addrs: SelectIo { bit, out1, out2, in1, in2 },
596                mult1: _,
597                mult2: _,
598            }) => {
599                let bit = memory.mr_unchecked(bit).val[0];
600                let in1 = memory.mr_unchecked(in1).val[0];
601                let in2 = memory.mr_unchecked(in2).val[0];
602                let out1_val = bit * in2 + (F::one() - bit) * in1;
603                let out2_val = bit * in1 + (F::one() - bit) * in2;
604                memory.mw_unchecked(out1, Block::from(out1_val));
605                memory.mw_unchecked(out2, Block::from(out2_val));
606
607                // Write the event to the record.
608                UnsafeCell::raw_get(record.select_events[offset].as_ptr()).write(SelectEvent {
609                    bit,
610                    out1: out1_val,
611                    out2: out2_val,
612                    in1,
613                    in2,
614                });
615            }
616            Instruction::HintBits(HintBitsInstr { ref output_addrs_mults, input_addr }) => {
617                let num = memory.mr_unchecked(input_addr).val[0].as_canonical_u32();
618                // Decompose the num into LE bits.
619                let bits = (0..output_addrs_mults.len())
620                    .map(|i| Block::from(F::from_canonical_u32((num >> i) & 1)))
621                    .collect::<Vec<_>>();
622
623                // Write the bits to the array at dst.
624                for (i, (bit, &(addr, _mult))) in
625                    bits.into_iter().zip(output_addrs_mults).enumerate()
626                {
627                    memory.mw_unchecked(addr, bit);
628
629                    // Write the event to the record.
630                    UnsafeCell::raw_get(record.mem_var_events[offset + i].as_ptr())
631                        .write(MemEvent { inner: bit });
632                }
633            }
634            Instruction::HintAddCurve(ref instr) => {
635                let HintAddCurveInstr {
636                    output_x_addrs_mults,
637                    output_y_addrs_mults,
638                    input1_x_addrs,
639                    input1_y_addrs,
640                    input2_x_addrs,
641                    input2_y_addrs,
642                } = instr.as_ref();
643                let input1_x = SepticExtension::<F>::from_base_fn(|i| {
644                    memory.mr_unchecked(input1_x_addrs[i]).val[0]
645                });
646                let input1_y = SepticExtension::<F>::from_base_fn(|i| {
647                    memory.mr_unchecked(input1_y_addrs[i]).val[0]
648                });
649                let input2_x = SepticExtension::<F>::from_base_fn(|i| {
650                    memory.mr_unchecked(input2_x_addrs[i]).val[0]
651                });
652                let input2_y = SepticExtension::<F>::from_base_fn(|i| {
653                    memory.mr_unchecked(input2_y_addrs[i]).val[0]
654                });
655                let point1 = SepticCurve { x: input1_x, y: input1_y };
656                let point2 = SepticCurve { x: input2_x, y: input2_y };
657                let output = point1.add_incomplete(point2);
658
659                for (i, (val, &(addr, _mult))) in output
660                    .x
661                    .0
662                    .into_iter()
663                    .zip(output_x_addrs_mults.iter())
664                    .chain(output.y.0.into_iter().zip(output_y_addrs_mults.iter()))
665                    .enumerate()
666                {
667                    memory.mw_unchecked(addr, Block::from(val));
668
669                    UnsafeCell::raw_get(record.mem_var_events[offset + i].as_ptr())
670                        .write(MemEvent { inner: Block::from(val) });
671                }
672            }
673            Instruction::PrefixSumChecks(ref instr) => {
674                let PrefixSumChecksInstr {
675                    addrs: PrefixSumChecksIo { zero, one, x1, x2, accs, field_accs },
676                    acc_mults: _,
677                    field_acc_mults: _,
678                } = instr.as_ref();
679                let zero = memory.mr_unchecked(*zero).val[0];
680                let one = memory.mr_unchecked(*one).val.ext::<EF>();
681                let x1_f = x1.iter().map(|addr| memory.mr_unchecked(*addr).val[0]).collect_vec();
682                let x2_ef =
683                    x2.iter().map(|addr| memory.mr_unchecked(*addr).val.ext::<EF>()).collect_vec();
684
685                let mut acc = EF::one();
686                let mut field_acc = F::zero();
687                for m in 0..x1_f.len() {
688                    let product = EF::from_base(x1_f[m]) * x2_ef[m];
689                    let lagrange_term = EF::one() - x1_f[m] - x2_ef[m] + product + product;
690                    let new_field_acc = x1_f[m] + field_acc * F::from_canonical_u32(2);
691                    let new_acc = acc * lagrange_term;
692
693                    UnsafeCell::raw_get(record.prefix_sum_checks_events[offset + m].as_ptr())
694                        .write(PrefixSumChecksEvent {
695                            zero,
696                            one: Block::from(one.as_base_slice()),
697                            x1: x1_f[m],
698                            x2: Block::from(x2_ef[m].as_base_slice()),
699                            acc: Block::from(acc.as_base_slice()),
700                            new_acc: Block::from(new_acc.as_base_slice()),
701                            field_acc,
702                            new_field_acc,
703                        });
704
705                    acc = new_acc;
706                    field_acc = new_field_acc;
707                    memory.mw_unchecked(accs[m], Block::from(acc.as_base_slice()));
708                    memory.mw_unchecked(field_accs[m], Block::from(field_acc));
709                }
710            }
711            Instruction::CommitPublicValues(ref instr) => {
712                let pv_addrs = instr.pv_addrs.as_array();
713                let pv_values: [F; RECURSIVE_PROOF_NUM_PV_ELTS] =
714                    array::from_fn(|i| memory.mr_unchecked(pv_addrs[i]).val[0]);
715
716                // Write the public values to the record.
717                UnsafeCell::raw_get(record.public_values.as_ptr())
718                    .write(*pv_values.as_slice().borrow());
719
720                // Write the event to the record.
721                UnsafeCell::raw_get(record.commit_pv_hash_events[offset].as_ptr()).write(
722                    CommitPublicValuesEvent { public_values: *pv_values.as_slice().borrow() },
723                );
724            }
725            Instruction::Print(PrintInstr { ref field_elt_type, addr }) => match field_elt_type {
726                FieldEltType::Base => {
727                    let f = memory.mr_unchecked(addr).val[0];
728                    writeln!(debug_stdout.lock().unwrap(), "PRINTF={f}")
729                }
730                FieldEltType::Extension => {
731                    let ef = memory.mr_unchecked(addr).val;
732                    writeln!(debug_stdout.lock().unwrap(), "PRINTEF={ef:?}")
733                }
734            }
735            .map_err(RuntimeError::DebugPrint)?,
736            Instruction::HintExt2Felts(HintExt2FeltsInstr { output_addrs_mults, input_addr }) => {
737                let fs = memory.mr_unchecked(input_addr).val;
738                // Write the bits to the array at dst.
739                for (i, (f, (addr, _mult))) in fs.into_iter().zip(output_addrs_mults).enumerate() {
740                    let felt = Block::from(f);
741                    memory.mw_unchecked(addr, felt);
742
743                    // Write the event to the record.
744                    UnsafeCell::raw_get(record.mem_var_events[offset + i].as_ptr())
745                        .write(MemEvent { inner: felt });
746                }
747            }
748            Instruction::Hint(HintInstr { ref output_addrs_mults }) => {
749                let witness_stream =
750                    witness_stream.expect("hint should be called outside parallel contexts");
751                // Check that enough Blocks can be read, so `drain` does not panic.
752                if witness_stream.len() < output_addrs_mults.len() {
753                    return Err(RuntimeError::EmptyWitnessStream);
754                }
755
756                let witness = witness_stream.drain(0..output_addrs_mults.len());
757                for (i, (&(addr, _mult), val)) in zip(output_addrs_mults, witness).enumerate() {
758                    // Inline [`Self::mw`] to mutably borrow multiple fields of `self`.
759                    memory.mw_unchecked(addr, val);
760
761                    // Write the event to the record.
762                    UnsafeCell::raw_get(record.mem_var_events[offset + i].as_ptr())
763                        .write(MemEvent { inner: val });
764                }
765            }
766            Instruction::DebugBacktrace(ref backtrace) => {
767                cfg_if! {
768                    if #[cfg(feature = "debug")] {
769                        state.last_trace = Some(backtrace.clone());
770                    } else {
771                        // Ignore.
772                        let _ = backtrace;
773                    }
774                }
775            }
776        }
777
778        Ok(())
779    }
780
781    unsafe fn execute_raw(
782        env: &ExecEnv<F, Diffusion>,
783        root_program: &Arc<RecursionProgram<F>>,
784        witness_stream: Option<&mut VecDeque<Block<F>>>,
785    ) -> Result<ExecutionRecord<F>, RuntimeError<F, EF>> {
786        let root_record = UnsafeRecord::<F>::new(root_program.event_counts);
787        debug_span!("root").in_scope(|| {
788            Self::execute_raw_inner(env, &root_program.inner, witness_stream, &root_record)
789        })?;
790
791        // SAFETY: `root_record` has been populated by the executor.
792        let record = root_record.into_record(Arc::clone(root_program), 0);
793        Ok(record)
794    }
795
796    /// # Safety
797    ///
798    /// This function makes the same safety assumptions as [`RecursionProgram::new_unchecked`].
799    unsafe fn execute_raw_inner(
800        env: &ExecEnv<F, Diffusion>,
801        program: &RawProgram<AnalyzedInstruction<F>>,
802        mut witness_stream: Option<&mut VecDeque<Block<F>>>,
803        record: &UnsafeRecord<F>,
804    ) -> Result<(), RuntimeError<F, EF>> {
805        let mut state = ExecState {
806            env: env.clone(),
807            #[cfg(feature = "debug")]
808            last_trace: None,
809        };
810
811        for block in &program.seq_blocks {
812            match block {
813                SeqBlock::Basic(basic_block) => {
814                    for analyzed_instruction in &basic_block.instrs {
815                        unsafe {
816                            Self::execute_one(
817                                &mut state,
818                                record,
819                                witness_stream.as_deref_mut(),
820                                analyzed_instruction,
821                            )
822                        }?;
823                    }
824                }
825                SeqBlock::Parallel(vec) => {
826                    vec.par_iter().try_for_each(|subprogram| {
827                        Self::execute_raw_inner(env, subprogram, None, record)
828                    })?;
829                }
830            }
831        }
832
833        Ok(())
834    }
835
836    /// Run the program.
837    pub fn run(&mut self) -> Result<(), RuntimeError<F, EF>> {
838        let record = unsafe {
839            Self::execute_raw(
840                &ExecEnv {
841                    memory: &self.memory,
842                    perm: self.perm.as_ref().unwrap(),
843                    debug_stdout: &Mutex::new(&mut self.debug_stdout),
844                },
845                &self.program,
846                Some(&mut self.witness_stream),
847            )
848        }?;
849
850        self.record = record;
851
852        Ok(())
853    }
854}
855
856struct ExecState<'a, 'b, F, Diffusion> {
857    pub env: ExecEnv<'a, 'b, F, Diffusion>,
858    // pub record: Arc<UnsafeRecord<F>>,
859    #[cfg(feature = "debug")]
860    pub last_trace: Option<Trace>,
861}
862
863impl<F, Diffusion> ExecState<'_, '_, F, Diffusion> {
864    fn resolve_trace(&mut self) -> Option<&mut Trace> {
865        cfg_if::cfg_if! {
866            if #[cfg(feature = "debug")] {
867                // False positive.
868                #[allow(clippy::manual_inspect)]
869                self.last_trace.as_mut().map(|trace| {
870                    trace.resolve();
871                    trace
872                })
873            } else {
874                None
875            }
876        }
877    }
878}
879
880impl<'a, 'b, F, Diffusion> Clone for ExecState<'a, 'b, F, Diffusion>
881where
882    ExecEnv<'a, 'b, F, Diffusion>: Clone,
883    ExecutionRecord<F>: Clone,
884{
885    fn clone(&self) -> Self {
886        let Self {
887            env,
888            // record,
889            #[cfg(feature = "debug")]
890            last_trace,
891        } = self;
892        Self {
893            env: env.clone(),
894            // record: record.clone(),
895            #[cfg(feature = "debug")]
896            last_trace: last_trace.clone(),
897        }
898    }
899
900    fn clone_from(&mut self, source: &Self) {
901        let Self {
902            env,
903            // record,
904            #[cfg(feature = "debug")]
905            last_trace,
906        } = self;
907        env.clone_from(&source.env);
908        // record.clone_from(&source.record);
909        #[cfg(feature = "debug")]
910        last_trace.clone_from(&source.last_trace);
911    }
912}
913
914struct ExecEnv<'a, 'b, F, Diffusion> {
915    pub memory: &'a MemVec<F>,
916    pub perm: &'a Perm<F, Diffusion>,
917    pub debug_stdout: &'a Mutex<dyn Write + Send + 'b>,
918}
919
920impl<F, Diffusion> Clone for ExecEnv<'_, '_, F, Diffusion> {
921    fn clone(&self) -> Self {
922        let Self { memory, perm, debug_stdout } = self;
923        Self { memory, perm, debug_stdout }
924    }
925
926    fn clone_from(&mut self, source: &Self) {
927        let Self { memory, perm, debug_stdout } = self;
928        memory.clone_from(&source.memory);
929        perm.clone_from(&source.perm);
930        debug_stdout.clone_from(&source.debug_stdout);
931    }
932}
sp1_recursion_executor/lib.rs

sp1_recursion_executor/
lib.rs
