//! Variable-time modular reduction via repeated subtraction.
use super::U256;

impl U256 {
    /// Reduces `self` modulo `modulus` in variable time by repeated subtraction.
    ///
    /// The loop count depends on how many times `modulus` fits into `self`,
    /// leaking the quotient through timing. For cryptographic contexts where
    /// this matters, use `modulo_ct` (enabled via the `ct` feature flag).
    ///
    /// # Panics
    ///
    /// Loops indefinitely if `modulus` is zero.
    #[inline]
    pub fn modulo_vt(&self, modulus: &U256) -> U256 {
        let mut r = *self;
        while r >= *modulus {
            let (reduced, _) = r.overflowing_sub(modulus);
            r = reduced;
        }
        r
    }
}

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

    /// Zero mod P is zero.
    #[test]
    fn zero_mod_p() {
        assert_eq!(U256::ZERO.modulo_vt(&P), U256::ZERO);
    }

    /// Value less than modulus is unchanged.
    #[test]
    fn below_modulus() {
        assert_eq!(U256::ONE.modulo_vt(&P), U256::ONE);
    }

    /// Modulus mod itself is zero.
    #[test]
    fn modulus_mod_self() {
        assert_eq!(P.modulo_vt(&P), U256::ZERO);
    }

    /// (2^256 - 1) mod P = 2^32 + 976.
    #[test]
    fn max_mod_p() {
        let max = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
        assert_eq!(max.modulo_vt(&P), U256::from_be_limbs([0, 0, 0, 0x1000003D0]));
    }
}
