//! Remainder of a 512-bit value divided by a `U256` divisor.
use crate::knuth_d::KnuthD;
use crate::u256::U256;

use super::U512;

impl U512 {
    /// Computes the remainder of dividing this 512-bit value by a [`U256`]
    /// divisor.
    ///
    /// Dispatches to the appropriate algorithm based on the divisor's size:
    /// - **1 limb**: single-digit division via [`div_u64`](U512::div_u64).
    /// - **2–4 limbs**: Knuth Algorithm D with MG10 reciprocal estimation
    ///   via [`KnuthD`].
    ///
    /// This is the reduction step for modular multiplication: after a
    /// widening multiply produces a 512-bit product, this method reduces
    /// it modulo the 256-bit modulus.
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u256::U256;
    /// use cnfy_uint::u512::U512;
    ///
    /// let dividend = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 42]);
    /// let divisor = U256::from_be_limbs([0, 0, 0, 7]);
    /// assert_eq!(dividend.div_u256(&divisor), U256::ZERO);
    /// ```
    pub fn div_u256(&self, divisor: &U256) -> U256 {
        if self.is_zero() {
            return U256::ZERO;
        }

        let n = divisor.sig_limbs();
        match n {
            1 => {
                let r = self.div_u64(divisor.0[0]);
                U256([r, 0, 0, 0])
            }
            _ => {
                let v_le = divisor.to_le_limbs();
                KnuthD::new(&v_le, n).rem(self)
            }
        }
    }
}

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

    /// Small dividend mod P.
    #[test]
    fn basic() {
        let dividend = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 42]);
        assert_eq!(dividend.div_u256(&P), U256::from_be_limbs([0, 0, 0, 42]));
    }

    /// (2^256-1)^2 mod P.
    #[test]
    fn max_squared() {
        let max = U256::from_be_limbs([u64::MAX; 4]);
        let product = max * max;
        let reduced = U256::from_be_limbs([0, 0, 0, 0x1000003D0]);
        let expected = reduced.mul_mod(&reduced, &P);
        assert_eq!(product.div_u256(&P), expected);
    }

    /// 2-limb divisor.
    #[test]
    fn two_limb_divisor() {
        let dividend = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 1, 0]);
        let divisor = U256::from_be_limbs([0, 0, 1, 1]);
        assert_eq!(
            dividend.div_u256(&divisor),
            U256::from_be_limbs([0, 0, 1, 0])
        );
    }

    /// (P-1)^2 mod P = 1.
    #[test]
    fn p_minus_one_squared() {
        let p_minus_1 = U256::from_be_limbs([
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFEFFFFFC2E,
        ]);
        let product = p_minus_1 * p_minus_1;
        assert_eq!(product.div_u256(&P), U256::ONE);
    }

    /// k * P mod P = 0.
    #[test]
    fn multiple_of_p() {
        let small = U256::from_be_limbs([0, 0, 0, 42]);
        let product = small * P;
        assert_eq!(product.div_u256(&P), U256::ZERO);
    }

    /// Zero dividend.
    #[test]
    fn zero_dividend() {
        let dividend = U512::from_be_limbs([0; 8]);
        assert_eq!(dividend.div_u256(&P), U256::ZERO);
    }

    /// Single-limb divisor path.
    #[test]
    fn single_limb_divisor() {
        let dividend = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 100]);
        let divisor = U256::from_be_limbs([0, 0, 0, 7]);
        // 100 % 7 = 2
        assert_eq!(
            dividend.div_u256(&divisor),
            U256::from_be_limbs([0, 0, 0, 2])
        );
    }
}
