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

cairo_lang_casm/hints/
mod.rs
