Skip to main content

DivisorU32

Enum DivisorU32 

Source
#[non_exhaustive]
pub enum DivisorU32 { PowerOfTwo(PowerOfTwoDivisorU32), Up(UpDivisorU32), Down(DownDivisorU32), AddIndicator(AddIndicatorDivisorU32), }
Expand description

A u32 divisor, precomputed once to divide many values by it

Division by a divisor that is only known at run time needs a divide instruction. Self::new precomputes a shift and a mask when the magnitude of the divisor is a power of two, and otherwise a multiplier, so that each division is a high multiply, shifts and additions. Self::new picks the variant from the divisor and the target.

To divide many values, match on the variant once, before the loop, and call the variant’s methods in the loop. They don’t branch on the divisor, so the loop doesn’t depend on the compiler moving a branch out of it. Move the variant into the loop’s closure, so that the compiler doesn’t reload its fields through a reference for each value. Self::wrapping_div_rem matches on each call, so a match can fall back to it for the variants it doesn’t specialize, including variants added later.

§Example

let values: Vec<u32> = vec![100, 7, 64];
let quotients: Vec<_> = match DivisorU32::new(7).unwrap() {
    DivisorU32::PowerOfTwo(d) => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),
    DivisorU32::AddIndicator(d) => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),
    d => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),
};
assert_eq!(quotients, [14, 1, 9]);

Variants (Non-exhaustive)§

This enum is marked as non-exhaustive
Non-exhaustive enums could have additional variants added in future. Therefore, when matching against variants of non-exhaustive enums, an extra wildcard arm must be added to account for any future variants.
§

PowerOfTwo(PowerOfTwoDivisorU32)

A divisor that is a power of two

§

Up(UpDivisorU32)

A divisor whose rounded-up multiplier is exact in N bits

§

Down(DownDivisorU32)

A divisor whose rounded-up multiplier isn’t exact in N bits, with the rounded-down multiplier, on targets where u32 saturating adds are cheap

§

AddIndicator(AddIndicatorDivisorU32)

Any other divisor

Implementations§

Source§

impl DivisorU32

Source

pub const fn wrapping_div_rem(self, n: u32) -> (u32, u32)

Returns (n.wrapping_div(divisor), n.wrapping_rem(divisor))

§Example
let divisor = DivisorU32::new(7).unwrap();
assert_eq!(divisor.wrapping_div_rem(100), (14, 2));
Source§

impl DivisorU32

Source

pub const fn new(divisor: u32) -> Option<Self>

Returns a divisor for divisor, or None if divisor is zero

With p = floor(log2(divisor)), it picks Self::Up when the rounded-up multiplier floor(2^(N+p) / divisor) + 1 satisfies theorem 4.2 of Granlund and Montgomery, “Division by Invariant Integers using Multiplication” (1994). Checking one p is enough, because a multiplier that is exact for a smaller p is also exact for this one, see ridiculous_fish, “Labor of Division (Episode I)”. Otherwise it picks Self::Down (a DownDivisorU32) on aarch64 and on x86 with SSE4.1, where a saturating increment takes one or two vector instructions. It picks Self::AddIndicator for any divisor the other variants don’t cover.

§Example
const SEVEN: DivisorU32 = DivisorU32::new(7).unwrap();
assert!(DivisorU32::new(0).is_none());

Trait Implementations§

Source§

impl Clone for DivisorU32

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Copy for DivisorU32

Source§

impl Debug for DivisorU32

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Allocation for T
where T: RefUnwindSafe + Send + Sync,

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
§

impl<ST, DT> CastableFrom<ST, Initialized, Initialized> for DT
where ST: ?Sized, DT: ?Sized,

§

impl<ST, DT> CastableFrom<ST, Uninit, Uninit> for DT
where ST: ?Sized, DT: ?Sized,

Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

§

impl<T> Read<Exclusive, BecauseExclusive> for T
where T: ?Sized,

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.