library/core/src/num/dec2flt/mod.rs

   1 //! Converting decimal strings into IEEE 754 binary floating point numbers.
   2 //!
   3 //! # Problem statement
   4 //!
   5 //! We are given a decimal string such as `12.34e56`. This string consists of integral (`12`),
   6 //! fractional (`34`), and exponent (`56`) parts. All parts are optional and interpreted as zero
   7 //! when missing.
   8 //!
   9 //! We seek the IEEE 754 floating point number that is closest to the exact value of the decimal
  10 //! string. It is well-known that many decimal strings do not have terminating representations in
  11 //! base two, so we round to 0.5 units in the last place (in other words, as well as possible).
  12 //! Ties, decimal values exactly half-way between two consecutive floats, are resolved with the
  13 //! half-to-even strategy, also known as banker's rounding.
  14 //!
  15 //! Needless to say, this is quite hard, both in terms of implementation complexity and in terms
  16 //! of CPU cycles taken.
  17 //!
  18 //! # Implementation
  19 //!
  20 //! First, we ignore signs. Or rather, we remove it at the very beginning of the conversion
  21 //! process and re-apply it at the very end. This is correct in all edge cases since IEEE
  22 //! floats are symmetric around zero, negating one simply flips the first bit.
  23 //!
  24 //! Then we remove the decimal point by adjusting the exponent: Conceptually, `12.34e56` turns
  25 //! into `1234e54`, which we describe with a positive integer `f = 1234` and an integer `e = 54`.
  26 //! The `(f, e)` representation is used by almost all code past the parsing stage.
  27 //!
  28 //! We then try a long chain of progressively more general and expensive special cases using
  29 //! machine-sized integers and small, fixed-sized floating point numbers (first `f32`/`f64`, then
  30 //! a type with 64 bit significand). The extended-precision algorithm
  31 //! uses the Eisel-Lemire algorithm, which uses a 128-bit (or 192-bit)
  32 //! representation that can accurately and quickly compute the vast majority
  33 //! of floats. When all these fail, we bite the bullet and resort to using
  34 //! a large-decimal representation, shifting the digits into range, calculating
  35 //! the upper significant bits and exactly round to the nearest representation.
  36 //!
  37 //! Another aspect that needs attention is the ``RawFloat`` trait by which almost all functions
  38 //! are parametrized. One might think that it's enough to parse to `f64` and cast the result to
  39 //! `f32`. Unfortunately this is not the world we live in, and this has nothing to do with using
  40 //! base two or half-to-even rounding.
  41 //!
  42 //! Consider for example two types `d2` and `d4` representing a decimal type with two decimal
  43 //! digits and four decimal digits each and take "0.01499" as input. Let's use half-up rounding.
  44 //! Going directly to two decimal digits gives `0.01`, but if we round to four digits first,
  45 //! we get `0.0150`, which is then rounded up to `0.02`. The same principle applies to other
  46 //! operations as well, if you want 0.5 ULP accuracy you need to do *everything* in full precision
  47 //! and round *exactly once, at the end*, by considering all truncated bits at once.
  48 //!
  49 //! Primarily, this module and its children implement the algorithms described in:
  50 //! "Number Parsing at a Gigabyte per Second", available online:
  51 //! <https://arxiv.org/abs/2101.11408>.
  52 //!
  53 //! # Other
  54 //!
  55 //! The conversion should *never* panic. There are assertions and explicit panics in the code,
  56 //! but they should never be triggered and only serve as internal sanity checks. Any panics should
  57 //! be considered a bug.
  58 //!
  59 //! There are unit tests but they are woefully inadequate at ensuring correctness, they only cover
  60 //! a small percentage of possible errors. Far more extensive tests are located in the directory
  61 //! `src/etc/test-float-parse` as a Python script.
  62 //!
  63 //! A note on integer overflow: Many parts of this file perform arithmetic with the decimal
  64 //! exponent `e`. Primarily, we shift the decimal point around: Before the first decimal digit,
  65 //! after the last decimal digit, and so on. This could overflow if done carelessly. We rely on
  66 //! the parsing submodule to only hand out sufficiently small exponents, where "sufficient" means
  67 //! "such that the exponent +/- the number of decimal digits fits into a 64 bit integer".
  68 //! Larger exponents are accepted, but we don't do arithmetic with them, they are immediately
  69 //! turned into {positive,negative} {zero,infinity}.
  70
  71 #![doc(hidden)]
  72 #![unstable(
  73     feature = "dec2flt",
  74     reason = "internal routines only exposed for testing",
  75     issue = "none"
  76 )]
  77
  78 use crate::fmt;
  79 use crate::str::FromStr;
  80
  81 use self::common::{BiasedFp, ByteSlice};
  82 use self::float::RawFloat;
  83 use self::lemire::compute_float;
  84 use self::parse::{parse_inf_nan, parse_number};
  85 use self::slow::parse_long_mantissa;
  86
  87 mod common;
  88 mod decimal;
  89 mod fpu;
  90 mod slow;
  91 mod table;
  92 // float is used in flt2dec, and all are used in unit tests.
  93 pub mod float;
  94 pub mod lemire;
  95 pub mod number;
  96 pub mod parse;
  97
  98 macro_rules! from_str_float_impl {
  99     ($t:ty) => {
 100         #[stable(feature = "rust1", since = "1.0.0")]
 101         impl FromStr for $t {
 102             type Err = ParseFloatError;
 103
 104             /// Converts a string in base 10 to a float.
 105             /// Accepts an optional decimal exponent.
 106             ///
 107             /// This function accepts strings such as
 108             ///
 109             /// * '3.14'
 110             /// * '-3.14'
 111             /// * '2.5E10', or equivalently, '2.5e10'
 112             /// * '2.5E-10'
 113             /// * '5.'
 114             /// * '.5', or, equivalently, '0.5'
 115             /// * 'inf', '-inf', '+infinity', 'NaN'
 116             ///
 117             /// Note that alphabetical characters are not case-sensitive.
 118             ///
 119             /// Leading and trailing whitespace represent an error.
 120             ///
 121             /// # Grammar
 122             ///
 123             /// All strings that adhere to the following [EBNF] grammar when
 124             /// lowercased will result in an [`Ok`] being returned:
 125             ///
 126             /// ```txt
 127             /// Float  ::= Sign? ( 'inf' | 'infinity' | 'nan' | Number )
 128             /// Number ::= ( Digit+ |
 129             ///              Digit+ '.' Digit* |
 130             ///              Digit* '.' Digit+ ) Exp?
 131             /// Exp    ::= 'e' Sign? Digit+
 132             /// Sign   ::= [+-]
 133             /// Digit  ::= [0-9]
 134             /// ```
 135             ///
 136             /// [EBNF]: https://www.w3.org/TR/REC-xml/#sec-notation
 137             ///
 138             /// # Arguments
 139             ///
 140             /// * src - A string
 141             ///
 142             /// # Return value
 143             ///
 144             /// `Err(ParseFloatError)` if the string did not represent a valid
 145             /// number. Otherwise, `Ok(n)` where `n` is the closest
 146             /// representable floating-point number to the number represented
 147             /// by `src` (following the same rules for rounding as for the
 148             /// results of primitive operations).
 149             #[inline]
 150             fn from_str(src: &str) -> Result<Self, ParseFloatError> {
 151                 dec2flt(src)
 152             }
 153         }
 154     };
 155 }
 156 from_str_float_impl!(f32);
 157 from_str_float_impl!(f64);
 158
 159 /// An error which can be returned when parsing a float.
 160 ///
 161 /// This error is used as the error type for the [`FromStr`] implementation
 162 /// for [`f32`] and [`f64`].
 163 ///
 164 /// # Example
 165 ///
 166 /// ```
 167 /// use std::str::FromStr;
 168 ///
 169 /// if let Err(e) = f64::from_str("a.12") {
 170 ///     println!("Failed conversion to f64: {e}");
 171 /// }
 172 /// ```
 173 #[derive(Debug, Clone, PartialEq, Eq)]
 174 #[stable(feature = "rust1", since = "1.0.0")]
 175 pub struct ParseFloatError {
 176     kind: FloatErrorKind,
 177 }
 178
 179 #[derive(Debug, Clone, PartialEq, Eq)]
 180 enum FloatErrorKind {
 181     Empty,
 182     Invalid,
 183 }
 184
 185 impl ParseFloatError {
 186     #[unstable(
 187         feature = "int_error_internals",
 188         reason = "available through Error trait and this method should \
 189                   not be exposed publicly",
 190         issue = "none"
 191     )]
 192     #[doc(hidden)]
 193     pub fn __description(&self) -> &str {
 194         match self.kind {
 195             FloatErrorKind::Empty => "cannot parse float from empty string",
 196             FloatErrorKind::Invalid => "invalid float literal",
 197         }
 198     }
 199 }
 200
 201 #[stable(feature = "rust1", since = "1.0.0")]
 202 impl fmt::Display for ParseFloatError {
 203     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 204         self.__description().fmt(f)
 205     }
 206 }
 207
 208 pub(super) fn pfe_empty() -> ParseFloatError {
 209     ParseFloatError { kind: FloatErrorKind::Empty }
 210 }
 211
 212 // Used in unit tests, keep public.
 213 // This is much better than making FloatErrorKind and ParseFloatError::kind public.
 214 pub fn pfe_invalid() -> ParseFloatError {
 215     ParseFloatError { kind: FloatErrorKind::Invalid }
 216 }
 217
 218 /// Converts a `BiasedFp` to the closest machine float type.
 219 fn biased_fp_to_float<T: RawFloat>(x: BiasedFp) -> T {
 220     let mut word = x.f;
 221     word |= (x.e as u64) << T::MANTISSA_EXPLICIT_BITS;
 222     T::from_u64_bits(word)
 223 }
 224
 225 /// Converts a decimal string into a floating point number.
 226 pub fn dec2flt<F: RawFloat>(s: &str) -> Result<F, ParseFloatError> {
 227     let mut s = s.as_bytes();
 228     let c = if let Some(&c) = s.first() {
 229         c
 230     } else {
 231         return Err(pfe_empty());
 232     };
 233     let negative = c == b'-';
 234     if c == b'-' || c == b'+' {
 235         s = s.advance(1);
 236     }
 237     if s.is_empty() {
 238         return Err(pfe_invalid());
 239     }
 240
 241     let num = match parse_number(s, negative) {
 242         Some(r) => r,
 243         None if let Some(value) = parse_inf_nan(s, negative) => return Ok(value),
 244         None => return Err(pfe_invalid()),
 245     };
 246     if let Some(value) = num.try_fast_path::<F>() {
 247         return Ok(value);
 248     }
 249
 250     // If significant digits were truncated, then we can have rounding error
 251     // only if `mantissa + 1` produces a different result. We also avoid
 252     // redundantly using the Eisel-Lemire algorithm if it was unable to
 253     // correctly round on the first pass.
 254     let mut fp = compute_float::<F>(num.exponent, num.mantissa);
 255     if num.many_digits && fp.e >= 0 && fp != compute_float::<F>(num.exponent, num.mantissa + 1) {
 256         fp.e = -1;
 257     }
 258     // Unable to correctly round the float using the Eisel-Lemire algorithm.
 259     // Fallback to a slower, but always correct algorithm.
 260     if fp.e < 0 {
 261         fp = parse_long_mantissa::<F>(s);
 262     }
 263
 264     let mut float = biased_fp_to_float::<F>(fp);
 265     if num.negative {
 266         float = -float;
 267     }
 268     Ok(float)
 269 }