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