| 1 |
//! Parse byte iterators to float. |
| 2 |
|
| 3 |
#![doc(hidden)] |
| 4 |
|
| 5 |
#[cfg(feature = "compact")] |
| 6 |
use crate::bellerophon::bellerophon; |
| 7 |
use crate::extended_float::{extended_to_float, ExtendedFloat}; |
| 8 |
#[cfg(not(feature = "compact"))] |
| 9 |
use crate::lemire::lemire; |
| 10 |
use crate::num::Float; |
| 11 |
use crate::number::Number; |
| 12 |
use crate::slow::slow; |
| 13 |
|
| 14 |
/// Try to parse the significant digits quickly. |
| 15 |
/// |
| 16 |
/// This attempts a very quick parse, to deal with common cases. |
| 17 |
/// |
| 18 |
/// * `integer` - Slice containing the integer digits. |
| 19 |
/// * `fraction` - Slice containing the fraction digits. |
| 20 |
#[inline] |
| 21 |
fn parse_number_fast<'a, Iter1, Iter2>( |
| 22 |
integer: Iter1, |
| 23 |
fraction: Iter2, |
| 24 |
exponent: i32, |
| 25 |
) -> Option<Number> |
| 26 |
where |
| 27 |
Iter1: Iterator<Item = &'a u8>, |
| 28 |
Iter2: Iterator<Item = &'a u8>, |
| 29 |
{ |
| 30 |
let mut num = Number::default(); |
| 31 |
let mut integer_count: usize = 0; |
| 32 |
let mut fraction_count: usize = 0; |
| 33 |
for &c in integer { |
| 34 |
integer_count += 1; |
| 35 |
let digit = c - b'0'; |
| 36 |
num.mantissa = num.mantissa.wrapping_mul(10).wrapping_add(digit as u64); |
| 37 |
} |
| 38 |
for &c in fraction { |
| 39 |
fraction_count += 1; |
| 40 |
let digit = c - b'0'; |
| 41 |
num.mantissa = num.mantissa.wrapping_mul(10).wrapping_add(digit as u64); |
| 42 |
} |
| 43 |
|
| 44 |
if integer_count + fraction_count <= 19 { |
| 45 |
// Can't overflow, since must be <= 19. |
| 46 |
num.exponent = exponent.saturating_sub(fraction_count as i32); |
| 47 |
Some(num) |
| 48 |
} else { |
| 49 |
None |
| 50 |
} |
| 51 |
} |
| 52 |
|
| 53 |
/// Parse the significant digits of the float and adjust the exponent. |
| 54 |
/// |
| 55 |
/// * `integer` - Slice containing the integer digits. |
| 56 |
/// * `fraction` - Slice containing the fraction digits. |
| 57 |
#[inline] |
| 58 |
fn parse_number<'a, Iter1, Iter2>(mut integer: Iter1, mut fraction: Iter2, exponent: i32) -> Number |
| 59 |
where |
| 60 |
Iter1: Iterator<Item = &'a u8> + Clone, |
| 61 |
Iter2: Iterator<Item = &'a u8> + Clone, |
| 62 |
{ |
| 63 |
// NOTE: for performance, we do this in 2 passes: |
| 64 |
if let Some(num) = parse_number_fast(integer.clone(), fraction.clone(), exponent) { |
| 65 |
return num; |
| 66 |
} |
| 67 |
|
| 68 |
// Can only add 19 digits. |
| 69 |
let mut num = Number::default(); |
| 70 |
let mut count = 0; |
| 71 |
while let Some(&c) = integer.next() { |
| 72 |
count += 1; |
| 73 |
if count == 20 { |
| 74 |
// Only the integer digits affect the exponent. |
| 75 |
num.many_digits = true; |
| 76 |
num.exponent = exponent.saturating_add(into_i32(1 + integer.count())); |
| 77 |
return num; |
| 78 |
} else { |
| 79 |
let digit = c - b'0'; |
| 80 |
num.mantissa = num.mantissa * 10 + digit as u64; |
| 81 |
} |
| 82 |
} |
| 83 |
|
| 84 |
// Skip leading fraction zeros. |
| 85 |
// This is required otherwise we might have a 0 mantissa and many digits. |
| 86 |
let mut fraction_count: usize = 0; |
| 87 |
if count == 0 { |
| 88 |
for &c in &mut fraction { |
| 89 |
fraction_count += 1; |
| 90 |
if c != b'0' { |
| 91 |
count += 1; |
| 92 |
let digit = c - b'0'; |
| 93 |
num.mantissa = num.mantissa * 10 + digit as u64; |
| 94 |
break; |
| 95 |
} |
| 96 |
} |
| 97 |
} |
| 98 |
for c in fraction { |
| 99 |
fraction_count += 1; |
| 100 |
count += 1; |
| 101 |
if count == 20 { |
| 102 |
num.many_digits = true; |
| 103 |
// This can't wrap, since we have at most 20 digits. |
| 104 |
// We've adjusted the exponent too high by `fraction_count - 1`. |
| 105 |
// Note: -1 is due to incrementing this loop iteration, which we |
| 106 |
// didn't use. |
| 107 |
num.exponent = exponent.saturating_sub(fraction_count as i32 - 1); |
| 108 |
return num; |
| 109 |
} else { |
| 110 |
let digit = c - b'0'; |
| 111 |
num.mantissa = num.mantissa * 10 + digit as u64; |
| 112 |
} |
| 113 |
} |
| 114 |
|
| 115 |
// No truncated digits: easy. |
| 116 |
// Cannot overflow: <= 20 digits. |
| 117 |
num.exponent = exponent.saturating_sub(fraction_count as i32); |
| 118 |
num |
| 119 |
} |
| 120 |
|
| 121 |
/// Parse float from extracted float components. |
| 122 |
/// |
| 123 |
/// * `integer` - Cloneable, forward iterator over integer digits. |
| 124 |
/// * `fraction` - Cloneable, forward iterator over integer digits. |
| 125 |
/// * `exponent` - Parsed, 32-bit exponent. |
| 126 |
/// |
| 127 |
/// # Preconditions |
| 128 |
/// 1. The integer should not have leading zeros. |
| 129 |
/// 2. The fraction should not have trailing zeros. |
| 130 |
/// 3. All bytes in `integer` and `fraction` should be valid digits, |
| 131 |
/// in the range [`b'0', b'9']. |
| 132 |
/// |
| 133 |
/// # Panics |
| 134 |
/// |
| 135 |
/// Although passing garbage input will not cause memory safety issues, |
| 136 |
/// it is very likely to cause a panic with a large number of digits, or |
| 137 |
/// in debug mode. The big-integer arithmetic without the `alloc` feature |
| 138 |
/// assumes a maximum, fixed-width input, which assumes at maximum a |
| 139 |
/// value of `10^(769 + 342)`, or ~4000 bits of storage. Passing in |
| 140 |
/// nonsensical digits may require up to ~6000 bits of storage, which will |
| 141 |
/// panic when attempting to add it to the big integer. It is therefore |
| 142 |
/// up to the caller to validate this input. |
| 143 |
/// |
| 144 |
/// We cannot efficiently remove trailing zeros while only accepting a |
| 145 |
/// forward iterator. |
| 146 |
pub fn parse_float<'a, F, Iter1, Iter2>(integer: Iter1, fraction: Iter2, exponent: i32) -> F |
| 147 |
where |
| 148 |
F: Float, |
| 149 |
Iter1: Iterator<Item = &'a u8> + Clone, |
| 150 |
Iter2: Iterator<Item = &'a u8> + Clone, |
| 151 |
{ |
| 152 |
// Parse the mantissa and attempt the fast and moderate-path algorithms. |
| 153 |
let num = parse_number(integer.clone(), fraction.clone(), exponent); |
| 154 |
// Try the fast-path algorithm. |
| 155 |
if let Some(value) = num.try_fast_path() { |
| 156 |
return value; |
| 157 |
} |
| 158 |
|
| 159 |
// Now try the moderate path algorithm. |
| 160 |
let mut fp = moderate_path::<F>(&num); |
| 161 |
if fp.exp < 0 { |
| 162 |
// Undo the invalid extended float biasing. |
| 163 |
fp.exp -= F::INVALID_FP; |
| 164 |
fp = slow::<F, _, _>(num, fp, integer, fraction); |
| 165 |
} |
| 166 |
|
| 167 |
// Unable to correctly round the float using the fast or moderate algorithms. |
| 168 |
// Fallback to a slower, but always correct algorithm. If we have |
| 169 |
// lossy, we can't be here. |
| 170 |
extended_to_float::<F>(fp) |
| 171 |
} |
| 172 |
|
| 173 |
/// Wrapper for different moderate-path algorithms. |
| 174 |
/// A return exponent of `-1` indicates an invalid value. |
| 175 |
#[inline] |
| 176 |
pub fn moderate_path<F: Float>(num: &Number) -> ExtendedFloat { |
| 177 |
#[cfg(not(feature = "compact"))] |
| 178 |
return lemire::<F>(num); |
| 179 |
|
| 180 |
#[cfg(feature = "compact")] |
| 181 |
return bellerophon::<F>(num); |
| 182 |
} |
| 183 |
|
| 184 |
/// Convert usize into i32 without overflow. |
| 185 |
/// |
| 186 |
/// This is needed to ensure when adjusting the exponent relative to |
| 187 |
/// the mantissa we do not overflow for comically-long exponents. |
| 188 |
#[inline] |
| 189 |
fn into_i32(value: usize) -> i32 { |
| 190 |
if value > i32::max_value() as usize { |
| 191 |
i32::max_value() |
| 192 |
} else { |
| 193 |
value as i32 |
| 194 |
} |
| 195 |
} |
| 196 |
|
| 197 |
// Add digit to mantissa. |
| 198 |
#[inline] |
| 199 |
pub fn add_digit(value: u64, digit: u8) -> Option<u64> { |
| 200 |
value.checked_mul(10)?.checked_add(digit as u64) |
| 201 |
} |