sp1_recursion_core/runtime/
instruction.rs

1use crate::*;
2#[cfg(feature = "debug")]
3use backtrace::Backtrace;
4use p3_field::{AbstractExtensionField, AbstractField};
5use serde::{Deserialize, Serialize};
6
7#[cfg(any(test, feature = "program_validation"))]
8use smallvec::SmallVec;
9
10use std::borrow::Borrow;
11
12#[derive(Debug, Clone, Serialize, Deserialize)]
13pub enum Instruction<F> {
14    BaseAlu(BaseAluInstr<F>),
15    ExtAlu(ExtAluInstr<F>),
16    Mem(MemInstr<F>),
17    Poseidon2(Box<Poseidon2Instr<F>>),
18    Select(SelectInstr<F>),
19    ExpReverseBitsLen(ExpReverseBitsInstr<F>),
20    HintBits(HintBitsInstr<F>),
21    HintAddCurve(Box<HintAddCurveInstr<F>>),
22    FriFold(Box<FriFoldInstr<F>>),
23    BatchFRI(Box<BatchFRIInstr<F>>),
24    Print(PrintInstr<F>),
25    HintExt2Felts(HintExt2FeltsInstr<F>),
26    CommitPublicValues(Box<CommitPublicValuesInstr<F>>),
27    Hint(HintInstr<F>),
28    #[cfg(feature = "debug")]
29    DebugBacktrace(Backtrace),
30}
31
32impl<F: Copy> Instruction<F> {
33    #[cfg(any(test, feature = "program_validation"))]
34    #[allow(clippy::type_complexity)]
35    #[must_use]
36    pub(crate) fn io_addrs(&self) -> (SmallVec<[Address<F>; 4]>, SmallVec<[Address<F>; 4]>) {
37        use smallvec::{smallvec as svec, *};
38        use std::iter;
39
40        match *self {
41            Instruction::BaseAlu(BaseAluInstr { addrs: BaseAluIo { out, in1, in2 }, .. }) => {
42                (svec![in1, in2], svec![out])
43            }
44            Instruction::ExtAlu(ExtAluInstr { addrs: ExtAluIo { out, in1, in2 }, .. }) => {
45                (svec![in1, in2], svec![out])
46            }
47            Instruction::Mem(MemInstr { addrs: MemIo { inner }, .. }) => (svec![], svec![inner]),
48            Instruction::Poseidon2(ref instr) => {
49                let Poseidon2SkinnyInstr { addrs: Poseidon2Io { input, output }, .. } =
50                    instr.as_ref();
51                (SmallVec::from_slice(input), SmallVec::from_slice(output))
52            }
53            Instruction::Select(SelectInstr {
54                addrs: SelectIo { bit, out1, out2, in1, in2 },
55                ..
56            }) => (svec![bit, in1, in2], svec![out1, out2]),
57            Instruction::ExpReverseBitsLen(ExpReverseBitsInstr {
58                addrs: ExpReverseBitsIo { base, ref exp, result },
59                ..
60            }) => (exp.iter().copied().chain(iter::once(base)).collect(), svec![result]),
61            Instruction::HintBits(HintBitsInstr { ref output_addrs_mults, input_addr }) => {
62                (svec![input_addr], output_addrs_mults.iter().map(|(a, _)| *a).collect())
63            }
64            Instruction::HintAddCurve(ref instr) => {
65                let HintAddCurveInstr {
66                    output_x_addrs_mults,
67                    output_y_addrs_mults,
68                    input1_x_addrs,
69                    input1_y_addrs,
70                    input2_x_addrs,
71                    input2_y_addrs,
72                } = instr.as_ref();
73                (
74                    [input1_x_addrs, input1_y_addrs, input2_x_addrs, input2_y_addrs]
75                        .into_iter()
76                        .flatten()
77                        .copied()
78                        .collect(),
79                    [output_x_addrs_mults, output_y_addrs_mults]
80                        .into_iter()
81                        .flatten()
82                        .map(|&(addr, _)| addr)
83                        .collect(),
84                )
85            }
86            Instruction::FriFold(ref instr) => {
87                let FriFoldInstr {
88                    base_single_addrs: FriFoldBaseIo { x },
89                    ext_single_addrs: FriFoldExtSingleIo { z, alpha },
90                    ext_vec_addrs:
91                        FriFoldExtVecIo {
92                            ref mat_opening,
93                            ref ps_at_z,
94                            ref alpha_pow_input,
95                            ref ro_input,
96                            ref alpha_pow_output,
97                            ref ro_output,
98                        },
99                    ..
100                } = *instr.as_ref();
101                (
102                    [mat_opening, ps_at_z, alpha_pow_input, ro_input]
103                        .into_iter()
104                        .flatten()
105                        .copied()
106                        .chain([x, z, alpha])
107                        .collect(),
108                    [alpha_pow_output, ro_output].into_iter().flatten().copied().collect(),
109                )
110            }
111            Instruction::BatchFRI(ref instr) => {
112                let BatchFRIInstr { base_vec_addrs, ext_single_addrs, ext_vec_addrs, .. } =
113                    instr.as_ref();
114                (
115                    [
116                        base_vec_addrs.p_at_x.as_slice(),
117                        ext_vec_addrs.p_at_z.as_slice(),
118                        ext_vec_addrs.alpha_pow.as_slice(),
119                    ]
120                    .concat()
121                    .to_vec()
122                    .into(),
123                    svec![ext_single_addrs.acc],
124                )
125            }
126            Instruction::Print(_) => Default::default(),
127            #[cfg(feature = "debug")]
128            Instruction::DebugBacktrace(_) => Default::default(),
129            Instruction::HintExt2Felts(HintExt2FeltsInstr { output_addrs_mults, input_addr }) => {
130                (svec![input_addr], output_addrs_mults.iter().map(|(a, _)| *a).collect())
131            }
132            Instruction::CommitPublicValues(ref instr) => {
133                let CommitPublicValuesInstr { pv_addrs } = instr.as_ref();
134                (pv_addrs.as_array().to_vec().into(), svec![])
135            }
136            Instruction::Hint(HintInstr { ref output_addrs_mults }) => {
137                (svec![], output_addrs_mults.iter().map(|(a, _)| *a).collect())
138            }
139        }
140    }
141}
142
143#[derive(Clone, Debug, Serialize, Deserialize)]
144pub struct HintBitsInstr<F> {
145    /// Addresses and mults of the output bits.
146    pub output_addrs_mults: Vec<(Address<F>, F)>,
147    /// Input value to decompose.
148    pub input_addr: Address<F>,
149}
150
151#[derive(Clone, Debug, Serialize, Deserialize)]
152pub struct PrintInstr<F> {
153    pub field_elt_type: FieldEltType,
154    pub addr: Address<F>,
155}
156
157#[derive(Clone, Debug, Serialize, Deserialize)]
158pub struct HintAddCurveInstr<F> {
159    pub output_x_addrs_mults: Vec<(Address<F>, F)>,
160    pub output_y_addrs_mults: Vec<(Address<F>, F)>,
161    pub input1_x_addrs: Vec<Address<F>>,
162    pub input1_y_addrs: Vec<Address<F>>,
163    pub input2_x_addrs: Vec<Address<F>>,
164    pub input2_y_addrs: Vec<Address<F>>,
165}
166#[derive(Clone, Debug, Serialize, Deserialize)]
167pub struct HintInstr<F> {
168    /// Addresses and mults of the output felts.
169    pub output_addrs_mults: Vec<(Address<F>, F)>,
170}
171
172#[derive(Clone, Debug, Serialize, Deserialize)]
173pub struct HintExt2FeltsInstr<F> {
174    /// Addresses and mults of the output bits.
175    pub output_addrs_mults: [(Address<F>, F); D],
176    /// Input value to decompose.
177    pub input_addr: Address<F>,
178}
179
180#[derive(Clone, Debug, Serialize, Deserialize)]
181pub enum FieldEltType {
182    Base,
183    Extension,
184}
185
186pub fn base_alu<F: AbstractField>(
187    opcode: BaseAluOpcode,
188    mult: u32,
189    out: u32,
190    in1: u32,
191    in2: u32,
192) -> Instruction<F> {
193    Instruction::BaseAlu(BaseAluInstr {
194        opcode,
195        mult: F::from_canonical_u32(mult),
196        addrs: BaseAluIo {
197            out: Address(F::from_canonical_u32(out)),
198            in1: Address(F::from_canonical_u32(in1)),
199            in2: Address(F::from_canonical_u32(in2)),
200        },
201    })
202}
203
204pub fn ext_alu<F: AbstractField>(
205    opcode: ExtAluOpcode,
206    mult: u32,
207    out: u32,
208    in1: u32,
209    in2: u32,
210) -> Instruction<F> {
211    Instruction::ExtAlu(ExtAluInstr {
212        opcode,
213        mult: F::from_canonical_u32(mult),
214        addrs: ExtAluIo {
215            out: Address(F::from_canonical_u32(out)),
216            in1: Address(F::from_canonical_u32(in1)),
217            in2: Address(F::from_canonical_u32(in2)),
218        },
219    })
220}
221
222pub fn mem<F: AbstractField>(
223    kind: MemAccessKind,
224    mult: u32,
225    addr: u32,
226    val: u32,
227) -> Instruction<F> {
228    mem_single(kind, mult, addr, F::from_canonical_u32(val))
229}
230
231pub fn mem_single<F: AbstractField>(
232    kind: MemAccessKind,
233    mult: u32,
234    addr: u32,
235    val: F,
236) -> Instruction<F> {
237    mem_block(kind, mult, addr, Block::from(val))
238}
239
240pub fn mem_ext<F: AbstractField + Copy, EF: AbstractExtensionField<F>>(
241    kind: MemAccessKind,
242    mult: u32,
243    addr: u32,
244    val: EF,
245) -> Instruction<F> {
246    mem_block(kind, mult, addr, val.as_base_slice().into())
247}
248
249pub fn mem_block<F: AbstractField>(
250    kind: MemAccessKind,
251    mult: u32,
252    addr: u32,
253    val: Block<F>,
254) -> Instruction<F> {
255    Instruction::Mem(MemInstr {
256        addrs: MemIo { inner: Address(F::from_canonical_u32(addr)) },
257        vals: MemIo { inner: val },
258        mult: F::from_canonical_u32(mult),
259        kind,
260    })
261}
262
263pub fn poseidon2<F: AbstractField>(
264    mults: [u32; WIDTH],
265    output: [u32; WIDTH],
266    input: [u32; WIDTH],
267) -> Instruction<F> {
268    Instruction::Poseidon2(Box::new(Poseidon2Instr {
269        mults: mults.map(F::from_canonical_u32),
270        addrs: Poseidon2Io {
271            output: output.map(F::from_canonical_u32).map(Address),
272            input: input.map(F::from_canonical_u32).map(Address),
273        },
274    }))
275}
276
277#[allow(clippy::too_many_arguments)]
278pub fn select<F: AbstractField>(
279    mult1: u32,
280    mult2: u32,
281    bit: u32,
282    out1: u32,
283    out2: u32,
284    in1: u32,
285    in2: u32,
286) -> Instruction<F> {
287    Instruction::Select(SelectInstr {
288        mult1: F::from_canonical_u32(mult1),
289        mult2: F::from_canonical_u32(mult2),
290        addrs: SelectIo {
291            bit: Address(F::from_canonical_u32(bit)),
292            out1: Address(F::from_canonical_u32(out1)),
293            out2: Address(F::from_canonical_u32(out2)),
294            in1: Address(F::from_canonical_u32(in1)),
295            in2: Address(F::from_canonical_u32(in2)),
296        },
297    })
298}
299
300pub fn exp_reverse_bits_len<F: AbstractField>(
301    mult: u32,
302    base: F,
303    exp: Vec<F>,
304    result: F,
305) -> Instruction<F> {
306    Instruction::ExpReverseBitsLen(ExpReverseBitsInstr {
307        mult: F::from_canonical_u32(mult),
308        addrs: ExpReverseBitsIo {
309            base: Address(base),
310            exp: exp.into_iter().map(Address).collect(),
311            result: Address(result),
312        },
313    })
314}
315
316#[allow(clippy::too_many_arguments)]
317pub fn fri_fold<F: AbstractField>(
318    z: u32,
319    alpha: u32,
320    x: u32,
321    mat_opening: Vec<u32>,
322    ps_at_z: Vec<u32>,
323    alpha_pow_input: Vec<u32>,
324    ro_input: Vec<u32>,
325    alpha_pow_output: Vec<u32>,
326    ro_output: Vec<u32>,
327    alpha_mults: Vec<u32>,
328    ro_mults: Vec<u32>,
329) -> Instruction<F> {
330    Instruction::FriFold(Box::new(FriFoldInstr {
331        base_single_addrs: FriFoldBaseIo { x: Address(F::from_canonical_u32(x)) },
332        ext_single_addrs: FriFoldExtSingleIo {
333            z: Address(F::from_canonical_u32(z)),
334            alpha: Address(F::from_canonical_u32(alpha)),
335        },
336        ext_vec_addrs: FriFoldExtVecIo {
337            mat_opening: mat_opening
338                .iter()
339                .map(|elm| Address(F::from_canonical_u32(*elm)))
340                .collect(),
341            ps_at_z: ps_at_z.iter().map(|elm| Address(F::from_canonical_u32(*elm))).collect(),
342            alpha_pow_input: alpha_pow_input
343                .iter()
344                .map(|elm| Address(F::from_canonical_u32(*elm)))
345                .collect(),
346            ro_input: ro_input.iter().map(|elm| Address(F::from_canonical_u32(*elm))).collect(),
347            alpha_pow_output: alpha_pow_output
348                .iter()
349                .map(|elm| Address(F::from_canonical_u32(*elm)))
350                .collect(),
351            ro_output: ro_output.iter().map(|elm| Address(F::from_canonical_u32(*elm))).collect(),
352        },
353        alpha_pow_mults: alpha_mults.iter().map(|mult| F::from_canonical_u32(*mult)).collect(),
354        ro_mults: ro_mults.iter().map(|mult| F::from_canonical_u32(*mult)).collect(),
355    }))
356}
357
358#[allow(clippy::too_many_arguments)]
359pub fn batch_fri<F: AbstractField>(
360    acc: u32,
361    alpha_pows: Vec<u32>,
362    p_at_zs: Vec<u32>,
363    p_at_xs: Vec<u32>,
364    acc_mult: u32,
365) -> Instruction<F> {
366    Instruction::BatchFRI(Box::new(BatchFRIInstr {
367        base_vec_addrs: BatchFRIBaseVecIo {
368            p_at_x: p_at_xs.iter().map(|elm| Address(F::from_canonical_u32(*elm))).collect(),
369        },
370        ext_single_addrs: BatchFRIExtSingleIo { acc: Address(F::from_canonical_u32(acc)) },
371        ext_vec_addrs: BatchFRIExtVecIo {
372            p_at_z: p_at_zs.iter().map(|elm| Address(F::from_canonical_u32(*elm))).collect(),
373            alpha_pow: alpha_pows.iter().map(|elm| Address(F::from_canonical_u32(*elm))).collect(),
374        },
375        acc_mult: F::from_canonical_u32(acc_mult),
376    }))
377}
378
379pub fn commit_public_values<F: AbstractField>(
380    public_values_a: &RecursionPublicValues<u32>,
381) -> Instruction<F> {
382    let pv_a = public_values_a.as_array().map(|pv| Address(F::from_canonical_u32(pv)));
383    let pv_address: &RecursionPublicValues<Address<F>> = pv_a.as_slice().borrow();
384
385    Instruction::CommitPublicValues(Box::new(CommitPublicValuesInstr {
386        pv_addrs: pv_address.clone(),
387    }))
388}
sp1_recursion_core/runtime/instruction.rs

sp1_recursion_core/runtime/
instruction.rs
