sp1_recursion_core/
lib.rs

1use p3_field::PrimeField64;
2use serde::{Deserialize, Serialize};
3use sp1_derive::AlignedBorrow;
4
5use crate::air::{Block, RecursionPublicValues};
6
7pub mod air;
8pub mod builder;
9pub mod chips;
10pub mod machine;
11pub mod runtime;
12pub mod shape;
13pub mod stark;
14#[cfg(feature = "sys")]
15pub mod sys;
16
17pub use runtime::*;
18
19// Re-export the stark stuff from `sp1_recursion_core` for now, until we will migrate it here.
20// pub use sp1_recursion_core::stark;
21
22use crate::chips::poseidon2_skinny::WIDTH;
23
24#[derive(
25    AlignedBorrow, Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize, Default,
26)]
27#[repr(transparent)]
28pub struct Address<F>(pub F);
29
30impl<F: PrimeField64> Address<F> {
31    #[inline]
32    pub fn as_usize(&self) -> usize {
33        self.0.as_canonical_u64() as usize
34    }
35}
36
37// -------------------------------------------------------------------------------------------------
38
39/// The inputs and outputs to an operation of the base field ALU.
40#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
41#[repr(C)]
42pub struct BaseAluIo<V> {
43    pub out: V,
44    pub in1: V,
45    pub in2: V,
46}
47
48pub type BaseAluEvent<F> = BaseAluIo<F>;
49
50/// An instruction invoking the extension field ALU.
51#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
52#[repr(C)]
53pub struct BaseAluInstr<F> {
54    pub opcode: BaseAluOpcode,
55    pub mult: F,
56    pub addrs: BaseAluIo<Address<F>>,
57}
58
59// -------------------------------------------------------------------------------------------------
60
61/// The inputs and outputs to an operation of the extension field ALU.
62#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
63#[repr(C)]
64pub struct ExtAluIo<V> {
65    pub out: V,
66    pub in1: V,
67    pub in2: V,
68}
69
70pub type ExtAluEvent<F> = ExtAluIo<Block<F>>;
71
72/// An instruction invoking the extension field ALU.
73#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
74#[repr(C)]
75pub struct ExtAluInstr<F> {
76    pub opcode: ExtAluOpcode,
77    pub mult: F,
78    pub addrs: ExtAluIo<Address<F>>,
79}
80
81// -------------------------------------------------------------------------------------------------
82
83/// The inputs and outputs to the manual memory management/memory initialization table.
84#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
85pub struct MemIo<V> {
86    pub inner: V,
87}
88
89#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
90pub struct MemInstr<F> {
91    pub addrs: MemIo<Address<F>>,
92    pub vals: MemIo<Block<F>>,
93    pub mult: F,
94    pub kind: MemAccessKind,
95}
96
97pub type MemEvent<F> = MemIo<Block<F>>;
98
99// -------------------------------------------------------------------------------------------------
100
101#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
102pub enum MemAccessKind {
103    Read,
104    Write,
105}
106
107/// The inputs and outputs to a Poseidon2 permutation.
108#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
109#[repr(C)]
110pub struct Poseidon2Io<V> {
111    pub input: [V; WIDTH],
112    pub output: [V; WIDTH],
113}
114
115/// An instruction invoking the Poseidon2 permutation.
116#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
117#[repr(C)]
118pub struct Poseidon2SkinnyInstr<F> {
119    pub addrs: Poseidon2Io<Address<F>>,
120    pub mults: [F; WIDTH],
121}
122
123pub type Poseidon2Event<F> = Poseidon2Io<F>;
124
125/// The inputs and outputs to a select operation.
126#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
127#[repr(C)]
128pub struct SelectIo<V> {
129    pub bit: V,
130    pub out1: V,
131    pub out2: V,
132    pub in1: V,
133    pub in2: V,
134}
135
136/// An instruction invoking the select operation.
137#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
138#[repr(C)]
139pub struct SelectInstr<F> {
140    pub addrs: SelectIo<Address<F>>,
141    pub mult1: F,
142    pub mult2: F,
143}
144
145/// The event encoding the inputs and outputs of a select operation.
146pub type SelectEvent<F> = SelectIo<F>;
147
148/// The inputs and outputs to an exp-reverse-bits operation.
149#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
150pub struct ExpReverseBitsIo<V> {
151    pub base: V,
152    // The bits of the exponent in little-endian order in a vec.
153    pub exp: Vec<V>,
154    pub result: V,
155}
156
157pub type Poseidon2WideEvent<F> = Poseidon2Io<F>;
158pub type Poseidon2Instr<F> = Poseidon2SkinnyInstr<F>;
159
160/// An instruction invoking the exp-reverse-bits operation.
161#[derive(Clone, Debug, Serialize, Deserialize)]
162pub struct ExpReverseBitsInstr<F> {
163    pub addrs: ExpReverseBitsIo<Address<F>>,
164    pub mult: F,
165}
166
167#[derive(Clone, Debug, PartialEq, Eq)]
168#[repr(C)]
169pub struct ExpReverseBitsInstrFFI<'a, F> {
170    pub base: &'a Address<F>,
171    pub exp_ptr: *const Address<F>,
172    pub exp_len: usize,
173    pub result: &'a Address<F>,
174
175    pub mult: &'a F,
176}
177
178impl<'a, F> From<&'a ExpReverseBitsInstr<F>> for ExpReverseBitsInstrFFI<'a, F> {
179    fn from(instr: &'a ExpReverseBitsInstr<F>) -> Self {
180        Self {
181            base: &instr.addrs.base,
182            exp_ptr: instr.addrs.exp.as_ptr(),
183            exp_len: instr.addrs.exp.len(),
184            result: &instr.addrs.result,
185
186            mult: &instr.mult,
187        }
188    }
189}
190
191/// The event encoding the inputs and outputs of an exp-reverse-bits operation. The `len` operand is
192/// now stored as the length of the `exp` field.
193#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
194pub struct ExpReverseBitsEvent<F> {
195    pub base: F,
196    pub exp: Vec<F>,
197    pub result: F,
198}
199
200#[derive(Clone, Debug, PartialEq, Eq)]
201#[repr(C)]
202pub struct ExpReverseBitsEventFFI<'a, F> {
203    pub base: &'a F,
204    pub exp_ptr: *const F,
205    pub exp_len: usize,
206    pub result: &'a F,
207}
208
209impl<'a, F> From<&'a ExpReverseBitsEvent<F>> for ExpReverseBitsEventFFI<'a, F> {
210    fn from(event: &'a ExpReverseBitsEvent<F>) -> Self {
211        Self {
212            base: &event.base,
213            exp_ptr: event.exp.as_ptr(),
214            exp_len: event.exp.len(),
215            result: &event.result,
216        }
217    }
218}
219
220#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
221pub struct FriFoldIo<V> {
222    pub ext_single: FriFoldExtSingleIo<Block<V>>,
223    pub ext_vec: FriFoldExtVecIo<Vec<Block<V>>>,
224    pub base_single: FriFoldBaseIo<V>,
225}
226
227/// The extension-field-valued single inputs to the FRI fold operation.
228#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
229#[repr(C)]
230pub struct FriFoldExtSingleIo<V> {
231    pub z: V,
232    pub alpha: V,
233}
234
235/// The extension-field-valued vector inputs to the FRI fold operation.
236#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
237#[repr(C)]
238pub struct FriFoldExtVecIo<V> {
239    pub mat_opening: V,
240    pub ps_at_z: V,
241    pub alpha_pow_input: V,
242    pub ro_input: V,
243    pub alpha_pow_output: V,
244    pub ro_output: V,
245}
246
247/// The base-field-valued inputs to the FRI fold operation.
248#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
249#[repr(C)]
250pub struct FriFoldBaseIo<V> {
251    pub x: V,
252}
253
254/// An instruction invoking the FRI fold operation. Addresses for extension field elements are of
255/// the same type as for base field elements.
256#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
257pub struct FriFoldInstr<F> {
258    pub base_single_addrs: FriFoldBaseIo<Address<F>>,
259    pub ext_single_addrs: FriFoldExtSingleIo<Address<F>>,
260    pub ext_vec_addrs: FriFoldExtVecIo<Vec<Address<F>>>,
261    pub alpha_pow_mults: Vec<F>,
262    pub ro_mults: Vec<F>,
263}
264
265#[derive(Clone, Debug, PartialEq, Eq)]
266#[repr(C)]
267pub struct FriFoldInstrFFI<'a, F> {
268    pub base_single_addrs: &'a FriFoldBaseIo<Address<F>>,
269    pub ext_single_addrs: &'a FriFoldExtSingleIo<Address<F>>,
270
271    pub ext_vec_addrs_mat_opening_ptr: *const Address<F>,
272    pub ext_vec_addrs_mat_opening_len: usize,
273    pub ext_vec_addrs_ps_at_z_ptr: *const Address<F>,
274    pub ext_vec_addrs_ps_at_z_len: usize,
275    pub ext_vec_addrs_alpha_pow_input_ptr: *const Address<F>,
276    pub ext_vec_addrs_alpha_pow_input_len: usize,
277    pub ext_vec_addrs_ro_input_ptr: *const Address<F>,
278    pub ext_vec_addrs_ro_input_len: usize,
279    pub ext_vec_addrs_alpha_pow_output_ptr: *const Address<F>,
280    pub ext_vec_addrs_alpha_pow_output_len: usize,
281    pub ext_vec_addrs_ro_output_ptr: *const Address<F>,
282    pub ext_vec_addrs_ro_output_len: usize,
283
284    pub alpha_pow_mults_ptr: *const F,
285    pub alpha_pow_mults_len: usize,
286
287    pub ro_mults_ptr: *const F,
288    pub ro_mults_len: usize,
289}
290
291impl<'a, F> From<&'a FriFoldInstr<F>> for FriFoldInstrFFI<'a, F> {
292    fn from(instr: &'a FriFoldInstr<F>) -> Self {
293        Self {
294            base_single_addrs: &instr.base_single_addrs,
295            ext_single_addrs: &instr.ext_single_addrs,
296
297            ext_vec_addrs_mat_opening_ptr: instr.ext_vec_addrs.mat_opening.as_ptr(),
298            ext_vec_addrs_mat_opening_len: instr.ext_vec_addrs.mat_opening.len(),
299            ext_vec_addrs_ps_at_z_ptr: instr.ext_vec_addrs.ps_at_z.as_ptr(),
300            ext_vec_addrs_ps_at_z_len: instr.ext_vec_addrs.ps_at_z.len(),
301            ext_vec_addrs_alpha_pow_input_ptr: instr.ext_vec_addrs.alpha_pow_input.as_ptr(),
302            ext_vec_addrs_alpha_pow_input_len: instr.ext_vec_addrs.alpha_pow_input.len(),
303            ext_vec_addrs_ro_input_ptr: instr.ext_vec_addrs.ro_input.as_ptr(),
304            ext_vec_addrs_ro_input_len: instr.ext_vec_addrs.ro_input.len(),
305            ext_vec_addrs_alpha_pow_output_ptr: instr.ext_vec_addrs.alpha_pow_output.as_ptr(),
306            ext_vec_addrs_alpha_pow_output_len: instr.ext_vec_addrs.alpha_pow_output.len(),
307            ext_vec_addrs_ro_output_ptr: instr.ext_vec_addrs.ro_output.as_ptr(),
308            ext_vec_addrs_ro_output_len: instr.ext_vec_addrs.ro_output.len(),
309
310            alpha_pow_mults_ptr: instr.alpha_pow_mults.as_ptr(),
311            alpha_pow_mults_len: instr.alpha_pow_mults.len(),
312
313            ro_mults_ptr: instr.ro_mults.as_ptr(),
314            ro_mults_len: instr.ro_mults.len(),
315        }
316    }
317}
318
319impl<'a, F> From<&'a Box<FriFoldInstr<F>>> for FriFoldInstrFFI<'a, F> {
320    fn from(instr: &'a Box<FriFoldInstr<F>>) -> Self {
321        Self::from(instr.as_ref())
322    }
323}
324
325/// The event encoding the data of a single iteration within the FRI fold operation.
326/// For any given event, we are accessing a single element of the `Vec` inputs, so that the event
327/// is not a type alias for `FriFoldIo` like many of the other events.
328#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
329#[repr(C)]
330pub struct FriFoldEvent<F> {
331    pub base_single: FriFoldBaseIo<F>,
332    pub ext_single: FriFoldExtSingleIo<Block<F>>,
333    pub ext_vec: FriFoldExtVecIo<Block<F>>,
334}
335
336#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
337pub struct BatchFRIIo<V> {
338    pub ext_single: BatchFRIExtSingleIo<Block<V>>,
339    pub ext_vec: BatchFRIExtVecIo<Vec<Block<V>>>,
340    pub base_vec: BatchFRIBaseVecIo<V>,
341}
342
343/// The extension-field-valued single inputs to the batch FRI operation.
344#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
345#[repr(C)]
346pub struct BatchFRIExtSingleIo<V> {
347    pub acc: V,
348}
349
350/// The extension-field-valued vector inputs to the batch FRI operation.
351#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
352#[repr(C)]
353pub struct BatchFRIExtVecIo<V> {
354    pub p_at_z: V,
355    pub alpha_pow: V,
356}
357
358/// The base-field-valued vector inputs to the batch FRI operation.
359#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
360#[repr(C)]
361pub struct BatchFRIBaseVecIo<V> {
362    pub p_at_x: V,
363}
364
365/// An instruction invoking the batch FRI operation. Addresses for extension field elements are of
366/// the same type as for base field elements.
367#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
368pub struct BatchFRIInstr<F> {
369    pub base_vec_addrs: BatchFRIBaseVecIo<Vec<Address<F>>>,
370    pub ext_single_addrs: BatchFRIExtSingleIo<Address<F>>,
371    pub ext_vec_addrs: BatchFRIExtVecIo<Vec<Address<F>>>,
372    pub acc_mult: F,
373}
374
375#[derive(Clone, Debug, PartialEq, Eq)]
376#[repr(C)]
377pub struct BatchFRIInstrFFI<'a, F> {
378    pub base_vec_addrs_p_at_x_ptr: *const Address<F>,
379    pub base_vec_addrs_p_at_x_len: usize,
380
381    pub ext_single_addrs: &'a BatchFRIExtSingleIo<Address<F>>,
382
383    pub ext_vec_addrs_p_at_z_ptr: *const Address<F>,
384    pub ext_vec_addrs_p_at_z_len: usize,
385    pub ext_vec_addrs_alpha_pow_ptr: *const Address<F>,
386    pub ext_vec_addrs_alpha_pow_len: usize,
387
388    pub acc_mult: &'a F,
389}
390
391impl<'a, F> From<&'a BatchFRIInstr<F>> for BatchFRIInstrFFI<'a, F> {
392    fn from(instr: &'a BatchFRIInstr<F>) -> Self {
393        Self {
394            base_vec_addrs_p_at_x_ptr: instr.base_vec_addrs.p_at_x.as_ptr(),
395            base_vec_addrs_p_at_x_len: instr.base_vec_addrs.p_at_x.len(),
396
397            ext_single_addrs: &instr.ext_single_addrs,
398
399            ext_vec_addrs_p_at_z_ptr: instr.ext_vec_addrs.p_at_z.as_ptr(),
400            ext_vec_addrs_p_at_z_len: instr.ext_vec_addrs.p_at_z.len(),
401            ext_vec_addrs_alpha_pow_ptr: instr.ext_vec_addrs.alpha_pow.as_ptr(),
402            ext_vec_addrs_alpha_pow_len: instr.ext_vec_addrs.alpha_pow.len(),
403
404            acc_mult: &instr.acc_mult,
405        }
406    }
407}
408
409impl<'a, 'b: 'a, F> From<&'b &'b Box<BatchFRIInstr<F>>> for BatchFRIInstrFFI<'a, F> {
410    fn from(instr: &'b &'b Box<BatchFRIInstr<F>>) -> Self {
411        Self::from(instr.as_ref())
412    }
413}
414
415/// The event encoding the data of a single iteration within the batch FRI operation.
416/// For any given event, we are accessing a single element of the `Vec` inputs, so that the event
417/// is not a type alias for `BatchFRIIo` like many of the other events.
418#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
419#[repr(C)]
420pub struct BatchFRIEvent<F> {
421    pub base_vec: BatchFRIBaseVecIo<F>,
422    pub ext_single: BatchFRIExtSingleIo<Block<F>>,
423    pub ext_vec: BatchFRIExtVecIo<Block<F>>,
424}
425
426/// An instruction that will save the public values to the execution record and will commit to
427/// it's digest.
428#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
429#[repr(C)]
430pub struct CommitPublicValuesInstr<F> {
431    pub pv_addrs: RecursionPublicValues<Address<F>>,
432}
433
434/// The event for committing to the public values.
435#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
436#[repr(C)]
437pub struct CommitPublicValuesEvent<F> {
438    pub public_values: RecursionPublicValues<F>,
439}
sp1_recursion_core/lib.rs

sp1_recursion_core/
lib.rs
