crypto_bigint/uint/boxed/
add.rs

1//! [`BoxedUint`] addition operations.
2
3use crate::{BoxedUint, CheckedAdd, Limb, Uint, Wrapping, WrappingAdd, Zero, U128, U64};
4use core::ops::{Add, AddAssign};
5use subtle::{Choice, ConditionallySelectable, CtOption};
6
7impl BoxedUint {
8    /// Computes `a + b + carry`, returning the result along with the new carry.
9    #[inline(always)]
10    pub fn adc(&self, rhs: &Self, carry: Limb) -> (Self, Limb) {
11        Self::fold_limbs(self, rhs, carry, |a, b, c| a.adc(b, c))
12    }
13
14    /// Computes `a + b + carry` in-place, returning the new carry.
15    ///
16    /// Panics if `rhs` has a larger precision than `self`.
17    #[inline]
18    pub fn adc_assign(&mut self, rhs: impl AsRef<[Limb]>, mut carry: Limb) -> Limb {
19        debug_assert!(self.bits_precision() <= (rhs.as_ref().len() as u32 * Limb::BITS));
20
21        for i in 0..self.nlimbs() {
22            let (limb, b) = self.limbs[i].adc(*rhs.as_ref().get(i).unwrap_or(&Limb::ZERO), carry);
23            self.limbs[i] = limb;
24            carry = b;
25        }
26
27        carry
28    }
29
30    /// Perform wrapping addition, discarding overflow.
31    pub fn wrapping_add(&self, rhs: &Self) -> Self {
32        self.adc(rhs, Limb::ZERO).0
33    }
34
35    /// Perform in-place wrapping addition, returning the truthy value as the second element of the
36    /// tuple if an overflow has occurred.
37    pub(crate) fn conditional_adc_assign(&mut self, rhs: &Self, choice: Choice) -> Choice {
38        debug_assert!(self.bits_precision() <= rhs.bits_precision());
39        let mask = Limb::conditional_select(&Limb::ZERO, &Limb::MAX, choice);
40        let mut carry = Limb::ZERO;
41
42        for i in 0..self.nlimbs() {
43            let masked_rhs = *rhs.limbs.get(i).unwrap_or(&Limb::ZERO) & mask;
44            let (limb, c) = self.limbs[i].adc(masked_rhs, carry);
45            self.limbs[i] = limb;
46            carry = c;
47        }
48
49        Choice::from((carry.0 & 1) as u8)
50    }
51}
52
53impl Add for BoxedUint {
54    type Output = Self;
55
56    fn add(self, rhs: Self) -> Self {
57        self.add(&rhs)
58    }
59}
60
61impl Add<&BoxedUint> for BoxedUint {
62    type Output = Self;
63
64    fn add(self, rhs: &Self) -> Self {
65        Add::add(&self, rhs)
66    }
67}
68
69impl Add<BoxedUint> for &BoxedUint {
70    type Output = BoxedUint;
71
72    fn add(self, rhs: BoxedUint) -> BoxedUint {
73        Add::add(self, &rhs)
74    }
75}
76
77impl Add<&BoxedUint> for &BoxedUint {
78    type Output = BoxedUint;
79
80    fn add(self, rhs: &BoxedUint) -> BoxedUint {
81        self.checked_add(rhs)
82            .expect("attempted to add with overflow")
83    }
84}
85
86impl AddAssign<BoxedUint> for BoxedUint {
87    fn add_assign(&mut self, rhs: BoxedUint) {
88        self.add_assign(&rhs)
89    }
90}
91
92impl AddAssign<&BoxedUint> for BoxedUint {
93    fn add_assign(&mut self, rhs: &BoxedUint) {
94        let carry = self.adc_assign(rhs, Limb::ZERO);
95        assert_eq!(
96            carry.is_zero().unwrap_u8(),
97            1,
98            "attempted to add with overflow"
99        );
100    }
101}
102
103impl<const LIMBS: usize> Add<Uint<LIMBS>> for BoxedUint {
104    type Output = BoxedUint;
105
106    fn add(self, rhs: Uint<LIMBS>) -> BoxedUint {
107        self.add(&rhs)
108    }
109}
110
111impl<const LIMBS: usize> Add<&Uint<LIMBS>> for BoxedUint {
112    type Output = BoxedUint;
113
114    fn add(mut self, rhs: &Uint<LIMBS>) -> BoxedUint {
115        self += rhs;
116        self
117    }
118}
119
120impl<const LIMBS: usize> Add<Uint<LIMBS>> for &BoxedUint {
121    type Output = BoxedUint;
122
123    fn add(self, rhs: Uint<LIMBS>) -> BoxedUint {
124        self.clone().add(rhs)
125    }
126}
127
128impl<const LIMBS: usize> Add<&Uint<LIMBS>> for &BoxedUint {
129    type Output = BoxedUint;
130
131    fn add(self, rhs: &Uint<LIMBS>) -> BoxedUint {
132        self.clone().add(rhs)
133    }
134}
135
136impl<const LIMBS: usize> AddAssign<Uint<LIMBS>> for BoxedUint {
137    fn add_assign(&mut self, rhs: Uint<LIMBS>) {
138        *self += &rhs;
139    }
140}
141
142impl<const LIMBS: usize> AddAssign<&Uint<LIMBS>> for BoxedUint {
143    fn add_assign(&mut self, rhs: &Uint<LIMBS>) {
144        let carry = self.adc_assign(rhs.as_limbs(), Limb::ZERO);
145        assert_eq!(carry.0, 0, "attempted to add with overflow");
146    }
147}
148
149impl AddAssign<Wrapping<BoxedUint>> for Wrapping<BoxedUint> {
150    fn add_assign(&mut self, other: Wrapping<BoxedUint>) {
151        self.0.adc_assign(&other.0, Limb::ZERO);
152    }
153}
154
155impl AddAssign<&Wrapping<BoxedUint>> for Wrapping<BoxedUint> {
156    fn add_assign(&mut self, other: &Wrapping<BoxedUint>) {
157        self.0.adc_assign(&other.0, Limb::ZERO);
158    }
159}
160
161impl CheckedAdd for BoxedUint {
162    fn checked_add(&self, rhs: &Self) -> CtOption<Self> {
163        let (result, carry) = self.adc(rhs, Limb::ZERO);
164        CtOption::new(result, carry.is_zero())
165    }
166}
167
168impl WrappingAdd for BoxedUint {
169    fn wrapping_add(&self, v: &Self) -> Self {
170        self.wrapping_add(v)
171    }
172}
173
174macro_rules! impl_add_primitive {
175    ($($primitive:ty),+) => {
176        $(
177            impl Add<$primitive> for BoxedUint {
178                type Output = BoxedUint;
179
180                #[inline]
181                fn add(self, rhs: $primitive) -> BoxedUint {
182                     self + U64::from(rhs)
183                }
184            }
185
186            impl Add<$primitive> for &BoxedUint {
187                type Output = BoxedUint;
188
189                #[inline]
190                fn add(self, rhs: $primitive) -> BoxedUint {
191                     self + U64::from(rhs)
192                }
193            }
194
195            impl AddAssign<$primitive> for BoxedUint {
196                fn add_assign(&mut self, rhs: $primitive) {
197                    *self += U64::from(rhs);
198                }
199            }
200        )+
201    };
202}
203
204impl_add_primitive!(u8, u16, u32, u64);
205
206impl Add<u128> for BoxedUint {
207    type Output = BoxedUint;
208
209    #[inline]
210    fn add(self, rhs: u128) -> BoxedUint {
211        self + U128::from(rhs)
212    }
213}
214
215impl Add<u128> for &BoxedUint {
216    type Output = BoxedUint;
217
218    #[inline]
219    fn add(self, rhs: u128) -> BoxedUint {
220        self + U128::from(rhs)
221    }
222}
223
224impl AddAssign<u128> for BoxedUint {
225    fn add_assign(&mut self, rhs: u128) {
226        *self += U128::from(rhs);
227    }
228}
229
230#[cfg(test)]
231#[allow(clippy::unwrap_used)]
232mod tests {
233    use super::{BoxedUint, CheckedAdd, Limb};
234
235    #[test]
236    fn adc_no_carry() {
237        let (res, carry) = BoxedUint::zero().adc(&BoxedUint::one(), Limb::ZERO);
238        assert_eq!(res, BoxedUint::one());
239        assert_eq!(carry, Limb::ZERO);
240    }
241
242    #[test]
243    fn adc_with_carry() {
244        let (res, carry) = BoxedUint::max(Limb::BITS).adc(&BoxedUint::one(), Limb::ZERO);
245        assert_eq!(res, BoxedUint::zero());
246        assert_eq!(carry, Limb::ONE);
247    }
248
249    #[test]
250    fn add_with_u32_rhs() {
251        let a = BoxedUint::from(1u64);
252        let b = a + u32::MAX;
253        assert_eq!(b, BoxedUint::from(0x100000000u64));
254    }
255
256    #[test]
257    fn checked_add_ok() {
258        let result = BoxedUint::zero().checked_add(&BoxedUint::one());
259        assert_eq!(result.unwrap(), BoxedUint::one());
260    }
261
262    #[test]
263    fn checked_add_overflow() {
264        let result = BoxedUint::max(Limb::BITS).checked_add(&BoxedUint::one());
265        assert!(!bool::from(result.is_some()));
266    }
267}
crypto_bigint/uint/boxed/add.rs

crypto_bigint/uint/boxed/
add.rs
