1use alloc::string::String;
  2use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
  3
  4use num::{One, Zero};
  5
  6use super::{fft::CyclotomicFourier, Inverse, MODULUS};
  7
  8#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
  9pub struct FalconFelt(u32);
 10
 11impl FalconFelt {
 12    pub const fn new(value: i16) -> Self {
 13        let gtz_bool = value >= 0;
 14        let gtz_int = gtz_bool as i16;
 15        let gtz_sign = gtz_int - ((!gtz_bool) as i16);
 16        let reduced = gtz_sign * (gtz_sign * value) % MODULUS;
 17        let canonical_representative = (reduced + MODULUS * (1 - gtz_int)) as u32;
 18        FalconFelt(canonical_representative)
 19    }
 20
 21    pub const fn value(&self) -> i16 {
 22        self.0 as i16
 23    }
 24
 25    pub fn balanced_value(&self) -> i16 {
 26        let value = self.value();
 27        let g = (value > ((MODULUS) / 2)) as i16;
 28        value - (MODULUS) * g
 29    }
 30
 31    pub const fn multiply(&self, other: Self) -> Self {
 32        FalconFelt((self.0 * other.0) % MODULUS as u32)
 33    }
 34}
 35
 36impl Add for FalconFelt {
 37    type Output = Self;
 38
 39    #[allow(clippy::suspicious_arithmetic_impl)]
 40    fn add(self, rhs: Self) -> Self::Output {
 41        let (s, _) = self.0.overflowing_add(rhs.0);
 42        let (d, n) = s.overflowing_sub(MODULUS as u32);
 43        let (r, _) = d.overflowing_add(MODULUS as u32 * (n as u32));
 44        FalconFelt(r)
 45    }
 46}
 47
 48impl AddAssign for FalconFelt {
 49    fn add_assign(&mut self, rhs: Self) {
 50        *self = *self + rhs;
 51    }
 52}
 53
 54impl Sub for FalconFelt {
 55    type Output = Self;
 56
 57    fn sub(self, rhs: Self) -> Self::Output {
 58        self + -rhs
 59    }
 60}
 61
 62impl SubAssign for FalconFelt {
 63    fn sub_assign(&mut self, rhs: Self) {
 64        *self = *self - rhs;
 65    }
 66}
 67
 68impl Neg for FalconFelt {
 69    type Output = FalconFelt;
 70
 71    fn neg(self) -> Self::Output {
 72        let is_nonzero = self.0 != 0;
 73        let r = MODULUS as u32 - self.0;
 74        FalconFelt(r * (is_nonzero as u32))
 75    }
 76}
 77
 78impl Mul for FalconFelt {
 79    fn mul(self, rhs: Self) -> Self::Output {
 80        FalconFelt((self.0 * rhs.0) % MODULUS as u32)
 81    }
 82
 83    type Output = Self;
 84}
 85
 86impl MulAssign for FalconFelt {
 87    fn mul_assign(&mut self, rhs: Self) {
 88        *self = *self * rhs;
 89    }
 90}
 91
 92impl Div for FalconFelt {
 93    type Output = FalconFelt;
 94
 95    #[allow(clippy::suspicious_arithmetic_impl)]
 96    fn div(self, rhs: Self) -> Self::Output {
 97        self * rhs.inverse_or_zero()
 98    }
 99}
100
101impl DivAssign for FalconFelt {
102    fn div_assign(&mut self, rhs: Self) {
103        *self = *self / rhs
104    }
105}
106
107impl Zero for FalconFelt {
108    fn zero() -> Self {
109        FalconFelt::new(0)
110    }
111
112    fn is_zero(&self) -> bool {
113        self.0 == 0
114    }
115}
116
117impl One for FalconFelt {
118    fn one() -> Self {
119        FalconFelt::new(1)
120    }
121}
122
123impl Inverse for FalconFelt {
124    fn inverse_or_zero(self) -> Self {
125        // q-2 = 0b10 11 11 11  11 11 11
126        let two = self.multiply(self);
127        let three = two.multiply(self);
128        let six = three.multiply(three);
129        let twelve = six.multiply(six);
130        let fifteen = twelve.multiply(three);
131        let thirty = fifteen.multiply(fifteen);
132        let sixty = thirty.multiply(thirty);
133        let sixty_three = sixty.multiply(three);
134
135        let sixty_three_sq = sixty_three.multiply(sixty_three);
136        let sixty_three_qu = sixty_three_sq.multiply(sixty_three_sq);
137        let sixty_three_oc = sixty_three_qu.multiply(sixty_three_qu);
138        let sixty_three_hx = sixty_three_oc.multiply(sixty_three_oc);
139        let sixty_three_tt = sixty_three_hx.multiply(sixty_three_hx);
140        let sixty_three_sf = sixty_three_tt.multiply(sixty_three_tt);
141
142        let all_ones = sixty_three_sf.multiply(sixty_three);
143        let two_e_twelve = all_ones.multiply(self);
144        let two_e_thirteen = two_e_twelve.multiply(two_e_twelve);
145
146        two_e_thirteen.multiply(all_ones)
147    }
148}
149
150impl CyclotomicFourier for FalconFelt {
151    fn primitive_root_of_unity(n: usize) -> Self {
152        let log2n = n.ilog2();
153        assert!(log2n <= 12);
154        // and 1331 is a twelfth root of unity
155        let mut a = FalconFelt::new(1331);
156        let num_squarings = 12 - n.ilog2();
157        for _ in 0..num_squarings {
158            a *= a;
159        }
160        a
161    }
162}
163
164impl TryFrom<u32> for FalconFelt {
165    type Error = String;
166
167    fn try_from(value: u32) -> Result<Self, Self::Error> {
168        if value >= MODULUS as u32 {
169            Err(format!("value {value} is greater than or equal to the field modulus {MODULUS}"))
170        } else {
171            Ok(FalconFelt::new(value as i16))
172        }
173    }
174}