fn _barret_reduce()

in src/integer_arith/scalar.rs [323:367]

• 28 lines of code
• 5 McCabe index (conditional complexity)

    fn _barret_reduce(a: (u64, u64), ratio: (u64, u64), q: u64) -> u64 {
        // compute w = a*ratio >> 128.

        // start with lw(a1r1)
        let mut w = 0; 
        if a.1 != 0{
            w = a.1.wrapping_mul(ratio.1);
        }
        let a0r0 = Scalar::_multiply_u64(a.0, ratio.0);

        let a0r1 = Scalar::_multiply_u64(a.0, ratio.1);

        // w += hw(a0r1)
        w += a0r1.1;

        // compute hw(a0r0) + lw(a0r1), add carry into w. put result into tmp.
        let (tmp, carry) = Scalar::_add_u64(a0r0.1, a0r1.0);
        w += carry as u64;

        // Round2
        if a.1 != 0{
            let a1r0 = Scalar::_multiply_u64(a.1, ratio.0);
            w += a1r0.1;
            // final carry
            let (_, carry2) = Scalar::_add_u64(a1r0.0, tmp);
            w += carry2 as u64;
        }

        // low = w*q mod 2^64.
        // let low = Scalar::multiply_u64(w, q).0;
        let low = w.wrapping_mul(q);

        let mut res;
        if a.0 >= low {
            res = a.0 - low;
        } else {
            // res = a.0 + 2^64 - low.
            res = a.0 + (!low) + 1;
        }

        if res >= q {
            res -= q;
        }
        res
    }