//! Detection of sparse moduli whose `2^256` complement fits in a `u64`.
use super::U256;

impl U256 {
    /// Returns the single-limb complement `2^256 − self` when it fits in a
    /// `u64`, or `None` otherwise.
    ///
    /// The complement fits in a `u64` exactly when the top 192 bits are all
    /// ones (limbs 0, 1, 2 are `u64::MAX`) and the lowest limb is not zero
    /// (so `2^256 − self ≠ 0`). This identifies "sparse" moduli like
    /// secp256k1's P (`2^256 − 2^32 − 977`), enabling fast folding reduction
    /// in [`mul_mod`](U256::mul_mod) and [`square_mod`](U256::square_mod).
    ///
    #[inline]
    pub(crate) const fn has_u64_complement(&self) -> Option<u64> {
        if (self.0[3] & self.0[2] & self.0[1]) == u64::MAX {
            let comp = self.0[0].wrapping_neg();
            if comp != 0 {
                return Some(comp);
            }
        }
        None
    }
}

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

    /// secp256k1 P has complement 0x1000003D1.
    #[test]
    fn secp256k1_p() {
        assert_eq!(P.has_u64_complement(), Some(0x1000003D1));
    }

    /// Small value has no u64 complement.
    #[test]
    fn small_value() {
        assert_eq!(
            U256::from_be_limbs([0, 0, 0, 42]).has_u64_complement(),
            None
        );
    }

    /// All-ones (2^256 - 1) has complement 1.
    #[test]
    fn all_ones() {
        assert_eq!(U256::MAX.has_u64_complement(), Some(1));
    }

    /// Value with only top 2 limbs set returns None.
    #[test]
    fn partial_top_limbs() {
        let v = U256::from_be_limbs([u64::MAX, u64::MAX, 0, 1]);
        assert_eq!(v.has_u64_complement(), None);
    }

    /// Modulus where low limb is zero returns None (complement would be 0).
    #[test]
    fn zero_complement() {
        let v = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, 0]);
        assert_eq!(v.has_u64_complement(), None);
    }

    /// Zero returns None.
    #[test]
    fn zero() {
        assert_eq!(U256::ZERO.has_u64_complement(), None);
    }

    /// Complement of (2^256 - 2) is 2.
    #[test]
    fn complement_of_two() {
        let v = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX - 1]);
        assert_eq!(v.has_u64_complement(), Some(2));
    }
}
