crypto_bigint/uint/
div.rs

1//! [`Uint`] division operations.
2
3use super::div_limb::Reciprocal;
4use crate::{
5    CheckedDiv, CtOption, Div, DivAssign, DivRemLimb, DivVartime, Limb, NonZero, Rem, RemAssign,
6    RemLimb, RemMixed, ToUnsigned, Uint, UintRef, Unsigned, Wrapping,
7};
8
9impl<const LIMBS: usize> Uint<LIMBS> {
10    /// Computes `self / rhs` using a pre-made reciprocal, returning the quotient
11    /// and remainder.
12    #[must_use]
13    pub const fn div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
14        let mut quo = *self;
15        let rem = quo
16            .as_mut_uint_ref()
17            .div_rem_limb_with_reciprocal(reciprocal);
18        (quo, rem)
19    }
20
21    /// Computes `self / rhs`, returning the quotient and remainder.
22    #[must_use]
23    pub const fn div_rem_limb(&self, rhs: NonZero<Limb>) -> (Self, Limb) {
24        let mut quo = *self;
25        let rem = quo.as_mut_uint_ref().div_rem_limb(rhs);
26        (quo, rem)
27    }
28
29    /// Computes `self % rhs` using a pre-made reciprocal.
30    #[must_use]
31    pub const fn rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> Limb {
32        self.as_uint_ref()
33            .rem_limb_with_reciprocal(reciprocal, Limb::ZERO)
34    }
35
36    /// Computes `self % rhs` for a `Limb`-sized divisor.
37    #[must_use]
38    pub const fn rem_limb(&self, rhs: NonZero<Limb>) -> Limb {
39        self.as_uint_ref().rem_limb(rhs)
40    }
41
42    /// Computes `self` / `rhs`, returning the quotient and the remainder.
43    ///
44    /// This function is constant-time with respect to both `self` and `rhs`.
45    #[must_use]
46    pub const fn div_rem<const RHS_LIMBS: usize>(
47        &self,
48        rhs: &NonZero<Uint<RHS_LIMBS>>,
49    ) -> (Self, Uint<RHS_LIMBS>) {
50        let (mut x, mut y) = (*self, *rhs.as_ref());
51        UintRef::div_rem(x.as_mut_uint_ref(), y.as_mut_uint_ref());
52        (x, y)
53    }
54
55    /// Computes `self` / `rhs`, returning the quotient and the remainder.
56    ///
57    /// This is variable-time only with respect to `rhs`.
58    ///
59    /// When used with a fixed `rhs`, this function is constant-time with respect
60    /// to `self`.
61    #[inline]
62    #[must_use]
63    pub const fn div_rem_vartime<const RHS_LIMBS: usize>(
64        &self,
65        rhs: &NonZero<Uint<RHS_LIMBS>>,
66    ) -> (Self, Uint<RHS_LIMBS>) {
67        let (mut x, mut y) = (*self, *rhs.as_ref());
68        UintRef::div_rem_vartime(x.as_mut_uint_ref(), y.as_mut_uint_ref());
69        (x, y)
70    }
71
72    /// Computes self / rhs, assigning the quotient to `self` and returning the remainder.
73    #[must_use]
74    pub(crate) fn div_rem_assign<Rhs: Unsigned>(&mut self, rhs: NonZero<Rhs>) -> Rhs {
75        let mut rem = rhs.get();
76        self.as_mut_uint_ref().div_rem(rem.as_mut_uint_ref());
77        rem
78    }
79
80    /// Computes `self` % `rhs`.
81    #[must_use]
82    pub const fn rem<const RHS_LIMBS: usize>(
83        &self,
84        rhs: &NonZero<Uint<RHS_LIMBS>>,
85    ) -> Uint<RHS_LIMBS> {
86        let (mut x, mut y) = (*self, *rhs.as_ref());
87        UintRef::div_rem(x.as_mut_uint_ref(), y.as_mut_uint_ref());
88        y
89    }
90
91    /// Computes `self` % `rhs` in variable-time with respect to `rhs`.
92    ///
93    /// When used with a fixed `rhs`, this function is constant-time with respect
94    /// to `self`.
95    #[inline]
96    #[must_use]
97    pub const fn rem_vartime<const RHS_LIMBS: usize>(
98        &self,
99        rhs: &NonZero<Uint<RHS_LIMBS>>,
100    ) -> Uint<RHS_LIMBS> {
101        let (mut x, mut y) = (*self, *rhs.as_ref());
102        UintRef::div_rem_vartime(x.as_mut_uint_ref(), y.as_mut_uint_ref());
103        y
104    }
105
106    /// Computes `self` % `rhs` for a double-width `Uint`.
107    #[inline]
108    #[must_use]
109    pub const fn rem_wide(mut lower_upper: (Self, Self), rhs: &NonZero<Self>) -> Self {
110        let mut y = *rhs.as_ref();
111        UintRef::rem_wide(
112            (
113                lower_upper.0.as_mut_uint_ref(),
114                lower_upper.1.as_mut_uint_ref(),
115            ),
116            y.as_mut_uint_ref(),
117        );
118        y
119    }
120
121    /// Computes `self` % `rhs`.
122    ///
123    /// This is variable-time only with respect to `rhs`.
124    ///
125    /// When used with a fixed `rhs`, this function is constant-time with respect
126    /// to `self`.
127    #[inline]
128    #[must_use]
129    pub const fn rem_wide_vartime(mut lower_upper: (Self, Self), rhs: &NonZero<Self>) -> Self {
130        let mut y = *rhs.as_ref();
131        UintRef::rem_wide_vartime(
132            (
133                lower_upper.0.as_mut_uint_ref(),
134                lower_upper.1.as_mut_uint_ref(),
135            ),
136            y.as_mut_uint_ref(),
137        );
138        y
139    }
140
141    /// Computes `self` % 2^k. Faster than reduce since its a power of 2.
142    /// Limited to 2^16-1 since Uint doesn't support higher.
143    ///
144    /// ### Usage:
145    /// ```
146    /// use crypto_bigint::{U448, Limb};
147    ///
148    /// let a = U448::from(10_u64);
149    /// let k = 3; // 2^3 = 8
150    /// let remainder = a.rem2k_vartime(k);
151    ///
152    /// // As 10 % 8 = 2
153    /// assert_eq!(remainder, U448::from(2_u64));
154    /// ```
155    #[must_use]
156    pub const fn rem2k_vartime(&self, k: u32) -> Self {
157        self.restrict_bits(k)
158    }
159
160    /// Wrapped division is just normal division i.e. `self` / `rhs`.
161    ///
162    /// There’s no way wrapping could ever happen.
163    /// This function exists, so that all operations are accounted for in the wrapping operations.
164    #[must_use]
165    pub const fn wrapping_div(&self, rhs: &NonZero<Self>) -> Self {
166        self.div_rem(rhs).0
167    }
168
169    /// Wrapped division is just normal division i.e. `self` / `rhs`.
170    ///
171    /// There’s no way wrapping could ever happen.
172    /// This function exists, so that all operations are accounted for in the wrapping operations.
173    #[must_use]
174    pub const fn wrapping_div_vartime<const RHS: usize>(&self, rhs: &NonZero<Uint<RHS>>) -> Self {
175        self.div_rem_vartime(rhs).0
176    }
177
178    /// Perform checked division, returning a [`CtOption`] which `is_some`
179    /// only if the rhs != 0.
180    ///
181    /// ### Usage:
182    /// ```
183    /// use crypto_bigint::{U448, NonZero};
184    ///
185    /// let a = U448::from(8_u64);
186    /// let result = NonZero::new(U448::from(4_u64))
187    ///     .map(|b| a.div_rem(&b))
188    ///     .expect("Division by zero");
189    ///
190    /// assert_eq!(result.0, U448::from(2_u64));
191    ///
192    /// // Check division by zero
193    /// let zero = U448::from(0_u64);
194    /// assert!(a.checked_div(&zero).is_none().to_bool(), "should be None for division by zero");
195    /// ```
196    #[must_use]
197    pub fn checked_div<const RHS_LIMBS: usize>(&self, rhs: &Uint<RHS_LIMBS>) -> CtOption<Self> {
198        NonZero::new(*rhs).map(|rhs| self.div_rem(&rhs).0)
199    }
200
201    /// This function exists, so that all operations are accounted for in the wrapping operations.
202    ///
203    /// # Panics
204    /// - if `rhs == 0`.
205    ///
206    /// ### Usage:
207    /// ```
208    /// use crypto_bigint::U448;
209    ///
210    /// let a = U448::from(10_u64);
211    /// let b = U448::from(3_u64);
212    /// let remainder = a.wrapping_rem_vartime(&b);
213    ///
214    /// assert_eq!(remainder, U448::from(1_u64));
215    /// ```
216    #[must_use]
217    pub const fn wrapping_rem_vartime(&self, rhs: &Self) -> Self {
218        let nz_rhs = rhs.to_nz().expect_copied("non-zero divisor");
219        self.rem_vartime(&nz_rhs)
220    }
221
222    /// Perform checked reduction, returning a [`CtOption`] which `is_some`
223    /// only if the rhs != 0
224    ///
225    /// ### Usage:
226    /// ```
227    /// use crypto_bigint::{U448, NonZero};
228    ///
229    /// let a = U448::from(10_u64);
230    /// let remainder_option = NonZero::new(U448::from(3_u64))
231    ///     .map(|b| a.rem(&b));
232    ///
233    /// assert!(bool::from(remainder_option.is_some()));
234    ///
235    /// // Check reduction by zero
236    /// let zero = U448::from(0_u64);
237    ///
238    /// assert!(a.checked_rem(&zero).is_none().to_bool(), "should be None for reduction by zero");
239    /// ```
240    #[must_use]
241    pub fn checked_rem<const RHS_LIMBS: usize>(
242        &self,
243        rhs: &Uint<RHS_LIMBS>,
244    ) -> CtOption<Uint<RHS_LIMBS>> {
245        NonZero::new(*rhs).map(|rhs| self.rem(&rhs))
246    }
247}
248
249impl<const LIMBS: usize, const RHS_LIMBS: usize> CheckedDiv<Uint<RHS_LIMBS>> for Uint<LIMBS> {
250    fn checked_div(&self, rhs: &Uint<RHS_LIMBS>) -> CtOption<Self> {
251        self.checked_div(rhs)
252    }
253}
254
255impl<const LIMBS: usize, Rhs: Unsigned> Div<Rhs> for &Uint<LIMBS> {
256    type Output = Uint<LIMBS>;
257
258    #[inline]
259    fn div(self, rhs: Rhs) -> Self::Output {
260        *self / rhs
261    }
262}
263
264impl<const LIMBS: usize, Rhs: Unsigned> Div<Rhs> for Uint<LIMBS> {
265    type Output = Uint<LIMBS>;
266
267    #[inline]
268    fn div(self, rhs: Rhs) -> Self::Output {
269        self / NonZero::new(rhs).expect("attempt to divide with a divisor of zero")
270    }
271}
272
273impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for &Uint<LIMBS> {
274    type Output = Uint<LIMBS>;
275
276    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
277        let mut quo = *self;
278        let _rem = quo.div_rem_assign(rhs.to_unsigned());
279        quo
280    }
281}
282
283impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for Uint<LIMBS> {
284    type Output = Self;
285
286    fn div(mut self, rhs: &NonZero<Rhs>) -> Self::Output {
287        let _rem = self.div_rem_assign(rhs.to_unsigned());
288        self
289    }
290}
291
292impl<const LIMBS: usize, Rhs: Unsigned> Div<NonZero<Rhs>> for &Uint<LIMBS> {
293    type Output = Uint<LIMBS>;
294
295    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
296        let mut quo = *self;
297        let _rem = quo.div_rem_assign(rhs);
298        quo
299    }
300}
301
302impl<const LIMBS: usize, Rhs: Unsigned> Div<NonZero<Rhs>> for Uint<LIMBS> {
303    type Output = Self;
304
305    fn div(mut self, rhs: NonZero<Rhs>) -> Self::Output {
306        let _rem = self.div_rem_assign(rhs);
307        self
308    }
309}
310
311impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> DivAssign<&NonZero<Rhs>> for Uint<LIMBS> {
312    fn div_assign(&mut self, rhs: &NonZero<Rhs>) {
313        let _rem = self.div_rem_assign(rhs.to_unsigned());
314    }
315}
316
317impl<const LIMBS: usize, Rhs: Unsigned> DivAssign<NonZero<Rhs>> for Uint<LIMBS> {
318    fn div_assign(&mut self, rhs: NonZero<Rhs>) {
319        let _rem = self.div_rem_assign(rhs);
320    }
321}
322
323impl<const LIMBS: usize, Rhs: Unsigned> Div<NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
324    type Output = Self;
325
326    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
327        Wrapping(self.0 / rhs)
328    }
329}
330
331impl<const LIMBS: usize, Rhs: Unsigned> Div<NonZero<Rhs>> for &Wrapping<Uint<LIMBS>> {
332    type Output = Wrapping<Uint<LIMBS>>;
333
334    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
335        Wrapping(self.0 / rhs)
336    }
337}
338
339impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for &Wrapping<Uint<LIMBS>> {
340    type Output = Wrapping<Uint<LIMBS>>;
341
342    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
343        Wrapping(self.0 / rhs)
344    }
345}
346
347impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
348    type Output = Self;
349
350    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
351        Wrapping(self.0 / rhs)
352    }
353}
354
355impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> DivAssign<&NonZero<Rhs>>
356    for Wrapping<Uint<LIMBS>>
357{
358    fn div_assign(&mut self, rhs: &NonZero<Rhs>) {
359        self.0 /= rhs;
360    }
361}
362
363impl<const LIMBS: usize, Rhs: Unsigned> DivAssign<NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
364    fn div_assign(&mut self, rhs: NonZero<Rhs>) {
365        self.0 /= rhs;
366    }
367}
368
369impl<const LIMBS: usize> DivVartime for Uint<LIMBS> {
370    fn div_vartime(&self, rhs: &NonZero<Uint<LIMBS>>) -> Self {
371        self.div_rem_vartime(rhs).0
372    }
373}
374
375impl<const LIMBS: usize, Rhs: Unsigned> Rem<Rhs> for &Uint<LIMBS> {
376    type Output = Rhs;
377
378    #[inline]
379    fn rem(self, rhs: Rhs) -> Self::Output {
380        *self % rhs
381    }
382}
383
384impl<const LIMBS: usize, Rhs: Unsigned> Rem<Rhs> for Uint<LIMBS> {
385    type Output = Rhs;
386
387    #[inline]
388    fn rem(self, rhs: Rhs) -> Self::Output {
389        self % NonZero::new(rhs).expect("attempt to calculate the remainder with a divisor of zero")
390    }
391}
392
393impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for &Uint<LIMBS> {
394    type Output = Rhs::Unsigned;
395
396    #[inline]
397    fn rem(self, rhs: &NonZero<Rhs>) -> Self::Output {
398        (*self).rem(rhs)
399    }
400}
401
402impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for Uint<LIMBS> {
403    type Output = Rhs::Unsigned;
404
405    #[inline]
406    fn rem(mut self, rhs: &NonZero<Rhs>) -> Self::Output {
407        self.div_rem_assign(rhs.to_unsigned())
408    }
409}
410
411impl<const LIMBS: usize, Rhs: Unsigned> Rem<NonZero<Rhs>> for &Uint<LIMBS> {
412    type Output = Rhs;
413
414    #[inline]
415    fn rem(self, rhs: NonZero<Rhs>) -> Self::Output {
416        (*self).rem(rhs)
417    }
418}
419
420impl<const LIMBS: usize, Rhs: Unsigned> Rem<NonZero<Rhs>> for Uint<LIMBS> {
421    type Output = Rhs;
422
423    #[inline]
424    fn rem(mut self, rhs: NonZero<Rhs>) -> Self::Output {
425        self.div_rem_assign(rhs)
426    }
427}
428
429impl<const LIMBS: usize, Rhs: Unsigned> Rem<NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
430    type Output = Wrapping<Rhs>;
431
432    fn rem(self, rhs: NonZero<Rhs>) -> Self::Output {
433        Wrapping(self.0 % rhs)
434    }
435}
436
437impl<const LIMBS: usize, Rhs: Unsigned> Rem<NonZero<Rhs>> for &Wrapping<Uint<LIMBS>> {
438    type Output = Wrapping<Rhs>;
439
440    fn rem(self, rhs: NonZero<Rhs>) -> Self::Output {
441        *self % rhs
442    }
443}
444
445impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for &Wrapping<Uint<LIMBS>> {
446    type Output = Wrapping<Rhs::Unsigned>;
447
448    fn rem(self, rhs: &NonZero<Rhs>) -> Self::Output {
449        *self % rhs.to_unsigned()
450    }
451}
452
453impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
454    type Output = Wrapping<Rhs::Unsigned>;
455
456    fn rem(self, rhs: &NonZero<Rhs>) -> Self::Output {
457        self % rhs.to_unsigned()
458    }
459}
460
461impl<const LIMBS: usize, Rhs: Unsigned> RemAssign<NonZero<Rhs>> for Uint<LIMBS> {
462    fn rem_assign(&mut self, rhs: NonZero<Rhs>) {
463        let rem = *self % rhs;
464        *self = rem.as_uint_ref().to_uint_resize();
465    }
466}
467
468impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> RemAssign<&NonZero<Rhs>> for Uint<LIMBS> {
469    fn rem_assign(&mut self, rhs: &NonZero<Rhs>) {
470        *self %= rhs.to_unsigned();
471    }
472}
473
474impl<const LIMBS: usize, Rhs: Unsigned> RemAssign<NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
475    fn rem_assign(&mut self, rhs: NonZero<Rhs>) {
476        *self %= &rhs;
477    }
478}
479
480impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> RemAssign<&NonZero<Rhs>>
481    for Wrapping<Uint<LIMBS>>
482{
483    fn rem_assign(&mut self, rhs: &NonZero<Rhs>) {
484        self.0 %= rhs;
485    }
486}
487
488impl<const LIMBS: usize> DivRemLimb for Uint<LIMBS> {
489    fn div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
490        Self::div_rem_limb_with_reciprocal(self, reciprocal)
491    }
492}
493
494impl<const LIMBS: usize> RemLimb for Uint<LIMBS> {
495    fn rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> Limb {
496        Self::rem_limb_with_reciprocal(self, reciprocal)
497    }
498}
499
500impl<const LIMBS: usize, Rhs: Unsigned> RemMixed<Rhs> for Uint<LIMBS> {
501    fn rem_mixed(&self, reductor: &NonZero<Rhs>) -> Rhs {
502        let (mut quo, mut rem) = (*self, reductor.as_ref().clone());
503        quo.as_mut_uint_ref().div_rem(rem.as_mut_uint_ref());
504        rem
505    }
506}
507
508#[cfg(test)]
509#[allow(clippy::integer_division_remainder_used, reason = "test")]
510mod tests {
511    use crate::{
512        CtAssign, DivVartime, Limb, NonZero, One, RemMixed, U64, U128, U256, U512, U896, U1024,
513        Uint, Word, Wrapping, Zero,
514    };
515
516    #[cfg(feature = "rand_core")]
517    use {crate::Random, chacha20::ChaCha8Rng, rand_core::Rng, rand_core::SeedableRng};
518
519    #[test]
520    fn div_word() {
521        for (n, d, e, ee) in &[
522            (200u64, 2u64, 100u64, 0),
523            (100u64, 25u64, 4u64, 0),
524            (100u64, 10u64, 10u64, 0),
525            (1024u64, 8u64, 128u64, 0),
526            (27u64, 13u64, 2u64, 1u64),
527            (26u64, 13u64, 2u64, 0u64),
528            (14u64, 13u64, 1u64, 1u64),
529            (13u64, 13u64, 1u64, 0u64),
530            (12u64, 13u64, 0u64, 12u64),
531            (1u64, 13u64, 0u64, 1u64),
532        ] {
533            let lhs = U256::from(*n);
534            let rhs = NonZero::new(U256::from(*d)).unwrap();
535            let (q, r) = lhs.div_rem(&rhs);
536            assert_eq!(U256::from(*e), q);
537            assert_eq!(U256::from(*ee), r);
538            let (q, r) = lhs.div_rem_vartime(&rhs);
539            assert_eq!(U256::from(*e), q);
540            assert_eq!(U256::from(*ee), r);
541        }
542    }
543
544    #[cfg(feature = "rand_core")]
545    #[test]
546    fn div() {
547        let mut rng = ChaCha8Rng::from_seed([7u8; 32]);
548        for _ in 0..25 {
549            let num = U256::random_from_rng(&mut rng)
550                .overflowing_shr_vartime(128)
551                .unwrap();
552            let den = NonZero::new(
553                U256::random_from_rng(&mut rng)
554                    .overflowing_shr_vartime(128)
555                    .unwrap(),
556            )
557            .unwrap();
558            let n = num.checked_mul(den.as_ref());
559            if n.is_some().into() {
560                let n = n.unwrap();
561                let (q, _) = n.div_rem(&den);
562                assert_eq!(q, num);
563                let (q, _) = n.div_rem_vartime(&den);
564                assert_eq!(q, num);
565            }
566        }
567    }
568
569    #[test]
570    fn div_max() {
571        let mut a = U256::ZERO;
572        let mut b = U256::ZERO;
573        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
574        let q = a.wrapping_div(&NonZero::new(b).unwrap());
575        assert_eq!(q, Uint::ZERO);
576        a.limbs[a.limbs.len() - 1] = Limb(1 << (Limb::HI_BIT - 7));
577        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (Limb::HI_BIT - 7));
578        let b = NonZero::new(b).unwrap();
579        let q = a.wrapping_div(&b);
580        assert_eq!(q, Uint::ZERO);
581    }
582
583    #[test]
584    fn div_one() {
585        let (q, r) = U256::from(10u8).div_rem(&NonZero::new(U256::ONE).unwrap());
586        assert_eq!(q, U256::from(10u8));
587        assert_eq!(r, U256::ZERO);
588        let (q, r) = U256::from(10u8).div_rem_vartime(&NonZero::new(U256::ONE).unwrap());
589        assert_eq!(q, U256::from(10u8));
590        assert_eq!(r, U256::ZERO);
591    }
592
593    #[test]
594    fn div_edge() {
595        let lo = U128::from_be_hex("00000000000000000000000000000001");
596        let hi = U128::from_be_hex("00000000000000000000000000000001");
597        let y = U128::from_be_hex("00000000000000010000000000000001");
598        let x = U256::from((lo, hi));
599        let expect = (U64::MAX.resize::<{ U256::LIMBS }>(), U256::from(2u64));
600
601        let (q1, r1) = Uint::div_rem(&x, &NonZero::new(y.resize()).unwrap());
602        assert_eq!((q1, r1), expect);
603        let (q2, r2) = Uint::div_rem_vartime(&x, &NonZero::new(y).unwrap());
604        assert_eq!((q2, r2.resize()), expect);
605        let r3 = Uint::rem(&x, &NonZero::new(y.resize()).unwrap());
606        assert_eq!(r3, expect.1);
607        let r4 = Uint::rem_vartime(&x, &NonZero::new(y.resize()).unwrap());
608        assert_eq!(r4, expect.1);
609        let r5 = Uint::rem_wide((lo, hi), &NonZero::new(y).unwrap());
610        assert_eq!(r5.resize(), expect.1);
611        let r6 = Uint::rem_wide_vartime((lo, hi), &NonZero::new(y).unwrap());
612        assert_eq!(r6.resize(), expect.1);
613    }
614
615    #[test]
616    fn div_rem_larger_denominator() {
617        // 1 = len(x) < len(y) and x < y
618        let x = U64::from_be_hex("8000000000000000");
619        let y = U128::from_be_hex("00000000000000010000000000000000")
620            .to_nz()
621            .unwrap();
622        let (quo, rem) = x.div_rem(&y);
623        assert_eq!(quo, Uint::ZERO);
624        assert_eq!(rem, x.resize());
625
626        // 1 = len(x) < len(y) and x > y
627        let x = U64::from_be_hex("8000000000000000");
628        let y = U128::from_be_hex("00000000000000000000000000001000")
629            .to_nz()
630            .unwrap();
631        let (quo, rem) = x.div_rem(&y);
632        assert_eq!(quo, U64::from_be_hex("0008000000000000"));
633        assert_eq!(rem, U128::ZERO);
634
635        // 2 = len(x) < len(y) and x < y
636        let x = U128::from_be_hex("80000000000000008000000000000000");
637        let y =
638            U256::from_be_hex("0000000000000001000000000000000000000000000000010000000000000000")
639                .to_nz()
640                .unwrap();
641        let (quo, rem) = x.div_rem(&y);
642        assert_eq!(quo, U128::ZERO);
643        assert_eq!(rem, x.resize());
644
645        // 2 = len(x) < len(y) and x > y
646        let x = U128::from_be_hex("80000000000000008000000000000000");
647        let y =
648            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000000110000")
649                .to_nz()
650                .unwrap();
651        let (quo, rem) = x.div_rem(&y);
652        assert_eq!(quo, U128::from_be_hex("000007878787878787878f0f0f0f0f0f"));
653        assert_eq!(
654            rem,
655            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000000010000",)
656        );
657    }
658
659    #[test]
660    fn div_rem_larger_numerator() {
661        let denom = U128::from_be_hex("AAAA0000FFFF11117777333344449999");
662        let (full_q, full_r) =
663            U1024::MAX.div_rem(&denom.resize::<{ U1024::LIMBS }>().to_nz().unwrap());
664
665        let (q, r) = U1024::MAX.div_rem(&denom.to_nz().unwrap());
666        assert_eq!(full_q, q);
667        assert_eq!(full_r.resize(), r);
668    }
669
670    #[allow(clippy::op_ref)]
671    #[test]
672    fn div_trait() {
673        let a = U256::from(10u64);
674        let b = NonZero::new(U256::from(2u64)).unwrap();
675        let c = U256::from(5u64);
676
677        assert_eq!(a / b, c);
678        assert_eq!(a / &b, c);
679        assert_eq!(&a / b, c);
680        assert_eq!(&a / &b, c);
681        assert_eq!(Wrapping(a) / b, Wrapping(c));
682        assert_eq!(Wrapping(a) / &b, Wrapping(c));
683        assert_eq!(&Wrapping(a) / b, Wrapping(c));
684        assert_eq!(&Wrapping(a) / &b, Wrapping(c));
685    }
686
687    #[allow(clippy::op_ref)]
688    #[test]
689    fn div_assign_trait() {
690        let a = U256::from(10u64);
691        let b = NonZero::new(U256::from(2u64)).unwrap();
692        let c = U256::from(5u64);
693
694        let mut res = a;
695        res /= b;
696        assert_eq!(res, c);
697        let mut res = a;
698        res /= &b;
699        assert_eq!(res, c);
700
701        let mut res = Wrapping(a);
702        res /= b;
703        assert_eq!(res, Wrapping(c));
704        let mut res = Wrapping(a);
705        res /= &b;
706        assert_eq!(res, Wrapping(c));
707    }
708
709    #[should_panic]
710    #[test]
711    fn div_zero() {
712        let _ = U256::ONE / U256::ZERO;
713    }
714
715    #[should_panic]
716    #[test]
717    #[allow(clippy::op_ref)]
718    fn div_ref_zero() {
719        let _ = &U256::ONE / U256::ZERO;
720    }
721
722    #[test]
723    fn reduce_one() {
724        let r = U256::from(10u8).rem_vartime(&NonZero::new(U256::ONE).unwrap());
725        assert_eq!(r, U256::ZERO);
726    }
727
728    #[test]
729    fn reduce_tests() {
730        let tests = [
731            (U256::from(2u8), 0u8),
732            (U256::from(3u8), 1u8),
733            (U256::from(7u8), 3u8),
734            (U256::MAX, 10u8),
735        ];
736        for (divisor, expect) in tests {
737            let r1 = U256::from(10u8).rem(&NonZero::new(divisor).unwrap());
738            let r2 = U256::from(10u8).rem_vartime(&NonZero::new(divisor).unwrap());
739            assert_eq!(r1, U256::from(expect));
740            assert_eq!(r1, r2);
741        }
742    }
743
744    #[test]
745    fn reduce_tests_wide_zero_padded() {
746        let tests = [
747            (U256::from(2u8), 0u8),
748            (U256::from(3u8), 1u8),
749            (U256::from(7u8), 3u8),
750            (U256::MAX, 10u8),
751        ];
752        for (divisor, expect) in tests {
753            let r1 = U256::rem_wide(
754                (U256::from(10u8), U256::ZERO),
755                &NonZero::new(divisor).unwrap(),
756            );
757            let r2 = U256::rem_wide_vartime(
758                (U256::from(10u8), U256::ZERO),
759                &NonZero::new(divisor).unwrap(),
760            );
761            assert_eq!(r1, U256::from(expect));
762            assert_eq!(r1, r2);
763        }
764    }
765
766    #[test]
767    fn rem_wide_corner_case() {
768        let modulus = "0000000000000000000000000000000081000000000000000000000000000001";
769        let modulus = NonZero::new(U256::from_be_hex(modulus)).expect("it's odd and not zero");
770        let lo_hi = (
771            U256::from_be_hex("1000000000000000000000000000000000000000000000000000000000000001"),
772            U256::ZERO,
773        );
774        let rem = U256::rem_wide(lo_hi, &modulus);
775        // Lower half is zero
776        assert_eq!(
777            &rem.to_be_bytes().as_ref()[0..16],
778            U128::ZERO.to_be_bytes().as_ref()
779        );
780        // Upper half
781        let expected = U128::from_be_hex("203F80FE03F80FE03F80FE03F80FE041");
782        assert_eq!(
783            &rem.to_be_bytes().as_ref()[16..],
784            expected.to_be_bytes().as_ref()
785        );
786
787        let remv = U256::rem_wide_vartime(lo_hi, &modulus);
788        assert_eq!(rem, remv);
789    }
790
791    #[test]
792    fn reduce_max() {
793        let mut a = U256::ZERO;
794        let mut b = U256::ZERO;
795        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
796        let r = a.wrapping_rem_vartime(&b);
797        assert_eq!(r, Uint::ZERO);
798        a.limbs[a.limbs.len() - 1] = Limb(1 << (Limb::HI_BIT - 7));
799        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (Limb::HI_BIT - 7));
800        let r = a.wrapping_rem_vartime(&b);
801        assert_eq!(r, a);
802    }
803
804    #[cfg(feature = "rand_core")]
805    #[test]
806    fn rem2krand() {
807        let mut rng = ChaCha8Rng::from_seed([7u8; 32]);
808        for _ in 0..25 {
809            let num = U256::random_from_rng(&mut rng);
810            let k = rng.next_u32() % 256;
811            let den = U256::ONE.overflowing_shl_vartime(k).unwrap();
812
813            let a = num.rem2k_vartime(k);
814            let e = num.wrapping_rem_vartime(&den);
815            assert_eq!(a, e);
816        }
817    }
818
819    #[allow(clippy::op_ref)]
820    #[test]
821    fn rem_trait() {
822        let a = U256::from(10u64);
823        let b = NonZero::new(U256::from(3u64)).unwrap();
824        let c = U256::from(1u64);
825
826        assert_eq!(a % b, c);
827        assert_eq!(a % &b, c);
828        assert_eq!(&a % b, c);
829        assert_eq!(&a % &b, c);
830        assert_eq!(Wrapping(a) % b, Wrapping(c));
831        assert_eq!(Wrapping(a) % &b, Wrapping(c));
832        assert_eq!(&Wrapping(a) % b, Wrapping(c));
833        assert_eq!(&Wrapping(a) % &b, Wrapping(c));
834    }
835
836    #[allow(clippy::op_ref)]
837    #[test]
838    fn rem_assign_trait() {
839        let a = U256::from(10u64);
840        let b = NonZero::new(U256::from(3u64)).unwrap();
841        let c = U256::from(1u64);
842
843        let mut res = a;
844        res %= b;
845        assert_eq!(res, c);
846        let mut res = a;
847        res %= &b;
848        assert_eq!(res, c);
849
850        let mut res = Wrapping(a);
851        res %= b;
852        assert_eq!(res, Wrapping(c));
853        let mut res = Wrapping(a);
854        res %= &b;
855        assert_eq!(res, Wrapping(c));
856    }
857
858    #[should_panic]
859    #[test]
860    fn rem_zero() {
861        let _ = U256::ONE % U256::ZERO;
862    }
863
864    #[should_panic]
865    #[test]
866    #[allow(clippy::op_ref)]
867    fn rem_ref_zero() {
868        let _ = &U256::ONE % U256::ZERO;
869    }
870
871    #[test]
872    fn rem_mixed() {
873        let x = U1024::from_be_hex(concat![
874            "3740C11DB8F260753BC6B97DD2B8746D3E2694412772AC6ABD975119EE0A6190",
875            "F27F6F0969BCA069D8D151031AF83EE2283CC2E3E4FADBBDB9EEDBF0B8F4C1FD",
876            "51912C0D329FDC37D49176DB0A1A2D17E5E6D4F9F6B217FE9412EAA2F881F702",
877            "7A831C1B06D31D3618D218D6E667DBD85BFC7B6B6B93422D52516989376AA29A",
878        ]);
879        let y = U128::from_u64(1234567890987654321);
880        let rem = x.rem_mixed(&y.to_nz().unwrap());
881
882        let y2: U1024 = U128::concat_mixed(&y, &U896::ZERO);
883        let rem_control = x.rem(&NonZero::new(y2).unwrap());
884
885        assert_eq!(rem.bits(), rem_control.bits());
886        assert_eq!(rem.as_words(), &rem_control.as_words()[0..U128::LIMBS]);
887        assert!(
888            rem_control.as_words()[U128::LIMBS..]
889                .iter()
890                .all(|w| *w == 0)
891        );
892    }
893
894    #[test]
895    fn rem_mixed_even() {
896        let x = U1024::from_be_hex(concat![
897            "3740C11DB8F260753BC6B97DD2B8746D3E2694412772AC6ABD975119EE0A6190",
898            "F27F6F0969BCA069D8D151031AF83EE2283CC2E3E4FADBBDB9EEDBF0B8F4C1FD",
899            "51912C0D329FDC37D49176DB0A1A2D17E5E6D4F9F6B217FE9412EAA2F881F702",
900            "7A831C1B06D31D3618D218D6E667DBD85BFC7B6B6B93422D52516989376AA29A",
901        ]);
902        let y = U512::from_u64(1234567890987654321);
903        let rem: U512 = x.rem_mixed(&y.to_nz().unwrap());
904
905        let y_wide = U512::concat_mixed(&y, &U512::ZERO);
906        let rem_control: U1024 = x.rem(&NonZero::new(y_wide).unwrap());
907
908        assert_eq!(rem.bits(), rem_control.bits());
909        assert_eq!(rem.as_words(), &rem_control.as_words()[0..U512::LIMBS]);
910        assert!(
911            rem_control.as_words()[U512::LIMBS..]
912                .iter()
913                .all(|w| *w == 0)
914        );
915    }
916
917    #[test]
918    fn rem_mixed_through_traits() {
919        struct A<T, U> {
920            t: T,
921            u: U,
922        }
923        impl<T, U> A<T, U>
924        where
925            T: RemMixed<U>,
926            U: Clone + Zero + One + CtAssign,
927        {
928            fn reduce_t_by_u(&self) -> U {
929                let rhs = &NonZero::new(self.u.clone()).unwrap();
930                self.t.rem_mixed(rhs)
931            }
932        }
933
934        let a = A {
935            t: U1024::from(1234567890u64),
936            u: U128::from(456u64),
937        };
938        assert_eq!(a.reduce_t_by_u(), U128::from(330u64));
939    }
940
941    #[test]
942    fn div_vartime_through_traits() {
943        struct A<T> {
944            x: T,
945            y: T,
946        }
947        impl<T> A<T>
948        where
949            T: DivVartime + Clone + Zero + One + CtAssign,
950        {
951            fn divide_x_by_y(&self) -> T {
952                let rhs = &NonZero::new(self.y.clone()).unwrap();
953                self.x.div_vartime(rhs)
954            }
955        }
956
957        let a = A {
958            x: U1024::from(1234567890u64),
959            y: U1024::from(456u64),
960        };
961        assert_eq!(a.divide_x_by_y(), U1024::from(2707385u64));
962    }
963}
crypto_bigint/uint/div.rs

crypto_bigint/uint/
div.rs
