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                        continue;
570                    } else {
571                        return Err(RunnerError::FillMemoryCoudNotFillTable(
572                            add_mod_index,
573                            mul_mod_index,
574                        ));
575                    }
576                }
577            }
578
579            return Err(RunnerError::FillMemoryCoudNotFillTable(
580                add_mod_index,
581                mul_mod_index,
582            ));
583        }
584        Ok(())
585    }
586
587    // Additional checks added to the standard builtin runner security checks
588    pub(crate) fn run_additional_security_checks(
589        &self,
590        vm: &VirtualMachine,
591    ) -> Result<(), VirtualMachineError> {
592        let segment_size = vm
593            .get_segment_used_size(self.base)
594            .ok_or(MemoryError::MissingSegmentUsedSizes)?;
595        let n_instances = div_ceil(segment_size, CELLS_PER_MOD as usize);
596        let mut prev_inputs = Inputs::default();
597        for instance in 0..n_instances {
598            let inputs = self.read_inputs(
599                &vm.segments.memory,
600                (self.base as isize, instance * CELLS_PER_MOD as usize).into(),
601            )?;
602            if !instance.is_zero() && prev_inputs.n > self.instance_def.batch_size {
603                for i in 0..N_WORDS {
604                    if inputs.p_values[i] != prev_inputs.p_values[i] {
605                        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]={}",
606                    i, inputs.p_values[i], prev_inputs.p_values[i])))).into());
607                    }
608                }
609                if inputs.values_ptr != prev_inputs.values_ptr {
610                    return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((self.name(), format!("inputs.values_ptr != prev_inputs.values_ptr. Got: inputs.values_ptr={}, prev_inputs.values_ptr={}",
611                inputs.values_ptr, prev_inputs.values_ptr)))).into());
612                }
613                if inputs.offsets_ptr
614                    != (prev_inputs.offsets_ptr + (3 * self.instance_def.batch_size))?
615                {
616                    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={}",
617                inputs.values_ptr, prev_inputs.values_ptr, self.instance_def.batch_size)))).into());
618                }
619                if inputs.n != prev_inputs.n.saturating_sub(self.instance_def.batch_size) {
620                    return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((self.name(), format!("inputs.n != prev_inputs.n - batch_size. Got: inputs.n={}, prev_inputs.n={}, batch_size={}",
621                inputs.n, prev_inputs.n, self.instance_def.batch_size)))).into());
622                }
623            }
624            for index_in_batch in 0..self.instance_def.batch_size {
625                let (a, b, c) = self.read_memory_vars(
626                    &vm.segments.memory,
627                    inputs.values_ptr,
628                    inputs.offsets_ptr,
629                    index_in_batch,
630                )?;
631                let a_op_b = self.apply_operation(&a, &b, &inputs.p)?;
632                if a_op_b.mod_floor(&inputs.p) != c.mod_floor(&inputs.p) {
633                    // Build error string
634                    let p = inputs.p;
635                    let op = self.builtin_type.operation_string();
636                    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}.");
637                    return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((
638                        self.name(),
639                        error_string,
640                    )))
641                    .into());
642                }
643            }
644            prev_inputs = inputs;
645        }
646        if !n_instances.is_zero() && prev_inputs.n != self.instance_def.batch_size {
647            return Err(RunnerError::ModBuiltinSecurityCheck(Box::new((
648                self.name(),
649                format!(
650                    "prev_inputs.n != batch_size Got: prev_inputs.n={}, batch_size={}",
651                    prev_inputs.n, self.instance_def.batch_size
652                ),
653            )))
654            .into());
655        }
656        Ok(())
657    }
658
659    #[cfg(test)]
660    #[cfg(feature = "mod_builtin")]
661    // Testing method used to test programs that use parameters which are not included in any layout
662    // For example, programs with large batch size
663    pub(crate) fn override_layout_params(&mut self, batch_size: usize, word_bit_len: u32) {
664        self.instance_def.batch_size = batch_size;
665        self.instance_def.word_bit_len = word_bit_len;
666        self.shift = BigUint::one().shl(word_bit_len);
667        self.shift_powers = core::array::from_fn(|i| self.shift.pow(i as u32));
668        self.zero_segment_size = core::cmp::max(N_WORDS, batch_size * 3);
669    }
670
671    // Calculates the result of `lhs OP rhs`
672    //
673    // The builtin type (add or mul) determines the OP
674    pub(crate) fn apply_operation(
675        &self,
676        lhs: &BigUint,
677        rhs: &BigUint,
678        prime: &BigUint,
679    ) -> Result<BigUint, MathError> {
680        let full_value = match self.builtin_type {
681            ModBuiltinType::Mul => lhs * rhs,
682            ModBuiltinType::Add => lhs + rhs,
683        };
684
685        let value = if full_value < &self.k_bound * prime {
686            full_value.mod_floor(prime)
687        } else {
688            full_value - (&self.k_bound - 1u32) * prime
689        };
690
691        Ok(value)
692    }
693
694    // Given `known OP unknown = result (mod p)`, it deduces `unknown`
695    //
696    // The builtin type (add or mul) determines the OP
697    pub(crate) fn deduce_operand(
698        &self,
699        known: &BigUint,
700        result: &BigUint,
701        prime: &BigUint,
702    ) -> Result<BigUint, MathError> {
703        let value = match self.builtin_type {
704            ModBuiltinType::Add => {
705                if known <= result {
706                    result - known
707                } else {
708                    result + prime - known
709                }
710            }
711            ModBuiltinType::Mul => div_mod_unsigned(result, known, prime)?,
712        };
713        Ok(value)
714    }
715}
716
717#[cfg(test)]
718mod tests {
719    use super::*;
720
721    #[test]
722    fn apply_operation_add() {
723        let builtin = ModBuiltinRunner::new_add_mod(&ModInstanceDef::new(Some(8), 8, 8), true);
724
725        assert_eq!(
726            builtin
727                .apply_operation(
728                    &BigUint::from(2u32),
729                    &BigUint::from(3u32),
730                    &BigUint::from(7u32)
731                )
732                .unwrap(),
733            BigUint::from(5u32)
734        );
735
736        assert_eq!(
737            builtin
738                .apply_operation(
739                    &BigUint::from(5u32),
740                    &BigUint::from(5u32),
741                    &BigUint::from(5u32)
742                )
743                .unwrap(),
744            BigUint::from(5u32)
745        );
746    }
747
748    #[test]
749    fn apply_operation_mul() {
750        let builtin = ModBuiltinRunner::new_mul_mod(&ModInstanceDef::new(Some(8), 8, 8), true);
751
752        assert_eq!(
753            builtin
754                .apply_operation(
755                    &BigUint::from(2u32),
756                    &BigUint::from(3u32),
757                    &BigUint::from(7u32)
758                )
759                .unwrap(),
760            BigUint::from(6u32)
761        );
762    }
763
764    #[test]
765    fn deduce_operand_add() {
766        let builtin = ModBuiltinRunner::new_add_mod(&ModInstanceDef::new(Some(8), 8, 8), true);
767
768        assert_eq!(
769            builtin
770                .deduce_operand(
771                    &BigUint::from(2u32),
772                    &BigUint::from(5u32),
773                    &BigUint::from(7u32)
774                )
775                .unwrap(),
776            BigUint::from(3u32)
777        );
778        assert_eq!(
779            builtin
780                .deduce_operand(
781                    &BigUint::from(5u32),
782                    &BigUint::from(2u32),
783                    &BigUint::from(7u32)
784                )
785                .unwrap(),
786            BigUint::from(4u32)
787        );
788    }
789
790    #[test]
791    fn deduce_operand_mul() {
792        let builtin = ModBuiltinRunner::new_mul_mod(&ModInstanceDef::new(Some(8), 8, 8), true);
793
794        assert_eq!(
795            builtin
796                .deduce_operand(
797                    &BigUint::from(2u32),
798                    &BigUint::from(1u32),
799                    &BigUint::from(7u32)
800                )
801                .unwrap(),
802            BigUint::from(4u32)
803        );
804    }
805
806    #[test]
807    #[cfg(feature = "mod_builtin")]
808    fn test_air_private_input_all_cairo() {
809        use crate::{
810            air_private_input::{ModInput, ModInputInstance, ModInputMemoryVars, PrivateInput},
811            hint_processor::builtin_hint_processor::builtin_hint_processor_definition::BuiltinHintProcessor,
812            types::layout_name::LayoutName,
813            utils::test_utils::Program,
814            vm::runners::cairo_runner::CairoRunner,
815            Felt252,
816        };
817
818        let program_data = include_bytes!(
819            "../../../../../cairo_programs/mod_builtin_feature/proof/mod_builtin.json"
820        );
821
822        let mut hint_processor = BuiltinHintProcessor::new_empty();
823        let program = Program::from_bytes(program_data, Some("main")).unwrap();
824        let proof_mode = true;
825        let mut runner = CairoRunner::new(
826            &program,
827            LayoutName::all_cairo,
828            None,
829            proof_mode,
830            false,
831            false,
832        )
833        .unwrap();
834
835        let end = runner.initialize(false).unwrap();
836        // Modify add_mod & mul_mod params
837
838        runner.run_until_pc(end, &mut hint_processor).unwrap();
839        runner.run_for_steps(1, &mut hint_processor).unwrap();
840        runner
841            .end_run(false, false, &mut hint_processor, proof_mode)
842            .unwrap();
843        runner.read_return_values(false).unwrap();
844        runner.finalize_segments().unwrap();
845
846        // We compare against the execution of python cairo-run with the same layout
847        let air_private_input = runner.get_air_private_input();
848        assert_eq!(
849            air_private_input.0.get(&BuiltinName::add_mod).unwrap()[0],
850            PrivateInput::Mod(ModInput {
851                instances: vec![
852                    ModInputInstance {
853                        index: 0,
854                        p0: Felt252::ONE,
855                        p1: Felt252::ONE,
856                        p2: Felt252::ZERO,
857                        p3: Felt252::ZERO,
858                        values_ptr: 23023,
859                        offsets_ptr: 23055,
860                        n: 2,
861                        batch: BTreeMap::from([(
862                            0,
863                            ModInputMemoryVars {
864                                a_offset: 0,
865                                a0: Felt252::ONE,
866                                a1: Felt252::ZERO,
867                                a2: Felt252::ZERO,
868                                a3: Felt252::ZERO,
869                                b_offset: 12,
870                                b0: Felt252::ONE,
871                                b1: Felt252::ONE,
872                                b2: Felt252::ZERO,
873                                b3: Felt252::ZERO,
874                                c_offset: 4,
875                                c0: Felt252::TWO,
876                                c1: Felt252::ONE,
877                                c2: Felt252::ZERO,
878                                c3: Felt252::ZERO
879                            }
880                        ),])
881                    },
882                    ModInputInstance {
883                        index: 1,
884                        p0: Felt252::ONE,
885                        p1: Felt252::ONE,
886                        p2: Felt252::ZERO,
887                        p3: Felt252::ZERO,
888                        values_ptr: 23023,
889                        offsets_ptr: 23058,
890                        n: 1,
891                        batch: BTreeMap::from([(
892                            0,
893                            ModInputMemoryVars {
894                                a_offset: 16,
895                                a0: Felt252::ZERO,
896                                a1: Felt252::ZERO,
897                                a2: Felt252::ZERO,
898                                a3: Felt252::ZERO,
899                                b_offset: 20,
900                                b0: Felt252::TWO,
901                                b1: Felt252::ZERO,
902                                b2: Felt252::ZERO,
903                                b3: Felt252::ZERO,
904                                c_offset: 24,
905                                c0: Felt252::TWO,
906                                c1: Felt252::ZERO,
907                                c2: Felt252::ZERO,
908                                c3: Felt252::ZERO
909                            }
910                        ),])
911                    }
912                ],
913                zero_value_address: 23019
914            })
915        );
916        assert_eq!(
917            air_private_input.0.get(&BuiltinName::mul_mod).unwrap()[0],
918            PrivateInput::Mod(ModInput {
919                instances: vec![
920                    ModInputInstance {
921                        index: 0,
922                        p0: Felt252::ONE,
923                        p1: Felt252::ONE,
924                        p2: Felt252::ZERO,
925                        p3: Felt252::ZERO,
926                        values_ptr: 23023,
927                        offsets_ptr: 23061,
928                        n: 3,
929                        batch: BTreeMap::from([(
930                            0,
931                            ModInputMemoryVars {
932                                a_offset: 12,
933                                a0: Felt252::ONE,
934                                a1: Felt252::ONE,
935                                a2: Felt252::ZERO,
936                                a3: Felt252::ZERO,
937                                b_offset: 8,
938                                b0: Felt252::TWO,
939                                b1: Felt252::ZERO,
940                                b2: Felt252::ZERO,
941                                b3: Felt252::ZERO,
942                                c_offset: 16,
943                                c0: Felt252::ZERO,
944                                c1: Felt252::ZERO,
945                                c2: Felt252::ZERO,
946                                c3: Felt252::ZERO
947                            }
948                        ),])
949                    },
950                    ModInputInstance {
951                        index: 1,
952                        p0: Felt252::ONE,
953                        p1: Felt252::ONE,
954                        p2: Felt252::ZERO,
955                        p3: Felt252::ZERO,
956                        values_ptr: 23023,
957                        offsets_ptr: 23064,
958                        n: 2,
959                        batch: BTreeMap::from([(
960                            0,
961                            ModInputMemoryVars {
962                                a_offset: 0,
963                                a0: Felt252::ONE,
964                                a1: Felt252::ZERO,
965                                a2: Felt252::ZERO,
966                                a3: Felt252::ZERO,
967                                b_offset: 8,
968                                b0: Felt252::TWO,
969                                b1: Felt252::ZERO,
970                                b2: Felt252::ZERO,
971                                b3: Felt252::ZERO,
972                                c_offset: 20,
973                                c0: Felt252::TWO,
974                                c1: Felt252::ZERO,
975                                c2: Felt252::ZERO,
976                                c3: Felt252::ZERO
977                            }
978                        ),])
979                    },
980                    ModInputInstance {
981                        index: 2,
982                        p0: Felt252::ONE,
983                        p1: Felt252::ONE,
984                        p2: Felt252::ZERO,
985                        p3: Felt252::ZERO,
986                        values_ptr: 23023,
987                        offsets_ptr: 23067,
988                        n: 1,
989                        batch: BTreeMap::from([(
990                            0,
991                            ModInputMemoryVars {
992                                a_offset: 8,
993                                a0: Felt252::TWO,
994                                a1: Felt252::ZERO,
995                                a2: Felt252::ZERO,
996                                a3: Felt252::ZERO,
997                                b_offset: 28,
998                                b0: Felt252::ONE,
999                                b1: Felt252::ZERO,
1000                                b2: Felt252::ZERO,
1001                                b3: Felt252::ZERO,
1002                                c_offset: 24,
1003                                c0: Felt252::TWO,
1004                                c1: Felt252::ZERO,
1005                                c2: Felt252::ZERO,
1006                                c3: Felt252::ZERO
1007                            }
1008                        ),])
1009                    }
1010                ],
1011                zero_value_address: 23019
1012            })
1013        )
1014    }
1015}
cairo_vm/vm/runners/builtin_runner/modulo.rs

cairo_vm/vm/runners/builtin_runner/
modulo.rs
