cairo_felt/
bigint_felt.rs

1#[cfg(all(not(feature = "std"), feature = "alloc"))]
2use alloc::{string::String, vec::Vec};
3
4use core::{
5    cmp,
6    convert::Into,
7    fmt,
8    iter::Sum,
9    ops::{
10        Add, AddAssign, BitAnd, BitOr, BitXor, Div, Mul, MulAssign, Neg, Rem, Shl, Shr, ShrAssign,
11        Sub, SubAssign,
12    },
13};
14
15use crate::{lib_bigint_felt::FeltOps, ParseFeltError};
16
17#[cfg(all(feature = "std", feature = "arbitrary"))]
18use arbitrary::Arbitrary;
19
20pub const FIELD_HIGH: u128 = (1 << 123) + (17 << 64); // this is equal to 10633823966279327296825105735305134080
21pub const FIELD_LOW: u128 = 1;
22use lazy_static::lazy_static;
23use num_bigint::{BigInt, BigUint, ToBigInt, U64Digits};
24use num_integer::Integer;
25use num_traits::{Bounded, FromPrimitive, Num, One, Pow, Signed, ToPrimitive, Zero};
26use serde::{Deserialize, Serialize};
27
28lazy_static! {
29    static ref CAIRO_PRIME_BIGUINT: BigUint =
30        (Into::<BigUint>::into(FIELD_HIGH) << 128) + Into::<BigUint>::into(FIELD_LOW);
31    pub static ref SIGNED_FELT_MAX: BigUint = (&*CAIRO_PRIME_BIGUINT).shr(1_u32);
32    pub static ref CAIRO_SIGNED_PRIME: BigInt = CAIRO_PRIME_BIGUINT
33        .to_bigint()
34        .expect("Conversion BigUint -> BigInt can't fail");
35}
36
37#[cfg_attr(all(feature = "arbitrary", feature = "std"), derive(Arbitrary))]
38#[derive(Eq, Hash, PartialEq, PartialOrd, Ord, Clone, Deserialize, Default, Serialize)]
39pub(crate) struct FeltBigInt<const PH: u128, const PL: u128> {
40    val: BigUint,
41}
42
43macro_rules! from_integer {
44    ($type:ty) => {
45        impl From<$type> for FeltBigInt<FIELD_HIGH, FIELD_LOW> {
46            fn from(value: $type) -> Self {
47                Self {
48                    val: value
49                        .try_into()
50                        .unwrap_or_else(|_| &*CAIRO_PRIME_BIGUINT - (-value as u128)),
51                }
52            }
53        }
54    };
55}
56
57macro_rules! from_unsigned {
58    ($type:ty) => {
59        impl From<$type> for FeltBigInt<FIELD_HIGH, FIELD_LOW> {
60            fn from(value: $type) -> Self {
61                Self { val: value.into() }
62            }
63        }
64    };
65}
66
67from_integer!(i8);
68from_integer!(i16);
69from_integer!(i32);
70from_integer!(i64);
71from_integer!(i128);
72from_integer!(isize);
73
74from_unsigned!(u8);
75from_unsigned!(u16);
76from_unsigned!(u32);
77from_unsigned!(u64);
78from_unsigned!(u128);
79from_unsigned!(usize);
80
81impl<const PH: u128, const PL: u128> From<BigUint> for FeltBigInt<PH, PL> {
82    fn from(value: BigUint) -> Self {
83        Self {
84            val: match value {
85                _ if value > *CAIRO_PRIME_BIGUINT => value.mod_floor(&CAIRO_PRIME_BIGUINT),
86                _ if value == *CAIRO_PRIME_BIGUINT => BigUint::zero(),
87                _ => value,
88            },
89        }
90    }
91}
92
93impl<const PH: u128, const PL: u128> From<&BigUint> for FeltBigInt<PH, PL> {
94    fn from(value: &BigUint) -> Self {
95        Self {
96            val: match value {
97                _ if value > &*CAIRO_PRIME_BIGUINT => value.mod_floor(&CAIRO_PRIME_BIGUINT),
98                _ if value == &*CAIRO_PRIME_BIGUINT => BigUint::zero(),
99                _ => value.clone(),
100            },
101        }
102    }
103}
104
105/* Code used to convert from BigUint to BigInt
106   impl ToBigInt for BigUint {
107       #[inline]
108       fn to_bigint(&self) -> Option<BigInt> {
109           if self.is_zero() {
110               Some(Zero::zero())
111           } else {
112               Some(BigInt {
113                   sign: Plus,
114                   data: self.clone(),
115               })
116           }
117       }
118   }
119*/
120
121impl<const PH: u128, const PL: u128> From<BigInt> for FeltBigInt<PH, PL> {
122    fn from(value: BigInt) -> Self {
123        (&value).into()
124    }
125}
126
127impl<const PH: u128, const PL: u128> From<&BigInt> for FeltBigInt<PH, PL> {
128    fn from(value: &BigInt) -> Self {
129        Self {
130            val: value
131                .mod_floor(&CAIRO_SIGNED_PRIME)
132                .to_biguint()
133                .expect("mod_floor is always positive"),
134        }
135    }
136}
137
138impl FeltOps for FeltBigInt<FIELD_HIGH, FIELD_LOW> {
139    fn new<T: Into<FeltBigInt<FIELD_HIGH, FIELD_LOW>>>(
140        value: T,
141    ) -> FeltBigInt<FIELD_HIGH, FIELD_LOW> {
142        value.into()
143    }
144
145    fn modpow(
146        &self,
147        exponent: &FeltBigInt<FIELD_HIGH, FIELD_LOW>,
148        modulus: &FeltBigInt<FIELD_HIGH, FIELD_LOW>,
149    ) -> FeltBigInt<FIELD_HIGH, FIELD_LOW> {
150        FeltBigInt {
151            val: self.val.modpow(&exponent.val, &modulus.val),
152        }
153    }
154
155    fn iter_u64_digits(&self) -> U64Digits {
156        self.val.iter_u64_digits()
157    }
158
159    #[cfg(any(feature = "std", feature = "alloc"))]
160    fn to_signed_bytes_le(&self) -> Vec<u8> {
161        self.val.to_bytes_le()
162    }
163
164    #[cfg(any(feature = "std", feature = "alloc"))]
165    fn to_bytes_be(&self) -> Vec<u8> {
166        self.val.to_bytes_be()
167    }
168
169    fn parse_bytes(buf: &[u8], radix: u32) -> Option<FeltBigInt<FIELD_HIGH, FIELD_LOW>> {
170        match BigUint::parse_bytes(buf, radix) {
171            Some(parsed) => Some(FeltBigInt::new(parsed)),
172            None => BigInt::parse_bytes(buf, radix).map(FeltBigInt::new),
173        }
174    }
175
176    fn from_bytes_be(bytes: &[u8]) -> FeltBigInt<FIELD_HIGH, FIELD_LOW> {
177        Self::from(BigUint::from_bytes_be(bytes))
178    }
179
180    fn from_bytes_le(bytes: &[u8]) -> FeltBigInt<FIELD_HIGH, FIELD_LOW> {
181        Self::from(BigUint::from_bytes_le(bytes))
182    }
183
184    #[cfg(any(feature = "std", feature = "alloc"))]
185    fn to_str_radix(&self, radix: u32) -> String {
186        self.val.to_str_radix(radix)
187    }
188
189    fn to_signed_felt(&self) -> BigInt {
190        if self.val > *SIGNED_FELT_MAX {
191            BigInt::from_biguint(num_bigint::Sign::Minus, &*CAIRO_PRIME_BIGUINT - &self.val)
192        } else {
193            self.val.clone().into()
194        }
195    }
196
197    fn to_bigint(&self) -> BigInt {
198        self.val.clone().into()
199    }
200
201    fn to_biguint(&self) -> BigUint {
202        self.val.clone()
203    }
204
205    fn bits(&self) -> u64 {
206        self.val.bits()
207    }
208
209    fn prime() -> BigUint {
210        (Into::<BigUint>::into(FIELD_HIGH) << 128) + Into::<BigUint>::into(FIELD_LOW)
211    }
212}
213
214impl<const PH: u128, const PL: u128> Add for FeltBigInt<PH, PL> {
215    type Output = Self;
216    fn add(mut self, rhs: Self) -> Self {
217        self.val += rhs.val;
218        if self.val >= *CAIRO_PRIME_BIGUINT {
219            self.val -= &*CAIRO_PRIME_BIGUINT;
220        }
221        self
222    }
223}
224
225impl<'a, const PH: u128, const PL: u128> Add for &'a FeltBigInt<PH, PL> {
226    type Output = FeltBigInt<PH, PL>;
227
228    fn add(self, rhs: Self) -> Self::Output {
229        let mut sum = &self.val + &rhs.val;
230        if sum >= *CAIRO_PRIME_BIGUINT {
231            sum -= &*CAIRO_PRIME_BIGUINT;
232        }
233        FeltBigInt { val: sum }
234    }
235}
236
237impl<'a, const PH: u128, const PL: u128> Add<&'a FeltBigInt<PH, PL>> for FeltBigInt<PH, PL> {
238    type Output = FeltBigInt<PH, PL>;
239
240    fn add(mut self, rhs: &'a FeltBigInt<PH, PL>) -> Self::Output {
241        self.val += &rhs.val;
242        if self.val >= *CAIRO_PRIME_BIGUINT {
243            self.val -= &*CAIRO_PRIME_BIGUINT;
244        }
245        self
246    }
247}
248
249impl<const PH: u128, const PL: u128> Add<u32> for FeltBigInt<PH, PL> {
250    type Output = Self;
251    fn add(mut self, rhs: u32) -> Self {
252        self.val += rhs;
253        if self.val >= *CAIRO_PRIME_BIGUINT {
254            self.val -= &*CAIRO_PRIME_BIGUINT;
255        }
256        self
257    }
258}
259
260impl<const PH: u128, const PL: u128> Add<usize> for FeltBigInt<PH, PL> {
261    type Output = Self;
262    fn add(mut self, rhs: usize) -> Self {
263        self.val += rhs;
264        if self.val >= *CAIRO_PRIME_BIGUINT {
265            self.val -= &*CAIRO_PRIME_BIGUINT;
266        }
267        self
268    }
269}
270
271impl<'a, const PH: u128, const PL: u128> Add<usize> for &'a FeltBigInt<PH, PL> {
272    type Output = FeltBigInt<PH, PL>;
273    fn add(self, rhs: usize) -> Self::Output {
274        let mut sum = &self.val + rhs;
275        if sum >= *CAIRO_PRIME_BIGUINT {
276            sum -= &*CAIRO_PRIME_BIGUINT;
277        }
278        FeltBigInt { val: sum }
279    }
280}
281
282impl<const PH: u128, const PL: u128> Add<u64> for &FeltBigInt<PH, PL> {
283    type Output = FeltBigInt<PH, PL>;
284    fn add(self, rhs: u64) -> Self::Output {
285        let mut sum = &self.val + rhs;
286        if sum >= *CAIRO_PRIME_BIGUINT {
287            sum -= &*CAIRO_PRIME_BIGUINT;
288        }
289        FeltBigInt { val: sum }
290    }
291}
292
293impl<const PH: u128, const PL: u128> AddAssign for FeltBigInt<PH, PL> {
294    fn add_assign(&mut self, rhs: Self) {
295        *self = &*self + &rhs;
296    }
297}
298
299impl<'a, const PH: u128, const PL: u128> AddAssign<&'a FeltBigInt<PH, PL>> for FeltBigInt<PH, PL> {
300    fn add_assign(&mut self, rhs: &'a FeltBigInt<PH, PL>) {
301        *self = &*self + rhs;
302    }
303}
304
305impl<const PH: u128, const PL: u128> Sum for FeltBigInt<PH, PL> {
306    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
307        iter.fold(FeltBigInt::zero(), |mut acc, x| {
308            acc += x;
309            acc
310        })
311    }
312}
313
314impl<const PH: u128, const PL: u128> Neg for FeltBigInt<PH, PL> {
315    type Output = FeltBigInt<PH, PL>;
316    fn neg(self) -> Self::Output {
317        if self.is_zero() {
318            self
319        } else {
320            FeltBigInt {
321                val: &*CAIRO_PRIME_BIGUINT - self.val,
322            }
323        }
324    }
325}
326
327impl<'a, const PH: u128, const PL: u128> Neg for &'a FeltBigInt<PH, PL> {
328    type Output = FeltBigInt<PH, PL>;
329    fn neg(self) -> Self::Output {
330        if self.is_zero() {
331            self.clone()
332        } else {
333            FeltBigInt {
334                val: &*CAIRO_PRIME_BIGUINT - &self.val,
335            }
336        }
337    }
338}
339
340impl<const PH: u128, const PL: u128> Sub for FeltBigInt<PH, PL> {
341    type Output = Self;
342    fn sub(mut self, rhs: Self) -> Self::Output {
343        if self.val < rhs.val {
344            self.val += &*CAIRO_PRIME_BIGUINT;
345        }
346        self.val -= rhs.val;
347        self
348    }
349}
350
351impl<'a, const PH: u128, const PL: u128> Sub<&'a FeltBigInt<PH, PL>> for FeltBigInt<PH, PL> {
352    type Output = FeltBigInt<PH, PL>;
353    fn sub(mut self, rhs: &'a FeltBigInt<PH, PL>) -> Self::Output {
354        if self.val < rhs.val {
355            self.val += &*CAIRO_PRIME_BIGUINT;
356        }
357        self.val -= &rhs.val;
358        self
359    }
360}
361
362impl<'a, const PH: u128, const PL: u128> Sub for &'a FeltBigInt<PH, PL> {
363    type Output = FeltBigInt<PH, PL>;
364    fn sub(self, rhs: Self) -> Self::Output {
365        FeltBigInt {
366            val: if self.val < rhs.val {
367                &*CAIRO_PRIME_BIGUINT - (&rhs.val - &self.val)
368            } else {
369                &self.val - &rhs.val
370            },
371        }
372    }
373}
374
375impl<const PH: u128, const PL: u128> Sub<u32> for FeltBigInt<PH, PL> {
376    type Output = FeltBigInt<PH, PL>;
377    fn sub(self, rhs: u32) -> Self {
378        match (self.val).to_u32() {
379            Some(num) if num < rhs => Self {
380                val: &*CAIRO_PRIME_BIGUINT - (rhs - self.val),
381            },
382            _ => Self {
383                val: self.val - rhs,
384            },
385        }
386    }
387}
388
389impl<'a, const PH: u128, const PL: u128> Sub<u32> for &'a FeltBigInt<PH, PL> {
390    type Output = FeltBigInt<PH, PL>;
391    fn sub(self, rhs: u32) -> Self::Output {
392        match (self.val).to_u32() {
393            Some(num) if num < rhs => FeltBigInt {
394                val: &*CAIRO_PRIME_BIGUINT - (rhs - &self.val),
395            },
396            _ => FeltBigInt {
397                val: &self.val - rhs,
398            },
399        }
400    }
401}
402
403impl<const PH: u128, const PL: u128> Sub<usize> for FeltBigInt<PH, PL> {
404    type Output = FeltBigInt<PH, PL>;
405    fn sub(self, rhs: usize) -> Self {
406        match (self.val).to_usize() {
407            Some(num) if num < rhs => FeltBigInt {
408                val: &*CAIRO_PRIME_BIGUINT - (rhs - num),
409            },
410            _ => FeltBigInt {
411                val: self.val - rhs,
412            },
413        }
414    }
415}
416
417impl<'a, const PH: u128, const PL: u128> Pow<&'a FeltBigInt<PH, PL>> for &'a FeltBigInt<PH, PL> {
418    type Output = FeltBigInt<PH, PL>;
419    fn pow(self, rhs: Self) -> Self::Output {
420        FeltBigInt {
421            val: self.val.modpow(&rhs.val, &CAIRO_PRIME_BIGUINT),
422        }
423    }
424}
425
426impl<const PH: u128, const PL: u128> SubAssign for FeltBigInt<PH, PL> {
427    fn sub_assign(&mut self, rhs: Self) {
428        *self = &*self - &rhs;
429    }
430}
431
432impl<'a, const PH: u128, const PL: u128> SubAssign<&'a FeltBigInt<PH, PL>> for FeltBigInt<PH, PL> {
433    fn sub_assign(&mut self, rhs: &'a FeltBigInt<PH, PL>) {
434        *self = &*self - rhs;
435    }
436}
437
438impl Sub<FeltBigInt<FIELD_HIGH, FIELD_LOW>> for usize {
439    type Output = FeltBigInt<FIELD_HIGH, FIELD_LOW>;
440    fn sub(self, rhs: FeltBigInt<FIELD_HIGH, FIELD_LOW>) -> Self::Output {
441        self - &rhs
442    }
443}
444
445impl Sub<&FeltBigInt<FIELD_HIGH, FIELD_LOW>> for usize {
446    type Output = FeltBigInt<FIELD_HIGH, FIELD_LOW>;
447    fn sub(self, rhs: &FeltBigInt<FIELD_HIGH, FIELD_LOW>) -> Self::Output {
448        match (rhs.val).to_usize() {
449            Some(num) => {
450                if num > self {
451                    FeltBigInt {
452                        val: &*CAIRO_PRIME_BIGUINT - (num - self),
453                    }
454                } else {
455                    FeltBigInt::new(self - num)
456                }
457            }
458            None => FeltBigInt {
459                val: &*CAIRO_PRIME_BIGUINT - (&rhs.val - self),
460            },
461        }
462    }
463}
464
465impl<const PH: u128, const PL: u128> Mul for FeltBigInt<PH, PL> {
466    type Output = Self;
467    fn mul(self, rhs: Self) -> Self::Output {
468        FeltBigInt {
469            val: (self.val * rhs.val).mod_floor(&CAIRO_PRIME_BIGUINT),
470        }
471    }
472}
473
474impl<'a, const PH: u128, const PL: u128> Mul for &'a FeltBigInt<PH, PL> {
475    type Output = FeltBigInt<PH, PL>;
476    fn mul(self, rhs: Self) -> Self::Output {
477        FeltBigInt {
478            val: (&self.val * &rhs.val).mod_floor(&CAIRO_PRIME_BIGUINT),
479        }
480    }
481}
482
483impl<'a, const PH: u128, const PL: u128> Mul<&'a FeltBigInt<PH, PL>> for FeltBigInt<PH, PL> {
484    type Output = FeltBigInt<PH, PL>;
485    fn mul(self, rhs: &'a FeltBigInt<PH, PL>) -> Self::Output {
486        FeltBigInt {
487            val: (&self.val * &rhs.val).mod_floor(&CAIRO_PRIME_BIGUINT),
488        }
489    }
490}
491
492impl<'a, const PH: u128, const PL: u128> MulAssign<&'a FeltBigInt<PH, PL>> for FeltBigInt<PH, PL> {
493    fn mul_assign(&mut self, rhs: &'a FeltBigInt<PH, PL>) {
494        *self = &*self * rhs;
495    }
496}
497
498impl<const PH: u128, const PL: u128> Pow<u32> for FeltBigInt<PH, PL> {
499    type Output = Self;
500    fn pow(self, rhs: u32) -> Self {
501        FeltBigInt {
502            val: self.val.modpow(&BigUint::from(rhs), &CAIRO_PRIME_BIGUINT),
503        }
504    }
505}
506
507impl<'a, const PH: u128, const PL: u128> Pow<u32> for &'a FeltBigInt<PH, PL> {
508    type Output = FeltBigInt<PH, PL>;
509    fn pow(self, rhs: u32) -> Self::Output {
510        FeltBigInt {
511            val: self.val.modpow(&BigUint::from(rhs), &CAIRO_PRIME_BIGUINT),
512        }
513    }
514}
515
516impl<const PH: u128, const PL: u128> Div for FeltBigInt<PH, PL> {
517    type Output = Self;
518    // In Felts `x / y` needs to be expressed as `x * y^-1`
519    #[allow(clippy::suspicious_arithmetic_impl)]
520    fn div(self, rhs: Self) -> Self::Output {
521        if rhs.is_zero() {
522            panic!("Can't divide Felt by zero")
523        }
524        let x = rhs
525            .val
526            .to_bigint() // Always succeeds for BigUint -> BigInt
527            .unwrap()
528            .extended_gcd(&CAIRO_SIGNED_PRIME)
529            .x;
530        self * &FeltBigInt::from(x)
531    }
532}
533
534impl<'a, const PH: u128, const PL: u128> Div for &'a FeltBigInt<PH, PL> {
535    type Output = FeltBigInt<PH, PL>;
536    // In Felts `x / y` needs to be expressed as `x * y^-1`
537    #[allow(clippy::suspicious_arithmetic_impl)]
538    fn div(self, rhs: Self) -> Self::Output {
539        if rhs.is_zero() {
540            panic!("Can't divide Felt by zero")
541        }
542        let x = rhs
543            .val
544            .to_bigint() // Always succeeds for BitUint -> BigInt
545            .unwrap()
546            .extended_gcd(&CAIRO_SIGNED_PRIME)
547            .x;
548        self * &FeltBigInt::from(x)
549    }
550}
551
552impl<'a, const PH: u128, const PL: u128> Div<FeltBigInt<PH, PL>> for &'a FeltBigInt<PH, PL> {
553    type Output = FeltBigInt<PH, PL>;
554    // In Felts `x / y` needs to be expressed as `x * y^-1`
555    #[allow(clippy::suspicious_arithmetic_impl)]
556    fn div(self, rhs: FeltBigInt<PH, PL>) -> Self::Output {
557        self / &rhs
558    }
559}
560
561impl<const PH: u128, const PL: u128> Rem for FeltBigInt<PH, PL> {
562    type Output = Self;
563    fn rem(self, _rhs: Self) -> Self {
564        FeltBigInt::zero()
565    }
566}
567
568impl<'a, const PH: u128, const PL: u128> Rem<&'a FeltBigInt<PH, PL>> for FeltBigInt<PH, PL> {
569    type Output = Self;
570    fn rem(self, _rhs: &'a FeltBigInt<PH, PL>) -> Self::Output {
571        FeltBigInt::zero()
572    }
573}
574
575impl<const PH: u128, const PL: u128> Zero for FeltBigInt<PH, PL> {
576    fn zero() -> Self {
577        Self {
578            val: BigUint::zero(),
579        }
580    }
581
582    fn is_zero(&self) -> bool {
583        self.val.is_zero()
584    }
585}
586
587impl<const PH: u128, const PL: u128> One for FeltBigInt<PH, PL> {
588    fn one() -> Self {
589        Self {
590            val: BigUint::one(),
591        }
592    }
593
594    fn is_one(&self) -> bool
595    where
596        Self: PartialEq,
597    {
598        self.val.is_one()
599    }
600}
601
602impl<const PH: u128, const PL: u128> Bounded for FeltBigInt<PH, PL> {
603    fn min_value() -> Self {
604        Self::zero()
605    }
606    fn max_value() -> Self {
607        Self {
608            val: &*CAIRO_PRIME_BIGUINT - 1_u32,
609        }
610    }
611}
612
613impl Num for FeltBigInt<FIELD_HIGH, FIELD_LOW> {
614    type FromStrRadixErr = ParseFeltError;
615    fn from_str_radix(string: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
616        match BigUint::from_str_radix(string, radix) {
617            Ok(num) => Ok(FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(num)),
618            Err(_) => Err(ParseFeltError),
619        }
620    }
621}
622
623impl Integer for FeltBigInt<FIELD_HIGH, FIELD_LOW> {
624    fn div_floor(&self, other: &Self) -> Self {
625        FeltBigInt {
626            val: &self.val / &other.val,
627        }
628    }
629
630    fn div_rem(&self, other: &Self) -> (Self, Self) {
631        let (d, m) = self.val.div_mod_floor(&other.val);
632        (FeltBigInt { val: d }, FeltBigInt { val: m })
633    }
634
635    fn divides(&self, other: &Self) -> bool {
636        self.is_multiple_of(other)
637    }
638
639    fn gcd(&self, other: &Self) -> Self {
640        Self {
641            val: self.val.gcd(&other.val),
642        }
643    }
644
645    fn is_even(&self) -> bool {
646        self.val.is_even()
647    }
648
649    fn is_multiple_of(&self, _other: &Self) -> bool {
650        true
651    }
652
653    fn is_odd(&self) -> bool {
654        self.val.is_odd()
655    }
656
657    fn lcm(&self, other: &Self) -> Self {
658        Self::new(cmp::max(&self.val, &other.val))
659    }
660
661    fn mod_floor(&self, other: &Self) -> Self {
662        Self {
663            val: self.val.mod_floor(&other.val),
664        }
665    }
666}
667
668impl Signed for FeltBigInt<FIELD_HIGH, FIELD_LOW> {
669    fn abs(&self) -> Self {
670        self.clone()
671    }
672
673    fn abs_sub(&self, other: &Self) -> Self {
674        if self > other {
675            self - other
676        } else {
677            other - self
678        }
679    }
680
681    fn signum(&self) -> Self {
682        if self.is_zero() {
683            FeltBigInt::zero()
684        } else {
685            FeltBigInt::one()
686        }
687    }
688
689    fn is_positive(&self) -> bool {
690        !self.is_zero()
691    }
692
693    fn is_negative(&self) -> bool {
694        !(self.is_positive() || self.is_zero())
695    }
696}
697
698impl<const PH: u128, const PL: u128> Shl<u32> for FeltBigInt<PH, PL> {
699    type Output = Self;
700    fn shl(self, other: u32) -> Self::Output {
701        FeltBigInt {
702            val: (self.val).shl(other).mod_floor(&CAIRO_PRIME_BIGUINT),
703        }
704    }
705}
706
707impl<'a, const PH: u128, const PL: u128> Shl<u32> for &'a FeltBigInt<PH, PL> {
708    type Output = FeltBigInt<PH, PL>;
709    fn shl(self, other: u32) -> Self::Output {
710        FeltBigInt {
711            val: (&self.val).shl(other).mod_floor(&CAIRO_PRIME_BIGUINT),
712        }
713    }
714}
715
716impl<const PH: u128, const PL: u128> Shl<usize> for FeltBigInt<PH, PL> {
717    type Output = Self;
718    fn shl(self, other: usize) -> Self::Output {
719        FeltBigInt {
720            val: (self.val).shl(other).mod_floor(&CAIRO_PRIME_BIGUINT),
721        }
722    }
723}
724
725impl<'a, const PH: u128, const PL: u128> Shl<usize> for &'a FeltBigInt<PH, PL> {
726    type Output = FeltBigInt<PH, PL>;
727    fn shl(self, other: usize) -> Self::Output {
728        FeltBigInt {
729            val: (&self.val).shl(other).mod_floor(&CAIRO_PRIME_BIGUINT),
730        }
731    }
732}
733
734impl<const PH: u128, const PL: u128> Shr<u32> for FeltBigInt<PH, PL> {
735    type Output = Self;
736    fn shr(self, other: u32) -> Self::Output {
737        FeltBigInt {
738            val: self.val.shr(other),
739        }
740    }
741}
742
743impl<'a, const PH: u128, const PL: u128> Shr<u32> for &'a FeltBigInt<PH, PL> {
744    type Output = FeltBigInt<PH, PL>;
745    fn shr(self, other: u32) -> Self::Output {
746        FeltBigInt {
747            val: (&self.val).shr(other).mod_floor(&CAIRO_PRIME_BIGUINT),
748        }
749    }
750}
751
752impl<const PH: u128, const PL: u128> ShrAssign<usize> for FeltBigInt<PH, PL> {
753    fn shr_assign(&mut self, other: usize) {
754        self.val = (&self.val).shr(other).mod_floor(&CAIRO_PRIME_BIGUINT);
755    }
756}
757
758impl<'a, const PH: u128, const PL: u128> BitAnd for &'a FeltBigInt<PH, PL> {
759    type Output = FeltBigInt<PH, PL>;
760    fn bitand(self, rhs: Self) -> Self::Output {
761        FeltBigInt {
762            val: &self.val & &rhs.val,
763        }
764    }
765}
766
767impl<'a, const PH: u128, const PL: u128> BitAnd<&'a FeltBigInt<PH, PL>> for FeltBigInt<PH, PL> {
768    type Output = Self;
769    fn bitand(self, rhs: &'a FeltBigInt<PH, PL>) -> Self::Output {
770        FeltBigInt {
771            val: self.val & &rhs.val,
772        }
773    }
774}
775
776impl<'a, const PH: u128, const PL: u128> BitAnd<FeltBigInt<PH, PL>> for &'a FeltBigInt<PH, PL> {
777    type Output = FeltBigInt<PH, PL>;
778    fn bitand(self, rhs: Self::Output) -> Self::Output {
779        FeltBigInt {
780            val: &self.val & rhs.val,
781        }
782    }
783}
784
785impl<'a, const PH: u128, const PL: u128> BitOr for &'a FeltBigInt<PH, PL> {
786    type Output = FeltBigInt<PH, PL>;
787    fn bitor(self, rhs: Self) -> Self::Output {
788        FeltBigInt {
789            val: &self.val | &rhs.val,
790        }
791    }
792}
793
794impl<'a, const PH: u128, const PL: u128> BitXor for &'a FeltBigInt<PH, PL> {
795    type Output = FeltBigInt<PH, PL>;
796    fn bitxor(self, rhs: Self) -> Self::Output {
797        FeltBigInt {
798            val: &self.val ^ &rhs.val,
799        }
800    }
801}
802
803impl<const PH: u128, const PL: u128> ToPrimitive for FeltBigInt<PH, PL> {
804    fn to_u128(&self) -> Option<u128> {
805        self.val.to_u128()
806    }
807
808    fn to_u64(&self) -> Option<u64> {
809        self.val.to_u64()
810    }
811
812    fn to_i64(&self) -> Option<i64> {
813        self.val.to_i64()
814    }
815
816    fn to_usize(&self) -> Option<usize> {
817        self.val.to_usize()
818    }
819}
820
821impl<const PH: u128, const PL: u128> FromPrimitive for FeltBigInt<PH, PL> {
822    fn from_u64(n: u64) -> Option<Self> {
823        BigUint::from_u64(n).map(|n| Self { val: n })
824    }
825
826    fn from_i64(n: i64) -> Option<Self> {
827        BigUint::from_i64(n).map(|n| Self { val: n })
828    }
829
830    fn from_usize(n: usize) -> Option<Self> {
831        BigUint::from_usize(n).map(|n| Self { val: n })
832    }
833}
834
835impl<const PH: u128, const PL: u128> fmt::Display for FeltBigInt<PH, PL> {
836    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
837        write!(f, "{}", self.val)
838    }
839}
840
841impl<const PH: u128, const PL: u128> fmt::Debug for FeltBigInt<PH, PL> {
842    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
843        write!(f, "{}", self.val)
844    }
845}
846
847#[cfg(test)]
848mod tests {
849    use super::*;
850    use proptest::prelude::*;
851
852    #[cfg(all(not(feature = "std"), feature = "alloc"))]
853    use alloc::string::ToString;
854
855    #[cfg(target_arch = "wasm32")]
856    use wasm_bindgen_test::*;
857
858    #[test]
859    // Tests that the result of adding two zeros is zero.
860    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
861    fn add_zeros() {
862        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
863        let b = FeltBigInt::new(0);
864        let c = FeltBigInt::new(0);
865
866        assert_eq!(a + b, c);
867    }
868
869    #[test]
870    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
871    // Tests that the result of performing add assign with two zeros is zero.
872    fn add_assign_zeros() {
873        let mut a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
874        let b = FeltBigInt::new(0);
875        a += b;
876        let c = FeltBigInt::new(0);
877
878        assert_eq!(a, c);
879    }
880    #[test]
881    // Tests that the result of performing a bitwise "and" operation with two zeros is zero.
882    fn bit_and_zeros() {
883        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
884        let b = FeltBigInt::new(0);
885        let c = FeltBigInt::new(0);
886
887        assert_eq!(&a & &b, c);
888    }
889    #[test]
890    // Tests that the result of performing a bitwise "or" operation with two zeros is zero.
891
892    fn bit_or_zeros() {
893        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
894        let b = FeltBigInt::new(0);
895        let c = FeltBigInt::new(0);
896
897        assert_eq!(&a | &b, c);
898    }
899
900    #[test]
901    // Tests that the result of performing a bitwise "xor" operation with two zeros results in zero.
902    fn bit_xor_zeros() {
903        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
904        let b = FeltBigInt::new(0);
905        let c = FeltBigInt::new(0);
906
907        assert_eq!(&a ^ &b, c);
908    }
909
910    #[test]
911    #[should_panic]
912    // Tests that the result of performing a division by zero results in panic.
913    fn div_zeros() {
914        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
915        let b = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
916        let _ = a / b;
917    }
918
919    #[test]
920    #[should_panic]
921    // Tests that the result of performing a division by zero results in panic.
922    fn div_zeros_ref() {
923        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
924        let b = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
925        let _ = &a / &b;
926    }
927
928    #[test]
929    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
930    // Tests that the result of multiplying two zeros is zero.
931    fn mul_zeros() {
932        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
933        let b = FeltBigInt::new(0);
934        let c = FeltBigInt::new(0);
935
936        assert_eq!(a * b, c);
937    }
938
939    #[test]
940    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
941    // Tests that the result of multiplying two zeros with assignment is zero.
942    fn mul_assign_zeros() {
943        let mut a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
944        let b = FeltBigInt::new(0);
945        a *= &b;
946        let c = FeltBigInt::new(0);
947
948        assert_eq!(a, c);
949    }
950
951    #[test]
952    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
953    // Tests that the result of subtracting two zeros is zero.
954    fn sub_zeros() {
955        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
956        let b = FeltBigInt::new(0);
957        let c = FeltBigInt::new(0);
958
959        assert_eq!(a - b, c);
960    }
961
962    #[test]
963    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
964    // Tests that the result of subtracting two zeros with assignment is zero.
965    fn sub_assign_zeros() {
966        let mut a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
967        let b = FeltBigInt::new(0);
968        a -= b;
969        let c = FeltBigInt::new(0);
970
971        assert_eq!(a, c);
972    }
973
974    #[test]
975    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
976    fn sub_usize_felt() {
977        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(4u32);
978        let b = FeltBigInt::new(2u32);
979
980        assert_eq!(6usize - &a, b);
981        assert_eq!(6usize - a, b);
982    }
983
984    #[test]
985    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
986    // Tests that the negative of zero is zero
987    fn negate_zero() {
988        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
989        let b = a.neg();
990        assert_eq!(
991            b,
992            FeltBigInt::from_str_radix("0", 10).expect("Couldn't parse int")
993        );
994
995        let c = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::from_str_radix("0", 10)
996            .expect("Couldn't parse int");
997        let d = c.neg();
998        assert_eq!(d, FeltBigInt::new(0));
999    }
1000
1001    #[test]
1002    // Tests a shift left operation performed on a felt of value zero
1003    fn shift_left_zero() {
1004        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1005        let b = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1006        let result = &a << 10_u32;
1007        assert_eq!(result, b)
1008    }
1009
1010    #[test]
1011    // Tests a shift right operation performed on a felt of value zero
1012    fn shift_right_zero() {
1013        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1014        let b = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1015        let result = &a >> 10_u32;
1016        assert_eq!(result, b)
1017    }
1018
1019    #[test]
1020    // Tests a shift right operation with assignment performed on a felt of value zero
1021    fn shift_right_assign_zero() {
1022        let mut a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1023        let b = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1024        a >>= 10;
1025        assert_eq!(a, b)
1026    }
1027
1028    #[test]
1029    // Test that an iterative sum of zeros results in zero
1030    fn sum_zeros() {
1031        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1032        let b = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1033        let c = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1034        let v = vec![a, b, c];
1035        let result: FeltBigInt<FIELD_HIGH, FIELD_LOW> = v.into_iter().sum();
1036        assert_eq!(result, FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0))
1037    }
1038
1039    #[test]
1040    // Tests that the remainder of a division where the dividend is 0, results in 0
1041    fn rem_zero() {
1042        let a = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1043        let b = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1044        let c = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(10);
1045        let d = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::new(0);
1046        assert_eq!(a.clone() % b, d);
1047        assert_eq!(a % c, d)
1048    }
1049
1050    proptest! {
1051        #[test]
1052        // Property-based test that ensures, for 100 pairs of values that are randomly generated each time tests are run, that performing a subtraction returns a result that is inside of the range [0, p].
1053        fn sub_bigint_felt_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1054            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1055            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1056            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1057            let result = x - y;
1058            let as_uint = &result.to_biguint();
1059            prop_assert!(as_uint < &p, "{}", as_uint);
1060        }
1061
1062        #[test]
1063        // Property-based test that ensures, for 100 pairs of values that are randomly generated each time tests are run, that performing a subtraction returns a result that is inside of the range [0, p].
1064        fn sub_assign_bigint_felt_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1065            let mut x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1066            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1067            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1068            x -= y;
1069            let as_uint = &x.to_biguint();
1070            prop_assert!(as_uint < &p, "{}", as_uint);
1071        }
1072
1073        #[test]
1074        // Property-based test that ensures that the remainder of a division between two random bigint felts returns 0. The test is performed 100 times each run.
1075        fn rem_bigint_felt_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1076            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1077            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1078
1079            let result = x % y;
1080            prop_assert!(result.is_zero());
1081        }
1082        // Tests that the result of adding two random large bigint felts falls within the range [0, p]. This test is performed 100 times each run.
1083        #[test]
1084        fn add_bigint_felts_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1085            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1086            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1087            let p = &CAIRO_PRIME_BIGUINT;
1088            let result = x + y;
1089            let as_uint = &result.to_biguint();
1090            prop_assert!(as_uint < p, "{}", as_uint);
1091
1092        }
1093        #[test]
1094        // Tests that the result of performing add assign on two random large bigint felts falls within the range [0, p]. This test is performed 100 times each run.
1095        fn add_assign_bigint_felts_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1096            let mut x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1097            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1098            let p = &CAIRO_PRIME_BIGUINT;
1099            x += y;
1100            let as_uint = &x.to_biguint();
1101            prop_assert!(as_uint < p, "{}", as_uint);
1102        }
1103
1104        #[test]
1105        // Tests that the result of performing the bitwise "and" operation on two random large bigint felts falls within the range [0, p]. This test is performed 100 times each run.
1106        fn bitand_bigint_felts_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1107            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1108            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1109            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1110            let result = &x & &y;
1111            let as_uint = result.to_biguint();
1112            prop_assert!(as_uint < p, "{}", as_uint);
1113        }
1114        #[test]
1115        // Tests that the result of performing the bitwise "or" operation on two random large bigint felts falls within the range [0, p]. This test is performed 100 times each run.
1116        fn bitor_bigint_felts_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1117            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1118            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1119            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1120            let result = &x | &y;
1121            let as_uint = result.to_biguint();
1122            prop_assert!(as_uint < p, "{}", as_uint);
1123        }
1124        #[test]
1125        // Tests that the result of performing the bitwise "xor" operation on two random large bigint felts falls within the range [0, p]. This test is performed 100 times each run.
1126        fn bitxor_bigint_felts_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1127            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1128            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1129            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1130            let result = &x ^ &y;
1131            let as_uint = result.to_biguint();
1132            prop_assert!(as_uint < p, "{}", as_uint);
1133        }
1134        #[test]
1135        // Tests that the result dividing two random large bigint felts falls within the range [0, p]. This test is performed 100 times each run.
1136        fn div_bigint_felts_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1137            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1138            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1139            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1140            let result = &x / &y;
1141            let as_uint = result.to_biguint();
1142            prop_assert!(as_uint < p, "{}", as_uint);
1143        }
1144        #[test]
1145        // Tests that the result multiplying two random large bigint felts falls within the range [0, p]. This test is performed 100 times each run.
1146        fn mul_bigint_felts_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1147            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1148            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1149            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1150            let result = &x * &y;
1151            let as_uint = result.to_biguint();
1152            prop_assert!(as_uint < p, "{}", as_uint);
1153        }
1154        #[test]
1155        // Tests that the result of performing a multiplication with assignment between two random large bigint felts falls within the range [0, p]. This test is performed 100 times each run.
1156        fn mul_assign_bigint_felts_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)") {
1157            let mut x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1158            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1159            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1160            x *= &y;
1161            let as_uint = x.to_biguint();
1162            prop_assert!(as_uint < p, "{}", as_uint);
1163        }
1164        #[test]
1165        // Tests that the result of applying the negative operation to a large bigint felt falls within the range [0, p]. This test is performed 100 times each run.
1166        fn neg_bigint_felt_within_field(ref x in "([1-9][0-9]*)") {
1167            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1168            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1169            let result = -x;
1170            let as_uint = &result.to_biguint();
1171            prop_assert!(as_uint < &p, "{}", as_uint);
1172        }
1173
1174        #[test]
1175         // Property-based test that ensures, for 100 {value}s that are randomly generated each time tests are run, that performing a bit shift to the left by an amount {y} of bits (between 0 and 999) returns a result that is inside of the range [0, p].
1176         fn shift_left_bigint_felt_within_field(ref x in "([1-9][0-9]*)", ref y in "[0-9]{1,3}") {
1177            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1178            let y = y.parse::<u32>().unwrap();
1179            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1180            let result = x << y;
1181            let as_uint = &result.to_biguint();
1182            prop_assert!(as_uint < &p, "{}", as_uint);
1183        }
1184
1185        #[test]
1186        // Property-based test that ensures, for 100 {value}s that are randomly generated each time tests are run, that performing a bit shift to the right by an amount {y} of bits (between 0 and 999) returns a result that is inside of the range [0, p].
1187        fn shift_right_bigint_felt_within_field(ref x in "([1-9][0-9]*)", ref y in "[0-9]{1,3}") {
1188           let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1189           let y = y.parse::<u32>().unwrap();
1190           let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1191           let result = x >> y;
1192           let as_uint = &result.to_biguint();
1193           prop_assert!(as_uint < &p, "{}", as_uint);
1194       }
1195
1196       #[test]
1197       // Property-based test that ensures, for 100 {value}s that are randomly generated each time tests are run, that performing a bit shift to the right with assignment by an amount {y} of bits (between 0 and 999) returns a result that is inside of the range [0, p].
1198       fn shift_right_assign_bigint_felt_within_field(ref x in "([1-9][0-9]*)", ref y in "[0-9]{1,3}") {
1199          let mut x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1200          let y = y.parse::<u32>().unwrap();
1201          let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1202          x >>= y.try_into().unwrap();
1203          let as_uint = &x.to_biguint();
1204          prop_assert!(as_uint < &p, "{}", as_uint);
1205        }
1206
1207        #[test]
1208        // Property-based test that ensures, vectors of three of values that are randomly generated each time tests are run, that performing an iterative sum returns a result that is inside of the range [0, p]. The test is performed 100 times each run.
1209        fn sum_bigint_felt_within_field(ref x in "([1-9][0-9]*)", ref y in "([1-9][0-9]*)", ref z in "([1-9][0-9]*)") {
1210            let x = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(x.as_bytes(), 10).unwrap();
1211            let y = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(y.as_bytes(), 10).unwrap();
1212            let z = FeltBigInt::<FIELD_HIGH, FIELD_LOW>::parse_bytes(z.as_bytes(), 10).unwrap();
1213            let p:BigUint = BigUint::parse_bytes(CAIRO_PRIME_BIGUINT.to_string().as_bytes(), 16).unwrap();
1214            let v = vec![x, y, z];
1215            let result: FeltBigInt<FIELD_HIGH, FIELD_LOW> = v.into_iter().sum();
1216            let as_uint = result.to_biguint();
1217            prop_assert!(as_uint < p, "{}", as_uint);
1218        }
1219    }
1220}
cairo_felt/bigint_felt.rs

cairo_felt/
bigint_felt.rs
