crypto_bigint/
wrapping.rs

1//! Wrapping arithmetic.
2
3use crate::{
4    Choice, CtEq, CtSelect, Integer, One, UintRef, WrappingAdd, WrappingMul, WrappingNeg,
5    WrappingShl, WrappingShr, WrappingSub, Zero,
6};
7use core::{
8    fmt,
9    ops::{
10        Add, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Mul, Neg, Not, Shl,
11        Shr, Sub,
12    },
13};
14
15#[cfg(feature = "rand_core")]
16use {crate::Random, rand_core::TryRng};
17
18#[cfg(feature = "serde")]
19use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
20
21/// Provides intentionally-wrapped arithmetic on `T`.
22///
23/// This is analogous to [`core::num::Wrapping`] but allows this crate to
24/// define trait impls for this type.
25#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, PartialOrd, Ord)]
26pub struct Wrapping<T>(pub T);
27
28impl<T: AsRef<UintRef>> AsRef<UintRef> for Wrapping<T> {
29    fn as_ref(&self) -> &UintRef {
30        self.0.as_ref()
31    }
32}
33
34impl<T: AsMut<UintRef>> AsMut<UintRef> for Wrapping<T> {
35    fn as_mut(&mut self) -> &mut UintRef {
36        self.0.as_mut()
37    }
38}
39
40impl<T: WrappingAdd> Add<Self> for Wrapping<T> {
41    type Output = Wrapping<T>;
42
43    #[inline]
44    fn add(self, rhs: Self) -> Self::Output {
45        Wrapping(self.0.wrapping_add(&rhs.0))
46    }
47}
48
49impl<T: WrappingAdd> Add<&Self> for Wrapping<T> {
50    type Output = Wrapping<T>;
51
52    #[inline]
53    fn add(self, rhs: &Self) -> Self::Output {
54        Wrapping(self.0.wrapping_add(&rhs.0))
55    }
56}
57
58impl<T: WrappingAdd> Add<Wrapping<T>> for &Wrapping<T> {
59    type Output = Wrapping<T>;
60
61    #[inline]
62    fn add(self, rhs: Wrapping<T>) -> Self::Output {
63        Wrapping(self.0.wrapping_add(&rhs.0))
64    }
65}
66
67impl<T: WrappingAdd> Add<&Wrapping<T>> for &Wrapping<T> {
68    type Output = Wrapping<T>;
69
70    #[inline]
71    fn add(self, rhs: &Wrapping<T>) -> Self::Output {
72        Wrapping(self.0.wrapping_add(&rhs.0))
73    }
74}
75
76impl<T: WrappingSub> Sub<Self> for Wrapping<T> {
77    type Output = Wrapping<T>;
78
79    #[inline]
80    fn sub(self, rhs: Self) -> Self::Output {
81        Wrapping(self.0.wrapping_sub(&rhs.0))
82    }
83}
84
85impl<T: WrappingSub> Sub<&Self> for Wrapping<T> {
86    type Output = Wrapping<T>;
87
88    #[inline]
89    fn sub(self, rhs: &Self) -> Self::Output {
90        Wrapping(self.0.wrapping_sub(&rhs.0))
91    }
92}
93
94impl<T: WrappingSub> Sub<Wrapping<T>> for &Wrapping<T> {
95    type Output = Wrapping<T>;
96
97    #[inline]
98    fn sub(self, rhs: Wrapping<T>) -> Self::Output {
99        Wrapping(self.0.wrapping_sub(&rhs.0))
100    }
101}
102
103impl<T: WrappingSub> Sub<&Wrapping<T>> for &Wrapping<T> {
104    type Output = Wrapping<T>;
105
106    #[inline]
107    fn sub(self, rhs: &Wrapping<T>) -> Self::Output {
108        Wrapping(self.0.wrapping_sub(&rhs.0))
109    }
110}
111
112impl<T: WrappingMul> Mul<Self> for Wrapping<T> {
113    type Output = Wrapping<T>;
114
115    #[inline]
116    fn mul(self, rhs: Self) -> Self::Output {
117        Wrapping(self.0.wrapping_mul(&rhs.0))
118    }
119}
120
121impl<T: WrappingMul> Mul<&Self> for Wrapping<T> {
122    type Output = Wrapping<T>;
123
124    #[inline]
125    fn mul(self, rhs: &Self) -> Self::Output {
126        Wrapping(self.0.wrapping_mul(&rhs.0))
127    }
128}
129
130impl<T: WrappingMul> Mul<Wrapping<T>> for &Wrapping<T> {
131    type Output = Wrapping<T>;
132
133    #[inline]
134    fn mul(self, rhs: Wrapping<T>) -> Self::Output {
135        Wrapping(self.0.wrapping_mul(&rhs.0))
136    }
137}
138
139impl<T: WrappingMul> Mul<&Wrapping<T>> for &Wrapping<T> {
140    type Output = Wrapping<T>;
141
142    #[inline]
143    fn mul(self, rhs: &Wrapping<T>) -> Self::Output {
144        Wrapping(self.0.wrapping_mul(&rhs.0))
145    }
146}
147
148impl<T: WrappingNeg> Neg for Wrapping<T> {
149    type Output = Wrapping<T>;
150
151    #[inline]
152    fn neg(self) -> Self::Output {
153        Wrapping(self.0.wrapping_neg())
154    }
155}
156
157impl<T: WrappingNeg> Neg for &Wrapping<T> {
158    type Output = Wrapping<T>;
159
160    #[inline]
161    fn neg(self) -> Self::Output {
162        Wrapping(self.0.wrapping_neg())
163    }
164}
165
166impl<T: WrappingShl> Shl<u32> for Wrapping<T> {
167    type Output = Wrapping<T>;
168
169    #[inline]
170    fn shl(self, rhs: u32) -> Self::Output {
171        Wrapping(self.0.wrapping_shl(rhs))
172    }
173}
174
175impl<T: WrappingShl> Shl<u32> for &Wrapping<T> {
176    type Output = Wrapping<T>;
177
178    #[inline]
179    fn shl(self, rhs: u32) -> Self::Output {
180        Wrapping(self.0.wrapping_shl(rhs))
181    }
182}
183
184impl<T: WrappingShr> Shr<u32> for Wrapping<T> {
185    type Output = Wrapping<T>;
186
187    #[inline]
188    fn shr(self, rhs: u32) -> Self::Output {
189        Wrapping(self.0.wrapping_shr(rhs))
190    }
191}
192
193impl<T: WrappingShr> Shr<u32> for &Wrapping<T> {
194    type Output = Wrapping<T>;
195
196    #[inline]
197    fn shr(self, rhs: u32) -> Self::Output {
198        Wrapping(self.0.wrapping_shr(rhs))
199    }
200}
201
202impl<T: Integer> BitAnd for Wrapping<T> {
203    type Output = Self;
204
205    fn bitand(self, rhs: Self) -> Wrapping<T> {
206        Wrapping(self.0.bitand(&rhs.0))
207    }
208}
209
210impl<T: Integer> BitAnd<&Wrapping<T>> for Wrapping<T> {
211    type Output = Wrapping<T>;
212
213    fn bitand(self, rhs: &Wrapping<T>) -> Wrapping<T> {
214        Wrapping(self.0.bitand(&rhs.0))
215    }
216}
217
218impl<T: Integer> BitAnd<Wrapping<T>> for &Wrapping<T> {
219    type Output = Wrapping<T>;
220
221    fn bitand(self, rhs: Wrapping<T>) -> Wrapping<T> {
222        Wrapping(rhs.0.bitand(&self.0))
223    }
224}
225
226impl<T: Integer> BitAnd<&Wrapping<T>> for &Wrapping<T> {
227    type Output = Wrapping<T>;
228
229    fn bitand(self, rhs: &Wrapping<T>) -> Wrapping<T> {
230        Wrapping(self.0.clone().bitand(&rhs.0))
231    }
232}
233
234impl<T: Integer> BitAndAssign for Wrapping<T> {
235    fn bitand_assign(&mut self, other: Self) {
236        self.0 &= other.0;
237    }
238}
239
240impl<T: Integer> BitAndAssign<&Wrapping<T>> for Wrapping<T> {
241    fn bitand_assign(&mut self, other: &Self) {
242        self.0 &= &other.0;
243    }
244}
245
246impl<T: Integer> BitOr for Wrapping<T> {
247    type Output = Self;
248
249    fn bitor(self, rhs: Self) -> Wrapping<T> {
250        Wrapping(self.0.bitor(&rhs.0))
251    }
252}
253
254impl<T: Integer> BitOr<&Wrapping<T>> for Wrapping<T> {
255    type Output = Wrapping<T>;
256
257    fn bitor(self, rhs: &Wrapping<T>) -> Wrapping<T> {
258        Wrapping(self.0.bitor(&rhs.0))
259    }
260}
261
262impl<T: Integer> BitOr<Wrapping<T>> for &Wrapping<T> {
263    type Output = Wrapping<T>;
264
265    fn bitor(self, rhs: Wrapping<T>) -> Wrapping<T> {
266        Wrapping(rhs.0.bitor(&self.0))
267    }
268}
269
270impl<T: Integer> BitOr<&Wrapping<T>> for &Wrapping<T> {
271    type Output = Wrapping<T>;
272
273    fn bitor(self, rhs: &Wrapping<T>) -> Wrapping<T> {
274        Wrapping(self.0.clone().bitor(&rhs.0))
275    }
276}
277
278impl<T: Integer> BitOrAssign for Wrapping<T> {
279    fn bitor_assign(&mut self, other: Self) {
280        self.0 |= other.0;
281    }
282}
283
284impl<T: Integer> BitOrAssign<&Wrapping<T>> for Wrapping<T> {
285    fn bitor_assign(&mut self, other: &Self) {
286        self.0 |= &other.0;
287    }
288}
289
290impl<T: Integer> BitXor for Wrapping<T> {
291    type Output = Self;
292
293    fn bitxor(self, rhs: Self) -> Wrapping<T> {
294        Wrapping(self.0.bitxor(&rhs.0))
295    }
296}
297
298impl<T: Integer> BitXor<&Wrapping<T>> for Wrapping<T> {
299    type Output = Wrapping<T>;
300
301    fn bitxor(self, rhs: &Wrapping<T>) -> Wrapping<T> {
302        Wrapping(self.0.bitxor(&rhs.0))
303    }
304}
305
306impl<T: Integer> BitXor<Wrapping<T>> for &Wrapping<T> {
307    type Output = Wrapping<T>;
308
309    fn bitxor(self, rhs: Wrapping<T>) -> Wrapping<T> {
310        Wrapping(rhs.0.bitxor(&self.0))
311    }
312}
313
314impl<T: Integer> BitXor<&Wrapping<T>> for &Wrapping<T> {
315    type Output = Wrapping<T>;
316
317    fn bitxor(self, rhs: &Wrapping<T>) -> Wrapping<T> {
318        Wrapping(self.0.clone().bitxor(&rhs.0))
319    }
320}
321
322impl<T: Integer> BitXorAssign for Wrapping<T> {
323    fn bitxor_assign(&mut self, other: Self) {
324        self.0 ^= other.0;
325    }
326}
327
328impl<T: Integer> BitXorAssign<&Wrapping<T>> for Wrapping<T> {
329    fn bitxor_assign(&mut self, other: &Self) {
330        self.0 ^= &other.0;
331    }
332}
333
334impl<T: Integer> Not for Wrapping<T> {
335    type Output = Self;
336
337    fn not(self) -> <Self as Not>::Output {
338        Wrapping(self.0.not())
339    }
340}
341
342impl<T: Integer> Not for &Wrapping<T> {
343    type Output = Wrapping<T>;
344
345    fn not(self) -> <Self as Not>::Output {
346        Wrapping(self.0.clone().not())
347    }
348}
349
350impl<T> CtEq for Wrapping<T>
351where
352    T: CtEq,
353{
354    #[inline]
355    fn ct_eq(&self, other: &Self) -> Choice {
356        CtEq::ct_eq(&self.0, &other.0)
357    }
358}
359
360impl<T> CtSelect for Wrapping<T>
361where
362    T: CtSelect,
363{
364    #[inline]
365    fn ct_select(&self, other: &Self, choice: Choice) -> Self {
366        Self(self.0.ct_select(&other.0, choice))
367    }
368}
369
370impl<T: Zero> Zero for Wrapping<T> {
371    #[inline]
372    fn zero() -> Self {
373        Wrapping(T::zero())
374    }
375}
376
377impl<T: One> One for Wrapping<T> {
378    #[inline]
379    fn one() -> Self {
380        Wrapping(T::one())
381    }
382}
383
384impl<T: num_traits::Zero + WrappingAdd> num_traits::Zero for Wrapping<T> {
385    #[inline]
386    fn zero() -> Self {
387        Wrapping(T::zero())
388    }
389
390    #[inline]
391    fn is_zero(&self) -> bool {
392        self.0.is_zero()
393    }
394}
395
396impl<T: num_traits::One + WrappingMul + PartialEq> num_traits::One for Wrapping<T> {
397    #[inline]
398    fn one() -> Self {
399        Wrapping(T::one())
400    }
401
402    #[inline]
403    fn is_one(&self) -> bool {
404        self.0.is_one()
405    }
406}
407
408impl<T: fmt::Display> fmt::Display for Wrapping<T> {
409    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
410        self.0.fmt(f)
411    }
412}
413
414impl<T: fmt::Binary> fmt::Binary for Wrapping<T> {
415    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
416        self.0.fmt(f)
417    }
418}
419
420impl<T: fmt::Octal> fmt::Octal for Wrapping<T> {
421    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
422        self.0.fmt(f)
423    }
424}
425
426impl<T: fmt::LowerHex> fmt::LowerHex for Wrapping<T> {
427    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
428        self.0.fmt(f)
429    }
430}
431
432impl<T: fmt::UpperHex> fmt::UpperHex for Wrapping<T> {
433    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
434        self.0.fmt(f)
435    }
436}
437
438#[cfg(feature = "rand_core")]
439impl<T: Random> Random for Wrapping<T> {
440    fn try_random_from_rng<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
441        Ok(Wrapping(Random::try_random_from_rng(rng)?))
442    }
443}
444
445#[cfg(feature = "serde")]
446impl<'de, T: Deserialize<'de>> Deserialize<'de> for Wrapping<T> {
447    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
448    where
449        D: Deserializer<'de>,
450    {
451        Ok(Self(T::deserialize(deserializer)?))
452    }
453}
454
455#[cfg(feature = "serde")]
456impl<T: Serialize> Serialize for Wrapping<T> {
457    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
458    where
459        S: Serializer,
460    {
461        self.0.serialize(serializer)
462    }
463}
464
465#[cfg(feature = "subtle")]
466impl<T> subtle::ConditionallySelectable for Wrapping<T>
467where
468    T: Copy,
469    Self: CtSelect,
470{
471    #[inline]
472    fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
473        a.ct_select(b, choice.into())
474    }
475}
476
477#[cfg(feature = "subtle")]
478impl<T> subtle::ConstantTimeEq for Wrapping<T>
479where
480    Self: CtEq,
481{
482    #[inline]
483    fn ct_eq(&self, other: &Self) -> subtle::Choice {
484        CtEq::ct_eq(self, other).into()
485    }
486}
487
488#[cfg(test)]
489#[allow(clippy::op_ref)]
490mod tests {
491    use super::Wrapping;
492    use crate::{
493        Choice, CtEq, CtSelect, Limb, WrappingAdd, WrappingMul, WrappingNeg, WrappingShl,
494        WrappingShr, WrappingSub,
495    };
496
497    // FIXME Could use itertools combinations or an equivalent iterator
498    const INPUTS: &[(Limb, Limb)] = &[
499        (Limb::ZERO, Limb::ZERO),
500        (Limb::ZERO, Limb::ONE),
501        (Limb::ZERO, Limb::MAX),
502        (Limb::ONE, Limb::ZERO),
503        (Limb::ONE, Limb::ONE),
504        (Limb::ONE, Limb::MAX),
505        (Limb::MAX, Limb::ZERO),
506        (Limb::MAX, Limb::ONE),
507        (Limb::MAX, Limb::MAX),
508    ];
509
510    #[test]
511    fn wrapping_new() {
512        assert_eq!(Wrapping::<Limb>::default().0, Limb::default());
513        assert_eq!(<Wrapping<Limb> as crate::Zero>::zero().0, Limb::ZERO);
514        assert_eq!(<Wrapping<Limb> as crate::One>::one().0, Limb::ONE);
515        assert_eq!(<Wrapping<Limb> as num_traits::Zero>::zero().0, Limb::ZERO);
516        assert_eq!(<Wrapping<Limb> as num_traits::One>::one().0, Limb::ONE);
517    }
518
519    #[test]
520    #[cfg(feature = "alloc")]
521    fn wrapping_format() {
522        for a in [Limb::ZERO, Limb::ONE, Limb::MAX] {
523            assert_eq!(format!("{}", Wrapping(a)), format!("{}", a));
524            assert_eq!(format!("{:?}", Wrapping(a)), format!("Wrapping({:?})", a));
525            assert_eq!(format!("{:b}", Wrapping(a)), format!("{:b}", a));
526            assert_eq!(format!("{:o}", Wrapping(a)), format!("{:o}", a));
527            assert_eq!(format!("{:x}", Wrapping(a)), format!("{:x}", a));
528            assert_eq!(format!("{:X}", Wrapping(a)), format!("{:X}", a));
529        }
530    }
531
532    #[test]
533    fn wrapping_eq_select() {
534        let pairs: &[(Limb, Limb, bool)] = &[
535            (Limb::ZERO, Limb::ZERO, true),
536            (Limb::ZERO, Limb::ONE, false),
537            (Limb::ONE, Limb::ZERO, false),
538            (Limb::ONE, Limb::ONE, true),
539        ];
540
541        for (a, b, eq) in pairs {
542            assert_eq!(a.ct_eq(b).to_bool(), *eq);
543            assert!(a.ct_select(b, Choice::FALSE).ct_eq(a).to_bool());
544            assert!(a.ct_select(b, Choice::TRUE).ct_eq(b).to_bool());
545            #[cfg(feature = "subtle")]
546            assert_eq!(bool::from(subtle::ConstantTimeEq::ct_eq(a, b)), *eq);
547            #[cfg(feature = "subtle")]
548            assert!(
549                subtle::ConditionallySelectable::conditional_select(
550                    a,
551                    b,
552                    subtle::Choice::from(0u8)
553                )
554                .ct_eq(a)
555                .to_bool()
556            );
557            #[cfg(feature = "subtle")]
558            assert!(
559                subtle::ConditionallySelectable::conditional_select(
560                    a,
561                    b,
562                    subtle::Choice::from(1u8)
563                )
564                .ct_eq(b)
565                .to_bool()
566            );
567        }
568    }
569
570    #[test]
571    fn wrapping_add() {
572        for (a, b) in INPUTS {
573            let expect = WrappingAdd::wrapping_add(a, b);
574            assert_eq!((Wrapping(*a) + Wrapping(*b)).0, expect);
575            assert_eq!((&Wrapping(*a) + Wrapping(*b)).0, expect);
576            assert_eq!((Wrapping(*a) + &Wrapping(*b)).0, expect);
577            assert_eq!((&Wrapping(*a) + &Wrapping(*b)).0, expect);
578        }
579    }
580
581    #[test]
582    fn wrapping_sub() {
583        for (a, b) in INPUTS {
584            let expect = WrappingSub::wrapping_sub(a, b);
585            assert_eq!((Wrapping(*a) - Wrapping(*b)).0, expect);
586            assert_eq!((&Wrapping(*a) - Wrapping(*b)).0, expect);
587            assert_eq!((Wrapping(*a) - &Wrapping(*b)).0, expect);
588            assert_eq!((&Wrapping(*a) - &Wrapping(*b)).0, expect);
589        }
590    }
591
592    #[test]
593    fn wrapping_mul() {
594        for (a, b) in INPUTS {
595            let expect = WrappingMul::wrapping_mul(a, b);
596            assert_eq!((Wrapping(*a) * Wrapping(*b)).0, expect);
597            assert_eq!((&Wrapping(*a) * Wrapping(*b)).0, expect);
598            assert_eq!((Wrapping(*a) * &Wrapping(*b)).0, expect);
599            assert_eq!((&Wrapping(*a) * &Wrapping(*b)).0, expect);
600        }
601    }
602
603    #[test]
604    fn wrapping_neg() {
605        for a in [Limb::ZERO, Limb::ONE, Limb::MAX] {
606            let expect = WrappingNeg::wrapping_neg(&a);
607            assert_eq!((-Wrapping(a)).0, expect);
608        }
609    }
610
611    #[test]
612    fn wrapping_shift() {
613        for a in [Limb::ZERO, Limb::ONE, Limb::MAX] {
614            assert_eq!((Wrapping(a) << 1).0, WrappingShl::wrapping_shl(&a, 1));
615            assert_eq!((&Wrapping(a) << 2).0, WrappingShl::wrapping_shl(&a, 2));
616            assert_eq!((Wrapping(a) >> 1).0, WrappingShr::wrapping_shr(&a, 1));
617            assert_eq!((&Wrapping(a) >> 2).0, WrappingShr::wrapping_shr(&a, 2));
618        }
619    }
620
621    #[test]
622    fn wrapping_bitand() {
623        for (a, b) in INPUTS {
624            let expect = *a & b;
625            assert_eq!((Wrapping(*a) & Wrapping(*b)).0, expect);
626            assert_eq!((&Wrapping(*a) & Wrapping(*b)).0, expect);
627            assert_eq!((Wrapping(*a) & &Wrapping(*b)).0, expect);
628            assert_eq!((&Wrapping(*a) & &Wrapping(*b)).0, expect);
629            let mut c = Wrapping(*a);
630            c &= Wrapping(*b);
631            assert_eq!(c.0, expect);
632            let mut c = Wrapping(*a);
633            c &= &Wrapping(*b);
634            assert_eq!(c.0, expect);
635        }
636    }
637
638    #[test]
639    fn wrapping_bitor() {
640        for (a, b) in INPUTS {
641            let expect = *a | b;
642            assert_eq!((Wrapping(*a) | Wrapping(*b)).0, expect);
643            assert_eq!((&Wrapping(*a) | Wrapping(*b)).0, expect);
644            assert_eq!((Wrapping(*a) | &Wrapping(*b)).0, expect);
645            assert_eq!((&Wrapping(*a) | &Wrapping(*b)).0, expect);
646            let mut c = Wrapping(*a);
647            c |= Wrapping(*b);
648            assert_eq!(c.0, expect);
649            let mut c = Wrapping(*a);
650            c |= &Wrapping(*b);
651            assert_eq!(c.0, expect);
652        }
653    }
654
655    #[test]
656    fn wrapping_bitxor() {
657        for (a, b) in INPUTS {
658            let expect = *a ^ b;
659            assert_eq!((Wrapping(*a) ^ Wrapping(*b)).0, expect);
660            assert_eq!((&Wrapping(*a) ^ Wrapping(*b)).0, expect);
661            assert_eq!((Wrapping(*a) ^ &Wrapping(*b)).0, expect);
662            assert_eq!((&Wrapping(*a) ^ &Wrapping(*b)).0, expect);
663            let mut c = Wrapping(*a);
664            c ^= Wrapping(*b);
665            assert_eq!(c.0, expect);
666            let mut c = Wrapping(*a);
667            c ^= &Wrapping(*b);
668            assert_eq!(c.0, expect);
669        }
670    }
671
672    #[test]
673    fn wrapping_bitnot() {
674        for a in [Limb::ZERO, Limb::ONE, Limb::MAX] {
675            let expect = !a;
676            assert_eq!((!Wrapping(a)).0, expect);
677            assert_eq!((!(&Wrapping(a))).0, expect);
678        }
679    }
680}
crypto_bigint/wrapping.rs

crypto_bigint/
wrapping.rs
