dashu_int/
div_const.rs

1//! Public interface for creating a constant divisor.
2
3use core::{
4    fmt::{Display, Formatter},
5    mem,
6    ops::{Div, DivAssign, Rem, RemAssign},
7};
8use dashu_base::{DivRem, DivRemAssign};
9use num_modular::{PreMulInv2by1, PreMulInv3by2};
10
11use crate::{
12    arch::word::{DoubleWord, Word},
13    buffer::Buffer,
14    div,
15    error::panic_divide_by_0,
16    helper_macros::debug_assert_zero,
17    math::{shl_dword, FastDivideNormalized2},
18    memory::MemoryAllocation,
19    primitive::{double_word, extend_word, shrink_dword},
20    repr::Repr,
21    repr::TypedRepr,
22    shift,
23    ubig::UBig,
24    IBig,
25};
26use alloc::boxed::Box;
27
28#[derive(Debug, PartialEq, Eq)]
29pub(crate) struct ConstSingleDivisor(pub(crate) PreMulInv2by1<Word>);
30
31#[derive(Debug, PartialEq, Eq)]
32pub(crate) struct ConstDoubleDivisor(pub(crate) PreMulInv3by2<Word, DoubleWord>);
33
34#[derive(Debug, PartialEq, Eq)]
35pub(crate) struct ConstLargeDivisor {
36    pub(crate) normalized_divisor: Box<[Word]>,
37    pub(crate) shift: u32,
38    pub(crate) fast_div_top: FastDivideNormalized2,
39}
40
41impl ConstSingleDivisor {
42    /// Create a single word const divisor
43    #[inline]
44    pub const fn new(n: Word) -> Self {
45        debug_assert!(n != 0);
46        Self(PreMulInv2by1::<Word>::new(n))
47    }
48
49    /// Get the original (unnormalized) divisor
50    #[inline]
51    pub const fn divisor(&self) -> Word {
52        self.0.divisor() >> self.0.shift()
53    }
54
55    #[inline]
56    pub const fn normalized_divisor(&self) -> Word {
57        self.0.divisor()
58    }
59    pub const fn shift(&self) -> u32 {
60        self.0.shift()
61    }
62
63    /// Calculate (word << self.shift) % self
64    #[inline]
65    pub const fn rem_word(&self, word: Word) -> Word {
66        if self.0.shift() == 0 {
67            self.0.divider().div_rem_1by1(word).1
68        } else {
69            self.0
70                .divider()
71                .div_rem_2by1(extend_word(word) << self.0.shift())
72                .1
73        }
74    }
75
76    /// Calculate (dword << self.shift) % self
77    #[inline]
78    pub const fn rem_dword(&self, dword: DoubleWord) -> Word {
79        if self.0.shift() == 0 {
80            self.0.divider().div_rem_2by1(dword).1
81        } else {
82            let (n0, n1, n2) = shl_dword(dword, self.0.shift());
83            let (_, r1) = self.0.divider().div_rem_2by1(double_word(n1, n2));
84            self.0.divider().div_rem_2by1(double_word(n0, r1)).1
85        }
86    }
87
88    /// Calculate (words << self.shift) % self
89    pub fn rem_large(&self, words: &[Word]) -> Word {
90        let mut rem = div::fast_rem_by_normalized_word(words, *self.0.divider());
91        if self.0.shift() != 0 {
92            rem = self
93                .0
94                .divider()
95                .div_rem_2by1(extend_word(rem) << self.0.shift())
96                .1
97        }
98        rem
99    }
100}
101
102impl ConstDoubleDivisor {
103    /// Create a double word const divisor
104    #[inline]
105    pub const fn new(n: DoubleWord) -> Self {
106        debug_assert!(n > Word::MAX as DoubleWord);
107        Self(PreMulInv3by2::<Word, DoubleWord>::new(n))
108    }
109
110    /// Get the original (unnormalized) divisor
111    #[inline]
112    pub const fn divisor(&self) -> DoubleWord {
113        self.0.divisor() >> self.0.shift()
114    }
115
116    #[inline]
117    pub const fn normalized_divisor(&self) -> DoubleWord {
118        self.0.divisor()
119    }
120    pub const fn shift(&self) -> u32 {
121        self.0.shift()
122    }
123
124    /// Calculate (dword << self.shift) % self
125    #[inline]
126    pub const fn rem_dword(&self, dword: DoubleWord) -> DoubleWord {
127        if self.0.shift() == 0 {
128            self.0.divider().div_rem_2by2(dword).1
129        } else {
130            let (n0, n1, n2) = shl_dword(dword, self.0.shift());
131            self.0.divider().div_rem_3by2(n0, double_word(n1, n2)).1
132        }
133    }
134
135    /// Calculate (words << self.shift) % self
136    pub fn rem_large(&self, words: &[Word]) -> DoubleWord {
137        let mut rem = div::fast_rem_by_normalized_dword(words, *self.0.divider());
138        if self.0.shift() != 0 {
139            let (r0, r1, r2) = shl_dword(rem, self.0.shift());
140            rem = self.0.divider().div_rem_3by2(r0, double_word(r1, r2)).1
141        }
142        rem
143    }
144}
145
146impl ConstLargeDivisor {
147    /// Create a const divisor with multiple words
148    pub fn new(mut n: Buffer) -> Self {
149        let (shift, fast_div_top) = crate::div::normalize(&mut n);
150        Self {
151            normalized_divisor: n.into_boxed_slice(),
152            shift,
153            fast_div_top,
154        }
155    }
156
157    /// Get the original (unnormalized) divisor
158    pub fn divisor(&self) -> Buffer {
159        let mut buffer = Buffer::from(self.normalized_divisor.as_ref());
160        debug_assert_zero!(shift::shr_in_place(&mut buffer, self.shift));
161        buffer
162    }
163
164    /// Calculate (words << self.shift) % self
165    #[inline]
166    pub fn rem_large(&self, mut words: Buffer) -> Buffer {
167        // shift
168        let carry = shift::shl_in_place(&mut words, self.shift);
169        words.push_resizing(carry);
170
171        // reduce
172        let modulus = &self.normalized_divisor;
173        if words.len() >= modulus.len() {
174            let mut allocation =
175                MemoryAllocation::new(div::memory_requirement_exact(words.len(), modulus.len()));
176            let _overflow = div::div_rem_in_place(
177                &mut words,
178                modulus,
179                self.fast_div_top,
180                &mut allocation.memory(),
181            );
182            words.truncate(modulus.len());
183        }
184        words
185    }
186
187    /// Calculate (x << self.shift) % self
188    #[inline]
189    pub fn rem_repr(&self, x: TypedRepr) -> Buffer {
190        match x {
191            TypedRepr::Small(dword) => {
192                let (lo, mid, hi) = shl_dword(dword, self.shift);
193                let mut buffer = Buffer::allocate_exact(self.normalized_divisor.len());
194                buffer.push(lo);
195                buffer.push(mid);
196                buffer.push(hi);
197
198                // because ConstLargeDivisor is used only for integer with more than two words,
199                // word << ring.shift() must be smaller than the normalized modulus
200                buffer
201            }
202            TypedRepr::Large(words) => self.rem_large(words),
203        }
204    }
205}
206
207#[derive(Debug, PartialEq, Eq)]
208pub(crate) enum ConstDivisorRepr {
209    Single(ConstSingleDivisor),
210    Double(ConstDoubleDivisor),
211    Large(ConstLargeDivisor),
212}
213
214/// An [UBig] with some pre-computed fields to support faster division.
215#[derive(Debug, PartialEq, Eq)]
216pub struct ConstDivisor(pub(crate) ConstDivisorRepr);
217
218impl ConstDivisor {
219    pub fn new(n: UBig) -> ConstDivisor {
220        Self(match n.into_repr() {
221            TypedRepr::Small(0) => panic_divide_by_0(),
222            TypedRepr::Small(dword) => {
223                if let Some(word) = shrink_dword(dword) {
224                    ConstDivisorRepr::Single(ConstSingleDivisor::new(word))
225                } else {
226                    ConstDivisorRepr::Double(ConstDoubleDivisor::new(dword))
227                }
228            }
229            TypedRepr::Large(words) => ConstDivisorRepr::Large(ConstLargeDivisor::new(words)),
230        })
231    }
232
233    #[inline]
234    pub const fn from_word(word: Word) -> Self {
235        if word == 0 {
236            panic_divide_by_0()
237        }
238        Self(ConstDivisorRepr::Single(ConstSingleDivisor::new(word)))
239    }
240
241    #[inline]
242    pub const fn from_dword(dword: DoubleWord) -> Self {
243        if dword == 0 {
244            panic_divide_by_0()
245        }
246
247        Self(if let Some(word) = shrink_dword(dword) {
248            ConstDivisorRepr::Single(ConstSingleDivisor::new(word))
249        } else {
250            ConstDivisorRepr::Double(ConstDoubleDivisor::new(dword))
251        })
252    }
253
254    #[inline]
255    pub fn value(&self) -> UBig {
256        UBig(match &self.0 {
257            ConstDivisorRepr::Single(d) => Repr::from_word(d.divisor()),
258            ConstDivisorRepr::Double(d) => Repr::from_dword(d.divisor()),
259            ConstDivisorRepr::Large(d) => Repr::from_buffer(d.divisor()),
260        })
261    }
262}
263
264impl Display for ConstDivisor {
265    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
266        Display::fmt(&self.value(), f)
267    }
268}
269
270impl<'r> Div<&'r ConstDivisor> for UBig {
271    type Output = UBig;
272
273    #[inline]
274    fn div(self, rhs: &ConstDivisor) -> UBig {
275        UBig(self.into_repr() / &rhs.0)
276    }
277}
278impl<'l, 'r> Div<&'r ConstDivisor> for &'l UBig {
279    type Output = UBig;
280
281    #[inline]
282    fn div(self, rhs: &ConstDivisor) -> UBig {
283        UBig(self.clone().into_repr() / &rhs.0)
284    }
285}
286impl<'r> DivAssign<&'r ConstDivisor> for UBig {
287    #[inline]
288    fn div_assign(&mut self, rhs: &'r ConstDivisor) {
289        *self = mem::take(self) / rhs;
290    }
291}
292
293impl<'r> Rem<&'r ConstDivisor> for UBig {
294    type Output = UBig;
295
296    #[inline]
297    fn rem(self, rhs: &ConstDivisor) -> UBig {
298        UBig(self.into_repr() % &rhs.0)
299    }
300}
301impl<'l, 'r> Rem<&'r ConstDivisor> for &'l UBig {
302    type Output = UBig;
303
304    #[inline]
305    fn rem(self, rhs: &ConstDivisor) -> UBig {
306        UBig(self.repr() % &rhs.0)
307    }
308}
309impl<'r> RemAssign<&'r ConstDivisor> for UBig {
310    #[inline]
311    fn rem_assign(&mut self, rhs: &'r ConstDivisor) {
312        *self = mem::take(self) % rhs;
313    }
314}
315
316impl<'r> DivRem<&'r ConstDivisor> for UBig {
317    type OutputDiv = UBig;
318    type OutputRem = UBig;
319
320    #[inline]
321    fn div_rem(self, rhs: &ConstDivisor) -> (UBig, UBig) {
322        let (q, r) = self.into_repr().div_rem(&rhs.0);
323        (UBig(q), UBig(r))
324    }
325}
326impl<'l, 'r> DivRem<&'r ConstDivisor> for &'l UBig {
327    type OutputDiv = UBig;
328    type OutputRem = UBig;
329
330    #[inline]
331    fn div_rem(self, rhs: &ConstDivisor) -> (UBig, UBig) {
332        let (q, r) = self.clone().into_repr().div_rem(&rhs.0);
333        (UBig(q), UBig(r))
334    }
335}
336impl<'r> DivRemAssign<&'r ConstDivisor> for UBig {
337    type OutputRem = UBig;
338    #[inline]
339    fn div_rem_assign(&mut self, rhs: &ConstDivisor) -> UBig {
340        let (q, r) = mem::take(self).div_rem(rhs);
341        *self = q;
342        r
343    }
344}
345
346impl<'r> Div<&'r ConstDivisor> for IBig {
347    type Output = IBig;
348
349    #[inline]
350    fn div(self, rhs: &ConstDivisor) -> IBig {
351        let (sign, repr) = self.into_sign_repr();
352        IBig((repr / &rhs.0).with_sign(sign))
353    }
354}
355impl<'l, 'r> Div<&'r ConstDivisor> for &'l IBig {
356    type Output = IBig;
357
358    #[inline]
359    fn div(self, rhs: &ConstDivisor) -> IBig {
360        let (sign, repr) = self.clone().into_sign_repr();
361        IBig((repr / &rhs.0).with_sign(sign))
362    }
363}
364impl<'r> DivAssign<&'r ConstDivisor> for IBig {
365    #[inline]
366    fn div_assign(&mut self, rhs: &'r ConstDivisor) {
367        *self = mem::take(self) / rhs;
368    }
369}
370
371impl<'r> Rem<&'r ConstDivisor> for IBig {
372    type Output = IBig;
373
374    #[inline]
375    fn rem(self, rhs: &ConstDivisor) -> IBig {
376        let (sign, repr) = self.into_sign_repr();
377        IBig((repr % &rhs.0).with_sign(sign))
378    }
379}
380impl<'l, 'r> Rem<&'r ConstDivisor> for &'l IBig {
381    type Output = IBig;
382
383    #[inline]
384    fn rem(self, rhs: &ConstDivisor) -> IBig {
385        let (sign, repr) = self.as_sign_repr();
386        IBig((repr % &rhs.0).with_sign(sign))
387    }
388}
389impl<'r> RemAssign<&'r ConstDivisor> for IBig {
390    #[inline]
391    fn rem_assign(&mut self, rhs: &'r ConstDivisor) {
392        *self = mem::take(self) % rhs;
393    }
394}
395
396impl<'r> DivRem<&'r ConstDivisor> for IBig {
397    type OutputDiv = IBig;
398    type OutputRem = IBig;
399
400    #[inline]
401    fn div_rem(self, rhs: &ConstDivisor) -> (IBig, IBig) {
402        let (sign, repr) = self.into_sign_repr();
403        let (q, r) = repr.div_rem(&rhs.0);
404        (IBig(q.with_sign(sign)), IBig(r.with_sign(sign)))
405    }
406}
407impl<'l, 'r> DivRem<&'r ConstDivisor> for &'l IBig {
408    type OutputDiv = IBig;
409    type OutputRem = IBig;
410
411    #[inline]
412    fn div_rem(self, rhs: &ConstDivisor) -> (IBig, IBig) {
413        let (sign, repr) = self.clone().into_sign_repr();
414        let (q, r) = repr.div_rem(&rhs.0);
415        (IBig(q.with_sign(sign)), IBig(r.with_sign(sign)))
416    }
417}
418impl<'r> DivRemAssign<&'r ConstDivisor> for IBig {
419    type OutputRem = IBig;
420    #[inline]
421    fn div_rem_assign(&mut self, rhs: &ConstDivisor) -> IBig {
422        let (q, r) = mem::take(self).div_rem(rhs);
423        *self = q;
424        r
425    }
426}
427
428mod repr {
429    use super::*;
430    use crate::repr::{
431        Repr,
432        TypedRepr::{self, *},
433        TypedReprRef::{self, *},
434    };
435
436    impl<'r> Div<&'r ConstDivisorRepr> for TypedRepr {
437        type Output = Repr;
438        fn div(self, rhs: &ConstDivisorRepr) -> Repr {
439            match (self, rhs) {
440                (Small(dword), ConstDivisorRepr::Single(div)) => {
441                    Repr::from_dword(div_rem_small_single(dword, div).0)
442                }
443                (Small(dword), ConstDivisorRepr::Double(div)) => {
444                    Repr::from_word(div_rem_small_double(dword, div).0)
445                }
446                (Small(_), ConstDivisorRepr::Large(_)) => {
447                    // lhs must be less than rhs
448                    Repr::zero()
449                }
450                (Large(mut buffer), ConstDivisorRepr::Single(div)) => {
451                    let _rem = div::fast_div_by_word_in_place(
452                        &mut buffer,
453                        div.0.shift(),
454                        *div.0.divider(),
455                    );
456                    Repr::from_buffer(buffer)
457                }
458                (Large(mut buffer), ConstDivisorRepr::Double(div)) => {
459                    let _rem = div::fast_div_by_dword_in_place(
460                        &mut buffer,
461                        div.0.shift(),
462                        *div.0.divider(),
463                    );
464                    Repr::from_buffer(buffer)
465                }
466                (Large(mut buffer), ConstDivisorRepr::Large(div)) => {
467                    let div_len = div.normalized_divisor.len();
468                    if buffer.len() < div_len {
469                        Repr::zero()
470                    } else {
471                        let mut allocation = MemoryAllocation::new(div::memory_requirement_exact(
472                            buffer.len(),
473                            div_len,
474                        ));
475                        let q_top = div::div_rem_unshifted_in_place(
476                            &mut buffer,
477                            &div.normalized_divisor,
478                            div.shift,
479                            div.fast_div_top,
480                            &mut allocation.memory(),
481                        );
482                        buffer.erase_front(div_len);
483                        buffer.push_resizing(q_top);
484                        Repr::from_buffer(buffer)
485                    }
486                }
487            }
488        }
489    }
490
491    impl<'r> Rem<&'r ConstDivisorRepr> for TypedRepr {
492        type Output = Repr;
493
494        fn rem(self, rhs: &ConstDivisorRepr) -> Repr {
495            match (self, rhs) {
496                (Small(dword), ConstDivisorRepr::Single(div)) => {
497                    Repr::from_word(div.rem_dword(dword) >> div.0.shift())
498                }
499                (Small(dword), ConstDivisorRepr::Double(div)) => {
500                    Repr::from_dword(div.rem_dword(dword) >> div.0.shift())
501                }
502                (Small(dword), ConstDivisorRepr::Large(_)) => {
503                    // lhs must be less than rhs
504                    Repr::from_dword(dword)
505                }
506                (Large(buffer), ConstDivisorRepr::Single(div)) => {
507                    Repr::from_word(div.rem_large(&buffer) >> div.0.shift())
508                }
509                (Large(buffer), ConstDivisorRepr::Double(div)) => {
510                    Repr::from_dword(div.rem_large(&buffer) >> div.0.shift())
511                }
512                (Large(buffer), ConstDivisorRepr::Large(div)) => rem_large_large(buffer, div),
513            }
514        }
515    }
516
517    impl<'l, 'r> Rem<&'r ConstDivisorRepr> for TypedReprRef<'l> {
518        type Output = Repr;
519
520        fn rem(self, rhs: &ConstDivisorRepr) -> Repr {
521            match (self, rhs) {
522                (RefSmall(dword), ConstDivisorRepr::Single(div)) => {
523                    Repr::from_word(div.rem_dword(dword) >> div.0.shift())
524                }
525                (RefSmall(dword), ConstDivisorRepr::Double(div)) => {
526                    Repr::from_dword(div.rem_dword(dword) >> div.0.shift())
527                }
528                (RefSmall(dword), ConstDivisorRepr::Large(_)) => {
529                    // lhs must be less than rhs
530                    Repr::from_dword(dword)
531                }
532                (RefLarge(words), ConstDivisorRepr::Single(div)) => {
533                    Repr::from_word(div.rem_large(words) >> div.0.shift())
534                }
535                (RefLarge(words), ConstDivisorRepr::Double(div)) => {
536                    Repr::from_dword(div.rem_large(words) >> div.0.shift())
537                }
538                (RefLarge(words), ConstDivisorRepr::Large(div)) => {
539                    rem_large_large(words.into(), div)
540                }
541            }
542        }
543    }
544
545    impl<'r> DivRem<&'r ConstDivisorRepr> for TypedRepr {
546        type OutputDiv = Repr;
547        type OutputRem = Repr;
548
549        fn div_rem(self, rhs: &ConstDivisorRepr) -> (Repr, Repr) {
550            match (self, rhs) {
551                (Small(dword), ConstDivisorRepr::Single(div)) => {
552                    let (q, r) = div_rem_small_single(dword, div);
553                    (Repr::from_dword(q), Repr::from_word(r))
554                }
555                (Small(dword), ConstDivisorRepr::Double(div)) => {
556                    let (q, r) = div_rem_small_double(dword, div);
557                    (Repr::from_word(q), Repr::from_dword(r))
558                }
559                (Small(dword), ConstDivisorRepr::Large(_)) => {
560                    // lhs must be less than rhs
561                    (Repr::zero(), Repr::from_dword(dword))
562                }
563                (Large(mut buffer), ConstDivisorRepr::Single(div)) => {
564                    let r = div::fast_div_by_word_in_place(
565                        &mut buffer,
566                        div.0.shift(),
567                        *div.0.divider(),
568                    );
569                    (Repr::from_buffer(buffer), Repr::from_word(r))
570                }
571                (Large(mut buffer), ConstDivisorRepr::Double(div)) => {
572                    let r = div::fast_div_by_dword_in_place(
573                        &mut buffer,
574                        div.0.shift(),
575                        *div.0.divider(),
576                    );
577                    (Repr::from_buffer(buffer), Repr::from_dword(r))
578                }
579                (Large(mut buffer), ConstDivisorRepr::Large(div)) => {
580                    let div_len = div.normalized_divisor.len();
581                    if buffer.len() < div_len {
582                        (Repr::zero(), Repr::from_buffer(buffer))
583                    } else {
584                        let mut allocation = MemoryAllocation::new(div::memory_requirement_exact(
585                            buffer.len(),
586                            div_len,
587                        ));
588                        let q_top = div::div_rem_unshifted_in_place(
589                            &mut buffer,
590                            &div.normalized_divisor,
591                            div.shift,
592                            div.fast_div_top,
593                            &mut allocation.memory(),
594                        );
595
596                        let mut q = Buffer::from(&buffer[div_len..]);
597                        q.push_resizing(q_top);
598                        buffer.truncate(div_len);
599                        debug_assert_zero!(shift::shr_in_place(&mut buffer, div.shift));
600                        (Repr::from_buffer(q), Repr::from_buffer(buffer))
601                    }
602                }
603            }
604        }
605    }
606
607    fn div_rem_small_single(lhs: DoubleWord, rhs: &ConstSingleDivisor) -> (DoubleWord, Word) {
608        let (lo, mid, hi) = shl_dword(lhs, rhs.0.shift());
609        let (q1, r1) = rhs.0.divider().div_rem_2by1(double_word(mid, hi));
610        let (q0, r0) = rhs.0.divider().div_rem_2by1(double_word(lo, r1));
611        (double_word(q0, q1), r0 >> rhs.0.shift())
612    }
613
614    fn div_rem_small_double(lhs: DoubleWord, rhs: &ConstDoubleDivisor) -> (Word, DoubleWord) {
615        let (lo, mid, hi) = shl_dword(lhs, rhs.0.shift());
616        let (q, r) = rhs.0.divider().div_rem_3by2(lo, double_word(mid, hi));
617        (q, r >> rhs.0.shift())
618    }
619
620    fn rem_large_large(mut lhs: Buffer, rhs: &ConstLargeDivisor) -> Repr {
621        let modulus = &rhs.normalized_divisor;
622
623        // only reduce if lhs can be larger than rhs
624        if lhs.len() >= modulus.len() {
625            let mut allocation =
626                MemoryAllocation::new(div::memory_requirement_exact(lhs.len(), modulus.len()));
627            let _qtop = div::div_rem_unshifted_in_place(
628                &mut lhs,
629                modulus,
630                rhs.shift,
631                rhs.fast_div_top,
632                &mut allocation.memory(),
633            );
634
635            lhs.truncate(modulus.len());
636            debug_assert_zero!(shift::shr_in_place(&mut lhs, rhs.shift));
637        }
638        Repr::from_buffer(lhs)
639    }
640}
dashu_int/div_const.rs

dashu_int/
div_const.rs
