1pub mod prime;
 2pub mod barrett;
 3pub mod montgomery;
 4pub mod shoup;
 5pub mod impl_u64;
 6
 7pub trait WordOps<O>{
 8    fn log2(self) -> O;
 9    fn reverse_bits_msb(self, n:u32) -> O;
10}
11
12impl WordOps<u64> for u64{
13    #[inline(always)]
14    fn log2(self) -> u64{
15        (u64::BITS - (self-1).leading_zeros()) as _
16    }
17    #[inline(always)]
18    fn reverse_bits_msb(self, n: u32) -> u64{
19        self.reverse_bits() >> (usize::BITS - n)
20    }
21}
22
23impl WordOps<usize> for usize{
24    #[inline(always)]
25    fn log2(self) -> usize{
26        (usize::BITS - (self-1).leading_zeros()) as _
27    }
28    #[inline(always)]
29    fn reverse_bits_msb(self, n: u32) -> usize{
30        self.reverse_bits() >> (usize::BITS - n)
31    }
32}
33
34pub trait ReduceOnce<O>{
35    /// Assigns self-q to self if self >= q in constant time.
36    /// User must ensure that 2q fits in O.
37    fn reduce_once_constant_time_assign(&mut self, q: O);
38    /// Returns self-q if self >= q else self in constant time.
39    /// /// User must ensure that 2q fits in O.
40    fn reduce_once_constant_time(&self, q:O) -> O;
41    /// Assigns self-q to self if self >= q.
42    /// /// User must ensure that 2q fits in O.
43    fn reduce_once_assign(&mut self, q: O);
44    /// Returns self-q if self >= q else self.
45    /// /// User must ensure that 2q fits in O.
46    fn reduce_once(&self, q:O) -> O;
47}
48
49impl ReduceOnce<u64> for u64{
50    #[inline(always)]
51    fn reduce_once_constant_time_assign(&mut self, q: u64){
52        debug_assert!(q < 0x8000000000000000, "2q >= 2^64");
53        *self -= (q.wrapping_sub(*self)>>63)*q;
54    }
55    
56    #[inline(always)]
57    fn reduce_once_constant_time(&self, q:u64) -> u64{
58        debug_assert!(q < 0x8000000000000000, "2q >= 2^64");
59        self - (q.wrapping_sub(*self)>>63)*q
60    }
61
62    #[inline(always)]
63    fn reduce_once_assign(&mut self, q: u64){
64        debug_assert!(q < 0x8000000000000000, "2q >= 2^64");
65        *self = (*self).min(self.wrapping_sub(q))
66    }
67
68    #[inline(always)]
69    fn reduce_once(&self, q:u64) -> u64{
70        debug_assert!(q < 0x8000000000000000, "2q >= 2^64");
71        (*self).min(self.wrapping_sub(q))
72    }
73}