1use crate::{
2 air_private_input::{PrivateInput, PrivateInputValue},
3 stdlib::{
4 cmp::{max, min},
5 prelude::*,
6 },
7 types::{builtin_name::BuiltinName, instance_definitions::LowRatio},
8};
9
10use crate::Felt252;
11use crate::{
12 types::relocatable::{MaybeRelocatable, Relocatable},
13 vm::{
14 errors::memory_errors::MemoryError,
15 vm_memory::{
16 memory::{Memory, ValidationRule},
17 memory_segments::MemorySegmentManager,
18 },
19 },
20};
21
22use lazy_static::lazy_static;
23
24const INNER_RC_BOUND_SHIFT: u64 = 16;
25const INNER_RC_BOUND_MASK: u64 = u16::MAX as u64;
26
27pub const RC_N_PARTS_STANDARD: u64 = 8;
28pub const RC_N_PARTS_96: u64 = 6;
29
30lazy_static! {
31 pub static ref BOUND_STANDARD: Felt252 =
32 Felt252::TWO.pow(INNER_RC_BOUND_SHIFT * RC_N_PARTS_STANDARD);
33 pub static ref BOUND_96: Felt252 = Felt252::TWO.pow(INNER_RC_BOUND_SHIFT * RC_N_PARTS_96);
34}
35
36#[derive(Debug, Clone)]
37pub struct RangeCheckBuiltinRunner<const N_PARTS: u64> {
38 ratio: Option<LowRatio>,
39 base: usize,
40 pub(crate) stop_ptr: Option<usize>,
41 pub(crate) included: bool,
42}
43
44impl<const N_PARTS: u64> RangeCheckBuiltinRunner<N_PARTS> {
45 pub fn new(ratio: Option<u32>, included: bool) -> RangeCheckBuiltinRunner<N_PARTS> {
46 RangeCheckBuiltinRunner {
47 ratio: ratio.map(LowRatio::new_int),
48 base: 0,
49 stop_ptr: None,
50 included,
51 }
52 }
53
54 pub fn new_with_low_ratio(
55 ratio: Option<LowRatio>,
56 included: bool,
57 ) -> RangeCheckBuiltinRunner<N_PARTS> {
58 RangeCheckBuiltinRunner {
59 ratio,
60 base: 0,
61 stop_ptr: None,
62 included,
63 }
64 }
65
66 pub fn initialize_segments(&mut self, segments: &mut MemorySegmentManager) {
67 self.base = segments.add().segment_index as usize }
69
70 pub fn initial_stack(&self) -> Vec<MaybeRelocatable> {
71 if self.included {
72 vec![MaybeRelocatable::from((self.base as isize, 0))]
73 } else {
74 vec![]
75 }
76 }
77
78 pub fn base(&self) -> usize {
79 self.base
80 }
81
82 pub fn ratio(&self) -> Option<u32> {
83 self.ratio.map(|ratio| ratio.numerator)
84 }
85
86 pub fn ratio_den(&self) -> Option<u32> {
87 self.ratio.map(|ratio| ratio.denominator)
88 }
89
90 pub fn name(&self) -> BuiltinName {
91 match N_PARTS {
92 RC_N_PARTS_96 => BuiltinName::range_check96,
93 _ => BuiltinName::range_check,
94 }
95 }
96
97 pub fn n_parts(&self) -> u64 {
98 N_PARTS
99 }
100
101 pub fn bound(&self) -> &'static Felt252 {
102 match N_PARTS {
103 RC_N_PARTS_96 => &BOUND_96,
104 _ => &BOUND_STANDARD,
105 }
106 }
107
108 pub fn add_validation_rule(&self, memory: &mut Memory) {
109 let rule = ValidationRule(Box::new(
110 |memory: &Memory, address: Relocatable| -> Result<Vec<Relocatable>, MemoryError> {
111 let num = memory
112 .get_integer(address)
113 .map_err(|_| MemoryError::RangeCheckFoundNonInt(Box::new(address)))?;
114 if num.bits() as u64 <= N_PARTS * INNER_RC_BOUND_SHIFT {
115 Ok(vec![address.to_owned()])
116 } else {
117 Err(MemoryError::RangeCheckNumOutOfBounds(Box::new((
118 num.into_owned(),
119 Felt252::TWO.pow((N_PARTS * INNER_RC_BOUND_SHIFT) as u128),
120 ))))
121 }
122 },
123 ));
124 memory.add_validation_rule(self.base, rule);
125 }
126
127 pub fn get_used_cells(&self, segments: &MemorySegmentManager) -> Result<usize, MemoryError> {
128 segments
129 .get_segment_used_size(self.base)
130 .ok_or(MemoryError::MissingSegmentUsedSizes)
131 }
132
133 pub fn get_range_check_usage(&self, memory: &Memory) -> Option<(usize, usize)> {
134 let range_check_segment = memory.data.get(self.base)?;
135 let mut rc_bounds =
136 (!range_check_segment.is_empty()).then_some((usize::MAX, usize::MIN))?;
137
138 for value in range_check_segment {
140 rc_bounds = value
141 .get_value()?
142 .get_int_ref()?
143 .to_le_digits()
144 .into_iter()
146 .flat_map(|digit| {
147 (0..=3)
148 .rev()
149 .map(move |i| ((digit >> (i * INNER_RC_BOUND_SHIFT)) & INNER_RC_BOUND_MASK))
150 })
151 .take(N_PARTS as usize)
152 .fold(rc_bounds, |mm, x| {
153 (min(mm.0, x as usize), max(mm.1, x as usize))
154 });
155 }
156 Some(rc_bounds)
157 }
158
159 pub fn get_used_instances(
160 &self,
161 segments: &MemorySegmentManager,
162 ) -> Result<usize, MemoryError> {
163 self.get_used_cells(segments)
164 }
165
166 pub fn air_private_input(&self, memory: &Memory) -> Vec<PrivateInput> {
167 let mut private_inputs = vec![];
168 if let Some(segment) = memory.data.get(self.base) {
169 for (index, cell) in segment.iter().enumerate() {
170 if let Some(value) = cell.get_value().and_then(|value| value.get_int()) {
171 private_inputs.push(PrivateInput::Value(PrivateInputValue { index, value }))
172 }
173 }
174 }
175 private_inputs
176 }
177}
178
179#[cfg(test)]
180mod tests {
181 use super::*;
182 use crate::relocatable;
183 use crate::types::builtin_name::BuiltinName;
184 use crate::vm::errors::runner_errors::RunnerError;
185 use crate::vm::vm_memory::memory::Memory;
186 use crate::{
187 hint_processor::builtin_hint_processor::builtin_hint_processor_definition::BuiltinHintProcessor,
188 types::program::Program, utils::test_utils::*, vm::runners::builtin_runner::BuiltinRunner,
189 };
190
191 #[cfg(target_arch = "wasm32")]
192 use wasm_bindgen_test::*;
193
194 #[test]
195 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
196 fn get_used_instances() {
197 let builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), true);
198
199 let mut vm = vm!();
200 vm.segments.segment_used_sizes = Some(vec![1]);
201
202 assert_eq!(builtin.get_used_instances(&vm.segments), Ok(1));
203 }
204
205 #[test]
206 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
207 fn final_stack() {
208 let mut builtin: BuiltinRunner =
209 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), true).into();
210
211 let mut vm = vm!();
212
213 vm.segments = segments![
214 ((0, 0), (0, 0)),
215 ((0, 1), (0, 1)),
216 ((2, 0), (0, 0)),
217 ((2, 1), (0, 0))
218 ];
219
220 vm.segments.segment_used_sizes = Some(vec![0]);
221
222 let pointer = Relocatable::from((2, 2));
223
224 assert_eq!(
225 builtin.final_stack(&vm.segments, pointer).unwrap(),
226 Relocatable::from((2, 1))
227 );
228 }
229
230 #[test]
231 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
232 fn final_stack_error_stop_pointer() {
233 let mut builtin: BuiltinRunner =
234 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), true).into();
235
236 let mut vm = vm!();
237
238 vm.segments = segments![
239 ((0, 0), (0, 0)),
240 ((0, 1), (0, 1)),
241 ((2, 0), (0, 0)),
242 ((2, 1), (0, 0))
243 ];
244
245 vm.segments.segment_used_sizes = Some(vec![998]);
246
247 let pointer = Relocatable::from((2, 2));
248
249 assert_eq!(
250 builtin.final_stack(&vm.segments, pointer),
251 Err(RunnerError::InvalidStopPointer(Box::new((
252 BuiltinName::range_check,
253 relocatable!(0, 998),
254 relocatable!(0, 0)
255 ))))
256 );
257 }
258
259 #[test]
260 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
261 fn final_stack_error_when_notincluded() {
262 let mut builtin: BuiltinRunner =
263 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), false).into();
264
265 let mut vm = vm!();
266
267 vm.segments = segments![
268 ((0, 0), (0, 0)),
269 ((0, 1), (0, 1)),
270 ((2, 0), (0, 0)),
271 ((2, 1), (0, 0))
272 ];
273
274 vm.segments.segment_used_sizes = Some(vec![0]);
275
276 let pointer = Relocatable::from((2, 2));
277
278 assert_eq!(
279 builtin.final_stack(&vm.segments, pointer).unwrap(),
280 Relocatable::from((2, 2))
281 );
282 }
283
284 #[test]
285 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
286 fn final_stack_error_non_relocatable() {
287 let mut builtin: BuiltinRunner =
288 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), true).into();
289
290 let mut vm = vm!();
291
292 vm.segments = segments![
293 ((0, 0), (0, 0)),
294 ((0, 1), (0, 1)),
295 ((2, 0), (0, 0)),
296 ((2, 1), 2)
297 ];
298
299 vm.segments.segment_used_sizes = Some(vec![0]);
300
301 let pointer = Relocatable::from((2, 2));
302
303 assert_eq!(
304 builtin.final_stack(&vm.segments, pointer),
305 Err(RunnerError::NoStopPointer(Box::new(
306 BuiltinName::range_check
307 )))
308 );
309 }
310
311 #[test]
312 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
313 fn get_used_cells_and_allocated_size_test() {
314 let builtin: BuiltinRunner =
315 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), true).into();
316
317 let program = program!(
318 builtins = vec![BuiltinName::range_check],
319 data = vec_data!(
320 (4612671182993129469_i64),
321 (5189976364521848832_i64),
322 (18446744073709551615_i128),
323 (5199546496550207487_i64),
324 (4612389712311386111_i64),
325 (5198983563776393216_i64),
326 (2),
327 (2345108766317314046_i64),
328 (5191102247248822272_i64),
329 (5189976364521848832_i64),
330 (7),
331 (1226245742482522112_i64),
332 ((
333 "3618502788666131213697322783095070105623107215331596699973092056135872020470",
334 10
335 )),
336 (2345108766317314046_i64)
337 ),
338 main = Some(8),
339 );
340
341 let mut cairo_runner = cairo_runner!(program);
342
343 cairo_runner.vm.segments.segment_used_sizes = Some(vec![0]);
344
345 let mut hint_processor = BuiltinHintProcessor::new_empty();
346
347 let address = cairo_runner.initialize(false).unwrap();
348
349 cairo_runner
350 .run_until_pc(address, &mut hint_processor)
351 .unwrap();
352
353 assert_eq!(
354 builtin.get_used_cells_and_allocated_size(&cairo_runner.vm),
355 Ok((0, 1))
356 );
357 }
358
359 #[test]
360 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
361 fn get_allocated_memory_units() {
362 let builtin: BuiltinRunner =
363 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(10), true).into();
364
365 let program = program!(
366 builtins = vec![BuiltinName::range_check],
367 data = vec_data!(
368 (4612671182993129469_i64),
369 (5189976364521848832_i64),
370 (18446744073709551615_i128),
371 (5199546496550207487_i64),
372 (4612389712311386111_i64),
373 (5198983563776393216_i64),
374 (2),
375 (2345108766317314046_i64),
376 (5191102247248822272_i64),
377 (5189976364521848832_i64),
378 (7),
379 (1226245742482522112_i64),
380 ((
381 "3618502788666131213697322783095070105623107215331596699973092056135872020470",
382 10
383 )),
384 (2345108766317314046_i64)
385 ),
386 main = Some(8),
387 );
388
389 let mut cairo_runner = cairo_runner!(program);
390
391 let mut hint_processor = BuiltinHintProcessor::new_empty();
392
393 let address = cairo_runner.initialize(false).unwrap();
394
395 cairo_runner
396 .run_until_pc(address, &mut hint_processor)
397 .unwrap();
398
399 assert_eq!(builtin.get_allocated_memory_units(&cairo_runner.vm), Ok(1));
400 }
401
402 #[test]
403 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
404 fn initialize_segments_for_range_check() {
405 let mut builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
406 let mut segments = MemorySegmentManager::new();
407 builtin.initialize_segments(&mut segments);
408 assert_eq!(builtin.base, 0);
409 }
410
411 #[test]
412 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
413 fn get_initial_stack_for_range_check_with_base() {
414 let mut builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
415 builtin.base = 1;
416 let initial_stack = builtin.initial_stack();
417 assert_eq!(
418 initial_stack[0].clone(),
419 MaybeRelocatable::RelocatableValue((builtin.base() as isize, 0).into())
420 );
421 assert_eq!(initial_stack.len(), 1);
422 }
423
424 #[test]
425 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
426 fn test_base() {
427 let builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
428 assert_eq!(builtin.base(), 0);
429 }
430
431 #[test]
432 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
433 fn test_ratio() {
434 let builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
435 assert_eq!(builtin.ratio(), Some(8));
436 }
437
438 #[test]
439 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
440 fn get_used_cells_missing_segment_used_sizes() {
441 let builtin = BuiltinRunner::RangeCheck(
442 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(256), true),
443 );
444 let vm = vm!();
445
446 assert_eq!(
447 builtin.get_used_cells(&vm.segments),
448 Err(MemoryError::MissingSegmentUsedSizes)
449 );
450 }
451
452 #[test]
453 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
454 fn get_used_cells_empty() {
455 let builtin = BuiltinRunner::RangeCheck(
456 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(256), true),
457 );
458 let mut vm = vm!();
459
460 vm.segments.segment_used_sizes = Some(vec![0]);
461 assert_eq!(builtin.get_used_cells(&vm.segments), Ok(0));
462 }
463
464 #[test]
465 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
466 fn get_used_cells() {
467 let builtin = BuiltinRunner::RangeCheck(
468 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(256), true),
469 );
470 let mut vm = vm!();
471
472 vm.segments.segment_used_sizes = Some(vec![4]);
473 assert_eq!(builtin.get_used_cells(&vm.segments), Ok(4));
474 }
475
476 #[test]
477 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
478 fn get_range_check_usage_succesful_a() {
479 let builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
480 let memory = memory![((0, 0), 1), ((0, 1), 2), ((0, 2), 3), ((0, 3), 4)];
481 assert_eq!(builtin.get_range_check_usage(&memory), Some((0, 4)));
482 }
483
484 #[test]
485 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
486 fn get_range_check_usage_succesful_b() {
487 let builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
488 let memory = memory![
489 ((0, 0), 1465218365),
490 ((0, 1), 2134570341),
491 ((0, 2), 31349610736_i64),
492 ((0, 3), 413468326585859_i64)
493 ];
494 assert_eq!(builtin.get_range_check_usage(&memory), Some((0, 62821)));
495 }
496
497 #[test]
498 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
499 fn get_range_check_usage_succesful_c() {
500 let builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
501 let memory = memory![
502 ((0, 0), 634834751465218365_i64),
503 ((0, 1), 42876922134570341_i64),
504 ((0, 2), 23469831349610736_i64),
505 ((0, 3), 23468413468326585859_i128),
506 ((0, 4), 75346043276073460326_i128),
507 ((0, 5), 87234598724867609478353436890268_i128)
508 ];
509 assert_eq!(builtin.get_range_check_usage(&memory), Some((0, 61576)));
510 }
511
512 #[test]
513 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
514 fn get_range_check_empty_memory() {
515 let builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
516 let memory = Memory::new();
517 assert_eq!(builtin.get_range_check_usage(&memory), None);
518 }
519
520 #[test]
522 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
523 fn get_used_perm_range_check_units() {
524 let builtin_runner: BuiltinRunner =
525 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true).into();
526 let mut vm = vm!();
527
528 vm.current_step = 8;
529 vm.segments.segment_used_sizes = Some(vec![1]);
530 assert_eq!(builtin_runner.get_used_perm_range_check_units(&vm), Ok(8));
531 }
532
533 #[test]
534 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
535 fn get_air_private_input() {
536 let builtin: BuiltinRunner =
537 RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(None, true).into();
538
539 let segments = segments![((0, 0), 0), ((0, 1), 1), ((0, 2), 2)];
540 assert_eq!(
541 builtin.air_private_input(&segments),
542 (vec![
543 PrivateInput::Value(PrivateInputValue {
544 index: 0,
545 value: 0.into(),
546 }),
547 PrivateInput::Value(PrivateInputValue {
548 index: 1,
549 value: 1.into(),
550 }),
551 PrivateInput::Value(PrivateInputValue {
552 index: 2,
553 value: 2.into(),
554 }),
555 ]),
556 );
557 }
558}