]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
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 (`45`), 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, `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. | |
33 | //! | |
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 | |
37 | //! | |
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 | |
9fa01778 | 40 | //! overflow and underflow and the desire to handle subnormal numbers. Bellerophon and |
e9174d1e SL |
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. | |
44 | //! | |
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. | |
49 | //! | |
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. | |
56 | //! | |
9fa01778 | 57 | //! FIXME: Although some code duplication is necessary, perhaps parts of the code could be shuffled |
e9174d1e SL |
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 | |
60 | //! parameters. | |
61 | //! | |
62 | //! # Other | |
63 | //! | |
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. | |
67 | //! | |
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. | |
71 | //! | |
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}. | |
e9174d1e SL |
79 | |
80 | #![doc(hidden)] | |
60c5eb7d XL |
81 | #![unstable( |
82 | feature = "dec2flt", | |
83 | reason = "internal routines only exposed for testing", | |
dfeec247 | 84 | issue = "none" |
60c5eb7d | 85 | )] |
e9174d1e | 86 | |
48663c56 XL |
87 | use crate::fmt; |
88 | use crate::str::FromStr; | |
e9174d1e | 89 | |
e9174d1e | 90 | use self::num::digits_to_big; |
60c5eb7d | 91 | use self::parse::{parse_decimal, Decimal, ParseResult, Sign}; |
e9174d1e SL |
92 | use self::rawfp::RawFloat; |
93 | ||
94 | mod algorithm; | |
e9174d1e | 95 | mod num; |
60c5eb7d | 96 | mod table; |
e9174d1e | 97 | // These two have their own tests. |
e9174d1e | 98 | pub mod parse; |
60c5eb7d | 99 | pub mod rawfp; |
e9174d1e SL |
100 | |
101 | macro_rules! from_str_float_impl { | |
9cc50fc6 | 102 | ($t:ty) => { |
e9174d1e SL |
103 | #[stable(feature = "rust1", since = "1.0.0")] |
104 | impl FromStr for $t { | |
105 | type Err = ParseFloatError; | |
106 | ||
107 | /// Converts a string in base 10 to a float. | |
108 | /// Accepts an optional decimal exponent. | |
109 | /// | |
110 | /// This function accepts strings such as | |
111 | /// | |
112 | /// * '3.14' | |
113 | /// * '-3.14' | |
114 | /// * '2.5E10', or equivalently, '2.5e10' | |
115 | /// * '2.5E-10' | |
e9174d1e | 116 | /// * '5.' |
9fa01778 | 117 | /// * '.5', or, equivalently, '0.5' |
e9174d1e SL |
118 | /// * 'inf', '-inf', 'NaN' |
119 | /// | |
120 | /// Leading and trailing whitespace represent an error. | |
121 | /// | |
9fa01778 XL |
122 | /// # Grammar |
123 | /// | |
124 | /// All strings that adhere to the following [EBNF] grammar | |
125 | /// will result in an [`Ok`] being returned: | |
126 | /// | |
127 | /// ```txt | |
128 | /// Float ::= Sign? ( 'inf' | 'NaN' | Number ) | |
129 | /// Number ::= ( Digit+ | | |
130 | /// Digit+ '.' Digit* | | |
131 | /// Digit* '.' Digit+ ) Exp? | |
132 | /// Exp ::= [eE] Sign? Digit+ | |
133 | /// Sign ::= [+-] | |
134 | /// Digit ::= [0-9] | |
135 | /// ``` | |
136 | /// | |
137 | /// [EBNF]: https://www.w3.org/TR/REC-xml/#sec-notation | |
138 | /// | |
139 | /// # Known bugs | |
140 | /// | |
141 | /// In some situations, some strings that should create a valid float | |
142 | /// instead return an error. See [issue #31407] for details. | |
143 | /// | |
144 | /// [issue #31407]: https://github.com/rust-lang/rust/issues/31407 | |
145 | /// | |
e9174d1e SL |
146 | /// # Arguments |
147 | /// | |
148 | /// * src - A string | |
149 | /// | |
150 | /// # Return value | |
151 | /// | |
152 | /// `Err(ParseFloatError)` if the string did not represent a valid | |
9fa01778 | 153 | /// number. Otherwise, `Ok(n)` where `n` is the floating-point |
e9174d1e SL |
154 | /// number represented by `src`. |
155 | #[inline] | |
156 | fn from_str(src: &str) -> Result<Self, ParseFloatError> { | |
157 | dec2flt(src) | |
158 | } | |
159 | } | |
60c5eb7d | 160 | }; |
e9174d1e | 161 | } |
9cc50fc6 SL |
162 | from_str_float_impl!(f32); |
163 | from_str_float_impl!(f64); | |
e9174d1e SL |
164 | |
165 | /// An error which can be returned when parsing a float. | |
7453a54e SL |
166 | /// |
167 | /// This error is used as the error type for the [`FromStr`] implementation | |
168 | /// for [`f32`] and [`f64`]. | |
169 | /// | |
1b1a35ee XL |
170 | /// # Example |
171 | /// | |
172 | /// ``` | |
173 | /// use std::str::FromStr; | |
174 | /// | |
175 | /// if let Err(e) = f64::from_str("a.12") { | |
176 | /// println!("Failed conversion to f64: {}", e); | |
177 | /// } | |
178 | /// ``` | |
9e0c209e | 179 | #[derive(Debug, Clone, PartialEq, Eq)] |
e9174d1e SL |
180 | #[stable(feature = "rust1", since = "1.0.0")] |
181 | pub struct ParseFloatError { | |
60c5eb7d | 182 | kind: FloatErrorKind, |
e9174d1e SL |
183 | } |
184 | ||
9e0c209e | 185 | #[derive(Debug, Clone, PartialEq, Eq)] |
e9174d1e SL |
186 | enum FloatErrorKind { |
187 | Empty, | |
188 | Invalid, | |
189 | } | |
190 | ||
191 | impl ParseFloatError { | |
60c5eb7d XL |
192 | #[unstable( |
193 | feature = "int_error_internals", | |
194 | reason = "available through Error trait and this method should \ | |
195 | not be exposed publicly", | |
dfeec247 | 196 | issue = "none" |
60c5eb7d | 197 | )] |
e9174d1e SL |
198 | #[doc(hidden)] |
199 | pub fn __description(&self) -> &str { | |
200 | match self.kind { | |
201 | FloatErrorKind::Empty => "cannot parse float from empty string", | |
202 | FloatErrorKind::Invalid => "invalid float literal", | |
203 | } | |
204 | } | |
205 | } | |
206 | ||
207 | #[stable(feature = "rust1", since = "1.0.0")] | |
208 | impl fmt::Display for ParseFloatError { | |
48663c56 | 209 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
e9174d1e SL |
210 | self.__description().fmt(f) |
211 | } | |
212 | } | |
213 | ||
9cc50fc6 | 214 | fn pfe_empty() -> ParseFloatError { |
e9174d1e SL |
215 | ParseFloatError { kind: FloatErrorKind::Empty } |
216 | } | |
217 | ||
9cc50fc6 | 218 | fn pfe_invalid() -> ParseFloatError { |
e9174d1e SL |
219 | ParseFloatError { kind: FloatErrorKind::Invalid } |
220 | } | |
221 | ||
9fa01778 | 222 | /// Splits a decimal string into sign and the rest, without inspecting or validating the rest. |
e9174d1e SL |
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), | |
229 | } | |
230 | } | |
231 | ||
9fa01778 | 232 | /// Converts a decimal string into a floating point number. |
e9174d1e SL |
233 | fn dec2flt<T: RawFloat>(s: &str) -> Result<T, ParseFloatError> { |
234 | if s.is_empty() { | |
60c5eb7d | 235 | return Err(pfe_empty()); |
e9174d1e SL |
236 | } |
237 | let (sign, s) = extract_sign(s); | |
238 | let flt = match parse_decimal(s) { | |
54a0048b | 239 | ParseResult::Valid(decimal) => convert(decimal)?, |
cc61c64b XL |
240 | ParseResult::ShortcutToInf => T::INFINITY, |
241 | ParseResult::ShortcutToZero => T::ZERO, | |
e9174d1e | 242 | ParseResult::Invalid => match s { |
cc61c64b XL |
243 | "inf" => T::INFINITY, |
244 | "NaN" => T::NAN, | |
60c5eb7d XL |
245 | _ => { |
246 | return Err(pfe_invalid()); | |
247 | } | |
248 | }, | |
e9174d1e SL |
249 | }; |
250 | ||
251 | match sign { | |
252 | Sign::Positive => Ok(flt), | |
253 | Sign::Negative => Ok(-flt), | |
254 | } | |
255 | } | |
256 | ||
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. | |
48663c56 | 259 | fn convert<T: RawFloat>(mut decimal: Decimal<'_>) -> Result<T, ParseFloatError> { |
e9174d1e SL |
260 | simplify(&mut decimal); |
261 | if let Some(x) = trivial_cases(&decimal) { | |
262 | return Ok(x); | |
263 | } | |
e9174d1e SL |
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) { | |
267 | return Ok(x); | |
268 | } | |
269 | // Big32x40 is limited to 1280 bits, which translates to about 385 decimal digits. | |
7453a54e SL |
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 { | |
e9174d1e SL |
273 | return Err(pfe_invalid()); |
274 | } | |
275 | let f = digits_to_big(decimal.integral, decimal.fractional); | |
276 | ||
277 | // Now the exponent certainly fits in 16 bit, which is used throughout the main algorithms. | |
278 | let e = e as i16; | |
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; | |
cc61c64b | 282 | let value_in_range = upper_bound <= T::MAX_NORMAL_DIGITS as u64; |
e9174d1e SL |
283 | if exponent_in_range && value_in_range { |
284 | Ok(algorithm::bellerophon(&f, e)) | |
285 | } else { | |
286 | Ok(algorithm::algorithm_m(&f, e)) | |
287 | } | |
288 | } | |
289 | ||
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. | |
293 | ||
294 | /// Strip zeros where possible, even when this requires changing the exponent | |
295 | #[inline(always)] | |
48663c56 | 296 | fn simplify(decimal: &mut Decimal<'_>) { |
e9174d1e SL |
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; | |
316 | } | |
317 | } | |
318 | ||
532ac7d7 XL |
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. | |
48663c56 | 321 | fn bound_intermediate_digits(decimal: &Decimal<'_>, e: i64) -> u64 { |
7453a54e SL |
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; | |
325 | if e >= 0 { | |
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. | |
329 | f_len + (e as u64) | |
330 | } else { | |
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 | |
336 | } | |
337 | } | |
338 | ||
532ac7d7 | 339 | /// Detects obvious overflows and underflows without even looking at the decimal digits. |
48663c56 | 340 | fn trivial_cases<T: RawFloat>(decimal: &Decimal<'_>) -> Option<T> { |
e9174d1e SL |
341 | // There were zeros but they were stripped by simplify() |
342 | if decimal.integral.is_empty() && decimal.fractional.is_empty() { | |
cc61c64b | 343 | return Some(T::ZERO); |
e9174d1e | 344 | } |
7453a54e SL |
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). | |
e9174d1e | 349 | let max_place = decimal.exp + decimal.integral.len() as i64; |
cc61c64b XL |
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); | |
e9174d1e SL |
354 | } |
355 | None | |
356 | } |