1 #[cfg(not(u64_digit))]
2 use super::u32_from_u128;
3 use super::{BigUint, IntDigits};
4
5 use crate::big_digit::{self, BigDigit};
6 use crate::UsizePromotion;
7
8 use core::iter::Sum;
9 use core::ops::{Add, AddAssign};
10 use num_traits::{CheckedAdd, Zero};
11
12 #[cfg(all(use_addcarry, target_arch = "x86_64"))]
13 use core::arch::x86_64 as arch;
14
15 #[cfg(all(use_addcarry, target_arch = "x86"))]
16 use core::arch::x86 as arch;
17
18 // Add with carry:
19 #[cfg(all(use_addcarry, u64_digit))]
20 #[inline]
adc(carry: u8, a: u64, b: u64, out: &mut u64) -> u821 fn adc(carry: u8, a: u64, b: u64, out: &mut u64) -> u8 {
22 // Safety: There are absolutely no safety concerns with calling `_addcarry_u64`.
23 // It's just unsafe for API consistency with other intrinsics.
24 unsafe { arch::_addcarry_u64(carry, a, b, out) }
25 }
26
27 #[cfg(all(use_addcarry, not(u64_digit)))]
28 #[inline]
adc(carry: u8, a: u32, b: u32, out: &mut u32) -> u829 fn adc(carry: u8, a: u32, b: u32, out: &mut u32) -> u8 {
30 // Safety: There are absolutely no safety concerns with calling `_addcarry_u32`.
31 // It's just unsafe for API consistency with other intrinsics.
32 unsafe { arch::_addcarry_u32(carry, a, b, out) }
33 }
34
35 // fallback for environments where we don't have an addcarry intrinsic
36 #[cfg(not(use_addcarry))]
37 #[inline]
adc(carry: u8, a: BigDigit, b: BigDigit, out: &mut BigDigit) -> u838 fn adc(carry: u8, a: BigDigit, b: BigDigit, out: &mut BigDigit) -> u8 {
39 use crate::big_digit::DoubleBigDigit;
40
41 let sum = DoubleBigDigit::from(a) + DoubleBigDigit::from(b) + DoubleBigDigit::from(carry);
42 *out = sum as BigDigit;
43 (sum >> big_digit::BITS) as u8
44 }
45
46 /// Two argument addition of raw slices, `a += b`, returning the carry.
47 ///
48 /// This is used when the data `Vec` might need to resize to push a non-zero carry, so we perform
49 /// the addition first hoping that it will fit.
50 ///
51 /// The caller _must_ ensure that `a` is at least as long as `b`.
52 #[inline]
__add2(a: &mut [BigDigit], b: &[BigDigit]) -> BigDigit53 pub(super) fn __add2(a: &mut [BigDigit], b: &[BigDigit]) -> BigDigit {
54 debug_assert!(a.len() >= b.len());
55
56 let mut carry = 0;
57 let (a_lo, a_hi) = a.split_at_mut(b.len());
58
59 for (a, b) in a_lo.iter_mut().zip(b) {
60 carry = adc(carry, *a, *b, a);
61 }
62
63 if carry != 0 {
64 for a in a_hi {
65 carry = adc(carry, *a, 0, a);
66 if carry == 0 {
67 break;
68 }
69 }
70 }
71
72 carry as BigDigit
73 }
74
75 /// Two argument addition of raw slices:
76 /// a += b
77 ///
78 /// The caller _must_ ensure that a is big enough to store the result - typically this means
79 /// resizing a to max(a.len(), b.len()) + 1, to fit a possible carry.
add2(a: &mut [BigDigit], b: &[BigDigit])80 pub(super) fn add2(a: &mut [BigDigit], b: &[BigDigit]) {
81 let carry = __add2(a, b);
82
83 debug_assert!(carry == 0);
84 }
85
86 forward_all_binop_to_val_ref_commutative!(impl Add for BigUint, add);
87 forward_val_assign!(impl AddAssign for BigUint, add_assign);
88
89 impl<'a> Add<&'a BigUint> for BigUint {
90 type Output = BigUint;
91
add(mut self, other: &BigUint) -> BigUint92 fn add(mut self, other: &BigUint) -> BigUint {
93 self += other;
94 self
95 }
96 }
97 impl<'a> AddAssign<&'a BigUint> for BigUint {
98 #[inline]
add_assign(&mut self, other: &BigUint)99 fn add_assign(&mut self, other: &BigUint) {
100 let self_len = self.data.len();
101 let carry = if self_len < other.data.len() {
102 let lo_carry = __add2(&mut self.data[..], &other.data[..self_len]);
103 self.data.extend_from_slice(&other.data[self_len..]);
104 __add2(&mut self.data[self_len..], &[lo_carry])
105 } else {
106 __add2(&mut self.data[..], &other.data[..])
107 };
108 if carry != 0 {
109 self.data.push(carry);
110 }
111 }
112 }
113
114 promote_unsigned_scalars!(impl Add for BigUint, add);
115 promote_unsigned_scalars_assign!(impl AddAssign for BigUint, add_assign);
116 forward_all_scalar_binop_to_val_val_commutative!(impl Add<u32> for BigUint, add);
117 forward_all_scalar_binop_to_val_val_commutative!(impl Add<u64> for BigUint, add);
118 forward_all_scalar_binop_to_val_val_commutative!(impl Add<u128> for BigUint, add);
119
120 impl Add<u32> for BigUint {
121 type Output = BigUint;
122
123 #[inline]
add(mut self, other: u32) -> BigUint124 fn add(mut self, other: u32) -> BigUint {
125 self += other;
126 self
127 }
128 }
129
130 impl AddAssign<u32> for BigUint {
131 #[inline]
add_assign(&mut self, other: u32)132 fn add_assign(&mut self, other: u32) {
133 if other != 0 {
134 if self.data.is_empty() {
135 self.data.push(0);
136 }
137
138 let carry = __add2(&mut self.data, &[other as BigDigit]);
139 if carry != 0 {
140 self.data.push(carry);
141 }
142 }
143 }
144 }
145
146 impl Add<u64> for BigUint {
147 type Output = BigUint;
148
149 #[inline]
add(mut self, other: u64) -> BigUint150 fn add(mut self, other: u64) -> BigUint {
151 self += other;
152 self
153 }
154 }
155
156 impl AddAssign<u64> for BigUint {
157 #[cfg(not(u64_digit))]
158 #[inline]
add_assign(&mut self, other: u64)159 fn add_assign(&mut self, other: u64) {
160 let (hi, lo) = big_digit::from_doublebigdigit(other);
161 if hi == 0 {
162 *self += lo;
163 } else {
164 while self.data.len() < 2 {
165 self.data.push(0);
166 }
167
168 let carry = __add2(&mut self.data, &[lo, hi]);
169 if carry != 0 {
170 self.data.push(carry);
171 }
172 }
173 }
174
175 #[cfg(u64_digit)]
176 #[inline]
add_assign(&mut self, other: u64)177 fn add_assign(&mut self, other: u64) {
178 if other != 0 {
179 if self.data.is_empty() {
180 self.data.push(0);
181 }
182
183 let carry = __add2(&mut self.data, &[other as BigDigit]);
184 if carry != 0 {
185 self.data.push(carry);
186 }
187 }
188 }
189 }
190
191 impl Add<u128> for BigUint {
192 type Output = BigUint;
193
194 #[inline]
add(mut self, other: u128) -> BigUint195 fn add(mut self, other: u128) -> BigUint {
196 self += other;
197 self
198 }
199 }
200
201 impl AddAssign<u128> for BigUint {
202 #[cfg(not(u64_digit))]
203 #[inline]
add_assign(&mut self, other: u128)204 fn add_assign(&mut self, other: u128) {
205 if other <= u128::from(u64::max_value()) {
206 *self += other as u64
207 } else {
208 let (a, b, c, d) = u32_from_u128(other);
209 let carry = if a > 0 {
210 while self.data.len() < 4 {
211 self.data.push(0);
212 }
213 __add2(&mut self.data, &[d, c, b, a])
214 } else {
215 debug_assert!(b > 0);
216 while self.data.len() < 3 {
217 self.data.push(0);
218 }
219 __add2(&mut self.data, &[d, c, b])
220 };
221
222 if carry != 0 {
223 self.data.push(carry);
224 }
225 }
226 }
227
228 #[cfg(u64_digit)]
229 #[inline]
add_assign(&mut self, other: u128)230 fn add_assign(&mut self, other: u128) {
231 let (hi, lo) = big_digit::from_doublebigdigit(other);
232 if hi == 0 {
233 *self += lo;
234 } else {
235 while self.data.len() < 2 {
236 self.data.push(0);
237 }
238
239 let carry = __add2(&mut self.data, &[lo, hi]);
240 if carry != 0 {
241 self.data.push(carry);
242 }
243 }
244 }
245 }
246
247 impl CheckedAdd for BigUint {
248 #[inline]
checked_add(&self, v: &BigUint) -> Option<BigUint>249 fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
250 Some(self.add(v))
251 }
252 }
253
254 impl_sum_iter_type!(BigUint);
255