crypto_bigint/uint/
div.rs

1//! [`Uint`] division operations.
2
3use super::div_limb::{div_rem_limb_with_reciprocal, Reciprocal};
4use crate::{CtChoice, Limb, NonZero, Uint, Word, Wrapping};
5use core::ops::{Div, DivAssign, Rem, RemAssign};
6use subtle::CtOption;
7
8impl<const LIMBS: usize> Uint<LIMBS> {
9    /// Computes `self` / `rhs` using a pre-made reciprocal,
10    /// returns the quotient (q) and remainder (r).
11    #[inline(always)]
12    pub const fn ct_div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
13        div_rem_limb_with_reciprocal(self, reciprocal)
14    }
15
16    /// Computes `self` / `rhs` using a pre-made reciprocal,
17    /// returns the quotient (q) and remainder (r).
18    #[inline(always)]
19    pub fn div_rem_limb_with_reciprocal(
20        &self,
21        reciprocal: &CtOption<Reciprocal>,
22    ) -> CtOption<(Self, Limb)> {
23        reciprocal.map(|r| div_rem_limb_with_reciprocal(self, &r))
24    }
25
26    /// Computes `self` / `rhs`, returns the quotient (q) and remainder (r).
27    /// Returns the truthy value as the third element of the tuple if `rhs != 0`,
28    /// and the falsy value otherwise.
29    #[inline(always)]
30    pub(crate) const fn ct_div_rem_limb(&self, rhs: Limb) -> (Self, Limb, CtChoice) {
31        let (reciprocal, is_some) = Reciprocal::ct_new(rhs);
32        let (quo, rem) = div_rem_limb_with_reciprocal(self, &reciprocal);
33        (quo, rem, is_some)
34    }
35
36    /// Computes `self` / `rhs`, returns the quotient (q) and remainder (r).
37    #[inline(always)]
38    pub fn div_rem_limb(&self, rhs: NonZero<Limb>) -> (Self, Limb) {
39        // Guaranteed to succeed since `rhs` is nonzero.
40        let (quo, rem, _is_some) = self.ct_div_rem_limb(*rhs);
41        (quo, rem)
42    }
43
44    /// Computes `self` / `rhs`, returns the quotient (q), remainder (r)
45    /// and the truthy value for is_some or the falsy value for is_none.
46    ///
47    /// NOTE: Use only if you need to access const fn. Otherwise use [`Self::div_rem`] because
48    /// the value for is_some needs to be checked before using `q` and `r`.
49    ///
50    /// This is variable only with respect to `rhs`.
51    ///
52    /// When used with a fixed `rhs`, this function is constant-time with respect
53    /// to `self`.
54    pub(crate) const fn ct_div_rem(&self, rhs: &Self) -> (Self, Self, CtChoice) {
55        let mb = rhs.bits_vartime();
56        let mut bd = Self::BITS - mb;
57        let mut rem = *self;
58        let mut quo = Self::ZERO;
59        let mut c = rhs.shl_vartime(bd);
60
61        loop {
62            let (mut r, borrow) = rem.sbb(&c, Limb::ZERO);
63            rem = Self::ct_select(&r, &rem, CtChoice::from_mask(borrow.0));
64            r = quo.bitor(&Self::ONE);
65            quo = Self::ct_select(&r, &quo, CtChoice::from_mask(borrow.0));
66            if bd == 0 {
67                break;
68            }
69            bd -= 1;
70            c = c.shr_vartime(1);
71            quo = quo.shl_vartime(1);
72        }
73
74        let is_some = Limb(mb as Word).ct_is_nonzero();
75        quo = Self::ct_select(&Self::ZERO, &quo, is_some);
76        (quo, rem, is_some)
77    }
78
79    /// Computes `self` % `rhs`, returns the remainder and
80    /// and the truthy value for is_some or the falsy value for is_none.
81    ///
82    /// NOTE: Use only if you need to access const fn. Otherwise use [`Self::rem`].
83    /// This is variable only with respect to `rhs`.
84    ///
85    /// When used with a fixed `rhs`, this function is constant-time with respect
86    /// to `self`.
87    pub const fn const_rem(&self, rhs: &Self) -> (Self, CtChoice) {
88        let mb = rhs.bits_vartime();
89        let mut bd = Self::BITS - mb;
90        let mut rem = *self;
91        let mut c = rhs.shl_vartime(bd);
92
93        loop {
94            let (r, borrow) = rem.sbb(&c, Limb::ZERO);
95            rem = Self::ct_select(&r, &rem, CtChoice::from_mask(borrow.0));
96            if bd == 0 {
97                break;
98            }
99            bd -= 1;
100            c = c.shr_vartime(1);
101        }
102
103        let is_some = Limb(mb as Word).ct_is_nonzero();
104        (rem, is_some)
105    }
106
107    /// Computes `self` % `rhs`, returns the remainder and
108    /// and the truthy value for is_some or the falsy value for is_none.
109    ///
110    /// This is variable only with respect to `rhs`.
111    ///
112    /// When used with a fixed `rhs`, this function is constant-time with respect
113    /// to `self`.
114    pub const fn const_rem_wide(lower_upper: (Self, Self), rhs: &Self) -> (Self, CtChoice) {
115        let mb = rhs.bits_vartime();
116
117        // The number of bits to consider is two sets of limbs * BITS - mb (modulus bitcount)
118        let mut bd = (2 * Self::BITS) - mb;
119
120        // The wide integer to reduce, split into two halves
121        let (mut lower, mut upper) = lower_upper;
122
123        // Factor of the modulus, split into two halves
124        let mut c = Self::shl_vartime_wide((*rhs, Uint::ZERO), bd);
125
126        loop {
127            let (lower_sub, borrow) = lower.sbb(&c.0, Limb::ZERO);
128            let (upper_sub, borrow) = upper.sbb(&c.1, borrow);
129
130            lower = Self::ct_select(&lower_sub, &lower, CtChoice::from_mask(borrow.0));
131            upper = Self::ct_select(&upper_sub, &upper, CtChoice::from_mask(borrow.0));
132            if bd == 0 {
133                break;
134            }
135            bd -= 1;
136            c = Self::shr_vartime_wide(c, 1);
137        }
138
139        let is_some = Limb(mb as Word).ct_is_nonzero();
140        (lower, is_some)
141    }
142
143    /// Computes `self` % 2^k. Faster than reduce since its a power of 2.
144    /// Limited to 2^16-1 since Uint doesn't support higher.
145    pub const fn rem2k(&self, k: usize) -> Self {
146        let highest = (LIMBS - 1) as u32;
147        let index = k as u32 / (Limb::BITS as u32);
148        let le = Limb::ct_le(Limb::from_u32(index), Limb::from_u32(highest));
149        let word = Limb::ct_select(Limb::from_u32(highest), Limb::from_u32(index), le).0 as usize;
150
151        let base = k % Limb::BITS;
152        let mask = (1 << base) - 1;
153        let mut out = *self;
154
155        let outmask = Limb(out.limbs[word].0 & mask);
156
157        out.limbs[word] = Limb::ct_select(out.limbs[word], outmask, le);
158
159        let mut i = word + 1;
160        while i < LIMBS {
161            out.limbs[i] = Limb::ZERO;
162            i += 1;
163        }
164
165        out
166    }
167
168    /// Computes self / rhs, returns the quotient, remainder.
169    pub fn div_rem(&self, rhs: &NonZero<Self>) -> (Self, Self) {
170        // Since `rhs` is nonzero, this should always hold.
171        let (q, r, _c) = self.ct_div_rem(rhs);
172        (q, r)
173    }
174
175    /// Computes self % rhs, returns the remainder.
176    pub fn rem(&self, rhs: &NonZero<Self>) -> Self {
177        // Since `rhs` is nonzero, this should always hold.
178        let (r, _c) = self.const_rem(rhs);
179        r
180    }
181
182    /// Wrapped division is just normal division i.e. `self` / `rhs`
183    /// There’s no way wrapping could ever happen.
184    /// This function exists, so that all operations are accounted for in the wrapping operations.
185    ///
186    /// Panics if `rhs == 0`.
187    pub const fn wrapping_div(&self, rhs: &Self) -> Self {
188        let (q, _, c) = self.ct_div_rem(rhs);
189        assert!(c.is_true_vartime(), "divide by zero");
190        q
191    }
192
193    /// Perform checked division, returning a [`CtOption`] which `is_some`
194    /// only if the rhs != 0
195    pub fn checked_div(&self, rhs: &Self) -> CtOption<Self> {
196        NonZero::new(*rhs).map(|rhs| {
197            let (q, _r) = self.div_rem(&rhs);
198            q
199        })
200    }
201
202    /// Wrapped (modular) remainder calculation is just `self` % `rhs`.
203    /// There’s no way wrapping could ever happen.
204    /// This function exists, so that all operations are accounted for in the wrapping operations.
205    ///
206    /// Panics if `rhs == 0`.
207    pub const fn wrapping_rem(&self, rhs: &Self) -> Self {
208        let (r, c) = self.const_rem(rhs);
209        assert!(c.is_true_vartime(), "modulo zero");
210        r
211    }
212
213    /// Perform checked reduction, returning a [`CtOption`] which `is_some`
214    /// only if the rhs != 0
215    pub fn checked_rem(&self, rhs: &Self) -> CtOption<Self> {
216        NonZero::new(*rhs).map(|rhs| self.rem(&rhs))
217    }
218}
219
220//
221// Division by a single limb
222//
223
224impl<const LIMBS: usize> Div<&NonZero<Limb>> for &Uint<LIMBS> {
225    type Output = Uint<LIMBS>;
226
227    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
228        *self / *rhs
229    }
230}
231
232impl<const LIMBS: usize> Div<&NonZero<Limb>> for Uint<LIMBS> {
233    type Output = Uint<LIMBS>;
234
235    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
236        self / *rhs
237    }
238}
239
240impl<const LIMBS: usize> Div<NonZero<Limb>> for &Uint<LIMBS> {
241    type Output = Uint<LIMBS>;
242
243    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
244        *self / rhs
245    }
246}
247
248impl<const LIMBS: usize> Div<NonZero<Limb>> for Uint<LIMBS> {
249    type Output = Uint<LIMBS>;
250
251    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
252        let (q, _, _) = self.ct_div_rem_limb(*rhs);
253        q
254    }
255}
256
257impl<const LIMBS: usize> DivAssign<&NonZero<Limb>> for Uint<LIMBS> {
258    fn div_assign(&mut self, rhs: &NonZero<Limb>) {
259        *self /= *rhs;
260    }
261}
262
263impl<const LIMBS: usize> DivAssign<NonZero<Limb>> for Uint<LIMBS> {
264    fn div_assign(&mut self, rhs: NonZero<Limb>) {
265        *self = *self / rhs;
266    }
267}
268
269impl<const LIMBS: usize> Div<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
270    type Output = Wrapping<Uint<LIMBS>>;
271
272    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
273        Wrapping(self.0 / rhs)
274    }
275}
276
277impl<const LIMBS: usize> Div<NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
278    type Output = Wrapping<Uint<LIMBS>>;
279
280    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
281        *self / rhs
282    }
283}
284
285impl<const LIMBS: usize> Div<&NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
286    type Output = Wrapping<Uint<LIMBS>>;
287
288    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
289        *self / *rhs
290    }
291}
292
293impl<const LIMBS: usize> Div<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
294    type Output = Wrapping<Uint<LIMBS>>;
295
296    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
297        self / *rhs
298    }
299}
300
301impl<const LIMBS: usize> DivAssign<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
302    fn div_assign(&mut self, rhs: &NonZero<Limb>) {
303        *self = Wrapping(self.0 / rhs)
304    }
305}
306
307impl<const LIMBS: usize> DivAssign<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
308    fn div_assign(&mut self, rhs: NonZero<Limb>) {
309        *self /= &rhs;
310    }
311}
312
313impl<const LIMBS: usize> Rem<&NonZero<Limb>> for &Uint<LIMBS> {
314    type Output = Limb;
315
316    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
317        *self % *rhs
318    }
319}
320
321impl<const LIMBS: usize> Rem<&NonZero<Limb>> for Uint<LIMBS> {
322    type Output = Limb;
323
324    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
325        self % *rhs
326    }
327}
328
329impl<const LIMBS: usize> Rem<NonZero<Limb>> for &Uint<LIMBS> {
330    type Output = Limb;
331
332    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
333        *self % rhs
334    }
335}
336
337impl<const LIMBS: usize> Rem<NonZero<Limb>> for Uint<LIMBS> {
338    type Output = Limb;
339
340    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
341        let (_, r, _) = self.ct_div_rem_limb(*rhs);
342        r
343    }
344}
345
346impl<const LIMBS: usize> RemAssign<&NonZero<Limb>> for Uint<LIMBS> {
347    fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
348        *self = (*self % rhs).into();
349    }
350}
351
352impl<const LIMBS: usize> RemAssign<NonZero<Limb>> for Uint<LIMBS> {
353    fn rem_assign(&mut self, rhs: NonZero<Limb>) {
354        *self %= &rhs;
355    }
356}
357
358impl<const LIMBS: usize> Rem<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
359    type Output = Wrapping<Limb>;
360
361    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
362        Wrapping(self.0 % rhs)
363    }
364}
365
366impl<const LIMBS: usize> Rem<NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
367    type Output = Wrapping<Limb>;
368
369    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
370        *self % rhs
371    }
372}
373
374impl<const LIMBS: usize> Rem<&NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
375    type Output = Wrapping<Limb>;
376
377    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
378        *self % *rhs
379    }
380}
381
382impl<const LIMBS: usize> Rem<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
383    type Output = Wrapping<Limb>;
384
385    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
386        self % *rhs
387    }
388}
389
390impl<const LIMBS: usize> RemAssign<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
391    fn rem_assign(&mut self, rhs: NonZero<Limb>) {
392        *self %= &rhs;
393    }
394}
395
396impl<const LIMBS: usize> RemAssign<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
397    fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
398        *self = Wrapping((self.0 % rhs).into())
399    }
400}
401
402//
403// Division by an Uint
404//
405
406impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
407    type Output = Uint<LIMBS>;
408
409    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
410        *self / *rhs
411    }
412}
413
414impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
415    type Output = Uint<LIMBS>;
416
417    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
418        self / *rhs
419    }
420}
421
422impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
423    type Output = Uint<LIMBS>;
424
425    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
426        *self / rhs
427    }
428}
429
430impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
431    type Output = Uint<LIMBS>;
432
433    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
434        let (q, _) = self.div_rem(&rhs);
435        q
436    }
437}
438
439impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
440    fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
441        *self /= *rhs
442    }
443}
444
445impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
446    fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
447        *self = *self / rhs;
448    }
449}
450
451impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
452    type Output = Wrapping<Uint<LIMBS>>;
453
454    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
455        Wrapping(self.0 / rhs)
456    }
457}
458
459impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
460    type Output = Wrapping<Uint<LIMBS>>;
461
462    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
463        *self / rhs
464    }
465}
466
467impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
468    type Output = Wrapping<Uint<LIMBS>>;
469
470    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
471        *self / *rhs
472    }
473}
474
475impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
476    type Output = Wrapping<Uint<LIMBS>>;
477
478    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
479        self / *rhs
480    }
481}
482
483impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
484    fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
485        *self = Wrapping(self.0 / rhs);
486    }
487}
488
489impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
490    fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
491        *self /= &rhs;
492    }
493}
494
495impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
496    type Output = Uint<LIMBS>;
497
498    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
499        *self % *rhs
500    }
501}
502
503impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
504    type Output = Uint<LIMBS>;
505
506    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
507        self % *rhs
508    }
509}
510
511impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
512    type Output = Uint<LIMBS>;
513
514    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
515        *self % rhs
516    }
517}
518
519impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
520    type Output = Uint<LIMBS>;
521
522    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
523        Self::rem(&self, &rhs)
524    }
525}
526
527impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
528    fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
529        *self %= *rhs
530    }
531}
532
533impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
534    fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
535        *self = *self % rhs;
536    }
537}
538
539impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
540    type Output = Wrapping<Uint<LIMBS>>;
541
542    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
543        Wrapping(self.0 % rhs)
544    }
545}
546
547impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
548    type Output = Wrapping<Uint<LIMBS>>;
549
550    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
551        *self % rhs
552    }
553}
554
555impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
556    type Output = Wrapping<Uint<LIMBS>>;
557
558    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
559        *self % *rhs
560    }
561}
562
563impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
564    type Output = Wrapping<Uint<LIMBS>>;
565
566    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
567        self % *rhs
568    }
569}
570
571impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
572    fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
573        *self %= &rhs;
574    }
575}
576
577impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
578    fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
579        *self = Wrapping(self.0 % rhs)
580    }
581}
582
583#[cfg(test)]
584mod tests {
585    use super::*;
586    use crate::{limb::HI_BIT, Limb, U256};
587
588    #[cfg(feature = "rand")]
589    use {
590        crate::{CheckedMul, Random},
591        rand_chacha::ChaChaRng,
592        rand_core::RngCore,
593        rand_core::SeedableRng,
594    };
595
596    #[test]
597    fn div_word() {
598        for (n, d, e, ee) in &[
599            (200u64, 2u64, 100u64, 0),
600            (100u64, 25u64, 4u64, 0),
601            (100u64, 10u64, 10u64, 0),
602            (1024u64, 8u64, 128u64, 0),
603            (27u64, 13u64, 2u64, 1u64),
604            (26u64, 13u64, 2u64, 0u64),
605            (14u64, 13u64, 1u64, 1u64),
606            (13u64, 13u64, 1u64, 0u64),
607            (12u64, 13u64, 0u64, 12u64),
608            (1u64, 13u64, 0u64, 1u64),
609        ] {
610            let lhs = U256::from(*n);
611            let rhs = U256::from(*d);
612            let (q, r, is_some) = lhs.ct_div_rem(&rhs);
613            assert!(is_some.is_true_vartime());
614            assert_eq!(U256::from(*e), q);
615            assert_eq!(U256::from(*ee), r);
616        }
617    }
618
619    #[cfg(feature = "rand")]
620    #[test]
621    fn div() {
622        let mut rng = ChaChaRng::from_seed([7u8; 32]);
623        for _ in 0..25 {
624            let num = U256::random(&mut rng).shr_vartime(128);
625            let den = U256::random(&mut rng).shr_vartime(128);
626            let n = num.checked_mul(&den);
627            if n.is_some().into() {
628                let (q, _, is_some) = n.unwrap().ct_div_rem(&den);
629                assert!(is_some.is_true_vartime());
630                assert_eq!(q, num);
631            }
632        }
633    }
634
635    #[test]
636    fn div_max() {
637        let mut a = U256::ZERO;
638        let mut b = U256::ZERO;
639        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
640        let q = a.wrapping_div(&b);
641        assert_eq!(q, Uint::ZERO);
642        a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
643        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
644        let q = a.wrapping_div(&b);
645        assert_eq!(q, Uint::ZERO);
646    }
647
648    #[test]
649    fn div_zero() {
650        let (q, r, is_some) = U256::ONE.ct_div_rem(&U256::ZERO);
651        assert!(!is_some.is_true_vartime());
652        assert_eq!(q, U256::ZERO);
653        assert_eq!(r, U256::ONE);
654    }
655
656    #[test]
657    fn div_one() {
658        let (q, r, is_some) = U256::from(10u8).ct_div_rem(&U256::ONE);
659        assert!(is_some.is_true_vartime());
660        assert_eq!(q, U256::from(10u8));
661        assert_eq!(r, U256::ZERO);
662    }
663
664    #[test]
665    fn reduce_one() {
666        let (r, is_some) = U256::from(10u8).const_rem(&U256::ONE);
667        assert!(is_some.is_true_vartime());
668        assert_eq!(r, U256::ZERO);
669    }
670
671    #[test]
672    fn reduce_zero() {
673        let u = U256::from(10u8);
674        let (r, is_some) = u.const_rem(&U256::ZERO);
675        assert!(!is_some.is_true_vartime());
676        assert_eq!(r, u);
677    }
678
679    #[test]
680    fn reduce_tests() {
681        let (r, is_some) = U256::from(10u8).const_rem(&U256::from(2u8));
682        assert!(is_some.is_true_vartime());
683        assert_eq!(r, U256::ZERO);
684        let (r, is_some) = U256::from(10u8).const_rem(&U256::from(3u8));
685        assert!(is_some.is_true_vartime());
686        assert_eq!(r, U256::ONE);
687        let (r, is_some) = U256::from(10u8).const_rem(&U256::from(7u8));
688        assert!(is_some.is_true_vartime());
689        assert_eq!(r, U256::from(3u8));
690    }
691
692    #[test]
693    fn reduce_tests_wide_zero_padded() {
694        let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(2u8));
695        assert!(is_some.is_true_vartime());
696        assert_eq!(r, U256::ZERO);
697        let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(3u8));
698        assert!(is_some.is_true_vartime());
699        assert_eq!(r, U256::ONE);
700        let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(7u8));
701        assert!(is_some.is_true_vartime());
702        assert_eq!(r, U256::from(3u8));
703    }
704
705    #[test]
706    fn reduce_max() {
707        let mut a = U256::ZERO;
708        let mut b = U256::ZERO;
709        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
710        let r = a.wrapping_rem(&b);
711        assert_eq!(r, Uint::ZERO);
712        a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
713        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
714        let r = a.wrapping_rem(&b);
715        assert_eq!(r, a);
716    }
717
718    #[cfg(feature = "rand")]
719    #[test]
720    fn rem2krand() {
721        let mut rng = ChaChaRng::from_seed([7u8; 32]);
722        for _ in 0..25 {
723            let num = U256::random(&mut rng);
724            let k = (rng.next_u32() % 256) as usize;
725            let den = U256::ONE.shl_vartime(k);
726
727            let a = num.rem2k(k);
728            let e = num.wrapping_rem(&den);
729            assert_eq!(a, e);
730        }
731    }
732
733    #[allow(clippy::op_ref)]
734    #[test]
735    fn rem_trait() {
736        let a = U256::from(10u64);
737        let b = NonZero::new(U256::from(3u64)).unwrap();
738        let c = U256::from(1u64);
739
740        assert_eq!(a % b, c);
741        assert_eq!(a % &b, c);
742        assert_eq!(&a % b, c);
743        assert_eq!(&a % &b, c);
744    }
745}
crypto_bigint/uint/div.rs

crypto_bigint/uint/
div.rs
