crypto_bigint/uint/boxed/
div.rs

1//! [`BoxedUint`] division operations.
2
3use crate::{
4    BoxedUint, CheckedDiv, CtAssign, CtOption, Div, DivAssign, DivRemLimb, DivVartime, Integer,
5    Limb, NonZero, Reciprocal, Rem, RemAssign, RemLimb, RemMixed, ToUnsigned, UintRef, Unsigned,
6    Wrapping, bitlen,
7};
8
9impl BoxedUint {
10    /// Computes `self / rhs` using a pre-made reciprocal,
11    /// returns the quotient (q) and remainder (r).
12    #[must_use]
13    pub fn div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
14        let mut quo = self.clone();
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`, returns the quotient (q) and remainder (r).
22    #[must_use]
23    pub fn div_rem_limb(&self, rhs: NonZero<Limb>) -> (Self, Limb) {
24        let mut quo = self.clone();
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    #[inline(always)]
31    #[must_use]
32    pub fn rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> Limb {
33        self.as_uint_ref()
34            .rem_limb_with_reciprocal(reciprocal, Limb::ZERO)
35    }
36
37    /// Computes `self % rhs`.
38    #[inline(always)]
39    #[must_use]
40    pub fn rem_limb(&self, rhs: NonZero<Limb>) -> Limb {
41        self.as_uint_ref().rem_limb(rhs)
42    }
43
44    /// Computes self / rhs, returns the quotient, remainder.
45    #[must_use]
46    pub fn div_rem<Rhs: ToUnsigned + ?Sized>(&self, rhs: &NonZero<Rhs>) -> (Self, Rhs::Unsigned) {
47        let mut quo = self.clone();
48        let rem = quo.div_rem_assign(rhs.to_unsigned());
49        (quo, rem)
50    }
51
52    /// Computes self % rhs, returns the remainder.
53    #[must_use]
54    pub fn rem<Rhs: ToUnsigned + ?Sized>(&self, rhs: &NonZero<Rhs>) -> Rhs::Unsigned {
55        self.div_rem(rhs).1
56    }
57
58    /// Computes self / rhs, assigning the quotient to `self` and returning the remainder.
59    #[must_use]
60    pub(crate) fn div_rem_assign<Rhs: AsMut<UintRef>>(&mut self, rhs: NonZero<Rhs>) -> Rhs {
61        let mut rem = rhs.get();
62        self.as_mut_uint_ref().div_rem(rem.as_mut());
63        rem
64    }
65
66    /// Exactly divides `self` by `rhs`, returning `CtOption::none()` if `self` is not divisible by `rhs`.
67    #[must_use]
68    pub fn div_exact<Rhs: ToUnsigned + ?Sized>(&self, rhs: &NonZero<Rhs>) -> CtOption<Self> {
69        let mut quo = self.clone();
70        let mut div = rhs.to_unsigned().get();
71        let exact = quo.as_mut_uint_ref().div_exact(div.as_mut_uint_ref());
72        CtOption::new(quo, exact)
73    }
74
75    /// Computes self / rhs, returns the quotient and remainder.
76    ///
77    /// Variable-time with respect to `rhs`
78    #[must_use]
79    pub fn div_rem_vartime<Rhs: ToUnsigned + ?Sized>(
80        &self,
81        rhs: &NonZero<Rhs>,
82    ) -> (Self, Rhs::Unsigned) {
83        let mut quo = self.clone();
84        let rem = quo.div_rem_assign_vartime(rhs.to_unsigned());
85        (quo, rem)
86    }
87
88    /// Computes self % rhs, returns the remainder.
89    ///
90    /// Variable-time with respect to `rhs`.
91    #[must_use]
92    pub fn rem_vartime<Rhs: ToUnsigned + ?Sized>(&self, rhs: &NonZero<Rhs>) -> Rhs::Unsigned {
93        let xc = self.limbs.len();
94        let yc = bitlen::to_limbs(rhs.as_ref().as_ref().bits_vartime());
95
96        match yc {
97            0 => unreachable!("zero divisor"),
98            1 => {
99                // Perform limb division
100                let rem_limb = self.as_uint_ref().rem_limb(rhs.lower_limb());
101                let mut rem = rhs.as_ref().to_unsigned_zero();
102                rem.as_mut_limbs()[0] = rem_limb;
103                rem
104            }
105            _ if yc > xc => {
106                let mut rem = rhs.as_ref().to_unsigned_zero();
107                rem.as_mut_uint_ref()
108                    .leading_mut(xc)
109                    .copy_from_slice(&self.limbs);
110                rem
111            }
112            _ => {
113                let mut quo = self.clone();
114                let mut rem = rhs.as_ref().to_unsigned();
115                quo.as_mut_uint_ref()
116                    .leading_mut(xc)
117                    .div_rem_large_vartime(rem.as_mut_uint_ref().leading_mut(yc));
118                rem
119            }
120        }
121    }
122
123    /// Computes self / rhs, returns the quotient and remainder.
124    ///
125    /// Variable-time with respect to `rhs`
126    #[must_use]
127    pub(crate) fn div_rem_assign_vartime<Rhs: AsMut<UintRef>>(&mut self, rhs: NonZero<Rhs>) -> Rhs {
128        let mut rem = rhs.get();
129        self.as_mut_uint_ref().div_rem_vartime(rem.as_mut());
130        rem
131    }
132
133    /// Exactly divides `self` by `rhs`, returning `CtOption::none()` if `self` is not divisible by `rhs`.
134    #[must_use]
135    pub fn div_exact_vartime<Rhs: ToUnsigned + ?Sized>(
136        &self,
137        rhs: &NonZero<Rhs>,
138    ) -> CtOption<Self> {
139        let mut quo = self.clone();
140        let mut div = rhs.to_unsigned().get();
141        let exact = quo
142            .as_mut_uint_ref()
143            .div_exact_vartime(div.as_mut_uint_ref());
144        CtOption::new(quo, exact)
145    }
146
147    /// Wrapped division is just normal division i.e. `self` / `rhs`
148    /// There’s no way wrapping could ever happen.
149    ///
150    /// This function exists, so that all operations are accounted for in the wrapping operations.
151    ///
152    /// # Panics
153    /// - if `rhs == 0`.
154    #[must_use]
155    pub fn wrapping_div<Rhs: ToUnsigned + ?Sized>(&self, rhs: &NonZero<Rhs>) -> Self {
156        self.div_rem(rhs).0
157    }
158
159    /// Wrapped division is just normal division i.e. `self` / `rhs`
160    ///
161    /// There’s no way wrapping could ever happen.
162    /// This function exists, so that all operations are accounted for in the wrapping operations
163    #[must_use]
164    pub fn wrapping_div_vartime<Rhs: ToUnsigned + ?Sized>(&self, rhs: &NonZero<Rhs>) -> Self {
165        self.div_rem_vartime(rhs).0
166    }
167
168    /// Perform checked division, returning a [`CtOption`] which `is_some`
169    /// only if the `rhs != 0`.
170    #[must_use]
171    pub fn checked_div(&self, rhs: impl AsRef<UintRef>) -> CtOption<Self> {
172        let mut quo = self.clone();
173        let rhs = rhs.as_ref();
174        let is_nz = rhs.is_nonzero();
175        let mut rem = Self::one_with_precision(rhs.bits_precision());
176        rem.as_mut_uint_ref().ct_assign(rhs, is_nz);
177        quo.as_mut_uint_ref().div_rem(rem.as_mut_uint_ref());
178        CtOption::new(quo, is_nz)
179    }
180}
181
182impl<Rhs: AsRef<UintRef>> CheckedDiv<Rhs> for BoxedUint {
183    fn checked_div(&self, rhs: &Rhs) -> CtOption<Self> {
184        self.checked_div(rhs)
185    }
186}
187
188impl<Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for &BoxedUint {
189    type Output = BoxedUint;
190
191    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
192        self.wrapping_div(rhs)
193    }
194}
195
196impl<Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for BoxedUint {
197    type Output = BoxedUint;
198
199    fn div(mut self, rhs: &NonZero<Rhs>) -> Self::Output {
200        let _rem = self.div_rem_assign(rhs.to_unsigned());
201        self
202    }
203}
204
205impl<Rhs: AsMut<UintRef>> Div<NonZero<Rhs>> for &BoxedUint {
206    type Output = BoxedUint;
207
208    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
209        let mut quo = self.clone();
210        let _rem = quo.div_rem_assign(rhs);
211        quo
212    }
213}
214
215impl<Rhs: AsMut<UintRef>> Div<NonZero<Rhs>> for BoxedUint {
216    type Output = BoxedUint;
217
218    fn div(mut self, rhs: NonZero<Rhs>) -> Self::Output {
219        let _rem = self.div_rem_assign(rhs);
220        self
221    }
222}
223
224impl<Rhs: ToUnsigned + ?Sized> DivAssign<&NonZero<Rhs>> for BoxedUint {
225    fn div_assign(&mut self, rhs: &NonZero<Rhs>) {
226        let _rem = self.div_rem_assign(rhs.to_unsigned());
227    }
228}
229
230impl<Rhs: AsMut<UintRef>> DivAssign<NonZero<Rhs>> for BoxedUint {
231    fn div_assign(&mut self, rhs: NonZero<Rhs>) {
232        let _rem = self.div_rem_assign(rhs);
233    }
234}
235
236impl DivVartime for BoxedUint {
237    fn div_vartime(&self, rhs: &NonZero<BoxedUint>) -> Self {
238        self.wrapping_div_vartime(rhs)
239    }
240}
241
242impl<Rhs: AsMut<UintRef>> Div<NonZero<Rhs>> for Wrapping<BoxedUint> {
243    type Output = Wrapping<BoxedUint>;
244
245    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
246        Wrapping(self.0 / rhs)
247    }
248}
249
250impl<Rhs: AsMut<UintRef>> Div<NonZero<Rhs>> for &Wrapping<BoxedUint> {
251    type Output = Wrapping<BoxedUint>;
252
253    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
254        Wrapping(&self.0 / rhs)
255    }
256}
257
258impl<Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for &Wrapping<BoxedUint> {
259    type Output = Wrapping<BoxedUint>;
260
261    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
262        Wrapping(&self.0 / rhs)
263    }
264}
265
266impl<Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for Wrapping<BoxedUint> {
267    type Output = Wrapping<BoxedUint>;
268
269    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
270        Wrapping(self.0 / rhs)
271    }
272}
273
274impl<Rhs: ToUnsigned + ?Sized> DivAssign<&NonZero<Rhs>> for Wrapping<BoxedUint> {
275    fn div_assign(&mut self, rhs: &NonZero<Rhs>) {
276        self.0 /= rhs;
277    }
278}
279
280impl<Rhs: AsMut<UintRef>> DivAssign<NonZero<Rhs>> for Wrapping<BoxedUint> {
281    fn div_assign(&mut self, rhs: NonZero<Rhs>) {
282        self.0 /= rhs;
283    }
284}
285
286impl<Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for &BoxedUint {
287    type Output = Rhs::Unsigned;
288
289    #[inline]
290    fn rem(self, rhs: &NonZero<Rhs>) -> Self::Output {
291        self.rem(rhs)
292    }
293}
294
295impl<Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for BoxedUint {
296    type Output = Rhs::Unsigned;
297
298    #[inline]
299    fn rem(self, rhs: &NonZero<Rhs>) -> Self::Output {
300        Self::rem(&self, rhs)
301    }
302}
303
304impl<Rhs: AsMut<UintRef>> Rem<NonZero<Rhs>> for &BoxedUint {
305    type Output = Rhs;
306
307    #[inline]
308    fn rem(self, rhs: NonZero<Rhs>) -> Self::Output {
309        self.clone().div_rem_assign(rhs)
310    }
311}
312
313impl<Rhs: AsMut<UintRef>> Rem<NonZero<Rhs>> for BoxedUint {
314    type Output = Rhs;
315
316    #[inline]
317    fn rem(mut self, rhs: NonZero<Rhs>) -> Self::Output {
318        self.div_rem_assign(rhs)
319    }
320}
321
322impl<Rhs: AsRef<UintRef> + ?Sized> RemAssign<&NonZero<Rhs>> for BoxedUint {
323    fn rem_assign(&mut self, rhs: &NonZero<Rhs>) {
324        *self = self.div_rem_assign(rhs.to_boxed());
325    }
326}
327
328impl<Rhs: AsRef<UintRef>> RemAssign<NonZero<Rhs>> for BoxedUint {
329    fn rem_assign(&mut self, rhs: NonZero<Rhs>) {
330        *self = self.div_rem_assign(rhs.to_boxed());
331    }
332}
333
334impl DivRemLimb for BoxedUint {
335    fn div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
336        Self::div_rem_limb_with_reciprocal(self, reciprocal)
337    }
338}
339
340impl RemLimb for BoxedUint {
341    fn rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> Limb {
342        Self::rem_limb_with_reciprocal(self, reciprocal)
343    }
344}
345
346impl<Rhs: Unsigned> RemMixed<Rhs> for BoxedUint {
347    fn rem_mixed(&self, reductor: &NonZero<Rhs>) -> Rhs {
348        Self::div_rem(self, reductor).1
349    }
350}
351
352#[cfg(test)]
353mod tests {
354    use super::{BoxedUint, Limb, NonZero};
355    use crate::{CtAssign, DivVartime, One, Resize, UintRef, Wrapping, Zero};
356
357    #[test]
358    fn div_trait() {
359        let n = BoxedUint::from(0xFFEECCBBAA99887766u128);
360        let p = NonZero::new(BoxedUint::from(997u128)).unwrap();
361        let res = BoxedUint::from(0x41b74857375c0f86u64);
362        assert_eq!(&n / &p, res);
363        assert_eq!(&n / p.clone(), res);
364        assert_eq!(n.clone() / &p, res);
365        assert_eq!(n / p, res);
366    }
367
368    #[test]
369    fn rem_trait() {
370        let n = BoxedUint::from(0xFFEECCBBAA99887766u128);
371        let p = NonZero::new(BoxedUint::from(997u128)).unwrap();
372        let res = BoxedUint::from(648u128);
373        assert_eq!(&n % &p, res);
374        assert_eq!(&n % p.clone(), res);
375        assert_eq!(n.clone() % &p, res);
376        assert_eq!(n % p, res);
377    }
378
379    #[test]
380    fn div_rem_larger_denominator() {
381        // 1 = len(x) < len(y) and x < y
382        let x = BoxedUint::from_be_hex("8000000000000000", 64).unwrap();
383        let y = BoxedUint::from_be_hex("00000000000000010000000000000000", 128)
384            .unwrap()
385            .to_nz()
386            .unwrap();
387        let (quo, rem) = x.div_rem(&y);
388        assert_eq!(quo, BoxedUint::zero_with_precision(64));
389        assert_eq!(rem, x.resize_unchecked(128));
390
391        // 1 = len(x) < len(y) and x > y
392        let x = BoxedUint::from_be_hex("8000000000000000", 64).unwrap();
393        let y = BoxedUint::from_be_hex("00000000000000000000000000001000", 128)
394            .unwrap()
395            .to_nz()
396            .unwrap();
397        let (quo, rem) = x.div_rem(&y);
398        assert_eq!(quo, BoxedUint::from_be_hex("0008000000000000", 64).unwrap());
399        assert_eq!(rem, BoxedUint::zero_with_precision(128));
400
401        // 2 = len(x) < len(y) and x < y
402        let x = BoxedUint::from_be_hex("80000000000000008000000000000000", 128).unwrap();
403        let y = BoxedUint::from_be_hex(
404            "0000000000000001000000000000000000000000000000010000000000000000",
405            256,
406        )
407        .unwrap()
408        .to_nz()
409        .unwrap();
410        let (quo, rem) = x.div_rem(&y);
411        assert_eq!(quo, BoxedUint::zero_with_precision(128));
412        assert_eq!(rem, x.resize_unchecked(256));
413
414        // 2 = len(x) < len(y) and x > y
415        let x = BoxedUint::from_be_hex("80000000000000008000000000000000", 128).unwrap();
416        let y = BoxedUint::from_be_hex(
417            "0000000000000000000000000000000000000000000000000000000000110000",
418            256,
419        )
420        .unwrap()
421        .to_nz()
422        .unwrap();
423        let (quo, rem) = x.div_rem(&y);
424        assert_eq!(
425            quo,
426            BoxedUint::from_be_hex("000007878787878787878f0f0f0f0f0f", 128).unwrap()
427        );
428        assert_eq!(
429            rem,
430            BoxedUint::from_be_hex(
431                "0000000000000000000000000000000000000000000000000000000000010000",
432                256
433            )
434            .unwrap()
435        );
436    }
437
438    #[test]
439    fn rem_vartime() {
440        let n = BoxedUint::from(0xFFEECCBBAA99887766u128);
441        let p = NonZero::new(BoxedUint::from(997u128)).unwrap();
442        assert_eq!(BoxedUint::from(648u128), n.rem_vartime(&p));
443    }
444
445    #[test]
446    fn rem_limb() {
447        let n = BoxedUint::from(0xFFEECCBBAA99887766u128);
448        let pl = NonZero::new(Limb(997)).unwrap();
449        let p = NonZero::new(BoxedUint::from(997u128)).unwrap();
450        assert_eq!(n.rem(&p).limbs[0], n.rem_limb(pl));
451    }
452
453    #[test]
454    fn div_vartime_through_trait() {
455        struct A<T> {
456            x: T,
457            y: T,
458        }
459        impl<T: DivVartime + Clone + Zero + One + CtAssign> A<T> {
460            fn divide_x_by_y(&self) -> T {
461                let rhs = &NonZero::new(self.y.clone()).unwrap();
462                self.x.div_vartime(rhs)
463            }
464        }
465
466        let a = A {
467            x: BoxedUint::from(1234567890u64),
468            y: BoxedUint::from(456u64),
469        };
470        assert_eq!(a.divide_x_by_y(), BoxedUint::from(2707385u64));
471    }
472
473    #[test]
474    fn div_uintref() {
475        let a = BoxedUint::from(1234567890u64);
476        let b = UintRef::new(&[Limb(456), Limb(0)])
477            .as_nz_vartime()
478            .expect("ensured non-zero");
479        assert_eq!(&a / b, BoxedUint::from(2707385u64));
480        assert_eq!(
481            a.checked_div(b.as_ref()).into_option(),
482            Some(BoxedUint::from(2707385u64))
483        );
484    }
485
486    #[test]
487    fn wrapping_div() {
488        let a = Wrapping(BoxedUint::from(1234567890u64));
489        let b = NonZero::new(BoxedUint::from(456u64)).expect("ensured non-zero");
490        let res = Wrapping(BoxedUint::from(2707385u64));
491        assert_eq!(&a / &b, res);
492        assert_eq!(&a / b.clone(), res);
493        assert_eq!(a.clone() / &b, res);
494        assert_eq!(a.clone() / b.clone(), res);
495
496        let mut c = a.clone();
497        c /= &b;
498        assert_eq!(c, res);
499        let mut c = a.clone();
500        c /= b;
501        assert_eq!(c, res);
502    }
503}
crypto_bigint/uint/boxed/div.rs

crypto_bigint/uint/boxed/
div.rs
