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