cairo_vm/vm/runners/builtin_runner/
mod.rs

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

cairo_vm/vm/runners/builtin_runner/
mod.rs
