cairo_vm/vm/runners/builtin_runner/
modulo.rs

1use crate::{
2    air_private_input::{ModInput, ModInputInstance, ModInputMemoryVars, PrivateInput},
3    math_utils::{div_mod_unsigned, safe_div_usize},
4    stdlib::{
5        borrow::Cow,
6        collections::BTreeMap,
7        prelude::{Box, Vec},
8    },
9    types::{
10        builtin_name::BuiltinName,
11        errors::math_errors::MathError,
12        instance_definitions::mod_instance_def::{ModInstanceDef, CELLS_PER_MOD, N_WORDS},
13        relocatable::{relocate_address, MaybeRelocatable, Relocatable},
14    },
15    vm::{
16        errors::{
17            memory_errors::MemoryError, runner_errors::RunnerError, vm_errors::VirtualMachineError,
18        },
19        vm_core::VirtualMachine,
20        vm_memory::{memory::Memory, memory_segments::MemorySegmentManager},
21    },
22    Felt252,
23};
24use core::ops::Shl;
25use num_bigint::BigUint;
26use num_integer::div_ceil;
27use num_integer::Integer;
28use num_traits::One;
29use num_traits::Zero;
30
31//The maximum n value that the function fill_memory accepts.
32const FILL_MEMORY_MAX: usize = 100000;
33
34const VALUES_PTR_OFFSET: u32 = 4;
35const OFFSETS_PTR_OFFSET: u32 = 5;
36const N_OFFSET: u32 = 6;
37
38#[derive(Debug, Clone)]
39pub struct ModBuiltinRunner {
40    builtin_type: ModBuiltinType,
41    base: usize,
42    pub(crate) stop_ptr: Option<usize>,
43    instance_def: ModInstanceDef,
44    pub(crate) included: bool,
45    zero_segment_index: usize,
46    zero_segment_size: usize,
47    // Precomputed powers used for reading and writing values that are represented as n_words words of word_bit_len bits each.
48    shift: BigUint,
49    shift_powers: [BigUint; N_WORDS],
50    k_bound: BigUint,
51}
52
53#[derive(Debug, Clone)]
54pub enum ModBuiltinType {
55    Mul,
56    Add,
57}
58
59impl ModBuiltinType {
60    pub(crate) fn operation_string(&self) -> &'static str {
61        match self {
62            ModBuiltinType::Mul => "*",
63            ModBuiltinType::Add => "+",
64        }
65    }
66}
67
68#[derive(Debug, Default)]
69struct Inputs {
70    p: BigUint,
71    p_values: [Felt252; N_WORDS],
72    values_ptr: Relocatable,
73    offsets_ptr: Relocatable,
74    n: usize,
75}
76
77impl ModBuiltinRunner {
78    pub(crate) fn new_add_mod(instance_def: &ModInstanceDef, included: bool) -> Self {
79        Self::new(
80            instance_def.clone(),
81            included,
82            ModBuiltinType::Add,
83            Some(2u32.into()),
84        )
85    }
86
87    pub(crate) fn new_mul_mod(instance_def: &ModInstanceDef, included: bool) -> Self {
88        Self::new(instance_def.clone(), included, ModBuiltinType::Mul, None)
89    }
90
91    fn new(
92        instance_def: ModInstanceDef,
93        included: bool,
94        builtin_type: ModBuiltinType,
95        k_bound: Option<BigUint>,
96    ) -> Self {
97        let shift = BigUint::one().shl(instance_def.word_bit_len);
98        let shift_powers = core::array::from_fn(|i| shift.pow(i as u32));
99        let zero_segment_size = core::cmp::max(N_WORDS, instance_def.batch_size * 3);
100        let int_lim = BigUint::from(2_u32).pow(N_WORDS as u32 * instance_def.word_bit_len);
101        Self {
102            builtin_type,
103            base: 0,
104            stop_ptr: None,
105            instance_def,
106            included,
107            zero_segment_index: 0,
108            zero_segment_size,
109            shift,
110            shift_powers,
111            k_bound: k_bound.unwrap_or(int_lim),
112        }
113    }
114
115    pub fn name(&self) -> BuiltinName {
116        match self.builtin_type {
117            ModBuiltinType::Mul => BuiltinName::mul_mod,
118            ModBuiltinType::Add => BuiltinName::add_mod,
119        }
120    }
121
122    pub fn initialize_segments(&mut self, segments: &mut MemorySegmentManager) {
123        self.base = segments.add().segment_index as usize; // segments.add() always returns a positive index
124    }
125
126    pub fn initialize_zero_segment(&mut self, segments: &mut MemorySegmentManager) {
127        self.zero_segment_index = segments.add_zero_segment(self.zero_segment_size);
128    }
129
130    pub fn initial_stack(&self) -> Vec<MaybeRelocatable> {
131        if self.included {
132            vec![MaybeRelocatable::from((self.base as isize, 0))]
133        } else {
134            vec![]
135        }
136    }
137
138    pub fn base(&self) -> usize {
139        self.base
140    }
141
142    pub fn ratio(&self) -> Option<u32> {
143        self.instance_def.ratio.map(|ratio| ratio.numerator)
144    }
145
146    pub fn ratio_den(&self) -> Option<u32> {
147        self.instance_def.ratio.map(|ratio| ratio.denominator)
148    }
149
150    pub fn batch_size(&self) -> usize {
151        self.instance_def.batch_size
152    }
153
154    pub fn get_used_cells(&self, segments: &MemorySegmentManager) -> Result<usize, MemoryError> {
155        segments
156            .get_segment_used_size(self.base)
157            .ok_or(MemoryError::MissingSegmentUsedSizes)
158    }
159
160    pub fn get_used_instances(
161        &self,
162        segments: &MemorySegmentManager,
163    ) -> Result<usize, MemoryError> {
164        let used_cells = self.get_used_cells(segments)?;
165        Ok(div_ceil(used_cells, CELLS_PER_MOD as usize))
166    }
167
168    pub(crate) fn air_private_input(&self, segments: &MemorySegmentManager) -> Vec<PrivateInput> {
169        let segment_index = self.base as isize;
170        let segment_size = segments
171            .get_segment_used_size(self.base)
172            .unwrap_or_default();
173        let relocation_table = segments.relocate_segments().unwrap_or_default();
174        let mut instances = Vec::<ModInputInstance>::new();
175        for instance in 0..segment_size
176            .checked_div(CELLS_PER_MOD as usize)
177            .unwrap_or_default()
178        {
179            let instance_addr_offset = instance * CELLS_PER_MOD as usize;
180            let values_ptr = segments
181                .memory
182                .get_relocatable(
183                    (
184                        segment_index,
185                        instance_addr_offset + VALUES_PTR_OFFSET as usize,
186                    )
187                        .into(),
188                )
189                .unwrap_or_default();
190            let offsets_ptr = segments
191                .memory
192                .get_relocatable(
193                    (
194                        segment_index,
195                        instance_addr_offset + OFFSETS_PTR_OFFSET as usize,
196                    )
197                        .into(),
198                )
199                .unwrap_or_default();
200            let n = segments
201                .memory
202                .get_usize((segment_index, instance_addr_offset + N_OFFSET as usize).into())
203                .unwrap_or_default();
204            let p_values: [Felt252; N_WORDS] = core::array::from_fn(|i| {
205                segments
206                    .memory
207                    .get_integer((segment_index, instance_addr_offset + i).into())
208                    .unwrap_or_default()
209                    .into_owned()
210            });
211            let mut batch = BTreeMap::<usize, ModInputMemoryVars>::new();
212            let fetch_offset_and_words = |var_index: usize,
213                                          index_in_batch: usize|
214             -> (usize, [Felt252; N_WORDS]) {
215                let offset = segments
216                    .memory
217                    .get_usize((offsets_ptr + (3 * index_in_batch + var_index)).unwrap_or_default())
218                    .unwrap_or_default();
219                let words: [Felt252; N_WORDS] = core::array::from_fn(|i| {
220                    segments
221                        .memory
222                        .get_integer((values_ptr + (offset + i)).unwrap_or_default())
223                        .unwrap_or_default()
224                        .into_owned()
225                });
226                (offset, words)
227            };
228            for index_in_batch in 0..self.batch_size() {
229                let (a_offset, a_values) = fetch_offset_and_words(0, index_in_batch);
230                let (b_offset, b_values) = fetch_offset_and_words(1, index_in_batch);
231                let (c_offset, c_values) = fetch_offset_and_words(2, index_in_batch);
232                batch.insert(
233                    index_in_batch,
234                    ModInputMemoryVars {
235                        a_offset,
236                        b_offset,
237                        c_offset,
238                        a0: a_values[0],
239                        a1: a_values[1],
240                        a2: a_values[2],
241                        a3: a_values[3],
242                        b0: b_values[0],
243                        b1: b_values[1],
244                        b2: b_values[2],
245                        b3: b_values[3],
246                        c0: c_values[0],
247                        c1: c_values[1],
248                        c2: c_values[2],
249                        c3: c_values[3],
250                    },
251                );
252            }
253            instances.push(ModInputInstance {
254                index: instance,
255                p0: p_values[0],
256                p1: p_values[1],
257                p2: p_values[2],
258                p3: p_values[3],
259                values_ptr: relocate_address(values_ptr, &relocation_table).unwrap_or_default(),
260                offsets_ptr: relocate_address(offsets_ptr, &relocation_table).unwrap_or_default(),
261                n,
262                batch,
263            });
264        }
265
266        instances.sort_by_key(|input| input.index);
267
268        vec![PrivateInput::Mod(ModInput {
269            instances,
270            zero_value_address: relocation_table
271                .get(self.zero_segment_index)
272                .cloned()
273                .unwrap_or_default(),
274        })]
275    }
276
277    // Reads N_WORDS from memory, starting at address=addr.
278    // Returns the words and the value if all words are in memory.
279    // Verifies that all words are integers and are bounded by 2**self.instance_def.word_bit_len.
280    fn read_n_words_value(
281        &self,
282        memory: &Memory,
283        addr: Relocatable,
284    ) -> Result<([Felt252; N_WORDS], Option<BigUint>), RunnerError> {
285        let mut words = Default::default();
286        let mut value = BigUint::zero();
287        for i in 0..N_WORDS {
288            let addr_i = (addr + i)?;
289            match memory.get(&addr_i).map(Cow::into_owned) {
290                None => return Ok((words, None)),
291                Some(MaybeRelocatable::RelocatableValue(_)) => {
292                    return Err(MemoryError::ExpectedInteger(Box::new(addr_i)).into())
293                }
294                Some(MaybeRelocatable::Int(word)) => {
295                    let biguint_word = word.to_biguint();
296                    if biguint_word >= self.shift {
297                        return Err(RunnerError::WordExceedsModBuiltinWordBitLen(Box::new((
298                            addr_i,
299                            self.instance_def.word_bit_len,
300                            word,
301                        ))));
302                    }
303                    words[i] = word;
304                    value += biguint_word * &self.shift_powers[i];
305                }
306            }
307        }
308        Ok((words, Some(value)))
309    }
310
311    // Reads the inputs to the builtin (see Inputs) from the memory at address=addr.
312    // Returns a struct with the inputs. Asserts that it exists in memory.
313    // Returns also the value of p, not just its words.
314    fn read_inputs(&self, memory: &Memory, addr: Relocatable) -> Result<Inputs, RunnerError> {
315        let values_ptr = memory.get_relocatable((addr + VALUES_PTR_OFFSET)?)?;
316        let offsets_ptr = memory.get_relocatable((addr + OFFSETS_PTR_OFFSET)?)?;
317        let n = memory.get_usize((addr + N_OFFSET)?)?;
318        if n < 1 {
319            return Err(RunnerError::ModBuiltinNLessThanOne(Box::new((
320                self.name(),
321                n,
322            ))));
323        }
324        let (p_values, p) = self.read_n_words_value(memory, addr)?;
325        let p = p.ok_or_else(|| {
326            RunnerError::ModBuiltinMissingValue(Box::new((
327                self.name(),
328                (addr + N_WORDS).unwrap_or_default(),
329            )))
330        })?;
331        Ok(Inputs {
332            p,
333            p_values,
334            values_ptr,
335            offsets_ptr,
336            n,
337        })
338    }
339
340    // Reads the memory variables to the builtin (see MEMORY_VARS) from the memory given
341    // the inputs (specifically, values_ptr and offsets_ptr).
342    // Computes and returns the values of a, b, and c.
343    fn read_memory_vars(
344        &self,
345        memory: &Memory,
346        values_ptr: Relocatable,
347        offsets_ptr: Relocatable,
348        index_in_batch: usize,
349    ) -> Result<(BigUint, BigUint, BigUint), RunnerError> {
350        let compute_value = |index: usize| -> Result<BigUint, RunnerError> {
351            let offset = memory.get_usize((offsets_ptr + (index + 3 * index_in_batch))?)?;
352            let value_addr = (values_ptr + offset)?;
353            let (_, value) = self.read_n_words_value(memory, value_addr)?;
354            let value = value.ok_or_else(|| {
355                RunnerError::ModBuiltinMissingValue(Box::new((
356                    self.name(),
357                    (value_addr + N_WORDS).unwrap_or_default(),
358                )))
359            })?;
360            Ok(value)
361        };
362
363        let a = compute_value(0)?;
364        let b = compute_value(1)?;
365        let c = compute_value(2)?;
366        Ok((a, b, c))
367    }
368
369    fn fill_inputs(
370        &self,
371        memory: &mut Memory,
372        builtin_ptr: Relocatable,
373        inputs: &Inputs,
374    ) -> Result<(), RunnerError> {
375        if inputs.n > FILL_MEMORY_MAX {
376            return Err(RunnerError::FillMemoryMaxExceeded(Box::new((
377                self.name(),
378                FILL_MEMORY_MAX,
379            ))));
380        }
381        let n_instances = safe_div_usize(inputs.n, self.instance_def.batch_size)?;
382        for instance in 1..n_instances {
383            let instance_ptr = (builtin_ptr + instance * CELLS_PER_MOD as usize)?;
384            for i in 0..N_WORDS {
385                memory.insert_as_accessed((instance_ptr + i)?, &inputs.p_values[i])?;
386            }
387            memory.insert_as_accessed((instance_ptr + VALUES_PTR_OFFSET)?, &inputs.values_ptr)?;
388            memory.insert_as_accessed(
389                (instance_ptr + OFFSETS_PTR_OFFSET)?,
390                (inputs.offsets_ptr + (3 * instance * self.instance_def.batch_size))?,
391            )?;
392            memory.insert_as_accessed(
393                (instance_ptr + N_OFFSET)?,
394                inputs
395                    .n
396                    .saturating_sub(instance * self.instance_def.batch_size),
397            )?;
398        }
399        Ok(())
400    }
401
402    // Copies the first offsets in the offsets table to its end, n_copies times.
403    fn fill_offsets(
404        &self,
405        memory: &mut Memory,
406        offsets_ptr: Relocatable,
407        index: usize,
408        n_copies: usize,
409    ) -> Result<(), RunnerError> {
410        if n_copies.is_zero() {
411            return Ok(());
412        }
413        for i in 0..3_usize {
414            let addr = (offsets_ptr + i)?;
415            let offset = memory
416                .get(&((offsets_ptr + i)?))
417                .ok_or_else(|| MemoryError::UnknownMemoryCell(Box::new(addr)))?
418                .into_owned();
419            for copy_i in 0..n_copies {
420                memory.insert_as_accessed((offsets_ptr + (3 * (index + copy_i) + i))?, &offset)?;
421            }
422        }
423        Ok(())
424    }
425
426    // Given a value, writes its n_words to memory, starting at address=addr.
427    fn write_n_words_value(
428        &self,
429        memory: &mut Memory,
430        addr: Relocatable,
431        value: BigUint,
432    ) -> Result<(), RunnerError> {
433        let mut value = value;
434        for i in 0..N_WORDS {
435            let word = value.mod_floor(&self.shift);
436            memory.insert_as_accessed((addr + i)?, Felt252::from(word))?;
437            value = value.div_floor(&self.shift)
438        }
439        if !value.is_zero() {
440            return Err(RunnerError::WriteNWordsValueNotZero(self.name()));
441        }
442        Ok(())
443    }
444
445    // Fills a value in the values table, if exactly one value is missing.
446    // Returns true on success or if all values are already known.
447    //
448    // The builtin type (add or mul) determines which operation to perform
449    fn fill_value(
450        &self,
451        memory: &mut Memory,
452        inputs: &Inputs,
453        index: usize,
454    ) -> Result<bool, RunnerError> {
455        let mut addresses = Vec::new();
456        let mut values = Vec::new();
457        for i in 0..3 {
458            let addr = (inputs.values_ptr
459                + memory
460                    .get_integer((inputs.offsets_ptr + (3 * index + i))?)?
461                    .as_ref())?;
462            addresses.push(addr);
463            let (_, value) = self.read_n_words_value(memory, addr)?;
464            values.push(value)
465        }
466        let (a, b, c) = (&values[0], &values[1], &values[2]);
467        match (a, b, c) {
468            // Deduce c from a and b and write it to memory.
469            (Some(a), Some(b), None) => {
470                let value = self.apply_operation(a, b, &inputs.p)?;
471                self.write_n_words_value(memory, addresses[2], value)?;
472                Ok(true)
473            }
474            // Deduce b from a and c and write it to memory.
475            (Some(a), None, Some(c)) => {
476                let value = self.deduce_operand(a, c, &inputs.p)?;
477                self.write_n_words_value(memory, addresses[1], value)?;
478                Ok(true)
479            }
480            // Deduce a from b and c and write it to memory.
481            (None, Some(b), Some(c)) => {
482                let value = self.deduce_operand(b, c, &inputs.p)?;
483                self.write_n_words_value(memory, addresses[0], value)?;
484                Ok(true)
485            }
486            // All values are already known.
487            (Some(_), Some(_), Some(_)) => Ok(true),
488            _ => Ok(false),
489        }
490    }
491
492    /// NOTE: It is advisable to use VirtualMachine::mod_builtin_fill_memory instead of this method directly
493    /// when implementing hints to avoid cloning the runners
494
495    /// Fills the memory with inputs to the builtin instances based on the inputs to the
496    /// first instance, pads the offsets table to fit the number of operations writen in the
497    /// input to the first instance, and caculates missing values in the values table.
498
499    /// For each builtin, the given tuple is of the form (builtin_ptr, builtin_runner, n),
500    /// where n is the number of operations in the offsets table (i.e., the length of the
501    /// offsets table is 3*n).
502
503    /// The number of operations written to the input of the first instance n' should be at
504    /// least n and a multiple of batch_size. Previous offsets are copied to the end of the
505    /// offsets table to make its length 3n'.
506    pub fn fill_memory(
507        memory: &mut Memory,
508        add_mod: Option<(Relocatable, &ModBuiltinRunner, usize)>,
509        mul_mod: Option<(Relocatable, &ModBuiltinRunner, usize)>,
510    ) -> Result<(), RunnerError> {
511        if add_mod.is_none() && mul_mod.is_none() {
512            return Err(RunnerError::FillMemoryNoBuiltinSet);
513        }
514        // Check that the instance definitions of the builtins are the same.
515        if let (Some((_, add_mod, _)), Some((_, mul_mod, _))) = (add_mod, mul_mod) {
516            if add_mod.instance_def.word_bit_len != mul_mod.instance_def.word_bit_len {
517                return Err(RunnerError::ModBuiltinsMismatchedInstanceDef);
518            }
519        }
520        // Fill the inputs to the builtins.
521        let (add_mod_inputs, add_mod_n) =
522            if let Some((add_mod_addr, add_mod, add_mod_index)) = add_mod {
523                let add_mod_inputs = add_mod.read_inputs(memory, add_mod_addr)?;
524                add_mod.fill_inputs(memory, add_mod_addr, &add_mod_inputs)?;
525                add_mod.fill_offsets(
526                    memory,
527                    add_mod_inputs.offsets_ptr,
528                    add_mod_index,
529                    add_mod_inputs.n.saturating_sub(add_mod_index),
530                )?;
531                (add_mod_inputs, add_mod_index)
532            } else {
533                Default::default()
534            };
535
536        let (mul_mod_inputs, mul_mod_n) =
537            if let Some((mul_mod_addr, mul_mod, mul_mod_index)) = mul_mod {
538                let mul_mod_inputs = mul_mod.read_inputs(memory, mul_mod_addr)?;
539                mul_mod.fill_inputs(memory, mul_mod_addr, &mul_mod_inputs)?;
540                mul_mod.fill_offsets(
541                    memory,
542                    mul_mod_inputs.offsets_ptr,
543                    mul_mod_index,
544                    mul_mod_inputs.n.saturating_sub(mul_mod_index),
545                )?;
546                (mul_mod_inputs, mul_mod_index)
547            } else {
548                Default::default()
549            };
550
551        // Fill the values table.
552        let mut add_mod_index = 0;
553        let mut mul_mod_index = 0;
554
555        while add_mod_index < add_mod_n || mul_mod_index < mul_mod_n {
556            if add_mod_index < add_mod_n {
557                if let Some((_, add_mod_runner, _)) = add_mod {
558                    if add_mod_runner.fill_value(memory, &add_mod_inputs, add_mod_index)? {
559                        add_mod_index += 1;
560                        continue;
561                    }
562                }
563            }
564
565            if mul_mod_index < mul_mod_n {
566                if let Some((_, mul_mod_runner, _)) = mul_mod {
567                    if mul_mod_runner.fill_value(memory, &mul_mod_inputs, mul_mod_index)? {
568                        mul_mod_index += 1;
569                    }
570                    continue;
571                }
572            }
573
574            return Err(RunnerError::FillMemoryCoudNotFillTable(
575                add_mod_index,
576                mul_mod_index,
577            ));
578        }
579        Ok(())
580    }
581
582    // Additional checks added to the standard builtin runner security checks
583    pub(crate) fn run_additional_security_checks(
584        &self,
585        vm: &VirtualMachine,
586    ) -> Result<(), VirtualMachineError> {
587        let segment_size = vm
588            .get_segment_used_size(self.base)
589            .ok_or(MemoryError::MissingSegmentUsedSizes)?;
590        let n_instances = div_ceil(segment_size, CELLS_PER_MOD as usize);
591        let mut prev_inputs = Inputs::default();
592        for instance in 0..n_instances {
593            let inputs = self.read_inputs(
594                &vm.segments.memory,
595                (self.base as isize, instance * CELLS_PER_MOD as usize).into(),
596            )?;
597            if !instance.is_zero() && prev_inputs.n > self.instance_def.batch_size {
598                for i in 0..N_WORDS {
599                    if inputs.p_values[i] != prev_inputs.p_values[i] {
600                        return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((self.name(), format!("inputs.p_values[i] != prev_inputs.p_values[i]. Got: i={}, inputs.p_values[i]={}, prev_inputs.p_values[i]={}",
601                    i, inputs.p_values[i], prev_inputs.p_values[i])))).into());
602                    }
603                }
604                if inputs.values_ptr != prev_inputs.values_ptr {
605                    return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((self.name(), format!("inputs.values_ptr != prev_inputs.values_ptr. Got: inputs.values_ptr={}, prev_inputs.values_ptr={}",
606                inputs.values_ptr, prev_inputs.values_ptr)))).into());
607                }
608                if inputs.offsets_ptr
609                    != (prev_inputs.offsets_ptr + (3 * self.instance_def.batch_size))?
610                {
611                    return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((self.name(), format!("inputs.offsets_ptr != prev_inputs.offsets_ptr + 3 * batch_size. Got: inputs.offsets_ptr={}, prev_inputs.offsets_ptr={}, batch_size={}",
612                inputs.values_ptr, prev_inputs.values_ptr, self.instance_def.batch_size)))).into());
613                }
614                if inputs.n != prev_inputs.n.saturating_sub(self.instance_def.batch_size) {
615                    return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((self.name(), format!("inputs.n != prev_inputs.n - batch_size. Got: inputs.n={}, prev_inputs.n={}, batch_size={}",
616                inputs.n, prev_inputs.n, self.instance_def.batch_size)))).into());
617                }
618            }
619            for index_in_batch in 0..self.instance_def.batch_size {
620                let (a, b, c) = self.read_memory_vars(
621                    &vm.segments.memory,
622                    inputs.values_ptr,
623                    inputs.offsets_ptr,
624                    index_in_batch,
625                )?;
626                let a_op_b = self.apply_operation(&a, &b, &inputs.p)?;
627                if a_op_b.mod_floor(&inputs.p) != c.mod_floor(&inputs.p) {
628                    // Build error string
629                    let p = inputs.p;
630                    let op = self.builtin_type.operation_string();
631                    let error_string = format!("Expected a {op} b == c (mod p). Got: instance={instance}, batch={index_in_batch}, p={p}, a={a}, b={b}, c={c}.");
632                    return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((
633                        self.name(),
634                        error_string,
635                    )))
636                    .into());
637                }
638            }
639            prev_inputs = inputs;
640        }
641        if !n_instances.is_zero() && prev_inputs.n != self.instance_def.batch_size {
642            return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((
643                self.name(),
644                format!(
645                    "prev_inputs.n != batch_size Got: prev_inputs.n={}, batch_size={}",
646                    prev_inputs.n, self.instance_def.batch_size
647                ),
648            )))
649            .into());
650        }
651        Ok(())
652    }
653
654    #[cfg(test)]
655    #[cfg(feature = "mod_builtin")]
656    // Testing method used to test programs that use parameters which are not included in any layout
657    // For example, programs with large batch size
658    pub(crate) fn override_layout_params(&mut self, batch_size: usize, word_bit_len: u32) {
659        self.instance_def.batch_size = batch_size;
660        self.instance_def.word_bit_len = word_bit_len;
661        self.shift = BigUint::one().shl(word_bit_len);
662        self.shift_powers = core::array::from_fn(|i| self.shift.pow(i as u32));
663        self.zero_segment_size = core::cmp::max(N_WORDS, batch_size * 3);
664    }
665
666    // Calculates the result of `lhs OP rhs`
667    //
668    // The builtin type (add or mul) determines the OP
669    pub(crate) fn apply_operation(
670        &self,
671        lhs: &BigUint,
672        rhs: &BigUint,
673        prime: &BigUint,
674    ) -> Result<BigUint, MathError> {
675        let full_value = match self.builtin_type {
676            ModBuiltinType::Mul => lhs * rhs,
677            ModBuiltinType::Add => lhs + rhs,
678        };
679
680        let value = if full_value < &self.k_bound * prime {
681            full_value.mod_floor(prime)
682        } else {
683            full_value - (&self.k_bound - 1u32) * prime
684        };
685
686        Ok(value)
687    }
688
689    // Given `known OP unknown = result (mod p)`, it deduces `unknown`
690    //
691    // The builtin type (add or mul) determines the OP
692    pub(crate) fn deduce_operand(
693        &self,
694        known: &BigUint,
695        result: &BigUint,
696        prime: &BigUint,
697    ) -> Result<BigUint, MathError> {
698        let value = match self.builtin_type {
699            ModBuiltinType::Add => {
700                if known <= result {
701                    result - known
702                } else {
703                    result + prime - known
704                }
705            }
706            ModBuiltinType::Mul => div_mod_unsigned(result, known, prime)?,
707        };
708        Ok(value)
709    }
710}
711
712#[cfg(test)]
713mod tests {
714    use super::*;
715
716    #[test]
717    fn apply_operation_add() {
718        let builtin = ModBuiltinRunner::new_add_mod(&ModInstanceDef::new(Some(8), 8, 8), true);
719
720        assert_eq!(
721            builtin
722                .apply_operation(
723                    &BigUint::from(2u32),
724                    &BigUint::from(3u32),
725                    &BigUint::from(7u32)
726                )
727                .unwrap(),
728            BigUint::from(5u32)
729        );
730
731        assert_eq!(
732            builtin
733                .apply_operation(
734                    &BigUint::from(5u32),
735                    &BigUint::from(5u32),
736                    &BigUint::from(5u32)
737                )
738                .unwrap(),
739            BigUint::from(5u32)
740        );
741    }
742
743    #[test]
744    fn apply_operation_mul() {
745        let builtin = ModBuiltinRunner::new_mul_mod(&ModInstanceDef::new(Some(8), 8, 8), true);
746
747        assert_eq!(
748            builtin
749                .apply_operation(
750                    &BigUint::from(2u32),
751                    &BigUint::from(3u32),
752                    &BigUint::from(7u32)
753                )
754                .unwrap(),
755            BigUint::from(6u32)
756        );
757    }
758
759    #[test]
760    fn deduce_operand_add() {
761        let builtin = ModBuiltinRunner::new_add_mod(&ModInstanceDef::new(Some(8), 8, 8), true);
762
763        assert_eq!(
764            builtin
765                .deduce_operand(
766                    &BigUint::from(2u32),
767                    &BigUint::from(5u32),
768                    &BigUint::from(7u32)
769                )
770                .unwrap(),
771            BigUint::from(3u32)
772        );
773        assert_eq!(
774            builtin
775                .deduce_operand(
776                    &BigUint::from(5u32),
777                    &BigUint::from(2u32),
778                    &BigUint::from(7u32)
779                )
780                .unwrap(),
781            BigUint::from(4u32)
782        );
783    }
784
785    #[test]
786    fn deduce_operand_mul() {
787        let builtin = ModBuiltinRunner::new_mul_mod(&ModInstanceDef::new(Some(8), 8, 8), true);
788
789        assert_eq!(
790            builtin
791                .deduce_operand(
792                    &BigUint::from(2u32),
793                    &BigUint::from(1u32),
794                    &BigUint::from(7u32)
795                )
796                .unwrap(),
797            BigUint::from(4u32)
798        );
799    }
800
801    #[test]
802    #[cfg(feature = "mod_builtin")]
803    fn test_air_private_input_all_cairo() {
804        use crate::{
805            air_private_input::{ModInput, ModInputInstance, ModInputMemoryVars, PrivateInput},
806            hint_processor::builtin_hint_processor::builtin_hint_processor_definition::BuiltinHintProcessor,
807            types::layout_name::LayoutName,
808            utils::test_utils::Program,
809            vm::runners::cairo_runner::CairoRunner,
810            Felt252,
811        };
812
813        let program_data = include_bytes!(
814            "../../../../../cairo_programs/mod_builtin_feature/proof/mod_builtin.json"
815        );
816
817        let mut hint_processor = BuiltinHintProcessor::new_empty();
818        let program = Program::from_bytes(program_data, Some("main")).unwrap();
819        let mut runner =
820            CairoRunner::new(&program, LayoutName::all_cairo, None, true, false, false).unwrap();
821
822        let end = runner.initialize(false).unwrap();
823        // Modify add_mod & mul_mod params
824
825        runner.run_until_pc(end, &mut hint_processor).unwrap();
826        runner.run_for_steps(1, &mut hint_processor).unwrap();
827        runner.end_run(false, false, &mut hint_processor).unwrap();
828        runner.read_return_values(false).unwrap();
829        runner.finalize_segments().unwrap();
830
831        // We compare against the execution of python cairo-run with the same layout
832        let air_private_input = runner.get_air_private_input();
833        assert_eq!(
834            air_private_input.0.get(&BuiltinName::add_mod).unwrap()[0],
835            PrivateInput::Mod(ModInput {
836                instances: vec![
837                    ModInputInstance {
838                        index: 0,
839                        p0: Felt252::ONE,
840                        p1: Felt252::ONE,
841                        p2: Felt252::ZERO,
842                        p3: Felt252::ZERO,
843                        values_ptr: 23023,
844                        offsets_ptr: 23055,
845                        n: 2,
846                        batch: BTreeMap::from([(
847                            0,
848                            ModInputMemoryVars {
849                                a_offset: 0,
850                                a0: Felt252::ONE,
851                                a1: Felt252::ZERO,
852                                a2: Felt252::ZERO,
853                                a3: Felt252::ZERO,
854                                b_offset: 12,
855                                b0: Felt252::ONE,
856                                b1: Felt252::ONE,
857                                b2: Felt252::ZERO,
858                                b3: Felt252::ZERO,
859                                c_offset: 4,
860                                c0: Felt252::TWO,
861                                c1: Felt252::ONE,
862                                c2: Felt252::ZERO,
863                                c3: Felt252::ZERO
864                            }
865                        ),])
866                    },
867                    ModInputInstance {
868                        index: 1,
869                        p0: Felt252::ONE,
870                        p1: Felt252::ONE,
871                        p2: Felt252::ZERO,
872                        p3: Felt252::ZERO,
873                        values_ptr: 23023,
874                        offsets_ptr: 23058,
875                        n: 1,
876                        batch: BTreeMap::from([(
877                            0,
878                            ModInputMemoryVars {
879                                a_offset: 16,
880                                a0: Felt252::ZERO,
881                                a1: Felt252::ZERO,
882                                a2: Felt252::ZERO,
883                                a3: Felt252::ZERO,
884                                b_offset: 20,
885                                b0: Felt252::TWO,
886                                b1: Felt252::ZERO,
887                                b2: Felt252::ZERO,
888                                b3: Felt252::ZERO,
889                                c_offset: 24,
890                                c0: Felt252::TWO,
891                                c1: Felt252::ZERO,
892                                c2: Felt252::ZERO,
893                                c3: Felt252::ZERO
894                            }
895                        ),])
896                    }
897                ],
898                zero_value_address: 23019
899            })
900        );
901        assert_eq!(
902            air_private_input.0.get(&BuiltinName::mul_mod).unwrap()[0],
903            PrivateInput::Mod(ModInput {
904                instances: vec![
905                    ModInputInstance {
906                        index: 0,
907                        p0: Felt252::ONE,
908                        p1: Felt252::ONE,
909                        p2: Felt252::ZERO,
910                        p3: Felt252::ZERO,
911                        values_ptr: 23023,
912                        offsets_ptr: 23061,
913                        n: 3,
914                        batch: BTreeMap::from([(
915                            0,
916                            ModInputMemoryVars {
917                                a_offset: 12,
918                                a0: Felt252::ONE,
919                                a1: Felt252::ONE,
920                                a2: Felt252::ZERO,
921                                a3: Felt252::ZERO,
922                                b_offset: 8,
923                                b0: Felt252::TWO,
924                                b1: Felt252::ZERO,
925                                b2: Felt252::ZERO,
926                                b3: Felt252::ZERO,
927                                c_offset: 16,
928                                c0: Felt252::ZERO,
929                                c1: Felt252::ZERO,
930                                c2: Felt252::ZERO,
931                                c3: Felt252::ZERO
932                            }
933                        ),])
934                    },
935                    ModInputInstance {
936                        index: 1,
937                        p0: Felt252::ONE,
938                        p1: Felt252::ONE,
939                        p2: Felt252::ZERO,
940                        p3: Felt252::ZERO,
941                        values_ptr: 23023,
942                        offsets_ptr: 23064,
943                        n: 2,
944                        batch: BTreeMap::from([(
945                            0,
946                            ModInputMemoryVars {
947                                a_offset: 0,
948                                a0: Felt252::ONE,
949                                a1: Felt252::ZERO,
950                                a2: Felt252::ZERO,
951                                a3: Felt252::ZERO,
952                                b_offset: 8,
953                                b0: Felt252::TWO,
954                                b1: Felt252::ZERO,
955                                b2: Felt252::ZERO,
956                                b3: Felt252::ZERO,
957                                c_offset: 20,
958                                c0: Felt252::TWO,
959                                c1: Felt252::ZERO,
960                                c2: Felt252::ZERO,
961                                c3: Felt252::ZERO
962                            }
963                        ),])
964                    },
965                    ModInputInstance {
966                        index: 2,
967                        p0: Felt252::ONE,
968                        p1: Felt252::ONE,
969                        p2: Felt252::ZERO,
970                        p3: Felt252::ZERO,
971                        values_ptr: 23023,
972                        offsets_ptr: 23067,
973                        n: 1,
974                        batch: BTreeMap::from([(
975                            0,
976                            ModInputMemoryVars {
977                                a_offset: 8,
978                                a0: Felt252::TWO,
979                                a1: Felt252::ZERO,
980                                a2: Felt252::ZERO,
981                                a3: Felt252::ZERO,
982                                b_offset: 28,
983                                b0: Felt252::ONE,
984                                b1: Felt252::ZERO,
985                                b2: Felt252::ZERO,
986                                b3: Felt252::ZERO,
987                                c_offset: 24,
988                                c0: Felt252::TWO,
989                                c1: Felt252::ZERO,
990                                c2: Felt252::ZERO,
991                                c3: Felt252::ZERO
992                            }
993                        ),])
994                    }
995                ],
996                zero_value_address: 23019
997            })
998        )
999    }
1000}
cairo_vm/vm/runners/builtin_runner/modulo.rs

cairo_vm/vm/runners/builtin_runner/
modulo.rs
