//! Variable-time modular addition of two [`U256`] values.
use super::U256;

impl U256 {
    /// Computes `(self + other) mod modulus` using branching reduction.
    ///
    /// Handles both reduced and unreduced inputs. Without overflow
    /// (`sum < 2^256`), at most one subtraction is needed since
    /// `sum < 2^256 < 2·modulus` for any modulus > 2^255. With
    /// overflow, the wrapping subtraction consumes the 257th bit;
    /// if the subtraction didn't underflow (sum was large enough),
    /// one more subtraction finishes the reduction.
    ///
    /// This is the fastest path but execution time depends on operand values.
    /// Use `add_mod_ct` when constant-time behavior is required.
    ///
    /// # 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, 10]);
    /// let b = U256::from_be_limbs([0, 0, 0, 20]);
    /// assert_eq!(a.add_mod_vt(&b, &P), U256::from_be_limbs([0, 0, 0, 30]));
    /// ```
    #[inline]
    pub fn add_mod_vt(&self, other: &U256, modulus: &U256) -> U256 {
        let (sum, overflow) = self.overflowing_add(other);
        if overflow {
            let (r, underflow) = sum.overflowing_sub(modulus);
            if underflow {
                r
            } else {
                r.overflowing_sub(modulus).0
            }
        } else if sum >= *modulus {
            sum.overflowing_sub(modulus).0
        } else {
            sum
        }
    }
}

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

    /// Adding zero to zero yields zero.
    #[test]
    fn zero_plus_zero() {
        assert_eq!(U256::ZERO.add_mod_vt(&U256::ZERO, &P), U256::ZERO);
    }

    /// Adding zero is the identity operation.
    #[test]
    fn additive_identity() {
        let a = U256::from_be_limbs([0, 0, 0, 42]);
        assert_eq!(a.add_mod_vt(&U256::ZERO, &P), a);
        assert_eq!(U256::ZERO.add_mod_vt(&a, &P), a);
    }

    /// Small values that don't require reduction.
    #[test]
    fn small_no_reduction() {
        let a = U256::from_be_limbs([
            0x0202020202020202,
            0x0202020202020202,
            0x0202020202020202,
            0x0202020202020202,
        ]);
        let expected = U256::from_be_limbs([
            0x0404040404040404,
            0x0404040404040404,
            0x0404040404040404,
            0x0404040404040404,
        ]);
        assert_eq!(a.add_mod_vt(&a, &P), expected);
    }

    /// Adding one to P-1 wraps to zero (exact modulus hit).
    #[test]
    fn p_minus_one_plus_one() {
        let p_minus_1 = U256::from_be_limbs([
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFEFFFFFC2E,
        ]);
        assert_eq!(p_minus_1.add_mod_vt(&U256::ONE, &P), U256::ZERO);
    }

    /// Adding two to P-1 wraps to one.
    #[test]
    fn p_minus_one_plus_two() {
        let p_minus_1 = U256::from_be_limbs([
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFEFFFFFC2E,
        ]);
        let two = U256::from_be_limbs([0, 0, 0, 2]);
        assert_eq!(p_minus_1.add_mod_vt(&two, &P), U256::ONE);
    }

    /// (P-1) + (P-1) mod P = P-2. Exercises 257-bit overflow path.
    #[test]
    fn p_minus_one_doubled() {
        let p_minus_1 = U256::from_be_limbs([
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFEFFFFFC2E,
        ]);
        let p_minus_2 = U256::from_be_limbs([
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFFFFFFFFFF,
            0xFFFFFFFEFFFFFC2D,
        ]);
        assert_eq!(p_minus_1.add_mod_vt(&p_minus_1, &P), p_minus_2);
    }

    /// Commutativity: a + b = b + a.
    #[test]
    fn commutative() {
        let a = U256::from_be_limbs([0, 0x1234, 0, 0x5678]);
        let b = U256::from_be_limbs([0, 0xABCD, 0, 0xEF01]);
        assert_eq!(a.add_mod_vt(&b, &P), b.add_mod_vt(&a, &P));
    }

    /// Inputs larger than modulus are reduced correctly.
    #[test]
    fn inputs_exceed_modulus() {
        let max = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
        assert_eq!(
            max.add_mod_vt(&max, &P),
            U256::from_be_limbs([0, 0, 0, 0x2000007A0]),
        );
    }
}

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

    /// (2^256 - 1) + (2^256 - 1) mod P exercises double-overflow reduction.
    #[test]
    fn all_ff_doubled() {
        let a = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
        let b = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);

        assert_eq!(
            a.add_mod_vt(&b, &P),
            U256::from_be_bytes([
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2,
                0, 0, 7, 160,
            ])
        );
    }

    /// All 0xFF + all 0xAA overflows and reduces mod P.
    #[test]
    fn all_ff_plus_all_aa() {
        let a = U256::from_be_bytes([0xFF; 32]);
        let b = U256::from_be_bytes([0xAA; 32]);

        assert_eq!(
            a.add_mod_vt(&b, &P),
            U256::from_be_bytes([
                170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170,
                170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 171, 170, 170, 174, 122
            ])
        );
    }
}
