diff options
| author | Alex Huszagh <ahuszagh@gmail.com> | 2021-07-17 00:30:34 -0500 |
|---|---|---|
| committer | Alex Huszagh <ahuszagh@gmail.com> | 2021-07-17 00:30:34 -0500 |
| commit | 8752b403695a8830913571f0fd5ebfcf1483db37 (patch) | |
| tree | fba1ac7613edb617bee5b257b21bd6d10dad0662 | |
| parent | d2b04f075c0ce010758c4c8674152ff89d1d73f3 (diff) | |
| download | rust-8752b403695a8830913571f0fd5ebfcf1483db37.tar.gz rust-8752b403695a8830913571f0fd5ebfcf1483db37.zip | |
Changed dec2flt to use the Eisel-Lemire algorithm.
Implementation is based off fast-float-rust, with a few notable changes. - Some unsafe methods have been removed. - Safe methods with inherently unsafe functionality have been removed. - All unsafe functionality is documented and provably safe. - Extensive documentation has been added for simpler maintenance. - Inline annotations on internal routines has been removed. - Fixed Python errors in src/etc/test-float-parse/runtests.py. - Updated test-float-parse to be a library, to avoid missing rand dependency. - Added regression tests for #31109 and #31407 in core tests. - Added regression tests for #31109 and #31407 in ui tests. - Use the existing slice primitive to simplify shared dec2flt methods - Remove Miri ignores from dec2flt, due to faster parsing times. - resolves #85198 - resolves #85214 - resolves #85234 - fixes #31407 - fixes #31109 - fixes #53015 - resolves #68396 - closes https://github.com/aldanor/fast-float-rust/issues/15
43 files changed, 2530 insertions, 2823 deletions
diff --git a/compiler/rustc_middle/src/mir/interpret/mod.rs b/compiler/rustc_middle/src/mir/interpret/mod.rs index 14bdb0a5a2d..58902c5e469 100644 --- a/compiler/rustc_middle/src/mir/interpret/mod.rs +++ b/compiler/rustc_middle/src/mir/interpret/mod.rs @@ -172,7 +172,6 @@ pub enum LitToConstError { /// This is used for graceful error handling (`delay_span_bug`) in /// type checking (`Const::from_anon_const`). TypeError, - UnparseableFloat, Reported, } diff --git a/compiler/rustc_mir_build/src/thir/constant.rs b/compiler/rustc_mir_build/src/thir/constant.rs index d62fd161e2f..1592a1e976e 100644 --- a/compiler/rustc_mir_build/src/thir/constant.rs +++ b/compiler/rustc_mir_build/src/thir/constant.rs @@ -46,9 +46,7 @@ crate fn lit_to_const<'tcx>( (ast::LitKind::Int(n, _), ty::Uint(_)) | (ast::LitKind::Int(n, _), ty::Int(_)) => { trunc(if neg { (*n as i128).overflowing_neg().0 as u128 } else { *n })? } - (ast::LitKind::Float(n, _), ty::Float(fty)) => { - parse_float(*n, *fty, neg).map_err(|_| LitToConstError::UnparseableFloat)? - } + (ast::LitKind::Float(n, _), ty::Float(fty)) => parse_float(*n, *fty, neg), (ast::LitKind::Bool(b), ty::Bool) => ConstValue::Scalar(Scalar::from_bool(*b)), (ast::LitKind::Char(c), ty::Char) => ConstValue::Scalar(Scalar::from_char(*c)), (ast::LitKind::Err(_), _) => return Err(LitToConstError::Reported), @@ -57,12 +55,14 @@ crate fn lit_to_const<'tcx>( Ok(ty::Const::from_value(tcx, lit, ty)) } -fn parse_float<'tcx>(num: Symbol, fty: ty::FloatTy, neg: bool) -> Result<ConstValue<'tcx>, ()> { +fn parse_float<'tcx>(num: Symbol, fty: ty::FloatTy, neg: bool) -> ConstValue<'tcx> { let num = num.as_str(); use rustc_apfloat::ieee::{Double, Single}; let scalar = match fty { ty::FloatTy::F32 => { - let rust_f = num.parse::<f32>().map_err(|_| ())?; + let rust_f = num + .parse::<f32>() + .unwrap_or_else(|e| panic!("f32 failed to parse `{}`: {:?}", num, e)); let mut f = num.parse::<Single>().unwrap_or_else(|e| { panic!("apfloat::ieee::Single failed to parse `{}`: {:?}", num, e) }); @@ -82,7 +82,9 @@ fn parse_float<'tcx>(num: Symbol, fty: ty::FloatTy, neg: bool) -> Result<ConstVa Scalar::from_f32(f) } ty::FloatTy::F64 => { - let rust_f = num.parse::<f64>().map_err(|_| ())?; + let rust_f = num + .parse::<f64>() + .unwrap_or_else(|e| panic!("f64 failed to parse `{}`: {:?}", num, e)); let mut f = num.parse::<Double>().unwrap_or_else(|e| { panic!("apfloat::ieee::Double failed to parse `{}`: {:?}", num, e) }); @@ -103,5 +105,5 @@ fn parse_float<'tcx>(num: Symbol, fty: ty::FloatTy, neg: bool) -> Result<ConstVa } }; - Ok(ConstValue::Scalar(scalar)) + ConstValue::Scalar(scalar) } diff --git a/compiler/rustc_mir_build/src/thir/cx/mod.rs b/compiler/rustc_mir_build/src/thir/cx/mod.rs index 49ba71e3520..604e544286a 100644 --- a/compiler/rustc_mir_build/src/thir/cx/mod.rs +++ b/compiler/rustc_mir_build/src/thir/cx/mod.rs @@ -67,12 +67,6 @@ impl<'tcx> Cx<'tcx> { match self.tcx.at(sp).lit_to_const(LitToConstInput { lit, ty, neg }) { Ok(c) => c, - Err(LitToConstError::UnparseableFloat) => { - // FIXME(#31407) this is only necessary because float parsing is buggy - self.tcx.sess.span_err(sp, "could not evaluate float literal (see issue #31407)"); - // create a dummy value and continue compiling - self.tcx.const_error(ty) - } Err(LitToConstError::Reported) => { // create a dummy value and continue compiling self.tcx.const_error(ty) diff --git a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs index 389a7595315..22c07fbec68 100644 --- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs +++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs @@ -84,7 +84,7 @@ impl<'tcx> Visitor<'tcx> for MatchVisitor<'_, 'tcx> { } impl PatCtxt<'_, '_> { - fn report_inlining_errors(&self, pat_span: Span) { + fn report_inlining_errors(&self) { for error in &self.errors { match *error { PatternError::StaticInPattern(span) => { @@ -96,14 +96,6 @@ impl PatCtxt<'_, '_> { PatternError::ConstParamInPattern(span) => { self.span_e0158(span, "const parameters cannot be referenced in patterns") } - PatternError::FloatBug => { - // FIXME(#31407) this is only necessary because float parsing is buggy - rustc_middle::mir::interpret::struct_error( - self.tcx.at(pat_span), - "could not evaluate float literal (see issue #31407)", - ) - .emit(); - } PatternError::NonConstPath(span) => { rustc_middle::mir::interpret::struct_error( self.tcx.at(span), @@ -142,7 +134,7 @@ impl<'tcx> MatchVisitor<'_, 'tcx> { let pattern: &_ = cx.pattern_arena.alloc(expand_pattern(pattern)); if !patcx.errors.is_empty() { *have_errors = true; - patcx.report_inlining_errors(pat.span); + patcx.report_inlining_errors(); } (pattern, pattern_ty) } diff --git a/compiler/rustc_mir_build/src/thir/pattern/mod.rs b/compiler/rustc_mir_build/src/thir/pattern/mod.rs index 3ea76fb99d5..c3adbb42215 100644 --- a/compiler/rustc_mir_build/src/thir/pattern/mod.rs +++ b/compiler/rustc_mir_build/src/thir/pattern/mod.rs @@ -31,7 +31,6 @@ crate enum PatternError { AssocConstInPattern(Span), ConstParamInPattern(Span), StaticInPattern(Span), - FloatBug, NonConstPath(Span), } @@ -563,10 +562,6 @@ impl<'a, 'tcx> PatCtxt<'a, 'tcx> { LitToConstInput { lit: &lit.node, ty: self.typeck_results.expr_ty(expr), neg }; match self.tcx.at(expr.span).lit_to_const(lit_input) { Ok(val) => *self.const_to_pat(val, expr.hir_id, lit.span, false).kind, - Err(LitToConstError::UnparseableFloat) => { - self.errors.push(PatternError::FloatBug); - PatKind::Wild - } Err(LitToConstError::Reported) => PatKind::Wild, Err(LitToConstError::TypeError) => bug!("lower_lit: had type error"), } diff --git a/library/core/src/num/dec2flt/algorithm.rs b/library/core/src/num/dec2flt/algorithm.rs deleted file mode 100644 index 313b6870ac9..00000000000 --- a/library/core/src/num/dec2flt/algorithm.rs +++ /dev/null @@ -1,429 +0,0 @@ -//! The various algorithms from the paper. - -use crate::cmp::min; -use crate::cmp::Ordering::{Equal, Greater, Less}; -use crate::num::dec2flt::num::{self, Big}; -use crate::num::dec2flt::rawfp::{self, fp_to_float, next_float, prev_float, RawFloat, Unpacked}; -use crate::num::dec2flt::table; -use crate::num::diy_float::Fp; - -/// Number of significand bits in Fp -const P: u32 = 64; - -// We simply store the best approximation for *all* exponents, so the variable "h" and the -// associated conditions can be omitted. This trades performance for a couple kilobytes of space. - -fn power_of_ten(e: i16) -> Fp { - assert!(e >= table::MIN_E); - let i = e - table::MIN_E; - let sig = table::POWERS.0[i as usize]; - let exp = table::POWERS.1[i as usize]; - Fp { f: sig, e: exp } -} - -// In most architectures, floating point operations have an explicit bit size, therefore the -// precision of the computation is determined on a per-operation basis. -#[cfg(any(not(target_arch = "x86"), target_feature = "sse2"))] -mod fpu_precision { - pub fn set_precision<T>() {} -} - -// On x86, the x87 FPU is used for float operations if the SSE/SSE2 extensions are not available. -// The x87 FPU operates with 80 bits of precision by default, which means that operations will -// round to 80 bits causing double rounding to happen when values are eventually represented as -// 32/64 bit float values. To overcome this, the FPU control word can be set so that the -// computations are performed in the desired precision. -#[cfg(all(target_arch = "x86", not(target_feature = "sse2")))] -mod fpu_precision { - use crate::mem::size_of; - - /// A structure used to preserve the original value of the FPU control word, so that it can be - /// restored when the structure is dropped. - /// - /// The x87 FPU is a 16-bits register whose fields are as follows: - /// - /// | 12-15 | 10-11 | 8-9 | 6-7 | 5 | 4 | 3 | 2 | 1 | 0 | - /// |------:|------:|----:|----:|---:|---:|---:|---:|---:|---:| - /// | | RC | PC | | PM | UM | OM | ZM | DM | IM | - /// - /// The documentation for all of the fields is available in the IA-32 Architectures Software - /// Developer's Manual (Volume 1). - /// - /// The only field which is relevant for the following code is PC, Precision Control. This - /// field determines the precision of the operations performed by the FPU. It can be set to: - /// - 0b00, single precision i.e., 32-bits - /// - 0b10, double precision i.e., 64-bits - /// - 0b11, double extended precision i.e., 80-bits (default state) - /// The 0b01 value is reserved and should not be used. - pub struct FPUControlWord(u16); - - fn set_cw(cw: u16) { - // SAFETY: the `fldcw` instruction has been audited to be able to work correctly with - // any `u16` - unsafe { - asm!( - "fldcw word ptr [{}]", - in(reg) &cw, - options(nostack), - ) - } - } - - /// Sets the precision field of the FPU to `T` and returns a `FPUControlWord`. - pub fn set_precision<T>() -> FPUControlWord { - let mut cw = 0_u16; - - // Compute the value for the Precision Control field that is appropriate for `T`. - let cw_precision = match size_of::<T>() { - 4 => 0x0000, // 32 bits - 8 => 0x0200, // 64 bits - _ => 0x0300, // default, 80 bits - }; - - // Get the original value of the control word to restore it later, when the - // `FPUControlWord` structure is dropped - // SAFETY: the `fnstcw` instruction has been audited to be able to work correctly with - // any `u16` - unsafe { - asm!( - "fnstcw word ptr [{}]", - in(reg) &mut cw, - options(nostack), - ) - } - - // Set the control word to the desired precision. This is achieved by masking away the old - // precision (bits 8 and 9, 0x300) and replacing it with the precision flag computed above. - set_cw((cw & 0xFCFF) | cw_precision); - - FPUControlWord(cw) - } - - impl Drop for FPUControlWord { - fn drop(&mut self) { - set_cw(self.0) - } - } -} - -/// The fast path of Bellerophon using machine-sized integers and floats. -/// -/// This is extracted into a separate function so that it can be attempted before constructing -/// a bignum. -pub fn fast_path<T: RawFloat>(integral: &[u8], fractional: &[u8], e: i64) -> Option<T> { - let num_digits = integral.len() + fractional.len(); - // log_10(f64::MAX_SIG) ~ 15.95. We compare the exact value to MAX_SIG near the end, - // this is just a quick, cheap rejection (and also frees the rest of the code from - // worrying about underflow). - if num_digits > 16 { - return None; - } - if e.abs() >= T::CEIL_LOG5_OF_MAX_SIG as i64 { - return None; - } - let f = num::from_str_unchecked(integral.iter().chain(fractional.iter())); - if f > T::MAX_SIG { - return None; - } - - // The fast path crucially depends on arithmetic being rounded to the correct number of bits - // without any intermediate rounding. On x86 (without SSE or SSE2) this requires the precision - // of the x87 FPU stack to be changed so that it directly rounds to 64/32 bit. - // The `set_precision` function takes care of setting the precision on architectures which - // require setting it by changing the global state (like the control word of the x87 FPU). - let _cw = fpu_precision::set_precision::<T>(); - - // The case e < 0 cannot be folded into the other branch. Negative powers result in - // a repeating fractional part in binary, which are rounded, which causes real - // (and occasionally quite significant!) errors in the final result. - if e >= 0 { - Some(T::from_int(f) * T::short_fast_pow10(e as usize)) - } else { - Some(T::from_int(f) / T::short_fast_pow10(e.abs() as usize)) - } -} - -/// Algorithm Bellerophon is trivial code justified by non-trivial numeric analysis. -/// -/// It rounds ``f`` to a float with 64 bit significand and multiplies it by the best approximation -/// of `10^e` (in the same floating point format). This is often enough to get the correct result. -/// However, when the result is close to halfway between two adjacent (ordinary) floats, the -/// compound rounding error from multiplying two approximation means the result may be off by a -/// few bits. When this happens, the iterative Algorithm R fixes things up. -/// -/// The hand-wavy "close to halfway" is made precise by the numeric analysis in the paper. -/// In the words of Clinger: -/// -/// > Slop, expressed in units of the least significant bit, is an inclusive bound for the error -/// > accumulated during the floating point calculation of the approximation to f * 10^e. (Slop is -/// > not a bound for the true error, but bounds the difference between the approximation z and -/// > the best possible approximation that uses p bits of significand.) -pub fn bellerophon<T: RawFloat>(f: &Big, e: i16) -> T { - let slop = if f <= &Big::from_u64(T::MAX_SIG) { - // The cases abs(e) < log5(2^N) are in fast_path() - if e >= 0 { 0 } else { 3 } - } else { - if e >= 0 { 1 } else { 4 } - }; - let z = rawfp::big_to_fp(f).mul(&power_of_ten(e)).normalize(); - let exp_p_n = 1 << (P - T::SIG_BITS as u32); - let lowbits: i64 = (z.f % exp_p_n) as i64; - // Is the slop large enough to make a difference when - // rounding to n bits? - if (lowbits - exp_p_n as i64 / 2).abs() <= slop { - algorithm_r(f, e, fp_to_float(z)) - } else { - fp_to_float(z) - } -} - -/// An iterative algorithm that improves a floating point approximation of `f * 10^e`. -/// -/// Each iteration gets one unit in the last place closer, which of course takes terribly long to -/// converge if `z0` is even mildly off. Luckily, when used as fallback for Bellerophon, the -/// starting approximation is off by at most one ULP. -fn algorithm_r<T: RawFloat>(f: &Big, e: i16, z0: T) -> T { - let mut z = z0; - loop { - let raw = z.unpack(); - let (m, k) = (raw.sig, raw.k); - let mut x = f.clone(); - let mut y = Big::from_u64(m); - - // Find positive integers `x`, `y` such that `x / y` is exactly `(f * 10^e) / (m * 2^k)`. - // This not only avoids dealing with the signs of `e` and `k`, we also eliminate the - // power of two common to `10^e` and `2^k` to make the numbers smaller. - make_ratio(&mut x, &mut y, e, k); - - let m_digits = [(m & 0xFF_FF_FF_FF) as u32, (m >> 32) as u32]; - // This is written a bit awkwardly because our bignums don't support - // negative numbers, so we use the absolute value + sign information. - // The multiplication with m_digits can't overflow. If `x` or `y` are large enough that - // we need to worry about overflow, then they are also large enough that `make_ratio` has - // reduced the fraction by a factor of 2^64 or more. - let (d2, d_negative) = if x >= y { - // Don't need x any more, save a clone(). - x.sub(&y).mul_pow2(1).mul_digits(&m_digits); - (x, false) - } else { - // Still need y - make a copy. - let mut y = y.clone(); - y.sub(&x).mul_pow2(1).mul_digits(&m_digits); - (y, true) - }; - - if d2 < y { - let mut d2_double = d2; - d2_double.mul_pow2(1); - if m == T::MIN_SIG && d_negative && d2_double > y { - z = prev_float(z); - } else { - return z; - } - } else if d2 == y { - if m % 2 == 0 { - if m == T::MIN_SIG && d_negative { - z = prev_float(z); - } else { - return z; - } - } else if d_negative { - z = prev_float(z); - } else { - z = next_float(z); - } - } else if d_negative { - z = prev_float(z); - } else { - z = next_float(z); - } - } -} - -/// Given `x = f` and `y = m` where `f` represent input decimal digits as usual and `m` is the -/// significand of a floating point approximation, make the ratio `x / y` equal to -/// `(f * 10^e) / (m * 2^k)`, possibly reduced by a power of two both have in common. -fn make_ratio(x: &mut Big, y: &mut Big, e: i16, k: i16) { - let (e_abs, k_abs) = (e.abs() as usize, k.abs() as usize); - if e >= 0 { - if k >= 0 { - // x = f * 10^e, y = m * 2^k, except that we reduce the fraction by some power of two. - let common = min(e_abs, k_abs); - x.mul_pow5(e_abs).mul_pow2(e_abs - common); - y.mul_pow2(k_abs - common); - } else { - // x = f * 10^e * 2^abs(k), y = m - // This can't overflow because it requires positive `e` and negative `k`, which can - // only happen for values extremely close to 1, which means that `e` and `k` will be - // comparatively tiny. - x.mul_pow5(e_abs).mul_pow2(e_abs + k_abs); - } - } else { - if k >= 0 { - // x = f, y = m * 10^abs(e) * 2^k - // This can't overflow either, see above. - y.mul_pow5(e_abs).mul_pow2(k_abs + e_abs); - } else { - // x = f * 2^abs(k), y = m * 10^abs(e), again reducing by a common power of two. - let common = min(e_abs, k_abs); - x.mul_pow2(k_abs - common); - y.mul_pow5(e_abs).mul_pow2(e_abs - common); - } - } -} - -/// Conceptually, Algorithm M is the simplest way to convert a decimal to a float. -/// -/// We form a ratio that is equal to `f * 10^e`, then throwing in powers of two until it gives -/// a valid float significand. The binary exponent `k` is the number of times we multiplied -/// numerator or denominator by two, i.e., at all times `f * 10^e` equals `(u / v) * 2^k`. -/// When we have found out significand, we only need to round by inspecting the remainder of the -/// division, which is done in helper functions further below. -/// -/// This algorithm is super slow, even with the optimization described in `quick_start()`. -/// However, it's the simplest of the algorithms to adapt for overflow, underflow, and subnormal -/// results. This implementation takes over when Bellerophon and Algorithm R are overwhelmed. -/// Detecting underflow and overflow is easy: The ratio still isn't an in-range significand, -/// yet the minimum/maximum exponent has been reached. In the case of overflow, we simply return -/// infinity. -/// -/// Handling underflow and subnormals is trickier. One big problem is that, with the minimum -/// exponent, the ratio might still be too large for a significand. See underflow() for details. -pub fn algorithm_m<T: RawFloat>(f: &Big, e: i16) -> T { - let mut u; - let mut v; - let e_abs = e.abs() as usize; - let mut k = 0; - if e < 0 { - u = f.clone(); - v = Big::from_small(1); - v.mul_pow5(e_abs).mul_pow2(e_abs); - } else { - // FIXME possible optimization: generalize big_to_fp so that we can do the equivalent of - // fp_to_float(big_to_fp(u)) here, only without the double rounding. - u = f.clone(); - u.mul_pow5(e_abs).mul_pow2(e_abs); - v = Big::from_small(1); - } - quick_start::<T>(&mut u, &mut v, &mut k); - let mut rem = Big::from_small(0); - let mut x = Big::from_small(0); - let min_sig = Big::from_u64(T::MIN_SIG); - let max_sig = Big::from_u64(T::MAX_SIG); - loop { - u.div_rem(&v, &mut x, &mut rem); - if k == T::MIN_EXP_INT { - // We have to stop at the minimum exponent, if we wait until `k < T::MIN_EXP_INT`, - // then we'd be off by a factor of two. Unfortunately this means we have to special- - // case normal numbers with the minimum exponent. - // FIXME find a more elegant formulation, but run the `tiny-pow10` test to make sure - // that it's actually correct! - if x >= min_sig && x <= max_sig { - break; - } - return underflow(x, v, rem); - } - if k > T::MAX_EXP_INT { - return T::INFINITY; - } - if x < min_sig { - u.mul_pow2(1); - k -= 1; - } else if x > max_sig { - v.mul_pow2(1); - k += 1; - } else { - break; - } - } - let q = num::to_u64(&x); - let z = rawfp::encode_normal(Unpacked::new(q, k)); - round_by_remainder(v, rem, q, z) -} - -/// Skips over most Algorithm M iterations by checking the bit length. -fn quick_start<T: RawFloat>(u: &mut Big, v: &mut Big, k: &mut i16) { - // The bit length is an estimate of the base two logarithm, and log(u / v) = log(u) - log(v). - // The estimate is off by at most 1, but always an under-estimate, so the error on log(u) - // and log(v) are of the same sign and cancel out (if both are large). Therefore the error - // for log(u / v) is at most one as well. - // The target ratio is one where u/v is in an in-range significand. Thus our termination - // condition is log2(u / v) being the significand bits, plus/minus one. - // FIXME Looking at the second bit could improve the estimate and avoid some more divisions. - let target_ratio = T::SIG_BITS as i16; - let log2_u = u.bit_length() as i16; - let log2_v = v.bit_length() as i16; - let mut u_shift: i16 = 0; - let mut v_shift: i16 = 0; - assert!(*k == 0); - loop { - if *k == T::MIN_EXP_INT { - // Underflow or subnormal. Leave it to the main function. - break; - } - if *k == T::MAX_EXP_INT { - // Overflow. Leave it to the main function. - break; - } - let log2_ratio = (log2_u + u_shift) - (log2_v + v_shift); - if log2_ratio < target_ratio - 1 { - u_shift += 1; - *k -= 1; - } else if log2_ratio > target_ratio + 1 { - v_shift += 1; - *k += 1; - } else { - break; - } - } - u.mul_pow2(u_shift as usize); - v.mul_pow2(v_shift as usize); -} - -fn underflow<T: RawFloat>(x: Big, v: Big, rem: Big) -> T { - if x < Big::from_u64(T::MIN_SIG) { - let q = num::to_u64(&x); - let z = rawfp::encode_subnormal(q); - return round_by_remainder(v, rem, q, z); - } - // Ratio isn't an in-range significand with the minimum exponent, so we need to round off - // excess bits and adjust the exponent accordingly. The real value now looks like this: - // - // x lsb - // /--------------\/ - // 1010101010101010.10101010101010 * 2^k - // \-----/\-------/ \------------/ - // q trunc. (represented by rem) - // - // Therefore, when the rounded-off bits are != 0.5 ULP, they decide the rounding - // on their own. When they are equal and the remainder is non-zero, the value still - // needs to be rounded up. Only when the rounded off bits are 1/2 and the remainder - // is zero, we have a half-to-even situation. - let bits = x.bit_length(); - let lsb = bits - T::SIG_BITS as usize; - let q = num::get_bits(&x, lsb, bits); - let k = T::MIN_EXP_INT + lsb as i16; - let z = rawfp::encode_normal(Unpacked::new(q, k)); - let q_even = q % 2 == 0; - match num::compare_with_half_ulp(&x, lsb) { - Greater => next_float(z), - Less => z, - Equal if rem.is_zero() && q_even => z, - Equal => next_float(z), - } -} - -/// Ordinary round-to-even, obfuscated by having to round based on the remainder of a division. -fn round_by_remainder<T: RawFloat>(v: Big, r: Big, q: u64, z: T) -> T { - let mut v_minus_r = v; - v_minus_r.sub(&r); - if r < v_minus_r { - z - } else if r > v_minus_r { - next_float(z) - } else if q % 2 == 0 { - z - } else { - next_float(z) - } -} diff --git a/library/core/src/num/dec2flt/common.rs b/library/core/src/num/dec2flt/common.rs new file mode 100644 index 00000000000..247123737df --- /dev/null +++ b/library/core/src/num/dec2flt/common.rs @@ -0,0 +1,198 @@ +//! Common utilities, for internal use only. + +use crate::ptr; + +/// Helper methods to process immutable bytes. +pub(crate) trait ByteSlice: AsRef<[u8]> { + unsafe fn first_unchecked(&self) -> u8 { + debug_assert!(!self.is_empty()); + // SAFETY: safe as long as self is not empty + unsafe { *self.as_ref().get_unchecked(0) } + } + + /// Get if the slice contains no elements. + fn is_empty(&self) -> bool { + self.as_ref().is_empty() + } + + /// Check if the slice at least `n` length. + fn check_len(&self, n: usize) -> bool { + n <= self.as_ref().len() + } + + /// Check if the first character in the slice is equal to c. + fn first_is(&self, c: u8) -> bool { + self.as_ref().first() == Some(&c) + } + + /// Check if the first character in the slice is equal to c1 or c2. + fn first_is2(&self, c1: u8, c2: u8) -> bool { + if let Some(&c) = self.as_ref().first() { c == c1 || c == c2 } else { false } + } + + /// Bounds-checked test if the first character in the slice is a digit. + fn first_isdigit(&self) -> bool { + if let Some(&c) = self.as_ref().first() { c.is_ascii_digit() } else { false } + } + + /// Check if self starts with u with a case-insensitive comparison. + fn eq_ignore_case(&self, u: &[u8]) -> bool { + debug_assert!(self.as_ref().len() >= u.len()); + let iter = self.as_ref().iter().zip(u.iter()); + let d = iter.fold(0, |i, (&x, &y)| i | (x ^ y)); + d == 0 || d == 32 + } + + /// Get the remaining slice after the first N elements. + fn advance(&self, n: usize) -> &[u8] { + &self.as_ref()[n..] + } + + /// Get the slice after skipping all leading characters equal c. + fn skip_chars(&self, c: u8) -> &[u8] { + let mut s = self.as_ref(); + while s.first_is(c) { + s = s.advance(1); + } + s + } + + /// Get the slice after skipping all leading characters equal c1 or c2. + fn skip_chars2(&self, c1: u8, c2: u8) -> &[u8] { + let mut s = self.as_ref(); + while s.first_is2(c1, c2) { + s = s.advance(1); + } + s + } + + /// Read 8 bytes as a 64-bit integer in little-endian order. + unsafe fn read_u64_unchecked(&self) -> u64 { + debug_assert!(self.check_len(8)); + let src = self.as_ref().as_ptr() as *const u64; + // SAFETY: safe as long as self is at least 8 bytes + u64::from_le(unsafe { ptr::read_unaligned(src) }) + } + + /// Try to read the next 8 bytes from the slice. + fn read_u64(&self) -> Option<u64> { + if self.check_len(8) { + // SAFETY: self must be at least 8 bytes. + Some(unsafe { self.read_u64_unchecked() }) + } else { + None + } + } + + /// Calculate the offset of slice from another. + fn offset_from(&self, other: &Self) -> isize { + other.as_ref().len() as isize - self.as_ref().len() as isize + } +} + +impl ByteSlice for [u8] {} + +/// Helper methods to process mutable bytes. +pub(crate) trait ByteSliceMut: AsMut<[u8]> { + /// Write a 64-bit integer as 8 bytes in little-endian order. + unsafe fn write_u64_unchecked(&mut self, value: u64) { + debug_assert!(self.as_mut().len() >= 8); + let dst = self.as_mut().as_mut_ptr() as *mut u64; + // NOTE: we must use `write_unaligned`, since dst is not + // guaranteed to be properly aligned. Miri will warn us + // if we use `write` instead of `write_unaligned`, as expected. + // SAFETY: safe as long as self is at least 8 bytes + unsafe { + ptr::write_unaligned(dst, u64::to_le(value)); + } + } +} + +impl ByteSliceMut for [u8] {} + +/// Bytes wrapper with specialized methods for ASCII characters. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(crate) struct AsciiStr<'a> { + slc: &'a [u8], +} + +impl<'a> AsciiStr<'a> { + pub fn new(slc: &'a [u8]) -> Self { + Self { slc } + } + + /// Advance the view by n, advancing it in-place to (n..). + pub unsafe fn step_by(&mut self, n: usize) -> &mut Self { + // SAFETY: safe as long n is less than the buffer length + self.slc = unsafe { self.slc.get_unchecked(n..) }; + self + } + + /// Advance the view by n, advancing it in-place to (1..). + pub unsafe fn step(&mut self) -> &mut Self { + // SAFETY: safe as long as self is not empty + unsafe { self.step_by(1) } + } + + /// Iteratively parse and consume digits from bytes. + pub fn parse_digits(&mut self, mut func: impl FnMut(u8)) { + while let Some(&c) = self.as_ref().first() { + let c = c.wrapping_sub(b'0'); + if c < 10 { + func(c); + // SAFETY: self cannot be empty + unsafe { + self.step(); + } + } else { + break; + } + } + } +} + +impl<'a> AsRef<[u8]> for AsciiStr<'a> { + #[inline] + fn as_ref(&self) -> &[u8] { + self.slc + } +} + +impl<'a> ByteSlice for AsciiStr<'a> {} + +/// Determine if 8 bytes are all decimal digits. +/// This does not care about the order in which the bytes were loaded. +pub(crate) fn is_8digits(v: u64) -> bool { + let a = v.wrapping_add(0x4646_4646_4646_4646); + let b = v.wrapping_sub(0x3030_3030_3030_3030); + (a | b) & 0x8080_8080_8080_8080 == 0 +} + +/// Iteratively parse and consume digits from bytes. +pub(crate) fn parse_digits(s: &mut &[u8], mut f: impl FnMut(u8)) { + while let Some(&c) = s.get(0) { + let c = c.wrapping_sub(b'0'); + if c < 10 { + f(c); + *s = s.advance(1); + } else { + break; + } + } +} + +/// A custom 64-bit floating point type, representing `f * 2^e`. +/// e is biased, so it be directly shifted into the exponent bits. +#[derive(Debug, Copy, Clone, PartialEq, Eq, Default)] +pub struct BiasedFp { + /// The significant digits. + pub f: u64, + /// The biased, binary exponent. + pub e: i32, +} + +impl BiasedFp { + pub const fn zero_pow2(e: i32) -> Self { + Self { f: 0, e } + } +} diff --git a/library/core/src/num/dec2flt/decimal.rs b/library/core/src/num/dec2flt/decimal.rs new file mode 100644 index 00000000000..f8edc3625e0 --- /dev/null +++ b/library/core/src/num/dec2flt/decimal.rs @@ -0,0 +1,351 @@ +//! Arbitrary-precision decimal class for fallback algorithms. +//! +//! This is only used if the fast-path (native floats) and +//! the Eisel-Lemire algorithm are unable to unambiguously +//! determine the float. +//! +//! The technique used is "Simple Decimal Conversion", developed +//! by Nigel Tao and Ken Thompson. A detailed description of the +//! algorithm can be found in "ParseNumberF64 by Simple Decimal Conversion", +//! available online: <https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html>. + +use crate::num::dec2flt::common::{is_8digits, parse_digits, ByteSlice, ByteSliceMut}; + +#[derive(Clone)] +pub struct Decimal { + /// The number of significant digits in the decimal. + pub num_digits: usize, + /// The offset of the decimal point in the significant digits. + pub decimal_point: i32, + /// If the number of significant digits stored in the decimal is truncated. + pub truncated: bool, + /// Buffer of the raw digits, in the range [0, 9]. + pub digits: [u8; Self::MAX_DIGITS], +} + +impl Default for Decimal { + fn default() -> Self { + Self { num_digits: 0, decimal_point: 0, truncated: false, digits: [0; Self::MAX_DIGITS] } + } +} + +impl Decimal { + /// The maximum number of digits required to unambiguously round a float. + /// + /// For a double-precision IEEE-754 float, this required 767 digits, + /// so we store the max digits + 1. + /// + /// We can exactly represent a float in radix `b` from radix 2 if + /// `b` is divisible by 2. This function calculates the exact number of + /// digits required to exactly represent that float. + /// + /// According to the "Handbook of Floating Point Arithmetic", + /// for IEEE754, with emin being the min exponent, p2 being the + /// precision, and b being the radix, the number of digits follows as: + /// + /// `−emin + p2 + ⌊(emin + 1) log(2, b) − log(1 − 2^(−p2), b)⌋` + /// + /// For f32, this follows as: + /// emin = -126 + /// p2 = 24 + /// + /// For f64, this follows as: + /// emin = -1022 + /// p2 = 53 + /// + /// In Python: + /// `-emin + p2 + math.floor((emin+ 1)*math.log(2, b)-math.log(1-2**(-p2), b))` + pub const MAX_DIGITS: usize = 768; + /// The max digits that can be exactly represented in a 64-bit integer. + pub const MAX_DIGITS_WITHOUT_OVERFLOW: usize = 19; + pub const DECIMAL_POINT_RANGE: i32 = 2047; + + /// Append a digit to the buffer. + pub fn try_add_digit(&mut self, digit: u8) { + if self.num_digits < Self::MAX_DIGITS { + self.digits[self.num_digits] = digit; + } + self.num_digits += 1; + } + + /// Trim trailing zeros from the buffer. + pub fn trim(&mut self) { + // All of the following calls to `Decimal::trim` can't panic because: + // + // 1. `parse_decimal` sets `num_digits` to a max of `Decimal::MAX_DIGITS`. + // 2. `right_shift` sets `num_digits` to `write_index`, which is bounded by `num_digits`. + // 3. `left_shift` `num_digits` to a max of `Decimal::MAX_DIGITS`. + // + // Trim is only called in `right_shift` and `left_shift`. + debug_assert!(self.num_digits <= Self::MAX_DIGITS); + while self.num_digits != 0 && self.digits[self.num_digits - 1] == 0 { + self.num_digits -= 1; + } + } + + pub fn round(&self) -> u64 { + if self.num_digits == 0 || self.decimal_point < 0 { + return 0; + } else if self.decimal_point > 18 { + return 0xFFFF_FFFF_FFFF_FFFF_u64; + } + let dp = self.decimal_point as usize; + let mut n = 0_u64; + for i in 0..dp { + n *= 10; + if i < self.num_digits { + n += self.digits[i] as u64; + } + } + let mut round_up = false; + if dp < self.num_digits { + round_up = self.digits[dp] >= 5; + if self.digits[dp] == 5 && dp + 1 == self.num_digits { + round_up = self.truncated || ((dp != 0) && (1 & self.digits[dp - 1] != 0)) + } + } + if round_up { + n += 1; + } + n + } + + /// Computes decimal * 2^shift. + pub fn left_shift(&mut self, shift: usize) { + if self.num_digits == 0 { + return; + } + let num_new_digits = number_of_digits_decimal_left_shift(self, shift); + let mut read_index = self.num_digits; + let mut write_index = self.num_digits + num_new_digits; + let mut n = 0_u64; + while read_index != 0 { + read_index -= 1; + write_index -= 1; + n += (self.digits[read_index] as u64) << shift; + let quotient = n / 10; + let remainder = n - (10 * quotient); + if write_index < Self::MAX_DIGITS { + self.digits[write_index] = remainder as u8; + } else if remainder > 0 { + self.truncated = true; + } + n = quotient; + } + while n > 0 { + write_index -= 1; + let quotient = n / 10; + let remainder = n - (10 * quotient); + if write_index < Self::MAX_DIGITS { + self.digits[write_index] = remainder as u8; + } else if remainder > 0 { + self.truncated = true; + } + n = quotient; + } + self.num_digits += num_new_digits; + if self.num_digits > Self::MAX_DIGITS { + self.num_digits = Self::MAX_DIGITS; + } + self.decimal_point += num_new_digits as i32; + self.trim(); + } + + /// Computes decimal * 2^-shift. + pub fn right_shift(&mut self, shift: usize) { + let mut read_index = 0; + let mut write_index = 0; + let mut n = 0_u64; + while (n >> shift) == 0 { + if read_index < self.num_digits { + n = (10 * n) + self.digits[read_index] as u64; + read_index += 1; + } else if n == 0 { + return; + } else { + while (n >> shift) == 0 { + n *= 10; + read_index += 1; + } + break; + } + } + self.decimal_point -= read_index as i32 - 1; + if self.decimal_point < -Self::DECIMAL_POINT_RANGE { + // `self = Self::Default()`, but without the overhead of clearing `digits`. + self.num_digits = 0; + self.decimal_point = 0; + self.truncated = false; + return; + } + let mask = (1_u64 << shift) - 1; + while read_index < self.num_digits { + let new_digit = (n >> shift) as u8; + n = (10 * (n & mask)) + self.digits[read_index] as u64; + read_index += 1; + self.digits[write_index] = new_digit; + write_index += 1; + } + while n > 0 { + let new_digit = (n >> shift) as u8; + n = 10 * (n & mask); + if write_index < Self::MAX_DIGITS { + self.digits[write_index] = new_digit; + write_index += 1; + } else if new_digit > 0 { + self.truncated = true; + } + } + self.num_digits = write_index; + self.trim(); + } +} + +/// Parse a big integer representation of the float as a decimal. +pub fn parse_decimal(mut s: &[u8]) -> Decimal { + let mut d = Decimal::default(); + let start = s; + s = s.skip_chars(b'0'); + parse_digits(&mut s, |digit| d.try_add_digit(digit)); + if s.first_is(b'.') { + s = s.advance(1); + let first = s; + // Skip leading zeros. + if d.num_digits == 0 { + s = s.skip_chars(b'0'); + } + while s.len() >= 8 && d.num_digits + 8 < Decimal::MAX_DIGITS { + // SAFETY: s is at least 8 bytes. + let v = unsafe { s.read_u64_unchecked() }; + if !is_8digits(v) { + break; + } + // SAFETY: d.num_digits + 8 is less than d.digits.len() + unsafe { + d.digits[d.num_digits..].write_u64_unchecked(v - 0x3030_3030_3030_3030); + } + d.num_digits += 8; + s = s.advance(8); + } + parse_digits(&mut s, |digit| d.try_add_digit(digit)); + d.decimal_point = s.len() as i32 - first.len() as i32; + } + if d.num_digits != 0 { + // Ignore the trailing zeros if there are any + let mut n_trailing_zeros = 0; + for &c in start[..(start.len() - s.len())].iter().rev() { + if c == b'0' { + n_trailing_zeros += 1; + } else if c != b'.' { + break; + } + } + d.decimal_point += n_trailing_zeros as i32; + d.num_digits -= n_trailing_zeros; + d.decimal_point += d.num_digits as i32; + if d.num_digits > Decimal::MAX_DIGITS { + d.truncated = true; + d.num_digits = Decimal::MAX_DIGITS; + } + } + if s.first_is2(b'e', b'E') { + s = s.advance(1); + let mut neg_exp = false; + if s.first_is(b'-') { + neg_exp = true; + s = s.advance(1); + } else if s.first_is(b'+') { + s = s.advance(1); + } + let mut exp_num = 0_i32; + parse_digits(&mut s, |digit| { + if exp_num < 0x10000 { + exp_num = 10 * exp_num + digit as i32; + } + }); + d.decimal_point += if neg_exp { -exp_num } else { exp_num }; + } + for i in d.num_digits..Decimal::MAX_DIGITS_WITHOUT_OVERFLOW { + d.digits[i] = 0; + } + d +} + +fn number_of_digits_decimal_left_shift(d: &Decimal, mut shift: usize) -> usize { + #[rustfmt::skip] + const TABLE: [u16; 65] = [ + 0x0000, 0x0800, 0x0801, 0x0803, 0x1006, 0x1009, 0x100D, 0x1812, 0x1817, 0x181D, 0x2024, + 0x202B, 0x2033, 0x203C, 0x2846, 0x2850, 0x285B, 0x3067, 0x3073, 0x3080, 0x388E, 0x389C, + 0x38AB, 0x38BB, 0x40CC, 0x40DD, 0x40EF, 0x4902, 0x4915, 0x4929, 0x513E, 0x5153, 0x5169, + 0x5180, 0x5998, 0x59B0, 0x59C9, 0x61E3, 0x61FD, 0x6218, 0x6A34, 0x6A50, 0x6A6D, 0x6A8B, + 0x72AA, 0x72C9, 0x72E9, 0x7B0A, 0x7B2B, 0x7B4D, 0x8370, 0x8393, 0x83B7, 0x83DC, 0x8C02, + 0x8C28, 0x8C4F, 0x9477, 0x949F, 0x94C8, 0x9CF2, 0x051C, 0x051C, 0x051C, 0x051C, + ]; + #[rustfmt::skip] + const TABLE_POW5: [u8; 0x051C] = [ + 5, 2, 5, 1, 2, 5, 6, 2, 5, 3, 1, 2, 5, 1, 5, 6, 2, 5, 7, 8, 1, 2, 5, 3, 9, 0, 6, 2, 5, 1, + 9, 5, 3, 1, 2, 5, 9, 7, 6, 5, 6, 2, 5, 4, 8, 8, 2, 8, 1, 2, 5, 2, 4, 4, 1, 4, 0, 6, 2, 5, + 1, 2, 2, 0, 7, 0, 3, 1, 2, 5, 6, 1, 0, 3, 5, 1, 5, 6, 2, 5, 3, 0, 5, 1, 7, 5, 7, 8, 1, 2, + 5, 1, 5, 2, 5, 8, 7, 8, 9, 0, 6, 2, 5, 7, 6, 2, 9, 3, 9, 4, 5, 3, 1, 2, 5, 3, 8, 1, 4, 6, + 9, 7, 2, 6, 5, 6, 2, 5, 1, 9, 0, 7, 3, 4, 8, 6, 3, 2, 8, 1, 2, 5, 9, 5, 3, 6, 7, 4, 3, 1, + 6, 4, 0, 6, 2, 5, 4, 7, 6, 8, 3, 7, 1, 5, 8, 2, 0, 3, 1, 2, 5, 2, 3, 8, 4, 1, 8, 5, 7, 9, + 1, 0, 1, 5, 6, 2, 5, 1, 1, 9, 2, 0, 9, 2, 8, 9, 5, 5, 0, 7, 8, 1, 2, 5, 5, 9, 6, 0, 4, 6, + 4, 4, 7, 7, 5, 3, 9, 0, 6, 2, 5, 2, 9, 8, 0, 2, 3, 2, 2, 3, 8, 7, 6, 9, 5, 3, 1, 2, 5, 1, + 4, 9, 0, 1, 1, 6, 1, 1, 9, 3, 8, 4, 7, 6, 5, 6, 2, 5, 7, 4, 5, 0, 5, 8, 0, 5, 9, 6, 9, 2, + 3, 8, 2, 8, 1, 2, 5, 3, 7, 2, 5, 2, 9, 0, 2, 9, 8, 4, 6, 1, 9, 1, 4, 0, 6, 2, 5, 1, 8, 6, + 2, 6, 4, 5, 1, 4, 9, 2, 3, 0, 9, 5, 7, 0, 3, 1, 2, 5, 9, 3, 1, 3, 2, 2, 5, 7, 4, 6, 1, 5, + 4, 7, 8, 5, 1, 5, 6, 2, 5, 4, 6, 5, 6, 6, 1, 2, 8, 7, 3, 0, 7, 7, 3, 9, 2, 5, 7, 8, 1, 2, + 5, 2, 3, 2, 8, 3, 0, 6, 4, 3, 6, 5, 3, 8, 6, 9, 6, 2, 8, 9, 0, 6, 2, 5, 1, 1, 6, 4, 1, 5, + 3, 2, 1, 8, 2, 6, 9, 3, 4, 8, 1, 4, 4, 5, 3, 1, 2, 5, 5, 8, 2, 0, 7, 6, 6, 0, 9, 1, 3, 4, + 6, 7, 4, 0, 7, 2, 2, 6, 5, 6, 2, 5, 2, 9, 1, 0, 3, 8, 3, 0, 4, 5, 6, 7, 3, 3, 7, 0, 3, 6, + 1, 3, 2, 8, 1, 2, 5, 1, 4, 5, 5, 1, 9, 1, 5, 2, 2, 8, 3, 6, 6, 8, 5, 1, 8, 0, 6, 6, 4, 0, + 6, 2, 5, 7, 2, 7, 5, 9, 5, 7, 6, 1, 4, 1, 8, 3, 4, 2, 5, 9, 0, 3, 3, 2, 0, 3, 1, 2, 5, 3, + 6, 3, 7, 9, 7, 8, 8, 0, 7, 0, 9, 1, 7, 1, 2, 9, 5, 1, 6, 6, 0, 1, 5, 6, 2, 5, 1, 8, 1, 8, + 9, 8, 9, 4, 0, 3, 5, 4, 5, 8, 5, 6, 4, 7, 5, 8, 3, 0, 0, 7, 8, 1, 2, 5, 9, 0, 9, 4, 9, 4, + 7, 0, 1, 7, 7, 2, 9, 2, 8, 2, 3, 7, 9, 1, 5, 0, 3, 9, 0, 6, 2, 5, 4, 5, 4, 7, 4, 7, 3, 5, + 0, 8, 8, 6, 4, 6, 4, 1, 1, 8, 9, 5, 7, 5, 1, 9, 5, 3, 1, 2, 5, 2, 2, 7, 3, 7, 3, 6, 7, 5, + 4, 4, 3, 2, 3, 2, 0, 5, 9, 4, 7, 8, 7, 5, 9, 7, 6, 5, 6, 2, 5, 1, 1, 3, 6, 8, 6, 8, 3, 7, + 7, 2, 1, 6, 1, 6, 0, 2, 9, 7, 3, 9, 3, 7, 9, 8, 8, 2, 8, 1, 2, 5, 5, 6, 8, 4, 3, 4, 1, 8, + 8, 6, 0, 8, 0, 8, 0, 1, 4, 8, 6, 9, 6, 8, 9, 9, 4, 1, 4, 0, 6, 2, 5, 2, 8, 4, 2, 1, 7, 0, + 9, 4, 3, 0, 4, 0, 4, 0, 0, 7, 4, 3, 4, 8, 4, 4, 9, 7, 0, 7, 0, 3, 1, 2, 5, 1, 4, 2, 1, 0, + 8, 5, 4, 7, 1, 5, 2, 0, 2, 0, 0, 3, 7, 1, 7, 4, 2, 2, 4, 8, 5, 3, 5, 1, 5, 6, 2, 5, 7, 1, + 0, 5, 4, 2, 7, 3, 5, 7, 6, 0, 1, 0, 0, 1, 8, 5, 8, 7, 1, 1, 2, 4, 2, 6, 7, 5, 7, 8, 1, 2, + 5, 3, 5, 5, 2, 7, 1, 3, 6, 7, 8, 8, 0, 0, 5, 0, 0, 9, 2, 9, 3, 5, 5, 6, 2, 1, 3, 3, 7, 8, + 9, 0, 6, 2, 5, 1, 7, 7, 6, 3, 5, 6, 8, 3, 9, 4, 0, 0, 2, 5, 0, 4, 6, 4, 6, 7, 7, 8, 1, 0, + 6, 6, 8, 9, 4, 5, 3, 1, 2, 5, 8, 8, 8, 1, 7, 8, 4, 1, 9, 7, 0, 0, 1, 2, 5, 2, 3, 2, 3, 3, + 8, 9, 0, 5, 3, 3, 4, 4, 7, 2, 6, 5, 6, 2, 5, 4, 4, 4, 0, 8, 9, 2, 0, 9, 8, 5, 0, 0, 6, 2, + 6, 1, 6, 1, 6, 9, 4, 5, 2, 6, 6, 7, 2, 3, 6, 3, 2, 8, 1, 2, 5, 2, 2, 2, 0, 4, 4, 6, 0, 4, + 9, 2, 5, 0, 3, 1, 3, 0, 8, 0, 8, 4, 7, 2, 6, 3, 3, 3, 6, 1, 8, 1, 6, 4, 0, 6, 2, 5, 1, 1, + 1, 0, 2, 2, 3, 0, 2, 4, 6, 2, 5, 1, 5, 6, 5, 4, 0, 4, 2, 3, 6, 3, 1, 6, 6, 8, 0, 9, 0, 8, + 2, 0, 3, 1, 2, 5, 5, 5, 5, 1, 1, 1, 5, 1, 2, 3, 1, 2, 5, 7, 8, 2, 7, 0, 2, 1, 1, 8, 1, 5, + 8, 3, 4, 0, 4, 5, 4, 1, 0, 1, 5, 6, 2, 5, 2, 7, 7, 5, 5, 5, 7, 5, 6, 1, 5, 6, 2, 8, 9, 1, + 3, 5, 1, 0, 5, 9, 0, 7, 9, 1, 7, 0, 2, 2, 7, 0, 5, 0, 7, 8, 1, 2, 5, 1, 3, 8, 7, 7, 7, 8, + 7, 8, 0, 7, 8, 1, 4, 4, 5, 6, 7, 5, 5, 2, 9, 5, 3, 9, 5, 8, 5, 1, 1, 3, 5, 2, 5, 3, 9, 0, + 6, 2, 5, 6, 9, 3, 8, 8, 9, 3, 9, 0, 3, 9, 0, 7, 2, 2, 8, 3, 7, 7, 6, 4, 7, 6, 9, 7, 9, 2, + 5, 5, 6, 7, 6, 2, 6, 9, 5, 3, 1, 2, 5, 3, 4, 6, 9, 4, 4, 6, 9, 5, 1, 9, 5, 3, 6, 1, 4, 1, + 8, 8, 8, 2, 3, 8, 4, 8, 9, 6, 2, 7, 8, 3, 8, 1, 3, 4, 7, 6, 5, 6, 2, 5, 1, 7, 3, 4, 7, 2, + 3, 4, 7, 5, 9, 7, 6, 8, 0, 7, 0, 9, 4, 4, 1, 1, 9, 2, 4, 4, 8, 1, 3, 9, 1, 9, 0, 6, 7, 3, + 8, 2, 8, 1, 2, 5, 8, 6, 7, 3, 6, 1, 7, 3, 7, 9, 8, 8, 4, 0, 3, 5, 4, 7, 2, 0, 5, 9, 6, 2, + 2, 4, 0, 6, 9, 5, 9, 5, 3, 3, 6, 9, 1, 4, 0, 6, 2, 5, + ]; + + shift &= 63; + let x_a = TABLE[shift]; + let x_b = TABLE[shift + 1]; + let num_new_digits = (x_a >> 11) as _; + let pow5_a = (0x7FF & x_a) as usize; + let pow5_b = (0x7FF & x_b) as usize; + let pow5 = &TABLE_POW5[pow5_a..]; + for (i, &p5) in pow5.iter().enumerate().take(pow5_b - pow5_a) { + if i >= d.num_digits { + return num_new_digits - 1; + } else if d.digits[i] == p5 { + continue; + } else if d.digits[i] < p5 { + return num_new_digits - 1; + } else { + return num_new_digits; + } + } + num_new_digits +} diff --git a/library/core/src/num/dec2flt/float.rs b/library/core/src/num/dec2flt/float.rs new file mode 100644 index 00000000000..5921c5ed472 --- /dev/null +++ b/library/core/src/num/dec2flt/float.rs @@ -0,0 +1,207 @@ +//! Helper trait for generic float types. + +use crate::fmt::{Debug, LowerExp}; +use crate::num::FpCategory; +use crate::ops::{Add, Div, Mul, Neg}; + +/// A helper trait to avoid duplicating basically all the conversion code for `f32` and `f64`. +/// +/// See the parent module's doc comment for why this is necessary. +/// +/// Should **never ever** be implemented for other types or be used outside the dec2flt module. +#[doc(hidden)] +pub trait RawFloat: + Sized + + Div<Output = Self> + + Neg<Output = Self> + + Mul<Output = Self> + + Add<Output = Self> + + LowerExp + + PartialEq + + PartialOrd + + Default + + Clone + + Copy + + Debug +{ + const INFINITY: Self; + const NEG_INFINITY: Self; + const NAN: Self; + const NEG_NAN: Self; + + /// The number of bits in the significand, *excluding* the hidden bit. + const MANTISSA_EXPLICIT_BITS: usize; + + // Round-to-even only happens for negative values of q + // when q ≥ −4 in the 64-bit case and when q ≥ −17 in + // the 32-bitcase. + // + // When q ≥ 0,we have that 5^q ≤ 2m+1. In the 64-bit case,we + // have 5^q ≤ 2m+1 ≤ 2^54 or q ≤ 23. In the 32-bit case,we have + // 5^q ≤ 2m+1 ≤ 2^25 or q ≤ 10. + // + // When q < 0, we have w ≥ (2m+1)×5^−q. We must have that w < 2^64 + // so (2m+1)×5^−q < 2^64. We have that 2m+1 > 2^53 (64-bit case) + // or 2m+1 > 2^24 (32-bit case). Hence,we must have 2^53×5^−q < 2^64 + // (64-bit) and 2^24×5^−q < 2^64 (32-bit). Hence we have 5^−q < 2^11 + // or q ≥ −4 (64-bit case) and 5^−q < 2^40 or q ≥ −17 (32-bitcase). + // + // Thus we have that we only need to round ties to even when + // we have that q ∈ [−4,23](in the 64-bit case) or q∈[−17,10] + // (in the 32-bit case). In both cases,the power of five(5^|q|) + // fits in a 64-bit word. + const MIN_EXPONENT_ROUND_TO_EVEN: i32; + const MAX_EXPONENT_ROUND_TO_EVEN: i32; + + // Minimum exponent that for a fast path case, or `-⌊(MANTISSA_EXPLICIT_BITS+1)/log2(5)⌋` + const MIN_EXPONENT_FAST_PATH: i64; + + // Maximum exponent that for a fast path case, or `⌊(MANTISSA_EXPLICIT_BITS+1)/log2(5)⌋` + const MAX_EXPONENT_FAST_PATH: i64; + + // Maximum exponent that can be represented for a disguised-fast path case. + // This is `MAX_EXPONENT_FAST_PATH + ⌊(MANTISSA_EXPLICIT_BITS+1)/log2(10)⌋` + const MAX_EXPONENT_DISGUISED_FAST_PATH: i64; + + // Minimum exponent value `-(1 << (EXP_BITS - 1)) + 1`. + const MINIMUM_EXPONENT: i32; + + // Largest exponent value `(1 << EXP_BITS) - 1`. + const INFINITE_POWER: i32; + + // Index (in bits) of the sign. + const SIGN_INDEX: usize; + + // Smallest decimal exponent for a non-zero value. + const SMALLEST_POWER_OF_TEN: i32; + + // Largest decimal exponent for a non-infinite value. + const LARGEST_POWER_OF_TEN: i32; + + // Maximum mantissa for the fast-path (`1 << 53` for f64). + const MAX_MANTISSA_FAST_PATH: u64 = 2_u64 << Self::MANTISSA_EXPLICIT_BITS; + + /// Convert integer into float through an as cast. + /// This is only called in the fast-path algorithm, and therefore + /// will not lose precision, since the value will always have + /// only if the value is <= Self::MAX_MANTISSA_FAST_PATH. + fn from_u64(v: u64) -> Self; + + /// Performs a raw transmutation from an integer. + fn from_u64_bits(v: u64) -> Self; + + /// Get a small power-of-ten for fast-path multiplication. + fn pow10_fast_path(exponent: usize) -> Self; + + /// Returns the category that this number falls into. + fn classify(self) -> FpCategory; + + /// Returns the mantissa, exponent and sign as integers. + fn integer_decode(self) -> (u64, i16, i8); +} + +impl RawFloat for f32 { + const INFINITY: Self = f32::INFINITY; + const NEG_INFINITY: Self = f32::NEG_INFINITY; + const NAN: Self = f32::NAN; + const NEG_NAN: Self = -f32::NAN; + + const MANTISSA_EXPLICIT_BITS: usize = 23; + const MIN_EXPONENT_ROUND_TO_EVEN: i32 = -17; + const MAX_EXPONENT_ROUND_TO_EVEN: i32 = 10; + const MIN_EXPONENT_FAST_PATH: i64 = -10; // assuming FLT_EVAL_METHOD = 0 + const MAX_EXPONENT_FAST_PATH: i64 = 10; + const MAX_EXPONENT_DISGUISED_FAST_PATH: i64 = 17; + const MINIMUM_EXPONENT: i32 = -127; + const INFINITE_POWER: i32 = 0xFF; + const SIGN_INDEX: usize = 31; + const SMALLEST_POWER_OF_TEN: i32 = -65; + const LARGEST_POWER_OF_TEN: i32 = 38; + + fn from_u64(v: u64) -> Self { + debug_assert!(v <= Self::MAX_MANTISSA_FAST_PATH); + v as _ + } + + fn from_u64_bits(v: u64) -> Self { + f32::from_bits((v & 0xFFFFFFFF) as u32) + } + + fn pow10_fast_path(exponent: usize) -> Self { + #[allow(clippy::use_self)] + const TABLE: [f32; 16] = + [1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 0., 0., 0., 0., 0.]; + TABLE[exponent & 15] + } + + /// Returns the mantissa, exponent and sign as integers. + fn integer_decode(self) -> (u64, i16, i8) { + let bits = self.to_bits(); + let sign: i8 = if bits >> 31 == 0 { 1 } else { -1 }; + let mut exponent: i16 = ((bits >> 23) & 0xff) as i16; + let mantissa = + if exponent == 0 { (bits & 0x7fffff) << 1 } else { (bits & 0x7fffff) | 0x800000 }; + // Exponent bias + mantissa shift + exponent -= 127 + 23; + (mantissa as u64, exponent, sign) + } + + fn classify(self) -> FpCategory { + self.classify() + } +} + +impl RawFloat for f64 { + const INFINITY: Self = f64::INFINITY; + const NEG_INFINITY: Self = f64::NEG_INFINITY; + const NAN: Self = f64::NAN; + const NEG_NAN: Self = -f64::NAN; + + const MANTISSA_EXPLICIT_BITS: usize = 52; + const MIN_EXPONENT_ROUND_TO_EVEN: i32 = -4; + const MAX_EXPONENT_ROUND_TO_EVEN: i32 = 23; + const MIN_EXPONENT_FAST_PATH: i64 = -22; // assuming FLT_EVAL_METHOD = 0 + const MAX_EXPONENT_FAST_PATH: i64 = 22; + const MAX_EXPONENT_DISGUISED_FAST_PATH: i64 = 37; + const MINIMUM_EXPONENT: i32 = -1023; + const INFINITE_POWER: i32 = 0x7FF; + const SIGN_INDEX: usize = 63; + const SMALLEST_POWER_OF_TEN: i32 = -342; + const LARGEST_POWER_OF_TEN: i32 = 308; + + fn from_u64(v: u64) -> Self { + debug_assert!(v <= Self::MAX_MANTISSA_FAST_PATH); + v as _ + } + + fn from_u64_bits(v: u64) -> Self { + f64::from_bits(v) + } + + fn pow10_fast_path(exponent: usize) -> Self { + const TABLE: [f64; 32] = [ + 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, + 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22, 0., 0., 0., 0., 0., 0., 0., 0., 0., + ]; + TABLE[exponent & 31] + } + + /// Returns the mantissa, exponent and sign as integers. + fn integer_decode(self) -> (u64, i16, i8) { + let bits = self.to_bits(); + let sign: i8 = if bits >> 63 == 0 { 1 } else { -1 }; + let mut exponent: i16 = ((bits >> 52) & 0x7ff) as i16; + let mantissa = if exponent == 0 { + (bits & 0xfffffffffffff) << 1 + } else { + (bits & 0xfffffffffffff) | 0x10000000000000 + }; + // Exponent bias + mantissa shift + exponent -= 1023 + 52; + (mantissa, exponent, sign) + } + + fn classify(self) -> FpCategory { + self.classify() + } +} diff --git a/library/core/src/num/dec2flt/fpu.rs b/library/core/src/num/dec2flt/fpu.rs new file mode 100644 index 00000000000..24492d9a1dd --- /dev/null +++ b/library/core/src/num/dec2flt/fpu.rs @@ -0,0 +1,89 @@ +//! Platform-specific, assembly instructions to avoid +//! intermediate rounding on architectures with FPUs. + +pub use fpu_precision::set_precision; + +// On x86, the x87 FPU is used for float operations if the SSE/SSE2 extensions are not available. +// The x87 FPU operates with 80 bits of precision by default, which means that operations will +// round to 80 bits causing double rounding to happen when values are eventually represented as +// 32/64 bit float values. To overcome this, the FPU control word can be set so that the +// computations are performed in the desired precision. +#[cfg(all(target_arch = "x86", not(target_feature = "sse2")))] +mod fpu_precision { + use core::mem::size_of; + + /// A structure used to preserve the original value of the FPU control word, so that it can be + /// restored when the structure is dropped. + /// + /// The x87 FPU is a 16-bits register whose fields are as follows: + /// + /// | 12-15 | 10-11 | 8-9 | 6-7 | 5 | 4 | 3 | 2 | 1 | 0 | + /// |------:|------:|----:|----:|---:|---:|---:|---:|---:|---:| + /// | | RC | PC | | PM | UM | OM | ZM | DM | IM | + /// + /// The documentation for all of the fields is available in the IA-32 Architectures Software + /// Developer's Manual (Volume 1). + /// + /// The only field which is relevant for the following code is PC, Precision Control. This + /// field determines the precision of the operations performed by the FPU. It can be set to: + /// - 0b00, single precision i.e., 32-bits + /// - 0b10, double precision i.e., 64-bits + /// - 0b11, double extended precision i.e., 80-bits (default state) + /// The 0b01 value is reserved and should not be used. + pub struct FPUControlWord(u16); + + fn set_cw(cw: u16) { + // SAFETY: the `fldcw` instruction has been audited to be able to work correctly with + // any `u16` + unsafe { + asm!( + "fldcw word ptr [{}]", + in(reg) &cw, + options(nostack), + ) + } + } + + /// Sets the precision field of the FPU to `T` and returns a `FPUControlWord`. + pub fn set_precision<T>() -> FPUControlWord { + let mut cw = 0_u16; + + // Compute the value for the Precision Control field that is appropriate for `T`. + let cw_precision = match size_of::<T>() { + 4 => 0x0000, // 32 bits + 8 => 0x0200, // 64 bits + _ => 0x0300, // default, 80 bits + }; + + // Get the original value of the control word to restore it later, when the + // `FPUControlWord` structure is dropped + // SAFETY: the `fnstcw` instruction has been audited to be able to work correctly with + // any `u16` + unsafe { + asm!( + "fnstcw word ptr [{}]", + in(reg) &mut cw, + options(nostack), + ) + } + + // Set the control word to the desired precision. This is achieved by masking away the old + // precision (bits 8 and 9, 0x300) and replacing it with the precision flag computed above. + set_cw((cw & 0xFCFF) | cw_precision); + + FPUControlWord(cw) + } + + impl Drop for FPUControlWord { + fn drop(&mut self) { + set_cw(self.0) + } + } +} + +// In most architectures, floating point operations have an explicit bit size, therefore the +// precision of the computation is determined on a per-operation basis. +#[cfg(any(not(target_arch = "x86"), target_feature = "sse2"))] +mod fpu_precision { + pub fn set_precision<T>() {} +} diff --git a/library/core/src/num/dec2flt/lemire.rs b/library/core/src/num/dec2flt/lemire.rs new file mode 100644 index 00000000000..9b7efc3d556 --- /dev/null +++ b/library/core/src/num/dec2flt/lemire.rs @@ -0,0 +1,166 @@ +//! Implementation of the Eisel-Lemire algorithm. + +use crate::num::dec2flt::common::BiasedFp; +use crate::num::dec2flt::float::RawFloat; +use crate::num::dec2flt::table::{ + LARGEST_POWER_OF_FIVE, POWER_OF_FIVE_128, SMALLEST_POWER_OF_FIVE, +}; + +/// Compute a float using an extended-precision representation. +/// +/// Fast conversion of a the significant digits and decimal exponent +/// a float to a extended representation with a binary float. This +/// algorithm will accurately parse the vast majority of cases, +/// and uses a 128-bit representation (with a fallback 192-bit +/// representation). +/// +/// This algorithm scales the exponent by the decimal exponent +/// using pre-computed powers-of-5, and calculates if the +/// representation can be unambiguously rounded to the nearest +/// machine float. Near-halfway cases are not handled here, +/// and are represented by a negative, biased binary exponent. +/// +/// The algorithm is described in detail in "Daniel Lemire, Number Parsing +/// at a Gigabyte per Second" in section 5, "Fast Algorithm", and +/// section 6, "Exact Numbers And Ties", available online: +/// <https://arxiv.org/abs/2101.11408.pdf>. +pub fn compute_float<F: RawFloat>(q: i64, mut w: u64) -> BiasedFp { + let fp_zero = BiasedFp::zero_pow2(0); + let fp_inf = BiasedFp::zero_pow2(F::INFINITE_POWER); + let fp_error = BiasedFp::zero_pow2(-1); + + // Short-circuit if the value can only be a literal 0 or infinity. + if w == 0 || q < F::SMALLEST_POWER_OF_TEN as i64 { + return fp_zero; + } else if q > F::LARGEST_POWER_OF_TEN as i64 { + return fp_inf; + } + // Normalize our significant digits, so the most-significant bit is set. + let lz = w.leading_zeros(); + w <<= lz; + let (lo, hi) = compute_product_approx(q, w, F::MANTISSA_EXPLICIT_BITS + 3); + if lo == 0xFFFF_FFFF_FFFF_FFFF { + // If we have failed to approximate w x 5^-q with our 128-bit value. + // Since the addition of 1 could lead to an overflow which could then + // round up over the half-way point, this can lead to improper rounding + // of a float. + // + // However, this can only occur if q ∈ [-27, 55]. The upper bound of q + // is 55 because 5^55 < 2^128, however, this can only happen if 5^q > 2^64, + // since otherwise the product can be represented in 64-bits, producing + // an exact result. For negative exponents, rounding-to-even can + // only occur if 5^-q < 2^64. + // + // For detailed explanations of rounding for negative exponents, see + // <https://arxiv.org/pdf/2101.11408.pdf#section.9.1>. For detailed + // explanations of rounding for positive exponents, see + // <https://arxiv.org/pdf/2101.11408.pdf#section.8>. + let inside_safe_exponent = (q >= -27) && (q <= 55); + if !inside_safe_exponent { + return fp_error; + } + } + let upperbit = (hi >> 63) as i32; + let mut mantissa = hi >> (upperbit + 64 - F::MANTISSA_EXPLICIT_BITS as i32 - 3); + let mut power2 = power(q as i32) + upperbit - lz as i32 - F::MINIMUM_EXPONENT; + if power2 <= 0 { + if -power2 + 1 >= 64 { + // Have more than 64 bits below the minimum exponent, must be 0. + return fp_zero; + } + // Have a subnormal value. + mantissa >>= -power2 + 1; + mantissa += mantissa & 1; + mantissa >>= 1; + power2 = (mantissa >= (1_u64 << F::MANTISSA_EXPLICIT_BITS)) as i32; + return BiasedFp { f: mantissa, e: power2 }; + } + // Need to handle rounding ties. Normally, we need to round up, + // but if we fall right in between and and we have an even basis, we + // need to round down. + // + // This will only occur if: + // 1. The lower 64 bits of the 128-bit representation is 0. + // IE, 5^q fits in single 64-bit word. + // 2. The least-significant bit prior to truncated mantissa is odd. + // 3. All the bits truncated when shifting to mantissa bits + 1 are 0. + // + // Or, we may fall between two floats: we are exactly halfway. + if lo <= 1 + && q >= F::MIN_EXPONENT_ROUND_TO_EVEN as i64 + && q <= F::MAX_EXPONENT_ROUND_TO_EVEN as i64 + && mantissa & 3 == 1 + && (mantissa << (upperbit + 64 - F::MANTISSA_EXPLICIT_BITS as i32 - 3)) == hi + { + // Zero the lowest bit, so we don't round up. + mantissa &= !1_u64; + } + // Round-to-even, then shift the significant digits into place. + mantissa += mantissa & 1; + mantissa >>= 1; + if mantissa >= (2_u64 << F::MANTISSA_EXPLICIT_BITS) { + // Rounding up overflowed, so the carry bit is set. Set the + // mantissa to 1 (only the implicit, hidden bit is set) and + // increase the exponent. + mantissa = 1_u64 << F::MANTISSA_EXPLICIT_BITS; + power2 += 1; + } + // Zero out the hidden bit. + mantissa &= !(1_u64 << F::MANTISSA_EXPLICIT_BITS); + if power2 >= F::INFINITE_POWER { + // Exponent is above largest normal value, must be infinite. + return fp_inf; + } + BiasedFp { f: mantissa, e: power2 } +} + +/// Calculate a base 2 exponent from a decimal exponent. +/// This uses a pre-computed integer approximation for +/// log2(10), where 217706 / 2^16 is accurate for the +/// entire range of non-finite decimal exponents. +fn power(q: i32) -> i32 { + (q.wrapping_mul(152_170 + 65536) >> 16) + 63 +} + +fn full_multiplication(a: u64, b: u64) -> (u64, u64) { + let r = (a as u128) * (b as u128); + (r as u64, (r >> 64) as u64) +} + +// This will compute or rather approximate w * 5**q and return a pair of 64-bit words +// approximating the result, with the "high" part corresponding to the most significant +// bits and the low part corresponding to the least significant bits. +fn compute_product_approx(q: i64, w: u64, precision: usize) -> (u64, u64) { + debug_assert!(q >= SMALLEST_POWER_OF_FIVE as i64); + debug_assert!(q <= LARGEST_POWER_OF_FIVE as i64); + debug_assert!(precision <= 64); + + let mask = if precision < 64 { + 0xFFFF_FFFF_FFFF_FFFF_u64 >> precision + } else { + 0xFFFF_FFFF_FFFF_FFFF_u64 + }; + + // 5^q < 2^64, then the multiplication always provides an exact value. + // That means whenever we need to round ties to even, we always have + // an exact value. + let index = (q - SMALLEST_POWER_OF_FIVE as i64) as usize; + let (lo5, hi5) = POWER_OF_FIVE_128[index]; + // Only need one multiplication as long as there is 1 zero but + // in the explicit mantissa bits, +1 for the hidden bit, +1 to + // determine the rounding direction, +1 for if the computed + // product has a leading zero. + let (mut first_lo, mut first_hi) = full_multiplication(w, lo5); + if first_hi & mask == mask { + // Need to do a second multiplication to get better precision + // for the lower product. This will always be exact + // where q is < 55, since 5^55 < 2^128. If this wraps, + // then we need to need to round up the hi product. + let (_, second_hi) = full_multiplication(w, hi5); + first_lo = first_lo.wrapping_add(second_hi); + if second_hi > first_lo { + first_hi += 1; + } + } + (first_lo, first_hi) +} diff --git a/library/core/src/num/dec2flt/mod.rs b/library/core/src/num/dec2flt/mod.rs index 6b4215c20ad..c78492f5ae2 100644 --- a/library/core/src/num/dec2flt/mod.rs +++ b/library/core/src/num/dec2flt/mod.rs @@ -27,20 +27,12 @@ //! //! We then try a long chain of progressively more general and expensive special cases using //! machine-sized integers and small, fixed-sized floating point numbers (first `f32`/`f64`, then -//! a type with 64 bit significand, `Fp`). When all these fail, we bite the bullet and resort to a -//! simple but very slow algorithm that involved computing `f * 10^e` fully and doing an iterative -//! search for the best approximation. -//! -//! Primarily, this module and its children implement the algorithms described in: -//! "How to Read Floating Point Numbers Accurately" by William D. Clinger, -//! available online: <https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.4152> -//! -//! In addition, there are numerous helper functions that are used in the paper but not available -//! in Rust (or at least in core). Our version is additionally complicated by the need to handle -//! overflow and underflow and the desire to handle subnormal numbers. Bellerophon and -//! Algorithm R have trouble with overflow, subnormals, and underflow. We conservatively switch to -//! Algorithm M (with the modifications described in section 8 of the paper) well before the -//! inputs get into the critical region. +//! a type with 64 bit significand). The extended-precision algorithm +//! uses the Eisel-Lemire algorithm, which uses a 128-bit (or 192-bit) +//! representation that can accurately and quickly compute the vast majority +//! of floats. When all these fail, we bite the bullet and resort to using +//! a large-decimal representation, shifting the digits into range, calculating +//! the upper significant bits and exactly round to the nearest representation. //! //! Another aspect that needs attention is the ``RawFloat`` trait by which almost all functions //! are parametrized. One might think that it's enough to parse to `f64` and cast the result to @@ -54,10 +46,9 @@ //! operations as well, if you want 0.5 ULP accuracy you need to do *everything* in full precision //! and round *exactly once, at the end*, by considering all truncated bits at once. //! -//! FIXME: Although some code duplication is necessary, perhaps parts of the code could be shuffled -//! around such that less code is duplicated. Large parts of the algorithms are independent of the -//! float type to output, or only needs access to a few constants, which could be passed in as -//! parameters. +//! Primarily, this module and its children implement the algorithms described in: +//! "Number Parsing at a Gigabyte per Second", available online: +//! <https://arxiv.org/abs/2101.11408>. //! //! # Other //! @@ -87,16 +78,22 @@ use crate::fmt; use crate::str::FromStr; -use self::num::digits_to_big; -use self::parse::{parse_decimal, Decimal, ParseResult, Sign}; -use self::rawfp::RawFloat; +use self::common::{BiasedFp, ByteSlice}; +use self::float::RawFloat; +use self::lemire::compute_float; +use self::parse::{parse_inf_nan, parse_number}; +use self::slow::parse_long_mantissa; -mod algorithm; -mod num; +mod common; +mod decimal; +mod fpu; +mod slow; mod table; -// These two have their own tests. +// float is used in flt2dec, and all are used in unit tests. +pub mod float; +pub mod lemire; +pub mod number; pub mod parse; -pub mod rawfp; macro_rules! from_str_float_impl { ($t:ty) => { @@ -136,13 +133,6 @@ macro_rules! from_str_float_impl { /// /// [EBNF]: https://www.w3.org/TR/REC-xml/#sec-notation /// - /// # Known bugs - /// - /// In some situations, some strings that should create a valid float - /// instead return an error. See [issue #31407] for details. - /// - /// [issue #31407]: https://github.com/rust-lang/rust/issues/31407 - /// /// # Arguments /// /// * src - A string @@ -211,148 +201,70 @@ impl fmt::Display for ParseFloatError { } } -fn pfe_empty() -> ParseFloatError { +pub(super) fn pfe_empty() -> ParseFloatError { ParseFloatError { kind: FloatErrorKind::Empty } } -fn pfe_invalid() -> ParseFloatError { +// Used in unit tests, keep public. +// This is much better than making FloatErrorKind and ParseFloatError::kind public. +pub fn pfe_invalid() -> ParseFloatError { ParseFloatError { kind: FloatErrorKind::Invalid } } -/// Splits a decimal string into sign and the rest, without inspecting or validating the rest. -fn extract_sign(s: &str) -> (Sign, &str) { - match s.as_bytes()[0] { - b'+' => (Sign::Positive, &s[1..]), - b'-' => (Sign::Negative, &s[1..]), - // If the string is invalid, we never use the sign, so we don't need to validate here. - _ => (Sign::Positive, s), - } +/// Converts a `BiasedFp` to the closest machine float type. +fn biased_fp_to_float<T: RawFloat>(x: BiasedFp) -> T { + let mut word = x.f; + word |= (x.e as u64) << T::MANTISSA_EXPLICIT_BITS; + T::from_u64_bits(word) } /// Converts a decimal string into a floating point number. -fn dec2flt<T: RawFloat>(s: &str) -> Result<T, ParseFloatError> { - if s.is_empty() { +pub fn dec2flt<F: RawFloat>(s: &str) -> Result<F, ParseFloatError> { + let mut s = s.as_bytes(); + let c = if let Some(&c) = s.first() { + c + } else { return Err(pfe_empty()); + }; + let negative = c == b'-'; + if c == b'-' || c == b'+' { + s = s.advance(1); + } + if s.is_empty() { + return Err(pfe_invalid()); } - let (sign, s) = extract_sign(s); - let flt = match parse_decimal(s) { - ParseResult::Valid(decimal) => convert(decimal)?, - ParseResult::ShortcutToInf => T::INFINITY, - ParseResult::ShortcutToZero => T::ZERO, - ParseResult::Invalid => { - if s.eq_ignore_ascii_case("nan") { - T::NAN - } else if s.eq_ignore_ascii_case("inf") || s.eq_ignore_ascii_case("infinity") { - T::INFINITY + + let num = match parse_number(s, negative) { + Some(r) => r, + None => { + if let Some(value) = parse_inf_nan(s, negative) { + return Ok(value); } else { return Err(pfe_invalid()); } } }; - - match sign { - Sign::Positive => Ok(flt), - Sign::Negative => Ok(-flt), + if let Some(value) = num.try_fast_path::<F>() { + return Ok(value); } -} - -/// The main workhorse for the decimal-to-float conversion: Orchestrate all the preprocessing -/// and figure out which algorithm should do the actual conversion. -fn convert<T: RawFloat>(mut decimal: Decimal<'_>) -> Result<T, ParseFloatError> { - simplify(&mut decimal); - if let Some(x) = trivial_cases(&decimal) { - return Ok(x); - } - // Remove/shift out the decimal point. - let e = decimal.exp - decimal.fractional.len() as i64; - if let Some(x) = algorithm::fast_path(decimal.integral, decimal.fractional, e) { - return Ok(x); - } - // Big32x40 is limited to 1280 bits, which translates to about 385 decimal digits. - // If we exceed this, we'll crash, so we error out before getting too close (within 10^10). - let upper_bound = bound_intermediate_digits(&decimal, e); - if upper_bound > 375 { - return Err(pfe_invalid()); - } - let f = digits_to_big(decimal.integral, decimal.fractional); - - // Now the exponent certainly fits in 16 bit, which is used throughout the main algorithms. - let e = e as i16; - // FIXME These bounds are rather conservative. A more careful analysis of the failure modes - // of Bellerophon could allow using it in more cases for a massive speed up. - let exponent_in_range = table::MIN_E <= e && e <= table::MAX_E; - let value_in_range = upper_bound <= T::MAX_NORMAL_DIGITS as u64; - if exponent_in_range && value_in_range { - Ok(algorithm::bellerophon(&f, e)) - } else { - Ok(algorithm::algorithm_m(&f, e)) - } -} -// As written, this optimizes badly (see #27130, though it refers to an old version of the code). -// `inline(always)` is a workaround for that. There are only two call sites overall and it doesn't -// make code size worse. - -/// Strip zeros where possible, even when this requires changing the exponent -#[inline(always)] -fn simplify(decimal: &mut Decimal<'_>) { - let is_zero = &|&&d: &&u8| -> bool { d == b'0' }; - // Trimming these zeros does not change anything but may enable the fast path (< 15 digits). - let leading_zeros = decimal.integral.iter().take_while(is_zero).count(); - decimal.integral = &decimal.integral[leading_zeros..]; - let trailing_zeros = decimal.fractional.iter().rev().take_while(is_zero).count(); - let end = decimal.fractional.len() - trailing_zeros; - decimal.fractional = &decimal.fractional[..end]; - // Simplify numbers of the form 0.0...x and x...0.0, adjusting the exponent accordingly. - // This may not always be a win (possibly pushes some numbers out of the fast path), but it - // simplifies other parts significantly (notably, approximating the magnitude of the value). - if decimal.integral.is_empty() { - let leading_zeros = decimal.fractional.iter().take_while(is_zero).count(); - decimal.fractional = &decimal.fractional[leading_zeros..]; - decimal.exp -= leading_zeros as i64; - } else if decimal.fractional.is_empty() { - let trailing_zeros = decimal.integral.iter().rev().take_while(is_zero).count(); - let end = decimal.integral.len() - trailing_zeros; - decimal.integral = &decimal.integral[..end]; - decimal.exp += trailing_zeros as i64; + // If significant digits were truncated, then we can have rounding error + // only if `mantissa + 1` produces a different result. We also avoid + // redundantly using the Eisel-Lemire algorithm if it was unable to + // correctly round on the first pass. + let mut fp = compute_float::<F>(num.exponent, num.mantissa); + if num.many_digits && fp.e >= 0 && fp != compute_float::<F>(num.exponent, num.mantissa + 1) { + fp.e = -1; } -} - -/// Returns a quick-an-dirty upper bound on the size (log10) of the largest value that Algorithm R -/// and Algorithm M will compute while working on the given decimal. -fn bound_intermediate_digits(decimal: &Decimal<'_>, e: i64) -> u64 { - // We don't need to worry too much about overflow here thanks to trivial_cases() and the - // parser, which filter out the most extreme inputs for us. - let f_len: u64 = decimal.integral.len() as u64 + decimal.fractional.len() as u64; - if e >= 0 { - // In the case e >= 0, both algorithms compute about `f * 10^e`. Algorithm R proceeds to - // do some complicated calculations with this but we can ignore that for the upper bound - // because it also reduces the fraction beforehand, so we have plenty of buffer there. - f_len + (e as u64) - } else { - // If e < 0, Algorithm R does roughly the same thing, but Algorithm M differs: - // It tries to find a positive number k such that `f << k / 10^e` is an in-range - // significand. This will result in about `2^53 * f * 10^e` < `10^17 * f * 10^e`. - // One input that triggers this is 0.33...33 (375 x 3). - f_len + e.unsigned_abs() + 17 + // Unable to correctly round the float using the Eisel-Lemire algorithm. + // Fallback to a slower, but always correct algorithm. + if fp.e < 0 { + fp = parse_long_mantissa::<F>(s); } -} -/// Detects obvious overflows and underflows without even looking at the decimal digits. -fn trivial_cases<T: RawFloat>(decimal: &Decimal<'_>) -> Option<T> { - // There were zeros but they were stripped by simplify() - if decimal.integral.is_empty() && decimal.fractional.is_empty() { - return Some(T::ZERO); - } - // This is a crude approximation of ceil(log10(the real value)). We don't need to worry too - // much about overflow here because the input length is tiny (at least compared to 2^64) and - // the parser already handles exponents whose absolute value is greater than 10^18 - // (which is still 10^19 short of 2^64). - let max_place = decimal.exp + decimal.integral.len() as i64; - if max_place > T::INF_CUTOFF { - return Some(T::INFINITY); - } else if max_place < T::ZERO_CUTOFF { - return Some(T::ZERO); + let mut float = biased_fp_to_float::<F>(fp); + if num.negative { + float = -float; } - None + Ok(float) } diff --git a/library/core/src/num/dec2flt/num.rs b/library/core/src/num/dec2flt/num.rs deleted file mode 100644 index 208783dd32f..00000000000 --- a/library/core/src/num/dec2flt/num.rs +++ /dev/null @@ -1,81 +0,0 @@ -//! Utility functions for bignums that don't make too much sense to turn into methods. - -// FIXME This module's name is a bit unfortunate, since other modules also import `core::num`. - -use crate::cmp::Ordering::{self, Equal, Greater, Less}; - -pub use crate::num::bignum::Big32x40 as Big; - -/// Test whether truncating all bits less significant than `ones_place` introduces -/// a relative error less, equal, or greater than 0.5 ULP. -pub fn compare_with_half_ulp(f: &Big, ones_place: usize) -> Ordering { - if ones_place == 0 { - return Less; - } - let half_bit = ones_place - 1; - if f.get_bit(half_bit) == 0 { - // < 0.5 ULP - return Less; - } - // If all remaining bits are zero, it's = 0.5 ULP, otherwise > 0.5 - // If there are no more bits (half_bit == 0), the below also correctly returns Equal. - for i in 0..half_bit { - if f.get_bit(i) == 1 { - return Greater; - } - } - Equal -} - -/// Converts an ASCII string containing only decimal digits to a `u64`. -/// -/// Does not perform checks for overflow or invalid characters, so if the caller is not careful, -/// the result is bogus and can panic (though it won't be `unsafe`). Additionally, empty strings -/// are treated as zero. This function exists because -/// -/// 1. using `FromStr` on `&[u8]` requires `from_utf8_unchecked`, which is bad, and -/// 2. piecing together the results of `integral.parse()` and `fractional.parse()` is -/// more complicated than this entire function. -pub fn from_str_unchecked<'a, T>(bytes: T) -> u64 -where - T: IntoIterator<Item = &'a u8>, -{ - let mut result = 0; - for &c in bytes { - result = result * 10 + (c - b'0') as u64; - } - result -} - -/// Converts a string of ASCII digits into a bignum. -/// -/// Like `from_str_unchecked`, this function relies on the parser to weed out non-digits. -pub fn digits_to_big(integral: &[u8], fractional: &[u8]) -> Big { - let mut f = Big::from_small(0); - for &c in integral.iter().chain(fractional) { - let n = (c - b'0') as u32; - f.mul_small(10); - f.add_small(n); - } - f -} - -/// Unwraps a bignum into a 64 bit integer. Panics if the number is too large. -pub fn to_u64(x: &Big) -> u64 { - assert!(x.bit_length() < 64); - let d = x.digits(); - if d.len() < 2 { d[0] as u64 } else { (d[1] as u64) << 32 | d[0] as u64 } -} - -/// Extracts a range of bits. - -/// Index 0 is the least significant bit and the range is half-open as usual. -/// Panics if asked to extract more bits than fit into the return type. -pub fn get_bits(x: &Big, start: usize, end: usize) -> u64 { - assert!(end - start <= 64); - let mut result: u64 = 0; - for i in (start..end).rev() { - result = result << 1 | x.get_bit(i) as u64; - } - result -} diff --git a/library/core/src/num/dec2flt/number.rs b/library/core/src/num/dec2flt/number.rs new file mode 100644 index 00000000000..36432718af4 --- /dev/null +++ b/library/core/src/num/dec2flt/number.rs @@ -0,0 +1,86 @@ +//! Representation of a float as the significant digits and exponent. + +use crate::num::dec2flt::float::RawFloat; +use crate::num::dec2flt::fpu::set_precision; + +#[rustfmt::skip] +const INT_POW10: [u64; 16] = [ + 1, + 10, + 100, + 1000, + 10000, + 100000, + 1000000, + 10000000, + 100000000, + 1000000000, + 10000000000, + 100000000000, + 1000000000000, + 10000000000000, + 100000000000000, + 1000000000000000, +]; + +#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)] +pub struct Number { + pub exponent: i64, + pub mantissa: u64, + pub negative: bool, + pub many_digits: bool, +} + +impl Number { + /// Detect if the float can be accurately reconstructed from native floats. + fn is_fast_path<F: RawFloat>(&self) -> bool { + F::MIN_EXPONENT_FAST_PATH <= self.exponent + && self.exponent <= F::MAX_EXPONENT_DISGUISED_FAST_PATH + && self.mantissa <= F::MAX_MANTISSA_FAST_PATH + && !self.many_digits + } + + /// The fast path algorithmn using machine-sized integers and floats. + /// + /// This is extracted into a separate function so that it can be attempted before constructing + /// a Decimal. This only works if both the mantissa and the exponent + /// can be exactly represented as a machine float, since IEE-754 guarantees + /// no rounding will occur. + /// + /// There is an exception: disguised fast-path cases, where we can shift + /// powers-of-10 from the exponent to the significant digits. + pub fn try_fast_path<F: RawFloat>(&self) -> Option<F> { + // The fast path crucially depends on arithmetic being rounded to the correct number of bits + // without any intermediate rounding. On x86 (without SSE or SSE2) this requires the precision + // of the x87 FPU stack to be changed so that it directly rounds to 64/32 bit. + // The `set_precision` function takes care of setting the precision on architectures which + // require setting it by changing the global state (like the control word of the x87 FPU). + let _cw = set_precision::<F>(); + + if self.is_fast_path::<F>() { + let mut value = if self.exponent <= F::MAX_EXPONENT_FAST_PATH { + // normal fast path + let value = F::from_u64(self.mantissa); + if self.exponent < 0 { + value / F::pow10_fast_path((-self.exponent) as _) + } else { + value * F::pow10_fast_path(self.exponent as _) + } + } else { + // disguised fast path + let shift = self.exponent - F::MAX_EXPONENT_FAST_PATH; + let mantissa = self.mantissa.checked_mul(INT_POW10[shift as usize])?; + if mantissa > F::MAX_MANTISSA_FAST_PATH { + return None; + } + F::from_u64(mantissa) * F::pow10_fast_path(F::MAX_EXPONENT_FAST_PATH as _) + }; + if self.negative { + value = -value; + } + Some(value) + } else { + None + } + } +} diff --git a/library/core/src/num/dec2flt/parse.rs b/library/core/src/num/dec2flt/parse.rs index 858cc3c9b01..fa677bf5123 100644 --- a/library/core/src/num/dec2flt/parse.rs +++ b/library/core/src/num/dec2flt/parse.rs @@ -1,121 +1,233 @@ -//! Validating and decomposing a decimal string of the form: -//! -//! `(digits | digits? '.'? digits?) (('e' | 'E') ('+' | '-')? digits)?` -//! -//! In other words, standard floating-point syntax, with two exceptions: No sign, and no -//! handling of "inf" and "NaN". These are handled by the driver function (super::dec2flt). -//! -//! Although recognizing valid inputs is relatively easy, this module also has to reject the -//! countless invalid variations, never panic, and perform numerous checks that the other -//! modules rely on to not panic (or overflow) in turn. -//! To make matters worse, all that happens in a single pass over the input. -//! So, be careful when modifying anything, and double-check with the other modules. -use self::ParseResult::{Invalid, ShortcutToInf, ShortcutToZero, Valid}; -use super::num; - -#[derive(Debug)] -pub enum Sign { - Positive, - Negative, +//! Functions to parse floating-point numbers. + +use crate::num::dec2flt::common::{is_8digits, AsciiStr, ByteSlice}; +use crate::num::dec2flt::float::RawFloat; +use crate::num::dec2flt::number::Number; + +const MIN_19DIGIT_INT: u64 = 100_0000_0000_0000_0000; + +/// Parse 8 digits, loaded as bytes in little-endian order. +/// +/// This uses the trick where every digit is in [0x030, 0x39], +/// and therefore can be parsed in 3 multiplications, much +/// faster than the normal 8. +/// +/// This is based off the algorithm described in "Fast numeric string to +/// int", available here: <https://johnnylee-sde.github.io/Fast-numeric-string-to-int/>. +fn parse_8digits(mut v: u64) -> u64 { + const MASK: u64 = 0x0000_00FF_0000_00FF; + const MUL1: u64 = 0x000F_4240_0000_0064; + const MUL2: u64 = 0x0000_2710_0000_0001; + v -= 0x3030_3030_3030_3030; + v = (v * 10) + (v >> 8); // will not overflow, fits in 63 bits + let v1 = (v & MASK).wrapping_mul(MUL1); + let v2 = ((v >> 16) & MASK).wrapping_mul(MUL2); + ((v1.wrapping_add(v2) >> 32) as u32) as u64 } -#[derive(Debug, PartialEq, Eq)] -/// The interesting parts of a decimal string. -pub struct Decimal<'a> { - pub integral: &'a [u8], - pub fractional: &'a [u8], - /// The decimal exponent, guaranteed to have fewer than 18 decimal digits. - pub exp: i64, +/// Parse digits until a non-digit character is found. +fn try_parse_digits(s: &mut AsciiStr<'_>, x: &mut u64) { + // may cause overflows, to be handled later + s.parse_digits(|digit| { + *x = x.wrapping_mul(10).wrapping_add(digit as _); + }); } -impl<'a> Decimal<'a> { - pub fn new(integral: &'a [u8], fractional: &'a [u8], exp: i64) -> Decimal<'a> { - Decimal { integral, fractional, exp } +/// Parse up to 19 digits (the max that can be stored in a 64-bit integer). +fn try_parse_19digits(s: &mut AsciiStr<'_>, x: &mut u64) { + while *x < MIN_19DIGIT_INT { + if let Some(&c) = s.as_ref().first() { + let digit = c.wrapping_sub(b'0'); + if digit < 10 { + *x = (*x * 10) + digit as u64; // no overflows here + // SAFETY: cannot be empty + unsafe { + s.step(); + } + } else { + break; + } + } else { + break; + } } } -#[derive(Debug, PartialEq, Eq)] -pub enum ParseResult<'a> { - Valid(Decimal<'a>), - ShortcutToInf, - ShortcutToZero, - Invalid, +/// Try to parse 8 digits at a time, using an optimized algorithm. +fn try_parse_8digits(s: &mut AsciiStr<'_>, x: &mut u64) { + // may cause overflows, to be handled later + if let Some(v) = s.read_u64() { + if is_8digits(v) { + *x = x.wrapping_mul(1_0000_0000).wrapping_add(parse_8digits(v)); + // SAFETY: already ensured the buffer was >= 8 bytes in read_u64. + unsafe { + s.step_by(8); + } + if let Some(v) = s.read_u64() { + if is_8digits(v) { + *x = x.wrapping_mul(1_0000_0000).wrapping_add(parse_8digits(v)); + // SAFETY: already ensured the buffer was >= 8 bytes in try_read_u64. + unsafe { + s.step_by(8); + } + } + } + } + } } -/// Checks if the input string is a valid floating point number and if so, locate the integral -/// part, the fractional part, and the exponent in it. Does not handle signs. -pub fn parse_decimal(s: &str) -> ParseResult<'_> { - if s.is_empty() { - return Invalid; +/// Parse the scientific notation component of a float. +fn parse_scientific(s: &mut AsciiStr<'_>) -> Option<i64> { + let mut exponent = 0_i64; + let mut negative = false; + if let Some(&c) = s.as_ref().get(0) { + negative = c == b'-'; + if c == b'-' || c == b'+' { + // SAFETY: s cannot be empty + unsafe { + s.step(); + } + } } + if s.first_isdigit() { + s.parse_digits(|digit| { + // no overflows here, saturate well before overflow + if exponent < 0x10000 { + exponent = 10 * exponent + digit as i64; + } + }); + if negative { Some(-exponent) } else { Some(exponent) } + } else { + None + } +} - let s = s.as_bytes(); - let (integral, s) = eat_digits(s); +/// Parse a partial, non-special floating point number. +/// +/// This creates a representation of the float as the +/// significant digits and the decimal exponent. +fn parse_partial_number(s: &[u8], negative: bool) -> Option<(Number, usize)> { + let mut s = AsciiStr::new(s); + let start = s; + debug_assert!(!s.is_empty()); - match s.first() { - None => Valid(Decimal::new(integral, b"", 0)), - Some(&b'e' | &b'E') => { - if integral.is_empty() { - return Invalid; // No digits before 'e' - } + // parse initial digits before dot + let mut mantissa = 0_u64; + let digits_start = s; + try_parse_digits(&mut s, &mut mantissa); + let mut n_digits = s.offset_from(&digits_start); + + // handle dot with the following digits + let mut n_after_dot = 0; + let mut exponent = 0_i64; + let int_end = s; + if s.first_is(b'.') { + // SAFETY: s cannot be empty due to first_is + unsafe { s.step() }; + let before = s; + try_parse_8digits(&mut s, &mut mantissa); + try_parse_digits(&mut s, &mut mantissa); + n_after_dot = s.offset_from(&before); + exponent = -n_after_dot as i64; + } - parse_exp(integral, b"", &s[1..]) + n_digits += n_after_dot; + if n_digits == 0 { + return None; + } + + // handle scientific format + let mut exp_number = 0_i64; + if s.first_is2(b'e', b'E') { + // SAFETY: s cannot be empty + unsafe { + s.step(); } - Some(&b'.') => { - let (fractional, s) = eat_digits(&s[1..]); - if integral.is_empty() && fractional.is_empty() { - // We require at least a single digit before or after the point. - return Invalid; - } + // If None, we have no trailing digits after exponent, or an invalid float. + exp_number = parse_scientific(&mut s)?; + exponent += exp_number; + } - match s.first() { - None => Valid(Decimal::new(integral, fractional, 0)), - Some(&b'e' | &b'E') => parse_exp(integral, fractional, &s[1..]), - _ => Invalid, // Trailing junk after fractional part - } + let len = s.offset_from(&start) as _; + + // handle uncommon case with many digits + if n_digits <= 19 { + return Some((Number { exponent, mantissa, negative, many_digits: false }, len)); + } + + n_digits -= 19; + let mut many_digits = false; + let mut p = digits_start; + while p.first_is2(b'0', b'.') { + // SAFETY: p cannot be empty due to first_is2 + unsafe { + // '0' = b'.' + 2 + n_digits -= p.first_unchecked().saturating_sub(b'0' - 1) as isize; + p.step(); } - _ => Invalid, // Trailing junk after first digit string } -} + if n_digits > 0 { + // at this point we have more than 19 significant digits, let's try again + many_digits = true; + mantissa = 0; + let mut s = digits_start; + try_parse_19digits(&mut s, &mut mantissa); + exponent = if mantissa >= MIN_19DIGIT_INT { + // big int + int_end.offset_from(&s) + } else { + // SAFETY: the next byte must be present and be '.' + // We know this is true because we had more than 19 + // digits previously, so we overflowed a 64-bit integer, + // but parsing only the integral digits produced less + // than 19 digits. That means we must have a decimal + // point, and at least 1 fractional digit. + unsafe { s.step() }; + let before = s; + try_parse_19digits(&mut s, &mut mantissa); + -s.offset_from(&before) + } as i64; + // add back the explicit part + exponent += exp_number; + } -/// Carves off decimal digits up to the first non-digit character. -fn eat_digits(s: &[u8]) -> (&[u8], &[u8]) { - let pos = s.iter().position(|c| !c.is_ascii_digit()).unwrap_or(s.len()); - s.split_at(pos) + Some((Number { exponent, mantissa, negative, many_digits }, len)) } -/// Exponent extraction and error checking. -fn parse_exp<'a>(integral: &'a [u8], fractional: &'a [u8], rest: &'a [u8]) -> ParseResult<'a> { - let (sign, rest) = match rest.first() { - Some(&b'-') => (Sign::Negative, &rest[1..]), - Some(&b'+') => (Sign::Positive, &rest[1..]), - _ => (Sign::Positive, rest), - }; - let (mut number, trailing) = eat_digits(rest); - if !trailing.is_empty() { - return Invalid; // Trailing junk after exponent +/// Try to parse a non-special floating point number. +pub fn parse_number(s: &[u8], negative: bool) -> Option<Number> { + if let Some((float, rest)) = parse_partial_number(s, negative) { + if rest == s.len() { + return Some(float); + } } - if number.is_empty() { - return Invalid; // Empty exponent + None +} + +/// Parse a partial representation of a special, non-finite float. +fn parse_partial_inf_nan<F: RawFloat>(s: &[u8]) -> Option<(F, usize)> { + fn parse_inf_rest(s: &[u8]) -> usize { + if s.len() >= 8 && s[3..].as_ref().eq_ignore_case(b"inity") { 8 } else { 3 } } - // At this point, we certainly have a valid string of digits. It may be too long to put into - // an `i64`, but if it's that huge, the input is certainly zero or infinity. Since each zero - // in the decimal digits only adjusts the exponent by +/- 1, at exp = 10^18 the input would - // have to be 17 exabyte (!) of zeros to get even remotely close to being finite. - // This is not exactly a use case we need to cater to. - while number.first() == Some(&b'0') { - number = &number[1..]; + if s.len() >= 3 { + if s.eq_ignore_case(b"nan") { + return Some((F::NAN, 3)); + } else if s.eq_ignore_case(b"inf") { + return Some((F::INFINITY, parse_inf_rest(s))); + } } - if number.len() >= 18 { - return match sign { - Sign::Positive => ShortcutToInf, - Sign::Negative => ShortcutToZero, - }; + None +} + +/// Try to parse a special, non-finite float. +pub fn parse_inf_nan<F: RawFloat>(s: &[u8], negative: bool) -> Option<F> { + if let Some((mut float, rest)) = parse_partial_inf_nan::<F>(s) { + if rest == s.len() { + if negative { + float = -float; + } + return Some(float); + } } - let abs_exp = num::from_str_unchecked(number); - let e = match sign { - Sign::Positive => abs_exp as i64, - Sign::Negative => -(abs_exp as i64), - }; - Valid(Decimal::new(integral, fractional, e)) + None } diff --git a/library/core/src/num/dec2flt/rawfp.rs b/library/core/src/num/dec2flt/rawfp.rs deleted file mode 100644 index 0ab15b23e53..00000000000 --- a/library/core/src/num/dec2flt/rawfp.rs +++ /dev/null @@ -1,363 +0,0 @@ -//! Bit fiddling on positive IEEE 754 floats. Negative numbers aren't and needn't be handled. -//! Normal floating point numbers have a canonical representation as (frac, exp) such that the -//! value is 2<sup>exp</sup> * (1 + sum(frac[N-i] / 2<sup>i</sup>)) where N is the number of bits. -//! Subnormals are slightly different and weird, but the same principle applies. -//! -//! Here, however, we represent them as (sig, k) with f positive, such that the value is f * -//! 2<sup>e</sup>. Besides making the "hidden bit" explicit, this changes the exponent by the -//! so-called mantissa shift. -//! -//! Put another way, normally floats are written as (1) but here they are written as (2): -//! -//! 1. `1.101100...11 * 2^m` -//! 2. `1101100...11 * 2^n` -//! -//! We call (1) the **fractional representation** and (2) the **integral representation**. -//! -//! Many functions in this module only handle normal numbers. The dec2flt routines conservatively -//! take the universally-correct slow path (Algorithm M) for very small and very large numbers. -//! That algorithm needs only next_float() which does handle subnormals and zeros. -use crate::cmp::Ordering::{Equal, Greater, Less}; -use crate::convert::{TryFrom, TryInto}; -use crate::fmt::{Debug, LowerExp}; -use crate::num::dec2flt::num::{self, Big}; -use crate::num::dec2flt::table; -use crate::num::diy_float::Fp; -use crate::num::FpCategory; -use crate::num::FpCategory::{Infinite, Nan, Normal, Subnormal, Zero}; -use crate::ops::{Add, Div, Mul, Neg}; - -#[derive(Copy, Clone, Debug)] -pub struct Unpacked { - pub sig: u64, - pub k: i16, -} - -impl Unpacked { - pub fn new(sig: u64, k: i16) -> Self { - Unpacked { sig, k } - } -} - -/// A helper trait to avoid duplicating basically all the conversion code for `f32` and `f64`. -/// -/// See the parent module's doc comment for why this is necessary. -/// -/// Should **never ever** be implemented for other types or be used outside the dec2flt module. -pub trait RawFloat: - Copy + Debug + LowerExp + Mul<Output = Self> + Div<Output = Self> + Neg<Output = Self> -{ - const INFINITY: Self; - const NAN: Self; - const ZERO: Self; - - /// Type used by `to_bits` and `from_bits`. - type Bits: Add<Output = Self::Bits> + From<u8> + TryFrom<u64>; - - /// Performs a raw transmutation to an integer. - fn to_bits(self) -> Self::Bits; - - /// Performs a raw transmutation from an integer. - fn from_bits(v: Self::Bits) -> Self; - - /// Returns the category that this number falls into. - fn classify(self) -> FpCategory; - - /// Returns the mantissa, exponent and sign as integers. - fn integer_decode(self) -> (u64, i16, i8); - - /// Decodes the float. - fn unpack(self) -> Unpacked; - - /// Casts from a small integer that can be represented exactly. Panic if the integer can't be - /// represented, the other code in this module makes sure to never let that happen. - fn from_int(x: u64) -> Self; - - /// Gets the value 10<sup>e</sup> from a pre-computed table. - /// Panics for `e >= CEIL_LOG5_OF_MAX_SIG`. - fn short_fast_pow10(e: usize) -> Self; - - /// What the name says. It's easier to hard code than juggling intrinsics and - /// hoping LLVM constant folds it. - const CEIL_LOG5_OF_MAX_SIG: i16; - - // A conservative bound on the decimal digits of inputs that can't produce overflow or zero or - /// subnormals. Probably the decimal exponent of the maximum normal value, hence the name. - const MAX_NORMAL_DIGITS: usize; - - /// When the most significant decimal digit has a place value greater than this, the number - /// is certainly rounded to infinity. - const INF_CUTOFF: i64; - - /// When the most significant decimal digit has a place value less than this, the number - /// is certainly rounded to zero. - const ZERO_CUTOFF: i64; - - /// The number of bits in the exponent. - const EXP_BITS: u8; - - /// The number of bits in the significand, *including* the hidden bit. - const SIG_BITS: u8; - - /// The number of bits in the significand, *excluding* the hidden bit. - const EXPLICIT_SIG_BITS: u8; - - /// The maximum legal exponent in fractional representation. - const MAX_EXP: i16; - - /// The minimum legal exponent in fractional representation, excluding subnormals. - const MIN_EXP: i16; - - /// `MAX_EXP` for integral representation, i.e., with the shift applied. - const MAX_EXP_INT: i16; - - /// `MAX_EXP` encoded (i.e., with offset bias) - const MAX_ENCODED_EXP: i16; - - /// `MIN_EXP` for integral representation, i.e., with the shift applied. - const MIN_EXP_INT: i16; - - /// The maximum normalized significand in integral representation. - const MAX_SIG: u64; - - /// The minimal normalized significand in integral representation. - const MIN_SIG: u64; -} - -// Mostly a workaround for #34344. -macro_rules! other_constants { - ($type: ident) => { - const EXPLICIT_SIG_BITS: u8 = Self::SIG_BITS - 1; - const MAX_EXP: i16 = (1 << (Self::EXP_BITS - 1)) - 1; - const MIN_EXP: i16 = -<Self as RawFloat>::MAX_EXP + 1; - const MAX_EXP_INT: i16 = <Self as RawFloat>::MAX_EXP - (Self::SIG_BITS as i16 - 1); - const MAX_ENCODED_EXP: i16 = (1 << Self::EXP_BITS) - 1; - const MIN_EXP_INT: i16 = <Self as RawFloat>::MIN_EXP - (Self::SIG_BITS as i16 - 1); - const MAX_SIG: u64 = (1 << Self::SIG_BITS) - 1; - const MIN_SIG: u64 = 1 << (Self::SIG_BITS - 1); - - const INFINITY: Self = $type::INFINITY; - const NAN: Self = $type::NAN; - const ZERO: Self = 0.0; - }; -} - -impl RawFloat for f32 { - type Bits = u32; - - const SIG_BITS: u8 = 24; - const EXP_BITS: u8 = 8; - const CEIL_LOG5_OF_MAX_SIG: i16 = 11; - const MAX_NORMAL_DIGITS: usize = 35; - const INF_CUTOFF: i64 = 40; - const ZERO_CUTOFF: i64 = -48; - other_constants!(f32); - - /// Returns the mantissa, exponent and sign as integers. - fn integer_decode(self) -> (u64, i16, i8) { - let bits = self.to_bits(); - let sign: i8 = if bits >> 31 == 0 { 1 } else { -1 }; - let mut exponent: i16 = ((bits >> 23) & 0xff) as i16; - let mantissa = - if exponent == 0 { (bits & 0x7fffff) << 1 } else { (bits & 0x7fffff) | 0x800000 }; - // Exponent bias + mantissa shift - exponent -= 127 + 23; - (mantissa as u64, exponent, sign) - } - - fn unpack(self) -> Unpacked { - let (sig, exp, _sig) = self.integer_decode(); - Unpacked::new(sig, exp) - } - - fn from_int(x: u64) -> f32 { - // rkruppe is uncertain whether `as` rounds correctly on all platforms. - debug_assert!(x as f32 == fp_to_float(Fp { f: x, e: 0 })); - x as f32 - } - - fn short_fast_pow10(e: usize) -> Self { - table::F32_SHORT_POWERS[e] - } - - fn classify(self) -> FpCategory { - self.classify() - } - fn to_bits(self) -> Self::Bits { - self.to_bits() - } - fn from_bits(v: Self::Bits) -> Self { - Self::from_bits(v) - } -} - -impl RawFloat for f64 { - type Bits = u64; - - const SIG_BITS: u8 = 53; - const EXP_BITS: u8 = 11; - const CEIL_LOG5_OF_MAX_SIG: i16 = 23; - const MAX_NORMAL_DIGITS: usize = 305; - const INF_CUTOFF: i64 = 310; - const ZERO_CUTOFF: i64 = -326; - other_constants!(f64); - - /// Returns the mantissa, exponent and sign as integers. - fn integer_decode(self) -> (u64, i16, i8) { - let bits = self.to_bits(); - let sign: i8 = if bits >> 63 == 0 { 1 } else { -1 }; - let mut exponent: i16 = ((bits >> 52) & 0x7ff) as i16; - let mantissa = if exponent == 0 { - (bits & 0xfffffffffffff) << 1 - } else { - (bits & 0xfffffffffffff) | 0x10000000000000 - }; - // Exponent bias + mantissa shift - exponent -= 1023 + 52; - (mantissa, exponent, sign) - } - - fn unpack(self) -> Unpacked { - let (sig, exp, _sig) = self.integer_decode(); - Unpacked::new(sig, exp) - } - - fn from_int(x: u64) -> f64 { - // rkruppe is uncertain whether `as` rounds correctly on all platforms. - debug_assert!(x as f64 == fp_to_float(Fp { f: x, e: 0 })); - x as f64 - } - - fn short_fast_pow10(e: usize) -> Self { - table::F64_SHORT_POWERS[e] - } - - fn classify(self) -> FpCategory { - self.classify() - } - fn to_bits(self) -> Self::Bits { - self.to_bits() - } - fn from_bits(v: Self::Bits) -> Self { - Self::from_bits(v) - } -} - -/// Converts an `Fp` to the closest machine float type. -/// Does not handle subnormal results. -pub fn fp_to_float<T: RawFloat>(x: Fp) -> T { - let x = x.normalize(); - // x.f is 64 bit, so x.e has a mantissa shift of 63 - let e = x.e + 63; - if e > T::MAX_EXP { - panic!("fp_to_float: exponent {} too large", e) - } else if e > T::MIN_EXP { - encode_normal(round_normal::<T>(x)) - } else { - panic!("fp_to_float: exponent {} too small", e) - } -} - -/// Round the 64-bit significand to T::SIG_BITS bits with half-to-even. -/// Does not handle exponent overflow. -pub fn round_normal<T: RawFloat>(x: Fp) -> Unpacked { - let excess = 64 - T::SIG_BITS as i16; - let half: u64 = 1 << (excess - 1); - let (q, rem) = (x.f >> excess, x.f & ((1 << excess) - 1)); - assert_eq!(q << excess | rem, x.f); - // Adjust mantissa shift - let k = x.e + excess; - if rem < half { - Unpacked::new(q, k) - } else if rem == half && (q % 2) == 0 { - Unpacked::new(q, k) - } else if q == T::MAX_SIG { - Unpacked::new(T::MIN_SIG, k + 1) - } else { - Unpacked::new(q + 1, k) - } -} - -/// Inverse of `RawFloat::unpack()` for normalized numbers. -/// Panics if the significand or exponent are not valid for normalized numbers. -pub fn encode_normal<T: RawFloat>(x: Unpacked) -> T { - debug_assert!( - T::MIN_SIG <= x.sig && x.sig <= T::MAX_SIG, - "encode_normal: significand not normalized" - ); - // Remove the hidden bit - let sig_enc = x.sig & !(1 << T::EXPLICIT_SIG_BITS); - // Adjust the exponent for exponent bias and mantissa shift - let k_enc = x.k + T::MAX_EXP + T::EXPLICIT_SIG_BITS as i16; - debug_assert!(k_enc != 0 && k_enc < T::MAX_ENCODED_EXP, "encode_normal: exponent out of range"); - // Leave sign bit at 0 ("+"), our numbers are all positive - let bits = (k_enc as u64) << T::EXPLICIT_SIG_BITS | sig_enc; - T::from_bits(bits.try_into().unwrap_or_else(|_| unreachable!())) -} - -/// Construct a subnormal. A mantissa of 0 is allowed and constructs zero. -pub fn encode_subnormal<T: RawFloat>(significand: u64) -> T { - assert!(significand < T::MIN_SIG, "encode_subnormal: not actually subnormal"); - // Encoded exponent is 0, the sign bit is 0, so we just have to reinterpret the bits. - T::from_bits(significand.try_into().unwrap_or_else(|_| unreachable!())) -} - -/// Approximate a bignum with an Fp. Rounds within 0.5 ULP with half-to-even. -pub fn big_to_fp(f: &Big) -> Fp { - let end = f.bit_length(); - assert!(end != 0, "big_to_fp: unexpectedly, input is zero"); - let start = end.saturating_sub(64); - let leading = num::get_bits(f, start, end); - // We cut off all bits prior to the index `start`, i.e., we effectively right-shift by - // an amount of `start`, so this is also the exponent we need. - let e = start as i16; - let rounded_down = Fp { f: leading, e }.normalize(); - // Round (half-to-even) depending on the truncated bits. - match num::compare_with_half_ulp(f, start) { - Less => rounded_down, - Equal if leading % 2 == 0 => rounded_down, - Equal | Greater => match leading.checked_add(1) { - Some(f) => Fp { f, e }.normalize(), - None => Fp { f: 1 << 63, e: e + 1 }, - }, - } -} - -/// Finds the largest floating point number strictly smaller than the argument. -/// Does not handle subnormals, zero, or exponent underflow. -pub fn prev_float<T: RawFloat>(x: T) -> T { - match x.classify() { - Infinite => panic!("prev_float: argument is infinite"), - Nan => panic!("prev_float: argument is NaN"), - Subnormal => panic!("prev_float: argument is subnormal"), - Zero => panic!("prev_float: argument is zero"), - Normal => { - let Unpacked { sig, k } = x.unpack(); - if sig == T::MIN_SIG { - encode_normal(Unpacked::new(T::MAX_SIG, k - 1)) - } else { - encode_normal(Unpacked::new(sig - 1, k)) - } - } - } -} - -// Find the smallest floating point number strictly larger than the argument. -// This operation is saturating, i.e., next_float(inf) == inf. -// Unlike most code in this module, this function does handle zero, subnormals, and infinities. -// However, like all other code here, it does not deal with NaN and negative numbers. -pub fn next_float<T: RawFloat>(x: T) -> T { - match x.classify() { - Nan => panic!("next_float: argument is NaN"), - Infinite => T::INFINITY, - // This seems too good to be true, but it works. - // 0.0 is encoded as the all-zero word. Subnormals are 0x000m...m where m is the mantissa. - // In particular, the smallest subnormal is 0x0...01 and the largest is 0x000F...F. - // The smallest normal number is 0x0010...0, so this corner case works as well. - // If the increment overflows the mantissa, the carry bit increments the exponent as we - // want, and the mantissa bits become zero. Because of the hidden bit convention, this - // too is exactly what we want! - // Finally, f64::MAX + 1 = 7eff...f + 1 = 7ff0...0 = f64::INFINITY. - Zero | Subnormal | Normal => T::from_bits(x.to_bits() + T::Bits::from(1u8)), - } -} diff --git a/library/core/src/num/dec2flt/slow.rs b/library/core/src/num/dec2flt/slow.rs new file mode 100644 index 00000000000..bf1044033e6 --- /dev/null +++ b/library/core/src/num/dec2flt/slow.rs @@ -0,0 +1,109 @@ +//! Slow, fallback algorithm for cases the Eisel-Lemire algorithm cannot round. + +use crate::num::dec2flt::common::BiasedFp; +use crate::num::dec2flt::decimal::{parse_decimal, Decimal}; +use crate::num::dec2flt::float::RawFloat; + +/// Parse the significant digits and biased, binary exponent of a float. +/// +/// This is a fallback algorithm that uses a big-integer representation +/// of the float, and therefore is considerably slower than faster +/// approximations. However, it will always determine how to round +/// the significant digits to the nearest machine float, allowing +/// use to handle near half-way cases. +/// +/// Near half-way cases are halfway between two consecutive machine floats. +/// For example, the float `16777217.0` has a bitwise representation of +/// `100000000000000000000000 1`. Rounding to a single-precision float, +/// the trailing `1` is truncated. Using round-nearest, tie-even, any +/// value above `16777217.0` must be rounded up to `16777218.0`, while +/// any value before or equal to `16777217.0` must be rounded down +/// to `16777216.0`. These near-halfway conversions therefore may require +/// a large number of digits to unambiguously determine how to round. +/// +/// The algorithms described here are based on "Processing Long Numbers Quickly", +/// available here: <https://arxiv.org/pdf/2101.11408.pdf#section.11>. +pub(crate) fn parse_long_mantissa<F: RawFloat>(s: &[u8]) -> BiasedFp { + const MAX_SHIFT: usize = 60; + const NUM_POWERS: usize = 19; + const POWERS: [u8; 19] = + [0, 3, 6, 9, 13, 16, 19, 23, 26, 29, 33, 36, 39, 43, 46, 49, 53, 56, 59]; + + let get_shift = |n| { + if n < NUM_POWERS { POWERS[n] as usize } else { MAX_SHIFT } + }; + + let fp_zero = BiasedFp::zero_pow2(0); + let fp_inf = BiasedFp::zero_pow2(F::INFINITE_POWER); + + let mut d = parse_decimal(s); + + // Short-circuit if the value can only be a literal 0 or infinity. + if d.num_digits == 0 || d.decimal_point < -324 { + return fp_zero; + } else if d.decimal_point >= 310 { + return fp_inf; + } + let mut exp2 = 0_i32; + // Shift right toward (1/2 ... 1]. + while d.decimal_point > 0 { + let n = d.decimal_point as usize; + let shift = get_shift(n); + d.right_shift(shift); + if d.decimal_point < -Decimal::DECIMAL_POINT_RANGE { + return fp_zero; + } + exp2 += shift as i32; + } + // Shift left toward (1/2 ... 1]. + while d.decimal_point <= 0 { + let shift = if d.decimal_point == 0 { + match d.digits[0] { + digit if digit >= 5 => break, + 0 | 1 => 2, + _ => 1, + } + } else { + get_shift((-d.decimal_point) as _) + }; + d.left_shift(shift); + if d.decimal_point > Decimal::DECIMAL_POINT_RANGE { + return fp_inf; + } + exp2 -= shift as i32; + } + // We are now in the range [1/2 ... 1] but the binary format uses [1 ... 2]. + exp2 -= 1; + while (F::MINIMUM_EXPONENT + 1) > exp2 { + let mut n = ((F::MINIMUM_EXPONENT + 1) - exp2) as usize; + if n > MAX_SHIFT { + n = MAX_SHIFT; + } + d.right_shift(n); + exp2 += n as i32; + } + if (exp2 - F::MINIMUM_EXPONENT) >= F::INFINITE_POWER { + return fp_inf; + } + // Shift the decimal to the hidden bit, and then round the value + // to get the high mantissa+1 bits. + d.left_shift(F::MANTISSA_EXPLICIT_BITS + 1); + let mut mantissa = d.round(); + if mantissa >= (1_u64 << (F::MANTISSA_EXPLICIT_BITS + 1)) { + // Rounding up overflowed to the carry bit, need to + // shift back to the hidden bit. + d.right_shift(1); + exp2 += 1; + mantissa = d.round(); + if (exp2 - F::MINIMUM_EXPONENT) >= F::INFINITE_POWER { + return fp_inf; + } + } + let mut power2 = exp2 - F::MINIMUM_EXPONENT; + if mantissa < (1_u64 << F::MANTISSA_EXPLICIT_BITS) { + power2 -= 1; + } + // Zero out all the bits above the explicit mantissa bits. + mantissa &= (1_u64 << F::MANTISSA_EXPLICIT_BITS) - 1; + BiasedFp { f: mantissa, e: power2 } +} diff --git a/library/core/src/num/dec2flt/table.rs b/library/core/src/num/dec2flt/table.rs index 97b497e81e0..4856074a62b 100644 --- a/library/core/src/num/dec2flt/table.rs +++ b/library/core/src/num/dec2flt/table.rs @@ -1,1277 +1,670 @@ -//! Tables of approximations of powers of ten. +//! Pre-computed tables powers-of-5 for extended-precision representations. +//! +//! These tables enable fast scaling of the significant digits +//! of a float to the decimal exponent, with minimal rounding +//! errors, in a 128 or 192-bit representation. +//! //! DO NOT MODIFY: Generated by `src/etc/dec2flt_table.py` -pub const MIN_E: i16 = -305; -pub const MAX_E: i16 = 305; +pub const SMALLEST_POWER_OF_FIVE: i32 = -342; +pub const LARGEST_POWER_OF_FIVE: i32 = 308; +pub const N_POWERS_OF_FIVE: usize = (LARGEST_POWER_OF_FIVE - SMALLEST_POWER_OF_FIVE + 1) as usize; +// Use static to avoid long compile times: Rust compiler errors +// can have the entire table compiled multiple times, and then +// emit code multiple times, even if it's stripped out in +// the final binary. #[rustfmt::skip] -pub static POWERS: ([u64; 611], [i16; 611]) = ( - [ - 0xe0b62e2929aba83c, - 0x8c71dcd9ba0b4926, - 0xaf8e5410288e1b6f, - 0xdb71e91432b1a24b, - 0x892731ac9faf056f, - 0xab70fe17c79ac6ca, - 0xd64d3d9db981787d, - 0x85f0468293f0eb4e, - 0xa76c582338ed2622, - 0xd1476e2c07286faa, - 0x82cca4db847945ca, - 0xa37fce126597973d, - 0xcc5fc196fefd7d0c, - 0xff77b1fcbebcdc4f, - 0x9faacf3df73609b1, - 0xc795830d75038c1e, - 0xf97ae3d0d2446f25, - 0x9becce62836ac577, - 0xc2e801fb244576d5, - 0xf3a20279ed56d48a, - 0x9845418c345644d7, - 0xbe5691ef416bd60c, - 0xedec366b11c6cb8f, - 0x94b3a202eb1c3f39, - 0xb9e08a83a5e34f08, - 0xe858ad248f5c22ca, - 0x91376c36d99995be, - 0xb58547448ffffb2e, - 0xe2e69915b3fff9f9, - 0x8dd01fad907ffc3c, - 0xb1442798f49ffb4b, - 0xdd95317f31c7fa1d, - 0x8a7d3eef7f1cfc52, - 0xad1c8eab5ee43b67, - 0xd863b256369d4a41, - 0x873e4f75e2224e68, - 0xa90de3535aaae202, - 0xd3515c2831559a83, - 0x8412d9991ed58092, - 0xa5178fff668ae0b6, - 0xce5d73ff402d98e4, - 0x80fa687f881c7f8e, - 0xa139029f6a239f72, - 0xc987434744ac874f, - 0xfbe9141915d7a922, - 0x9d71ac8fada6c9b5, - 0xc4ce17b399107c23, - 0xf6019da07f549b2b, - 0x99c102844f94e0fb, - 0xc0314325637a193a, - 0xf03d93eebc589f88, - 0x96267c7535b763b5, - 0xbbb01b9283253ca3, - 0xea9c227723ee8bcb, - 0x92a1958a7675175f, - 0xb749faed14125d37, - 0xe51c79a85916f485, - 0x8f31cc0937ae58d3, - 0xb2fe3f0b8599ef08, - 0xdfbdcece67006ac9, - 0x8bd6a141006042be, - 0xaecc49914078536d, - 0xda7f5bf590966849, - 0x888f99797a5e012d, - 0xaab37fd7d8f58179, - 0xd5605fcdcf32e1d7, - 0x855c3be0a17fcd26, - 0xa6b34ad8c9dfc070, - 0xd0601d8efc57b08c, - 0x823c12795db6ce57, - 0xa2cb1717b52481ed, - 0xcb7ddcdda26da269, - 0xfe5d54150b090b03, - 0x9efa548d26e5a6e2, - 0xc6b8e9b0709f109a, - 0xf867241c8cc6d4c1, - 0x9b407691d7fc44f8, - 0xc21094364dfb5637, - 0xf294b943e17a2bc4, - 0x979cf3ca6cec5b5b, - 0xbd8430bd08277231, - 0xece53cec4a314ebe, - 0x940f4613ae5ed137, - 0xb913179899f68584, - 0xe757dd7ec07426e5, - 0x9096ea6f3848984f, - 0xb4bca50b065abe63, - 0xe1ebce4dc7f16dfc, - 0x8d3360f09cf6e4bd, - 0xb080392cc4349ded, - 0xdca04777f541c568, - 0x89e42caaf9491b61, - 0xac5d37d5b79b6239, - 0xd77485cb25823ac7, - 0x86a8d39ef77164bd, - 0xa8530886b54dbdec, - 0xd267caa862a12d67, - 0x8380dea93da4bc60, - 0xa46116538d0deb78, - 0xcd795be870516656, - 0x806bd9714632dff6, - 0xa086cfcd97bf97f4, - 0xc8a883c0fdaf7df0, - 0xfad2a4b13d1b5d6c, - 0x9cc3a6eec6311a64, - 0xc3f490aa77bd60fd, - 0xf4f1b4d515acb93c, - 0x991711052d8bf3c5, - 0xbf5cd54678eef0b7, - 0xef340a98172aace5, - 0x9580869f0e7aac0f, - 0xbae0a846d2195713, - 0xe998d258869facd7, - 0x91ff83775423cc06, - 0xb67f6455292cbf08, - 0xe41f3d6a7377eeca, - 0x8e938662882af53e, - 0xb23867fb2a35b28e, - 0xdec681f9f4c31f31, - 0x8b3c113c38f9f37f, - 0xae0b158b4738705f, - 0xd98ddaee19068c76, - 0x87f8a8d4cfa417ca, - 0xa9f6d30a038d1dbc, - 0xd47487cc8470652b, - 0x84c8d4dfd2c63f3b, - 0xa5fb0a17c777cf0a, - 0xcf79cc9db955c2cc, - 0x81ac1fe293d599c0, - 0xa21727db38cb0030, - 0xca9cf1d206fdc03c, - 0xfd442e4688bd304b, - 0x9e4a9cec15763e2f, - 0xc5dd44271ad3cdba, - 0xf7549530e188c129, - 0x9a94dd3e8cf578ba, - 0xc13a148e3032d6e8, - 0xf18899b1bc3f8ca2, - 0x96f5600f15a7b7e5, - 0xbcb2b812db11a5de, - 0xebdf661791d60f56, - 0x936b9fcebb25c996, - 0xb84687c269ef3bfb, - 0xe65829b3046b0afa, - 0x8ff71a0fe2c2e6dc, - 0xb3f4e093db73a093, - 0xe0f218b8d25088b8, - 0x8c974f7383725573, - 0xafbd2350644eead0, - 0xdbac6c247d62a584, - 0x894bc396ce5da772, - 0xab9eb47c81f5114f, - 0xd686619ba27255a3, - 0x8613fd0145877586, - 0xa798fc4196e952e7, - 0xd17f3b51fca3a7a1, - 0x82ef85133de648c5, - 0xa3ab66580d5fdaf6, - 0xcc963fee10b7d1b3, - 0xffbbcfe994e5c620, - 0x9fd561f1fd0f9bd4, - 0xc7caba6e7c5382c9, - 0xf9bd690a1b68637b, - 0x9c1661a651213e2d, - 0xc31bfa0fe5698db8, - 0xf3e2f893dec3f126, - 0x986ddb5c6b3a76b8, - 0xbe89523386091466, - 0xee2ba6c0678b597f, - 0x94db483840b717f0, - 0xba121a4650e4ddec, - 0xe896a0d7e51e1566, - 0x915e2486ef32cd60, - 0xb5b5ada8aaff80b8, - 0xe3231912d5bf60e6, - 0x8df5efabc5979c90, - 0xb1736b96b6fd83b4, - 0xddd0467c64bce4a1, - 0x8aa22c0dbef60ee4, - 0xad4ab7112eb3929e, - 0xd89d64d57a607745, - 0x87625f056c7c4a8b, - 0xa93af6c6c79b5d2e, - 0xd389b47879823479, - 0x843610cb4bf160cc, - 0xa54394fe1eedb8ff, - 0xce947a3da6a9273e, - 0x811ccc668829b887, - 0xa163ff802a3426a9, - 0xc9bcff6034c13053, - 0xfc2c3f3841f17c68, - 0x9d9ba7832936edc1, - 0xc5029163f384a931, - 0xf64335bcf065d37d, - 0x99ea0196163fa42e, - 0xc06481fb9bcf8d3a, - 0xf07da27a82c37088, - 0x964e858c91ba2655, - 0xbbe226efb628afeb, - 0xeadab0aba3b2dbe5, - 0x92c8ae6b464fc96f, - 0xb77ada0617e3bbcb, - 0xe55990879ddcaabe, - 0x8f57fa54c2a9eab7, - 0xb32df8e9f3546564, - 0xdff9772470297ebd, - 0x8bfbea76c619ef36, - 0xaefae51477a06b04, - 0xdab99e59958885c5, - 0x88b402f7fd75539b, - 0xaae103b5fcd2a882, - 0xd59944a37c0752a2, - 0x857fcae62d8493a5, - 0xa6dfbd9fb8e5b88f, - 0xd097ad07a71f26b2, - 0x825ecc24c8737830, - 0xa2f67f2dfa90563b, - 0xcbb41ef979346bca, - 0xfea126b7d78186bd, - 0x9f24b832e6b0f436, - 0xc6ede63fa05d3144, - 0xf8a95fcf88747d94, - 0x9b69dbe1b548ce7d, - 0xc24452da229b021c, - 0xf2d56790ab41c2a3, - 0x97c560ba6b0919a6, - 0xbdb6b8e905cb600f, - 0xed246723473e3813, - 0x9436c0760c86e30c, - 0xb94470938fa89bcf, - 0xe7958cb87392c2c3, - 0x90bd77f3483bb9ba, - 0xb4ecd5f01a4aa828, - 0xe2280b6c20dd5232, - 0x8d590723948a535f, - 0xb0af48ec79ace837, - 0xdcdb1b2798182245, - 0x8a08f0f8bf0f156b, - 0xac8b2d36eed2dac6, - 0xd7adf884aa879177, - 0x86ccbb52ea94baeb, - 0xa87fea27a539e9a5, - 0xd29fe4b18e88640f, - 0x83a3eeeef9153e89, - 0xa48ceaaab75a8e2b, - 0xcdb02555653131b6, - 0x808e17555f3ebf12, - 0xa0b19d2ab70e6ed6, - 0xc8de047564d20a8c, - 0xfb158592be068d2f, - 0x9ced737bb6c4183d, - 0xc428d05aa4751e4d, - 0xf53304714d9265e0, - 0x993fe2c6d07b7fac, - 0xbf8fdb78849a5f97, - 0xef73d256a5c0f77d, - 0x95a8637627989aae, - 0xbb127c53b17ec159, - 0xe9d71b689dde71b0, - 0x9226712162ab070e, - 0xb6b00d69bb55c8d1, - 0xe45c10c42a2b3b06, - 0x8eb98a7a9a5b04e3, - 0xb267ed1940f1c61c, - 0xdf01e85f912e37a3, - 0x8b61313bbabce2c6, - 0xae397d8aa96c1b78, - 0xd9c7dced53c72256, - 0x881cea14545c7575, - 0xaa242499697392d3, - 0xd4ad2dbfc3d07788, - 0x84ec3c97da624ab5, - 0xa6274bbdd0fadd62, - 0xcfb11ead453994ba, - 0x81ceb32c4b43fcf5, - 0xa2425ff75e14fc32, - 0xcad2f7f5359a3b3e, - 0xfd87b5f28300ca0e, - 0x9e74d1b791e07e48, - 0xc612062576589ddb, - 0xf79687aed3eec551, - 0x9abe14cd44753b53, - 0xc16d9a0095928a27, - 0xf1c90080baf72cb1, - 0x971da05074da7bef, - 0xbce5086492111aeb, - 0xec1e4a7db69561a5, - 0x9392ee8e921d5d07, - 0xb877aa3236a4b449, - 0xe69594bec44de15b, - 0x901d7cf73ab0acd9, - 0xb424dc35095cd80f, - 0xe12e13424bb40e13, - 0x8cbccc096f5088cc, - 0xafebff0bcb24aaff, - 0xdbe6fecebdedd5bf, - 0x89705f4136b4a597, - 0xabcc77118461cefd, - 0xd6bf94d5e57a42bc, - 0x8637bd05af6c69b6, - 0xa7c5ac471b478423, - 0xd1b71758e219652c, - 0x83126e978d4fdf3b, - 0xa3d70a3d70a3d70a, - 0xcccccccccccccccd, - 0x8000000000000000, - 0xa000000000000000, - 0xc800000000000000, - 0xfa00000000000000, - 0x9c40000000000000, - 0xc350000000000000, - 0xf424000000000000, - 0x9896800000000000, - 0xbebc200000000000, - 0xee6b280000000000, - 0x9502f90000000000, - 0xba43b74000000000, - 0xe8d4a51000000000, - 0x9184e72a00000000, - 0xb5e620f480000000, - 0xe35fa931a0000000, - 0x8e1bc9bf04000000, - 0xb1a2bc2ec5000000, - 0xde0b6b3a76400000, - 0x8ac7230489e80000, - 0xad78ebc5ac620000, - 0xd8d726b7177a8000, - 0x878678326eac9000, - 0xa968163f0a57b400, - 0xd3c21bcecceda100, - 0x84595161401484a0, - 0xa56fa5b99019a5c8, - 0xcecb8f27f4200f3a, - 0x813f3978f8940984, - 0xa18f07d736b90be5, - 0xc9f2c9cd04674edf, - 0xfc6f7c4045812296, - 0x9dc5ada82b70b59e, - 0xc5371912364ce305, - 0xf684df56c3e01bc7, - 0x9a130b963a6c115c, - 0xc097ce7bc90715b3, - 0xf0bdc21abb48db20, - 0x96769950b50d88f4, - 0xbc143fa4e250eb31, - 0xeb194f8e1ae525fd, - 0x92efd1b8d0cf37be, - 0xb7abc627050305ae, - 0xe596b7b0c643c719, - 0x8f7e32ce7bea5c70, - 0xb35dbf821ae4f38c, - 0xe0352f62a19e306f, - 0x8c213d9da502de45, - 0xaf298d050e4395d7, - 0xdaf3f04651d47b4c, - 0x88d8762bf324cd10, - 0xab0e93b6efee0054, - 0xd5d238a4abe98068, - 0x85a36366eb71f041, - 0xa70c3c40a64e6c52, - 0xd0cf4b50cfe20766, - 0x82818f1281ed44a0, - 0xa321f2d7226895c8, - 0xcbea6f8ceb02bb3a, - 0xfee50b7025c36a08, - 0x9f4f2726179a2245, - 0xc722f0ef9d80aad6, - 0xf8ebad2b84e0d58c, - 0x9b934c3b330c8577, - 0xc2781f49ffcfa6d5, - 0xf316271c7fc3908b, - 0x97edd871cfda3a57, - 0xbde94e8e43d0c8ec, - 0xed63a231d4c4fb27, - 0x945e455f24fb1cf9, - 0xb975d6b6ee39e437, - 0xe7d34c64a9c85d44, - 0x90e40fbeea1d3a4b, - 0xb51d13aea4a488dd, - 0xe264589a4dcdab15, - 0x8d7eb76070a08aed, - 0xb0de65388cc8ada8, - 0xdd15fe86affad912, - 0x8a2dbf142dfcc7ab, - 0xacb92ed9397bf996, - 0xd7e77a8f87daf7fc, - 0x86f0ac99b4e8dafd, - 0xa8acd7c0222311bd, - 0xd2d80db02aabd62c, - 0x83c7088e1aab65db, - 0xa4b8cab1a1563f52, - 0xcde6fd5e09abcf27, - 0x80b05e5ac60b6178, - 0xa0dc75f1778e39d6, - 0xc913936dd571c84c, - 0xfb5878494ace3a5f, - 0x9d174b2dcec0e47b, - 0xc45d1df942711d9a, - 0xf5746577930d6501, - 0x9968bf6abbe85f20, - 0xbfc2ef456ae276e9, - 0xefb3ab16c59b14a3, - 0x95d04aee3b80ece6, - 0xbb445da9ca61281f, - 0xea1575143cf97227, - 0x924d692ca61be758, - 0xb6e0c377cfa2e12e, - 0xe498f455c38b997a, - 0x8edf98b59a373fec, - 0xb2977ee300c50fe7, - 0xdf3d5e9bc0f653e1, - 0x8b865b215899f46d, - 0xae67f1e9aec07188, - 0xda01ee641a708dea, - 0x884134fe908658b2, - 0xaa51823e34a7eedf, - 0xd4e5e2cdc1d1ea96, - 0x850fadc09923329e, - 0xa6539930bf6bff46, - 0xcfe87f7cef46ff17, - 0x81f14fae158c5f6e, - 0xa26da3999aef774a, - 0xcb090c8001ab551c, - 0xfdcb4fa002162a63, - 0x9e9f11c4014dda7e, - 0xc646d63501a1511e, - 0xf7d88bc24209a565, - 0x9ae757596946075f, - 0xc1a12d2fc3978937, - 0xf209787bb47d6b85, - 0x9745eb4d50ce6333, - 0xbd176620a501fc00, - 0xec5d3fa8ce427b00, - 0x93ba47c980e98ce0, - 0xb8a8d9bbe123f018, - 0xe6d3102ad96cec1e, - 0x9043ea1ac7e41393, - 0xb454e4a179dd1877, - 0xe16a1dc9d8545e95, - 0x8ce2529e2734bb1d, - 0xb01ae745b101e9e4, - 0xdc21a1171d42645d, - 0x899504ae72497eba, - 0xabfa45da0edbde69, - 0xd6f8d7509292d603, - 0x865b86925b9bc5c2, - 0xa7f26836f282b733, - 0xd1ef0244af2364ff, - 0x8335616aed761f1f, - 0xa402b9c5a8d3a6e7, - 0xcd036837130890a1, - 0x802221226be55a65, - 0xa02aa96b06deb0fe, - 0xc83553c5c8965d3d, - 0xfa42a8b73abbf48d, - 0x9c69a97284b578d8, - 0xc38413cf25e2d70e, - 0xf46518c2ef5b8cd1, - 0x98bf2f79d5993803, - 0xbeeefb584aff8604, - 0xeeaaba2e5dbf6785, - 0x952ab45cfa97a0b3, - 0xba756174393d88e0, - 0xe912b9d1478ceb17, - 0x91abb422ccb812ef, - 0xb616a12b7fe617aa, - 0xe39c49765fdf9d95, - 0x8e41ade9fbebc27d, - 0xb1d219647ae6b31c, - 0xde469fbd99a05fe3, - 0x8aec23d680043bee, - 0xada72ccc20054aea, - 0xd910f7ff28069da4, - 0x87aa9aff79042287, - 0xa99541bf57452b28, - 0xd3fa922f2d1675f2, - 0x847c9b5d7c2e09b7, - 0xa59bc234db398c25, - 0xcf02b2c21207ef2f, - 0x8161afb94b44f57d, - 0xa1ba1ba79e1632dc, - 0xca28a291859bbf93, - 0xfcb2cb35e702af78, - 0x9defbf01b061adab, - 0xc56baec21c7a1916, - 0xf6c69a72a3989f5c, - 0x9a3c2087a63f6399, - 0xc0cb28a98fcf3c80, - 0xf0fdf2d3f3c30b9f, - 0x969eb7c47859e744, - 0xbc4665b596706115, - 0xeb57ff22fc0c795a, - 0x9316ff75dd87cbd8, - 0xb7dcbf5354e9bece, - 0xe5d3ef282a242e82, - 0x8fa475791a569d11, - 0xb38d92d760ec4455, - 0xe070f78d3927556b, - 0x8c469ab843b89563, - 0xaf58416654a6babb, - 0xdb2e51bfe9d0696a, - 0x88fcf317f22241e2, - 0xab3c2fddeeaad25b, - 0xd60b3bd56a5586f2, - 0x85c7056562757457, - 0xa738c6bebb12d16d, - 0xd106f86e69d785c8, - 0x82a45b450226b39d, - 0xa34d721642b06084, - 0xcc20ce9bd35c78a5, - 0xff290242c83396ce, - 0x9f79a169bd203e41, - 0xc75809c42c684dd1, - 0xf92e0c3537826146, - 0x9bbcc7a142b17ccc, - 0xc2abf989935ddbfe, - 0xf356f7ebf83552fe, - 0x98165af37b2153df, - 0xbe1bf1b059e9a8d6, - 0xeda2ee1c7064130c, - 0x9485d4d1c63e8be8, - 0xb9a74a0637ce2ee1, - 0xe8111c87c5c1ba9a, - 0x910ab1d4db9914a0, - 0xb54d5e4a127f59c8, - 0xe2a0b5dc971f303a, - 0x8da471a9de737e24, - 0xb10d8e1456105dad, - 0xdd50f1996b947519, - 0x8a5296ffe33cc930, - 0xace73cbfdc0bfb7b, - 0xd8210befd30efa5a, - 0x8714a775e3e95c78, - 0xa8d9d1535ce3b396, - 0xd31045a8341ca07c, - 0x83ea2b892091e44e, - 0xa4e4b66b68b65d61, - 0xce1de40642e3f4b9, - 0x80d2ae83e9ce78f4, - 0xa1075a24e4421731, - 0xc94930ae1d529cfd, - 0xfb9b7cd9a4a7443c, - 0x9d412e0806e88aa6, - 0xc491798a08a2ad4f, - 0xf5b5d7ec8acb58a3, - 0x9991a6f3d6bf1766, - 0xbff610b0cc6edd3f, - 0xeff394dcff8a948f, - 0x95f83d0a1fb69cd9, - 0xbb764c4ca7a44410, - 0xea53df5fd18d5514, - 0x92746b9be2f8552c, - 0xb7118682dbb66a77, - 0xe4d5e82392a40515, - 0x8f05b1163ba6832d, - 0xb2c71d5bca9023f8, - 0xdf78e4b2bd342cf7, - 0x8bab8eefb6409c1a, - 0xae9672aba3d0c321, - 0xda3c0f568cc4f3e9, - 0x8865899617fb1871, - 0xaa7eebfb9df9de8e, - 0xd51ea6fa85785631, - 0x8533285c936b35df, - 0xa67ff273b8460357, - 0xd01fef10a657842c, - 0x8213f56a67f6b29c, - 0xa298f2c501f45f43, - 0xcb3f2f7642717713, - 0xfe0efb53d30dd4d8, - 0x9ec95d1463e8a507, - 0xc67bb4597ce2ce49, - 0xf81aa16fdc1b81db, - 0x9b10a4e5e9913129, - 0xc1d4ce1f63f57d73, - 0xf24a01a73cf2dcd0, - 0x976e41088617ca02, - 0xbd49d14aa79dbc82, - 0xec9c459d51852ba3, - 0x93e1ab8252f33b46, - 0xb8da1662e7b00a17, - 0xe7109bfba19c0c9d, - 0x906a617d450187e2, - 0xb484f9dc9641e9db, - 0xe1a63853bbd26451, - 0x8d07e33455637eb3, - 0xb049dc016abc5e60, - 0xdc5c5301c56b75f7, - 0x89b9b3e11b6329bb, - 0xac2820d9623bf429, - 0xd732290fbacaf134, - 0x867f59a9d4bed6c0, - 0xa81f301449ee8c70, - 0xd226fc195c6a2f8c, - 0x83585d8fd9c25db8, - 0xa42e74f3d032f526, - 0xcd3a1230c43fb26f, - 0x80444b5e7aa7cf85, - 0xa0555e361951c367, - 0xc86ab5c39fa63441, - 0xfa856334878fc151, - 0x9c935e00d4b9d8d2, - 0xc3b8358109e84f07, - 0xf4a642e14c6262c9, - 0x98e7e9cccfbd7dbe, - 0xbf21e44003acdd2d, - 0xeeea5d5004981478, - 0x95527a5202df0ccb, - 0xbaa718e68396cffe, - 0xe950df20247c83fd, - 0x91d28b7416cdd27e, - ], - [ - -1077, - -1073, - -1070, - -1067, - -1063, - -1060, - -1057, - -1053, - -1050, - -1047, - -1043, - -1040, - -1037, - -1034, - -1030, - -1027, - -1024, - -1020, - -1017, - -1014, - -1010, - -1007, - -1004, - -1000, - -997, - -994, - -990, - -987, - -984, - -980, - -977, - -974, - -970, - -967, - -964, - -960, - -957, - -954, - -950, - -947, - -944, - -940, - -937, - -934, - -931, - -927, - -924, - -921, - -917, - -914, - -911, - -907, - -904, - -901, - -897, - -894, - -891, - -887, - -884, - -881, - -877, - -874, - -871, - -867, - -864, - -861, - -857, - -854, - -851, - -847, - -844, - -841, - -838, - -834, - -831, - -828, - -824, - -821, - -818, - -814, - -811, - -808, - -804, - -801, - -798, - -794, - -791, - -788, - -784, - -781, - -778, - -774, - -771, - -768, - -764, - -761, - -758, - -754, - -751, - -748, - -744, - -741, - -738, - -735, - -731, - -728, - -725, - -721, - -718, - -715, - -711, - -708, - -705, - -701, - -698, - -695, - -691, - -688, - -685, - -681, - -678, - -675, - -671, - -668, - -665, - -661, - -658, - -655, - -651, - -648, - -645, - -642, - -638, - -635, - -632, - -628, - -625, - -622, - -618, - -615, - -612, - -608, - -605, - -602, - -598, - -595, - -592, - -588, - -585, - -582, - -578, - -575, - -572, - -568, - -565, - -562, - -558, - -555, - -552, - -549, - -545, - -542, - -539, - -535, - -532, - -529, - -525, - -522, - -519, - -515, - -512, - -509, - -505, - -502, - -499, - -495, - -492, - -489, - -485, - -482, - -479, - -475, - -472, - -469, - -465, - -462, - -459, - -455, - -452, - -449, - -446, - -442, - -439, - -436, - -432, - -429, - -426, - -422, - -419, - -416, - -412, - -409, - -406, - -402, - -399, - -396, - -392, - -389, - -386, - -382, - -379, - -376, - -372, - -369, - -366, - -362, - -359, - -356, - -353, - -349, - -346, - -343, - -339, - -336, - -333, - -329, - -326, - -323, - -319, - -316, - -313, - -309, - -306, - -303, - -299, - -296, - -293, - -289, - -286, - -283, - -279, - -276, - -273, - -269, - -266, - -263, - -259, - -256, - -253, - -250, - -246, - -243, - -240, - -236, - -233, - -230, - -226, - -223, - -220, - -216, - -213, - -210, - -206, - -203, - -200, - -196, - -193, - -190, - -186, - -183, - -180, - -176, - -173, - -170, - -166, - -163, - -160, - -157, - -153, - -150, - -147, - -143, - -140, - -137, - -133, - -130, - -127, - -123, - -120, - -117, - -113, - -110, - -107, - -103, - -100, - -97, - -93, - -90, - -87, - -83, - -80, - -77, - -73, - -70, - -67, - -63, - -60, - -57, - -54, - -50, - -47, - -44, - -40, - -37, - -34, - -30, - -27, - -24, - -20, - -17, - -14, - -10, - -7, - -4, - 0, - 3, - 6, - 10, - 13, - 16, - 20, - 23, - 26, - 30, - 33, - 36, - 39, - 43, - 46, - 49, - 53, - 56, - 59, - 63, - 66, - 69, - 73, - 76, - 79, - 83, - 86, - 89, - 93, - 96, - 99, - 103, - 106, - 109, - 113, - 116, - 119, - 123, - 126, - 129, - 132, - 136, - 139, - 142, - 146, - 149, - 152, - 156, - 159, - 162, - 166, - 169, - 172, - 176, - 179, - 182, - 186, - 189, - 192, - 196, - 199, - 202, - 206, - 209, - 212, - 216, - 219, - 222, - 226, - 229, - 232, - 235, - 239, - 242, - 245, - 249, - 252, - 255, - 259, - 262, - 265, - 269, - 272, - 275, - 279, - 282, - 285, - 289, - 292, - 295, - 299, - 302, - 305, - 309, - 312, - 315, - 319, - 322, - 325, - 328, - 332, - 335, - 338, - 342, - 345, - 348, - 352, - 355, - 358, - 362, - 365, - 368, - 372, - 375, - 378, - 382, - 385, - 388, - 392, - 395, - 398, - 402, - 405, - 408, - 412, - 415, - 418, - 422, - 425, - 428, - 431, - 435, - 438, - 441, - 445, - 448, - 451, - 455, - 458, - 461, - 465, - 468, - 471, - 475, - 478, - 481, - 485, - 488, - 491, - 495, - 498, - 501, - 505, - 508, - 511, - 515, - 518, - 521, - 524, - 528, - 531, - 534, - 538, - 541, - 544, - 548, - 551, - 554, - 558, - 561, - 564, - 568, - 571, - 574, - 578, - 581, - 584, - 588, - 591, - 594, - 598, - 601, - 604, - 608, - 611, - 614, - 617, - 621, - 624, - 627, - 631, - 634, - 637, - 641, - 644, - 647, - 651, - 654, - 657, - 661, - 664, - 667, - 671, - 674, - 677, - 681, - 684, - 687, - 691, - 694, - 697, - 701, - 704, - 707, - 711, - 714, - 717, - 720, - 724, - 727, - 730, - 734, - 737, - 740, - 744, - 747, - 750, - 754, - 757, - 760, - 764, - 767, - 770, - 774, - 777, - 780, - 784, - 787, - 790, - 794, - 797, - 800, - 804, - 807, - 810, - 813, - 817, - 820, - 823, - 827, - 830, - 833, - 837, - 840, - 843, - 847, - 850, - 853, - 857, - 860, - 863, - 867, - 870, - 873, - 877, - 880, - 883, - 887, - 890, - 893, - 897, - 900, - 903, - 907, - 910, - 913, - 916, - 920, - 923, - 926, - 930, - 933, - 936, - 940, - 943, - 946, - 950, - ], -); - -#[rustfmt::skip] -pub const F32_SHORT_POWERS: [f32; 11] = [ - 1e0, - 1e1, - 1e2, - 1e3, - 1e4, - 1e5, - 1e6, - 1e7, - 1e8, - 1e9, - 1e10, -]; - -#[rustfmt::skip] -pub const F64_SHORT_POWERS: [f64; 23] = [ - 1e0, - 1e1, - 1e2, - 1e3, - 1e4, - 1e5, - 1e6, - 1e7, - 1e8, - 1e9, - 1e10, - 1e11, - 1e12, - 1e13, - 1e14, - 1e15, - 1e16, - 1e17, - 1e18, - 1e19, - 1e20, - 1e21, - 1e22, +pub static POWER_OF_FIVE_128: [(u64, u64); N_POWERS_OF_FIVE] = [ + (0xeef453d6923bd65a, 0x113faa2906a13b3f), // 5^-342 + (0x9558b4661b6565f8, 0x4ac7ca59a424c507), // 5^-341 + (0xbaaee17fa23ebf76, 0x5d79bcf00d2df649), // 5^-340 + (0xe95a99df8ace6f53, 0xf4d82c2c107973dc), // 5^-339 + (0x91d8a02bb6c10594, 0x79071b9b8a4be869), // 5^-338 + (0xb64ec836a47146f9, 0x9748e2826cdee284), // 5^-337 + (0xe3e27a444d8d98b7, 0xfd1b1b2308169b25), // 5^-336 + (0x8e6d8c6ab0787f72, 0xfe30f0f5e50e20f7), // 5^-335 + (0xb208ef855c969f4f, 0xbdbd2d335e51a935), // 5^-334 + (0xde8b2b66b3bc4723, 0xad2c788035e61382), // 5^-333 + (0x8b16fb203055ac76, 0x4c3bcb5021afcc31), // 5^-332 + (0xaddcb9e83c6b1793, 0xdf4abe242a1bbf3d), // 5^-331 + (0xd953e8624b85dd78, 0xd71d6dad34a2af0d), // 5^-330 + (0x87d4713d6f33aa6b, 0x8672648c40e5ad68), // 5^-329 + (0xa9c98d8ccb009506, 0x680efdaf511f18c2), // 5^-328 + (0xd43bf0effdc0ba48, 0x212bd1b2566def2), // 5^-327 + (0x84a57695fe98746d, 0x14bb630f7604b57), // 5^-326 + (0xa5ced43b7e3e9188, 0x419ea3bd35385e2d), // 5^-325 + (0xcf42894a5dce35ea, 0x52064cac828675b9), // 5^-324 + (0x818995ce7aa0e1b2, 0x7343efebd1940993), // 5^-323 + (0xa1ebfb4219491a1f, 0x1014ebe6c5f90bf8), // 5^-322 + (0xca66fa129f9b60a6, 0xd41a26e077774ef6), // 5^-321 + (0xfd00b897478238d0, 0x8920b098955522b4), // 5^-320 + (0x9e20735e8cb16382, 0x55b46e5f5d5535b0), // 5^-319 + (0xc5a890362fddbc62, 0xeb2189f734aa831d), // 5^-318 + (0xf712b443bbd52b7b, 0xa5e9ec7501d523e4), // 5^-317 + (0x9a6bb0aa55653b2d, 0x47b233c92125366e), // 5^-316 + (0xc1069cd4eabe89f8, 0x999ec0bb696e840a), // 5^-315 + (0xf148440a256e2c76, 0xc00670ea43ca250d), // 5^-314 + (0x96cd2a865764dbca, 0x380406926a5e5728), // 5^-313 + (0xbc807527ed3e12bc, 0xc605083704f5ecf2), // 5^-312 + (0xeba09271e88d976b, 0xf7864a44c633682e), // 5^-311 + (0x93445b8731587ea3, 0x7ab3ee6afbe0211d), // 5^-310 + (0xb8157268fdae9e4c, 0x5960ea05bad82964), // 5^-309 + (0xe61acf033d1a45df, 0x6fb92487298e33bd), // 5^-308 + (0x8fd0c16206306bab, 0xa5d3b6d479f8e056), // 5^-307 + (0xb3c4f1ba87bc8696, 0x8f48a4899877186c), // 5^-306 + (0xe0b62e2929aba83c, 0x331acdabfe94de87), // 5^-305 + (0x8c71dcd9ba0b4925, 0x9ff0c08b7f1d0b14), // 5^-304 + (0xaf8e5410288e1b6f, 0x7ecf0ae5ee44dd9), // 5^-303 + (0xdb71e91432b1a24a, 0xc9e82cd9f69d6150), // 5^-302 + (0x892731ac9faf056e, 0xbe311c083a225cd2), // 5^-301 + (0xab70fe17c79ac6ca, 0x6dbd630a48aaf406), // 5^-300 + (0xd64d3d9db981787d, 0x92cbbccdad5b108), // 5^-299 + (0x85f0468293f0eb4e, 0x25bbf56008c58ea5), // 5^-298 + (0xa76c582338ed2621, 0xaf2af2b80af6f24e), // 5^-297 + (0xd1476e2c07286faa, 0x1af5af660db4aee1), // 5^-296 + (0x82cca4db847945ca, 0x50d98d9fc890ed4d), // 5^-295 + (0xa37fce126597973c, 0xe50ff107bab528a0), // 5^-294 + (0xcc5fc196fefd7d0c, 0x1e53ed49a96272c8), // 5^-293 + (0xff77b1fcbebcdc4f, 0x25e8e89c13bb0f7a), // 5^-292 + (0x9faacf3df73609b1, 0x77b191618c54e9ac), // 5^-291 + (0xc795830d75038c1d, 0xd59df5b9ef6a2417), // 5^-290 + (0xf97ae3d0d2446f25, 0x4b0573286b44ad1d), // 5^-289 + (0x9becce62836ac577, 0x4ee367f9430aec32), // 5^-288 + (0xc2e801fb244576d5, 0x229c41f793cda73f), // 5^-287 + (0xf3a20279ed56d48a, 0x6b43527578c1110f), // 5^-286 + (0x9845418c345644d6, 0x830a13896b78aaa9), // 5^-285 + (0xbe5691ef416bd60c, 0x23cc986bc656d553), // 5^-284 + (0xedec366b11c6cb8f, 0x2cbfbe86b7ec8aa8), // 5^-283 + (0x94b3a202eb1c3f39, 0x7bf7d71432f3d6a9), // 5^-282 + (0xb9e08a83a5e34f07, 0xdaf5ccd93fb0cc53), // 5^-281 + (0xe858ad248f5c22c9, 0xd1b3400f8f9cff68), // 5^-280 + (0x91376c36d99995be, 0x23100809b9c21fa1), // 5^-279 + (0xb58547448ffffb2d, 0xabd40a0c2832a78a), // 5^-278 + (0xe2e69915b3fff9f9, 0x16c90c8f323f516c), // 5^-277 + (0x8dd01fad907ffc3b, 0xae3da7d97f6792e3), // 5^-276 + (0xb1442798f49ffb4a, 0x99cd11cfdf41779c), // 5^-275 + (0xdd95317f31c7fa1d, 0x40405643d711d583), // 5^-274 + (0x8a7d3eef7f1cfc52, 0x482835ea666b2572), // 5^-273 + (0xad1c8eab5ee43b66, 0xda3243650005eecf), // 5^-272 + (0xd863b256369d4a40, 0x90bed43e40076a82), // 5^-271 + (0x873e4f75e2224e68, 0x5a7744a6e804a291), // 5^-270 + (0xa90de3535aaae202, 0x711515d0a205cb36), // 5^-269 + (0xd3515c2831559a83, 0xd5a5b44ca873e03), // 5^-268 + (0x8412d9991ed58091, 0xe858790afe9486c2), // 5^-267 + (0xa5178fff668ae0b6, 0x626e974dbe39a872), // 5^-266 + (0xce5d73ff402d98e3, 0xfb0a3d212dc8128f), // 5^-265 + (0x80fa687f881c7f8e, 0x7ce66634bc9d0b99), // 5^-264 + (0xa139029f6a239f72, 0x1c1fffc1ebc44e80), // 5^-263 + (0xc987434744ac874e, 0xa327ffb266b56220), // 5^-262 + (0xfbe9141915d7a922, 0x4bf1ff9f0062baa8), // 5^-261 + (0x9d71ac8fada6c9b5, 0x6f773fc3603db4a9), // 5^-260 + (0xc4ce17b399107c22, 0xcb550fb4384d21d3), // 5^-259 + (0xf6019da07f549b2b, 0x7e2a53a146606a48), // 5^-258 + (0x99c102844f94e0fb, 0x2eda7444cbfc426d), // 5^-257 + (0xc0314325637a1939, 0xfa911155fefb5308), // 5^-256 + (0xf03d93eebc589f88, 0x793555ab7eba27ca), // 5^-255 + (0x96267c7535b763b5, 0x4bc1558b2f3458de), // 5^-254 + (0xbbb01b9283253ca2, 0x9eb1aaedfb016f16), // 5^-253 + (0xea9c227723ee8bcb, 0x465e15a979c1cadc), // 5^-252 + (0x92a1958a7675175f, 0xbfacd89ec191ec9), // 5^-251 + (0xb749faed14125d36, 0xcef980ec671f667b), // 5^-250 + (0xe51c79a85916f484, 0x82b7e12780e7401a), // 5^-249 + (0x8f31cc0937ae58d2, 0xd1b2ecb8b0908810), // 5^-248 + (0xb2fe3f0b8599ef07, 0x861fa7e6dcb4aa15), // 5^-247 + (0xdfbdcece67006ac9, 0x67a791e093e1d49a), // 5^-246 + (0x8bd6a141006042bd, 0xe0c8bb2c5c6d24e0), // 5^-245 + (0xaecc49914078536d, 0x58fae9f773886e18), // 5^-244 + (0xda7f5bf590966848, 0xaf39a475506a899e), // 5^-243 + (0x888f99797a5e012d, 0x6d8406c952429603), // 5^-242 + (0xaab37fd7d8f58178, 0xc8e5087ba6d33b83), // 5^-241 + (0xd5605fcdcf32e1d6, 0xfb1e4a9a90880a64), // 5^-240 + (0x855c3be0a17fcd26, 0x5cf2eea09a55067f), // 5^-239 + (0xa6b34ad8c9dfc06f, 0xf42faa48c0ea481e), // 5^-238 + (0xd0601d8efc57b08b, 0xf13b94daf124da26), // 5^-237 + (0x823c12795db6ce57, 0x76c53d08d6b70858), // 5^-236 + (0xa2cb1717b52481ed, 0x54768c4b0c64ca6e), // 5^-235 + (0xcb7ddcdda26da268, 0xa9942f5dcf7dfd09), // 5^-234 + (0xfe5d54150b090b02, 0xd3f93b35435d7c4c), // 5^-233 + (0x9efa548d26e5a6e1, 0xc47bc5014a1a6daf), // 5^-232 + (0xc6b8e9b0709f109a, 0x359ab6419ca1091b), // 5^-231 + (0xf867241c8cc6d4c0, 0xc30163d203c94b62), // 5^-230 + (0x9b407691d7fc44f8, 0x79e0de63425dcf1d), // 5^-229 + (0xc21094364dfb5636, 0x985915fc12f542e4), // 5^-228 + (0xf294b943e17a2bc4, 0x3e6f5b7b17b2939d), // 5^-227 + (0x979cf3ca6cec5b5a, 0xa705992ceecf9c42), // 5^-226 + (0xbd8430bd08277231, 0x50c6ff782a838353), // 5^-225 + (0xece53cec4a314ebd, 0xa4f8bf5635246428), // 5^-224 + (0x940f4613ae5ed136, 0x871b7795e136be99), // 5^-223 + (0xb913179899f68584, 0x28e2557b59846e3f), // 5^-222 + (0xe757dd7ec07426e5, 0x331aeada2fe589cf), // 5^-221 + (0x9096ea6f3848984f, 0x3ff0d2c85def7621), // 5^-220 + (0xb4bca50b065abe63, 0xfed077a756b53a9), // 5^-219 + (0xe1ebce4dc7f16dfb, 0xd3e8495912c62894), // 5^-218 + (0x8d3360f09cf6e4bd, 0x64712dd7abbbd95c), // 5^-217 + (0xb080392cc4349dec, 0xbd8d794d96aacfb3), // 5^-216 + (0xdca04777f541c567, 0xecf0d7a0fc5583a0), // 5^-215 + (0x89e42caaf9491b60, 0xf41686c49db57244), // 5^-214 + (0xac5d37d5b79b6239, 0x311c2875c522ced5), // 5^-213 + (0xd77485cb25823ac7, 0x7d633293366b828b), // 5^-212 + (0x86a8d39ef77164bc, 0xae5dff9c02033197), // 5^-211 + (0xa8530886b54dbdeb, 0xd9f57f830283fdfc), // 5^-210 + (0xd267caa862a12d66, 0xd072df63c324fd7b), // 5^-209 + (0x8380dea93da4bc60, 0x4247cb9e59f71e6d), // 5^-208 + (0xa46116538d0deb78, 0x52d9be85f074e608), // 5^-207 + (0xcd795be870516656, 0x67902e276c921f8b), // 5^-206 + (0x806bd9714632dff6, 0xba1cd8a3db53b6), // 5^-205 + (0xa086cfcd97bf97f3, 0x80e8a40eccd228a4), // 5^-204 + (0xc8a883c0fdaf7df0, 0x6122cd128006b2cd), // 5^-203 + (0xfad2a4b13d1b5d6c, 0x796b805720085f81), // 5^-202 + (0x9cc3a6eec6311a63, 0xcbe3303674053bb0), // 5^-201 + (0xc3f490aa77bd60fc, 0xbedbfc4411068a9c), // 5^-200 + (0xf4f1b4d515acb93b, 0xee92fb5515482d44), // 5^-199 + (0x991711052d8bf3c5, 0x751bdd152d4d1c4a), // 5^-198 + (0xbf5cd54678eef0b6, 0xd262d45a78a0635d), // 5^-197 + (0xef340a98172aace4, 0x86fb897116c87c34), // 5^-196 + (0x9580869f0e7aac0e, 0xd45d35e6ae3d4da0), // 5^-195 + (0xbae0a846d2195712, 0x8974836059cca109), // 5^-194 + (0xe998d258869facd7, 0x2bd1a438703fc94b), // 5^-193 + (0x91ff83775423cc06, 0x7b6306a34627ddcf), // 5^-192 + (0xb67f6455292cbf08, 0x1a3bc84c17b1d542), // 5^-191 + (0xe41f3d6a7377eeca, 0x20caba5f1d9e4a93), // 5^-190 + (0x8e938662882af53e, 0x547eb47b7282ee9c), // 5^-189 + (0xb23867fb2a35b28d, 0xe99e619a4f23aa43), // 5^-188 + (0xdec681f9f4c31f31, 0x6405fa00e2ec94d4), // 5^-187 + (0x8b3c113c38f9f37e, 0xde83bc408dd3dd04), // 5^-186 + (0xae0b158b4738705e, 0x9624ab50b148d445), // 5^-185 + (0xd98ddaee19068c76, 0x3badd624dd9b0957), // 5^-184 + (0x87f8a8d4cfa417c9, 0xe54ca5d70a80e5d6), // 5^-183 + (0xa9f6d30a038d1dbc, 0x5e9fcf4ccd211f4c), // 5^-182 + (0xd47487cc8470652b, 0x7647c3200069671f), // 5^-181 + (0x84c8d4dfd2c63f3b, 0x29ecd9f40041e073), // 5^-180 + (0xa5fb0a17c777cf09, 0xf468107100525890), // 5^-179 + (0xcf79cc9db955c2cc, 0x7182148d4066eeb4), // 5^-178 + (0x81ac1fe293d599bf, 0xc6f14cd848405530), // 5^-177 + (0xa21727db38cb002f, 0xb8ada00e5a506a7c), // 5^-176 + (0xca9cf1d206fdc03b, 0xa6d90811f0e4851c), // 5^-175 + (0xfd442e4688bd304a, 0x908f4a166d1da663), // 5^-174 + (0x9e4a9cec15763e2e, 0x9a598e4e043287fe), // 5^-173 + (0xc5dd44271ad3cdba, 0x40eff1e1853f29fd), // 5^-172 + (0xf7549530e188c128, 0xd12bee59e68ef47c), // 5^-171 + (0x9a94dd3e8cf578b9, 0x82bb74f8301958ce), // 5^-170 + (0xc13a148e3032d6e7, 0xe36a52363c1faf01), // 5^-169 + (0xf18899b1bc3f8ca1, 0xdc44e6c3cb279ac1), // 5^-168 + (0x96f5600f15a7b7e5, 0x29ab103a5ef8c0b9), // 5^-167 + (0xbcb2b812db11a5de, 0x7415d448f6b6f0e7), // 5^-166 + (0xebdf661791d60f56, 0x111b495b3464ad21), // 5^-165 + (0x936b9fcebb25c995, 0xcab10dd900beec34), // 5^-164 + (0xb84687c269ef3bfb, 0x3d5d514f40eea742), // 5^-163 + (0xe65829b3046b0afa, 0xcb4a5a3112a5112), // 5^-162 + (0x8ff71a0fe2c2e6dc, 0x47f0e785eaba72ab), // 5^-161 + (0xb3f4e093db73a093, 0x59ed216765690f56), // 5^-160 + (0xe0f218b8d25088b8, 0x306869c13ec3532c), // 5^-159 + (0x8c974f7383725573, 0x1e414218c73a13fb), // 5^-158 + (0xafbd2350644eeacf, 0xe5d1929ef90898fa), // 5^-157 + (0xdbac6c247d62a583, 0xdf45f746b74abf39), // 5^-156 + (0x894bc396ce5da772, 0x6b8bba8c328eb783), // 5^-155 + (0xab9eb47c81f5114f, 0x66ea92f3f326564), // 5^-154 + (0xd686619ba27255a2, 0xc80a537b0efefebd), // 5^-153 + (0x8613fd0145877585, 0xbd06742ce95f5f36), // 5^-152 + (0xa798fc4196e952e7, 0x2c48113823b73704), // 5^-151 + (0xd17f3b51fca3a7a0, 0xf75a15862ca504c5), // 5^-150 + (0x82ef85133de648c4, 0x9a984d73dbe722fb), // 5^-149 + (0xa3ab66580d5fdaf5, 0xc13e60d0d2e0ebba), // 5^-148 + (0xcc963fee10b7d1b3, 0x318df905079926a8), // 5^-147 + (0xffbbcfe994e5c61f, 0xfdf17746497f7052), // 5^-146 + (0x9fd561f1fd0f9bd3, 0xfeb6ea8bedefa633), // 5^-145 + (0xc7caba6e7c5382c8, 0xfe64a52ee96b8fc0), // 5^-144 + (0xf9bd690a1b68637b, 0x3dfdce7aa3c673b0), // 5^-143 + (0x9c1661a651213e2d, 0x6bea10ca65c084e), // 5^-142 + (0xc31bfa0fe5698db8, 0x486e494fcff30a62), // 5^-141 + (0xf3e2f893dec3f126, 0x5a89dba3c3efccfa), // 5^-140 + (0x986ddb5c6b3a76b7, 0xf89629465a75e01c), // 5^-139 + (0xbe89523386091465, 0xf6bbb397f1135823), // 5^-138 + (0xee2ba6c0678b597f, 0x746aa07ded582e2c), // 5^-137 + (0x94db483840b717ef, 0xa8c2a44eb4571cdc), // 5^-136 + (0xba121a4650e4ddeb, 0x92f34d62616ce413), // 5^-135 + (0xe896a0d7e51e1566, 0x77b020baf9c81d17), // 5^-134 + (0x915e2486ef32cd60, 0xace1474dc1d122e), // 5^-133 + (0xb5b5ada8aaff80b8, 0xd819992132456ba), // 5^-132 + (0xe3231912d5bf60e6, 0x10e1fff697ed6c69), // 5^-131 + (0x8df5efabc5979c8f, 0xca8d3ffa1ef463c1), // 5^-130 + (0xb1736b96b6fd83b3, 0xbd308ff8a6b17cb2), // 5^-129 + (0xddd0467c64bce4a0, 0xac7cb3f6d05ddbde), // 5^-128 + (0x8aa22c0dbef60ee4, 0x6bcdf07a423aa96b), // 5^-127 + (0xad4ab7112eb3929d, 0x86c16c98d2c953c6), // 5^-126 + (0xd89d64d57a607744, 0xe871c7bf077ba8b7), // 5^-125 + (0x87625f056c7c4a8b, 0x11471cd764ad4972), // 5^-124 + (0xa93af6c6c79b5d2d, 0xd598e40d3dd89bcf), // 5^-123 + (0xd389b47879823479, 0x4aff1d108d4ec2c3), // 5^-122 + (0x843610cb4bf160cb, 0xcedf722a585139ba), // 5^-121 + (0xa54394fe1eedb8fe, 0xc2974eb4ee658828), // 5^-120 + (0xce947a3da6a9273e, 0x733d226229feea32), // 5^-119 + (0x811ccc668829b887, 0x806357d5a3f525f), // 5^-118 + (0xa163ff802a3426a8, 0xca07c2dcb0cf26f7), // 5^-117 + (0xc9bcff6034c13052, 0xfc89b393dd02f0b5), // 5^-116 + (0xfc2c3f3841f17c67, 0xbbac2078d443ace2), // 5^-115 + (0x9d9ba7832936edc0, 0xd54b944b84aa4c0d), // 5^-114 + (0xc5029163f384a931, 0xa9e795e65d4df11), // 5^-113 + (0xf64335bcf065d37d, 0x4d4617b5ff4a16d5), // 5^-112 + (0x99ea0196163fa42e, 0x504bced1bf8e4e45), // 5^-111 + (0xc06481fb9bcf8d39, 0xe45ec2862f71e1d6), // 5^-110 + (0xf07da27a82c37088, 0x5d767327bb4e5a4c), // 5^-109 + (0x964e858c91ba2655, 0x3a6a07f8d510f86f), // 5^-108 + (0xbbe226efb628afea, 0x890489f70a55368b), // 5^-107 + (0xeadab0aba3b2dbe5, 0x2b45ac74ccea842e), // 5^-106 + (0x92c8ae6b464fc96f, 0x3b0b8bc90012929d), // 5^-105 + (0xb77ada0617e3bbcb, 0x9ce6ebb40173744), // 5^-104 + (0xe55990879ddcaabd, 0xcc420a6a101d0515), // 5^-103 + (0x8f57fa54c2a9eab6, 0x9fa946824a12232d), // 5^-102 + (0xb32df8e9f3546564, 0x47939822dc96abf9), // 5^-101 + (0xdff9772470297ebd, 0x59787e2b93bc56f7), // 5^-100 + (0x8bfbea76c619ef36, 0x57eb4edb3c55b65a), // 5^-99 + (0xaefae51477a06b03, 0xede622920b6b23f1), // 5^-98 + (0xdab99e59958885c4, 0xe95fab368e45eced), // 5^-97 + (0x88b402f7fd75539b, 0x11dbcb0218ebb414), // 5^-96 + (0xaae103b5fcd2a881, 0xd652bdc29f26a119), // 5^-95 + (0xd59944a37c0752a2, 0x4be76d3346f0495f), // 5^-94 + (0x857fcae62d8493a5, 0x6f70a4400c562ddb), // 5^-93 + (0xa6dfbd9fb8e5b88e, 0xcb4ccd500f6bb952), // 5^-92 + (0xd097ad07a71f26b2, 0x7e2000a41346a7a7), // 5^-91 + (0x825ecc24c873782f, 0x8ed400668c0c28c8), // 5^-90 + (0xa2f67f2dfa90563b, 0x728900802f0f32fa), // 5^-89 + (0xcbb41ef979346bca, 0x4f2b40a03ad2ffb9), // 5^-88 + (0xfea126b7d78186bc, 0xe2f610c84987bfa8), // 5^-87 + (0x9f24b832e6b0f436, 0xdd9ca7d2df4d7c9), // 5^-86 + (0xc6ede63fa05d3143, 0x91503d1c79720dbb), // 5^-85 + (0xf8a95fcf88747d94, 0x75a44c6397ce912a), // 5^-84 + (0x9b69dbe1b548ce7c, 0xc986afbe3ee11aba), // 5^-83 + (0xc24452da229b021b, 0xfbe85badce996168), // 5^-82 + (0xf2d56790ab41c2a2, 0xfae27299423fb9c3), // 5^-81 + (0x97c560ba6b0919a5, 0xdccd879fc967d41a), // 5^-80 + (0xbdb6b8e905cb600f, 0x5400e987bbc1c920), // 5^-79 + (0xed246723473e3813, 0x290123e9aab23b68), // 5^-78 + (0x9436c0760c86e30b, 0xf9a0b6720aaf6521), // 5^-77 + (0xb94470938fa89bce, 0xf808e40e8d5b3e69), // 5^-76 + (0xe7958cb87392c2c2, 0xb60b1d1230b20e04), // 5^-75 + (0x90bd77f3483bb9b9, 0xb1c6f22b5e6f48c2), // 5^-74 + (0xb4ecd5f01a4aa828, 0x1e38aeb6360b1af3), // 5^-73 + (0xe2280b6c20dd5232, 0x25c6da63c38de1b0), // 5^-72 + (0x8d590723948a535f, 0x579c487e5a38ad0e), // 5^-71 + (0xb0af48ec79ace837, 0x2d835a9df0c6d851), // 5^-70 + (0xdcdb1b2798182244, 0xf8e431456cf88e65), // 5^-69 + (0x8a08f0f8bf0f156b, 0x1b8e9ecb641b58ff), // 5^-68 + (0xac8b2d36eed2dac5, 0xe272467e3d222f3f), // 5^-67 + (0xd7adf884aa879177, 0x5b0ed81dcc6abb0f), // 5^-66 + (0x86ccbb52ea94baea, 0x98e947129fc2b4e9), // 5^-65 + (0xa87fea27a539e9a5, 0x3f2398d747b36224), // 5^-64 + (0xd29fe4b18e88640e, 0x8eec7f0d19a03aad), // 5^-63 + (0x83a3eeeef9153e89, 0x1953cf68300424ac), // 5^-62 + (0xa48ceaaab75a8e2b, 0x5fa8c3423c052dd7), // 5^-61 + (0xcdb02555653131b6, 0x3792f412cb06794d), // 5^-60 + (0x808e17555f3ebf11, 0xe2bbd88bbee40bd0), // 5^-59 + (0xa0b19d2ab70e6ed6, 0x5b6aceaeae9d0ec4), // 5^-58 + (0xc8de047564d20a8b, 0xf245825a5a445275), // 5^-57 + (0xfb158592be068d2e, 0xeed6e2f0f0d56712), // 5^-56 + (0x9ced737bb6c4183d, 0x55464dd69685606b), // 5^-55 + (0xc428d05aa4751e4c, 0xaa97e14c3c26b886), // 5^-54 + (0xf53304714d9265df, 0xd53dd99f4b3066a8), // 5^-53 + (0x993fe2c6d07b7fab, 0xe546a8038efe4029), // 5^-52 + (0xbf8fdb78849a5f96, 0xde98520472bdd033), // 5^-51 + (0xef73d256a5c0f77c, 0x963e66858f6d4440), // 5^-50 + (0x95a8637627989aad, 0xdde7001379a44aa8), // 5^-49 + (0xbb127c53b17ec159, 0x5560c018580d5d52), // 5^-48 + (0xe9d71b689dde71af, 0xaab8f01e6e10b4a6), // 5^-47 + (0x9226712162ab070d, 0xcab3961304ca70e8), // 5^-46 + (0xb6b00d69bb55c8d1, 0x3d607b97c5fd0d22), // 5^-45 + (0xe45c10c42a2b3b05, 0x8cb89a7db77c506a), // 5^-44 + (0x8eb98a7a9a5b04e3, 0x77f3608e92adb242), // 5^-43 + (0xb267ed1940f1c61c, 0x55f038b237591ed3), // 5^-42 + (0xdf01e85f912e37a3, 0x6b6c46dec52f6688), // 5^-41 + (0x8b61313bbabce2c6, 0x2323ac4b3b3da015), // 5^-40 + (0xae397d8aa96c1b77, 0xabec975e0a0d081a), // 5^-39 + (0xd9c7dced53c72255, 0x96e7bd358c904a21), // 5^-38 + (0x881cea14545c7575, 0x7e50d64177da2e54), // 5^-37 + (0xaa242499697392d2, 0xdde50bd1d5d0b9e9), // 5^-36 + (0xd4ad2dbfc3d07787, 0x955e4ec64b44e864), // 5^-35 + (0x84ec3c97da624ab4, 0xbd5af13bef0b113e), // 5^-34 + (0xa6274bbdd0fadd61, 0xecb1ad8aeacdd58e), // 5^-33 + (0xcfb11ead453994ba, 0x67de18eda5814af2), // 5^-32 + (0x81ceb32c4b43fcf4, 0x80eacf948770ced7), // 5^-31 + (0xa2425ff75e14fc31, 0xa1258379a94d028d), // 5^-30 + (0xcad2f7f5359a3b3e, 0x96ee45813a04330), // 5^-29 + (0xfd87b5f28300ca0d, 0x8bca9d6e188853fc), // 5^-28 + (0x9e74d1b791e07e48, 0x775ea264cf55347e), // 5^-27 + (0xc612062576589dda, 0x95364afe032a819e), // 5^-26 + (0xf79687aed3eec551, 0x3a83ddbd83f52205), // 5^-25 + (0x9abe14cd44753b52, 0xc4926a9672793543), // 5^-24 + (0xc16d9a0095928a27, 0x75b7053c0f178294), // 5^-23 + (0xf1c90080baf72cb1, 0x5324c68b12dd6339), // 5^-22 + (0x971da05074da7bee, 0xd3f6fc16ebca5e04), // 5^-21 + (0xbce5086492111aea, 0x88f4bb1ca6bcf585), // 5^-20 + (0xec1e4a7db69561a5, 0x2b31e9e3d06c32e6), // 5^-19 + (0x9392ee8e921d5d07, 0x3aff322e62439fd0), // 5^-18 + (0xb877aa3236a4b449, 0x9befeb9fad487c3), // 5^-17 + (0xe69594bec44de15b, 0x4c2ebe687989a9b4), // 5^-16 + (0x901d7cf73ab0acd9, 0xf9d37014bf60a11), // 5^-15 + (0xb424dc35095cd80f, 0x538484c19ef38c95), // 5^-14 + (0xe12e13424bb40e13, 0x2865a5f206b06fba), // 5^-13 + (0x8cbccc096f5088cb, 0xf93f87b7442e45d4), // 5^-12 + (0xafebff0bcb24aafe, 0xf78f69a51539d749), // 5^-11 + (0xdbe6fecebdedd5be, 0xb573440e5a884d1c), // 5^-10 + (0x89705f4136b4a597, 0x31680a88f8953031), // 5^-9 + (0xabcc77118461cefc, 0xfdc20d2b36ba7c3e), // 5^-8 + (0xd6bf94d5e57a42bc, 0x3d32907604691b4d), // 5^-7 + (0x8637bd05af6c69b5, 0xa63f9a49c2c1b110), // 5^-6 + (0xa7c5ac471b478423, 0xfcf80dc33721d54), // 5^-5 + (0xd1b71758e219652b, 0xd3c36113404ea4a9), // 5^-4 + (0x83126e978d4fdf3b, 0x645a1cac083126ea), // 5^-3 + (0xa3d70a3d70a3d70a, 0x3d70a3d70a3d70a4), // 5^-2 + (0xcccccccccccccccc, 0xcccccccccccccccd), // 5^-1 + (0x8000000000000000, 0x0), // 5^0 + (0xa000000000000000, 0x0), // 5^1 + (0xc800000000000000, 0x0), // 5^2 + (0xfa00000000000000, 0x0), // 5^3 + (0x9c40000000000000, 0x0), // 5^4 + (0xc350000000000000, 0x0), // 5^5 + (0xf424000000000000, 0x0), // 5^6 + (0x9896800000000000, 0x0), // 5^7 + (0xbebc200000000000, 0x0), // 5^8 + (0xee6b280000000000, 0x0), // 5^9 + (0x9502f90000000000, 0x0), // 5^10 + (0xba43b74000000000, 0x0), // 5^11 + (0xe8d4a51000000000, 0x0), // 5^12 + (0x9184e72a00000000, 0x0), // 5^13 + (0xb5e620f480000000, 0x0), // 5^14 + (0xe35fa931a0000000, 0x0), // 5^15 + (0x8e1bc9bf04000000, 0x0), // 5^16 + (0xb1a2bc2ec5000000, 0x0), // 5^17 + (0xde0b6b3a76400000, 0x0), // 5^18 + (0x8ac7230489e80000, 0x0), // 5^19 + (0xad78ebc5ac620000, 0x0), // 5^20 + (0xd8d726b7177a8000, 0x0), // 5^21 + (0x878678326eac9000, 0x0), // 5^22 + (0xa968163f0a57b400, 0x0), // 5^23 + (0xd3c21bcecceda100, 0x0), // 5^24 + (0x84595161401484a0, 0x0), // 5^25 + (0xa56fa5b99019a5c8, 0x0), // 5^26 + (0xcecb8f27f4200f3a, 0x0), // 5^27 + (0x813f3978f8940984, 0x4000000000000000), // 5^28 + (0xa18f07d736b90be5, 0x5000000000000000), // 5^29 + (0xc9f2c9cd04674ede, 0xa400000000000000), // 5^30 + (0xfc6f7c4045812296, 0x4d00000000000000), // 5^31 + (0x9dc5ada82b70b59d, 0xf020000000000000), // 5^32 + (0xc5371912364ce305, 0x6c28000000000000), // 5^33 + (0xf684df56c3e01bc6, 0xc732000000000000), // 5^34 + (0x9a130b963a6c115c, 0x3c7f400000000000), // 5^35 + (0xc097ce7bc90715b3, 0x4b9f100000000000), // 5^36 + (0xf0bdc21abb48db20, 0x1e86d40000000000), // 5^37 + (0x96769950b50d88f4, 0x1314448000000000), // 5^38 + (0xbc143fa4e250eb31, 0x17d955a000000000), // 5^39 + (0xeb194f8e1ae525fd, 0x5dcfab0800000000), // 5^40 + (0x92efd1b8d0cf37be, 0x5aa1cae500000000), // 5^41 + (0xb7abc627050305ad, 0xf14a3d9e40000000), // 5^42 + (0xe596b7b0c643c719, 0x6d9ccd05d0000000), // 5^43 + (0x8f7e32ce7bea5c6f, 0xe4820023a2000000), // 5^44 + (0xb35dbf821ae4f38b, 0xdda2802c8a800000), // 5^45 + (0xe0352f62a19e306e, 0xd50b2037ad200000), // 5^46 + (0x8c213d9da502de45, 0x4526f422cc340000), // 5^47 + (0xaf298d050e4395d6, 0x9670b12b7f410000), // 5^48 + (0xdaf3f04651d47b4c, 0x3c0cdd765f114000), // 5^49 + (0x88d8762bf324cd0f, 0xa5880a69fb6ac800), // 5^50 + (0xab0e93b6efee0053, 0x8eea0d047a457a00), // 5^51 + (0xd5d238a4abe98068, 0x72a4904598d6d880), // 5^52 + (0x85a36366eb71f041, 0x47a6da2b7f864750), // 5^53 + (0xa70c3c40a64e6c51, 0x999090b65f67d924), // 5^54 + (0xd0cf4b50cfe20765, 0xfff4b4e3f741cf6d), // 5^55 + (0x82818f1281ed449f, 0xbff8f10e7a8921a4), // 5^56 + (0xa321f2d7226895c7, 0xaff72d52192b6a0d), // 5^57 + (0xcbea6f8ceb02bb39, 0x9bf4f8a69f764490), // 5^58 + (0xfee50b7025c36a08, 0x2f236d04753d5b4), // 5^59 + (0x9f4f2726179a2245, 0x1d762422c946590), // 5^60 + (0xc722f0ef9d80aad6, 0x424d3ad2b7b97ef5), // 5^61 + (0xf8ebad2b84e0d58b, 0xd2e0898765a7deb2), // 5^62 + (0x9b934c3b330c8577, 0x63cc55f49f88eb2f), // 5^63 + (0xc2781f49ffcfa6d5, 0x3cbf6b71c76b25fb), // 5^64 + (0xf316271c7fc3908a, 0x8bef464e3945ef7a), // 5^65 + (0x97edd871cfda3a56, 0x97758bf0e3cbb5ac), // 5^66 + (0xbde94e8e43d0c8ec, 0x3d52eeed1cbea317), // 5^67 + (0xed63a231d4c4fb27, 0x4ca7aaa863ee4bdd), // 5^68 + (0x945e455f24fb1cf8, 0x8fe8caa93e74ef6a), // 5^69 + (0xb975d6b6ee39e436, 0xb3e2fd538e122b44), // 5^70 + (0xe7d34c64a9c85d44, 0x60dbbca87196b616), // 5^71 + (0x90e40fbeea1d3a4a, 0xbc8955e946fe31cd), // 5^72 + (0xb51d13aea4a488dd, 0x6babab6398bdbe41), // 5^73 + (0xe264589a4dcdab14, 0xc696963c7eed2dd1), // 5^74 + (0x8d7eb76070a08aec, 0xfc1e1de5cf543ca2), // 5^75 + (0xb0de65388cc8ada8, 0x3b25a55f43294bcb), // 5^76 + (0xdd15fe86affad912, 0x49ef0eb713f39ebe), // 5^77 + (0x8a2dbf142dfcc7ab, 0x6e3569326c784337), // 5^78 + (0xacb92ed9397bf996, 0x49c2c37f07965404), // 5^79 + (0xd7e77a8f87daf7fb, 0xdc33745ec97be906), // 5^80 + (0x86f0ac99b4e8dafd, 0x69a028bb3ded71a3), // 5^81 + (0xa8acd7c0222311bc, 0xc40832ea0d68ce0c), // 5^82 + (0xd2d80db02aabd62b, 0xf50a3fa490c30190), // 5^83 + (0x83c7088e1aab65db, 0x792667c6da79e0fa), // 5^84 + (0xa4b8cab1a1563f52, 0x577001b891185938), // 5^85 + (0xcde6fd5e09abcf26, 0xed4c0226b55e6f86), // 5^86 + (0x80b05e5ac60b6178, 0x544f8158315b05b4), // 5^87 + (0xa0dc75f1778e39d6, 0x696361ae3db1c721), // 5^88 + (0xc913936dd571c84c, 0x3bc3a19cd1e38e9), // 5^89 + (0xfb5878494ace3a5f, 0x4ab48a04065c723), // 5^90 + (0x9d174b2dcec0e47b, 0x62eb0d64283f9c76), // 5^91 + (0xc45d1df942711d9a, 0x3ba5d0bd324f8394), // 5^92 + (0xf5746577930d6500, 0xca8f44ec7ee36479), // 5^93 + (0x9968bf6abbe85f20, 0x7e998b13cf4e1ecb), // 5^94 + (0xbfc2ef456ae276e8, 0x9e3fedd8c321a67e), // 5^95 + (0xefb3ab16c59b14a2, 0xc5cfe94ef3ea101e), // 5^96 + (0x95d04aee3b80ece5, 0xbba1f1d158724a12), // 5^97 + (0xbb445da9ca61281f, 0x2a8a6e45ae8edc97), // 5^98 + (0xea1575143cf97226, 0xf52d09d71a3293bd), // 5^99 + (0x924d692ca61be758, 0x593c2626705f9c56), // 5^100 + (0xb6e0c377cfa2e12e, 0x6f8b2fb00c77836c), // 5^101 + (0xe498f455c38b997a, 0xb6dfb9c0f956447), // 5^102 + (0x8edf98b59a373fec, 0x4724bd4189bd5eac), // 5^103 + (0xb2977ee300c50fe7, 0x58edec91ec2cb657), // 5^104 + (0xdf3d5e9bc0f653e1, 0x2f2967b66737e3ed), // 5^105 + (0x8b865b215899f46c, 0xbd79e0d20082ee74), // 5^106 + (0xae67f1e9aec07187, 0xecd8590680a3aa11), // 5^107 + (0xda01ee641a708de9, 0xe80e6f4820cc9495), // 5^108 + (0x884134fe908658b2, 0x3109058d147fdcdd), // 5^109 + (0xaa51823e34a7eede, 0xbd4b46f0599fd415), // 5^110 + (0xd4e5e2cdc1d1ea96, 0x6c9e18ac7007c91a), // 5^111 + (0x850fadc09923329e, 0x3e2cf6bc604ddb0), // 5^112 + (0xa6539930bf6bff45, 0x84db8346b786151c), // 5^113 + (0xcfe87f7cef46ff16, 0xe612641865679a63), // 5^114 + (0x81f14fae158c5f6e, 0x4fcb7e8f3f60c07e), // 5^115 + (0xa26da3999aef7749, 0xe3be5e330f38f09d), // 5^116 + (0xcb090c8001ab551c, 0x5cadf5bfd3072cc5), // 5^117 + (0xfdcb4fa002162a63, 0x73d9732fc7c8f7f6), // 5^118 + (0x9e9f11c4014dda7e, 0x2867e7fddcdd9afa), // 5^119 + (0xc646d63501a1511d, 0xb281e1fd541501b8), // 5^120 + (0xf7d88bc24209a565, 0x1f225a7ca91a4226), // 5^121 + (0x9ae757596946075f, 0x3375788de9b06958), // 5^122 + (0xc1a12d2fc3978937, 0x52d6b1641c83ae), // 5^123 + (0xf209787bb47d6b84, 0xc0678c5dbd23a49a), // 5^124 + (0x9745eb4d50ce6332, 0xf840b7ba963646e0), // 5^125 + (0xbd176620a501fbff, 0xb650e5a93bc3d898), // 5^126 + (0xec5d3fa8ce427aff, 0xa3e51f138ab4cebe), // 5^127 + (0x93ba47c980e98cdf, 0xc66f336c36b10137), // 5^128 + (0xb8a8d9bbe123f017, 0xb80b0047445d4184), // 5^129 + (0xe6d3102ad96cec1d, 0xa60dc059157491e5), // 5^130 + (0x9043ea1ac7e41392, 0x87c89837ad68db2f), // 5^131 + (0xb454e4a179dd1877, 0x29babe4598c311fb), // 5^132 + (0xe16a1dc9d8545e94, 0xf4296dd6fef3d67a), // 5^133 + (0x8ce2529e2734bb1d, 0x1899e4a65f58660c), // 5^134 + (0xb01ae745b101e9e4, 0x5ec05dcff72e7f8f), // 5^135 + (0xdc21a1171d42645d, 0x76707543f4fa1f73), // 5^136 + (0x899504ae72497eba, 0x6a06494a791c53a8), // 5^137 + (0xabfa45da0edbde69, 0x487db9d17636892), // 5^138 + (0xd6f8d7509292d603, 0x45a9d2845d3c42b6), // 5^139 + (0x865b86925b9bc5c2, 0xb8a2392ba45a9b2), // 5^140 + (0xa7f26836f282b732, 0x8e6cac7768d7141e), // 5^141 + (0xd1ef0244af2364ff, 0x3207d795430cd926), // 5^142 + (0x8335616aed761f1f, 0x7f44e6bd49e807b8), // 5^143 + (0xa402b9c5a8d3a6e7, 0x5f16206c9c6209a6), // 5^144 + (0xcd036837130890a1, 0x36dba887c37a8c0f), // 5^145 + (0x802221226be55a64, 0xc2494954da2c9789), // 5^146 + (0xa02aa96b06deb0fd, 0xf2db9baa10b7bd6c), // 5^147 + (0xc83553c5c8965d3d, 0x6f92829494e5acc7), // 5^148 + (0xfa42a8b73abbf48c, 0xcb772339ba1f17f9), // 5^149 + (0x9c69a97284b578d7, 0xff2a760414536efb), // 5^150 + (0xc38413cf25e2d70d, 0xfef5138519684aba), // 5^151 + (0xf46518c2ef5b8cd1, 0x7eb258665fc25d69), // 5^152 + (0x98bf2f79d5993802, 0xef2f773ffbd97a61), // 5^153 + (0xbeeefb584aff8603, 0xaafb550ffacfd8fa), // 5^154 + (0xeeaaba2e5dbf6784, 0x95ba2a53f983cf38), // 5^155 + (0x952ab45cfa97a0b2, 0xdd945a747bf26183), // 5^156 + (0xba756174393d88df, 0x94f971119aeef9e4), // 5^157 + (0xe912b9d1478ceb17, 0x7a37cd5601aab85d), // 5^158 + (0x91abb422ccb812ee, 0xac62e055c10ab33a), // 5^159 + (0xb616a12b7fe617aa, 0x577b986b314d6009), // 5^160 + (0xe39c49765fdf9d94, 0xed5a7e85fda0b80b), // 5^161 + (0x8e41ade9fbebc27d, 0x14588f13be847307), // 5^162 + (0xb1d219647ae6b31c, 0x596eb2d8ae258fc8), // 5^163 + (0xde469fbd99a05fe3, 0x6fca5f8ed9aef3bb), // 5^164 + (0x8aec23d680043bee, 0x25de7bb9480d5854), // 5^165 + (0xada72ccc20054ae9, 0xaf561aa79a10ae6a), // 5^166 + (0xd910f7ff28069da4, 0x1b2ba1518094da04), // 5^167 + (0x87aa9aff79042286, 0x90fb44d2f05d0842), // 5^168 + (0xa99541bf57452b28, 0x353a1607ac744a53), // 5^169 + (0xd3fa922f2d1675f2, 0x42889b8997915ce8), // 5^170 + (0x847c9b5d7c2e09b7, 0x69956135febada11), // 5^171 + (0xa59bc234db398c25, 0x43fab9837e699095), // 5^172 + (0xcf02b2c21207ef2e, 0x94f967e45e03f4bb), // 5^173 + (0x8161afb94b44f57d, 0x1d1be0eebac278f5), // 5^174 + (0xa1ba1ba79e1632dc, 0x6462d92a69731732), // 5^175 + (0xca28a291859bbf93, 0x7d7b8f7503cfdcfe), // 5^176 + (0xfcb2cb35e702af78, 0x5cda735244c3d43e), // 5^177 + (0x9defbf01b061adab, 0x3a0888136afa64a7), // 5^178 + (0xc56baec21c7a1916, 0x88aaa1845b8fdd0), // 5^179 + (0xf6c69a72a3989f5b, 0x8aad549e57273d45), // 5^180 + (0x9a3c2087a63f6399, 0x36ac54e2f678864b), // 5^181 + (0xc0cb28a98fcf3c7f, 0x84576a1bb416a7dd), // 5^182 + (0xf0fdf2d3f3c30b9f, 0x656d44a2a11c51d5), // 5^183 + (0x969eb7c47859e743, 0x9f644ae5a4b1b325), // 5^184 + (0xbc4665b596706114, 0x873d5d9f0dde1fee), // 5^185 + (0xeb57ff22fc0c7959, 0xa90cb506d155a7ea), // 5^186 + (0x9316ff75dd87cbd8, 0x9a7f12442d588f2), // 5^187 + (0xb7dcbf5354e9bece, 0xc11ed6d538aeb2f), // 5^188 + (0xe5d3ef282a242e81, 0x8f1668c8a86da5fa), // 5^189 + (0x8fa475791a569d10, 0xf96e017d694487bc), // 5^190 + (0xb38d92d760ec4455, 0x37c981dcc395a9ac), // 5^191 + (0xe070f78d3927556a, 0x85bbe253f47b1417), // 5^192 + (0x8c469ab843b89562, 0x93956d7478ccec8e), // 5^193 + (0xaf58416654a6babb, 0x387ac8d1970027b2), // 5^194 + (0xdb2e51bfe9d0696a, 0x6997b05fcc0319e), // 5^195 + (0x88fcf317f22241e2, 0x441fece3bdf81f03), // 5^196 + (0xab3c2fddeeaad25a, 0xd527e81cad7626c3), // 5^197 + (0xd60b3bd56a5586f1, 0x8a71e223d8d3b074), // 5^198 + (0x85c7056562757456, 0xf6872d5667844e49), // 5^199 + (0xa738c6bebb12d16c, 0xb428f8ac016561db), // 5^200 + (0xd106f86e69d785c7, 0xe13336d701beba52), // 5^201 + (0x82a45b450226b39c, 0xecc0024661173473), // 5^202 + (0xa34d721642b06084, 0x27f002d7f95d0190), // 5^203 + (0xcc20ce9bd35c78a5, 0x31ec038df7b441f4), // 5^204 + (0xff290242c83396ce, 0x7e67047175a15271), // 5^205 + (0x9f79a169bd203e41, 0xf0062c6e984d386), // 5^206 + (0xc75809c42c684dd1, 0x52c07b78a3e60868), // 5^207 + (0xf92e0c3537826145, 0xa7709a56ccdf8a82), // 5^208 + (0x9bbcc7a142b17ccb, 0x88a66076400bb691), // 5^209 + (0xc2abf989935ddbfe, 0x6acff893d00ea435), // 5^210 + (0xf356f7ebf83552fe, 0x583f6b8c4124d43), // 5^211 + (0x98165af37b2153de, 0xc3727a337a8b704a), // 5^212 + (0xbe1bf1b059e9a8d6, 0x744f18c0592e4c5c), // 5^213 + (0xeda2ee1c7064130c, 0x1162def06f79df73), // 5^214 + (0x9485d4d1c63e8be7, 0x8addcb5645ac2ba8), // 5^215 + (0xb9a74a0637ce2ee1, 0x6d953e2bd7173692), // 5^216 + (0xe8111c87c5c1ba99, 0xc8fa8db6ccdd0437), // 5^217 + (0x910ab1d4db9914a0, 0x1d9c9892400a22a2), // 5^218 + (0xb54d5e4a127f59c8, 0x2503beb6d00cab4b), // 5^219 + (0xe2a0b5dc971f303a, 0x2e44ae64840fd61d), // 5^220 + (0x8da471a9de737e24, 0x5ceaecfed289e5d2), // 5^221 + (0xb10d8e1456105dad, 0x7425a83e872c5f47), // 5^222 + (0xdd50f1996b947518, 0xd12f124e28f77719), // 5^223 + (0x8a5296ffe33cc92f, 0x82bd6b70d99aaa6f), // 5^224 + (0xace73cbfdc0bfb7b, 0x636cc64d1001550b), // 5^225 + (0xd8210befd30efa5a, 0x3c47f7e05401aa4e), // 5^226 + (0x8714a775e3e95c78, 0x65acfaec34810a71), // 5^227 + (0xa8d9d1535ce3b396, 0x7f1839a741a14d0d), // 5^228 + (0xd31045a8341ca07c, 0x1ede48111209a050), // 5^229 + (0x83ea2b892091e44d, 0x934aed0aab460432), // 5^230 + (0xa4e4b66b68b65d60, 0xf81da84d5617853f), // 5^231 + (0xce1de40642e3f4b9, 0x36251260ab9d668e), // 5^232 + (0x80d2ae83e9ce78f3, 0xc1d72b7c6b426019), // 5^233 + (0xa1075a24e4421730, 0xb24cf65b8612f81f), // 5^234 + (0xc94930ae1d529cfc, 0xdee033f26797b627), // 5^235 + (0xfb9b7cd9a4a7443c, 0x169840ef017da3b1), // 5^236 + (0x9d412e0806e88aa5, 0x8e1f289560ee864e), // 5^237 + (0xc491798a08a2ad4e, 0xf1a6f2bab92a27e2), // 5^238 + (0xf5b5d7ec8acb58a2, 0xae10af696774b1db), // 5^239 + (0x9991a6f3d6bf1765, 0xacca6da1e0a8ef29), // 5^240 + (0xbff610b0cc6edd3f, 0x17fd090a58d32af3), // 5^241 + (0xeff394dcff8a948e, 0xddfc4b4cef07f5b0), // 5^242 + (0x95f83d0a1fb69cd9, 0x4abdaf101564f98e), // 5^243 + (0xbb764c4ca7a4440f, 0x9d6d1ad41abe37f1), // 5^244 + (0xea53df5fd18d5513, 0x84c86189216dc5ed), // 5^245 + (0x92746b9be2f8552c, 0x32fd3cf5b4e49bb4), // 5^246 + (0xb7118682dbb66a77, 0x3fbc8c33221dc2a1), // 5^247 + (0xe4d5e82392a40515, 0xfabaf3feaa5334a), // 5^248 + (0x8f05b1163ba6832d, 0x29cb4d87f2a7400e), // 5^249 + (0xb2c71d5bca9023f8, 0x743e20e9ef511012), // 5^250 + (0xdf78e4b2bd342cf6, 0x914da9246b255416), // 5^251 + (0x8bab8eefb6409c1a, 0x1ad089b6c2f7548e), // 5^252 + (0xae9672aba3d0c320, 0xa184ac2473b529b1), // 5^253 + (0xda3c0f568cc4f3e8, 0xc9e5d72d90a2741e), // 5^254 + (0x8865899617fb1871, 0x7e2fa67c7a658892), // 5^255 + (0xaa7eebfb9df9de8d, 0xddbb901b98feeab7), // 5^256 + (0xd51ea6fa85785631, 0x552a74227f3ea565), // 5^257 + (0x8533285c936b35de, 0xd53a88958f87275f), // 5^258 + (0xa67ff273b8460356, 0x8a892abaf368f137), // 5^259 + (0xd01fef10a657842c, 0x2d2b7569b0432d85), // 5^260 + (0x8213f56a67f6b29b, 0x9c3b29620e29fc73), // 5^261 + (0xa298f2c501f45f42, 0x8349f3ba91b47b8f), // 5^262 + (0xcb3f2f7642717713, 0x241c70a936219a73), // 5^263 + (0xfe0efb53d30dd4d7, 0xed238cd383aa0110), // 5^264 + (0x9ec95d1463e8a506, 0xf4363804324a40aa), // 5^265 + (0xc67bb4597ce2ce48, 0xb143c6053edcd0d5), // 5^266 + (0xf81aa16fdc1b81da, 0xdd94b7868e94050a), // 5^267 + (0x9b10a4e5e9913128, 0xca7cf2b4191c8326), // 5^268 + (0xc1d4ce1f63f57d72, 0xfd1c2f611f63a3f0), // 5^269 + (0xf24a01a73cf2dccf, 0xbc633b39673c8cec), // 5^270 + (0x976e41088617ca01, 0xd5be0503e085d813), // 5^271 + (0xbd49d14aa79dbc82, 0x4b2d8644d8a74e18), // 5^272 + (0xec9c459d51852ba2, 0xddf8e7d60ed1219e), // 5^273 + (0x93e1ab8252f33b45, 0xcabb90e5c942b503), // 5^274 + (0xb8da1662e7b00a17, 0x3d6a751f3b936243), // 5^275 + (0xe7109bfba19c0c9d, 0xcc512670a783ad4), // 5^276 + (0x906a617d450187e2, 0x27fb2b80668b24c5), // 5^277 + (0xb484f9dc9641e9da, 0xb1f9f660802dedf6), // 5^278 + (0xe1a63853bbd26451, 0x5e7873f8a0396973), // 5^279 + (0x8d07e33455637eb2, 0xdb0b487b6423e1e8), // 5^280 + (0xb049dc016abc5e5f, 0x91ce1a9a3d2cda62), // 5^281 + (0xdc5c5301c56b75f7, 0x7641a140cc7810fb), // 5^282 + (0x89b9b3e11b6329ba, 0xa9e904c87fcb0a9d), // 5^283 + (0xac2820d9623bf429, 0x546345fa9fbdcd44), // 5^284 + (0xd732290fbacaf133, 0xa97c177947ad4095), // 5^285 + (0x867f59a9d4bed6c0, 0x49ed8eabcccc485d), // 5^286 + (0xa81f301449ee8c70, 0x5c68f256bfff5a74), // 5^287 + (0xd226fc195c6a2f8c, 0x73832eec6fff3111), // 5^288 + (0x83585d8fd9c25db7, 0xc831fd53c5ff7eab), // 5^289 + (0xa42e74f3d032f525, 0xba3e7ca8b77f5e55), // 5^290 + (0xcd3a1230c43fb26f, 0x28ce1bd2e55f35eb), // 5^291 + (0x80444b5e7aa7cf85, 0x7980d163cf5b81b3), // 5^292 + (0xa0555e361951c366, 0xd7e105bcc332621f), // 5^293 + (0xc86ab5c39fa63440, 0x8dd9472bf3fefaa7), // 5^294 + (0xfa856334878fc150, 0xb14f98f6f0feb951), // 5^295 + (0x9c935e00d4b9d8d2, 0x6ed1bf9a569f33d3), // 5^296 + (0xc3b8358109e84f07, 0xa862f80ec4700c8), // 5^297 + (0xf4a642e14c6262c8, 0xcd27bb612758c0fa), // 5^298 + (0x98e7e9cccfbd7dbd, 0x8038d51cb897789c), // 5^299 + (0xbf21e44003acdd2c, 0xe0470a63e6bd56c3), // 5^300 + (0xeeea5d5004981478, 0x1858ccfce06cac74), // 5^301 + (0x95527a5202df0ccb, 0xf37801e0c43ebc8), // 5^302 + (0xbaa718e68396cffd, 0xd30560258f54e6ba), // 5^303 + (0xe950df20247c83fd, 0x47c6b82ef32a2069), // 5^304 + (0x91d28b7416cdd27e, 0x4cdc331d57fa5441), // 5^305 + (0xb6472e511c81471d, 0xe0133fe4adf8e952), // 5^306 + (0xe3d8f9e563a198e5, 0x58180fddd97723a6), // 5^307 + (0x8e679c2f5e44ff8f, 0x570f09eaa7ea7648), // 5^308 ]; diff --git a/library/core/src/num/flt2dec/decoder.rs b/library/core/src/num/flt2dec/decoder.rs index c43536c6fcc..5763860540a 100644 --- a/library/core/src/num/flt2dec/decoder.rs +++ b/library/core/src/num/flt2dec/decoder.rs @@ -1,6 +1,6 @@ //! Decodes a floating-point value into individual parts and error ranges. -use crate::num::dec2flt::rawfp::RawFloat; +use crate::num::dec2flt::float::RawFloat; use crate::num::FpCategory; /// Decoded unsigned finite value, such that: diff --git a/library/core/tests/num/dec2flt/float.rs b/library/core/tests/num/dec2flt/float.rs new file mode 100644 index 00000000000..7a9587a18d0 --- /dev/null +++ b/library/core/tests/num/dec2flt/float.rs @@ -0,0 +1,33 @@ +use core::num::dec2flt::float::RawFloat; + +#[test] +fn test_f32_integer_decode() { + assert_eq!(3.14159265359f32.integer_decode(), (13176795, -22, 1)); + assert_eq!((-8573.5918555f32).integer_decode(), (8779358, -10, -1)); + assert_eq!(2f32.powf(100.0).integer_decode(), (8388608, 77, 1)); + assert_eq!(0f32.integer_decode(), (0, -150, 1)); + assert_eq!((-0f32).integer_decode(), (0, -150, -1)); + assert_eq!(f32::INFINITY.integer_decode(), (8388608, 105, 1)); + assert_eq!(f32::NEG_INFINITY.integer_decode(), (8388608, 105, -1)); + + // Ignore the "sign" (quiet / signalling flag) of NAN. + // It can vary between runtime operations and LLVM folding. + let (nan_m, nan_e, _nan_s) = f32::NAN.integer_decode(); + assert_eq!((nan_m, nan_e), (12582912, 105)); +} + +#[test] +fn test_f64_integer_decode() { + assert_eq!(3.14159265359f64.integer_decode(), (7074237752028906, -51, 1)); + assert_eq!((-8573.5918555f64).integer_decode(), (4713381968463931, -39, -1)); + assert_eq!(2f64.powf(100.0).integer_decode(), (4503599627370496, 48, 1)); + assert_eq!(0f64.integer_decode(), (0, -1075, 1)); + assert_eq!((-0f64).integer_decode(), (0, -1075, -1)); + assert_eq!(f64::INFINITY.integer_decode(), (4503599627370496, 972, 1)); + assert_eq!(f64::NEG_INFINITY.integer_decode(), (4503599627370496, 972, -1)); + + // Ignore the "sign" (quiet / signalling flag) of NAN. + // It can vary between runtime operations and LLVM folding. + let (nan_m, nan_e, _nan_s) = f64::NAN.integer_decode(); + assert_eq!((nan_m, nan_e), (6755399441055744, 972)); +} diff --git a/library/core/tests/num/dec2flt/lemire.rs b/library/core/tests/num/dec2flt/lemire.rs new file mode 100644 index 00000000000..f71bbb7c7a3 --- /dev/null +++ b/library/core/tests/num/dec2flt/lemire.rs @@ -0,0 +1,53 @@ +use core::num::dec2flt::lemire::compute_float; + +fn compute_float32(q: i64, w: u64) -> (i32, u64) { + let fp = compute_float::<f32>(q, w); + (fp.e, fp.f) +} + +fn compute_float64(q: i64, w: u64) -> (i32, u64) { + let fp = compute_float::<f64>(q, w); + (fp.e, fp.f) +} + +#[test] +fn compute_float_f32_rounding() { + // These test near-halfway cases for single-precision floats. + assert_eq!(compute_float32(0, 16777216), (151, 0)); + assert_eq!(compute_float32(0, 16777217), (151, 0)); + assert_eq!(compute_float32(0, 16777218), (151, 1)); + assert_eq!(compute_float32(0, 16777219), (151, 2)); + assert_eq!(compute_float32(0, 16777220), (151, 2)); + + // These are examples of the above tests, with + // digits from the exponent shifted to the mantissa. + assert_eq!(compute_float32(-10, 167772160000000000), (151, 0)); + assert_eq!(compute_float32(-10, 167772170000000000), (151, 0)); + assert_eq!(compute_float32(-10, 167772180000000000), (151, 1)); + // Let's check the lines to see if anything is different in table... + assert_eq!(compute_float32(-10, 167772190000000000), (151, 2)); + assert_eq!(compute_float32(-10, 167772200000000000), (151, 2)); +} + +#[test] +fn compute_float_f64_rounding() { + // These test near-halfway cases for double-precision floats. + assert_eq!(compute_float64(0, 9007199254740992), (1076, 0)); + assert_eq!(compute_float64(0, 9007199254740993), (1076, 0)); + assert_eq!(compute_float64(0, 9007199254740994), (1076, 1)); + assert_eq!(compute_float64(0, 9007199254740995), (1076, 2)); + assert_eq!(compute_float64(0, 9007199254740996), (1076, 2)); + assert_eq!(compute_float64(0, 18014398509481984), (1077, 0)); + assert_eq!(compute_float64(0, 18014398509481986), (1077, 0)); + assert_eq!(compute_float64(0, 18014398509481988), (1077, 1)); + assert_eq!(compute_float64(0, 18014398509481990), (1077, 2)); + assert_eq!(compute_float64(0, 18014398509481992), (1077, 2)); + + // These are examples of the above tests, with + // digits from the exponent shifted to the mantissa. + assert_eq!(compute_float64(-3, 9007199254740992000), (1076, 0)); + assert_eq!(compute_float64(-3, 9007199254740993000), (1076, 0)); + assert_eq!(compute_float64(-3, 9007199254740994000), (1076, 1)); + assert_eq!(compute_float64(-3, 9007199254740995000), (1076, 2)); + assert_eq!(compute_float64(-3, 9007199254740996000), (1076, 2)); +} diff --git a/library/core/tests/num/dec2flt/mod.rs b/library/core/tests/num/dec2flt/mod.rs index 32f05d1def5..4990d4a083d 100644 --- a/library/core/tests/num/dec2flt/mod.rs +++ b/library/core/tests/num/dec2flt/mod.rs @@ -1,7 +1,8 @@ #![allow(overflowing_literals)] +mod float; +mod lemire; mod parse; -mod rawfp; // Take a float literal, turn it into a string in various ways (that are all trusted // to be correct) and see if those strings are parsed back to the value of the literal. @@ -28,12 +29,6 @@ fn ordinary() { test_literal!(0.1); test_literal!(12345.); test_literal!(0.9999999); - - if cfg!(miri) { - // Miri is too slow - return; - } - test_literal!(2.2250738585072014e-308); } @@ -54,7 +49,6 @@ fn large() { } #[test] -#[cfg_attr(miri, ignore)] // Miri is too slow fn subnormals() { test_literal!(5e-324); test_literal!(91e-324); @@ -66,7 +60,6 @@ fn subnormals() { } #[test] -#[cfg_attr(miri, ignore)] // Miri is too slow fn infinity() { test_literal!(1e400); test_literal!(1e309); @@ -78,12 +71,6 @@ fn infinity() { fn zero() { test_literal!(0.0); test_literal!(1e-325); - - if cfg!(miri) { - // Miri is too slow - return; - } - test_literal!(1e-326); test_literal!(1e-500); } diff --git a/library/core/tests/num/dec2flt/parse.rs b/library/core/tests/num/dec2flt/parse.rs index bb7e51d3002..473feacc91f 100644 --- a/library/core/tests/num/dec2flt/parse.rs +++ b/library/core/tests/num/dec2flt/parse.rs @@ -1,17 +1,23 @@ -use core::num::dec2flt::parse::ParseResult::{Invalid, Valid}; -use core::num::dec2flt::parse::{parse_decimal, Decimal}; +use core::num::dec2flt::number::Number; +use core::num::dec2flt::parse::parse_number; +use core::num::dec2flt::{dec2flt, pfe_invalid}; + +fn new_number(e: i64, m: u64) -> Number { + Number { exponent: e, mantissa: m, negative: false, many_digits: false } +} #[test] fn missing_pieces() { let permutations = &[".e", "1e", "e4", "e", ".12e", "321.e", "32.12e+", "12.32e-"]; for &s in permutations { - assert_eq!(parse_decimal(s), Invalid); + assert_eq!(dec2flt::<f64>(s), Err(pfe_invalid())); } } #[test] fn invalid_chars() { let invalid = "r,?<j"; + let error = Err(pfe_invalid()); let valid_strings = &["123", "666.", ".1", "5e1", "7e-3", "0.0e+1"]; for c in invalid.chars() { for s in valid_strings { @@ -19,23 +25,153 @@ fn invalid_chars() { let mut input = String::new(); input.push_str(s); input.insert(i, c); - assert!(parse_decimal(&input) == Invalid, "did not reject invalid {:?}", input); + assert!(dec2flt::<f64>(&input) == error, "did not reject invalid {:?}", input); } } } } +fn parse_positive(s: &[u8]) -> Option<Number> { + parse_number(s, false) +} + #[test] fn valid() { - assert_eq!(parse_decimal("123.456e789"), Valid(Decimal::new(b"123", b"456", 789))); - assert_eq!(parse_decimal("123.456e+789"), Valid(Decimal::new(b"123", b"456", 789))); - assert_eq!(parse_decimal("123.456e-789"), Valid(Decimal::new(b"123", b"456", -789))); - assert_eq!(parse_decimal(".050"), Valid(Decimal::new(b"", b"050", 0))); - assert_eq!(parse_decimal("999"), Valid(Decimal::new(b"999", b"", 0))); - assert_eq!(parse_decimal("1.e300"), Valid(Decimal::new(b"1", b"", 300))); - assert_eq!(parse_decimal(".1e300"), Valid(Decimal::new(b"", b"1", 300))); - assert_eq!(parse_decimal("101e-33"), Valid(Decimal::new(b"101", b"", -33))); + assert_eq!(parse_positive(b"123.456e789"), Some(new_number(786, 123456))); + assert_eq!(parse_positive(b"123.456e+789"), Some(new_number(786, 123456))); + assert_eq!(parse_positive(b"123.456e-789"), Some(new_number(-792, 123456))); + assert_eq!(parse_positive(b".050"), Some(new_number(-3, 50))); + assert_eq!(parse_positive(b"999"), Some(new_number(0, 999))); + assert_eq!(parse_positive(b"1.e300"), Some(new_number(300, 1))); + assert_eq!(parse_positive(b".1e300"), Some(new_number(299, 1))); + assert_eq!(parse_positive(b"101e-33"), Some(new_number(-33, 101))); let zeros = "0".repeat(25); let s = format!("1.5e{}", zeros); - assert_eq!(parse_decimal(&s), Valid(Decimal::new(b"1", b"5", 0))); + assert_eq!(parse_positive(s.as_bytes()), Some(new_number(-1, 15))); +} + +macro_rules! assert_float_result_bits_eq { + ($bits:literal, $ty:ty, $str:literal) => {{ + let p = dec2flt::<$ty>($str); + assert_eq!(p.map(|x| x.to_bits()), Ok($bits)); + }}; +} + +#[test] +fn issue31109() { + // Regression test for #31109. + // Ensure the test produces a valid float with the expected bit pattern. + assert_float_result_bits_eq!( + 0x3fd5555555555555, + f64, + "0.3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333" + ); +} + +#[test] +fn issue31407() { + // Regression test for #31407. + // Ensure the test produces a valid float with the expected bit pattern. + assert_float_result_bits_eq!( + 0x1752a64e34ba0d3, + f64, + "1234567890123456789012345678901234567890e-340" + ); + assert_float_result_bits_eq!( + 0xfffffffffffff, + f64, + "2.225073858507201136057409796709131975934819546351645648023426109724822222021076945516529523908135087914149158913039621106870086438694594645527657207407820621743379988141063267329253552286881372149012981122451451889849057222307285255133155755015914397476397983411801999323962548289017107081850690630666655994938275772572015763062690663332647565300009245888316433037779791869612049497390377829704905051080609940730262937128958950003583799967207254304360284078895771796150945516748243471030702609144621572289880258182545180325707018860872113128079512233426288368622321503775666622503982534335974568884423900265498198385487948292206894721689831099698365846814022854243330660339850886445804001034933970427567186443383770486037861622771738545623065874679014086723327636718749999999999999999999999999999999999999e-308" + ); + assert_float_result_bits_eq!( + 0x10000000000000, + f64, + "2.22507385850720113605740979670913197593481954635164564802342610972482222202107694551652952390813508791414915891303962110687008643869459464552765720740782062174337998814106326732925355228688137214901298112245145188984905722230728525513315575501591439747639798341180199932396254828901710708185069063066665599493827577257201576306269066333264756530000924588831643303777979186961204949739037782970490505108060994073026293712895895000358379996720725430436028407889577179615094551674824347103070260914462157228988025818254518032570701886087211312807951223342628836862232150377566662250398253433597456888442390026549819838548794829220689472168983109969836584681402285424333066033985088644580400103493397042756718644338377048603786162277173854562306587467901408672332763671875e-308" + ); + assert_float_result_bits_eq!( + 0x10000000000000, + f64, + "0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000222507385850720138309023271733240406421921598046233183055332741688720443481391819585428315901251102056406733973103581100515243416155346010885601238537771882113077799353200233047961014744258363607192156504694250373420837525080665061665815894872049117996859163964850063590877011830487479978088775374994945158045160505091539985658247081864511353793580499211598108576605199243335211435239014879569960959128889160299264151106346631339366347758651302937176204732563178148566435087212282863764204484681140761391147706280168985324411002416144742161856716615054015428508471675290190316132277889672970737312333408698898317506783884692609277397797285865965494109136909540613646756870239867831529068098461721092462539672851562500000000000000001" + ); + assert_float_result_bits_eq!( + 0x7fefffffffffffff, + f64, + "179769313486231580793728971405303415079934132710037826936173778980444968292764750946649017977587207096330286416692887910946555547851940402630657488671505820681908902000708383676273854845817711531764475730270069855571366959622842914819860834936475292719074168444365510704342711559699508093042880177904174497791.9999999999999999999999999999999999999999999999999999999999999999999999" + ); + assert_float_result_bits_eq!(0x0, f64, "2.47032822920623272e-324"); + assert_float_result_bits_eq!( + 0x8000000, + f64, + "6.631236871469758276785396630275967243399099947355303144249971758736286630139265439618068200788048744105960420552601852889715006376325666595539603330361800519107591783233358492337208057849499360899425128640718856616503093444922854759159988160304439909868291973931426625698663157749836252274523485312442358651207051292453083278116143932569727918709786004497872322193856150225415211997283078496319412124640111777216148110752815101775295719811974338451936095907419622417538473679495148632480391435931767981122396703443803335529756003353209830071832230689201383015598792184172909927924176339315507402234836120730914783168400715462440053817592702766213559042115986763819482654128770595766806872783349146967171293949598850675682115696218943412532098591327667236328125E-316" + ); + assert_float_result_bits_eq!( + 0x10000, + f64, + "3.237883913302901289588352412501532174863037669423108059901297049552301970670676565786835742587799557860615776559838283435514391084153169252689190564396459577394618038928365305143463955100356696665629202017331344031730044369360205258345803431471660032699580731300954848363975548690010751530018881758184174569652173110473696022749934638425380623369774736560008997404060967498028389191878963968575439222206416981462690113342524002724385941651051293552601421155333430225237291523843322331326138431477823591142408800030775170625915670728657003151953664260769822494937951845801530895238439819708403389937873241463484205608000027270531106827387907791444918534771598750162812548862768493201518991668028251730299953143924168545708663913273994694463908672332763671875E-319" + ); + assert_float_result_bits_eq!( + 0x800000000100, + f64, + "6.953355807847677105972805215521891690222119817145950754416205607980030131549636688806115726399441880065386399864028691275539539414652831584795668560082999889551357784961446896042113198284213107935110217162654939802416034676213829409720583759540476786936413816541621287843248433202369209916612249676005573022703244799714622116542188837770376022371172079559125853382801396219552418839469770514904192657627060319372847562301074140442660237844114174497210955449896389180395827191602886654488182452409583981389442783377001505462015745017848754574668342161759496661766020028752888783387074850773192997102997936619876226688096314989645766000479009083731736585750335262099860150896718774401964796827166283225641992040747894382698751809812609536720628966577351093292236328125E-310" + ); + assert_float_result_bits_eq!( + 0x10800, + f64, + "3.339068557571188581835713701280943911923401916998521771655656997328440314559615318168849149074662609099998113009465566426808170378434065722991659642619467706034884424989741080790766778456332168200464651593995817371782125010668346652995912233993254584461125868481633343674905074271064409763090708017856584019776878812425312008812326260363035474811532236853359905334625575404216060622858633280744301892470300555678734689978476870369853549413277156622170245846166991655321535529623870646888786637528995592800436177901746286272273374471701452991433047257863864601424252024791567368195056077320885329384322332391564645264143400798619665040608077549162173963649264049738362290606875883456826586710961041737908872035803481241600376705491726170293986797332763671875E-319" + ); + assert_float_result_bits_eq!( + 0x0, + f64, + "2.4703282292062327208828439643411068618252990130716238221279284125033775363510437593264991818081799618989828234772285886546332835517796989819938739800539093906315035659515570226392290858392449105184435931802849936536152500319370457678249219365623669863658480757001585769269903706311928279558551332927834338409351978015531246597263579574622766465272827220056374006485499977096599470454020828166226237857393450736339007967761930577506740176324673600968951340535537458516661134223766678604162159680461914467291840300530057530849048765391711386591646239524912623653881879636239373280423891018672348497668235089863388587925628302755995657524455507255189313690836254779186948667994968324049705821028513185451396213837722826145437693412532098591327667236328124999e-324" + ); + assert_float_result_bits_eq!( + 0x0, + f64, + "2.4703282292062327208828439643411068618252990130716238221279284125033775363510437593264991818081799618989828234772285886546332835517796989819938739800539093906315035659515570226392290858392449105184435931802849936536152500319370457678249219365623669863658480757001585769269903706311928279558551332927834338409351978015531246597263579574622766465272827220056374006485499977096599470454020828166226237857393450736339007967761930577506740176324673600968951340535537458516661134223766678604162159680461914467291840300530057530849048765391711386591646239524912623653881879636239373280423891018672348497668235089863388587925628302755995657524455507255189313690836254779186948667994968324049705821028513185451396213837722826145437693412532098591327667236328125e-324" + ); + assert_float_result_bits_eq!( + 0x1, + f64, + "2.4703282292062327208828439643411068618252990130716238221279284125033775363510437593264991818081799618989828234772285886546332835517796989819938739800539093906315035659515570226392290858392449105184435931802849936536152500319370457678249219365623669863658480757001585769269903706311928279558551332927834338409351978015531246597263579574622766465272827220056374006485499977096599470454020828166226237857393450736339007967761930577506740176324673600968951340535537458516661134223766678604162159680461914467291840300530057530849048765391711386591646239524912623653881879636239373280423891018672348497668235089863388587925628302755995657524455507255189313690836254779186948667994968324049705821028513185451396213837722826145437693412532098591327667236328125001e-324" + ); + assert_float_result_bits_eq!( + 0x1, + f64, + "7.4109846876186981626485318930233205854758970392148714663837852375101326090531312779794975454245398856969484704316857659638998506553390969459816219401617281718945106978546710679176872575177347315553307795408549809608457500958111373034747658096871009590975442271004757307809711118935784838675653998783503015228055934046593739791790738723868299395818481660169122019456499931289798411362062484498678713572180352209017023903285791732520220528974020802906854021606612375549983402671300035812486479041385743401875520901590172592547146296175134159774938718574737870961645638908718119841271673056017045493004705269590165763776884908267986972573366521765567941072508764337560846003984904972149117463085539556354188641513168478436313080237596295773983001708984374999e-324" + ); + assert_float_result_bits_eq!( + 0x2, + f64, + "7.4109846876186981626485318930233205854758970392148714663837852375101326090531312779794975454245398856969484704316857659638998506553390969459816219401617281718945106978546710679176872575177347315553307795408549809608457500958111373034747658096871009590975442271004757307809711118935784838675653998783503015228055934046593739791790738723868299395818481660169122019456499931289798411362062484498678713572180352209017023903285791732520220528974020802906854021606612375549983402671300035812486479041385743401875520901590172592547146296175134159774938718574737870961645638908718119841271673056017045493004705269590165763776884908267986972573366521765567941072508764337560846003984904972149117463085539556354188641513168478436313080237596295773983001708984375e-324" + ); + assert_float_result_bits_eq!( + 0x2, + f64, + "7.4109846876186981626485318930233205854758970392148714663837852375101326090531312779794975454245398856969484704316857659638998506553390969459816219401617281718945106978546710679176872575177347315553307795408549809608457500958111373034747658096871009590975442271004757307809711118935784838675653998783503015228055934046593739791790738723868299395818481660169122019456499931289798411362062484498678713572180352209017023903285791732520220528974020802906854021606612375549983402671300035812486479041385743401875520901590172592547146296175134159774938718574737870961645638908718119841271673056017045493004705269590165763776884908267986972573366521765567941072508764337560846003984904972149117463085539556354188641513168478436313080237596295773983001708984375001e-324" + ); + assert_float_result_bits_eq!( + 0x6c9a143590c14, + f64, + "94393431193180696942841837085033647913224148539854e-358" + ); + assert_float_result_bits_eq!( + 0x7802665fd9600, + f64, + "104308485241983990666713401708072175773165034278685682646111762292409330928739751702404658197872319129036519947435319418387839758990478549477777586673075945844895981012024387992135617064532141489278815239849108105951619997829153633535314849999674266169258928940692239684771590065027025835804863585454872499320500023126142553932654370362024104462255244034053203998964360882487378334860197725139151265590832887433736189468858614521708567646743455601905935595381852723723645799866672558576993978025033590728687206296379801363024094048327273913079612469982585674824156000783167963081616214710691759864332339239688734656548790656486646106983450809073750535624894296242072010195710276073042036425579852459556183541199012652571123898996574563824424330960027873516082763671875e-1075" + ); +} + +#[test] +fn many_digits() { + // Check large numbers of digits to ensure we have cases where significant + // digits (above Decimal::MAX_DIGITS) occurs. + assert_float_result_bits_eq!( + 0x7ffffe, + f32, + "1.175494140627517859246175898662808184331245864732796240031385942718174675986064769972472277004271745681762695312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e-38" + ); + assert_float_result_bits_eq!( + 0x7ffffe, + f32, + "1.175494140627517859246175898662808184331245864732796240031385942718174675986064769972472277004271745681762695312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e-38" + ); } diff --git a/library/core/tests/num/dec2flt/rawfp.rs b/library/core/tests/num/dec2flt/rawfp.rs deleted file mode 100644 index 34a37209d99..00000000000 --- a/library/core/tests/num/dec2flt/rawfp.rs +++ /dev/null @@ -1,172 +0,0 @@ -use core::num::dec2flt::rawfp::RawFloat; -use core::num::dec2flt::rawfp::{fp_to_float, next_float, prev_float, round_normal}; -use core::num::diy_float::Fp; - -fn integer_decode(f: f64) -> (u64, i16, i8) { - RawFloat::integer_decode(f) -} - -#[test] -fn fp_to_float_half_to_even() { - fn is_normalized(sig: u64) -> bool { - // intentionally written without {min,max}_sig() as a sanity check - sig >> 52 == 1 && sig >> 53 == 0 - } - - fn conv(sig: u64) -> u64 { - // The significands are perfectly in range, so the exponent should not matter - let (m1, e1, _) = integer_decode(fp_to_float::<f64>(Fp { f: sig, e: 0 })); - assert_eq!(e1, 0 + 64 - 53); - let (m2, e2, _) = integer_decode(fp_to_float::<f64>(Fp { f: sig, e: 55 })); - assert_eq!(e2, 55 + 64 - 53); - assert_eq!(m2, m1); - let (m3, e3, _) = integer_decode(fp_to_float::<f64>(Fp { f: sig, e: -78 })); - assert_eq!(e3, -78 + 64 - 53); - assert_eq!(m3, m2); - m3 - } - - let odd = 0x1F_EDCB_A012_345F; - let even = odd - 1; - assert!(is_normalized(odd)); - assert!(is_normalized(even)); - assert_eq!(conv(odd << 11), odd); - assert_eq!(conv(even << 11), even); - assert_eq!(conv(odd << 11 | 1 << 10), odd + 1); - assert_eq!(conv(even << 11 | 1 << 10), even); - assert_eq!(conv(even << 11 | 1 << 10 | 1), even + 1); - assert_eq!(conv(odd << 11 | 1 << 9), odd); - assert_eq!(conv(even << 11 | 1 << 9), even); - assert_eq!(conv(odd << 11 | 0x7FF), odd + 1); - assert_eq!(conv(even << 11 | 0x7FF), even + 1); - assert_eq!(conv(odd << 11 | 0x3FF), odd); - assert_eq!(conv(even << 11 | 0x3FF), even); -} - -#[test] -fn integers_to_f64() { - assert_eq!(fp_to_float::<f64>(Fp { f: 1, e: 0 }), 1.0); - assert_eq!(fp_to_float::<f64>(Fp { f: 42, e: 7 }), (42 << 7) as f64); - assert_eq!(fp_to_float::<f64>(Fp { f: 1 << 20, e: 30 }), (1u64 << 50) as f64); - assert_eq!(fp_to_float::<f64>(Fp { f: 4, e: -3 }), 0.5); -} - -const SOME_FLOATS: [f64; 9] = [ - 0.1f64, - 33.568, - 42.1e-5, - 777.0e9, - 1.1111, - 0.347997, - 9843579834.35892, - 12456.0e-150, - 54389573.0e-150, -]; - -#[test] -fn human_f64_roundtrip() { - for &x in &SOME_FLOATS { - let (f, e, _) = integer_decode(x); - let fp = Fp { f: f, e: e }; - assert_eq!(fp_to_float::<f64>(fp), x); - } -} - -#[test] -fn rounding_overflow() { - let x = Fp { f: 0xFF_FF_FF_FF_FF_FF_FF_00u64, e: 42 }; - let rounded = round_normal::<f64>(x); - let adjusted_k = x.e + 64 - 53; - assert_eq!(rounded.sig, 1 << 52); - assert_eq!(rounded.k, adjusted_k + 1); -} - -#[test] -fn prev_float_monotonic() { - let mut x = 1.0; - for _ in 0..100 { - let x1 = prev_float(x); - assert!(x1 < x); - assert!(x - x1 < 1e-15); - x = x1; - } -} - -const MIN_SUBNORMAL: f64 = 5e-324; - -#[test] -fn next_float_zero() { - let tiny = next_float(0.0); - assert_eq!(tiny, MIN_SUBNORMAL); - assert!(tiny != 0.0); -} - -#[test] -fn next_float_subnormal() { - let second = next_float(MIN_SUBNORMAL); - // For subnormals, MIN_SUBNORMAL is the ULP - assert!(second != MIN_SUBNORMAL); - assert!(second > 0.0); - assert_eq!(second - MIN_SUBNORMAL, MIN_SUBNORMAL); -} - -#[test] -fn next_float_inf() { - assert_eq!(next_float(f64::MAX), f64::INFINITY); - assert_eq!(next_float(f64::INFINITY), f64::INFINITY); -} - -#[test] -fn next_prev_identity() { - for &x in &SOME_FLOATS { - assert_eq!(prev_float(next_float(x)), x); - assert_eq!(prev_float(prev_float(next_float(next_float(x)))), x); - assert_eq!(next_float(prev_float(x)), x); - assert_eq!(next_float(next_float(prev_float(prev_float(x)))), x); - } -} - -#[test] -fn next_float_monotonic() { - let mut x = 0.49999999999999; - assert!(x < 0.5); - for _ in 0..200 { - let x1 = next_float(x); - assert!(x1 > x); - assert!(x1 - x < 1e-15, "next_float_monotonic: delta = {:?}", x1 - x); - x = x1; - } - assert!(x > 0.5); -} - -#[test] -fn test_f32_integer_decode() { - assert_eq!(3.14159265359f32.integer_decode(), (13176795, -22, 1)); - assert_eq!((-8573.5918555f32).integer_decode(), (8779358, -10, -1)); - assert_eq!(2f32.powf(100.0).integer_decode(), (8388608, 77, 1)); - assert_eq!(0f32.integer_decode(), (0, -150, 1)); - assert_eq!((-0f32).integer_decode(), (0, -150, -1)); - assert_eq!(f32::INFINITY.integer_decode(), (8388608, 105, 1)); - assert_eq!(f32::NEG_INFINITY.integer_decode(), (8388608, 105, -1)); - - // Ignore the "sign" (quiet / signalling flag) of NAN. - // It can vary between runtime operations and LLVM folding. - let (nan_m, nan_e, _nan_s) = f32::NAN.integer_decode(); - assert_eq!((nan_m, nan_e), (12582912, 105)); -} - -#[test] -fn test_f64_integer_decode() { - assert_eq!(3.14159265359f64.integer_decode(), (7074237752028906, -51, 1)); - assert_eq!((-8573.5918555f64).integer_decode(), (4713381968463931, -39, -1)); - assert_eq!(2f64.powf(100.0).integer_decode(), (4503599627370496, 48, 1)); - assert_eq!(0f64.integer_decode(), (0, -1075, 1)); - assert_eq!((-0f64).integer_decode(), (0, -1075, -1)); - assert_eq!(f64::INFINITY.integer_decode(), (4503599627370496, 972, 1)); - assert_eq!(f64::NEG_INFINITY.integer_decode(), (4503599627370496, 972, -1)); - - // Ignore the "sign" (quiet / signalling flag) of NAN. - // It can vary between runtime operations and LLVM folding. - let (nan_m, nan_e, _nan_s) = f64::NAN.integer_decode(); - assert_eq!((nan_m, nan_e), (6755399441055744, 972)); -} diff --git a/src/etc/dec2flt_table.py b/src/etc/dec2flt_table.py index ad2292e8571..aa5188d96c3 100755..100644 --- a/src/etc/dec2flt_table.py +++ b/src/etc/dec2flt_table.py @@ -1,141 +1,110 @@ #!/usr/bin/env python3 """ -Generate powers of ten using William Clinger's ``AlgorithmM`` for use in +Generate powers of five using Daniel Lemire's ``Eisel-Lemire algorithm`` for use in decimal to floating point conversions. Specifically, computes and outputs (as Rust code) a table of 10^e for some -range of exponents e. The output is one array of 64 bit significands and -another array of corresponding base two exponents. The approximations are -normalized and rounded perfectly, i.e., within 0.5 ULP of the true value. +range of exponents e. The output is one array of 128 bit significands. +The base two exponents can be inferred using a logarithmic slope +of the decimal exponent. The approximations are normalized and rounded perfectly, +i.e., within 0.5 ULP of the true value. -The representation ([u64], [i16]) instead of the more natural [(u64, i16)] -is used because (u64, i16) has a ton of padding which would make the table -even larger, and it's already uncomfortably large (6 KiB). +Adapted from Daniel Lemire's fast_float ``table_generation.py``, +available here: <https://github.com/fastfloat/fast_float/blob/main/script/table_generation.py>. """ from __future__ import print_function -from math import ceil, log +from math import ceil, floor, log, log2 from fractions import Fraction -from collections import namedtuple - - -N = 64 # Size of the significand field in bits -MIN_SIG = 2 ** (N - 1) -MAX_SIG = (2 ** N) - 1 - -# Hand-rolled fp representation without arithmetic or any other operations. -# The significand is normalized and always N bit, but the exponent is -# unrestricted in range. -Fp = namedtuple('Fp', 'sig exp') - - -def algorithm_m(f, e): - assert f > 0 - if e < 0: - u = f - v = 10 ** abs(e) - else: - u = f * 10 ** e - v = 1 - k = 0 - x = u // v - while True: - if x < MIN_SIG: - u <<= 1 - k -= 1 - elif x >= MAX_SIG: - v <<= 1 - k += 1 - else: - break - x = u // v - return ratio_to_float(u, v, k) - - -def ratio_to_float(u, v, k): - q, r = divmod(u, v) - v_r = v - r - z = Fp(q, k) - if r < v_r: - return z - elif r > v_r: - return next_float(z) - elif q % 2 == 0: - return z - else: - return next_float(z) - - -def next_float(z): - if z.sig == MAX_SIG: - return Fp(MIN_SIG, z.exp + 1) - else: - return Fp(z.sig + 1, z.exp) - - -def error(f, e, z): - decimal = f * Fraction(10) ** e - binary = z.sig * Fraction(2) ** z.exp - abs_err = abs(decimal - binary) - # The unit in the last place has value z.exp - ulp_err = abs_err / Fraction(2) ** z.exp - return float(ulp_err) - +from collections import deque HEADER = """ -//! Tables of approximations of powers of ten. +//! Pre-computed tables powers-of-5 for extended-precision representations. +//! +//! These tables enable fast scaling of the significant digits +//! of a float to the decimal exponent, with minimal rounding +//! errors, in a 128 or 192-bit representation. +//! //! DO NOT MODIFY: Generated by `src/etc/dec2flt_table.py` """ +STATIC_WARNING = """ +// Use static to avoid long compile times: Rust compiler errors +// can have the entire table compiled multiple times, and then +// emit code multiple times, even if it's stripped out in +// the final binary. +""" def main(): + min_exp = minimum_exponent(10) + max_exp = maximum_exponent(10) + bias = -minimum_exponent(5) + print(HEADER.strip()) print() - print_proper_powers() - print() - print_short_powers(32, 24) + print('pub const SMALLEST_POWER_OF_FIVE: i32 = {};'.format(min_exp)) + print('pub const LARGEST_POWER_OF_FIVE: i32 = {};'.format(max_exp)) + print('pub const N_POWERS_OF_FIVE: usize = ', end='') + print('(LARGEST_POWER_OF_FIVE - SMALLEST_POWER_OF_FIVE + 1) as usize;') print() - print_short_powers(64, 53) + print_proper_powers(min_exp, max_exp, bias) + + +def minimum_exponent(base): + return ceil(log(5e-324, base) - log(0xFFFFFFFFFFFFFFFF, base)) + +def maximum_exponent(base): + return floor(log(1.7976931348623157e+308, base)) -def print_proper_powers(): - MIN_E = -305 - MAX_E = 305 - e_range = range(MIN_E, MAX_E+1) + +def print_proper_powers(min_exp, max_exp, bias): + powers = deque() + + # Add negative exponents. + # 2^(2b)/(5^−q) with b=64 + int(math.ceil(log2(5^−q))) powers = [] - for e in e_range: - z = algorithm_m(1, e) - err = error(1, e, z) - assert err < 0.5 - powers.append(z) - print("pub const MIN_E: i16 = {};".format(MIN_E)) - print("pub const MAX_E: i16 = {};".format(MAX_E)) - print() - print("#[rustfmt::skip]") - typ = "([u64; {0}], [i16; {0}])".format(len(powers)) - print("pub static POWERS: ", typ, " = (", sep='') - print(" [") - for z in powers: - print(" 0x{:x},".format(z.sig)) - print(" ],") - print(" [") - for z in powers: - print(" {},".format(z.exp)) - print(" ],") - print(");") - - -def print_short_powers(num_bits, significand_size): - max_sig = 2**significand_size - 1 - # The fast path bails out for exponents >= ceil(log5(max_sig)) - max_e = int(ceil(log(max_sig, 5))) - e_range = range(max_e) - typ = "[f{}; {}]".format(num_bits, len(e_range)) - print("#[rustfmt::skip]") - print("pub const F", num_bits, "_SHORT_POWERS: ", typ, " = [", sep='') - for e in e_range: - print(" 1e{},".format(e)) - print("];") + for q in range(min_exp, 0): + power5 = 5 ** -q + z = 0 + while (1 << z) < power5: + z += 1 + if q >= -27: + b = z + 127 + c = 2 ** b // power5 + 1 + powers.append((c, q)) + else: + b = 2 * z + 2 * 64 + c = 2 ** b // power5 + 1 + # truncate + while c >= (1<<128): + c //= 2 + powers.append((c, q)) + + # Add positive exponents + for q in range(0, max_exp + 1): + power5 = 5 ** q + # move the most significant bit in position + while power5 < (1<<127): + power5 *= 2 + # *truncate* + while power5 >= (1<<128): + power5 //= 2 + powers.append((power5, q)) + + # Print the powers. + print(STATIC_WARNING.strip()) + print('#[rustfmt::skip]') + typ = '[(u64, u64); N_POWERS_OF_FIVE]' + print('pub static POWER_OF_FIVE_128: {} = ['.format(typ)) + lo_mask = (1 << 64) - 1 + for c, exp in powers: + hi = '0x{:x}'.format(c // (1 << 64)) + lo = '0x{:x}'.format(c % (1 << 64)) + value = ' ({}, {}), '.format(hi, lo) + comment = '// {}^{}'.format(5, exp) + print(value.ljust(46, ' ') + comment) + print('];') if __name__ == '__main__': diff --git a/src/etc/test-float-parse/Cargo.toml b/src/etc/test-float-parse/Cargo.toml new file mode 100644 index 00000000000..8226e815c2c --- /dev/null +++ b/src/etc/test-float-parse/Cargo.toml @@ -0,0 +1,13 @@ +[package] +name = "test-float-parse" +version = "0.1.0" +edition = "2018" +publish = false + +[workspace] + +[dependencies] +rand = "0.4" + +[lib] +name = "test_float_parse" diff --git a/src/etc/test-float-parse/runtests.py b/src/etc/test-float-parse/runtests.py index 218552a4597..cf7279534dc 100644 --- a/src/etc/test-float-parse/runtests.py +++ b/src/etc/test-float-parse/runtests.py @@ -131,22 +131,20 @@ def write_errors(): exit_status = 101 -def rustc(test): - rs = test + '.rs' - exe = test + '.exe' # hopefully this makes it work on *nix - print("compiling", test) +def cargo(): + print("compiling tests") sys.stdout.flush() - check_call(['rustc', rs, '-o', exe]) + check_call(['cargo', 'build', '--release']) def run(test): global test_name test_name = test - t0 = time.clock() + t0 = time.perf_counter() msg("setting up supervisor") - exe = test + '.exe' - proc = Popen(exe, bufsize=1<<20 , stdin=PIPE, stdout=PIPE, stderr=PIPE) + command = ['cargo', 'run', '--bin', test, '--release'] + proc = Popen(command, bufsize=1<<20 , stdin=PIPE, stdout=PIPE, stderr=PIPE) done = multiprocessing.Value(ctypes.c_bool) queue = multiprocessing.Queue(maxsize=5)#(maxsize=1024) workers = [] @@ -166,7 +164,7 @@ def run(test): worker.join() msg("python is done") assert queue.empty(), "did not validate everything" - dt = time.clock() - t0 + dt = time.perf_counter() - t0 msg("took", round(dt, 3), "seconds") @@ -176,7 +174,7 @@ def interact(proc, queue): line = proc.stdout.readline() if not line: continue - assert line.endswith('\n'), "incomplete line: " + repr(line) + assert line.endswith(b'\n'), "incomplete line: " + repr(line) queue.put(line) n += 1 if n % UPDATE_EVERY_N == 0: @@ -185,7 +183,7 @@ def interact(proc, queue): rest, stderr = proc.communicate() if stderr: msg("rust stderr output:", stderr) - for line in rest.split('\n'): + for line in rest.split(b'\n'): if not line: continue queue.put(line) @@ -193,18 +191,19 @@ def interact(proc, queue): def main(): global MAILBOX - all_tests = [os.path.splitext(f)[0] for f in glob('*.rs') if not f.startswith('_')] + files = glob('src/bin/*.rs') + basenames = [os.path.basename(i) for i in files] + all_tests = [os.path.splitext(f)[0] for f in basenames if not f.startswith('_')] args = sys.argv[1:] if args: tests = [test for test in all_tests if test in args] - else + else: tests = all_tests if not tests: print("Error: No tests to run") sys.exit(1) # Compile first for quicker feedback - for test in tests: - rustc(test) + cargo() # Set up mailbox once for all tests MAILBOX = multiprocessing.Queue() mailman = threading.Thread(target=write_errors) @@ -251,7 +250,7 @@ def do_work(queue): else: continue bin64, bin32, text = line.rstrip().split() - validate(bin64, bin32, text) + validate(bin64, bin32, text.decode('utf-8')) def decode_binary64(x): @@ -331,7 +330,11 @@ SINGLE_ZERO_CUTOFF = MIN_SUBNORMAL_SINGLE / 2 SINGLE_INF_CUTOFF = MAX_SINGLE + 2 ** (MAX_ULP_SINGLE - 1) def validate(bin64, bin32, text): - double = decode_binary64(bin64) + try: + double = decode_binary64(bin64) + except AssertionError: + print(bin64, bin32, text) + raise single = decode_binary32(bin32) real = Fraction(text) diff --git a/src/etc/test-float-parse/few-ones.rs b/src/etc/test-float-parse/src/bin/few-ones.rs index 2d82918aabb..6bb406a5947 100644 --- a/src/etc/test-float-parse/few-ones.rs +++ b/src/etc/test-float-parse/src/bin/few-ones.rs @@ -1,6 +1,4 @@ -mod _common; - -use _common::validate; +use test_float_parse::validate; fn main() { let mut pow = vec![]; diff --git a/src/etc/test-float-parse/huge-pow10.rs b/src/etc/test-float-parse/src/bin/huge-pow10.rs index 9a16d9c6028..722a24ffcd8 100644 --- a/src/etc/test-float-parse/huge-pow10.rs +++ b/src/etc/test-float-parse/src/bin/huge-pow10.rs @@ -1,6 +1,4 @@ -mod _common; - -use _common::validate; +use test_float_parse::validate; fn main() { for e in 300..310 { diff --git a/src/etc/test-float-parse/long-fractions.rs b/src/etc/test-float-parse/src/bin/long-fractions.rs index 60cf85c4a60..c715bc1ac2b 100644 --- a/src/etc/test-float-parse/long-fractions.rs +++ b/src/etc/test-float-parse/src/bin/long-fractions.rs @@ -1,7 +1,5 @@ -mod _common; - -use _common::validate; use std::char; +use test_float_parse::validate; fn main() { for n in 0..10 { diff --git a/src/etc/test-float-parse/many-digits.rs b/src/etc/test-float-parse/src/bin/many-digits.rs index 599986e20dd..ba166fd5607 100644 --- a/src/etc/test-float-parse/many-digits.rs +++ b/src/etc/test-float-parse/src/bin/many-digits.rs @@ -1,11 +1,9 @@ extern crate rand; -mod _common; - -use _common::{validate, SEED}; use rand::distributions::{Range, Sample}; use rand::{IsaacRng, Rng, SeedableRng}; use std::char; +use test_float_parse::{validate, SEED}; fn main() { let mut rnd = IsaacRng::from_seed(&SEED); diff --git a/src/etc/test-float-parse/rand-f64.rs b/src/etc/test-float-parse/src/bin/rand-f64.rs index 39ad63945cd..6991e8be15e 100644 --- a/src/etc/test-float-parse/rand-f64.rs +++ b/src/etc/test-float-parse/src/bin/rand-f64.rs @@ -1,10 +1,8 @@ extern crate rand; -mod _common; - -use _common::{validate, SEED}; use rand::{IsaacRng, Rng, SeedableRng}; use std::mem::transmute; +use test_float_parse::{validate, SEED}; fn main() { let mut rnd = IsaacRng::from_seed(&SEED); diff --git a/src/etc/test-float-parse/short-decimals.rs b/src/etc/test-float-parse/src/bin/short-decimals.rs index 8b9b6f78ae3..49084eb35e8 100644 --- a/src/etc/test-float-parse/short-decimals.rs +++ b/src/etc/test-float-parse/src/bin/short-decimals.rs @@ -1,6 +1,4 @@ -mod _common; - -use _common::validate; +use test_float_parse::validate; fn main() { // Skip e = 0 because small-u32 already does those. diff --git a/src/etc/test-float-parse/subnorm.rs b/src/etc/test-float-parse/src/bin/subnorm.rs index ba68d31e4ed..ac88747eacd 100644 --- a/src/etc/test-float-parse/subnorm.rs +++ b/src/etc/test-float-parse/src/bin/subnorm.rs @@ -1,7 +1,5 @@ -mod _common; - -use _common::validate; use std::mem::transmute; +use test_float_parse::validate; fn main() { for bits in 0u32..(1 << 21) { diff --git a/src/etc/test-float-parse/tiny-pow10.rs b/src/etc/test-float-parse/src/bin/tiny-pow10.rs index 43fad5b49ee..fb6ba166380 100644 --- a/src/etc/test-float-parse/tiny-pow10.rs +++ b/src/etc/test-float-parse/src/bin/tiny-pow10.rs @@ -1,6 +1,4 @@ -mod _common; - -use _common::validate; +use test_float_parse::validate; fn main() { for e in 301..327 { diff --git a/src/etc/test-float-parse/u32-small.rs b/src/etc/test-float-parse/src/bin/u32-small.rs index 3ae62425adf..5ec9d1eea5f 100644 --- a/src/etc/test-float-parse/u32-small.rs +++ b/src/etc/test-float-parse/src/bin/u32-small.rs @@ -1,6 +1,4 @@ -mod _common; - -use _common::validate; +use test_float_parse::validate; fn main() { for i in 0..(1 << 19) { diff --git a/src/etc/test-float-parse/u64-pow2.rs b/src/etc/test-float-parse/src/bin/u64-pow2.rs index 7e67e2b1246..984e49200cd 100644 --- a/src/etc/test-float-parse/u64-pow2.rs +++ b/src/etc/test-float-parse/src/bin/u64-pow2.rs @@ -1,6 +1,4 @@ -mod _common; - -use _common::validate; +use test_float_parse::validate; fn main() { for exp in 19..64 { diff --git a/src/etc/test-float-parse/_common.rs b/src/etc/test-float-parse/src/lib.rs index 9cbad5486b4..9cbad5486b4 100644 --- a/src/etc/test-float-parse/_common.rs +++ b/src/etc/test-float-parse/src/lib.rs diff --git a/src/test/ui/issues/issue-31109.rs b/src/test/ui/issues/issue-31109.rs deleted file mode 100644 index 37c23905819..00000000000 --- a/src/test/ui/issues/issue-31109.rs +++ /dev/null @@ -1,6 +0,0 @@ -fn main() { - // FIXME(#31407) this error should go away, but in the meantime we test that it - // is accompanied by a somewhat useful error message. - let _: f64 = 1234567890123456789012345678901234567890e-340; - //~^ ERROR could not evaluate float literal (see issue #31407) -} diff --git a/src/test/ui/issues/issue-31109.stderr b/src/test/ui/issues/issue-31109.stderr deleted file mode 100644 index d354f61a501..00000000000 --- a/src/test/ui/issues/issue-31109.stderr +++ /dev/null @@ -1,8 +0,0 @@ -error: could not evaluate float literal (see issue #31407) - --> $DIR/issue-31109.rs:4:18 - | -LL | let _: f64 = 1234567890123456789012345678901234567890e-340; - | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - -error: aborting due to previous error - diff --git a/src/test/ui/parser/float-literals.rs b/src/test/ui/parser/float-literals.rs new file mode 100644 index 00000000000..1e9319fd27d --- /dev/null +++ b/src/test/ui/parser/float-literals.rs @@ -0,0 +1,9 @@ +// build-pass +// ignore-tidy-linelength +// Regression test for #31109 and #31407. + +pub fn main() { + let _: f64 = 0.3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333; + + let _: f64 = 1234567890123456789012345678901234567890e-340; +} diff --git a/src/test/ui/pattern/issue-68396-let-float-bug.rs b/src/test/ui/pattern/issue-68396-let-float-bug.rs deleted file mode 100644 index afc599a4b22..00000000000 --- a/src/test/ui/pattern/issue-68396-let-float-bug.rs +++ /dev/null @@ -1,7 +0,0 @@ -fn main() { - let 1234567890123456789012345678901234567890e-340: f64 = 0.0; - //~^ ERROR could not evaluate float literal (see issue #31407) - - fn param(1234567890123456789012345678901234567890e-340: f64) {} - //~^ ERROR could not evaluate float literal (see issue #31407) -} diff --git a/src/test/ui/pattern/issue-68396-let-float-bug.stderr b/src/test/ui/pattern/issue-68396-let-float-bug.stderr deleted file mode 100644 index 618aa4b5021..00000000000 --- a/src/test/ui/pattern/issue-68396-let-float-bug.stderr +++ /dev/null @@ -1,15 +0,0 @@ -error[E0080]: could not evaluate float literal (see issue #31407) - --> $DIR/issue-68396-let-float-bug.rs:2:9 - | -LL | let 1234567890123456789012345678901234567890e-340: f64 = 0.0; - | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - -error[E0080]: could not evaluate float literal (see issue #31407) - --> $DIR/issue-68396-let-float-bug.rs:5:14 - | -LL | fn param(1234567890123456789012345678901234567890e-340: f64) {} - | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - -error: aborting due to 2 previous errors - -For more information about this error, try `rustc --explain E0080`. |