clock_bigint/
sub.rs

1//! Subtraction operations for BigInt.
2//!
3//! Implements constant-time subtraction using the `sbb` (subtract with borrow) algorithm
4//! as specified in the Arithmetic Algorithm Specification.
5
6use crate::error::Result;
7use crate::limbs::{ct_compare, limb_sub_borrow};
8use crate::types::BigIntCore;
9
10#[cfg(feature = "alloc")]
11use crate::types::BigInt;
12
13/// Subtract two BigInt magnitudes (a - b).
14///
15/// Returns (result, borrow_out) where borrow_out indicates if result is negative.
16#[cfg(feature = "alloc")]
17pub fn sub_magnitude(a: &BigInt, b: &BigInt, result: &mut BigInt) -> Result<bool> {
18    let n = a.limb_count().max(b.limb_count());
19    result.ensure_capacity(n)?;
20
21    let a_limbs = a.limbs();
22    let b_limbs = b.limbs();
23    let result_limbs = result.limbs_mut();
24
25    let mut borrow = 0u64;
26
27    // Subtract limbs from least significant to most significant
28    // Execute full loop for constant-time behavior
29    for i in 0..n {
30        let a_val = if i < a_limbs.len() { a_limbs[i] } else { 0 };
31        let b_val = if i < b_limbs.len() { b_limbs[i] } else { 0 };
32
33        let (diff, borrow_out) = limb_sub_borrow(a_val, b_val, borrow);
34        if i < result_limbs.len() {
35            result_limbs[i] = diff;
36        }
37        borrow = borrow_out;
38    }
39
40    let is_negative = borrow != 0;
41
42    // If result is negative, compute two's complement
43    if is_negative {
44        // Two's complement: invert all bits and add 1
45        for i in 0..n {
46            if i < result_limbs.len() {
47                result_limbs[i] = !result_limbs[i];
48            }
49        }
50
51        // Add 1 to complete two's complement
52        let mut carry = 1u64;
53        for i in 0..n {
54            if i < result_limbs.len() {
55                let (sum, carry_out) = crate::limbs::limb_add_carry(result_limbs[i], 0, carry);
56                result_limbs[i] = sum;
57                carry = carry_out;
58            }
59        }
60    }
61
62    result.canonicalize()?;
63    Ok(is_negative)
64}
65
66/// Subtract two BigInt values (a - b).
67#[cfg(feature = "alloc")]
68pub fn sub(a: &BigInt, b: &BigInt) -> Result<BigInt> {
69    // Handle zero cases
70    if b.is_zero() {
71        return Ok(a.clone());
72    }
73    if a.is_zero() {
74        let mut result = b.clone();
75        result.set_sign(!b.sign()); // Negate b
76        return Ok(result);
77    }
78
79    // Compare magnitudes to determine result sign
80    let cmp = ct_compare(a.limbs(), b.limbs());
81    let a_gt_b = (cmp & 1) != 0;
82    let a_eq_b = cmp == 0;
83
84    if a_eq_b {
85        // Equal magnitudes: result is zero
86        let max_limbs = a.max_limbs().max(b.max_limbs());
87        return Ok(BigInt::new(max_limbs));
88    }
89
90    let max_limbs = a.max_limbs().max(b.max_limbs());
91    let mut result = BigInt::new(max_limbs);
92
93    let is_negative = if a_gt_b {
94        // a > b: compute a - b
95        sub_magnitude(a, b, &mut result)?
96    } else {
97        // a < b: compute b - a, result will be negative
98        sub_magnitude(b, a, &mut result)?
99    };
100
101    // Determine final sign
102    let final_sign = if a.sign() == b.sign() {
103        // Same sign: if a > b, keep sign; if a < b, flip sign
104        if a_gt_b { a.sign() } else { !a.sign() }
105    } else {
106        // Opposite signs: if a is positive and a > b, result positive
107        // if a is negative and a > b, result negative
108        if a_gt_b { a.sign() } else { b.sign() }
109    };
110
111    result.set_sign(final_sign ^ is_negative);
112    Ok(result)
113}
114
115/// In-place subtraction for dynamic BigInt.
116#[cfg(feature = "alloc")]
117pub fn sub_assign(a: &mut BigInt, b: &BigInt) -> Result<()> {
118    let result = sub(a, b)?;
119    *a = result;
120    Ok(())
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126
127    #[test]
128    fn test_sub_simple() {
129        let a = BigInt::from_u64(20, 10);
130        let b = BigInt::from_u64(10, 10);
131        let result = sub(&a, &b).unwrap();
132        assert_eq!(result.limbs()[0], 10);
133        assert!(!result.sign());
134    }
135
136    #[test]
137    fn test_sub_with_borrow() {
138        let a = BigInt::from_u64(10, 10);
139        let b = BigInt::from_u64(20, 10);
140        let result = sub(&a, &b).unwrap();
141        // Result should be negative
142        assert!(result.sign() || result.is_zero());
143    }
144}
clock_bigint/sub.rs

clock_bigint/
sub.rs
