]>
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`), | |
5869c6ff | 6 | //! fractional (`34`), and exponent (`56`) parts. All parts are optional and interpreted as zero |
e9174d1e SL |
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 | |
136023e0 XL |
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. | |
e9174d1e SL |
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 | //! | |
136023e0 XL |
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>. | |
e9174d1e SL |
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}. | |
e9174d1e SL |
70 | |
71 | #![doc(hidden)] | |
60c5eb7d XL |
72 | #![unstable( |
73 | feature = "dec2flt", | |
74 | reason = "internal routines only exposed for testing", | |
dfeec247 | 75 | issue = "none" |
60c5eb7d | 76 | )] |
e9174d1e | 77 | |
48663c56 XL |
78 | use crate::fmt; |
79 | use crate::str::FromStr; | |
e9174d1e | 80 | |
136023e0 XL |
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; | |
e9174d1e | 86 | |
136023e0 XL |
87 | mod common; |
88 | mod decimal; | |
89 | mod fpu; | |
90 | mod slow; | |
60c5eb7d | 91 | mod table; |
136023e0 XL |
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; | |
e9174d1e SL |
96 | pub mod parse; |
97 | ||
98 | macro_rules! from_str_float_impl { | |
9cc50fc6 | 99 | ($t:ty) => { |
e9174d1e SL |
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' | |
e9174d1e | 113 | /// * '5.' |
9fa01778 | 114 | /// * '.5', or, equivalently, '0.5' |
e9174d1e SL |
115 | /// * 'inf', '-inf', 'NaN' |
116 | /// | |
117 | /// Leading and trailing whitespace represent an error. | |
118 | /// | |
9fa01778 XL |
119 | /// # Grammar |
120 | /// | |
121 | /// All strings that adhere to the following [EBNF] grammar | |
122 | /// will result in an [`Ok`] being returned: | |
123 | /// | |
124 | /// ```txt | |
125 | /// Float ::= Sign? ( 'inf' | 'NaN' | Number ) | |
126 | /// Number ::= ( Digit+ | | |
127 | /// Digit+ '.' Digit* | | |
128 | /// Digit* '.' Digit+ ) Exp? | |
129 | /// Exp ::= [eE] Sign? Digit+ | |
130 | /// Sign ::= [+-] | |
131 | /// Digit ::= [0-9] | |
132 | /// ``` | |
133 | /// | |
134 | /// [EBNF]: https://www.w3.org/TR/REC-xml/#sec-notation | |
135 | /// | |
e9174d1e SL |
136 | /// # Arguments |
137 | /// | |
138 | /// * src - A string | |
139 | /// | |
140 | /// # Return value | |
141 | /// | |
142 | /// `Err(ParseFloatError)` if the string did not represent a valid | |
9fa01778 | 143 | /// number. Otherwise, `Ok(n)` where `n` is the floating-point |
e9174d1e SL |
144 | /// number represented by `src`. |
145 | #[inline] | |
146 | fn from_str(src: &str) -> Result<Self, ParseFloatError> { | |
147 | dec2flt(src) | |
148 | } | |
149 | } | |
60c5eb7d | 150 | }; |
e9174d1e | 151 | } |
9cc50fc6 SL |
152 | from_str_float_impl!(f32); |
153 | from_str_float_impl!(f64); | |
e9174d1e SL |
154 | |
155 | /// An error which can be returned when parsing a float. | |
7453a54e SL |
156 | /// |
157 | /// This error is used as the error type for the [`FromStr`] implementation | |
158 | /// for [`f32`] and [`f64`]. | |
159 | /// | |
1b1a35ee XL |
160 | /// # Example |
161 | /// | |
162 | /// ``` | |
163 | /// use std::str::FromStr; | |
164 | /// | |
165 | /// if let Err(e) = f64::from_str("a.12") { | |
166 | /// println!("Failed conversion to f64: {}", e); | |
167 | /// } | |
168 | /// ``` | |
9e0c209e | 169 | #[derive(Debug, Clone, PartialEq, Eq)] |
e9174d1e SL |
170 | #[stable(feature = "rust1", since = "1.0.0")] |
171 | pub struct ParseFloatError { | |
60c5eb7d | 172 | kind: FloatErrorKind, |
e9174d1e SL |
173 | } |
174 | ||
9e0c209e | 175 | #[derive(Debug, Clone, PartialEq, Eq)] |
e9174d1e SL |
176 | enum FloatErrorKind { |
177 | Empty, | |
178 | Invalid, | |
179 | } | |
180 | ||
181 | impl ParseFloatError { | |
60c5eb7d XL |
182 | #[unstable( |
183 | feature = "int_error_internals", | |
184 | reason = "available through Error trait and this method should \ | |
185 | not be exposed publicly", | |
dfeec247 | 186 | issue = "none" |
60c5eb7d | 187 | )] |
e9174d1e SL |
188 | #[doc(hidden)] |
189 | pub fn __description(&self) -> &str { | |
190 | match self.kind { | |
191 | FloatErrorKind::Empty => "cannot parse float from empty string", | |
192 | FloatErrorKind::Invalid => "invalid float literal", | |
193 | } | |
194 | } | |
195 | } | |
196 | ||
197 | #[stable(feature = "rust1", since = "1.0.0")] | |
198 | impl fmt::Display for ParseFloatError { | |
48663c56 | 199 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
e9174d1e SL |
200 | self.__description().fmt(f) |
201 | } | |
202 | } | |
203 | ||
136023e0 | 204 | pub(super) fn pfe_empty() -> ParseFloatError { |
e9174d1e SL |
205 | ParseFloatError { kind: FloatErrorKind::Empty } |
206 | } | |
207 | ||
136023e0 XL |
208 | // Used in unit tests, keep public. |
209 | // This is much better than making FloatErrorKind and ParseFloatError::kind public. | |
210 | pub fn pfe_invalid() -> ParseFloatError { | |
e9174d1e SL |
211 | ParseFloatError { kind: FloatErrorKind::Invalid } |
212 | } | |
213 | ||
136023e0 XL |
214 | /// Converts a `BiasedFp` to the closest machine float type. |
215 | fn biased_fp_to_float<T: RawFloat>(x: BiasedFp) -> T { | |
216 | let mut word = x.f; | |
217 | word |= (x.e as u64) << T::MANTISSA_EXPLICIT_BITS; | |
218 | T::from_u64_bits(word) | |
e9174d1e SL |
219 | } |
220 | ||
9fa01778 | 221 | /// Converts a decimal string into a floating point number. |
136023e0 XL |
222 | pub fn dec2flt<F: RawFloat>(s: &str) -> Result<F, ParseFloatError> { |
223 | let mut s = s.as_bytes(); | |
224 | let c = if let Some(&c) = s.first() { | |
225 | c | |
226 | } else { | |
60c5eb7d | 227 | return Err(pfe_empty()); |
136023e0 XL |
228 | }; |
229 | let negative = c == b'-'; | |
230 | if c == b'-' || c == b'+' { | |
231 | s = s.advance(1); | |
232 | } | |
233 | if s.is_empty() { | |
234 | return Err(pfe_invalid()); | |
e9174d1e | 235 | } |
136023e0 XL |
236 | |
237 | let num = match parse_number(s, negative) { | |
238 | Some(r) => r, | |
239 | None => { | |
240 | if let Some(value) = parse_inf_nan(s, negative) { | |
241 | return Ok(value); | |
cdc7bbd5 | 242 | } else { |
60c5eb7d XL |
243 | return Err(pfe_invalid()); |
244 | } | |
cdc7bbd5 | 245 | } |
e9174d1e | 246 | }; |
136023e0 XL |
247 | if let Some(value) = num.try_fast_path::<F>() { |
248 | return Ok(value); | |
e9174d1e | 249 | } |
e9174d1e | 250 | |
136023e0 XL |
251 | // If significant digits were truncated, then we can have rounding error |
252 | // only if `mantissa + 1` produces a different result. We also avoid | |
253 | // redundantly using the Eisel-Lemire algorithm if it was unable to | |
254 | // correctly round on the first pass. | |
255 | let mut fp = compute_float::<F>(num.exponent, num.mantissa); | |
256 | if num.many_digits && fp.e >= 0 && fp != compute_float::<F>(num.exponent, num.mantissa + 1) { | |
257 | fp.e = -1; | |
e9174d1e | 258 | } |
136023e0 XL |
259 | // Unable to correctly round the float using the Eisel-Lemire algorithm. |
260 | // Fallback to a slower, but always correct algorithm. | |
261 | if fp.e < 0 { | |
262 | fp = parse_long_mantissa::<F>(s); | |
7453a54e | 263 | } |
7453a54e | 264 | |
136023e0 XL |
265 | let mut float = biased_fp_to_float::<F>(fp); |
266 | if num.negative { | |
267 | float = -float; | |
e9174d1e | 268 | } |
136023e0 | 269 | Ok(float) |
e9174d1e | 270 | } |