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

cairo_lang_casm/hints/
mod.rs
