1 use super::BigUint;
2
3 use crate::big_digit::{self, BigDigit};
4 use crate::UsizePromotion;
5
6 use core::cmp::Ordering::{Equal, Greater, Less};
7 use core::ops::{Sub, SubAssign};
8 use num_traits::CheckedSub;
9
10 #[cfg(target_arch = "x86_64")]
11 use core::arch::x86_64 as arch;
12
13 #[cfg(target_arch = "x86")]
14 use core::arch::x86 as arch;
15
16 // Subtract with borrow:
17 #[cfg(target_arch = "x86_64")]
18 cfg_64!(
19 #[inline]
20 fn sbb(borrow: u8, a: u64, b: u64, out: &mut u64) -> u8 {
21 // Safety: There are absolutely no safety concerns with calling `_subborrow_u64`.
22 // It's just unsafe for API consistency with other intrinsics.
23 unsafe { arch::_subborrow_u64(borrow, a, b, out) }
24 }
25 );
26
27 #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
28 cfg_32!(
29 #[inline]
30 fn sbb(borrow: u8, a: u32, b: u32, out: &mut u32) -> u8 {
31 // Safety: There are absolutely no safety concerns with calling `_subborrow_u32`.
32 // It's just unsafe for API consistency with other intrinsics.
33 unsafe { arch::_subborrow_u32(borrow, a, b, out) }
34 }
35 );
36
37 // fallback for environments where we don't have a subborrow intrinsic
38 // (copied from the standard library's `borrowing_sub`)
39 #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
40 #[inline]
sbb(borrow: u8, lhs: BigDigit, rhs: BigDigit, out: &mut BigDigit) -> u841 fn sbb(borrow: u8, lhs: BigDigit, rhs: BigDigit, out: &mut BigDigit) -> u8 {
42 let (a, b) = lhs.overflowing_sub(rhs);
43 let (c, d) = a.overflowing_sub(borrow as BigDigit);
44 *out = c;
45 u8::from(b || d)
46 }
47
sub2(a: &mut [BigDigit], b: &[BigDigit])48 pub(super) fn sub2(a: &mut [BigDigit], b: &[BigDigit]) {
49 let mut borrow = 0;
50
51 let len = Ord::min(a.len(), b.len());
52 let (a_lo, a_hi) = a.split_at_mut(len);
53 let (b_lo, b_hi) = b.split_at(len);
54
55 for (a, b) in a_lo.iter_mut().zip(b_lo) {
56 borrow = sbb(borrow, *a, *b, a);
57 }
58
59 if borrow != 0 {
60 for a in a_hi {
61 borrow = sbb(borrow, *a, 0, a);
62 if borrow == 0 {
63 break;
64 }
65 }
66 }
67
68 // note: we're _required_ to fail on underflow
69 assert!(
70 borrow == 0 && b_hi.iter().all(|x| *x == 0),
71 "Cannot subtract b from a because b is larger than a."
72 );
73 }
74
75 // Only for the Sub impl. `a` and `b` must have same length.
76 #[inline]
__sub2rev(a: &[BigDigit], b: &mut [BigDigit]) -> u877 fn __sub2rev(a: &[BigDigit], b: &mut [BigDigit]) -> u8 {
78 debug_assert!(b.len() == a.len());
79
80 let mut borrow = 0;
81
82 for (ai, bi) in a.iter().zip(b) {
83 borrow = sbb(borrow, *ai, *bi, bi);
84 }
85
86 borrow
87 }
88
sub2rev(a: &[BigDigit], b: &mut [BigDigit])89 fn sub2rev(a: &[BigDigit], b: &mut [BigDigit]) {
90 debug_assert!(b.len() >= a.len());
91
92 let len = Ord::min(a.len(), b.len());
93 let (a_lo, a_hi) = a.split_at(len);
94 let (b_lo, b_hi) = b.split_at_mut(len);
95
96 let borrow = __sub2rev(a_lo, b_lo);
97
98 assert!(a_hi.is_empty());
99
100 // note: we're _required_ to fail on underflow
101 assert!(
102 borrow == 0 && b_hi.iter().all(|x| *x == 0),
103 "Cannot subtract b from a because b is larger than a."
104 );
105 }
106
107 forward_val_val_binop!(impl Sub for BigUint, sub);
108 forward_ref_ref_binop!(impl Sub for BigUint, sub);
109 forward_val_assign!(impl SubAssign for BigUint, sub_assign);
110
111 impl Sub<&BigUint> for BigUint {
112 type Output = BigUint;
113
sub(mut self, other: &BigUint) -> BigUint114 fn sub(mut self, other: &BigUint) -> BigUint {
115 self -= other;
116 self
117 }
118 }
119 impl SubAssign<&BigUint> for BigUint {
sub_assign(&mut self, other: &BigUint)120 fn sub_assign(&mut self, other: &BigUint) {
121 sub2(&mut self.data[..], &other.data[..]);
122 self.normalize();
123 }
124 }
125
126 impl Sub<BigUint> for &BigUint {
127 type Output = BigUint;
128
sub(self, mut other: BigUint) -> BigUint129 fn sub(self, mut other: BigUint) -> BigUint {
130 let other_len = other.data.len();
131 if other_len < self.data.len() {
132 let lo_borrow = __sub2rev(&self.data[..other_len], &mut other.data);
133 other.data.extend_from_slice(&self.data[other_len..]);
134 if lo_borrow != 0 {
135 sub2(&mut other.data[other_len..], &[1])
136 }
137 } else {
138 sub2rev(&self.data[..], &mut other.data[..]);
139 }
140 other.normalized()
141 }
142 }
143
144 promote_unsigned_scalars!(impl Sub for BigUint, sub);
145 promote_unsigned_scalars_assign!(impl SubAssign for BigUint, sub_assign);
146 forward_all_scalar_binop_to_val_val!(impl Sub<u32> for BigUint, sub);
147 forward_all_scalar_binop_to_val_val!(impl Sub<u64> for BigUint, sub);
148 forward_all_scalar_binop_to_val_val!(impl Sub<u128> for BigUint, sub);
149
150 impl Sub<u32> for BigUint {
151 type Output = BigUint;
152
153 #[inline]
sub(mut self, other: u32) -> BigUint154 fn sub(mut self, other: u32) -> BigUint {
155 self -= other;
156 self
157 }
158 }
159
160 impl SubAssign<u32> for BigUint {
sub_assign(&mut self, other: u32)161 fn sub_assign(&mut self, other: u32) {
162 sub2(&mut self.data[..], &[other as BigDigit]);
163 self.normalize();
164 }
165 }
166
167 impl Sub<BigUint> for u32 {
168 type Output = BigUint;
169
170 cfg_digit!(
171 #[inline]
172 fn sub(self, mut other: BigUint) -> BigUint {
173 if other.data.len() == 0 {
174 other.data.push(self);
175 } else {
176 sub2rev(&[self], &mut other.data[..]);
177 }
178 other.normalized()
179 }
180
181 #[inline]
182 fn sub(self, mut other: BigUint) -> BigUint {
183 if other.data.is_empty() {
184 other.data.push(self as BigDigit);
185 } else {
186 sub2rev(&[self as BigDigit], &mut other.data[..]);
187 }
188 other.normalized()
189 }
190 );
191 }
192
193 impl Sub<u64> for BigUint {
194 type Output = BigUint;
195
196 #[inline]
sub(mut self, other: u64) -> BigUint197 fn sub(mut self, other: u64) -> BigUint {
198 self -= other;
199 self
200 }
201 }
202
203 impl SubAssign<u64> for BigUint {
204 cfg_digit!(
205 #[inline]
206 fn sub_assign(&mut self, other: u64) {
207 let (hi, lo) = big_digit::from_doublebigdigit(other);
208 sub2(&mut self.data[..], &[lo, hi]);
209 self.normalize();
210 }
211
212 #[inline]
213 fn sub_assign(&mut self, other: u64) {
214 sub2(&mut self.data[..], &[other as BigDigit]);
215 self.normalize();
216 }
217 );
218 }
219
220 impl Sub<BigUint> for u64 {
221 type Output = BigUint;
222
223 cfg_digit!(
224 #[inline]
225 fn sub(self, mut other: BigUint) -> BigUint {
226 while other.data.len() < 2 {
227 other.data.push(0);
228 }
229
230 let (hi, lo) = big_digit::from_doublebigdigit(self);
231 sub2rev(&[lo, hi], &mut other.data[..]);
232 other.normalized()
233 }
234
235 #[inline]
236 fn sub(self, mut other: BigUint) -> BigUint {
237 if other.data.is_empty() {
238 other.data.push(self);
239 } else {
240 sub2rev(&[self], &mut other.data[..]);
241 }
242 other.normalized()
243 }
244 );
245 }
246
247 impl Sub<u128> for BigUint {
248 type Output = BigUint;
249
250 #[inline]
sub(mut self, other: u128) -> BigUint251 fn sub(mut self, other: u128) -> BigUint {
252 self -= other;
253 self
254 }
255 }
256
257 impl SubAssign<u128> for BigUint {
258 cfg_digit!(
259 #[inline]
260 fn sub_assign(&mut self, other: u128) {
261 let (a, b, c, d) = super::u32_from_u128(other);
262 sub2(&mut self.data[..], &[d, c, b, a]);
263 self.normalize();
264 }
265
266 #[inline]
267 fn sub_assign(&mut self, other: u128) {
268 let (hi, lo) = big_digit::from_doublebigdigit(other);
269 sub2(&mut self.data[..], &[lo, hi]);
270 self.normalize();
271 }
272 );
273 }
274
275 impl Sub<BigUint> for u128 {
276 type Output = BigUint;
277
278 cfg_digit!(
279 #[inline]
280 fn sub(self, mut other: BigUint) -> BigUint {
281 while other.data.len() < 4 {
282 other.data.push(0);
283 }
284
285 let (a, b, c, d) = super::u32_from_u128(self);
286 sub2rev(&[d, c, b, a], &mut other.data[..]);
287 other.normalized()
288 }
289
290 #[inline]
291 fn sub(self, mut other: BigUint) -> BigUint {
292 while other.data.len() < 2 {
293 other.data.push(0);
294 }
295
296 let (hi, lo) = big_digit::from_doublebigdigit(self);
297 sub2rev(&[lo, hi], &mut other.data[..]);
298 other.normalized()
299 }
300 );
301 }
302
303 impl CheckedSub for BigUint {
304 #[inline]
checked_sub(&self, v: &BigUint) -> Option<BigUint>305 fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
306 match self.cmp(v) {
307 Less => None,
308 Equal => Some(Self::ZERO),
309 Greater => Some(self.sub(v)),
310 }
311 }
312 }
313