crypto_bigint/uint/
div.rs

Help
1//! [`UInt`] division operations.
2
3use super::UInt;
4use crate::limb::Word;
5use crate::{Integer, Limb, NonZero, Wrapping};
6use core::ops::{Div, DivAssign, Rem, RemAssign};
7use subtle::{Choice, CtOption};
8
9impl<const LIMBS: usize> UInt<LIMBS> {
10    /// Computes `self` / `rhs`, returns the quotient (q), remainder (r)
11    /// and 1 for is_some or 0 for is_none. The results can be wrapped in [`CtOption`].
12    /// NOTE: Use only if you need to access const fn. Otherwise use `div_rem` because
13    /// the value for is_some needs to be checked before using `q` and `r`.
14    ///
15    /// This is variable only with respect to `rhs`.
16    ///
17    /// When used with a fixed `rhs`, this function is constant-time with respect
18    /// to `self`.
19    pub(crate) const fn ct_div_rem(&self, rhs: &Self) -> (Self, Self, u8) {
20        let mb = rhs.bits_vartime();
21        let mut bd = (LIMBS * Limb::BIT_SIZE) - mb;
22        let mut rem = *self;
23        let mut quo = Self::ZERO;
24        let mut c = rhs.shl_vartime(bd);
25
26        loop {
27            let (mut r, borrow) = rem.sbb(&c, Limb::ZERO);
28            rem = Self::ct_select(r, rem, borrow.0);
29            r = quo.bitor(&Self::ONE);
30            quo = Self::ct_select(r, quo, borrow.0);
31            if bd == 0 {
32                break;
33            }
34            bd -= 1;
35            c = c.shr_vartime(1);
36            quo = quo.shl_vartime(1);
37        }
38
39        let is_some = Limb(mb as Word).is_nonzero();
40        quo = Self::ct_select(Self::ZERO, quo, is_some);
41        (quo, rem, (is_some & 1) as u8)
42    }
43
44    /// Computes `self` % `rhs`, returns the remainder and
45    /// and 1 for is_some or 0 for is_none. The results can be wrapped in [`CtOption`].
46    /// NOTE: Use only if you need to access const fn. Otherwise use `reduce`
47    /// This is variable only with respect to `rhs`.
48    ///
49    /// When used with a fixed `rhs`, this function is constant-time with respect
50    /// to `self`.
51    pub(crate) const fn ct_reduce(&self, rhs: &Self) -> (Self, u8) {
52        let mb = rhs.bits_vartime();
53        let mut bd = (LIMBS * Limb::BIT_SIZE) - mb;
54        let mut rem = *self;
55        let mut c = rhs.shl_vartime(bd);
56
57        loop {
58            let (r, borrow) = rem.sbb(&c, Limb::ZERO);
59            rem = Self::ct_select(r, rem, borrow.0);
60            if bd == 0 {
61                break;
62            }
63            bd -= 1;
64            c = c.shr_vartime(1);
65        }
66
67        let is_some = Limb(mb as Word).is_nonzero();
68        (rem, (is_some & 1) as u8)
69    }
70
71    /// Computes `self` % 2^k. Faster than reduce since its a power of 2.
72    /// Limited to 2^16-1 since UInt doesn't support higher.
73    pub const fn reduce2k(&self, k: usize) -> Self {
74        let highest = (LIMBS - 1) as u32;
75        let index = k as u32 / (Limb::BIT_SIZE as u32);
76        let res = Limb::ct_cmp(Limb::from_u32(index), Limb::from_u32(highest)) - 1;
77        let le = Limb::is_nonzero(Limb(res as Word));
78        let word = Limb::ct_select(Limb::from_u32(highest), Limb::from_u32(index), le).0 as usize;
79
80        let base = k % Limb::BIT_SIZE;
81        let mask = (1 << base) - 1;
82        let mut out = *self;
83
84        let outmask = Limb(out.limbs[word].0 & mask);
85
86        out.limbs[word] = Limb::ct_select(out.limbs[word], outmask, le);
87
88        let mut i = word + 1;
89        while i < LIMBS {
90            out.limbs[i] = Limb::ZERO;
91            i += 1;
92        }
93
94        out
95    }
96
97    /// Computes self / rhs, returns the quotient, remainder
98    /// if rhs != 0
99    pub fn div_rem(&self, rhs: &Self) -> CtOption<(Self, Self)> {
100        let (q, r, c) = self.ct_div_rem(rhs);
101        CtOption::new((q, r), Choice::from(c))
102    }
103
104    /// Computes self % rhs, returns the remainder
105    /// if rhs != 0
106    pub fn reduce(&self, rhs: &Self) -> CtOption<Self> {
107        let (r, c) = self.ct_reduce(rhs);
108        CtOption::new(r, Choice::from(c))
109    }
110
111    /// Wrapped division is just normal division i.e. `self` / `rhs`
112    /// There’s no way wrapping could ever happen.
113    /// This function exists, so that all operations are accounted for in the wrapping operations.
114    pub const fn wrapping_div(&self, rhs: &Self) -> Self {
115        let (q, _, c) = self.ct_div_rem(rhs);
116        assert!(c == 1, "divide by zero");
117        q
118    }
119
120    /// Perform checked division, returning a [`CtOption`] which `is_some`
121    /// only if the rhs != 0
122    pub fn checked_div(&self, rhs: &Self) -> CtOption<Self> {
123        let (q, _, c) = self.ct_div_rem(rhs);
124        CtOption::new(q, Choice::from(c))
125    }
126
127    /// Wrapped (modular) remainder calculation is just `self` % `rhs`.
128    /// There’s no way wrapping could ever happen.
129    /// This function exists, so that all operations are accounted for in the wrapping operations.
130    pub const fn wrapping_rem(&self, rhs: &Self) -> Self {
131        let (r, c) = self.ct_reduce(rhs);
132        assert!(c == 1, "modulo zero");
133        r
134    }
135
136    /// Perform checked reduction, returning a [`CtOption`] which `is_some`
137    /// only if the rhs != 0
138    pub fn checked_rem(&self, rhs: &Self) -> CtOption<Self> {
139        let (r, c) = self.ct_reduce(rhs);
140        CtOption::new(r, Choice::from(c))
141    }
142}
143
144impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
145where
146    UInt<LIMBS>: Integer,
147{
148    type Output = UInt<LIMBS>;
149
150    fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
151        *self / *rhs
152    }
153}
154
155impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
156where
157    UInt<LIMBS>: Integer,
158{
159    type Output = UInt<LIMBS>;
160
161    fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
162        self / *rhs
163    }
164}
165
166impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
167where
168    UInt<LIMBS>: Integer,
169{
170    type Output = UInt<LIMBS>;
171
172    fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
173        *self / rhs
174    }
175}
176
177impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
178where
179    UInt<LIMBS>: Integer,
180{
181    type Output = UInt<LIMBS>;
182
183    fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
184        let (q, _, _) = self.ct_div_rem(&rhs);
185        q
186    }
187}
188
189impl<const LIMBS: usize> DivAssign<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
190where
191    UInt<LIMBS>: Integer,
192{
193    fn div_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
194        let (q, _, _) = self.ct_div_rem(rhs);
195        *self = q
196    }
197}
198
199impl<const LIMBS: usize> DivAssign<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
200where
201    UInt<LIMBS>: Integer,
202{
203    fn div_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
204        *self /= &rhs;
205    }
206}
207
208impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
209    type Output = Wrapping<UInt<LIMBS>>;
210
211    fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
212        Wrapping(self.0.wrapping_div(rhs.as_ref()))
213    }
214}
215
216impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
217    type Output = Wrapping<UInt<LIMBS>>;
218
219    fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
220        *self / rhs
221    }
222}
223
224impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
225    type Output = Wrapping<UInt<LIMBS>>;
226
227    fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
228        *self / *rhs
229    }
230}
231
232impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
233    type Output = Wrapping<UInt<LIMBS>>;
234
235    fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
236        self / *rhs
237    }
238}
239
240impl<const LIMBS: usize> DivAssign<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
241    fn div_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
242        *self = Wrapping(self.0.wrapping_div(rhs.as_ref()))
243    }
244}
245
246impl<const LIMBS: usize> DivAssign<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
247    fn div_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
248        *self /= &rhs;
249    }
250}
251
252impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
253where
254    UInt<LIMBS>: Integer,
255{
256    type Output = UInt<LIMBS>;
257
258    fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
259        *self % *rhs
260    }
261}
262
263impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
264where
265    UInt<LIMBS>: Integer,
266{
267    type Output = UInt<LIMBS>;
268
269    fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
270        self % *rhs
271    }
272}
273
274impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
275where
276    UInt<LIMBS>: Integer,
277{
278    type Output = UInt<LIMBS>;
279
280    fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
281        *self % rhs
282    }
283}
284
285impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
286where
287    UInt<LIMBS>: Integer,
288{
289    type Output = UInt<LIMBS>;
290
291    fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
292        let (r, _) = self.ct_reduce(&rhs);
293        r
294    }
295}
296
297impl<const LIMBS: usize> RemAssign<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
298where
299    UInt<LIMBS>: Integer,
300{
301    fn rem_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
302        let (r, _) = self.ct_reduce(rhs);
303        *self = r
304    }
305}
306
307impl<const LIMBS: usize> RemAssign<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
308where
309    UInt<LIMBS>: Integer,
310{
311    fn rem_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
312        *self %= &rhs;
313    }
314}
315
316impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
317    type Output = Wrapping<UInt<LIMBS>>;
318
319    fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
320        Wrapping(self.0.wrapping_rem(rhs.as_ref()))
321    }
322}
323
324impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
325    type Output = Wrapping<UInt<LIMBS>>;
326
327    fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
328        *self % rhs
329    }
330}
331
332impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
333    type Output = Wrapping<UInt<LIMBS>>;
334
335    fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
336        *self % *rhs
337    }
338}
339
340impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
341    type Output = Wrapping<UInt<LIMBS>>;
342
343    fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
344        self % *rhs
345    }
346}
347
348impl<const LIMBS: usize> RemAssign<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
349    fn rem_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
350        *self %= &rhs;
351    }
352}
353
354impl<const LIMBS: usize> RemAssign<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
355    fn rem_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
356        *self = Wrapping(self.0.wrapping_rem(rhs.as_ref()))
357    }
358}
359
360#[cfg(test)]
361mod tests {
362    use super::*;
363    use crate::{limb::HI_BIT, Limb, U256};
364
365    #[cfg(feature = "rand")]
366    use {
367        crate::{CheckedMul, Random},
368        rand_chacha::ChaChaRng,
369        rand_core::RngCore,
370        rand_core::SeedableRng,
371    };
372
373    #[test]
374    fn div_word() {
375        for (n, d, e, ee) in &[
376            (200u64, 2u64, 100u64, 0),
377            (100u64, 25u64, 4u64, 0),
378            (100u64, 10u64, 10u64, 0),
379            (1024u64, 8u64, 128u64, 0),
380            (27u64, 13u64, 2u64, 1u64),
381            (26u64, 13u64, 2u64, 0u64),
382            (14u64, 13u64, 1u64, 1u64),
383            (13u64, 13u64, 1u64, 0u64),
384            (12u64, 13u64, 0u64, 12u64),
385            (1u64, 13u64, 0u64, 1u64),
386        ] {
387            let lhs = U256::from(*n);
388            let rhs = U256::from(*d);
389            let (q, r, is_some) = lhs.ct_div_rem(&rhs);
390            assert_eq!(is_some, 1);
391            assert_eq!(U256::from(*e), q);
392            assert_eq!(U256::from(*ee), r);
393        }
394    }
395
396    #[cfg(feature = "rand")]
397    #[test]
398    fn div() {
399        let mut rng = ChaChaRng::from_seed([7u8; 32]);
400        for _ in 0..25 {
401            let num = U256::random(&mut rng).shr_vartime(128);
402            let den = U256::random(&mut rng).shr_vartime(128);
403            let n = num.checked_mul(&den);
404            if n.is_some().unwrap_u8() == 1 {
405                let (q, _, is_some) = n.unwrap().ct_div_rem(&den);
406                assert_eq!(is_some, 1);
407                assert_eq!(q, num);
408            }
409        }
410    }
411
412    #[test]
413    fn div_max() {
414        let mut a = U256::ZERO;
415        let mut b = U256::ZERO;
416        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
417        let q = a.wrapping_div(&b);
418        assert_eq!(q, UInt::ZERO);
419        a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
420        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
421        let q = a.wrapping_div(&b);
422        assert_eq!(q, UInt::ZERO);
423    }
424
425    #[test]
426    fn div_zero() {
427        let (q, r, is_some) = U256::ONE.ct_div_rem(&U256::ZERO);
428        assert_eq!(is_some, 0);
429        assert_eq!(q, U256::ZERO);
430        assert_eq!(r, U256::ONE);
431    }
432
433    #[test]
434    fn div_one() {
435        let (q, r, is_some) = U256::from(10u8).ct_div_rem(&U256::ONE);
436        assert_eq!(is_some, 1);
437        assert_eq!(q, U256::from(10u8));
438        assert_eq!(r, U256::ZERO);
439    }
440
441    #[test]
442    fn reduce_one() {
443        let (r, is_some) = U256::from(10u8).ct_reduce(&U256::ONE);
444        assert_eq!(is_some, 1);
445        assert_eq!(r, U256::ZERO);
446    }
447
448    #[test]
449    fn reduce_zero() {
450        let u = U256::from(10u8);
451        let (r, is_some) = u.ct_reduce(&U256::ZERO);
452        assert_eq!(is_some, 0);
453        assert_eq!(r, u);
454    }
455
456    #[test]
457    fn reduce_tests() {
458        let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(2u8));
459        assert_eq!(is_some, 1);
460        assert_eq!(r, U256::ZERO);
461        let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(3u8));
462        assert_eq!(is_some, 1);
463        assert_eq!(r, U256::ONE);
464        let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(7u8));
465        assert_eq!(is_some, 1);
466        assert_eq!(r, U256::from(3u8));
467    }
468
469    #[test]
470    fn reduce_max() {
471        let mut a = U256::ZERO;
472        let mut b = U256::ZERO;
473        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
474        let r = a.wrapping_rem(&b);
475        assert_eq!(r, UInt::ZERO);
476        a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
477        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
478        let r = a.wrapping_rem(&b);
479        assert_eq!(r, a);
480    }
481
482    #[cfg(feature = "rand")]
483    #[test]
484    fn reduce2krand() {
485        let mut rng = ChaChaRng::from_seed([7u8; 32]);
486        for _ in 0..25 {
487            let num = U256::random(&mut rng);
488            let k = (rng.next_u32() % 256) as usize;
489            let den = U256::ONE.shl_vartime(k);
490
491            let a = num.reduce2k(k);
492            let e = num.wrapping_rem(&den);
493            assert_eq!(a, e);
494        }
495    }
496}
crypto_bigint/uint/div.rs

crypto_bigint/uint/
div.rs
