//! Subtracts `q` times the normalized divisor from a dividend slice, returning the borrow.
use super::KnuthD;

impl KnuthD {
    /// Subtracts `q * vn[0..n]` from `u[0..n]`, returning the borrow.
    ///
    /// Used in the overflow path of the main division loop when the quotient
    /// digit estimate is `u64::MAX` and a full n-limb multiply-subtract is
    /// needed.
    #[inline]
    pub(crate) fn submul(&self, u: &mut [u64], q: u64) -> u64 {
        let mut borrow: u64 = 0;
        // Range loop is faster than zip+take iterators here (measured ~17% regression).
        #[allow(clippy::needless_range_loop)]
        for i in 0..self.n {
            let prod = (q as u128) * (self.vn[i] as u128) + (borrow as u128);
            let (diff, b) = u[i].overflowing_sub(prod as u64);
            u[i] = diff;
            borrow = (prod >> 64) as u64 + b as u64;
        }
        borrow
    }
}

#[cfg(test)]
mod ai_tests {
    use super::*;

    /// Subtracting 1 * v from u gives u - v.
    #[test]
    fn submul_by_one() {
        let kd = KnuthD::new(&[3, 1u64 << 63, 0, 0], 2);
        let mut u = [10u64, 1u64 << 63, 0, 0];
        let borrow = kd.submul(&mut u, 1);
        assert_eq!(borrow, 0);
        assert_eq!(u[0], 7); // 10 - 3
        assert_eq!(u[1], 0); // (1<<63) - (1<<63)
    }

    /// Subtracting 0 * v leaves u unchanged.
    #[test]
    fn submul_by_zero() {
        let kd = KnuthD::new(&[5, 1u64 << 63, 0, 0], 2);
        let mut u = [42u64, 99, 0, 0];
        let borrow = kd.submul(&mut u, 0);
        assert_eq!(borrow, 0);
        assert_eq!(u[0], 42);
        assert_eq!(u[1], 99);
    }

    /// Submul that produces a borrow.
    #[test]
    fn submul_with_borrow() {
        let kd = KnuthD::new(&[5, 1u64 << 63, 0, 0], 2);
        let mut u = [0u64, 0, 0, 0];
        let borrow = kd.submul(&mut u, 1);
        // u[0] = 0 - 5 = wraps, borrow propagates
        assert!(borrow > 0);
    }
}
