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