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![
102                        rc_output_info.clone(),
103                        OutputVarInfo {
104                            ty: ty.clone(),
105                            ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
106                        },
107                    ],
108                    ap_change: SierraApChange::Known { new_vars_only: false },
109                },
110                BranchSignature {
111                    vars: vec![
112                        rc_output_info,
113                        OutputVarInfo { ty, ref_info: wrapping_result_ref_info },
114                    ],
115                    ap_change: SierraApChange::Known { new_vars_only: false },
116                },
117            ],
118            fallthrough: Some(0),
119        })
120    }
121
122    fn specialize(
123        &self,
124        context: &dyn SpecializationContext,
125        args: &[GenericArg],
126    ) -> Result<Self::Concrete, SpecializationError> {
127        Ok(IntOperationConcreteLibfunc {
128            operator: self.operator,
129            signature: self.specialize_signature(context.upcast(), args)?,
130        })
131    }
132}
133
134/// Libfunc for calculating uint's square root.
135#[derive(Default)]
136pub struct UintSquareRootLibfunc<TUintTraits: UintTraits> {
137    _phantom: PhantomData<TUintTraits>,
138}
139impl<TUintTraits: UintTraits> NoGenericArgsGenericLibfunc for UintSquareRootLibfunc<TUintTraits> {
140    const STR_ID: &'static str = TUintTraits::SQUARE_ROOT;
141
142    fn specialize_signature(
143        &self,
144        context: &dyn SignatureSpecializationContext,
145    ) -> Result<LibfuncSignature, SpecializationError> {
146        let ty = context.get_concrete_type(TUintTraits::GENERIC_TYPE_ID, &[])?;
147        let sqrt_ty = context.get_concrete_type(TUintTraits::SQUARE_ROOT_TYPE_ID, &[])?;
148        let range_check_type = context.get_concrete_type(RangeCheckType::id(), &[])?;
149        Ok(LibfuncSignature::new_non_branch_ex(
150            vec![
151                ParamSignature::new(range_check_type.clone()).with_allow_add_const(),
152                ParamSignature::new(ty),
153            ],
154            vec![
155                OutputVarInfo::new_builtin(range_check_type, 0),
156                OutputVarInfo {
157                    ty: sqrt_ty,
158                    ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
159                },
160            ],
161            SierraApChange::Known { new_vars_only: false },
162        ))
163    }
164}
165
166/// Libfunc for uint divmod.
167#[derive(Default)]
168pub struct UintDivmodLibfunc<TUintTraits: UintTraits> {
169    _phantom: PhantomData<TUintTraits>,
170}
171impl<TUintTraits: UintTraits> NoGenericArgsGenericLibfunc for UintDivmodLibfunc<TUintTraits> {
172    const STR_ID: &'static str = TUintTraits::DIVMOD;
173
174    fn specialize_signature(
175        &self,
176        context: &dyn SignatureSpecializationContext,
177    ) -> Result<LibfuncSignature, SpecializationError> {
178        let ty = context.get_concrete_type(TUintTraits::GENERIC_TYPE_ID, &[])?;
179        let range_check_type = context.get_concrete_type(RangeCheckType::id(), &[])?;
180        Ok(LibfuncSignature::new_non_branch_ex(
181            vec![
182                ParamSignature::new(range_check_type.clone()).with_allow_add_const(),
183                ParamSignature::new(ty.clone()),
184                ParamSignature::new(nonzero_ty(context, &ty)?),
185            ],
186            vec![
187                OutputVarInfo::new_builtin(range_check_type, 0),
188                OutputVarInfo {
189                    ty: ty.clone(),
190                    ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
191                },
192                OutputVarInfo { ty, ref_info: OutputVarReferenceInfo::NewTempVar { idx: 1 } },
193            ],
194            SierraApChange::Known { new_vars_only: false },
195        ))
196    }
197}
198
199/// Libfunc for computing the Bitwise (and,or,xor) of two uints.
200/// Returns 3 uints (and the updated builtin pointer).
201#[derive(Default)]
202pub struct UintBitwiseLibfunc<TUintTraits: UintTraits> {
203    _phantom: PhantomData<TUintTraits>,
204}
205impl<TUintTraits: UintTraits> NoGenericArgsGenericLibfunc for UintBitwiseLibfunc<TUintTraits> {
206    const STR_ID: &'static str = TUintTraits::BITWISE;
207
208    fn specialize_signature(
209        &self,
210        context: &dyn SignatureSpecializationContext,
211    ) -> Result<LibfuncSignature, SpecializationError> {
212        let bitwise_ty = context.get_concrete_type(BitwiseType::id(), &[])?;
213        let ty = context.get_concrete_type(TUintTraits::GENERIC_TYPE_ID, &[])?;
214        let deferred_ty_output_info = OutputVarInfo {
215            ty: ty.clone(),
216            ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
217        };
218        let ty_param = ParamSignature::new(ty);
219        Ok(LibfuncSignature::new_non_branch_ex(
220            vec![
221                ParamSignature::new(bitwise_ty.clone()).with_allow_add_const(),
222                ty_param.clone(),
223                ty_param,
224            ],
225            vec![
226                OutputVarInfo::new_builtin(bitwise_ty, 0),
227                deferred_ty_output_info.clone(),
228                deferred_ty_output_info.clone(),
229                deferred_ty_output_info,
230            ],
231            SierraApChange::Known { new_vars_only: true },
232        ))
233    }
234}
235
236define_libfunc_hierarchy! {
237    pub enum UintLibfunc<TUintTraits: UintTraits + IntMulTraits + IsZeroTraits> {
238        Const(IntConstLibfunc<TUintTraits>),
239        Operation(UintOperationLibfunc<TUintTraits>),
240        SquareRoot(UintSquareRootLibfunc<TUintTraits>),
241        Equal(IntEqualLibfunc<TUintTraits>),
242        ToFelt252(IntToFelt252Libfunc<TUintTraits>),
243        FromFelt252(IntFromFelt252Libfunc<TUintTraits>),
244        IsZero(IsZeroLibfunc<TUintTraits>),
245        Divmod(UintDivmodLibfunc<TUintTraits>),
246        WideMul(IntWideMulLibfunc<TUintTraits>),
247        Bitwise(UintBitwiseLibfunc<TUintTraits>),
248    }, UintConcrete
249}
250
251#[derive(Default)]
252pub struct Uint8Traits;
253
254impl IntTraits for Uint8Traits {
255    type IntType = u8;
256    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u8");
257    const IS_SMALL: bool = true;
258    const CONST: &'static str = "u8_const";
259    const EQUAL: &'static str = "u8_eq";
260    const TO_FELT252: &'static str = "u8_to_felt252";
261    const TRY_FROM_FELT252: &'static str = "u8_try_from_felt252";
262}
263
264impl UintTraits for Uint8Traits {
265    const OVERFLOWING_ADD: &'static str = "u8_overflowing_add";
266    const OVERFLOWING_SUB: &'static str = "u8_overflowing_sub";
267    const SQUARE_ROOT: &'static str = "u8_sqrt";
268    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Self as IntTraits>::GENERIC_TYPE_ID;
269    const DIVMOD: &'static str = "u8_safe_divmod";
270    const BITWISE: &'static str = "u8_bitwise";
271}
272
273impl IntMulTraits for Uint8Traits {
274    const WIDE_MUL: &'static str = "u8_wide_mul";
275    const WIDE_MUL_RES_TYPE_ID: GenericTypeId = <Uint16Type as NamedType>::ID;
276}
277
278impl IsZeroTraits for Uint8Traits {
279    const IS_ZERO: &'static str = "u8_is_zero";
280    const GENERIC_TYPE_ID: GenericTypeId = <Uint8Type as NamedType>::ID;
281}
282
283/// Type for u8.
284pub type Uint8Type = IntType<Uint8Traits>;
285pub type Uint8Libfunc = UintLibfunc<Uint8Traits>;
286pub type Uint8Concrete = <Uint8Libfunc as GenericLibfunc>::Concrete;
287
288#[derive(Default)]
289pub struct Uint16Traits;
290
291impl IntTraits for Uint16Traits {
292    type IntType = u16;
293    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u16");
294    const IS_SMALL: bool = true;
295    const CONST: &'static str = "u16_const";
296    const EQUAL: &'static str = "u16_eq";
297    const TO_FELT252: &'static str = "u16_to_felt252";
298    const TRY_FROM_FELT252: &'static str = "u16_try_from_felt252";
299}
300
301impl UintTraits for Uint16Traits {
302    const OVERFLOWING_ADD: &'static str = "u16_overflowing_add";
303    const OVERFLOWING_SUB: &'static str = "u16_overflowing_sub";
304    const SQUARE_ROOT: &'static str = "u16_sqrt";
305    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Uint8Type as NamedType>::ID;
306    const DIVMOD: &'static str = "u16_safe_divmod";
307    const BITWISE: &'static str = "u16_bitwise";
308}
309
310impl IntMulTraits for Uint16Traits {
311    const WIDE_MUL: &'static str = "u16_wide_mul";
312    const WIDE_MUL_RES_TYPE_ID: GenericTypeId = <Uint32Type as NamedType>::ID;
313}
314
315impl IsZeroTraits for Uint16Traits {
316    const IS_ZERO: &'static str = "u16_is_zero";
317    const GENERIC_TYPE_ID: GenericTypeId = <Uint16Type as NamedType>::ID;
318}
319
320/// Type for u16.
321pub type Uint16Type = IntType<Uint16Traits>;
322pub type Uint16Libfunc = UintLibfunc<Uint16Traits>;
323pub type Uint16Concrete = <Uint16Libfunc as GenericLibfunc>::Concrete;
324
325#[derive(Default)]
326pub struct Uint32Traits;
327
328impl IntTraits for Uint32Traits {
329    type IntType = u32;
330    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u32");
331    const IS_SMALL: bool = true;
332    const CONST: &'static str = "u32_const";
333    const EQUAL: &'static str = "u32_eq";
334    const TO_FELT252: &'static str = "u32_to_felt252";
335    const TRY_FROM_FELT252: &'static str = "u32_try_from_felt252";
336}
337
338impl UintTraits for Uint32Traits {
339    const OVERFLOWING_ADD: &'static str = "u32_overflowing_add";
340    const OVERFLOWING_SUB: &'static str = "u32_overflowing_sub";
341    const SQUARE_ROOT: &'static str = "u32_sqrt";
342    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Uint16Type as NamedType>::ID;
343    const DIVMOD: &'static str = "u32_safe_divmod";
344    const BITWISE: &'static str = "u32_bitwise";
345}
346
347impl IntMulTraits for Uint32Traits {
348    const WIDE_MUL: &'static str = "u32_wide_mul";
349    const WIDE_MUL_RES_TYPE_ID: GenericTypeId = <Uint64Type as NamedType>::ID;
350}
351
352impl IsZeroTraits for Uint32Traits {
353    const IS_ZERO: &'static str = "u32_is_zero";
354    const GENERIC_TYPE_ID: GenericTypeId = <Uint32Type as NamedType>::ID;
355}
356
357/// Type for u32.
358pub type Uint32Type = IntType<Uint32Traits>;
359pub type Uint32Libfunc = UintLibfunc<Uint32Traits>;
360pub type Uint32Concrete = <Uint32Libfunc as GenericLibfunc>::Concrete;
361
362#[derive(Default)]
363pub struct Uint64Traits;
364
365impl IntTraits for Uint64Traits {
366    type IntType = u64;
367    const GENERIC_TYPE_ID: GenericTypeId = GenericTypeId::new_inline("u64");
368    const IS_SMALL: bool = true;
369    const CONST: &'static str = "u64_const";
370    const EQUAL: &'static str = "u64_eq";
371    const TO_FELT252: &'static str = "u64_to_felt252";
372    const TRY_FROM_FELT252: &'static str = "u64_try_from_felt252";
373}
374
375impl UintTraits for Uint64Traits {
376    const OVERFLOWING_ADD: &'static str = "u64_overflowing_add";
377    const OVERFLOWING_SUB: &'static str = "u64_overflowing_sub";
378    const SQUARE_ROOT: &'static str = "u64_sqrt";
379    const SQUARE_ROOT_TYPE_ID: GenericTypeId = <Uint32Type as NamedType>::ID;
380    const DIVMOD: &'static str = "u64_safe_divmod";
381    const BITWISE: &'static str = "u64_bitwise";
382}
383
384impl IntMulTraits for Uint64Traits {
385    const WIDE_MUL: &'static str = "u64_wide_mul";
386    const WIDE_MUL_RES_TYPE_ID: GenericTypeId = <Uint128Type as NamedType>::ID;
387}
388
389impl IsZeroTraits for Uint64Traits {
390    const IS_ZERO: &'static str = "u64_is_zero";
391    const GENERIC_TYPE_ID: GenericTypeId = <Uint64Type as NamedType>::ID;
392}
393
394/// Type for u64.
395pub type Uint64Type = IntType<Uint64Traits>;
396pub type Uint64Libfunc = UintLibfunc<Uint64Traits>;
397pub type Uint64Concrete = <Uint64Libfunc as GenericLibfunc>::Concrete;
cairo_lang_sierra/extensions/modules/int/unsigned.rs

cairo_lang_sierra/extensions/modules/int/
unsigned.rs
