clock_bigint/

add.rs

//! Addition operations for BigInt.
//!
//! Implements constant-time addition using the `adc` (add with carry) algorithm
//! as specified in the Arithmetic Algorithm Specification.
//!
//! ## Constant-Time Behavior
//!
//! All addition operations execute in constant time regardless of input values,
//! making them suitable for cryptographic applications where timing attacks
//! must be prevented.
//!
//! ## Error Handling
//!
//! Operations may return `BigIntError::Overflow` if the result would exceed
//! the configured maximum limb capacity of the BigInt.

use crate::error::Result;
use crate::limbs::limb_add_carry;
use crate::sub;
use crate::types::BigIntCore;

#[cfg(feature = "alloc")]
use crate::types::BigInt;

/// Add two BigInt magnitudes (unsigned addition).
///
/// This function performs addition of the absolute values of two BigInts,
/// ignoring their signs. The result is stored in the provided mutable BigInt.
/// Both inputs must have their magnitudes added together.
///
/// # Arguments
///
/// * `a` - First BigInt operand
/// * `b` - Second BigInt operand
/// * `result` - Mutable BigInt to store the result (must have sufficient capacity)
///
/// # Returns
///
/// Returns `Ok(())` on success, or `BigIntError::Overflow` if the result
/// would exceed the maximum limb capacity.
///
/// # Examples
///
/// ```rust
/// use clock_bigint::{BigInt, BigIntCore, add_magnitude};
///
/// let a = BigInt::from_u64(10, 10);
/// let b = BigInt::from_u64(5, 10);
/// let mut result = BigInt::new(10);
///
/// add_magnitude(&a, &b, &mut result).unwrap();
/// assert_eq!(result.limbs()[0], 15);
/// ```
///
/// # Performance
///
/// Executes in O(n) time where n is the maximum limb count of the inputs.
/// The algorithm processes limbs from least significant to most significant
/// using constant-time carry propagation.
#[cfg(feature = "alloc")]
pub fn add_magnitude(a: &BigInt, b: &BigInt, result: &mut BigInt) -> Result<()> {
    let n = a.limb_count().max(b.limb_count());

    // Ensure result has sufficient capacity
    result.ensure_capacity(n + 1)?; // +1 for potential carry

    let a_limbs = a.limbs();
    let b_limbs = b.limbs();
    let result_limbs = result.limbs_mut();

    let mut carry = 0u64;

    // Add limbs from least significant to most significant
    // Execute full loop for constant-time behavior
    for i in 0..n {
        let a_val = if i < a_limbs.len() { a_limbs[i] } else { 0 };
        let b_val = if i < b_limbs.len() { b_limbs[i] } else { 0 };

        let (sum, carry_out) = limb_add_carry(a_val, b_val, carry);
        if i < result_limbs.len() {
            result_limbs[i] = sum;
        }
        carry = carry_out;
    }

    // Handle final carry
    if carry != 0 {
        if n < result_limbs.len() {
            result_limbs[n] = carry;
        } else {
            // Need to ensure capacity for the additional limb
            result.ensure_capacity(n + 1)?;
            result.limbs_mut()[n] = carry;
        }
    }

    result.canonicalize()?;
    Ok(())
}

/// Add two BigInt values with proper sign handling.
///
/// Performs algebraic addition of two BigInts, correctly handling all sign combinations:
///
/// - **Same sign**: Adds the magnitudes and keeps the common sign
/// - **Opposite signs**: Performs subtraction of the smaller magnitude from the larger,
///   with the result taking the sign of the larger operand
/// - **Zero handling**: Returns the non-zero operand when one input is zero
///
/// # Arguments
///
/// * `a` - First BigInt operand
/// * `b` - Second BigInt operand
///
/// # Returns
///
/// Returns `Ok(result)` containing the sum, or `BigIntError::Overflow` if the
/// result would exceed the maximum limb capacity of either input.
///
/// # Examples
///
/// ```rust
/// use clock_bigint::{BigInt, BigIntCore};
///
/// // Positive + positive
/// let a = BigInt::from_u64(10, 10);
/// let b = BigInt::from_u64(5, 10);
/// let sum = clock_bigint::add(&a, &b).unwrap();
/// assert_eq!(sum.limbs()[0], 15);
/// assert!(!sum.sign());
///
/// // Positive + negative (becomes subtraction)
/// let mut neg_b = BigInt::from_u64(3, 10);
/// neg_b.set_sign(true);
/// let diff = clock_bigint::add(&a, &neg_b).unwrap();
/// assert_eq!(diff.limbs()[0], 7);
/// assert!(!diff.sign());
///
/// // Zero handling
/// let zero = BigInt::from_u64(0, 10);
/// let same = clock_bigint::add(&a, &zero).unwrap();
/// assert_eq!(same.limbs()[0], 10);
/// ```
///
/// # Algorithm
///
/// For same-sign operands, delegates to `add_magnitude` for efficient limb-by-limb
/// addition with carry propagation.
///
/// For opposite-sign operands, uses subtraction: `a + b = a - (-b)` when signs differ,
/// optimized to avoid temporary allocations.
///
/// # Performance
///
/// Same-sign addition: O(n) where n is the maximum limb count
/// Opposite-sign addition: O(n) via subtraction algorithm
/// Zero handling: O(1)
#[cfg(feature = "alloc")]
pub fn add(a: &BigInt, b: &BigInt) -> Result<BigInt> {
    // Handle zero cases
    if a.is_zero() {
        return Ok(b.clone());
    }
    if b.is_zero() {
        return Ok(a.clone());
    }

    // Same sign: add magnitudes
    if a.sign() == b.sign() {
        let max_limbs = a.max_limbs().max(b.max_limbs());
        let mut result = BigInt::new(max_limbs + 1); // +1 for potential carry
        add_magnitude(a, b, &mut result)?;
        result.set_sign(a.sign());
        return Ok(result);
    }

    // Opposite sign: delegate to subtraction
    // If signs differ: a + b = a - (-b)
    // But we can optimize: if a >= 0 and b < 0, then a + b = a - |b|
    // If a < 0 and b >= 0, then a + b = b - |a|
    if a.sign() == false && b.sign() == true {
        // a >= 0, b < 0: a + b = a - |b|
        sub::sub(a, b)
    } else {
        // a < 0, b >= 0: a + b = b - |a|
        sub::sub(b, a)
    }
}

/// In-place addition for BigInt.
///
/// Adds the second operand to the first operand in-place, modifying the first operand.
/// This is more efficient than `add` when you don't need to preserve the original value.
///
/// # Arguments
///
/// * `a` - Mutable BigInt to be modified (left-hand side)
/// * `b` - BigInt to add (right-hand side)
///
/// # Returns
///
/// Returns `Ok(())` on success, or `BigIntError::Overflow` if the result would
/// exceed the maximum limb capacity.
///
/// # Examples
///
/// ```rust
/// use clock_bigint::{BigInt, BigIntCore, add_assign};
///
/// let mut a = BigInt::from_u64(10, 10);
/// let b = BigInt::from_u64(5, 10);
///
/// add_assign(&mut a, &b).unwrap();
/// assert_eq!(a.limbs()[0], 15);
/// ```
///
/// # Performance
///
/// Same performance characteristics as `add`, but avoids allocating a new BigInt
/// for the result.
#[cfg(feature = "alloc")]
pub fn add_assign(a: &mut BigInt, b: &BigInt) -> Result<()> {
    let result = add(a, b)?;
    *a = result;
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::types::BigInt;

    #[test]
    fn test_add_same_sign() {
        let a = BigInt::from_u64(10, 10);
        let b = BigInt::from_u64(20, 10);
        let result = add(&a, &b).unwrap();
        assert_eq!(result.limbs()[0], 30);
        assert!(!result.sign());
    }

    #[test]
    fn test_add_positive_negative() {
        // 10 + (-5) = 5
        let a = BigInt::from_u64(10, 10);
        let mut neg_b = BigInt::from_u64(5, 10);
        neg_b.set_sign(true);
        let result = add(&a, &neg_b).unwrap();
        assert_eq!(result.limbs()[0], 5);
        assert!(!result.sign());
    }

    #[test]
    fn test_add_negative_positive() {
        // -10 + 5 = -5
        let mut neg_a = BigInt::from_u64(10, 10);
        neg_a.set_sign(true);
        let b = BigInt::from_u64(5, 10);
        let result = add(&neg_a, &b).unwrap();
        assert_eq!(result.limbs()[0], 5);
        assert!(result.sign());
    }

    #[test]
    fn test_add_negative_negative() {
        // -10 + (-5) = -15
        let mut neg_a = BigInt::from_u64(10, 10);
        neg_a.set_sign(true);
        let mut neg_b = BigInt::from_u64(5, 10);
        neg_b.set_sign(true);
        let result = add(&neg_a, &neg_b).unwrap();
        assert_eq!(result.limbs()[0], 15);
        assert!(result.sign());
    }

    #[test]
    fn test_add_opposite_signs_result_zero() {
        // 10 + (-10) = 0
        let a = BigInt::from_u64(10, 10);
        let mut neg_b = BigInt::from_u64(10, 10);
        neg_b.set_sign(true);
        let result = add(&a, &neg_b).unwrap();
        assert!(result.is_zero());
    }

    #[test]
    fn test_add_opposite_signs_result_negative() {
        // 5 + (-10) = -5
        let a = BigInt::from_u64(5, 10);
        let mut neg_b = BigInt::from_u64(10, 10);
        neg_b.set_sign(true);
        let result = add(&a, &neg_b).unwrap();
        assert_eq!(result.limbs()[0], 5);
        assert!(result.sign());
    }

    #[test]
    fn test_add_with_carry() {
        let a = BigInt::from_u64(u64::MAX, 10);
        let b = BigInt::from_u64(1, 10);
        let result = add(&a, &b).unwrap();
        assert_eq!(result.limbs()[0], 0);
        assert_eq!(result.limbs()[1], 1);
        assert!(!result.sign());
    }

    #[test]
    fn test_add_zero() {
        let a = BigInt::from_u64(42, 10);
        let b = BigInt::from_u64(0, 10);
        let result = add(&a, &b).unwrap();
        assert_eq!(result.limbs()[0], 42);
    }

    #[test]
    fn test_add_both_zero() {
        let a = BigInt::from_u64(0, 10);
        let b = BigInt::from_u64(0, 10);
        let result = add(&a, &b).unwrap();
        assert!(result.is_zero());
    }

    #[test]
    fn test_add_large_numbers() {
        // Test with multi-limb numbers: (2^128 - 1) + 1 = 2^128
        let a = BigInt::from_limbs(&[u64::MAX, u64::MAX], 10).unwrap();
        let b = BigInt::from_limbs(&[1, 0], 10).unwrap();
        let result = add(&a, &b).unwrap();

        // Result should be [0, 0, 1] representing 2^128
        assert_eq!(result.limb_count(), 3);
        assert_eq!(result.limbs()[0], 0);
        assert_eq!(result.limbs()[1], 0);
        assert_eq!(result.limbs()[2], 1);
        assert!(!result.sign());
    }

    #[test]
    fn test_add_assign() {
        let mut a = BigInt::from_u64(10, 10);
        let b = BigInt::from_u64(5, 10);
        add_assign(&mut a, &b).unwrap();
        assert_eq!(a.limbs()[0], 15);
        assert!(!a.sign());
    }

    #[test]
    fn test_add_assign_opposite_signs() {
        let mut a = BigInt::from_u64(10, 10);
        let mut neg_b = BigInt::from_u64(15, 10);
        neg_b.set_sign(true);
        add_assign(&mut a, &neg_b).unwrap();
        assert_eq!(a.limbs()[0], 5);
        assert!(a.sign());
    }

    #[test]
    fn test_add_magnitude_basic() {
        let a = BigInt::from_u64(10, 10);
        let b = BigInt::from_u64(5, 10);
        let mut result = BigInt::new(10);
        add_magnitude(&a, &b, &mut result).unwrap();
        assert_eq!(result.limbs()[0], 15);
        assert!(!result.sign());
    }

    #[test]
    fn test_add_magnitude_with_carry() {
        let a = BigInt::from_u64(u64::MAX, 10);
        let b = BigInt::from_u64(1, 10);
        let mut result = BigInt::new(10);
        add_magnitude(&a, &b, &mut result).unwrap();
        assert_eq!(result.limbs()[0], 0);
        assert_eq!(result.limbs()[1], 1);
        assert!(!result.sign());
    }

    #[test]
    fn test_add_magnitude_different_sizes() {
        let a = BigInt::from_limbs(&[1, 2, 3], 10).unwrap();
        let b = BigInt::from_limbs(&[4], 10).unwrap();
        let mut result = BigInt::new(10);
        add_magnitude(&a, &b, &mut result).unwrap();
        assert_eq!(result.limbs()[0], 5);
        assert_eq!(result.limbs()[1], 2);
        assert_eq!(result.limbs()[2], 3);
        assert!(!result.sign());
    }
}