1/**************************************************************** 2 * 3 * The author of this software is David M. Gay. 4 * 5 * Copyright (c) 1991, 2000, 2001 by Lucent Technologies. 6 * Copyright (C) 2002, 2005, 2006, 2007, 2008, 2010, 2012 Apple Inc. All rights reserved. 7 * 8 * Permission to use, copy, modify, and distribute this software for any 9 * purpose without fee is hereby granted, provided that this entire notice 10 * is included in all copies of any software which is or includes a copy 11 * or modification of this software and in all copies of the supporting 12 * documentation for such software. 13 * 14 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED 15 * WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY 16 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY 17 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. 18 * 19 ***************************************************************/ 20 21/* Please send bug reports to David M. Gay (dmg at acm dot org, 22 * with " at " changed at "@" and " dot " changed to "."). */ 23 24/* On a machine with IEEE extended-precision registers, it is 25 * necessary to specify double-precision (53-bit) rounding precision 26 * before invoking strtod or dtoa. If the machine uses (the equivalent 27 * of) Intel 80x87 arithmetic, the call 28 * _control87(PC_53, MCW_PC); 29 * does this with many compilers. Whether this or another call is 30 * appropriate depends on the compiler; for this to work, it may be 31 * necessary to #include "float.h" or another system-dependent header 32 * file. 33 */ 34 35#include "config.h" 36#include "dtoa.h" 37 38#include <stdio.h> 39#include <wtf/MathExtras.h> 40#include <wtf/Threading.h> 41#include <wtf/Vector.h> 42 43#if COMPILER(MSVC) 44#pragma warning(disable: 4244) 45#pragma warning(disable: 4245) 46#pragma warning(disable: 4554) 47#endif 48 49#if CPU(PPC64) || CPU(X86_64) || CPU(ARM64) 50// FIXME: should we enable this on all 64-bit CPUs? 51// 64-bit emulation provided by the compiler is likely to be slower than dtoa own code on 32-bit hardware. 52#define USE_LONG_LONG 53#endif 54 55namespace WTF { 56 57Mutex* s_dtoaP5Mutex; 58 59typedef union { 60 double d; 61 uint32_t L[2]; 62} U; 63 64#if CPU(BIG_ENDIAN) || CPU(MIDDLE_ENDIAN) 65#define word0(x) (x)->L[0] 66#define word1(x) (x)->L[1] 67#else 68#define word0(x) (x)->L[1] 69#define word1(x) (x)->L[0] 70#endif 71#define dval(x) (x)->d 72 73#ifndef USE_LONG_LONG 74/* The following definition of Storeinc is appropriate for MIPS processors. 75 * An alternative that might be better on some machines is 76 * *p++ = high << 16 | low & 0xffff; 77 */ 78static ALWAYS_INLINE uint32_t* storeInc(uint32_t* p, uint16_t high, uint16_t low) 79{ 80 uint16_t* p16 = reinterpret_cast<uint16_t*>(p); 81#if CPU(BIG_ENDIAN) 82 p16[0] = high; 83 p16[1] = low; 84#else 85 p16[1] = high; 86 p16[0] = low; 87#endif 88 return p + 1; 89} 90 91#endif // USE_LONG_LONG 92 93#define Exp_shift 20 94#define Exp_shift1 20 95#define Exp_msk1 0x100000 96#define Exp_msk11 0x100000 97#define Exp_mask 0x7ff00000 98#define P 53 99#define Bias 1023 100#define Emin (-1022) 101#define Exp_1 0x3ff00000 102#define Exp_11 0x3ff00000 103#define Ebits 11 104#define Frac_mask 0xfffff 105#define Frac_mask1 0xfffff 106#define Ten_pmax 22 107#define Bletch 0x10 108#define Bndry_mask 0xfffff 109#define Bndry_mask1 0xfffff 110#define LSB 1 111#define Sign_bit 0x80000000 112#define Log2P 1 113#define Tiny0 0 114#define Tiny1 1 115#define Quick_max 14 116#define Int_max 14 117 118#define rounded_product(a, b) a *= b 119#define rounded_quotient(a, b) a /= b 120 121#define Big0 (Frac_mask1 | Exp_msk1 * (DBL_MAX_EXP + Bias - 1)) 122#define Big1 0xffffffff 123 124struct BigInt { 125 BigInt() : sign(0) { } 126 int sign; 127 128 void clear() 129 { 130 sign = 0; 131 m_words.clear(); 132 } 133 134 size_t size() const 135 { 136 return m_words.size(); 137 } 138 139 void resize(size_t s) 140 { 141 m_words.resize(s); 142 } 143 144 uint32_t* words() 145 { 146 return m_words.data(); 147 } 148 149 const uint32_t* words() const 150 { 151 return m_words.data(); 152 } 153 154 void append(uint32_t w) 155 { 156 m_words.append(w); 157 } 158 159 Vector<uint32_t, 16> m_words; 160}; 161 162static void multadd(BigInt& b, int m, int a) /* multiply by m and add a */ 163{ 164#ifdef USE_LONG_LONG 165 unsigned long long carry; 166#else 167 uint32_t carry; 168#endif 169 170 int wds = b.size(); 171 uint32_t* x = b.words(); 172 int i = 0; 173 carry = a; 174 do { 175#ifdef USE_LONG_LONG 176 unsigned long long y = *x * (unsigned long long)m + carry; 177 carry = y >> 32; 178 *x++ = (uint32_t)y & 0xffffffffUL; 179#else 180 uint32_t xi = *x; 181 uint32_t y = (xi & 0xffff) * m + carry; 182 uint32_t z = (xi >> 16) * m + (y >> 16); 183 carry = z >> 16; 184 *x++ = (z << 16) + (y & 0xffff); 185#endif 186 } while (++i < wds); 187 188 if (carry) 189 b.append((uint32_t)carry); 190} 191 192static int hi0bits(uint32_t x) 193{ 194 int k = 0; 195 196 if (!(x & 0xffff0000)) { 197 k = 16; 198 x <<= 16; 199 } 200 if (!(x & 0xff000000)) { 201 k += 8; 202 x <<= 8; 203 } 204 if (!(x & 0xf0000000)) { 205 k += 4; 206 x <<= 4; 207 } 208 if (!(x & 0xc0000000)) { 209 k += 2; 210 x <<= 2; 211 } 212 if (!(x & 0x80000000)) { 213 k++; 214 if (!(x & 0x40000000)) 215 return 32; 216 } 217 return k; 218} 219 220static int lo0bits(uint32_t* y) 221{ 222 int k; 223 uint32_t x = *y; 224 225 if (x & 7) { 226 if (x & 1) 227 return 0; 228 if (x & 2) { 229 *y = x >> 1; 230 return 1; 231 } 232 *y = x >> 2; 233 return 2; 234 } 235 k = 0; 236 if (!(x & 0xffff)) { 237 k = 16; 238 x >>= 16; 239 } 240 if (!(x & 0xff)) { 241 k += 8; 242 x >>= 8; 243 } 244 if (!(x & 0xf)) { 245 k += 4; 246 x >>= 4; 247 } 248 if (!(x & 0x3)) { 249 k += 2; 250 x >>= 2; 251 } 252 if (!(x & 1)) { 253 k++; 254 x >>= 1; 255 if (!x) 256 return 32; 257 } 258 *y = x; 259 return k; 260} 261 262static void i2b(BigInt& b, int i) 263{ 264 b.sign = 0; 265 b.resize(1); 266 b.words()[0] = i; 267} 268 269static void mult(BigInt& aRef, const BigInt& bRef) 270{ 271 const BigInt* a = &aRef; 272 const BigInt* b = &bRef; 273 BigInt c; 274 int wa, wb, wc; 275 const uint32_t* x = 0; 276 const uint32_t* xa; 277 const uint32_t* xb; 278 const uint32_t* xae; 279 const uint32_t* xbe; 280 uint32_t* xc; 281 uint32_t* xc0; 282 uint32_t y; 283#ifdef USE_LONG_LONG 284 unsigned long long carry, z; 285#else 286 uint32_t carry, z; 287#endif 288 289 if (a->size() < b->size()) { 290 const BigInt* tmp = a; 291 a = b; 292 b = tmp; 293 } 294 295 wa = a->size(); 296 wb = b->size(); 297 wc = wa + wb; 298 c.resize(wc); 299 300 for (xc = c.words(), xa = xc + wc; xc < xa; xc++) 301 *xc = 0; 302 xa = a->words(); 303 xae = xa + wa; 304 xb = b->words(); 305 xbe = xb + wb; 306 xc0 = c.words(); 307#ifdef USE_LONG_LONG 308 for (; xb < xbe; xc0++) { 309 if ((y = *xb++)) { 310 x = xa; 311 xc = xc0; 312 carry = 0; 313 do { 314 z = *x++ * (unsigned long long)y + *xc + carry; 315 carry = z >> 32; 316 *xc++ = (uint32_t)z & 0xffffffffUL; 317 } while (x < xae); 318 *xc = (uint32_t)carry; 319 } 320 } 321#else 322 for (; xb < xbe; xb++, xc0++) { 323 if ((y = *xb & 0xffff)) { 324 x = xa; 325 xc = xc0; 326 carry = 0; 327 do { 328 z = (*x & 0xffff) * y + (*xc & 0xffff) + carry; 329 carry = z >> 16; 330 uint32_t z2 = (*x++ >> 16) * y + (*xc >> 16) + carry; 331 carry = z2 >> 16; 332 xc = storeInc(xc, z2, z); 333 } while (x < xae); 334 *xc = carry; 335 } 336 if ((y = *xb >> 16)) { 337 x = xa; 338 xc = xc0; 339 carry = 0; 340 uint32_t z2 = *xc; 341 do { 342 z = (*x & 0xffff) * y + (*xc >> 16) + carry; 343 carry = z >> 16; 344 xc = storeInc(xc, z, z2); 345 z2 = (*x++ >> 16) * y + (*xc & 0xffff) + carry; 346 carry = z2 >> 16; 347 } while (x < xae); 348 *xc = z2; 349 } 350 } 351#endif 352 for (xc0 = c.words(), xc = xc0 + wc; wc > 0 && !*--xc; --wc) { } 353 c.resize(wc); 354 aRef = c; 355} 356 357struct P5Node { 358 WTF_MAKE_NONCOPYABLE(P5Node); WTF_MAKE_FAST_ALLOCATED; 359public: 360 P5Node() { } 361 BigInt val; 362 P5Node* next; 363}; 364 365static P5Node* p5s; 366static int p5sCount; 367 368static ALWAYS_INLINE void pow5mult(BigInt& b, int k) 369{ 370 static int p05[3] = { 5, 25, 125 }; 371 372 if (int i = k & 3) 373 multadd(b, p05[i - 1], 0); 374 375 if (!(k >>= 2)) 376 return; 377 378 s_dtoaP5Mutex->lock(); 379 P5Node* p5 = p5s; 380 381 if (!p5) { 382 /* first time */ 383 p5 = new P5Node; 384 i2b(p5->val, 625); 385 p5->next = 0; 386 p5s = p5; 387 p5sCount = 1; 388 } 389 390 int p5sCountLocal = p5sCount; 391 s_dtoaP5Mutex->unlock(); 392 int p5sUsed = 0; 393 394 for (;;) { 395 if (k & 1) 396 mult(b, p5->val); 397 398 if (!(k >>= 1)) 399 break; 400 401 if (++p5sUsed == p5sCountLocal) { 402 s_dtoaP5Mutex->lock(); 403 if (p5sUsed == p5sCount) { 404 ASSERT(!p5->next); 405 p5->next = new P5Node; 406 p5->next->next = 0; 407 p5->next->val = p5->val; 408 mult(p5->next->val, p5->next->val); 409 ++p5sCount; 410 } 411 412 p5sCountLocal = p5sCount; 413 s_dtoaP5Mutex->unlock(); 414 } 415 p5 = p5->next; 416 } 417} 418 419static ALWAYS_INLINE void lshift(BigInt& b, int k) 420{ 421 int n = k >> 5; 422 423 int origSize = b.size(); 424 int n1 = n + origSize + 1; 425 426 if (k &= 0x1f) 427 b.resize(b.size() + n + 1); 428 else 429 b.resize(b.size() + n); 430 431 const uint32_t* srcStart = b.words(); 432 uint32_t* dstStart = b.words(); 433 const uint32_t* src = srcStart + origSize - 1; 434 uint32_t* dst = dstStart + n1 - 1; 435 if (k) { 436 uint32_t hiSubword = 0; 437 int s = 32 - k; 438 for (; src >= srcStart; --src) { 439 *dst-- = hiSubword | *src >> s; 440 hiSubword = *src << k; 441 } 442 *dst = hiSubword; 443 ASSERT(dst == dstStart + n); 444 445 b.resize(origSize + n + !!b.words()[n1 - 1]); 446 } 447 else { 448 do { 449 *--dst = *src--; 450 } while (src >= srcStart); 451 } 452 for (dst = dstStart + n; dst != dstStart; ) 453 *--dst = 0; 454 455 ASSERT(b.size() <= 1 || b.words()[b.size() - 1]); 456} 457 458static int cmp(const BigInt& a, const BigInt& b) 459{ 460 const uint32_t *xa, *xa0, *xb, *xb0; 461 int i, j; 462 463 i = a.size(); 464 j = b.size(); 465 ASSERT(i <= 1 || a.words()[i - 1]); 466 ASSERT(j <= 1 || b.words()[j - 1]); 467 if (i -= j) 468 return i; 469 xa0 = a.words(); 470 xa = xa0 + j; 471 xb0 = b.words(); 472 xb = xb0 + j; 473 for (;;) { 474 if (*--xa != *--xb) 475 return *xa < *xb ? -1 : 1; 476 if (xa <= xa0) 477 break; 478 } 479 return 0; 480} 481 482static ALWAYS_INLINE void diff(BigInt& c, const BigInt& aRef, const BigInt& bRef) 483{ 484 const BigInt* a = &aRef; 485 const BigInt* b = &bRef; 486 int i, wa, wb; 487 uint32_t* xc; 488 489 i = cmp(*a, *b); 490 if (!i) { 491 c.sign = 0; 492 c.resize(1); 493 c.words()[0] = 0; 494 return; 495 } 496 if (i < 0) { 497 const BigInt* tmp = a; 498 a = b; 499 b = tmp; 500 i = 1; 501 } else 502 i = 0; 503 504 wa = a->size(); 505 const uint32_t* xa = a->words(); 506 const uint32_t* xae = xa + wa; 507 wb = b->size(); 508 const uint32_t* xb = b->words(); 509 const uint32_t* xbe = xb + wb; 510 511 c.resize(wa); 512 c.sign = i; 513 xc = c.words(); 514#ifdef USE_LONG_LONG 515 unsigned long long borrow = 0; 516 do { 517 unsigned long long y = (unsigned long long)*xa++ - *xb++ - borrow; 518 borrow = y >> 32 & (uint32_t)1; 519 *xc++ = (uint32_t)y & 0xffffffffUL; 520 } while (xb < xbe); 521 while (xa < xae) { 522 unsigned long long y = *xa++ - borrow; 523 borrow = y >> 32 & (uint32_t)1; 524 *xc++ = (uint32_t)y & 0xffffffffUL; 525 } 526#else 527 uint32_t borrow = 0; 528 do { 529 uint32_t y = (*xa & 0xffff) - (*xb & 0xffff) - borrow; 530 borrow = (y & 0x10000) >> 16; 531 uint32_t z = (*xa++ >> 16) - (*xb++ >> 16) - borrow; 532 borrow = (z & 0x10000) >> 16; 533 xc = storeInc(xc, z, y); 534 } while (xb < xbe); 535 while (xa < xae) { 536 uint32_t y = (*xa & 0xffff) - borrow; 537 borrow = (y & 0x10000) >> 16; 538 uint32_t z = (*xa++ >> 16) - borrow; 539 borrow = (z & 0x10000) >> 16; 540 xc = storeInc(xc, z, y); 541 } 542#endif 543 while (!*--xc) 544 wa--; 545 c.resize(wa); 546} 547 548static ALWAYS_INLINE void d2b(BigInt& b, U* d, int* e, int* bits) 549{ 550 int de, k; 551 uint32_t* x; 552 uint32_t y, z; 553 int i; 554#define d0 word0(d) 555#define d1 word1(d) 556 557 b.sign = 0; 558 b.resize(1); 559 x = b.words(); 560 561 z = d0 & Frac_mask; 562 d0 &= 0x7fffffff; /* clear sign bit, which we ignore */ 563 if ((de = (int)(d0 >> Exp_shift))) 564 z |= Exp_msk1; 565 if ((y = d1)) { 566 if ((k = lo0bits(&y))) { 567 x[0] = y | (z << (32 - k)); 568 z >>= k; 569 } else 570 x[0] = y; 571 if (z) { 572 b.resize(2); 573 x[1] = z; 574 } 575 576 i = b.size(); 577 } else { 578 k = lo0bits(&z); 579 x[0] = z; 580 i = 1; 581 b.resize(1); 582 k += 32; 583 } 584 if (de) { 585 *e = de - Bias - (P - 1) + k; 586 *bits = P - k; 587 } else { 588 *e = 0 - Bias - (P - 1) + 1 + k; 589 *bits = (32 * i) - hi0bits(x[i - 1]); 590 } 591} 592#undef d0 593#undef d1 594 595static const double tens[] = { 596 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 597 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 598 1e20, 1e21, 1e22 599}; 600 601static const double bigtens[] = { 1e16, 1e32, 1e64, 1e128, 1e256 }; 602 603#define Scale_Bit 0x10 604#define n_bigtens 5 605 606static ALWAYS_INLINE int quorem(BigInt& b, BigInt& S) 607{ 608 size_t n; 609 uint32_t* bx; 610 uint32_t* bxe; 611 uint32_t q; 612 uint32_t* sx; 613 uint32_t* sxe; 614#ifdef USE_LONG_LONG 615 unsigned long long borrow, carry, y, ys; 616#else 617 uint32_t borrow, carry, y, ys; 618 uint32_t si, z, zs; 619#endif 620 ASSERT(b.size() <= 1 || b.words()[b.size() - 1]); 621 ASSERT(S.size() <= 1 || S.words()[S.size() - 1]); 622 623 n = S.size(); 624 ASSERT_WITH_MESSAGE(b.size() <= n, "oversize b in quorem"); 625 if (b.size() < n) 626 return 0; 627 sx = S.words(); 628 sxe = sx + --n; 629 bx = b.words(); 630 bxe = bx + n; 631 q = *bxe / (*sxe + 1); /* ensure q <= true quotient */ 632 ASSERT_WITH_MESSAGE(q <= 9, "oversized quotient in quorem"); 633 if (q) { 634 borrow = 0; 635 carry = 0; 636 do { 637#ifdef USE_LONG_LONG 638 ys = *sx++ * (unsigned long long)q + carry; 639 carry = ys >> 32; 640 y = *bx - (ys & 0xffffffffUL) - borrow; 641 borrow = y >> 32 & (uint32_t)1; 642 *bx++ = (uint32_t)y & 0xffffffffUL; 643#else 644 si = *sx++; 645 ys = (si & 0xffff) * q + carry; 646 zs = (si >> 16) * q + (ys >> 16); 647 carry = zs >> 16; 648 y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 649 borrow = (y & 0x10000) >> 16; 650 z = (*bx >> 16) - (zs & 0xffff) - borrow; 651 borrow = (z & 0x10000) >> 16; 652 bx = storeInc(bx, z, y); 653#endif 654 } while (sx <= sxe); 655 if (!*bxe) { 656 bx = b.words(); 657 while (--bxe > bx && !*bxe) 658 --n; 659 b.resize(n); 660 } 661 } 662 if (cmp(b, S) >= 0) { 663 q++; 664 borrow = 0; 665 carry = 0; 666 bx = b.words(); 667 sx = S.words(); 668 do { 669#ifdef USE_LONG_LONG 670 ys = *sx++ + carry; 671 carry = ys >> 32; 672 y = *bx - (ys & 0xffffffffUL) - borrow; 673 borrow = y >> 32 & (uint32_t)1; 674 *bx++ = (uint32_t)y & 0xffffffffUL; 675#else 676 si = *sx++; 677 ys = (si & 0xffff) + carry; 678 zs = (si >> 16) + (ys >> 16); 679 carry = zs >> 16; 680 y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 681 borrow = (y & 0x10000) >> 16; 682 z = (*bx >> 16) - (zs & 0xffff) - borrow; 683 borrow = (z & 0x10000) >> 16; 684 bx = storeInc(bx, z, y); 685#endif 686 } while (sx <= sxe); 687 bx = b.words(); 688 bxe = bx + n; 689 if (!*bxe) { 690 while (--bxe > bx && !*bxe) 691 --n; 692 b.resize(n); 693 } 694 } 695 return q; 696} 697 698/* dtoa for IEEE arithmetic (dmg): convert double to ASCII string. 699 * 700 * Inspired by "How to Print Floating-Point Numbers Accurately" by 701 * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 112-126]. 702 * 703 * Modifications: 704 * 1. Rather than iterating, we use a simple numeric overestimate 705 * to determine k = floor(log10(d)). We scale relevant 706 * quantities using O(log2(k)) rather than O(k) multiplications. 707 * 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't 708 * try to generate digits strictly left to right. Instead, we 709 * compute with fewer bits and propagate the carry if necessary 710 * when rounding the final digit up. This is often faster. 711 * 3. Under the assumption that input will be rounded nearest, 712 * mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22. 713 * That is, we allow equality in stopping tests when the 714 * round-nearest rule will give the same floating-point value 715 * as would satisfaction of the stopping test with strict 716 * inequality. 717 * 4. We remove common factors of powers of 2 from relevant 718 * quantities. 719 * 5. When converting floating-point integers less than 1e16, 720 * we use floating-point arithmetic rather than resorting 721 * to multiple-precision integers. 722 * 6. When asked to produce fewer than 15 digits, we first try 723 * to get by with floating-point arithmetic; we resort to 724 * multiple-precision integer arithmetic only if we cannot 725 * guarantee that the floating-point calculation has given 726 * the correctly rounded result. For k requested digits and 727 * "uniformly" distributed input, the probability is 728 * something like 10^(k-15) that we must resort to the int32_t 729 * calculation. 730 * 731 * Note: 'leftright' translates to 'generate shortest possible string'. 732 */ 733template<bool roundingNone, bool roundingSignificantFigures, bool roundingDecimalPlaces, bool leftright> 734void dtoa(DtoaBuffer result, double dd, int ndigits, bool& signOut, int& exponentOut, unsigned& precisionOut) 735{ 736 // Exactly one rounding mode must be specified. 737 ASSERT(roundingNone + roundingSignificantFigures + roundingDecimalPlaces == 1); 738 // roundingNone only allowed (only sensible?) with leftright set. 739 ASSERT(!roundingNone || leftright); 740 741 ASSERT(std::isfinite(dd)); 742 743 int bbits, b2, b5, be, dig, i, ieps, ilim = 0, ilim0, ilim1 = 0, 744 j, j1, k, k0, k_check, m2, m5, s2, s5, 745 spec_case; 746 int32_t L; 747 int denorm; 748 uint32_t x; 749 BigInt b, delta, mlo, mhi, S; 750 U d2, eps, u; 751 double ds; 752 char* s; 753 char* s0; 754 755 u.d = dd; 756 757 /* Infinity or NaN */ 758 ASSERT((word0(&u) & Exp_mask) != Exp_mask); 759 760 // JavaScript toString conversion treats -0 as 0. 761 if (!dval(&u)) { 762 signOut = false; 763 exponentOut = 0; 764 precisionOut = 1; 765 result[0] = '0'; 766 result[1] = '\0'; 767 return; 768 } 769 770 if (word0(&u) & Sign_bit) { 771 signOut = true; 772 word0(&u) &= ~Sign_bit; // clear sign bit 773 } else 774 signOut = false; 775 776 d2b(b, &u, &be, &bbits); 777 if ((i = (int)(word0(&u) >> Exp_shift1 & (Exp_mask >> Exp_shift1)))) { 778 dval(&d2) = dval(&u); 779 word0(&d2) &= Frac_mask1; 780 word0(&d2) |= Exp_11; 781 782 /* log(x) ~=~ log(1.5) + (x-1.5)/1.5 783 * log10(x) = log(x) / log(10) 784 * ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10)) 785 * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2) 786 * 787 * This suggests computing an approximation k to log10(d) by 788 * 789 * k = (i - Bias)*0.301029995663981 790 * + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 ); 791 * 792 * We want k to be too large rather than too small. 793 * The error in the first-order Taylor series approximation 794 * is in our favor, so we just round up the constant enough 795 * to compensate for any error in the multiplication of 796 * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077, 797 * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14, 798 * adding 1e-13 to the constant term more than suffices. 799 * Hence we adjust the constant term to 0.1760912590558. 800 * (We could get a more accurate k by invoking log10, 801 * but this is probably not worthwhile.) 802 */ 803 804 i -= Bias; 805 denorm = 0; 806 } else { 807 /* d is denormalized */ 808 809 i = bbits + be + (Bias + (P - 1) - 1); 810 x = (i > 32) ? (word0(&u) << (64 - i)) | (word1(&u) >> (i - 32)) 811 : word1(&u) << (32 - i); 812 dval(&d2) = x; 813 word0(&d2) -= 31 * Exp_msk1; /* adjust exponent */ 814 i -= (Bias + (P - 1) - 1) + 1; 815 denorm = 1; 816 } 817 ds = (dval(&d2) - 1.5) * 0.289529654602168 + 0.1760912590558 + (i * 0.301029995663981); 818 k = (int)ds; 819 if (ds < 0. && ds != k) 820 k--; /* want k = floor(ds) */ 821 k_check = 1; 822 if (k >= 0 && k <= Ten_pmax) { 823 if (dval(&u) < tens[k]) 824 k--; 825 k_check = 0; 826 } 827 j = bbits - i - 1; 828 if (j >= 0) { 829 b2 = 0; 830 s2 = j; 831 } else { 832 b2 = -j; 833 s2 = 0; 834 } 835 if (k >= 0) { 836 b5 = 0; 837 s5 = k; 838 s2 += k; 839 } else { 840 b2 -= k; 841 b5 = -k; 842 s5 = 0; 843 } 844 845 if (roundingNone) { 846 ilim = ilim1 = -1; 847 i = 18; 848 ndigits = 0; 849 } 850 if (roundingSignificantFigures) { 851 if (ndigits <= 0) 852 ndigits = 1; 853 ilim = ilim1 = i = ndigits; 854 } 855 if (roundingDecimalPlaces) { 856 i = ndigits + k + 1; 857 ilim = i; 858 ilim1 = i - 1; 859 if (i <= 0) 860 i = 1; 861 } 862 863 s = s0 = result; 864 865 if (ilim >= 0 && ilim <= Quick_max) { 866 /* Try to get by with floating-point arithmetic. */ 867 868 i = 0; 869 dval(&d2) = dval(&u); 870 k0 = k; 871 ilim0 = ilim; 872 ieps = 2; /* conservative */ 873 if (k > 0) { 874 ds = tens[k & 0xf]; 875 j = k >> 4; 876 if (j & Bletch) { 877 /* prevent overflows */ 878 j &= Bletch - 1; 879 dval(&u) /= bigtens[n_bigtens - 1]; 880 ieps++; 881 } 882 for (; j; j >>= 1, i++) { 883 if (j & 1) { 884 ieps++; 885 ds *= bigtens[i]; 886 } 887 } 888 dval(&u) /= ds; 889 } else if ((j1 = -k)) { 890 dval(&u) *= tens[j1 & 0xf]; 891 for (j = j1 >> 4; j; j >>= 1, i++) { 892 if (j & 1) { 893 ieps++; 894 dval(&u) *= bigtens[i]; 895 } 896 } 897 } 898 if (k_check && dval(&u) < 1. && ilim > 0) { 899 if (ilim1 <= 0) 900 goto fastFailed; 901 ilim = ilim1; 902 k--; 903 dval(&u) *= 10.; 904 ieps++; 905 } 906 dval(&eps) = (ieps * dval(&u)) + 7.; 907 word0(&eps) -= (P - 1) * Exp_msk1; 908 if (!ilim) { 909 S.clear(); 910 mhi.clear(); 911 dval(&u) -= 5.; 912 if (dval(&u) > dval(&eps)) 913 goto oneDigit; 914 if (dval(&u) < -dval(&eps)) 915 goto noDigits; 916 goto fastFailed; 917 } 918 if (leftright) { 919 /* Use Steele & White method of only 920 * generating digits needed. 921 */ 922 dval(&eps) = (0.5 / tens[ilim - 1]) - dval(&eps); 923 for (i = 0;;) { 924 L = (long int)dval(&u); 925 dval(&u) -= L; 926 *s++ = '0' + (int)L; 927 if (dval(&u) < dval(&eps)) 928 goto ret; 929 if (1. - dval(&u) < dval(&eps)) 930 goto bumpUp; 931 if (++i >= ilim) 932 break; 933 dval(&eps) *= 10.; 934 dval(&u) *= 10.; 935 } 936 } else { 937 /* Generate ilim digits, then fix them up. */ 938 dval(&eps) *= tens[ilim - 1]; 939 for (i = 1;; i++, dval(&u) *= 10.) { 940 L = (int32_t)(dval(&u)); 941 if (!(dval(&u) -= L)) 942 ilim = i; 943 *s++ = '0' + (int)L; 944 if (i == ilim) { 945 if (dval(&u) > 0.5 + dval(&eps)) 946 goto bumpUp; 947 if (dval(&u) < 0.5 - dval(&eps)) { 948 while (*--s == '0') { } 949 s++; 950 goto ret; 951 } 952 break; 953 } 954 } 955 } 956fastFailed: 957 s = s0; 958 dval(&u) = dval(&d2); 959 k = k0; 960 ilim = ilim0; 961 } 962 963 /* Do we have a "small" integer? */ 964 965 if (be >= 0 && k <= Int_max) { 966 /* Yes. */ 967 ds = tens[k]; 968 if (ndigits < 0 && ilim <= 0) { 969 S.clear(); 970 mhi.clear(); 971 if (ilim < 0 || dval(&u) <= 5 * ds) 972 goto noDigits; 973 goto oneDigit; 974 } 975 for (i = 1;; i++, dval(&u) *= 10.) { 976 L = (int32_t)(dval(&u) / ds); 977 dval(&u) -= L * ds; 978 *s++ = '0' + (int)L; 979 if (!dval(&u)) { 980 break; 981 } 982 if (i == ilim) { 983 dval(&u) += dval(&u); 984 if (dval(&u) > ds || (dval(&u) == ds && (L & 1))) { 985bumpUp: 986 while (*--s == '9') 987 if (s == s0) { 988 k++; 989 *s = '0'; 990 break; 991 } 992 ++*s++; 993 } 994 break; 995 } 996 } 997 goto ret; 998 } 999 1000 m2 = b2; 1001 m5 = b5; 1002 mhi.clear(); 1003 mlo.clear(); 1004 if (leftright) { 1005 i = denorm ? be + (Bias + (P - 1) - 1 + 1) : 1 + P - bbits; 1006 b2 += i; 1007 s2 += i; 1008 i2b(mhi, 1); 1009 } 1010 if (m2 > 0 && s2 > 0) { 1011 i = m2 < s2 ? m2 : s2; 1012 b2 -= i; 1013 m2 -= i; 1014 s2 -= i; 1015 } 1016 if (b5 > 0) { 1017 if (leftright) { 1018 if (m5 > 0) { 1019 pow5mult(mhi, m5); 1020 mult(b, mhi); 1021 } 1022 if ((j = b5 - m5)) 1023 pow5mult(b, j); 1024 } else 1025 pow5mult(b, b5); 1026 } 1027 i2b(S, 1); 1028 if (s5 > 0) 1029 pow5mult(S, s5); 1030 1031 /* Check for special case that d is a normalized power of 2. */ 1032 1033 spec_case = 0; 1034 if ((roundingNone || leftright) && (!word1(&u) && !(word0(&u) & Bndry_mask) && word0(&u) & (Exp_mask & ~Exp_msk1))) { 1035 /* The special case */ 1036 b2 += Log2P; 1037 s2 += Log2P; 1038 spec_case = 1; 1039 } 1040 1041 /* Arrange for convenient computation of quotients: 1042 * shift left if necessary so divisor has 4 leading 0 bits. 1043 * 1044 * Perhaps we should just compute leading 28 bits of S once 1045 * and for all and pass them and a shift to quorem, so it 1046 * can do shifts and ors to compute the numerator for q. 1047 */ 1048 if ((i = ((s5 ? 32 - hi0bits(S.words()[S.size() - 1]) : 1) + s2) & 0x1f)) 1049 i = 32 - i; 1050 if (i > 4) { 1051 i -= 4; 1052 b2 += i; 1053 m2 += i; 1054 s2 += i; 1055 } else if (i < 4) { 1056 i += 28; 1057 b2 += i; 1058 m2 += i; 1059 s2 += i; 1060 } 1061 if (b2 > 0) 1062 lshift(b, b2); 1063 if (s2 > 0) 1064 lshift(S, s2); 1065 if (k_check) { 1066 if (cmp(b, S) < 0) { 1067 k--; 1068 multadd(b, 10, 0); /* we botched the k estimate */ 1069 if (leftright) 1070 multadd(mhi, 10, 0); 1071 ilim = ilim1; 1072 } 1073 } 1074 if (ilim <= 0 && roundingDecimalPlaces) { 1075 if (ilim < 0) 1076 goto noDigits; 1077 multadd(S, 5, 0); 1078 // For IEEE-754 unbiased rounding this check should be <=, such that 0.5 would flush to zero. 1079 if (cmp(b, S) < 0) 1080 goto noDigits; 1081 goto oneDigit; 1082 } 1083 if (leftright) { 1084 if (m2 > 0) 1085 lshift(mhi, m2); 1086 1087 /* Compute mlo -- check for special case 1088 * that d is a normalized power of 2. 1089 */ 1090 1091 mlo = mhi; 1092 if (spec_case) 1093 lshift(mhi, Log2P); 1094 1095 for (i = 1;;i++) { 1096 dig = quorem(b, S) + '0'; 1097 /* Do we yet have the shortest decimal string 1098 * that will round to d? 1099 */ 1100 j = cmp(b, mlo); 1101 diff(delta, S, mhi); 1102 j1 = delta.sign ? 1 : cmp(b, delta); 1103#ifdef DTOA_ROUND_BIASED 1104 if (j < 0 || !j) { 1105#else 1106 // FIXME: ECMA-262 specifies that equidistant results round away from 1107 // zero, which probably means we shouldn't be on the unbiased code path 1108 // (the (word1(&u) & 1) clause is looking highly suspicious). I haven't 1109 // yet understood this code well enough to make the call, but we should 1110 // probably be enabling DTOA_ROUND_BIASED. I think the interesting corner 1111 // case to understand is probably "Math.pow(0.5, 24).toString()". 1112 // I believe this value is interesting because I think it is precisely 1113 // representable in binary floating point, and its decimal representation 1114 // has a single digit that Steele & White reduction can remove, with the 1115 // value 5 (thus equidistant from the next numbers above and below). 1116 // We produce the correct answer using either codepath, and I don't as 1117 // yet understand why. :-) 1118 if (!j1 && !(word1(&u) & 1)) { 1119 if (dig == '9') 1120 goto round9up; 1121 if (j > 0) 1122 dig++; 1123 *s++ = dig; 1124 goto ret; 1125 } 1126 if (j < 0 || (!j && !(word1(&u) & 1))) { 1127#endif 1128 if ((b.words()[0] || b.size() > 1) && (j1 > 0)) { 1129 lshift(b, 1); 1130 j1 = cmp(b, S); 1131 // For IEEE-754 round-to-even, this check should be (j1 > 0 || (!j1 && (dig & 1))), 1132 // but ECMA-262 specifies that equidistant values (e.g. (.5).toFixed()) should 1133 // be rounded away from zero. 1134 if (j1 >= 0) { 1135 if (dig == '9') 1136 goto round9up; 1137 dig++; 1138 } 1139 } 1140 *s++ = dig; 1141 goto ret; 1142 } 1143 if (j1 > 0) { 1144 if (dig == '9') { /* possible if i == 1 */ 1145round9up: 1146 *s++ = '9'; 1147 goto roundoff; 1148 } 1149 *s++ = dig + 1; 1150 goto ret; 1151 } 1152 *s++ = dig; 1153 if (i == ilim) 1154 break; 1155 multadd(b, 10, 0); 1156 multadd(mlo, 10, 0); 1157 multadd(mhi, 10, 0); 1158 } 1159 } else { 1160 for (i = 1;; i++) { 1161 *s++ = dig = quorem(b, S) + '0'; 1162 if (!b.words()[0] && b.size() <= 1) 1163 goto ret; 1164 if (i >= ilim) 1165 break; 1166 multadd(b, 10, 0); 1167 } 1168 } 1169 1170 /* Round off last digit */ 1171 1172 lshift(b, 1); 1173 j = cmp(b, S); 1174 // For IEEE-754 round-to-even, this check should be (j > 0 || (!j && (dig & 1))), 1175 // but ECMA-262 specifies that equidistant values (e.g. (.5).toFixed()) should 1176 // be rounded away from zero. 1177 if (j >= 0) { 1178roundoff: 1179 while (*--s == '9') 1180 if (s == s0) { 1181 k++; 1182 *s++ = '1'; 1183 goto ret; 1184 } 1185 ++*s++; 1186 } else { 1187 while (*--s == '0') { } 1188 s++; 1189 } 1190 goto ret; 1191noDigits: 1192 exponentOut = 0; 1193 precisionOut = 1; 1194 result[0] = '0'; 1195 result[1] = '\0'; 1196 return; 1197oneDigit: 1198 *s++ = '1'; 1199 k++; 1200 goto ret; 1201ret: 1202 ASSERT(s > result); 1203 *s = 0; 1204 exponentOut = k; 1205 precisionOut = s - result; 1206} 1207 1208void dtoa(DtoaBuffer result, double dd, bool& sign, int& exponent, unsigned& precision) 1209{ 1210 // flags are roundingNone, leftright. 1211 dtoa<true, false, false, true>(result, dd, 0, sign, exponent, precision); 1212} 1213 1214void dtoaRoundSF(DtoaBuffer result, double dd, int ndigits, bool& sign, int& exponent, unsigned& precision) 1215{ 1216 // flag is roundingSignificantFigures. 1217 dtoa<false, true, false, false>(result, dd, ndigits, sign, exponent, precision); 1218} 1219 1220void dtoaRoundDP(DtoaBuffer result, double dd, int ndigits, bool& sign, int& exponent, unsigned& precision) 1221{ 1222 // flag is roundingDecimalPlaces. 1223 dtoa<false, false, true, false>(result, dd, ndigits, sign, exponent, precision); 1224} 1225 1226const char* numberToString(double d, NumberToStringBuffer buffer) 1227{ 1228 double_conversion::StringBuilder builder(buffer, NumberToStringBufferLength); 1229 const double_conversion::DoubleToStringConverter& converter = double_conversion::DoubleToStringConverter::EcmaScriptConverter(); 1230 converter.ToShortest(d, &builder); 1231 return builder.Finalize(); 1232} 1233 1234static inline const char* formatStringTruncatingTrailingZerosIfNeeded(NumberToStringBuffer buffer, double_conversion::StringBuilder& builder) 1235{ 1236 size_t length = builder.position(); 1237 size_t decimalPointPosition = 0; 1238 for (; decimalPointPosition < length; ++decimalPointPosition) { 1239 if (buffer[decimalPointPosition] == '.') 1240 break; 1241 } 1242 1243 // No decimal seperator found, early exit. 1244 if (decimalPointPosition == length) 1245 return builder.Finalize(); 1246 1247 size_t truncatedLength = length - 1; 1248 for (; truncatedLength > decimalPointPosition; --truncatedLength) { 1249 if (buffer[truncatedLength] != '0') 1250 break; 1251 } 1252 1253 // No trailing zeros found to strip. 1254 if (truncatedLength == length - 1) 1255 return builder.Finalize(); 1256 1257 // If we removed all trailing zeros, remove the decimal point as well. 1258 if (truncatedLength == decimalPointPosition) { 1259 ASSERT(truncatedLength > 0); 1260 --truncatedLength; 1261 } 1262 1263 // Truncate the StringBuilder, and return the final result. 1264 builder.SetPosition(truncatedLength + 1); 1265 return builder.Finalize(); 1266} 1267 1268const char* numberToFixedPrecisionString(double d, unsigned significantFigures, NumberToStringBuffer buffer, bool truncateTrailingZeros) 1269{ 1270 // Mimic String::format("%.[precision]g", ...), but use dtoas rounding facilities. 1271 // "g": Signed value printed in f or e format, whichever is more compact for the given value and precision. 1272 // The e format is used only when the exponent of the value is less than –4 or greater than or equal to the 1273 // precision argument. Trailing zeros are truncated, and the decimal point appears only if one or more digits follow it. 1274 // "precision": The precision specifies the maximum number of significant digits printed. 1275 double_conversion::StringBuilder builder(buffer, NumberToStringBufferLength); 1276 const double_conversion::DoubleToStringConverter& converter = double_conversion::DoubleToStringConverter::EcmaScriptConverter(); 1277 converter.ToPrecision(d, significantFigures, &builder); 1278 if (!truncateTrailingZeros) 1279 return builder.Finalize(); 1280 return formatStringTruncatingTrailingZerosIfNeeded(buffer, builder); 1281} 1282 1283const char* numberToFixedWidthString(double d, unsigned decimalPlaces, NumberToStringBuffer buffer) 1284{ 1285 // Mimic String::format("%.[precision]f", ...), but use dtoas rounding facilities. 1286 // "f": Signed value having the form [ – ]dddd.dddd, where dddd is one or more decimal digits. 1287 // The number of digits before the decimal point depends on the magnitude of the number, and 1288 // the number of digits after the decimal point depends on the requested precision. 1289 // "precision": The precision value specifies the number of digits after the decimal point. 1290 // If a decimal point appears, at least one digit appears before it. 1291 // The value is rounded to the appropriate number of digits. 1292 double_conversion::StringBuilder builder(buffer, NumberToStringBufferLength); 1293 const double_conversion::DoubleToStringConverter& converter = double_conversion::DoubleToStringConverter::EcmaScriptConverter(); 1294 converter.ToFixed(d, decimalPlaces, &builder); 1295 return builder.Finalize(); 1296} 1297 1298namespace Internal { 1299 1300double parseDoubleFromLongString(const UChar* string, size_t length, size_t& parsedLength) 1301{ 1302 Vector<LChar> conversionBuffer(length); 1303 for (size_t i = 0; i < length; ++i) 1304 conversionBuffer[i] = isASCII(string[i]) ? string[i] : 0; 1305 return parseDouble(conversionBuffer.data(), length, parsedLength); 1306} 1307 1308} // namespace Internal 1309 1310} // namespace WTF 1311