1 /* 2 * Copyright (c) 2021, 2023, 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.Double.*; 31 import static java.lang.Long.*; 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 double} as a string. 37 */ 38 public final class DoubleToDecimal { 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 = (Double.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 = -323; 68 69 /* 10^(E_MAX - 1) <= MAX_VALUE < 10^E_MAX */ 70 static final int E_MAX = 309; 71 72 /* Threshold to detect tiny values, as in section 8.2.1 of [1] */ 73 static final long C_TINY = 3; 74 75 /* The minimum and maximum k, as in section 8 of [1] */ 76 static final int K_MIN = -324; 77 static final int K_MAX = 292; 78 79 /* H is as in section 8.1 of [1] */ 80 static final int H = 17; 81 82 /* Minimum value of the significand of a normal value: 2^(P-1) */ 83 private static final long C_MIN = 1L << (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 long T_MASK = (1L << (P - 1)) - 1; 90 91 /* Used in rop() */ 92 private static final long MASK_63 = (1L << 63) - 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.dddddddddddd H + 2 characters 107 * -0.00ddddddddddddddddd H + 5 characters 108 * -d.ddddddddddddddddE-eee H + 7 characters 109 * where there are H digits d 110 */ 111 public static final int MAX_CHARS = H + 7; 112 113 private final byte[] bytes; 114 115 /* Index into bytes of rightmost valid character */ 116 private int index; 117 DoubleToDecimal(boolean noChars)118 private DoubleToDecimal(boolean noChars) { 119 bytes = noChars ? null : new byte[MAX_CHARS]; 120 } 121 122 /** 123 * Returns a string representation of the {@code double} 124 * argument. All characters mentioned below are ASCII characters. 125 * 126 * @param v the {@code double} to be converted. 127 * @return a string representation of the argument. 128 * @see Double#toString(double) 129 */ toString(double v)130 public static String toString(double v) { 131 return new DoubleToDecimal(false).toDecimalString(v); 132 } 133 134 /** 135 * Splits the decimal <i>d</i> described in 136 * {@link Double#toString(double)} in integers <i>f</i> and <i>e</i> 137 * such that <i>d</i> = <i>f</i> 10<sup><i>e</i></sup>. 138 * 139 * <p>Further, determines integer <i>n</i> such that <i>n</i> = 0 when 140 * <i>f</i> = 0, and 141 * 10<sup><i>n</i>-1</sup> ≤ <i>f</i> < 10<sup><i>n</i></sup> 142 * otherwise. 143 * 144 * <p>The argument {@code v} is assumed to be a positive finite value or 145 * positive zero. 146 * Further, {@code fd} must not be {@code null}. 147 * 148 * @param v the finite {@code double} to be split. 149 * @param fd the object that will carry <i>f</i>, <i>e</i>, and <i>n</i>. 150 */ split(double v, FormattedFPDecimal fd)151 public static void split(double v, FormattedFPDecimal fd) { 152 new DoubleToDecimal(true).toDecimal(v, fd); 153 } 154 155 /** 156 * Appends the rendering of the {@code v} to {@code app}. 157 * 158 * <p>The outcome is the same as if {@code v} were first 159 * {@link #toString(double) rendered} and the resulting string were then 160 * {@link Appendable#append(CharSequence) appended} to {@code app}. 161 * 162 * @param v the {@code double} whose rendering is appended. 163 * @param app the {@link Appendable} to append to. 164 * @throws IOException If an I/O error occurs 165 */ appendTo(double v, Appendable app)166 public static Appendable appendTo(double v, Appendable app) 167 throws IOException { 168 return new DoubleToDecimal(false).appendDecimalTo(v, app); 169 } 170 toDecimalString(double v)171 private String toDecimalString(double v) { 172 return switch (toDecimal(v, null)) { 173 case NON_SPECIAL -> charsToString(); 174 case PLUS_ZERO -> "0.0"; 175 case MINUS_ZERO -> "-0.0"; 176 case PLUS_INF -> "Infinity"; 177 case MINUS_INF -> "-Infinity"; 178 default -> "NaN"; 179 }; 180 } 181 appendDecimalTo(double v, Appendable app)182 private Appendable appendDecimalTo(double v, Appendable app) 183 throws IOException { 184 switch (toDecimal(v, null)) { 185 case NON_SPECIAL: 186 char[] chars = new char[index + 1]; 187 for (int i = 0; i < chars.length; ++i) { 188 chars[i] = (char) bytes[i]; 189 } 190 if (app instanceof StringBuilder builder) { 191 return builder.append(chars); 192 } 193 if (app instanceof StringBuffer buffer) { 194 return buffer.append(chars); 195 } 196 for (char c : chars) { 197 app.append(c); 198 } 199 return app; 200 case PLUS_ZERO: return app.append("0.0"); 201 case MINUS_ZERO: return app.append("-0.0"); 202 case PLUS_INF: return app.append("Infinity"); 203 case MINUS_INF: return app.append("-Infinity"); 204 default: return app.append("NaN"); 205 } 206 } 207 208 /* 209 * Returns 210 * PLUS_ZERO iff v is 0.0 211 * MINUS_ZERO iff v is -0.0 212 * PLUS_INF iff v is POSITIVE_INFINITY 213 * MINUS_INF iff v is NEGATIVE_INFINITY 214 * NAN iff v is NaN 215 */ toDecimal(double v, FormattedFPDecimal fd)216 private int toDecimal(double v, FormattedFPDecimal fd) { 217 /* 218 * For full details see references [2] and [1]. 219 * 220 * For finite v != 0, determine integers c and q such that 221 * |v| = c 2^q and 222 * Q_MIN <= q <= Q_MAX and 223 * either 2^(P-1) <= c < 2^P (normal) 224 * or 0 < c < 2^(P-1) and q = Q_MIN (subnormal) 225 */ 226 long bits = doubleToRawLongBits(v); 227 long t = bits & T_MASK; 228 int bq = (int) (bits >>> P - 1) & BQ_MASK; 229 if (bq < BQ_MASK) { 230 index = -1; 231 if (bits < 0) { 232 /* 233 * fd != null implies bytes == null and bits >= 0 234 * Thus, when fd != null, control never reaches here. 235 */ 236 append('-'); 237 } 238 if (bq != 0) { 239 /* normal value. Here mq = -q */ 240 int mq = -Q_MIN + 1 - bq; 241 long c = C_MIN | t; 242 /* The fast path discussed in section 8.3 of [1] */ 243 if (0 < mq & mq < P) { 244 long f = c >> mq; 245 if (f << mq == c) { 246 return toChars(f, 0, fd); 247 } 248 } 249 return toDecimal(-mq, c, 0, fd); 250 } 251 if (t != 0) { 252 /* subnormal value */ 253 return t < C_TINY 254 ? toDecimal(Q_MIN, 10 * t, -1, fd) 255 : toDecimal(Q_MIN, t, 0, fd); 256 } 257 return bits == 0 ? PLUS_ZERO : MINUS_ZERO; 258 } 259 if (t != 0) { 260 return NAN; 261 } 262 return bits > 0 ? PLUS_INF : MINUS_INF; 263 } 264 toDecimal(int q, long c, int dk, FormattedFPDecimal fd)265 private int toDecimal(int q, long c, int dk, FormattedFPDecimal fd) { 266 /* 267 * The skeleton corresponds to figure 7 of [1]. 268 * The efficient computations are those summarized in figure 9. 269 * 270 * Here's a correspondence between Java names and names in [1], 271 * expressed as approximate LaTeX source code and informally. 272 * Other names are identical. 273 * cb: \bar{c} "c-bar" 274 * cbr: \bar{c}_r "c-bar-r" 275 * cbl: \bar{c}_l "c-bar-l" 276 * 277 * vb: \bar{v} "v-bar" 278 * vbr: \bar{v}_r "v-bar-r" 279 * vbl: \bar{v}_l "v-bar-l" 280 * 281 * rop: r_o' "r-o-prime" 282 */ 283 int out = (int) c & 0x1; 284 long cb = c << 2; 285 long cbr = cb + 2; 286 long cbl; 287 int k; 288 /* 289 * flog10pow2(e) = floor(log_10(2^e)) 290 * flog10threeQuartersPow2(e) = floor(log_10(3/4 2^e)) 291 * flog2pow10(e) = floor(log_2(10^e)) 292 */ 293 if (c != C_MIN | q == Q_MIN) { 294 /* regular spacing */ 295 cbl = cb - 2; 296 k = flog10pow2(q); 297 } else { 298 /* irregular spacing */ 299 cbl = cb - 1; 300 k = flog10threeQuartersPow2(q); 301 } 302 int h = q + flog2pow10(-k) + 2; 303 304 /* g1 and g0 are as in section 9.8.3 of [1], so g = g1 2^63 + g0 */ 305 long g1 = g1(k); 306 long g0 = g0(k); 307 308 long vb = rop(g1, g0, cb << h); 309 long vbl = rop(g1, g0, cbl << h); 310 long vbr = rop(g1, g0, cbr << h); 311 312 long s = vb >> 2; 313 if (s >= 100) { 314 /* 315 * For n = 17, m = 1 the table in section 10 of [1] shows 316 * s' = floor(s / 10) = floor(s 115_292_150_460_684_698 / 2^60) 317 * = floor(s 115_292_150_460_684_698 2^4 / 2^64) 318 * 319 * sp10 = 10 s' 320 * tp10 = 10 t' 321 * upin iff u' = sp10 10^k in Rv 322 * wpin iff w' = tp10 10^k in Rv 323 * See section 9.3 of [1]. 324 */ 325 long sp10 = 10 * multiplyHigh(s, 115_292_150_460_684_698L << 4); 326 long tp10 = sp10 + 10; 327 boolean upin = vbl + out <= sp10 << 2; 328 boolean wpin = (tp10 << 2) + out <= vbr; 329 if (upin != wpin) { 330 return toChars(upin ? sp10 : tp10, k, fd); 331 } 332 } 333 334 /* 335 * 10 <= s < 100 or s >= 100 and u', w' not in Rv 336 * uin iff u = s 10^k in Rv 337 * win iff w = t 10^k in Rv 338 * See section 9.3 of [1]. 339 */ 340 long t = s + 1; 341 boolean uin = vbl + out <= s << 2; 342 boolean win = (t << 2) + out <= vbr; 343 if (uin != win) { 344 /* Exactly one of u or w lies in Rv */ 345 return toChars(uin ? s : t, k + dk, fd); 346 } 347 /* 348 * Both u and w lie in Rv: determine the one closest to v. 349 * See section 9.3 of [1]. 350 */ 351 long cmp = vb - (s + t << 1); 352 return toChars(cmp < 0 || cmp == 0 && (s & 0x1) == 0 ? s : t, k + dk, fd); 353 } 354 355 /* 356 * Computes rop(cp g 2^(-127)), where g = g1 2^63 + g0 357 * See section 9.9 and figure 8 of [1]. 358 */ rop(long g1, long g0, long cp)359 private static long rop(long g1, long g0, long cp) { 360 long x1 = multiplyHigh(g0, cp); 361 long y0 = g1 * cp; 362 long y1 = multiplyHigh(g1, cp); 363 long z = (y0 >>> 1) + x1; 364 long vbp = y1 + (z >>> 63); 365 return vbp | (z & MASK_63) + MASK_63 >>> 63; 366 } 367 368 /* 369 * Formats the decimal f 10^e. 370 */ toChars(long f, int e, FormattedFPDecimal fd)371 private int toChars(long f, int e, FormattedFPDecimal fd) { 372 /* 373 * For details not discussed here see section 10 of [1]. 374 * 375 * Determine len such that 376 * 10^(len-1) <= f < 10^len 377 */ 378 int len = flog10pow2(Long.SIZE - numberOfLeadingZeros(f)); 379 if (f >= pow10(len)) { 380 len += 1; 381 } 382 if (fd != null) { 383 fd.set(f, e, len); 384 return NON_SPECIAL; 385 } 386 387 /* 388 * Let fp and ep be the original f and e, respectively. 389 * Transform f and e to ensure 390 * 10^(H-1) <= f < 10^H 391 * fp 10^ep = f 10^(e-H) = 0.f 10^e 392 */ 393 f *= pow10(H - len); 394 e += len; 395 396 /* 397 * The toChars?() methods perform left-to-right digits extraction 398 * using ints, provided that the arguments are limited to 8 digits. 399 * Therefore, split the H = 17 digits of f into: 400 * h = the most significant digit of f 401 * m = the next 8 most significant digits of f 402 * l = the last 8, least significant digits of f 403 * 404 * For n = 17, m = 8 the table in section 10 of [1] shows 405 * floor(f / 10^8) = floor(193_428_131_138_340_668 f / 2^84) = 406 * floor(floor(193_428_131_138_340_668 f / 2^64) / 2^20) 407 * and for n = 9, m = 8 408 * floor(hm / 10^8) = floor(1_441_151_881 hm / 2^57) 409 */ 410 long hm = multiplyHigh(f, 193_428_131_138_340_668L) >>> 20; 411 int l = (int) (f - 100_000_000L * hm); 412 int h = (int) (hm * 1_441_151_881L >>> 57); 413 int m = (int) (hm - 100_000_000 * h); 414 415 if (0 < e && e <= 7) { 416 return toChars1(h, m, l, e); 417 } 418 if (-3 < e && e <= 0) { 419 return toChars2(h, m, l, e); 420 } 421 return toChars3(h, m, l, e); 422 } 423 toChars1(int h, int m, int l, int e)424 private int toChars1(int h, int m, int l, int e) { 425 /* 426 * 0 < e <= 7: plain format without leading zeroes. 427 * Left-to-right digits extraction: 428 * algorithm 1 in [3], with b = 10, k = 8, n = 28. 429 */ 430 appendDigit(h); 431 int y = y(m); 432 int t; 433 int i = 1; 434 for (; i < e; ++i) { 435 t = 10 * y; 436 appendDigit(t >>> 28); 437 y = t & MASK_28; 438 } 439 append('.'); 440 for (; i <= 8; ++i) { 441 t = 10 * y; 442 appendDigit(t >>> 28); 443 y = t & MASK_28; 444 } 445 lowDigits(l); 446 return NON_SPECIAL; 447 } 448 toChars2(int h, int m, int l, int e)449 private int toChars2(int h, int m, int l, int e) { 450 /* -3 < e <= 0: plain format with leading zeroes */ 451 appendDigit(0); 452 append('.'); 453 for (; e < 0; ++e) { 454 appendDigit(0); 455 } 456 appendDigit(h); 457 append8Digits(m); 458 lowDigits(l); 459 return NON_SPECIAL; 460 } 461 toChars3(int h, int m, int l, int e)462 private int toChars3(int h, int m, int l, int e) { 463 /* -3 >= e | e > 7: computerized scientific notation */ 464 appendDigit(h); 465 append('.'); 466 append8Digits(m); 467 lowDigits(l); 468 exponent(e - 1); 469 return NON_SPECIAL; 470 } 471 lowDigits(int l)472 private void lowDigits(int l) { 473 if (l != 0) { 474 append8Digits(l); 475 } 476 removeTrailingZeroes(); 477 } 478 append8Digits(int m)479 private void append8Digits(int m) { 480 /* 481 * Left-to-right digits extraction: 482 * algorithm 1 in [3], with b = 10, k = 8, n = 28. 483 */ 484 int y = y(m); 485 for (int i = 0; i < 8; ++i) { 486 int t = 10 * y; 487 appendDigit(t >>> 28); 488 y = t & MASK_28; 489 } 490 } 491 removeTrailingZeroes()492 private void removeTrailingZeroes() { 493 while (bytes[index] == '0') { 494 --index; 495 } 496 /* ... but do not remove the one directly to the right of '.' */ 497 if (bytes[index] == '.') { 498 ++index; 499 } 500 } 501 y(int a)502 private int y(int a) { 503 /* 504 * Algorithm 1 in [3] needs computation of 505 * floor((a + 1) 2^n / b^k) - 1 506 * with a < 10^8, b = 10, k = 8, n = 28. 507 * Noting that 508 * (a + 1) 2^n <= 10^8 2^28 < 10^17 509 * For n = 17, m = 8 the table in section 10 of [1] leads to: 510 */ 511 return (int) (multiplyHigh( 512 (long) (a + 1) << 28, 513 193_428_131_138_340_668L) >>> 20) - 1; 514 } 515 exponent(int e)516 private void exponent(int e) { 517 append('E'); 518 if (e < 0) { 519 append('-'); 520 e = -e; 521 } 522 if (e < 10) { 523 appendDigit(e); 524 return; 525 } 526 int d; 527 if (e >= 100) { 528 /* 529 * For n = 3, m = 2 the table in section 10 of [1] shows 530 * floor(e / 100) = floor(1_311 e / 2^17) 531 */ 532 d = e * 1_311 >>> 17; 533 appendDigit(d); 534 e -= 100 * d; 535 } 536 /* 537 * For n = 2, m = 1 the table in section 10 of [1] shows 538 * floor(e / 10) = floor(103 e / 2^10) 539 */ 540 d = e * 103 >>> 10; 541 appendDigit(d); 542 appendDigit(e - 10 * d); 543 } 544 append(int c)545 private void append(int c) { 546 bytes[++index] = (byte) c; 547 } 548 appendDigit(int d)549 private void appendDigit(int d) { 550 bytes[++index] = (byte) ('0' + d); 551 } 552 553 /* Using the deprecated constructor enhances performance */ 554 @SuppressWarnings("deprecation") charsToString()555 private String charsToString() { 556 return new String(bytes, 0, 0, index + 1); 557 } 558 559 } 560