1 //! Converting decimal strings into IEEE 754 binary floating point numbers.
3 //! # Problem statement
5 //! We are given a decimal string such as `12.34e56`. This string consists of integral (`12`),
6 //! fractional (`45`), and exponent (`56`) parts. All parts are optional and interpreted as zero
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.
15 //! Needless to say, this is quite hard, both in terms of implementation complexity and in terms
16 //! of CPU cycles taken.
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.
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.
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, `Fp`). When all these fail, we bite the bullet and resort to a
31 //! simple but very slow algorithm that involved computing `f * 10^e` fully and doing an iterative
32 //! search for the best approximation.
34 //! Primarily, this module and its children implement the algorithms described in:
35 //! "How to Read Floating Point Numbers Accurately" by William D. Clinger,
36 //! available online: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.4152
38 //! In addition, there are numerous helper functions that are used in the paper but not available
39 //! in Rust (or at least in core). Our version is additionally complicated by the need to handle
40 //! overflow and underflow and the desire to handle subnormal numbers. Bellerophon and
41 //! Algorithm R have trouble with overflow, subnormals, and underflow. We conservatively switch to
42 //! Algorithm M (with the modifications described in section 8 of the paper) well before the
43 //! inputs get into the critical region.
45 //! Another aspect that needs attention is the ``RawFloat`` trait by which almost all functions
46 //! are parametrized. One might think that it's enough to parse to `f64` and cast the result to
47 //! `f32`. Unfortunately this is not the world we live in, and this has nothing to do with using
48 //! base two or half-to-even rounding.
50 //! Consider for example two types `d2` and `d4` representing a decimal type with two decimal
51 //! digits and four decimal digits each and take "0.01499" as input. Let's use half-up rounding.
52 //! Going directly to two decimal digits gives `0.01`, but if we round to four digits first,
53 //! we get `0.0150`, which is then rounded up to `0.02`. The same principle applies to other
54 //! operations as well, if you want 0.5 ULP accuracy you need to do *everything* in full precision
55 //! and round *exactly once, at the end*, by considering all truncated bits at once.
57 //! FIXME: Although some code duplication is necessary, perhaps parts of the code could be shuffled
58 //! around such that less code is duplicated. Large parts of the algorithms are independent of the
59 //! float type to output, or only needs access to a few constants, which could be passed in as
64 //! The conversion should *never* panic. There are assertions and explicit panics in the code,
65 //! but they should never be triggered and only serve as internal sanity checks. Any panics should
66 //! be considered a bug.
68 //! There are unit tests but they are woefully inadequate at ensuring correctness, they only cover
69 //! a small percentage of possible errors. Far more extensive tests are located in the directory
70 //! `src/etc/test-float-parse` as a Python script.
72 //! A note on integer overflow: Many parts of this file perform arithmetic with the decimal
73 //! exponent `e`. Primarily, we shift the decimal point around: Before the first decimal digit,
74 //! after the last decimal digit, and so on. This could overflow if done carelessly. We rely on
75 //! the parsing submodule to only hand out sufficiently small exponents, where "sufficient" means
76 //! "such that the exponent +/- the number of decimal digits fits into a 64 bit integer".
77 //! Larger exponents are accepted, but we don't do arithmetic with them, they are immediately
78 //! turned into {positive,negative} {zero,infinity}.
83 reason
= "internal routines only exposed for testing",
88 use crate::str::FromStr
;
90 use self::num
::digits_to_big
;
91 use self::parse
::{parse_decimal, Decimal, ParseResult, Sign}
;
92 use self::rawfp
::RawFloat
;
97 // These two have their own tests.
101 macro_rules
! from_str_float_impl
{
103 #[stable(feature = "rust1", since = "1.0.0")]
104 impl FromStr
for $t
{
105 type Err
= ParseFloatError
;
107 /// Converts a string in base 10 to a float.
108 /// Accepts an optional decimal exponent.
110 /// This function accepts strings such as
114 /// * '2.5E10', or equivalently, '2.5e10'
117 /// * '.5', or, equivalently, '0.5'
118 /// * 'inf', '-inf', 'NaN'
120 /// Leading and trailing whitespace represent an error.
124 /// All strings that adhere to the following [EBNF] grammar
125 /// will result in an [`Ok`] being returned:
128 /// Float ::= Sign? ( 'inf' | 'NaN' | Number )
129 /// Number ::= ( Digit+ |
130 /// Digit+ '.' Digit* |
131 /// Digit* '.' Digit+ ) Exp?
132 /// Exp ::= [eE] Sign? Digit+
137 /// [EBNF]: https://www.w3.org/TR/REC-xml/#sec-notation
141 /// In some situations, some strings that should create a valid float
142 /// instead return an error. See [issue #31407] for details.
144 /// [issue #31407]: https://github.com/rust-lang/rust/issues/31407
152 /// `Err(ParseFloatError)` if the string did not represent a valid
153 /// number. Otherwise, `Ok(n)` where `n` is the floating-point
154 /// number represented by `src`.
156 fn from_str(src
: &str) -> Result
<Self, ParseFloatError
> {
162 from_str_float_impl
!(f32);
163 from_str_float_impl
!(f64);
165 /// An error which can be returned when parsing a float.
167 /// This error is used as the error type for the [`FromStr`] implementation
168 /// for [`f32`] and [`f64`].
173 /// use std::str::FromStr;
175 /// if let Err(e) = f64::from_str("a.12") {
176 /// println!("Failed conversion to f64: {}", e);
179 #[derive(Debug, Clone, PartialEq, Eq)]
180 #[stable(feature = "rust1", since = "1.0.0")]
181 pub struct ParseFloatError
{
182 kind
: FloatErrorKind
,
185 #[derive(Debug, Clone, PartialEq, Eq)]
186 enum FloatErrorKind
{
191 impl ParseFloatError
{
193 feature
= "int_error_internals",
194 reason
= "available through Error trait and this method should \
195 not be exposed publicly",
199 pub fn __description(&self) -> &str {
201 FloatErrorKind
::Empty
=> "cannot parse float from empty string",
202 FloatErrorKind
::Invalid
=> "invalid float literal",
207 #[stable(feature = "rust1", since = "1.0.0")]
208 impl fmt
::Display
for ParseFloatError
{
209 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
210 self.__description().fmt(f
)
214 fn pfe_empty() -> ParseFloatError
{
215 ParseFloatError { kind: FloatErrorKind::Empty }
218 fn pfe_invalid() -> ParseFloatError
{
219 ParseFloatError { kind: FloatErrorKind::Invalid }
222 /// Splits a decimal string into sign and the rest, without inspecting or validating the rest.
223 fn extract_sign(s
: &str) -> (Sign
, &str) {
224 match s
.as_bytes()[0] {
225 b'
+'
=> (Sign
::Positive
, &s
[1..]),
226 b'
-'
=> (Sign
::Negative
, &s
[1..]),
227 // If the string is invalid, we never use the sign, so we don't need to validate here.
228 _
=> (Sign
::Positive
, s
),
232 /// Converts a decimal string into a floating point number.
233 fn dec2flt
<T
: RawFloat
>(s
: &str) -> Result
<T
, ParseFloatError
> {
235 return Err(pfe_empty());
237 let (sign
, s
) = extract_sign(s
);
238 let flt
= match parse_decimal(s
) {
239 ParseResult
::Valid(decimal
) => convert(decimal
)?
,
240 ParseResult
::ShortcutToInf
=> T
::INFINITY
,
241 ParseResult
::ShortcutToZero
=> T
::ZERO
,
242 ParseResult
::Invalid
=> match s
{
243 "inf" => T
::INFINITY
,
246 return Err(pfe_invalid());
252 Sign
::Positive
=> Ok(flt
),
253 Sign
::Negative
=> Ok(-flt
),
257 /// The main workhorse for the decimal-to-float conversion: Orchestrate all the preprocessing
258 /// and figure out which algorithm should do the actual conversion.
259 fn convert
<T
: RawFloat
>(mut decimal
: Decimal
<'_
>) -> Result
<T
, ParseFloatError
> {
260 simplify(&mut decimal
);
261 if let Some(x
) = trivial_cases(&decimal
) {
264 // Remove/shift out the decimal point.
265 let e
= decimal
.exp
- decimal
.fractional
.len() as i64;
266 if let Some(x
) = algorithm
::fast_path(decimal
.integral
, decimal
.fractional
, e
) {
269 // Big32x40 is limited to 1280 bits, which translates to about 385 decimal digits.
270 // If we exceed this, we'll crash, so we error out before getting too close (within 10^10).
271 let upper_bound
= bound_intermediate_digits(&decimal
, e
);
272 if upper_bound
> 375 {
273 return Err(pfe_invalid());
275 let f
= digits_to_big(decimal
.integral
, decimal
.fractional
);
277 // Now the exponent certainly fits in 16 bit, which is used throughout the main algorithms.
279 // FIXME These bounds are rather conservative. A more careful analysis of the failure modes
280 // of Bellerophon could allow using it in more cases for a massive speed up.
281 let exponent_in_range
= table
::MIN_E
<= e
&& e
<= table
::MAX_E
;
282 let value_in_range
= upper_bound
<= T
::MAX_NORMAL_DIGITS
as u64;
283 if exponent_in_range
&& value_in_range
{
284 Ok(algorithm
::bellerophon(&f
, e
))
286 Ok(algorithm
::algorithm_m(&f
, e
))
290 // As written, this optimizes badly (see #27130, though it refers to an old version of the code).
291 // `inline(always)` is a workaround for that. There are only two call sites overall and it doesn't
292 // make code size worse.
294 /// Strip zeros where possible, even when this requires changing the exponent
296 fn simplify(decimal
: &mut Decimal
<'_
>) {
297 let is_zero
= &|&&d
: &&u8| -> bool { d == b'0' }
;
298 // Trimming these zeros does not change anything but may enable the fast path (< 15 digits).
299 let leading_zeros
= decimal
.integral
.iter().take_while(is_zero
).count();
300 decimal
.integral
= &decimal
.integral
[leading_zeros
..];
301 let trailing_zeros
= decimal
.fractional
.iter().rev().take_while(is_zero
).count();
302 let end
= decimal
.fractional
.len() - trailing_zeros
;
303 decimal
.fractional
= &decimal
.fractional
[..end
];
304 // Simplify numbers of the form 0.0...x and x...0.0, adjusting the exponent accordingly.
305 // This may not always be a win (possibly pushes some numbers out of the fast path), but it
306 // simplifies other parts significantly (notably, approximating the magnitude of the value).
307 if decimal
.integral
.is_empty() {
308 let leading_zeros
= decimal
.fractional
.iter().take_while(is_zero
).count();
309 decimal
.fractional
= &decimal
.fractional
[leading_zeros
..];
310 decimal
.exp
-= leading_zeros
as i64;
311 } else if decimal
.fractional
.is_empty() {
312 let trailing_zeros
= decimal
.integral
.iter().rev().take_while(is_zero
).count();
313 let end
= decimal
.integral
.len() - trailing_zeros
;
314 decimal
.integral
= &decimal
.integral
[..end
];
315 decimal
.exp
+= trailing_zeros
as i64;
319 /// Returns a quick-an-dirty upper bound on the size (log10) of the largest value that Algorithm R
320 /// and Algorithm M will compute while working on the given decimal.
321 fn bound_intermediate_digits(decimal
: &Decimal
<'_
>, e
: i64) -> u64 {
322 // We don't need to worry too much about overflow here thanks to trivial_cases() and the
323 // parser, which filter out the most extreme inputs for us.
324 let f_len
: u64 = decimal
.integral
.len() as u64 + decimal
.fractional
.len() as u64;
326 // In the case e >= 0, both algorithms compute about `f * 10^e`. Algorithm R proceeds to
327 // do some complicated calculations with this but we can ignore that for the upper bound
328 // because it also reduces the fraction beforehand, so we have plenty of buffer there.
331 // If e < 0, Algorithm R does roughly the same thing, but Algorithm M differs:
332 // It tries to find a positive number k such that `f << k / 10^e` is an in-range
333 // significand. This will result in about `2^53 * f * 10^e` < `10^17 * f * 10^e`.
334 // One input that triggers this is 0.33...33 (375 x 3).
335 f_len
+ (e
.abs() as u64) + 17
339 /// Detects obvious overflows and underflows without even looking at the decimal digits.
340 fn trivial_cases
<T
: RawFloat
>(decimal
: &Decimal
<'_
>) -> Option
<T
> {
341 // There were zeros but they were stripped by simplify()
342 if decimal
.integral
.is_empty() && decimal
.fractional
.is_empty() {
343 return Some(T
::ZERO
);
345 // This is a crude approximation of ceil(log10(the real value)). We don't need to worry too
346 // much about overflow here because the input length is tiny (at least compared to 2^64) and
347 // the parser already handles exponents whose absolute value is greater than 10^18
348 // (which is still 10^19 short of 2^64).
349 let max_place
= decimal
.exp
+ decimal
.integral
.len() as i64;
350 if max_place
> T
::INF_CUTOFF
{
351 return Some(T
::INFINITY
);
352 } else if max_place
< T
::ZERO_CUTOFF
{
353 return Some(T
::ZERO
);