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