//! Remainder of a 512-bit value divided by a single `u64` via schoolbook long division.
use super::U512;

impl U512 {
    /// Computes the remainder of dividing this 512-bit value by a single `u64`
    /// divisor using schoolbook long division.
    ///
    /// Iterates the eight limbs from most-significant to least-significant,
    /// carrying the running 128-bit remainder across each step. Returns
    /// only the final remainder (the quotient is discarded).
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u512::U512;
    ///
    /// let v = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 100]);
    /// assert_eq!(v.div_u64(7), 2); // 100 % 7 = 2
    /// ```
    #[inline]
    pub fn div_u64(&self, d: u64) -> u64 {
        let divisor = d as u128;
        let mut rem: u128 = 0;
        let mut i = 7i32;
        while i >= 0 {
            let cur = (rem << 64) | (self.0[i as usize] as u128);
            rem = cur % divisor;
            i -= 1;
        }
        rem as u64
    }
}

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

    /// 100 % 7 = 2.
    #[test]
    fn small_value() {
        let v = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 100]);
        assert_eq!(v.div_u64(7), 2);
    }

    /// Zero divided by anything is zero.
    #[test]
    fn zero_dividend() {
        let v = U512::from_be_limbs([0; 8]);
        assert_eq!(v.div_u64(42), 0);
    }

    /// Dividing by 1 always gives remainder 0.
    #[test]
    fn div_by_one() {
        let v = U512::from_be_limbs([0x1234, 0x5678, 0x9ABC, 0xDEF0, 1, 2, 3, 4]);
        assert_eq!(v.div_u64(1), 0);
    }

    /// Value equal to divisor gives remainder 0.
    #[test]
    fn exact_division() {
        let v = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 42]);
        assert_eq!(v.div_u64(42), 0);
    }

    /// Large dividend with high limbs set.
    #[test]
    fn large_dividend() {
        // 2^64 % 10 = 6 (since 2^64 = 1844674407370955161 * 10 + 6)
        let v = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 1, 0]);
        assert_eq!(v.div_u64(10), 6);
    }

    /// All limbs set to MAX, divide by MAX gives remainder 0.
    #[test]
    fn max_div_max() {
        let v = U512::from_be_limbs([u64::MAX; 8]);
        assert_eq!(v.div_u64(u64::MAX), 0);
    }

    /// MSB-only dividend exercises the carry propagation.
    #[test]
    fn msb_only() {
        let v = U512::from_be_limbs([1, 0, 0, 0, 0, 0, 0, 0]);
        // 2^448 % 10:  2^448 mod 10
        // 2^1=2, 2^2=4, 2^3=8, 2^4=6, cycle of 4: 448 % 4 = 0 → 2^448 mod 10 = 6
        assert_eq!(v.div_u64(10), 6);
    }
}
