cnfy-uint 0.2.3

//! 512-bit addition with overflow detection.
use super::U512;

impl U512 {
    /// Computes `self + other` by packing limb pairs into `u128` for
    /// native `add` + `adc` carry chaining, returning the 512-bit result
    /// and a boolean indicating whether the addition overflowed (i.e.,
    /// the true result exceeds `2^512 - 1`).
    ///
    /// Packs the eight limbs as four `u128` pairs: `[0]+[1]`, `[2]+[3]`,
    /// `[4]+[5]`, `[6]+[7]`, then chains carries from LSB to MSB.
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u512::U512;
    ///
    /// let a = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 10]);
    /// let b = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 20]);
    /// let (result, overflow) = a.overflowing_add(&b);
    /// assert_eq!(result, U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 30]));
    /// assert!(!overflow);
    /// ```
    #[inline]
    pub const fn overflowing_add(&self, other: &U512) -> (U512, bool) {
        // Pack as 4 u128 pairs (LE pair ordering: p0=LSB, p3=MSB)
        let a0 = ((self.0[1] as u128) << 64) | (self.0[0] as u128);
        let a1 = ((self.0[3] as u128) << 64) | (self.0[2] as u128);
        let a2 = ((self.0[5] as u128) << 64) | (self.0[4] as u128);
        let a3 = ((self.0[7] as u128) << 64) | (self.0[6] as u128);

        let b0 = ((other.0[1] as u128) << 64) | (other.0[0] as u128);
        let b1 = ((other.0[3] as u128) << 64) | (other.0[2] as u128);
        let b2 = ((other.0[5] as u128) << 64) | (other.0[4] as u128);
        let b3 = ((other.0[7] as u128) << 64) | (other.0[6] as u128);

        let (s0, c0) = a0.overflowing_add(b0);
        let (s1, c1a) = a1.overflowing_add(b1);
        let (s1, c1b) = s1.overflowing_add(c0 as u128);
        let (s2, c2a) = a2.overflowing_add(b2);
        let (s2, c2b) = s2.overflowing_add((c1a | c1b) as u128);
        let (s3, c3a) = a3.overflowing_add(b3);
        let (s3, c3b) = s3.overflowing_add((c2a | c2b) as u128);

        (
            U512([
                s0 as u64,
                (s0 >> 64) as u64,
                s1 as u64,
                (s1 >> 64) as u64,
                s2 as u64,
                (s2 >> 64) as u64,
                s3 as u64,
                (s3 >> 64) as u64,
            ]),
            c3a | c3b,
        )
    }
}

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

    /// Adding two small values produces no overflow.
    #[test]
    fn small_no_overflow() {
        let a = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 100]);
        let b = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 200]);
        let (result, overflow) = a.overflowing_add(&b);
        assert_eq!(result, U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, 300]));
        assert!(!overflow);
    }

    /// Adding max to one overflows, wrapping to zero.
    #[test]
    fn max_plus_one_overflows() {
        let (result, overflow) = U512::MAX.overflowing_add(&U512::ONE);
        assert_eq!(result, U512::ZERO);
        assert!(overflow);
    }

    /// Carry propagates across all eight limbs.
    #[test]
    fn carry_propagation() {
        let a = U512::from_be_limbs([0, 0, 0, 0, 0, 0, 0, u64::MAX]);
        let one = U512::ONE;
        let (result, overflow) = a.overflowing_add(&one);
        assert_eq!(result, U512::from_be_limbs([0, 0, 0, 0, 0, 0, 1, 0]));
        assert!(!overflow);
    }

    /// Zero is the additive identity.
    #[test]
    fn additive_identity() {
        let a = U512::from_be_limbs([0x1234, 0x5678, 0x9ABC, 0xDEF0, 1, 2, 3, 4]);
        let (result, overflow) = a.overflowing_add(&U512::ZERO);
        assert_eq!(result, a);
        assert!(!overflow);
    }

    /// Carry across all limb-pair boundaries.
    #[test]
    fn full_carry_chain() {
        let a = U512::from_be_limbs([0, u64::MAX, u64::MAX, u64::MAX, u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
        let (result, overflow) = a.overflowing_add(&U512::ONE);
        assert_eq!(result, U512::from_be_limbs([1, 0, 0, 0, 0, 0, 0, 0]));
        assert!(!overflow);
    }

    /// Addition is commutative.
    #[test]
    fn commutative() {
        let a = U512::from_be_limbs([1, 2, 3, 4, 5, 6, 7, 8]);
        let b = U512::from_be_limbs([8, 7, 6, 5, 4, 3, 2, 1]);
        assert_eq!(a.overflowing_add(&b), b.overflowing_add(&a));
    }
}