Skip to main content

arrow_buffer/
divisor.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5/// Whether a saturating increment on `u32` lanes is cheap: one `uqadd` on aarch64, and `pminud`
6/// from SSE4.1 and a subtract on x86. Baseline x86-64 has no unsigned 32-bit min and emulates it
7/// with compares, so there the saturating increment of [`DivisorU32::Down`] costs more than the
8/// add and halve of [`DivisorU32::AddIndicator`]
9const 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        ///
21        /// Division by a divisor that is only known at run time needs a divide instruction.
22        /// [`Self::new`] precomputes a shift and a mask when the magnitude of the divisor is a
23        /// power of two, and otherwise a multiplier, so that each division is a high multiply,
24        /// shifts and additions. [`Self::new`] picks the variant from the divisor and the target.
25        ///
26        /// To divide many values, match on the variant once, before the loop, and call the
27        /// variant's methods in the loop. They don't branch on the divisor, so the loop doesn't
28        /// depend on the compiler moving a branch out of it. Move the variant into the loop's
29        /// closure, so that the compiler doesn't reload its fields through a reference for each
30        /// value. [`Self::wrapping_div_rem`] matches on each call, so a match can fall back to it
31        /// for the variants it doesn't specialize, including variants added later.
32        ///
33        /// # Example
34        /// ```
35        #[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        ///     d => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),
41        /// };
42        /// assert_eq!(quotients, [14, 1, 9]);
43        /// ```
44        #[derive(Debug, Clone, Copy)]
45        #[non_exhaustive]
46        pub enum $name {
47            $($(#[$doc])* $variant($inner),)+
48        }
49
50        impl $name {
51            /// Returns `(n.wrapping_div(divisor), n.wrapping_rem(divisor))`
52            ///
53            /// # Example
54            /// ```
55            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
56            #[doc = concat!("let divisor = ", stringify!($name), "::new(7).unwrap();")]
57            /// assert_eq!(divisor.wrapping_div_rem(100), (14, 2));
58            /// ```
59            #[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
69/// A divisor with an N-bit multiplier, which computes the quotient as `MULUH(m, n') >> shift`
70/// for `n'` from `$body`. `Up` and `Down` differ only in `n'`, and the macro keeps them from
71/// duplicating the rest. `|n| ...` looks like a closure but is macro syntax for the expression,
72/// because a `const fn` can't call a closure
73macro_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            /// Returns `(n / divisor, n % divisor)`
85            ///
86            /// # Example
87            /// ```
88            #[doc = concat!("# use arrow_buffer::", stringify!($enum), ";")]
89            #[doc = $example]
90            /// ```
91            #[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            /// A divisor that is a power of two
109            PowerOfTwo($power_of_two),
110            /// A divisor whose rounded-up multiplier is exact in N bits
111            Up($up),
112            $(
113                /// A divisor whose rounded-up multiplier isn't exact in N bits, with the
114                /// rounded-down multiplier, on targets where `u32` saturating adds are cheap
115                Down($down),
116            )?
117            /// Any other divisor
118            AddIndicator($add),
119        );
120
121        impl $name {
122            /// Returns a divisor for `divisor`, or `None` if `divisor` is zero
123            ///
124            /// With `p = floor(log2(divisor))`, it picks [`Self::Up`] when the rounded-up
125            /// multiplier `floor(2^(N+p) / divisor) + 1` satisfies theorem 4.2 of
126            /// [Granlund and Montgomery, "Division by Invariant Integers using Multiplication" (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf).
127            /// Checking one `p` is enough, because a multiplier that is exact for a smaller `p` is
128            /// also exact for this one, see
129            /// [ridiculous_fish, "Labor of Division (Episode I)"](https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html).
130            $(
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            /// It picks [`Self::AddIndicator`] for any divisor the other variants don't cover.
134            ///
135            /// # Example
136            /// ```
137            #[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            /// ```
141            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                // divisor > 2^p, so down + 1 < 2^N
153                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                    // When the rounded-up multiplier isn't exact, the rounded-down one with the
162                    // dividend increased by 1 is, by the proof of universality in
163                    // "Labor of Division (Episode III)"
164                    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            /// Returns `(n / divisor, n % divisor)`
195            ///
196            /// # Example
197            /// ```
198            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
199            #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) = ", stringify!($name), "::new(8).unwrap() else { unreachable!() };")]
200            /// assert_eq!(divisor.wrapping_div_rem(100), (12, 4));
201            /// ```
202            #[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            ///
211            /// It computes `MULUH(m, n) >> shift`, where `m` satisfies theorem 4.2 of
212            /// [Granlund and Montgomery, "Division by Invariant Integers using Multiplication" (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf)
213            /// with `l = shift` and fits in N bits, so it needs no add and halve as in figure 4.1.
214            $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        ///
224        /// It uses the `N + 1`-bit multiplier from figure 4.1 of
225        /// [Granlund and Montgomery, "Division by Invariant Integers using Multiplication" (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf).
226        $(
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            /// `m'` in figure 4.1
234            multiplier: $t,
235            /// `sh2` in figure 4.1
236            shift: u32,
237        }
238
239        impl $add {
240            /// `divisor` must be at least 3 and not a power of two, `p` is `floor(log2(divisor))`,
241            /// `pow` is `2^(N+p)` and `down` is `pow / divisor`
242            const fn new(divisor: $t, p: u32, pow: $wide, down: $wide) -> Self {
243                // Figure 4.1 uses `l = ceil(log2(divisor)) = p + 1`, so `sh1` is 1, `sh2` is `p`
244                // and `m' = floor(2^(N+l) / divisor) - 2^N + 1`. `2^(N+l)` is `2 * pow`, and
245                // `floor(2a / d) = 2 * floor(a / d) + (2 * (a mod d) >= d)`, so `new` gets the
246                // quotient from `down` and its remainder instead of a second wide division, which
247                // is a call to `__udivti3` for `u64`. `2^l < 2 * divisor`, so `m'` fits in N bits
248                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            /// Returns `(n / divisor, n % divisor)`
258            ///
259            /// # Example
260            /// ```
261            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
262            #[doc = concat!("if let ", stringify!($name), "::AddIndicator(divisor) = ", stringify!($name), "::new(7).unwrap() {")]
263            ///     assert_eq!(divisor.wrapping_div_rem(100), (14, 2));
264            /// }
265            /// ```
266            #[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                // `(n + t) >> l` could overflow, so this halves `n - t` first, as figure 4.1 does
270                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            /// A divisor whose magnitude is a power of two
283            PowerOfTwo($power_of_two),
284            /// Any other divisor
285            AddIndicator($add),
286        );
287
288        impl $name {
289            /// Returns a divisor for `divisor`, or `None` if `divisor` is zero
290            ///
291            /// # Example
292            /// ```
293            #[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            /// ```
297            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            ///
309            /// It matches on the variant on each call. Only [`Self::PowerOfTwo`] can return `None`.
310            ///
311            /// # Example
312            /// ```
313            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
314            #[doc = concat!("let divisor = ", stringify!($name), "::new(-7).unwrap();")]
315            /// assert_eq!(divisor.checked_div_rem(-100), Some((14, -2)));
316            ///
317            #[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            /// ```
320            #[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        ///
331        /// The quotient and remainder follow sections 10-1 and 10-2 of Warren, "Hacker's Delight",
332        /// 2nd edition. Those sections compute the addend `2^k - 1` for a negative `n` with two
333        /// shifts. This type computes it with one shift that spreads the sign bit of `n` and an AND
334        /// with `2^k - 1`, which it computes once for the divisor.
335        #[derive(Debug, Clone, Copy)]
336        pub struct $power_of_two {
337            shift: u32,
338            /// `|divisor| - 1`
339            mask: $t,
340            /// -1 if the divisor is negative, otherwise 0
341            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            ///
359            /// # Example
360            /// ```
361            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
362            #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) = ", stringify!($name), "::new(-8).unwrap() else { unreachable!() };")]
363            /// assert_eq!(divisor.wrapping_div_rem(-100), (12, -4));
364            ///
365            #[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            /// ```
368            #[inline]
369            pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
370                // Adding `|divisor| - 1` to a negative `n` makes the shift round toward zero
371                let t = n + ((n >> (<$t>::BITS - 1)) & self.mask);
372                let q = t >> self.shift;
373                // `(x ^ sign) - sign` negates `x` when `sign` is -1, and wraps only for `MIN / -1`
374                // `t & !mask` is `n` rounded toward zero to a multiple of `|divisor|`
375                ((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            ///
380            /// # Example
381            /// ```
382            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
383            #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) = ", stringify!($name), "::new(-8).unwrap() else { unreachable!() };")]
384            /// assert_eq!(divisor.checked_div_rem(-100), Some((12, -4)));
385            ///
386            #[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            /// ```
389            #[inline]
390            pub const fn checked_div_rem(self, n: $t) -> Option<($t, $t)> {
391                // -1 is the only divisor with a negative sign and a zero mask
392                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        ///
402        /// It uses the signed multiplier from figure 5.1 of
403        /// [Granlund and Montgomery, "Division by Invariant Integers using Multiplication" (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf).
404        #[derive(Debug, Clone, Copy)]
405        pub struct $add {
406            divisor: $t,
407            /// `m'` in figure 5.1
408            multiplier: $t,
409            /// `sh_post` in figure 5.1
410            shift: u32,
411        }
412
413        impl $add {
414            /// `|divisor|` must be at least 3 and not a power of two
415            const fn new(divisor: $t) -> Self {
416                let magnitude = divisor.unsigned_abs();
417                // ceil(log2(|divisor|)), which is at least 2 because |divisor| >= 3, so figure
418                // 5.1's `max(..., 1)` isn't needed
419                let l = <$t>::BITS - (magnitude - 1).leading_zeros();
420                // m = 1 + floor(2^(N + l - 1) / |divisor|) is between 2^(N - 1) and 2^N, so
421                // m - 2^N fits in the narrow type
422                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            /// Returns `(n / divisor, n % divisor)`, which can't overflow
431            ///
432            /// # Example
433            /// ```
434            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
435            #[doc = concat!("let ", stringify!($name), "::AddIndicator(divisor) = ", stringify!($name), "::new(-7).unwrap() else { unreachable!() };")]
436            /// assert_eq!(divisor.wrapping_div_rem(-100), (14, -2));
437            /// ```
438            #[inline]
439            pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
440                // `MULSH(m', n)` in figure 5.1
441                let high = ((self.multiplier as $wide * n as $wide) >> <$t>::BITS) as $t;
442                // The shift rounds down, and subtracting the sign of `n` rounds toward zero instead
443                let q = ((n + high) >> self.shift) - (n >> (<$t>::BITS - 1));
444                let sign = self.divisor >> (<$t>::BITS - 1);
445                // The remainder doesn't depend on the sign of the divisor, as section 3.1 of
446                // Lemire, Kaser and Kurz, "Faster Remainder by Direct Computation",
447                // https://arxiv.org/abs/1902.01961, states, so it uses `q` before the sign fix
448                // and `|divisor|`. `divisor` is never `MIN`, whose magnitude is a power of two
449                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    /// A `u32` divisor whose rounded-up multiplier isn't exact in N bits, see [`DivisorU32`]
490    ///
491    /// It computes `MULUH(m, n + 1) >> shift` with the rounded-down multiplier
492    /// `m = floor(2^(N+shift) / divisor)`, from
493    /// [ridiculous_fish, "Labor of Division (Episode III)"](https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html).
494    /// The increment saturates, so `u32::MAX` gives the quotient of `u32::MAX - 1`. The two are
495    /// equal unless the divisor divides `2^N - 1`, and those divisors always have an exact
496    /// rounded-up multiplier, as the post proves, so they never use this type.
497    ///
498    /// [`DivisorU32::new`] returns it only on aarch64 and on x86 with SSE4.1, so the example
499    /// checks nothing on other targets.
500    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)] // Takes too long
517            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                    // The quotient is monotone in `n`, so an error shows first at an end of a
549                    // quotient step `[k * d, k * d + d - 1]`, and the last steps are where the
550                    // multiplier's error is largest
551                    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)] // Takes too long
566            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                    // The ends of the last quotient steps on each side of zero, as in the
600                    // unsigned test
601                    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    /// Checks which variant `new` picks: `Up` when theorem 4.2 holds at `p = floor(log2(d))`,
630    /// otherwise `Down` when `$down` is true, otherwise `AddIndicator`. `$is_down` checks for `Down`,
631    /// which only `u32` has
632    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                // Every divisor of 2^N - 1, whose rounded-up multiplier always fits in N bits,
641                // which `Down`'s saturating increment relies on
642                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                    // `Down` would be wrong for these divisors at `MAX`, so check the values too.
681                    // `d` divides `MAX`, so `MAX` is the end of the last quotient step
682                    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    /// `DivisorU32::new` picks `AddIndicator` only on targets without cheap saturation, so this
711    /// checks it directly for the divisors that would use it
712    #[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}