1use super::BigUint;
2
3use crate::big_digit::{self, BigDigit};
4use crate::UsizePromotion;
5
6use core::cmp::Ordering::{Equal, Greater, Less};
7use core::ops::{Sub, SubAssign};
8use num_traits::CheckedSub;
9
10#[cfg(target_arch = "x86_64")]
11use core::arch::x86_64 as arch;
12
13#[cfg(target_arch = "x86")]
14use core::arch::x86 as arch;
15
16// Subtract with borrow:
17#[cfg(target_arch = "x86_64")]
18cfg_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"))]
28cfg_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]
41fn 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
48pub(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]
77fn __sub2rev(a: &[BigDigit], b: &mut [BigDigit]) -> u8 {
78 debug_assert!(b.len() == a.len());
79
80 let mut borrow: u8 = 0;
81
82 for (ai: &u64, bi: &mut u64) in a.iter().zip(b) {
83 borrow = sbb(borrow, *ai, *bi, out:bi);
84 }
85
86 borrow
87}
88
89fn sub2rev(a: &[BigDigit], b: &mut [BigDigit]) {
90 debug_assert!(b.len() >= a.len());
91
92 let len: usize = Ord::min(self:a.len(), other:b.len());
93 let (a_lo: &[u64], a_hi: &[u64]) = a.split_at(mid:len);
94 let (b_lo: &mut [u64], b_hi: &mut [u64]) = b.split_at_mut(mid:len);
95
96 let borrow: u8 = __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
107forward_val_val_binop!(impl Sub for BigUint, sub);
108forward_ref_ref_binop!(impl Sub for BigUint, sub);
109forward_val_assign!(impl SubAssign for BigUint, sub_assign);
110
111impl Sub<&BigUint> for BigUint {
112 type Output = BigUint;
113
114 fn sub(mut self, other: &BigUint) -> BigUint {
115 self -= other;
116 self
117 }
118}
119impl SubAssign<&BigUint> for BigUint {
120 fn sub_assign(&mut self, other: &BigUint) {
121 sub2(&mut self.data[..], &other.data[..]);
122 self.normalize();
123 }
124}
125
126impl Sub<BigUint> for &BigUint {
127 type Output = BigUint;
128
129 fn sub(self, mut other: BigUint) -> BigUint {
130 let other_len: usize = other.data.len();
131 if other_len < self.data.len() {
132 let lo_borrow: u8 = __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
144promote_unsigned_scalars!(impl Sub for BigUint, sub);
145promote_unsigned_scalars_assign!(impl SubAssign for BigUint, sub_assign);
146forward_all_scalar_binop_to_val_val!(impl Sub<u32> for BigUint, sub);
147forward_all_scalar_binop_to_val_val!(impl Sub<u64> for BigUint, sub);
148forward_all_scalar_binop_to_val_val!(impl Sub<u128> for BigUint, sub);
149
150impl Sub<u32> for BigUint {
151 type Output = BigUint;
152
153 #[inline]
154 fn sub(mut self, other: u32) -> BigUint {
155 self -= other;
156 self
157 }
158}
159
160impl SubAssign<u32> for BigUint {
161 fn sub_assign(&mut self, other: u32) {
162 sub2(&mut self.data[..], &[other as BigDigit]);
163 self.normalize();
164 }
165}
166
167impl 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
193impl Sub<u64> for BigUint {
194 type Output = BigUint;
195
196 #[inline]
197 fn sub(mut self, other: u64) -> BigUint {
198 self -= other;
199 self
200 }
201}
202
203impl 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
220impl 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
247impl Sub<u128> for BigUint {
248 type Output = BigUint;
249
250 #[inline]
251 fn sub(mut self, other: u128) -> BigUint {
252 self -= other;
253 self
254 }
255}
256
257impl 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
275impl 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
303impl CheckedSub for BigUint {
304 #[inline]
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