1 /* 2 * Copyright (c) 2021, 2022, Oracle and/or its affiliates. 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle 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 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package jdk.internal.math; 27 28 import java.io.IOException; 29 30 import static java.lang.Float.*; 31 import static java.lang.Integer.*; 32 import static java.lang.Math.multiplyHigh; 33 import static jdk.internal.math.MathUtils.*; 34 35 /** 36 * This class exposes a method to render a {@code float} as a string. 37 */ 38 final public class FloatToDecimal { 39 /* 40 * For full details about this code see the following references: 41 * 42 * [1] Giulietti, "The Schubfach way to render doubles", 43 * https://drive.google.com/file/d/1gp5xv4CAa78SVgCeWfGqqI4FfYYYuNFb 44 * 45 * [2] IEEE Computer Society, "IEEE Standard for Floating-Point Arithmetic" 46 * 47 * [3] Bouvier & Zimmermann, "Division-Free Binary-to-Decimal Conversion" 48 * 49 * Divisions are avoided altogether for the benefit of those architectures 50 * that do not provide specific machine instructions or where they are slow. 51 * This is discussed in section 10 of [1]. 52 */ 53 54 /* The precision in bits */ 55 static final int P = PRECISION; 56 57 /* Exponent width in bits */ 58 private static final int W = (Float.SIZE - 1) - (P - 1); 59 60 /* Minimum value of the exponent: -(2^(W-1)) - P + 3 */ 61 static final int Q_MIN = (-1 << (W - 1)) - P + 3; 62 63 /* Maximum value of the exponent: 2^(W-1) - P */ 64 static final int Q_MAX = (1 << (W - 1)) - P; 65 66 /* 10^(E_MIN - 1) <= MIN_VALUE < 10^E_MIN */ 67 static final int E_MIN = -44; 68 69 /* 10^(E_MAX - 1) <= MAX_VALUE < 10^E_MAX */ 70 static final int E_MAX = 39; 71 72 /* Threshold to detect tiny values, as in section 8.2.1 of [1] */ 73 static final int C_TINY = 8; 74 75 /* The minimum and maximum k, as in section 8 of [1] */ 76 static final int K_MIN = -45; 77 static final int K_MAX = 31; 78 79 /* H is as in section 8.1 of [1] */ 80 static final int H = 9; 81 82 /* Minimum value of the significand of a normal value: 2^(P-1) */ 83 private static final int C_MIN = 1 << (P - 1); 84 85 /* Mask to extract the biased exponent */ 86 private static final int BQ_MASK = (1 << W) - 1; 87 88 /* Mask to extract the fraction bits */ 89 private static final int T_MASK = (1 << (P - 1)) - 1; 90 91 /* Used in rop() */ 92 private static final long MASK_32 = (1L << 32) - 1; 93 94 /* Used for left-to-tight digit extraction */ 95 private static final int MASK_28 = (1 << 28) - 1; 96 97 private static final int NON_SPECIAL = 0; 98 private static final int PLUS_ZERO = 1; 99 private static final int MINUS_ZERO = 2; 100 private static final int PLUS_INF = 3; 101 private static final int MINUS_INF = 4; 102 private static final int NAN = 5; 103 104 /* 105 * Room for the longer of the forms 106 * -ddddd.dddd H + 2 characters 107 * -0.00ddddddddd H + 5 characters 108 * -d.ddddddddE-ee H + 6 characters 109 * where there are H digits d 110 */ 111 public static final int MAX_CHARS = H + 6; 112 113 private final byte[] bytes = new byte[MAX_CHARS]; 114 115 /* Index into bytes of rightmost valid character */ 116 private int index; 117 FloatToDecimal()118 private FloatToDecimal() { 119 } 120 121 /** 122 * Returns a string representation of the {@code float} 123 * argument. All characters mentioned below are ASCII characters. 124 * 125 * @param v the {@code float} to be converted. 126 * @return a string representation of the argument. 127 * @see Float#toString(float) 128 */ toString(float v)129 public static String toString(float v) { 130 return new FloatToDecimal().toDecimalString(v); 131 } 132 133 /** 134 * Appends the rendering of the {@code v} to {@code app}. 135 * 136 * <p>The outcome is the same as if {@code v} were first 137 * {@link #toString(float) rendered} and the resulting string were then 138 * {@link Appendable#append(CharSequence) appended} to {@code app}. 139 * 140 * @param v the {@code float} whose rendering is appended. 141 * @param app the {@link Appendable} to append to. 142 * @throws IOException If an I/O error occurs 143 */ appendTo(float v, Appendable app)144 public static Appendable appendTo(float v, Appendable app) 145 throws IOException { 146 return new FloatToDecimal().appendDecimalTo(v, app); 147 } 148 toDecimalString(float v)149 private String toDecimalString(float v) { 150 return switch (toDecimal(v)) { 151 case NON_SPECIAL -> charsToString(); 152 case PLUS_ZERO -> "0.0"; 153 case MINUS_ZERO -> "-0.0"; 154 case PLUS_INF -> "Infinity"; 155 case MINUS_INF -> "-Infinity"; 156 default -> "NaN"; 157 }; 158 } 159 appendDecimalTo(float v, Appendable app)160 private Appendable appendDecimalTo(float v, Appendable app) 161 throws IOException { 162 switch (toDecimal(v)) { 163 case NON_SPECIAL: 164 char[] chars = new char[index + 1]; 165 for (int i = 0; i < chars.length; ++i) { 166 chars[i] = (char) bytes[i]; 167 } 168 if (app instanceof StringBuilder builder) { 169 return builder.append(chars); 170 } 171 if (app instanceof StringBuffer buffer) { 172 return buffer.append(chars); 173 } 174 for (char c : chars) { 175 app.append(c); 176 } 177 return app; 178 case PLUS_ZERO: return app.append("0.0"); 179 case MINUS_ZERO: return app.append("-0.0"); 180 case PLUS_INF: return app.append("Infinity"); 181 case MINUS_INF: return app.append("-Infinity"); 182 default: return app.append("NaN"); 183 } 184 } 185 186 /* 187 * Returns 188 * PLUS_ZERO iff v is 0.0 189 * MINUS_ZERO iff v is -0.0 190 * PLUS_INF iff v is POSITIVE_INFINITY 191 * MINUS_INF iff v is NEGATIVE_INFINITY 192 * NAN iff v is NaN 193 */ toDecimal(float v)194 private int toDecimal(float v) { 195 /* 196 * For full details see references [2] and [1]. 197 * 198 * For finite v != 0, determine integers c and q such that 199 * |v| = c 2^q and 200 * Q_MIN <= q <= Q_MAX and 201 * either 2^(P-1) <= c < 2^P (normal) 202 * or 0 < c < 2^(P-1) and q = Q_MIN (subnormal) 203 */ 204 int bits = floatToRawIntBits(v); 205 int t = bits & T_MASK; 206 int bq = (bits >>> P - 1) & BQ_MASK; 207 if (bq < BQ_MASK) { 208 index = -1; 209 if (bits < 0) { 210 append('-'); 211 } 212 if (bq != 0) { 213 /* normal value. Here mq = -q */ 214 int mq = -Q_MIN + 1 - bq; 215 int c = C_MIN | t; 216 /* The fast path discussed in section 8.3 of [1] */ 217 if (0 < mq & mq < P) { 218 int f = c >> mq; 219 if (f << mq == c) { 220 return toChars(f, 0); 221 } 222 } 223 return toDecimal(-mq, c, 0); 224 } 225 if (t != 0) { 226 /* subnormal value */ 227 return t < C_TINY 228 ? toDecimal(Q_MIN, 10 * t, -1) 229 : toDecimal(Q_MIN, t, 0); 230 } 231 return bits == 0 ? PLUS_ZERO : MINUS_ZERO; 232 } 233 if (t != 0) { 234 return NAN; 235 } 236 return bits > 0 ? PLUS_INF : MINUS_INF; 237 } 238 toDecimal(int q, int c, int dk)239 private int toDecimal(int q, int c, int dk) { 240 /* 241 * The skeleton corresponds to figure 7 of [1]. 242 * The efficient computations are those summarized in figure 9. 243 * Also check the appendix. 244 * 245 * Here's a correspondence between Java names and names in [1], 246 * expressed as approximate LaTeX source code and informally. 247 * Other names are identical. 248 * cb: \bar{c} "c-bar" 249 * cbr: \bar{c}_r "c-bar-r" 250 * cbl: \bar{c}_l "c-bar-l" 251 * 252 * vb: \bar{v} "v-bar" 253 * vbr: \bar{v}_r "v-bar-r" 254 * vbl: \bar{v}_l "v-bar-l" 255 * 256 * rop: r_o' "r-o-prime" 257 */ 258 int out = c & 0x1; 259 long cb = c << 2; 260 long cbr = cb + 2; 261 long cbl; 262 int k; 263 /* 264 * flog10pow2(e) = floor(log_10(2^e)) 265 * flog10threeQuartersPow2(e) = floor(log_10(3/4 2^e)) 266 * flog2pow10(e) = floor(log_2(10^e)) 267 */ 268 if (c != C_MIN | q == Q_MIN) { 269 /* regular spacing */ 270 cbl = cb - 2; 271 k = flog10pow2(q); 272 } else { 273 /* irregular spacing */ 274 cbl = cb - 1; 275 k = flog10threeQuartersPow2(q); 276 } 277 int h = q + flog2pow10(-k) + 33; 278 279 /* g is as in the appendix */ 280 long g = g1(k) + 1; 281 282 int vb = rop(g, cb << h); 283 int vbl = rop(g, cbl << h); 284 int vbr = rop(g, cbr << h); 285 286 int s = vb >> 2; 287 if (s >= 100) { 288 /* 289 * For n = 9, m = 1 the table in section 10 of [1] shows 290 * s' = floor(s / 10) = floor(s 1_717_986_919 / 2^34) 291 * 292 * sp10 = 10 s' 293 * tp10 = 10 t' 294 * upin iff u' = sp10 10^k in Rv 295 * wpin iff w' = tp10 10^k in Rv 296 * See section 9.3 of [1]. 297 */ 298 int sp10 = 10 * (int) (s * 1_717_986_919L >>> 34); 299 int tp10 = sp10 + 10; 300 boolean upin = vbl + out <= sp10 << 2; 301 boolean wpin = (tp10 << 2) + out <= vbr; 302 if (upin != wpin) { 303 return toChars(upin ? sp10 : tp10, k); 304 } 305 } 306 307 /* 308 * 10 <= s < 100 or s >= 100 and u', w' not in Rv 309 * uin iff u = s 10^k in Rv 310 * win iff w = t 10^k in Rv 311 * See section 9.3 of [1]. 312 */ 313 int t = s + 1; 314 boolean uin = vbl + out <= s << 2; 315 boolean win = (t << 2) + out <= vbr; 316 if (uin != win) { 317 /* Exactly one of u or w lies in Rv */ 318 return toChars(uin ? s : t, k + dk); 319 } 320 /* 321 * Both u and w lie in Rv: determine the one closest to v. 322 * See section 9.3 of [1]. 323 */ 324 int cmp = vb - (s + t << 1); 325 return toChars(cmp < 0 || cmp == 0 && (s & 0x1) == 0 ? s : t, k + dk); 326 } 327 328 /* 329 * Computes rop(cp g 2^(-95)) 330 * See appendix and figure 11 of [1]. 331 */ rop(long g, long cp)332 private static int rop(long g, long cp) { 333 long x1 = multiplyHigh(g, cp); 334 long vbp = x1 >>> 31; 335 return (int) (vbp | (x1 & MASK_32) + MASK_32 >>> 32); 336 } 337 338 /* 339 * Formats the decimal f 10^e. 340 */ toChars(int f, int e)341 private int toChars(int f, int e) { 342 /* 343 * For details not discussed here see section 10 of [1]. 344 * 345 * Determine len such that 346 * 10^(len-1) <= f < 10^len 347 */ 348 int len = flog10pow2(Integer.SIZE - numberOfLeadingZeros(f)); 349 if (f >= pow10(len)) { 350 len += 1; 351 } 352 353 /* 354 * Let fp and ep be the original f and e, respectively. 355 * Transform f and e to ensure 356 * 10^(H-1) <= f < 10^H 357 * fp 10^ep = f 10^(e-H) = 0.f 10^e 358 */ 359 f *= (int)pow10(H - len); 360 e += len; 361 362 /* 363 * The toChars?() methods perform left-to-right digits extraction 364 * using ints, provided that the arguments are limited to 8 digits. 365 * Therefore, split the H = 9 digits of f into: 366 * h = the most significant digit of f 367 * l = the last 8, least significant digits of f 368 * 369 * For n = 9, m = 8 the table in section 10 of [1] shows 370 * floor(f / 10^8) = floor(1_441_151_881 f / 2^57) 371 */ 372 int h = (int) (f * 1_441_151_881L >>> 57); 373 int l = f - 100_000_000 * h; 374 375 if (0 < e && e <= 7) { 376 return toChars1(h, l, e); 377 } 378 if (-3 < e && e <= 0) { 379 return toChars2(h, l, e); 380 } 381 return toChars3(h, l, e); 382 } 383 toChars1(int h, int l, int e)384 private int toChars1(int h, int l, int e) { 385 /* 386 * 0 < e <= 7: plain format without leading zeroes. 387 * Left-to-right digits extraction: 388 * algorithm 1 in [3], with b = 10, k = 8, n = 28. 389 */ 390 appendDigit(h); 391 int y = y(l); 392 int t; 393 int i = 1; 394 for (; i < e; ++i) { 395 t = 10 * y; 396 appendDigit(t >>> 28); 397 y = t & MASK_28; 398 } 399 append('.'); 400 for (; i <= 8; ++i) { 401 t = 10 * y; 402 appendDigit(t >>> 28); 403 y = t & MASK_28; 404 } 405 removeTrailingZeroes(); 406 return NON_SPECIAL; 407 } 408 toChars2(int h, int l, int e)409 private int toChars2(int h, int l, int e) { 410 /* -3 < e <= 0: plain format with leading zeroes */ 411 appendDigit(0); 412 append('.'); 413 for (; e < 0; ++e) { 414 appendDigit(0); 415 } 416 appendDigit(h); 417 append8Digits(l); 418 removeTrailingZeroes(); 419 return NON_SPECIAL; 420 } 421 toChars3(int h, int l, int e)422 private int toChars3(int h, int l, int e) { 423 /* -3 >= e | e > 7: computerized scientific notation */ 424 appendDigit(h); 425 append('.'); 426 append8Digits(l); 427 removeTrailingZeroes(); 428 exponent(e - 1); 429 return NON_SPECIAL; 430 } 431 append8Digits(int m)432 private void append8Digits(int m) { 433 /* 434 * Left-to-right digits extraction: 435 * algorithm 1 in [3], with b = 10, k = 8, n = 28. 436 */ 437 int y = y(m); 438 for (int i = 0; i < 8; ++i) { 439 int t = 10 * y; 440 appendDigit(t >>> 28); 441 y = t & MASK_28; 442 } 443 } 444 removeTrailingZeroes()445 private void removeTrailingZeroes() { 446 while (bytes[index] == '0') { 447 --index; 448 } 449 /* ... but do not remove the one directly to the right of '.' */ 450 if (bytes[index] == '.') { 451 ++index; 452 } 453 } 454 y(int a)455 private int y(int a) { 456 /* 457 * Algorithm 1 in [3] needs computation of 458 * floor((a + 1) 2^n / b^k) - 1 459 * with a < 10^8, b = 10, k = 8, n = 28. 460 * Noting that 461 * (a + 1) 2^n <= 10^8 2^28 < 10^17 462 * For n = 17, m = 8 the table in section 10 of [1] leads to: 463 */ 464 return (int) (multiplyHigh( 465 (long) (a + 1) << 28, 466 193_428_131_138_340_668L) >>> 20) - 1; 467 } 468 exponent(int e)469 private void exponent(int e) { 470 append('E'); 471 if (e < 0) { 472 append('-'); 473 e = -e; 474 } 475 if (e < 10) { 476 appendDigit(e); 477 return; 478 } 479 /* 480 * For n = 2, m = 1 the table in section 10 of [1] shows 481 * floor(e / 10) = floor(103 e / 2^10) 482 */ 483 int d = e * 103 >>> 10; 484 appendDigit(d); 485 appendDigit(e - 10 * d); 486 } 487 append(int c)488 private void append(int c) { 489 bytes[++index] = (byte) c; 490 } 491 appendDigit(int d)492 private void appendDigit(int d) { 493 bytes[++index] = (byte) ('0' + d); 494 } 495 496 /* Using the deprecated constructor enhances performance */ 497 @SuppressWarnings("deprecation") charsToString()498 private String charsToString() { 499 return new String(bytes, 0, 0, index + 1); 500 } 501 502 } 503