cairo_vm/hint_processor/builtin_hint_processor/
uint384_extension.rs

1use super::secp::bigint_utils::{Uint384, Uint768};
2use crate::stdlib::{collections::HashMap, prelude::*};
3use crate::types::errors::math_errors::MathError;
4use crate::{
5    hint_processor::hint_processor_definition::HintReference,
6    serde::deserialize_program::ApTracking,
7    vm::{errors::hint_errors::HintError, vm_core::VirtualMachine},
8};
9use num_integer::Integer;
10use num_traits::Zero;
11
12/* Implements Hint:
13       %{
14           def split(num: int, num_bits_shift: int, length: int):
15               a = []
16               for _ in range(length):
17                   a.append( num & ((1 << num_bits_shift) - 1) )
18                   num = num >> num_bits_shift
19               return tuple(a)
20
21           def pack(z, num_bits_shift: int) -> int:
22               limbs = (z.d0, z.d1, z.d2)
23               return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))
24
25           def pack_extended(z, num_bits_shift: int) -> int:
26               limbs = (z.d0, z.d1, z.d2, z.d3, z.d4, z.d5)
27               return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))
28
29           a = pack_extended(ids.a, num_bits_shift = 128)
30           div = pack(ids.div, num_bits_shift = 128)
31
32           quotient, remainder = divmod(a, div)
33
34           quotient_split = split(quotient, num_bits_shift=128, length=6)
35
36           ids.quotient.d0 = quotient_split[0]
37           ids.quotient.d1 = quotient_split[1]
38           ids.quotient.d2 = quotient_split[2]
39           ids.quotient.d3 = quotient_split[3]
40           ids.quotient.d4 = quotient_split[4]
41           ids.quotient.d5 = quotient_split[5]
42
43           remainder_split = split(remainder, num_bits_shift=128, length=3)
44           ids.remainder.d0 = remainder_split[0]
45           ids.remainder.d1 = remainder_split[1]
46           ids.remainder.d2 = remainder_split[2]
47       %}
48*/
49pub fn unsigned_div_rem_uint768_by_uint384(
50    vm: &mut VirtualMachine,
51    ids_data: &HashMap<String, HintReference>,
52    ap_tracking: &ApTracking,
53) -> Result<(), HintError> {
54    let a = Uint768::from_var_name("a", vm, ids_data, ap_tracking)?.pack();
55    let div = Uint384::from_var_name("div", vm, ids_data, ap_tracking)?.pack();
56
57    if div.is_zero() {
58        return Err(MathError::DividedByZero.into());
59    }
60    let (quotient, remainder) = a.div_mod_floor(&div);
61    let quotient_split = Uint768::split(&quotient);
62    quotient_split.insert_from_var_name("quotient", vm, ids_data, ap_tracking)?;
63    let remainder_split = Uint384::split(&remainder);
64    remainder_split.insert_from_var_name("remainder", vm, ids_data, ap_tracking)
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70    use crate::any_box;
71    use crate::hint_processor::builtin_hint_processor::builtin_hint_processor_definition::BuiltinHintProcessor;
72    use crate::hint_processor::builtin_hint_processor::builtin_hint_processor_definition::HintProcessorData;
73    use crate::hint_processor::builtin_hint_processor::hint_code;
74    use crate::hint_processor::builtin_hint_processor::secp::bigint_utils::Uint768;
75    use crate::hint_processor::hint_processor_definition::HintProcessorLogic;
76    use crate::utils::test_utils::*;
77
78    use assert_matches::assert_matches;
79
80    use crate::felt_str;
81    use crate::Felt252;
82    use rstest::rstest;
83    #[cfg(target_arch = "wasm32")]
84    use wasm_bindgen_test::*;
85
86    #[test]
87    fn get_uint768_from_base_addr_ok() {
88        //Uint768(1,2,3,4,5,6)
89        let mut vm = vm!();
90        vm.segments = segments![
91            ((1, 0), 1),
92            ((1, 1), 2),
93            ((1, 2), 3),
94            ((1, 3), 4),
95            ((1, 4), 5),
96            ((1, 5), 6)
97        ];
98        let x = Uint768::from_base_addr((1, 0).into(), "x", &vm).unwrap();
99        assert_eq!(x.limbs[0].as_ref(), &Felt252::ONE);
100        assert_eq!(x.limbs[1].as_ref(), &Felt252::from(2));
101        assert_eq!(x.limbs[2].as_ref(), &Felt252::from(3));
102    }
103
104    fn assert_is_err_identifier_has_no_member(
105        result: Result<Uint768, HintError>,
106        x: &str,
107        y: &str,
108    ) {
109        assert_matches!(result, Err(HintError::IdentifierHasNoMember(bx)) if *bx == (x.to_string(), y.to_string()))
110    }
111
112    #[test]
113    fn get_uint768_from_base_addr_missing_member_d0() {
114        //Uint768(x,2,x,x,x,x)
115        let mut vm = vm!();
116        vm.segments = segments![((0, 1), 2)];
117        let r = Uint768::from_base_addr((0, 0).into(), "x", &vm);
118        assert_is_err_identifier_has_no_member(r, "x", "d0")
119    }
120
121    #[test]
122    fn get_uint768_from_base_addr_missing_member_d1() {
123        //Uint768(1,x,x,x,x,x)
124        let mut vm = vm!();
125        vm.segments = segments![((0, 0), 1)];
126        let r = Uint768::from_base_addr((0, 0).into(), "x", &vm);
127        assert_is_err_identifier_has_no_member(r, "x", "d1")
128    }
129
130    #[test]
131    fn get_uint768_from_base_addr_missing_member_d2() {
132        //Uint768(1,2,x,x,x,x)
133        let mut vm = vm!();
134        vm.segments = segments![((0, 0), 1), ((0, 1), 2)];
135        let r = Uint768::from_base_addr((0, 0).into(), "x", &vm);
136        assert_is_err_identifier_has_no_member(r, "x", "d2")
137    }
138
139    #[test]
140    fn get_uint768_from_base_addr_missing_member_d3() {
141        //Uint768(1,2,3,x,x,x)
142        let mut vm = vm!();
143        vm.segments = segments![((0, 0), 1), ((0, 1), 2), ((0, 2), 3)];
144        let r = Uint768::from_base_addr((0, 0).into(), "x", &vm);
145        assert_is_err_identifier_has_no_member(r, "x", "d3")
146    }
147
148    #[test]
149    fn get_uint768_from_base_addr_missing_member_d4() {
150        //Uint768(1,2,3,4,x,x)
151        let mut vm = vm!();
152        vm.segments = segments![((0, 0), 1), ((0, 1), 2), ((0, 2), 3), ((0, 3), 4)];
153        let r = Uint768::from_base_addr((0, 0).into(), "x", &vm);
154        assert_is_err_identifier_has_no_member(r, "x", "d4")
155    }
156
157    #[test]
158    fn get_uint768_from_base_addr_missing_member_d5() {
159        //Uint768(1,2,3,4,5,x)
160        let mut vm = vm!();
161        vm.segments = segments![
162            ((0, 0), 1),
163            ((0, 1), 2),
164            ((0, 2), 3),
165            ((0, 3), 4),
166            ((0, 4), 5)
167        ];
168        let r = Uint768::from_base_addr((0, 0).into(), "x", &vm);
169        assert_is_err_identifier_has_no_member(r, "x", "d5")
170    }
171
172    #[test]
173    fn get_uint768_from_var_name_ok() {
174        //Uint768(1,2,3,4,5,6)
175        let mut vm = vm!();
176        vm.set_fp(1);
177        vm.segments = segments![
178            ((1, 0), 1),
179            ((1, 1), 2),
180            ((1, 2), 3),
181            ((1, 3), 4),
182            ((1, 4), 5),
183            ((1, 5), 6)
184        ];
185        let ids_data = ids_data!["x"];
186        let x = Uint768::from_var_name("x", &vm, &ids_data, &ApTracking::default()).unwrap();
187        assert_eq!(x.limbs[0].as_ref(), &Felt252::ONE);
188        assert_eq!(x.limbs[1].as_ref(), &Felt252::from(2));
189        assert_eq!(x.limbs[2].as_ref(), &Felt252::from(3));
190    }
191
192    #[test]
193    fn get_uint768_from_var_name_missing_member() {
194        //Uint768(1,2,x,x,x)
195        let mut vm = vm!();
196        vm.set_fp(1);
197        vm.segments = segments![((1, 0), 1), ((1, 1), 2)];
198        let ids_data = ids_data!["x"];
199        let r = Uint768::from_var_name("x", &vm, &ids_data, &ApTracking::default());
200        assert_is_err_identifier_has_no_member(r, "x", "d2")
201    }
202
203    #[test]
204    fn get_uint768_from_var_name_invalid_reference() {
205        let mut vm = vm!();
206        vm.segments = segments![((1, 0), 1), ((1, 1), 2), ((1, 2), 3)];
207        let ids_data = ids_data!["x"];
208        let r = Uint768::from_var_name("x", &vm, &ids_data, &ApTracking::default());
209        assert_matches!(r, Err(HintError::UnknownIdentifier(bx)) if bx.as_ref() == "x")
210    }
211
212    #[rstest]
213    #[case(hint_code::UNSIGNED_DIV_REM_UINT768_BY_UINT384)]
214    #[case(hint_code::UNSIGNED_DIV_REM_UINT768_BY_UINT384_STRIPPED)]
215    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
216    fn run_unsigned_div_rem_ok(#[case] hint_code: &str) {
217        let mut vm = vm_with_range_check!();
218        //Initialize fp
219        vm.run_context.fp = 17;
220        //Create hint_data
221        let ids_data = non_continuous_ids_data![
222            ("a", -17),
223            ("div", -11),
224            ("quotient", -8),
225            ("remainder", -2)
226        ];
227        //Insert ids into memory
228        vm.segments = segments![
229            //a
230            ((1, 0), 1),
231            ((1, 1), 2),
232            ((1, 2), 3),
233            ((1, 3), 4),
234            ((1, 4), 5),
235            ((1, 5), 6),
236            //div
237            ((1, 6), 6),
238            ((1, 7), 7),
239            ((1, 8), 8)
240        ];
241        //Execute the hint
242        assert_matches!(run_hint!(vm, ids_data, hint_code), Ok(()));
243        //Check hint memory inserts
244        check_memory![
245            vm.segments.memory,
246            // quotient
247            //((1, 9), 328319314958874220607240343889245110272),
248            //((1, 10), 329648542954659136480144150949525454847),
249            //((1, 11), 255211775190703847597530955573826158591),
250            ((1, 12), 0),
251            ((1, 13), 0),
252            ((1, 14), 0),
253            // remainder
254            ((1, 15), 71778311772385457136805581255138607105),
255            ((1, 16), 147544307532125661892322583691118247938),
256            ((1, 17), 3)
257        ];
258        assert_eq!(
259            vm.segments
260                .memory
261                .get_integer((1, 9).into())
262                .unwrap()
263                .as_ref(),
264            &felt_str!("328319314958874220607240343889245110272")
265        );
266        assert_eq!(
267            vm.segments
268                .memory
269                .get_integer((1, 10).into())
270                .unwrap()
271                .as_ref(),
272            &felt_str!("329648542954659136480144150949525454847")
273        );
274        assert_eq!(
275            vm.segments
276                .memory
277                .get_integer((1, 11).into())
278                .unwrap()
279                .as_ref(),
280            &felt_str!("255211775190703847597530955573826158591")
281        );
282    }
283
284    #[rstest]
285    #[case(hint_code::UNSIGNED_DIV_REM_UINT768_BY_UINT384)]
286    #[case(hint_code::UNSIGNED_DIV_REM_UINT768_BY_UINT384_STRIPPED)]
287    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
288    fn run_unsigned_div_rem_divide_by_zero(#[case] hint_code: &str) {
289        let mut vm = vm_with_range_check!();
290        //Initialize fp
291        vm.run_context.fp = 17;
292        //Create hint_data
293        let ids_data = non_continuous_ids_data![
294            ("a", -17),
295            ("div", -11),
296            ("quotient", -8),
297            ("remainder", -2)
298        ];
299        //Insert ids into memory
300        vm.segments = segments![
301            //a
302            ((1, 0), 1),
303            ((1, 1), 2),
304            ((1, 2), 3),
305            ((1, 3), 4),
306            ((1, 4), 5),
307            ((1, 5), 6),
308            //div
309            ((1, 6), 0),
310            ((1, 7), 0),
311            ((1, 8), 0)
312        ];
313        //Execute the hint
314        assert_matches!(
315            run_hint!(vm, ids_data, hint_code),
316            Err(HintError::Math(MathError::DividedByZero))
317        );
318    }
319}
cairo_vm/hint_processor/builtin_hint_processor/uint384_extension.rs

cairo_vm/hint_processor/builtin_hint_processor/
uint384_extension.rs
