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