num_bigint/biguint/
addition.rs

Help
1#[cfg(not(u64_digit))]
2use super::u32_from_u128;
3use super::{BigUint, IntDigits};
4
5use crate::big_digit::{self, BigDigit};
6use crate::UsizePromotion;
7
8use core::iter::Sum;
9use core::ops::{Add, AddAssign};
10use num_traits::{CheckedAdd, Zero};
11
12#[cfg(all(use_addcarry, target_arch = "x86_64"))]
13use core::arch::x86_64 as arch;
14
15#[cfg(all(use_addcarry, target_arch = "x86"))]
16use core::arch::x86 as arch;
17
18// Add with carry:
19#[cfg(all(use_addcarry, u64_digit))]
20#[inline]
21fn 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]
29fn 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]
38fn 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]
53pub(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.
80pub(super) fn add2(a: &mut [BigDigit], b: &[BigDigit]) {
81    let carry = __add2(a, b);
82
83    debug_assert!(carry == 0);
84}
85
86forward_all_binop_to_val_ref_commutative!(impl Add for BigUint, add);
87forward_val_assign!(impl AddAssign for BigUint, add_assign);
88
89impl<'a> Add<&'a BigUint> for BigUint {
90    type Output = BigUint;
91
92    fn add(mut self, other: &BigUint) -> BigUint {
93        self += other;
94        self
95    }
96}
97impl<'a> AddAssign<&'a BigUint> for BigUint {
98    #[inline]
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
114promote_unsigned_scalars!(impl Add for BigUint, add);
115promote_unsigned_scalars_assign!(impl AddAssign for BigUint, add_assign);
116forward_all_scalar_binop_to_val_val_commutative!(impl Add<u32> for BigUint, add);
117forward_all_scalar_binop_to_val_val_commutative!(impl Add<u64> for BigUint, add);
118forward_all_scalar_binop_to_val_val_commutative!(impl Add<u128> for BigUint, add);
119
120impl Add<u32> for BigUint {
121    type Output = BigUint;
122
123    #[inline]
124    fn add(mut self, other: u32) -> BigUint {
125        self += other;
126        self
127    }
128}
129
130impl AddAssign<u32> for BigUint {
131    #[inline]
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
146impl Add<u64> for BigUint {
147    type Output = BigUint;
148
149    #[inline]
150    fn add(mut self, other: u64) -> BigUint {
151        self += other;
152        self
153    }
154}
155
156impl AddAssign<u64> for BigUint {
157    #[cfg(not(u64_digit))]
158    #[inline]
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]
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
191impl Add<u128> for BigUint {
192    type Output = BigUint;
193
194    #[inline]
195    fn add(mut self, other: u128) -> BigUint {
196        self += other;
197        self
198    }
199}
200
201impl AddAssign<u128> for BigUint {
202    #[cfg(not(u64_digit))]
203    #[inline]
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]
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
247impl CheckedAdd for BigUint {
248    #[inline]
249    fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
250        Some(self.add(v))
251    }
252}
253
254impl_sum_iter_type!(BigUint);
num_bigint/biguint/addition.rs

num_bigint/biguint/
addition.rs
