mod.rs - source
Description: Source of the Rust file `library/core/src/num/dec2flt/mod.rs`.

#
core/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 a
    7//! default value (1 or 0) 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/tools/test-float-parse` as a Rust program.
    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//! # Notation
    72//!
    73//! This module uses the same notation as the Lemire paper:
    74//!
    75//! - `m`: binary mantissa; always nonnegative
    76//! - `p`: binary exponent; a signed integer
    77//! - `w`: decimal significand; always nonnegative
    78//! - `q`: decimal exponent; a signed integer
    79//!
    80//! This gives `m * 2^p` for the binary floating-point number, with `w * 10^q` as the decimal
    81//! equivalent.
    82
    83#![doc(hidden)]
    84#![unstable(
    85    feature = "dec2flt",
    86    reason = "internal routines only exposed for testing",
    87    issue = "none"
    88)]
    89
    90use self::common::BiasedFp;
    91use self::float::RawFloat;
    92use self::lemire::compute_float;
    93use self::parse::{parse_inf_nan, parse_number};
    94use self::slow::parse_long_mantissa;
    95use crate::error::Error;
    96use crate::fmt;
    97use crate::str::FromStr;
    98
    99mod common;
    100pub mod decimal;
    101pub mod decimal_seq;
    102mod fpu;
    103mod slow;
    104mod table;
    105// float is used in flt2dec, and all are used in unit tests.
    106pub mod float;
    107pub mod lemire;
    108pub mod parse;
    109
    110macro_rules! from_str_float_impl {
    111    ($t:ty) => {
    112        #[stable(feature = "rust1", since = "1.0.0")]
    113        impl FromStr for $t {
    114            type Err = ParseFloatError;
    115
    116            /// Converts a string in base 10 to a float.
    117            /// Accepts an optional decimal exponent.
    118            ///
    119            /// This function accepts strings such as
    120            ///
    121            /// * '3.14'
    122            /// * '-3.14'
    123            /// * '2.5E10', or equivalently, '2.5e10'
    124            /// * '2.5E-10'
    125            /// * '5.'
    126            /// * '.5', or, equivalently, '0.5'
    127            /// * '7'
    128            /// * '007'
    129            /// * 'inf', '-inf', '+infinity', 'NaN'
    130            ///
    131            /// Note that alphabetical characters are not case-sensitive.
    132            ///
    133            /// Leading and trailing whitespace represent an error.
    134            ///
    135            /// # Grammar
    136            ///
    137            /// All strings that adhere to the following [EBNF] grammar when
    138            /// lowercased will result in an [`Ok`] being returned:
    139            ///
    140            /// ```txt
    141            /// Float  ::= Sign? ( 'inf' | 'infinity' | 'nan' | Number )
    142            /// Number ::= ( Digit+ |
    143            ///              Digit+ '.' Digit* |
    144            ///              Digit* '.' Digit+ ) Exp?
    145            /// Exp    ::= 'e' Sign? Digit+
    146            /// Sign   ::= [+-]
    147            /// Digit  ::= [0-9]
    148            /// ```
    149            ///
    150            /// [EBNF]: https://www.w3.org/TR/REC-xml/#sec-notation
    151            ///
    152            /// # Arguments
    153            ///
    154            /// * src - A string
    155            ///
    156            /// # Return value
    157            ///
    158            /// `Err(ParseFloatError)` if the string did not represent a valid
    159            /// number. Otherwise, `Ok(n)` where `n` is the closest
    160            /// representable floating-point number to the number represented
    161            /// by `src` (following the same rules for rounding as for the
    162            /// results of primitive operations).
    163            // We add the `#[inline(never)]` attribute, since its content will
    164            // be filled with that of `dec2flt`, which has #[inline(always)].
    165            // Since `dec2flt` is generic, a normal inline attribute on this function
    166            // with `dec2flt` having no attributes results in heavily repeated
    167            // generation of `dec2flt`, despite the fact only a maximum of 2
    168            // possible instances can ever exist. Adding #[inline(never)] avoids this.
    169            #[inline(never)]
    170            fn from_str(src: &str) -> Result<Self, ParseFloatError> {
    171                dec2flt(src)
    172            }
    173        }
    174    };
    175}
    176
    177#[cfg(target_has_reliable_f16)]
    178from_str_float_impl!(f16);
    179from_str_float_impl!(f32);
    180from_str_float_impl!(f64);
    181
    182// FIXME(f16_f128): A fallback is used when the backend+target does not support f16 well, in order
    183// to avoid ICEs.
    184
    185#[cfg(not(target_has_reliable_f16))]
    186impl FromStr for f16 {
    187    type Err = ParseFloatError;
    188
    189    #[inline]
    190    fn from_str(_src: &str) -> Result<Self, ParseFloatError> {
    191        unimplemented!("requires target_has_reliable_f16")
    192    }
    193}
    194
    195/// An error which can be returned when parsing a float.
    196///
    197/// This error is used as the error type for the [`FromStr`] implementation
    198/// for [`f32`] and [`f64`].
    199///
    200/// # Example
    201///
    202/// ```
    203/// use std::str::FromStr;
    204///
    205/// if let Err(e) = f64::from_str("a.12") {
    206///     println!("Failed conversion to f64: {e}");
    207/// }
    208/// ```
    209#[derive(Debug, Clone, PartialEq, Eq)]
    210#[stable(feature = "rust1", since = "1.0.0")]
    211pub struct ParseFloatError {
    212    kind: FloatErrorKind,
    213}
    214
    215#[derive(Debug, Clone, PartialEq, Eq)]
    216enum FloatErrorKind {
    217    Empty,
    218    Invalid,
    219}
    220
    221#[stable(feature = "rust1", since = "1.0.0")]
    222impl Error for ParseFloatError {}
    223
    224#[stable(feature = "rust1", since = "1.0.0")]
    225impl fmt::Display for ParseFloatError {
    226    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    227        match self.kind {
    228            FloatErrorKind::Empty => "cannot parse float from empty string",
    229            FloatErrorKind::Invalid => "invalid float literal",
    230        }
    231        .fmt(f)
    232    }
    233}
    234
    235#[inline]
    236pub(super) fn pfe_empty() -> ParseFloatError {
    237    ParseFloatError { kind: FloatErrorKind::Empty }
    238}
    239
    240// Used in unit tests, keep public.
    241// This is much better than making FloatErrorKind and ParseFloatError::kind public.
    242#[inline]
    243pub fn pfe_invalid() -> ParseFloatError {
    244    ParseFloatError { kind: FloatErrorKind::Invalid }
    245}
    246
    247/// Converts a `BiasedFp` to the closest machine float type.
    248fn biased_fp_to_float<F: RawFloat>(x: BiasedFp) -> F {
    249    let mut word = x.m;
    250    word |= (x.p_biased as u64) << F::SIG_BITS;
    251    F::from_u64_bits(word)
    252}
    253
    254/// Converts a decimal string into a floating point number.
    255#[inline(always)] // Will be inlined into a function with `#[inline(never)]`, see above
    256pub fn dec2flt<F: RawFloat>(s: &str) -> Result<F, ParseFloatError> {
    257    let mut s = s.as_bytes();
    258    let Some(&c) = s.first() else { return Err(pfe_empty()) };
    259    let negative = c == b'-';
    260    if c == b'-' || c == b'+' {
    261        s = &s[1..];
    262    }
    263    if s.is_empty() {
    264        return Err(pfe_invalid());
    265    }
    266
    267    let mut num = match parse_number(s) {
    268        Some(r) => r,
    269        None if let Some(value) = parse_inf_nan(s, negative) => return Ok(value),
    270        None => return Err(pfe_invalid()),
    271    };
    272    num.negative = negative;
    273    if !cfg!(feature = "optimize_for_size") {
    274        if let Some(value) = num.try_fast_path::<F>() {
    275            return Ok(value);
    276        }
    277    }
    278
    279    // If significant digits were truncated, then we can have rounding error
    280    // only if `mantissa + 1` produces a different result. We also avoid
    281    // redundantly using the Eisel-Lemire algorithm if it was unable to
    282    // correctly round on the first pass.
    283    let mut fp = compute_float::<F>(num.exponent, num.mantissa);
    284    if num.many_digits
    285        && fp.p_biased >= 0
    286        && fp != compute_float::<F>(num.exponent, num.mantissa + 1)
    287    {
    288        fp.p_biased = -1;
    289    }
    290    // Unable to correctly round the float using the Eisel-Lemire algorithm.
    291    // Fallback to a slower, but always correct algorithm.
    292    if fp.p_biased < 0 {
    293        fp = parse_long_mantissa::<F>(s);
    294    }
    295
    296    let mut float = biased_fp_to_float::<F>(fp);
    297    if num.negative {
    298        float = -float;
    299    }
    300    Ok(float)
    301}