cairo-native 0.8.0

A compiler to convert Cairo's IR Sierra code to MLIR and execute it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

// Copied from: https://github.com/keep-starknet-strange/alexandria
// License: MIT

//! # Fast power algorithm
use core::ops::DivAssign;

/// Calculate the base ^ power
/// using the fast powering algorithm
/// # Arguments
/// * ` base ` - The base of the exponentiation
/// * ` power ` - The power of the exponentiation
/// # Returns
/// * ` T ` - The result of base ^ power
/// # Panics
/// * ` base ` is 0
pub fn fast_power<
    T,
    +Div<T>,
    +DivAssign<T, T>,
    +Rem<T>,
    +Into<u8, T>,
    +Into<T, u256>,
    +TryInto<u256, T>,
    +PartialEq<T>,
    +Copy<T>,
    +Drop<T>
>(
    base: T, mut power: T
) -> T {
    assert!(base != 0_u8.into(), "fast_power: invalid input");

    let mut base: u256 = base.into();
    let mut result: u256 = 1;

    loop {
        if power % 2_u8.into() != 0_u8.into() {
            result *= base;
        }
        power /= 2_u8.into();
        if (power == 0_u8.into()) {
            break;
        }
        base *= base;
    };

    result.try_into().expect('too large to fit output type')
}

/// Calculate the ( base ^ power ) mod modulus
/// using the fast powering algorithm
/// # Arguments
/// * ` base ` - The base of the exponentiation
/// * ` power ` - The power of the exponentiation
/// * ` modulus ` - The modulus used in the calculation
/// # Returns
/// * ` T ` - The result of ( base ^ power ) mod modulus
/// # Panics
/// * ` base ` is 0
pub fn fast_power_mod<
    T,
    +Div<T>,
    +DivAssign<T, T>,
    +Rem<T>,
    +Into<u8, T>,
    +Into<T, u256>,
    +TryInto<u256, T>,
    +PartialEq<T>,
    +Copy<T>,
    +Drop<T>
>(
    base: T, mut power: T, modulus: T
) -> T {
    assert!(base != 0_u8.into(), "fast_power: invalid input");

    if modulus == 1_u8.into() {
        return 0_u8.into();
    }

    let mut base: u256 = base.into();
    let modulus: u256 = modulus.into();
    let mut result: u256 = 1;

    loop {
        if power % 2_u8.into() != 0_u8.into() {
            result = (result * base) % modulus;
        }
        power /= 2_u8.into();
        if (power == 0_u8.into()) {
            break;
        }
        base = (base * base) % modulus;
    };

    result.try_into().expect('too large to fit output type')
}