openvm_instructions/
program.rs

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

openvm_instructions/
program.rs
