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
93
94
95
96
97
//! 256-bit subtraction with underflow detection.
use super::U256;
impl U256 {
/// Computes `self - other` by packing limb pairs into `u128` for
/// native `sub` + `sbb` borrow chaining, returning the 256-bit
/// result and a boolean indicating whether the subtraction
/// underflowed (i.e., `self < other`).
///
/// Using `u128` lets LLVM emit a single `sbb` for the intra-pair
/// borrow instead of two `overflowing_sub` calls with a bool
/// intermediate, reducing the operation count from 7 subs + 7 setc
/// + 3 or to 3 subs + 3 sbb + 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, 3]);
/// let (result, underflow) = a.overflowing_sub(&b);
/// assert_eq!(result, U256::from_be_limbs([0, 0, 0, 7]));
/// assert!(!underflow);
/// ```
#[inline]
pub const fn overflowing_sub(&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 (diff_lo, borrow) = a_lo.overflowing_sub(b_lo);
let (diff_hi, u1) = a_hi.overflowing_sub(b_hi);
let (diff_hi, u2) = diff_hi.overflowing_sub(borrow as u128);
(
U256([
diff_lo as u64,
(diff_lo >> 64) as u64,
diff_hi as u64,
(diff_hi >> 64) as u64,
]),
u1 | u2,
)
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
/// Subtracting a smaller value produces no underflow.
#[test]
fn small_no_underflow() {
let a = U256::from_be_limbs([0, 0, 0, 10]);
let b = U256::from_be_limbs([0, 0, 0, 3]);
let (result, underflow) = a.overflowing_sub(&b);
assert_eq!(result, U256::from_be_limbs([0, 0, 0, 7]));
assert!(!underflow);
}
/// Subtracting a larger value underflows and wraps.
#[test]
fn underflow_wraps() {
let a = U256::from_be_limbs([0, 0, 0, 0]);
let b = U256::from_be_limbs([0, 0, 0, 1]);
let (result, underflow) = a.overflowing_sub(&b);
assert_eq!(
result,
U256::from_be_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]),
);
assert!(underflow);
}
/// Borrow propagates across all four limbs.
#[test]
fn borrow_propagation() {
let a = U256::from_be_limbs([1, 0, 0, 0]);
let b = U256::from_be_limbs([0, 0, 0, 1]);
let (result, underflow) = a.overflowing_sub(&b);
assert_eq!(
result,
U256::from_be_limbs([0, u64::MAX, u64::MAX, u64::MAX]),
);
assert!(!underflow);
}
/// Subtracting self yields zero with no underflow.
#[test]
fn self_cancellation() {
let a = U256::from_be_limbs([0x1234, 0x5678, 0x9ABC, 0xDEF0]);
let (result, underflow) = a.overflowing_sub(&a);
assert_eq!(result, U256::from_be_limbs([0, 0, 0, 0]));
assert!(!underflow);
}
}