1use 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 #[inline]
44 pub const fn new(n: Word) -> Self {
45 debug_assert!(n != 0);
46 Self(PreMulInv2by1::<Word>::new(n))
47 }
48
49 #[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 #[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 #[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 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 #[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 #[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 #[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 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 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 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 #[inline]
166 pub fn rem_large(&self, mut words: Buffer) -> Buffer {
167 let carry = shift::shl_in_place(&mut words, self.shift);
169 words.push_resizing(carry);
170
171 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 #[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 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#[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 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 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 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 (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 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}