1 /*
2 * Copyright (c) 2018, Raffaello Giulietti. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 * This particular file is subject to the "Classpath" exception as provided
9 * in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 */
21
22 package jdk.internal.math;
23
24 import static java.lang.Float.*;
25 import static java.lang.Long.numberOfLeadingZeros;
26 import static java.lang.Math.multiplyHigh;
27 import static jdk.internal.math.MathUtils.*;
28
29 /**
30 * This class exposes a method to render a {@code float} as a string.
31
32 * @author Raffaello Giulietti
33 */
34 final public class FloatToDecimal {
35
36 // Precision of normal values in bits.
37 private static final int P = 24;
38
39 // Length in bits of the exponent field.
40 private static final int W = (Float.SIZE - 1) - (P - 1);
41
42 // Minimum value of the exponent.
43 private static final int Q_MIN = (-1 << W - 1) - P + 3;
44
45 // Minimum value of the coefficient of a normal value.
46 private static final int C_MIN = 1 << P - 1;
47
48 // Mask to extract the IEEE 754-2008 biased exponent.
49 private static final int BQ_MASK = (1 << W) - 1;
50
51 // Mask to extract the IEEE 754-2008 fraction bits.
52 private static final int T_MASK = (1 << P - 1) - 1;
53
54 // H = min {n integer | 10^(n-1) > 2^P}
55 private static final int H = 9;
56
57 // used in the left-to-right extraction of the digits
58 private static final int LTR = 28;
59 private static final int MASK_LTR = (1 << LTR) - 1;
60
61 private static final long MASK_63 = (1L << Long.SIZE - 1) - 1;
62
63 // for thread-safety, each thread gets its own instance of this class
64 private static final ThreadLocal<FloatToDecimal> threadLocal =
65 ThreadLocal.withInitial(FloatToDecimal::new);
66
67 /*
68 Room for the longer of the forms
69 -ddddd.dddd H + 2 characters
70 -0.00ddddddddd H + 5 characters
71 -d.ddddddddE-ee H + 6 characters
72 where there are H digits d
73 */
74 private final char[] buf = new char[H + 6];
75
76 // index of rightmost valid character
77 private int index;
78
79 private FloatToDecimal() {
80 }
81
82 /*
83 See Float::toString for javadoc.
84 */
85 public static String toString(float v) {
86 return threadLocalInstance().toDecimal(v);
87 }
88
89 private static FloatToDecimal threadLocalInstance() {
90 return threadLocal.get();
91 }
92
93 private String toDecimal(float v) {
94 int bits = floatToRawIntBits(v);
95 int bq = (bits >>> P - 1) & BQ_MASK;
96 if (bq < BQ_MASK) {
97 index = -1;
98 if (bits < 0) {
99 append('-');
100 }
101 if (bq > 0) {
102 return toDecimal(Q_MIN - 1 + bq, C_MIN | bits & T_MASK);
103 }
104 if (bits == 0x0000_0000) {
105 return "0.0";
106 }
107 if (bits == 0x8000_0000) {
108 return "-0.0";
109 }
110 return toDecimal(Q_MIN, bits & T_MASK);
111 }
112 if (v != v) {
113 return "NaN";
114 }
115 if (v == POSITIVE_INFINITY) {
116 return "Infinity";
117 }
118 return "-Infinity";
119 }
120
121 // Let v = c * 2^q be the absolute value of the original float. Renders v.
122 private String toDecimal(int q, int c) {
123 /*
124 out = 0, if the boundaries of the rounding interval are included
125 out = 1, if they are excluded
126 d = 1 for even, d = 2 for uneven spacing around v.
127 v = cb * 2^qb
128 predecessor(v) = cbl * 2^qb
129 successor(v) = cbr * 2^qb
130 */
131 int out = c & 0x1;
132
133 long cb;
134 long cbr;
135 long cbl;
136 int k;
137 int ord2alpha;
138 if (c != C_MIN | q == Q_MIN) {
139 cb = c << 1;
140 cbr = cb + 1;
141 k = flog10pow2(q);
142 ord2alpha = q + flog2pow10(-k) + 1;
143 } else {
144 cb = c << 2;
145 cbr = cb + 2;
146 k = flog10threeQuartersPow2(q);
147 ord2alpha = q + flog2pow10(-k);
148 }
149 cbl = cb - 1;
150 long mask = (1L << 63 - ord2alpha) - 1;
151 long threshold = 1L << 62 - ord2alpha;
152
153 // pow5 = pow51*2^63 + pow50
154 long pow51 = ceilPow5dHigh(-k);
155 long pow50 = ceilPow5dLow(-k);
156
157 // p = p2*2^126 + p1*2^63 + p0 and p = pow5 * cb
158 long x0 = pow50 * cb;
159 long x1 = multiplyHigh(pow50, cb);
160 long y0 = pow51 * cb;
161 long y1 = multiplyHigh(pow51, cb);
162 long z = (x1 << 1 | x0 >>> 63) + (y0 & MASK_63);
163 long p0 = x0 & MASK_63;
164 long p1 = z & MASK_63;
165 long p2 = (y1 << 1 | y0 >>> 63) + (z >>> 63);
166 long vn = p2 << 1 + ord2alpha | p1 >>> 62 - ord2alpha;
167 if ((p1 & mask) != 0 || p0 >= threshold) {
168 vn |= 1;
169 }
170
171 // Similarly as above, with p = pow5 * cbl
172 x0 = pow50 * cbl;
173 x1 = multiplyHigh(pow50, cbl);
174 y0 = pow51 * cbl;
175 y1 = multiplyHigh(pow51, cbl);
176 z = (x1 << 1 | x0 >>> 63) + (y0 & MASK_63);
177 p0 = x0 & MASK_63;
178 p1 = z & MASK_63;
179 p2 = (y1 << 1 | y0 >>> 63) + (z >>> 63);
180 long vnl = p2 << ord2alpha | p1 >>> 63 - ord2alpha;
181 if ((p1 & mask) != 0 || p0 >= threshold) {
182 vnl |= 1;
183 }
184
185 // Similarly as above, with p = pow5 * cbr
186 x0 = pow50 * cbr;
187 x1 = multiplyHigh(pow50, cbr);
188 y0 = pow51 * cbr;
189 y1 = multiplyHigh(pow51, cbr);
190 z = (x1 << 1 | x0 >>> 63) + (y0 & MASK_63);
191 p0 = x0 & MASK_63;
192 p1 = z & MASK_63;
193 p2 = (y1 << 1 | y0 >>> 63) + (z >>> 63);
194 long vnr = p2 << ord2alpha | p1 >>> 63 - ord2alpha;
195 if ((p1 & mask) != 0 || p0 >= threshold) {
196 vnr |= 1;
197 }
198
199 long s = vn >> 2;
200 if (s >= 100) {
201 long s10 = s - s % 10;
202 long t10 = s10 + 10;
203 boolean uin10 = vnl + out <= s10 << 1;
204 boolean win10 = (t10 << 1) + out <= vnr;
205 if (uin10 | win10) {
206 if (!win10) {
207 return toChars(s10, k);
208 }
209 if (!uin10) {
210 return toChars(t10, k);
211 }
212 }
213 } else if (s < 10) {
214 /*
215 Special cases that need to be made artificially longer to meet
216 the specification
217 */
218 switch ((int) s) {
219 case 1: return toChars(14, -46); // 1.4 * 10^-45
220 case 2: return toChars(28, -46); // 2.8 * 10^-45
221 case 4: return toChars(42, -46); // 4.2 * 10^-45
222 case 5: return toChars(56, -46); // 5.6 * 10^-45
223 case 7: return toChars(70, -46); // 7.0 * 10^-45
224 case 8: return toChars(84, -46); // 8.4 * 10^-45
225 case 9: return toChars(98, -46); // 9.8 * 10^-45
226 }
227 }
228 long t = s + 1;
229 boolean uin = vnl + out <= s << 1;
230 boolean win = (t << 1) + out <= vnr;
231 if (!win) {
232 return toChars(s, k);
233 }
234 if (!uin) {
235 return toChars(t, k);
236 }
237 long cmp = vn - (s + t << 1);
238 if (cmp < 0) {
239 return toChars(s, k);
240 }
241 if (cmp > 0) {
242 return toChars(t, k);
243 }
244 if ((s & 1) == 0) {
245 return toChars(s, k);
246 }
247 return toChars(t, k);
248 }
249
250 /*
251 The method formats the number f * 10^e
252
253 Division is avoided altogether by replacing it with multiplications
254 and shifts. This has a noticeable impact on performance.
255 For more in-depth readings, see for example
256 * Moeller & Granlund, "Improved division by invariant integers"
257 * ridiculous_fish, "Labor of Division (Episode III): Faster Unsigned
258 Division by Constants"
259
260 Also, once the quotient is known, the remainder is computed indirectly.
261 */
262 private String toChars(long f, int e) {
263 // Normalize f to lie in the f-independent interval [10^(H-1), 10^H)
264 int len10 = flog10pow2(Long.SIZE - numberOfLeadingZeros(f));
265 if (f >= pow10[len10]) {
266 len10 += 1;
267 }
268 // 10^(len10-1) <= f < 10^len10
269 f *= pow10[H - len10];
270 e += len10;
271
272 /*
273 Split the H = 9 digits of f into:
274 h = the most significant digit of f
275 l = the last 8, least significant digits of f
276
277 Pictorially, the selected decimal to format as String is
278 0.hllllllll * 10^e
279 Depending on the value of e, plain or computerized scientific notation
280 is used.
281 */
282 int h = (int) (f * 1_441_151_881L >>> 57);
283 int l = (int) (f - 100_000_000 * h);
284
285 /*
286 The left-to-right digits generation in toChars_* is inspired by
287 * Bouvier & Zimmermann, "Division-Free Binary-to-Decimal Conversion"
288 */
289 if (0 < e && e <= 7) {
290 return toChars_1(h, l, e);
291 }
292 if (-3 < e && e <= 0) {
293 return toChars_2(h, l, e);
294 }
295 return toChars_3(h, l, e);
296 }
297
298 // 0 < e <= 7: plain format without leading zeroes.
299 private String toChars_1(int h, int l, int e) {
300 appendDigit(h);
301 // y = (l + 1) * 2^LTR / 100_000_000 - 1;
302 int y = (int) (multiplyHigh(
303 (long) (l + 1) << LTR,
304 48_357_032_784_585_167L) >>> 18) - 1;
305 int t;
306 int i = 1;
307 for (; i < e; ++i) {
308 t = 10 * y;
309 appendDigit(t >>> LTR);
310 y = t & MASK_LTR;
311 }
312 append('.');
313 for (; i <= 8; ++i) {
314 t = 10 * y;
315 appendDigit(t >>> LTR);
316 y = t & MASK_LTR;
317 }
318 removeTrailingZeroes();
319 return charsToString();
320 }
321
322 // -3 < e <= 0: plain format with leading zeroes.
323 private String toChars_2(int h, int l, int e) {
324 appendDigit(0);
325 append('.');
326 for (; e < 0; ++e) {
327 appendDigit(0);
328 }
329 appendDigit(h);
330 append8Digits(l);
331 removeTrailingZeroes();
332 return charsToString();
333 }
334
335 // -3 >= e | e > 7: computerized scientific notation
336 private String toChars_3(int h, int l, int e) {
337 appendDigit(h);
338 append('.');
339 append8Digits(l);
340 removeTrailingZeroes();
341 exponent(e - 1);
342 return charsToString();
343 }
344
345 private void append8Digits(int v) {
346 // y = (v + 1) * 2^LTR / 100_000_000 - 1;
347 int y = (int) (multiplyHigh((long) (v + 1) << LTR,
348 48_357_032_784_585_167L) >>> 18) - 1;
349 for (int i = 0; i < 8; ++i) {
350 int t = 10 * y;
351 appendDigit(t >>> LTR);
352 y = t & MASK_LTR;
353 }
354 }
355
356 private void removeTrailingZeroes() {
357 while (buf[index] == '0') {
358 --index;
359 }
360 if (buf[index] == '.') {
361 ++index;
362 }
363 }
364
365 private void exponent(int e) {
366 append('E');
367 if (e < 0) {
368 append('-');
369 e = -e;
370 }
371 if (e < 10) {
372 appendDigit(e);
373 return;
374 }
375 // d = e / 10
376 int d = e * 205 >>> 11;
377 appendDigit(d);
378 appendDigit(e - 10 * d);
379 }
380
381 private void append(int c) {
382 buf[++index] = (char) c;
383 }
384
385 private void appendDigit(int d) {
386 buf[++index] = (char) ('0' + d);
387 }
388
389 private String charsToString() {
390 return new String(buf, 0, index + 1);
391 }
392
393 }