crypto_bigint/uint/boxed/
sub.rs

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

crypto_bigint/uint/boxed/
sub.rs
