cairo_vm/hint_processor/builtin_hint_processor/
bigint.rs

1use crate::hint_processor::builtin_hint_processor::secp::bigint_utils::BigInt5;
2use crate::hint_processor::builtin_hint_processor::secp::secp_utils::BASE;
3use crate::math_utils::{div_mod, safe_div_bigint, signed_felt};
4use crate::stdlib::collections::HashMap;
5use crate::stdlib::prelude::String;
6use crate::types::exec_scope::ExecutionScopes;
7use crate::Felt252;
8use crate::{
9    hint_processor::{
10        builtin_hint_processor::secp::bigint_utils::BigInt3,
11        hint_processor_definition::HintReference,
12    },
13    serde::deserialize_program::ApTracking,
14    vm::{errors::hint_errors::HintError, vm_core::VirtualMachine},
15};
16use num_bigint::BigInt;
17use num_traits::Signed;
18
19use super::hint_utils::insert_value_from_var_name;
20
21/// Implements hint:
22/// ```python
23/// from starkware.cairo.common.cairo_secp.secp_utils import pack
24/// from starkware.cairo.common.math_utils import as_int
25/// from starkware.python.math_utils import div_mod, safe_div
26///
27/// p = pack(ids.P, PRIME)
28/// x = pack(ids.x, PRIME) + as_int(ids.x.d3, PRIME) * ids.BASE ** 3 + as_int(ids.x.d4, PRIME) * ids.BASE ** 4
29/// y = pack(ids.y, PRIME)
30///
31/// value = res = div_mod(x, y, p)
32/// ```
33pub fn bigint_pack_div_mod_hint(
34    vm: &mut VirtualMachine,
35    exec_scopes: &mut ExecutionScopes,
36    ids_data: &HashMap<String, HintReference>,
37    ap_tracking: &ApTracking,
38) -> Result<(), HintError> {
39    let p: BigInt = BigInt3::from_var_name("P", vm, ids_data, ap_tracking)?.pack86();
40
41    let x: BigInt = {
42        let x_bigint5 = BigInt5::from_var_name("x", vm, ids_data, ap_tracking)?;
43        // pack only takes the first three limbs
44        let x_lower = BigInt3 {
45            limbs: [
46                x_bigint5.limbs[0].clone(),
47                x_bigint5.limbs[1].clone(),
48                x_bigint5.limbs[2].clone(),
49            ],
50        };
51        let x_lower = x_lower.pack86();
52        let d3 = signed_felt(*x_bigint5.limbs[3].as_ref());
53        let d4 = signed_felt(*x_bigint5.limbs[4].as_ref());
54        x_lower + d3 * BigInt::from(BASE.pow(3)) + d4 * BigInt::from(BASE.pow(4))
55    };
56    let y: BigInt = BigInt3::from_var_name("y", vm, ids_data, ap_tracking)?.pack86();
57
58    let res = div_mod(&x, &y, &p)?;
59    exec_scopes.insert_value("res", res.clone());
60    exec_scopes.insert_value("value", res);
61    exec_scopes.insert_value("x", x);
62    exec_scopes.insert_value("y", y);
63    exec_scopes.insert_value("p", p);
64
65    Ok(())
66}
67
68/// Implements hint:
69/// ```python
70/// k = safe_div(res * y - x, p)
71/// value = k if k > 0 else 0 - k
72/// ids.flag = 1 if k > 0 else 0
73/// ```
74pub fn bigint_safe_div_hint(
75    vm: &mut VirtualMachine,
76    exec_scopes: &mut ExecutionScopes,
77    ids_data: &HashMap<String, HintReference>,
78    ap_tracking: &ApTracking,
79) -> Result<(), HintError> {
80    let res = exec_scopes.get::<BigInt>("res")?;
81    let y = exec_scopes.get::<BigInt>("y")?;
82    let x = exec_scopes.get::<BigInt>("x")?;
83    let p = exec_scopes.get::<BigInt>("p")?;
84
85    let k = safe_div_bigint(&(res * y - x), &p)?;
86    let (value, flag) = if k.is_positive() {
87        (k.clone(), Felt252::ONE)
88    } else {
89        (-k.clone(), Felt252::ZERO)
90    };
91
92    exec_scopes.insert_value("k", k);
93    exec_scopes.insert_value("value", value);
94    insert_value_from_var_name("flag", flag, vm, ids_data, ap_tracking)?;
95
96    Ok(())
97}
98
99#[cfg(test)]
100mod test {
101    use crate::any_box;
102    use crate::hint_processor::builtin_hint_processor::builtin_hint_processor_definition::BuiltinHintProcessor;
103    use crate::hint_processor::builtin_hint_processor::builtin_hint_processor_definition::HintProcessorData;
104    use crate::hint_processor::builtin_hint_processor::hint_code;
105    use crate::hint_processor::hint_processor_definition::{HintProcessorLogic, HintReference};
106    use crate::types::exec_scope::ExecutionScopes;
107    use crate::utils::test_utils::*;
108    use assert_matches::assert_matches;
109    use num_bigint::BigInt;
110
111    #[cfg(target_arch = "wasm32")]
112    use wasm_bindgen_test::*;
113
114    /// Input:
115    /// x = UnreducedBigInt5(0x38a23ca66202c8c2a72277, 0x6730e765376ff17ea8385, 0xca1ad489ab60ea581e6c1, 0, 0);
116    /// y = UnreducedBigInt3(0x20a4b46d3c5e24cda81f22, 0x967bf895824330d4273d0, 0x541e10c21560da25ada4c);
117    /// p = BigInt3(0x8a03bbfd25e8cd0364141, 0x3ffffffffffaeabb739abd, 0xfffffffffffffffffffff);
118    /// expected: value = res = 109567829260688255124154626727441144629993228404337546799996747905569082729709 (py int)
119    #[test]
120    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
121    fn test_bigint_pack_div_mod_hint() {
122        // Prepare the VM context:
123        let ids_data = non_continuous_ids_data![
124            ("x", 0), // located at `fp + 0`.
125            ("y", 5), // located at `fp + 5`.
126            ("P", 8)  // located at `fp + 8`.
127        ];
128
129        let mut vm = vm!();
130        vm.run_context.fp = 0;
131        add_segments!(vm, 11); // Alloc space for `ids.x`, `ids.y` and `ids.p`.
132        vm.segments = segments![
133            ((1, 0), 0x38a23ca66202c8c2a72277_i128), // x.d0
134            ((1, 1), 0x6730e765376ff17ea8385_i128),  // x.d1
135            ((1, 2), 0xca1ad489ab60ea581e6c1_i128),  // x.d2
136            ((1, 3), 0_i128),                        // x.d3
137            ((1, 4), 0_i128),                        // x.d4
138            ((1, 5), 0x20a4b46d3c5e24cda81f22_i128), // y.d0
139            ((1, 6), 0x967bf895824330d4273d0_i128),  // y.d1
140            ((1, 7), 0x541e10c21560da25ada4c_i128),  // y.d2
141            ((1, 8), 0x8a03bbfd25e8cd0364141_i128),  // P.id0
142            ((1, 9), 0x3ffffffffffaeabb739abd_i128), // P.id1
143            ((1, 10), 0xfffffffffffffffffffff_i128), // P.id2
144        ];
145
146        let mut exec_scopes = ExecutionScopes::new();
147        assert_matches!(
148            run_hint!(
149                vm,
150                ids_data,
151                hint_code::BIGINT_PACK_DIV_MOD,
152                &mut exec_scopes
153            ),
154            Ok(())
155        );
156
157        let expected = bigint_str!(
158            "109567829260688255124154626727441144629993228404337546799996747905569082729709"
159        );
160        assert_matches!(exec_scopes.get::<BigInt>("res"), Ok(x) if x == expected);
161        assert_matches!(exec_scopes.get::<BigInt>("value"), Ok(x) if x == expected);
162        assert_matches!(exec_scopes.get::<BigInt>("y"), Ok(x) if x == bigint_str!("38047400353360331012910998489219098987968251547384484838080352663220422975266"));
163        assert_matches!(exec_scopes.get::<BigInt>("x"), Ok(x) if x == bigint_str!("91414600319290532004473480113251693728834511388719905794310982800988866814583"));
164        assert_matches!(exec_scopes.get::<BigInt>("p"), Ok(x) if x == bigint_str!("115792089237316195423570985008687907852837564279074904382605163141518161494337"));
165    }
166
167    /// Input:
168    /// res = 109567829260688255124154626727441144629993228404337546799996747905569082729709
169    /// y = 38047400353360331012910998489219098987968251547384484838080352663220422975266
170    /// x = 91414600319290532004473480113251693728834511388719905794310982800988866814583
171    /// p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
172    /// Output:
173    /// k = 36002209591245282109880156842267569109802494162594623391338581162816748840003
174    /// value = 36002209591245282109880156842267569109802494162594623391338581162816748840003
175    /// ids.flag = 1
176    #[test]
177    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
178    fn test_bigint_safe_div_hint() {
179        let mut exec_scopes = ExecutionScopes::new();
180        exec_scopes.insert_value(
181            "res",
182            bigint_str!(
183                "109567829260688255124154626727441144629993228404337546799996747905569082729709"
184            ),
185        );
186        exec_scopes.insert_value(
187            "x",
188            bigint_str!(
189                "91414600319290532004473480113251693728834511388719905794310982800988866814583"
190            ),
191        );
192        exec_scopes.insert_value(
193            "y",
194            bigint_str!(
195                "38047400353360331012910998489219098987968251547384484838080352663220422975266"
196            ),
197        );
198        exec_scopes.insert_value(
199            "p",
200            bigint_str!(
201                "115792089237316195423570985008687907852837564279074904382605163141518161494337"
202            ),
203        );
204
205        let mut vm = vm!();
206        let ids_data = non_continuous_ids_data![("flag", 0)];
207        vm.run_context.fp = 0;
208        add_segments!(vm, 2); // Alloc space for `flag`
209
210        assert_matches!(
211            run_hint!(vm, ids_data, hint_code::BIGINT_SAFE_DIV, &mut exec_scopes),
212            Ok(())
213        );
214        assert_matches!(exec_scopes.get::<BigInt>("k"), Ok(x) if x == bigint_str!("36002209591245282109880156842267569109802494162594623391338581162816748840003"));
215        assert_matches!(exec_scopes.get::<BigInt>("value"), Ok(x) if x == bigint_str!("36002209591245282109880156842267569109802494162594623391338581162816748840003"));
216
217        check_memory![vm.segments.memory, ((1, 0), 1)];
218        // let flag_result = get_integer_from_var_name("flag", vm, ids_data, ap_tracking);
219        // assert!(flag_result.is_ok());
220        // assert_eq!(flag_result.unwrap().as_ref(), Felt252::ONE);
221    }
222}
cairo_vm/hint_processor/builtin_hint_processor/bigint.rs

cairo_vm/hint_processor/builtin_hint_processor/
bigint.rs
