1pub mod prime;
  2pub mod barrett;
  3pub mod montgomery;
  4pub mod impl_u64;
  5
  6pub type REDUCEMOD = u8;
  7
  8pub const NONE: REDUCEMOD = 0;
  9pub const ONCE: REDUCEMOD = 1;
 10pub const TWICE: REDUCEMOD = 2;
 11pub const FOURTIMES: REDUCEMOD = 3;
 12pub const BARRETT: REDUCEMOD = 4;
 13pub const BARRETTLAZY: REDUCEMOD = 5;
 14
 15pub trait WordOps<O>{
 16    fn log2(self) -> O;
 17    fn reverse_bits_msb(self, n:u32) -> O;
 18}
 19
 20impl WordOps<u64> for u64{
 21    #[inline(always)]
 22    fn log2(self) -> u64{
 23        (u64::BITS - (self-1).leading_zeros()) as _
 24    }
 25    #[inline(always)]
 26    fn reverse_bits_msb(self, n: u32) -> u64{
 27        self.reverse_bits() >> (usize::BITS - n)
 28    }
 29}
 30
 31impl WordOps<usize> for usize{
 32    #[inline(always)]
 33    fn log2(self) -> usize{
 34        (usize::BITS - (self-1).leading_zeros()) as _
 35    }
 36    #[inline(always)]
 37    fn reverse_bits_msb(self, n: u32) -> usize{
 38        self.reverse_bits() >> (usize::BITS - n)
 39    }
 40}
 41
 42pub trait ReduceOnce<O>{
 43    /// Assigns self-q to self if self >= q in constant time.
 44    /// User must ensure that 2q fits in O.
 45    fn reduce_once_constant_time_assign(&mut self, q: O);
 46    /// Returns self-q if self >= q else self in constant time.
 47    /// /// User must ensure that 2q fits in O.
 48    fn reduce_once_constant_time(&self, q:O) -> O;
 49    /// Assigns self-q to self if self >= q.
 50    /// /// User must ensure that 2q fits in O.
 51    fn reduce_once_assign(&mut self, q: O);
 52    /// Returns self-q if self >= q else self.
 53    /// /// User must ensure that 2q fits in O.
 54    fn reduce_once(&self, q:O) -> O;
 55}
 56
 57pub trait WordOperations<O>{
 58
 59    // Applies a parameterized modular reduction.
 60    fn word_reduce_assign<const REDUCE:REDUCEMOD>(&self, x: &mut O);
 61
 62    // Assigns a + b to c.
 63    fn word_add_binary_assign<const REDUCE:REDUCEMOD>(&self, a: &O, b:&O, c: &mut O);
 64
 65    // Assigns a + b to b.
 66    fn word_add_unary_assign<const REDUCE:REDUCEMOD>(&self, a: &O, b: &mut O);
 67
 68    // Assigns a - b to c.
 69    fn word_sub_binary_assign<const REDUCE:REDUCEMOD>(&self, a: &O, b:&O, c: &mut O);
 70
 71    // Assigns b - a to b.
 72    fn word_sub_unary_assign<const REDUCE:REDUCEMOD>(&self, a: &O, b: &mut O);
 73
 74    // Assigns -a to a.
 75    fn word_neg_unary_assign<const REDUCE:REDUCEMOD>(&self, a:&mut O);
 76
 77    // Assigns -a to b.
 78    fn word_neg_binary_assign<const REDUCE:REDUCEMOD>(&self, a: &O, b:&mut O);
 79
 80    // Assigns a * 2^64 to b.
 81    fn word_prepare_montgomery_assign<const REDUCE:REDUCEMOD>(&self, a: &O, b: &mut montgomery::Montgomery<O>);
 82
 83    // Assigns a * b to c.
 84    fn word_mul_montgomery_external_binary_assign<const REDUCE:REDUCEMOD>(&self, a:&montgomery::Montgomery<O>, b:&O, c: &mut O);
 85
 86    // Assigns a * b to b.
 87    fn word_mul_montgomery_external_unary_assign<const REDUCE:REDUCEMOD>(&self, a:&montgomery::Montgomery<O>, b:&mut O);
 88
 89    // Assigns a * b to c.
 90    fn word_mul_barrett_binary_assign<const REDUCE:REDUCEMOD>(&self, a: &barrett::Barrett<O>, b:&O, c: &mut O);
 91
 92    // Assigns a * b to b.
 93    fn word_mul_barrett_unary_assign<const REDUCE:REDUCEMOD>(&self, a:&barrett::Barrett<O>, b:&mut O);
 94
 95    // Assigns (a + 2q - b) * c to d.
 96    fn word_sum_aqqmb_prod_c_barrett_assign_d<const REDUCE:REDUCEMOD>(&self, a: &O, b: &O, c: &barrett::Barrett<O>, d: &mut O);
 97
 98    // Assigns (a + 2q - b) * c to b.
 99    fn word_sum_aqqmb_prod_c_barrett_assign_b<const REDUCE:REDUCEMOD>(&self, a: &u64, c: &barrett::Barrett<u64>, b: &mut u64);
100}
101
102pub trait VecOperations<O>{
103
104    // Applies a parameterized modular reduction.
105    fn vec_reduce_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, x: &mut [O]);
106
107    // Assigns a[i] + b[i] to c[i]
108    fn vec_add_binary_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b:&[O], c: &mut [O]);
109
110    // Assigns a[i] + b[i] to b[i]
111    fn vec_add_unary_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b: &mut [O]);
112
113    // Assigns a[i] - b[i] to c[i]
114    fn vec_sub_binary_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b:&[O], c: &mut [O]);
115
116    // Assigns a[i] - b[i] to b[i]
117    fn vec_sub_unary_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b: &mut [O]);
118
119    // Assigns -a[i] to a[i].
120    fn vec_neg_unary_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &mut [O]);
121
122    // Assigns -a[i] to a[i].
123    fn vec_neg_binary_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b: &mut [O]);
124
125    // Assigns a * 2^64 to b.
126    fn vec_prepare_montgomery_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[O], b: &mut [montgomery::Montgomery<O>]);
127
128    // Assigns a[i] * b[i] to c[i].
129    fn vec_mul_montgomery_external_binary_assign<const CHUNK:usize,const REDUCE:REDUCEMOD>(&self, a:&[montgomery::Montgomery<O>], b:&[O], c: &mut [O]);
130
131    // Assigns a[i] * b[i] to b[i].
132    fn vec_mul_montgomery_external_unary_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a:&[montgomery::Montgomery<O>], b:&mut [O]);
133
134    // Assigns a * b[i] to b[i].
135    fn vec_mul_scalar_barrett_external_unary_assign<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a:& barrett::Barrett<u64>, b:&mut [u64]);
136
137    // Assigns a * b[i] to c[i].
138    fn vec_mul_scalar_barrett_external_binary_assign<const CHUNK:usize,const REDUCE:REDUCEMOD>(&self, a:& barrett::Barrett<u64>, b:&[u64], c: &mut [u64]);
139
140    // Assigns (a[i] + 2q - b[i]) * c to d[i].
141    fn vec_sum_aqqmb_prod_c_scalar_barrett_assign_d<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[u64], b: &[u64], c: &barrett::Barrett<u64>, d: &mut [u64]);
142
143    // Assigns (a[i] + 2q - b[i]) * c to b[i].
144    fn vec_sum_aqqmb_prod_c_scalar_barrett_assign_b<const CHUNK:usize, const REDUCE:REDUCEMOD>(&self, a: &[u64], c: &barrett::Barrett<u64>, b: &mut [u64]);
145}
146
147
148
149