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 *err = 0;
1251 bb = bd = bs = delta = NULL;
1252 sign = nz0 = nz = 0;
1253 rv = 0.;
1255 /* Locking for Balloc's shared buffers that will be used in this block */
1256 ACQUIRE_DTOA_LOCK();
1258 for(s = s00;;s++) switch(*s) {
1259 case '-':
1260 sign = 1;
1261 /* no break */
1262 case '+':
1263 if (*++s)
1264 goto break2;
1265 /* no break */
1266 case 0:
1267 s = s00;
1268 goto ret;
1269 case '\t':
1270 case '\n':
1271 case '\v':
1272 case '\f':
1273 case '\r':
1274 case ' ':
1275 continue;
1276 default:
1277 goto break2;
1278 }
1279 break2:
1281 if (*s == '0') {
1282 nz0 = 1;
1283 while(*++s == '0') ;
1284 if (!*s)
1285 goto ret;
1286 }
1287 s0 = s;
1288 y = z = 0;
1289 for(nd = nf = 0; (c = *s) >= '0' && c <= '9'; nd++, s++)
1290 if (nd < 9)
1291 y = 10*y + c - '0';
1292 else if (nd < 16)
1293 z = 10*z + c - '0';
1294 nd0 = nd;
1295 if (c == '.') {
1296 c = *++s;
1297 if (!nd) {
1298 for(; c == '0'; c = *++s)
1299 nz++;
1300 if (c > '0' && c <= '9') {
1301 s0 = s;
1302 nf += nz;
1303 nz = 0;
1304 goto have_dig;
1305 }
1306 goto dig_done;
1307 }
1308 for(; c >= '0' && c <= '9'; c = *++s) {
1309 have_dig:
1310 nz++;
1311 if (c -= '0') {
1312 nf += nz;
1313 for(i = 1; i < nz; i++)
1314 if (nd++ < 9)
1315 y *= 10;
1316 else if (nd <= DBL_DIG + 1)
1317 z *= 10;
1318 if (nd++ < 9)
1319 y = 10*y + c;
1320 else if (nd <= DBL_DIG + 1)
1321 z = 10*z + c;
1322 nz = 0;
1323 }
1324 }
1325 }
1326 dig_done:
1327 e = 0;
1328 if (c == 'e' || c == 'E') {
1329 if (!nd && !nz && !nz0) {
1330 s = s00;
1331 goto ret;
1332 }
1333 s00 = s;
1334 esign = 0;
1335 switch(c = *++s) {
1336 case '-':
1337 esign = 1;
1338 case '+':
1339 c = *++s;
1340 }
1341 if (c >= '0' && c <= '9') {
1342 while(c == '0')
1343 c = *++s;
1344 if (c > '0' && c <= '9') {
1345 L = c - '0';
1346 s1 = s;
1347 while((c = *++s) >= '0' && c <= '9')
1348 L = 10*L + c - '0';
1349 if (s - s1 > 8 || L > 19999)
1350 /* Avoid confusion from exponents
1351 * so large that e might overflow.
1352 */
1353 e = 19999; /* safe for 16 bit ints */
1354 else
1355 e = (int32)L;
1356 if (esign)
1357 e = -e;
1358 }
1359 else
1360 e = 0;
1361 }
1362 else
1363 s = s00;
1364 }
1365 if (!nd) {
1366 if (!nz && !nz0) {
1367 #ifdef INFNAN_CHECK
1368 /* Check for Nan and Infinity */
1369 switch(c) {
1370 case 'i':
1371 case 'I':
1372 if (match(&s,"nfinity")) {
1373 word0(rv) = 0x7ff00000;
1374 word1(rv) = 0;
1375 goto ret;
1376 }
1377 break;
1378 case 'n':
1379 case 'N':
1380 if (match(&s, "an")) {
1381 word0(rv) = NAN_WORD0;
1382 word1(rv) = NAN_WORD1;
1383 goto ret;
1384 }
1385 }
1386 #endif /* INFNAN_CHECK */
1387 s = s00;
1388 }
1389 goto ret;
1390 }
1391 e1 = e -= nf;
1393 /* Now we have nd0 digits, starting at s0, followed by a
1394 * decimal point, followed by nd-nd0 digits. The number we're
1395 * after is the integer represented by those digits times
1396 * 10**e */
1398 if (!nd0)
1399 nd0 = nd;
1400 k = nd < DBL_DIG + 1 ? nd : DBL_DIG + 1;
1401 rv = y;
1402 if (k > 9)
1403 rv = tens[k - 9] * rv + z;
1404 bd0 = 0;
1405 if (nd <= DBL_DIG
1406 #ifndef RND_PRODQUOT
1407 && FLT_ROUNDS == 1
1408 #endif
1409 ) {
1410 if (!e)
1411 goto ret;
1412 if (e > 0) {
1413 if (e <= Ten_pmax) {
1414 /* rv = */ rounded_product(rv, tens[e]);
1415 goto ret;
1416 }
1417 i = DBL_DIG - nd;
1418 if (e <= Ten_pmax + i) {
1419 /* A fancier test would sometimes let us do
1420 * this for larger i values.
1421 */
1422 e -= i;
1423 rv *= tens[i];
1424 /* rv = */ rounded_product(rv, tens[e]);
1425 goto ret;
1426 }
1427 }
1428 #ifndef Inaccurate_Divide
1429 else if (e >= -Ten_pmax) {
1430 /* rv = */ rounded_quotient(rv, tens[-e]);
1431 goto ret;
1432 }
1433 #endif
1434 }
1435 e1 += nd - k;
1437 scale = 0;
1439 /* Get starting approximation = rv * 10**e1 */
1441 if (e1 > 0) {
1442 if ((i = e1 & 15) != 0)
1443 rv *= tens[i];
1444 if (e1 &= ~15) {
1445 if (e1 > DBL_MAX_10_EXP) {
1446 ovfl:
1447 *err = JS_DTOA_ERANGE;
1448 #ifdef __STDC__
1449 rv = HUGE_VAL;
1450 #else
1451 /* Can't trust HUGE_VAL */
1452 word0(rv) = Exp_mask;
1453 word1(rv) = 0;
1454 #endif
1455 if (bd0)
1456 goto retfree;
1457 goto ret;
1458 }
1459 e1 >>= 4;
1460 for(j = 0; e1 > 1; j++, e1 >>= 1)
1461 if (e1 & 1)
1462 rv *= bigtens[j];
1463 /* The last multiplication could overflow. */
1464 set_word0(rv, word0(rv) - P*Exp_msk1);
1465 rv *= bigtens[j];
1466 if ((z = word0(rv) & Exp_mask) > Exp_msk1*(DBL_MAX_EXP+Bias-P))
1467 goto ovfl;
1468 if (z > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) {
1469 /* set to largest number */
1470 /* (Can't trust DBL_MAX) */
1471 set_word0(rv, Big0);
1472 set_word1(rv, Big1);
1473 }
1474 else
1475 set_word0(rv, word0(rv) + P*Exp_msk1);
1476 }
1477 }
1478 else if (e1 < 0) {
1479 e1 = -e1;
1480 if ((i = e1 & 15) != 0)
1481 rv /= tens[i];
1482 if (e1 &= ~15) {
1483 e1 >>= 4;
1484 if (e1 >= 1 << n_bigtens)
1485 goto undfl;
1486 #ifdef Avoid_Underflow
1487 if (e1 & Scale_Bit)
1488 scale = P;
1489 for(j = 0; e1 > 0; j++, e1 >>= 1)
1490 if (e1 & 1)
1491 rv *= tinytens[j];
1492 if (scale && (j = P + 1 - ((word0(rv) & Exp_mask)
1493 >> Exp_shift)) > 0) {
1494 /* scaled rv is denormal; zap j low bits */
1495 if (j >= 32) {
1496 set_word1(rv, 0);
1497 set_word0(rv, word0(rv) & (0xffffffff << (j-32)));
1498 if (!word0(rv))
1499 set_word0(rv, 1);
1500 }
1501 else
1502 set_word1(rv, word1(rv) & (0xffffffff << j));
1503 }
1504 #else
1505 for(j = 0; e1 > 1; j++, e1 >>= 1)
1506 if (e1 & 1)
1507 rv *= tinytens[j];
1508 /* The last multiplication could underflow. */
1509 rv0 = rv;
1510 rv *= tinytens[j];
1511 if (!rv) {
1512 rv = 2.*rv0;
1513 rv *= tinytens[j];
1514 #endif
1515 if (!rv) {
1516 undfl:
1517 rv = 0.;
1518 *err = JS_DTOA_ERANGE;
1519 if (bd0)
1520 goto retfree;
1521 goto ret;
1522 }
1523 #ifndef Avoid_Underflow
1524 set_word0(rv, Tiny0);
1525 set_word1(rv, Tiny1);
1526 /* The refinement below will clean
1527 * this approximation up.
1528 */
1529 }
1530 #endif
1531 }
1532 }
1534 /* Now the hard part -- adjusting rv to the correct value.*/
1536 /* Put digits into bd: true value = bd * 10^e */
1538 bd0 = s2b(s0, nd0, nd, y);
1539 if (!bd0)
1540 goto nomem;
1542 for(;;) {
1543 bd = Balloc(bd0->k);
1544 if (!bd)
1545 goto nomem;
1546 Bcopy(bd, bd0);
1547 bb = d2b(rv, &bbe, &bbbits); /* rv = bb * 2^bbe */
1548 if (!bb)
1549 goto nomem;
1550 bs = i2b(1);
1551 if (!bs)
1552 goto nomem;
1554 if (e >= 0) {
1555 bb2 = bb5 = 0;
1556 bd2 = bd5 = e;
1557 }
1558 else {
1559 bb2 = bb5 = -e;
1560 bd2 = bd5 = 0;
1561 }
1562 if (bbe >= 0)
1563 bb2 += bbe;
1564 else
1565 bd2 -= bbe;
1566 bs2 = bb2;
1567 #ifdef Sudden_Underflow
1568 j = P + 1 - bbbits;
1569 #else
1570 #ifdef Avoid_Underflow
1571 j = bbe - scale;
1572 #else
1573 j = bbe;
1574 #endif
1575 i = j + bbbits - 1; /* logb(rv) */
1576 if (i < Emin) /* denormal */
1577 j += P - Emin;
1578 else
1579 j = P + 1 - bbbits;
1580 #endif
1581 bb2 += j;
1582 bd2 += j;
1583 #ifdef Avoid_Underflow
1584 bd2 += scale;
1585 #endif
1586 i = bb2 < bd2 ? bb2 : bd2;
1587 if (i > bs2)
1588 i = bs2;
1589 if (i > 0) {
1590 bb2 -= i;
1591 bd2 -= i;
1592 bs2 -= i;
1593 }
1594 if (bb5 > 0) {
1595 bs = pow5mult(bs, bb5);
1596 if (!bs)
1597 goto nomem;
1598 bb1 = mult(bs, bb);
1599 if (!bb1)
1600 goto nomem;
1601 Bfree(bb);
1602 bb = bb1;
1603 }
1604 if (bb2 > 0) {
1605 bb = lshift(bb, bb2);
1606 if (!bb)
1607 goto nomem;
1608 }
1609 if (bd5 > 0) {
1610 bd = pow5mult(bd, bd5);
1611 if (!bd)
1612 goto nomem;
1613 }
1614 if (bd2 > 0) {
1615 bd = lshift(bd, bd2);
1616 if (!bd)
1617 goto nomem;
1618 }
1619 if (bs2 > 0) {
1620 bs = lshift(bs, bs2);
1621 if (!bs)
1622 goto nomem;
1623 }
1624 delta = diff(bb, bd);
1625 if (!delta)
1626 goto nomem;
1627 dsign = delta->sign;
1628 delta->sign = 0;
1629 i = cmp(delta, bs);
1630 if (i < 0) {
1631 /* Error is less than half an ulp -- check for
1632 * special case of mantissa a power of two.
1633 */
1634 if (dsign || word1(rv) || word0(rv) & Bndry_mask
1635 #ifdef Avoid_Underflow
1636 || (word0(rv) & Exp_mask) <= Exp_msk1 + P*Exp_msk1
1637 #else
1638 || (word0(rv) & Exp_mask) <= Exp_msk1
1639 #endif
1640 ) {
1641 #ifdef Avoid_Underflow
1642 if (!delta->x[0] && delta->wds == 1)
1643 dsign = 2;
1644 #endif
1645 break;
1646 }
1647 delta = lshift(delta,Log2P);
1648 if (!delta)
1649 goto nomem;
1650 if (cmp(delta, bs) > 0)
1651 goto drop_down;
1652 break;
1653 }
1654 if (i == 0) {
1655 /* exactly half-way between */
1656 if (dsign) {
1657 if ((word0(rv) & Bndry_mask1) == Bndry_mask1
1658 && word1(rv) == 0xffffffff) {
1659 /*boundary case -- increment exponent*/
1660 set_word0(rv, (word0(rv) & Exp_mask) + Exp_msk1);
1661 set_word1(rv, 0);
1662 #ifdef Avoid_Underflow
1663 dsign = 0;
1664 #endif
1665 break;
1666 }
1667 }
1668 else if (!(word0(rv) & Bndry_mask) && !word1(rv)) {
1669 #ifdef Avoid_Underflow
1670 dsign = 2;
1671 #endif
1672 drop_down:
1673 /* boundary case -- decrement exponent */
1674 #ifdef Sudden_Underflow
1675 L = word0(rv) & Exp_mask;
1676 if (L <= Exp_msk1)
1677 goto undfl;
1678 L -= Exp_msk1;
1679 #else
1680 L = (word0(rv) & Exp_mask) - Exp_msk1;
1681 #endif
1682 set_word0(rv, L | Bndry_mask1);
1683 set_word1(rv, 0xffffffff);
1684 break;
1685 }
1686 #ifndef ROUND_BIASED
1687 if (!(word1(rv) & LSB))
1688 break;
1689 #endif
1690 if (dsign)
1691 rv += ulp(rv);
1692 #ifndef ROUND_BIASED
1693 else {
1694 rv -= ulp(rv);
1695 #ifndef Sudden_Underflow
1696 if (!rv)
1697 goto undfl;
1698 #endif
1699 }
1700 #ifdef Avoid_Underflow
1701 dsign = 1 - dsign;
1702 #endif
1703 #endif
1704 break;
1705 }
1706 if ((aadj = ratio(delta, bs)) <= 2.) {
1707 if (dsign)
1708 aadj = aadj1 = 1.;
1709 else if (word1(rv) || word0(rv) & Bndry_mask) {
1710 #ifndef Sudden_Underflow
1711 if (word1(rv) == Tiny1 && !word0(rv))
1712 goto undfl;
1713 #endif
1714 aadj = 1.;
1715 aadj1 = -1.;
1716 }
1717 else {
1718 /* special case -- power of FLT_RADIX to be */
1719 /* rounded down... */
1721 if (aadj < 2./FLT_RADIX)
1722 aadj = 1./FLT_RADIX;
1723 else
1724 aadj *= 0.5;
1725 aadj1 = -aadj;
1726 }
1727 }
1728 else {
1729 aadj *= 0.5;
1730 aadj1 = dsign ? aadj : -aadj;
1731 #ifdef Check_FLT_ROUNDS
1732 switch(FLT_ROUNDS) {
1733 case 2: /* towards +infinity */
1734 aadj1 -= 0.5;
1735 break;
1736 case 0: /* towards 0 */
1737 case 3: /* towards -infinity */
1738 aadj1 += 0.5;
1739 }
1740 #else
1741 if (FLT_ROUNDS == 0)
1742 aadj1 += 0.5;
1743 #endif
1744 }
1745 y = word0(rv) & Exp_mask;
1747 /* Check for overflow */
1749 if (y == Exp_msk1*(DBL_MAX_EXP+Bias-1)) {
1750 rv0 = rv;
1751 set_word0(rv, word0(rv) - P*Exp_msk1);
1752 adj = aadj1 * ulp(rv);
1753 rv += adj;
1754 if ((word0(rv) & Exp_mask) >=
1755 Exp_msk1*(DBL_MAX_EXP+Bias-P)) {
1756 if (word0(rv0) == Big0 && word1(rv0) == Big1)
1757 goto ovfl;
1758 set_word0(rv, Big0);
1759 set_word1(rv, Big1);
1760 goto cont;
1761 }
1762 else
1763 set_word0(rv, word0(rv) + P*Exp_msk1);
1764 }
1765 else {
1766 #ifdef Sudden_Underflow
1767 if ((word0(rv) & Exp_mask) <= P*Exp_msk1) {
1768 rv0 = rv;
1769 set_word0(rv, word0(rv) + P*Exp_msk1);
1770 adj = aadj1 * ulp(rv);
1771 rv += adj;
1772 if ((word0(rv) & Exp_mask) <= P*Exp_msk1)
1773 {
1774 if (word0(rv0) == Tiny0
1775 && word1(rv0) == Tiny1)
1776 goto undfl;
1777 set_word0(rv, Tiny0);
1778 set_word1(rv, Tiny1);
1779 goto cont;
1780 }
1781 else
1782 set_word0(rv, word0(rv) - P*Exp_msk1);
1783 }
1784 else {
1785 adj = aadj1 * ulp(rv);
1786 rv += adj;
1787 }
1788 #else
1789 /* Compute adj so that the IEEE rounding rules will
1790 * correctly round rv + adj in some half-way cases.
1791 * If rv * ulp(rv) is denormalized (i.e.,
1792 * y <= (P-1)*Exp_msk1), we must adjust aadj to avoid
1793 * trouble from bits lost to denormalization;
1794 * example: 1.2e-307 .
1795 */
1796 #ifdef Avoid_Underflow
1797 if (y <= P*Exp_msk1 && aadj > 1.)
1798 #else
1799 if (y <= (P-1)*Exp_msk1 && aadj > 1.)
1800 #endif
1801 {
1802 aadj1 = (double)(int32)(aadj + 0.5);
1803 if (!dsign)
1804 aadj1 = -aadj1;
1805 }
1806 #ifdef Avoid_Underflow
1807 if (scale && y <= P*Exp_msk1)
1808 set_word0(aadj1, word0(aadj1) + (P+1)*Exp_msk1 - y);
1809 #endif
1810 adj = aadj1 * ulp(rv);
1811 rv += adj;
1812 #endif
1813 }
1814 z = word0(rv) & Exp_mask;
1815 #ifdef Avoid_Underflow
1816 if (!scale)
1817 #endif
1818 if (y == z) {
1819 /* Can we stop now? */
1820 L = (Long)aadj;
1821 aadj -= L;
1822 /* The tolerances below are conservative. */
1823 if (dsign || word1(rv) || word0(rv) & Bndry_mask) {
1824 if (aadj < .4999999 || aadj > .5000001)
1825 break;
1826 }
1827 else if (aadj < .4999999/FLT_RADIX)
1828 break;
1829 }
1830 cont:
1831 Bfree(bb);
1832 Bfree(bd);
1833 Bfree(bs);
1834 Bfree(delta);
1835 bb = bd = bs = delta = NULL;
1836 }
1837 #ifdef Avoid_Underflow
1838 if (scale) {
1839 set_word0(rv0, Exp_1 - P*Exp_msk1);
1840 set_word1(rv0, 0);
1841 if ((word0(rv) & Exp_mask) <= P*Exp_msk1
1842 && word1(rv) & 1
1843 && dsign != 2) {
1844 if (dsign) {
1845 #ifdef Sudden_Underflow
1846 /* rv will be 0, but this would give the */
1847 /* right result if only rv *= rv0 worked. */
1848 set_word0(rv, word0(rv) + P*Exp_msk1);
1849 set_word0(rv0, Exp_1 - 2*P*Exp_msk1);
1850 #endif
1851 rv += ulp(rv);
1852 }
1853 else
1854 set_word1(rv, word1(rv) & ~1);
1855 }
1856 rv *= rv0;
1857 }
1858 #endif /* Avoid_Underflow */
1859 retfree:
1860 Bfree(bb);
1861 Bfree(bd);
1862 Bfree(bs);
1863 Bfree(bd0);
1864 Bfree(delta);
1865 ret:
1866 RELEASE_DTOA_LOCK();
1867 if (se)
1868 *se = (char *)s;
1869 return sign ? -rv : rv;
1871 nomem:
1872 Bfree(bb);
1873 Bfree(bd);
1874 Bfree(bs);
1875 Bfree(bd0);
1876 Bfree(delta);
1877 *err = JS_DTOA_ENOMEM;
1878 return 0;
1879 }
1882 /* Return floor(b/2^k) and set b to be the remainder. The returned quotient must be less than 2^32. */
1883 static uint32 quorem2(Bigint *b, int32 k)
1884 {
1885 ULong mask;
1886 ULong result;
1887 ULong *bx, *bxe;
1888 int32 w;
1889 int32 n = k >> 5;
1890 k &= 0x1F;
1891 mask = (1<<k) - 1;
1893 w = b->wds - n;
1894 if (w <= 0)
1895 return 0;
1896 JS_ASSERT(w <= 2);
1897 bx = b->x;
1898 bxe = bx + n;
1899 result = *bxe >> k;
1900 *bxe &= mask;
1901 if (w == 2) {
1902 JS_ASSERT(!(bxe[1] & ~mask));
1903 if (k)
1904 result |= bxe[1] << (32 - k);
1905 }
1906 n++;
1907 while (!*bxe && bxe != bx) {
1908 n--;
1909 bxe--;
1910 }
1911 b->wds = n;
1912 return result;
1913 }
1915 /* Return floor(b/S) and set b to be the remainder. As added restrictions, b must not have
1916 * more words than S, the most significant word of S must not start with a 1 bit, and the
1917 * returned quotient must be less than 36. */
1918 static int32 quorem(Bigint *b, Bigint *S)
1919 {
1920 int32 n;
1921 ULong *bx, *bxe, q, *sx, *sxe;
1922 #ifdef ULLong
1923 ULLong borrow, carry, y, ys;
1924 #else
1925 ULong borrow, carry, y, ys;
1926 ULong si, z, zs;
1927 #endif
1929 n = S->wds;
1930 JS_ASSERT(b->wds <= n);
1931 if (b->wds < n)
1932 return 0;
1933 sx = S->x;
1934 sxe = sx + --n;
1935 bx = b->x;
1936 bxe = bx + n;
1937 JS_ASSERT(*sxe <= 0x7FFFFFFF);
1938 q = *bxe / (*sxe + 1); /* ensure q <= true quotient */
1939 JS_ASSERT(q < 36);
1940 if (q) {
1941 borrow = 0;
1942 carry = 0;
1943 do {
1944 #ifdef ULLong
1945 ys = *sx++ * (ULLong)q + carry;
1946 carry = ys >> 32;
1947 y = *bx - (ys & 0xffffffffUL) - borrow;
1948 borrow = y >> 32 & 1UL;
1949 *bx++ = (ULong)(y & 0xffffffffUL);
1950 #else
1951 si = *sx++;
1952 ys = (si & 0xffff) * q + carry;
1953 zs = (si >> 16) * q + (ys >> 16);
1954 carry = zs >> 16;
1955 y = (*bx & 0xffff) - (ys & 0xffff) - borrow;
1956 borrow = (y & 0x10000) >> 16;
1957 z = (*bx >> 16) - (zs & 0xffff) - borrow;
1958 borrow = (z & 0x10000) >> 16;
1959 Storeinc(bx, z, y);
1960 #endif
1961 }
1962 while(sx <= sxe);
1963 if (!*bxe) {
1964 bx = b->x;
1965 while(--bxe > bx && !*bxe)
1966 --n;
1967 b->wds = n;
1968 }
1969 }
1970 if (cmp(b, S) >= 0) {
1971 q++;
1972 borrow = 0;
1973 carry = 0;
1974 bx = b->x;
1975 sx = S->x;
1976 do {
1977 #ifdef ULLong
1978 ys = *sx++ + carry;
1979 carry = ys >> 32;
1980 y = *bx - (ys & 0xffffffffUL) - borrow;
1981 borrow = y >> 32 & 1UL;
1982 *bx++ = (ULong)(y & 0xffffffffUL);
1983 #else
1984 si = *sx++;
1985 ys = (si & 0xffff) + carry;
1986 zs = (si >> 16) + (ys >> 16);
1987 carry = zs >> 16;
1988 y = (*bx & 0xffff) - (ys & 0xffff) - borrow;
1989 borrow = (y & 0x10000) >> 16;
1990 z = (*bx >> 16) - (zs & 0xffff) - borrow;
1991 borrow = (z & 0x10000) >> 16;
1992 Storeinc(bx, z, y);
1993 #endif
1994 } while(sx <= sxe);
1995 bx = b->x;
1996 bxe = bx + n;
1997 if (!*bxe) {
1998 while(--bxe > bx && !*bxe)
1999 --n;
2000 b->wds = n;
2001 }
2002 }
2003 return (int32)q;
2004 }
2006 /* dtoa for IEEE arithmetic (dmg): convert double to ASCII string.
2007 *
2008 * Inspired by "How to Print Floating-Point Numbers Accurately" by
2009 * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 92-101].
2010 *
2011 * Modifications:
2012 * 1. Rather than iterating, we use a simple numeric overestimate
2013 * to determine k = floor(log10(d)). We scale relevant
2014 * quantities using O(log2(k)) rather than O(k) multiplications.
2015 * 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't
2016 * try to generate digits strictly left to right. Instead, we
2017 * compute with fewer bits and propagate the carry if necessary
2018 * when rounding the final digit up. This is often faster.
2019 * 3. Under the assumption that input will be rounded nearest,
2020 * mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22.
2021 * That is, we allow equality in stopping tests when the
2022 * round-nearest rule will give the same floating-point value
2023 * as would satisfaction of the stopping test with strict
2024 * inequality.
2025 * 4. We remove common factors of powers of 2 from relevant
2026 * quantities.
2027 * 5. When converting floating-point integers less than 1e16,
2028 * we use floating-point arithmetic rather than resorting
2029 * to multiple-precision integers.
2030 * 6. When asked to produce fewer than 15 digits, we first try
2031 * to get by with floating-point arithmetic; we resort to
2032 * multiple-precision integer arithmetic only if we cannot
2033 * guarantee that the floating-point calculation has given
2034 * the correctly rounded result. For k requested digits and
2035 * "uniformly" distributed input, the probability is
2036 * something like 10^(k-15) that we must resort to the Long
2037 * calculation.
2038 */
2040 /* Always emits at least one digit. */
2041 /* If biasUp is set, then rounding in modes 2 and 3 will round away from zero
2042 * when the number is exactly halfway between two representable values. For example,
2043 * rounding 2.5 to zero digits after the decimal point will return 3 and not 2.
2044 * 2.49 will still round to 2, and 2.51 will still round to 3. */
2045 /* bufsize should be at least 20 for modes 0 and 1. For the other modes,
2046 * bufsize should be two greater than the maximum number of output characters expected. */
2047 static JSBool
2048 js_dtoa(double d, int mode, JSBool biasUp, int ndigits,
2049 int *decpt, int *sign, char **rve, char *buf, size_t bufsize)
2050 {
2051 /* Arguments ndigits, decpt, sign are similar to those
2052 of ecvt and fcvt; trailing zeros are suppressed from
2053 the returned string. If not null, *rve is set to point
2054 to the end of the return value. If d is +-Infinity or NaN,
2055 then *decpt is set to 9999.
2057 mode:
2058 0 ==> shortest string that yields d when read in
2059 and rounded to nearest.
2060 1 ==> like 0, but with Steele & White stopping rule;
2061 e.g. with IEEE P754 arithmetic , mode 0 gives
2062 1e23 whereas mode 1 gives 9.999999999999999e22.
2063 2 ==> max(1,ndigits) significant digits. This gives a
2064 return value similar to that of ecvt, except
2065 that trailing zeros are suppressed.
2066 3 ==> through ndigits past the decimal point. This
2067 gives a return value similar to that from fcvt,
2068 except that trailing zeros are suppressed, and
2069 ndigits can be negative.
2070 4-9 should give the same return values as 2-3, i.e.,
2071 4 <= mode <= 9 ==> same return as mode
2072 2 + (mode & 1). These modes are mainly for
2073 debugging; often they run slower but sometimes
2074 faster than modes 2-3.
2075 4,5,8,9 ==> left-to-right digit generation.
2076 6-9 ==> don't try fast floating-point estimate
2077 (if applicable).
2079 Values of mode other than 0-9 are treated as mode 0.
2081 Sufficient space is allocated to the return value
2082 to hold the suppressed trailing zeros.
2083 */
2085 int32 bbits, b2, b5, be, dig, i, ieps, ilim, ilim0, ilim1,
2086 j, j1, k, k0, k_check, leftright, m2, m5, s2, s5,
2087 spec_case, try_quick;
2088 Long L;
2089 #ifndef Sudden_Underflow
2090 int32 denorm;
2091 ULong x;
2092 #endif
2093 Bigint *b, *b1, *delta, *mlo, *mhi, *S;
2094 double d2, ds, eps;
2095 char *s;
2097 if (word0(d) & Sign_bit) {
2098 /* set sign for everything, including 0's and NaNs */
2099 *sign = 1;
2100 set_word0(d, word0(d) & ~Sign_bit); /* clear sign bit */
2101 }
2102 else
2103 *sign = 0;
2105 if ((word0(d) & Exp_mask) == Exp_mask) {
2106 /* Infinity or NaN */
2107 *decpt = 9999;
2108 s = !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN";
2109 if ((s[0] == 'I' && bufsize < 9) || (s[0] == 'N' && bufsize < 4)) {
2110 JS_ASSERT(JS_FALSE);
2111 /* JS_SetError(JS_BUFFER_OVERFLOW_ERROR, 0); */
2112 return JS_FALSE;
2113 }
2114 strcpy(buf, s);
2115 if (rve) {
2116 *rve = buf[3] ? buf + 8 : buf + 3;
2117 JS_ASSERT(**rve == '\0');
2118 }
2119 return JS_TRUE;
2120 }
2122 b = NULL; /* initialize for abort protection */
2123 S = NULL;
2124 mlo = mhi = NULL;
2126 if (!d) {
2127 no_digits:
2128 *decpt = 1;
2129 if (bufsize < 2) {
2130 JS_ASSERT(JS_FALSE);
2131 /* JS_SetError(JS_BUFFER_OVERFLOW_ERROR, 0); */
2132 return JS_FALSE;
2133 }
2134 buf[0] = '0'; buf[1] = '\0'; /* copy "0" to buffer */
2135 if (rve)
2136 *rve = buf + 1;
2137 /* We might have jumped to "no_digits" from below, so we need
2138 * to be sure to free the potentially allocated Bigints to avoid
2139 * memory leaks. */
2140 Bfree(b);
2141 Bfree(S);
2142 if (mlo != mhi)
2143 Bfree(mlo);
2144 Bfree(mhi);
2145 return JS_TRUE;
2146 }
2148 b = d2b(d, &be, &bbits);
2149 if (!b)
2150 goto nomem;
2151 #ifdef Sudden_Underflow
2152 i = (int32)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1));
2153 #else
2154 if ((i = (int32)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1))) != 0) {
2155 #endif
2156 d2 = d;
2157 set_word0(d2, word0(d2) & Frac_mask1);
2158 set_word0(d2, word0(d2) | Exp_11);
2160 /* log(x) ~=~ log(1.5) + (x-1.5)/1.5
2161 * log10(x) = log(x) / log(10)
2162 * ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10))
2163 * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2)
2164 *
2165 * This suggests computing an approximation k to log10(d) by
2166 *
2167 * k = (i - Bias)*0.301029995663981
2168 * + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 );
2169 *
2170 * We want k to be too large rather than too small.
2171 * The error in the first-order Taylor series approximation
2172 * is in our favor, so we just round up the constant enough
2173 * to compensate for any error in the multiplication of
2174 * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077,
2175 * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14,
2176 * adding 1e-13 to the constant term more than suffices.
2177 * Hence we adjust the constant term to 0.1760912590558.
2178 * (We could get a more accurate k by invoking log10,
2179 * but this is probably not worthwhile.)
2180 */
2182 i -= Bias;
2183 #ifndef Sudden_Underflow
2184 denorm = 0;
2185 }
2186 else {
2187 /* d is denormalized */
2189 i = bbits + be + (Bias + (P-1) - 1);
2190 x = i > 32 ? word0(d) << (64 - i) | word1(d) >> (i - 32) : word1(d) << (32 - i);
2191 d2 = x;
2192 set_word0(d2, word0(d2) - 31*Exp_msk1); /* adjust exponent */
2193 i -= (Bias + (P-1) - 1) + 1;
2194 denorm = 1;
2195 }
2196 #endif
2197 /* At this point d = f*2^i, where 1 <= f < 2. d2 is an approximation of f. */
2198 ds = (d2-1.5)*0.289529654602168 + 0.1760912590558 + i*0.301029995663981;
2199 k = (int32)ds;
2200 if (ds < 0. && ds != k)
2201 k--; /* want k = floor(ds) */
2202 k_check = 1;
2203 if (k >= 0 && k <= Ten_pmax) {
2204 if (d < tens[k])
2205 k--;
2206 k_check = 0;
2207 }
2208 /* At this point floor(log10(d)) <= k <= floor(log10(d))+1.
2209 If k_check is zero, we're guaranteed that k = floor(log10(d)). */
2210 j = bbits - i - 1;
2211 /* At this point d = b/2^j, where b is an odd integer. */
2212 if (j >= 0) {
2213 b2 = 0;
2214 s2 = j;
2215 }
2216 else {
2217 b2 = -j;
2218 s2 = 0;
2219 }
2220 if (k >= 0) {
2221 b5 = 0;
2222 s5 = k;
2223 s2 += k;
2224 }
2225 else {
2226 b2 -= k;
2227 b5 = -k;
2228 s5 = 0;
2229 }
2230 /* At this point d/10^k = (b * 2^b2 * 5^b5) / (2^s2 * 5^s5), where b is an odd integer,
2231 b2 >= 0, b5 >= 0, s2 >= 0, and s5 >= 0. */
2232 if (mode < 0 || mode > 9)
2233 mode = 0;
2234 try_quick = 1;
2235 if (mode > 5) {
2236 mode -= 4;
2237 try_quick = 0;
2238 }
2239 leftright = 1;
2240 ilim = ilim1 = 0;
2241 switch(mode) {
2242 case 0:
2243 case 1:
2244 ilim = ilim1 = -1;
2245 i = 18;
2246 ndigits = 0;
2247 break;
2248 case 2:
2249 leftright = 0;
2250 /* no break */
2251 case 4:
2252 if (ndigits <= 0)
2253 ndigits = 1;
2254 ilim = ilim1 = i = ndigits;
2255 break;
2256 case 3:
2257 leftright = 0;
2258 /* no break */
2259 case 5:
2260 i = ndigits + k + 1;
2261 ilim = i;
2262 ilim1 = i - 1;
2263 if (i <= 0)
2264 i = 1;
2265 }
2266 /* ilim is the maximum number of significant digits we want, based on k and ndigits. */
2267 /* ilim1 is the maximum number of significant digits we want, based on k and ndigits,
2268 when it turns out that k was computed too high by one. */
2270 /* Ensure space for at least i+1 characters, including trailing null. */
2271 if (bufsize <= (size_t)i) {
2272 Bfree(b);
2273 JS_ASSERT(JS_FALSE);
2274 return JS_FALSE;
2275 }
2276 s = buf;
2278 if (ilim >= 0 && ilim <= Quick_max && try_quick) {
2280 /* Try to get by with floating-point arithmetic. */
2282 i = 0;
2283 d2 = d;
2284 k0 = k;
2285 ilim0 = ilim;
2286 ieps = 2; /* conservative */
2287 /* Divide d by 10^k, keeping track of the roundoff error and avoiding overflows. */
2288 if (k > 0) {
2289 ds = tens[k&0xf];
2290 j = k >> 4;
2291 if (j & Bletch) {
2292 /* prevent overflows */
2293 j &= Bletch - 1;
2294 d /= bigtens[n_bigtens-1];
2295 ieps++;
2296 }
2297 for(; j; j >>= 1, i++)
2298 if (j & 1) {
2299 ieps++;
2300 ds *= bigtens[i];
2301 }
2302 d /= ds;
2303 }
2304 else if ((j1 = -k) != 0) {
2305 d *= tens[j1 & 0xf];
2306 for(j = j1 >> 4; j; j >>= 1, i++)
2307 if (j & 1) {
2308 ieps++;
2309 d *= bigtens[i];
2310 }
2311 }
2312 /* Check that k was computed correctly. */
2313 if (k_check && d < 1. && ilim > 0) {
2314 if (ilim1 <= 0)
2315 goto fast_failed;
2316 ilim = ilim1;
2317 k--;
2318 d *= 10.;
2319 ieps++;
2320 }
2321 /* eps bounds the cumulative error. */
2322 eps = ieps*d + 7.;
2323 set_word0(eps, word0(eps) - (P-1)*Exp_msk1);
2324 if (ilim == 0) {
2325 S = mhi = 0;
2326 d -= 5.;
2327 if (d > eps)
2328 goto one_digit;
2329 if (d < -eps)
2330 goto no_digits;
2331 goto fast_failed;
2332 }
2333 #ifndef No_leftright
2334 if (leftright) {
2335 /* Use Steele & White method of only
2336 * generating digits needed.
2337 */
2338 eps = 0.5/tens[ilim-1] - eps;
2339 for(i = 0;;) {
2340 L = (Long)d;
2341 d -= L;
2342 *s++ = '0' + (char)L;
2343 if (d < eps)
2344 goto ret1;
2345 if (1. - d < eps)
2346 goto bump_up;
2347 if (++i >= ilim)
2348 break;
2349 eps *= 10.;
2350 d *= 10.;
2351 }
2352 }
2353 else {
2354 #endif
2355 /* Generate ilim digits, then fix them up. */
2356 eps *= tens[ilim-1];
2357 for(i = 1;; i++, d *= 10.) {
2358 L = (Long)d;
2359 d -= L;
2360 *s++ = '0' + (char)L;
2361 if (i == ilim) {
2362 if (d > 0.5 + eps)
2363 goto bump_up;
2364 else if (d < 0.5 - eps) {
2365 while(*--s == '0') ;
2366 s++;
2367 goto ret1;
2368 }
2369 break;
2370 }
2371 }
2372 #ifndef No_leftright
2373 }
2374 #endif
2375 fast_failed:
2376 s = buf;
2377 d = d2;
2378 k = k0;
2379 ilim = ilim0;
2380 }
2382 /* Do we have a "small" integer? */
2384 if (be >= 0 && k <= Int_max) {
2385 /* Yes. */
2386 ds = tens[k];
2387 if (ndigits < 0 && ilim <= 0) {
2388 S = mhi = 0;
2389 if (ilim < 0 || d < 5*ds || (!biasUp && d == 5*ds))
2390 goto no_digits;
2391 goto one_digit;
2392 }
2393 for(i = 1;; i++) {
2394 L = (Long) (d / ds);
2395 d -= L*ds;
2396 #ifdef Check_FLT_ROUNDS
2397 /* If FLT_ROUNDS == 2, L will usually be high by 1 */
2398 if (d < 0) {
2399 L--;
2400 d += ds;
2401 }
2402 #endif
2403 *s++ = '0' + (char)L;
2404 if (i == ilim) {
2405 d += d;
2406 if ((d > ds) || (d == ds && (L & 1 || biasUp))) {
2407 bump_up:
2408 while(*--s == '9')
2409 if (s == buf) {
2410 k++;
2411 *s = '0';
2412 break;
2413 }
2414 ++*s++;
2415 }
2416 break;
2417 }
2418 if (!(d *= 10.))
2419 break;
2420 }
2421 goto ret1;
2422 }
2424 m2 = b2;
2425 m5 = b5;
2426 if (leftright) {
2427 if (mode < 2) {
2428 i =
2429 #ifndef Sudden_Underflow
2430 denorm ? be + (Bias + (P-1) - 1 + 1) :
2431 #endif
2432 1 + P - bbits;
2433 /* i is 1 plus the number of trailing zero bits in d's significand. Thus,
2434 (2^m2 * 5^m5) / (2^(s2+i) * 5^s5) = (1/2 lsb of d)/10^k. */
2435 }
2436 else {
2437 j = ilim - 1;
2438 if (m5 >= j)
2439 m5 -= j;
2440 else {
2441 s5 += j -= m5;
2442 b5 += j;
2443 m5 = 0;
2444 }
2445 if ((i = ilim) < 0) {
2446 m2 -= i;
2447 i = 0;
2448 }
2449 /* (2^m2 * 5^m5) / (2^(s2+i) * 5^s5) = (1/2 * 10^(1-ilim))/10^k. */
2450 }
2451 b2 += i;
2452 s2 += i;
2453 mhi = i2b(1);
2454 if (!mhi)
2455 goto nomem;
2456 /* (mhi * 2^m2 * 5^m5) / (2^s2 * 5^s5) = one-half of last printed (when mode >= 2) or
2457 input (when mode < 2) significant digit, divided by 10^k. */
2458 }
2459 /* We still have d/10^k = (b * 2^b2 * 5^b5) / (2^s2 * 5^s5). Reduce common factors in
2460 b2, m2, and s2 without changing the equalities. */
2461 if (m2 > 0 && s2 > 0) {
2462 i = m2 < s2 ? m2 : s2;
2463 b2 -= i;
2464 m2 -= i;
2465 s2 -= i;
2466 }
2468 /* Fold b5 into b and m5 into mhi. */
2469 if (b5 > 0) {
2470 if (leftright) {
2471 if (m5 > 0) {
2472 mhi = pow5mult(mhi, m5);
2473 if (!mhi)
2474 goto nomem;
2475 b1 = mult(mhi, b);
2476 if (!b1)
2477 goto nomem;
2478 Bfree(b);
2479 b = b1;
2480 }
2481 if ((j = b5 - m5) != 0) {
2482 b = pow5mult(b, j);
2483 if (!b)
2484 goto nomem;
2485 }
2486 }
2487 else {
2488 b = pow5mult(b, b5);
2489 if (!b)
2490 goto nomem;
2491 }
2492 }
2493 /* Now we have d/10^k = (b * 2^b2) / (2^s2 * 5^s5) and
2494 (mhi * 2^m2) / (2^s2 * 5^s5) = one-half of last printed or input significant digit, divided by 10^k. */
2496 S = i2b(1);
2497 if (!S)
2498 goto nomem;
2499 if (s5 > 0) {
2500 S = pow5mult(S, s5);
2501 if (!S)
2502 goto nomem;
2503 }
2504 /* Now we have d/10^k = (b * 2^b2) / (S * 2^s2) and
2505 (mhi * 2^m2) / (S * 2^s2) = one-half of last printed or input significant digit, divided by 10^k. */
2507 /* Check for special case that d is a normalized power of 2. */
2508 spec_case = 0;
2509 if (mode < 2) {
2510 if (!word1(d) && !(word0(d) & Bndry_mask)
2511 #ifndef Sudden_Underflow
2512 && word0(d) & (Exp_mask & Exp_mask << 1)
2513 #endif
2514 ) {
2515 /* The special case. Here we want to be within a quarter of the last input
2516 significant digit instead of one half of it when the decimal output string's value is less than d. */
2517 b2 += Log2P;
2518 s2 += Log2P;
2519 spec_case = 1;
2520 }
2521 }
2523 /* Arrange for convenient computation of quotients:
2524 * shift left if necessary so divisor has 4 leading 0 bits.
2525 *
2526 * Perhaps we should just compute leading 28 bits of S once
2527 * and for all and pass them and a shift to quorem, so it
2528 * can do shifts and ors to compute the numerator for q.
2529 */
2530 if ((i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0x1f) != 0)
2531 i = 32 - i;
2532 /* i is the number of leading zero bits in the most significant word of S*2^s2. */
2533 if (i > 4) {
2534 i -= 4;
2535 b2 += i;
2536 m2 += i;
2537 s2 += i;
2538 }
2539 else if (i < 4) {
2540 i += 28;
2541 b2 += i;
2542 m2 += i;
2543 s2 += i;
2544 }
2545 /* Now S*2^s2 has exactly four leading zero bits in its most significant word. */
2546 if (b2 > 0) {
2547 b = lshift(b, b2);
2548 if (!b)
2549 goto nomem;
2550 }
2551 if (s2 > 0) {
2552 S = lshift(S, s2);
2553 if (!S)
2554 goto nomem;
2555 }
2556 /* Now we have d/10^k = b/S and
2557 (mhi * 2^m2) / S = maximum acceptable error, divided by 10^k. */
2558 if (k_check) {
2559 if (cmp(b,S) < 0) {
2560 k--;
2561 b = multadd(b, 10, 0); /* we botched the k estimate */
2562 if (!b)
2563 goto nomem;
2564 if (leftright) {
2565 mhi = multadd(mhi, 10, 0);
2566 if (!mhi)
2567 goto nomem;
2568 }
2569 ilim = ilim1;
2570 }
2571 }
2572 /* At this point 1 <= d/10^k = b/S < 10. */
2574 if (ilim <= 0 && mode > 2) {
2575 /* We're doing fixed-mode output and d is less than the minimum nonzero output in this mode.
2576 Output either zero or the minimum nonzero output depending on which is closer to d. */
2577 if (ilim < 0)
2578 goto no_digits;
2579 S = multadd(S,5,0);
2580 if (!S)
2581 goto nomem;
2582 i = cmp(b,S);
2583 if (i < 0 || (i == 0 && !biasUp)) {
2584 /* Always emit at least one digit. If the number appears to be zero
2585 using the current mode, then emit one '0' digit and set decpt to 1. */
2586 /*no_digits:
2587 k = -1 - ndigits;
2588 goto ret; */
2589 goto no_digits;
2590 }
2591 one_digit:
2592 *s++ = '1';
2593 k++;
2594 goto ret;
2595 }
2596 if (leftright) {
2597 if (m2 > 0) {
2598 mhi = lshift(mhi, m2);
2599 if (!mhi)
2600 goto nomem;
2601 }
2603 /* Compute mlo -- check for special case
2604 * that d is a normalized power of 2.
2605 */
2607 mlo = mhi;
2608 if (spec_case) {
2609 mhi = Balloc(mhi->k);
2610 if (!mhi)
2611 goto nomem;
2612 Bcopy(mhi, mlo);
2613 mhi = lshift(mhi, Log2P);
2614 if (!mhi)
2615 goto nomem;
2616 }
2617 /* mlo/S = maximum acceptable error, divided by 10^k, if the output is less than d. */
2618 /* mhi/S = maximum acceptable error, divided by 10^k, if the output is greater than d. */
2620 for(i = 1;;i++) {
2621 dig = quorem(b,S) + '0';
2622 /* Do we yet have the shortest decimal string
2623 * that will round to d?
2624 */
2625 j = cmp(b, mlo);
2626 /* j is b/S compared with mlo/S. */
2627 delta = diff(S, mhi);
2628 if (!delta)
2629 goto nomem;
2630 j1 = delta->sign ? 1 : cmp(b, delta);
2631 Bfree(delta);
2632 /* j1 is b/S compared with 1 - mhi/S. */
2633 #ifndef ROUND_BIASED
2634 if (j1 == 0 && !mode && !(word1(d) & 1)) {
2635 if (dig == '9')
2636 goto round_9_up;
2637 if (j > 0)
2638 dig++;
2639 *s++ = (char)dig;
2640 goto ret;
2641 }
2642 #endif
2643 if ((j < 0) || (j == 0 && !mode
2644 #ifndef ROUND_BIASED
2645 && !(word1(d) & 1)
2646 #endif
2647 )) {
2648 if (j1 > 0) {
2649 /* Either dig or dig+1 would work here as the least significant decimal digit.
2650 Use whichever would produce a decimal value closer to d. */
2651 b = lshift(b, 1);
2652 if (!b)
2653 goto nomem;
2654 j1 = cmp(b, S);
2655 if (((j1 > 0) || (j1 == 0 && (dig & 1 || biasUp)))
2656 && (dig++ == '9'))
2657 goto round_9_up;
2658 }
2659 *s++ = (char)dig;
2660 goto ret;
2661 }
2662 if (j1 > 0) {
2663 if (dig == '9') { /* possible if i == 1 */
2664 round_9_up:
2665 *s++ = '9';
2666 goto roundoff;
2667 }
2668 *s++ = (char)dig + 1;
2669 goto ret;
2670 }
2671 *s++ = (char)dig;
2672 if (i == ilim)
2673 break;
2674 b = multadd(b, 10, 0);
2675 if (!b)
2676 goto nomem;
2677 if (mlo == mhi) {
2678 mlo = mhi = multadd(mhi, 10, 0);
2679 if (!mhi)
2680 goto nomem;
2681 }
2682 else {
2683 mlo = multadd(mlo, 10, 0);
2684 if (!mlo)
2685 goto nomem;
2686 mhi = multadd(mhi, 10, 0);
2687 if (!mhi)
2688 goto nomem;
2689 }
2690 }
2691 }
2692 else
2693 for(i = 1;; i++) {
2694 *s++ = (char)(dig = quorem(b,S) + '0');
2695 if (i >= ilim)
2696 break;
2697 b = multadd(b, 10, 0);
2698 if (!b)
2699 goto nomem;
2700 }
2702 /* Round off last digit */
2704 b = lshift(b, 1);
2705 if (!b)
2706 goto nomem;
2707 j = cmp(b, S);
2708 if ((j > 0) || (j == 0 && (dig & 1 || biasUp))) {
2709 roundoff:
2710 while(*--s == '9')
2711 if (s == buf) {
2712 k++;
2713 *s++ = '1';
2714 goto ret;
2715 }
2716 ++*s++;
2717 }
2718 else {
2719 /* Strip trailing zeros */
2720 while(*--s == '0') ;
2721 s++;
2722 }
2723 ret:
2724 Bfree(S);
2725 if (mhi) {
2726 if (mlo && mlo != mhi)
2727 Bfree(mlo);
2728 Bfree(mhi);
2729 }
2730 ret1:
2731 Bfree(b);
2732 JS_ASSERT(s < buf + bufsize);
2733 *s = '\0';
2734 if (rve)
2735 *rve = s;
2736 *decpt = k + 1;
2737 return JS_TRUE;
2739 nomem:
2740 Bfree(S);
2741 if (mhi) {
2742 if (mlo && mlo != mhi)
2743 Bfree(mlo);
2744 Bfree(mhi);
2745 }
2746 Bfree(b);
2747 return JS_FALSE;
2748 }
2751 /* Mapping of JSDToStrMode -> js_dtoa mode */
2752 static const int dtoaModes[] = {
2753 0, /* DTOSTR_STANDARD */
2754 0, /* DTOSTR_STANDARD_EXPONENTIAL, */
2755 3, /* DTOSTR_FIXED, */
2756 2, /* DTOSTR_EXPONENTIAL, */
2757 2}; /* DTOSTR_PRECISION */
2759 JS_FRIEND_API(char *)
2760 JS_dtostr(char *buffer, size_t bufferSize, JSDToStrMode mode, int precision, double d)
2761 {
2762 int decPt; /* Position of decimal point relative to first digit returned by js_dtoa */
2763 int sign; /* Nonzero if the sign bit was set in d */
2764 int nDigits; /* Number of significand digits returned by js_dtoa */
2765 char *numBegin = buffer+2; /* Pointer to the digits returned by js_dtoa; the +2 leaves space for */
2766 /* the sign and/or decimal point */
2767 char *numEnd; /* Pointer past the digits returned by js_dtoa */
2768 JSBool dtoaRet;
2770 JS_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL ? DTOSTR_STANDARD_BUFFER_SIZE :
2771 DTOSTR_VARIABLE_BUFFER_SIZE(precision)));
2773 if (mode == DTOSTR_FIXED && (d >= 1e21 || d <= -1e21))
2774 mode = DTOSTR_STANDARD; /* Change mode here rather than below because the buffer may not be large enough to hold a large integer. */
2776 /* Locking for Balloc's shared buffers */
2777 ACQUIRE_DTOA_LOCK();
2778 dtoaRet = js_dtoa(d, dtoaModes[mode], mode >= DTOSTR_FIXED, precision, &decPt, &sign, &numEnd, numBegin, bufferSize-2);
2779 RELEASE_DTOA_LOCK();
2780 if (!dtoaRet)
2781 return 0;
2783 nDigits = numEnd - numBegin;
2785 /* If Infinity, -Infinity, or NaN, return the string regardless of the mode. */
2786 if (decPt != 9999) {
2787 JSBool exponentialNotation = JS_FALSE;
2788 int minNDigits = 0; /* Minimum number of significand digits required by mode and precision */
2789 char *p;
2790 char *q;
2792 switch (mode) {
2793 case DTOSTR_STANDARD:
2794 if (decPt < -5 || decPt > 21)
2795 exponentialNotation = JS_TRUE;
2796 else
2797 minNDigits = decPt;
2798 break;
2800 case DTOSTR_FIXED:
2801 if (precision >= 0)
2802 minNDigits = decPt + precision;
2803 else
2804 minNDigits = decPt;
2805 break;
2807 case DTOSTR_EXPONENTIAL:
2808 JS_ASSERT(precision > 0);
2809 minNDigits = precision;
2810 /* Fall through */
2811 case DTOSTR_STANDARD_EXPONENTIAL:
2812 exponentialNotation = JS_TRUE;
2813 break;
2815 case DTOSTR_PRECISION:
2816 JS_ASSERT(precision > 0);
2817 minNDigits = precision;
2818 if (decPt < -5 || decPt > precision)
2819 exponentialNotation = JS_TRUE;
2820 break;
2821 }
2823 /* If the number has fewer than minNDigits, pad it with zeros at the end */
2824 if (nDigits < minNDigits) {
2825 p = numBegin + minNDigits;
2826 nDigits = minNDigits;
2827 do {
2828 *numEnd++ = '0';
2829 } while (numEnd != p);
2830 *numEnd = '\0';
2831 }
2833 if (exponentialNotation) {
2834 /* Insert a decimal point if more than one significand digit */
2835 if (nDigits != 1) {
2836 numBegin--;
2837 numBegin[0] = numBegin[1];
2838 numBegin[1] = '.';
2839 }
2840 JS_snprintf(numEnd, bufferSize - (numEnd - buffer), "e%+d", decPt-1);
2841 } else if (decPt != nDigits) {
2842 /* Some kind of a fraction in fixed notation */
2843 JS_ASSERT(decPt <= nDigits);
2844 if (decPt > 0) {
2845 /* dd...dd . dd...dd */
2846 p = --numBegin;
2847 do {
2848 *p = p[1];
2849 p++;
2850 } while (--decPt);
2851 *p = '.';
2852 } else {
2853 /* 0 . 00...00dd...dd */
2854 p = numEnd;
2855 numEnd += 1 - decPt;
2856 q = numEnd;
2857 JS_ASSERT(numEnd < buffer + bufferSize);
2858 *numEnd = '\0';
2859 while (p != numBegin)
2860 *--q = *--p;
2861 for (p = numBegin + 1; p != q; p++)
2862 *p = '0';
2863 *numBegin = '.';
2864 *--numBegin = '0';
2865 }
2866 }
2867 }
2869 /* If negative and neither -0.0 nor NaN, output a leading '-'. */
2870 if (sign &&
2871 !(word0(d) == Sign_bit && word1(d) == 0) &&
2872 !((word0(d) & Exp_mask) == Exp_mask &&
2873 (word1(d) || (word0(d) & Frac_mask)))) {
2874 *--numBegin = '-';
2875 }
2876 return numBegin;
2877 }
2880 /* Let b = floor(b / divisor), and return the remainder. b must be nonnegative.
2881 * divisor must be between 1 and 65536.
2882 * This function cannot run out of memory. */
2883 static uint32
2884 divrem(Bigint *b, uint32 divisor)
2885 {
2886 int32 n = b->wds;
2887 uint32 remainder = 0;
2888 ULong *bx;
2889 ULong *bp;
2891 JS_ASSERT(divisor > 0 && divisor <= 65536);
2893 if (!n)
2894 return 0; /* b is zero */
2895 bx = b->x;
2896 bp = bx + n;
2897 do {
2898 ULong a = *--bp;
2899 ULong dividend = remainder << 16 | a >> 16;
2900 ULong quotientHi = dividend / divisor;
2901 ULong quotientLo;
2903 remainder = dividend - quotientHi*divisor;
2904 JS_ASSERT(quotientHi <= 0xFFFF && remainder < divisor);
2905 dividend = remainder << 16 | (a & 0xFFFF);
2906 quotientLo = dividend / divisor;
2907 remainder = dividend - quotientLo*divisor;
2908 JS_ASSERT(quotientLo <= 0xFFFF && remainder < divisor);
2909 *bp = quotientHi << 16 | quotientLo;
2910 } while (bp != bx);
2911 /* Decrease the size of the number if its most significant word is now zero. */
2912 if (bx[n-1] == 0)
2913 b->wds--;
2914 return remainder;
2915 }
2918 /* "-0.0000...(1073 zeros after decimal point)...0001\0" is the longest string that we could produce,
2919 * which occurs when printing -5e-324 in binary. We could compute a better estimate of the size of
2920 * the output string and malloc fewer bytes depending on d and base, but why bother? */
2921 #define DTOBASESTR_BUFFER_SIZE 1078
2922 #define BASEDIGIT(digit) ((char)(((digit) >= 10) ? 'a' - 10 + (digit) : '0' + (digit)))
2924 JS_FRIEND_API(char *)
2925 JS_dtobasestr(int base, double d)
2926 {
2927 char *buffer; /* The output string */
2928 char *p; /* Pointer to current position in the buffer */
2929 char *pInt; /* Pointer to the beginning of the integer part of the string */
2930 char *q;
2931 uint32 digit;
2932 double di; /* d truncated to an integer */
2933 double df; /* The fractional part of d */
2935 JS_ASSERT(base >= 2 && base <= 36);
2937 buffer = (char*) malloc(DTOBASESTR_BUFFER_SIZE);
2938 if (buffer) {
2939 p = buffer;
2940 if (d < 0.0
2941 #if defined(XP_WIN) || defined(XP_OS2)
2942 && !((word0(d) & Exp_mask) == Exp_mask && ((word0(d) & Frac_mask) || word1(d))) /* Visual C++ doesn't know how to compare against NaN */
2943 #endif
2944 ) {
2945 *p++ = '-';
2946 d = -d;
2947 }
2949 /* Check for Infinity and NaN */
2950 if ((word0(d) & Exp_mask) == Exp_mask) {
2951 strcpy(p, !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN");
2952 return buffer;
2953 }
2955 /* Locking for Balloc's shared buffers */
2956 ACQUIRE_DTOA_LOCK();
2958 /* Output the integer part of d with the digits in reverse order. */
2959 pInt = p;
2960 di = fd_floor(d);
2961 if (di <= 4294967295.0) {
2962 uint32 n = (uint32)di;
2963 if (n)
2964 do {
2965 uint32 m = n / base;
2966 digit = n - m*base;
2967 n = m;
2968 JS_ASSERT(digit < (uint32)base);
2969 *p++ = BASEDIGIT(digit);
2970 } while (n);
2971 else *p++ = '0';
2972 } else {
2973 int32 e;
2974 int32 bits; /* Number of significant bits in di; not used. */
2975 Bigint *b = d2b(di, &e, &bits);
2976 if (!b)
2977 goto nomem1;
2978 b = lshift(b, e);
2979 if (!b) {
2980 nomem1:
2981 Bfree(b);
2982 return NULL;
2983 }
2984 do {
2985 digit = divrem(b, base);
2986 JS_ASSERT(digit < (uint32)base);
2987 *p++ = BASEDIGIT(digit);
2988 } while (b->wds);
2989 Bfree(b);
2990 }
2991 /* Reverse the digits of the integer part of d. */
2992 q = p-1;
2993 while (q > pInt) {
2994 char ch = *pInt;
2995 *pInt++ = *q;
2996 *q-- = ch;
2997 }
2999 df = d - di;
3000 if (df != 0.0) {
3001 /* We have a fraction. */
3002 int32 e, bbits, s2, done;
3003 Bigint *b, *s, *mlo, *mhi;
3005 b = s = mlo = mhi = NULL;
3007 *p++ = '.';
3008 b = d2b(df, &e, &bbits);
3009 if (!b) {
3010 nomem2:
3011 Bfree(b);
3012 Bfree(s);
3013 if (mlo != mhi)
3014 Bfree(mlo);
3015 Bfree(mhi);
3016 return NULL;
3017 }
3018 JS_ASSERT(e < 0);
3019 /* At this point df = b * 2^e. e must be less than zero because 0 < df < 1. */
3021 s2 = -(int32)(word0(d) >> Exp_shift1 & Exp_mask>>Exp_shift1);
3022 #ifndef Sudden_Underflow
3023 if (!s2)
3024 s2 = -1;
3025 #endif
3026 s2 += Bias + P;
3027 /* 1/2^s2 = (nextDouble(d) - d)/2 */
3028 JS_ASSERT(-s2 < e);
3029 mlo = i2b(1);
3030 if (!mlo)
3031 goto nomem2;
3032 mhi = mlo;
3033 if (!word1(d) && !(word0(d) & Bndry_mask)
3034 #ifndef Sudden_Underflow
3035 && word0(d) & (Exp_mask & Exp_mask << 1)
3036 #endif
3037 ) {
3038 /* The special case. Here we want to be within a quarter of the last input
3039 significant digit instead of one half of it when the output string's value is less than d. */
3040 s2 += Log2P;
3041 mhi = i2b(1<<Log2P);
3042 if (!mhi)
3043 goto nomem2;
3044 }
3045 b = lshift(b, e + s2);
3046 if (!b)
3047 goto nomem2;
3048 s = i2b(1);
3049 if (!s)
3050 goto nomem2;
3051 s = lshift(s, s2);
3052 if (!s)
3053 goto nomem2;
3054 /* At this point we have the following:
3055 * s = 2^s2;
3056 * 1 > df = b/2^s2 > 0;
3057 * (d - prevDouble(d))/2 = mlo/2^s2;
3058 * (nextDouble(d) - d)/2 = mhi/2^s2. */
3060 done = JS_FALSE;
3061 do {
3062 int32 j, j1;
3063 Bigint *delta;
3065 b = multadd(b, base, 0);
3066 if (!b)
3067 goto nomem2;
3068 digit = quorem2(b, s2);
3069 if (mlo == mhi) {
3070 mlo = mhi = multadd(mlo, base, 0);
3071 if (!mhi)
3072 goto nomem2;
3073 }
3074 else {
3075 mlo = multadd(mlo, base, 0);
3076 if (!mlo)
3077 goto nomem2;
3078 mhi = multadd(mhi, base, 0);
3079 if (!mhi)
3080 goto nomem2;
3081 }
3083 /* Do we yet have the shortest string that will round to d? */
3084 j = cmp(b, mlo);
3085 /* j is b/2^s2 compared with mlo/2^s2. */
3086 delta = diff(s, mhi);
3087 if (!delta)
3088 goto nomem2;
3089 j1 = delta->sign ? 1 : cmp(b, delta);
3090 Bfree(delta);
3091 /* j1 is b/2^s2 compared with 1 - mhi/2^s2. */
3093 #ifndef ROUND_BIASED
3094 if (j1 == 0 && !(word1(d) & 1)) {
3095 if (j > 0)
3096 digit++;
3097 done = JS_TRUE;
3098 } else
3099 #endif
3100 if (j < 0 || (j == 0
3101 #ifndef ROUND_BIASED
3102 && !(word1(d) & 1)
3103 #endif
3104 )) {
3105 if (j1 > 0) {
3106 /* Either dig or dig+1 would work here as the least significant digit.
3107 Use whichever would produce an output value closer to d. */
3108 b = lshift(b, 1);
3109 if (!b)
3110 goto nomem2;
3111 j1 = cmp(b, s);
3112 if (j1 > 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here because it messes up odd base output
3113 * such as 3.5 in base 3. */
3114 digit++;
3115 }
3116 done = JS_TRUE;
3117 } else if (j1 > 0) {
3118 digit++;
3119 done = JS_TRUE;
3120 }
3121 JS_ASSERT(digit < (uint32)base);
3122 *p++ = BASEDIGIT(digit);
3123 } while (!done);
3124 Bfree(b);
3125 Bfree(s);
3126 if (mlo != mhi)
3127 Bfree(mlo);
3128 Bfree(mhi);
3129 }
3130 JS_ASSERT(p < buffer + DTOBASESTR_BUFFER_SIZE);
3131 *p = '\0';
3132 RELEASE_DTOA_LOCK();
3133 }
3134 return buffer;
3135 }