michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0:  * Portable double to alphanumeric string and back converters.
michael@0:  */
michael@0: 
michael@0: #include "jsdtoa.h"
michael@0: 
michael@0: #include "jsprf.h"
michael@0: #include "jstypes.h"
michael@0: #include "jsutil.h"
michael@0: 
michael@0: using namespace js;
michael@0: 
michael@0: #ifdef IS_LITTLE_ENDIAN
michael@0: #define IEEE_8087
michael@0: #else
michael@0: #define IEEE_MC68k
michael@0: #endif
michael@0: 
michael@0: #ifndef Long
michael@0: #define Long int32_t
michael@0: #endif
michael@0: 
michael@0: #ifndef ULong
michael@0: #define ULong uint32_t
michael@0: #endif
michael@0: 
michael@0: /*
michael@0: #ifndef Llong
michael@0: #define Llong int64_t
michael@0: #endif
michael@0: 
michael@0: #ifndef ULlong
michael@0: #define ULlong uint64_t
michael@0: #endif
michael@0: */
michael@0: 
michael@0: /*
michael@0:  * MALLOC gets declared external, and that doesn't work for class members, so
michael@0:  * wrap.
michael@0:  */
michael@0: static inline void* dtoa_malloc(size_t size) { return js_malloc(size); }
michael@0: static inline void dtoa_free(void* p) { return js_free(p); }
michael@0: 
michael@0: #define NO_GLOBAL_STATE
michael@0: #define NO_ERRNO
michael@0: #define MALLOC dtoa_malloc
michael@0: #define FREE dtoa_free
michael@0: #include "dtoa.c"
michael@0: 
michael@0: /* Mapping of JSDToStrMode -> js_dtoa mode */
michael@0: static const uint8_t dtoaModes[] = {
michael@0:     0,   /* DTOSTR_STANDARD */
michael@0:     0,   /* DTOSTR_STANDARD_EXPONENTIAL, */
michael@0:     3,   /* DTOSTR_FIXED, */
michael@0:     2,   /* DTOSTR_EXPONENTIAL, */
michael@0:     2};  /* DTOSTR_PRECISION */
michael@0: 
michael@0: double
michael@0: js_strtod_harder(DtoaState *state, const char *s00, char **se, int *err)
michael@0: {
michael@0:     double retval;
michael@0:     if (err)
michael@0:         *err = 0;
michael@0:     retval = _strtod(state, s00, se);
michael@0:     return retval;
michael@0: }
michael@0: 
michael@0: char *
michael@0: js_dtostr(DtoaState *state, char *buffer, size_t bufferSize, JSDToStrMode mode, int precision,
michael@0:           double dinput)
michael@0: {
michael@0:     U d;
michael@0:     int decPt;        /* Offset of decimal point from first digit */
michael@0:     int sign;         /* Nonzero if the sign bit was set in d */
michael@0:     int nDigits;      /* Number of significand digits returned by js_dtoa */
michael@0:     char *numBegin;   /* Pointer to the digits returned by js_dtoa */
michael@0:     char *numEnd = 0; /* Pointer past the digits returned by js_dtoa */
michael@0: 
michael@0:     JS_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL
michael@0:                                     ? DTOSTR_STANDARD_BUFFER_SIZE
michael@0:                                     : DTOSTR_VARIABLE_BUFFER_SIZE(precision)));
michael@0: 
michael@0:     /*
michael@0:      * Change mode here rather than below because the buffer may not be large
michael@0:      * enough to hold a large integer.
michael@0:      */
michael@0:     if (mode == DTOSTR_FIXED && (dinput >= 1e21 || dinput <= -1e21))
michael@0:         mode = DTOSTR_STANDARD;
michael@0: 
michael@0:     dval(d) = dinput;
michael@0:     numBegin = dtoa(PASS_STATE d, dtoaModes[mode], precision, &decPt, &sign, &numEnd);
michael@0:     if (!numBegin) {
michael@0:         return nullptr;
michael@0:     }
michael@0: 
michael@0:     nDigits = numEnd - numBegin;
michael@0:     JS_ASSERT((size_t) nDigits <= bufferSize - 2);
michael@0:     if ((size_t) nDigits > bufferSize - 2) {
michael@0:         return nullptr;
michael@0:     }
michael@0: 
michael@0:     js_memcpy(buffer + 2, numBegin, nDigits);
michael@0:     freedtoa(PASS_STATE numBegin);
michael@0:     numBegin = buffer + 2; /* +2 leaves space for sign and/or decimal point */
michael@0:     numEnd = numBegin + nDigits;
michael@0:     *numEnd = '\0';
michael@0: 
michael@0:     /* If Infinity, -Infinity, or NaN, return the string regardless of mode. */
michael@0:     if (decPt != 9999) {
michael@0:         bool exponentialNotation = false;
michael@0:         int minNDigits = 0;  /* Min number of significant digits required */
michael@0:         char *p;
michael@0:         char *q;
michael@0: 
michael@0:         switch (mode) {
michael@0:             case DTOSTR_STANDARD:
michael@0:                 if (decPt < -5 || decPt > 21)
michael@0:                     exponentialNotation = true;
michael@0:                 else
michael@0:                     minNDigits = decPt;
michael@0:                 break;
michael@0: 
michael@0:             case DTOSTR_FIXED:
michael@0:                 if (precision >= 0)
michael@0:                     minNDigits = decPt + precision;
michael@0:                 else
michael@0:                     minNDigits = decPt;
michael@0:                 break;
michael@0: 
michael@0:             case DTOSTR_EXPONENTIAL:
michael@0:                 JS_ASSERT(precision > 0);
michael@0:                 minNDigits = precision;
michael@0:                 /* Fall through */
michael@0:             case DTOSTR_STANDARD_EXPONENTIAL:
michael@0:                 exponentialNotation = true;
michael@0:                 break;
michael@0: 
michael@0:             case DTOSTR_PRECISION:
michael@0:                 JS_ASSERT(precision > 0);
michael@0:                 minNDigits = precision;
michael@0:                 if (decPt < -5 || decPt > precision)
michael@0:                     exponentialNotation = true;
michael@0:                 break;
michael@0:         }
michael@0: 
michael@0:         /* If the number has fewer than minNDigits, end-pad it with zeros. */
michael@0:         if (nDigits < minNDigits) {
michael@0:             p = numBegin + minNDigits;
michael@0:             nDigits = minNDigits;
michael@0:             do {
michael@0:                 *numEnd++ = '0';
michael@0:             } while (numEnd != p);
michael@0:             *numEnd = '\0';
michael@0:         }
michael@0: 
michael@0:         if (exponentialNotation) {
michael@0:             /* Insert a decimal point if more than one significand digit */
michael@0:             if (nDigits != 1) {
michael@0:                 numBegin--;
michael@0:                 numBegin[0] = numBegin[1];
michael@0:                 numBegin[1] = '.';
michael@0:             }
michael@0:             JS_snprintf(numEnd, bufferSize - (numEnd - buffer), "e%+d", decPt-1);
michael@0:         } else if (decPt != nDigits) {
michael@0:             /* Some kind of a fraction in fixed notation */
michael@0:             JS_ASSERT(decPt <= nDigits);
michael@0:             if (decPt > 0) {
michael@0:                 /* dd...dd . dd...dd */
michael@0:                 p = --numBegin;
michael@0:                 do {
michael@0:                     *p = p[1];
michael@0:                     p++;
michael@0:                 } while (--decPt);
michael@0:                 *p = '.';
michael@0:             } else {
michael@0:                 /* 0 . 00...00dd...dd */
michael@0:                 p = numEnd;
michael@0:                 numEnd += 1 - decPt;
michael@0:                 q = numEnd;
michael@0:                 JS_ASSERT(numEnd < buffer + bufferSize);
michael@0:                 *numEnd = '\0';
michael@0:                 while (p != numBegin)
michael@0:                     *--q = *--p;
michael@0:                 for (p = numBegin + 1; p != q; p++)
michael@0:                     *p = '0';
michael@0:                 *numBegin = '.';
michael@0:                 *--numBegin = '0';
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* If negative and neither -0.0 nor NaN, output a leading '-'. */
michael@0:     if (sign &&
michael@0:             !(word0(d) == Sign_bit && word1(d) == 0) &&
michael@0:             !((word0(d) & Exp_mask) == Exp_mask &&
michael@0:               (word1(d) || (word0(d) & Frac_mask)))) {
michael@0:         *--numBegin = '-';
michael@0:     }
michael@0:     return numBegin;
michael@0: }
michael@0: 
michael@0: 
michael@0: /* Let b = floor(b / divisor), and return the remainder.  b must be nonnegative.
michael@0:  * divisor must be between 1 and 65536.
michael@0:  * This function cannot run out of memory. */
michael@0: static uint32_t
michael@0: divrem(Bigint *b, uint32_t divisor)
michael@0: {
michael@0:     int32_t n = b->wds;
michael@0:     uint32_t remainder = 0;
michael@0:     ULong *bx;
michael@0:     ULong *bp;
michael@0: 
michael@0:     JS_ASSERT(divisor > 0 && divisor <= 65536);
michael@0: 
michael@0:     if (!n)
michael@0:         return 0; /* b is zero */
michael@0:     bx = b->x;
michael@0:     bp = bx + n;
michael@0:     do {
michael@0:         ULong a = *--bp;
michael@0:         ULong dividend = remainder << 16 | a >> 16;
michael@0:         ULong quotientHi = dividend / divisor;
michael@0:         ULong quotientLo;
michael@0: 
michael@0:         remainder = dividend - quotientHi*divisor;
michael@0:         JS_ASSERT(quotientHi <= 0xFFFF && remainder < divisor);
michael@0:         dividend = remainder << 16 | (a & 0xFFFF);
michael@0:         quotientLo = dividend / divisor;
michael@0:         remainder = dividend - quotientLo*divisor;
michael@0:         JS_ASSERT(quotientLo <= 0xFFFF && remainder < divisor);
michael@0:         *bp = quotientHi << 16 | quotientLo;
michael@0:     } while (bp != bx);
michael@0:     /* Decrease the size of the number if its most significant word is now zero. */
michael@0:     if (bx[n-1] == 0)
michael@0:         b->wds--;
michael@0:     return remainder;
michael@0: }
michael@0: 
michael@0: /* Return floor(b/2^k) and set b to be the remainder.  The returned quotient must be less than 2^32. */
michael@0: static uint32_t quorem2(Bigint *b, int32_t k)
michael@0: {
michael@0:     ULong mask;
michael@0:     ULong result;
michael@0:     ULong *bx, *bxe;
michael@0:     int32_t w;
michael@0:     int32_t n = k >> 5;
michael@0:     k &= 0x1F;
michael@0:     mask = (1<<k) - 1;
michael@0: 
michael@0:     w = b->wds - n;
michael@0:     if (w <= 0)
michael@0:         return 0;
michael@0:     JS_ASSERT(w <= 2);
michael@0:     bx = b->x;
michael@0:     bxe = bx + n;
michael@0:     result = *bxe >> k;
michael@0:     *bxe &= mask;
michael@0:     if (w == 2) {
michael@0:         JS_ASSERT(!(bxe[1] & ~mask));
michael@0:         if (k)
michael@0:             result |= bxe[1] << (32 - k);
michael@0:     }
michael@0:     n++;
michael@0:     while (!*bxe && bxe != bx) {
michael@0:         n--;
michael@0:         bxe--;
michael@0:     }
michael@0:     b->wds = n;
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: 
michael@0: /* "-0.0000...(1073 zeros after decimal point)...0001\0" is the longest string that we could produce,
michael@0:  * which occurs when printing -5e-324 in binary.  We could compute a better estimate of the size of
michael@0:  * the output string and malloc fewer bytes depending on d and base, but why bother? */
michael@0: #define DTOBASESTR_BUFFER_SIZE 1078
michael@0: #define BASEDIGIT(digit) ((char)(((digit) >= 10) ? 'a' - 10 + (digit) : '0' + (digit)))
michael@0: 
michael@0: char *
michael@0: js_dtobasestr(DtoaState *state, int base, double dinput)
michael@0: {
michael@0:     U d;
michael@0:     char *buffer;        /* The output string */
michael@0:     char *p;             /* Pointer to current position in the buffer */
michael@0:     char *pInt;          /* Pointer to the beginning of the integer part of the string */
michael@0:     char *q;
michael@0:     uint32_t digit;
michael@0:     U di;                /* d truncated to an integer */
michael@0:     U df;                /* The fractional part of d */
michael@0: 
michael@0:     JS_ASSERT(base >= 2 && base <= 36);
michael@0: 
michael@0:     dval(d) = dinput;
michael@0:     buffer = (char*) js_malloc(DTOBASESTR_BUFFER_SIZE);
michael@0:     if (!buffer)
michael@0:         return nullptr;
michael@0:     p = buffer;
michael@0: 
michael@0:     if (dval(d) < 0.0
michael@0: #if defined(XP_WIN)
michael@0:         && !((word0(d) & Exp_mask) == Exp_mask && ((word0(d) & Frac_mask) || word1(d))) /* Visual C++ doesn't know how to compare against NaN */
michael@0: #endif
michael@0:        ) {
michael@0:         *p++ = '-';
michael@0:         dval(d) = -dval(d);
michael@0:     }
michael@0: 
michael@0:     /* Check for Infinity and NaN */
michael@0:     if ((word0(d) & Exp_mask) == Exp_mask) {
michael@0:         strcpy(p, !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN");
michael@0:         return buffer;
michael@0:     }
michael@0: 
michael@0:     /* Output the integer part of d with the digits in reverse order. */
michael@0:     pInt = p;
michael@0:     dval(di) = floor(dval(d));
michael@0:     if (dval(di) <= 4294967295.0) {
michael@0:         uint32_t n = (uint32_t)dval(di);
michael@0:         if (n)
michael@0:             do {
michael@0:                 uint32_t m = n / base;
michael@0:                 digit = n - m*base;
michael@0:                 n = m;
michael@0:                 JS_ASSERT(digit < (uint32_t)base);
michael@0:                 *p++ = BASEDIGIT(digit);
michael@0:             } while (n);
michael@0:         else *p++ = '0';
michael@0:     } else {
michael@0:         int e;
michael@0:         int bits;  /* Number of significant bits in di; not used. */
michael@0:         Bigint *b = d2b(PASS_STATE di, &e, &bits);
michael@0:         if (!b)
michael@0:             goto nomem1;
michael@0:         b = lshift(PASS_STATE b, e);
michael@0:         if (!b) {
michael@0:           nomem1:
michael@0:             Bfree(PASS_STATE b);
michael@0:             js_free(buffer);
michael@0:             return nullptr;
michael@0:         }
michael@0:         do {
michael@0:             digit = divrem(b, base);
michael@0:             JS_ASSERT(digit < (uint32_t)base);
michael@0:             *p++ = BASEDIGIT(digit);
michael@0:         } while (b->wds);
michael@0:         Bfree(PASS_STATE b);
michael@0:     }
michael@0:     /* Reverse the digits of the integer part of d. */
michael@0:     q = p-1;
michael@0:     while (q > pInt) {
michael@0:         char ch = *pInt;
michael@0:         *pInt++ = *q;
michael@0:         *q-- = ch;
michael@0:     }
michael@0: 
michael@0:     dval(df) = dval(d) - dval(di);
michael@0:     if (dval(df) != 0.0) {
michael@0:         /* We have a fraction. */
michael@0:         int e, bbits;
michael@0:         int32_t s2, done;
michael@0:         Bigint *b, *s, *mlo, *mhi;
michael@0: 
michael@0:         b = s = mlo = mhi = nullptr;
michael@0: 
michael@0:         *p++ = '.';
michael@0:         b = d2b(PASS_STATE df, &e, &bbits);
michael@0:         if (!b) {
michael@0:           nomem2:
michael@0:             Bfree(PASS_STATE b);
michael@0:             Bfree(PASS_STATE s);
michael@0:             if (mlo != mhi)
michael@0:                 Bfree(PASS_STATE mlo);
michael@0:             Bfree(PASS_STATE mhi);
michael@0:             js_free(buffer);
michael@0:             return nullptr;
michael@0:         }
michael@0:         JS_ASSERT(e < 0);
michael@0:         /* At this point df = b * 2^e.  e must be less than zero because 0 < df < 1. */
michael@0: 
michael@0:         s2 = -(int32_t)(word0(d) >> Exp_shift1 & Exp_mask>>Exp_shift1);
michael@0: #ifndef Sudden_Underflow
michael@0:         if (!s2)
michael@0:             s2 = -1;
michael@0: #endif
michael@0:         s2 += Bias + P;
michael@0:         /* 1/2^s2 = (nextDouble(d) - d)/2 */
michael@0:         JS_ASSERT(-s2 < e);
michael@0:         mlo = i2b(PASS_STATE 1);
michael@0:         if (!mlo)
michael@0:             goto nomem2;
michael@0:         mhi = mlo;
michael@0:         if (!word1(d) && !(word0(d) & Bndry_mask)
michael@0: #ifndef Sudden_Underflow
michael@0:             && word0(d) & (Exp_mask & Exp_mask << 1)
michael@0: #endif
michael@0:             ) {
michael@0:             /* The special case.  Here we want to be within a quarter of the last input
michael@0:                significant digit instead of one half of it when the output string's value is less than d.  */
michael@0:             s2 += Log2P;
michael@0:             mhi = i2b(PASS_STATE 1<<Log2P);
michael@0:             if (!mhi)
michael@0:                 goto nomem2;
michael@0:         }
michael@0:         b = lshift(PASS_STATE b, e + s2);
michael@0:         if (!b)
michael@0:             goto nomem2;
michael@0:         s = i2b(PASS_STATE 1);
michael@0:         if (!s)
michael@0:             goto nomem2;
michael@0:         s = lshift(PASS_STATE s, s2);
michael@0:         if (!s)
michael@0:             goto nomem2;
michael@0:         /* At this point we have the following:
michael@0:          *   s = 2^s2;
michael@0:          *   1 > df = b/2^s2 > 0;
michael@0:          *   (d - prevDouble(d))/2 = mlo/2^s2;
michael@0:          *   (nextDouble(d) - d)/2 = mhi/2^s2. */
michael@0: 
michael@0:         done = false;
michael@0:         do {
michael@0:             int32_t j, j1;
michael@0:             Bigint *delta;
michael@0: 
michael@0:             b = multadd(PASS_STATE b, base, 0);
michael@0:             if (!b)
michael@0:                 goto nomem2;
michael@0:             digit = quorem2(b, s2);
michael@0:             if (mlo == mhi) {
michael@0:                 mlo = mhi = multadd(PASS_STATE mlo, base, 0);
michael@0:                 if (!mhi)
michael@0:                     goto nomem2;
michael@0:             }
michael@0:             else {
michael@0:                 mlo = multadd(PASS_STATE mlo, base, 0);
michael@0:                 if (!mlo)
michael@0:                     goto nomem2;
michael@0:                 mhi = multadd(PASS_STATE mhi, base, 0);
michael@0:                 if (!mhi)
michael@0:                     goto nomem2;
michael@0:             }
michael@0: 
michael@0:             /* Do we yet have the shortest string that will round to d? */
michael@0:             j = cmp(b, mlo);
michael@0:             /* j is b/2^s2 compared with mlo/2^s2. */
michael@0:             delta = diff(PASS_STATE s, mhi);
michael@0:             if (!delta)
michael@0:                 goto nomem2;
michael@0:             j1 = delta->sign ? 1 : cmp(b, delta);
michael@0:             Bfree(PASS_STATE delta);
michael@0:             /* j1 is b/2^s2 compared with 1 - mhi/2^s2. */
michael@0: 
michael@0: #ifndef ROUND_BIASED
michael@0:             if (j1 == 0 && !(word1(d) & 1)) {
michael@0:                 if (j > 0)
michael@0:                     digit++;
michael@0:                 done = true;
michael@0:             } else
michael@0: #endif
michael@0:             if (j < 0 || (j == 0
michael@0: #ifndef ROUND_BIASED
michael@0:                 && !(word1(d) & 1)
michael@0: #endif
michael@0:                 )) {
michael@0:                 if (j1 > 0) {
michael@0:                     /* Either dig or dig+1 would work here as the least significant digit.
michael@0:                        Use whichever would produce an output value closer to d. */
michael@0:                     b = lshift(PASS_STATE b, 1);
michael@0:                     if (!b)
michael@0:                         goto nomem2;
michael@0:                     j1 = cmp(b, s);
michael@0:                     if (j1 > 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here because it messes up odd base output
michael@0:                                  * such as 3.5 in base 3.  */
michael@0:                         digit++;
michael@0:                 }
michael@0:                 done = true;
michael@0:             } else if (j1 > 0) {
michael@0:                 digit++;
michael@0:                 done = true;
michael@0:             }
michael@0:             JS_ASSERT(digit < (uint32_t)base);
michael@0:             *p++ = BASEDIGIT(digit);
michael@0:         } while (!done);
michael@0:         Bfree(PASS_STATE b);
michael@0:         Bfree(PASS_STATE s);
michael@0:         if (mlo != mhi)
michael@0:             Bfree(PASS_STATE mlo);
michael@0:         Bfree(PASS_STATE mhi);
michael@0:     }
michael@0:     JS_ASSERT(p < buffer + DTOBASESTR_BUFFER_SIZE);
michael@0:     *p = '\0';
michael@0:     return buffer;
michael@0: }
michael@0: 
michael@0: DtoaState *
michael@0: js_NewDtoaState()
michael@0: {
michael@0:     return newdtoa();
michael@0: }
michael@0: 
michael@0: void
michael@0: js_DestroyDtoaState(DtoaState *state)
michael@0: {
michael@0:     destroydtoa(state);
michael@0: }