//! Fused multiply-and-reduce for sparse primes, avoiding the U512 intermediate.
//!
//! Dispatches to `mul_mod_sparse_ct` (constant-time) when the `ct-field`
//! feature is enabled, or `mul_mod_sparse_vt` (variable-time) by default.
use super::U256;

impl U256 {
    /// Computes `(self * other) mod modulus` for sparse primes in a single
    /// fused pass: schoolbook multiply directly into sparse reduce.
    ///
    /// `comp` is the sparse prime complement: `2^256 - modulus`, which must
    /// fit in a single `u64`.
    ///
    /// With the `ct-field` feature enabled, this is constant-time (branchless
    /// reduction). Without the feature, uses early-return optimizations.
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u256::U256;
    /// let P = U256::from_be_limbs([
    ///     0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
    ///     0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
    /// ]);
    ///
    /// let a = U256::from_be_limbs([0, 0, 0, 7]);
    /// let b = U256::from_be_limbs([0, 0, 0, 6]);
    /// assert_eq!(a.mul_mod_sparse(&b, &P, 0x1000003D1), U256::from_be_limbs([0, 0, 0, 42]));
    /// ```
    #[inline]
    pub fn mul_mod_sparse(&self, other: &U256, modulus: &U256, comp: u64) -> U256 {
        #[cfg(feature = "ct-field")]
        { self.mul_mod_sparse_ct(other, modulus, comp) }
        #[cfg(not(feature = "ct-field"))]
        { self.mul_mod_sparse_vt(other, modulus, comp) }
    }
}

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

    /// Dispatcher matches VT variant for diverse inputs.
    #[test]
    fn matches_vt() {
        let cases = [
            (U256::from_be_limbs([0, 0, 0, 7]), U256::from_be_limbs([0, 0, 0, 6])),
            (U256::ZERO, U256::from_be_limbs([0x1234, 0x5678, 0x9ABC, 0xDEF0])),
            (
                U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, 0xFFFFFFFEFFFFFC2E]),
                U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, 0xFFFFFFFEFFFFFC2E]),
            ),
        ];
        for (a, b) in &cases {
            assert_eq!(
                a.mul_mod_sparse(b, &P, COMP),
                a.mul_mod_sparse_vt(b, &P, COMP),
            );
        }
    }

    /// Sparse reduce matches generic path.
    #[test]
    fn sparse_matches_generic() {
        let cases = [
            (U256::from_be_limbs([0, 0, 0, 1]), U256::from_be_limbs([0, 0, 0, 1])),
            (
                U256::from_be_limbs([
                    0x123456789ABCDEF0, 0xFEDCBA9876543210,
                    0x1111222233334444, 0x5555666677778888,
                ]),
                U256::from_be_limbs([
                    0xAAAABBBBCCCCDDDD, 0xEEEEFFFF00001111,
                    0x2222333344445555, 0x6666777788889999,
                ]),
            ),
            (
                U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, 0xFFFFFFFEFFFFFC2E]),
                U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, 0xFFFFFFFEFFFFFC2E]),
            ),
        ];
        for (a, b) in &cases {
            let product = *a * *b;
            let generic = product.div_u256(&P);
            let sparse = product.sparse_reduce(&P, 0x1000003D1);
            assert_eq!(sparse, generic, "mismatch for {a:?} * {b:?}");
        }
    }

    /// Sparse reduce handles zero product correctly.
    #[test]
    fn sparse_reduce_zero() {
        let product = crate::u512::U512::from_be_limbs([0u64; 8]);
        assert_eq!(product.sparse_reduce(&P, 0x1000003D1), U256::ZERO);
    }

    /// Sparse reduce handles max product.
    #[test]
    fn sparse_reduce_max_product() {
        let product = crate::u512::U512::from_be_limbs([u64::MAX; 8]);
        let result = product.sparse_reduce(&P, 0x1000003D1);
        let generic = product.div_u256(&P);
        assert_eq!(result, generic);
    }
}
