1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 *
3 * ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5 *
6 * The contents of this file are subject to the Mozilla Public License Version
7 * 1.1 (the "License"); you may not use this file except in compliance with
8 * the License. You may obtain a copy of the License at
9 * http://www.mozilla.org/MPL/
10 *
11 * Software distributed under the License is distributed on an "AS IS" basis,
12 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13 * for the specific language governing rights and limitations under the
14 * License.
15 *
16 * The Original Code is Mozilla Communicator client code, released
17 * March 31, 1998.
18 *
19 * The Initial Developer of the Original Code is
20 * Netscape Communications Corporation.
21 * Portions created by the Initial Developer are Copyright (C) 1998
22 * the Initial Developer. All Rights Reserved.
23 *
24 * Contributor(s):
25 *
26 * Alternatively, the contents of this file may be used under the terms of
27 * either of the GNU General Public License Version 2 or later (the "GPL"),
28 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29 * in which case the provisions of the GPL or the LGPL are applicable instead
30 * of those above. If you wish to allow use of your version of this file only
31 * under the terms of either the GPL or the LGPL, and not to allow others to
32 * use your version of this file under the terms of the MPL, indicate your
33 * decision by deleting the provisions above and replace them with the notice
34 * and other provisions required by the GPL or the LGPL. If you do not delete
35 * the provisions above, a recipient may use your version of this file under
36 * the terms of any one of the MPL, the GPL or the LGPL.
37 *
38 * ***** END LICENSE BLOCK ***** */
40 /*
41 * Portable double to alphanumeric string and back converters.
42 */
43 #include "jsstddef.h"
44 #include "jslibmath.h"
45 #include "jstypes.h"
46 #include "jsdtoa.h"
47 #include "jsprf.h"
48 #include "jsutil.h" /* Added by JSIFY */
49 #include "jspubtd.h"
50 #include "jsnum.h"
52 #ifdef JS_THREADSAFE
53 #include "prlock.h"
54 #endif
56 /****************************************************************
57 *
58 * The author of this software is David M. Gay.
59 *
60 * Copyright (c) 1991 by Lucent Technologies.
61 *
62 * Permission to use, copy, modify, and distribute this software for any
63 * purpose without fee is hereby granted, provided that this entire notice
64 * is included in all copies of any software which is or includes a copy
65 * or modification of this software and in all copies of the supporting
66 * documentation for such software.
67 *
68 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
69 * WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY
70 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
71 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
72 *
73 ***************************************************************/
75 /* Please send bug reports to
76 David M. Gay
77 Bell Laboratories, Room 2C-463
78 600 Mountain Avenue
79 Murray Hill, NJ 07974-0636
80 U.S.A.
81 dmg@bell-labs.com
82 */
84 /* On a machine with IEEE extended-precision registers, it is
85 * necessary to specify double-precision (53-bit) rounding precision
86 * before invoking strtod or dtoa. If the machine uses (the equivalent
87 * of) Intel 80x87 arithmetic, the call
88 * _control87(PC_53, MCW_PC);
89 * does this with many compilers. Whether this or another call is
90 * appropriate depends on the compiler; for this to work, it may be
91 * necessary to #include "float.h" or another system-dependent header
92 * file.
93 */
95 /* strtod for IEEE-arithmetic machines.
96 *
97 * This strtod returns a nearest machine number to the input decimal
98 * string (or sets err to JS_DTOA_ERANGE or JS_DTOA_ENOMEM). With IEEE
99 * arithmetic, ties are broken by the IEEE round-even rule. Otherwise
100 * ties are broken by biased rounding (add half and chop).
101 *
102 * Inspired loosely by William D. Clinger's paper "How to Read Floating
103 * Point Numbers Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101].
104 *
105 * Modifications:
106 *
107 * 1. We only require IEEE double-precision
108 * arithmetic (not IEEE double-extended).
109 * 2. We get by with floating-point arithmetic in a case that
110 * Clinger missed -- when we're computing d * 10^n
111 * for a small integer d and the integer n is not too
112 * much larger than 22 (the maximum integer k for which
113 * we can represent 10^k exactly), we may be able to
114 * compute (d*10^k) * 10^(e-k) with just one roundoff.
115 * 3. Rather than a bit-at-a-time adjustment of the binary
116 * result in the hard case, we use floating-point
117 * arithmetic to determine the adjustment to within
118 * one bit; only in really hard cases do we need to
119 * compute a second residual.
120 * 4. Because of 3., we don't need a large table of powers of 10
121 * for ten-to-e (just some small tables, e.g. of 10^k
122 * for 0 <= k <= 22).
123 */
125 /*
126 * #define IEEE_8087 for IEEE-arithmetic machines where the least
127 * significant byte has the lowest address.
128 * #define IEEE_MC68k for IEEE-arithmetic machines where the most
129 * significant byte has the lowest address.
130 * #define Long int on machines with 32-bit ints and 64-bit longs.
131 * #define Sudden_Underflow for IEEE-format machines without gradual
132 * underflow (i.e., that flush to zero on underflow).
133 * #define No_leftright to omit left-right logic in fast floating-point
134 * computation of js_dtoa.
135 * #define Check_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3.
136 * #define RND_PRODQUOT to use rnd_prod and rnd_quot (assembly routines
137 * that use extended-precision instructions to compute rounded
138 * products and quotients) with IBM.
139 * #define ROUND_BIASED for IEEE-format with biased rounding.
140 * #define Inaccurate_Divide for IEEE-format with correctly rounded
141 * products but inaccurate quotients, e.g., for Intel i860.
142 * #define JS_HAVE_LONG_LONG on machines that have a "long long"
143 * integer type (of >= 64 bits). If long long is available and the name is
144 * something other than "long long", #define Llong to be the name,
145 * and if "unsigned Llong" does not work as an unsigned version of
146 * Llong, #define #ULLong to be the corresponding unsigned type.
147 * #define Bad_float_h if your system lacks a float.h or if it does not
148 * define some or all of DBL_DIG, DBL_MAX_10_EXP, DBL_MAX_EXP,
149 * FLT_RADIX, FLT_ROUNDS, and DBL_MAX.
150 * #define MALLOC your_malloc, where your_malloc(n) acts like malloc(n)
151 * if memory is available and otherwise does something you deem
152 * appropriate. If MALLOC is undefined, malloc will be invoked
153 * directly -- and assumed always to succeed.
154 * #define Omit_Private_Memory to omit logic (added Jan. 1998) for making
155 * memory allocations from a private pool of memory when possible.
156 * When used, the private pool is PRIVATE_MEM bytes long: 2000 bytes,
157 * unless #defined to be a different length. This default length
158 * suffices to get rid of MALLOC calls except for unusual cases,
159 * such as decimal-to-binary conversion of a very long string of
160 * digits.
161 * #define INFNAN_CHECK on IEEE systems to cause strtod to check for
162 * Infinity and NaN (case insensitively). On some systems (e.g.,
163 * some HP systems), it may be necessary to #define NAN_WORD0
164 * appropriately -- to the most significant word of a quiet NaN.
165 * (On HP Series 700/800 machines, -DNAN_WORD0=0x7ff40000 works.)
166 * #define MULTIPLE_THREADS if the system offers preemptively scheduled
167 * multiple threads. In this case, you must provide (or suitably
168 * #define) two locks, acquired by ACQUIRE_DTOA_LOCK() and released
169 * by RELEASE_DTOA_LOCK(). (The second lock, accessed
170 * in pow5mult, ensures lazy evaluation of only one copy of high
171 * powers of 5; omitting this lock would introduce a small
172 * probability of wasting memory, but would otherwise be harmless.)
173 * You must also invoke freedtoa(s) to free the value s returned by
174 * dtoa. You may do so whether or not MULTIPLE_THREADS is #defined.
175 * #define NO_IEEE_Scale to disable new (Feb. 1997) logic in strtod that
176 * avoids underflows on inputs whose result does not underflow.
177 */
178 #ifdef IS_LITTLE_ENDIAN
179 #define IEEE_8087
180 #else
181 #define IEEE_MC68k
182 #endif
184 #ifndef Long
185 #define Long int32
186 #endif
188 #ifndef ULong
189 #define ULong uint32
190 #endif
192 #define Bug(errorMessageString) JS_ASSERT(!errorMessageString)
194 #include "stdlib.h"
195 #include "string.h"
197 #ifdef MALLOC
198 extern void *MALLOC(size_t);
199 #else
200 #define MALLOC malloc
201 #endif
203 #define Omit_Private_Memory
204 /* Private memory currently doesn't work with JS_THREADSAFE */
205 #ifndef Omit_Private_Memory
206 #ifndef PRIVATE_MEM
207 #define PRIVATE_MEM 2000
208 #endif
209 #define PRIVATE_mem ((PRIVATE_MEM+sizeof(double)-1)/sizeof(double))
210 static double private_mem[PRIVATE_mem], *pmem_next = private_mem;
211 #endif
213 #ifdef Bad_float_h
214 #undef __STDC__
216 #define DBL_DIG 15
217 #define DBL_MAX_10_EXP 308
218 #define DBL_MAX_EXP 1024
219 #define FLT_RADIX 2
220 #define FLT_ROUNDS 1
221 #define DBL_MAX 1.7976931348623157e+308
225 #ifndef LONG_MAX
226 #define LONG_MAX 2147483647
227 #endif
229 #else /* ifndef Bad_float_h */
230 #include "float.h"
231 #endif /* Bad_float_h */
233 #ifndef __MATH_H__
234 #include "math.h"
235 #endif
237 #ifndef CONST
238 #define CONST const
239 #endif
241 #if defined(IEEE_8087) + defined(IEEE_MC68k) != 1
242 Exactly one of IEEE_8087 or IEEE_MC68k should be defined.
243 #endif
245 #define word0(x) JSDOUBLE_HI32(x)
246 #define set_word0(x, y) JSDOUBLE_SET_HI32(x, y)
247 #define word1(x) JSDOUBLE_LO32(x)
248 #define set_word1(x, y) JSDOUBLE_SET_LO32(x, y)
250 #define Storeinc(a,b,c) (*(a)++ = (b) << 16 | (c) & 0xffff)
252 /* #define P DBL_MANT_DIG */
253 /* Ten_pmax = floor(P*log(2)/log(5)) */
254 /* Bletch = (highest power of 2 < DBL_MAX_10_EXP) / 16 */
255 /* Quick_max = floor((P-1)*log(FLT_RADIX)/log(10) - 1) */
256 /* Int_max = floor(P*log(FLT_RADIX)/log(10) - 1) */
258 #define Exp_shift 20
259 #define Exp_shift1 20
260 #define Exp_msk1 0x100000
261 #define Exp_msk11 0x100000
262 #define Exp_mask 0x7ff00000
263 #define P 53
264 #define Bias 1023
265 #define Emin (-1022)
266 #define Exp_1 0x3ff00000
267 #define Exp_11 0x3ff00000
268 #define Ebits 11
269 #define Frac_mask 0xfffff
270 #define Frac_mask1 0xfffff
271 #define Ten_pmax 22
272 #define Bletch 0x10
273 #define Bndry_mask 0xfffff
274 #define Bndry_mask1 0xfffff
275 #define LSB 1
276 #define Sign_bit 0x80000000
277 #define Log2P 1
278 #define Tiny0 0
279 #define Tiny1 1
280 #define Quick_max 14
281 #define Int_max 14
282 #define Infinite(x) (word0(x) == 0x7ff00000) /* sufficient test for here */
283 #ifndef NO_IEEE_Scale
284 #define Avoid_Underflow
285 #endif
289 #ifdef RND_PRODQUOT
290 #define rounded_product(a,b) a = rnd_prod(a, b)
291 #define rounded_quotient(a,b) a = rnd_quot(a, b)
292 extern double rnd_prod(double, double), rnd_quot(double, double);
293 #else
294 #define rounded_product(a,b) a *= b
295 #define rounded_quotient(a,b) a /= b
296 #endif
298 #define Big0 (Frac_mask1 | Exp_msk1*(DBL_MAX_EXP+Bias-1))
299 #define Big1 0xffffffff
301 #ifndef JS_HAVE_LONG_LONG
302 #undef ULLong
303 #else /* long long available */
304 #ifndef Llong
305 #define Llong JSInt64
306 #endif
307 #ifndef ULLong
308 #define ULLong JSUint64
309 #endif
310 #endif /* JS_HAVE_LONG_LONG */
312 #ifdef JS_THREADSAFE
313 #define MULTIPLE_THREADS
314 static PRLock *freelist_lock;
315 #define ACQUIRE_DTOA_LOCK() \
316 JS_BEGIN_MACRO \
317 if (!initialized) \
318 InitDtoa(); \
319 PR_Lock(freelist_lock); \
320 JS_END_MACRO
321 #define RELEASE_DTOA_LOCK() PR_Unlock(freelist_lock)
322 #else
323 #undef MULTIPLE_THREADS
324 #define ACQUIRE_DTOA_LOCK() /*nothing*/
325 #define RELEASE_DTOA_LOCK() /*nothing*/
326 #endif
328 #define Kmax 15
330 struct Bigint {
331 struct Bigint *next; /* Free list link */
332 int32 k; /* lg2(maxwds) */
333 int32 maxwds; /* Number of words allocated for x */
334 int32 sign; /* Zero if positive, 1 if negative. Ignored by most Bigint routines! */
335 int32 wds; /* Actual number of words. If value is nonzero, the most significant word must be nonzero. */
336 ULong x[1]; /* wds words of number in little endian order */
337 };
339 #ifdef ENABLE_OOM_TESTING
340 /* Out-of-memory testing. Use a good testcase (over and over) and then use
341 * these routines to cause a memory failure on every possible Balloc allocation,
342 * to make sure that all out-of-memory paths can be followed. See bug 14044.
343 */
345 static int allocationNum; /* which allocation is next? */
346 static int desiredFailure; /* which allocation should fail? */
348 /**
349 * js_BigintTestingReset
350 *
351 * Call at the beginning of a test run to set the allocation failure position.
352 * (Set to 0 to just have the engine count allocations without failing.)
353 */
354 JS_PUBLIC_API(void)
355 js_BigintTestingReset(int newFailure)
356 {
357 allocationNum = 0;
358 desiredFailure = newFailure;
359 }
361 /**
362 * js_BigintTestingWhere
363 *
364 * Report the current allocation position. This is really only useful when you
365 * want to learn how many allocations a test run has.
366 */
367 JS_PUBLIC_API(int)
368 js_BigintTestingWhere()
369 {
370 return allocationNum;
371 }
374 /*
375 * So here's what you do: Set up a fantastic test case that exercises the
376 * elements of the code you wish. Set the failure point at 0 and run the test,
377 * then get the allocation position. This number is the number of allocations
378 * your test makes. Now loop from 1 to that number, setting the failure point
379 * at each loop count, and run the test over and over, causing failures at each
380 * step. Any memory failure *should* cause a Out-Of-Memory exception; if it
381 * doesn't, then there's still an error here.
382 */
383 #endif
385 typedef struct Bigint Bigint;
387 static Bigint *freelist[Kmax+1];
389 /*
390 * Allocate a Bigint with 2^k words.
391 * This is not threadsafe. The caller must use thread locks
392 */
393 static Bigint *Balloc(int32 k)
394 {
395 int32 x;
396 Bigint *rv;
397 #ifndef Omit_Private_Memory
398 uint32 len;
399 #endif
401 #ifdef ENABLE_OOM_TESTING
402 if (++allocationNum == desiredFailure) {
403 printf("Forced Failing Allocation number %d\n", allocationNum);
404 return NULL;
405 }
406 #endif
408 if ((rv = freelist[k]) != NULL)
409 freelist[k] = rv->next;
410 if (rv == NULL) {
411 x = 1 << k;
412 #ifdef Omit_Private_Memory
413 rv = (Bigint *)MALLOC(sizeof(Bigint) + (x-1)*sizeof(ULong));
414 #else
415 len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
416 /sizeof(double);
417 if (pmem_next - private_mem + len <= PRIVATE_mem) {
418 rv = (Bigint*)pmem_next;
419 pmem_next += len;
420 }
421 else
422 rv = (Bigint*)MALLOC(len*sizeof(double));
423 #endif
424 if (!rv)
425 return NULL;
426 rv->k = k;
427 rv->maxwds = x;
428 }
429 rv->sign = rv->wds = 0;
430 return rv;
431 }
433 static void Bfree(Bigint *v)
434 {
435 if (v) {
436 v->next = freelist[v->k];
437 freelist[v->k] = v;
438 }
439 }
441 #define Bcopy(x,y) memcpy((char *)&x->sign, (char *)&y->sign, \
442 y->wds*sizeof(Long) + 2*sizeof(int32))
444 /* Return b*m + a. Deallocate the old b. Both a and m must be between 0 and
445 * 65535 inclusive. NOTE: old b is deallocated on memory failure.
446 */
447 static Bigint *multadd(Bigint *b, int32 m, int32 a)
448 {
449 int32 i, wds;
450 #ifdef ULLong
451 ULong *x;
452 ULLong carry, y;
453 #else
454 ULong carry, *x, y;
455 ULong xi, z;
456 #endif
457 Bigint *b1;
459 #ifdef ENABLE_OOM_TESTING
460 if (++allocationNum == desiredFailure) {
461 /* Faux allocation, because I'm not getting all of the failure paths
462 * without it.
463 */
464 printf("Forced Failing Allocation number %d\n", allocationNum);
465 Bfree(b);
466 return NULL;
467 }
468 #endif
470 wds = b->wds;
471 x = b->x;
472 i = 0;
473 carry = a;
474 do {
475 #ifdef ULLong
476 y = *x * (ULLong)m + carry;
477 carry = y >> 32;
478 *x++ = (ULong)(y & 0xffffffffUL);
479 #else
480 xi = *x;
481 y = (xi & 0xffff) * m + carry;
482 z = (xi >> 16) * m + (y >> 16);
483 carry = z >> 16;
484 *x++ = (z << 16) + (y & 0xffff);
485 #endif
486 }
487 while(++i < wds);
488 if (carry) {
489 if (wds >= b->maxwds) {
490 b1 = Balloc(b->k+1);
491 if (!b1) {
492 Bfree(b);
493 return NULL;
494 }
495 Bcopy(b1, b);
496 Bfree(b);
497 b = b1;
498 }
499 b->x[wds++] = (ULong)carry;
500 b->wds = wds;
501 }
502 return b;
503 }
505 static Bigint *s2b(CONST char *s, int32 nd0, int32 nd, ULong y9)
506 {
507 Bigint *b;
508 int32 i, k;
509 Long x, y;
511 x = (nd + 8) / 9;
512 for(k = 0, y = 1; x > y; y <<= 1, k++) ;
513 b = Balloc(k);
514 if (!b)
515 return NULL;
516 b->x[0] = y9;
517 b->wds = 1;
519 i = 9;
520 if (9 < nd0) {
521 s += 9;
522 do {
523 b = multadd(b, 10, *s++ - '0');
524 if (!b)
525 return NULL;
526 } while(++i < nd0);
527 s++;
528 }
529 else
530 s += 10;
531 for(; i < nd; i++) {
532 b = multadd(b, 10, *s++ - '0');
533 if (!b)
534 return NULL;
535 }
536 return b;
537 }
540 /* Return the number (0 through 32) of most significant zero bits in x. */
541 static int32 hi0bits(register ULong x)
542 {
543 register int32 k = 0;
545 if (!(x & 0xffff0000)) {
546 k = 16;
547 x <<= 16;
548 }
549 if (!(x & 0xff000000)) {
550 k += 8;
551 x <<= 8;
552 }
553 if (!(x & 0xf0000000)) {
554 k += 4;
555 x <<= 4;
556 }
557 if (!(x & 0xc0000000)) {
558 k += 2;
559 x <<= 2;
560 }
561 if (!(x & 0x80000000)) {
562 k++;
563 if (!(x & 0x40000000))
564 return 32;
565 }
566 return k;
567 }
570 /* Return the number (0 through 32) of least significant zero bits in y.
571 * Also shift y to the right past these 0 through 32 zeros so that y's
572 * least significant bit will be set unless y was originally zero. */
573 static int32 lo0bits(ULong *y)
574 {
575 register int32 k;
576 register ULong x = *y;
578 if (x & 7) {
579 if (x & 1)
580 return 0;
581 if (x & 2) {
582 *y = x >> 1;
583 return 1;
584 }
585 *y = x >> 2;
586 return 2;
587 }
588 k = 0;
589 if (!(x & 0xffff)) {
590 k = 16;
591 x >>= 16;
592 }
593 if (!(x & 0xff)) {
594 k += 8;
595 x >>= 8;
596 }
597 if (!(x & 0xf)) {
598 k += 4;
599 x >>= 4;
600 }
601 if (!(x & 0x3)) {
602 k += 2;
603 x >>= 2;
604 }
605 if (!(x & 1)) {
606 k++;
607 x >>= 1;
608 if (!x & 1)
609 return 32;
610 }
611 *y = x;
612 return k;
613 }
615 /* Return a new Bigint with the given integer value, which must be nonnegative. */
616 static Bigint *i2b(int32 i)
617 {
618 Bigint *b;
620 b = Balloc(1);
621 if (!b)
622 return NULL;
623 b->x[0] = i;
624 b->wds = 1;
625 return b;
626 }
628 /* Return a newly allocated product of a and b. */
629 static Bigint *mult(CONST Bigint *a, CONST Bigint *b)
630 {
631 CONST Bigint *t;
632 Bigint *c;
633 int32 k, wa, wb, wc;
634 ULong y;
635 ULong *xc, *xc0, *xce;
636 CONST ULong *x, *xa, *xae, *xb, *xbe;
637 #ifdef ULLong
638 ULLong carry, z;
639 #else
640 ULong carry, z;
641 ULong z2;
642 #endif
644 if (a->wds < b->wds) {
645 t = a;
646 a = b;
647 b = t;
648 }
649 k = a->k;
650 wa = a->wds;
651 wb = b->wds;
652 wc = wa + wb;
653 if (wc > a->maxwds)
654 k++;
655 c = Balloc(k);
656 if (!c)
657 return NULL;
658 for(xc = c->x, xce = xc + wc; xc < xce; xc++)
659 *xc = 0;
660 xa = a->x;
661 xae = xa + wa;
662 xb = b->x;
663 xbe = xb + wb;
664 xc0 = c->x;
665 #ifdef ULLong
666 for(; xb < xbe; xc0++) {
667 if ((y = *xb++) != 0) {
668 x = xa;
669 xc = xc0;
670 carry = 0;
671 do {
672 z = *x++ * (ULLong)y + *xc + carry;
673 carry = z >> 32;
674 *xc++ = (ULong)(z & 0xffffffffUL);
675 }
676 while(x < xae);
677 *xc = (ULong)carry;
678 }
679 }
680 #else
681 for(; xb < xbe; xb++, xc0++) {
682 if ((y = *xb & 0xffff) != 0) {
683 x = xa;
684 xc = xc0;
685 carry = 0;
686 do {
687 z = (*x & 0xffff) * y + (*xc & 0xffff) + carry;
688 carry = z >> 16;
689 z2 = (*x++ >> 16) * y + (*xc >> 16) + carry;
690 carry = z2 >> 16;
691 Storeinc(xc, z2, z);
692 }
693 while(x < xae);
694 *xc = carry;
695 }
696 if ((y = *xb >> 16) != 0) {
697 x = xa;
698 xc = xc0;
699 carry = 0;
700 z2 = *xc;
701 do {
702 z = (*x & 0xffff) * y + (*xc >> 16) + carry;
703 carry = z >> 16;
704 Storeinc(xc, z, z2);
705 z2 = (*x++ >> 16) * y + (*xc & 0xffff) + carry;
706 carry = z2 >> 16;
707 }
708 while(x < xae);
709 *xc = z2;
710 }
711 }
712 #endif
713 for(xc0 = c->x, xc = xc0 + wc; wc > 0 && !*--xc; --wc) ;
714 c->wds = wc;
715 return c;
716 }
718 /*
719 * 'p5s' points to a linked list of Bigints that are powers of 5.
720 * This list grows on demand, and it can only grow: it won't change
721 * in any other way. So if we read 'p5s' or the 'next' field of
722 * some Bigint on the list, and it is not NULL, we know it won't
723 * change to NULL or some other value. Only when the value of
724 * 'p5s' or 'next' is NULL do we need to acquire the lock and add
725 * a new Bigint to the list.
726 */
728 static Bigint *p5s;
730 #ifdef JS_THREADSAFE
731 static PRLock *p5s_lock;
732 #endif
734 /* Return b * 5^k. Deallocate the old b. k must be nonnegative. */
735 /* NOTE: old b is deallocated on memory failure. */
736 static Bigint *pow5mult(Bigint *b, int32 k)
737 {
738 Bigint *b1, *p5, *p51;
739 int32 i;
740 static CONST int32 p05[3] = { 5, 25, 125 };
742 if ((i = k & 3) != 0) {
743 b = multadd(b, p05[i-1], 0);
744 if (!b)
745 return NULL;
746 }
748 if (!(k >>= 2))
749 return b;
750 if (!(p5 = p5s)) {
751 #ifdef JS_THREADSAFE
752 /*
753 * We take great care to not call i2b() and Bfree()
754 * while holding the lock.
755 */
756 Bigint *wasted_effort = NULL;
757 p5 = i2b(625);
758 if (!p5) {
759 Bfree(b);
760 return NULL;
761 }
762 /* lock and check again */
763 PR_Lock(p5s_lock);
764 if (!p5s) {
765 /* first time */
766 p5s = p5;
767 p5->next = 0;
768 } else {
769 /* some other thread just beat us */
770 wasted_effort = p5;
771 p5 = p5s;
772 }
773 PR_Unlock(p5s_lock);
774 if (wasted_effort) {
775 Bfree(wasted_effort);
776 }
777 #else
778 /* first time */
779 p5 = p5s = i2b(625);
780 if (!p5) {
781 Bfree(b);
782 return NULL;
783 }
784 p5->next = 0;
785 #endif
786 }
787 for(;;) {
788 if (k & 1) {
789 b1 = mult(b, p5);
790 Bfree(b);
791 if (!b1)
792 return NULL;
793 b = b1;
794 }
795 if (!(k >>= 1))
796 break;
797 if (!(p51 = p5->next)) {
798 #ifdef JS_THREADSAFE
799 Bigint *wasted_effort = NULL;
800 p51 = mult(p5, p5);
801 if (!p51) {
802 Bfree(b);
803 return NULL;
804 }
805 PR_Lock(p5s_lock);
806 if (!p5->next) {
807 p5->next = p51;
808 p51->next = 0;
809 } else {
810 wasted_effort = p51;
811 p51 = p5->next;
812 }
813 PR_Unlock(p5s_lock);
814 if (wasted_effort) {
815 Bfree(wasted_effort);
816 }
817 #else
818 p51 = mult(p5,p5);
819 if (!p51) {
820 Bfree(b);
821 return NULL;
822 }
823 p51->next = 0;
824 p5->next = p51;
825 #endif
826 }
827 p5 = p51;
828 }
829 return b;
830 }
832 /* Return b * 2^k. Deallocate the old b. k must be nonnegative.
833 * NOTE: on memory failure, old b is deallocated. */
834 static Bigint *lshift(Bigint *b, int32 k)
835 {
836 int32 i, k1, n, n1;
837 Bigint *b1;
838 ULong *x, *x1, *xe, z;
840 n = k >> 5;
841 k1 = b->k;
842 n1 = n + b->wds + 1;
843 for(i = b->maxwds; n1 > i; i <<= 1)
844 k1++;
845 b1 = Balloc(k1);
846 if (!b1)
847 goto done;
848 x1 = b1->x;
849 for(i = 0; i < n; i++)
850 *x1++ = 0;
851 x = b->x;
852 xe = x + b->wds;
853 if (k &= 0x1f) {
854 k1 = 32 - k;
855 z = 0;
856 do {
857 *x1++ = *x << k | z;
858 z = *x++ >> k1;
859 }
860 while(x < xe);
861 if ((*x1 = z) != 0)
862 ++n1;
863 }
864 else do
865 *x1++ = *x++;
866 while(x < xe);
867 b1->wds = n1 - 1;
868 done:
869 Bfree(b);
870 return b1;
871 }
873 /* Return -1, 0, or 1 depending on whether a<b, a==b, or a>b, respectively. */
874 static int32 cmp(Bigint *a, Bigint *b)
875 {
876 ULong *xa, *xa0, *xb, *xb0;
877 int32 i, j;
879 i = a->wds;
880 j = b->wds;
881 #ifdef DEBUG
882 if (i > 1 && !a->x[i-1])
883 Bug("cmp called with a->x[a->wds-1] == 0");
884 if (j > 1 && !b->x[j-1])
885 Bug("cmp called with b->x[b->wds-1] == 0");
886 #endif
887 if (i -= j)
888 return i;
889 xa0 = a->x;
890 xa = xa0 + j;
891 xb0 = b->x;
892 xb = xb0 + j;
893 for(;;) {
894 if (*--xa != *--xb)
895 return *xa < *xb ? -1 : 1;
896 if (xa <= xa0)
897 break;
898 }
899 return 0;
900 }
902 static Bigint *diff(Bigint *a, Bigint *b)
903 {
904 Bigint *c;
905 int32 i, wa, wb;
906 ULong *xa, *xae, *xb, *xbe, *xc;
907 #ifdef ULLong
908 ULLong borrow, y;
909 #else
910 ULong borrow, y;
911 ULong z;
912 #endif
914 i = cmp(a,b);
915 if (!i) {
916 c = Balloc(0);
917 if (!c)
918 return NULL;
919 c->wds = 1;
920 c->x[0] = 0;
921 return c;
922 }
923 if (i < 0) {
924 c = a;
925 a = b;
926 b = c;
927 i = 1;
928 }
929 else
930 i = 0;
931 c = Balloc(a->k);
932 if (!c)
933 return NULL;
934 c->sign = i;
935 wa = a->wds;
936 xa = a->x;
937 xae = xa + wa;
938 wb = b->wds;
939 xb = b->x;
940 xbe = xb + wb;
941 xc = c->x;
942 borrow = 0;
943 #ifdef ULLong
944 do {
945 y = (ULLong)*xa++ - *xb++ - borrow;
946 borrow = y >> 32 & 1UL;
947 *xc++ = (ULong)(y & 0xffffffffUL);
948 }
949 while(xb < xbe);
950 while(xa < xae) {
951 y = *xa++ - borrow;
952 borrow = y >> 32 & 1UL;
953 *xc++ = (ULong)(y & 0xffffffffUL);
954 }
955 #else
956 do {
957 y = (*xa & 0xffff) - (*xb & 0xffff) - borrow;
958 borrow = (y & 0x10000) >> 16;
959 z = (*xa++ >> 16) - (*xb++ >> 16) - borrow;
960 borrow = (z & 0x10000) >> 16;
961 Storeinc(xc, z, y);
962 }
963 while(xb < xbe);
964 while(xa < xae) {
965 y = (*xa & 0xffff) - borrow;
966 borrow = (y & 0x10000) >> 16;
967 z = (*xa++ >> 16) - borrow;
968 borrow = (z & 0x10000) >> 16;
969 Storeinc(xc, z, y);
970 }
971 #endif
972 while(!*--xc)
973 wa--;
974 c->wds = wa;
975 return c;
976 }
978 /* Return the absolute difference between x and the adjacent greater-magnitude double number (ignoring exponent overflows). */
979 static double ulp(double x)
980 {
981 register Long L;
982 double a = 0;
984 L = (word0(x) & Exp_mask) - (P-1)*Exp_msk1;
985 #ifndef Sudden_Underflow
986 if (L > 0) {
987 #endif
988 set_word0(a, L);
989 set_word1(a, 0);
990 #ifndef Sudden_Underflow
991 }
992 else {
993 L = -L >> Exp_shift;
994 if (L < Exp_shift) {
995 set_word0(a, 0x80000 >> L);
996 set_word1(a, 0);
997 }
998 else {
999 set_word0(a, 0);
1000 L -= Exp_shift;
1001 set_word1(a, L >= 31 ? 1 : 1 << (31 - L));
1002 }
1003 }
1004 #endif
1005 return a;
1006 }
1009 static double b2d(Bigint *a, int32 *e)
1010 {
1011 ULong *xa, *xa0, w, y, z;
1012 int32 k;
1013 double d = 0;
1014 #define d0 word0(d)
1015 #define d1 word1(d)
1016 #define set_d0(x) set_word0(d, x)
1017 #define set_d1(x) set_word1(d, x)
1019 xa0 = a->x;
1020 xa = xa0 + a->wds;
1021 y = *--xa;
1022 #ifdef DEBUG
1023 if (!y) Bug("zero y in b2d");
1024 #endif
1025 k = hi0bits(y);
1026 *e = 32 - k;
1027 if (k < Ebits) {
1028 set_d0(Exp_1 | y >> (Ebits - k));
1029 w = xa > xa0 ? *--xa : 0;
1030 set_d1(y << (32-Ebits + k) | w >> (Ebits - k));
1031 goto ret_d;
1032 }
1033 z = xa > xa0 ? *--xa : 0;
1034 if (k -= Ebits) {
1035 set_d0(Exp_1 | y << k | z >> (32 - k));
1036 y = xa > xa0 ? *--xa : 0;
1037 set_d1(z << k | y >> (32 - k));
1038 }
1039 else {
1040 set_d0(Exp_1 | y);
1041 set_d1(z);
1042 }
1043 ret_d:
1044 #undef d0
1045 #undef d1
1046 #undef set_d0
1047 #undef set_d1
1048 return d;
1049 }
1052 /* Convert d into the form b*2^e, where b is an odd integer. b is the returned
1053 * Bigint and e is the returned binary exponent. Return the number of significant
1054 * bits in b in bits. d must be finite and nonzero. */
1055 static Bigint *d2b(double d, int32 *e, int32 *bits)
1056 {
1057 Bigint *b;
1058 int32 de, i, k;
1059 ULong *x, y, z;
1060 #define d0 word0(d)
1061 #define d1 word1(d)
1062 #define set_d0(x) set_word0(d, x)
1063 #define set_d1(x) set_word1(d, x)
1065 b = Balloc(1);
1066 if (!b)
1067 return NULL;
1068 x = b->x;
1070 z = d0 & Frac_mask;
1071 set_d0(d0 & 0x7fffffff); /* clear sign bit, which we ignore */
1072 #ifdef Sudden_Underflow
1073 de = (int32)(d0 >> Exp_shift);
1074 z |= Exp_msk11;
1075 #else
1076 if ((de = (int32)(d0 >> Exp_shift)) != 0)
1077 z |= Exp_msk1;
1078 #endif
1079 if ((y = d1) != 0) {
1080 if ((k = lo0bits(&y)) != 0) {
1081 x[0] = y | z << (32 - k);
1082 z >>= k;
1083 }
1084 else
1085 x[0] = y;
1086 i = b->wds = (x[1] = z) ? 2 : 1;
1087 }
1088 else {
1089 JS_ASSERT(z);
1090 k = lo0bits(&z);
1091 x[0] = z;
1092 i = b->wds = 1;
1093 k += 32;
1094 }
1095 #ifndef Sudden_Underflow
1096 if (de) {
1097 #endif
1098 *e = de - Bias - (P-1) + k;
1099 *bits = P - k;
1100 #ifndef Sudden_Underflow
1101 }
1102 else {
1103 *e = de - Bias - (P-1) + 1 + k;
1104 *bits = 32*i - hi0bits(x[i-1]);
1105 }
1106 #endif
1107 return b;
1108 }
1109 #undef d0
1110 #undef d1
1111 #undef set_d0
1112 #undef set_d1
1115 static double ratio(Bigint *a, Bigint *b)
1116 {
1117 double da, db;
1118 int32 k, ka, kb;
1120 da = b2d(a, &ka);
1121 db = b2d(b, &kb);
1122 k = ka - kb + 32*(a->wds - b->wds);
1123 if (k > 0)
1124 set_word0(da, word0(da) + k*Exp_msk1);
1125 else {
1126 k = -k;
1127 set_word0(db, word0(db) + k*Exp_msk1);
1128 }
1129 return da / db;
1130 }
1132 static CONST double
1133 tens[] = {
1134 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
1135 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
1136 1e20, 1e21, 1e22
1137 };
1139 static CONST double bigtens[] = { 1e16, 1e32, 1e64, 1e128, 1e256 };
1140 static CONST double tinytens[] = { 1e-16, 1e-32, 1e-64, 1e-128,
1141 #ifdef Avoid_Underflow
1142 9007199254740992.e-256
1143 #else
1144 1e-256
1145 #endif
1146 };
1147 /* The factor of 2^53 in tinytens[4] helps us avoid setting the underflow */
1148 /* flag unnecessarily. It leads to a song and dance at the end of strtod. */
1149 #define Scale_Bit 0x10
1150 #define n_bigtens 5
1153 #ifdef INFNAN_CHECK
1155 #ifndef NAN_WORD0
1156 #define NAN_WORD0 0x7ff80000
1157 #endif
1159 #ifndef NAN_WORD1
1160 #define NAN_WORD1 0
1161 #endif
1163 static int match(CONST char **sp, char *t)
1164 {
1165 int c, d;
1166 CONST char *s = *sp;
1168 while(d = *t++) {
1169 if ((c = *++s) >= 'A' && c <= 'Z')
1170 c += 'a' - 'A';
1171 if (c != d)
1172 return 0;
1173 }
1174 *sp = s + 1;
1175 return 1;
1176 }
1177 #endif /* INFNAN_CHECK */
1180 #ifdef JS_THREADSAFE
1181 static JSBool initialized = JS_FALSE;
1183 /* hacked replica of nspr _PR_InitDtoa */
1184 static void InitDtoa(void)
1185 {
1186 freelist_lock = PR_NewLock();
1187 p5s_lock = PR_NewLock();
1188 initialized = JS_TRUE;
1189 }
1190 #endif
1192 void js_FinishDtoa(void)
1193 {
1194 int count;
1195 Bigint *temp;
1197 #ifdef JS_THREADSAFE
1198 if (initialized == JS_TRUE) {
1199 PR_DestroyLock(freelist_lock);
1200 PR_DestroyLock(p5s_lock);
1201 initialized = JS_FALSE;
1202 }
1203 #endif
1205 /* clear down the freelist array and p5s */
1207 /* static Bigint *freelist[Kmax+1]; */
1208 for (count = 0; count <= Kmax; count++) {
1209 Bigint **listp = &freelist[count];
1210 while ((temp = *listp) != NULL) {
1211 *listp = temp->next;
1212 free(temp);
1213 }
1214 freelist[count] = NULL;
1215 }
1217 /* static Bigint *p5s; */
1218 while (p5s) {
1219 temp = p5s;
1220 p5s = p5s->next;
1221 free(temp);
1222 }
1223 }
1225 /* nspr2 watcom bug ifdef omitted */
1227 JS_FRIEND_API(double)
1228 JS_strtod(CONST char *s00, char **se, int *err)
1229 {
1230 int32 scale;
1231 int32 bb2, bb5, bbe, bd2, bd5, bbbits, bs2, c, dsign,
1232 e, e1, esign, i, j, k, nd, nd0, nf, nz, nz0, sign;
1233 CONST char *s, *s0, *s1;
1234 double aadj, aadj1, adj, rv, rv0;
1235 Long L;
1236 ULong y, z;
1237 Bigint *bb, *bb1, *bd, *bd0, *bs, *delta;
1239 *err = 0;
1241 bb = bd = bs = delta = NULL;
1242 sign = nz0 = nz = 0;
1243 rv = 0.;
1245 /* Locking for Balloc's shared buffers that will be used in this block */
1246 ACQUIRE_DTOA_LOCK();
1248 for(s = s00;;s++) switch(*s) {
1249 case '-':
1250 sign = 1;
1251 /* no break */
1252 case '+':
1253 if (*++s)
1254 goto break2;
1255 /* no break */
1256 case 0:
1257 s = s00;
1258 goto ret;
1259 case '\t':
1260 case '\n':
1261 case '\v':
1262 case '\f':
1263 case '\r':
1264 case ' ':
1265 continue;
1266 default:
1267 goto break2;
1268 }
1269 break2:
1271 if (*s == '0') {
1272 nz0 = 1;
1273 while(*++s == '0') ;
1274 if (!*s)
1275 goto ret;
1276 }
1277 s0 = s;
1278 y = z = 0;
1279 for(nd = nf = 0; (c = *s) >= '0' && c <= '9'; nd++, s++)
1280 if (nd < 9)
1281 y = 10*y + c - '0';
1282 else if (nd < 16)
1283 z = 10*z + c - '0';
1284 nd0 = nd;
1285 if (c == '.') {
1286 c = *++s;
1287 if (!nd) {
1288 for(; c == '0'; c = *++s)
1289 nz++;
1290 if (c > '0' && c <= '9') {
1291 s0 = s;
1292 nf += nz;
1293 nz = 0;
1294 goto have_dig;
1295 }
1296 goto dig_done;
1297 }
1298 for(; c >= '0' && c <= '9'; c = *++s) {
1299 have_dig:
1300 nz++;
1301 if (c -= '0') {
1302 nf += nz;
1303 for(i = 1; i < nz; i++)
1304 if (nd++ < 9)
1305 y *= 10;
1306 else if (nd <= DBL_DIG + 1)
1307 z *= 10;
1308 if (nd++ < 9)
1309 y = 10*y + c;
1310 else if (nd <= DBL_DIG + 1)
1311 z = 10*z + c;
1312 nz = 0;
1313 }
1314 }
1315 }
1316 dig_done:
1317 e = 0;
1318 if (c == 'e' || c == 'E') {
1319 if (!nd && !nz && !nz0) {
1320 s = s00;
1321 goto ret;
1322 }
1323 s00 = s;
1324 esign = 0;
1325 switch(c = *++s) {
1326 case '-':
1327 esign = 1;
1328 case '+':
1329 c = *++s;
1330 }
1331 if (c >= '0' && c <= '9') {
1332 while(c == '0')
1333 c = *++s;
1334 if (c > '0' && c <= '9') {
1335 L = c - '0';
1336 s1 = s;
1337 while((c = *++s) >= '0' && c <= '9')
1338 L = 10*L + c - '0';
1339 if (s - s1 > 8 || L > 19999)
1340 /* Avoid confusion from exponents
1341 * so large that e might overflow.
1342 */
1343 e = 19999; /* safe for 16 bit ints */
1344 else
1345 e = (int32)L;
1346 if (esign)
1347 e = -e;
1348 }
1349 else
1350 e = 0;
1351 }
1352 else
1353 s = s00;
1354 }
1355 if (!nd) {
1356 if (!nz && !nz0) {
1357 #ifdef INFNAN_CHECK
1358 /* Check for Nan and Infinity */
1359 switch(c) {
1360 case 'i':
1361 case 'I':
1362 if (match(&s,"nfinity")) {
1363 word0(rv) = 0x7ff00000;
1364 word1(rv) = 0;
1365 goto ret;
1366 }
1367 break;
1368 case 'n':
1369 case 'N':
1370 if (match(&s, "an")) {
1371 word0(rv) = NAN_WORD0;
1372 word1(rv) = NAN_WORD1;
1373 goto ret;
1374 }
1375 }
1376 #endif /* INFNAN_CHECK */
1377 s = s00;
1378 }
1379 goto ret;
1380 }
1381 e1 = e -= nf;
1383 /* Now we have nd0 digits, starting at s0, followed by a
1384 * decimal point, followed by nd-nd0 digits. The number we're
1385 * after is the integer represented by those digits times
1386 * 10**e */
1388 if (!nd0)
1389 nd0 = nd;
1390 k = nd < DBL_DIG + 1 ? nd : DBL_DIG + 1;
1391 rv = y;
1392 if (k > 9)
1393 rv = tens[k - 9] * rv + z;
1394 bd0 = 0;
1395 if (nd <= DBL_DIG
1396 #ifndef RND_PRODQUOT
1397 && FLT_ROUNDS == 1
1398 #endif
1399 ) {
1400 if (!e)
1401 goto ret;
1402 if (e > 0) {
1403 if (e <= Ten_pmax) {
1404 /* rv = */ rounded_product(rv, tens[e]);
1405 goto ret;
1406 }
1407 i = DBL_DIG - nd;
1408 if (e <= Ten_pmax + i) {
1409 /* A fancier test would sometimes let us do
1410 * this for larger i values.
1411 */
1412 e -= i;
1413 rv *= tens[i];
1414 /* rv = */ rounded_product(rv, tens[e]);
1415 goto ret;
1416 }
1417 }
1418 #ifndef Inaccurate_Divide
1419 else if (e >= -Ten_pmax) {
1420 /* rv = */ rounded_quotient(rv, tens[-e]);
1421 goto ret;
1422 }
1423 #endif
1424 }
1425 e1 += nd - k;
1427 scale = 0;
1429 /* Get starting approximation = rv * 10**e1 */
1431 if (e1 > 0) {
1432 if ((i = e1 & 15) != 0)
1433 rv *= tens[i];
1434 if (e1 &= ~15) {
1435 if (e1 > DBL_MAX_10_EXP) {
1436 ovfl:
1437 *err = JS_DTOA_ERANGE;
1438 #ifdef __STDC__
1439 rv = HUGE_VAL;
1440 #else
1441 /* Can't trust HUGE_VAL */
1442 word0(rv) = Exp_mask;
1443 word1(rv) = 0;
1444 #endif
1445 if (bd0)
1446 goto retfree;
1447 goto ret;
1448 }
1449 e1 >>= 4;
1450 for(j = 0; e1 > 1; j++, e1 >>= 1)
1451 if (e1 & 1)
1452 rv *= bigtens[j];
1453 /* The last multiplication could overflow. */
1454 set_word0(rv, word0(rv) - P*Exp_msk1);
1455 rv *= bigtens[j];
1456 if ((z = word0(rv) & Exp_mask) > Exp_msk1*(DBL_MAX_EXP+Bias-P))
1457 goto ovfl;
1458 if (z > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) {
1459 /* set to largest number */
1460 /* (Can't trust DBL_MAX) */
1461 set_word0(rv, Big0);
1462 set_word1(rv, Big1);
1463 }
1464 else
1465 set_word0(rv, word0(rv) + P*Exp_msk1);
1466 }
1467 }
1468 else if (e1 < 0) {
1469 e1 = -e1;
1470 if ((i = e1 & 15) != 0)
1471 rv /= tens[i];
1472 if (e1 &= ~15) {
1473 e1 >>= 4;
1474 if (e1 >= 1 << n_bigtens)
1475 goto undfl;
1476 #ifdef Avoid_Underflow
1477 if (e1 & Scale_Bit)
1478 scale = P;
1479 for(j = 0; e1 > 0; j++, e1 >>= 1)
1480 if (e1 & 1)
1481 rv *= tinytens[j];
1482 if (scale && (j = P + 1 - ((word0(rv) & Exp_mask)
1483 >> Exp_shift)) > 0) {
1484 /* scaled rv is denormal; zap j low bits */
1485 if (j >= 32) {
1486 set_word1(rv, 0);
1487 set_word0(rv, word0(rv) & (0xffffffff << (j-32)));
1488 if (!word0(rv))
1489 set_word0(rv, 1);
1490 }
1491 else
1492 set_word1(rv, word1(rv) & (0xffffffff << j));
1493 }
1494 #else
1495 for(j = 0; e1 > 1; j++, e1 >>= 1)
1496 if (e1 & 1)
1497 rv *= tinytens[j];
1498 /* The last multiplication could underflow. */
1499 rv0 = rv;
1500 rv *= tinytens[j];
1501 if (!rv) {
1502 rv = 2.*rv0;
1503 rv *= tinytens[j];
1504 #endif
1505 if (!rv) {
1506 undfl:
1507 rv = 0.;
1508 *err = JS_DTOA_ERANGE;
1509 if (bd0)
1510 goto retfree;
1511 goto ret;
1512 }
1513 #ifndef Avoid_Underflow
1514 set_word0(rv, Tiny0);
1515 set_word1(rv, Tiny1);
1516 /* The refinement below will clean
1517 * this approximation up.
1518 */
1519 }
1520 #endif
1521 }
1522 }
1524 /* Now the hard part -- adjusting rv to the correct value.*/
1526 /* Put digits into bd: true value = bd * 10^e */
1528 bd0 = s2b(s0, nd0, nd, y);
1529 if (!bd0)
1530 goto nomem;
1532 for(;;) {
1533 bd = Balloc(bd0->k);
1534 if (!bd)
1535 goto nomem;
1536 Bcopy(bd, bd0);
1537 bb = d2b(rv, &bbe, &bbbits); /* rv = bb * 2^bbe */
1538 if (!bb)
1539 goto nomem;
1540 bs = i2b(1);
1541 if (!bs)
1542 goto nomem;
1544 if (e >= 0) {
1545 bb2 = bb5 = 0;
1546 bd2 = bd5 = e;
1547 }
1548 else {
1549 bb2 = bb5 = -e;
1550 bd2 = bd5 = 0;
1551 }
1552 if (bbe >= 0)
1553 bb2 += bbe;
1554 else
1555 bd2 -= bbe;
1556 bs2 = bb2;
1557 #ifdef Sudden_Underflow
1558 j = P + 1 - bbbits;
1559 #else
1560 #ifdef Avoid_Underflow
1561 j = bbe - scale;
1562 #else
1563 j = bbe;
1564 #endif
1565 i = j + bbbits - 1; /* logb(rv) */
1566 if (i < Emin) /* denormal */
1567 j += P - Emin;
1568 else
1569 j = P + 1 - bbbits;
1570 #endif
1571 bb2 += j;
1572 bd2 += j;
1573 #ifdef Avoid_Underflow
1574 bd2 += scale;
1575 #endif
1576 i = bb2 < bd2 ? bb2 : bd2;
1577 if (i > bs2)
1578 i = bs2;
1579 if (i > 0) {
1580 bb2 -= i;
1581 bd2 -= i;
1582 bs2 -= i;
1583 }
1584 if (bb5 > 0) {
1585 bs = pow5mult(bs, bb5);
1586 if (!bs)
1587 goto nomem;
1588 bb1 = mult(bs, bb);
1589 if (!bb1)
1590 goto nomem;
1591 Bfree(bb);
1592 bb = bb1;
1593 }
1594 if (bb2 > 0) {
1595 bb = lshift(bb, bb2);
1596 if (!bb)
1597 goto nomem;
1598 }
1599 if (bd5 > 0) {
1600 bd = pow5mult(bd, bd5);
1601 if (!bd)
1602 goto nomem;
1603 }
1604 if (bd2 > 0) {
1605 bd = lshift(bd, bd2);
1606 if (!bd)
1607 goto nomem;
1608 }
1609 if (bs2 > 0) {
1610 bs = lshift(bs, bs2);
1611 if (!bs)
1612 goto nomem;
1613 }
1614 delta = diff(bb, bd);
1615 if (!delta)
1616 goto nomem;
1617 dsign = delta->sign;
1618 delta->sign = 0;
1619 i = cmp(delta, bs);
1620 if (i < 0) {
1621 /* Error is less than half an ulp -- check for
1622 * special case of mantissa a power of two.
1623 */
1624 if (dsign || word1(rv) || word0(rv) & Bndry_mask
1625 #ifdef Avoid_Underflow
1626 || (word0(rv) & Exp_mask) <= Exp_msk1 + P*Exp_msk1
1627 #else
1628 || (word0(rv) & Exp_mask) <= Exp_msk1
1629 #endif
1630 ) {
1631 #ifdef Avoid_Underflow
1632 if (!delta->x[0] && delta->wds == 1)
1633 dsign = 2;
1634 #endif
1635 break;
1636 }
1637 delta = lshift(delta,Log2P);
1638 if (!delta)
1639 goto nomem;
1640 if (cmp(delta, bs) > 0)
1641 goto drop_down;
1642 break;
1643 }
1644 if (i == 0) {
1645 /* exactly half-way between */
1646 if (dsign) {
1647 if ((word0(rv) & Bndry_mask1) == Bndry_mask1
1648 && word1(rv) == 0xffffffff) {
1649 /*boundary case -- increment exponent*/
1650 set_word0(rv, (word0(rv) & Exp_mask) + Exp_msk1);
1651 set_word1(rv, 0);
1652 #ifdef Avoid_Underflow
1653 dsign = 0;
1654 #endif
1655 break;
1656 }
1657 }
1658 else if (!(word0(rv) & Bndry_mask) && !word1(rv)) {
1659 #ifdef Avoid_Underflow
1660 dsign = 2;
1661 #endif
1662 drop_down:
1663 /* boundary case -- decrement exponent */
1664 #ifdef Sudden_Underflow
1665 L = word0(rv) & Exp_mask;
1666 if (L <= Exp_msk1)
1667 goto undfl;
1668 L -= Exp_msk1;
1669 #else
1670 L = (word0(rv) & Exp_mask) - Exp_msk1;
1671 #endif
1672 set_word0(rv, L | Bndry_mask1);
1673 set_word1(rv, 0xffffffff);
1674 break;
1675 }
1676 #ifndef ROUND_BIASED
1677 if (!(word1(rv) & LSB))
1678 break;
1679 #endif
1680 if (dsign)
1681 rv += ulp(rv);
1682 #ifndef ROUND_BIASED
1683 else {
1684 rv -= ulp(rv);
1685 #ifndef Sudden_Underflow
1686 if (!rv)
1687 goto undfl;
1688 #endif
1689 }
1690 #ifdef Avoid_Underflow
1691 dsign = 1 - dsign;
1692 #endif
1693 #endif
1694 break;
1695 }
1696 if ((aadj = ratio(delta, bs)) <= 2.) {
1697 if (dsign)
1698 aadj = aadj1 = 1.;
1699 else if (word1(rv) || word0(rv) & Bndry_mask) {
1700 #ifndef Sudden_Underflow
1701 if (word1(rv) == Tiny1 && !word0(rv))
1702 goto undfl;
1703 #endif
1704 aadj = 1.;
1705 aadj1 = -1.;
1706 }
1707 else {
1708 /* special case -- power of FLT_RADIX to be */
1709 /* rounded down... */
1711 if (aadj < 2./FLT_RADIX)
1712 aadj = 1./FLT_RADIX;
1713 else
1714 aadj *= 0.5;
1715 aadj1 = -aadj;
1716 }
1717 }
1718 else {
1719 aadj *= 0.5;
1720 aadj1 = dsign ? aadj : -aadj;
1721 #ifdef Check_FLT_ROUNDS
1722 switch(FLT_ROUNDS) {
1723 case 2: /* towards +infinity */
1724 aadj1 -= 0.5;
1725 break;
1726 case 0: /* towards 0 */
1727 case 3: /* towards -infinity */
1728 aadj1 += 0.5;
1729 }
1730 #else
1731 if (FLT_ROUNDS == 0)
1732 aadj1 += 0.5;
1733 #endif
1734 }
1735 y = word0(rv) & Exp_mask;
1737 /* Check for overflow */
1739 if (y == Exp_msk1*(DBL_MAX_EXP+Bias-1)) {
1740 rv0 = rv;
1741 set_word0(rv, word0(rv) - P*Exp_msk1);
1742 adj = aadj1 * ulp(rv);
1743 rv += adj;
1744 if ((word0(rv) & Exp_mask) >=
1745 Exp_msk1*(DBL_MAX_EXP+Bias-P)) {
1746 if (word0(rv0) == Big0 && word1(rv0) == Big1)
1747 goto ovfl;
1748 set_word0(rv, Big0);
1749 set_word1(rv, Big1);
1750 goto cont;
1751 }
1752 else
1753 set_word0(rv, word0(rv) + P*Exp_msk1);
1754 }
1755 else {
1756 #ifdef Sudden_Underflow
1757 if ((word0(rv) & Exp_mask) <= P*Exp_msk1) {
1758 rv0 = rv;
1759 set_word0(rv, word0(rv) + P*Exp_msk1);
1760 adj = aadj1 * ulp(rv);
1761 rv += adj;
1762 if ((word0(rv) & Exp_mask) <= P*Exp_msk1)
1763 {
1764 if (word0(rv0) == Tiny0
1765 && word1(rv0) == Tiny1)
1766 goto undfl;
1767 set_word0(rv, Tiny0);
1768 set_word1(rv, Tiny1);
1769 goto cont;
1770 }
1771 else
1772 set_word0(rv, word0(rv) - P*Exp_msk1);
1773 }
1774 else {
1775 adj = aadj1 * ulp(rv);
1776 rv += adj;
1777 }
1778 #else
1779 /* Compute adj so that the IEEE rounding rules will
1780 * correctly round rv + adj in some half-way cases.
1781 * If rv * ulp(rv) is denormalized (i.e.,
1782 * y <= (P-1)*Exp_msk1), we must adjust aadj to avoid
1783 * trouble from bits lost to denormalization;
1784 * example: 1.2e-307 .
1785 */
1786 #ifdef Avoid_Underflow
1787 if (y <= P*Exp_msk1 && aadj > 1.)
1788 #else
1789 if (y <= (P-1)*Exp_msk1 && aadj > 1.)
1790 #endif
1791 {
1792 aadj1 = (double)(int32)(aadj + 0.5);
1793 if (!dsign)
1794 aadj1 = -aadj1;
1795 }
1796 #ifdef Avoid_Underflow
1797 if (scale && y <= P*Exp_msk1)
1798 set_word0(aadj1, word0(aadj1) + (P+1)*Exp_msk1 - y);
1799 #endif
1800 adj = aadj1 * ulp(rv);
1801 rv += adj;
1802 #endif
1803 }
1804 z = word0(rv) & Exp_mask;
1805 #ifdef Avoid_Underflow
1806 if (!scale)
1807 #endif
1808 if (y == z) {
1809 /* Can we stop now? */
1810 L = (Long)aadj;
1811 aadj -= L;
1812 /* The tolerances below are conservative. */
1813 if (dsign || word1(rv) || word0(rv) & Bndry_mask) {
1814 if (aadj < .4999999 || aadj > .5000001)
1815 break;
1816 }
1817 else if (aadj < .4999999/FLT_RADIX)
1818 break;
1819 }
1820 cont:
1821 Bfree(bb);
1822 Bfree(bd);
1823 Bfree(bs);
1824 Bfree(delta);
1825 bb = bd = bs = delta = NULL;
1826 }
1827 #ifdef Avoid_Underflow
1828 if (scale) {
1829 set_word0(rv0, Exp_1 - P*Exp_msk1);
1830 set_word1(rv0, 0);
1831 if ((word0(rv) & Exp_mask) <= P*Exp_msk1
1832 && word1(rv) & 1
1833 && dsign != 2) {
1834 if (dsign) {
1835 #ifdef Sudden_Underflow
1836 /* rv will be 0, but this would give the */
1837 /* right result if only rv *= rv0 worked. */
1838 set_word0(rv, word0(rv) + P*Exp_msk1);
1839 set_word0(rv0, Exp_1 - 2*P*Exp_msk1);
1840 #endif
1841 rv += ulp(rv);
1842 }
1843 else
1844 set_word1(rv, word1(rv) & ~1);
1845 }
1846 rv *= rv0;
1847 }
1848 #endif /* Avoid_Underflow */
1849 retfree:
1850 Bfree(bb);
1851 Bfree(bd);
1852 Bfree(bs);
1853 Bfree(bd0);
1854 Bfree(delta);
1855 ret:
1856 RELEASE_DTOA_LOCK();
1857 if (se)
1858 *se = (char *)s;
1859 return sign ? -rv : rv;
1861 nomem:
1862 Bfree(bb);
1863 Bfree(bd);
1864 Bfree(bs);
1865 Bfree(bd0);
1866 Bfree(delta);
1867 *err = JS_DTOA_ENOMEM;
1868 return 0;
1869 }
1872 /* Return floor(b/2^k) and set b to be the remainder. The returned quotient must be less than 2^32. */
1873 static uint32 quorem2(Bigint *b, int32 k)
1874 {
1875 ULong mask;
1876 ULong result;
1877 ULong *bx, *bxe;
1878 int32 w;
1879 int32 n = k >> 5;
1880 k &= 0x1F;
1881 mask = (1<<k) - 1;
1883 w = b->wds - n;
1884 if (w <= 0)
1885 return 0;
1886 JS_ASSERT(w <= 2);
1887 bx = b->x;
1888 bxe = bx + n;
1889 result = *bxe >> k;
1890 *bxe &= mask;
1891 if (w == 2) {
1892 JS_ASSERT(!(bxe[1] & ~mask));
1893 if (k)
1894 result |= bxe[1] << (32 - k);
1895 }
1896 n++;
1897 while (!*bxe && bxe != bx) {
1898 n--;
1899 bxe--;
1900 }
1901 b->wds = n;
1902 return result;
1903 }
1905 /* Return floor(b/S) and set b to be the remainder. As added restrictions, b must not have
1906 * more words than S, the most significant word of S must not start with a 1 bit, and the
1907 * returned quotient must be less than 36. */
1908 static int32 quorem(Bigint *b, Bigint *S)
1909 {
1910 int32 n;
1911 ULong *bx, *bxe, q, *sx, *sxe;
1912 #ifdef ULLong
1913 ULLong borrow, carry, y, ys;
1914 #else
1915 ULong borrow, carry, y, ys;
1916 ULong si, z, zs;
1917 #endif
1919 n = S->wds;
1920 JS_ASSERT(b->wds <= n);
1921 if (b->wds < n)
1922 return 0;
1923 sx = S->x;
1924 sxe = sx + --n;
1925 bx = b->x;
1926 bxe = bx + n;
1927 JS_ASSERT(*sxe <= 0x7FFFFFFF);
1928 q = *bxe / (*sxe + 1); /* ensure q <= true quotient */
1929 JS_ASSERT(q < 36);
1930 if (q) {
1931 borrow = 0;
1932 carry = 0;
1933 do {
1934 #ifdef ULLong
1935 ys = *sx++ * (ULLong)q + carry;
1936 carry = ys >> 32;
1937 y = *bx - (ys & 0xffffffffUL) - borrow;
1938 borrow = y >> 32 & 1UL;
1939 *bx++ = (ULong)(y & 0xffffffffUL);
1940 #else
1941 si = *sx++;
1942 ys = (si & 0xffff) * q + carry;
1943 zs = (si >> 16) * q + (ys >> 16);
1944 carry = zs >> 16;
1945 y = (*bx & 0xffff) - (ys & 0xffff) - borrow;
1946 borrow = (y & 0x10000) >> 16;
1947 z = (*bx >> 16) - (zs & 0xffff) - borrow;
1948 borrow = (z & 0x10000) >> 16;
1949 Storeinc(bx, z, y);
1950 #endif
1951 }
1952 while(sx <= sxe);
1953 if (!*bxe) {
1954 bx = b->x;
1955 while(--bxe > bx && !*bxe)
1956 --n;
1957 b->wds = n;
1958 }
1959 }
1960 if (cmp(b, S) >= 0) {
1961 q++;
1962 borrow = 0;
1963 carry = 0;
1964 bx = b->x;
1965 sx = S->x;
1966 do {
1967 #ifdef ULLong
1968 ys = *sx++ + carry;
1969 carry = ys >> 32;
1970 y = *bx - (ys & 0xffffffffUL) - borrow;
1971 borrow = y >> 32 & 1UL;
1972 *bx++ = (ULong)(y & 0xffffffffUL);
1973 #else
1974 si = *sx++;
1975 ys = (si & 0xffff) + carry;
1976 zs = (si >> 16) + (ys >> 16);
1977 carry = zs >> 16;
1978 y = (*bx & 0xffff) - (ys & 0xffff) - borrow;
1979 borrow = (y & 0x10000) >> 16;
1980 z = (*bx >> 16) - (zs & 0xffff) - borrow;
1981 borrow = (z & 0x10000) >> 16;
1982 Storeinc(bx, z, y);
1983 #endif
1984 } while(sx <= sxe);
1985 bx = b->x;
1986 bxe = bx + n;
1987 if (!*bxe) {
1988 while(--bxe > bx && !*bxe)
1989 --n;
1990 b->wds = n;
1991 }
1992 }
1993 return (int32)q;
1994 }
1996 /* dtoa for IEEE arithmetic (dmg): convert double to ASCII string.
1997 *
1998 * Inspired by "How to Print Floating-Point Numbers Accurately" by
1999 * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 92-101].
2000 *
2001 * Modifications:
2002 * 1. Rather than iterating, we use a simple numeric overestimate
2003 * to determine k = floor(log10(d)). We scale relevant
2004 * quantities using O(log2(k)) rather than O(k) multiplications.
2005 * 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't
2006 * try to generate digits strictly left to right. Instead, we
2007 * compute with fewer bits and propagate the carry if necessary
2008 * when rounding the final digit up. This is often faster.
2009 * 3. Under the assumption that input will be rounded nearest,
2010 * mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22.
2011 * That is, we allow equality in stopping tests when the
2012 * round-nearest rule will give the same floating-point value
2013 * as would satisfaction of the stopping test with strict
2014 * inequality.
2015 * 4. We remove common factors of powers of 2 from relevant
2016 * quantities.
2017 * 5. When converting floating-point integers less than 1e16,
2018 * we use floating-point arithmetic rather than resorting
2019 * to multiple-precision integers.
2020 * 6. When asked to produce fewer than 15 digits, we first try
2021 * to get by with floating-point arithmetic; we resort to
2022 * multiple-precision integer arithmetic only if we cannot
2023 * guarantee that the floating-point calculation has given
2024 * the correctly rounded result. For k requested digits and
2025 * "uniformly" distributed input, the probability is
2026 * something like 10^(k-15) that we must resort to the Long
2027 * calculation.
2028 */
2030 /* Always emits at least one digit. */
2031 /* If biasUp is set, then rounding in modes 2 and 3 will round away from zero
2032 * when the number is exactly halfway between two representable values. For example,
2033 * rounding 2.5 to zero digits after the decimal point will return 3 and not 2.
2034 * 2.49 will still round to 2, and 2.51 will still round to 3. */
2035 /* bufsize should be at least 20 for modes 0 and 1. For the other modes,
2036 * bufsize should be two greater than the maximum number of output characters expected. */
2037 static JSBool
2038 js_dtoa(double d, int mode, JSBool biasUp, int ndigits,
2039 int *decpt, int *sign, char **rve, char *buf, size_t bufsize)
2040 {
2041 /* Arguments ndigits, decpt, sign are similar to those
2042 of ecvt and fcvt; trailing zeros are suppressed from
2043 the returned string. If not null, *rve is set to point
2044 to the end of the return value. If d is +-Infinity or NaN,
2045 then *decpt is set to 9999.
2047 mode:
2048 0 ==> shortest string that yields d when read in
2049 and rounded to nearest.
2050 1 ==> like 0, but with Steele & White stopping rule;
2051 e.g. with IEEE P754 arithmetic , mode 0 gives
2052 1e23 whereas mode 1 gives 9.999999999999999e22.
2053 2 ==> max(1,ndigits) significant digits. This gives a
2054 return value similar to that of ecvt, except
2055 that trailing zeros are suppressed.
2056 3 ==> through ndigits past the decimal point. This
2057 gives a return value similar to that from fcvt,
2058 except that trailing zeros are suppressed, and
2059 ndigits can be negative.
2060 4-9 should give the same return values as 2-3, i.e.,
2061 4 <= mode <= 9 ==> same return as mode
2062 2 + (mode & 1). These modes are mainly for
2063 debugging; often they run slower but sometimes
2064 faster than modes 2-3.
2065 4,5,8,9 ==> left-to-right digit generation.
2066 6-9 ==> don't try fast floating-point estimate
2067 (if applicable).
2069 Values of mode other than 0-9 are treated as mode 0.
2071 Sufficient space is allocated to the return value
2072 to hold the suppressed trailing zeros.
2073 */
2075 int32 bbits, b2, b5, be, dig, i, ieps, ilim, ilim0, ilim1,
2076 j, j1, k, k0, k_check, leftright, m2, m5, s2, s5,
2077 spec_case, try_quick;
2078 Long L;
2079 #ifndef Sudden_Underflow
2080 int32 denorm;
2081 ULong x;
2082 #endif
2083 Bigint *b, *b1, *delta, *mlo, *mhi, *S;
2084 double d2, ds, eps;
2085 char *s;
2087 if (word0(d) & Sign_bit) {
2088 /* set sign for everything, including 0's and NaNs */
2089 *sign = 1;
2090 set_word0(d, word0(d) & ~Sign_bit); /* clear sign bit */
2091 }
2092 else
2093 *sign = 0;
2095 if ((word0(d) & Exp_mask) == Exp_mask) {
2096 /* Infinity or NaN */
2097 *decpt = 9999;
2098 s = !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN";
2099 if ((s[0] == 'I' && bufsize < 9) || (s[0] == 'N' && bufsize < 4)) {
2100 JS_ASSERT(JS_FALSE);
2101 /* JS_SetError(JS_BUFFER_OVERFLOW_ERROR, 0); */
2102 return JS_FALSE;
2103 }
2104 strcpy(buf, s);
2105 if (rve) {
2106 *rve = buf[3] ? buf + 8 : buf + 3;
2107 JS_ASSERT(**rve == '\0');
2108 }
2109 return JS_TRUE;
2110 }
2112 b = NULL; /* initialize for abort protection */
2113 S = NULL;
2114 mlo = mhi = NULL;
2116 if (!d) {
2117 no_digits:
2118 *decpt = 1;
2119 if (bufsize < 2) {
2120 JS_ASSERT(JS_FALSE);
2121 /* JS_SetError(JS_BUFFER_OVERFLOW_ERROR, 0); */
2122 return JS_FALSE;
2123 }
2124 buf[0] = '0'; buf[1] = '\0'; /* copy "0" to buffer */
2125 if (rve)
2126 *rve = buf + 1;
2127 /* We might have jumped to "no_digits" from below, so we need
2128 * to be sure to free the potentially allocated Bigints to avoid
2129 * memory leaks. */
2130 Bfree(b);
2131 Bfree(S);
2132 if (mlo != mhi)
2133 Bfree(mlo);
2134 Bfree(mhi);
2135 return JS_TRUE;
2136 }
2138 b = d2b(d, &be, &bbits);
2139 if (!b)
2140 goto nomem;
2141 #ifdef Sudden_Underflow
2142 i = (int32)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1));
2143 #else
2144 if ((i = (int32)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1))) != 0) {
2145 #endif
2146 d2 = d;
2147 set_word0(d2, word0(d2) & Frac_mask1);
2148 set_word0(d2, word0(d2) | Exp_11);
2150 /* log(x) ~=~ log(1.5) + (x-1.5)/1.5
2151 * log10(x) = log(x) / log(10)
2152 * ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10))
2153 * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2)
2154 *
2155 * This suggests computing an approximation k to log10(d) by
2156 *
2157 * k = (i - Bias)*0.301029995663981
2158 * + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 );
2159 *
2160 * We want k to be too large rather than too small.
2161 * The error in the first-order Taylor series approximation
2162 * is in our favor, so we just round up the constant enough
2163 * to compensate for any error in the multiplication of
2164 * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077,
2165 * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14,
2166 * adding 1e-13 to the constant term more than suffices.
2167 * Hence we adjust the constant term to 0.1760912590558.
2168 * (We could get a more accurate k by invoking log10,
2169 * but this is probably not worthwhile.)
2170 */
2172 i -= Bias;
2173 #ifndef Sudden_Underflow
2174 denorm = 0;
2175 }
2176 else {
2177 /* d is denormalized */
2179 i = bbits + be + (Bias + (P-1) - 1);
2180 x = i > 32 ? word0(d) << (64 - i) | word1(d) >> (i - 32) : word1(d) << (32 - i);
2181 d2 = x;
2182 set_word0(d2, word0(d2) - 31*Exp_msk1); /* adjust exponent */
2183 i -= (Bias + (P-1) - 1) + 1;
2184 denorm = 1;
2185 }
2186 #endif
2187 /* At this point d = f*2^i, where 1 <= f < 2. d2 is an approximation of f. */
2188 ds = (d2-1.5)*0.289529654602168 + 0.1760912590558 + i*0.301029995663981;
2189 k = (int32)ds;
2190 if (ds < 0. && ds != k)
2191 k--; /* want k = floor(ds) */
2192 k_check = 1;
2193 if (k >= 0 && k <= Ten_pmax) {
2194 if (d < tens[k])
2195 k--;
2196 k_check = 0;
2197 }
2198 /* At this point floor(log10(d)) <= k <= floor(log10(d))+1.
2199 If k_check is zero, we're guaranteed that k = floor(log10(d)). */
2200 j = bbits - i - 1;
2201 /* At this point d = b/2^j, where b is an odd integer. */
2202 if (j >= 0) {
2203 b2 = 0;
2204 s2 = j;
2205 }
2206 else {
2207 b2 = -j;
2208 s2 = 0;
2209 }
2210 if (k >= 0) {
2211 b5 = 0;
2212 s5 = k;
2213 s2 += k;
2214 }
2215 else {
2216 b2 -= k;
2217 b5 = -k;
2218 s5 = 0;
2219 }
2220 /* At this point d/10^k = (b * 2^b2 * 5^b5) / (2^s2 * 5^s5), where b is an odd integer,
2221 b2 >= 0, b5 >= 0, s2 >= 0, and s5 >= 0. */
2222 if (mode < 0 || mode > 9)
2223 mode = 0;
2224 try_quick = 1;
2225 if (mode > 5) {
2226 mode -= 4;
2227 try_quick = 0;
2228 }
2229 leftright = 1;
2230 ilim = ilim1 = 0;
2231 switch(mode) {
2232 case 0:
2233 case 1:
2234 ilim = ilim1 = -1;
2235 i = 18;
2236 ndigits = 0;
2237 break;
2238 case 2:
2239 leftright = 0;
2240 /* no break */
2241 case 4:
2242 if (ndigits <= 0)
2243 ndigits = 1;
2244 ilim = ilim1 = i = ndigits;
2245 break;
2246 case 3:
2247 leftright = 0;
2248 /* no break */
2249 case 5:
2250 i = ndigits + k + 1;
2251 ilim = i;
2252 ilim1 = i - 1;
2253 if (i <= 0)
2254 i = 1;
2255 }
2256 /* ilim is the maximum number of significant digits we want, based on k and ndigits. */
2257 /* ilim1 is the maximum number of significant digits we want, based on k and ndigits,
2258 when it turns out that k was computed too high by one. */
2260 /* Ensure space for at least i+1 characters, including trailing null. */
2261 if (bufsize <= (size_t)i) {
2262 Bfree(b);
2263 JS_ASSERT(JS_FALSE);
2264 return JS_FALSE;
2265 }
2266 s = buf;
2268 if (ilim >= 0 && ilim <= Quick_max && try_quick) {
2270 /* Try to get by with floating-point arithmetic. */
2272 i = 0;
2273 d2 = d;
2274 k0 = k;
2275 ilim0 = ilim;
2276 ieps = 2; /* conservative */
2277 /* Divide d by 10^k, keeping track of the roundoff error and avoiding overflows. */
2278 if (k > 0) {
2279 ds = tens[k&0xf];
2280 j = k >> 4;
2281 if (j & Bletch) {
2282 /* prevent overflows */
2283 j &= Bletch - 1;
2284 d /= bigtens[n_bigtens-1];
2285 ieps++;
2286 }
2287 for(; j; j >>= 1, i++)
2288 if (j & 1) {
2289 ieps++;
2290 ds *= bigtens[i];
2291 }
2292 d /= ds;
2293 }
2294 else if ((j1 = -k) != 0) {
2295 d *= tens[j1 & 0xf];
2296 for(j = j1 >> 4; j; j >>= 1, i++)
2297 if (j & 1) {
2298 ieps++;
2299 d *= bigtens[i];
2300 }
2301 }
2302 /* Check that k was computed correctly. */
2303 if (k_check && d < 1. && ilim > 0) {
2304 if (ilim1 <= 0)
2305 goto fast_failed;
2306 ilim = ilim1;
2307 k--;
2308 d *= 10.;
2309 ieps++;
2310 }
2311 /* eps bounds the cumulative error. */
2312 eps = ieps*d + 7.;
2313 set_word0(eps, word0(eps) - (P-1)*Exp_msk1);
2314 if (ilim == 0) {
2315 S = mhi = 0;
2316 d -= 5.;
2317 if (d > eps)
2318 goto one_digit;
2319 if (d < -eps)
2320 goto no_digits;
2321 goto fast_failed;
2322 }
2323 #ifndef No_leftright
2324 if (leftright) {
2325 /* Use Steele & White method of only
2326 * generating digits needed.
2327 */
2328 eps = 0.5/tens[ilim-1] - eps;
2329 for(i = 0;;) {
2330 L = (Long)d;
2331 d -= L;
2332 *s++ = '0' + (char)L;
2333 if (d < eps)
2334 goto ret1;
2335 if (1. - d < eps)
2336 goto bump_up;
2337 if (++i >= ilim)
2338 break;
2339 eps *= 10.;
2340 d *= 10.;
2341 }
2342 }
2343 else {
2344 #endif
2345 /* Generate ilim digits, then fix them up. */
2346 eps *= tens[ilim-1];
2347 for(i = 1;; i++, d *= 10.) {
2348 L = (Long)d;
2349 d -= L;
2350 *s++ = '0' + (char)L;
2351 if (i == ilim) {
2352 if (d > 0.5 + eps)
2353 goto bump_up;
2354 else if (d < 0.5 - eps) {
2355 while(*--s == '0') ;
2356 s++;
2357 goto ret1;
2358 }
2359 break;
2360 }
2361 }
2362 #ifndef No_leftright
2363 }
2364 #endif
2365 fast_failed:
2366 s = buf;
2367 d = d2;
2368 k = k0;
2369 ilim = ilim0;
2370 }
2372 /* Do we have a "small" integer? */
2374 if (be >= 0 && k <= Int_max) {
2375 /* Yes. */
2376 ds = tens[k];
2377 if (ndigits < 0 && ilim <= 0) {
2378 S = mhi = 0;
2379 if (ilim < 0 || d < 5*ds || (!biasUp && d == 5*ds))
2380 goto no_digits;
2381 goto one_digit;
2382 }
2384 /* Use true number of digits to limit looping. */
2385 for(i = 1; i<=k+1; i++) {
2386 L = (Long) (d / ds);
2387 d -= L*ds;
2388 #ifdef Check_FLT_ROUNDS
2389 /* If FLT_ROUNDS == 2, L will usually be high by 1 */
2390 if (d < 0) {
2391 L--;
2392 d += ds;
2393 }
2394 #endif
2395 *s++ = '0' + (char)L;
2396 if (i == ilim) {
2397 d += d;
2398 if ((d > ds) || (d == ds && (L & 1 || biasUp))) {
2399 bump_up:
2400 while(*--s == '9')
2401 if (s == buf) {
2402 k++;
2403 *s = '0';
2404 break;
2405 }
2406 ++*s++;
2407 }
2408 break;
2409 }
2410 d *= 10.;
2411 }
2412 goto ret1;
2413 }
2415 m2 = b2;
2416 m5 = b5;
2417 if (leftright) {
2418 if (mode < 2) {
2419 i =
2420 #ifndef Sudden_Underflow
2421 denorm ? be + (Bias + (P-1) - 1 + 1) :
2422 #endif
2423 1 + P - bbits;
2424 /* i is 1 plus the number of trailing zero bits in d's significand. Thus,
2425 (2^m2 * 5^m5) / (2^(s2+i) * 5^s5) = (1/2 lsb of d)/10^k. */
2426 }
2427 else {
2428 j = ilim - 1;
2429 if (m5 >= j)
2430 m5 -= j;
2431 else {
2432 s5 += j -= m5;
2433 b5 += j;
2434 m5 = 0;
2435 }
2436 if ((i = ilim) < 0) {
2437 m2 -= i;
2438 i = 0;
2439 }
2440 /* (2^m2 * 5^m5) / (2^(s2+i) * 5^s5) = (1/2 * 10^(1-ilim))/10^k. */
2441 }
2442 b2 += i;
2443 s2 += i;
2444 mhi = i2b(1);
2445 if (!mhi)
2446 goto nomem;
2447 /* (mhi * 2^m2 * 5^m5) / (2^s2 * 5^s5) = one-half of last printed (when mode >= 2) or
2448 input (when mode < 2) significant digit, divided by 10^k. */
2449 }
2450 /* We still have d/10^k = (b * 2^b2 * 5^b5) / (2^s2 * 5^s5). Reduce common factors in
2451 b2, m2, and s2 without changing the equalities. */
2452 if (m2 > 0 && s2 > 0) {
2453 i = m2 < s2 ? m2 : s2;
2454 b2 -= i;
2455 m2 -= i;
2456 s2 -= i;
2457 }
2459 /* Fold b5 into b and m5 into mhi. */
2460 if (b5 > 0) {
2461 if (leftright) {
2462 if (m5 > 0) {
2463 mhi = pow5mult(mhi, m5);
2464 if (!mhi)
2465 goto nomem;
2466 b1 = mult(mhi, b);
2467 if (!b1)
2468 goto nomem;
2469 Bfree(b);
2470 b = b1;
2471 }
2472 if ((j = b5 - m5) != 0) {
2473 b = pow5mult(b, j);
2474 if (!b)
2475 goto nomem;
2476 }
2477 }
2478 else {
2479 b = pow5mult(b, b5);
2480 if (!b)
2481 goto nomem;
2482 }
2483 }
2484 /* Now we have d/10^k = (b * 2^b2) / (2^s2 * 5^s5) and
2485 (mhi * 2^m2) / (2^s2 * 5^s5) = one-half of last printed or input significant digit, divided by 10^k. */
2487 S = i2b(1);
2488 if (!S)
2489 goto nomem;
2490 if (s5 > 0) {
2491 S = pow5mult(S, s5);
2492 if (!S)
2493 goto nomem;
2494 }
2495 /* Now we have d/10^k = (b * 2^b2) / (S * 2^s2) and
2496 (mhi * 2^m2) / (S * 2^s2) = one-half of last printed or input significant digit, divided by 10^k. */
2498 /* Check for special case that d is a normalized power of 2. */
2499 spec_case = 0;
2500 if (mode < 2) {
2501 if (!word1(d) && !(word0(d) & Bndry_mask)
2502 #ifndef Sudden_Underflow
2503 && word0(d) & (Exp_mask & Exp_mask << 1)
2504 #endif
2505 ) {
2506 /* The special case. Here we want to be within a quarter of the last input
2507 significant digit instead of one half of it when the decimal output string's value is less than d. */
2508 b2 += Log2P;
2509 s2 += Log2P;
2510 spec_case = 1;
2511 }
2512 }
2514 /* Arrange for convenient computation of quotients:
2515 * shift left if necessary so divisor has 4 leading 0 bits.
2516 *
2517 * Perhaps we should just compute leading 28 bits of S once
2518 * and for all and pass them and a shift to quorem, so it
2519 * can do shifts and ors to compute the numerator for q.
2520 */
2521 if ((i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0x1f) != 0)
2522 i = 32 - i;
2523 /* i is the number of leading zero bits in the most significant word of S*2^s2. */
2524 if (i > 4) {
2525 i -= 4;
2526 b2 += i;
2527 m2 += i;
2528 s2 += i;
2529 }
2530 else if (i < 4) {
2531 i += 28;
2532 b2 += i;
2533 m2 += i;
2534 s2 += i;
2535 }
2536 /* Now S*2^s2 has exactly four leading zero bits in its most significant word. */
2537 if (b2 > 0) {
2538 b = lshift(b, b2);
2539 if (!b)
2540 goto nomem;
2541 }
2542 if (s2 > 0) {
2543 S = lshift(S, s2);
2544 if (!S)
2545 goto nomem;
2546 }
2547 /* Now we have d/10^k = b/S and
2548 (mhi * 2^m2) / S = maximum acceptable error, divided by 10^k. */
2549 if (k_check) {
2550 if (cmp(b,S) < 0) {
2551 k--;
2552 b = multadd(b, 10, 0); /* we botched the k estimate */
2553 if (!b)
2554 goto nomem;
2555 if (leftright) {
2556 mhi = multadd(mhi, 10, 0);
2557 if (!mhi)
2558 goto nomem;
2559 }
2560 ilim = ilim1;
2561 }
2562 }
2563 /* At this point 1 <= d/10^k = b/S < 10. */
2565 if (ilim <= 0 && mode > 2) {
2566 /* We're doing fixed-mode output and d is less than the minimum nonzero output in this mode.
2567 Output either zero or the minimum nonzero output depending on which is closer to d. */
2568 if (ilim < 0)
2569 goto no_digits;
2570 S = multadd(S,5,0);
2571 if (!S)
2572 goto nomem;
2573 i = cmp(b,S);
2574 if (i < 0 || (i == 0 && !biasUp)) {
2575 /* Always emit at least one digit. If the number appears to be zero
2576 using the current mode, then emit one '0' digit and set decpt to 1. */
2577 /*no_digits:
2578 k = -1 - ndigits;
2579 goto ret; */
2580 goto no_digits;
2581 }
2582 one_digit:
2583 *s++ = '1';
2584 k++;
2585 goto ret;
2586 }
2587 if (leftright) {
2588 if (m2 > 0) {
2589 mhi = lshift(mhi, m2);
2590 if (!mhi)
2591 goto nomem;
2592 }
2594 /* Compute mlo -- check for special case
2595 * that d is a normalized power of 2.
2596 */
2598 mlo = mhi;
2599 if (spec_case) {
2600 mhi = Balloc(mhi->k);
2601 if (!mhi)
2602 goto nomem;
2603 Bcopy(mhi, mlo);
2604 mhi = lshift(mhi, Log2P);
2605 if (!mhi)
2606 goto nomem;
2607 }
2608 /* mlo/S = maximum acceptable error, divided by 10^k, if the output is less than d. */
2609 /* mhi/S = maximum acceptable error, divided by 10^k, if the output is greater than d. */
2611 for(i = 1;;i++) {
2612 dig = quorem(b,S) + '0';
2613 /* Do we yet have the shortest decimal string
2614 * that will round to d?
2615 */
2616 j = cmp(b, mlo);
2617 /* j is b/S compared with mlo/S. */
2618 delta = diff(S, mhi);
2619 if (!delta)
2620 goto nomem;
2621 j1 = delta->sign ? 1 : cmp(b, delta);
2622 Bfree(delta);
2623 /* j1 is b/S compared with 1 - mhi/S. */
2624 #ifndef ROUND_BIASED
2625 if (j1 == 0 && !mode && !(word1(d) & 1)) {
2626 if (dig == '9')
2627 goto round_9_up;
2628 if (j > 0)
2629 dig++;
2630 *s++ = (char)dig;
2631 goto ret;
2632 }
2633 #endif
2634 if ((j < 0) || (j == 0 && !mode
2635 #ifndef ROUND_BIASED
2636 && !(word1(d) & 1)
2637 #endif
2638 )) {
2639 if (j1 > 0) {
2640 /* Either dig or dig+1 would work here as the least significant decimal digit.
2641 Use whichever would produce a decimal value closer to d. */
2642 b = lshift(b, 1);
2643 if (!b)
2644 goto nomem;
2645 j1 = cmp(b, S);
2646 if (((j1 > 0) || (j1 == 0 && (dig & 1 || biasUp)))
2647 && (dig++ == '9'))
2648 goto round_9_up;
2649 }
2650 *s++ = (char)dig;
2651 goto ret;
2652 }
2653 if (j1 > 0) {
2654 if (dig == '9') { /* possible if i == 1 */
2655 round_9_up:
2656 *s++ = '9';
2657 goto roundoff;
2658 }
2659 *s++ = (char)dig + 1;
2660 goto ret;
2661 }
2662 *s++ = (char)dig;
2663 if (i == ilim)
2664 break;
2665 b = multadd(b, 10, 0);
2666 if (!b)
2667 goto nomem;
2668 if (mlo == mhi) {
2669 mlo = mhi = multadd(mhi, 10, 0);
2670 if (!mhi)
2671 goto nomem;
2672 }
2673 else {
2674 mlo = multadd(mlo, 10, 0);
2675 if (!mlo)
2676 goto nomem;
2677 mhi = multadd(mhi, 10, 0);
2678 if (!mhi)
2679 goto nomem;
2680 }
2681 }
2682 }
2683 else
2684 for(i = 1;; i++) {
2685 *s++ = (char)(dig = quorem(b,S) + '0');
2686 if (i >= ilim)
2687 break;
2688 b = multadd(b, 10, 0);
2689 if (!b)
2690 goto nomem;
2691 }
2693 /* Round off last digit */
2695 b = lshift(b, 1);
2696 if (!b)
2697 goto nomem;
2698 j = cmp(b, S);
2699 if ((j > 0) || (j == 0 && (dig & 1 || biasUp))) {
2700 roundoff:
2701 while(*--s == '9')
2702 if (s == buf) {
2703 k++;
2704 *s++ = '1';
2705 goto ret;
2706 }
2707 ++*s++;
2708 }
2709 else {
2710 /* Strip trailing zeros */
2711 while(*--s == '0') ;
2712 s++;
2713 }
2714 ret:
2715 Bfree(S);
2716 if (mhi) {
2717 if (mlo && mlo != mhi)
2718 Bfree(mlo);
2719 Bfree(mhi);
2720 }
2721 ret1:
2722 Bfree(b);
2723 JS_ASSERT(s < buf + bufsize);
2724 *s = '\0';
2725 if (rve)
2726 *rve = s;
2727 *decpt = k + 1;
2728 return JS_TRUE;
2730 nomem:
2731 Bfree(S);
2732 if (mhi) {
2733 if (mlo && mlo != mhi)
2734 Bfree(mlo);
2735 Bfree(mhi);
2736 }
2737 Bfree(b);
2738 return JS_FALSE;
2739 }
2742 /* Mapping of JSDToStrMode -> js_dtoa mode */
2743 static const int dtoaModes[] = {
2744 0, /* DTOSTR_STANDARD */
2745 0, /* DTOSTR_STANDARD_EXPONENTIAL, */
2746 3, /* DTOSTR_FIXED, */
2747 2, /* DTOSTR_EXPONENTIAL, */
2748 2}; /* DTOSTR_PRECISION */
2750 JS_FRIEND_API(char *)
2751 JS_dtostr(char *buffer, size_t bufferSize, JSDToStrMode mode, int precision, double d)
2752 {
2753 int decPt; /* Position of decimal point relative to first digit returned by js_dtoa */
2754 int sign; /* Nonzero if the sign bit was set in d */
2755 int nDigits; /* Number of significand digits returned by js_dtoa */
2756 char *numBegin = buffer+2; /* Pointer to the digits returned by js_dtoa; the +2 leaves space for */
2757 /* the sign and/or decimal point */
2758 char *numEnd; /* Pointer past the digits returned by js_dtoa */
2759 JSBool dtoaRet;
2761 JS_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL ? DTOSTR_STANDARD_BUFFER_SIZE :
2762 DTOSTR_VARIABLE_BUFFER_SIZE(precision)));
2764 if (mode == DTOSTR_FIXED && (d >= 1e21 || d <= -1e21))
2765 mode = DTOSTR_STANDARD; /* Change mode here rather than below because the buffer may not be large enough to hold a large integer. */
2767 /* Locking for Balloc's shared buffers */
2768 ACQUIRE_DTOA_LOCK();
2769 dtoaRet = js_dtoa(d, dtoaModes[mode], mode >= DTOSTR_FIXED, precision, &decPt, &sign, &numEnd, numBegin, bufferSize-2);
2770 RELEASE_DTOA_LOCK();
2771 if (!dtoaRet)
2772 return 0;
2774 nDigits = numEnd - numBegin;
2776 /* If Infinity, -Infinity, or NaN, return the string regardless of the mode. */
2777 if (decPt != 9999) {
2778 JSBool exponentialNotation = JS_FALSE;
2779 int minNDigits = 0; /* Minimum number of significand digits required by mode and precision */
2780 char *p;
2781 char *q;
2783 switch (mode) {
2784 case DTOSTR_STANDARD:
2785 if (decPt < -5 || decPt > 21)
2786 exponentialNotation = JS_TRUE;
2787 else
2788 minNDigits = decPt;
2789 break;
2791 case DTOSTR_FIXED:
2792 if (precision >= 0)
2793 minNDigits = decPt + precision;
2794 else
2795 minNDigits = decPt;
2796 break;
2798 case DTOSTR_EXPONENTIAL:
2799 JS_ASSERT(precision > 0);
2800 minNDigits = precision;
2801 /* Fall through */
2802 case DTOSTR_STANDARD_EXPONENTIAL:
2803 exponentialNotation = JS_TRUE;
2804 break;
2806 case DTOSTR_PRECISION:
2807 JS_ASSERT(precision > 0);
2808 minNDigits = precision;
2809 if (decPt < -5 || decPt > precision)
2810 exponentialNotation = JS_TRUE;
2811 break;
2812 }
2814 /* If the number has fewer than minNDigits, pad it with zeros at the end */
2815 if (nDigits < minNDigits) {
2816 p = numBegin + minNDigits;
2817 nDigits = minNDigits;
2818 do {
2819 *numEnd++ = '0';
2820 } while (numEnd != p);
2821 *numEnd = '\0';
2822 }
2824 if (exponentialNotation) {
2825 /* Insert a decimal point if more than one significand digit */
2826 if (nDigits != 1) {
2827 numBegin--;
2828 numBegin[0] = numBegin[1];
2829 numBegin[1] = '.';
2830 }
2831 JS_snprintf(numEnd, bufferSize - (numEnd - buffer), "e%+d", decPt-1);
2832 } else if (decPt != nDigits) {
2833 /* Some kind of a fraction in fixed notation */
2834 JS_ASSERT(decPt <= nDigits);
2835 if (decPt > 0) {
2836 /* dd...dd . dd...dd */
2837 p = --numBegin;
2838 do {
2839 *p = p[1];
2840 p++;
2841 } while (--decPt);
2842 *p = '.';
2843 } else {
2844 /* 0 . 00...00dd...dd */
2845 p = numEnd;
2846 numEnd += 1 - decPt;
2847 q = numEnd;
2848 JS_ASSERT(numEnd < buffer + bufferSize);
2849 *numEnd = '\0';
2850 while (p != numBegin)
2851 *--q = *--p;
2852 for (p = numBegin + 1; p != q; p++)
2853 *p = '0';
2854 *numBegin = '.';
2855 *--numBegin = '0';
2856 }
2857 }
2858 }
2860 /* If negative and neither -0.0 nor NaN, output a leading '-'. */
2861 if (sign &&
2862 !(word0(d) == Sign_bit && word1(d) == 0) &&
2863 !((word0(d) & Exp_mask) == Exp_mask &&
2864 (word1(d) || (word0(d) & Frac_mask)))) {
2865 *--numBegin = '-';
2866 }
2867 return numBegin;
2868 }
2871 /* Let b = floor(b / divisor), and return the remainder. b must be nonnegative.
2872 * divisor must be between 1 and 65536.
2873 * This function cannot run out of memory. */
2874 static uint32
2875 divrem(Bigint *b, uint32 divisor)
2876 {
2877 int32 n = b->wds;
2878 uint32 remainder = 0;
2879 ULong *bx;
2880 ULong *bp;
2882 JS_ASSERT(divisor > 0 && divisor <= 65536);
2884 if (!n)
2885 return 0; /* b is zero */
2886 bx = b->x;
2887 bp = bx + n;
2888 do {
2889 ULong a = *--bp;
2890 ULong dividend = remainder << 16 | a >> 16;
2891 ULong quotientHi = dividend / divisor;
2892 ULong quotientLo;
2894 remainder = dividend - quotientHi*divisor;
2895 JS_ASSERT(quotientHi <= 0xFFFF && remainder < divisor);
2896 dividend = remainder << 16 | (a & 0xFFFF);
2897 quotientLo = dividend / divisor;
2898 remainder = dividend - quotientLo*divisor;
2899 JS_ASSERT(quotientLo <= 0xFFFF && remainder < divisor);
2900 *bp = quotientHi << 16 | quotientLo;
2901 } while (bp != bx);
2902 /* Decrease the size of the number if its most significant word is now zero. */
2903 if (bx[n-1] == 0)
2904 b->wds--;
2905 return remainder;
2906 }
2909 /* "-0.0000...(1073 zeros after decimal point)...0001\0" is the longest string that we could produce,
2910 * which occurs when printing -5e-324 in binary. We could compute a better estimate of the size of
2911 * the output string and malloc fewer bytes depending on d and base, but why bother? */
2912 #define DTOBASESTR_BUFFER_SIZE 1078
2913 #define BASEDIGIT(digit) ((char)(((digit) >= 10) ? 'a' - 10 + (digit) : '0' + (digit)))
2915 JS_FRIEND_API(char *)
2916 JS_dtobasestr(int base, double d)
2917 {
2918 char *buffer; /* The output string */
2919 char *p; /* Pointer to current position in the buffer */
2920 char *pInt; /* Pointer to the beginning of the integer part of the string */
2921 char *q;
2922 uint32 digit;
2923 double di; /* d truncated to an integer */
2924 double df; /* The fractional part of d */
2926 JS_ASSERT(base >= 2 && base <= 36);
2928 buffer = (char*) malloc(DTOBASESTR_BUFFER_SIZE);
2929 if (buffer) {
2930 p = buffer;
2931 if (d < 0.0
2932 #if defined(XP_WIN) || defined(XP_OS2)
2933 && !((word0(d) & Exp_mask) == Exp_mask && ((word0(d) & Frac_mask) || word1(d))) /* Visual C++ doesn't know how to compare against NaN */
2934 #endif
2935 ) {
2936 *p++ = '-';
2937 d = -d;
2938 }
2940 /* Check for Infinity and NaN */
2941 if ((word0(d) & Exp_mask) == Exp_mask) {
2942 strcpy(p, !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN");
2943 return buffer;
2944 }
2946 /* Locking for Balloc's shared buffers */
2947 ACQUIRE_DTOA_LOCK();
2949 /* Output the integer part of d with the digits in reverse order. */
2950 pInt = p;
2951 di = fd_floor(d);
2952 if (di <= 4294967295.0) {
2953 uint32 n = (uint32)di;
2954 if (n)
2955 do {
2956 uint32 m = n / base;
2957 digit = n - m*base;
2958 n = m;
2959 JS_ASSERT(digit < (uint32)base);
2960 *p++ = BASEDIGIT(digit);
2961 } while (n);
2962 else *p++ = '0';
2963 } else {
2964 int32 e;
2965 int32 bits; /* Number of significant bits in di; not used. */
2966 Bigint *b = d2b(di, &e, &bits);
2967 if (!b)
2968 goto nomem1;
2969 b = lshift(b, e);
2970 if (!b) {
2971 nomem1:
2972 Bfree(b);
2973 return NULL;
2974 }
2975 do {
2976 digit = divrem(b, base);
2977 JS_ASSERT(digit < (uint32)base);
2978 *p++ = BASEDIGIT(digit);
2979 } while (b->wds);
2980 Bfree(b);
2981 }
2982 /* Reverse the digits of the integer part of d. */
2983 q = p-1;
2984 while (q > pInt) {
2985 char ch = *pInt;
2986 *pInt++ = *q;
2987 *q-- = ch;
2988 }
2990 df = d - di;
2991 if (df != 0.0) {
2992 /* We have a fraction. */
2993 int32 e, bbits, s2, done;
2994 Bigint *b, *s, *mlo, *mhi;
2996 b = s = mlo = mhi = NULL;
2998 *p++ = '.';
2999 b = d2b(df, &e, &bbits);
3000 if (!b) {
3001 nomem2:
3002 Bfree(b);
3003 Bfree(s);
3004 if (mlo != mhi)
3005 Bfree(mlo);
3006 Bfree(mhi);
3007 return NULL;
3008 }
3009 JS_ASSERT(e < 0);
3010 /* At this point df = b * 2^e. e must be less than zero because 0 < df < 1. */
3012 s2 = -(int32)(word0(d) >> Exp_shift1 & Exp_mask>>Exp_shift1);
3013 #ifndef Sudden_Underflow
3014 if (!s2)
3015 s2 = -1;
3016 #endif
3017 s2 += Bias + P;
3018 /* 1/2^s2 = (nextDouble(d) - d)/2 */
3019 JS_ASSERT(-s2 < e);
3020 mlo = i2b(1);
3021 if (!mlo)
3022 goto nomem2;
3023 mhi = mlo;
3024 if (!word1(d) && !(word0(d) & Bndry_mask)
3025 #ifndef Sudden_Underflow
3026 && word0(d) & (Exp_mask & Exp_mask << 1)
3027 #endif
3028 ) {
3029 /* The special case. Here we want to be within a quarter of the last input
3030 significant digit instead of one half of it when the output string's value is less than d. */
3031 s2 += Log2P;
3032 mhi = i2b(1<<Log2P);
3033 if (!mhi)
3034 goto nomem2;
3035 }
3036 b = lshift(b, e + s2);
3037 if (!b)
3038 goto nomem2;
3039 s = i2b(1);
3040 if (!s)
3041 goto nomem2;
3042 s = lshift(s, s2);
3043 if (!s)
3044 goto nomem2;
3045 /* At this point we have the following:
3046 * s = 2^s2;
3047 * 1 > df = b/2^s2 > 0;
3048 * (d - prevDouble(d))/2 = mlo/2^s2;
3049 * (nextDouble(d) - d)/2 = mhi/2^s2. */
3051 done = JS_FALSE;
3052 do {
3053 int32 j, j1;
3054 Bigint *delta;
3056 b = multadd(b, base, 0);
3057 if (!b)
3058 goto nomem2;
3059 digit = quorem2(b, s2);
3060 if (mlo == mhi) {
3061 mlo = mhi = multadd(mlo, base, 0);
3062 if (!mhi)
3063 goto nomem2;
3064 }
3065 else {
3066 mlo = multadd(mlo, base, 0);
3067 if (!mlo)
3068 goto nomem2;
3069 mhi = multadd(mhi, base, 0);
3070 if (!mhi)
3071 goto nomem2;
3072 }
3074 /* Do we yet have the shortest string that will round to d? */
3075 j = cmp(b, mlo);
3076 /* j is b/2^s2 compared with mlo/2^s2. */
3077 delta = diff(s, mhi);
3078 if (!delta)
3079 goto nomem2;
3080 j1 = delta->sign ? 1 : cmp(b, delta);
3081 Bfree(delta);
3082 /* j1 is b/2^s2 compared with 1 - mhi/2^s2. */
3084 #ifndef ROUND_BIASED
3085 if (j1 == 0 && !(word1(d) & 1)) {
3086 if (j > 0)
3087 digit++;
3088 done = JS_TRUE;
3089 } else
3090 #endif
3091 if (j < 0 || (j == 0
3092 #ifndef ROUND_BIASED
3093 && !(word1(d) & 1)
3094 #endif
3095 )) {
3096 if (j1 > 0) {
3097 /* Either dig or dig+1 would work here as the least significant digit.
3098 Use whichever would produce an output value closer to d. */
3099 b = lshift(b, 1);
3100 if (!b)
3101 goto nomem2;
3102 j1 = cmp(b, s);
3103 if (j1 > 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here because it messes up odd base output
3104 * such as 3.5 in base 3. */
3105 digit++;
3106 }
3107 done = JS_TRUE;
3108 } else if (j1 > 0) {
3109 digit++;
3110 done = JS_TRUE;
3111 }
3112 JS_ASSERT(digit < (uint32)base);
3113 *p++ = BASEDIGIT(digit);
3114 } while (!done);
3115 Bfree(b);
3116 Bfree(s);
3117 if (mlo != mhi)
3118 Bfree(mlo);
3119 Bfree(mhi);
3120 }
3121 JS_ASSERT(p < buffer + DTOBASESTR_BUFFER_SIZE);
3122 *p = '\0';
3123 RELEASE_DTOA_LOCK();
3124 }
3125 return buffer;
3126 }