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