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