cairo_lang_sierra/extensions/modules/int/
unsigned.rs

1use std::marker::PhantomData;
2
3use super::unsigned128::Uint128Type;
4use super::{
5    IntConstLibfunc, IntEqualLibfunc, IntFromFelt252Libfunc, IntMulTraits,
6    IntOperationConcreteLibfunc, IntOperator, IntToFelt252Libfunc, IntTraits, IntType,
7    IntWideMulLibfunc,
8};
9use crate::define_libfunc_hierarchy;
10use crate::extensions::bitwise::BitwiseType;
11use crate::extensions::is_zero::{IsZeroLibfunc, IsZeroTraits};
12use crate::extensions::lib_func::{
13    BranchSignature, DeferredOutputKind, LibfuncSignature, OutputVarInfo, ParamSignature,
14    SierraApChange, SignatureSpecializationContext, SpecializationContext,
15};
16use crate::extensions::non_zero::nonzero_ty;
17use crate::extensions::range_check::RangeCheckType;
18use crate::extensions::{
19    GenericLibfunc, NamedType, NoGenericArgsGenericLibfunc, OutputVarReferenceInfo,
20    SpecializationError,
21};
22use crate::ids::{GenericLibfuncId, GenericTypeId};
23use crate::program::GenericArg;
24
25/// Trait for implementing unsigned integers.
26pub trait UintTraits: IntTraits {
27    /// The generic libfunc id for addition.
28    const OVERFLOWING_ADD: &'static str;
29    /// The generic libfunc id for subtraction.
30    const OVERFLOWING_SUB: &'static str;
31    /// The generic libfunc id for calculating the integer square root.
32    const SQUARE_ROOT: &'static str;
33    /// The generic type id for the type's square root.
34    const SQUARE_ROOT_TYPE_ID: GenericTypeId;
35    /// The generic libfunc id that divides two integers.
36    const DIVMOD: &'static str;
37    /// The generic libfunc id that provides bitwise operations on two integers.
38    const BITWISE: &'static str;
39}
40
41/// Libfunc for integer operations.
42pub struct UintOperationLibfunc<TUintTraits: UintTraits> {
43    pub operator: IntOperator,
44    _phantom: PhantomData<TUintTraits>,
45}
46impl<TUintTraits: UintTraits> UintOperationLibfunc<TUintTraits> {
47    const OVERFLOWING_ADD: &'static str = TUintTraits::OVERFLOWING_ADD;
48    const OVERFLOWING_SUB: &'static str = TUintTraits::OVERFLOWING_SUB;
49    fn new(operator: IntOperator) -> Option<Self> {
50        Some(Self { operator, _phantom: PhantomData })
51    }
52}
53impl<TUintTraits: UintTraits> GenericLibfunc for UintOperationLibfunc<TUintTraits> {
54    type Concrete = IntOperationConcreteLibfunc;
55
56    fn supported_ids() -> Vec<GenericLibfuncId> {
57        vec![
58            GenericLibfuncId::from(Self::OVERFLOWING_ADD),
59            GenericLibfuncId::from(Self::OVERFLOWING_SUB),
60        ]
61    }
62
63    fn by_id(id: &GenericLibfuncId) -> Option<Self> {
64        match id.0.as_str() {
65            id if id == Self::OVERFLOWING_ADD => Self::new(IntOperator::OverflowingAdd),
66            id if id == Self::OVERFLOWING_SUB => Self::new(IntOperator::OverflowingSub),
67            _ => None,
68        }
69    }
70
71    fn specialize_signature(
72        &self,
73        context: &dyn SignatureSpecializationContext,
74        args: &[GenericArg],
75    ) -> Result<LibfuncSignature, SpecializationError> {
76        if !args.is_empty() {
77            return Err(SpecializationError::WrongNumberOfGenericArgs);
78        }
79        let ty = context.get_concrete_type(TUintTraits::GENERIC_TYPE_ID, &[])?;
80        let range_check_type = context.get_concrete_type(RangeCheckType::id(), &[])?;
81
82        let wrapping_result_ref_info = match (self.operator, TUintTraits::IS_SMALL) {
83            (IntOperator::OverflowingSub, true) => {
84                OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic)
85            }
86            (IntOperator::OverflowingAdd, false)
87            | (IntOperator::OverflowingAdd, true)
88            | (IntOperator::OverflowingSub, false) => OutputVarReferenceInfo::NewTempVar { idx: 0 },
89        };
90
91        let rc_output_info = OutputVarInfo::new_builtin(range_check_type.clone(), 0);
92        let ty_param = ParamSignature::new(ty.clone());
93        Ok(LibfuncSignature {
94            param_signatures: vec![
95                ParamSignature::new(range_check_type).with_allow_add_const(),
96                ty_param.clone(),
97                ty_param,
98            ],
99            branch_signatures: vec![
100                BranchSignature {
101                    vars: vec![rc_output_info.clone(), OutputVarInfo {
102                        ty: ty.clone(),
103                        ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
104                    }],
105                    ap_change: SierraApChange::Known { new_vars_only: false },
106                },
107                BranchSignature {
108                    vars: vec![rc_output_info, OutputVarInfo {
109                        ty,
110                        ref_info: wrapping_result_ref_info,
111                    }],
112                    ap_change: SierraApChange::Known { new_vars_only: false },
113                },
114            ],
115            fallthrough: Some(0),
116        })
117    }
118
119    fn specialize(
120        &self,
121        context: &dyn SpecializationContext,
122        args: &[GenericArg],
123    ) -> Result<Self::Concrete, SpecializationError> {
124        Ok(IntOperationConcreteLibfunc {
125            operator: self.operator,
126            signature: self.specialize_signature(context.upcast(), args)?,
127        })
128    }
129}
130
131/// Libfunc for calculating uint's square root.
132#[derive(Default)]
133pub struct UintSquareRootLibfunc<TUintTraits: UintTraits> {
134    _phantom: PhantomData<TUintTraits>,
135}
136impl<TUintTraits: UintTraits> NoGenericArgsGenericLibfunc for UintSquareRootLibfunc<TUintTraits> {
137    const STR_ID: &'static str = TUintTraits::SQUARE_ROOT;
138
139    fn specialize_signature(
140        &self,
141        context: &dyn SignatureSpecializationContext,
142    ) -> Result<LibfuncSignature, SpecializationError> {
143        let ty = context.get_concrete_type(TUintTraits::GENERIC_TYPE_ID, &[])?;
144        let sqrt_ty = context.get_concrete_type(TUintTraits::SQUARE_ROOT_TYPE_ID, &[])?;
145        let range_check_type = context.get_concrete_type(RangeCheckType::id(), &[])?;
146        Ok(LibfuncSignature::new_non_branch_ex(
147            vec![
148                ParamSignature::new(range_check_type.clone()).with_allow_add_const(),
149                ParamSignature::new(ty),
150            ],
151            vec![OutputVarInfo::new_builtin(range_check_type, 0), OutputVarInfo {
152                ty: sqrt_ty,
153                ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
154            }],
155            SierraApChange::Known { new_vars_only: false },
156        ))
157    }
158}
159
160/// Libfunc for uint divmod.
161#[derive(Default)]
162pub struct UintDivmodLibfunc<TUintTraits: UintTraits> {
163    _phantom: PhantomData<TUintTraits>,
164}
165impl<TUintTraits: UintTraits> NoGenericArgsGenericLibfunc for UintDivmodLibfunc<TUintTraits> {
166    const STR_ID: &'static str = TUintTraits::DIVMOD;
167
168    fn specialize_signature(
169        &self,
170        context: &dyn SignatureSpecializationContext,
171    ) -> Result<LibfuncSignature, SpecializationError> {
172        let ty = context.get_concrete_type(TUintTraits::GENERIC_TYPE_ID, &[])?;
173        let range_check_type = context.get_concrete_type(RangeCheckType::id(), &[])?;
174        Ok(LibfuncSignature::new_non_branch_ex(
175            vec![
176                ParamSignature::new(range_check_type.clone()).with_allow_add_const(),
177                ParamSignature::new(ty.clone()),
178                ParamSignature::new(nonzero_ty(context, &ty)?),
179            ],
180            vec![
181                OutputVarInfo::new_builtin(range_check_type, 0),
182                OutputVarInfo {
183                    ty: ty.clone(),
184                    ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
185                },
186                OutputVarInfo { ty, ref_info: OutputVarReferenceInfo::NewTempVar { idx: 1 } },
187            ],
188            SierraApChange::Known { new_vars_only: false },
189        ))
190    }
191}
192
193/// Libfunc for computing the Bitwise (and,or,xor) of two uints.
194/// Returns 3 uints (and the updated builtin pointer).
195#[derive(Default)]
196pub struct UintBitwiseLibfunc<TUintTraits: UintTraits> {
197    _phantom: PhantomData<TUintTraits>,
198}
199impl<TUintTraits: UintTraits> NoGenericArgsGenericLibfunc for UintBitwiseLibfunc<TUintTraits> {
200    const STR_ID: &'static str = TUintTraits::BITWISE;
201
202    fn specialize_signature(
203        &self,
204        context: &dyn SignatureSpecializationContext,
205    ) -> Result<LibfuncSignature, SpecializationError> {
206        let bitwise_ty = context.get_concrete_type(BitwiseType::id(), &[])?;
207        let ty = context.get_concrete_type(TUintTraits::GENERIC_TYPE_ID, &[])?;
208        let deferred_ty_output_info = OutputVarInfo {
209            ty: ty.clone(),
210            ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
211        };
212        let ty_param = ParamSignature::new(ty);
213        Ok(LibfuncSignature::new_non_branch_ex(
214            vec![
215                ParamSignature::new(bitwise_ty.clone()).with_allow_add_const(),
216                ty_param.clone(),
217                ty_param,
218            ],
219            vec![
220                OutputVarInfo::new_builtin(bitwise_ty, 0),
221                deferred_ty_output_info.clone(),
222                deferred_ty_output_info.clone(),
223                deferred_ty_output_info,
224            ],
225            SierraApChange::Known { new_vars_only: true },
226        ))
227    }
228}
229
230define_libfunc_hierarchy! {
231    pub enum UintLibfunc<TUintTraits: UintTraits + IntMulTraits + IsZeroTraits> {
232        Const(IntConstLibfunc<TUintTraits>),
233        Operation(UintOperationLibfunc<TUintTraits>),
234        SquareRoot(UintSquareRootLibfunc<TUintTraits>),
235        Equal(IntEqualLibfunc<TUintTraits>),
236        ToFelt252(IntToFelt252Libfunc<TUintTraits>),
237        FromFelt252(IntFromFelt252Libfunc<TUintTraits>),
238        IsZero(IsZeroLibfunc<TUintTraits>),
239        Divmod(UintDivmodLibfunc<TUintTraits>),
240        WideMul(IntWideMulLibfunc<TUintTraits>),
241        Bitwise(UintBitwiseLibfunc<TUintTraits>),
242    }, UintConcrete
243}
244
245#[derive(Default)]
246pub struct Uint8Traits;
247
248impl IntTraits for Uint8Traits {
249    type IntType = u8;
250    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u8");
251    const IS_SMALL: bool = true;
252    const CONST: &'static str = "u8_const";
253    const EQUAL: &'static str = "u8_eq";
254    const TO_FELT252: &'static str = "u8_to_felt252";
255    const TRY_FROM_FELT252: &'static str = "u8_try_from_felt252";
256}
257
258impl UintTraits for Uint8Traits {
259    const OVERFLOWING_ADD: &'static str = "u8_overflowing_add";
260    const OVERFLOWING_SUB: &'static str = "u8_overflowing_sub";
261    const SQUARE_ROOT: &'static str = "u8_sqrt";
262    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Self as IntTraits>::GENERIC_TYPE_ID;
263    const DIVMOD: &'static str = "u8_safe_divmod";
264    const BITWISE: &'static str = "u8_bitwise";
265}
266
267impl IntMulTraits for Uint8Traits {
268    const WIDE_MUL: &'static str = "u8_wide_mul";
269    const WIDE_MUL_RES_TYPE_ID: GenericTypeId = <Uint16Type as NamedType>::ID;
270}
271
272impl IsZeroTraits for Uint8Traits {
273    const IS_ZERO: &'static str = "u8_is_zero";
274    const GENERIC_TYPE_ID: GenericTypeId = <Uint8Type as NamedType>::ID;
275}
276
277/// Type for u8.
278pub type Uint8Type = IntType<Uint8Traits>;
279pub type Uint8Libfunc = UintLibfunc<Uint8Traits>;
280pub type Uint8Concrete = <Uint8Libfunc as GenericLibfunc>::Concrete;
281
282#[derive(Default)]
283pub struct Uint16Traits;
284
285impl IntTraits for Uint16Traits {
286    type IntType = u16;
287    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u16");
288    const IS_SMALL: bool = true;
289    const CONST: &'static str = "u16_const";
290    const EQUAL: &'static str = "u16_eq";
291    const TO_FELT252: &'static str = "u16_to_felt252";
292    const TRY_FROM_FELT252: &'static str = "u16_try_from_felt252";
293}
294
295impl UintTraits for Uint16Traits {
296    const OVERFLOWING_ADD: &'static str = "u16_overflowing_add";
297    const OVERFLOWING_SUB: &'static str = "u16_overflowing_sub";
298    const SQUARE_ROOT: &'static str = "u16_sqrt";
299    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Uint8Type as NamedType>::ID;
300    const DIVMOD: &'static str = "u16_safe_divmod";
301    const BITWISE: &'static str = "u16_bitwise";
302}
303
304impl IntMulTraits for Uint16Traits {
305    const WIDE_MUL: &'static str = "u16_wide_mul";
306    const WIDE_MUL_RES_TYPE_ID: GenericTypeId = <Uint32Type as NamedType>::ID;
307}
308
309impl IsZeroTraits for Uint16Traits {
310    const IS_ZERO: &'static str = "u16_is_zero";
311    const GENERIC_TYPE_ID: GenericTypeId = <Uint16Type as NamedType>::ID;
312}
313
314/// Type for u16.
315pub type Uint16Type = IntType<Uint16Traits>;
316pub type Uint16Libfunc = UintLibfunc<Uint16Traits>;
317pub type Uint16Concrete = <Uint16Libfunc as GenericLibfunc>::Concrete;
318
319#[derive(Default)]
320pub struct Uint32Traits;
321
322impl IntTraits for Uint32Traits {
323    type IntType = u32;
324    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u32");
325    const IS_SMALL: bool = true;
326    const CONST: &'static str = "u32_const";
327    const EQUAL: &'static str = "u32_eq";
328    const TO_FELT252: &'static str = "u32_to_felt252";
329    const TRY_FROM_FELT252: &'static str = "u32_try_from_felt252";
330}
331
332impl UintTraits for Uint32Traits {
333    const OVERFLOWING_ADD: &'static str = "u32_overflowing_add";
334    const OVERFLOWING_SUB: &'static str = "u32_overflowing_sub";
335    const SQUARE_ROOT: &'static str = "u32_sqrt";
336    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Uint16Type as NamedType>::ID;
337    const DIVMOD: &'static str = "u32_safe_divmod";
338    const BITWISE: &'static str = "u32_bitwise";
339}
340
341impl IntMulTraits for Uint32Traits {
342    const WIDE_MUL: &'static str = "u32_wide_mul";
343    const WIDE_MUL_RES_TYPE_ID: GenericTypeId = <Uint64Type as NamedType>::ID;
344}
345
346impl IsZeroTraits for Uint32Traits {
347    const IS_ZERO: &'static str = "u32_is_zero";
348    const GENERIC_TYPE_ID: GenericTypeId = <Uint32Type as NamedType>::ID;
349}
350
351/// Type for u32.
352pub type Uint32Type = IntType<Uint32Traits>;
353pub type Uint32Libfunc = UintLibfunc<Uint32Traits>;
354pub type Uint32Concrete = <Uint32Libfunc as GenericLibfunc>::Concrete;
355
356#[derive(Default)]
357pub struct Uint64Traits;
358
359impl IntTraits for Uint64Traits {
360    type IntType = u64;
361    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u64");
362    const IS_SMALL: bool = true;
363    const CONST: &'static str = "u64_const";
364    const EQUAL: &'static str = "u64_eq";
365    const TO_FELT252: &'static str = "u64_to_felt252";
366    const TRY_FROM_FELT252: &'static str = "u64_try_from_felt252";
367}
368
369impl UintTraits for Uint64Traits {
370    const OVERFLOWING_ADD: &'static str = "u64_overflowing_add";
371    const OVERFLOWING_SUB: &'static str = "u64_overflowing_sub";
372    const SQUARE_ROOT: &'static str = "u64_sqrt";
373    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Uint32Type as NamedType>::ID;
374    const DIVMOD: &'static str = "u64_safe_divmod";
375    const BITWISE: &'static str = "u64_bitwise";
376}
377
378impl IntMulTraits for Uint64Traits {
379    const WIDE_MUL: &'static str = "u64_wide_mul";
380    const WIDE_MUL_RES_TYPE_ID: GenericTypeId = <Uint128Type as NamedType>::ID;
381}
382
383impl IsZeroTraits for Uint64Traits {
384    const IS_ZERO: &'static str = "u64_is_zero";
385    const GENERIC_TYPE_ID: GenericTypeId = <Uint64Type as NamedType>::ID;
386}
387
388/// Type for u64.
389pub type Uint64Type = IntType<Uint64Traits>;
390pub type Uint64Libfunc = UintLibfunc<Uint64Traits>;
391pub type Uint64Concrete = <Uint64Libfunc as GenericLibfunc>::Concrete;
cairo_lang_sierra/extensions/modules/int/unsigned.rs

cairo_lang_sierra/extensions/modules/int/
unsigned.rs
