cairo_lang_casm/hints/
mod.rs

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

cairo_lang_casm/hints/
mod.rs
