]>
Commit | Line | Data |
---|---|---|
d9579d0f AL |
1 | // Copyright 2015 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | /*! | |
12 | ||
13 | Floating-point number to decimal conversion routines. | |
14 | ||
15 | # Problem statement | |
16 | ||
17 | We are given the floating-point number `v = f * 2^e` with an integer `f`, | |
18 | and its bounds `minus` and `plus` such that any number between `v - minus` and | |
19 | `v + plus` will be rounded to `v`. For the simplicity we assume that | |
20 | this range is exclusive. Then we would like to get the unique decimal | |
21 | representation `V = 0.d[0..n-1] * 10^k` such that: | |
22 | ||
23 | - `d[0]` is non-zero. | |
24 | ||
25 | - It's correctly rounded when parsed back: `v - minus < V < v + plus`. | |
26 | Furthermore it is shortest such one, i.e. there is no representation | |
27 | with less than `n` digits that is correctly rounded. | |
28 | ||
29 | - It's closest to the original value: `abs(V - v) <= 10^(k-n) / 2`. Note that | |
30 | there might be two representations satisfying this uniqueness requirement, | |
31 | in which case some tie-breaking mechanism is used. | |
32 | ||
33 | We will call this mode of operation as to the *shortest* mode. This mode is used | |
34 | when there is no additional constraint, and can be thought as a "natural" mode | |
35 | as it matches the ordinary intuition (it at least prints `0.1f32` as "0.1"). | |
36 | ||
37 | We have two more modes of operation closely related to each other. In these modes | |
38 | we are given either the number of significant digits `n` or the last-digit | |
39 | limitation `limit` (which determines the actual `n`), and we would like to get | |
40 | the representation `V = 0.d[0..n-1] * 10^k` such that: | |
41 | ||
42 | - `d[0]` is non-zero, unless `n` was zero in which case only `k` is returned. | |
43 | ||
44 | - It's closest to the original value: `abs(V - v) <= 10^(k-n) / 2`. Again, | |
45 | there might be some tie-breaking mechanism. | |
46 | ||
47 | When `limit` is given but not `n`, we set `n` such that `k - n = limit` | |
48 | so that the last digit `d[n-1]` is scaled by `10^(k-n) = 10^limit`. | |
49 | If such `n` is negative, we clip it to zero so that we will only get `k`. | |
50 | We are also limited by the supplied buffer. This limitation is used to print | |
51 | the number up to given number of fractional digits without knowing | |
52 | the correct `k` beforehand. | |
53 | ||
54 | We will call the mode of operation requiring `n` as to the *exact* mode, | |
55 | and one requiring `limit` as to the *fixed* mode. The exact mode is a subset of | |
56 | the fixed mode: the sufficiently large last-digit limitation will eventually fill | |
57 | the supplied buffer and let the algorithm to return. | |
58 | ||
59 | # Implementation overview | |
60 | ||
61 | It is easy to get the floating point printing correct but slow (Russ Cox has | |
62 | [demonstrated](http://research.swtch.com/ftoa) how it's easy), or incorrect but | |
63 | fast (naïve division and modulo). But it is surprisingly hard to print | |
64 | floating point numbers correctly *and* efficiently. | |
65 | ||
66 | There are two classes of algorithms widely known to be correct. | |
67 | ||
68 | - The "Dragon" family of algorithm is first described by Guy L. Steele Jr. and | |
69 | Jon L. White. They rely on the fixed-size big integer for their correctness. | |
70 | A slight improvement was found later, which is posthumously described by | |
71 | Robert G. Burger and R. Kent Dybvig. David Gay's `dtoa.c` routine is | |
72 | a popular implementation of this strategy. | |
73 | ||
74 | - The "Grisu" family of algorithm is first described by Florian Loitsch. | |
75 | They use very cheap integer-only procedure to determine the close-to-correct | |
76 | representation which is at least guaranteed to be shortest. The variant, | |
77 | Grisu3, actively detects if the resulting representation is incorrect. | |
78 | ||
79 | We implement both algorithms with necessary tweaks to suit our requirements. | |
80 | In particular, published literatures are short of the actual implementation | |
81 | difficulties like how to avoid arithmetic overflows. Each implementation, | |
82 | available in `strategy::dragon` and `strategy::grisu` respectively, | |
83 | extensively describes all necessary justifications and many proofs for them. | |
84 | (It is still difficult to follow though. You have been warned.) | |
85 | ||
86 | Both implementations expose two public functions: | |
87 | ||
88 | - `format_shortest(decoded, buf)`, which always needs at least | |
89 | `MAX_SIG_DIGITS` digits of buffer. Implements the shortest mode. | |
90 | ||
91 | - `format_exact(decoded, buf, limit)`, which accepts as small as | |
92 | one digit of buffer. Implements exact and fixed modes. | |
93 | ||
94 | They try to fill the `u8` buffer with digits and returns the number of digits | |
95 | written and the exponent `k`. They are total for all finite `f32` and `f64` | |
96 | inputs (Grisu internally falls back to Dragon if necessary). | |
97 | ||
98 | The rendered digits are formatted into the actual string form with | |
99 | four functions: | |
100 | ||
101 | - `to_shortest_str` prints the shortest representation, which can be padded by | |
102 | zeroes to make *at least* given number of fractional digits. | |
103 | ||
104 | - `to_shortest_exp_str` prints the shortest representation, which can be | |
105 | padded by zeroes when its exponent is in the specified ranges, | |
106 | or can be printed in the exponential form such as `1.23e45`. | |
107 | ||
108 | - `to_exact_exp_str` prints the exact representation with given number of | |
109 | digits in the exponential form. | |
110 | ||
111 | - `to_exact_fixed_str` prints the fixed representation with *exactly* | |
112 | given number of fractional digits. | |
113 | ||
114 | They all return a slice of preallocated `Part` array, which corresponds to | |
115 | the individual part of strings: a fixed string, a part of rendered digits, | |
116 | a number of zeroes or a small (`u16`) number. The caller is expected to | |
117 | provide a large enough buffer and `Part` array, and to assemble the final | |
118 | string from resulting `Part`s itself. | |
119 | ||
120 | All algorithms and formatting functions are accompanied by extensive tests | |
121 | in `coretest::num::flt2dec` module. It also shows how to use individual | |
122 | functions. | |
123 | ||
124 | */ | |
125 | ||
126 | // while this is extensively documented, this is in principle private which is | |
127 | // only made public for testing. do not expose us. | |
128 | #![doc(hidden)] | |
62682a34 | 129 | #![unstable(feature = "flt2dec", |
e9174d1e SL |
130 | reason = "internal routines only exposed for testing", |
131 | issue = "0")] | |
d9579d0f | 132 | |
e9174d1e | 133 | use prelude::v1::*; |
d9579d0f | 134 | use i16; |
d9579d0f AL |
135 | pub use self::decoder::{decode, DecodableFloat, FullDecoded, Decoded}; |
136 | ||
137 | pub mod estimator; | |
d9579d0f AL |
138 | pub mod decoder; |
139 | ||
140 | /// Digit-generation algorithms. | |
141 | pub mod strategy { | |
142 | pub mod dragon; | |
143 | pub mod grisu; | |
144 | } | |
145 | ||
146 | /// The minimum size of buffer necessary for the shortest mode. | |
147 | /// | |
148 | /// It is a bit non-trivial to derive, but this is one plus the maximal number of | |
149 | /// significant decimal digits from formatting algorithms with the shortest result. | |
150 | /// The exact formula is `ceil(# bits in mantissa * log_10 2 + 1)`. | |
151 | pub const MAX_SIG_DIGITS: usize = 17; | |
152 | ||
153 | /// When `d[..n]` contains decimal digits, increase the last digit and propagate carry. | |
154 | /// Returns a next digit when it causes the length change. | |
155 | #[doc(hidden)] | |
156 | pub fn round_up(d: &mut [u8], n: usize) -> Option<u8> { | |
157 | match d[..n].iter().rposition(|&c| c != b'9') { | |
158 | Some(i) => { // d[i+1..n] is all nines | |
159 | d[i] += 1; | |
160 | for j in i+1..n { d[j] = b'0'; } | |
161 | None | |
162 | } | |
163 | None if n > 0 => { // 999..999 rounds to 1000..000 with an increased exponent | |
164 | d[0] = b'1'; | |
165 | for j in 1..n { d[j] = b'0'; } | |
166 | Some(b'0') | |
167 | } | |
168 | None => { // an empty buffer rounds up (a bit strange but reasonable) | |
169 | Some(b'1') | |
170 | } | |
171 | } | |
172 | } | |
173 | ||
174 | /// Formatted parts. | |
175 | #[derive(Copy, Clone, PartialEq, Eq, Debug)] | |
176 | pub enum Part<'a> { | |
177 | /// Given number of zero digits. | |
178 | Zero(usize), | |
179 | /// A literal number up to 5 digits. | |
180 | Num(u16), | |
181 | /// A verbatim copy of given bytes. | |
182 | Copy(&'a [u8]), | |
183 | } | |
184 | ||
185 | impl<'a> Part<'a> { | |
186 | /// Returns the exact byte length of given part. | |
187 | pub fn len(&self) -> usize { | |
188 | match *self { | |
189 | Part::Zero(nzeroes) => nzeroes, | |
190 | Part::Num(v) => if v < 1_000 { if v < 10 { 1 } else if v < 100 { 2 } else { 3 } } | |
191 | else { if v < 10_000 { 4 } else { 5 } }, | |
192 | Part::Copy(buf) => buf.len(), | |
193 | } | |
194 | } | |
195 | ||
196 | /// Writes a part into the supplied buffer. | |
197 | /// Returns the number of written bytes, or `None` if the buffer is not enough. | |
198 | /// (It may still leave partially written bytes in the buffer; do not rely on that.) | |
199 | pub fn write(&self, out: &mut [u8]) -> Option<usize> { | |
200 | let len = self.len(); | |
201 | if out.len() >= len { | |
202 | match *self { | |
203 | Part::Zero(nzeroes) => { | |
204 | for c in &mut out[..nzeroes] { *c = b'0'; } | |
205 | } | |
206 | Part::Num(mut v) => { | |
207 | for c in out[..len].iter_mut().rev() { | |
208 | *c = b'0' + (v % 10) as u8; | |
209 | v /= 10; | |
210 | } | |
211 | } | |
212 | Part::Copy(buf) => { | |
7453a54e | 213 | out[..buf.len()].copy_from_slice(buf); |
d9579d0f AL |
214 | } |
215 | } | |
216 | Some(len) | |
217 | } else { | |
218 | None | |
219 | } | |
220 | } | |
221 | } | |
222 | ||
223 | /// Formatted result containing one or more parts. | |
224 | /// This can be written to the byte buffer or converted to the allocated string. | |
54a0048b | 225 | #[allow(missing_debug_implementations)] |
d9579d0f AL |
226 | #[derive(Clone)] |
227 | pub struct Formatted<'a> { | |
228 | /// A byte slice representing a sign, either `""`, `"-"` or `"+"`. | |
229 | pub sign: &'static [u8], | |
230 | /// Formatted parts to be rendered after a sign and optional zero padding. | |
231 | pub parts: &'a [Part<'a>], | |
232 | } | |
233 | ||
234 | impl<'a> Formatted<'a> { | |
235 | /// Returns the exact byte length of combined formatted result. | |
236 | pub fn len(&self) -> usize { | |
237 | let mut len = self.sign.len(); | |
238 | for part in self.parts { | |
239 | len += part.len(); | |
240 | } | |
241 | len | |
242 | } | |
243 | ||
244 | /// Writes all formatted parts into the supplied buffer. | |
245 | /// Returns the number of written bytes, or `None` if the buffer is not enough. | |
246 | /// (It may still leave partially written bytes in the buffer; do not rely on that.) | |
247 | pub fn write(&self, out: &mut [u8]) -> Option<usize> { | |
248 | if out.len() < self.sign.len() { return None; } | |
7453a54e | 249 | out[..self.sign.len()].copy_from_slice(self.sign); |
d9579d0f AL |
250 | |
251 | let mut written = self.sign.len(); | |
252 | for part in self.parts { | |
253 | match part.write(&mut out[written..]) { | |
254 | Some(len) => { written += len; } | |
255 | None => { return None; } | |
256 | } | |
257 | } | |
258 | Some(written) | |
259 | } | |
260 | } | |
261 | ||
262 | /// Formats given decimal digits `0.<...buf...> * 10^exp` into the decimal form | |
263 | /// with at least given number of fractional digits. The result is stored to | |
264 | /// the supplied parts array and a slice of written parts is returned. | |
265 | /// | |
266 | /// `frac_digits` can be less than the number of actual fractional digits in `buf`; | |
267 | /// it will be ignored and full digits will be printed. It is only used to print | |
268 | /// additional zeroes after rendered digits. Thus `frac_digits` of 0 means that | |
269 | /// it will only print given digits and nothing else. | |
270 | fn digits_to_dec_str<'a>(buf: &'a [u8], exp: i16, frac_digits: usize, | |
271 | parts: &'a mut [Part<'a>]) -> &'a [Part<'a>] { | |
272 | assert!(!buf.is_empty()); | |
273 | assert!(buf[0] > b'0'); | |
274 | assert!(parts.len() >= 4); | |
275 | ||
276 | // if there is the restriction on the last digit position, `buf` is assumed to be | |
277 | // left-padded with the virtual zeroes. the number of virtual zeroes, `nzeroes`, | |
278 | // equals to `max(0, exp + frac_digits - buf.len())`, so that the position of | |
279 | // the last digit `exp - buf.len() - nzeroes` is no more than `-frac_digits`: | |
280 | // | |
281 | // |<-virtual->| | |
282 | // |<---- buf ---->| zeroes | exp | |
283 | // 0. 1 2 3 4 5 6 7 8 9 _ _ _ _ _ _ x 10 | |
284 | // | | | | |
285 | // 10^exp 10^(exp-buf.len()) 10^(exp-buf.len()-nzeroes) | |
286 | // | |
287 | // `nzeroes` is individually calculated for each case in order to avoid overflow. | |
288 | ||
289 | if exp <= 0 { | |
290 | // the decimal point is before rendered digits: [0.][000...000][1234][____] | |
291 | let minus_exp = -(exp as i32) as usize; | |
292 | parts[0] = Part::Copy(b"0."); | |
293 | parts[1] = Part::Zero(minus_exp); | |
294 | parts[2] = Part::Copy(buf); | |
295 | if frac_digits > buf.len() && frac_digits - buf.len() > minus_exp { | |
296 | parts[3] = Part::Zero((frac_digits - buf.len()) - minus_exp); | |
297 | &parts[..4] | |
298 | } else { | |
299 | &parts[..3] | |
300 | } | |
301 | } else { | |
302 | let exp = exp as usize; | |
303 | if exp < buf.len() { | |
304 | // the decimal point is inside rendered digits: [12][.][34][____] | |
305 | parts[0] = Part::Copy(&buf[..exp]); | |
306 | parts[1] = Part::Copy(b"."); | |
307 | parts[2] = Part::Copy(&buf[exp..]); | |
308 | if frac_digits > buf.len() - exp { | |
309 | parts[3] = Part::Zero(frac_digits - (buf.len() - exp)); | |
310 | &parts[..4] | |
311 | } else { | |
312 | &parts[..3] | |
313 | } | |
314 | } else { | |
315 | // the decimal point is after rendered digits: [1234][____0000] or [1234][__][.][__]. | |
316 | parts[0] = Part::Copy(buf); | |
317 | parts[1] = Part::Zero(exp - buf.len()); | |
318 | if frac_digits > 0 { | |
319 | parts[2] = Part::Copy(b"."); | |
320 | parts[3] = Part::Zero(frac_digits); | |
321 | &parts[..4] | |
322 | } else { | |
323 | &parts[..2] | |
324 | } | |
325 | } | |
326 | } | |
327 | } | |
328 | ||
329 | /// Formats given decimal digits `0.<...buf...> * 10^exp` into the exponential form | |
330 | /// with at least given number of significant digits. When `upper` is true, | |
331 | /// the exponent will be prefixed by `E`; otherwise that's `e`. The result is | |
332 | /// stored to the supplied parts array and a slice of written parts is returned. | |
333 | /// | |
334 | /// `min_digits` can be less than the number of actual significant digits in `buf`; | |
335 | /// it will be ignored and full digits will be printed. It is only used to print | |
336 | /// additional zeroes after rendered digits. Thus `min_digits` of 0 means that | |
337 | /// it will only print given digits and nothing else. | |
338 | fn digits_to_exp_str<'a>(buf: &'a [u8], exp: i16, min_ndigits: usize, upper: bool, | |
339 | parts: &'a mut [Part<'a>]) -> &'a [Part<'a>] { | |
340 | assert!(!buf.is_empty()); | |
341 | assert!(buf[0] > b'0'); | |
342 | assert!(parts.len() >= 6); | |
343 | ||
344 | let mut n = 0; | |
345 | ||
346 | parts[n] = Part::Copy(&buf[..1]); | |
347 | n += 1; | |
348 | ||
349 | if buf.len() > 1 || min_ndigits > 1 { | |
350 | parts[n] = Part::Copy(b"."); | |
351 | parts[n + 1] = Part::Copy(&buf[1..]); | |
352 | n += 2; | |
353 | if min_ndigits > buf.len() { | |
354 | parts[n] = Part::Zero(min_ndigits - buf.len()); | |
355 | n += 1; | |
356 | } | |
357 | } | |
358 | ||
359 | // 0.1234 x 10^exp = 1.234 x 10^(exp-1) | |
360 | let exp = exp as i32 - 1; // avoid underflow when exp is i16::MIN | |
361 | if exp < 0 { | |
362 | parts[n] = Part::Copy(if upper { b"E-" } else { b"e-" }); | |
363 | parts[n + 1] = Part::Num(-exp as u16); | |
364 | } else { | |
365 | parts[n] = Part::Copy(if upper { b"E" } else { b"e" }); | |
366 | parts[n + 1] = Part::Num(exp as u16); | |
367 | } | |
368 | &parts[..n + 2] | |
369 | } | |
370 | ||
371 | /// Sign formatting options. | |
372 | #[derive(Copy, Clone, PartialEq, Eq, Debug)] | |
373 | pub enum Sign { | |
374 | /// Prints `-` only for the negative non-zero values. | |
375 | Minus, // -inf -1 0 0 1 inf nan | |
376 | /// Prints `-` only for any negative values (including the negative zero). | |
377 | MinusRaw, // -inf -1 -0 0 1 inf nan | |
378 | /// Prints `-` for the negative non-zero values, or `+` otherwise. | |
379 | MinusPlus, // -inf -1 +0 +0 +1 +inf nan | |
380 | /// Prints `-` for any negative values (including the negative zero), or `+` otherwise. | |
381 | MinusPlusRaw, // -inf -1 -0 +0 +1 +inf nan | |
382 | } | |
383 | ||
384 | /// Returns the static byte string corresponding to the sign to be formatted. | |
385 | /// It can be either `b""`, `b"+"` or `b"-"`. | |
386 | fn determine_sign(sign: Sign, decoded: &FullDecoded, negative: bool) -> &'static [u8] { | |
387 | match (*decoded, sign) { | |
388 | (FullDecoded::Nan, _) => b"", | |
389 | (FullDecoded::Zero, Sign::Minus) => b"", | |
390 | (FullDecoded::Zero, Sign::MinusRaw) => if negative { b"-" } else { b"" }, | |
391 | (FullDecoded::Zero, Sign::MinusPlus) => b"+", | |
392 | (FullDecoded::Zero, Sign::MinusPlusRaw) => if negative { b"-" } else { b"+" }, | |
393 | (_, Sign::Minus) | (_, Sign::MinusRaw) => if negative { b"-" } else { b"" }, | |
394 | (_, Sign::MinusPlus) | (_, Sign::MinusPlusRaw) => if negative { b"-" } else { b"+" }, | |
395 | } | |
396 | } | |
397 | ||
398 | /// Formats given floating point number into the decimal form with at least | |
399 | /// given number of fractional digits. The result is stored to the supplied parts | |
400 | /// array while utilizing given byte buffer as a scratch. `upper` is currently | |
401 | /// unused but left for the future decision to change the case of non-finite values, | |
402 | /// i.e. `inf` and `nan`. The first part to be rendered is always a `Part::Sign` | |
403 | /// (which can be an empty string if no sign is rendered). | |
404 | /// | |
405 | /// `format_shortest` should be the underlying digit-generation function. | |
406 | /// You probably would want `strategy::grisu::format_shortest` for this. | |
407 | /// | |
408 | /// `frac_digits` can be less than the number of actual fractional digits in `v`; | |
409 | /// it will be ignored and full digits will be printed. It is only used to print | |
410 | /// additional zeroes after rendered digits. Thus `frac_digits` of 0 means that | |
411 | /// it will only print given digits and nothing else. | |
412 | /// | |
413 | /// The byte buffer should be at least `MAX_SIG_DIGITS` bytes long. | |
414 | /// There should be at least 5 parts available, due to the worst case like | |
415 | /// `[+][0.][0000][45][0000]` with `frac_digits = 10`. | |
416 | pub fn to_shortest_str<'a, T, F>(mut format_shortest: F, v: T, | |
417 | sign: Sign, frac_digits: usize, _upper: bool, | |
418 | buf: &'a mut [u8], parts: &'a mut [Part<'a>]) -> Formatted<'a> | |
419 | where T: DecodableFloat, F: FnMut(&Decoded, &mut [u8]) -> (usize, i16) { | |
420 | assert!(parts.len() >= 4); | |
421 | assert!(buf.len() >= MAX_SIG_DIGITS); | |
422 | ||
423 | let (negative, full_decoded) = decode(v); | |
424 | let sign = determine_sign(sign, &full_decoded, negative); | |
425 | match full_decoded { | |
426 | FullDecoded::Nan => { | |
427 | parts[0] = Part::Copy(b"NaN"); | |
428 | Formatted { sign: sign, parts: &parts[..1] } | |
429 | } | |
430 | FullDecoded::Infinite => { | |
431 | parts[0] = Part::Copy(b"inf"); | |
432 | Formatted { sign: sign, parts: &parts[..1] } | |
433 | } | |
434 | FullDecoded::Zero => { | |
435 | if frac_digits > 0 { // [0.][0000] | |
436 | parts[0] = Part::Copy(b"0."); | |
437 | parts[1] = Part::Zero(frac_digits); | |
438 | Formatted { sign: sign, parts: &parts[..2] } | |
439 | } else { | |
440 | parts[0] = Part::Copy(b"0"); | |
441 | Formatted { sign: sign, parts: &parts[..1] } | |
442 | } | |
443 | } | |
444 | FullDecoded::Finite(ref decoded) => { | |
445 | let (len, exp) = format_shortest(decoded, buf); | |
446 | Formatted { sign: sign, | |
447 | parts: digits_to_dec_str(&buf[..len], exp, frac_digits, parts) } | |
448 | } | |
449 | } | |
450 | } | |
451 | ||
452 | /// Formats given floating point number into the decimal form or | |
453 | /// the exponential form, depending on the resulting exponent. The result is | |
454 | /// stored to the supplied parts array while utilizing given byte buffer | |
455 | /// as a scratch. `upper` is used to determine the case of non-finite values | |
456 | /// (`inf` and `nan`) or the case of the exponent prefix (`e` or `E`). | |
457 | /// The first part to be rendered is always a `Part::Sign` (which can be | |
458 | /// an empty string if no sign is rendered). | |
459 | /// | |
460 | /// `format_shortest` should be the underlying digit-generation function. | |
461 | /// You probably would want `strategy::grisu::format_shortest` for this. | |
462 | /// | |
463 | /// The `dec_bounds` is a tuple `(lo, hi)` such that the number is formatted | |
b039eaaf | 464 | /// as decimal only when `10^lo <= V < 10^hi`. Note that this is the *apparent* `V` |
d9579d0f AL |
465 | /// instead of the actual `v`! Thus any printed exponent in the exponential form |
466 | /// cannot be in this range, avoiding any confusion. | |
467 | /// | |
468 | /// The byte buffer should be at least `MAX_SIG_DIGITS` bytes long. | |
469 | /// There should be at least 7 parts available, due to the worst case like | |
470 | /// `[+][1][.][2345][e][-][67]`. | |
471 | pub fn to_shortest_exp_str<'a, T, F>(mut format_shortest: F, v: T, | |
472 | sign: Sign, dec_bounds: (i16, i16), upper: bool, | |
473 | buf: &'a mut [u8], parts: &'a mut [Part<'a>]) -> Formatted<'a> | |
474 | where T: DecodableFloat, F: FnMut(&Decoded, &mut [u8]) -> (usize, i16) { | |
475 | assert!(parts.len() >= 6); | |
476 | assert!(buf.len() >= MAX_SIG_DIGITS); | |
477 | assert!(dec_bounds.0 <= dec_bounds.1); | |
478 | ||
479 | let (negative, full_decoded) = decode(v); | |
480 | let sign = determine_sign(sign, &full_decoded, negative); | |
481 | match full_decoded { | |
482 | FullDecoded::Nan => { | |
483 | parts[0] = Part::Copy(b"NaN"); | |
484 | Formatted { sign: sign, parts: &parts[..1] } | |
485 | } | |
486 | FullDecoded::Infinite => { | |
487 | parts[0] = Part::Copy(b"inf"); | |
488 | Formatted { sign: sign, parts: &parts[..1] } | |
489 | } | |
490 | FullDecoded::Zero => { | |
491 | parts[0] = if dec_bounds.0 <= 0 && 0 < dec_bounds.1 { | |
492 | Part::Copy(b"0") | |
493 | } else { | |
494 | Part::Copy(if upper { b"0E0" } else { b"0e0" }) | |
495 | }; | |
496 | Formatted { sign: sign, parts: &parts[..1] } | |
497 | } | |
498 | FullDecoded::Finite(ref decoded) => { | |
499 | let (len, exp) = format_shortest(decoded, buf); | |
500 | let vis_exp = exp as i32 - 1; | |
501 | let parts = if dec_bounds.0 as i32 <= vis_exp && vis_exp < dec_bounds.1 as i32 { | |
502 | digits_to_dec_str(&buf[..len], exp, 0, parts) | |
503 | } else { | |
504 | digits_to_exp_str(&buf[..len], exp, 0, upper, parts) | |
505 | }; | |
506 | Formatted { sign: sign, parts: parts } | |
507 | } | |
508 | } | |
509 | } | |
510 | ||
511 | /// Returns rather crude approximation (upper bound) for the maximum buffer size | |
512 | /// calculated from the given decoded exponent. | |
513 | /// | |
514 | /// The exact limit is: | |
515 | /// | |
516 | /// - when `exp < 0`, the maximum length is `ceil(log_10 (5^-exp * (2^64 - 1)))`. | |
517 | /// - when `exp >= 0`, the maximum length is `ceil(log_10 (2^exp * (2^64 - 1)))`. | |
518 | /// | |
519 | /// `ceil(log_10 (x^exp * (2^64 - 1)))` is less than `ceil(log_10 (2^64 - 1)) + | |
520 | /// ceil(exp * log_10 x)`, which is in turn less than `20 + (1 + exp * log_10 x)`. | |
521 | /// We use the facts that `log_10 2 < 5/16` and `log_10 5 < 12/16`, which is | |
522 | /// enough for our purposes. | |
523 | /// | |
524 | /// Why do we need this? `format_exact` functions will fill the entire buffer | |
525 | /// unless limited by the last digit restriction, but it is possible that | |
526 | /// the number of digits requested is ridiculously large (say, 30,000 digits). | |
527 | /// The vast majority of buffer will be filled with zeroes, so we don't want to | |
528 | /// allocate all the buffer beforehand. Consequently, for any given arguments, | |
529 | /// 826 bytes of buffer should be sufficient for `f64`. Compare this with | |
530 | /// the actual number for the worst case: 770 bytes (when `exp = -1074`). | |
531 | fn estimate_max_buf_len(exp: i16) -> usize { | |
532 | 21 + ((if exp < 0 { -12 } else { 5 } * exp as i32) as usize >> 4) | |
533 | } | |
534 | ||
535 | /// Formats given floating point number into the exponential form with | |
536 | /// exactly given number of significant digits. The result is stored to | |
537 | /// the supplied parts array while utilizing given byte buffer as a scratch. | |
538 | /// `upper` is used to determine the case of the exponent prefix (`e` or `E`). | |
539 | /// The first part to be rendered is always a `Part::Sign` (which can be | |
540 | /// an empty string if no sign is rendered). | |
541 | /// | |
542 | /// `format_exact` should be the underlying digit-generation function. | |
543 | /// You probably would want `strategy::grisu::format_exact` for this. | |
544 | /// | |
545 | /// The byte buffer should be at least `ndigits` bytes long unless `ndigits` is | |
546 | /// so large that only the fixed number of digits will be ever written. | |
547 | /// (The tipping point for `f64` is about 800, so 1000 bytes should be enough.) | |
548 | /// There should be at least 7 parts available, due to the worst case like | |
549 | /// `[+][1][.][2345][e][-][67]`. | |
550 | pub fn to_exact_exp_str<'a, T, F>(mut format_exact: F, v: T, | |
551 | sign: Sign, ndigits: usize, upper: bool, | |
552 | buf: &'a mut [u8], parts: &'a mut [Part<'a>]) -> Formatted<'a> | |
553 | where T: DecodableFloat, F: FnMut(&Decoded, &mut [u8], i16) -> (usize, i16) { | |
554 | assert!(parts.len() >= 6); | |
555 | assert!(ndigits > 0); | |
556 | ||
557 | let (negative, full_decoded) = decode(v); | |
558 | let sign = determine_sign(sign, &full_decoded, negative); | |
559 | match full_decoded { | |
560 | FullDecoded::Nan => { | |
561 | parts[0] = Part::Copy(b"NaN"); | |
562 | Formatted { sign: sign, parts: &parts[..1] } | |
563 | } | |
564 | FullDecoded::Infinite => { | |
565 | parts[0] = Part::Copy(b"inf"); | |
566 | Formatted { sign: sign, parts: &parts[..1] } | |
567 | } | |
568 | FullDecoded::Zero => { | |
569 | if ndigits > 1 { // [0.][0000][e0] | |
570 | parts[0] = Part::Copy(b"0."); | |
571 | parts[1] = Part::Zero(ndigits - 1); | |
572 | parts[2] = Part::Copy(if upper { b"E0" } else { b"e0" }); | |
573 | Formatted { sign: sign, parts: &parts[..3] } | |
574 | } else { | |
575 | parts[0] = Part::Copy(if upper { b"0E0" } else { b"0e0" }); | |
576 | Formatted { sign: sign, parts: &parts[..1] } | |
577 | } | |
578 | } | |
579 | FullDecoded::Finite(ref decoded) => { | |
580 | let maxlen = estimate_max_buf_len(decoded.exp); | |
581 | assert!(buf.len() >= ndigits || buf.len() >= maxlen); | |
582 | ||
583 | let trunc = if ndigits < maxlen { ndigits } else { maxlen }; | |
584 | let (len, exp) = format_exact(decoded, &mut buf[..trunc], i16::MIN); | |
585 | Formatted { sign: sign, | |
586 | parts: digits_to_exp_str(&buf[..len], exp, ndigits, upper, parts) } | |
587 | } | |
588 | } | |
589 | } | |
590 | ||
591 | /// Formats given floating point number into the decimal form with exactly | |
592 | /// given number of fractional digits. The result is stored to the supplied parts | |
593 | /// array while utilizing given byte buffer as a scratch. `upper` is currently | |
594 | /// unused but left for the future decision to change the case of non-finite values, | |
595 | /// i.e. `inf` and `nan`. The first part to be rendered is always a `Part::Sign` | |
596 | /// (which can be an empty string if no sign is rendered). | |
597 | /// | |
598 | /// `format_exact` should be the underlying digit-generation function. | |
599 | /// You probably would want `strategy::grisu::format_exact` for this. | |
600 | /// | |
601 | /// The byte buffer should be enough for the output unless `frac_digits` is | |
602 | /// so large that only the fixed number of digits will be ever written. | |
603 | /// (The tipping point for `f64` is about 800, and 1000 bytes should be enough.) | |
604 | /// There should be at least 5 parts available, due to the worst case like | |
605 | /// `[+][0.][0000][45][0000]` with `frac_digits = 10`. | |
606 | pub fn to_exact_fixed_str<'a, T, F>(mut format_exact: F, v: T, | |
607 | sign: Sign, frac_digits: usize, _upper: bool, | |
608 | buf: &'a mut [u8], parts: &'a mut [Part<'a>]) -> Formatted<'a> | |
609 | where T: DecodableFloat, F: FnMut(&Decoded, &mut [u8], i16) -> (usize, i16) { | |
610 | assert!(parts.len() >= 4); | |
611 | ||
612 | let (negative, full_decoded) = decode(v); | |
613 | let sign = determine_sign(sign, &full_decoded, negative); | |
614 | match full_decoded { | |
615 | FullDecoded::Nan => { | |
616 | parts[0] = Part::Copy(b"NaN"); | |
617 | Formatted { sign: sign, parts: &parts[..1] } | |
618 | } | |
619 | FullDecoded::Infinite => { | |
620 | parts[0] = Part::Copy(b"inf"); | |
621 | Formatted { sign: sign, parts: &parts[..1] } | |
622 | } | |
623 | FullDecoded::Zero => { | |
624 | if frac_digits > 0 { // [0.][0000] | |
625 | parts[0] = Part::Copy(b"0."); | |
626 | parts[1] = Part::Zero(frac_digits); | |
627 | Formatted { sign: sign, parts: &parts[..2] } | |
628 | } else { | |
629 | parts[0] = Part::Copy(b"0"); | |
630 | Formatted { sign: sign, parts: &parts[..1] } | |
631 | } | |
632 | } | |
633 | FullDecoded::Finite(ref decoded) => { | |
634 | let maxlen = estimate_max_buf_len(decoded.exp); | |
635 | assert!(buf.len() >= maxlen); | |
636 | ||
637 | // it *is* possible that `frac_digits` is ridiculously large. | |
638 | // `format_exact` will end rendering digits much earlier in this case, | |
639 | // because we are strictly limited by `maxlen`. | |
640 | let limit = if frac_digits < 0x8000 { -(frac_digits as i16) } else { i16::MIN }; | |
641 | let (len, exp) = format_exact(decoded, &mut buf[..maxlen], limit); | |
642 | if exp <= limit { | |
643 | // the restriction couldn't been met, so this should render like zero no matter | |
644 | // `exp` was. this does not include the case that the restriction has been met | |
645 | // only after the final rounding-up; it's a regular case with `exp = limit + 1`. | |
646 | debug_assert_eq!(len, 0); | |
647 | if frac_digits > 0 { // [0.][0000] | |
648 | parts[0] = Part::Copy(b"0."); | |
649 | parts[1] = Part::Zero(frac_digits); | |
650 | Formatted { sign: sign, parts: &parts[..2] } | |
651 | } else { | |
652 | parts[0] = Part::Copy(b"0"); | |
653 | Formatted { sign: sign, parts: &parts[..1] } | |
654 | } | |
655 | } else { | |
656 | Formatted { sign: sign, | |
657 | parts: digits_to_dec_str(&buf[..len], exp, frac_digits, parts) } | |
658 | } | |
659 | } | |
660 | } | |
661 | } | |
662 |