devela/num/int/
divisor.rs

Help
1// devela::num::int::divisor
2
3#[allow(unused_imports)]
4use crate::{
5    _core::{fmt, hash, ops},
6    compile, iif, isize_up, paste, usize_up,
7};
8
9/// Faster divisor for division and modulo operations.
10///
11/// # Features
12/// It's implemented for the integer primitives enabled by the corresponding
13/// [capability features][crate::_info::features#capability-features]:
14/// [`_int_i8`][Self#impl-Divisor<i8>],
15/// [`_int_i16`][Self#impl-Divisor<i16>],
16/// [`_int_i32`][Self#impl-Divisor<i32>],
17/// [`_int_i64`][Self#impl-Divisor<i64>],
18/// [`_int_i128`][Self#impl-Divisor<i128>],
19/// [`_int_isize`][Self#impl-Divisor<isize>],
20/// [`_int_u8`][Self#impl-Divisor<u8>],
21/// [`_int_u16`][Self#impl-Divisor<u16>],
22/// [`_int_u32`][Self#impl-Divisor<u32>],
23/// [`_int_u64`][Self#impl-Divisor<u64>],
24/// [`_int_u128`][Self#impl-Divisor<u128>],
25/// [`_int_usize`][Self#impl-Divisor<usize>].
26///
27#[doc = crate::doc_!(vendor: "quickdiv")]
28#[must_use]
29#[derive(Clone, Copy)]
30pub struct Divisor<T> {
31    inner: DivisorInner<T>,
32}
33
34/// Inner representation of [`Divisor`].
35#[derive(Clone, Copy)]
36enum DivisorInner<T> {
37    Shift(T, u8),
38    MultiplyShift(T, T, u8),
39    MultiplyAddShift(T, T, u8),
40    /// *Variant only used for signed numbers.*
41    #[allow(dead_code)]
42    ShiftAndNegate(T, u8),
43    /// *Variant only used for signed numbers.*
44    #[allow(dead_code)]
45    MultiplyAddShiftNegate(T, T, u8),
46}
47
48/// Implements [`Divisor`]`<T>` for each enabled integer primitive.
49macro_rules! impl_divisor {
50    () => {
51        impl_divisor![signed
52            i8|u8|i16|u16:Y:"_int_i8", i16|u16|i32|u32:Y:"_int_i16", i32|u32|i64|u64:Y:"_int_i32",
53            i64|u64|i128|u128:PW:"_int_i64", i128|u128|i128|u128:N:"_int_i128",
54            isize|usize|isize_up|usize_up:Y:"_int_isize"
55        ];
56        impl_divisor![unsigned
57            u8|u16:Y:"_int_u8", u16|u32:Y:"_int_u16", u32|u64:Y:"_int_u32",
58            u64|u128:PW:"_int_u64", u128|u128:N:"_int_u128", usize|usize_up:Y:"_int_usize"
59        ];
60    };
61
62    (
63    // (un)signed entry arms
64    //
65    // # Arguments:
66    // $t:     the type. E.g. i8.
67    // $un:    the unsigned type of the same size. E.g. u8. (only for signed)
68    // $up:    the upcasted type. E.g. i16.
69    // $unup:  the unsigned upcasted type. E.g. u16. (only for signed)
70    // $is_up: upcasted behavior. Y:upcasted | N:not upcasted | PW depends on pointer width == 64
71    // $cap:   the capability feature that enables the current implementation.
72     signed $( $t:ty | $un:ty | $up:ty | $unup:ty : $is_up:ident : $cap:literal),+) => {
73        $( impl_divisor![@signed $t|$un|$up|$unup:$is_up:$cap]; )+
74    };
75    (unsigned $( $t:ty | $up:ty : $is_up:ident : $cap:literal),+) => {
76        $( impl_divisor![@unsigned $t|$up:$is_up:$cap]; )+
77    };
78    (
79    /* inner arms */
80     @signed $t:ty | $un:ty | $up:ty | $unup:ty : $is_up:ident : $cap:literal) => {
81        #[cfg(feature = $cap )]
82        impl_divisor![@traits $t];
83
84        #[cfg(feature = $cap )]
85        #[doc = crate::doc_availability!(feature = $cap)]
86        // #[cfg_attr(feature = "nightly_doc", doc(cfg(feature = $cap)))]
87        impl Divisor<$t> {
88            impl_divisor![@shared $t|$un|$up|$unup:$is_up:$cap]; // shared methods
89
90            /// Returns the absolute value of the signed primitive as its unsigned equivalent.
91            #[must_use]
92            const fn abs(n: $t) -> $un {
93                iif![n < 0; ((-1i8) as $un).wrapping_mul(n as $un); n as $un]
94            }
95
96            /// Creates a divisor which can be used for faster computation
97            /// of division and modulo by `d`.
98            ///
99            /// Returns `None` if `d` equals zero.
100            ///
101            /// # Examples
102            /// ```
103            /// # use devela::Divisor;
104            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(-21).unwrap();"]]
105            /// ```
106            #[must_use]
107            pub const fn new(d: $t) -> Option<Divisor<$t>> {
108                if d == 0 {
109                    Self::cold_0_divisor()
110                } else {
111                    let ud = Self::abs(d);
112                    let shift = ud.ilog2() as u8;
113                    let inner = if ud.is_power_of_two() {
114                        iif![d > 0; DivisorInner::Shift(d, shift); DivisorInner::ShiftAndNegate(d, shift)]
115                    } else {
116                        let (mut magic, rem) = Self::div_rem_wide_by_base(1 << (shift - 1), ud);
117                        let e = ud - rem;
118                        if e < 1 << shift {
119                            DivisorInner::MultiplyShift(d, d.signum() * (magic as $t + 1), shift - 1)
120                        } else {
121                            magic *= 2;
122                            let (doubled_rem, overflowed) = rem.overflowing_mul(2);
123                            iif![doubled_rem >= ud || overflowed; magic += 1];
124                            magic += 1;
125                            if d > 0 {
126                                DivisorInner::MultiplyAddShift(d, magic as $t, shift)
127                            } else {
128                                DivisorInner::MultiplyAddShiftNegate(d, -(magic as $t), shift)
129                            }
130                        }
131                    };
132
133                    Some(Self { inner })
134                }
135            }
136
137            /// Returns the value that was used to construct this divisor as a primitive type.
138            ///
139            /// # Examples
140            /// ```
141            /// # use devela::Divisor;
142            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(-15).unwrap();"]]
143            /// assert_eq!(d.get(), -15);
144            /// ```
145            #[must_use]
146            pub const fn get(&self) -> $t {
147                match self.inner {
148                    DivisorInner::Shift(d, _) => d,
149                    DivisorInner::ShiftAndNegate(d, _) => d,
150                    DivisorInner::MultiplyShift(d, _, _) => d,
151                    DivisorInner::MultiplyAddShift(d, _, _) => d,
152                    DivisorInner::MultiplyAddShiftNegate(d, _, _) => d,
153                }
154            }
155
156            /// Returns `true` if `n` is divisible by `self`.
157            ///
158            /// We take `0` to be divisible by all non-zero numbers.
159            ///
160            /// # Examples
161            /// ```
162            /// # use devela::Divisor;
163            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(-9).unwrap();"]]
164            /// assert!(d.divides(27));
165            /// ```
166            #[must_use]
167            pub const fn divides(&self, n: $t) -> bool {
168                self.rem_of(n) == 0
169            }
170
171            /// Returns the remainder of dividing `n` by `self`.
172            ///
173            /// # Examples
174            /// ```
175            /// # use devela::Divisor;
176            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(21).unwrap();"]]
177            /// let rem = d.rem_of(-30);
178            /// assert_eq!(rem, -9);
179            /// ```
180            #[must_use]
181            pub const fn rem_of(&self, n: $t) -> $t {
182                n.wrapping_add((self.get().wrapping_mul(self.div_of(n))).wrapping_mul(-1))
183            }
184
185            /// Returns the result of dividing `n` by `self`.
186            ///
187            /// This will perform a wrapping division, i.e.
188            #[doc = concat!("`Divisor::<", stringify!($t), ">::new(-1).unwrap().div_of(",
189                stringify!($t) ,"::MIN)`")]
190            /// will always silently return
191            #[doc = concat!("`", stringify!($t) ,"::MIN`")]
192            /// whether the program was compiled with `overflow-checks` turned off or not.
193            ///
194            /// # Examples
195            /// ```
196            /// # use devela::Divisor;
197            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(13).unwrap();"]]
198            /// let div = d.div_of(-30);
199            /// assert_eq!(div, -2);
200            /// ```
201            #[must_use]
202            pub const fn div_of(&self, n: $t) -> $t {
203                match self.inner {
204                    DivisorInner::Shift(_, shift) => {
205                        let mask = (1 as $t << shift).wrapping_sub(1);
206                        let b = (n >> (<$t>::BITS - 1)) & mask;
207                        n.wrapping_add(b) >> shift
208                    },
209                    DivisorInner::ShiftAndNegate(_, shift) => {
210                        let mask = (1 as $t << shift).wrapping_sub(1);
211                        let b = (n >> (<$t>::BITS - 1)) & mask;
212                        let t = n.wrapping_add(b) >> shift;
213                        t.wrapping_mul(-1)
214                    },
215                    DivisorInner::MultiplyShift(_, magic, shift) => {
216                        let q = Self::mulh(magic, n) >> shift;
217                        iif![q < 0; q + 1; q]
218                    },
219                    DivisorInner::MultiplyAddShift(_, magic, shift) => {
220                        let q = Self::mulh(magic, n);
221                        let t = q.wrapping_add(n) >> shift;
222                        iif![t < 0; t + 1; t]
223                    },
224                    DivisorInner::MultiplyAddShiftNegate(_, magic, shift) => {
225                        let q = Self::mulh(magic, n);
226                        let t = q.wrapping_add(n.wrapping_mul(-1)) >> shift;
227                        iif![t < 0; t + 1; t]
228                    }
229                }
230            }
231        }
232    };
233
234    (@unsigned $t:ty | $up:ty : $is_up:ident : $cap:literal) => {
235        #[cfg(feature = $cap )]
236        impl_divisor![@traits $t];
237
238        #[cfg(feature = $cap )]
239        #[doc = crate::doc_availability!(feature = $cap)]
240        // #[cfg_attr(feature = "nightly_doc", doc(cfg(feature = $cap)))]
241        impl Divisor<$t> {
242            impl_divisor![@shared $t|$t|$up|$up:$is_up:$cap]; // shared methods
243
244            /// Creates a divisor which can be used for faster computation
245            /// of division and modulo by `d`.
246            ///
247            /// Returns `None` if `d` equals zero.
248            ///
249            /// # Examples
250            /// ```
251            /// # use devela::Divisor;
252            #[doc = concat!["let _d = Divisor::<", stringify![$t], ">::new(5);"]]
253            /// ```
254            #[must_use]
255            pub const fn new(d: $t) -> Option<Divisor<$t>> {
256                if d == 0 {
257                    Self::cold_0_divisor()
258                } else {
259                    let shift = d.ilog2() as u8;
260                    let inner = if d.is_power_of_two() {
261                        DivisorInner::Shift(d, shift)
262                    } else {
263                        let (mut magic, rem) = Self::div_rem_wide_by_base(1 << shift, d);
264                        let e = d - rem;
265                        if e < 1 << shift {
266                            DivisorInner::MultiplyShift(d, magic + 1, shift)
267                        } else {
268                            magic = magic.wrapping_mul(2);
269                            let (doubled_rem, overflowed) = rem.overflowing_mul(2);
270                            if doubled_rem >= d || overflowed { magic += 1; }
271                            DivisorInner::MultiplyAddShift(d, magic + 1, shift)
272                        }
273                    };
274                    Some(Self { inner })
275                }
276            }
277
278            /// Returns the value that was used to construct this divisor as a primitive type.
279            ///
280            /// # Examples
281            /// ```
282            /// # use devela::Divisor;
283            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(7).unwrap();"]]
284            /// assert_eq!(d.get(), 7);
285            /// ```
286            #[must_use]
287            pub const fn get(&self) -> $t {
288                match self.inner {
289                    DivisorInner::Shift(d, _) => d,
290                    DivisorInner::MultiplyShift(d, _, _) => d,
291                    DivisorInner::MultiplyAddShift(d, _, _) => d,
292                    _ => unreachable![],
293                }
294            }
295
296            /// Returns `true` if `n` is divisible by `self`.
297            ///
298            /// We take `0` to be divisible by all non-zero numbers.
299            ///
300            /// # Examples
301            /// ```
302            /// # use devela::Divisor;
303            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(17).unwrap();"]]
304            /// assert!(d.divides(34));
305            /// ```
306            #[must_use]
307            pub const fn divides(&self, n: $t) -> bool {
308                self.rem_of(n) == 0
309            }
310
311            /// Returns the remainder of dividing `n` by `self`.
312            ///
313            /// # Examples
314            /// ```
315            /// # use devela::Divisor;
316            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(11).unwrap();"]]
317            /// let rem = d.rem_of(30);
318            /// assert_eq!(rem, 8);
319            /// ```
320            #[must_use]
321            pub const fn rem_of(&self, n: $t) -> $t {
322                n - self.get() * self.div_of(n)
323            }
324
325            /// Returns the result of dividing `n` by `self`.
326            ///
327            /// # Examples
328            /// ```
329            /// # use devela::Divisor;
330            #[doc = concat!["let d = Divisor::<", stringify![$t], ">::new(17).unwrap();"]]
331            /// let div = d.div_of(34);
332            /// assert_eq!(div, 2);
333            /// ```
334            #[must_use]
335            pub const fn div_of(&self, n: $t) -> $t {
336                match self.inner {
337                    DivisorInner::Shift(_, shift) => n >> shift,
338                    DivisorInner::MultiplyShift(_, magic, shift) => Self::mulh(magic, n) >> shift,
339                    DivisorInner::MultiplyAddShift(_, magic, shift) => {
340                        let q = Self::mulh(magic, n);
341                        let t = ((n - q) >> 1) + q;
342                        t >> shift
343                    },
344                    _ => unreachable![], // the remaining arms are only for signed
345                }
346            }
347        }
348    };
349
350    (@shared $t:ty | $un:ty | $up:ty | $unup:ty : $is_up:ident : $cap:literal) => {
351        paste!{
352            /// Alias of [`new`][Self::new] with a unique name that helps type inference.
353            pub const fn [<new_ $t>](d: $t) -> Option<Divisor<$t>> { Self::new(d) }
354        }
355
356        /// Helper function to be called from the cold path branch when divisor == 0.
357        #[cold] #[inline(never)]
358        const fn cold_0_divisor() -> Option<Self> { None }
359
360        /// Multiply two words together, returning only the top half of the product.
361        ///
362        /// Works by extending the factors to 2N-bits, using the built-in 2N-by-2N-bit
363        /// multiplication and shifting right to the top half only.
364        #[compile(any(same($is_up, Y), all(same($is_up, PW), pointer_width_eq(64))))]
365        const fn mulh(x: $t, y: $t) -> $t {
366            (((x as $up) * (y as $up)) >> <$t>::BITS) as $t
367        }
368        /// Non-upcasting version, adapted from Figure 8-2 in Hacker's Delight, 2nd Ed.
369        #[compile(any(same($is_up, N), all(same($is_up, PW), not(pointer_width_eq(64)))))]
370        const fn mulh(x: $t, y: $t) -> $t {
371            const HALF_WIDTH_BITS: u32 = <$t>::BITS / 2;
372            const LOWER_HALF_MASK: $t = (1 << HALF_WIDTH_BITS) - 1;
373
374            let x_low = x & LOWER_HALF_MASK;
375            let y_low = y & LOWER_HALF_MASK;
376            let t = x_low.wrapping_mul(y_low);
377            let k = t >> HALF_WIDTH_BITS;
378
379            let x_high = x >> HALF_WIDTH_BITS;
380            let t = x_high.wrapping_mul(y_low) + k;
381            let k = t & LOWER_HALF_MASK;
382            let w1 = t >> HALF_WIDTH_BITS;
383
384            let y_high = y >> HALF_WIDTH_BITS;
385            let t = x_low.wrapping_mul(y_high) + k;
386            let k = t >> HALF_WIDTH_BITS;
387
388            x_high.wrapping_mul(y_high) + w1 + k
389        }
390
391        /// Divide a 2N-bit dividend by an N-bit divisor with remainder, assuming
392        /// that the result fits into N bits and that the lower half of bits of the
393        /// dividend are all zero.
394        ///
395        /// Works by extending the dividend to 2N-bits and then using the built-in
396        /// 2N-by-2N-bit division method.
397        #[compile(any(same($is_up, Y), all(same($is_up, PW), pointer_width_eq(64))))]
398        const fn div_rem_wide_by_base(top_half: $un, d: $un) -> ($un, $un) {
399            let n = (top_half as $unup) << <$un>::BITS;
400            let quot = (n / (d as $unup)) as $un;
401            let rem = (n % (d as $unup)) as $un;
402            (quot, rem)
403        }
404        /// Non-upcasting version, adapted from Figure 9-3 in Hacker's Delight, 2nd Ed.
405        #[compile(any(same($is_up, N), all(same($is_up, PW), not(pointer_width_eq(64)))))]
406        const fn div_rem_wide_by_base(top_half: $un, d: $un) -> ($un, $un) {
407            const HALF_WORD_BITS: u32 = <$un>::BITS / 2;
408            const BASE: $un = 1 << HALF_WORD_BITS;
409            let s = d.leading_zeros();
410            let v = d << s;
411            let vn1 = v >> HALF_WORD_BITS;
412            let vn0 = v & (BASE - 1);
413            let un32 = top_half << s;
414            let mut q1 = un32 / vn1;
415            let mut rhat = un32 - q1 * vn1;
416            loop {
417                if q1 >= BASE || q1 * vn0 > (rhat << HALF_WORD_BITS) {
418                    q1 -= 1;
419                    rhat += vn1;
420                    iif![rhat < BASE; continue];
421                }
422                break;
423            }
424            let un21 = (un32 << HALF_WORD_BITS).wrapping_sub(q1.wrapping_mul(v));
425            let mut q0 = un21 / vn1;
426            rhat = un21 - q0 * vn1;
427            loop {
428                if q0 >= BASE || q0 * vn0 > (rhat << HALF_WORD_BITS) {
429                    q0 -= 1;
430                    rhat += vn1;
431                    iif![rhat < BASE; continue];
432                }
433                break;
434            }
435            let r = ((un21 << HALF_WORD_BITS).wrapping_sub(q0.wrapping_mul(v))) >> s;
436            ((q1 << HALF_WORD_BITS) + q0, r)
437        }
438    };
439
440    (@traits $t:ty) => {
441        impl PartialEq for Divisor<$t> {
442            fn eq(&self, other: &Self) -> bool { self.get() == other.get() }
443        }
444        impl Eq for Divisor<$t> {}
445        impl fmt::Debug for Divisor<$t> {
446            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", self.get()) }
447        }
448        impl fmt::Display for Divisor<$t> {
449            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", self.get()) }
450        }
451        impl hash::Hash for Divisor<$t> {
452            fn hash<H: hash::Hasher>(&self, state: &mut H) { self.get().hash(state); }
453        }
454        impl ops::Div<Divisor<$t>> for $t {
455            type Output = $t;
456            fn div(self, rhs: Divisor<$t>) -> Self::Output { rhs.div_of(self) }
457        }
458        impl ops::DivAssign<Divisor<$t>> for $t {
459            fn div_assign(&mut self, rhs: Divisor<$t>) { *self = rhs.div_of(*self) }
460        }
461        impl ops::Rem<Divisor<$t>> for $t {
462            type Output = $t;
463            fn rem(self, rhs: Divisor<$t>) -> Self::Output { rhs.rem_of(self) }
464        }
465        impl ops::RemAssign<Divisor<$t>> for $t {
466            fn rem_assign(&mut self, rhs: Divisor<$t>) { *self = rhs.rem_of(*self) }
467        }
468    };
469}
470impl_divisor!();
devela/num/int/divisor.rs

devela/num/int/
divisor.rs
