Revision control
Copy as Markdown
Other Tools
use crate::constants::{MAX_I32_SCALE, MAX_PRECISION_I32, POWERS_10};
use crate::Decimal;
#[derive(Debug)]
pub struct Buf12 {
pub data: [u32; 3],
}
impl Buf12 {
pub(super) const fn from_dec64(value: &Dec64) -> Self {
Buf12 {
data: [value.low64 as u32, (value.low64 >> 32) as u32, value.hi],
}
}
pub(super) const fn from_decimal(value: &Decimal) -> Self {
Buf12 {
data: value.mantissa_array3(),
}
}
#[inline(always)]
pub const fn lo(&self) -> u32 {
self.data[0]
}
#[inline(always)]
pub const fn mid(&self) -> u32 {
self.data[1]
}
#[inline(always)]
pub const fn hi(&self) -> u32 {
self.data[2]
}
#[inline(always)]
pub fn set_lo(&mut self, value: u32) {
self.data[0] = value;
}
#[inline(always)]
pub fn set_mid(&mut self, value: u32) {
self.data[1] = value;
}
#[inline(always)]
pub fn set_hi(&mut self, value: u32) {
self.data[2] = value;
}
#[inline(always)]
pub const fn low64(&self) -> u64 {
((self.data[1] as u64) << 32) | (self.data[0] as u64)
}
#[inline(always)]
pub fn set_low64(&mut self, value: u64) {
self.data[1] = (value >> 32) as u32;
self.data[0] = value as u32;
}
#[inline(always)]
pub const fn high64(&self) -> u64 {
((self.data[2] as u64) << 32) | (self.data[1] as u64)
}
#[inline(always)]
pub fn set_high64(&mut self, value: u64) {
self.data[2] = (value >> 32) as u32;
self.data[1] = value as u32;
}
// Determine the maximum value of x that ensures that the quotient when scaled up by 10^x
// still fits in 96 bits. Ultimately, we want to make scale positive - if we can't then
// we're going to overflow. Because x is ultimately used to lookup inside the POWERS array, it
// must be a valid value 0 <= x <= 9
pub fn find_scale(&self, scale: i32) -> Option<usize> {
const OVERFLOW_MAX_9_HI: u32 = 4;
const OVERFLOW_MAX_8_HI: u32 = 42;
const OVERFLOW_MAX_7_HI: u32 = 429;
const OVERFLOW_MAX_6_HI: u32 = 4294;
const OVERFLOW_MAX_5_HI: u32 = 42949;
const OVERFLOW_MAX_4_HI: u32 = 429496;
const OVERFLOW_MAX_3_HI: u32 = 4294967;
const OVERFLOW_MAX_2_HI: u32 = 42949672;
const OVERFLOW_MAX_1_HI: u32 = 429496729;
const OVERFLOW_MAX_9_LOW64: u64 = 5441186219426131129;
let hi = self.data[2];
let low64 = self.low64();
let mut x = 0usize;
// Quick check to stop us from trying to scale any more.
//
if hi > OVERFLOW_MAX_1_HI {
// If it's less than 0, which it probably is - overflow. We can't do anything.
if scale < 0 {
return None;
}
return Some(x);
}
if scale > MAX_PRECISION_I32 - 9 {
// We can't scale by 10^9 without exceeding the max scale factor.
// Instead, we'll try to scale by the most that we can and see if that works.
// This is safe to do due to the check above. e.g. scale > 19 in the above, so it will
// evaluate to 9 or less below.
x = (MAX_PRECISION_I32 - scale) as usize;
if hi < POWER_OVERFLOW_VALUES[x - 1].data[2] {
if x as i32 + scale < 0 {
// We still overflow
return None;
}
return Some(x);
}
} else if hi < OVERFLOW_MAX_9_HI || hi == OVERFLOW_MAX_9_HI && low64 <= OVERFLOW_MAX_9_LOW64 {
return Some(9);
}
// Do a binary search to find a power to scale by that is less than 9
x = if hi > OVERFLOW_MAX_5_HI {
if hi > OVERFLOW_MAX_3_HI {
if hi > OVERFLOW_MAX_2_HI {
1
} else {
2
}
} else if hi > OVERFLOW_MAX_4_HI {
3
} else {
4
}
} else if hi > OVERFLOW_MAX_7_HI {
if hi > OVERFLOW_MAX_6_HI {
5
} else {
6
}
} else if hi > OVERFLOW_MAX_8_HI {
7
} else {
8
};
// Double check what we've found won't overflow. Otherwise, we go one below.
if hi == POWER_OVERFLOW_VALUES[x - 1].data[2] && low64 > POWER_OVERFLOW_VALUES[x - 1].low64() {
x -= 1;
}
// Confirm we've actually resolved things
if x as i32 + scale < 0 {
None
} else {
Some(x)
}
}
}
// This is a table of the largest values that will not overflow when multiplied
// by a given power as represented by the index.
static POWER_OVERFLOW_VALUES: [Buf12; 8] = [
Buf12 {
data: [2576980377, 2576980377, 429496729],
},
Buf12 {
data: [687194767, 4123168604, 42949672],
},
Buf12 {
data: [2645699854, 1271310319, 4294967],
},
Buf12 {
data: [694066715, 3133608139, 429496],
},
Buf12 {
data: [2216890319, 2890341191, 42949],
},
Buf12 {
data: [2369172679, 4154504685, 4294],
},
Buf12 {
data: [4102387834, 2133437386, 429],
},
Buf12 {
data: [410238783, 4078814305, 42],
},
];
pub(super) struct Dec64 {
pub negative: bool,
pub scale: u32,
pub hi: u32,
pub low64: u64,
}
impl Dec64 {
pub(super) const fn new(d: &Decimal) -> Dec64 {
let m = d.mantissa_array3();
if m[1] == 0 {
Dec64 {
negative: d.is_sign_negative(),
scale: d.scale(),
hi: m[2],
low64: m[0] as u64,
}
} else {
Dec64 {
negative: d.is_sign_negative(),
scale: d.scale(),
hi: m[2],
low64: ((m[1] as u64) << 32) | (m[0] as u64),
}
}
}
#[inline(always)]
pub(super) const fn lo(&self) -> u32 {
self.low64 as u32
}
#[inline(always)]
pub(super) const fn mid(&self) -> u32 {
(self.low64 >> 32) as u32
}
#[inline(always)]
pub(super) const fn high64(&self) -> u64 {
(self.low64 >> 32) | ((self.hi as u64) << 32)
}
pub(super) const fn to_decimal(&self) -> Decimal {
Decimal::from_parts(
self.low64 as u32,
(self.low64 >> 32) as u32,
self.hi,
self.negative,
self.scale,
)
}
}
pub struct Buf16 {
pub data: [u32; 4],
}
impl Buf16 {
pub const fn zero() -> Self {
Buf16 { data: [0, 0, 0, 0] }
}
pub const fn low64(&self) -> u64 {
((self.data[1] as u64) << 32) | (self.data[0] as u64)
}
pub fn set_low64(&mut self, value: u64) {
self.data[1] = (value >> 32) as u32;
self.data[0] = value as u32;
}
pub const fn mid64(&self) -> u64 {
((self.data[2] as u64) << 32) | (self.data[1] as u64)
}
pub fn set_mid64(&mut self, value: u64) {
self.data[2] = (value >> 32) as u32;
self.data[1] = value as u32;
}
pub const fn high64(&self) -> u64 {
((self.data[3] as u64) << 32) | (self.data[2] as u64)
}
pub fn set_high64(&mut self, value: u64) {
self.data[3] = (value >> 32) as u32;
self.data[2] = value as u32;
}
}
#[derive(Debug)]
pub struct Buf24 {
pub data: [u32; 6],
}
impl Buf24 {
pub const fn zero() -> Self {
Buf24 {
data: [0, 0, 0, 0, 0, 0],
}
}
pub const fn low64(&self) -> u64 {
((self.data[1] as u64) << 32) | (self.data[0] as u64)
}
pub fn set_low64(&mut self, value: u64) {
self.data[1] = (value >> 32) as u32;
self.data[0] = value as u32;
}
#[allow(dead_code)]
pub const fn mid64(&self) -> u64 {
((self.data[3] as u64) << 32) | (self.data[2] as u64)
}
pub fn set_mid64(&mut self, value: u64) {
self.data[3] = (value >> 32) as u32;
self.data[2] = value as u32;
}
#[allow(dead_code)]
pub const fn high64(&self) -> u64 {
((self.data[5] as u64) << 32) | (self.data[4] as u64)
}
pub fn set_high64(&mut self, value: u64) {
self.data[5] = (value >> 32) as u32;
self.data[4] = value as u32;
}
pub const fn upper_word(&self) -> usize {
if self.data[5] > 0 {
return 5;
}
if self.data[4] > 0 {
return 4;
}
if self.data[3] > 0 {
return 3;
}
if self.data[2] > 0 {
return 2;
}
if self.data[1] > 0 {
return 1;
}
0
}
// Attempt to rescale the number into 96 bits. If successful, the scale is returned wrapped
// in an Option. If it failed due to overflow, we return None.
// * `upper` - Index of last non-zero value in self.
// * `scale` - Current scale factor for this value.
pub fn rescale(&mut self, upper: usize, scale: u32) -> Option<u32> {
let mut scale = scale as i32;
let mut upper = upper;
// Determine a rescale target to start with
let mut rescale_target = 0i32;
if upper > 2 {
rescale_target = upper as i32 * 32 - 64 - 1;
rescale_target -= self.data[upper].leading_zeros() as i32;
rescale_target = ((rescale_target * 77) >> 8) + 1;
if rescale_target > scale {
return None;
}
}
// Make sure we scale enough to bring it into a valid range
if rescale_target < scale - MAX_PRECISION_I32 {
rescale_target = scale - MAX_PRECISION_I32;
}
if rescale_target > 0 {
// We're going to keep reducing by powers of 10. So, start by reducing the scale by
// that amount.
scale -= rescale_target;
let mut sticky = 0;
let mut remainder = 0;
loop {
sticky |= remainder;
let mut power = if rescale_target > 8 {
POWERS_10[9]
} else {
POWERS_10[rescale_target as usize]
};
let high = self.data[upper];
let high_quotient = high / power;
remainder = high - high_quotient * power;
for item in self.data.iter_mut().rev().skip(6 - upper) {
let num = (*item as u64).wrapping_add((remainder as u64) << 32);
*item = (num / power as u64) as u32;
remainder = (num as u32).wrapping_sub(item.wrapping_mul(power));
}
self.data[upper] = high_quotient;
// If the high quotient was zero then decrease the upper bound
if high_quotient == 0 && upper > 0 {
upper -= 1;
}
if rescale_target > MAX_I32_SCALE {
// Scale some more
rescale_target -= MAX_I32_SCALE;
continue;
}
// If we fit into 96 bits then we've scaled enough. Otherwise, scale once more.
if upper > 2 {
if scale == 0 {
return None;
}
// Equivalent to scaling down by 10
rescale_target = 1;
scale -= 1;
continue;
}
// Round the final result.
power >>= 1;
let carried = if power <= remainder {
// If we're less than half then we're fine. Otherwise, we round if odd or if the
// sticky bit is set.
if power < remainder || ((self.data[0] & 1) | sticky) != 0 {
// Round up
self.data[0] = self.data[0].wrapping_add(1);
// Check if we carried
self.data[0] == 0
} else {
false
}
} else {
false
};
// If we carried then propagate through the portions
if carried {
let mut pos = 0;
for (index, value) in self.data.iter_mut().enumerate().skip(1) {
pos = index;
*value = value.wrapping_add(1);
if *value != 0 {
break;
}
}
// If we ended up rounding over the 96 bits then we'll try to rescale down (again)
if pos > 2 {
// Nothing to scale down from will cause overflow
if scale == 0 {
return None;
}
// Loop back around using scale of 10.
// Reset the sticky bit and remainder before looping.
upper = pos;
sticky = 0;
remainder = 0;
rescale_target = 1;
scale -= 1;
continue;
}
}
break;
}
}
Some(scale as u32)
}
}