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