crypto_bigint/uint/
div.rs

1//! [`Uint`] division operations.
2
3use super::div_limb::{
4    div2by1, div3by2, div_rem_limb_with_reciprocal, rem_limb_with_reciprocal,
5    rem_limb_with_reciprocal_wide, Reciprocal,
6};
7use crate::{CheckedDiv, ConstChoice, DivRemLimb, Limb, NonZero, RemLimb, Uint, Wrapping};
8use core::ops::{Div, DivAssign, Rem, RemAssign};
9
10use subtle::CtOption;
11
12impl<const LIMBS: usize> Uint<LIMBS> {
13    /// Computes `self / rhs` using a pre-made reciprocal,
14    /// returns the quotient (q) and remainder (r).
15    #[inline(always)]
16    pub const fn div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
17        div_rem_limb_with_reciprocal(self, reciprocal)
18    }
19
20    /// Computes `self / rhs`, returns the quotient (q) and remainder (r).
21    #[inline(always)]
22    pub const fn div_rem_limb(&self, rhs: NonZero<Limb>) -> (Self, Limb) {
23        div_rem_limb_with_reciprocal(self, &Reciprocal::new(rhs))
24    }
25
26    /// Computes `self % rhs` using a pre-made reciprocal.
27    #[inline(always)]
28    pub const fn rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> Limb {
29        rem_limb_with_reciprocal(self, reciprocal)
30    }
31
32    /// Computes `self % rhs`.
33    #[inline(always)]
34    pub const fn rem_limb(&self, rhs: NonZero<Limb>) -> Limb {
35        rem_limb_with_reciprocal(self, &Reciprocal::new(rhs))
36    }
37
38    /// Computes `self` / `rhs`, returns the quotient (q) and the remainder (r)
39    ///
40    /// This function is constant-time with respect to both `self` and `rhs`.
41    pub const fn div_rem(&self, rhs: &NonZero<Self>) -> (Self, Self) {
42        // Based on Section 4.3.1, of The Art of Computer Programming, Volume 2, by Donald E. Knuth.
43        // Further explanation at https://janmr.com/blog/2014/04/basic-multiple-precision-long-division/
44
45        // Statically determined short circuit for Uint<1>
46        if LIMBS == 1 {
47            let (quo, rem_limb) = self.div_rem_limb(rhs.0.limbs[0].to_nz().expect("zero divisor"));
48            let mut rem = Self::ZERO;
49            rem.limbs[0] = rem_limb;
50            return (quo, rem);
51        }
52
53        let dbits = rhs.0.bits();
54        assert!(dbits > 0, "zero divisor");
55        let dwords = dbits.div_ceil(Limb::BITS);
56        let lshift = (Limb::BITS - (dbits % Limb::BITS)) % Limb::BITS;
57
58        // Shift entire divisor such that the high bit is set
59        let mut y = rhs.0.shl(Self::BITS - dbits).to_limbs();
60        // Shift the dividend to align the words
61        let (x, mut x_hi) = self.shl_limb(lshift);
62        let mut x = x.to_limbs();
63        let mut xi = LIMBS - 1;
64        let mut x_lo = x[LIMBS - 1];
65        let mut i;
66        let mut carry;
67
68        let reciprocal = Reciprocal::new(y[LIMBS - 1].to_nz().expect("zero divisor"));
69
70        while xi > 0 {
71            // Divide high dividend words by the high divisor word to estimate the quotient word
72            let mut quo = div3by2(x_hi.0, x_lo.0, x[xi - 1].0, &reciprocal, y[LIMBS - 2].0);
73
74            // This loop is a no-op once xi is smaller than the number of words in the divisor
75            let done = ConstChoice::from_u32_lt(xi as u32, dwords - 1);
76            quo = done.select_word(quo, 0);
77
78            // Subtract q*divisor from the dividend
79            carry = Limb::ZERO;
80            let mut borrow = Limb::ZERO;
81            let mut tmp;
82            i = 0;
83            while i <= xi {
84                (tmp, carry) = Limb::ZERO.mac(y[LIMBS - xi + i - 1], Limb(quo), carry);
85                (x[i], borrow) = x[i].sbb(tmp, borrow);
86                i += 1;
87            }
88            (_, borrow) = x_hi.sbb(carry, borrow);
89
90            // If the subtraction borrowed, then decrement q and add back the divisor
91            // The probability of this being needed is very low, about 2/(Limb::MAX+1)
92            let ct_borrow = ConstChoice::from_word_mask(borrow.0);
93            carry = Limb::ZERO;
94            i = 0;
95            while i <= xi {
96                (x[i], carry) = x[i].adc(
97                    Limb::select(Limb::ZERO, y[LIMBS - xi + i - 1], ct_borrow),
98                    carry,
99                );
100                i += 1;
101            }
102            quo = ct_borrow.select_word(quo, quo.saturating_sub(1));
103
104            // Store the quotient within dividend and set x_hi to the current highest word
105            x_hi = Limb::select(x[xi], x_hi, done);
106            x[xi] = Limb::select(Limb(quo), x[xi], done);
107            x_lo = Limb::select(x[xi - 1], x_lo, done);
108            xi -= 1;
109        }
110
111        let limb_div = ConstChoice::from_u32_eq(1, dwords);
112
113        // Calculate quotient and remainder for the case where the divisor is a single word
114        // Note that `div2by1()` will panic if `x_hi >= reciprocal.divisor_normalized`,
115        // but this can only be the case if `limb_div` is falsy,
116        // in which case we discard the result anyway,
117        // so we conditionally set `x_hi` to zero for this branch.
118        let x_hi_adjusted = Limb::select(Limb::ZERO, x_hi, limb_div);
119        let (quo2, rem2) = div2by1(x_hi_adjusted.0, x_lo.0, &reciprocal);
120
121        // Adjust the quotient for single limb division
122        x[0] = Limb::select(x[0], Limb(quo2), limb_div);
123
124        // Copy out the remainder
125        y[0] = Limb::select(x[0], Limb(rem2), limb_div);
126        i = 1;
127        while i < LIMBS {
128            y[i] = Limb::select(Limb::ZERO, x[i], ConstChoice::from_u32_lt(i as u32, dwords));
129            y[i] = Limb::select(y[i], x_hi, ConstChoice::from_u32_eq(i as u32, dwords - 1));
130            i += 1;
131        }
132
133        (
134            Uint::new(x).shr((dwords - 1) * Limb::BITS),
135            Uint::new(y).shr(lshift),
136        )
137    }
138
139    /// Computes `self << shift` where `0 <= shift < Limb::BITS`,
140    /// returning the result and the carry.
141    ///
142    /// Note: assumes that `self` only has `limb_num` lowest non-zero limbs.
143    const fn shl_limb_vartime(&self, shift: u32, limbs_num: usize) -> (Self, Limb) {
144        if shift == 0 {
145            return (*self, Limb::ZERO);
146        }
147
148        let mut limbs = [Limb::ZERO; LIMBS];
149
150        let lshift = shift;
151        let rshift = Limb::BITS - shift;
152
153        let carry = self.limbs[limbs_num - 1].0 >> rshift;
154        let mut i = limbs_num - 1;
155        while i > 0 {
156            limbs[i] = Limb((self.limbs[i].0 << lshift) | (self.limbs[i - 1].0 >> rshift));
157            i -= 1;
158        }
159        limbs[0] = Limb(self.limbs[0].0 << lshift);
160
161        (Uint::<LIMBS>::new(limbs), Limb(carry))
162    }
163
164    /// Computes `self >> shift` where `0 <= shift < Limb::BITS`.
165    ///
166    /// Note: assumes that `self` only has `limb_num` lowest non-zero limbs.
167    const fn shr_limb_vartime(&self, shift: u32, limbs_num: usize) -> Self {
168        if shift == 0 {
169            return *self;
170        }
171
172        let mut limbs = [Limb::ZERO; LIMBS];
173
174        let lshift = Limb::BITS - shift;
175        let rshift = shift;
176
177        let mut i = 0;
178        while i < limbs_num - 1 {
179            limbs[i] = Limb((self.limbs[i].0 >> rshift) | (self.limbs[i + 1].0 << lshift));
180            i += 1;
181        }
182        limbs[limbs_num - 1] = Limb(self.limbs[limbs_num - 1].0 >> rshift);
183
184        Uint::<LIMBS>::new(limbs)
185    }
186
187    /// Computes `self` / `rhs`, returns the quotient (q) and the remainder (r)
188    ///
189    /// This is variable only with respect to `rhs`.
190    ///
191    /// When used with a fixed `rhs`, this function is constant-time with respect
192    /// to `self`.
193    pub const fn div_rem_vartime<const RHS_LIMBS: usize>(
194        &self,
195        rhs: &NonZero<Uint<RHS_LIMBS>>,
196    ) -> (Self, Uint<RHS_LIMBS>) {
197        // Based on Section 4.3.1, of The Art of Computer Programming, Volume 2, by Donald E. Knuth.
198        // Further explanation at https://janmr.com/blog/2014/04/basic-multiple-precision-long-division/
199
200        let dbits = rhs.0.bits_vartime();
201        let yc = dbits.div_ceil(Limb::BITS) as usize;
202
203        // Short circuit for small or extra large divisors
204        if yc == 1 {
205            // If the divisor is a single limb, use limb division
206            let (q, r) = div_rem_limb_with_reciprocal(
207                self,
208                &Reciprocal::new(rhs.0.limbs[0].to_nz().expect("zero divisor")),
209            );
210            return (q, Uint::from_word(r.0));
211        }
212        if yc > LIMBS {
213            // Divisor is greater than dividend. Return zero and the dividend as the
214            // quotient and remainder
215            return (Uint::ZERO, self.resize());
216        }
217
218        // The shift needed to set the MSB of the highest nonzero limb of the divisor.
219        // 2^shift == d in the algorithm above.
220        let shift = (Limb::BITS - (dbits % Limb::BITS)) % Limb::BITS;
221
222        let (x, mut x_hi) = self.shl_limb_vartime(shift, LIMBS);
223        let mut x = x.to_limbs();
224        let (y, _) = rhs.0.shl_limb_vartime(shift, yc);
225        let mut y = y.to_limbs();
226
227        let reciprocal = Reciprocal::new(y[yc - 1].to_nz().expect("zero divisor"));
228
229        let mut i;
230
231        let mut xi = LIMBS - 1;
232
233        loop {
234            // Divide high dividend words by the high divisor word to estimate the quotient word
235            let mut quo = div3by2(x_hi.0, x[xi].0, x[xi - 1].0, &reciprocal, y[yc - 2].0);
236
237            // Subtract q*divisor from the dividend
238            let borrow = {
239                let mut carry = Limb::ZERO;
240                let mut borrow = Limb::ZERO;
241                let mut tmp;
242                i = 0;
243                while i < yc {
244                    (tmp, carry) = Limb::ZERO.mac(y[i], Limb(quo), carry);
245                    (x[xi + i + 1 - yc], borrow) = x[xi + i + 1 - yc].sbb(tmp, borrow);
246                    i += 1;
247                }
248                (_, borrow) = x_hi.sbb(carry, borrow);
249                borrow
250            };
251
252            // If the subtraction borrowed, then decrement q and add back the divisor
253            // The probability of this being needed is very low, about 2/(Limb::MAX+1)
254            quo = {
255                let ct_borrow = ConstChoice::from_word_mask(borrow.0);
256                let mut carry = Limb::ZERO;
257                i = 0;
258                while i < yc {
259                    (x[xi + i + 1 - yc], carry) =
260                        x[xi + i + 1 - yc].adc(Limb::select(Limb::ZERO, y[i], ct_borrow), carry);
261                    i += 1;
262                }
263                ct_borrow.select_word(quo, quo.wrapping_sub(1))
264            };
265
266            // Store the quotient within dividend and set x_hi to the current highest word
267            x_hi = x[xi];
268            x[xi] = Limb(quo);
269
270            if xi == yc - 1 {
271                break;
272            }
273            xi -= 1;
274        }
275
276        // Copy the remainder to divisor
277        i = 0;
278        while i < yc - 1 {
279            y[i] = x[i];
280            i += 1;
281        }
282        y[yc - 1] = x_hi;
283
284        // Unshift the remainder from the earlier adjustment
285        let y = Uint::new(y).shr_limb_vartime(shift, yc);
286
287        // Shift the quotient to the low limbs within dividend
288        i = 0;
289        while i < LIMBS {
290            if i <= (LIMBS - yc) {
291                x[i] = x[i + yc - 1];
292            } else {
293                x[i] = Limb::ZERO;
294            }
295            i += 1;
296        }
297
298        (Uint::new(x), y)
299    }
300
301    /// Computes `self` % `rhs`, returns the remainder.
302    pub const fn rem(&self, rhs: &NonZero<Self>) -> Self {
303        self.div_rem(rhs).1
304    }
305
306    /// Computes `self` % `rhs`, returns the remainder in variable-time with respect to `rhs`.
307    ///
308    /// When used with a fixed `rhs`, this function is constant-time with respect
309    /// to `self`.
310    pub const fn rem_vartime(&self, rhs: &NonZero<Self>) -> Self {
311        self.div_rem_vartime(rhs).1
312    }
313
314    /// Computes `self` % `rhs`, returns the remainder.
315    ///
316    /// This is variable only with respect to `rhs`.
317    ///
318    /// When used with a fixed `rhs`, this function is constant-time with respect
319    /// to `self`.
320    pub const fn rem_wide_vartime(lower_upper: (Self, Self), rhs: &NonZero<Self>) -> Self {
321        let dbits = rhs.0.bits_vartime();
322        let yc = dbits.div_ceil(Limb::BITS) as usize;
323
324        // If the divisor is a single limb, use limb division
325        if yc == 1 {
326            let r = rem_limb_with_reciprocal_wide(
327                (&lower_upper.0, &lower_upper.1),
328                &Reciprocal::new(rhs.0.limbs[0].to_nz().expect("zero divisor")),
329            );
330            return Uint::from_word(r.0);
331        }
332
333        // The shift needed to set the MSB of the highest nonzero limb of the divisor.
334        // 2^shift == d in the algorithm above.
335        let shift = (Limb::BITS - (dbits % Limb::BITS)) % Limb::BITS;
336
337        let (y, _) = rhs.0.shl_limb_vartime(shift, yc);
338        let y = y.to_limbs();
339
340        let (x_lo, x_lo_carry) = lower_upper.0.shl_limb_vartime(shift, LIMBS);
341        let (x, mut x_hi) = lower_upper.1.shl_limb_vartime(shift, LIMBS);
342        let mut x = x.to_limbs();
343        if shift > 0 {
344            x[0] = Limb(x[0].0 | x_lo_carry.0);
345        }
346
347        let reciprocal = Reciprocal::new(y[yc - 1].to_nz().expect("zero divisor"));
348
349        let mut xi = LIMBS - 1;
350        let mut extra_limbs = LIMBS;
351        let mut i;
352
353        // Note that in the algorithm we only ever need to access the highest `yc` limbs
354        // of the dividend, and since `yc < LIMBS`, we only need to access
355        // the high half of the dividend.
356        //
357        // So we proceed similarly to `div_rem_vartime()` applied to the high half of the dividend,
358        // fetching the limbs from the lower part as we go.
359
360        loop {
361            // Divide high dividend words by the high divisor word to estimate the quotient word
362            let quo = div3by2(x_hi.0, x[xi].0, x[xi - 1].0, &reciprocal, y[yc - 2].0);
363
364            // Subtract q*divisor from the dividend
365            let borrow = {
366                let mut carry = Limb::ZERO;
367                let mut borrow = Limb::ZERO;
368                let mut tmp;
369                i = 0;
370                while i < yc {
371                    (tmp, carry) = Limb::ZERO.mac(y[i], Limb(quo), carry);
372                    (x[xi + i + 1 - yc], borrow) = x[xi + i + 1 - yc].sbb(tmp, borrow);
373                    i += 1;
374                }
375                (_, borrow) = x_hi.sbb(carry, borrow);
376                borrow
377            };
378
379            // If the subtraction borrowed, then add back the divisor
380            // The probability of this being needed is very low, about 2/(Limb::MAX+1)
381            {
382                let ct_borrow = ConstChoice::from_word_mask(borrow.0);
383                let mut carry = Limb::ZERO;
384                i = 0;
385                while i < yc {
386                    (x[xi + i + 1 - yc], carry) =
387                        x[xi + i + 1 - yc].adc(Limb::select(Limb::ZERO, y[i], ct_borrow), carry);
388                    i += 1;
389                }
390            }
391
392            // Set x_hi to the current highest word
393            x_hi = x[xi];
394
395            // If we have lower limbs remaining, shift the divisor words one word left
396            if extra_limbs > 0 {
397                extra_limbs -= 1;
398                i = LIMBS - 1;
399                while i > 0 {
400                    x[i] = x[i - 1];
401                    i -= 1;
402                }
403                x[0] = x_lo.limbs[extra_limbs];
404            } else {
405                if xi == yc - 1 {
406                    break;
407                }
408                x[xi] = Limb::ZERO;
409                xi -= 1;
410            }
411        }
412
413        // Unshift the remainder from the earlier adjustment
414        Uint::new(x).shr_limb_vartime(shift, yc)
415    }
416
417    /// Computes `self` % 2^k. Faster than reduce since its a power of 2.
418    /// Limited to 2^16-1 since Uint doesn't support higher.
419    ///
420    /// ### Usage:
421    /// ```
422    /// use crypto_bigint::{U448, Limb};
423    ///
424    /// let a = U448::from(10_u64);
425    /// let k = 3; // 2^3 = 8
426    /// let remainder = a.rem2k_vartime(k);
427    ///
428    /// // As 10 % 8 = 2
429    /// assert_eq!(remainder, U448::from(2_u64));
430    /// ```
431    pub const fn rem2k_vartime(&self, k: u32) -> Self {
432        let highest = (LIMBS - 1) as u32;
433        let index = k / Limb::BITS;
434        let le = ConstChoice::from_u32_le(index, highest);
435        let limb_num = le.select_u32(highest, index) as usize;
436
437        let base = k % Limb::BITS;
438        let mask = (1 << base) - 1;
439        let mut out = *self;
440
441        let outmask = Limb(out.limbs[limb_num].0 & mask);
442
443        out.limbs[limb_num] = Limb::select(out.limbs[limb_num], outmask, le);
444
445        // TODO: this is not constant-time.
446        let mut i = limb_num + 1;
447        while i < LIMBS {
448            out.limbs[i] = Limb::ZERO;
449            i += 1;
450        }
451
452        out
453    }
454
455    /// Wrapped division is just normal division i.e. `self` / `rhs`
456    ///
457    /// There’s no way wrapping could ever happen.
458    /// This function exists, so that all operations are accounted for in the wrapping operations.
459    pub const fn wrapping_div(&self, rhs: &NonZero<Self>) -> Self {
460        self.div_rem(rhs).0
461    }
462
463    /// Wrapped division is just normal division i.e. `self` / `rhs`
464    ///
465    /// There’s no way wrapping could ever happen.
466    /// This function exists, so that all operations are accounted for in the wrapping operations.
467    pub const fn wrapping_div_vartime<const RHS: usize>(&self, rhs: &NonZero<Uint<RHS>>) -> Self {
468        self.div_rem_vartime(rhs).0
469    }
470
471    /// Perform checked division, returning a [`CtOption`] which `is_some`
472    /// only if the rhs != 0
473    ///
474    /// ### Usage:
475    /// ```
476    /// use crypto_bigint::{U448, NonZero, subtle::{CtOption, Choice}};
477    ///
478    /// let a = U448::from(8_u64);
479    /// let result = NonZero::new(U448::from(4_u64))
480    ///     .map(|b| a.div_rem(&b))
481    ///     .expect("Division by zero");
482    ///
483    /// assert_eq!(result.0, U448::from(2_u64));
484    ///
485    /// // Check division by zero
486    /// let zero = U448::from(0_u64);
487    /// assert!(bool::from(a.checked_div(&zero).is_none()), "Should be None for division by zero");
488    /// ```
489    pub fn checked_div(&self, rhs: &Self) -> CtOption<Self> {
490        NonZero::new(*rhs).map(|rhs| {
491            let (q, _r) = self.div_rem(&rhs);
492            q
493        })
494    }
495
496    /// This function exists, so that all operations are accounted for in the wrapping operations.
497    /// Panics if `rhs == 0`.
498    ///
499    /// ### Usage:
500    /// ```
501    /// use crypto_bigint::U448;
502    ///
503    /// let a = U448::from(10_u64);
504    /// let b = U448::from(3_u64);
505    /// let remainder = a.wrapping_rem_vartime(&b);
506    ///
507    /// assert_eq!(remainder, U448::from(1_u64));
508    /// ```
509    pub const fn wrapping_rem_vartime(&self, rhs: &Self) -> Self {
510        let nz_rhs = rhs.to_nz().expect("non-zero divisor");
511        self.rem_vartime(&nz_rhs)
512    }
513
514    /// Perform checked reduction, returning a [`CtOption`] which `is_some`
515    /// only if the rhs != 0
516    ///
517    /// ### Usage:
518    /// ```
519    /// use crypto_bigint::{U448, NonZero, subtle::{Choice,CtOption}};
520    ///
521    /// let a = U448::from(10_u64);
522    /// let remainder_option = NonZero::new(U448::from(3_u64))
523    ///     .map(|b| a.rem(&b));
524    ///
525    /// assert!(bool::from(remainder_option.is_some()));
526    ///
527    /// // Check reduction by zero
528    /// let zero = U448::from(0_u64);
529    ///
530    /// assert!(bool::from(a.checked_rem(&zero).is_none()), "Should be None for reduction by zero");
531    /// ```
532    pub fn checked_rem(&self, rhs: &Self) -> CtOption<Self> {
533        NonZero::new(*rhs).map(|rhs| self.rem(&rhs))
534    }
535}
536
537//
538// Division by a single limb
539//
540
541impl<const LIMBS: usize> Div<&NonZero<Limb>> for &Uint<LIMBS> {
542    type Output = Uint<LIMBS>;
543
544    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
545        *self / *rhs
546    }
547}
548
549impl<const LIMBS: usize> Div<&NonZero<Limb>> for Uint<LIMBS> {
550    type Output = Uint<LIMBS>;
551
552    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
553        self / *rhs
554    }
555}
556
557impl<const LIMBS: usize> Div<NonZero<Limb>> for &Uint<LIMBS> {
558    type Output = Uint<LIMBS>;
559
560    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
561        *self / rhs
562    }
563}
564
565impl<const LIMBS: usize> Div<NonZero<Limb>> for Uint<LIMBS> {
566    type Output = Uint<LIMBS>;
567
568    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
569        let (q, _) = self.div_rem_limb(rhs);
570        q
571    }
572}
573
574impl<const LIMBS: usize> DivAssign<&NonZero<Limb>> for Uint<LIMBS> {
575    fn div_assign(&mut self, rhs: &NonZero<Limb>) {
576        *self /= *rhs;
577    }
578}
579
580impl<const LIMBS: usize> DivAssign<NonZero<Limb>> for Uint<LIMBS> {
581    fn div_assign(&mut self, rhs: NonZero<Limb>) {
582        *self = *self / rhs;
583    }
584}
585
586impl<const LIMBS: usize> Div<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
587    type Output = Wrapping<Uint<LIMBS>>;
588
589    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
590        Wrapping(self.0 / rhs)
591    }
592}
593
594impl<const LIMBS: usize> Div<NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
595    type Output = Wrapping<Uint<LIMBS>>;
596
597    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
598        *self / rhs
599    }
600}
601
602impl<const LIMBS: usize> Div<&NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
603    type Output = Wrapping<Uint<LIMBS>>;
604
605    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
606        *self / *rhs
607    }
608}
609
610impl<const LIMBS: usize> Div<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
611    type Output = Wrapping<Uint<LIMBS>>;
612
613    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
614        self / *rhs
615    }
616}
617
618impl<const LIMBS: usize> DivAssign<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
619    fn div_assign(&mut self, rhs: &NonZero<Limb>) {
620        *self = Wrapping(self.0 / rhs)
621    }
622}
623
624impl<const LIMBS: usize> DivAssign<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
625    fn div_assign(&mut self, rhs: NonZero<Limb>) {
626        *self /= &rhs;
627    }
628}
629
630impl<const LIMBS: usize> Rem<&NonZero<Limb>> for &Uint<LIMBS> {
631    type Output = Limb;
632
633    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
634        *self % *rhs
635    }
636}
637
638impl<const LIMBS: usize> Rem<&NonZero<Limb>> for Uint<LIMBS> {
639    type Output = Limb;
640
641    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
642        self % *rhs
643    }
644}
645
646impl<const LIMBS: usize> Rem<NonZero<Limb>> for &Uint<LIMBS> {
647    type Output = Limb;
648
649    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
650        *self % rhs
651    }
652}
653
654impl<const LIMBS: usize> Rem<NonZero<Limb>> for Uint<LIMBS> {
655    type Output = Limb;
656
657    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
658        let (_, r) = self.div_rem_limb(rhs);
659        r
660    }
661}
662
663impl<const LIMBS: usize> RemAssign<&NonZero<Limb>> for Uint<LIMBS> {
664    fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
665        *self = (*self % rhs).into();
666    }
667}
668
669impl<const LIMBS: usize> RemAssign<NonZero<Limb>> for Uint<LIMBS> {
670    fn rem_assign(&mut self, rhs: NonZero<Limb>) {
671        *self %= &rhs;
672    }
673}
674
675impl<const LIMBS: usize> Rem<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
676    type Output = Wrapping<Limb>;
677
678    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
679        Wrapping(self.0 % rhs)
680    }
681}
682
683impl<const LIMBS: usize> Rem<NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
684    type Output = Wrapping<Limb>;
685
686    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
687        *self % rhs
688    }
689}
690
691impl<const LIMBS: usize> Rem<&NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
692    type Output = Wrapping<Limb>;
693
694    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
695        *self % *rhs
696    }
697}
698
699impl<const LIMBS: usize> Rem<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
700    type Output = Wrapping<Limb>;
701
702    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
703        self % *rhs
704    }
705}
706
707impl<const LIMBS: usize> RemAssign<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
708    fn rem_assign(&mut self, rhs: NonZero<Limb>) {
709        *self %= &rhs;
710    }
711}
712
713impl<const LIMBS: usize> RemAssign<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
714    fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
715        *self = Wrapping((self.0 % rhs).into())
716    }
717}
718
719//
720// Division by an Uint
721//
722
723impl<const LIMBS: usize> CheckedDiv for Uint<LIMBS> {
724    fn checked_div(&self, rhs: &Uint<LIMBS>) -> CtOption<Self> {
725        self.checked_div(rhs)
726    }
727}
728
729impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
730    type Output = Uint<LIMBS>;
731
732    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
733        *self / *rhs
734    }
735}
736
737impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
738    type Output = Uint<LIMBS>;
739
740    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
741        self / *rhs
742    }
743}
744
745impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
746    type Output = Uint<LIMBS>;
747
748    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
749        *self / rhs
750    }
751}
752
753impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
754    type Output = Uint<LIMBS>;
755
756    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
757        let (q, _) = self.div_rem(&rhs);
758        q
759    }
760}
761
762impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
763    fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
764        *self /= *rhs
765    }
766}
767
768impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
769    fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
770        *self = *self / rhs;
771    }
772}
773
774impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
775    type Output = Wrapping<Uint<LIMBS>>;
776
777    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
778        Wrapping(self.0 / rhs)
779    }
780}
781
782impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
783    type Output = Wrapping<Uint<LIMBS>>;
784
785    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
786        *self / rhs
787    }
788}
789
790impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
791    type Output = Wrapping<Uint<LIMBS>>;
792
793    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
794        *self / *rhs
795    }
796}
797
798impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
799    type Output = Wrapping<Uint<LIMBS>>;
800
801    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
802        self / *rhs
803    }
804}
805
806impl<const LIMBS: usize> Div<Uint<LIMBS>> for &Uint<LIMBS> {
807    type Output = Uint<LIMBS>;
808
809    #[inline]
810    fn div(self, rhs: Uint<LIMBS>) -> Self::Output {
811        self / NonZero::new(rhs).expect("attempt to divide with a divisor of zero")
812    }
813}
814
815impl<const LIMBS: usize> Div<Uint<LIMBS>> for Uint<LIMBS> {
816    type Output = Uint<LIMBS>;
817
818    #[inline]
819    fn div(self, rhs: Uint<LIMBS>) -> Self::Output {
820        &self / rhs
821    }
822}
823
824impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
825    fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
826        *self = Wrapping(self.0 / rhs);
827    }
828}
829
830impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
831    fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
832        *self /= &rhs;
833    }
834}
835
836impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
837    type Output = Uint<LIMBS>;
838
839    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
840        *self % *rhs
841    }
842}
843
844impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
845    type Output = Uint<LIMBS>;
846
847    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
848        self % *rhs
849    }
850}
851
852impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
853    type Output = Uint<LIMBS>;
854
855    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
856        *self % rhs
857    }
858}
859
860impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
861    type Output = Uint<LIMBS>;
862
863    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
864        Self::rem(&self, &rhs)
865    }
866}
867
868impl<const LIMBS: usize> Rem<Uint<LIMBS>> for &Uint<LIMBS> {
869    type Output = Uint<LIMBS>;
870
871    #[inline]
872    fn rem(self, rhs: Uint<LIMBS>) -> Self::Output {
873        self % NonZero::new(rhs).expect("attempt to calculate the remainder with a divisor of zero")
874    }
875}
876
877impl<const LIMBS: usize> Rem<Uint<LIMBS>> for Uint<LIMBS> {
878    type Output = Uint<LIMBS>;
879
880    #[inline]
881    fn rem(self, rhs: Uint<LIMBS>) -> Self::Output {
882        &self % rhs
883    }
884}
885
886impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
887    fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
888        *self %= *rhs
889    }
890}
891
892impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
893    fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
894        *self = *self % rhs;
895    }
896}
897
898impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
899    type Output = Wrapping<Uint<LIMBS>>;
900
901    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
902        Wrapping(self.0 % rhs)
903    }
904}
905
906impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
907    type Output = Wrapping<Uint<LIMBS>>;
908
909    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
910        *self % rhs
911    }
912}
913
914impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
915    type Output = Wrapping<Uint<LIMBS>>;
916
917    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
918        *self % *rhs
919    }
920}
921
922impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
923    type Output = Wrapping<Uint<LIMBS>>;
924
925    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
926        self % *rhs
927    }
928}
929
930impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
931    fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
932        *self %= &rhs;
933    }
934}
935
936impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
937    fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
938        *self = Wrapping(self.0 % rhs)
939    }
940}
941
942impl<const LIMBS: usize> DivRemLimb for Uint<LIMBS> {
943    fn div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
944        Self::div_rem_limb_with_reciprocal(self, reciprocal)
945    }
946}
947
948impl<const LIMBS: usize> RemLimb for Uint<LIMBS> {
949    fn rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> Limb {
950        Self::rem_limb_with_reciprocal(self, reciprocal)
951    }
952}
953
954#[cfg(test)]
955mod tests {
956    use crate::{Limb, NonZero, RemMixed, Uint, Word, Zero, U1024, U128, U256, U64, U896};
957
958    #[cfg(feature = "rand")]
959    use {
960        crate::{CheckedMul, Random},
961        rand_chacha::ChaChaRng,
962        rand_core::RngCore,
963        rand_core::SeedableRng,
964    };
965
966    #[test]
967    fn div_word() {
968        for (n, d, e, ee) in &[
969            (200u64, 2u64, 100u64, 0),
970            (100u64, 25u64, 4u64, 0),
971            (100u64, 10u64, 10u64, 0),
972            (1024u64, 8u64, 128u64, 0),
973            (27u64, 13u64, 2u64, 1u64),
974            (26u64, 13u64, 2u64, 0u64),
975            (14u64, 13u64, 1u64, 1u64),
976            (13u64, 13u64, 1u64, 0u64),
977            (12u64, 13u64, 0u64, 12u64),
978            (1u64, 13u64, 0u64, 1u64),
979        ] {
980            let lhs = U256::from(*n);
981            let rhs = NonZero::new(U256::from(*d)).unwrap();
982            let (q, r) = lhs.div_rem(&rhs);
983            assert_eq!(U256::from(*e), q);
984            assert_eq!(U256::from(*ee), r);
985            let (q, r) = lhs.div_rem_vartime(&rhs);
986            assert_eq!(U256::from(*e), q);
987            assert_eq!(U256::from(*ee), r);
988        }
989    }
990
991    #[cfg(feature = "rand")]
992    #[test]
993    fn div() {
994        let mut rng = ChaChaRng::from_seed([7u8; 32]);
995        for _ in 0..25 {
996            let num = U256::random(&mut rng).overflowing_shr_vartime(128).unwrap();
997            let den =
998                NonZero::new(U256::random(&mut rng).overflowing_shr_vartime(128).unwrap()).unwrap();
999            let n = num.checked_mul(den.as_ref());
1000            if n.is_some().into() {
1001                let (q, _) = n.unwrap().div_rem(&den);
1002                assert_eq!(q, num);
1003                let (q, _) = n.unwrap().div_rem_vartime(&den);
1004                assert_eq!(q, num);
1005            }
1006        }
1007    }
1008
1009    #[test]
1010    fn div_max() {
1011        let mut a = U256::ZERO;
1012        let mut b = U256::ZERO;
1013        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
1014        let q = a.wrapping_div(&NonZero::new(b).unwrap());
1015        assert_eq!(q, Uint::ZERO);
1016        a.limbs[a.limbs.len() - 1] = Limb(1 << (Limb::HI_BIT - 7));
1017        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (Limb::HI_BIT - 7));
1018        let q = a.wrapping_div(&NonZero::new(b).unwrap());
1019        assert_eq!(q, Uint::ZERO);
1020    }
1021
1022    #[test]
1023    fn div_one() {
1024        let (q, r) = U256::from(10u8).div_rem(&NonZero::new(U256::ONE).unwrap());
1025        assert_eq!(q, U256::from(10u8));
1026        assert_eq!(r, U256::ZERO);
1027        let (q, r) = U256::from(10u8).div_rem_vartime(&NonZero::new(U256::ONE).unwrap());
1028        assert_eq!(q, U256::from(10u8));
1029        assert_eq!(r, U256::ZERO);
1030    }
1031
1032    #[test]
1033    fn div_edge() {
1034        let lo = U128::from_be_hex("00000000000000000000000000000001");
1035        let hi = U128::from_be_hex("00000000000000000000000000000001");
1036        let y = U128::from_be_hex("00000000000000010000000000000001");
1037        let x = U256::from((lo, hi));
1038        let expect = (U64::MAX.resize::<{ U256::LIMBS }>(), U256::from(2u64));
1039
1040        let (q1, r1) = Uint::div_rem(&x, &NonZero::new(y.resize()).unwrap());
1041        assert_eq!((q1, r1), expect);
1042        let (q2, r2) = Uint::div_rem_vartime(&x, &NonZero::new(y).unwrap());
1043        assert_eq!((q2, r2.resize()), expect);
1044        let r3 = Uint::rem(&x, &NonZero::new(y.resize()).unwrap());
1045        assert_eq!(r3, expect.1);
1046        let r4 = Uint::rem_vartime(&x, &NonZero::new(y.resize()).unwrap());
1047        assert_eq!(r4, expect.1);
1048        let r5 = Uint::rem_wide_vartime((lo, hi), &NonZero::new(y).unwrap());
1049        assert_eq!(r5.resize(), expect.1);
1050    }
1051
1052    #[test]
1053    fn reduce_one() {
1054        let r = U256::from(10u8).rem_vartime(&NonZero::new(U256::ONE).unwrap());
1055        assert_eq!(r, U256::ZERO);
1056    }
1057
1058    #[test]
1059    fn reduce_tests() {
1060        let r = U256::from(10u8).rem_vartime(&NonZero::new(U256::from(2u8)).unwrap());
1061        assert_eq!(r, U256::ZERO);
1062        let r = U256::from(10u8).rem_vartime(&NonZero::new(U256::from(3u8)).unwrap());
1063        assert_eq!(r, U256::ONE);
1064        let r = U256::from(10u8).rem_vartime(&NonZero::new(U256::from(7u8)).unwrap());
1065        assert_eq!(r, U256::from(3u8));
1066    }
1067
1068    #[test]
1069    fn reduce_tests_wide_zero_padded() {
1070        let r = U256::rem_wide_vartime(
1071            (U256::from(10u8), U256::ZERO),
1072            &NonZero::new(U256::from(2u8)).unwrap(),
1073        );
1074        assert_eq!(r, U256::ZERO);
1075        let r = U256::rem_wide_vartime(
1076            (U256::from(10u8), U256::ZERO),
1077            &NonZero::new(U256::from(3u8)).unwrap(),
1078        );
1079        assert_eq!(r, U256::ONE);
1080        let r = U256::rem_wide_vartime(
1081            (U256::from(10u8), U256::ZERO),
1082            &NonZero::new(U256::from(7u8)).unwrap(),
1083        );
1084        assert_eq!(r, U256::from(3u8));
1085        let r = U256::rem_wide_vartime(
1086            (U256::from(10u8), U256::ZERO),
1087            &NonZero::new(U256::MAX).unwrap(),
1088        );
1089        assert_eq!(r, U256::from(10u8));
1090    }
1091
1092    #[test]
1093    fn rem_wide_vartime_corner_case() {
1094        let modulus = "0000000000000000000000000000000081000000000000000000000000000001";
1095        let modulus = NonZero::new(U256::from_be_hex(modulus)).expect("it's odd and not zero");
1096        let lo_hi = (
1097            U256::from_be_hex("1000000000000000000000000000000000000000000000000000000000000001"),
1098            U256::ZERO,
1099        );
1100        let rem = U256::rem_wide_vartime(lo_hi, &modulus);
1101        // Lower half is zero
1102        assert_eq!(rem.to_be_bytes()[0..16], U128::ZERO.to_be_bytes());
1103        // Upper half
1104        let expected = U128::from_be_hex("203F80FE03F80FE03F80FE03F80FE041");
1105        assert_eq!(rem.to_be_bytes()[16..], expected.to_be_bytes());
1106    }
1107
1108    #[test]
1109    fn reduce_max() {
1110        let mut a = U256::ZERO;
1111        let mut b = U256::ZERO;
1112        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
1113        let r = a.wrapping_rem_vartime(&b);
1114        assert_eq!(r, Uint::ZERO);
1115        a.limbs[a.limbs.len() - 1] = Limb(1 << (Limb::HI_BIT - 7));
1116        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (Limb::HI_BIT - 7));
1117        let r = a.wrapping_rem_vartime(&b);
1118        assert_eq!(r, a);
1119    }
1120
1121    #[cfg(feature = "rand")]
1122    #[test]
1123    fn rem2krand() {
1124        let mut rng = ChaChaRng::from_seed([7u8; 32]);
1125        for _ in 0..25 {
1126            let num = U256::random(&mut rng);
1127            let k = rng.next_u32() % 256;
1128            let den = U256::ONE.overflowing_shl_vartime(k).unwrap();
1129
1130            let a = num.rem2k_vartime(k);
1131            let e = num.wrapping_rem_vartime(&den);
1132            assert_eq!(a, e);
1133        }
1134    }
1135
1136    #[allow(clippy::op_ref)]
1137    #[test]
1138    fn rem_trait() {
1139        let a = U256::from(10u64);
1140        let b = NonZero::new(U256::from(3u64)).unwrap();
1141        let c = U256::from(1u64);
1142
1143        assert_eq!(a % b, c);
1144        assert_eq!(a % &b, c);
1145        assert_eq!(&a % b, c);
1146        assert_eq!(&a % &b, c);
1147    }
1148
1149    #[test]
1150    fn rem_mixed() {
1151        let x = U1024::from_be_hex("3740C11DB8F260753BC6B97DD2B8746D3E2694412772AC6ABD975119EE0A6190F27F6F0969BCA069D8D151031AF83EE2283CC2E3E4FADBBDB9EEDBF0B8F4C1FD51912C0D329FDC37D49176DB0A1A2D17E5E6D4F9F6B217FE9412EAA2F881F7027A831C1B06D31D3618D218D6E667DBD85BFC7B6B6B93422D52516989376AA29A");
1152        let y = U128::from_u64(1234567890987654321);
1153        let rem = x.rem_mixed(&y.to_nz().unwrap());
1154
1155        let y2: U1024 = U128::concat_mixed(&y, &U896::ZERO);
1156        let rem_control = x.rem(&NonZero::new(y2).unwrap());
1157
1158        assert_eq!(rem.bits(), rem_control.bits());
1159        assert_eq!(rem.as_words(), &rem_control.as_words()[0..U128::LIMBS]);
1160        assert!(rem_control.as_words()[U128::LIMBS..]
1161            .iter()
1162            .all(|w| *w == 0));
1163    }
1164
1165    #[test]
1166    fn rem_mixed_through_traits() {
1167        struct A<T, U> {
1168            t: T,
1169            u: U,
1170        }
1171        impl<T, U> A<T, U>
1172        where
1173            T: RemMixed<U>,
1174            U: Clone + Zero,
1175        {
1176            fn reduce_t_by_u(&self) -> U {
1177                let rhs = &NonZero::new(self.u.clone()).unwrap();
1178                self.t.rem_mixed(rhs)
1179            }
1180        }
1181
1182        let a = A {
1183            t: U1024::from(1234567890u64),
1184            u: U128::from(456u64),
1185        };
1186        assert_eq!(a.reduce_t_by_u(), U128::from(330u64));
1187    }
1188}
crypto_bigint/uint/div.rs

crypto_bigint/uint/
div.rs
