cairo_vm/vm/runners/builtin_runner/
modulo.rs

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

cairo_vm/vm/runners/builtin_runner/
modulo.rs
