#[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
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
impl DivisorU32
Source§impl DivisorU32
impl DivisorU32
Sourcepub const fn new(divisor: u32) -> Option<Self>
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());