crypto_bigint/limb/
div.rs

1//! Limb division
2
3use core::slice;
4
5use crate::{
6    CheckedDiv, CtOption, Div, DivAssign, DivRemLimb, Limb, NonZero, Reciprocal, Rem, RemAssign,
7    RemLimb, UintRef,
8};
9
10impl Limb {
11    /// Computes `self / rhs`, returning the quotient and remainder.
12    #[inline(always)]
13    #[must_use]
14    pub const fn div_rem(self, rhs: NonZero<Self>) -> (Limb, Limb) {
15        self.div_rem_with_reciprocal(&Reciprocal::new(rhs))
16    }
17
18    /// Computes `self / rhs` where `recip` is a [`Reciprocal`] created from a non-zero Limb `rhs`.
19    /// Returns the quotient and remainder.
20    #[inline(always)]
21    #[must_use]
22    pub const fn div_rem_with_reciprocal(self, recip: &Reciprocal) -> (Limb, Limb) {
23        let mut quo = self;
24        let rem = UintRef::new_mut(slice::from_mut(&mut quo)).div_rem_limb_with_reciprocal(recip);
25        (quo, rem)
26    }
27
28    /// Computes the checked division `self / rhs`, returning the quotient
29    /// if the divisor is non-zero, and `CtOption::none()` otherwise.
30    #[must_use]
31    pub const fn checked_div(self, rhs: Self) -> CtOption<Limb> {
32        let (rhs_nz, is_nz) = rhs.to_nz_or_one();
33        let quo = self.div_rem(rhs_nz).0;
34        CtOption::new(quo, is_nz)
35    }
36
37    /// Computes the checked division `self / rhs`, returning the remainder
38    /// if the divisor is non-zero, and `CtOption::none()` otherwise.
39    #[must_use]
40    pub const fn checked_rem(self, rhs: Self) -> CtOption<Limb> {
41        let (rhs_nz, is_nz) = rhs.to_nz_or_one();
42        let rem = self.div_rem(rhs_nz).1;
43        CtOption::new(rem, is_nz)
44    }
45
46    /// Exactly divides `self` by `rhs`, returning `CtOption::none()` if `self` is not divisible by `rhs`.
47    #[must_use]
48    pub const fn div_exact(&self, rhs: NonZero<Limb>) -> CtOption<Self> {
49        let mut quo = *self;
50        let mut div = rhs.get_copy();
51        let exact = UintRef::new_mut(slice::from_mut(&mut quo))
52            .div_exact(UintRef::new_mut(slice::from_mut(&mut div)));
53        CtOption::new(quo, exact)
54    }
55
56    /// Exactly divides `self` by `rhs`, returning `CtOption::none()` if `self` is not divisible by `rhs`.
57    ///
58    /// This is variable-time only with respect to `rhs`.
59    ///
60    /// When used with a fixed `rhs`, this function is constant-time with respect to `self`.
61    #[must_use]
62    pub const fn div_exact_vartime(&self, rhs: NonZero<Limb>) -> CtOption<Self> {
63        let mut quo = *self;
64        let mut div = rhs.get_copy();
65        let exact = UintRef::new_mut(slice::from_mut(&mut quo))
66            .div_exact_vartime(UintRef::new_mut(slice::from_mut(&mut div)));
67        CtOption::new(quo, exact)
68    }
69}
70
71impl CheckedDiv for Limb {
72    #[inline]
73    fn checked_div(&self, rhs: &Self) -> CtOption<Self> {
74        (*self).checked_div(*rhs)
75    }
76}
77
78impl DivRemLimb for Limb {
79    #[inline]
80    fn div_rem_limb(&self, rhs: NonZero<Limb>) -> (Self, Limb) {
81        self.div_rem(rhs)
82    }
83
84    #[inline]
85    fn div_rem_limb_with_reciprocal(&self, rhs: &Reciprocal) -> (Self, Limb) {
86        self.div_rem_with_reciprocal(rhs)
87    }
88}
89
90impl Div<Limb> for Limb {
91    type Output = Limb;
92
93    #[inline]
94    fn div(self, rhs: Limb) -> Self {
95        self.checked_div(rhs).expect("division by zero")
96    }
97}
98
99impl Div<&Limb> for Limb {
100    type Output = Limb;
101
102    #[inline]
103    fn div(self, rhs: &Limb) -> Self {
104        self / (*rhs)
105    }
106}
107
108impl Div<Limb> for &Limb {
109    type Output = Limb;
110
111    #[inline]
112    fn div(self, rhs: Limb) -> Limb {
113        (*self) / rhs
114    }
115}
116
117impl Div<&Limb> for &Limb {
118    type Output = Limb;
119
120    #[inline]
121    fn div(self, rhs: &Limb) -> Limb {
122        (*self) / (*rhs)
123    }
124}
125
126impl Div<NonZero<Limb>> for Limb {
127    type Output = Limb;
128
129    #[inline]
130    fn div(self, rhs: NonZero<Limb>) -> Self {
131        self.div_rem(rhs).0
132    }
133}
134
135impl Div<&NonZero<Limb>> for Limb {
136    type Output = Limb;
137
138    #[inline]
139    fn div(self, rhs: &NonZero<Limb>) -> Self {
140        self / (*rhs)
141    }
142}
143
144impl Div<NonZero<Limb>> for &Limb {
145    type Output = Limb;
146
147    #[inline]
148    fn div(self, rhs: NonZero<Limb>) -> Limb {
149        (*self) / rhs
150    }
151}
152
153impl Div<&NonZero<Limb>> for &Limb {
154    type Output = Limb;
155
156    #[inline]
157    fn div(self, rhs: &NonZero<Limb>) -> Limb {
158        (*self) / (*rhs)
159    }
160}
161
162impl RemLimb for Limb {
163    #[inline]
164    fn rem_limb(&self, rhs: NonZero<Limb>) -> Limb {
165        self.div_rem(rhs).1
166    }
167
168    fn rem_limb_with_reciprocal(&self, rhs: &Reciprocal) -> Limb {
169        self.div_rem_with_reciprocal(rhs).1
170    }
171}
172
173impl Rem<Limb> for Limb {
174    type Output = Limb;
175
176    #[inline]
177    fn rem(self, rhs: Limb) -> Self {
178        self.checked_rem(rhs).expect("division by zero")
179    }
180}
181
182impl Rem<&Limb> for Limb {
183    type Output = Limb;
184
185    #[inline]
186    fn rem(self, rhs: &Limb) -> Self {
187        self % (*rhs)
188    }
189}
190
191impl Rem<Limb> for &Limb {
192    type Output = Limb;
193
194    #[inline]
195    fn rem(self, rhs: Limb) -> Limb {
196        (*self) % rhs
197    }
198}
199
200impl Rem<&Limb> for &Limb {
201    type Output = Limb;
202
203    #[inline]
204    fn rem(self, rhs: &Limb) -> Limb {
205        (*self) % (*rhs)
206    }
207}
208
209impl Rem<NonZero<Limb>> for Limb {
210    type Output = Limb;
211
212    #[inline]
213    fn rem(self, rhs: NonZero<Limb>) -> Self {
214        self.div_rem(rhs).1
215    }
216}
217
218impl Rem<&NonZero<Limb>> for Limb {
219    type Output = Limb;
220
221    #[inline]
222    fn rem(self, rhs: &NonZero<Limb>) -> Self {
223        self % (*rhs)
224    }
225}
226
227impl Rem<NonZero<Limb>> for &Limb {
228    type Output = Limb;
229
230    #[inline]
231    fn rem(self, rhs: NonZero<Limb>) -> Limb {
232        (*self) % rhs
233    }
234}
235
236impl Rem<&NonZero<Limb>> for &Limb {
237    type Output = Limb;
238
239    #[inline]
240    fn rem(self, rhs: &NonZero<Limb>) -> Limb {
241        (*self) % (*rhs)
242    }
243}
244
245impl DivAssign<Limb> for Limb {
246    #[inline]
247    fn div_assign(&mut self, rhs: Limb) {
248        *self = (*self) / rhs;
249    }
250}
251
252impl DivAssign<&Limb> for Limb {
253    #[inline]
254    fn div_assign(&mut self, rhs: &Limb) {
255        *self = (*self) / (*rhs);
256    }
257}
258
259impl DivAssign<NonZero<Limb>> for Limb {
260    #[inline]
261    fn div_assign(&mut self, rhs: NonZero<Limb>) {
262        *self = (*self) / rhs;
263    }
264}
265
266impl DivAssign<&NonZero<Limb>> for Limb {
267    #[inline]
268    fn div_assign(&mut self, rhs: &NonZero<Limb>) {
269        *self = (*self) / (*rhs);
270    }
271}
272
273impl RemAssign<Limb> for Limb {
274    #[inline]
275    fn rem_assign(&mut self, rhs: Limb) {
276        *self = (*self) % rhs;
277    }
278}
279
280impl RemAssign<&Limb> for Limb {
281    #[inline]
282    fn rem_assign(&mut self, rhs: &Limb) {
283        *self = (*self) % (*rhs);
284    }
285}
286
287impl RemAssign<NonZero<Limb>> for Limb {
288    #[inline]
289    fn rem_assign(&mut self, rhs: NonZero<Limb>) {
290        *self = (*self) % rhs;
291    }
292}
293
294impl RemAssign<&NonZero<Limb>> for Limb {
295    #[inline]
296    fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
297        *self = (*self) % (*rhs);
298    }
299}
300
301#[cfg(test)]
302#[allow(clippy::op_ref)]
303mod tests {
304    use super::{CheckedDiv, Limb};
305    use crate::NonZero;
306
307    #[test]
308    fn div_rem_ok() {
309        let n = Limb::from_u32(0xffff_ffff);
310        let d = NonZero::new(Limb::from_u32(0xfffe)).expect("ensured non-zero");
311        assert_eq!(n.div_rem(d), (Limb::from_u32(0x10002), Limb::from_u32(0x3)));
312
313        assert_eq!(n.div_exact(d).into_option(), None);
314        assert_eq!(n.div_exact_vartime(d).into_option(), None);
315
316        let d = NonZero::new(Limb::from_u32(0xffff)).expect("ensured non-zero");
317        assert_eq!(n.div_rem(d), (Limb::from_u32(0x10001), Limb::from_u32(0)));
318        assert_eq!(n.div_exact(d).into_option(), Some(Limb::from_u32(0x10001)));
319        assert_eq!(
320            n.div_exact_vartime(d).into_option(),
321            Some(Limb::from_u32(0x10001))
322        );
323    }
324
325    #[test]
326    fn checked_div() {
327        assert_eq!(
328            CheckedDiv::checked_div(&Limb::ONE, &Limb::ONE).into_option(),
329            Some(Limb::ONE)
330        );
331        assert_eq!(
332            CheckedDiv::checked_div(&Limb::MAX, &Limb::ZERO).into_option(),
333            None
334        );
335    }
336
337    #[test]
338    fn checked_rem() {
339        assert_eq!(
340            Limb::ONE.checked_rem(Limb::ONE).into_option(),
341            Some(Limb::ZERO)
342        );
343        assert_eq!(Limb::MAX.checked_rem(Limb::ZERO).into_option(), None);
344    }
345
346    #[test]
347    fn div_trait() {
348        let a = Limb::from(10u64);
349        let b = NonZero::new(Limb::from(2u64)).unwrap();
350        let c = Limb::from(5u64);
351
352        assert_eq!(a / b, c);
353        assert_eq!(a / &b, c);
354        assert_eq!(&a / b, c);
355        assert_eq!(&a / &b, c);
356        assert_eq!(a / b.as_ref(), c);
357        assert_eq!(&a / b.get(), c);
358    }
359
360    #[test]
361    fn div_assign_trait() {
362        let a = Limb::from(10u64);
363        let b = NonZero::new(Limb::from(2u64)).unwrap();
364        let c = Limb::from(5u64);
365
366        let mut res = a;
367        res /= b;
368        assert_eq!(res, c);
369        let mut res = a;
370        res /= &b;
371        assert_eq!(res, c);
372        let mut res = a;
373        res /= b.get();
374        assert_eq!(res, c);
375        let mut res = a;
376        res /= b.as_ref();
377        assert_eq!(res, c);
378    }
379
380    #[should_panic]
381    #[test]
382    fn div_zero() {
383        let _ = Limb::ONE / Limb::ZERO;
384    }
385
386    #[should_panic]
387    #[test]
388    fn div_ref_zero() {
389        let _ = &Limb::ONE / Limb::ZERO;
390    }
391
392    #[test]
393    fn rem_trait() {
394        let a = Limb::from(10u64);
395        let b = NonZero::new(Limb::from(3u64)).unwrap();
396        let c = Limb::from(1u64);
397
398        assert_eq!(a % b, c);
399        assert_eq!(a % &b, c);
400        assert_eq!(&a % b, c);
401        assert_eq!(&a % &b, c);
402        assert_eq!(a % b.as_ref(), c);
403        assert_eq!(&a % b.get(), c);
404    }
405
406    #[test]
407    fn rem_assign_trait() {
408        let a = Limb::from(10u64);
409        let b = NonZero::new(Limb::from(3u64)).unwrap();
410        let c = Limb::from(1u64);
411
412        let mut res = a;
413        res %= b;
414        assert_eq!(res, c);
415        let mut res = a;
416        res %= &b;
417        assert_eq!(res, c);
418        let mut res = a;
419        res %= b.get();
420        assert_eq!(res, c);
421        let mut res = a;
422        res %= b.as_ref();
423        assert_eq!(res, c);
424    }
425
426    #[should_panic]
427    #[test]
428    fn rem_zero() {
429        let _ = Limb::ONE % Limb::ZERO;
430    }
431
432    #[should_panic]
433    #[test]
434    fn rem_ref_zero() {
435        let _ = &Limb::ONE % Limb::ZERO;
436    }
437}
crypto_bigint/limb/div.rs

crypto_bigint/limb/
div.rs
