1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//! 256-bit addition with overflow detection.
use super::U256;
impl U256 {
/// Computes `self + other` by packing limb pairs into `u128` for
/// native `add` + `adc` carry chaining, returning the 256-bit result
/// and a boolean indicating whether the addition overflowed (i.e.,
/// the true result exceeds `2^256 - 1`).
///
/// Using `u128` lets LLVM emit a single `adc` for the intra-pair
/// carry instead of two `overflowing_add` calls with a bool
/// intermediate, reducing the operation count from 7 adds + 7 setc
/// + 3 or to 3 adds + 3 adc + 3 setc.
///
/// # Examples
///
/// ```
/// use cnfy_uint::u256::U256;
///
/// let a = U256::from_be_limbs([0, 0, 0, 10]);
/// let b = U256::from_be_limbs([0, 0, 0, 20]);
/// let (result, overflow) = a.overflowing_add(&b);
/// assert_eq!(result, U256::from_be_limbs([0, 0, 0, 30]));
/// assert!(!overflow);
/// ```
#[inline]
pub const fn overflowing_add(&self, other: &U256) -> (U256, bool) {
let a_lo = ((self.0[1] as u128) << 64) | (self.0[0] as u128);
let a_hi = ((self.0[3] as u128) << 64) | (self.0[2] as u128);
let b_lo = ((other.0[1] as u128) << 64) | (other.0[0] as u128);
let b_hi = ((other.0[3] as u128) << 64) | (other.0[2] as u128);
let (sum_lo, carry) = a_lo.overflowing_add(b_lo);
let (sum_hi, c1) = a_hi.overflowing_add(b_hi);
let (sum_hi, c2) = sum_hi.overflowing_add(carry as u128);
(
U256([
sum_lo as u64,
(sum_lo >> 64) as u64,
sum_hi as u64,
(sum_hi >> 64) as u64,
]),
c1 | c2,
)
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
/// Adding two small values produces no overflow.
#[test]
fn small_no_overflow() {
let a = U256::from_be_limbs([0, 0, 0, 100]);
let b = U256::from_be_limbs([0, 0, 0, 200]);
let (result, overflow) = a.overflowing_add(&b);
assert_eq!(result, U256::from_be_limbs([0, 0, 0, 300]));
assert!(!overflow);
}
/// Adding max to one overflows, wrapping to zero.
#[test]
fn max_plus_one_overflows() {
let max = U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
let one = U256::from_be_limbs([0, 0, 0, 1]);
let (result, overflow) = max.overflowing_add(&one);
assert_eq!(result, U256::from_be_limbs([0, 0, 0, 0]));
assert!(overflow);
}
/// Carry propagates across all four limbs.
#[test]
fn carry_propagation() {
let a = U256::from_be_limbs([0, 0, 0, u64::MAX]);
let one = U256::from_be_limbs([0, 0, 0, 1]);
let (result, overflow) = a.overflowing_add(&one);
assert_eq!(result, U256::from_be_limbs([0, 0, 1, 0]));
assert!(!overflow);
}
/// Zero is the additive identity.
#[test]
fn additive_identity() {
let a = U256::from_be_limbs([0x1234, 0x5678, 0x9ABC, 0xDEF0]);
let zero = U256::from_be_limbs([0, 0, 0, 0]);
let (result, overflow) = a.overflowing_add(&zero);
assert_eq!(result, a);
assert!(!overflow);
}
}