sp1_recursion_executor/
instruction.rs

1use std::borrow::Borrow;
2
3use crate::{block::Block, *};
4use backtrace::Backtrace;
5use serde::{Deserialize, Serialize};
6use slop_algebra::{AbstractExtensionField, AbstractField};
7
8#[cfg(any(test, feature = "program_validation"))]
9use smallvec::SmallVec;
10
11#[derive(Debug, Clone, Serialize, Deserialize)]
12pub enum Instruction<F> {
13    BaseAlu(BaseAluInstr<F>),
14    ExtAlu(ExtAluInstr<F>),
15    Mem(MemInstr<F>),
16    Poseidon2(Box<Poseidon2Instr<F>>),
17    Poseidon2LinearLayer(Box<Poseidon2LinearLayerInstr<F>>),
18    Poseidon2SBox(Poseidon2SBoxInstr<F>),
19    ExtFelt(ExtFeltInstr<F>),
20    Select(SelectInstr<F>),
21    HintBits(HintBitsInstr<F>),
22    HintAddCurve(Box<HintAddCurveInstr<F>>),
23    PrefixSumChecks(Box<PrefixSumChecksInstr<F>>),
24    Print(PrintInstr<F>),
25    HintExt2Felts(HintExt2FeltsInstr<F>),
26    CommitPublicValues(Box<CommitPublicValuesInstr<F>>),
27    Hint(HintInstr<F>),
28    DebugBacktrace(Backtrace),
29}
30
31impl<F: Copy> Instruction<F> {
32    #[cfg(any(test, feature = "program_validation"))]
33    #[allow(clippy::type_complexity)]
34    #[must_use]
35    pub(crate) fn io_addrs(&self) -> (SmallVec<[Address<F>; 4]>, SmallVec<[Address<F>; 4]>) {
36        use smallvec::{smallvec as svec, *};
37
38        match *self {
39            Instruction::BaseAlu(BaseAluInstr { addrs: BaseAluIo { out, in1, in2 }, .. }) => {
40                (svec![in1, in2], svec![out])
41            }
42            Instruction::ExtAlu(ExtAluInstr { addrs: ExtAluIo { out, in1, in2 }, .. }) => {
43                (svec![in1, in2], svec![out])
44            }
45            Instruction::Mem(MemInstr { addrs: MemIo { inner }, .. }) => (svec![], svec![inner]),
46            Instruction::ExtFelt(ExtFeltInstr { addrs, ext2felt, .. }) => {
47                if ext2felt {
48                    (svec![addrs[0]], svec![addrs[1], addrs[2], addrs[3], addrs[4]])
49                } else {
50                    (svec![addrs[1], addrs[2], addrs[3], addrs[4]], svec![addrs[0]])
51                }
52            }
53            Instruction::Poseidon2(ref instr) => {
54                let Poseidon2Instr { addrs: Poseidon2Io { input, output }, .. } = instr.as_ref();
55                (SmallVec::from_slice(input), SmallVec::from_slice(output))
56            }
57            Instruction::Poseidon2LinearLayer(ref instr) => {
58                let Poseidon2LinearLayerInstr {
59                    addrs: Poseidon2LinearLayerIo { input, output },
60                    ..
61                } = instr.as_ref();
62                (SmallVec::from_slice(input), SmallVec::from_slice(output))
63            }
64            Instruction::Poseidon2SBox(Poseidon2SBoxInstr {
65                addrs: Poseidon2SBoxIo { input, output },
66                ..
67            }) => (svec![input], svec![output]),
68            Instruction::Select(SelectInstr {
69                addrs: SelectIo { bit, out1, out2, in1, in2 },
70                ..
71            }) => (svec![bit, in1, in2], svec![out1, out2]),
72            Instruction::HintBits(HintBitsInstr { ref output_addrs_mults, input_addr }) => {
73                (svec![input_addr], output_addrs_mults.iter().map(|(a, _)| *a).collect())
74            }
75            Instruction::HintAddCurve(ref instr) => {
76                let HintAddCurveInstr {
77                    output_x_addrs_mults,
78                    output_y_addrs_mults,
79                    input1_x_addrs,
80                    input1_y_addrs,
81                    input2_x_addrs,
82                    input2_y_addrs,
83                } = instr.as_ref();
84                (
85                    [input1_x_addrs, input1_y_addrs, input2_x_addrs, input2_y_addrs]
86                        .into_iter()
87                        .flatten()
88                        .copied()
89                        .collect(),
90                    [output_x_addrs_mults, output_y_addrs_mults]
91                        .into_iter()
92                        .flatten()
93                        .map(|&(addr, _)| addr)
94                        .collect(),
95                )
96            }
97            Instruction::PrefixSumChecks(ref instr) => {
98                let PrefixSumChecksInstr {
99                    addrs: PrefixSumChecksIo { zero, one, x1, x2, accs, field_accs },
100                    ..
101                } = instr.as_ref();
102                (
103                    [x1.as_slice(), x2.as_slice(), &[*one], &[*zero]].concat().to_vec().into(),
104                    accs.iter().copied().chain(field_accs.iter().copied()).collect(),
105                )
106            }
107            Instruction::Print(_) | Instruction::DebugBacktrace(_) => Default::default(),
108            Instruction::HintExt2Felts(HintExt2FeltsInstr { output_addrs_mults, input_addr }) => {
109                (svec![input_addr], output_addrs_mults.iter().map(|(a, _)| *a).collect())
110            }
111            Instruction::CommitPublicValues(ref instr) => {
112                let CommitPublicValuesInstr { pv_addrs } = instr.as_ref();
113                (pv_addrs.as_array().to_vec().into(), svec![])
114            }
115            Instruction::Hint(HintInstr { ref output_addrs_mults }) => {
116                (svec![], output_addrs_mults.iter().map(|(a, _)| *a).collect())
117            }
118        }
119    }
120}
121
122#[derive(Clone, Debug, Serialize, Deserialize)]
123pub struct HintBitsInstr<F> {
124    /// Addresses and mults of the output bits.
125    pub output_addrs_mults: Vec<(Address<F>, F)>,
126    /// Input value to decompose.
127    pub input_addr: Address<F>,
128}
129
130#[derive(Clone, Debug, Serialize, Deserialize)]
131pub struct PrintInstr<F> {
132    pub field_elt_type: FieldEltType,
133    pub addr: Address<F>,
134}
135
136#[derive(Clone, Debug, Serialize, Deserialize)]
137pub struct HintAddCurveInstr<F> {
138    pub output_x_addrs_mults: Vec<(Address<F>, F)>,
139    pub output_y_addrs_mults: Vec<(Address<F>, F)>,
140    pub input1_x_addrs: Vec<Address<F>>,
141    pub input1_y_addrs: Vec<Address<F>>,
142    pub input2_x_addrs: Vec<Address<F>>,
143    pub input2_y_addrs: Vec<Address<F>>,
144}
145#[derive(Clone, Debug, Serialize, Deserialize)]
146pub struct HintInstr<F> {
147    /// Addresses and mults of the output felts.
148    pub output_addrs_mults: Vec<(Address<F>, F)>,
149}
150
151#[derive(Clone, Debug, Serialize, Deserialize)]
152pub struct HintExt2FeltsInstr<F> {
153    /// Addresses and mults of the output bits.
154    pub output_addrs_mults: [(Address<F>, F); D],
155    /// Input value to decompose.
156    pub input_addr: Address<F>,
157}
158
159#[derive(Clone, Debug, Serialize, Deserialize)]
160pub enum FieldEltType {
161    Base,
162    Extension,
163}
164
165pub fn base_alu<F: AbstractField>(
166    opcode: BaseAluOpcode,
167    mult: u32,
168    out: u32,
169    in1: u32,
170    in2: u32,
171) -> Instruction<F> {
172    Instruction::BaseAlu(BaseAluInstr {
173        opcode,
174        mult: F::from_canonical_u32(mult),
175        addrs: BaseAluIo {
176            out: Address(F::from_canonical_u32(out)),
177            in1: Address(F::from_canonical_u32(in1)),
178            in2: Address(F::from_canonical_u32(in2)),
179        },
180    })
181}
182
183pub fn ext_alu<F: AbstractField>(
184    opcode: ExtAluOpcode,
185    mult: u32,
186    out: u32,
187    in1: u32,
188    in2: u32,
189) -> Instruction<F> {
190    Instruction::ExtAlu(ExtAluInstr {
191        opcode,
192        mult: F::from_canonical_u32(mult),
193        addrs: ExtAluIo {
194            out: Address(F::from_canonical_u32(out)),
195            in1: Address(F::from_canonical_u32(in1)),
196            in2: Address(F::from_canonical_u32(in2)),
197        },
198    })
199}
200
201pub fn mem<F: AbstractField>(
202    kind: MemAccessKind,
203    mult: u32,
204    addr: u32,
205    val: u32,
206) -> Instruction<F> {
207    mem_single(kind, mult, addr, F::from_canonical_u32(val))
208}
209
210pub fn mem_single<F: AbstractField>(
211    kind: MemAccessKind,
212    mult: u32,
213    addr: u32,
214    val: F,
215) -> Instruction<F> {
216    mem_block(kind, mult, addr, Block::from(val))
217}
218
219pub fn mem_ext<F: AbstractField + Copy, EF: AbstractExtensionField<F>>(
220    kind: MemAccessKind,
221    mult: u32,
222    addr: u32,
223    val: EF,
224) -> Instruction<F> {
225    mem_block(kind, mult, addr, val.as_base_slice().into())
226}
227
228pub fn mem_block<F: AbstractField>(
229    kind: MemAccessKind,
230    mult: u32,
231    addr: u32,
232    val: Block<F>,
233) -> Instruction<F> {
234    Instruction::Mem(MemInstr {
235        addrs: MemIo { inner: Address(F::from_canonical_u32(addr)) },
236        vals: MemIo { inner: val },
237        mult: F::from_canonical_u32(mult),
238        kind,
239    })
240}
241
242pub fn poseidon2<F: AbstractField>(
243    mults: [u32; PERMUTATION_WIDTH],
244    output: [u32; PERMUTATION_WIDTH],
245    input: [u32; PERMUTATION_WIDTH],
246) -> Instruction<F> {
247    Instruction::Poseidon2(Box::new(Poseidon2Instr {
248        mults: mults.map(F::from_canonical_u32),
249        addrs: Poseidon2Io {
250            output: output.map(F::from_canonical_u32).map(Address),
251            input: input.map(F::from_canonical_u32).map(Address),
252        },
253    }))
254}
255
256#[allow(clippy::too_many_arguments)]
257pub fn select<F: AbstractField>(
258    mult1: u32,
259    mult2: u32,
260    bit: u32,
261    out1: u32,
262    out2: u32,
263    in1: u32,
264    in2: u32,
265) -> Instruction<F> {
266    Instruction::Select(SelectInstr {
267        mult1: F::from_canonical_u32(mult1),
268        mult2: F::from_canonical_u32(mult2),
269        addrs: SelectIo {
270            bit: Address(F::from_canonical_u32(bit)),
271            out1: Address(F::from_canonical_u32(out1)),
272            out2: Address(F::from_canonical_u32(out2)),
273            in1: Address(F::from_canonical_u32(in1)),
274            in2: Address(F::from_canonical_u32(in2)),
275        },
276    })
277}
278
279#[allow(clippy::too_many_arguments)]
280pub fn prefix_sum_checks<F: AbstractField>(
281    mults: Vec<u32>,
282    field_mults: Vec<u32>,
283    x1: Vec<F>,
284    x2: Vec<F>,
285    zero: F,
286    one: F,
287    accs: Vec<F>,
288    field_accs: Vec<F>,
289) -> Instruction<F> {
290    Instruction::PrefixSumChecks(Box::new(PrefixSumChecksInstr {
291        acc_mults: mults.iter().map(|mult| F::from_canonical_u32(*mult)).collect(),
292        field_acc_mults: field_mults.iter().map(|mult| F::from_canonical_u32(*mult)).collect(),
293        addrs: PrefixSumChecksIo {
294            zero: Address(zero),
295            one: Address(one),
296            x1: x1.into_iter().map(Address).collect(),
297            x2: x2.into_iter().map(Address).collect(),
298            accs: accs.into_iter().map(Address).collect(),
299            field_accs: field_accs.into_iter().map(Address).collect(),
300        },
301    }))
302}
303
304pub fn commit_public_values<F: AbstractField>(
305    public_values_a: &RecursionPublicValues<u32>,
306) -> Instruction<F> {
307    let pv_a = public_values_a.as_array().map(|pv| Address(F::from_canonical_u32(pv)));
308    let pv_address: &RecursionPublicValues<Address<F>> = pv_a.as_slice().borrow();
309
310    Instruction::CommitPublicValues(Box::new(CommitPublicValuesInstr {
311        pv_addrs: pv_address.clone(),
312    }))
313}
sp1_recursion_executor/instruction.rs

sp1_recursion_executor/
instruction.rs
