cairo_vm/vm/runners/builtin_runner/
mod.rs

1use crate::air_private_input::PrivateInput;
2use crate::math_utils::safe_div_usize;
3use crate::stdlib::prelude::*;
4use crate::types::builtin_name::BuiltinName;
5use crate::types::instance_definitions::bitwise_instance_def::{
6    CELLS_PER_BITWISE, INPUT_CELLS_PER_BITWISE,
7};
8use crate::types::instance_definitions::builtins_instance_def::BUILTIN_INSTANCES_PER_COMPONENT;
9use crate::types::instance_definitions::ec_op_instance_def::{
10    CELLS_PER_EC_OP, INPUT_CELLS_PER_EC_OP,
11};
12use crate::types::instance_definitions::ecdsa_instance_def::CELLS_PER_SIGNATURE;
13use crate::types::instance_definitions::keccak_instance_def::{
14    CELLS_PER_KECCAK, INPUT_CELLS_PER_KECCAK, KECCAK_INSTANCES_PER_COMPONENT,
15};
16use crate::types::instance_definitions::mod_instance_def::CELLS_PER_MOD;
17use crate::types::instance_definitions::pedersen_instance_def::{
18    CELLS_PER_HASH, INPUT_CELLS_PER_HASH,
19};
20use crate::types::instance_definitions::poseidon_instance_def::{
21    CELLS_PER_POSEIDON, INPUT_CELLS_PER_POSEIDON,
22};
23use crate::types::instance_definitions::range_check_instance_def::CELLS_PER_RANGE_CHECK;
24use crate::types::relocatable::{MaybeRelocatable, Relocatable};
25use crate::vm::errors::memory_errors::{self, InsufficientAllocatedCellsError, MemoryError};
26use crate::vm::errors::runner_errors::RunnerError;
27use crate::vm::errors::vm_errors::VirtualMachineError;
28use crate::vm::vm_core::VirtualMachine;
29use crate::vm::vm_memory::memory::Memory;
30use crate::vm::vm_memory::memory_segments::MemorySegmentManager;
31
32mod bitwise;
33mod ec_op;
34mod hash;
35mod keccak;
36mod modulo;
37mod output;
38mod poseidon;
39mod range_check;
40mod segment_arena;
41mod signature;
42
43pub use self::keccak::KeccakBuiltinRunner;
44pub(crate) use self::range_check::{RC_N_PARTS_96, RC_N_PARTS_STANDARD};
45use self::segment_arena::ARENA_BUILTIN_SIZE;
46pub use bitwise::BitwiseBuiltinRunner;
47pub use ec_op::EcOpBuiltinRunner;
48pub use hash::HashBuiltinRunner;
49pub use modulo::ModBuiltinRunner;
50use num_integer::{div_ceil, div_floor};
51pub use output::{OutputBuiltinRunner, OutputBuiltinState};
52pub use poseidon::PoseidonBuiltinRunner;
53pub use range_check::RangeCheckBuiltinRunner;
54pub use segment_arena::SegmentArenaBuiltinRunner;
55pub use signature::SignatureBuiltinRunner;
56
57use super::cairo_pie::BuiltinAdditionalData;
58
59const MIN_N_INSTANCES_IN_BUILTIN_SEGMENT: usize = 16;
60
61// Assert MIN_N_INSTANCES_IN_BUILTIN_SEGMENT is a power of 2.
62const _: () = assert!(MIN_N_INSTANCES_IN_BUILTIN_SEGMENT.is_power_of_two());
63
64/* NB: this enum is no accident: we may need (and cairo-vm-py *does* need)
65 * structs containing this to be `Send`. The only two ways to achieve that
66 * are either storing a `dyn Trait` inside an `Arc<Mutex<&dyn Trait>>` or
67 * making the type itself `Send`. We opted for not complicating the user nor
68 * moving the guarantees to runtime by using an `enum` rather than a `Trait`.
69 * This works under the assumption that we don't expect downstream users to
70 * extend Cairo by adding new builtin runners.
71 */
72#[derive(Debug, Clone)]
73pub enum BuiltinRunner {
74    Bitwise(BitwiseBuiltinRunner),
75    EcOp(EcOpBuiltinRunner),
76    Hash(HashBuiltinRunner),
77    Output(OutputBuiltinRunner),
78    RangeCheck(RangeCheckBuiltinRunner<RC_N_PARTS_STANDARD>),
79    RangeCheck96(RangeCheckBuiltinRunner<RC_N_PARTS_96>),
80    Keccak(KeccakBuiltinRunner),
81    Signature(SignatureBuiltinRunner),
82    Poseidon(PoseidonBuiltinRunner),
83    SegmentArena(SegmentArenaBuiltinRunner),
84    Mod(ModBuiltinRunner),
85}
86
87impl BuiltinRunner {
88    ///Creates the necessary segments for the builtin in the MemorySegmentManager and stores the first address on the builtin's base
89    pub fn initialize_segments(&mut self, segments: &mut MemorySegmentManager) {
90        match *self {
91            BuiltinRunner::Bitwise(ref mut bitwise) => bitwise.initialize_segments(segments),
92            BuiltinRunner::EcOp(ref mut ec) => ec.initialize_segments(segments),
93            BuiltinRunner::Hash(ref mut hash) => hash.initialize_segments(segments),
94            BuiltinRunner::Output(ref mut output) => output.initialize_segments(segments),
95            BuiltinRunner::RangeCheck(ref mut range_check) => {
96                range_check.initialize_segments(segments)
97            }
98            BuiltinRunner::RangeCheck96(ref mut range_check) => {
99                range_check.initialize_segments(segments)
100            }
101            BuiltinRunner::Keccak(ref mut keccak) => keccak.initialize_segments(segments),
102            BuiltinRunner::Signature(ref mut signature) => signature.initialize_segments(segments),
103            BuiltinRunner::Poseidon(ref mut poseidon) => poseidon.initialize_segments(segments),
104            BuiltinRunner::SegmentArena(ref mut segment_arena) => {
105                segment_arena.initialize_segments(segments)
106            }
107            BuiltinRunner::Mod(ref mut modulo) => modulo.initialize_segments(segments),
108        }
109    }
110
111    pub fn initial_stack(&self) -> Vec<MaybeRelocatable> {
112        match *self {
113            BuiltinRunner::Bitwise(ref bitwise) => bitwise.initial_stack(),
114            BuiltinRunner::EcOp(ref ec) => ec.initial_stack(),
115            BuiltinRunner::Hash(ref hash) => hash.initial_stack(),
116            BuiltinRunner::Output(ref output) => output.initial_stack(),
117            BuiltinRunner::RangeCheck(ref range_check) => range_check.initial_stack(),
118            BuiltinRunner::RangeCheck96(ref range_check) => range_check.initial_stack(),
119            BuiltinRunner::Keccak(ref keccak) => keccak.initial_stack(),
120            BuiltinRunner::Signature(ref signature) => signature.initial_stack(),
121            BuiltinRunner::Poseidon(ref poseidon) => poseidon.initial_stack(),
122            BuiltinRunner::SegmentArena(ref segment_arena) => segment_arena.initial_stack(),
123            BuiltinRunner::Mod(ref modulo) => modulo.initial_stack(),
124        }
125    }
126
127    ///Returns the builtin's final stack
128    pub fn final_stack(
129        &mut self,
130        segments: &MemorySegmentManager,
131        pointer: Relocatable,
132    ) -> Result<Relocatable, RunnerError> {
133        if let BuiltinRunner::Output(output) = self {
134            return output.final_stack(segments, pointer);
135        }
136        if self.included() {
137            let stop_pointer_addr =
138                (pointer - 1).map_err(|_| RunnerError::NoStopPointer(Box::new(self.name())))?;
139            let stop_pointer = segments
140                .memory
141                .get_relocatable(stop_pointer_addr)
142                .map_err(|_| RunnerError::NoStopPointer(Box::new(self.name())))?;
143            if self.base() as isize != stop_pointer.segment_index {
144                return Err(RunnerError::InvalidStopPointerIndex(Box::new((
145                    self.name(),
146                    stop_pointer,
147                    self.base(),
148                ))));
149            }
150            let stop_ptr = stop_pointer.offset;
151            let mut num_instances = self.get_used_instances(segments)?;
152            if matches!(self, BuiltinRunner::SegmentArena(_)) {
153                // SegmentArena builtin starts with one instance pre-loaded
154                // This is reflected in the builtin base's offset, but as we compare `stop_ptr.offset` agains `used`
155                // instead of comparing `stop_ptr` against `base + used` we need to account for the base offset (aka the pre-loaded instance) here
156                num_instances += 1;
157            }
158            let used = num_instances * self.cells_per_instance() as usize;
159            if stop_ptr != used {
160                return Err(RunnerError::InvalidStopPointer(Box::new((
161                    self.name(),
162                    Relocatable::from((self.base() as isize, used)),
163                    Relocatable::from((self.base() as isize, stop_ptr)),
164                ))));
165            }
166            self.set_stop_ptr(stop_ptr);
167            Ok(stop_pointer_addr)
168        } else {
169            self.set_stop_ptr(0);
170            Ok(pointer)
171        }
172    }
173
174    ///Returns the builtin's allocated memory units
175    pub fn get_allocated_memory_units(
176        &self,
177        vm: &VirtualMachine,
178    ) -> Result<usize, memory_errors::MemoryError> {
179        Ok(self.get_allocated_instances(vm)? * self.cells_per_instance() as usize)
180    }
181
182    ///Returns the builtin's allocated instances
183    pub fn get_allocated_instances(
184        &self,
185        vm: &VirtualMachine,
186    ) -> Result<usize, memory_errors::MemoryError> {
187        match *self {
188            BuiltinRunner::Output(_) | BuiltinRunner::SegmentArena(_) => Ok(0),
189            _ => {
190                match self.ratio() {
191                    None => {
192                        // Dynamic layout has the exact number of instances it needs (up to a power of 2).
193                        let instances: usize =
194                            self.get_used_cells(&vm.segments)? / self.cells_per_instance() as usize;
195                        let needed_components = instances / self.instances_per_component() as usize;
196
197                        let components = if needed_components > 0 {
198                            needed_components.next_power_of_two()
199                        } else {
200                            0
201                        };
202                        Ok(self.instances_per_component() as usize * components)
203                    }
204                    // Dynamic layout allows for builtins with ratio 0
205                    Some(0) => Ok(0),
206                    Some(ratio) => {
207                        let min_step_num = (ratio * self.instances_per_component()) as usize;
208                        let min_step = if let Some(ratio_den) = self.ratio_den() {
209                            div_ceil(min_step_num, ratio_den as usize)
210                        } else {
211                            min_step_num
212                        };
213
214                        if vm.current_step < min_step {
215                            return Err(InsufficientAllocatedCellsError::MinStepNotReached(
216                                Box::new((min_step, self.name())),
217                            )
218                            .into());
219                        };
220
221                        let allocated_instances = if let Some(ratio_den) = self.ratio_den() {
222                            safe_div_usize(vm.current_step * ratio_den as usize, ratio as usize)
223                                .map_err(|_| MemoryError::ErrorCalculatingMemoryUnits)?
224                        } else {
225                            safe_div_usize(vm.current_step, ratio as usize)
226                                .map_err(|_| MemoryError::ErrorCalculatingMemoryUnits)?
227                        };
228                        Ok(allocated_instances)
229                    }
230                }
231            }
232        }
233    }
234
235    /// Returns if the builtin is included in the program builtins
236    fn included(&self) -> bool {
237        match *self {
238            BuiltinRunner::Bitwise(ref bitwise) => bitwise.included,
239            BuiltinRunner::EcOp(ref ec) => ec.included,
240            BuiltinRunner::Hash(ref hash) => hash.included,
241            BuiltinRunner::Output(ref output) => output.included,
242            BuiltinRunner::RangeCheck(ref range_check) => range_check.included,
243            BuiltinRunner::RangeCheck96(ref range_check) => range_check.included,
244            BuiltinRunner::Keccak(ref keccak) => keccak.included,
245            BuiltinRunner::Signature(ref signature) => signature.included,
246            BuiltinRunner::Poseidon(ref poseidon) => poseidon.included,
247            BuiltinRunner::SegmentArena(ref segment_arena) => segment_arena.included,
248            BuiltinRunner::Mod(ref modulo) => modulo.included,
249        }
250    }
251
252    ///Returns the builtin's base
253    pub fn base(&self) -> usize {
254        match *self {
255            BuiltinRunner::Bitwise(ref bitwise) => bitwise.base(),
256            BuiltinRunner::EcOp(ref ec) => ec.base(),
257            BuiltinRunner::Hash(ref hash) => hash.base(),
258            BuiltinRunner::Output(ref output) => output.base(),
259            BuiltinRunner::RangeCheck(ref range_check) => range_check.base(),
260            BuiltinRunner::RangeCheck96(ref range_check) => range_check.base(),
261            BuiltinRunner::Keccak(ref keccak) => keccak.base(),
262            BuiltinRunner::Signature(ref signature) => signature.base(),
263            BuiltinRunner::Poseidon(ref poseidon) => poseidon.base(),
264            //Warning, returns only the segment index, base offset will be 3
265            BuiltinRunner::SegmentArena(ref segment_arena) => segment_arena.base(),
266            BuiltinRunner::Mod(ref modulo) => modulo.base(),
267        }
268    }
269
270    pub fn ratio(&self) -> Option<u32> {
271        match self {
272            BuiltinRunner::Bitwise(bitwise) => bitwise.ratio(),
273            BuiltinRunner::EcOp(ec) => ec.ratio(),
274            BuiltinRunner::Hash(hash) => hash.ratio(),
275            BuiltinRunner::Output(_) | BuiltinRunner::SegmentArena(_) => None,
276            BuiltinRunner::RangeCheck(range_check) => range_check.ratio(),
277            BuiltinRunner::RangeCheck96(range_check) => range_check.ratio(),
278            BuiltinRunner::Keccak(keccak) => keccak.ratio(),
279            BuiltinRunner::Signature(ref signature) => signature.ratio(),
280            BuiltinRunner::Poseidon(poseidon) => poseidon.ratio(),
281            BuiltinRunner::Mod(ref modulo) => modulo.ratio(),
282        }
283    }
284
285    pub fn ratio_den(&self) -> Option<u32> {
286        match self {
287            BuiltinRunner::RangeCheck(range_check) => range_check.ratio_den(),
288            BuiltinRunner::RangeCheck96(range_check) => range_check.ratio_den(),
289            BuiltinRunner::Mod(modulo) => modulo.ratio_den(),
290            _ => None,
291        }
292    }
293
294    pub fn add_validation_rule(&self, memory: &mut Memory) {
295        match *self {
296            BuiltinRunner::RangeCheck(ref range_check) => range_check.add_validation_rule(memory),
297            BuiltinRunner::RangeCheck96(ref range_check) => range_check.add_validation_rule(memory),
298            BuiltinRunner::Signature(ref signature) => signature.add_validation_rule(memory),
299            BuiltinRunner::Poseidon(ref poseidon) => poseidon.add_validation_rule(memory),
300            _ => {}
301        }
302    }
303
304    pub fn deduce_memory_cell(
305        &self,
306        address: Relocatable,
307        memory: &Memory,
308    ) -> Result<Option<MaybeRelocatable>, RunnerError> {
309        match *self {
310            BuiltinRunner::Bitwise(ref bitwise) => bitwise.deduce_memory_cell(address, memory),
311            BuiltinRunner::EcOp(ref ec) => ec.deduce_memory_cell(address, memory),
312            BuiltinRunner::Hash(ref hash) => hash.deduce_memory_cell(address, memory),
313            BuiltinRunner::Keccak(ref keccak) => keccak.deduce_memory_cell(address, memory),
314            BuiltinRunner::Poseidon(ref poseidon) => poseidon.deduce_memory_cell(address, memory),
315            _ => Ok(None),
316        }
317    }
318
319    pub fn get_memory_segment_addresses(&self) -> (usize, Option<usize>) {
320        (self.base(), self.stop_ptr())
321    }
322
323    pub fn get_used_cells(&self, segments: &MemorySegmentManager) -> Result<usize, MemoryError> {
324        match self {
325            BuiltinRunner::Bitwise(ref bitwise) => bitwise.get_used_cells(segments),
326            BuiltinRunner::EcOp(ref ec) => ec.get_used_cells(segments),
327            BuiltinRunner::Hash(ref hash) => hash.get_used_cells(segments),
328            BuiltinRunner::Output(ref output) => output.get_used_cells(segments),
329            BuiltinRunner::RangeCheck(ref range_check) => range_check.get_used_cells(segments),
330            BuiltinRunner::RangeCheck96(ref range_check) => range_check.get_used_cells(segments),
331            BuiltinRunner::Keccak(ref keccak) => keccak.get_used_cells(segments),
332            BuiltinRunner::Signature(ref signature) => signature.get_used_cells(segments),
333            BuiltinRunner::Poseidon(ref poseidon) => poseidon.get_used_cells(segments),
334            BuiltinRunner::SegmentArena(ref segment_arena) => {
335                segment_arena.get_used_cells(segments)
336            }
337            BuiltinRunner::Mod(ref modulo) => modulo.get_used_cells(segments),
338        }
339    }
340
341    pub fn get_used_instances(
342        &self,
343        segments: &MemorySegmentManager,
344    ) -> Result<usize, MemoryError> {
345        match self {
346            BuiltinRunner::Bitwise(ref bitwise) => bitwise.get_used_instances(segments),
347            BuiltinRunner::EcOp(ref ec) => ec.get_used_instances(segments),
348            BuiltinRunner::Hash(ref hash) => hash.get_used_instances(segments),
349            BuiltinRunner::Output(ref output) => output.get_used_instances(segments),
350            BuiltinRunner::RangeCheck(ref range_check) => range_check.get_used_instances(segments),
351            BuiltinRunner::RangeCheck96(ref range_check) => {
352                range_check.get_used_instances(segments)
353            }
354            BuiltinRunner::Keccak(ref keccak) => keccak.get_used_instances(segments),
355            BuiltinRunner::Signature(ref signature) => signature.get_used_instances(segments),
356            BuiltinRunner::Poseidon(ref poseidon) => poseidon.get_used_instances(segments),
357            BuiltinRunner::SegmentArena(ref segment_arena) => {
358                segment_arena.get_used_instances(segments)
359            }
360            BuiltinRunner::Mod(modulo) => modulo.get_used_instances(segments),
361        }
362    }
363
364    pub fn get_range_check_usage(&self, memory: &Memory) -> Option<(usize, usize)> {
365        match self {
366            BuiltinRunner::RangeCheck(ref range_check) => range_check.get_range_check_usage(memory),
367            BuiltinRunner::RangeCheck96(ref range_check) => {
368                range_check.get_range_check_usage(memory)
369            }
370            _ => None,
371        }
372    }
373
374    /// Returns the number of range check units used by the builtin.
375    pub fn get_used_perm_range_check_units(
376        &self,
377        vm: &VirtualMachine,
378    ) -> Result<usize, MemoryError> {
379        match self {
380            BuiltinRunner::RangeCheck(range_check) => {
381                let (used_cells, _) = self.get_used_cells_and_allocated_size(vm)?;
382                Ok(used_cells * range_check.n_parts() as usize)
383            }
384            BuiltinRunner::RangeCheck96(range_check) => {
385                let (used_cells, _) = self.get_used_cells_and_allocated_size(vm)?;
386                Ok(used_cells * range_check.n_parts() as usize)
387            }
388            _ => Ok(0),
389        }
390    }
391
392    pub fn get_used_diluted_check_units(&self, diluted_spacing: u32, diluted_n_bits: u32) -> usize {
393        match self {
394            BuiltinRunner::Bitwise(ref bitwise) => {
395                bitwise.get_used_diluted_check_units(diluted_spacing, diluted_n_bits)
396            }
397            BuiltinRunner::Keccak(ref keccak) => {
398                keccak.get_used_diluted_check_units(diluted_n_bits)
399            }
400            _ => 0,
401        }
402    }
403
404    fn cells_per_instance(&self) -> u32 {
405        match self {
406            BuiltinRunner::Bitwise(_) => CELLS_PER_BITWISE,
407            BuiltinRunner::EcOp(_) => CELLS_PER_EC_OP,
408            BuiltinRunner::Hash(_) => CELLS_PER_HASH,
409            BuiltinRunner::RangeCheck(_) | BuiltinRunner::RangeCheck96(_) => CELLS_PER_RANGE_CHECK,
410            BuiltinRunner::Output(_) => 0,
411            BuiltinRunner::Keccak(_) => CELLS_PER_KECCAK,
412            BuiltinRunner::Signature(_) => CELLS_PER_SIGNATURE,
413            BuiltinRunner::Poseidon(_) => CELLS_PER_POSEIDON,
414            BuiltinRunner::SegmentArena(_) => ARENA_BUILTIN_SIZE,
415            BuiltinRunner::Mod(_) => CELLS_PER_MOD,
416        }
417    }
418
419    fn n_input_cells(&self) -> u32 {
420        match self {
421            BuiltinRunner::Bitwise(_) => INPUT_CELLS_PER_BITWISE,
422            BuiltinRunner::EcOp(_) => INPUT_CELLS_PER_EC_OP,
423            BuiltinRunner::Hash(_) => INPUT_CELLS_PER_HASH,
424            BuiltinRunner::RangeCheck(_) | BuiltinRunner::RangeCheck96(_) => CELLS_PER_RANGE_CHECK,
425            BuiltinRunner::Output(_) => 0,
426            BuiltinRunner::Keccak(_) => INPUT_CELLS_PER_KECCAK,
427            BuiltinRunner::Signature(_) => CELLS_PER_SIGNATURE,
428            BuiltinRunner::Poseidon(_) => INPUT_CELLS_PER_POSEIDON,
429            BuiltinRunner::SegmentArena(_) => ARENA_BUILTIN_SIZE,
430            BuiltinRunner::Mod(_) => CELLS_PER_MOD,
431        }
432    }
433
434    fn instances_per_component(&self) -> u32 {
435        match self {
436            BuiltinRunner::Keccak(_) => KECCAK_INSTANCES_PER_COMPONENT,
437            _ => BUILTIN_INSTANCES_PER_COMPONENT,
438        }
439    }
440
441    pub fn name(&self) -> BuiltinName {
442        match self {
443            BuiltinRunner::Bitwise(_) => BuiltinName::bitwise,
444            BuiltinRunner::EcOp(_) => BuiltinName::ec_op,
445            BuiltinRunner::Hash(_) => BuiltinName::pedersen,
446            BuiltinRunner::RangeCheck(_) => BuiltinName::range_check,
447            BuiltinRunner::RangeCheck96(_) => BuiltinName::range_check96,
448            BuiltinRunner::Output(_) => BuiltinName::output,
449            BuiltinRunner::Keccak(_) => BuiltinName::keccak,
450            BuiltinRunner::Signature(_) => BuiltinName::ecdsa,
451            BuiltinRunner::Poseidon(_) => BuiltinName::poseidon,
452            BuiltinRunner::SegmentArena(_) => BuiltinName::segment_arena,
453            BuiltinRunner::Mod(b) => b.name(),
454        }
455    }
456
457    pub fn run_security_checks(&self, vm: &VirtualMachine) -> Result<(), VirtualMachineError> {
458        if let BuiltinRunner::Output(_) | BuiltinRunner::SegmentArena(_) = self {
459            return Ok(());
460        }
461        if let BuiltinRunner::Mod(modulo) = self {
462            modulo.run_additional_security_checks(vm)?;
463        }
464        let cells_per_instance = self.cells_per_instance() as usize;
465        let n_input_cells = self.n_input_cells() as usize;
466        let builtin_segment_index = self.base();
467        // If the builtin's segment is empty, there are no security checks to run
468        let builtin_segment = match vm.segments.memory.data.get(builtin_segment_index) {
469            Some(segment) if !segment.is_empty() => segment,
470            _ => return Ok(()),
471        };
472        // The builtin segment's size - 1 is the maximum offset within the segment's addresses
473        // Assumption: The last element is not a None value
474        // It is safe to asume this for normal program execution
475        // If there are trailing None values at the end, the following security checks will fail
476        let offset_max = builtin_segment.len().saturating_sub(1);
477        // offset_len is the amount of non-None values in the segment
478        let offset_len = builtin_segment.iter().filter(|x| x.is_some()).count();
479        let n = match offset_len {
480            0 => 0,
481            _ => div_floor(offset_max, cells_per_instance) + 1,
482        };
483        // Verify that n is not too large to make sure the expected_offsets set that is constructed
484        // below is not too large.
485        if n > div_floor(offset_len, n_input_cells) {
486            return Err(MemoryError::MissingMemoryCells(Box::new(self.name())).into());
487        }
488        // Check that the two inputs (x and y) of each instance are set.
489        let mut missing_offsets = Vec::with_capacity(n);
490        // Check for missing expected offsets (either their address is no present, or their value is None)
491        for i in 0..n {
492            for j in 0..n_input_cells {
493                let offset = cells_per_instance * i + j;
494                if builtin_segment
495                    .get(offset)
496                    .filter(|x| x.is_some())
497                    .is_none()
498                {
499                    missing_offsets.push(offset)
500                }
501            }
502        }
503        if !missing_offsets.is_empty() {
504            return Err(MemoryError::MissingMemoryCellsWithOffsets(Box::new((
505                self.name(),
506                missing_offsets,
507            )))
508            .into());
509        }
510        // Verify auto deduction rules for the unasigned output cells
511        // Assigned output cells are checked as part of the call to verify_auto_deductions().
512        for i in 0..n {
513            for j in n_input_cells..cells_per_instance {
514                let offset = cells_per_instance * i + j;
515                if builtin_segment
516                    .get(offset)
517                    .filter(|x| x.is_some())
518                    .is_none()
519                {
520                    vm.verify_auto_deductions_for_addr(
521                        Relocatable::from((builtin_segment_index as isize, offset)),
522                        self,
523                    )?;
524                }
525            }
526        }
527        Ok(())
528    }
529
530    pub fn get_used_cells_and_allocated_size(
531        &self,
532        vm: &VirtualMachine,
533    ) -> Result<(usize, usize), MemoryError> {
534        match self {
535            BuiltinRunner::Output(_) | BuiltinRunner::SegmentArena(_) => {
536                let used = self.get_used_cells(&vm.segments)?;
537                Ok((used, used))
538            }
539            _ => {
540                let used_cells = self.get_used_cells(&vm.segments)?;
541                if vm.disable_trace_padding {
542                    // If trace padding is disabled, we pad the used cells to still ensure that the
543                    // number of instances is a power of 2, and at least
544                    // MIN_N_INSTANCES_IN_BUILTIN_SEGMENT.
545                    let num_instances = self.get_used_instances(&vm.segments)?;
546                    let padded_used_cells = if num_instances > 0 {
547                        let padded_num_instances = core::cmp::max(
548                            MIN_N_INSTANCES_IN_BUILTIN_SEGMENT,
549                            num_instances.next_power_of_two(),
550                        );
551                        padded_num_instances * self.cells_per_instance() as usize
552                    } else {
553                        0
554                    };
555                    Ok((used_cells, padded_used_cells))
556                } else {
557                    let size = self.get_allocated_memory_units(vm)?;
558                    if used_cells > size {
559                        return Err(InsufficientAllocatedCellsError::BuiltinCells(Box::new((
560                            self.name(),
561                            used_cells,
562                            size,
563                        )))
564                        .into());
565                    }
566                    Ok((used_cells, size))
567                }
568            }
569        }
570    }
571
572    /// Returns data stored internally by builtins needed to re-execute from a cairo pie
573    pub fn get_additional_data(&self) -> BuiltinAdditionalData {
574        match self {
575            BuiltinRunner::Hash(builtin) => builtin.get_additional_data(),
576            BuiltinRunner::Output(builtin) => builtin.get_additional_data(),
577            BuiltinRunner::Signature(builtin) => builtin.get_additional_data(),
578            _ => BuiltinAdditionalData::None,
579        }
580    }
581
582    /// Extends the builtin's internal data with the internal data obtained from a previous cairo execution
583    /// Used solely when running from a cairo pie
584    pub fn extend_additional_data(
585        &mut self,
586        additional_data: &BuiltinAdditionalData,
587    ) -> Result<(), RunnerError> {
588        match self {
589            BuiltinRunner::Hash(builtin) => builtin.extend_additional_data(additional_data),
590            BuiltinRunner::Output(builtin) => builtin.extend_additional_data(additional_data),
591            BuiltinRunner::Signature(builtin) => builtin.extend_additional_data(additional_data),
592            _ => Ok(()),
593        }
594    }
595
596    // Returns information about the builtin that should be added to the AIR private input.
597    pub fn air_private_input(&self, segments: &MemorySegmentManager) -> Vec<PrivateInput> {
598        match self {
599            BuiltinRunner::RangeCheck(builtin) => builtin.air_private_input(&segments.memory),
600            BuiltinRunner::RangeCheck96(builtin) => builtin.air_private_input(&segments.memory),
601            BuiltinRunner::Bitwise(builtin) => builtin.air_private_input(&segments.memory),
602            BuiltinRunner::Hash(builtin) => builtin.air_private_input(&segments.memory),
603            BuiltinRunner::EcOp(builtin) => builtin.air_private_input(&segments.memory),
604            BuiltinRunner::Poseidon(builtin) => builtin.air_private_input(&segments.memory),
605            BuiltinRunner::Signature(builtin) => builtin.air_private_input(&segments.memory),
606            BuiltinRunner::Keccak(builtin) => builtin.air_private_input(&segments.memory),
607            BuiltinRunner::Mod(builtin) => builtin.air_private_input(segments),
608            _ => vec![],
609        }
610    }
611
612    pub(crate) fn set_stop_ptr(&mut self, stop_ptr: usize) {
613        match self {
614            BuiltinRunner::Bitwise(ref mut bitwise) => bitwise.stop_ptr = Some(stop_ptr),
615            BuiltinRunner::EcOp(ref mut ec) => ec.stop_ptr = Some(stop_ptr),
616            BuiltinRunner::Hash(ref mut hash) => hash.stop_ptr = Some(stop_ptr),
617            BuiltinRunner::Output(ref mut output) => output.stop_ptr = Some(stop_ptr),
618            BuiltinRunner::RangeCheck(ref mut range_check) => range_check.stop_ptr = Some(stop_ptr),
619            BuiltinRunner::RangeCheck96(ref mut range_check) => {
620                range_check.stop_ptr = Some(stop_ptr)
621            }
622            BuiltinRunner::Keccak(ref mut keccak) => keccak.stop_ptr = Some(stop_ptr),
623            BuiltinRunner::Signature(ref mut signature) => signature.stop_ptr = Some(stop_ptr),
624            BuiltinRunner::Poseidon(ref mut poseidon) => poseidon.stop_ptr = Some(stop_ptr),
625            BuiltinRunner::SegmentArena(ref mut segment_arena) => {
626                segment_arena.stop_ptr = Some(stop_ptr)
627            }
628            BuiltinRunner::Mod(modulo) => modulo.stop_ptr = Some(stop_ptr),
629        }
630    }
631
632    pub(crate) fn stop_ptr(&self) -> Option<usize> {
633        match self {
634            BuiltinRunner::Bitwise(ref bitwise) => bitwise.stop_ptr,
635            BuiltinRunner::EcOp(ref ec) => ec.stop_ptr,
636            BuiltinRunner::Hash(ref hash) => hash.stop_ptr,
637            BuiltinRunner::Output(ref output) => output.stop_ptr,
638            BuiltinRunner::RangeCheck(ref range_check) => range_check.stop_ptr,
639            BuiltinRunner::RangeCheck96(ref range_check) => range_check.stop_ptr,
640            BuiltinRunner::Keccak(ref keccak) => keccak.stop_ptr,
641            BuiltinRunner::Signature(ref signature) => signature.stop_ptr,
642            BuiltinRunner::Poseidon(ref poseidon) => poseidon.stop_ptr,
643            BuiltinRunner::SegmentArena(ref segment_arena) => segment_arena.stop_ptr,
644            BuiltinRunner::Mod(ref modulo) => modulo.stop_ptr,
645        }
646    }
647}
648
649impl From<KeccakBuiltinRunner> for BuiltinRunner {
650    fn from(runner: KeccakBuiltinRunner) -> Self {
651        BuiltinRunner::Keccak(runner)
652    }
653}
654
655impl From<BitwiseBuiltinRunner> for BuiltinRunner {
656    fn from(runner: BitwiseBuiltinRunner) -> Self {
657        BuiltinRunner::Bitwise(runner)
658    }
659}
660
661impl From<EcOpBuiltinRunner> for BuiltinRunner {
662    fn from(runner: EcOpBuiltinRunner) -> Self {
663        BuiltinRunner::EcOp(runner)
664    }
665}
666
667impl From<HashBuiltinRunner> for BuiltinRunner {
668    fn from(runner: HashBuiltinRunner) -> Self {
669        BuiltinRunner::Hash(runner)
670    }
671}
672
673impl From<OutputBuiltinRunner> for BuiltinRunner {
674    fn from(runner: OutputBuiltinRunner) -> Self {
675        BuiltinRunner::Output(runner)
676    }
677}
678
679impl From<RangeCheckBuiltinRunner<RC_N_PARTS_STANDARD>> for BuiltinRunner {
680    fn from(runner: RangeCheckBuiltinRunner<RC_N_PARTS_STANDARD>) -> Self {
681        BuiltinRunner::RangeCheck(runner)
682    }
683}
684
685impl From<RangeCheckBuiltinRunner<RC_N_PARTS_96>> for BuiltinRunner {
686    fn from(runner: RangeCheckBuiltinRunner<RC_N_PARTS_96>) -> Self {
687        BuiltinRunner::RangeCheck96(runner)
688    }
689}
690
691impl From<SignatureBuiltinRunner> for BuiltinRunner {
692    fn from(runner: SignatureBuiltinRunner) -> Self {
693        BuiltinRunner::Signature(runner)
694    }
695}
696
697impl From<PoseidonBuiltinRunner> for BuiltinRunner {
698    fn from(runner: PoseidonBuiltinRunner) -> Self {
699        BuiltinRunner::Poseidon(runner)
700    }
701}
702
703impl From<SegmentArenaBuiltinRunner> for BuiltinRunner {
704    fn from(runner: SegmentArenaBuiltinRunner) -> Self {
705        BuiltinRunner::SegmentArena(runner)
706    }
707}
708
709impl From<ModBuiltinRunner> for BuiltinRunner {
710    fn from(runner: ModBuiltinRunner) -> Self {
711        BuiltinRunner::Mod(runner)
712    }
713}
714
715#[cfg(test)]
716mod tests {
717    use super::*;
718    use crate::cairo_run::{cairo_run, CairoRunConfig};
719    use crate::hint_processor::builtin_hint_processor::builtin_hint_processor_definition::BuiltinHintProcessor;
720    use crate::relocatable;
721    use crate::types::builtin_name::BuiltinName;
722    use crate::types::instance_definitions::mod_instance_def::ModInstanceDef;
723    use crate::types::instance_definitions::LowRatio;
724    use crate::types::layout_name::LayoutName;
725    use crate::types::program::Program;
726    use crate::utils::test_utils::*;
727    use crate::vm::errors::memory_errors::InsufficientAllocatedCellsError;
728    use crate::vm::vm_memory::memory::MemoryCell;
729    use assert_matches::assert_matches;
730
731    #[cfg(target_arch = "wasm32")]
732    use wasm_bindgen_test::*;
733
734    #[test]
735    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
736    fn get_n_input_cells_bitwise() {
737        let bitwise = BitwiseBuiltinRunner::new(Some(10), true);
738        let builtin: BuiltinRunner = bitwise.clone().into();
739        assert_eq!(INPUT_CELLS_PER_BITWISE, builtin.n_input_cells())
740    }
741
742    #[test]
743    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
744    fn get_n_input_cells_hash() {
745        let hash = HashBuiltinRunner::new(Some(10), true);
746        let builtin: BuiltinRunner = hash.clone().into();
747        assert_eq!(INPUT_CELLS_PER_HASH, builtin.n_input_cells())
748    }
749
750    #[test]
751    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
752    fn get_n_input_cells_ec_op() {
753        let ec_op = EcOpBuiltinRunner::new(Some(256), true);
754        let builtin: BuiltinRunner = ec_op.clone().into();
755        assert_eq!(INPUT_CELLS_PER_EC_OP, builtin.n_input_cells())
756    }
757
758    #[test]
759    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
760    fn get_n_input_cells_ecdsa() {
761        let signature = SignatureBuiltinRunner::new(Some(10), true);
762        let builtin: BuiltinRunner = signature.clone().into();
763        assert_eq!(CELLS_PER_SIGNATURE, builtin.n_input_cells())
764    }
765
766    #[test]
767    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
768    fn get_n_input_cells_output() {
769        let output = OutputBuiltinRunner::new(true);
770        let builtin: BuiltinRunner = output.into();
771        assert_eq!(0, builtin.n_input_cells())
772    }
773
774    #[test]
775    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
776    fn get_cells_per_instance_bitwise() {
777        let bitwise = BitwiseBuiltinRunner::new(Some(10), true);
778        let builtin: BuiltinRunner = bitwise.clone().into();
779        assert_eq!(CELLS_PER_BITWISE, builtin.cells_per_instance())
780    }
781
782    #[test]
783    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
784    fn get_cells_per_instance_hash() {
785        let hash = HashBuiltinRunner::new(Some(10), true);
786        let builtin: BuiltinRunner = hash.clone().into();
787        assert_eq!(CELLS_PER_HASH, builtin.cells_per_instance())
788    }
789
790    #[test]
791    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
792    fn get_cells_per_instance_ec_op() {
793        let ec_op = EcOpBuiltinRunner::new(Some(256), true);
794        let builtin: BuiltinRunner = ec_op.clone().into();
795        assert_eq!(CELLS_PER_EC_OP, builtin.cells_per_instance())
796    }
797
798    #[test]
799    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
800    fn get_cells_per_instance_ecdsa() {
801        let signature = SignatureBuiltinRunner::new(Some(10), true);
802        let builtin: BuiltinRunner = signature.clone().into();
803        assert_eq!(CELLS_PER_SIGNATURE, builtin.cells_per_instance())
804    }
805
806    #[test]
807    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
808    fn get_cells_per_instance_output() {
809        let output = OutputBuiltinRunner::new(true);
810        let builtin: BuiltinRunner = output.into();
811        assert_eq!(0, builtin.cells_per_instance())
812    }
813
814    #[test]
815    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
816    fn get_name_bitwise() {
817        let bitwise = BitwiseBuiltinRunner::new(Some(10), true);
818        let builtin: BuiltinRunner = bitwise.into();
819        assert_eq!(BuiltinName::bitwise, builtin.name())
820    }
821
822    #[test]
823    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
824    fn get_name_hash() {
825        let hash = HashBuiltinRunner::new(Some(10), true);
826        let builtin: BuiltinRunner = hash.into();
827        assert_eq!(BuiltinName::pedersen, builtin.name())
828    }
829
830    #[test]
831    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
832    fn get_name_range_check() {
833        let range_check = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), true);
834        let builtin: BuiltinRunner = range_check.into();
835        assert_eq!(BuiltinName::range_check, builtin.name())
836    }
837
838    #[test]
839    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
840    fn get_name_ec_op() {
841        let ec_op = EcOpBuiltinRunner::new(Some(256), true);
842        let builtin: BuiltinRunner = ec_op.into();
843        assert_eq!(BuiltinName::ec_op, builtin.name())
844    }
845
846    #[test]
847    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
848    fn get_name_ecdsa() {
849        let signature = SignatureBuiltinRunner::new(Some(10), true);
850        let builtin: BuiltinRunner = signature.into();
851        assert_eq!(BuiltinName::ecdsa, builtin.name())
852    }
853
854    #[test]
855    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
856    fn get_name_output() {
857        let output = OutputBuiltinRunner::new(true);
858        let builtin: BuiltinRunner = output.into();
859        assert_eq!(BuiltinName::output, builtin.name())
860    }
861
862    #[test]
863    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
864    fn get_allocated_memory_units_bitwise_with_items() {
865        let builtin = BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(10), true));
866
867        let program = program!(
868            builtins = vec![BuiltinName::bitwise],
869            data = vec_data!(
870                (4612671182993129469_i64),
871                (5189976364521848832_i64),
872                (18446744073709551615_i128),
873                (5199546496550207487_i64),
874                (4612389712311386111_i64),
875                (5198983563776393216_i64),
876                (2),
877                (2345108766317314046_i64),
878                (5191102247248822272_i64),
879                (5189976364521848832_i64),
880                (7),
881                (1226245742482522112_i64),
882                ((
883                    "3618502788666131213697322783095070105623107215331596699973092056135872020470",
884                    10
885                )),
886                (2345108766317314046_i64)
887            ),
888            main = Some(8),
889        );
890
891        let mut cairo_runner = cairo_runner!(program);
892
893        let mut hint_processor = BuiltinHintProcessor::new_empty();
894
895        let address = cairo_runner.initialize(false).unwrap();
896
897        cairo_runner
898            .run_until_pc(address, &mut hint_processor)
899            .unwrap();
900
901        assert_eq!(builtin.get_allocated_memory_units(&cairo_runner.vm), Ok(5));
902    }
903
904    #[test]
905    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
906    fn compare_proof_mode_with_and_without_disable_trace_padding() {
907        const PEDERSEN_TEST: &[u8] =
908            include_bytes!("../../../../../cairo_programs/proof_programs/pedersen_test.json");
909        const BIGINT_TEST: &[u8] =
910            include_bytes!("../../../../../cairo_programs/proof_programs/bigint.json");
911        const POSEIDON_HASH_TEST: &[u8] =
912            include_bytes!("../../../../../cairo_programs/proof_programs/poseidon_hash.json");
913
914        let program_files = vec![PEDERSEN_TEST, BIGINT_TEST, POSEIDON_HASH_TEST];
915
916        for program_data in program_files {
917            let config_false = CairoRunConfig {
918                disable_trace_padding: false,
919                proof_mode: true,
920                layout: LayoutName::all_cairo,
921                ..Default::default()
922            };
923            let mut hint_processor_false = BuiltinHintProcessor::new_empty();
924            let runner_false =
925                cairo_run(program_data, &config_false, &mut hint_processor_false).unwrap();
926            let last_step_false = runner_false.vm.current_step;
927
928            assert!(last_step_false.is_power_of_two());
929
930            let config_true = CairoRunConfig {
931                disable_trace_padding: true,
932                proof_mode: true,
933                layout: LayoutName::all_cairo,
934                ..Default::default()
935            };
936            let mut hint_processor_true = BuiltinHintProcessor::new_empty();
937            let runner_true =
938                cairo_run(program_data, &config_true, &mut hint_processor_true).unwrap();
939            let last_step_true = runner_true.vm.current_step;
940
941            // Ensure the last step is not a power of two - true for this specific program, not always.
942            assert!(!last_step_true.is_power_of_two());
943
944            assert!(last_step_true < last_step_false);
945
946            let builtin_runners_false = &runner_false.vm.builtin_runners;
947            let builtin_runners_true = &runner_true.vm.builtin_runners;
948            assert_eq!(builtin_runners_false.len(), builtin_runners_true.len());
949            // Compare allocated instances for each pair of builtin runners.
950            for (builtin_runner_false, builtin_runner_true) in builtin_runners_false
951                .iter()
952                .zip(builtin_runners_true.iter())
953            {
954                assert_eq!(builtin_runner_false.name(), builtin_runner_true.name());
955                match builtin_runner_false {
956                    BuiltinRunner::Output(_) | BuiltinRunner::SegmentArena(_) => {
957                        continue;
958                    }
959                    _ => {}
960                }
961                let (_, allocated_size_false) = builtin_runner_false
962                    .get_used_cells_and_allocated_size(&runner_false.vm)
963                    .unwrap();
964                let (used_cells_true, allocated_size_true) = builtin_runner_true
965                    .get_used_cells_and_allocated_size(&runner_true.vm)
966                    .unwrap();
967                let n_allocated_instances_false = safe_div_usize(
968                    allocated_size_false,
969                    builtin_runner_false.cells_per_instance() as usize,
970                )
971                .unwrap();
972                let n_allocated_instances_true = safe_div_usize(
973                    allocated_size_true,
974                    builtin_runner_true.cells_per_instance() as usize,
975                )
976                .unwrap();
977                assert!(
978                    n_allocated_instances_false.is_power_of_two()
979                        || n_allocated_instances_false == 0
980                );
981                assert!(
982                    n_allocated_instances_true.is_power_of_two() || n_allocated_instances_true == 0
983                );
984                // Assert the builtin segment is padded to at least
985                // `MIN_N_INSTANCES_IN_BUILTIN_SEGMENT`.
986                // Pedersen proof has exactly one pedersen builtin, so this indeed tests the padding
987                // to at least `MIN_N_INSTANCES_IN_BUILTIN_SEGMENT`.
988                assert!(
989                    n_allocated_instances_true >= MIN_N_INSTANCES_IN_BUILTIN_SEGMENT
990                        || n_allocated_instances_true == 0
991                );
992
993                // Checks that the number of allocated instances is different when trace padding is
994                // enabled/disabled. Holds for this specific program, not always (that is, in other
995                // programs, padding may be of size 0, or the same).
996                assert!(
997                    n_allocated_instances_true == 0
998                        || n_allocated_instances_true != n_allocated_instances_false
999                );
1000
1001                // Since the last instance of the builtin isn't guaranteed to have a full output,
1002                // the number of used_cells might not be a multiple of cells_per_instance, so we
1003                // make sure that the discrepancy is up to the number of output cells.
1004                // This is the same for both cases, so we only check one (true).
1005                let n_output_cells = builtin_runner_true.cells_per_instance() as usize
1006                    - builtin_runner_true.n_input_cells() as usize;
1007                assert!(
1008                    used_cells_true + n_output_cells
1009                        >= (builtin_runner_true.cells_per_instance() as usize)
1010                            * builtin_runner_true
1011                                .get_used_instances(&runner_true.vm.segments)
1012                                .unwrap()
1013                );
1014            }
1015        }
1016    }
1017
1018    #[test]
1019    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1020    fn get_allocated_memory_units_ec_op_with_items() {
1021        let builtin = BuiltinRunner::EcOp(EcOpBuiltinRunner::new(Some(10), true));
1022
1023        let program = program!(
1024            builtins = vec![BuiltinName::ec_op],
1025            data = vec_data!(
1026                (4612671182993129469_i64),
1027                (5189976364521848832_i64),
1028                (18446744073709551615_i128),
1029                (5199546496550207487_i64),
1030                (4612389712311386111_i64),
1031                (5198983563776393216_i64),
1032                (2),
1033                (2345108766317314046_i64),
1034                (5191102247248822272_i64),
1035                (5189976364521848832_i64),
1036                (7),
1037                (1226245742482522112_i64),
1038                ((
1039                    "3618502788666131213697322783095070105623107215331596699973092056135872020470",
1040                    10
1041                )),
1042                (2345108766317314046_i64)
1043            ),
1044            main = Some(8),
1045        );
1046
1047        let mut cairo_runner = cairo_runner!(program);
1048
1049        let mut hint_processor = BuiltinHintProcessor::new_empty();
1050
1051        let address = cairo_runner.initialize(false).unwrap();
1052
1053        cairo_runner
1054            .run_until_pc(address, &mut hint_processor)
1055            .unwrap();
1056
1057        assert_eq!(builtin.get_allocated_memory_units(&cairo_runner.vm), Ok(7));
1058    }
1059
1060    #[test]
1061    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1062    fn get_allocated_memory_units_hash_with_items() {
1063        let builtin = BuiltinRunner::Hash(HashBuiltinRunner::new(Some(10), true));
1064
1065        let program = program!(
1066            builtins = vec![BuiltinName::pedersen],
1067            data = vec_data!(
1068                (4612671182993129469_i64),
1069                (5189976364521848832_i64),
1070                (18446744073709551615_i128),
1071                (5199546496550207487_i64),
1072                (4612389712311386111_i64),
1073                (5198983563776393216_i64),
1074                (2),
1075                (2345108766317314046_i64),
1076                (5191102247248822272_i64),
1077                (5189976364521848832_i64),
1078                (7),
1079                (1226245742482522112_i64),
1080                ((
1081                    "3618502788666131213697322783095070105623107215331596699973092056135872020470",
1082                    10
1083                )),
1084                (2345108766317314046_i64)
1085            ),
1086            main = Some(8),
1087        );
1088
1089        let mut cairo_runner = cairo_runner!(program);
1090
1091        let mut hint_processor = BuiltinHintProcessor::new_empty();
1092
1093        let address = cairo_runner.initialize(false).unwrap();
1094
1095        cairo_runner
1096            .run_until_pc(address, &mut hint_processor)
1097            .unwrap();
1098
1099        assert_eq!(builtin.get_allocated_memory_units(&cairo_runner.vm), Ok(3));
1100    }
1101
1102    #[test]
1103    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1104    fn get_allocated_memory_units_range_check_with_items() {
1105        let builtin = BuiltinRunner::RangeCheck(
1106            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), true),
1107        );
1108
1109        let program = program!(
1110            builtins = vec![BuiltinName::range_check],
1111            data = vec_data!(
1112                (4612671182993129469_i64),
1113                (5189976364521848832_i64),
1114                (18446744073709551615_i128),
1115                (5199546496550207487_i64),
1116                (4612389712311386111_i64),
1117                (5198983563776393216_i64),
1118                (2),
1119                (2345108766317314046_i64),
1120                (5191102247248822272_i64),
1121                (5189976364521848832_i64),
1122                (7),
1123                (1226245742482522112_i64),
1124                ((
1125                    "3618502788666131213697322783095070105623107215331596699973092056135872020470",
1126                    10
1127                )),
1128                (2345108766317314046_i64)
1129            ),
1130            main = Some(8),
1131        );
1132
1133        let mut cairo_runner = cairo_runner!(program);
1134
1135        let mut hint_processor = BuiltinHintProcessor::new_empty();
1136
1137        let address = cairo_runner.initialize(false).unwrap();
1138
1139        cairo_runner
1140            .run_until_pc(address, &mut hint_processor)
1141            .unwrap();
1142
1143        assert_eq!(builtin.get_allocated_memory_units(&cairo_runner.vm), Ok(1));
1144    }
1145
1146    #[test]
1147    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1148    fn get_allocated_memory_units_keccak_with_items() {
1149        let builtin = BuiltinRunner::Keccak(KeccakBuiltinRunner::new(Some(10), true));
1150
1151        let mut vm = vm!();
1152        vm.current_step = 160;
1153        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(256));
1154    }
1155
1156    #[test]
1157    fn get_allocated_memory_units_keccak_min_steps_not_reached() {
1158        let builtin = BuiltinRunner::Keccak(KeccakBuiltinRunner::new(Some(10), true));
1159
1160        let mut vm = vm!();
1161        vm.current_step = 10;
1162        assert_eq!(
1163            builtin.get_allocated_memory_units(&vm),
1164            Err(MemoryError::InsufficientAllocatedCells(
1165                InsufficientAllocatedCellsError::MinStepNotReached(Box::new((
1166                    160,
1167                    BuiltinName::keccak
1168                )))
1169            ))
1170        );
1171    }
1172
1173    #[test]
1174    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1175    fn get_allocated_memory_units_output() {
1176        let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
1177        let vm = vm!();
1178
1179        // In this case, the function always return Ok(0)
1180        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(0));
1181    }
1182
1183    #[test]
1184    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1185    fn get_allocated_memory_units_range_check() {
1186        let builtin = BuiltinRunner::RangeCheck(
1187            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true),
1188        );
1189        let mut vm = vm!();
1190        vm.current_step = 8;
1191        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(1));
1192    }
1193
1194    #[test]
1195    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1196    fn get_allocated_memory_units_hash() {
1197        let builtin = BuiltinRunner::Hash(HashBuiltinRunner::new(Some(1), true));
1198        let mut vm = vm!();
1199        vm.current_step = 1;
1200        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(3));
1201    }
1202
1203    #[test]
1204    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1205    fn get_allocated_memory_units_bitwise() {
1206        let builtin = BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(256), true));
1207        let mut vm = vm!();
1208        vm.current_step = 256;
1209        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(5));
1210    }
1211
1212    #[test]
1213    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1214    fn get_allocated_memory_units_ec_op() {
1215        let builtin = BuiltinRunner::EcOp(EcOpBuiltinRunner::new(Some(256), true));
1216        let mut vm = vm!();
1217        vm.current_step = 256;
1218        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(7));
1219    }
1220
1221    #[test]
1222    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1223    fn get_allocated_memory_units_keccak() {
1224        let builtin = BuiltinRunner::Keccak(KeccakBuiltinRunner::new(Some(2048), true));
1225        let mut vm = vm!();
1226        vm.current_step = 32768;
1227        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(256));
1228    }
1229
1230    #[test]
1231    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1232    fn get_allocated_memory_units_zero_ratio() {
1233        let builtin = BuiltinRunner::Keccak(KeccakBuiltinRunner::new(Some(0), true));
1234        let vm = vm!();
1235        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(0));
1236    }
1237
1238    #[test]
1239    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1240    fn get_allocated_memory_units_none_ratio() {
1241        let mut builtin = BuiltinRunner::Keccak(KeccakBuiltinRunner::new(None, true));
1242        let mut vm = vm!();
1243
1244        builtin.initialize_segments(&mut vm.segments);
1245        vm.compute_segments_effective_sizes();
1246
1247        assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(0));
1248    }
1249
1250    #[test]
1251    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1252    fn get_range_check_usage_range_check() {
1253        let builtin = BuiltinRunner::RangeCheck(
1254            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true),
1255        );
1256        let memory = memory![((0, 0), 1), ((0, 1), 2), ((0, 2), 3), ((0, 3), 4)];
1257        assert_eq!(builtin.get_range_check_usage(&memory), Some((0, 4)));
1258    }
1259
1260    #[test]
1261    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1262    fn get_range_check_usage_output() {
1263        let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
1264        let memory = memory![((0, 0), 1), ((0, 1), 2), ((0, 2), 3), ((0, 3), 4)];
1265        assert_eq!(builtin.get_range_check_usage(&memory), None);
1266    }
1267
1268    #[test]
1269    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1270    fn get_range_check_usage_hash() {
1271        let builtin = BuiltinRunner::Hash(HashBuiltinRunner::new(Some(256), true));
1272        let memory = memory![((0, 0), 1), ((0, 1), 2), ((0, 2), 3), ((0, 3), 4)];
1273        assert_eq!(builtin.get_range_check_usage(&memory), None);
1274    }
1275
1276    #[test]
1277    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1278    fn get_range_check_usage_ec_op() {
1279        let builtin = BuiltinRunner::EcOp(EcOpBuiltinRunner::new(Some(256), true));
1280        let memory = memory![((0, 0), 1), ((0, 1), 2), ((0, 2), 3), ((0, 3), 4)];
1281        assert_eq!(builtin.get_range_check_usage(&memory), None);
1282    }
1283
1284    #[test]
1285    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1286    fn get_range_check_usage_bitwise() {
1287        let builtin = BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(256), true));
1288        let memory = memory![((0, 0), 1), ((0, 1), 2), ((0, 2), 3), ((0, 3), 4)];
1289        assert_eq!(builtin.get_range_check_usage(&memory), None);
1290    }
1291
1292    #[test]
1293    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1294    fn get_used_diluted_check_units_bitwise() {
1295        let builtin = BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(256), true));
1296        assert_eq!(builtin.get_used_diluted_check_units(270, 7), 1255);
1297    }
1298
1299    #[test]
1300    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1301    fn get_used_diluted_check_units_keccak_zero_case() {
1302        let builtin = BuiltinRunner::Keccak(KeccakBuiltinRunner::new(Some(2048), true));
1303        assert_eq!(builtin.get_used_diluted_check_units(270, 7), 0);
1304    }
1305
1306    #[test]
1307    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1308    fn get_used_diluted_check_units_keccak_non_zero_case() {
1309        let builtin = BuiltinRunner::Keccak(KeccakBuiltinRunner::new(Some(2048), true));
1310        assert_eq!(builtin.get_used_diluted_check_units(0, 8), 32768);
1311    }
1312
1313    #[test]
1314    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1315    fn get_used_diluted_check_units_ec_op() {
1316        let builtin = BuiltinRunner::EcOp(EcOpBuiltinRunner::new(Some(10), true));
1317        assert_eq!(builtin.get_used_diluted_check_units(270, 7), 0);
1318    }
1319
1320    #[test]
1321    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1322    fn get_used_diluted_check_units_hash() {
1323        let builtin = BuiltinRunner::Hash(HashBuiltinRunner::new(Some(1), true));
1324        assert_eq!(builtin.get_used_diluted_check_units(270, 7), 0);
1325    }
1326
1327    #[test]
1328    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1329    fn get_used_diluted_check_units_range_check() {
1330        let builtin = BuiltinRunner::RangeCheck(
1331            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true),
1332        );
1333        assert_eq!(builtin.get_used_diluted_check_units(270, 7), 0);
1334    }
1335
1336    #[test]
1337    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1338    fn get_used_diluted_check_units_output() {
1339        let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
1340        assert_eq!(builtin.get_used_diluted_check_units(270, 7), 0);
1341    }
1342
1343    #[test]
1344    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1345    fn get_memory_segment_addresses_test() {
1346        let bitwise_builtin: BuiltinRunner = BitwiseBuiltinRunner::new(Some(256), true).into();
1347        assert_eq!(bitwise_builtin.get_memory_segment_addresses(), (0, None),);
1348        let ec_op_builtin: BuiltinRunner = EcOpBuiltinRunner::new(Some(256), true).into();
1349        assert_eq!(ec_op_builtin.get_memory_segment_addresses(), (0, None),);
1350        let hash_builtin: BuiltinRunner = HashBuiltinRunner::new(Some(8), true).into();
1351        assert_eq!(hash_builtin.get_memory_segment_addresses(), (0, None),);
1352        let output_builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
1353        assert_eq!(output_builtin.get_memory_segment_addresses(), (0, None),);
1354        let range_check_builtin: BuiltinRunner = BuiltinRunner::RangeCheck(
1355            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true),
1356        );
1357        assert_eq!(
1358            range_check_builtin.get_memory_segment_addresses(),
1359            (0, None),
1360        );
1361    }
1362
1363    #[test]
1364    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1365    fn run_security_checks_for_output() {
1366        let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
1367        let vm = vm!();
1368
1369        assert_matches!(builtin.run_security_checks(&vm), Ok(()));
1370    }
1371
1372    #[test]
1373    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1374    fn run_security_checks_empty_memory() {
1375        let builtin = BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(256), true));
1376        let vm = vm!();
1377        // Unused builtin shouldn't fail security checks
1378        assert_matches!(builtin.run_security_checks(&vm), Ok(()));
1379    }
1380
1381    #[test]
1382    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1383    fn run_security_checks_empty_offsets() {
1384        let builtin = BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(256), true));
1385        let mut vm = vm!();
1386
1387        vm.segments.memory.data = vec![vec![]];
1388
1389        assert_matches!(builtin.run_security_checks(&vm), Ok(()));
1390    }
1391
1392    #[test]
1393    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1394    fn run_security_checks_bitwise_missing_memory_cells_with_offsets() {
1395        let builtin = BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(256), true));
1396        let mut vm = vm!();
1397        vm.segments.memory = memory![
1398            ((0, 1), (0, 1)),
1399            ((0, 2), (0, 2)),
1400            ((0, 3), (0, 3)),
1401            ((0, 4), (0, 4))
1402        ];
1403
1404        assert_matches!(
1405            builtin.run_security_checks(&vm),
1406            Err(VirtualMachineError::Memory(
1407                MemoryError::MissingMemoryCellsWithOffsets(bx)
1408            )) if *bx == (BuiltinName::bitwise, vec![0])
1409        );
1410    }
1411
1412    #[test]
1413    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1414    fn run_security_checks_bitwise_missing_memory_cells() {
1415        let bitwise_builtin = BitwiseBuiltinRunner::new(Some(256), true);
1416
1417        let builtin: BuiltinRunner = bitwise_builtin.into();
1418
1419        let mut vm = vm!();
1420
1421        vm.segments.memory = memory![((0, 4), (0, 5))];
1422
1423        assert_matches!(
1424            builtin.run_security_checks(&vm),
1425            Err(VirtualMachineError::Memory(
1426                MemoryError::MissingMemoryCells(bx)
1427            )) if *bx == BuiltinName::bitwise
1428        );
1429    }
1430
1431    #[test]
1432    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1433    fn run_security_checks_hash_missing_memory_cells_with_offsets() {
1434        let builtin: BuiltinRunner = HashBuiltinRunner::new(Some(8), true).into();
1435        let mut vm = vm!();
1436
1437        vm.segments.memory = memory![
1438            ((0, 1), (0, 1)),
1439            ((0, 2), (0, 2)),
1440            ((0, 3), (0, 3)),
1441            ((0, 4), (0, 4)),
1442            ((0, 5), (0, 5))
1443        ];
1444        assert_matches!(
1445            builtin.run_security_checks(&vm),
1446            Err(VirtualMachineError::Memory(
1447                MemoryError::MissingMemoryCellsWithOffsets(bx)
1448            )) if *bx == (BuiltinName::pedersen, vec![0])
1449        );
1450    }
1451
1452    #[test]
1453    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1454    fn run_security_checks_hash_missing_memory_cells() {
1455        let hash_builtin = HashBuiltinRunner::new(Some(8), true);
1456
1457        let builtin: BuiltinRunner = hash_builtin.into();
1458
1459        let mut vm = vm!();
1460
1461        vm.segments.memory = memory![((0, 0), (0, 0))];
1462
1463        assert_matches!(
1464            builtin.run_security_checks(&vm),
1465            Err(VirtualMachineError::Memory(
1466                MemoryError::MissingMemoryCells(bx)
1467            )) if *bx == BuiltinName::pedersen
1468        );
1469    }
1470
1471    #[test]
1472    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1473    fn run_security_checks_range_check_missing_memory_cells_with_offsets() {
1474        let range_check_builtin =
1475            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
1476        let builtin: BuiltinRunner = range_check_builtin.into();
1477        let mut vm = vm!();
1478
1479        vm.segments.memory = memory![
1480            ((0, 1), 100),
1481            ((0, 2), 2),
1482            ((0, 3), 3),
1483            ((0, 5), 5),
1484            ((0, 6), 17),
1485            ((0, 7), 22)
1486        ];
1487
1488        assert_matches!(
1489            builtin.run_security_checks(&vm),
1490            Err(VirtualMachineError::Memory(
1491                MemoryError::MissingMemoryCells(bx)
1492            )) if *bx == BuiltinName::range_check
1493        );
1494    }
1495
1496    #[test]
1497    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1498    fn run_security_checks_range_check_missing_memory_cells() {
1499        let builtin: BuiltinRunner = BuiltinRunner::RangeCheck(RangeCheckBuiltinRunner::<
1500            RC_N_PARTS_STANDARD,
1501        >::new(Some(8), true));
1502        let mut vm = vm!();
1503
1504        vm.segments.memory = memory![((0, 1), 1)];
1505
1506        assert_matches!(
1507            builtin.run_security_checks(&vm),
1508            Err(VirtualMachineError::Memory(
1509                MemoryError::MissingMemoryCells(bx)
1510            )) if *bx == BuiltinName::range_check
1511        );
1512    }
1513
1514    #[test]
1515    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1516    fn run_security_checks_range_check_empty() {
1517        let range_check_builtin =
1518            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
1519
1520        let builtin: BuiltinRunner = range_check_builtin.into();
1521
1522        let mut vm = vm!();
1523
1524        vm.segments.memory.data = vec![vec![MemoryCell::NONE, MemoryCell::NONE, MemoryCell::NONE]];
1525
1526        assert_matches!(builtin.run_security_checks(&vm), Ok(()));
1527    }
1528
1529    #[test]
1530    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1531    fn run_security_checks_validate_auto_deductions() {
1532        let builtin: BuiltinRunner = BitwiseBuiltinRunner::new(Some(256), true).into();
1533
1534        let mut vm = vm!();
1535        vm.segments
1536            .memory
1537            .validated_addresses
1538            .extend(&[relocatable!(0, 2)]);
1539
1540        vm.segments.memory = memory![
1541            ((0, 0), (0, 0)),
1542            ((0, 1), (0, 1)),
1543            ((0, 2), (0, 2)),
1544            ((0, 3), (0, 3)),
1545            ((0, 4), (0, 4))
1546        ];
1547
1548        assert_matches!(builtin.run_security_checks(&vm), Ok(()));
1549    }
1550
1551    #[test]
1552    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1553    fn run_security_ec_op_check_memory_empty() {
1554        let ec_op_builtin = EcOpBuiltinRunner::new(Some(256), true);
1555
1556        let builtin: BuiltinRunner = ec_op_builtin.into();
1557
1558        let mut vm = vm!();
1559        // The values stored in memory are not relevant for this test
1560        vm.segments.memory.data = vec![vec![]];
1561
1562        assert_matches!(builtin.run_security_checks(&vm), Ok(()));
1563    }
1564
1565    #[test]
1566    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1567    fn run_security_ec_op_check_memory_1_element() {
1568        let ec_op_builtin = EcOpBuiltinRunner::new(Some(256), true);
1569
1570        let builtin: BuiltinRunner = ec_op_builtin.into();
1571
1572        let mut vm = vm!();
1573        // The values stored in memory are not relevant for this test
1574        vm.segments.memory = memory![((0, 0), 0)];
1575        assert_matches!(
1576            builtin.run_security_checks(&vm),
1577            Err(VirtualMachineError::Memory(
1578                MemoryError::MissingMemoryCells(bx)
1579            )) if *bx == BuiltinName::ec_op
1580        );
1581    }
1582
1583    #[test]
1584    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1585    fn run_security_ec_op_check_memory_3_elements() {
1586        let ec_op_builtin = EcOpBuiltinRunner::new(Some(256), true);
1587
1588        let builtin: BuiltinRunner = ec_op_builtin.into();
1589
1590        let mut vm = vm!();
1591        // The values stored in memory are not relevant for this test
1592        vm.segments.memory = memory![((0, 0), 0), ((0, 1), 0), ((0, 2), 0)];
1593
1594        assert_matches!(
1595            builtin.run_security_checks(&vm),
1596            Err(VirtualMachineError::Memory(
1597                MemoryError::MissingMemoryCells(bx)
1598            )) if *bx == BuiltinName::ec_op
1599        );
1600    }
1601
1602    #[test]
1603    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1604    fn run_security_ec_op_missing_memory_cells_with_offsets() {
1605        let builtin: BuiltinRunner = EcOpBuiltinRunner::new(Some(256), true).into();
1606        let mut vm = vm!();
1607        vm.segments.memory = memory![
1608            ((0, 1), (0, 1)),
1609            ((0, 2), (0, 2)),
1610            ((0, 3), (0, 3)),
1611            ((0, 4), (0, 4)),
1612            ((0, 5), (0, 5)),
1613            ((0, 6), (0, 6))
1614        ];
1615
1616        assert_matches!(
1617            builtin.run_security_checks(&vm),
1618            Err(VirtualMachineError::Memory(
1619                MemoryError::MissingMemoryCellsWithOffsets(bx)
1620            )) if *bx == (BuiltinName::ec_op, vec![0])
1621        );
1622    }
1623
1624    #[test]
1625    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1626    fn run_security_ec_op_check_memory_gap() {
1627        let ec_op_builtin = EcOpBuiltinRunner::new(Some(256), true);
1628
1629        let builtin: BuiltinRunner = ec_op_builtin.into();
1630
1631        let mut vm = vm!();
1632        // The values stored in memory are not relevant for this test
1633        vm.segments.memory = memory![
1634            ((0, 0), 0),
1635            ((0, 1), 1),
1636            ((0, 2), 2),
1637            ((0, 3), 3),
1638            ((0, 4), 4),
1639            ((0, 5), 5),
1640            ((0, 6), 6),
1641            ((0, 8), 8),
1642            ((0, 9), 9),
1643            ((0, 10), 10),
1644            ((0, 11), 11)
1645        ];
1646
1647        assert_matches!(
1648            builtin.run_security_checks(&vm),
1649            Err(VirtualMachineError::Memory(
1650                MemoryError::MissingMemoryCellsWithOffsets(bx)
1651            )) if *bx == (BuiltinName::ec_op, vec![7])
1652        );
1653    }
1654
1655    /// Test that get_used_perm_range_check_units() returns zero when the
1656    /// builtin is a BitwiseBuiltinRunner.
1657    #[test]
1658    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1659    fn get_used_perm_range_check_units_bitwise() {
1660        let builtin_runner: BuiltinRunner = BitwiseBuiltinRunner::new(Some(256), true).into();
1661        let mut vm = vm!();
1662
1663        vm.current_step = 8;
1664        vm.segments.segment_used_sizes = Some(vec![5]);
1665        assert_eq!(builtin_runner.get_used_perm_range_check_units(&vm), Ok(0));
1666    }
1667
1668    /// Test that get_used_perm_range_check_units() returns zero when the
1669    /// builtin is an EcOpBuiltinRunner.
1670    #[test]
1671    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1672    fn get_used_perm_range_check_units_ec_op() {
1673        let builtin_runner: BuiltinRunner = EcOpBuiltinRunner::new(Some(256), true).into();
1674        let mut vm = vm!();
1675
1676        vm.current_step = 8;
1677        vm.segments.segment_used_sizes = Some(vec![5]);
1678        assert_eq!(builtin_runner.get_used_perm_range_check_units(&vm), Ok(0));
1679    }
1680
1681    /// Test that get_used_perm_range_check_units() returns zero when the
1682    /// builtin is a HashBuiltinRunner.
1683    #[test]
1684    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1685    fn get_used_perm_range_check_units_hash() {
1686        let builtin_runner: BuiltinRunner = HashBuiltinRunner::new(Some(8), true).into();
1687        let mut vm = vm!();
1688
1689        vm.current_step = 8;
1690        vm.segments.segment_used_sizes = Some(vec![5]);
1691        assert_eq!(builtin_runner.get_used_perm_range_check_units(&vm), Ok(0));
1692    }
1693
1694    /// Test that get_used_perm_range_check_units() returns zero when the
1695    /// builtin is an OutputBuiltinRunner.
1696    #[test]
1697    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1698    fn get_used_perm_range_check_units_output() {
1699        let builtin_runner: BuiltinRunner = OutputBuiltinRunner::new(true).into();
1700        let mut vm = vm!();
1701
1702        vm.current_step = 8;
1703        vm.segments.segment_used_sizes = Some(vec![5]);
1704        assert_eq!(builtin_runner.get_used_perm_range_check_units(&vm), Ok(0));
1705    }
1706
1707    /// Test that get_used_perm_range_check_units() calls the corresponding
1708    /// method when the builtin is a RangeCheckBuiltinRunner.
1709    #[test]
1710    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1711    fn get_used_perm_range_check_units_range_check() {
1712        let builtin_runner: BuiltinRunner =
1713            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true).into();
1714        let mut vm = vm!();
1715
1716        vm.current_step = 8;
1717        vm.segments.segment_used_sizes = Some(vec![1]);
1718        assert_eq!(builtin_runner.get_used_perm_range_check_units(&vm), Ok(8));
1719    }
1720
1721    #[test]
1722    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1723    fn get_ratio_tests() {
1724        let bitwise_builtin: BuiltinRunner = BitwiseBuiltinRunner::new(Some(256), true).into();
1725        assert_eq!(bitwise_builtin.ratio(), (Some(256)),);
1726        let ec_op_builtin: BuiltinRunner = EcOpBuiltinRunner::new(Some(256), true).into();
1727        assert_eq!(ec_op_builtin.ratio(), (Some(256)),);
1728        let hash_builtin: BuiltinRunner = HashBuiltinRunner::new(Some(8), true).into();
1729        assert_eq!(hash_builtin.ratio(), (Some(8)),);
1730        let output_builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
1731        assert_eq!(output_builtin.ratio(), None,);
1732        let range_check_builtin: BuiltinRunner = BuiltinRunner::RangeCheck(
1733            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true),
1734        );
1735        assert_eq!(range_check_builtin.ratio(), (Some(8)),);
1736        let keccak_builtin: BuiltinRunner = KeccakBuiltinRunner::new(Some(2048), true).into();
1737        assert_eq!(keccak_builtin.ratio(), (Some(2048)),);
1738    }
1739
1740    #[test]
1741    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1742    fn get_ratio_den_tests() {
1743        let rangecheck_builtin: BuiltinRunner =
1744            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new_with_low_ratio(
1745                Some(LowRatio::new(1, 2)),
1746                true,
1747            )
1748            .into();
1749        assert_eq!(rangecheck_builtin.ratio_den(), (Some(2)),);
1750
1751        let rangecheck96_builtin: BuiltinRunner =
1752            RangeCheckBuiltinRunner::<RC_N_PARTS_96>::new_with_low_ratio(
1753                Some(LowRatio::new(1, 4)),
1754                true,
1755            )
1756            .into();
1757        assert_eq!(rangecheck96_builtin.ratio_den(), (Some(4)),);
1758
1759        let mod_builtin: BuiltinRunner =
1760            ModBuiltinRunner::new_add_mod(&ModInstanceDef::new(Some(5), 3, 3), true).into();
1761        assert_eq!(mod_builtin.ratio_den(), (Some(1)),);
1762    }
1763
1764    #[test]
1765    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1766    fn bitwise_get_used_instances_test() {
1767        let mut vm = vm!();
1768        vm.segments.segment_used_sizes = Some(vec![4]);
1769
1770        let bitwise_builtin: BuiltinRunner = BitwiseBuiltinRunner::new(Some(256), true).into();
1771        assert_eq!(bitwise_builtin.get_used_instances(&vm.segments), Ok(1));
1772    }
1773
1774    #[test]
1775    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1776    fn ec_op_get_used_instances_test() {
1777        let mut vm = vm!();
1778        vm.segments.segment_used_sizes = Some(vec![4]);
1779
1780        let ec_op_builtin: BuiltinRunner = EcOpBuiltinRunner::new(Some(256), true).into();
1781        assert_eq!(ec_op_builtin.get_used_instances(&vm.segments), Ok(1));
1782    }
1783
1784    #[test]
1785    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1786    fn hash_get_used_instances_test() {
1787        let mut vm = vm!();
1788        vm.segments.segment_used_sizes = Some(vec![4]);
1789
1790        let hash_builtin: BuiltinRunner = HashBuiltinRunner::new(Some(8), true).into();
1791        assert_eq!(hash_builtin.get_used_instances(&vm.segments), Ok(2));
1792    }
1793
1794    #[test]
1795    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1796    fn output_get_used_instances_test() {
1797        let mut vm = vm!();
1798        vm.segments.segment_used_sizes = Some(vec![4]);
1799
1800        let output_builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
1801        assert_eq!(output_builtin.get_used_instances(&vm.segments), Ok(4));
1802    }
1803    #[test]
1804    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1805    fn range_check_get_used_instances_test() {
1806        let mut vm = vm!();
1807        vm.segments.segment_used_sizes = Some(vec![4]);
1808
1809        let range_check_builtin: BuiltinRunner = BuiltinRunner::RangeCheck(
1810            RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true),
1811        );
1812        assert_eq!(range_check_builtin.get_used_instances(&vm.segments), Ok(4));
1813    }
1814
1815    #[test]
1816    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1817    fn runners_final_stack() {
1818        let mut builtins = vec![
1819            BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(256), false)),
1820            BuiltinRunner::EcOp(EcOpBuiltinRunner::new(Some(256), false)),
1821            BuiltinRunner::Hash(HashBuiltinRunner::new(Some(1), false)),
1822            BuiltinRunner::Output(OutputBuiltinRunner::new(false)),
1823            BuiltinRunner::RangeCheck(RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(
1824                Some(8),
1825                false,
1826            )),
1827            BuiltinRunner::Keccak(KeccakBuiltinRunner::new(Some(2048), false)),
1828            BuiltinRunner::Signature(SignatureBuiltinRunner::new(Some(512), false)),
1829        ];
1830        let vm = vm!();
1831
1832        for br in builtins.iter_mut() {
1833            assert_eq!(br.final_stack(&vm.segments, vm.get_ap()), Ok(vm.get_ap()));
1834        }
1835    }
1836
1837    #[test]
1838    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1839    fn runners_set_stop_ptr() {
1840        let builtins = vec![
1841            BuiltinRunner::Bitwise(BitwiseBuiltinRunner::new(Some(256), false)),
1842            BuiltinRunner::EcOp(EcOpBuiltinRunner::new(Some(256), false)),
1843            BuiltinRunner::Hash(HashBuiltinRunner::new(Some(1), false)),
1844            BuiltinRunner::Output(OutputBuiltinRunner::new(false)),
1845            BuiltinRunner::RangeCheck(RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(
1846                Some(8),
1847                false,
1848            )),
1849            BuiltinRunner::Keccak(KeccakBuiltinRunner::new(Some(2048), false)),
1850            BuiltinRunner::Signature(SignatureBuiltinRunner::new(Some(512), false)),
1851            BuiltinRunner::Poseidon(PoseidonBuiltinRunner::new(Some(32), false)),
1852            BuiltinRunner::SegmentArena(SegmentArenaBuiltinRunner::new(false)),
1853        ];
1854
1855        let ptr = 3;
1856
1857        for mut br in builtins {
1858            br.set_stop_ptr(ptr);
1859            let (_, stop_ptr) = br.get_memory_segment_addresses();
1860            assert_eq!(stop_ptr, Some(ptr));
1861        }
1862    }
1863
1864    #[test]
1865    fn get_additonal_data_none() {
1866        let builtin: BuiltinRunner = PoseidonBuiltinRunner::new(None, true).into();
1867        assert_eq!(builtin.get_additional_data(), BuiltinAdditionalData::None)
1868    }
1869}