1const CHEAP_SATURATION: bool = cfg!(any(
10 target_arch = "aarch64",
11 all(
12 any(target_arch = "x86", target_arch = "x86_64"),
13 target_feature = "sse4.1"
14 )
15));
16
17macro_rules! divisor_enum {
18 ($name:ident, $t:ty, $($(#[$doc:meta])* $variant:ident($inner:ident),)+) => {
19 #[doc = concat!("A `", stringify!($t), "` divisor, precomputed once to divide many values by it")]
20 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
36 #[doc = concat!("let values: Vec<", stringify!($t), "> = vec![100, 7, 64];")]
37 #[doc = concat!("let quotients: Vec<_> = match ", stringify!($name), "::new(7).unwrap() {")]
38 #[doc = concat!(" ", stringify!($name), "::PowerOfTwo(d) => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),")]
39 #[doc = concat!(" ", stringify!($name), "::AddIndicator(d) => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),")]
40 #[derive(Debug, Clone, Copy)]
45 #[non_exhaustive]
46 pub enum $name {
47 $($(#[$doc])* $variant($inner),)+
48 }
49
50 impl $name {
51 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
56 #[doc = concat!("let divisor = ", stringify!($name), "::new(7).unwrap();")]
57 #[inline]
60 pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
61 match self {
62 $(Self::$variant(d) => d.wrapping_div_rem(n),)+
63 }
64 }
65 }
66 };
67}
68
69macro_rules! n_bit_divisor {
74 ($(#[$doc:meta])* $name:ident, $enum:ident, $t:ty, $wide:ty, |$n:ident| $body:expr, $example:expr) => {
75 $(#[$doc])*
76 #[derive(Debug, Clone, Copy)]
77 pub struct $name {
78 divisor: $t,
79 multiplier: $t,
80 shift: u32,
81 }
82
83 impl $name {
84 #[doc = concat!("# use arrow_buffer::", stringify!($enum), ";")]
89 #[doc = $example]
90 #[inline]
92 pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
93 let $n = n;
94 let n1: $t = $body;
95 let high = ((self.multiplier as $wide * n1 as $wide) >> <$t>::BITS) as $t;
96 let q = high >> self.shift;
97 (q, n - q * self.divisor)
98 }
99 }
100 };
101}
102
103macro_rules! unsigned_divisor {
104 ($name:ident, $power_of_two:ident, $up:ident, $add:ident, $t:ty, $wide:ty $(, $down:ident)?) => {
105 divisor_enum!(
106 $name,
107 $t,
108 PowerOfTwo($power_of_two),
110 Up($up),
112 $(
113 Down($down),
116 )?
117 AddIndicator($add),
119 );
120
121 impl $name {
122 $(
131 #[doc = concat!("Otherwise it picks [`Self::Down`] (a [`", stringify!($down), "`]) on aarch64 and on x86 with SSE4.1, where a saturating increment takes one or two vector instructions.")]
132 )?
133 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
138 #[doc = concat!("const SEVEN: ", stringify!($name), " = ", stringify!($name), "::new(7).unwrap();")]
139 #[doc = concat!("assert!(", stringify!($name), "::new(0).is_none());")]
140 pub const fn new(divisor: $t) -> Option<Self> {
142 if divisor == 0 {
143 return None;
144 }
145 if let Some(d) = $power_of_two::new(divisor) {
146 return Some(Self::PowerOfTwo(d));
147 }
148 let p = <$t>::BITS - 1 - divisor.leading_zeros();
149 let one: $wide = 1;
150 let pow = one << (<$t>::BITS + p);
151 let down = pow / divisor as $wide;
152 if (down + 1) * divisor as $wide - pow <= one << p {
154 return Some(Self::Up($up {
155 divisor,
156 multiplier: (down + 1) as $t,
157 shift: p,
158 }));
159 }
160 $(
161 if CHEAP_SATURATION {
165 return Some(Self::Down($down {
166 divisor,
167 multiplier: down as $t,
168 shift: p,
169 }));
170 }
171 )?
172 Some(Self::AddIndicator($add::new(divisor, p, pow, down)))
173 }
174 }
175
176 #[doc = concat!("A `", stringify!($t), "` divisor that is a power of two, see [`", stringify!($name), "`]")]
177 #[derive(Debug, Clone, Copy)]
178 pub struct $power_of_two {
179 shift: u32,
180 mask: $t,
181 }
182
183 impl $power_of_two {
184 const fn new(divisor: $t) -> Option<Self> {
185 if !divisor.is_power_of_two() {
186 return None;
187 }
188 Some(Self {
189 shift: divisor.trailing_zeros(),
190 mask: divisor - 1,
191 })
192 }
193
194 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
199 #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) = ", stringify!($name), "::new(8).unwrap() else { unreachable!() };")]
200 #[inline]
203 pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
204 (n >> self.shift, n & self.mask)
205 }
206 }
207
208 n_bit_divisor!(
209 #[doc = concat!("A `", stringify!($t), "` divisor whose rounded-up multiplier is exact in N bits, see [`", stringify!($name), "`]")]
210 $up,
215 $name,
216 $t,
217 $wide,
218 |n| n,
219 concat!("let ", stringify!($name), "::Up(divisor) = ", stringify!($name), "::new(13).unwrap() else { unreachable!() };\nassert_eq!(divisor.wrapping_div_rem(100), (7, 9));")
220 );
221
222 #[doc = concat!("A `", stringify!($t), "` divisor that isn't a power of two, see [`", stringify!($name), "`]")]
223 $(
227 #[doc = ""]
228 #[doc = concat!("[`", stringify!($name), "::new`] returns it only on targets without [`", stringify!($down), "`], so the example checks nothing on aarch64 and on x86 with SSE4.1.")]
229 )?
230 #[derive(Debug, Clone, Copy)]
231 pub struct $add {
232 divisor: $t,
233 multiplier: $t,
235 shift: u32,
237 }
238
239 impl $add {
240 const fn new(divisor: $t, p: u32, pow: $wide, down: $wide) -> Self {
243 let below = pow - down * divisor as $wide;
249 let carry = (2 * below >= divisor as $wide) as $wide;
250 Self {
251 divisor,
252 multiplier: (2 * down + carry + 1 - (pow >> p)) as $t,
253 shift: p,
254 }
255 }
256
257 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
262 #[doc = concat!("if let ", stringify!($name), "::AddIndicator(divisor) = ", stringify!($name), "::new(7).unwrap() {")]
263 #[inline]
267 pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
268 let t = ((self.multiplier as $wide * n as $wide) >> <$t>::BITS) as $t;
269 let q = (t + ((n - t) >> 1)) >> self.shift;
271 (q, n - q * self.divisor)
272 }
273 }
274 };
275}
276
277macro_rules! signed_divisor {
278 ($name:ident, $power_of_two:ident, $add:ident, $t:ty, $wide:ty) => {
279 divisor_enum!(
280 $name,
281 $t,
282 PowerOfTwo($power_of_two),
284 AddIndicator($add),
286 );
287
288 impl $name {
289 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
294 #[doc = concat!("const SEVEN: ", stringify!($name), " = ", stringify!($name), "::new(7).unwrap();")]
295 #[doc = concat!("assert!(", stringify!($name), "::new(0).is_none());")]
296 pub const fn new(divisor: $t) -> Option<Self> {
298 if divisor == 0 {
299 return None;
300 }
301 Some(match $power_of_two::new(divisor) {
302 Some(d) => Self::PowerOfTwo(d),
303 None => Self::AddIndicator($add::new(divisor)),
304 })
305 }
306
307 #[doc = concat!("Returns `(n / divisor, n % divisor)`, or `None` for `", stringify!($t), "::MIN / -1`")]
308 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
314 #[doc = concat!("let divisor = ", stringify!($name), "::new(-7).unwrap();")]
315 #[doc = concat!("let minus_one = ", stringify!($name), "::new(-1).unwrap();")]
318 #[doc = concat!("assert_eq!(minus_one.checked_div_rem(", stringify!($t), "::MIN), None);")]
319 #[inline]
321 pub const fn checked_div_rem(self, n: $t) -> Option<($t, $t)> {
322 match self {
323 Self::PowerOfTwo(d) => d.checked_div_rem(n),
324 Self::AddIndicator(d) => Some(d.wrapping_div_rem(n)),
325 }
326 }
327 }
328
329 #[doc = concat!("A `", stringify!($t), "` divisor whose magnitude is a power of two, see [`", stringify!($name), "`]")]
330 #[derive(Debug, Clone, Copy)]
336 pub struct $power_of_two {
337 shift: u32,
338 mask: $t,
340 sign: $t,
342 }
343
344 impl $power_of_two {
345 const fn new(divisor: $t) -> Option<Self> {
346 let magnitude = divisor.unsigned_abs();
347 if !magnitude.is_power_of_two() {
348 return None;
349 }
350 Some(Self {
351 shift: magnitude.trailing_zeros(),
352 mask: (magnitude - 1) as $t,
353 sign: divisor >> (<$t>::BITS - 1),
354 })
355 }
356
357 #[doc = concat!("Returns `(n.wrapping_div(divisor), n.wrapping_rem(divisor))`, so `", stringify!($t), "::MIN / -1` returns `(", stringify!($t), "::MIN, 0)`")]
358 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
362 #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) = ", stringify!($name), "::new(-8).unwrap() else { unreachable!() };")]
363 #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(minus_one) = ", stringify!($name), "::new(-1).unwrap() else { unreachable!() };")]
366 #[doc = concat!("assert_eq!(minus_one.wrapping_div_rem(", stringify!($t), "::MIN), (", stringify!($t), "::MIN, 0));")]
367 #[inline]
369 pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
370 let t = n + ((n >> (<$t>::BITS - 1)) & self.mask);
372 let q = t >> self.shift;
373 ((q ^ self.sign).wrapping_sub(self.sign), n - (t & !self.mask))
376 }
377
378 #[doc = concat!("Returns `(n / divisor, n % divisor)`, or `None` for `", stringify!($t), "::MIN / -1`")]
379 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
383 #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) = ", stringify!($name), "::new(-8).unwrap() else { unreachable!() };")]
384 #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(minus_one) = ", stringify!($name), "::new(-1).unwrap() else { unreachable!() };")]
387 #[doc = concat!("assert_eq!(minus_one.checked_div_rem(", stringify!($t), "::MIN), None);")]
388 #[inline]
390 pub const fn checked_div_rem(self, n: $t) -> Option<($t, $t)> {
391 if n == <$t>::MIN && self.sign == -1 && self.mask == 0 {
393 None
394 } else {
395 Some(self.wrapping_div_rem(n))
396 }
397 }
398 }
399
400 #[doc = concat!("A `", stringify!($t), "` divisor whose magnitude isn't a power of two, see [`", stringify!($name), "`]")]
401 #[derive(Debug, Clone, Copy)]
405 pub struct $add {
406 divisor: $t,
407 multiplier: $t,
409 shift: u32,
411 }
412
413 impl $add {
414 const fn new(divisor: $t) -> Self {
416 let magnitude = divisor.unsigned_abs();
417 let l = <$t>::BITS - (magnitude - 1).leading_zeros();
420 let m = 1 + (1 << (<$t>::BITS + l - 1)) / magnitude as $wide;
423 Self {
424 divisor,
425 multiplier: (m - (1 << <$t>::BITS)) as $t,
426 shift: l - 1,
427 }
428 }
429
430 #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
435 #[doc = concat!("let ", stringify!($name), "::AddIndicator(divisor) = ", stringify!($name), "::new(-7).unwrap() else { unreachable!() };")]
436 #[inline]
439 pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
440 let high = ((self.multiplier as $wide * n as $wide) >> <$t>::BITS) as $t;
442 let q = ((n + high) >> self.shift) - (n >> (<$t>::BITS - 1));
444 let sign = self.divisor >> (<$t>::BITS - 1);
445 let magnitude = (self.divisor ^ sign) - sign;
450 ((q ^ sign) - sign, n - q * magnitude)
451 }
452 }
453 };
454}
455
456unsigned_divisor!(
457 DivisorU32,
458 PowerOfTwoDivisorU32,
459 UpDivisorU32,
460 AddIndicatorDivisorU32,
461 u32,
462 u64,
463 DownDivisorU32
464);
465unsigned_divisor!(
466 DivisorU64,
467 PowerOfTwoDivisorU64,
468 UpDivisorU64,
469 AddIndicatorDivisorU64,
470 u64,
471 u128
472);
473signed_divisor!(
474 DivisorI32,
475 PowerOfTwoDivisorI32,
476 AddIndicatorDivisorI32,
477 i32,
478 i64
479);
480signed_divisor!(
481 DivisorI64,
482 PowerOfTwoDivisorI64,
483 AddIndicatorDivisorI64,
484 i64,
485 i128
486);
487
488n_bit_divisor!(
489 DownDivisorU32,
501 DivisorU32,
502 u32,
503 u64,
504 |n| n.saturating_add(1),
505 "if let DivisorU32::Down(divisor) = DivisorU32::new(7).unwrap() {\n assert_eq!(divisor.wrapping_div_rem(100), (14, 2));\n}"
506);
507
508#[cfg(test)]
509mod tests {
510 use super::*;
511 use rand::{RngExt, SeedableRng, rngs::StdRng};
512
513 macro_rules! test_unsigned {
514 ($name:ident, $divisor:ident, $t:ty) => {
515 #[test]
516 #[cfg_attr(miri, ignore)] fn $name() {
518 let mut rng = StdRng::seed_from_u64(42);
519 let bits = <$t>::BITS;
520
521 let mut divisors: Vec<$t> = (1..=2000).collect();
522 divisors.extend([<$t>::MAX, <$t>::MAX - 1]);
523 for k in 0..bits {
524 let p = 1 << k;
525 divisors.extend([p, p - 1, p + 1]);
526 }
527 let mut p: $t = 10;
528 while let Some(next) = p.checked_mul(10) {
529 divisors.extend([p - 1, p, p + 1]);
530 p = next;
531 }
532 divisors.extend((0..500).map(|_| rng.random::<$t>() >> rng.random_range(0..bits)));
533 divisors.retain(|d| *d != 0);
534
535 let mut values: Vec<$t> = vec![0, 1, 2, <$t>::MAX, <$t>::MAX - 1];
536 values.extend([
537 1 << (bits - 1),
538 (1 << (bits - 1)) - 1,
539 (1 << (bits - 1)) + 1,
540 ]);
541 values.extend((0..500).map(|_| rng.random::<$t>() >> rng.random_range(0..bits)));
542
543 assert!($divisor::new(0).is_none());
544 for d in divisors {
545 let divisor = $divisor::new(d).unwrap();
546 let power_of_two = matches!(divisor, $divisor::PowerOfTwo(_));
547 assert_eq!(power_of_two, d.is_power_of_two(), "{d}");
548 let top = <$t>::MAX / d * d;
552 let near = [d - 1, d, d.wrapping_add(1), d.wrapping_mul(7)];
553 let ends = [top, top.wrapping_sub(1), top.wrapping_sub(d)];
554 for &n in values.iter().chain(&near).chain(&ends) {
555 assert_eq!(divisor.wrapping_div_rem(n), (n / d, n % d), "{n} / {d}");
556 }
557 }
558 }
559 };
560 }
561
562 macro_rules! test_signed {
563 ($name:ident, $divisor:ident, $t:ty, $u:ty) => {
564 #[test]
565 #[cfg_attr(miri, ignore)] fn $name() {
567 let mut rng = StdRng::seed_from_u64(42);
568 let bits = <$t>::BITS;
569
570 let mut magnitudes: Vec<$t> = (1..=1000).collect();
571 for k in 0..bits - 1 {
572 let p: $t = 1 << k;
573 magnitudes.extend([p, p - 1, p + 1]);
574 }
575 let mut p: $t = 10;
576 while let Some(next) = p.checked_mul(10) {
577 magnitudes.extend([p - 1, p, p + 1]);
578 p = next;
579 }
580 magnitudes.extend(
581 (0..200).map(|_| (rng.random::<$u>() >> rng.random_range(1..bits)) as $t),
582 );
583
584 let mut divisors: Vec<$t> = magnitudes.iter().flat_map(|d| [*d, -*d]).collect();
585 divisors.extend([<$t>::MIN, <$t>::MAX, -1, 1]);
586 divisors.retain(|d| *d != 0);
587
588 let mut values: Vec<$t> = vec![0, 1, -1, <$t>::MIN, <$t>::MAX, <$t>::MIN + 1];
589 values.extend((0..200).flat_map(|_| {
590 let v = (rng.random::<$u>() >> rng.random_range(1..bits)) as $t;
591 [v, -v]
592 }));
593
594 assert!($divisor::new(0).is_none());
595 for d in divisors {
596 let divisor = $divisor::new(d).unwrap();
597 let power_of_two = matches!(divisor, $divisor::PowerOfTwo(_));
598 assert_eq!(power_of_two, d.unsigned_abs().is_power_of_two(), "{d}");
599 let ad = d.unsigned_abs();
602 let top = <$t>::MAX as $u / ad * ad;
603 let bottom = <$t>::MIN.unsigned_abs() / ad * ad;
604 let ends = [top, top.wrapping_sub(1), top.wrapping_sub(ad)]
605 .map(|n| n as $t)
606 .into_iter()
607 .chain(
608 [bottom, bottom.wrapping_sub(1), bottom.wrapping_sub(ad)]
609 .map(|n| n.wrapping_neg() as $t),
610 )
611 .collect::<Vec<_>>();
612 let near = [d.wrapping_sub(1), d, d.wrapping_add(1), d.wrapping_mul(7)];
613 for &n in values.iter().chain(&near).chain(&ends) {
614 let expected = (n.wrapping_div(d), n.wrapping_rem(d));
615 assert_eq!(divisor.wrapping_div_rem(n), expected, "{n} / {d}");
616 let checked = n.checked_div(d).zip(n.checked_rem(d));
617 assert_eq!(divisor.checked_div_rem(n), checked, "{n} / {d}");
618 }
619 }
620 }
621 };
622 }
623
624 test_unsigned!(test_divisor_u32, DivisorU32, u32);
625 test_unsigned!(test_divisor_u64, DivisorU64, u64);
626 test_signed!(test_divisor_i32, DivisorI32, i32, u32);
627 test_signed!(test_divisor_i64, DivisorI64, i64, u64);
628
629 macro_rules! test_unsigned_variant {
633 ($name:ident, $divisor:ident, $t:ty, $wide:ty, $down:expr, $is_down:expr, $primes:expr) => {
634 #[test]
635 fn $name() {
636 let mut rng = StdRng::seed_from_u64(42);
637 let bits = <$t>::BITS;
638 let mut divisors: Vec<$t> = (1..=3000).collect();
639 divisors.extend([<$t>::MAX, <$t>::MAX - 1, (1 << (bits - 1)) + 1]);
640 let primes: &[$t] = &$primes;
643 assert_eq!(primes.iter().product::<$t>(), <$t>::MAX);
644 let mut factors = vec![];
645 for subset in 1..1u32 << primes.len() {
646 let d = (0..primes.len())
647 .filter(|i| subset & (1 << i) != 0)
648 .fold(1, |d, i| d * primes[i]);
649 factors.push(d);
650 }
651 divisors.extend(&factors);
652 divisors.extend((0..2000).map(|_| rng.random::<$t>() >> rng.random_range(0..bits)));
653 divisors.retain(|d| *d != 0);
654
655 for d in divisors {
656 let divisor = $divisor::new(d).unwrap();
657 if d.is_power_of_two() {
658 assert!(matches!(divisor, $divisor::PowerOfTwo(_)), "{d}");
659 continue;
660 }
661 let p = bits - 1 - d.leading_zeros();
662 let one: $wide = 1;
663 let pow = one << (bits + p);
664 let up = pow / d as $wide + 1;
665 if up * d as $wide - pow <= 1 << p {
666 assert!(matches!(divisor, $divisor::Up(_)), "{d}");
667 } else if $down {
668 assert!(!factors.contains(&d), "{d}");
669 assert!($is_down(&divisor), "{d}");
670 } else {
671 assert!(matches!(divisor, $divisor::AddIndicator(_)), "{d}");
672 }
673 }
674 for d in factors
675 .into_iter()
676 .filter(|d| *d > 1 && !d.is_power_of_two())
677 {
678 let divisor = $divisor::new(d).unwrap();
679 assert!(matches!(divisor, $divisor::Up(_)), "{d}");
680 let max = <$t>::MAX;
683 for n in [0, 1, d - 1, d, d.wrapping_add(1), max, max - 1, max - d] {
684 assert_eq!(divisor.wrapping_div_rem(n), (n / d, n % d), "{n} / {d}");
685 }
686 }
687 }
688 };
689 }
690
691 test_unsigned_variant!(
692 test_variant_u32,
693 DivisorU32,
694 u32,
695 u64,
696 CHEAP_SATURATION,
697 |d: &DivisorU32| matches!(d, DivisorU32::Down(_)),
698 [3, 5, 17, 257, 65537]
699 );
700 test_unsigned_variant!(
701 test_variant_u64,
702 DivisorU64,
703 u64,
704 u128,
705 false,
706 |_: &DivisorU64| false,
707 [3, 5, 17, 257, 641, 65537, 6700417]
708 );
709
710 #[test]
713 fn test_add_indicator_u32() {
714 let mut rng = StdRng::seed_from_u64(42);
715 let mut divisors: Vec<u32> = (3..=3000).collect();
716 divisors.extend([u32::MAX - 1, (1 << 31) + 1]);
717 divisors.extend((0..2000).map(|_| rng.random::<u32>() >> rng.random_range(0..32)));
718 divisors.retain(|d| *d >= 3 && !d.is_power_of_two());
719 for d in divisors {
720 let p = u32::BITS - 1 - d.leading_zeros();
721 let pow = 1u64 << (u32::BITS + p);
722 let divisor = AddIndicatorDivisorU32::new(d, p, pow, pow / d as u64);
723 let top = u32::MAX / d * d;
724 let values = [
725 0,
726 1,
727 d - 1,
728 d,
729 d + 1,
730 top,
731 top - 1,
732 top - d,
733 u32::MAX,
734 u32::MAX - 1,
735 ];
736 for n in values {
737 assert_eq!(divisor.wrapping_div_rem(n), (n / d, n % d), "{n} / {d}");
738 }
739 }
740 }
741
742 #[test]
743 fn test_variant_signed() {
744 for d in [3, -3, 7, -7, 13, -13, 100, -100, i32::MAX, i32::MIN + 1] {
745 assert!(
746 matches!(DivisorI32::new(d).unwrap(), DivisorI32::AddIndicator(_)),
747 "{d}"
748 );
749 let d = d as i64;
750 assert!(
751 matches!(DivisorI64::new(d).unwrap(), DivisorI64::AddIndicator(_)),
752 "{d}"
753 );
754 }
755 }
756
757 #[test]
758 fn test_const_new() {
759 const TEN: DivisorU64 = DivisorU64::new(10).unwrap();
760 const MINUS_EIGHT: DivisorI32 = DivisorI32::new(-8).unwrap();
761 assert_eq!(TEN.wrapping_div_rem(1234), (123, 4));
762 assert_eq!(MINUS_EIGHT.wrapping_div_rem(-17), (2, -1));
763 }
764}