devela 0.27.0

// devela::num::dom::int::define_divisor
//
//! Defines [`define_divisor!`].
//

#[cfg(feature = "_docs_examples")]
define_divisor! {
    #[doc = crate::_tags!(example num)]
    /// An example divisor helper generated by [`define_divisor!`].
    #[doc = crate::_doc_location!("num/dom/int")]
    ///
    /// This type exists to document the methods produced by the macro.
    ///
    /// Implemented for [`i32`](#impl-DivisorExample<i32>)
    /// and [`u32`](#impl-DivisorExample<u32>).
    /// *(The macro supports all integer primitives)*
    pub struct DivisorExample:<> impl (i32, u32)
}

#[doc(hidden)]
/// Inner representation of a type defined with [`define_divisor`].
#[derive(Clone, Copy)]
pub enum DivisorInner<T> {
    Shift(T, u8),
    MultiplyShift(T, T, u8),
    MultiplyAddShift(T, T, u8),
    #[allow(dead_code, reason = "only used for signed integers")]
    ShiftAndNegate(T, u8),
    #[allow(dead_code, reason = "only used for signed integers")]
    MultiplyAddShiftNegate(T, T, u8),
}

#[doc = crate::_tags!(construction code num)]
/// Defines a divisor struct for faster division and modulo operations.
#[doc = crate::_doc_location!("num/dom/int")]
///
/// This macro generates a *divisor helper type* that precomputes information
/// about a divisor to speed up repeated division and remainder operations.
///
/// The macro supports both:
/// - **Concrete divisor types**, bound to a single primitive integer.
/// - **Generic divisor shells**, which can later be implemented for multiple primitive integers.
///
/// ---
///
/// ## Syntax overview
///
/// The macro follows a common grammar:
/// ```text
/// struct Name : Spec [impl (targets)]
/// impl   Name : Spec (targets)
/// ```
///
/// Where:
/// - `Name` is the type name
/// - `Spec` is either:
///   - `(T)`   for a concrete primitive type
///   - `<>`    to declare a generic divisor shell
/// - `targets` is a comma-separated list of primitive integer types
///
/// ## Examples
/// ```
/// # use devela::define_divisor;
/// // Define and implement a divisor type for a single primitive:
/// define_divisor![pub struct DivU8 : (u8) impl];
/// let d = DivU8::new(5).unwrap();
/// let x = d.div_of(42);
///
/// // Define a generic divisor type without implementations:
/// define_divisor![pub struct Div : <>];
///
/// // Attach implementations to a previously defined generic divisor:
/// define_divisor![impl Div : <> (i8, u32, usize)];
///
/// // Define a generic divisor and immediately implement it:
/// define_divisor![pub struct FastDiv : <> impl (i8, u32, u128, usize)];
/// ```
/// See [`DivisorExample`] for the fully documented methods generated by this macro.
///
/// ---
///
/// ## Notes
/// - All implementations are resolved at compile time.
/// - Only supported integer primitives are accepted as targets.
/// - Passing an unsupported type results in a compile-time error.
/// - Division by zero is checked when constructing a divisor.
#[doc = crate::_doc!(vendor: "quickdiv")]
#[macro_export]
#[cfg_attr(cargo_primary_package, doc(hidden))]
macro_rules! define_divisor {
    (
    /* public macro arms */

        // new individual definition + impl
        $(#[$attr:meta])* $vis:vis struct $Name:ident : ($T:ident) impl) => {
        $(#[$attr])* #[must_use] #[derive(Clone, Copy)]
        $vis struct $Name { inner: $crate::DivisorInner<$T> }

        $crate::define_divisor!(impl $Name : ($T));
    };
    (
        // new generic definition + impl(s)
        $(#[$attr:meta])* $vis:vis struct $Name:ident : <> impl ($($T:ident),+)) => {

        $(#[$attr])* #[must_use] #[derive(Clone, Copy)]
        $vis struct $Name<T> { inner: $crate::DivisorInner<T> }

        $( $crate::define_divisor!(%impl $Name<$T>, $Name; $T); )+
    };
    (
        // new individual definition
        $(#[$attr:meta])* $vis:vis struct $Name:ident : ($T:ident)) => {
        $(#[$attr])* #[must_use] #[derive(Clone, Copy)]
        $vis struct $Name { inner: $crate::DivisorInner<$T> }
    };
    (
        // new generic definition
        $(#[$attr:meta])* $vis:vis struct $Name:ident : <>) => {
        $(#[$attr])* #[must_use] #[derive(Clone, Copy)]
        $vis struct $Name<T> { inner: $crate::DivisorInner<T> }
    };
    (
        // individual impl
        impl $Name:ident : ($T:ident)) => {
        $crate::define_divisor!(%impl $Name, $Name; $T);
    };
    (
        // generic impl(s)
        impl $Name:ident : <> ($($T:ident),+)) => {
        $( $crate::define_divisor!(%impl $Name<$T>, $Name; $T); )+
    };

    // $N: the full type
    // $n: just the name
    (
    /* private API */
    // supported representations
     %impl $Type:ty, $Name:ident; u8) => {
        $crate::define_divisor!(%impl_u $Type,$Name; u8|u16:Y); };
    (%impl $Type:ty,$Name:ident; u16) => {
        $crate::define_divisor!(%impl_u $Type,$Name; u16|u32:Y); };
    (%impl $Type:ty,$Name:ident; u32) => {
        $crate::define_divisor!(%impl_u $Type,$Name; u32|u64:Y); };
    (%impl $Type:ty,$Name:ident; u64) => {
        $crate::define_divisor!(%impl_u $Type,$Name; u64|u128:PW); };
    (%impl $Type:ty,$Name:ident; u128) => {
        $crate::define_divisor!(%impl_u $Type,$Name; u128|u128:N); };
    (%impl $Type:ty,$Name:ident; usize) => {
        $crate::define_divisor!(%impl_u $Type,$Name; usize|$crate::usize_up:Y); };
    (%impl $Type:ty,$Name:ident; i8) => {
        $crate::define_divisor!(%impl_i $Type,$Name; i8|u8|i16|u16:Y); };
    (%impl $Type:ty,$Name:ident; i16) => {
        $crate::define_divisor!(%impl_i $Type,$Name; i16|u16|i32|u32:Y); };
    (%impl $Type:ty,$Name:ident; i32) => {
        $crate::define_divisor!(%impl_i $Type,$Name; i32|u32|i64|u64:Y); };
    (%impl $Type:ty,$Name:ident; i64) => {
        $crate::define_divisor!(%impl_i $Type,$Name; i64|u64|i128|u128:PW); };
    (%impl $Type:ty,$Name:ident; i128) => {
        $crate::define_divisor!(%impl_i $Type,$Name; i128|u128|i128|u128:N); };
    (%impl $Type:ty,$Name:ident; isize) => {
        $crate::define_divisor!(%impl_i $Type,$Name;
            isize|usize|$crate::isize_up|$crate::usize_up:Y); };

    // signed implementations
    // # Arguments:
    // $t:     the type. E.g. i8.
    // $un:    the unsigned type of the same size. E.g. u8. (only for signed)
    // $up:    the upcasted type. E.g. i16.
    // $unup:  the unsigned upcasted type. E.g. u16. (only for signed)
    // $is_up: upcasted behavior. Y:upcasted | N:not upcasted | PW depends on pointer width == 64
    //
    (// specific implementations
     %impl_i $Type:ty, $Name:ident; $t:ty | $un:ty | $up:ty | $unup:ty : $is_up:ident) => {
        define_divisor![%traits $Type, $Name; $t]; // utility traits

        impl $Type {
            define_divisor![%shared $Type,$Name; $t|$un|$up|$unup:$is_up]; // shared methods

            /// Returns the absolute value of the signed primitive as its unsigned equivalent.
            #[must_use]
            const fn abs(n: $t) -> $un {
                $crate::is![n < 0, ((-1i8) as $un).wrapping_mul(n as $un), n as $un]
            }

            /// Creates a divisor which can be used for faster computation
            /// of division and modulo by `d`.
            ///
            /// Returns `None` if `d` equals zero.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(-21).unwrap();"]]
            /// # }
            /// ```
            #[must_use]
            pub const fn new(d: $t) -> Option<$Type> {
                if d == 0 {
                    Self::cold_0_divisor()
                } else {
                    let ud = Self::abs(d);
                    let shift = ud.ilog2() as u8;
                    let inner = if ud.is_power_of_two() {
                        if d > 0 { $crate::DivisorInner::Shift(d, shift) }
                        else { $crate::DivisorInner::ShiftAndNegate(d, shift) }
                    } else {
                        let (mut magic, rem) = Self::div_rem_wide_by_base(1 << (shift - 1), ud);
                        let e = ud - rem;
                        if e < 1 << shift {
                            $crate::DivisorInner::MultiplyShift(d, d.signum()
                                * (magic as $t + 1), shift - 1)
                        } else {
                            magic *= 2;
                            let (doubled_rem, overflowed) = rem.overflowing_mul(2);
                            $crate::is![doubled_rem >= ud || overflowed, magic += 1];
                            magic += 1;
                            if d > 0 {
                                $crate::DivisorInner::MultiplyAddShift(d, magic as $t, shift)
                            } else {
                                $crate::DivisorInner::MultiplyAddShiftNegate(d, -(magic as $t), shift)
                            }
                        }
                    };
                    Some(Self { inner })
                }
            }

            /// Returns the value that was used to construct this divisor as a primitive type.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(-15).unwrap();"]]
            /// assert_eq!(d.get(), -15);
            /// # }
            /// ```
            #[must_use]
            pub const fn get(&self) -> $t {
                match self.inner {
                    $crate::DivisorInner::Shift(d, _) => d,
                    $crate::DivisorInner::ShiftAndNegate(d, _) => d,
                    $crate::DivisorInner::MultiplyShift(d, _, _) => d,
                    $crate::DivisorInner::MultiplyAddShift(d, _, _) => d,
                    $crate::DivisorInner::MultiplyAddShiftNegate(d, _, _) => d,
                }
            }

            /// Returns `true` if `n` is divisible by `self`.
            ///
            /// We take `0` to be divisible by all non-zero numbers.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(-9).unwrap();"]]
            /// assert!(d.divides(27));
            /// # }
            /// ```
            #[must_use]
            pub const fn divides(&self, n: $t) -> bool {
                self.rem_of(n) == 0
            }

            /// Returns the remainder of dividing `n` by `self`.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(21).unwrap();"]]
            /// let rem = d.rem_of(-30);
            /// assert_eq!(rem, -9);
            /// # }
            /// ```
            #[must_use]
            pub const fn rem_of(&self, n: $t) -> $t {
                n.wrapping_add((self.get().wrapping_mul(self.div_of(n))).wrapping_mul(-1))
            }

            /// Returns the result of dividing `n` by `self`.
            ///
            /// This will perform a wrapping division, i.e.
            #[doc = concat!("`DivisorExample::<", stringify!($t), ">::new(-1).unwrap().div_of(",
                stringify!($t) ,"::MIN)`")]
            /// will always silently return
            #[doc = concat!("`", stringify!($t) ,"::MIN`")]
            /// whether the program was compiled with `overflow-checks` turned off or not.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(13).unwrap();"]]
            /// let div = d.div_of(-30);
            /// assert_eq!(div, -2);
            /// # }
            /// ```
            #[must_use]
            pub const fn div_of(&self, n: $t) -> $t {
                match self.inner {
                    $crate::DivisorInner::Shift(_, shift) => {
                        let mask = (1 as $t << shift).wrapping_sub(1);
                        let b = (n >> (<$t>::BITS - 1)) & mask;
                        n.wrapping_add(b) >> shift
                    },
                    $crate::DivisorInner::ShiftAndNegate(_, shift) => {
                        let mask = (1 as $t << shift).wrapping_sub(1);
                        let b = (n >> (<$t>::BITS - 1)) & mask;
                        let t = n.wrapping_add(b) >> shift;
                        t.wrapping_mul(-1)
                    },
                    $crate::DivisorInner::MultiplyShift(_, magic, shift) => {
                        let q = Self::mulh(magic, n) >> shift;
                        $crate::is![q < 0, q + 1, q]
                    },
                    $crate::DivisorInner::MultiplyAddShift(_, magic, shift) => {
                        let q = Self::mulh(magic, n);
                        let t = q.wrapping_add(n) >> shift;
                        $crate::is![t < 0, t + 1, t]
                    },
                    $crate::DivisorInner::MultiplyAddShiftNegate(_, magic, shift) => {
                        let q = Self::mulh(magic, n);
                        let t = q.wrapping_add(n.wrapping_mul(-1)) >> shift;
                        $crate::is![t < 0, t + 1, t]
                    }
                }
            }
        }
    };
    // unsigned implementations
    //
    // # Arguments:
    // $t:     the type. E.g. i8.
    // $up:    the upcasted type. E.g. i16.
    // $is_up: upcasted behavior. Y:upcasted | N:not upcasted | PW depends on pointer width == 64
    (%impl_u $Type:ty, $Name:ident; $t:ty | $up:ty : $is_up:ident) => {
        define_divisor![%traits $Type, $Name; $t]; // utility traits

        impl $Type {
            define_divisor![%shared $Type, $Name; $t|$t|$up|$up:$is_up]; // shared methods

            /// Creates a divisor which can be used for faster computation
            /// of division and modulo by `d`.
            ///
            /// Returns `None` if `d` equals zero.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let _d = DivisorExample::<", stringify![$t], ">::new(5);"]]
            /// # }
            /// ```
            #[must_use]
            pub const fn new(d: $t) -> Option<$Type> {
                if d == 0 {
                    Self::cold_0_divisor()
                } else {
                    let shift = d.ilog2() as u8;
                    let inner = if d.is_power_of_two() {
                        $crate::DivisorInner::Shift(d, shift)
                    } else {
                        let (mut magic, rem) = Self::div_rem_wide_by_base(1 << shift, d);
                        let e = d - rem;
                        if e < 1 << shift {
                            $crate::DivisorInner::MultiplyShift(d, magic + 1, shift)
                        } else {
                            magic = magic.wrapping_mul(2);
                            let (doubled_rem, overflowed) = rem.overflowing_mul(2);
                            if doubled_rem >= d || overflowed { magic += 1; }
                            $crate::DivisorInner::MultiplyAddShift(d, magic + 1, shift)
                        }
                    };
                    Some(Self { inner })
                }
            }

            /// Returns the value that was used to construct this divisor as a primitive type.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(7).unwrap();"]]
            /// assert_eq!(d.get(), 7);
            /// # }
            /// ```
            #[must_use]
            pub const fn get(&self) -> $t {
                match self.inner {
                    $crate::DivisorInner::Shift(d, _) => d,
                    $crate::DivisorInner::MultiplyShift(d, _, _) => d,
                    $crate::DivisorInner::MultiplyAddShift(d, _, _) => d,
                    _ => unreachable![],
                }
            }

            /// Returns `true` if `n` is divisible by `self`.
            ///
            /// We take `0` to be divisible by all non-zero numbers.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(17).unwrap();"]]
            /// assert!(d.divides(34));
            /// # }
            /// ```
            #[must_use]
            pub const fn divides(&self, n: $t) -> bool {
                self.rem_of(n) == 0
            }

            /// Returns the remainder of dividing `n` by `self`.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(11).unwrap();"]]
            /// let rem = d.rem_of(30);
            /// assert_eq!(rem, 8);
            /// # }
            /// ```
            #[must_use]
            pub const fn rem_of(&self, n: $t) -> $t {
                n - self.get() * self.div_of(n)
            }

            /// Returns the result of dividing `n` by `self`.
            ///
            /// # Examples
            /// ```
            /// # #[cfg(feature = "_docs_examples")] {
            /// # use devela::DivisorExample;
            #[doc = concat!["let d = DivisorExample::<", stringify![$t], ">::new(17).unwrap();"]]
            /// let div = d.div_of(34);
            /// assert_eq!(div, 2);
            /// # }
            /// ```
            #[must_use]
            pub const fn div_of(&self, n: $t) -> $t {
                match self.inner {
                    $crate::DivisorInner::Shift(_, shift) => n >> shift,
                    $crate::DivisorInner::MultiplyShift(_, magic, shift)
                        => Self::mulh(magic, n) >> shift,
                    $crate::DivisorInner::MultiplyAddShift(_, magic, shift) => {
                        let q = Self::mulh(magic, n);
                        let t = ((n - q) >> 1) + q;
                        t >> shift
                    },
                    _ => unreachable![], // the remaining arms are only for signed
                }
            }
        }
    };

    (%shared $Type:ty, $Name:ident; $t:ty | $un:ty | $up:ty | $unup:ty : $is_up:ident) => {
        $crate::paste!{
            /// Alias of [`new`][Self::new] with a unique name that helps type inference.
            pub const fn [<new_ $t>](d: $t) -> Option<$Type> { Self::new(d) }
        }

        /// Helper function to be called from the cold path branch when divisor == 0.
        #[cold] #[inline(never)]
        const fn cold_0_divisor() -> Option<Self> { None }

        /// Multiply two words together, returning only the top half of the product.
        ///
        /// Works by extending the factors to 2N-bits, using the built-in 2N-by-2N-bit
        /// multiplication and shifting right to the top half only.
        #[$crate::compile(any(same($is_up, Y), all(same($is_up, PW), pointer_width_eq(64))))]
        const fn mulh(x: $t, y: $t) -> $t {
            (((x as $up) * (y as $up)) >> <$t>::BITS) as $t
        }
        /// Non-upcasting version, adapted from Figure 8-2 in Hacker's Delight, 2nd Ed.
        #[$crate::compile(any(same($is_up, N), all(same($is_up, PW), not(pointer_width_eq(64)))))]
        const fn mulh(x: $t, y: $t) -> $t {
            const HALF_WIDTH_BITS: u32 = <$t>::BITS / 2;
            const LOWER_HALF_MASK: $t = (1 << HALF_WIDTH_BITS) - 1;

            let x_low = x & LOWER_HALF_MASK;
            let y_low = y & LOWER_HALF_MASK;
            let t = x_low.wrapping_mul(y_low);
            let k = t >> HALF_WIDTH_BITS;

            let x_high = x >> HALF_WIDTH_BITS;
            let t = x_high.wrapping_mul(y_low) + k;
            let k = t & LOWER_HALF_MASK;
            let w1 = t >> HALF_WIDTH_BITS;

            let y_high = y >> HALF_WIDTH_BITS;
            let t = x_low.wrapping_mul(y_high) + k;
            let k = t >> HALF_WIDTH_BITS;

            x_high.wrapping_mul(y_high) + w1 + k
        }

        /// Divide a 2N-bit dividend by an N-bit divisor with remainder, assuming
        /// that the result fits into N bits and that the lower half of bits of the
        /// dividend are all zero.
        ///
        /// Works by extending the dividend to 2N-bits and then using the built-in
        /// 2N-by-2N-bit division method.
        #[$crate::compile(any(same($is_up, Y), all(same($is_up, PW), pointer_width_eq(64))))]
        const fn div_rem_wide_by_base(top_half: $un, d: $un) -> ($un, $un) {
            let n = (top_half as $unup) << <$un>::BITS;
            let quot = (n / (d as $unup)) as $un;
            let rem = (n % (d as $unup)) as $un;
            (quot, rem)
        }
        /// Non-upcasting version, adapted from Figure 9-3 in Hacker's Delight, 2nd Ed.
        #[$crate::compile(any(same($is_up, N), all(same($is_up, PW), not(pointer_width_eq(64)))))]
        const fn div_rem_wide_by_base(top_half: $un, d: $un) -> ($un, $un) {
            const HALF_WORD_BITS: u32 = <$un>::BITS / 2;
            const BASE: $un = 1 << HALF_WORD_BITS;
            let s = d.leading_zeros();
            let v = d << s;
            let vn1 = v >> HALF_WORD_BITS;
            let vn0 = v & (BASE - 1);
            let un32 = top_half << s;
            let mut q1 = un32 / vn1;
            let mut rhat = un32 - q1 * vn1;
            loop {
                if q1 >= BASE || q1 * vn0 > (rhat << HALF_WORD_BITS) {
                    q1 -= 1;
                    rhat += vn1;
                    if rhat < BASE { continue }
                }
                break;
            }
            let un21 = (un32 << HALF_WORD_BITS).wrapping_sub(q1.wrapping_mul(v));
            let mut q0 = un21 / vn1;
            rhat = un21 - q0 * vn1;
            loop {
                if q0 >= BASE || q0 * vn0 > (rhat << HALF_WORD_BITS) {
                    q0 -= 1;
                    rhat += vn1;
                    if rhat < BASE { continue }
                }
                break;
            }
            let r = ((un21 << HALF_WORD_BITS).wrapping_sub(q0.wrapping_mul(v))) >> s;
            ((q1 << HALF_WORD_BITS) + q0, r)
        }
    };
    (%traits $Type:ty, $Name:ident; $t:ty) => {
        // TODO IMPROVE

        impl PartialEq for $Type {
            fn eq(&self, other: &Self) -> bool { self.get() == other.get() }
        }
        impl Eq for $Type {}
        impl $crate::Debug for $Type {
            fn fmt(&self, f: &mut $crate::Formatter<'_>) -> $crate::FmtResult<()> { write!(f, "{}", self.get()) }
        }
        impl $crate::Display for $Type {
            fn fmt(&self, f: &mut $crate::Formatter<'_>) -> $crate::FmtResult<()> { write!(f, "{}", self.get()) }
        }
        impl $crate::Hash for $Type {
            fn hash<H: $crate::Hasher>(&self, state: &mut H) { self.get().hash(state); }
        }
        impl $crate::Div<$Type> for $t {
            type Output = $t;
            fn div(self, rhs: $Type) -> Self::Output { rhs.div_of(self) }
        }
        impl $crate::DivAssign<$Type> for $t {
            fn div_assign(&mut self, rhs: $Type) { *self = rhs.div_of(*self) }
        }
        impl $crate::Rem<$Type> for $t {
            type Output = $t;
            fn rem(self, rhs: $Type) -> Self::Output { rhs.rem_of(self) }
        }
        impl $crate::RemAssign<$Type> for $t {
            fn rem_assign(&mut self, rhs: $Type) { *self = rhs.rem_of(*self) }
        }
    };

    // ($($tt:tt)*) => {
    //     compile_error![ concat!("Invalid input for `define_divisor!`:\n\t", // MAYBE
    //     stringify!($($tt)*))];
    // };
}
#[doc(inline)]
pub use define_divisor;

#[cfg(test)]
mod tests {
    #![allow(unused)]

    #[test]
    fn define_divisor() {
        // individual separate
        define_divisor![pub struct DivI8: (i8)];
        define_divisor![impl DivI8: (i8)];
        // individual combined
        define_divisor![pub struct DivU8: (u8) impl];

        // generic separate
        define_divisor![pub struct DivA:<>];
        define_divisor![impl DivA:<> (i8, u32, u128, usize, isize)];
        // generic combined
        define_divisor![pub struct DivB:<> impl (i8, u32, u128, usize, isize)];
    }
}