1pub mod prime;
  2pub mod barrett;
  3pub mod montgomery;
  4pub mod shoup;
  5pub mod impl_u64;
  6
  7
  8
  9pub trait WordOps<O>{
 10    fn log2(self) -> O;
 11    fn reverse_bits_msb(self, n:u32) -> O;
 12}
 13
 14impl WordOps<u64> for u64{
 15    #[inline(always)]
 16    fn log2(self) -> u64{
 17        (u64::BITS - (self-1).leading_zeros()) as _
 18    }
 19    #[inline(always)]
 20    fn reverse_bits_msb(self, n: u32) -> u64{
 21        self.reverse_bits() >> (usize::BITS - n)
 22    }
 23}
 24
 25impl WordOps<usize> for usize{
 26    #[inline(always)]
 27    fn log2(self) -> usize{
 28        (usize::BITS - (self-1).leading_zeros()) as _
 29    }
 30    #[inline(always)]
 31    fn reverse_bits_msb(self, n: u32) -> usize{
 32        self.reverse_bits() >> (usize::BITS - n)
 33    }
 34}
 35
 36pub trait ReduceOnce<O>{
 37    /// Assigns self-q to self if self >= q in constant time.
 38    /// User must ensure that 2q fits in O.
 39    fn reduce_once_constant_time_assign(&mut self, q: O);
 40    /// Returns self-q if self >= q else self in constant time.
 41    /// /// User must ensure that 2q fits in O.
 42    fn reduce_once_constant_time(&self, q:O) -> O;
 43    /// Assigns self-q to self if self >= q.
 44    /// /// User must ensure that 2q fits in O.
 45    fn reduce_once_assign(&mut self, q: O);
 46    /// Returns self-q if self >= q else self.
 47    /// /// User must ensure that 2q fits in O.
 48    fn reduce_once(&self, q:O) -> O;
 49}
 50
 51impl ReduceOnce<u64> for u64{
 52    #[inline(always)]
 53    fn reduce_once_constant_time_assign(&mut self, q: u64){
 54        debug_assert!(q < 0x8000000000000000, "2q >= 2^64");
 55        *self -= (q.wrapping_sub(*self)>>63)*q;
 56    }
 57    
 58    #[inline(always)]
 59    fn reduce_once_constant_time(&self, q:u64) -> u64{
 60        debug_assert!(q < 0x8000000000000000, "2q >= 2^64");
 61        self - (q.wrapping_sub(*self)>>63)*q
 62    }
 63
 64    #[inline(always)]
 65    fn reduce_once_assign(&mut self, q: u64){
 66        debug_assert!(q < 0x8000000000000000, "2q >= 2^64");
 67        *self = (*self).min(self.wrapping_sub(q))
 68    }
 69
 70    #[inline(always)]
 71    fn reduce_once(&self, q:u64) -> u64{
 72        debug_assert!(q < 0x8000000000000000, "2q >= 2^64");
 73        (*self).min(self.wrapping_sub(q))
 74    }
 75}
 76
 77
 78pub trait Operations<O>{
 79    // Assigns a + b to c.
 80    fn add_binary_assign(&self, a: &O, b:&O, c: &mut O);
 81
 82    // Assigns a + b to b.
 83    fn add_unary_assign(&self, a: &O, b: &mut O);
 84
 85    // Assigns a[i] + b[i] to c[i]
 86    fn add_vec_binary_assign<const CHUNK:usize>(&self, a: &[O], b:&[O], c: &mut [O]);
 87
 88    // Assigns a[i] + b[i] to b[i]
 89    fn add_vec_unary_assign<const CHUNK:usize>(&self, a: &[O], b: &mut [O]);
 90
 91    // Assigns a - b to c.
 92    fn sub_binary_assign(&self, a: &O, b:&O, c: &mut O);
 93
 94    // Assigns b - a to b.
 95    fn sub_unary_assign(&self, a: &O, b: &mut O);
 96
 97    // Assigns a[i] - b[i] to c[i]
 98    fn sub_vec_binary_assign<const CHUNK:usize>(&self, a: &[O], b:&[O], c: &mut [O]);
 99
100    // Assigns a[i] - b[i] to b[i]
101    fn sub_vec_unary_assign<const CHUNK:usize>(&self, a: &[O], b: &mut [O]);
102
103    // Assigns -a to a.
104    fn neg_assign(&self, a:&mut O);
105
106    // Assigns -a[i] to a[i].
107    fn neg_vec_assign<const CHUNK:usize>(&self, a: &mut [O]);
108}
109
110