openvm_instructions/
program.rs

Help
1use std::{fmt, fmt::Display};
2
3use itertools::Itertools;
4use openvm_stark_backend::p3_field::Field;
5use serde::{Deserialize, Serialize};
6
7use crate::instruction::{DebugInfo, Instruction};
8
9pub const PC_BITS: usize = 30;
10/// We use default PC step of 4 whenever possible for consistency with RISC-V, where 4 comes
11/// from the fact that each standard RISC-V instruction is 32-bits = 4 bytes.
12pub const DEFAULT_PC_STEP: u32 = 4;
13pub const DEFAULT_MAX_NUM_PUBLIC_VALUES: usize = 32;
14pub const MAX_ALLOWED_PC: u32 = (1 << PC_BITS) - 1;
15
16#[derive(Clone, Debug, Default, Serialize, Deserialize)]
17pub struct Program<F> {
18    /// A map from program counter to instruction.
19    /// Sometimes the instructions are enumerated as 0, 4, 8, etc.
20    /// Maybe at some point we will replace this with a struct that would have a `Vec` under the hood and divide the incoming `pc` by whatever given.
21    pub instructions_and_debug_infos: Vec<Option<(Instruction<F>, Option<DebugInfo>)>>,
22    pub step: u32,
23    pub pc_base: u32,
24    /// The upper bound of the number of public values the program would publish.
25    /// Currently, this won't result any constraint. But users should always be aware of the limit
26    /// of public values when they write programs.
27    pub max_num_public_values: usize,
28}
29
30impl<F: Field> Program<F> {
31    pub fn new_empty(step: u32, pc_base: u32, max_num_public_values: usize) -> Self {
32        Self {
33            instructions_and_debug_infos: vec![],
34            step,
35            pc_base,
36            max_num_public_values,
37        }
38    }
39
40    pub fn new_without_debug_infos(
41        instructions: &[Instruction<F>],
42        step: u32,
43        pc_base: u32,
44        max_num_public_values: usize,
45    ) -> Self {
46        Self {
47            instructions_and_debug_infos: instructions
48                .iter()
49                .map(|instruction| Some((instruction.clone(), None)))
50                .collect(),
51            step,
52            pc_base,
53            max_num_public_values,
54        }
55    }
56
57    pub fn new_without_debug_infos_with_option(
58        instructions: &[Option<Instruction<F>>],
59        step: u32,
60        pc_base: u32,
61        max_num_public_values: usize,
62    ) -> Self {
63        Self {
64            instructions_and_debug_infos: instructions
65                .iter()
66                .map(|instruction| instruction.clone().map(|instruction| (instruction, None)))
67                .collect(),
68            step,
69            pc_base,
70            max_num_public_values,
71        }
72    }
73
74    /// We assume that pc_start = pc_base = 0 everywhere except the RISC-V programs, until we need otherwise
75    /// We use [DEFAULT_PC_STEP] for consistency with RISC-V
76    pub fn from_instructions_and_debug_infos(
77        instructions: &[Instruction<F>],
78        debug_infos: &[Option<DebugInfo>],
79    ) -> Self {
80        Self {
81            instructions_and_debug_infos: instructions
82                .iter()
83                .zip_eq(debug_infos.iter())
84                .map(|(instruction, debug_info)| Some((instruction.clone(), debug_info.clone())))
85                .collect(),
86            step: DEFAULT_PC_STEP,
87            pc_base: 0,
88            max_num_public_values: DEFAULT_MAX_NUM_PUBLIC_VALUES,
89        }
90    }
91
92    pub fn strip_debug_infos(self) -> Self {
93        Self {
94            instructions_and_debug_infos: self
95                .instructions_and_debug_infos
96                .into_iter()
97                .map(|opt| opt.map(|(ins, _)| (ins, None)))
98                .collect(),
99            ..self
100        }
101    }
102
103    pub fn from_instructions(instructions: &[Instruction<F>]) -> Self {
104        Self::new_without_debug_infos(
105            instructions,
106            DEFAULT_PC_STEP,
107            0,
108            DEFAULT_MAX_NUM_PUBLIC_VALUES,
109        )
110    }
111
112    pub fn len(&self) -> usize {
113        self.instructions_and_debug_infos.len()
114    }
115
116    pub fn is_empty(&self) -> bool {
117        self.instructions_and_debug_infos.is_empty()
118    }
119
120    pub fn defined_instructions(&self) -> Vec<Instruction<F>> {
121        self.instructions_and_debug_infos
122            .iter()
123            .flatten()
124            .map(|(instruction, _)| instruction.clone())
125            .collect()
126    }
127
128    // if this is being called a lot, we may want to optimize this later
129    pub fn num_defined_instructions(&self) -> usize {
130        self.defined_instructions().len()
131    }
132
133    pub fn debug_infos(&self) -> Vec<Option<DebugInfo>> {
134        self.instructions_and_debug_infos
135            .iter()
136            .flatten()
137            .map(|(_, debug_info)| debug_info.clone())
138            .collect()
139    }
140
141    pub fn enumerate_by_pc(&self) -> Vec<(u32, Instruction<F>, Option<DebugInfo>)> {
142        self.instructions_and_debug_infos
143            .iter()
144            .enumerate()
145            .flat_map(|(index, option)| {
146                option.clone().map(|(instruction, debug_info)| {
147                    (
148                        self.pc_base + (self.step * (index as u32)),
149                        instruction,
150                        debug_info,
151                    )
152                })
153            })
154            .collect()
155    }
156
157    // such that pc = pc_base + (step * index)
158    pub fn get_instruction_and_debug_info(
159        &self,
160        index: usize,
161    ) -> Option<&(Instruction<F>, Option<DebugInfo>)> {
162        self.instructions_and_debug_infos
163            .get(index)
164            .and_then(|x| x.as_ref())
165    }
166
167    pub fn push_instruction_and_debug_info(
168        &mut self,
169        instruction: Instruction<F>,
170        debug_info: Option<DebugInfo>,
171    ) {
172        self.instructions_and_debug_infos
173            .push(Some((instruction, debug_info)));
174    }
175
176    pub fn push_instruction(&mut self, instruction: Instruction<F>) {
177        self.push_instruction_and_debug_info(instruction, None);
178    }
179
180    pub fn append(&mut self, other: Program<F>) {
181        self.instructions_and_debug_infos
182            .extend(other.instructions_and_debug_infos);
183    }
184}
185impl<F: Field> Display for Program<F> {
186    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
187        for instruction in self.defined_instructions().iter() {
188            let Instruction {
189                opcode,
190                a,
191                b,
192                c,
193                d,
194                e,
195                f,
196                g,
197            } = instruction;
198            writeln!(
199                formatter,
200                "{:?} {} {} {} {} {} {} {}",
201                opcode, a, b, c, d, e, f, g,
202            )?;
203        }
204        Ok(())
205    }
206}
207
208pub fn display_program_with_pc<F: Field>(program: &Program<F>) {
209    for (pc, instruction) in program.defined_instructions().iter().enumerate() {
210        let Instruction {
211            opcode,
212            a,
213            b,
214            c,
215            d,
216            e,
217            f,
218            g,
219        } = instruction;
220        println!(
221            "{} | {:?} {} {} {} {} {} {} {}",
222            pc, opcode, a, b, c, d, e, f, g
223        );
224    }
225}
openvm_instructions/program.rs

openvm_instructions/
program.rs
