cairo_lang_sierra/extensions/modules/int/
unsigned128.rs

1use super::unsigned::{
2    Uint64Type, UintBitwiseLibfunc, UintDivmodLibfunc, UintOperationLibfunc, UintSquareRootLibfunc,
3    UintTraits,
4};
5use super::{IntConstLibfunc, IntEqualLibfunc, IntToFelt252Libfunc, IntTraits, IntType};
6use crate::define_libfunc_hierarchy;
7use crate::extensions::bitwise::BitwiseType;
8use crate::extensions::felt252::Felt252Type;
9use crate::extensions::is_zero::{IsZeroLibfunc, IsZeroTraits};
10use crate::extensions::lib_func::{
11    BranchSignature, DeferredOutputKind, LibfuncSignature, OutputVarInfo, ParamSignature,
12    SierraApChange, SignatureSpecializationContext,
13};
14use crate::extensions::range_check::RangeCheckType;
15use crate::extensions::{
16    NamedType, NoGenericArgsGenericLibfunc, NoGenericArgsGenericType, OutputVarReferenceInfo,
17    SpecializationError,
18};
19use crate::ids::GenericTypeId;
20
21/// Type for u128.
22pub type Uint128Type = IntType<Uint128Traits>;
23
24/// A type that contains 4 u128s (a, b, c, d) and guarantees that `a * b = 2**128 * c + d`.
25///
26/// The guarantee is verified by `u128_mul_guarantee_verify`, which is the only way to destruct this
27/// type. This way, one can trust that the guarantee holds although it has not yet been verified.
28#[derive(Default)]
29pub struct U128MulGuaranteeType;
30impl NoGenericArgsGenericType for U128MulGuaranteeType {
31    const ID: GenericTypeId = GenericTypeId::new_inline("U128MulGuarantee");
32    const STORABLE: bool = true;
33    const DUPLICATABLE: bool = false;
34    const DROPPABLE: bool = false;
35    const ZERO_SIZED: bool = false;
36}
37
38define_libfunc_hierarchy! {
39    pub enum Uint128Libfunc {
40        Operation(UintOperationLibfunc<Uint128Traits>),
41        Divmod(UintDivmodLibfunc<Uint128Traits>),
42        GuaranteeMul(U128GuaranteeMulLibfunc),
43        MulGuaranteeVerify(U128MulGuaranteeVerifyLibfunc),
44        Equal(IntEqualLibfunc<Uint128Traits>),
45        SquareRoot(UintSquareRootLibfunc<Uint128Traits>),
46        Const(IntConstLibfunc<Uint128Traits>),
47        FromFelt252(Uint128sFromFelt252Libfunc),
48        ToFelt252(IntToFelt252Libfunc<Uint128Traits>),
49        IsZero(IsZeroLibfunc<Uint128Traits>),
50        Bitwise(UintBitwiseLibfunc<Uint128Traits>),
51        ByteReverse(U128ByteReverseLibfunc),
52    }, Uint128Concrete
53}
54
55#[derive(Default)]
56pub struct Uint128Traits;
57
58impl IntTraits for Uint128Traits {
59    type IntType = u128;
60    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u128");
61    const IS_SMALL: bool = false;
62    const CONST: &'static str = "u128_const";
63    const EQUAL: &'static str = "u128_eq";
64    const TO_FELT252: &'static str = "u128_to_felt252";
65    const TRY_FROM_FELT252: &'static str = "u128_try_from_felt252";
66}
67
68impl UintTraits for Uint128Traits {
69    const OVERFLOWING_ADD: &'static str = "u128_overflowing_add";
70    const OVERFLOWING_SUB: &'static str = "u128_overflowing_sub";
71    const SQUARE_ROOT: &'static str = "u128_sqrt";
72    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Uint64Type as NamedType>::ID;
73    const DIVMOD: &'static str = "u128_safe_divmod";
74    const BITWISE: &'static str = "bitwise";
75}
76
77impl IsZeroTraits for Uint128Traits {
78    const IS_ZERO: &'static str = "u128_is_zero";
79    const GENERIC_TYPE_ID: GenericTypeId = <Uint128Type as NamedType>::ID;
80}
81
82/// Libfunc for u128_guarantee_mul.
83#[derive(Default)]
84pub struct U128GuaranteeMulLibfunc {}
85impl NoGenericArgsGenericLibfunc for U128GuaranteeMulLibfunc {
86    const STR_ID: &'static str = "u128_guarantee_mul";
87
88    fn specialize_signature(
89        &self,
90        context: &dyn SignatureSpecializationContext,
91    ) -> Result<LibfuncSignature, SpecializationError> {
92        let u128_type = context.get_concrete_type(Uint128Type::id(), &[])?;
93        Ok(LibfuncSignature::new_non_branch_ex(
94            vec![ParamSignature::new(u128_type.clone()), ParamSignature::new(u128_type.clone())],
95            vec![
96                // High.
97                OutputVarInfo {
98                    ty: u128_type.clone(),
99                    ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
100                },
101                // Low.
102                OutputVarInfo {
103                    ty: u128_type,
104                    ref_info: OutputVarReferenceInfo::NewTempVar { idx: 1 },
105                },
106                // Guarantee.
107                OutputVarInfo {
108                    ty: context.get_concrete_type(U128MulGuaranteeType::id(), &[])?,
109                    ref_info: OutputVarReferenceInfo::SimpleDerefs,
110                },
111            ],
112            SierraApChange::Known { new_vars_only: true },
113        ))
114    }
115}
116
117/// Libfunc for u128_mul_guarantee_verify.
118#[derive(Default)]
119pub struct U128MulGuaranteeVerifyLibfunc {}
120impl NoGenericArgsGenericLibfunc for U128MulGuaranteeVerifyLibfunc {
121    const STR_ID: &'static str = "u128_mul_guarantee_verify";
122
123    fn specialize_signature(
124        &self,
125        context: &dyn SignatureSpecializationContext,
126    ) -> Result<LibfuncSignature, SpecializationError> {
127        let range_check_type = context.get_concrete_type(RangeCheckType::id(), &[])?;
128        Ok(LibfuncSignature::new_non_branch_ex(
129            vec![
130                ParamSignature::new(range_check_type.clone()).with_allow_add_const(),
131                ParamSignature::new(context.get_concrete_type(U128MulGuaranteeType::id(), &[])?),
132            ],
133            vec![OutputVarInfo::new_builtin(range_check_type, 0)],
134            SierraApChange::Known { new_vars_only: false },
135        ))
136    }
137}
138
139/// Libfunc for converting a felt252 into a u128, or the number and the overflow in the case of
140/// failure.
141#[derive(Default)]
142pub struct Uint128sFromFelt252Libfunc {}
143impl NoGenericArgsGenericLibfunc for Uint128sFromFelt252Libfunc {
144    const STR_ID: &'static str = "u128s_from_felt252";
145
146    fn specialize_signature(
147        &self,
148        context: &dyn SignatureSpecializationContext,
149    ) -> Result<LibfuncSignature, SpecializationError> {
150        let range_check_type = context.get_concrete_type(RangeCheckType::id(), &[])?;
151        let rc_output_info = OutputVarInfo::new_builtin(range_check_type.clone(), 0);
152        Ok(LibfuncSignature {
153            param_signatures: vec![
154                ParamSignature::new(range_check_type).with_allow_add_const(),
155                ParamSignature::new(context.get_concrete_type(Felt252Type::id(), &[])?),
156            ],
157            branch_signatures: vec![
158                BranchSignature {
159                    vars: vec![
160                        rc_output_info.clone(),
161                        OutputVarInfo {
162                            ty: context.get_concrete_type(Uint128Type::id(), &[])?,
163                            ref_info: OutputVarReferenceInfo::SameAsParam { param_idx: 1 },
164                        },
165                    ],
166                    ap_change: SierraApChange::Known { new_vars_only: false },
167                },
168                BranchSignature {
169                    vars: vec![
170                        rc_output_info,
171                        OutputVarInfo {
172                            ty: context.get_concrete_type(Uint128Type::id(), &[])?,
173                            ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
174                        },
175                        OutputVarInfo {
176                            ty: context.get_concrete_type(Uint128Type::id(), &[])?,
177                            ref_info: OutputVarReferenceInfo::NewTempVar { idx: 1 },
178                        },
179                    ],
180                    ap_change: SierraApChange::Known { new_vars_only: false },
181                },
182            ],
183            fallthrough: Some(0),
184        })
185    }
186}
187
188/// Libfunc for reversing the byte order of a u128.
189/// Returns a u128 (and the updated builtin pointer).
190#[derive(Default)]
191pub struct U128ByteReverseLibfunc {}
192impl NoGenericArgsGenericLibfunc for U128ByteReverseLibfunc {
193    const STR_ID: &'static str = "u128_byte_reverse";
194
195    fn specialize_signature(
196        &self,
197        context: &dyn SignatureSpecializationContext,
198    ) -> Result<LibfuncSignature, SpecializationError> {
199        let bitwise_ty = context.get_concrete_type(BitwiseType::id(), &[])?;
200        let u128_ty = context.get_concrete_type(Uint128Type::id(), &[])?;
201        Ok(LibfuncSignature::new_non_branch_ex(
202            vec![
203                ParamSignature::new(bitwise_ty.clone()).with_allow_add_const(),
204                ParamSignature::new(u128_ty.clone()),
205            ],
206            vec![
207                // bitwise
208                OutputVarInfo::new_builtin(bitwise_ty, 0),
209                // result
210                OutputVarInfo {
211                    ty: u128_ty,
212                    ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
213                },
214            ],
215            SierraApChange::Known { new_vars_only: false },
216        ))
217    }
218}
cairo_lang_sierra/extensions/modules/int/unsigned128.rs

cairo_lang_sierra/extensions/modules/int/
unsigned128.rs
