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

crypto_bigint/uint/boxed/
div.rs
