| 1 |
// Adapted from https://github.com/Alexhuszagh/rust-lexical. |
| 2 |
|
| 3 |
//! Algorithms to efficiently convert strings to floats. |
| 4 |
|
| 5 |
use super::bhcomp::*; |
| 6 |
use super::cached::*; |
| 7 |
use super::errors::*; |
| 8 |
use super::float::ExtendedFloat; |
| 9 |
use super::num::*; |
| 10 |
use super::small_powers::*; |
| 11 |
|
| 12 |
// FAST |
| 13 |
// ---- |
| 14 |
|
| 15 |
/// Convert mantissa to exact value for a non-base2 power. |
| 16 |
/// |
| 17 |
/// Returns the resulting float and if the value can be represented exactly. |
| 18 |
pub(crate) fn fast_path<F>(mantissa: u64, exponent: i32) -> Option<F> |
| 19 |
where |
| 20 |
F: Float, |
| 21 |
{ |
| 22 |
// `mantissa >> (F::MANTISSA_SIZE+1) != 0` effectively checks if the |
| 23 |
// value has a no bits above the hidden bit, which is what we want. |
| 24 |
let (min_exp, max_exp) = F::exponent_limit(); |
| 25 |
let shift_exp = F::mantissa_limit(); |
| 26 |
let mantissa_size = F::MANTISSA_SIZE + 1; |
| 27 |
if mantissa == 0 { |
| 28 |
Some(F::ZERO) |
| 29 |
} else if mantissa >> mantissa_size != 0 { |
| 30 |
// Would require truncation of the mantissa. |
| 31 |
None |
| 32 |
} else if exponent == 0 { |
| 33 |
// 0 exponent, same as value, exact representation. |
| 34 |
let float = F::as_cast(mantissa); |
| 35 |
Some(float) |
| 36 |
} else if exponent >= min_exp && exponent <= max_exp { |
| 37 |
// Value can be exactly represented, return the value. |
| 38 |
// Do not use powi, since powi can incrementally introduce |
| 39 |
// error. |
| 40 |
let float = F::as_cast(mantissa); |
| 41 |
Some(float.pow10(exponent)) |
| 42 |
} else if exponent >= 0 && exponent <= max_exp + shift_exp { |
| 43 |
// Check to see if we have a disguised fast-path, where the |
| 44 |
// number of digits in the mantissa is very small, but and |
| 45 |
// so digits can be shifted from the exponent to the mantissa. |
| 46 |
// https://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/ |
| 47 |
let small_powers = POW10_64; |
| 48 |
let shift = exponent - max_exp; |
| 49 |
let power = small_powers[shift as usize]; |
| 50 |
|
| 51 |
// Compute the product of the power, if it overflows, |
| 52 |
// prematurely return early, otherwise, if we didn't overshoot, |
| 53 |
// we can get an exact value. |
| 54 |
let value = match mantissa.checked_mul(power) { |
| 55 |
None => return None, |
| 56 |
Some(value) => value, |
| 57 |
}; |
| 58 |
if value >> mantissa_size != 0 { |
| 59 |
None |
| 60 |
} else { |
| 61 |
// Use powi, since it's correct, and faster on |
| 62 |
// the fast-path. |
| 63 |
let float = F::as_cast(value); |
| 64 |
Some(float.pow10(max_exp)) |
| 65 |
} |
| 66 |
} else { |
| 67 |
// Cannot be exactly represented, exponent too small or too big, |
| 68 |
// would require truncation. |
| 69 |
None |
| 70 |
} |
| 71 |
} |
| 72 |
|
| 73 |
// MODERATE |
| 74 |
// -------- |
| 75 |
|
| 76 |
/// Multiply the floating-point by the exponent. |
| 77 |
/// |
| 78 |
/// Multiply by pre-calculated powers of the base, modify the extended- |
| 79 |
/// float, and return if new value and if the value can be represented |
| 80 |
/// accurately. |
| 81 |
fn multiply_exponent_extended<F>(fp: &mut ExtendedFloat, exponent: i32, truncated: bool) -> bool |
| 82 |
where |
| 83 |
F: Float, |
| 84 |
{ |
| 85 |
let powers = ExtendedFloat::get_powers(); |
| 86 |
let exponent = exponent.saturating_add(powers.bias); |
| 87 |
let small_index = exponent % powers.step; |
| 88 |
let large_index = exponent / powers.step; |
| 89 |
if exponent < 0 { |
| 90 |
// Guaranteed underflow (assign 0). |
| 91 |
fp.mant = 0; |
| 92 |
true |
| 93 |
} else if large_index as usize >= powers.large.len() { |
| 94 |
// Overflow (assign infinity) |
| 95 |
fp.mant = 1 << 63; |
| 96 |
fp.exp = 0x7FF; |
| 97 |
true |
| 98 |
} else { |
| 99 |
// Within the valid exponent range, multiply by the large and small |
| 100 |
// exponents and return the resulting value. |
| 101 |
|
| 102 |
// Track errors to as a factor of unit in last-precision. |
| 103 |
let mut errors: u32 = 0; |
| 104 |
if truncated { |
| 105 |
errors += u64::error_halfscale(); |
| 106 |
} |
| 107 |
|
| 108 |
// Multiply by the small power. |
| 109 |
// Check if we can directly multiply by an integer, if not, |
| 110 |
// use extended-precision multiplication. |
| 111 |
match fp |
| 112 |
.mant |
| 113 |
.overflowing_mul(powers.get_small_int(small_index as usize)) |
| 114 |
{ |
| 115 |
// Overflow, multiplication unsuccessful, go slow path. |
| 116 |
(_, true) => { |
| 117 |
fp.normalize(); |
| 118 |
fp.imul(&powers.get_small(small_index as usize)); |
| 119 |
errors += u64::error_halfscale(); |
| 120 |
} |
| 121 |
// No overflow, multiplication successful. |
| 122 |
(mant, false) => { |
| 123 |
fp.mant = mant; |
| 124 |
fp.normalize(); |
| 125 |
} |
| 126 |
} |
| 127 |
|
| 128 |
// Multiply by the large power |
| 129 |
fp.imul(&powers.get_large(large_index as usize)); |
| 130 |
if errors > 0 { |
| 131 |
errors += 1; |
| 132 |
} |
| 133 |
errors += u64::error_halfscale(); |
| 134 |
|
| 135 |
// Normalize the floating point (and the errors). |
| 136 |
let shift = fp.normalize(); |
| 137 |
errors <<= shift; |
| 138 |
|
| 139 |
u64::error_is_accurate::<F>(errors, fp) |
| 140 |
} |
| 141 |
} |
| 142 |
|
| 143 |
/// Create a precise native float using an intermediate extended-precision float. |
| 144 |
/// |
| 145 |
/// Return the float approximation and if the value can be accurately |
| 146 |
/// represented with mantissa bits of precision. |
| 147 |
#[inline] |
| 148 |
pub(crate) fn moderate_path<F>( |
| 149 |
mantissa: u64, |
| 150 |
exponent: i32, |
| 151 |
truncated: bool, |
| 152 |
) -> (ExtendedFloat, bool) |
| 153 |
where |
| 154 |
F: Float, |
| 155 |
{ |
| 156 |
let mut fp = ExtendedFloat { |
| 157 |
mant: mantissa, |
| 158 |
exp: 0, |
| 159 |
}; |
| 160 |
let valid = multiply_exponent_extended::<F>(&mut fp, exponent, truncated); |
| 161 |
(fp, valid) |
| 162 |
} |
| 163 |
|
| 164 |
// FALLBACK |
| 165 |
// -------- |
| 166 |
|
| 167 |
/// Fallback path when the fast path does not work. |
| 168 |
/// |
| 169 |
/// Uses the moderate path, if applicable, otherwise, uses the slow path |
| 170 |
/// as required. |
| 171 |
pub(crate) fn fallback_path<F>( |
| 172 |
integer: &[u8], |
| 173 |
fraction: &[u8], |
| 174 |
mantissa: u64, |
| 175 |
exponent: i32, |
| 176 |
mantissa_exponent: i32, |
| 177 |
truncated: bool, |
| 178 |
) -> F |
| 179 |
where |
| 180 |
F: Float, |
| 181 |
{ |
| 182 |
// Moderate path (use an extended 80-bit representation). |
| 183 |
let (fp, valid) = moderate_path::<F>(mantissa, mantissa_exponent, truncated); |
| 184 |
if valid { |
| 185 |
return fp.into_float::<F>(); |
| 186 |
} |
| 187 |
|
| 188 |
// Slow path, fast path didn't work. |
| 189 |
let b = fp.into_downward_float::<F>(); |
| 190 |
if b.is_special() { |
| 191 |
// We have a non-finite number, we get to leave early. |
| 192 |
b |
| 193 |
} else { |
| 194 |
bhcomp(b, integer, fraction, exponent) |
| 195 |
} |
| 196 |
} |