crypto_bigint/uint/boxed/
add.rs

1//! [`BoxedUint`] addition operations.
2
3use crate::{
4    Add, AddAssign, BoxedUint, CheckedAdd, Choice, CtOption, Limb, U64, U128, UintRef, Wrapping,
5    WrappingAdd,
6};
7use core::cmp;
8
9impl BoxedUint {
10    /// Computes `self + rhs + carry`, returning the result along with the new carry.
11    #[deprecated(since = "0.7.0", note = "please use `carrying_add` instead")]
12    #[must_use]
13    pub fn adc(&self, rhs: &Self, carry: Limb) -> (Self, Limb) {
14        self.carrying_add(rhs, carry)
15    }
16
17    /// Computes `self + rhs + carry`, returning the result along with the new carry.
18    ///
19    /// The result is widened to the same width as the widest input.
20    #[inline(always)]
21    #[must_use]
22    pub fn carrying_add(&self, rhs: impl AsRef<UintRef>, carry: Limb) -> (Self, Limb) {
23        let rhs = rhs.as_ref();
24        let precision = cmp::max(self.bits_precision(), rhs.bits_precision());
25        let mut result = Self::zero_with_precision(precision);
26        let carry =
27            result
28                .as_mut_uint_ref()
29                .fold_limbs(self.as_uint_ref(), rhs, carry, Limb::carrying_add);
30        (result, carry)
31    }
32
33    /// Computes `self + rhs + carry` in-place, returning the new carry.
34    ///
35    /// # Panics
36    /// - if `rhs` has a larger precision than `self`.
37    #[deprecated(since = "0.7.0", note = "please use `carrying_add_assign` instead")]
38    pub fn adc_assign(&mut self, rhs: impl AsRef<[Limb]>, carry: Limb) -> Limb {
39        self.carrying_add_assign(UintRef::new(rhs.as_ref()), carry)
40    }
41
42    /// Computes `self + rhs + carry` in-place, returning the new carry.
43    ///
44    /// # Panics
45    /// - if `rhs` has a larger precision than `self`.
46    #[inline(always)]
47    #[track_caller]
48    pub(crate) fn carrying_add_assign(&mut self, rhs: impl AsRef<UintRef>, carry: Limb) -> Limb {
49        let rhs = rhs.as_ref();
50        assert!(rhs.nlimbs() <= self.nlimbs());
51
52        self.as_mut_uint_ref()
53            .fold_limbs_assign(rhs, carry, Limb::carrying_add)
54    }
55
56    /// Computes `self + rhs`, returning a result which is concatenated with the overflow limb which
57    /// would be returned if `carrying_add` were called with the same operands.
58    #[must_use]
59    pub fn concatenating_add(&self, rhs: impl AsRef<UintRef>) -> Self {
60        let rhs = rhs.as_ref();
61        let bits = cmp::max(self.bits_precision(), rhs.bits_precision()) + 1;
62        let mut result = Self::zero_with_precision(bits);
63        let overflow = result.as_mut_uint_ref().fold_limbs(
64            self.as_uint_ref(),
65            rhs,
66            Limb::ZERO,
67            Limb::carrying_add,
68        );
69        // Overflow should always be zero here because we added a zero limb to the result
70        debug_assert_eq!(overflow, Limb::ZERO);
71        result
72    }
73
74    /// Computes `self + rhs`, returning a tuple of the sum along with a [`Choice`] which indicates
75    /// whether an overflow occurred.
76    ///
77    /// If an overflow occurred, then the wrapped value is returned.
78    #[must_use]
79    pub fn overflowing_add(&self, rhs: impl AsRef<UintRef>) -> (Self, Choice) {
80        let rhs = rhs.as_ref();
81        let nlimbs = cmp::min(self.nlimbs(), rhs.nlimbs());
82        let (rhs, rhs_over) = rhs.split_at(nlimbs);
83        let (ret, carry) = self.carrying_add(rhs, Limb::ZERO);
84        (ret, carry.is_nonzero().or(rhs_over.is_nonzero()))
85    }
86
87    /// Adds `rhs` to self, returning a [`Choice`] which indicates whether an overflow occurred.
88    ///
89    /// If an overflow occurred, then the wrapped value is returned.
90    pub fn overflowing_add_assign(&mut self, rhs: impl AsRef<UintRef>) -> Choice {
91        let rhs = rhs.as_ref();
92        let nlimbs = cmp::min(self.nlimbs(), rhs.nlimbs());
93        let (rhs, rhs_over) = rhs.split_at(nlimbs);
94        let carry = self.carrying_add_assign(rhs, Limb::ZERO);
95        carry.is_nonzero().or(rhs_over.is_nonzero())
96    }
97
98    /// Perform wrapping addition, discarding overflow.
99    #[must_use]
100    pub fn wrapping_add(&self, rhs: impl AsRef<UintRef>) -> Self {
101        let rhs = rhs.as_ref();
102        let nlimbs = cmp::min(self.nlimbs(), rhs.nlimbs());
103        self.carrying_add(rhs.leading(nlimbs), Limb::ZERO).0
104    }
105
106    /// Perform wrapping addition of `rhs` to `self`, discarding overflow.
107    pub fn wrapping_add_assign(&mut self, rhs: impl AsRef<UintRef>) {
108        let rhs = rhs.as_ref();
109        let nlimbs = cmp::min(self.nlimbs(), rhs.nlimbs());
110        self.carrying_add_assign(rhs.leading(nlimbs), Limb::ZERO);
111    }
112
113    /// Perform a conditional in-place wrapping addition, returning the truthy value
114    /// if an overflow has occurred.
115    pub(crate) fn conditional_carrying_add_assign(&mut self, rhs: &Self, choice: Choice) -> Choice {
116        self.as_mut_uint_ref()
117            .conditional_add_assign(rhs.as_uint_ref(), Limb::ZERO, choice)
118            .lsb_to_choice()
119    }
120}
121
122impl<Rhs: AsRef<UintRef>> Add<Rhs> for BoxedUint {
123    type Output = Self;
124
125    fn add(self, rhs: Rhs) -> Self {
126        Add::add(&self, rhs)
127    }
128}
129
130impl<Rhs: AsRef<UintRef>> Add<Rhs> for &BoxedUint {
131    type Output = BoxedUint;
132
133    fn add(self, rhs: Rhs) -> BoxedUint {
134        let (res, overflow) = self.overflowing_add(rhs);
135        assert!(overflow.not().to_bool(), "attempted to add with overflow");
136        res
137    }
138}
139
140impl<Rhs: AsRef<UintRef>> AddAssign<Rhs> for BoxedUint {
141    fn add_assign(&mut self, rhs: Rhs) {
142        let overflow = self.overflowing_add_assign(rhs);
143        assert!(overflow.not().to_bool(), "attempted to add with overflow");
144    }
145}
146
147impl<Rhs: AsRef<UintRef>> AddAssign<Rhs> for Wrapping<BoxedUint> {
148    fn add_assign(&mut self, other: Rhs) {
149        self.0.wrapping_add_assign(other);
150    }
151}
152
153impl<Rhs: AsRef<UintRef>> CheckedAdd<Rhs> for BoxedUint {
154    fn checked_add(&self, rhs: &Rhs) -> CtOption<Self> {
155        let (result, overflow) = self.overflowing_add(rhs);
156        CtOption::new(result, overflow.not())
157    }
158}
159
160impl WrappingAdd for BoxedUint {
161    fn wrapping_add(&self, v: &Self) -> Self {
162        self.wrapping_add(v)
163    }
164}
165
166macro_rules! impl_add_primitive {
167    ($($primitive:ty),+) => {
168        $(
169            impl Add<$primitive> for BoxedUint {
170                type Output = <Self as Add<U64>>::Output;
171
172                #[inline]
173                fn add(self, rhs: $primitive) -> Self::Output {
174                    self + U64::from(rhs)
175                }
176            }
177
178            impl Add<$primitive> for &BoxedUint {
179                type Output = <Self as Add<U64>>::Output;
180
181                #[inline]
182                fn add(self, rhs: $primitive) -> Self::Output {
183                    self + U64::from(rhs)
184                }
185            }
186
187            impl AddAssign<$primitive> for BoxedUint {
188                fn add_assign(&mut self, rhs: $primitive) {
189                    *self += U64::from(rhs);
190                }
191            }
192        )+
193    };
194}
195
196impl_add_primitive!(u8, u16, u32, u64);
197
198impl Add<u128> for BoxedUint {
199    type Output = BoxedUint;
200
201    #[inline]
202    fn add(self, rhs: u128) -> BoxedUint {
203        self + U128::from(rhs)
204    }
205}
206
207impl Add<u128> for &BoxedUint {
208    type Output = BoxedUint;
209
210    #[inline]
211    fn add(self, rhs: u128) -> BoxedUint {
212        self + U128::from(rhs)
213    }
214}
215
216impl AddAssign<u128> for BoxedUint {
217    fn add_assign(&mut self, rhs: u128) {
218        *self += U128::from(rhs);
219    }
220}
221
222#[cfg(test)]
223#[allow(clippy::unwrap_used)]
224mod tests {
225    use super::{BoxedUint, CheckedAdd, Limb, UintRef, Wrapping};
226    use crate::Resize;
227
228    #[test]
229    fn add_assign() {
230        let mut h = BoxedUint::one().resize(1024);
231        h += BoxedUint::one();
232        assert_eq!(h, BoxedUint::from(2u8));
233    }
234
235    #[test]
236    fn add_with_u32_rhs() {
237        let a = BoxedUint::from(1u64);
238        let b = a + u32::MAX;
239        assert_eq!(b, BoxedUint::from(0x100000000u64));
240    }
241
242    #[test]
243    fn carrying_add_no_carry() {
244        let (res, carry) = BoxedUint::zero().carrying_add(BoxedUint::one(), Limb::ZERO);
245        assert_eq!(res, BoxedUint::one());
246        assert_eq!(carry, Limb::ZERO);
247    }
248
249    #[test]
250    fn carrying_add_with_carry() {
251        let (res, carry) = BoxedUint::max(Limb::BITS).carrying_add(BoxedUint::one(), Limb::ZERO);
252        assert_eq!(res, BoxedUint::zero());
253        assert_eq!(carry, Limb::ONE);
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
268    #[test]
269    fn concatenating_add() {
270        let result = BoxedUint::max(Limb::BITS).concatenating_add(BoxedUint::one());
271        assert_eq!(result.as_limbs(), &[Limb::ZERO, Limb::ONE]);
272    }
273
274    #[test]
275    fn overflowing_add() {
276        let one = BoxedUint::one();
277        let (ret, overflow) = one.overflowing_add(&one);
278        assert_eq!(ret, &one + &one);
279        assert!(!overflow.to_bool());
280
281        let (ret, overflow) = BoxedUint::max(2 * Limb::BITS).overflowing_add(&one);
282        assert!(ret.is_zero().to_bool());
283        assert!(overflow.to_bool());
284    }
285
286    #[test]
287    fn wrapping_add() {
288        let ret = BoxedUint::one().wrapping_add(Limb::ONE);
289        assert_eq!(ret, BoxedUint::from(2u8));
290
291        let mut ret = Wrapping(BoxedUint::max(2 * Limb::BITS));
292        ret += Wrapping(Limb::ONE);
293        assert!(ret.0.is_zero_vartime());
294    }
295
296    #[test]
297    fn add_uintref() {
298        let a = BoxedUint::from(1234567890u64);
299        let b = UintRef::new(&[Limb(456), Limb(0)]);
300        assert_eq!(
301            a.carrying_add(b, Limb::ZERO).0,
302            BoxedUint::from(1234568346u64)
303        );
304    }
305}
crypto_bigint/uint/boxed/add.rs

crypto_bigint/uint/boxed/
add.rs
