1use crate::modulus::barrett::{Barrett, BarrettPrecomp};
 2use crate::modulus::ReduceOnce;
 3
 4use num_bigint::BigUint;
 5use num_traits::cast::ToPrimitive;
 6
 7impl BarrettPrecomp<u64>{
 8    
 9    pub fn new(q: u64) -> BarrettPrecomp<u64> {
10        let big_r: BigUint = (BigUint::from(1 as usize)<<((u64::BITS<<1) as usize)) / BigUint::from(q);
11        let lo: u64 = (&big_r & BigUint::from(u64::MAX)).to_u64().unwrap();
12        let hi: u64 = (big_r >> u64::BITS).to_u64().unwrap();
13        let mut precomp: BarrettPrecomp<u64> = Self{q, lo, hi, one:Barrett(0,0)};
14        precomp.one = precomp.prepare(1);
15        precomp
16    }
17
18    #[inline(always)]
19    pub fn one(&self) -> Barrett<u64> {
20        self.one
21    }
22
23    #[inline(always)]
24    pub fn prepare(&self, v: u64) -> Barrett<u64> {
25        debug_assert!(v < self.q);
26        let quotient: u64 = (((v as u128) << 64) / self.q as u128) as _;
27        Barrett(v, quotient)
28    }
29
30    /// Returns lhs mod q.
31    #[inline(always)]
32    pub fn reduce(&self, lhs: u64) -> u64{
33        let mut r: u64 = self.reduce_lazy(lhs);
34        r.reduce_once_assign(self.q);
35        r
36    }
37
38    /// Returns lhs mod q in range [0, 2q-1].
39    #[inline(always)]
40    pub fn reduce_lazy(&self, lhs: u64) -> u64{
41        let (_, mhi) = lhs.widening_mul(self.hi);
42        lhs - mhi.wrapping_mul(self.q)
43    }
44
45    /// Assigns lhs mod q to lhs.
46    #[inline(always)]
47    pub fn reduce_assign(&self, lhs: &mut u64){
48        self.reduce_lazy_assign(lhs);
49        lhs.reduce_once_assign(self.q);
50    }
51
52    /// Assigns lhs mod q in range [0, 2q-1] to lhs.
53    #[inline(always)]
54    pub fn reduce_lazy_assign(&self, lhs: &mut u64){
55        let (_, mhi) = lhs.widening_mul(self.hi);
56        *lhs = *lhs - mhi.wrapping_mul(self.q)
57    }
58
59    #[inline(always)]
60    pub fn mul_external(&self, lhs: Barrett<u64>, rhs: u64) -> u64 {
61        let mut r: u64 = self.mul_external_lazy(lhs, rhs);
62        r.reduce_once_assign(self.q);
63        r
64    }
65
66    #[inline(always)]
67    pub fn mul_external_assign(&self, lhs: Barrett<u64>, rhs: &mut u64){
68        self.mul_external_lazy_assign(lhs, rhs);
69        rhs.reduce_once_assign(self.q);
70    }
71
72    #[inline(always)]
73    pub fn mul_external_lazy(&self, lhs: Barrett<u64>, rhs: u64) -> u64 {
74        let mut r: u64 = rhs;
75        self.mul_external_lazy_assign(lhs, &mut r);
76        r
77    }
78
79    #[inline(always)]
80    pub fn mul_external_lazy_assign(&self, lhs: Barrett<u64>, rhs: &mut u64){
81        let t: u64 = ((*lhs.quotient() as u128 * *rhs as u128) >> 64) as _;
82        *rhs = (rhs.wrapping_mul(*lhs.value())).wrapping_sub(self.q.wrapping_mul(t));
83    }
84}