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    // TODO(ilya): Remove once the blake2s opecode is supported by the VM.
365    /// Compresses a message using the Blake2s algorithm.
366    #[cfg_attr(feature = "parity-scale-codec", codec(index = 4))]
367    Blake2sCompress {
368        state: ResOperand,
369        byte_count: ResOperand,
370        message: ResOperand,
371        output: ResOperand,
372        finalize: ResOperand,
373    },
374}
375
376struct DerefOrImmediateFormatter<'a>(&'a DerefOrImmediate);
377impl Display for DerefOrImmediateFormatter<'_> {
378    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
379        match self.0 {
380            DerefOrImmediate::Deref(d) => write!(f, "memory{d}"),
381            DerefOrImmediate::Immediate(i) => write!(f, "{}", i.value),
382        }
383    }
384}
385
386struct ResOperandAsIntegerFormatter<'a>(&'a ResOperand);
387impl Display for ResOperandAsIntegerFormatter<'_> {
388    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
389        match self.0 {
390            ResOperand::Deref(d) => write!(f, "memory{d}"),
391            ResOperand::DoubleDeref(d, i) => write!(f, "memory[memory{d} + {i}]"),
392            ResOperand::Immediate(i) => write!(f, "{}", i.value),
393            ResOperand::BinOp(bin_op) => {
394                write!(
395                    f,
396                    "(memory{} {} {}) % PRIME",
397                    bin_op.a,
398                    bin_op.op,
399                    DerefOrImmediateFormatter(&bin_op.b)
400                )
401            }
402        }
403    }
404}
405
406struct ResOperandAsAddressFormatter<'a>(&'a ResOperand);
407impl Display for ResOperandAsAddressFormatter<'_> {
408    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
409        match self.0 {
410            ResOperand::Deref(d) => write!(f, "memory{d}"),
411            ResOperand::DoubleDeref(d, i) => write!(f, "memory[memory{d} + {i}]"),
412            ResOperand::Immediate(i) => {
413                unreachable!("Address cannot be an immediate: {}.", i.value)
414            }
415            ResOperand::BinOp(bin_op) => {
416                write!(
417                    f,
418                    "memory{} {} {}",
419                    bin_op.a,
420                    bin_op.op,
421                    DerefOrImmediateFormatter(&bin_op.b)
422                )
423            }
424        }
425    }
426}
427
428impl PythonicHint for CoreHintBase {
429    fn get_pythonic_hint(&self) -> String {
430        match self {
431            CoreHintBase::Core(hint) => hint.get_pythonic_hint(),
432            CoreHintBase::Deprecated(_) => {
433                unreachable!("Deprecated hints do not have a pythonic version.")
434            }
435        }
436    }
437}
438
439impl PythonicHint for CoreHint {
440    fn get_pythonic_hint(&self) -> String {
441        match self {
442            CoreHint::AllocSegment { dst } => format!("memory{dst} = segments.add()"),
443            CoreHint::AllocFelt252Dict { segment_arena_ptr } => {
444                let segment_arena_ptr = ResOperandAsAddressFormatter(segment_arena_ptr);
445                formatdoc! {"
446
447                    if '__dict_manager' not in globals():
448                        from starkware.cairo.common.dict import DictManager
449                        __dict_manager = DictManager()
450
451                    if '__segment_index_to_arena_index' not in globals():
452                        # A map from the relocatable value segment index to the index in the
453                        # arena.
454                        __segment_index_to_arena_index = {{}}
455
456                    # {segment_arena_ptr} is the address of the next SegmentArenaBuiltin.
457                    # memory[{segment_arena_ptr} - 2] is the number of allocated segments.
458                    index = memory[{segment_arena_ptr} - 2]
459
460                    segment_start = __dict_manager.new_default_dict(
461                        segments, 0, temp_segment=index > 0
462                    )
463
464                    # Update '__segment_index_to_arena_index'.
465                    __segment_index_to_arena_index[segment_start.segment_index] = index
466
467                    # Update 'SegmentInfo::start'.
468                    # memory[{segment_arena_ptr} - 3] is the address of the segment arena infos
469                    # segment. index * 3 is added to get the address of the new SegmentInfo.
470                    memory[memory[{segment_arena_ptr} - 3] + index * 3] = segment_start
471                "}
472            }
473            CoreHint::Felt252DictEntryInit { dict_ptr, key } => {
474                let (dict_ptr, key) =
475                    (ResOperandAsAddressFormatter(dict_ptr), ResOperandAsIntegerFormatter(key));
476                formatdoc! {"
477
478                    dict_tracker = __dict_manager.get_tracker({dict_ptr})
479                    dict_tracker.current_ptr += 3
480                    memory[{dict_ptr} + 1] = dict_tracker.data[{key}]
481                "}
482            }
483            CoreHint::Felt252DictEntryUpdate { dict_ptr, value } => {
484                let (dict_ptr, value) =
485                    (ResOperandAsAddressFormatter(dict_ptr), ResOperandAsIntegerFormatter(value));
486                formatdoc! {"
487
488                    dict_tracker = __dict_manager.get_tracker({dict_ptr})
489                    dict_tracker.data[memory[{dict_ptr} - 3]] = {value}
490                "}
491            }
492            CoreHint::TestLessThan { lhs, rhs, dst } => {
493                format!(
494                    "memory{dst} = {} < {}",
495                    ResOperandAsIntegerFormatter(lhs),
496                    ResOperandAsIntegerFormatter(rhs)
497                )
498            }
499            CoreHint::TestLessThanOrEqual { lhs, rhs, dst } => format!(
500                "memory{dst} = {} <= {}",
501                ResOperandAsIntegerFormatter(lhs),
502                ResOperandAsIntegerFormatter(rhs)
503            ),
504            CoreHint::TestLessThanOrEqualAddress { lhs, rhs, dst } => format!(
505                "memory{dst} = {} <= {}",
506                ResOperandAsAddressFormatter(lhs),
507                ResOperandAsAddressFormatter(rhs)
508            ),
509            CoreHint::WideMul128 { lhs, rhs, high, low } => format!(
510                "(memory{high}, memory{low}) = divmod({} * {}, 2**128)",
511                ResOperandAsIntegerFormatter(lhs),
512                ResOperandAsIntegerFormatter(rhs)
513            ),
514            CoreHint::DivMod { lhs, rhs, quotient, remainder } => format!(
515                "(memory{quotient}, memory{remainder}) = divmod({}, {})",
516                ResOperandAsIntegerFormatter(lhs),
517                ResOperandAsIntegerFormatter(rhs)
518            ),
519            CoreHint::Uint256DivMod {
520                dividend0,
521                dividend1,
522                quotient0,
523                quotient1,
524                divisor0,
525                divisor1,
526                remainder0,
527                remainder1,
528            } => {
529                let (dividend0, dividend1, divisor0, divisor1) = (
530                    ResOperandAsIntegerFormatter(dividend0),
531                    ResOperandAsIntegerFormatter(dividend1),
532                    ResOperandAsIntegerFormatter(divisor0),
533                    ResOperandAsIntegerFormatter(divisor1),
534                );
535                formatdoc! {"
536
537                    dividend = {dividend0} + {dividend1} * 2**128
538                    divisor = {divisor0} + {divisor1} * 2**128
539                    quotient, remainder = divmod(dividend, divisor)
540                    memory{quotient0} = quotient & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
541                    memory{quotient1} = quotient >> 128
542                    memory{remainder0} = remainder & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
543                    memory{remainder1} = remainder >> 128
544                "}
545            }
546            CoreHint::Uint512DivModByUint256 {
547                dividend0,
548                dividend1,
549                dividend2,
550                dividend3,
551                divisor0,
552                divisor1,
553                quotient0,
554                quotient1,
555                quotient2,
556                quotient3,
557                remainder0,
558                remainder1,
559            } => {
560                let [dividend0, dividend1, dividend2, dividend3, divisor0, divisor1] =
561                    [dividend0, dividend1, dividend2, dividend3, divisor0, divisor1]
562                        .map(ResOperandAsIntegerFormatter);
563                formatdoc! {"
564
565                    dividend = {dividend0} + {dividend1} * 2**128 + {dividend2} * 2**256 + \
566                     {dividend3} * 2**384
567                    divisor = {divisor0} + {divisor1} * 2**128
568                    quotient, remainder = divmod(dividend, divisor)
569                    memory{quotient0} = quotient & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
570                    memory{quotient1} = (quotient >> 128) & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
571                    memory{quotient2} = (quotient >> 256) & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
572                    memory{quotient3} = quotient >> 384
573                    memory{remainder0} = remainder & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
574                    memory{remainder1} = remainder >> 128
575                "}
576            }
577            CoreHint::SquareRoot { value, dst } => {
578                let value = ResOperandAsIntegerFormatter(value);
579                formatdoc! {"
580
581                    import math
582                    memory{dst} = math.isqrt({value})
583                "}
584            }
585            CoreHint::Uint256SquareRoot {
586                value_low,
587                value_high,
588                sqrt0,
589                sqrt1,
590                remainder_low,
591                remainder_high,
592                sqrt_mul_2_minus_remainder_ge_u128,
593            } => {
594                let (value_low, value_high) = (
595                    ResOperandAsIntegerFormatter(value_low),
596                    ResOperandAsIntegerFormatter(value_high),
597                );
598                formatdoc! {"
599
600                    import math;
601                    value = {value_low} + {value_high} * 2**128
602                    root = math.isqrt(value)
603                    remainder = value - root ** 2
604                    memory{sqrt0} = root & 0xFFFFFFFFFFFFFFFF
605                    memory{sqrt1} = root >> 64
606                    memory{remainder_low} = remainder & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
607                    memory{remainder_high} = remainder >> 128
608                    memory{sqrt_mul_2_minus_remainder_ge_u128} = root * 2 - remainder >= 2**128
609                "}
610            }
611            CoreHint::LinearSplit { value, scalar, max_x, x, y } => {
612                let (value, scalar, max_x) = (
613                    ResOperandAsIntegerFormatter(value),
614                    ResOperandAsIntegerFormatter(scalar),
615                    ResOperandAsIntegerFormatter(max_x),
616                );
617                formatdoc! {"
618
619                    (value, scalar) = ({value}, {scalar})
620                    x = min(value // scalar, {max_x})
621                    y = value - x * scalar
622                    memory{x} = x
623                    memory{y} = y
624                "}
625            }
626            CoreHint::RandomEcPoint { x, y } => {
627                formatdoc! {"
628
629                    from starkware.crypto.signature.signature import ALPHA, BETA, FIELD_PRIME
630                    from starkware.python.math_utils import random_ec_point
631                    (memory{x}, memory{y}) = random_ec_point(FIELD_PRIME, ALPHA, BETA)
632                "}
633            }
634            CoreHint::FieldSqrt { val, sqrt } => {
635                let val = ResOperandAsIntegerFormatter(val);
636                formatdoc! {"
637
638                    from starkware.crypto.signature.signature import FIELD_PRIME
639                    from starkware.python.math_utils import is_quad_residue, sqrt
640
641                    val = {val}
642                    if is_quad_residue(val, FIELD_PRIME):
643                        memory{sqrt} = sqrt(val, FIELD_PRIME)
644                    else:
645                        memory{sqrt} = sqrt(val * 3, FIELD_PRIME)
646                "}
647            }
648            CoreHint::GetCurrentAccessIndex { range_check_ptr } => {
649                let rc = ResOperandAsAddressFormatter(range_check_ptr);
650                formatdoc! {"
651
652                    current_access_indices = sorted(access_indices[key])[::-1]
653                    current_access_index = current_access_indices.pop()
654                    memory[{rc}] = current_access_index
655                "}
656            }
657            CoreHint::ShouldSkipSquashLoop { should_skip_loop } => {
658                format!("memory{should_skip_loop} = 0 if current_access_indices else 1")
659            }
660            CoreHint::GetCurrentAccessDelta { index_delta_minus1 } => formatdoc! {"
661
662                new_access_index = current_access_indices.pop()
663                memory{index_delta_minus1} = new_access_index - current_access_index - 1
664                current_access_index = new_access_index
665            "},
666            CoreHint::ShouldContinueSquashLoop { should_continue } => {
667                format!("memory{should_continue} = 1 if current_access_indices else 0")
668            }
669            CoreHint::GetNextDictKey { next_key } => formatdoc! {"
670                assert len(keys) > 0, 'No keys left but remaining_accesses > 0.'
671                memory{next_key} = key = keys.pop()
672            "},
673            CoreHint::GetSegmentArenaIndex { dict_end_ptr, dict_index } => {
674                let dict_end_ptr = ResOperandAsAddressFormatter(dict_end_ptr);
675                formatdoc! {"
676
677                    memory{dict_index} = __segment_index_to_arena_index[
678                        {dict_end_ptr}.segment_index
679                    ]
680                "}
681            }
682            CoreHint::InitSquashData {
683                dict_accesses,
684                ptr_diff,
685                n_accesses,
686                big_keys,
687                first_key,
688            } => {
689                let (dict_accesses, ptr_diff, n_accesses) = (
690                    ResOperandAsAddressFormatter(dict_accesses),
691                    ResOperandAsIntegerFormatter(ptr_diff),
692                    ResOperandAsIntegerFormatter(n_accesses),
693                );
694                formatdoc! {"
695
696                    dict_access_size = 3
697                    address = {dict_accesses}
698                    assert {ptr_diff} % dict_access_size == 0, 'Accesses array size must be \
699                     divisible by DictAccess.SIZE'
700                    n_accesses = {n_accesses}
701                    if '__squash_dict_max_size' in globals():
702                        assert n_accesses <= __squash_dict_max_size, f'squash_dict() can only be \
703                     used with n_accesses<={{__squash_dict_max_size}}. ' f'Got: \
704                     n_accesses={{n_accesses}}.'
705                    # A map from key to the list of indices accessing it.
706                    access_indices = {{}}
707                    for i in range(n_accesses):
708                        key = memory[address + dict_access_size * i]
709                        access_indices.setdefault(key, []).append(i)
710                    # Descending list of keys.
711                    keys = sorted(access_indices.keys(), reverse=True)
712                    # Are the keys used bigger than range_check bound.
713                    memory{big_keys} = 1 if keys[0] >= range_check_builtin.bound else 0
714                    memory{first_key} = key = keys.pop()
715                "}
716            }
717            CoreHint::AssertLeFindSmallArcs { range_check_ptr, a, b } => {
718                let (range_check_ptr, a, b) = (
719                    ResOperandAsAddressFormatter(range_check_ptr),
720                    ResOperandAsIntegerFormatter(a),
721                    ResOperandAsIntegerFormatter(b),
722                );
723                formatdoc! {"
724
725                    import itertools
726
727                    from starkware.cairo.common.math_utils import assert_integer
728                    assert_integer({a})
729                    assert_integer({b})
730                    a = {a} % PRIME
731                    b = {b} % PRIME
732                    assert a <= b, f'a = {{a}} is not less than or equal to b = {{b}}.'
733
734                    # Find an arc less than PRIME / 3, and another less than PRIME / 2.
735                    lengths_and_indices = [(a, 0), (b - a, 1), (PRIME - 1 - b, 2)]
736                    lengths_and_indices.sort()
737                    assert lengths_and_indices[0][0] <= PRIME // 3 and lengths_and_indices[1][0] \
738                     <= PRIME // 2
739                    excluded = lengths_and_indices[2][1]
740
741                    memory[{range_check_ptr} + 1], memory[{range_check_ptr} + 0] = (
742                        divmod(lengths_and_indices[0][0], 3544607988759775765608368578435044694))
743                    memory[{range_check_ptr} + 3], memory[{range_check_ptr} + 2] = (
744                        divmod(lengths_and_indices[1][0], 5316911983139663648412552867652567041))
745                "}
746            }
747            CoreHint::AssertLeIsFirstArcExcluded { skip_exclude_a_flag } => {
748                format!("memory{skip_exclude_a_flag} = 1 if excluded != 0 else 0",)
749            }
750            CoreHint::AssertLeIsSecondArcExcluded { skip_exclude_b_minus_a } => {
751                format!("memory{skip_exclude_b_minus_a} = 1 if excluded != 1 else 0",)
752            }
753            CoreHint::DebugPrint { start, end } => {
754                let [start, end] = [start, end].map(ResOperandAsAddressFormatter);
755                formatdoc! {"
756
757                    curr = {start}
758                    end = {end}
759                    while curr != end:
760                        print(hex(memory[curr]))
761                        curr += 1
762                "}
763            }
764            CoreHint::AllocConstantSize { size, dst } => {
765                let size = ResOperandAsIntegerFormatter(size);
766                formatdoc! {"
767
768                    if '__boxed_segment' not in globals():
769                        __boxed_segment = segments.add()
770                    memory{dst} = __boxed_segment
771                    __boxed_segment += {size}
772                "}
773            }
774            CoreHint::U256InvModN {
775                b0,
776                b1,
777                n0,
778                n1,
779                g0_or_no_inv,
780                g1_option,
781                s_or_r0,
782                s_or_r1,
783                t_or_k0,
784                t_or_k1,
785            } => {
786                let [b0, b1, n0, n1] = [b0, b1, n0, n1].map(ResOperandAsIntegerFormatter);
787                formatdoc! {"
788
789                    from starkware.python.math_utils import igcdex
790
791                    b = {b0} + ({b1} << 128)
792                    n = {n0} + ({n1} << 128)
793
794                    (_, r, g) = igcdex(n, b)
795                    if n == 1:
796                        memory{g0_or_no_inv} = 1
797                        memory{g1_option} = 0
798                        memory{s_or_r0} = {b0}
799                        memory{s_or_r1} = {b1}
800                        memory{t_or_k0} = 1
801                        memory{t_or_k1} = 0
802                    elif g != 1:
803                        if g % 2 == 0:
804                            g = 2
805                        s = b // g
806                        t = n // g
807                        memory{g0_or_no_inv} = g & 0xffffffffffffffffffffffffffffffff
808                        memory{g1_option} = g >> 128
809                        memory{s_or_r0} = s & 0xffffffffffffffffffffffffffffffff
810                        memory{s_or_r1} = s >> 128
811                        memory{t_or_k0} = t & 0xffffffffffffffffffffffffffffffff
812                        memory{t_or_k1} = t >> 128
813                    else:
814                        r %= n
815                        k = (r * b - 1) // n
816                        memory{g0_or_no_inv} = 0
817                        memory{s_or_r0} = r & 0xffffffffffffffffffffffffffffffff
818                        memory{s_or_r1} = r >> 128
819                        memory{t_or_k0} = k & 0xffffffffffffffffffffffffffffffff
820                        memory{t_or_k1} = k >> 128
821                "}
822            }
823            CoreHint::EvalCircuit { n_add_mods, add_mod_builtin, n_mul_mods, mul_mod_builtin } => {
824                let n_add_mods = ResOperandAsIntegerFormatter(n_add_mods);
825                let add_mod_builtin = ResOperandAsAddressFormatter(add_mod_builtin);
826                let n_mul_mods = ResOperandAsIntegerFormatter(n_mul_mods);
827                let mul_mod_builtin = ResOperandAsAddressFormatter(mul_mod_builtin);
828                formatdoc! {"
829
830                from starkware.cairo.lang.builtins.modulo.mod_builtin_runner import ModBuiltinRunner
831
832                ModBuiltinRunner.fill_memory(
833                        memory=memory,
834                        add_mod=({add_mod_builtin}, builtin_runners[\"add_mod_builtin\"], {n_add_mods}),
835                        mul_mod=({mul_mod_builtin}, builtin_runners[\"mul_mod_builtin\"], {n_mul_mods}),
836                )
837                "}
838            }
839        }
840    }
841}
842
843impl PythonicHint for StarknetHint {
844    fn get_pythonic_hint(&self) -> String {
845        match self {
846            StarknetHint::SystemCall { system } => {
847                format!(
848                    "syscall_handler.syscall(syscall_ptr={})",
849                    ResOperandAsAddressFormatter(system)
850                )
851            }
852            StarknetHint::Cheatcode { .. } => {
853                r#"raise NotImplementedError("Cheatcode")"#.to_string()
854            }
855        }
856    }
857}
858
859impl PythonicHint for ExternalHint {
860    fn get_pythonic_hint(&self) -> String {
861        match self {
862            Self::AddRelocationRule { src, dst } => {
863                let [src, dst] = [src, dst].map(ResOperandAsAddressFormatter);
864                format!("memory.add_relocation_rule(src_ptr={src}, dest_ptr={dst})")
865            }
866            Self::WriteRunParam { index, dst } => {
867                let index = ResOperandAsIntegerFormatter(index);
868                format!("WriteRunParam {{ dst: {dst}, index: {index} }}",)
869            }
870            Self::AddMarker { start, end } => {
871                let [start, end] = [start, end].map(ResOperandAsAddressFormatter);
872                format!("AddMarker {{ start: {start}, end: {end} }}")
873            }
874            Self::Blake2sCompress { state, byte_count, message, output, finalize } => {
875                let [state, byte_count, message, output] =
876                    [state, byte_count, message, output].map(ResOperandAsAddressFormatter);
877                let finalize = ResOperandAsIntegerFormatter(finalize);
878                formatdoc! {"
879                    
880                    Blake2sCompress {{
881                        state: {state},
882                        byte_count: {byte_count},
883                        message: {message},
884                        output: {output},
885                        finalize: {finalize}
886                    }}
887                "}
888            }
889            Self::AddTrace { flag } => {
890                format!("AddTrace {{ flag: {} }}", ResOperandAsIntegerFormatter(flag))
891            }
892        }
893    }
894}
cairo_lang_casm/hints/mod.rs

cairo_lang_casm/hints/
mod.rs
