//! Integer division returning quotient and remainder.
use super::U256;

impl U256 {
    /// Computes `(floor(self / divisor), self % divisor)` via base-256 long
    /// division.
    ///
    /// Left-aligns the divisor by shifting out leading zero bytes, then
    /// extracts one base-256 quotient digit per byte position via repeated
    /// subtraction. Returns the integer quotient and remainder as a tuple.
    ///
    /// # Panics
    ///
    /// Loops indefinitely if `divisor` is zero.
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u256::U256;
    ///
    /// let a = U256::from_be_limbs([0, 0, 0, 10]);
    /// let b = U256::from_be_limbs([0, 0, 0, 3]);
    /// let (q, r) = a.div_rem(&b);
    /// assert_eq!(q, U256::from_be_limbs([0, 0, 0, 3]));
    /// assert_eq!(r, U256::from_be_limbs([0, 0, 0, 1]));
    /// ```
    #[inline]
    pub fn div_rem(&self, divisor: &U256) -> (U256, U256) {
        let zeros = divisor.leading_zero_bytes();
        let mut shifted = divisor.shl_bytes(zeros);
        let mut dividend = *self;
        let mut quotient = U256::ZERO;

        loop {
            let mut digit: u8 = 0;
            while dividend >= shifted {
                let (reduced, _) = dividend.overflowing_sub(&shifted);
                dividend = reduced;
                digit += 1;
            }
            quotient = quotient.shl_bytes(1);
            quotient.0[0] |= digit as u64;

            if shifted.leading_zero_bytes() == zeros {
                break;
            }
            shifted = shifted.shr_bytes(1);
        }

        (quotient, dividend)
    }
}

#[cfg(test)]
mod ai_tests {
    use super::*;
    const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);

    /// 10 / 3 = quotient 3, remainder 1.
    #[test]
    fn ten_div_three() {
        let a = U256::from_be_limbs([0, 0, 0, 10]);
        let b = U256::from_be_limbs([0, 0, 0, 3]);
        let (q, r) = a.div_rem(&b);
        assert_eq!(q, U256::from_be_limbs([0, 0, 0, 3]));
        assert_eq!(r, U256::from_be_limbs([0, 0, 0, 1]));
    }

    /// 8 / 2 = quotient 4, remainder 0 (exact).
    #[test]
    fn eight_div_two_exact() {
        let a = U256::from_be_limbs([0, 0, 0, 8]);
        let b = U256::from_be_limbs([0, 0, 0, 2]);
        let (q, r) = a.div_rem(&b);
        assert_eq!(q, U256::from_be_limbs([0, 0, 0, 4]));
        assert_eq!(r, U256::ZERO);
    }

    /// Zero divided by any non-zero value is (0, 0).
    #[test]
    fn zero_dividend() {
        let (q, r) = U256::ZERO.div_rem(&U256::ONE);
        assert_eq!(q, U256::ZERO);
        assert_eq!(r, U256::ZERO);
    }

    /// Self-division yields quotient 1, remainder 0.
    #[test]
    fn self_division() {
        let a = U256::from_be_limbs([0x1234, 0x5678, 0x9ABC, 0xDEF0]);
        let (q, r) = a.div_rem(&a);
        assert_eq!(q, U256::ONE);
        assert_eq!(r, U256::ZERO);
    }

    /// Dividend smaller than divisor yields quotient 0, remainder = dividend.
    #[test]
    fn dividend_less_than_divisor() {
        let a = U256::from_be_limbs([0, 0, 0, 3]);
        let b = U256::from_be_limbs([0, 0, 0, 10]);
        let (q, r) = a.div_rem(&b);
        assert_eq!(q, U256::ZERO);
        assert_eq!(r, a);
    }

    /// P / 2 = (P - 1) / 2 with remainder 1 (P is odd).
    #[test]
    fn p_div_two() {
        let two = U256::from_be_limbs([0, 0, 0, 2]);
        let (q, r) = P.div_rem(&two);
        assert_eq!(
            q,
            U256::from_be_limbs([
                0x7FFFFFFFFFFFFFFF,
                0xFFFFFFFFFFFFFFFF,
                0xFFFFFFFFFFFFFFFF,
                0xFFFFFFFF7FFFFE17,
            ]),
        );
        assert_eq!(r, U256::ONE);
    }

    /// 0xFF..FF / 3 = 0x55..55 remainder 0 (exact division).
    #[test]
    fn all_ff_div_three_exact() {
        let a = U256::from_be_bytes([0xFF; 32]);
        let b = U256::from_be_limbs([0, 0, 0, 3]);
        let (q, r) = a.div_rem(&b);
        assert_eq!(
            q,
            U256::from_be_limbs([
                0x5555555555555555,
                0x5555555555555555,
                0x5555555555555555,
                0x5555555555555555,
            ]),
        );
        assert_eq!(r, U256::ZERO);
    }

    /// Quotient x divisor + remainder reconstructs the dividend.
    #[test]
    fn reconstruction() {
        let a = U256::from_be_limbs([0, 0, 0, 100]);
        let b = U256::from_be_limbs([0, 0, 0, 7]);
        let (q, r) = a.div_rem(&b);
        assert_eq!(q, U256::from_be_limbs([0, 0, 0, 14]));
        assert_eq!(r, U256::from_be_limbs([0, 0, 0, 2]));
    }

    /// Large dividend divided by large divisor with small quotient.
    #[test]
    fn large_div_large() {
        let a = U256::from_be_limbs([
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFEFFFFFC2E,
        ]);
        let b = U256::from_be_limbs([
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFEFFFFFC2D,
        ]);
        let (q, r) = a.div_rem(&b);
        assert_eq!(q, U256::ONE);
        assert_eq!(r, U256::ONE);
    }
}
