1 /*
2 * Copyright 2018-2019 Raffaello Giulietti
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 * THE SOFTWARE.
21 */
22
23 package jdk.internal.math;
24
25 import java.io.IOException;
26
27 import static java.lang.Float.*;
28 import static java.lang.Integer.*;
29 import static java.lang.Math.multiplyHigh;
30 import static jdk.internal.math.MathUtils.*;
31
32 /**
33 * This class exposes a method to render a {@code float} as a string.
34 *
35 * @author Raffaello Giulietti
36 */
37 final public class FloatToDecimal {
38 /*
39 For full details about this code see the following references:
40
41 [1] Giulietti, "The Schubfach way to render doubles",
42 https://drive.google.com/open?id=1KLtG_LaIbK9ETXI290zqCxvBW94dj058
43
44 [2] IEEE Computer Society, "IEEE Standard for Floating-Point Arithmetic"
45
46 [3] Bouvier & Zimmermann, "Division-Free Binary-to-Decimal Conversion"
47
48 Divisions are avoided for the benefit of those architectures that do not
49 provide specific machine instructions or where they are slow.
50 This is discussed in section 10 of [1].
51 */
52
53 // The precision in bits.
54 static final int P = 24;
55
56 // H is as in section 8 of [1].
57 static final int H = 9;
58
59 // 10^(MIN_EXP - 1) <= MIN_VALUE < 10^MIN_EXP
60 static final int MIN_EXP = -44;
61
62 // 10^(MAX_EXP - 1) <= MAX_VALUE < 10^MAX_EXP
63 static final int MAX_EXP = 39;
64
65 // Exponent width in bits.
66 private static final int W = (Float.SIZE - 1) - (P - 1);
67
68 // Minimum value of the exponent: -(2^(W-1)) - P + 3.
69 private static final int Q_MIN = (-1 << W - 1) - P + 3;
70
71 // Minimum value of the significand of a normal value: 2^(P-1).
72 private static final int C_MIN = 1 << P - 1;
73
74 // Mask to extract the biased exponent.
75 private static final int BQ_MASK = (1 << W) - 1;
76
77 // Mask to extract the fraction bits.
78 private static final int T_MASK = (1 << P - 1) - 1;
79
80 // Used in rop().
81 private static final long MASK_32 = (1L << 32) - 1;
82
83 // Used for left-to-tight digit extraction.
84 private static final int MASK_28 = (1 << 28) - 1;
85
86 private static final int NON_SPECIAL = 0;
87 private static final int PLUS_ZERO = 1;
88 private static final int MINUS_ZERO = 2;
89 private static final int PLUS_INF = 3;
90 private static final int MINUS_INF = 4;
91 private static final int NAN = 5;
92
93 // For thread-safety, each thread gets its own instance of this class.
94 private static final ThreadLocal<FloatToDecimal> threadLocal =
95 ThreadLocal.withInitial(FloatToDecimal::new);
96
97 /*
98 Room for the longer of
99 -ddddd.dddd H + 2 characters
100 -0.00ddddddddd H + 5 characters
101 -d.ddddddddE-ee H + 6 characters
102 -Infinity
103 NaN
104 where there are H digits d
105 */
106 public final int MAX_CHARS = H + 6;
107
108 // Numerical results are created here...
109 private final byte[] bytes = new byte[MAX_CHARS];
110
111 // ... and copied here in appendTo()
112 private final char[] chars = new char[MAX_CHARS];
113
114 // Index into bytes of rightmost valid character.
115 private int index;
116
117 private FloatToDecimal() {
118 }
119
120 /**
121 * Returns a string rendering of the {@code float} argument.
122 *
123 * <p>The characters of the result are all drawn from the ASCII set.
124 * <ul>
125 * <li> Any NaN, whether quiet or signaling, is rendered as
126 * {@code "NaN"}, regardless of the sign bit.
127 * <li> The infinities +∞ and -∞ are rendered as
128 * {@code "Infinity"} and {@code "-Infinity"}, respectively.
129 * <li> The positive and negative zeroes are rendered as
130 * {@code "0.0"} and {@code "-0.0"}, respectively.
131 * <li> A finite negative {@code v} is rendered as the sign
132 * '{@code -}' followed by the rendering of the magnitude -{@code v}.
133 * <li> A finite positive {@code v} is rendered in two stages:
134 * <ul>
135 * <li> <em>Selection of a decimal</em>: A well-defined
136 * decimal <i>d</i><sub><code>v</code></sub> is selected
137 * to represent {@code v}.
138 * <li> <em>Formatting as a string</em>: The decimal
139 * <i>d</i><sub><code>v</code></sub> is formatted as a string,
140 * either in plain or in computerized scientific notation,
141 * depending on its value.
142 * </ul>
143 * </ul>
144 *
145 * <p>A <em>decimal</em> is a number of the form
146 * <i>d</i>×10<sup><i>i</i></sup>
147 * for some (unique) integers <i>d</i> > 0 and <i>i</i> such that
148 * <i>d</i> is not a multiple of 10.
149 * These integers are the <em>significand</em> and
150 * the <em>exponent</em>, respectively, of the decimal.
151 * The <em>length</em> of the decimal is the (unique)
152 * integer <i>n</i> meeting
153 * 10<sup><i>n</i>-1</sup> ≤ <i>d</i> < 10<sup><i>n</i></sup>.
154 *
155 * <p>The decimal <i>d</i><sub><code>v</code></sub>
156 * for a finite positive {@code v} is defined as follows:
157 * <ul>
158 * <li>Let <i>R</i> be the set of all decimals that round to {@code v}
159 * according to the usual round-to-closest rule of
160 * IEEE 754 floating-point arithmetic.
161 * <li>Let <i>m</i> be the minimal length over all decimals in <i>R</i>.
162 * <li>When <i>m</i> ≥ 2, let <i>T</i> be the set of all decimals
163 * in <i>R</i> with length <i>m</i>.
164 * Otherwise, let <i>T</i> be the set of all decimals
165 * in <i>R</i> with length 1 or 2.
166 * <li>Define <i>d</i><sub><code>v</code></sub> as
167 * the decimal in <i>T</i> that is closest to {@code v}.
168 * Or if there are two such decimals in <i>T</i>,
169 * select the one with the even significand (there is exactly one).
170 * </ul>
171 *
172 * <p>The (uniquely) selected decimal <i>d</i><sub><code>v</code></sub>
173 * is then formatted.
174 *
175 * <p>Let <i>d</i>, <i>i</i> and <i>n</i> be the significand, exponent and
176 * length of <i>d</i><sub><code>v</code></sub>, respectively.
177 * Further, let <i>e</i> = <i>n</i> + <i>i</i> - 1 and let
178 * <i>d</i><sub>1</sub>…<i>d</i><sub><i>n</i></sub>
179 * be the usual decimal expansion of the significand.
180 * Note that <i>d</i><sub>1</sub> ≠ 0 ≠ <i>d</i><sub><i>n</i></sub>.
181 * <ul>
182 * <li>Case -3 ≤ <i>e</i> < 0:
183 * <i>d</i><sub><code>v</code></sub> is formatted as
184 * <code>0.0</code>…<code>0</code><!--
185 * --><i>d</i><sub>1</sub>…<i>d</i><sub><i>n</i></sub>,
186 * where there are exactly -(<i>n</i> + <i>i</i>) zeroes between
187 * the decimal point and <i>d</i><sub>1</sub>.
188 * For example, 123 × 10<sup>-4</sup> is formatted as
189 * {@code 0.0123}.
190 * <li>Case 0 ≤ <i>e</i> < 7:
191 * <ul>
192 * <li>Subcase <i>i</i> ≥ 0:
193 * <i>d</i><sub><code>v</code></sub> is formatted as
194 * <i>d</i><sub>1</sub>…<i>d</i><sub><i>n</i></sub><!--
195 * --><code>0</code>…<code>0.0</code>,
196 * where there are exactly <i>i</i> zeroes
197 * between <i>d</i><sub><i>n</i></sub> and the decimal point.
198 * For example, 123 × 10<sup>2</sup> is formatted as
199 * {@code 12300.0}.
200 * <li>Subcase <i>i</i> < 0:
201 * <i>d</i><sub><code>v</code></sub> is formatted as
202 * <i>d</i><sub>1</sub>…<!--
203 * --><i>d</i><sub><i>n</i>+<i>i</i></sub>.<!--
204 * --><i>d</i><sub><i>n</i>+<i>i</i>+1</sub>…<!--
205 * --><i>d</i><sub><i>n</i></sub>.
206 * There are exactly -<i>i</i> digits to the right of
207 * the decimal point.
208 * For example, 123 × 10<sup>-1</sup> is formatted as
209 * {@code 12.3}.
210 * </ul>
211 * <li>Case <i>e</i> < -3 or <i>e</i> ≥ 7:
212 * computerized scientific notation is used to format
213 * <i>d</i><sub><code>v</code></sub>.
214 * Here <i>e</i> is formatted as by {@link Integer#toString(int)}.
215 * <ul>
216 * <li>Subcase <i>n</i> = 1:
217 * <i>d</i><sub><code>v</code></sub> is formatted as
218 * <i>d</i><sub>1</sub><code>.0E</code><i>e</i>.
219 * For example, 1 × 10<sup>23</sup> is formatted as
220 * {@code 1.0E23}.
221 * <li>Subcase <i>n</i> > 1:
222 * <i>d</i><sub><code>v</code></sub> is formatted as
223 * <i>d</i><sub>1</sub><code>.</code><i>d</i><sub>2</sub><!--
224 * -->…<i>d</i><sub><i>n</i></sub><code>E</code><i>e</i>.
225 * For example, 123 × 10<sup>-21</sup> is formatted as
226 * {@code 1.23E-19}.
227 * </ul>
228 * </ul>
229 *
230 * @param v the {@code float} to be rendered.
231 * @return a string rendering of the argument.
232 */
233 public static String toString(float v) {
234 return threadLocalInstance().toDecimalString(v);
235 }
236
237 /**
238 * Appends the rendering of the {@code v} to {@code app}.
239 *
240 * <p>The outcome is the same as if {@code v} were first
241 * {@link #toString(float) rendered} and the resulting string were then
242 * {@link Appendable#append(CharSequence) appended} to {@code app}.
243 *
244 * @param v the {@code float} whose rendering is appended.
245 * @param app the {@link Appendable} to append to.
246 * @throws IOException If an I/O error occurs
247 */
248 public static Appendable appendTo(float v, Appendable app)
249 throws IOException {
250 return threadLocalInstance().appendDecimalTo(v, app);
251 }
252
253 private static FloatToDecimal threadLocalInstance() {
254 return threadLocal.get();
255 }
256
257 private String toDecimalString(float v) {
258 switch (toDecimal(v)) {
259 case NON_SPECIAL: return charsToString();
260 case PLUS_ZERO: return "0.0";
261 case MINUS_ZERO: return "-0.0";
262 case PLUS_INF: return "Infinity";
263 case MINUS_INF: return "-Infinity";
264 default: return "NaN";
265 }
266 }
267
268 private Appendable appendDecimalTo(float v, Appendable app)
269 throws IOException {
270 switch (toDecimal(v)) {
271 case NON_SPECIAL:
272 for (int i = 0; i <= index; ++i) {
273 chars[i] = (char) bytes[i];
274 }
275 if (app instanceof StringBuilder) {
276 return ((StringBuilder) app).append(chars, 0, index + 1);
277 }
278 if (app instanceof StringBuffer) {
279 return ((StringBuffer) app).append(chars, 0, index + 1);
280 }
281 for (int i = 0; i <= index; ++i) {
282 app.append(chars[i]);
283 }
284 return app;
285 case PLUS_ZERO: return app.append("0.0");
286 case MINUS_ZERO: return app.append("-0.0");
287 case PLUS_INF: return app.append("Infinity");
288 case MINUS_INF: return app.append("-Infinity");
289 default: return app.append("NaN");
290 }
291 }
292
293 private int toDecimal(float v) {
294 /*
295 For full details see references [2] and [1].
296
297 Let
298 Q_MAX = 2^(W-1) - P
299 For finite v != 0, determine integers c and q such that
300 |v| = c 2^q and
301 Q_MIN <= q <= Q_MAX and
302 either 2^(P-1) <= c < 2^P (normal)
303 or 0 < c < 2^(P-1) and q = Q_MIN (subnormal)
304 */
305 int bits = floatToRawIntBits(v);
306 int t = bits & T_MASK;
307 int bq = (bits >>> P - 1) & BQ_MASK;
308 if (bq < BQ_MASK) {
309 index = -1;
310 if (bits < 0) {
311 append('-');
312 }
313 if (bq != 0) {
314 // normal value. Here mq = -q
315 int mq = -Q_MIN + 1 - bq;
316 int c = C_MIN | t;
317 // The fast path discussed in section 8.3 of [1].
318 if (0 < mq & mq < P) {
319 int f = c >> mq;
320 if (f << mq == c) {
321 return toChars(f, 0);
322 }
323 }
324 return toDecimal(-mq, c);
325 }
326 if (t != 0) {
327 // subnormal value
328 return toDecimal(Q_MIN, t);
329 }
330 return bits == 0 ? PLUS_ZERO : MINUS_ZERO;
331 }
332 if (t != 0) {
333 return NAN;
334 }
335 return bits > 0 ? PLUS_INF : MINUS_INF;
336 }
337
338 private int toDecimal(int q, int c) {
339 /*
340 The skeleton corresponds to figure 4 of [1].
341 The efficient computations are those summarized in figure 7.
342 Also check the appendix.
343
344 Here's a correspondence between Java names and names in [1],
345 expressed as approximate LaTeX source code and informally.
346 Other names are identical.
347 cb: \bar{c} "c-bar"
348 cbr: \bar{c}_r "c-bar-r"
349 cbl: \bar{c}_l "c-bar-l"
350
351 vb: \bar{v} "v-bar"
352 vbr: \bar{v}_r "v-bar-r"
353 vbl: \bar{v}_l "v-bar-l"
354
355 rop: r_o' "r-o-prime"
356 */
357 int out = c & 0x1;
358 long cb;
359 long cbr;
360 long cbl;
361 int k;
362 int h;
363 /*
364 flog10pow2(e) = floor(log_10(2^e))
365 flog10threeQuartersPow2(e) = floor(log_10(3/4 2^e))
366 flog2pow10(e) = floor(log_2(10^e))
367 */
368 if (c != C_MIN | q == Q_MIN) {
369 // regular spacing
370 cb = c << 1;
371 cbr = cb + 1;
372 k = flog10pow2(q);
373 h = q + flog2pow10(-k) + 34;
374 } else {
375 // irregular spacing
376 cb = c << 2;
377 cbr = cb + 2;
378 k = flog10threeQuartersPow2(q);
379 h = q + flog2pow10(-k) + 33;
380 }
381 cbl = cb - 1;
382
383 // g is as in the appendix
384 long g = g1(-k) + 1;
385
386 int vb = rop(g, cb << h);
387 int vbl = rop(g, cbl << h);
388 int vbr = rop(g, cbr << h);
389
390 int s = vb >> 2;
391 if (s >= 100) {
392 /*
393 For n = 9, m = 1 the table in section 10 of [1] shows
394 s' =
395 floor(s / 10) = floor(s 1'717'986'919 / 2^34)
396
397 sp10 = 10 s', tp10 = 10 t' = sp10 + 10
398 upin iff u' = sp10 10^k in Rv
399 wpin iff w' = tp10 10^k in Rv
400 See section 9.3.
401 */
402 int sp10 = 10 * (int) (s * 1_717_986_919L >>> 34);
403 int tp10 = sp10 + 10;
404 boolean upin = vbl + out <= sp10 << 2;
405 boolean wpin = (tp10 << 2) + out <= vbr;
406 if (upin != wpin) {
407 return toChars(upin ? sp10 : tp10, k);
408 }
409 } else if (s < 10) {
410 switch (s) {
411 case 1: return toChars(14, -46); // 1.4 * 10^-45
412 case 2: return toChars(28, -46); // 2.8 * 10^-45
413 case 4: return toChars(42, -46); // 4.2 * 10^-45
414 case 5: return toChars(56, -46); // 5.6 * 10^-45
415 case 7: return toChars(70, -46); // 7.0 * 10^-45
416 case 8: return toChars(84, -46); // 8.4 * 10^-45
417 case 9: return toChars(98, -46); // 9.8 * 10^-45
418 }
419 }
420
421 /*
422 10 <= s < 100 or s >= 100 and u', w' not in Rv
423 uin iff u = s 10^k in Rv
424 win iff w = t 10^k in Rv
425 See section 9.3.
426 */
427 int t = s + 1;
428 boolean uin = vbl + out <= s << 2;
429 boolean win = (t << 2) + out <= vbr;
430 if (uin != win) {
431 // Exactly one of u or w lies in Rv.
432 return toChars(uin ? s : t, k);
433 }
434 /*
435 Both u and w lie in Rv: determine the one closest to v.
436 See section 9.3.
437 */
438 int cmp = vb - (s + t << 1);
439 return toChars(cmp < 0 || cmp == 0 && (s & 0x1) == 0 ? s : t, k);
440 }
441
442 /*
443 Computes rop(cp g 2^(-95))
444 See appendix and figure 9 of [1].
445 */
446 private static int rop(long g, long cp) {
447 long x1 = multiplyHigh(g, cp);
448 long vbp = x1 >>> 31;
449 return (int) (vbp | (x1 & MASK_32) + MASK_32 >>> 32);
450 }
451
452 /*
453 Formats the decimal f 10^e.
454 */
455 private int toChars(int f, int e) {
456 /*
457 For details not discussed here see section 10 of [1].
458
459 Determine len such that
460 10^(len-1) <= f < 10^len
461 */
462 int len = flog10pow2(Integer.SIZE - numberOfLeadingZeros(f));
463 if (f >= pow10(len)) {
464 len += 1;
465 }
466
467 /*
468 Let fp and ep be the original f and e, respectively.
469 Transform f and e to ensure
470 10^(H-1) <= f < 10^H
471 fp 10^ep = f 10^(e-H) = 0.f 10^e
472 */
473 f *= pow10(H - len);
474 e += len;
475
476 /*
477 The toChars?() methods perform left-to-right digits extraction
478 using ints, provided that the arguments are limited to 8 digits.
479 Therefore, split the H = 9 digits of f into:
480 h = the most significant digit of f
481 l = the last 8, least significant digits of f
482
483 For n = 9, m = 8 the table in section 10 of [1] shows
484 floor(f / 10^8) = floor(1'441'151'881 f / 2^57)
485 */
486 int h = (int) (f * 1_441_151_881L >>> 57);
487 int l = f - 100_000_000 * h;
488
489 if (0 < e && e <= 7) {
490 return toChars1(h, l, e);
491 }
492 if (-3 < e && e <= 0) {
493 return toChars2(h, l, e);
494 }
495 return toChars3(h, l, e);
496 }
497
498 private int toChars1(int h, int l, int e) {
499 /*
500 0 < e <= 7: plain format without leading zeroes.
501 Left-to-right digits extraction:
502 algorithm 1 in [3], with b = 10, k = 8, n = 28.
503 */
504 appendDigit(h);
505 int y = y(l);
506 int t;
507 int i = 1;
508 for (; i < e; ++i) {
509 t = 10 * y;
510 appendDigit(t >>> 28);
511 y = t & MASK_28;
512 }
513 append('.');
514 for (; i <= 8; ++i) {
515 t = 10 * y;
516 appendDigit(t >>> 28);
517 y = t & MASK_28;
518 }
519 removeTrailingZeroes();
520 return NON_SPECIAL;
521 }
522
523 private int toChars2(int h, int l, int e) {
524 // -3 < e <= 0: plain format with leading zeroes.
525 appendDigit(0);
526 append('.');
527 for (; e < 0; ++e) {
528 appendDigit(0);
529 }
530 appendDigit(h);
531 append8Digits(l);
532 removeTrailingZeroes();
533 return NON_SPECIAL;
534 }
535
536 private int toChars3(int h, int l, int e) {
537 // -3 >= e | e > 7: computerized scientific notation
538 appendDigit(h);
539 append('.');
540 append8Digits(l);
541 removeTrailingZeroes();
542 exponent(e - 1);
543 return NON_SPECIAL;
544 }
545
546 private void append8Digits(int m) {
547 /*
548 Left-to-right digits extraction:
549 algorithm 1 in [3], with b = 10, k = 8, n = 28.
550 */
551 int y = y(m);
552 for (int i = 0; i < 8; ++i) {
553 int t = 10 * y;
554 appendDigit(t >>> 28);
555 y = t & MASK_28;
556 }
557 }
558
559 private void removeTrailingZeroes() {
560 while (bytes[index] == '0') {
561 --index;
562 }
563 // ... but do not remove the one directly to the right of '.'
564 if (bytes[index] == '.') {
565 ++index;
566 }
567 }
568
569 private int y(int a) {
570 /*
571 Algorithm 1 in [3] needs computation of
572 floor((a + 1) 2^n / b^k) - 1
573 with a < 10^8, b = 10, k = 8, n = 28.
574 Noting that
575 (a + 1) 2^n <= 10^8 2^28 < 10^17
576 For n = 17, m = 8 the table in section 10 of [1] leads to:
577 */
578 return (int) (multiplyHigh(
579 (long) (a + 1) << 28,
580 193_428_131_138_340_668L) >>> 20) - 1;
581 }
582
583 private void exponent(int e) {
584 append('E');
585 if (e < 0) {
586 append('-');
587 e = -e;
588 }
589 if (e < 10) {
590 appendDigit(e);
591 return;
592 }
593 /*
594 For n = 2, m = 1 the table in section 10 of [1] shows
595 floor(e / 10) = floor(103 e / 2^10)
596 */
597 int d = e * 103 >>> 10;
598 appendDigit(d);
599 appendDigit(e - 10 * d);
600 }
601
602 private void append(int c) {
603 bytes[++index] = (byte) c;
604 }
605
606 private void appendDigit(int d) {
607 bytes[++index] = (byte) ('0' + d);
608 }
609
610 /*
611 Using the deprecated constructor enhances performance.
612 */
613 @SuppressWarnings("deprecation")
614 private String charsToString() {
615 return new String(bytes, 0, 0, index + 1);
616 }
617
618 }