cairo_lang_casm/hints/
mod.rs

1#![expect(clippy::literal_string_with_formatting_args)]
2#[cfg(not(feature = "std"))]
3use alloc::{
4    format,
5    string::{String, ToString},
6};
7use core::fmt::{Display, Formatter};
8
9use cairo_lang_utils::bigint::BigIntAsHex;
10use indoc::formatdoc;
11
12use crate::operand::{CellRef, DerefOrImmediate, ResOperand};
13
14#[cfg(test)]
15mod test;
16
17// Represents a cairo hint.
18// Note: Hint encoding should be backwards-compatible. This is an API guarantee.
19// For example, new variants should have new `index`.
20#[derive(Debug, Eq, PartialEq, Clone)]
21#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize), serde(untagged))]
22#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
23#[cfg_attr(
24    feature = "parity-scale-codec",
25    derive(parity_scale_codec::Encode, parity_scale_codec::Decode)
26)]
27pub enum Hint {
28    #[cfg_attr(feature = "parity-scale-codec", codec(index = 0))]
29    Core(CoreHintBase),
30    #[cfg_attr(feature = "parity-scale-codec", codec(index = 1))]
31    Starknet(StarknetHint),
32    #[cfg_attr(feature = "parity-scale-codec", codec(index = 2))]
33    #[cfg_attr(feature = "schemars", schemars(skip))]
34    External(ExternalHint),
35}
36
37impl Hint {
38    pub fn representing_string(&self) -> String {
39        format!("{self:?}")
40    }
41}
42
43impl From<CoreHint> for Hint {
44    fn from(value: CoreHint) -> Self {
45        Hint::Core(value.into())
46    }
47}
48impl From<StarknetHint> for Hint {
49    fn from(value: StarknetHint) -> Self {
50        Hint::Starknet(value)
51    }
52}
53impl From<ExternalHint> for Hint {
54    fn from(value: ExternalHint) -> Self {
55        Hint::External(value)
56    }
57}
58
59/// A trait for displaying the pythonic version of a hint.
60/// Should only be used from within the compiler.
61pub trait PythonicHint {
62    fn get_pythonic_hint(&self) -> String;
63}
64
65impl PythonicHint for Hint {
66    fn get_pythonic_hint(&self) -> String {
67        match self {
68            Hint::Core(hint) => hint.get_pythonic_hint(),
69            Hint::Starknet(hint) => hint.get_pythonic_hint(),
70            Hint::External(hint) => hint.get_pythonic_hint(),
71        }
72    }
73}
74
75/// Represents a hint that triggers a system call.
76#[derive(Debug, Eq, PartialEq, Clone)]
77#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
78#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
79#[cfg_attr(
80    feature = "parity-scale-codec",
81    derive(parity_scale_codec::Encode, parity_scale_codec::Decode)
82)]
83pub enum StarknetHint {
84    #[cfg_attr(feature = "parity-scale-codec", codec(index = 0))]
85    SystemCall { system: ResOperand },
86    #[cfg_attr(feature = "parity-scale-codec", codec(index = 1))]
87    #[cfg_attr(feature = "schemars", schemars(skip))]
88    Cheatcode {
89        selector: BigIntAsHex,
90        input_start: ResOperand,
91        input_end: ResOperand,
92        output_start: CellRef,
93        output_end: CellRef,
94    },
95}
96
97// Represents a cairo core hint.
98#[derive(Debug, Eq, PartialEq, Clone)]
99#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize), serde(untagged))]
100#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
101#[cfg_attr(
102    feature = "parity-scale-codec",
103    derive(parity_scale_codec::Encode, parity_scale_codec::Decode)
104)]
105pub enum CoreHintBase {
106    #[cfg_attr(feature = "parity-scale-codec", codec(index = 0))]
107    Core(CoreHint),
108    #[cfg_attr(feature = "parity-scale-codec", codec(index = 1))]
109    Deprecated(DeprecatedHint),
110}
111
112impl From<CoreHint> for CoreHintBase {
113    fn from(value: CoreHint) -> Self {
114        CoreHintBase::Core(value)
115    }
116}
117impl From<DeprecatedHint> for CoreHintBase {
118    fn from(value: DeprecatedHint) -> Self {
119        CoreHintBase::Deprecated(value)
120    }
121}
122
123#[derive(Debug, Eq, PartialEq, Clone)]
124#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
125#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
126#[cfg_attr(
127    feature = "parity-scale-codec",
128    derive(parity_scale_codec::Encode, parity_scale_codec::Decode)
129)]
130pub enum CoreHint {
131    #[cfg_attr(feature = "parity-scale-codec", codec(index = 0))]
132    AllocSegment { dst: CellRef },
133    #[cfg_attr(feature = "parity-scale-codec", codec(index = 1))]
134    TestLessThan { lhs: ResOperand, rhs: ResOperand, dst: CellRef },
135    #[cfg_attr(feature = "parity-scale-codec", codec(index = 2))]
136    TestLessThanOrEqual { lhs: ResOperand, rhs: ResOperand, dst: CellRef },
137    /// Variant of TestLessThanOrEqual that compares addresses.
138    #[cfg_attr(feature = "parity-scale-codec", codec(index = 28))]
139    TestLessThanOrEqualAddress { lhs: ResOperand, rhs: ResOperand, dst: CellRef },
140    /// Multiplies two 128-bit integers and returns two 128-bit integers: the high and low parts of
141    /// the product.
142    #[cfg_attr(feature = "parity-scale-codec", codec(index = 3))]
143    WideMul128 { lhs: ResOperand, rhs: ResOperand, high: CellRef, low: CellRef },
144    /// Computes lhs/rhs and returns the quotient and remainder.
145    ///
146    /// Note: the hint may be used to write an already assigned memory cell.
147    #[cfg_attr(feature = "parity-scale-codec", codec(index = 4))]
148    DivMod { lhs: ResOperand, rhs: ResOperand, quotient: CellRef, remainder: CellRef },
149    /// Divides dividend (represented by 2 128bit limbs) by divisor (represented by 2 128bit
150    /// limbs). Returns the quotient (represented by 2 128bit limbs) and remainder (represented by
151    /// 2 128bit limbs). In all cases - `name`0 is the least significant limb.
152    #[cfg_attr(feature = "parity-scale-codec", codec(index = 5))]
153    Uint256DivMod {
154        dividend0: ResOperand,
155        dividend1: ResOperand,
156        divisor0: ResOperand,
157        divisor1: ResOperand,
158        quotient0: CellRef,
159        quotient1: CellRef,
160        remainder0: CellRef,
161        remainder1: CellRef,
162    },
163    /// Divides dividend (represented by 4 128bit limbs) by divisor (represented by 2 128bit
164    /// limbs). Returns the quotient (represented by 4 128bit limbs) and remainder (represented
165    /// by 2 128bit limbs).
166    /// In all cases - `name`0 is the least significant limb.
167    #[cfg_attr(feature = "parity-scale-codec", codec(index = 6))]
168    Uint512DivModByUint256 {
169        dividend0: ResOperand,
170        dividend1: ResOperand,
171        dividend2: ResOperand,
172        dividend3: ResOperand,
173        divisor0: ResOperand,
174        divisor1: ResOperand,
175        quotient0: CellRef,
176        quotient1: CellRef,
177        quotient2: CellRef,
178        quotient3: CellRef,
179        remainder0: CellRef,
180        remainder1: CellRef,
181    },
182    #[cfg_attr(feature = "parity-scale-codec", codec(index = 7))]
183    SquareRoot { value: ResOperand, dst: CellRef },
184    /// Computes the square root of value_low<<128+value_high, stores the 64bit limbs of the result
185    /// in sqrt0 and sqrt1 as well as the 128bit limbs of the remainder in remainder_low and
186    /// remainder_high. The remainder is defined as `value - sqrt**2`.
187    /// Lastly it checks whether `2*sqrt - remainder >= 2**128`.
188    #[cfg_attr(feature = "parity-scale-codec", codec(index = 8))]
189    Uint256SquareRoot {
190        value_low: ResOperand,
191        value_high: ResOperand,
192        sqrt0: CellRef,
193        sqrt1: CellRef,
194        remainder_low: CellRef,
195        remainder_high: CellRef,
196        sqrt_mul_2_minus_remainder_ge_u128: CellRef,
197    },
198    /// Finds some `x` and `y` such that `x * scalar + y = value` and `x <= max_x`.
199    #[cfg_attr(feature = "parity-scale-codec", codec(index = 9))]
200    LinearSplit { value: ResOperand, scalar: ResOperand, max_x: ResOperand, x: CellRef, y: CellRef },
201    /// Allocates a new dict segment, and write its start address into the dict_infos segment.
202    #[cfg_attr(feature = "parity-scale-codec", codec(index = 10))]
203    AllocFelt252Dict { segment_arena_ptr: ResOperand },
204    /// Fetch the previous value of a key in a dict, and write it in a new dict access.
205    #[cfg_attr(feature = "parity-scale-codec", codec(index = 11))]
206    Felt252DictEntryInit { dict_ptr: ResOperand, key: ResOperand },
207    /// Similar to Felt252DictWrite, but updates an existing entry and does not write the previous
208    /// value to the stack.
209    #[cfg_attr(feature = "parity-scale-codec", codec(index = 12))]
210    Felt252DictEntryUpdate { dict_ptr: ResOperand, value: ResOperand },
211    /// Retrieves the index of the given dict in the dict_infos segment.
212    #[cfg_attr(feature = "parity-scale-codec", codec(index = 13))]
213    GetSegmentArenaIndex { dict_end_ptr: ResOperand, dict_index: CellRef },
214    /// Initialized the lists of accesses of each key of a dict as a preparation of squash_dict.
215    #[cfg_attr(feature = "parity-scale-codec", codec(index = 14))]
216    InitSquashData {
217        dict_accesses: ResOperand,
218        ptr_diff: ResOperand,
219        n_accesses: ResOperand,
220        big_keys: CellRef,
221        first_key: CellRef,
222    },
223    /// Retrieves the current index of a dict access to process.
224    #[cfg_attr(feature = "parity-scale-codec", codec(index = 15))]
225    GetCurrentAccessIndex { range_check_ptr: ResOperand },
226    /// Writes if the squash_dict loop should be skipped.
227    #[cfg_attr(feature = "parity-scale-codec", codec(index = 16))]
228    ShouldSkipSquashLoop { should_skip_loop: CellRef },
229    /// Writes the delta from the current access index to the next one.
230    #[cfg_attr(feature = "parity-scale-codec", codec(index = 17))]
231    GetCurrentAccessDelta { index_delta_minus1: CellRef },
232    /// Writes if the squash_dict loop should be continued.
233    #[cfg_attr(feature = "parity-scale-codec", codec(index = 18))]
234    ShouldContinueSquashLoop { should_continue: CellRef },
235    /// Writes the next dict key to process.
236    #[cfg_attr(feature = "parity-scale-codec", codec(index = 19))]
237    GetNextDictKey { next_key: CellRef },
238    /// Finds the two small arcs from within [(0,a),(a,b),(b,PRIME)] and writes it to the
239    /// range_check segment.
240    #[cfg_attr(feature = "parity-scale-codec", codec(index = 20))]
241    AssertLeFindSmallArcs { range_check_ptr: ResOperand, a: ResOperand, b: ResOperand },
242    /// Writes if the arc (0,a) was excluded.
243    #[cfg_attr(feature = "parity-scale-codec", codec(index = 21))]
244    AssertLeIsFirstArcExcluded { skip_exclude_a_flag: CellRef },
245    /// Writes if the arc (a,b) was excluded.
246    #[cfg_attr(feature = "parity-scale-codec", codec(index = 22))]
247    AssertLeIsSecondArcExcluded { skip_exclude_b_minus_a: CellRef },
248    /// Samples a random point on the EC.
249    #[cfg_attr(feature = "parity-scale-codec", codec(index = 23))]
250    RandomEcPoint { x: CellRef, y: CellRef },
251    /// Computes the square root of `val`, if `val` is a quadratic residue, and of `3 * val`
252    /// otherwise.
253    ///
254    /// Since 3 is not a quadratic residue, exactly one of `val` and `3 * val` is a quadratic
255    /// residue (unless `val` is 0). This allows proving that `val` is not a quadratic residue.
256    #[cfg_attr(feature = "parity-scale-codec", codec(index = 24))]
257    FieldSqrt { val: ResOperand, sqrt: CellRef },
258    /// Prints the values from start to end.
259    /// Both must be pointers.
260    #[cfg_attr(feature = "parity-scale-codec", codec(index = 25))]
261    DebugPrint { start: ResOperand, end: ResOperand },
262    /// Returns an address with `size` free locations afterwards.
263    #[cfg_attr(feature = "parity-scale-codec", codec(index = 26))]
264    AllocConstantSize { size: ResOperand, dst: CellRef },
265    /// Provides the inverse of b (represented by 2 128-bit limbs) modulo n (represented by 2
266    /// 128-bit limbs), or a proof that b has no inverse.
267    ///
268    /// In case b has an inverse: Returns `r` and `k` such that:
269    ///   * `r = 1 / b (mod n)`
270    ///   * `k = (r * b - 1) / n`
271    ///   * `g0_or_no_inv = 0`
272    ///
273    /// In case b has no inverse: Returns `g`, `s`, and `t`, such that:
274    /// `g > 1`
275    /// `g == 2 || g % 2 == 1` (in particular, `g0_or_no_inv = g0 != 0`)
276    /// `g * s = b`
277    /// `g * t = n`
278    ///
279    /// The case `n == 1` is considered "no-inverse" (special case).
280    /// In this case: Returns `g == 1`, `s == b` and `t == 1`.
281    /// All no-inverse requirements are satisfied, except for `g > 1`.
282    ///
283    /// In all cases - `name`0 is the least significant limb.
284    #[cfg_attr(feature = "parity-scale-codec", codec(index = 27))]
285    U256InvModN {
286        b0: ResOperand,
287        b1: ResOperand,
288        n0: ResOperand,
289        n1: ResOperand,
290        g0_or_no_inv: CellRef,
291        g1_option: CellRef,
292        s_or_r0: CellRef,
293        s_or_r1: CellRef,
294        t_or_k0: CellRef,
295        t_or_k1: CellRef,
296    },
297
298    #[cfg_attr(feature = "parity-scale-codec", codec(index = 29))]
299    EvalCircuit {
300        n_add_mods: ResOperand,
301        add_mod_builtin: ResOperand,
302        n_mul_mods: ResOperand,
303        mul_mod_builtin: ResOperand,
304    },
305}
306
307/// Represents a deprecated hint which is kept for backward compatibility of previously deployed
308/// contracts.
309#[derive(Debug, Eq, PartialEq, Clone)]
310#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
311#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
312#[cfg_attr(
313    feature = "parity-scale-codec",
314    derive(parity_scale_codec::Encode, parity_scale_codec::Decode)
315)]
316pub enum DeprecatedHint {
317    /// Asserts that the current access indices list is empty (after the loop).
318    #[cfg_attr(feature = "parity-scale-codec", codec(index = 0))]
319    AssertCurrentAccessIndicesIsEmpty,
320    /// Asserts that the number of used accesses is equal to the length of the original accesses
321    /// list.
322    #[cfg_attr(feature = "parity-scale-codec", codec(index = 1))]
323    AssertAllAccessesUsed { n_used_accesses: CellRef },
324    /// Asserts that the keys list is empty.
325    #[cfg_attr(feature = "parity-scale-codec", codec(index = 2))]
326    AssertAllKeysUsed,
327    /// Asserts that the arc (b, PRIME) was excluded.
328    #[cfg_attr(feature = "parity-scale-codec", codec(index = 3))]
329    AssertLeAssertThirdArcExcluded,
330    /// Asserts that the input represents integers and that a<b.
331    #[cfg_attr(feature = "parity-scale-codec", codec(index = 4))]
332    AssertLtAssertValidInput { a: ResOperand, b: ResOperand },
333    /// Retrieves and writes the value corresponding to the given dict and key from the vm
334    /// dict_manager.
335    #[cfg_attr(feature = "parity-scale-codec", codec(index = 5))]
336    Felt252DictRead { dict_ptr: ResOperand, key: ResOperand, value_dst: CellRef },
337    /// Sets the value corresponding to the key in the vm dict_manager.
338    #[cfg_attr(feature = "parity-scale-codec", codec(index = 6))]
339    Felt252DictWrite { dict_ptr: ResOperand, key: ResOperand, value: ResOperand },
340}
341
342/// Represents an external hint.
343///
344/// Hints used out of the Sierra environment, mostly for creating external wrapper for code.
345#[derive(Debug, Eq, PartialEq, Clone)]
346#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
347#[cfg_attr(
348    feature = "parity-scale-codec",
349    derive(parity_scale_codec::Encode, parity_scale_codec::Decode)
350)]
351pub enum ExternalHint {
352    /// Relocates a segment from `src` to `dst`.
353    #[cfg_attr(feature = "parity-scale-codec", codec(index = 0))]
354    AddRelocationRule { src: ResOperand, dst: ResOperand },
355    /// Writes a run argument of number `index` to `dst` and on.
356    #[cfg_attr(feature = "parity-scale-codec", codec(index = 1))]
357    WriteRunParam { index: ResOperand, dst: CellRef },
358    /// Stores an array marker in the HintProcessor. Useful for debugging.
359    #[cfg_attr(feature = "parity-scale-codec", codec(index = 2))]
360    AddMarker { start: ResOperand, end: ResOperand },
361    /// Adds a trace call with the given flag to the HintProcessor. Useful for debugging.
362    #[cfg_attr(feature = "parity-scale-codec", codec(index = 3))]
363    AddTrace { flag: ResOperand },
364}
365
366struct DerefOrImmediateFormatter<'a>(&'a DerefOrImmediate);
367impl Display for DerefOrImmediateFormatter<'_> {
368    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
369        match self.0 {
370            DerefOrImmediate::Deref(d) => write!(f, "memory{d}"),
371            DerefOrImmediate::Immediate(i) => write!(f, "{}", i.value),
372        }
373    }
374}
375
376struct ResOperandAsIntegerFormatter<'a>(&'a ResOperand);
377impl Display for ResOperandAsIntegerFormatter<'_> {
378    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
379        match self.0 {
380            ResOperand::Deref(d) => write!(f, "memory{d}"),
381            ResOperand::DoubleDeref(d, i) => write!(f, "memory[memory{d} + {i}]"),
382            ResOperand::Immediate(i) => write!(f, "{}", i.value),
383            ResOperand::BinOp(bin_op) => {
384                write!(
385                    f,
386                    "(memory{} {} {}) % PRIME",
387                    bin_op.a,
388                    bin_op.op,
389                    DerefOrImmediateFormatter(&bin_op.b)
390                )
391            }
392        }
393    }
394}
395
396struct ResOperandAsAddressFormatter<'a>(&'a ResOperand);
397impl Display for ResOperandAsAddressFormatter<'_> {
398    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
399        match self.0 {
400            ResOperand::Deref(d) => write!(f, "memory{d}"),
401            ResOperand::DoubleDeref(d, i) => write!(f, "memory[memory{d} + {i}]"),
402            ResOperand::Immediate(i) => {
403                unreachable!("Address cannot be an immediate: {}.", i.value)
404            }
405            ResOperand::BinOp(bin_op) => {
406                write!(
407                    f,
408                    "memory{} {} {}",
409                    bin_op.a,
410                    bin_op.op,
411                    DerefOrImmediateFormatter(&bin_op.b)
412                )
413            }
414        }
415    }
416}
417
418impl PythonicHint for CoreHintBase {
419    fn get_pythonic_hint(&self) -> String {
420        match self {
421            CoreHintBase::Core(hint) => hint.get_pythonic_hint(),
422            CoreHintBase::Deprecated(_) => {
423                unreachable!("Deprecated hints do not have a pythonic version.")
424            }
425        }
426    }
427}
428
429impl PythonicHint for CoreHint {
430    fn get_pythonic_hint(&self) -> String {
431        match self {
432            CoreHint::AllocSegment { dst } => format!("memory{dst} = segments.add()"),
433            CoreHint::AllocFelt252Dict { segment_arena_ptr } => {
434                let segment_arena_ptr = ResOperandAsAddressFormatter(segment_arena_ptr);
435                formatdoc! {"
436
437                    if '__dict_manager' not in globals():
438                        from starkware.cairo.common.dict import DictManager
439                        __dict_manager = DictManager()
440
441                    if '__segment_index_to_arena_index' not in globals():
442                        # A map from the relocatable value segment index to the index in the
443                        # arena.
444                        __segment_index_to_arena_index = {{}}
445
446                    # {segment_arena_ptr} is the address of the next SegmentArenaBuiltin.
447                    # memory[{segment_arena_ptr} - 2] is the number of allocated segments.
448                    index = memory[{segment_arena_ptr} - 2]
449
450                    segment_start = __dict_manager.new_default_dict(
451                        segments, 0, temp_segment=index > 0
452                    )
453
454                    # Update '__segment_index_to_arena_index'.
455                    __segment_index_to_arena_index[segment_start.segment_index] = index
456
457                    # Update 'SegmentInfo::start'.
458                    # memory[{segment_arena_ptr} - 3] is the address of the segment arena infos
459                    # segment. index * 3 is added to get the address of the new SegmentInfo.
460                    memory[memory[{segment_arena_ptr} - 3] + index * 3] = segment_start
461                "}
462            }
463            CoreHint::Felt252DictEntryInit { dict_ptr, key } => {
464                let (dict_ptr, key) =
465                    (ResOperandAsAddressFormatter(dict_ptr), ResOperandAsIntegerFormatter(key));
466                formatdoc! {"
467
468                    dict_tracker = __dict_manager.get_tracker({dict_ptr})
469                    dict_tracker.current_ptr += 3
470                    memory[{dict_ptr} + 1] = dict_tracker.data[{key}]
471                "}
472            }
473            CoreHint::Felt252DictEntryUpdate { dict_ptr, value } => {
474                let (dict_ptr, value) =
475                    (ResOperandAsAddressFormatter(dict_ptr), ResOperandAsIntegerFormatter(value));
476                formatdoc! {"
477
478                    dict_tracker = __dict_manager.get_tracker({dict_ptr})
479                    dict_tracker.data[memory[{dict_ptr} - 3]] = {value}
480                "}
481            }
482            CoreHint::TestLessThan { lhs, rhs, dst } => {
483                format!(
484                    "memory{dst} = {} < {}",
485                    ResOperandAsIntegerFormatter(lhs),
486                    ResOperandAsIntegerFormatter(rhs)
487                )
488            }
489            CoreHint::TestLessThanOrEqual { lhs, rhs, dst } => format!(
490                "memory{dst} = {} <= {}",
491                ResOperandAsIntegerFormatter(lhs),
492                ResOperandAsIntegerFormatter(rhs)
493            ),
494            CoreHint::TestLessThanOrEqualAddress { lhs, rhs, dst } => format!(
495                "memory{dst} = {} <= {}",
496                ResOperandAsAddressFormatter(lhs),
497                ResOperandAsAddressFormatter(rhs)
498            ),
499            CoreHint::WideMul128 { lhs, rhs, high, low } => format!(
500                "(memory{high}, memory{low}) = divmod({} * {}, 2**128)",
501                ResOperandAsIntegerFormatter(lhs),
502                ResOperandAsIntegerFormatter(rhs)
503            ),
504            CoreHint::DivMod { lhs, rhs, quotient, remainder } => format!(
505                "(memory{quotient}, memory{remainder}) = divmod({}, {})",
506                ResOperandAsIntegerFormatter(lhs),
507                ResOperandAsIntegerFormatter(rhs)
508            ),
509            CoreHint::Uint256DivMod {
510                dividend0,
511                dividend1,
512                quotient0,
513                quotient1,
514                divisor0,
515                divisor1,
516                remainder0,
517                remainder1,
518            } => {
519                let (dividend0, dividend1, divisor0, divisor1) = (
520                    ResOperandAsIntegerFormatter(dividend0),
521                    ResOperandAsIntegerFormatter(dividend1),
522                    ResOperandAsIntegerFormatter(divisor0),
523                    ResOperandAsIntegerFormatter(divisor1),
524                );
525                formatdoc! {"
526
527                    dividend = {dividend0} + {dividend1} * 2**128
528                    divisor = {divisor0} + {divisor1} * 2**128
529                    quotient, remainder = divmod(dividend, divisor)
530                    memory{quotient0} = quotient & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
531                    memory{quotient1} = quotient >> 128
532                    memory{remainder0} = remainder & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
533                    memory{remainder1} = remainder >> 128
534                "}
535            }
536            CoreHint::Uint512DivModByUint256 {
537                dividend0,
538                dividend1,
539                dividend2,
540                dividend3,
541                divisor0,
542                divisor1,
543                quotient0,
544                quotient1,
545                quotient2,
546                quotient3,
547                remainder0,
548                remainder1,
549            } => {
550                let [dividend0, dividend1, dividend2, dividend3, divisor0, divisor1] =
551                    [dividend0, dividend1, dividend2, dividend3, divisor0, divisor1]
552                        .map(ResOperandAsIntegerFormatter);
553                formatdoc! {"
554
555                    dividend = {dividend0} + {dividend1} * 2**128 + {dividend2} * 2**256 + \
556                     {dividend3} * 2**384
557                    divisor = {divisor0} + {divisor1} * 2**128
558                    quotient, remainder = divmod(dividend, divisor)
559                    memory{quotient0} = quotient & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
560                    memory{quotient1} = (quotient >> 128) & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
561                    memory{quotient2} = (quotient >> 256) & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
562                    memory{quotient3} = quotient >> 384
563                    memory{remainder0} = remainder & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
564                    memory{remainder1} = remainder >> 128
565                "}
566            }
567            CoreHint::SquareRoot { value, dst } => {
568                let value = ResOperandAsIntegerFormatter(value);
569                formatdoc! {"
570
571                    import math
572                    memory{dst} = math.isqrt({value})
573                "}
574            }
575            CoreHint::Uint256SquareRoot {
576                value_low,
577                value_high,
578                sqrt0,
579                sqrt1,
580                remainder_low,
581                remainder_high,
582                sqrt_mul_2_minus_remainder_ge_u128,
583            } => {
584                let (value_low, value_high) = (
585                    ResOperandAsIntegerFormatter(value_low),
586                    ResOperandAsIntegerFormatter(value_high),
587                );
588                formatdoc! {"
589
590                    import math;
591                    value = {value_low} + {value_high} * 2**128
592                    root = math.isqrt(value)
593                    remainder = value - root ** 2
594                    memory{sqrt0} = root & 0xFFFFFFFFFFFFFFFF
595                    memory{sqrt1} = root >> 64
596                    memory{remainder_low} = remainder & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
597                    memory{remainder_high} = remainder >> 128
598                    memory{sqrt_mul_2_minus_remainder_ge_u128} = root * 2 - remainder >= 2**128
599                "}
600            }
601            CoreHint::LinearSplit { value, scalar, max_x, x, y } => {
602                let (value, scalar, max_x) = (
603                    ResOperandAsIntegerFormatter(value),
604                    ResOperandAsIntegerFormatter(scalar),
605                    ResOperandAsIntegerFormatter(max_x),
606                );
607                formatdoc! {"
608
609                    (value, scalar) = ({value}, {scalar})
610                    x = min(value // scalar, {max_x})
611                    y = value - x * scalar
612                    memory{x} = x
613                    memory{y} = y
614                "}
615            }
616            CoreHint::RandomEcPoint { x, y } => {
617                formatdoc! {"
618
619                    from starkware.crypto.signature.signature import ALPHA, BETA, FIELD_PRIME
620                    from starkware.python.math_utils import random_ec_point
621                    (memory{x}, memory{y}) = random_ec_point(FIELD_PRIME, ALPHA, BETA)
622                "}
623            }
624            CoreHint::FieldSqrt { val, sqrt } => {
625                let val = ResOperandAsIntegerFormatter(val);
626                formatdoc! {"
627
628                    from starkware.crypto.signature.signature import FIELD_PRIME
629                    from starkware.python.math_utils import is_quad_residue, sqrt
630
631                    val = {val}
632                    if is_quad_residue(val, FIELD_PRIME):
633                        memory{sqrt} = sqrt(val, FIELD_PRIME)
634                    else:
635                        memory{sqrt} = sqrt(val * 3, FIELD_PRIME)
636                "}
637            }
638            CoreHint::GetCurrentAccessIndex { range_check_ptr } => {
639                let rc = ResOperandAsAddressFormatter(range_check_ptr);
640                formatdoc! {"
641
642                    current_access_indices = sorted(access_indices[key])[::-1]
643                    current_access_index = current_access_indices.pop()
644                    memory[{rc}] = current_access_index
645                "}
646            }
647            CoreHint::ShouldSkipSquashLoop { should_skip_loop } => {
648                format!("memory{should_skip_loop} = 0 if current_access_indices else 1")
649            }
650            CoreHint::GetCurrentAccessDelta { index_delta_minus1 } => formatdoc! {"
651
652                new_access_index = current_access_indices.pop()
653                memory{index_delta_minus1} = new_access_index - current_access_index - 1
654                current_access_index = new_access_index
655            "},
656            CoreHint::ShouldContinueSquashLoop { should_continue } => {
657                format!("memory{should_continue} = 1 if current_access_indices else 0")
658            }
659            CoreHint::GetNextDictKey { next_key } => formatdoc! {"
660                assert len(keys) > 0, 'No keys left but remaining_accesses > 0.'
661                memory{next_key} = key = keys.pop()
662            "},
663            CoreHint::GetSegmentArenaIndex { dict_end_ptr, dict_index } => {
664                let dict_end_ptr = ResOperandAsAddressFormatter(dict_end_ptr);
665                formatdoc! {"
666
667                    memory{dict_index} = __segment_index_to_arena_index[
668                        {dict_end_ptr}.segment_index
669                    ]
670                "}
671            }
672            CoreHint::InitSquashData {
673                dict_accesses,
674                ptr_diff,
675                n_accesses,
676                big_keys,
677                first_key,
678            } => {
679                let (dict_accesses, ptr_diff, n_accesses) = (
680                    ResOperandAsAddressFormatter(dict_accesses),
681                    ResOperandAsIntegerFormatter(ptr_diff),
682                    ResOperandAsIntegerFormatter(n_accesses),
683                );
684                formatdoc! {"
685
686                    dict_access_size = 3
687                    address = {dict_accesses}
688                    assert {ptr_diff} % dict_access_size == 0, 'Accesses array size must be \
689                     divisible by DictAccess.SIZE'
690                    n_accesses = {n_accesses}
691                    if '__squash_dict_max_size' in globals():
692                        assert n_accesses <= __squash_dict_max_size, f'squash_dict() can only be \
693                     used with n_accesses<={{__squash_dict_max_size}}. ' f'Got: \
694                     n_accesses={{n_accesses}}.'
695                    # A map from key to the list of indices accessing it.
696                    access_indices = {{}}
697                    for i in range(n_accesses):
698                        key = memory[address + dict_access_size * i]
699                        access_indices.setdefault(key, []).append(i)
700                    # Descending list of keys.
701                    keys = sorted(access_indices.keys(), reverse=True)
702                    # Are the keys used bigger than range_check bound.
703                    memory{big_keys} = 1 if keys[0] >= range_check_builtin.bound else 0
704                    memory{first_key} = key = keys.pop()
705                "}
706            }
707            CoreHint::AssertLeFindSmallArcs { range_check_ptr, a, b } => {
708                let (range_check_ptr, a, b) = (
709                    ResOperandAsAddressFormatter(range_check_ptr),
710                    ResOperandAsIntegerFormatter(a),
711                    ResOperandAsIntegerFormatter(b),
712                );
713                formatdoc! {"
714
715                    import itertools
716
717                    from starkware.cairo.common.math_utils import assert_integer
718                    assert_integer({a})
719                    assert_integer({b})
720                    a = {a} % PRIME
721                    b = {b} % PRIME
722                    assert a <= b, f'a = {{a}} is not less than or equal to b = {{b}}.'
723
724                    # Find an arc less than PRIME / 3, and another less than PRIME / 2.
725                    lengths_and_indices = [(a, 0), (b - a, 1), (PRIME - 1 - b, 2)]
726                    lengths_and_indices.sort()
727                    assert lengths_and_indices[0][0] <= PRIME // 3 and lengths_and_indices[1][0] \
728                     <= PRIME // 2
729                    excluded = lengths_and_indices[2][1]
730
731                    memory[{range_check_ptr} + 1], memory[{range_check_ptr} + 0] = (
732                        divmod(lengths_and_indices[0][0], 3544607988759775765608368578435044694))
733                    memory[{range_check_ptr} + 3], memory[{range_check_ptr} + 2] = (
734                        divmod(lengths_and_indices[1][0], 5316911983139663648412552867652567041))
735                "}
736            }
737            CoreHint::AssertLeIsFirstArcExcluded { skip_exclude_a_flag } => {
738                format!("memory{skip_exclude_a_flag} = 1 if excluded != 0 else 0",)
739            }
740            CoreHint::AssertLeIsSecondArcExcluded { skip_exclude_b_minus_a } => {
741                format!("memory{skip_exclude_b_minus_a} = 1 if excluded != 1 else 0",)
742            }
743            CoreHint::DebugPrint { start, end } => {
744                let [start, end] = [start, end].map(ResOperandAsAddressFormatter);
745                formatdoc! {"
746
747                    curr = {start}
748                    end = {end}
749                    while curr != end:
750                        print(hex(memory[curr]))
751                        curr += 1
752                "}
753            }
754            CoreHint::AllocConstantSize { size, dst } => {
755                let size = ResOperandAsIntegerFormatter(size);
756                formatdoc! {"
757
758                    if '__boxed_segment' not in globals():
759                        __boxed_segment = segments.add()
760                    memory{dst} = __boxed_segment
761                    __boxed_segment += {size}
762                "}
763            }
764            CoreHint::U256InvModN {
765                b0,
766                b1,
767                n0,
768                n1,
769                g0_or_no_inv,
770                g1_option,
771                s_or_r0,
772                s_or_r1,
773                t_or_k0,
774                t_or_k1,
775            } => {
776                let [b0, b1, n0, n1] = [b0, b1, n0, n1].map(ResOperandAsIntegerFormatter);
777                formatdoc! {"
778
779                    from starkware.python.math_utils import igcdex
780
781                    b = {b0} + ({b1} << 128)
782                    n = {n0} + ({n1} << 128)
783
784                    (_, r, g) = igcdex(n, b)
785                    if n == 1:
786                        memory{g0_or_no_inv} = 1
787                        memory{g1_option} = 0
788                        memory{s_or_r0} = {b0}
789                        memory{s_or_r1} = {b1}
790                        memory{t_or_k0} = 1
791                        memory{t_or_k1} = 0
792                    elif g != 1:
793                        if g % 2 == 0:
794                            g = 2
795                        s = b // g
796                        t = n // g
797                        memory{g0_or_no_inv} = g & 0xffffffffffffffffffffffffffffffff
798                        memory{g1_option} = g >> 128
799                        memory{s_or_r0} = s & 0xffffffffffffffffffffffffffffffff
800                        memory{s_or_r1} = s >> 128
801                        memory{t_or_k0} = t & 0xffffffffffffffffffffffffffffffff
802                        memory{t_or_k1} = t >> 128
803                    else:
804                        r %= n
805                        k = (r * b - 1) // n
806                        memory{g0_or_no_inv} = 0
807                        memory{s_or_r0} = r & 0xffffffffffffffffffffffffffffffff
808                        memory{s_or_r1} = r >> 128
809                        memory{t_or_k0} = k & 0xffffffffffffffffffffffffffffffff
810                        memory{t_or_k1} = k >> 128
811                "}
812            }
813            CoreHint::EvalCircuit { n_add_mods, add_mod_builtin, n_mul_mods, mul_mod_builtin } => {
814                let n_add_mods = ResOperandAsIntegerFormatter(n_add_mods);
815                let add_mod_builtin = ResOperandAsAddressFormatter(add_mod_builtin);
816                let n_mul_mods = ResOperandAsIntegerFormatter(n_mul_mods);
817                let mul_mod_builtin = ResOperandAsAddressFormatter(mul_mod_builtin);
818                formatdoc! {"
819
820                from starkware.cairo.lang.builtins.modulo.mod_builtin_runner import ModBuiltinRunner
821
822                ModBuiltinRunner.fill_memory(
823                        memory=memory,
824                        add_mod=({add_mod_builtin}, builtin_runners[\"add_mod_builtin\"], {n_add_mods}),
825                        mul_mod=({mul_mod_builtin}, builtin_runners[\"mul_mod_builtin\"], {n_mul_mods}),
826                )
827                "}
828            }
829        }
830    }
831}
832
833impl PythonicHint for StarknetHint {
834    fn get_pythonic_hint(&self) -> String {
835        match self {
836            StarknetHint::SystemCall { system } => {
837                format!(
838                    "syscall_handler.syscall(syscall_ptr={})",
839                    ResOperandAsAddressFormatter(system)
840                )
841            }
842            StarknetHint::Cheatcode { .. } => {
843                r#"raise NotImplementedError("Cheatcode")"#.to_string()
844            }
845        }
846    }
847}
848
849impl PythonicHint for ExternalHint {
850    fn get_pythonic_hint(&self) -> String {
851        match self {
852            Self::AddRelocationRule { src, dst } => {
853                let [src, dst] = [src, dst].map(ResOperandAsAddressFormatter);
854                format!("memory.add_relocation_rule(src_ptr={src}, dest_ptr={dst})")
855            }
856            Self::WriteRunParam { index, dst } => {
857                let index = ResOperandAsIntegerFormatter(index);
858                format!("WriteRunParam {{ dst: {dst}, index: {index} }}",)
859            }
860            Self::AddMarker { start, end } => {
861                let [start, end] = [start, end].map(ResOperandAsAddressFormatter);
862                format!("AddMarker {{ start: {start}, end: {end} }}")
863            }
864            Self::AddTrace { flag } => {
865                format!("AddTrace {{ flag: {} }}", ResOperandAsIntegerFormatter(flag))
866            }
867        }
868    }
869}
cairo_lang_casm/hints/mod.rs

cairo_lang_casm/hints/
mod.rs
