1use crate::modulus::ReduceOnce;
 2
 3use num_bigint::BigUint;
 4use num_traits::cast::ToPrimitive;
 5
 6#[derive(Clone, Copy, Debug, PartialEq, Eq)]
 7pub struct BarrettPrecomp<O>{
 8    q: O,
 9    lo:O,
10    hi:O,
11}
12
13impl<O> BarrettPrecomp<O>{
14
15    #[inline(always)]
16    pub fn value_hi(&self) -> &O{
17        &self.hi
18    }
19
20    #[inline(always)]
21    pub fn value_lo(&self) -> &O{
22        &self.lo
23    }
24}
25
26impl BarrettPrecomp<u64>{
27    pub fn new(q: u64) -> BarrettPrecomp<u64> {
28        let big_r: BigUint = (BigUint::from(1 as usize)<<((u64::BITS<<1) as usize)) / BigUint::from(q);
29        let lo: u64 = (&big_r & BigUint::from(u64::MAX)).to_u64().unwrap();
30        let hi: u64 = (big_r >> u64::BITS).to_u64().unwrap();
31        Self{q, lo, hi}
32    }
33
34    /// Returns lhs mod q.
35    #[inline(always)]
36    pub fn reduce(&self, lhs: u64) -> u64{
37        let mut r: u64 = self.reduce_lazy(lhs);
38        r.reduce_once_assign(self.q);
39        r
40    }
41
42    /// Returns lhs mod q in range [0, 2q-1].
43    #[inline(always)]
44    pub fn reduce_lazy(&self, lhs: u64) -> u64{
45        let (_, mhi) = lhs.widening_mul(self.hi);
46        lhs - mhi.wrapping_mul(self.q)
47    }
48}