crypto_bigint/uint/boxed/
sub.rs

1//! [`BoxedUint`] subtraction operations.
2
3use crate::{BoxedUint, CheckedSub, Limb, Uint, Wrapping, WrappingSub, Zero, U128, U64};
4use core::ops::{Sub, SubAssign};
5use subtle::{Choice, ConditionallySelectable, CtOption};
6
7impl BoxedUint {
8    /// Computes `a - (b + borrow)`, returning the result along with the new borrow.
9    #[inline(always)]
10    pub fn sbb(&self, rhs: &Self, borrow: Limb) -> (Self, Limb) {
11        Self::fold_limbs(self, rhs, borrow, |a, b, c| a.sbb(b, c))
12    }
13
14    /// Computes `a - (b + borrow)` in-place, returning the new borrow.
15    ///
16    /// Panics if `rhs` has a larger precision than `self`.
17    #[inline(always)]
18    pub fn sbb_assign(&mut self, rhs: impl AsRef<[Limb]>, mut borrow: Limb) -> Limb {
19        debug_assert!(self.bits_precision() <= (rhs.as_ref().len() as u32 * Limb::BITS));
20
21        for i in 0..self.nlimbs() {
22            let (limb, b) = self.limbs[i].sbb(*rhs.as_ref().get(i).unwrap_or(&Limb::ZERO), borrow);
23            self.limbs[i] = limb;
24            borrow = b;
25        }
26
27        borrow
28    }
29
30    /// Perform wrapping subtraction, discarding overflow.
31    pub fn wrapping_sub(&self, rhs: &Self) -> Self {
32        self.sbb(rhs, Limb::ZERO).0
33    }
34
35    /// Perform in-place wrapping subtraction, returning the truthy value as the second element of
36    /// the tuple if an underflow has occurred.
37    pub(crate) fn conditional_sbb_assign(&mut self, rhs: &Self, choice: Choice) -> Choice {
38        debug_assert!(self.bits_precision() <= rhs.bits_precision());
39        let mask = Limb::conditional_select(&Limb::ZERO, &Limb::MAX, choice);
40        let mut borrow = Limb::ZERO;
41
42        for i in 0..self.nlimbs() {
43            let masked_rhs = *rhs.limbs.get(i).unwrap_or(&Limb::ZERO) & mask;
44            let (limb, b) = self.limbs[i].sbb(masked_rhs, borrow);
45            self.limbs[i] = limb;
46            borrow = b;
47        }
48
49        Choice::from((borrow.0 & 1) as u8)
50    }
51}
52
53impl CheckedSub for BoxedUint {
54    fn checked_sub(&self, rhs: &Self) -> CtOption<Self> {
55        let (result, carry) = self.sbb(rhs, Limb::ZERO);
56        CtOption::new(result, carry.is_zero())
57    }
58}
59
60impl Sub for BoxedUint {
61    type Output = Self;
62
63    fn sub(self, rhs: Self) -> Self {
64        self.sub(&rhs)
65    }
66}
67
68impl Sub<&BoxedUint> for BoxedUint {
69    type Output = Self;
70
71    fn sub(self, rhs: &Self) -> Self {
72        Sub::sub(&self, rhs)
73    }
74}
75
76impl Sub<BoxedUint> for &BoxedUint {
77    type Output = BoxedUint;
78
79    fn sub(self, rhs: BoxedUint) -> BoxedUint {
80        Sub::sub(self, &rhs)
81    }
82}
83
84impl Sub<&BoxedUint> for &BoxedUint {
85    type Output = BoxedUint;
86
87    fn sub(self, rhs: &BoxedUint) -> BoxedUint {
88        self.checked_sub(rhs)
89            .expect("attempted to subtract with underflow")
90    }
91}
92
93impl SubAssign<BoxedUint> for BoxedUint {
94    fn sub_assign(&mut self, rhs: BoxedUint) {
95        self.sub_assign(&rhs)
96    }
97}
98
99impl SubAssign<&BoxedUint> for BoxedUint {
100    fn sub_assign(&mut self, rhs: &BoxedUint) {
101        let carry = self.sbb_assign(rhs, Limb::ZERO);
102        assert_eq!(
103            carry.is_zero().unwrap_u8(),
104            1,
105            "attempted to subtract with underflow"
106        );
107    }
108}
109
110impl<const LIMBS: usize> Sub<Uint<LIMBS>> for BoxedUint {
111    type Output = BoxedUint;
112
113    fn sub(self, rhs: Uint<LIMBS>) -> BoxedUint {
114        self.sub(&rhs)
115    }
116}
117
118impl<const LIMBS: usize> Sub<&Uint<LIMBS>> for BoxedUint {
119    type Output = BoxedUint;
120
121    fn sub(mut self, rhs: &Uint<LIMBS>) -> BoxedUint {
122        self -= rhs;
123        self
124    }
125}
126
127impl<const LIMBS: usize> Sub<Uint<LIMBS>> for &BoxedUint {
128    type Output = BoxedUint;
129
130    fn sub(self, rhs: Uint<LIMBS>) -> BoxedUint {
131        self.clone().sub(rhs)
132    }
133}
134
135impl<const LIMBS: usize> Sub<&Uint<LIMBS>> for &BoxedUint {
136    type Output = BoxedUint;
137
138    fn sub(self, rhs: &Uint<LIMBS>) -> BoxedUint {
139        self.clone().sub(rhs)
140    }
141}
142
143impl<const LIMBS: usize> SubAssign<Uint<LIMBS>> for BoxedUint {
144    fn sub_assign(&mut self, rhs: Uint<LIMBS>) {
145        *self -= &rhs;
146    }
147}
148
149impl<const LIMBS: usize> SubAssign<&Uint<LIMBS>> for BoxedUint {
150    fn sub_assign(&mut self, rhs: &Uint<LIMBS>) {
151        let carry = self.sbb_assign(rhs.as_limbs(), Limb::ZERO);
152        assert_eq!(carry.0, 0, "attempted to sub with overflow");
153    }
154}
155
156impl SubAssign<Wrapping<BoxedUint>> for Wrapping<BoxedUint> {
157    fn sub_assign(&mut self, other: Wrapping<BoxedUint>) {
158        self.0.sbb_assign(&other.0, Limb::ZERO);
159    }
160}
161
162impl SubAssign<&Wrapping<BoxedUint>> for Wrapping<BoxedUint> {
163    fn sub_assign(&mut self, other: &Wrapping<BoxedUint>) {
164        self.0.sbb_assign(&other.0, Limb::ZERO);
165    }
166}
167
168impl WrappingSub for BoxedUint {
169    fn wrapping_sub(&self, v: &Self) -> Self {
170        self.wrapping_sub(v)
171    }
172}
173
174macro_rules! impl_sub_primitive {
175    ($($primitive:ty),+) => {
176        $(
177            impl Sub<$primitive> for BoxedUint {
178                type Output = BoxedUint;
179
180                #[inline]
181                fn sub(self, rhs: $primitive) -> BoxedUint {
182                     self - U64::from(rhs)
183                }
184            }
185
186            impl Sub<$primitive> for &BoxedUint {
187                type Output = BoxedUint;
188
189                #[inline]
190                fn sub(self, rhs: $primitive) -> BoxedUint {
191                     self - U64::from(rhs)
192                }
193            }
194
195            impl SubAssign<$primitive> for BoxedUint {
196                fn sub_assign(&mut self, rhs: $primitive) {
197                    *self -= U64::from(rhs);
198                }
199            }
200        )+
201    };
202}
203
204impl_sub_primitive!(u8, u16, u32, u64);
205
206impl Sub<u128> for BoxedUint {
207    type Output = BoxedUint;
208
209    #[inline]
210    fn sub(self, rhs: u128) -> BoxedUint {
211        self - U128::from(rhs)
212    }
213}
214
215impl Sub<u128> for &BoxedUint {
216    type Output = BoxedUint;
217
218    #[inline]
219    fn sub(self, rhs: u128) -> BoxedUint {
220        self - U128::from(rhs)
221    }
222}
223
224impl SubAssign<u128> for BoxedUint {
225    fn sub_assign(&mut self, rhs: u128) {
226        *self -= U128::from(rhs);
227    }
228}
229
230#[cfg(test)]
231#[allow(clippy::unwrap_used)]
232mod tests {
233    use super::{BoxedUint, CheckedSub, Limb};
234
235    #[test]
236    fn sbb_no_borrow() {
237        let (res, carry) = BoxedUint::one().sbb(&BoxedUint::one(), Limb::ZERO);
238        assert_eq!(res, BoxedUint::zero());
239        assert_eq!(carry, Limb::ZERO);
240
241        let (res, carry) = BoxedUint::one().sbb(&BoxedUint::zero(), Limb::ZERO);
242        assert_eq!(res, BoxedUint::one());
243        assert_eq!(carry, Limb::ZERO);
244    }
245
246    #[test]
247    fn sbb_with_borrow() {
248        let (res, borrow) = BoxedUint::zero().sbb(&BoxedUint::one(), Limb::ZERO);
249        assert_eq!(res, BoxedUint::max(Limb::BITS));
250        assert_eq!(borrow, Limb::MAX);
251    }
252
253    #[test]
254    fn sub_with_u32_rhs() {
255        let a = BoxedUint::from(0x100000000u64);
256        let b = a - u32::MAX;
257        assert_eq!(b, BoxedUint::one());
258    }
259
260    #[test]
261    fn checked_sub_ok() {
262        let result = BoxedUint::one().checked_sub(&BoxedUint::one());
263        assert_eq!(result.unwrap(), BoxedUint::zero());
264    }
265
266    #[test]
267    fn checked_sub_overflow() {
268        let result = BoxedUint::zero().checked_sub(&BoxedUint::one());
269        assert!(!bool::from(result.is_some()));
270    }
271}
crypto_bigint/uint/boxed/sub.rs

crypto_bigint/uint/boxed/
sub.rs
