#![no_std]
use core::ops::{Div, Rem};
mod long_division;
#[derive(Clone, Copy, Debug)]
pub struct StrengthReducedU8 {
multiplier: u16,
divisor: u8,
}
impl StrengthReducedU8 {
#[inline]
pub fn new(divisor: u8) -> Self {
assert!(divisor > 0);
if divisor.is_power_of_two() {
Self{ multiplier: 0, divisor }
} else {
let divided = core::u16::MAX / (divisor as u16);
Self{ multiplier: divided + 1, divisor }
}
}
#[inline]
pub fn div_rem(numerator: u8, denom: Self) -> (u8, u8) {
let quotient = numerator / denom;
let remainder = numerator % denom;
(quotient, remainder)
}
#[inline]
pub fn get(&self) -> u8 {
self.divisor
}
}
impl Div<StrengthReducedU8> for u8 {
type Output = u8;
#[inline]
fn div(self, rhs: StrengthReducedU8) -> Self::Output {
if rhs.multiplier == 0 {
(self as u16 >> rhs.divisor.trailing_zeros()) as u8
} else {
let numerator = self as u16;
let multiplied_hi = numerator * (rhs.multiplier >> 8);
let multiplied_lo = (numerator * rhs.multiplier as u8 as u16) >> 8;
((multiplied_hi + multiplied_lo) >> 8) as u8
}
}
}
impl Rem<StrengthReducedU8> for u8 {
type Output = u8;
#[inline]
fn rem(self, rhs: StrengthReducedU8) -> Self::Output {
if rhs.multiplier == 0 {
self & (rhs.divisor - 1)
} else {
let product = rhs.multiplier.wrapping_mul(self as u16) as u32;
let divisor = rhs.divisor as u32;
let shifted = (product * divisor) >> 16;
shifted as u8
}
}
}
macro_rules! strength_reduced_u16 {
($struct_name:ident, $primitive_type:ident) => (
#[derive(Clone, Copy, Debug)]
pub struct $struct_name {
multiplier: u32,
divisor: $primitive_type,
}
impl $struct_name {
#[inline]
pub fn new(divisor: $primitive_type) -> Self {
assert!(divisor > 0);
if divisor.is_power_of_two() {
Self{ multiplier: 0, divisor }
} else {
let divided = core::u32::MAX / (divisor as u32);
Self{ multiplier: divided + 1, divisor }
}
}
#[inline]
pub fn div_rem(numerator: $primitive_type, denom: Self) -> ($primitive_type, $primitive_type) {
let quotient = numerator / denom;
let remainder = numerator - quotient * denom.divisor;
(quotient, remainder)
}
#[inline]
pub fn get(&self) -> $primitive_type {
self.divisor
}
}
impl Div<$struct_name> for $primitive_type {
type Output = $primitive_type;
#[inline]
fn div(self, rhs: $struct_name) -> Self::Output {
if rhs.multiplier == 0 {
self >> rhs.divisor.trailing_zeros()
} else {
let numerator = self as u32;
let multiplied_hi = numerator * (rhs.multiplier >> 16);
let multiplied_lo = (numerator * rhs.multiplier as u16 as u32) >> 16;
((multiplied_hi + multiplied_lo) >> 16) as $primitive_type
}
}
}
impl Rem<$struct_name> for $primitive_type {
type Output = $primitive_type;
#[inline]
fn rem(self, rhs: $struct_name) -> Self::Output {
if rhs.multiplier == 0 {
self & (rhs.divisor - 1)
} else {
let quotient = self / rhs;
self - quotient * rhs.divisor
}
}
}
)
}
macro_rules! strength_reduced_u32 {
($struct_name:ident, $primitive_type:ident) => (
#[derive(Clone, Copy, Debug)]
pub struct $struct_name {
multiplier: u64,
divisor: $primitive_type,
}
impl $struct_name {
#[inline]
pub fn new(divisor: $primitive_type) -> Self {
assert!(divisor > 0);
if divisor.is_power_of_two() {
Self{ multiplier: 0, divisor }
} else {
let divided = core::u64::MAX / (divisor as u64);
Self{ multiplier: divided + 1, divisor }
}
}
#[inline]
pub fn div_rem(numerator: $primitive_type, denom: Self) -> ($primitive_type, $primitive_type) {
if denom.multiplier == 0 {
(numerator >> denom.divisor.trailing_zeros(), numerator & (denom.divisor - 1))
}
else {
let numerator64 = numerator as u64;
let multiplied_hi = numerator64 * (denom.multiplier >> 32);
let multiplied_lo = numerator64 * (denom.multiplier as u32 as u64) >> 32;
let quotient = ((multiplied_hi + multiplied_lo) >> 32) as $primitive_type;
let remainder = numerator - quotient * denom.divisor;
(quotient, remainder)
}
}
#[inline]
pub fn get(&self) -> $primitive_type {
self.divisor
}
}
impl Div<$struct_name> for $primitive_type {
type Output = $primitive_type;
#[inline]
fn div(self, rhs: $struct_name) -> Self::Output {
if rhs.multiplier == 0 {
self >> rhs.divisor.trailing_zeros()
} else {
let numerator = self as u64;
let multiplied_hi = numerator * (rhs.multiplier >> 32);
let multiplied_lo = numerator * (rhs.multiplier as u32 as u64) >> 32;
((multiplied_hi + multiplied_lo) >> 32) as $primitive_type
}
}
}
impl Rem<$struct_name> for $primitive_type {
type Output = $primitive_type;
#[inline]
fn rem(self, rhs: $struct_name) -> Self::Output {
if rhs.multiplier == 0 {
self & (rhs.divisor - 1)
} else {
let product = rhs.multiplier.wrapping_mul(self as u64) as u128;
let divisor = rhs.divisor as u128;
let shifted = (product * divisor) >> 64;
shifted as $primitive_type
}
}
}
)
}
macro_rules! strength_reduced_u64 {
($struct_name:ident, $primitive_type:ident) => (
#[derive(Clone, Copy, Debug)]
pub struct $struct_name {
multiplier: u128,
divisor: $primitive_type,
}
impl $struct_name {
#[inline]
pub fn new(divisor: $primitive_type) -> Self {
assert!(divisor > 0);
if divisor.is_power_of_two() {
Self{ multiplier: 0, divisor }
} else {
let divided = long_division::divide_128_max(divisor as u64);
Self{ multiplier: divided + 1, divisor }
}
}
#[inline]
pub fn div_rem(numerator: $primitive_type, denom: Self) -> ($primitive_type, $primitive_type) {
if denom.multiplier == 0 {
(numerator >> denom.divisor.trailing_zeros(), numerator & (denom.divisor - 1))
}
else {
let numerator128 = numerator as u128;
let multiplied_hi = numerator128 * (denom.multiplier >> 64);
let multiplied_lo = numerator128 * (denom.multiplier as u64 as u128) >> 64;
let quotient = ((multiplied_hi + multiplied_lo) >> 64) as $primitive_type;
let remainder = numerator - quotient * denom.divisor;
(quotient, remainder)
}
}
#[inline]
pub fn get(&self) -> $primitive_type {
self.divisor
}
}
impl Div<$struct_name> for $primitive_type {
type Output = $primitive_type;
#[inline]
fn div(self, rhs: $struct_name) -> Self::Output {
if rhs.multiplier == 0 {
self >> rhs.divisor.trailing_zeros()
} else {
let numerator = self as u128;
let multiplied_hi = numerator * (rhs.multiplier >> 64);
let multiplied_lo = numerator * (rhs.multiplier as u64 as u128) >> 64;
((multiplied_hi + multiplied_lo) >> 64) as $primitive_type
}
}
}
impl Rem<$struct_name> for $primitive_type {
type Output = $primitive_type;
#[inline]
fn rem(self, rhs: $struct_name) -> Self::Output {
if rhs.multiplier == 0 {
self & (rhs.divisor - 1)
} else {
let quotient = self / rhs;
self - quotient * rhs.divisor
}
}
}
)
}
strength_reduced_u16!(StrengthReducedU16, u16);
strength_reduced_u32!(StrengthReducedU32, u32);
strength_reduced_u64!(StrengthReducedU64, u64);
#[cfg(target_pointer_width = "16")]
strength_reduced_u16!(StrengthReducedUsize, usize);
#[cfg(target_pointer_width = "32")]
strength_reduced_u32!(StrengthReducedUsize, usize);
#[cfg(target_pointer_width = "64")]
strength_reduced_u64!(StrengthReducedUsize, usize);
#[cfg(test)]
mod unit_tests {
use super::*;
macro_rules! reduction_test {
($test_name:ident, $struct_name:ident, $primitive_type:ident) => (
#[test]
fn $test_name() {
let max = core::$primitive_type::MAX;
let divisors = [7,8,9,10,11,12,13,14,15,16,17,18,19,20,max-1,max];
let numerators = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,max-1,max];
for &divisor in &divisors {
let reduced_divisor = $struct_name::new(divisor);
for &numerator in &numerators {
let expected_div = numerator / divisor;
let expected_rem = numerator % divisor;
let reduced_div = numerator / reduced_divisor;
assert_eq!(expected_div, reduced_div, "Divide failed with numerator: {}, divisor: {}", numerator, divisor);
let reduced_rem = numerator % reduced_divisor;
let (reduced_combined_div, reduced_combined_rem) = $struct_name::div_rem(numerator, reduced_divisor);
assert_eq!(expected_rem, reduced_rem, "Modulo failed with numerator: {}, divisor: {}", numerator, divisor);
assert_eq!(expected_div, reduced_combined_div, "div_rem divide failed with numerator: {}, divisor: {}", numerator, divisor);
assert_eq!(expected_rem, reduced_combined_rem, "div_rem modulo failed with numerator: {}, divisor: {}", numerator, divisor);
}
}
}
)
}
reduction_test!(test_strength_reduced_u8, StrengthReducedU8, u8);
reduction_test!(test_strength_reduced_u16, StrengthReducedU16, u16);
reduction_test!(test_strength_reduced_u32, StrengthReducedU32, u32);
reduction_test!(test_strength_reduced_u64, StrengthReducedU64, u64);
reduction_test!(test_strength_reduced_usize, StrengthReducedUsize, usize);
}