//! Widening multiplication of two [`U256`] values into a [`U512`].
use super::U256;
use crate::u512::U512;
use core::ops::Mul;

/// Widening multiplication of two 256-bit integers, producing a 512-bit
/// result using fully-unrolled row-major schoolbook multiplication.
///
/// Each of the 4 rows computes `a[i] * b[0..3]` and accumulates into
/// the result with carry propagation. All 16 `u64×u64→u128` products
/// and their accumulations are fully unrolled (no loops) to give LLVM
/// maximum visibility into the dependency graph for register allocation
/// and instruction scheduling.
///
/// # Examples
///
/// ```
/// use cnfy_uint::u256::U256;
/// use cnfy_uint::u512::U512;
///
/// let a = U256::from_be_limbs([0, 0, 0, 7]);
/// let b = U256::from_be_limbs([0, 0, 0, 6]);
/// assert_eq!(a * b, U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 42]));
/// ```
impl Mul<U256> for U256 {
    type Output = U512;

    #[inline]
    fn mul(self, rhs: U256) -> U512 {
        let a = self.0;
        let b = rhs.0;

        // Row 0: a[0] * b[0..3]
        let p = (a[0] as u128) * (b[0] as u128);
        let r0 = p as u64;
        let carry = p >> 64;

        let p = (a[0] as u128) * (b[1] as u128) + carry;
        let r1 = p as u64;
        let carry = p >> 64;

        let p = (a[0] as u128) * (b[2] as u128) + carry;
        let r2 = p as u64;
        let carry = p >> 64;

        let p = (a[0] as u128) * (b[3] as u128) + carry;
        let r3 = p as u64;
        let r4 = (p >> 64) as u64;

        // Row 1: a[1] * b[0..3], accumulate into r[1..5]
        let p = (a[1] as u128) * (b[0] as u128) + (r1 as u128);
        let r1 = p as u64;
        let carry = p >> 64;

        let p = (a[1] as u128) * (b[1] as u128) + (r2 as u128) + carry;
        let r2 = p as u64;
        let carry = p >> 64;

        let p = (a[1] as u128) * (b[2] as u128) + (r3 as u128) + carry;
        let r3 = p as u64;
        let carry = p >> 64;

        let p = (a[1] as u128) * (b[3] as u128) + (r4 as u128) + carry;
        let r4 = p as u64;
        let r5 = (p >> 64) as u64;

        // Row 2: a[2] * b[0..3], accumulate into r[2..6]
        let p = (a[2] as u128) * (b[0] as u128) + (r2 as u128);
        let r2 = p as u64;
        let carry = p >> 64;

        let p = (a[2] as u128) * (b[1] as u128) + (r3 as u128) + carry;
        let r3 = p as u64;
        let carry = p >> 64;

        let p = (a[2] as u128) * (b[2] as u128) + (r4 as u128) + carry;
        let r4 = p as u64;
        let carry = p >> 64;

        let p = (a[2] as u128) * (b[3] as u128) + (r5 as u128) + carry;
        let r5 = p as u64;
        let r6 = (p >> 64) as u64;

        // Row 3: a[3] * b[0..3], accumulate into r[3..7]
        let p = (a[3] as u128) * (b[0] as u128) + (r3 as u128);
        let r3 = p as u64;
        let carry = p >> 64;

        let p = (a[3] as u128) * (b[1] as u128) + (r4 as u128) + carry;
        let r4 = p as u64;
        let carry = p >> 64;

        let p = (a[3] as u128) * (b[2] as u128) + (r5 as u128) + carry;
        let r5 = p as u64;
        let carry = p >> 64;

        let p = (a[3] as u128) * (b[3] as u128) + (r6 as u128) + carry;
        let r6 = p as u64;
        let r7 = (p >> 64) as u64;

        U512([r0, r1, r2, r3, r4, r5, r6, r7])
    }
}

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

    /// 7 * 6 = 42.
    #[test]
    fn small_product() {
        let a = U256::from_be_limbs([0, 0, 0, 7]);
        let b = U256::from_be_limbs([0, 0, 0, 6]);
        assert_eq!(a * b, U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 42]));
    }

    /// Anything times zero is zero.
    #[test]
    fn mul_by_zero() {
        let a = U256::from_be_limbs([0x1234, 0x5678, 0x9ABC, 0xDEF0]);
        assert_eq!(a * U256::ZERO, U512::from_be_limbs([0; 8]));
    }

    /// Multiplicative identity: x * 1 = x (in lower 256 bits).
    #[test]
    fn mul_by_one() {
        let a = U256::from_be_limbs([0x1234, 0x5678, 0x9ABC, 0xDEF0]);
        let product = a * U256::ONE;
        assert_eq!(
            product,
            U512::from_be_limbs([0, 0, 0, 0, 0x1234, 0x5678, 0x9ABC, 0xDEF0])
        );
    }

    /// Commutativity: a * b = b * a.
    #[test]
    fn commutative() {
        let a = U256::from_be_limbs([0x11, 0x22, 0x33, 0x44]);
        let b = U256::from_be_limbs([0x55, 0x66, 0x77, 0x88]);
        assert_eq!(a * b, b * a);
    }

    /// (2^64) * (2^64) = 2^128 in the 512-bit result.
    #[test]
    fn cross_limb_product() {
        let a = U256::from_be_limbs([0, 0, 1, 0]);
        let product = a * a;
        assert_eq!(product, U512::from_be_limbs([0, 0, 0, 0, 0, 1, 0, 0]));
    }

    /// (P-1)^2 produces a 512-bit result whose remainder mod P is 1.
    #[test]
    fn p_minus_one_squared_512() {
        let p_minus_1 = U256::from_be_limbs([
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFEFFFFFC2E,
        ]);
        let product = p_minus_1 * p_minus_1;
        // (P-1)^2 = P^2 - 2P + 1, so product mod P = 1
        // Just verify the product is non-zero and has high bits set
        assert_ne!(product.to_be_limbs()[0], 0);
    }

    /// Max * Max = (2^256 - 1)^2 = 2^512 - 2^257 + 1.
    #[test]
    fn max_times_max() {
        let max = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
        let product = max * max;
        assert_eq!(
            product,
            U512::from_be_limbs([
                0xFFFFFFFFFFFFFFFF,
                0xFFFFFFFFFFFFFFFF,
                0xFFFFFFFFFFFFFFFF,
                0xFFFFFFFFFFFFFFFE,
                0,
                0,
                0,
                1,
            ]),
        );
    }
}
