//! Adds the divisor back to the dividend after a quotient overestimate (Knuth Algorithm D correction step).
use super::KnuthD;

impl KnuthD {
    /// Adds `vn[0..n]` to `u[0..n+1]` (Knuth Algorithm D add-back correction).
    ///
    /// Called when the quotient digit was overestimated by 1 and the
    /// multiply-subtract produced a negative result. Restores `u` by
    /// adding the divisor back. This path is extremely rare in practice
    /// (probability ~2/b where b = 2^64).
    #[inline]
    pub(crate) fn add_back(&self, u: &mut [u64]) {
        let mut carry: 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 sum = (u[i] as u128) + (self.vn[i] as u128) + (carry as u128);
            u[i] = sum as u64;
            carry = (sum >> 64) as u64;
        }
        u[self.n] = u[self.n].wrapping_add(carry);
    }
}

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

    /// Adding back after zeroing gives the divisor itself.
    #[test]
    fn add_back_to_zero() {
        let kd = KnuthD::new(&[3, 1u64 << 63, 0, 0], 2);
        let mut u = [0u64, 0, 0];
        kd.add_back(&mut u);
        assert_eq!(u[0], kd.vn[0]);
        assert_eq!(u[1], kd.vn[1]);
    }

    /// Adding back with carry propagation.
    #[test]
    fn add_back_with_carry() {
        let kd = KnuthD::new(&[u64::MAX, 1u64 << 63, 0, 0], 2);
        let mut u = [1u64, 0, 0];
        kd.add_back(&mut u);
        // u[0] = 1 + MAX = 0 (carry 1)
        // u[1] = 0 + (1<<63) + 1 = (1<<63) + 1
        assert_eq!(u[0], 0);
        assert_eq!(u[1], (1u64 << 63) + 1);
    }
}
