1use crate::modulus::barrett::{Barrett, BarrettPrecomp};
 2use crate::modulus::ReduceOnce;
 3use crate::modulus::{REDUCEMOD, NONE, ONCE, TWICE, FOURTIMES, BARRETT, BARRETTLAZY};
 4
 5use num_bigint::BigUint;
 6use num_traits::cast::ToPrimitive;
 7
 8impl BarrettPrecomp<u64>{
 9    
10    pub fn new(q: u64) -> BarrettPrecomp<u64> {
11        let big_r: BigUint = (BigUint::from(1 as usize)<<((u64::BITS<<1) as usize)) / BigUint::from(q);
12        let lo: u64 = (&big_r & BigUint::from(u64::MAX)).to_u64().unwrap();
13        let hi: u64 = (big_r >> u64::BITS).to_u64().unwrap();
14        let mut precomp: BarrettPrecomp<u64> = Self{q:q, two_q:q<<1, four_q:q<<2, lo:lo, hi:hi, one:Barrett(0,0)};
15        precomp.one = precomp.prepare(1);
16        precomp
17    }
18
19    #[inline(always)]
20    pub fn one(&self) -> Barrett<u64> {
21        self.one
22    }
23
24    #[inline(always)]
25    pub fn reduce_assign<const REDUCE:REDUCEMOD>(&self, x: &mut u64){
26        match REDUCE {
27            NONE =>{},
28            ONCE =>{x.reduce_once_assign(self.q)},
29            TWICE=>{x.reduce_once_assign(self.two_q)},
30            FOURTIMES =>{x.reduce_once_assign(self.four_q)},
31            BARRETT =>{
32                let (_, mhi) = x.widening_mul(self.hi);
33                *x = *x - mhi.wrapping_mul(self.q);
34                x.reduce_once_assign(self.q);
35            },
36            BARRETTLAZY =>{
37                let (_, mhi) = x.widening_mul(self.hi);
38                *x = *x - mhi.wrapping_mul(self.q)
39            },
40            _ => unreachable!("invalid REDUCE argument")
41        }
42    }
43
44    #[inline(always)]
45    pub fn reduce<const REDUCE:REDUCEMOD>(&self, x: &u64) -> u64{
46        let mut r = *x;
47        self.reduce_assign::<REDUCE>(&mut r);
48        r
49    }
50
51    #[inline(always)]
52    pub fn prepare(&self, v: u64) -> Barrett<u64> {
53        debug_assert!(v < self.q);
54        let quotient: u64 = (((v as u128) << 64) / self.q as u128) as _;
55        Barrett(v, quotient)
56    }
57
58    #[inline(always)]
59    pub fn mul_external<const REDUCE:REDUCEMOD>(&self, lhs: Barrett<u64>, rhs: u64) -> u64 {
60        let mut r: u64 = rhs;
61        self.mul_external_assign::<REDUCE>(lhs, &mut r);
62        r
63    }
64
65    #[inline(always)]
66    pub fn mul_external_assign<const REDUCE:REDUCEMOD>(&self, lhs: Barrett<u64>, rhs: &mut u64){
67        let t: u64 = ((*lhs.quotient() as u128 * *rhs as u128) >> 64) as _;
68        *rhs = (rhs.wrapping_mul(*lhs.value())).wrapping_sub(self.q.wrapping_mul(t));
69        self.reduce_assign::<REDUCE>(rhs);
70    }
71}