crypto_bigint/limb/
sub.rs

1//! Limb subtraction
2
3use crate::{
4    Checked, CheckedSub, CtOption, Limb, Sub, SubAssign, SubMod, Wrapping, WrappingSub,
5    primitives::borrowing_sub,
6};
7
8impl Limb {
9    /// Computes `self - (rhs + borrow)`, returning the result along with the new borrow.
10    #[deprecated(since = "0.7.0", note = "please use `borrowing_sub` instead")]
11    #[must_use]
12    pub const fn sbb(self, rhs: Limb, borrow: Limb) -> (Limb, Limb) {
13        self.borrowing_sub(rhs, borrow)
14    }
15
16    /// Computes `self - (rhs + borrow)`, returning the result along with the new borrow.
17    ///
18    /// The incoming borrow is the most significant bit of `borrow`. The outgoing borrow is
19    /// [`Limb::ZERO`] if the subtraction does not underflow, or [`Limb::MAX`] otherwise.
20    #[inline(always)]
21    #[must_use]
22    pub const fn borrowing_sub(self, rhs: Limb, borrow: Limb) -> (Limb, Limb) {
23        let (res, borrow) = borrowing_sub(self.0, rhs.0, borrow.0);
24        (Limb(res), Limb(borrow))
25    }
26
27    /// Perform saturating subtraction.
28    #[inline]
29    #[must_use]
30    pub const fn saturating_sub(&self, rhs: Self) -> Self {
31        Limb(self.0.saturating_sub(rhs.0))
32    }
33
34    /// Perform wrapping subtraction, discarding underflow and wrapping around
35    /// the boundary of the type.
36    #[inline(always)]
37    #[must_use]
38    pub const fn wrapping_sub(&self, rhs: Self) -> Self {
39        Limb(self.0.wrapping_sub(rhs.0))
40    }
41}
42
43impl CheckedSub for Limb {
44    #[inline]
45    fn checked_sub(&self, rhs: &Self) -> CtOption<Self> {
46        let (result, underflow) = self.borrowing_sub(*rhs, Limb::ZERO);
47        CtOption::new(result, underflow.is_zero())
48    }
49}
50
51impl Sub for Limb {
52    type Output = Self;
53
54    #[inline]
55    fn sub(self, rhs: Self) -> Self {
56        self.checked_sub(&rhs)
57            .expect("attempted to subtract with underflow")
58    }
59}
60
61impl Sub<&Self> for Limb {
62    type Output = Self;
63
64    #[inline]
65    fn sub(self, rhs: &Self) -> Self {
66        self - *rhs
67    }
68}
69
70impl SubAssign for Limb {
71    #[inline]
72    fn sub_assign(&mut self, rhs: Self) {
73        *self = *self - rhs;
74    }
75}
76
77impl SubAssign<&Self> for Limb {
78    #[inline]
79    fn sub_assign(&mut self, rhs: &Self) {
80        *self = *self - *rhs;
81    }
82}
83
84impl SubAssign for Wrapping<Limb> {
85    #[inline]
86    fn sub_assign(&mut self, other: Self) {
87        *self = *self - other;
88    }
89}
90
91impl SubAssign<&Wrapping<Limb>> for Wrapping<Limb> {
92    #[inline]
93    fn sub_assign(&mut self, other: &Self) {
94        *self = *self - other;
95    }
96}
97
98impl SubAssign for Checked<Limb> {
99    #[inline]
100    fn sub_assign(&mut self, other: Self) {
101        *self = *self - other;
102    }
103}
104
105impl SubAssign<&Checked<Limb>> for Checked<Limb> {
106    #[inline]
107    fn sub_assign(&mut self, other: &Self) {
108        *self = *self - other;
109    }
110}
111
112impl WrappingSub for Limb {
113    #[inline]
114    fn wrapping_sub(&self, v: &Self) -> Self {
115        self.wrapping_sub(*v)
116    }
117}
118
119impl SubMod for Limb {
120    type Output = Self;
121
122    fn sub_mod(&self, rhs: &Self, p: &crate::NonZero<Self>) -> Self::Output {
123        let (res, borrow) = self.borrowing_sub(*rhs, Limb::ZERO);
124        Self::select(res, res.wrapping_add(p.get()), borrow.is_nonzero())
125    }
126}
127
128#[cfg(test)]
129mod tests {
130    use crate::{CheckedSub, Limb};
131
132    #[test]
133    fn borrowing_sub_boundary_values() {
134        use crate::{Limb, Word};
135
136        let msb = 1 << (Word::BITS - 1);
137        let values = [0, 1, 2, msb - 1, msb, msb + 1, Word::MAX - 1, Word::MAX];
138        let borrows = [0, 1, msb, Word::MAX];
139
140        for lhs in values {
141            for rhs in values {
142                for borrow in borrows {
143                    let (ret, borrow1) = lhs.overflowing_sub(borrow >> (Word::BITS - 1));
144                    let (expected, borrow2) = ret.overflowing_sub(rhs);
145                    let expected_borrow = Word::from(borrow1 | borrow2).wrapping_neg();
146
147                    assert_eq!(
148                        Limb(lhs).borrowing_sub(Limb(rhs), Limb(borrow)),
149                        (Limb(expected), Limb(expected_borrow)),
150                        "lhs={lhs:#x}, rhs={rhs:#x}, borrow={borrow:#x}"
151                    );
152                }
153            }
154        }
155    }
156
157    #[test]
158    fn borrowing_sub_no_borrow() {
159        let (res, borrow) = Limb::ONE.borrowing_sub(Limb::ONE, Limb::ZERO);
160        assert_eq!(res, Limb::ZERO);
161        assert_eq!(borrow, Limb::ZERO);
162    }
163
164    #[test]
165    fn borrowing_sub_with_borrow() {
166        let (res, borrow) = Limb::ZERO.borrowing_sub(Limb::ONE, Limb::ZERO);
167
168        assert_eq!(res, Limb::MAX);
169        assert_eq!(borrow, Limb::MAX);
170    }
171
172    #[test]
173    fn wrapping_sub_no_borrow() {
174        assert_eq!(Limb::ONE.wrapping_sub(Limb::ONE), Limb::ZERO);
175    }
176
177    #[test]
178    fn wrapping_sub_with_borrow() {
179        assert_eq!(Limb::ZERO.wrapping_sub(Limb::ONE), Limb::MAX);
180    }
181
182    #[test]
183    fn checked_sub_ok() {
184        let result = Limb::ONE.checked_sub(&Limb::ONE);
185        assert_eq!(result.unwrap(), Limb::ZERO);
186    }
187
188    #[test]
189    fn checked_sub_overflow() {
190        let result = Limb::ZERO.checked_sub(&Limb::ONE);
191        assert!(!bool::from(result.is_some()));
192    }
193}
crypto_bigint/limb/sub.rs

crypto_bigint/limb/
sub.rs
