1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jsdtoa.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,511 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/*
1.11 + * Portable double to alphanumeric string and back converters.
1.12 + */
1.13 +
1.14 +#include "jsdtoa.h"
1.15 +
1.16 +#include "jsprf.h"
1.17 +#include "jstypes.h"
1.18 +#include "jsutil.h"
1.19 +
1.20 +using namespace js;
1.21 +
1.22 +#ifdef IS_LITTLE_ENDIAN
1.23 +#define IEEE_8087
1.24 +#else
1.25 +#define IEEE_MC68k
1.26 +#endif
1.27 +
1.28 +#ifndef Long
1.29 +#define Long int32_t
1.30 +#endif
1.31 +
1.32 +#ifndef ULong
1.33 +#define ULong uint32_t
1.34 +#endif
1.35 +
1.36 +/*
1.37 +#ifndef Llong
1.38 +#define Llong int64_t
1.39 +#endif
1.40 +
1.41 +#ifndef ULlong
1.42 +#define ULlong uint64_t
1.43 +#endif
1.44 +*/
1.45 +
1.46 +/*
1.47 + * MALLOC gets declared external, and that doesn't work for class members, so
1.48 + * wrap.
1.49 + */
1.50 +static inline void* dtoa_malloc(size_t size) { return js_malloc(size); }
1.51 +static inline void dtoa_free(void* p) { return js_free(p); }
1.52 +
1.53 +#define NO_GLOBAL_STATE
1.54 +#define NO_ERRNO
1.55 +#define MALLOC dtoa_malloc
1.56 +#define FREE dtoa_free
1.57 +#include "dtoa.c"
1.58 +
1.59 +/* Mapping of JSDToStrMode -> js_dtoa mode */
1.60 +static const uint8_t dtoaModes[] = {
1.61 + 0, /* DTOSTR_STANDARD */
1.62 + 0, /* DTOSTR_STANDARD_EXPONENTIAL, */
1.63 + 3, /* DTOSTR_FIXED, */
1.64 + 2, /* DTOSTR_EXPONENTIAL, */
1.65 + 2}; /* DTOSTR_PRECISION */
1.66 +
1.67 +double
1.68 +js_strtod_harder(DtoaState *state, const char *s00, char **se, int *err)
1.69 +{
1.70 + double retval;
1.71 + if (err)
1.72 + *err = 0;
1.73 + retval = _strtod(state, s00, se);
1.74 + return retval;
1.75 +}
1.76 +
1.77 +char *
1.78 +js_dtostr(DtoaState *state, char *buffer, size_t bufferSize, JSDToStrMode mode, int precision,
1.79 + double dinput)
1.80 +{
1.81 + U d;
1.82 + int decPt; /* Offset of decimal point from first digit */
1.83 + int sign; /* Nonzero if the sign bit was set in d */
1.84 + int nDigits; /* Number of significand digits returned by js_dtoa */
1.85 + char *numBegin; /* Pointer to the digits returned by js_dtoa */
1.86 + char *numEnd = 0; /* Pointer past the digits returned by js_dtoa */
1.87 +
1.88 + JS_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL
1.89 + ? DTOSTR_STANDARD_BUFFER_SIZE
1.90 + : DTOSTR_VARIABLE_BUFFER_SIZE(precision)));
1.91 +
1.92 + /*
1.93 + * Change mode here rather than below because the buffer may not be large
1.94 + * enough to hold a large integer.
1.95 + */
1.96 + if (mode == DTOSTR_FIXED && (dinput >= 1e21 || dinput <= -1e21))
1.97 + mode = DTOSTR_STANDARD;
1.98 +
1.99 + dval(d) = dinput;
1.100 + numBegin = dtoa(PASS_STATE d, dtoaModes[mode], precision, &decPt, &sign, &numEnd);
1.101 + if (!numBegin) {
1.102 + return nullptr;
1.103 + }
1.104 +
1.105 + nDigits = numEnd - numBegin;
1.106 + JS_ASSERT((size_t) nDigits <= bufferSize - 2);
1.107 + if ((size_t) nDigits > bufferSize - 2) {
1.108 + return nullptr;
1.109 + }
1.110 +
1.111 + js_memcpy(buffer + 2, numBegin, nDigits);
1.112 + freedtoa(PASS_STATE numBegin);
1.113 + numBegin = buffer + 2; /* +2 leaves space for sign and/or decimal point */
1.114 + numEnd = numBegin + nDigits;
1.115 + *numEnd = '\0';
1.116 +
1.117 + /* If Infinity, -Infinity, or NaN, return the string regardless of mode. */
1.118 + if (decPt != 9999) {
1.119 + bool exponentialNotation = false;
1.120 + int minNDigits = 0; /* Min number of significant digits required */
1.121 + char *p;
1.122 + char *q;
1.123 +
1.124 + switch (mode) {
1.125 + case DTOSTR_STANDARD:
1.126 + if (decPt < -5 || decPt > 21)
1.127 + exponentialNotation = true;
1.128 + else
1.129 + minNDigits = decPt;
1.130 + break;
1.131 +
1.132 + case DTOSTR_FIXED:
1.133 + if (precision >= 0)
1.134 + minNDigits = decPt + precision;
1.135 + else
1.136 + minNDigits = decPt;
1.137 + break;
1.138 +
1.139 + case DTOSTR_EXPONENTIAL:
1.140 + JS_ASSERT(precision > 0);
1.141 + minNDigits = precision;
1.142 + /* Fall through */
1.143 + case DTOSTR_STANDARD_EXPONENTIAL:
1.144 + exponentialNotation = true;
1.145 + break;
1.146 +
1.147 + case DTOSTR_PRECISION:
1.148 + JS_ASSERT(precision > 0);
1.149 + minNDigits = precision;
1.150 + if (decPt < -5 || decPt > precision)
1.151 + exponentialNotation = true;
1.152 + break;
1.153 + }
1.154 +
1.155 + /* If the number has fewer than minNDigits, end-pad it with zeros. */
1.156 + if (nDigits < minNDigits) {
1.157 + p = numBegin + minNDigits;
1.158 + nDigits = minNDigits;
1.159 + do {
1.160 + *numEnd++ = '0';
1.161 + } while (numEnd != p);
1.162 + *numEnd = '\0';
1.163 + }
1.164 +
1.165 + if (exponentialNotation) {
1.166 + /* Insert a decimal point if more than one significand digit */
1.167 + if (nDigits != 1) {
1.168 + numBegin--;
1.169 + numBegin[0] = numBegin[1];
1.170 + numBegin[1] = '.';
1.171 + }
1.172 + JS_snprintf(numEnd, bufferSize - (numEnd - buffer), "e%+d", decPt-1);
1.173 + } else if (decPt != nDigits) {
1.174 + /* Some kind of a fraction in fixed notation */
1.175 + JS_ASSERT(decPt <= nDigits);
1.176 + if (decPt > 0) {
1.177 + /* dd...dd . dd...dd */
1.178 + p = --numBegin;
1.179 + do {
1.180 + *p = p[1];
1.181 + p++;
1.182 + } while (--decPt);
1.183 + *p = '.';
1.184 + } else {
1.185 + /* 0 . 00...00dd...dd */
1.186 + p = numEnd;
1.187 + numEnd += 1 - decPt;
1.188 + q = numEnd;
1.189 + JS_ASSERT(numEnd < buffer + bufferSize);
1.190 + *numEnd = '\0';
1.191 + while (p != numBegin)
1.192 + *--q = *--p;
1.193 + for (p = numBegin + 1; p != q; p++)
1.194 + *p = '0';
1.195 + *numBegin = '.';
1.196 + *--numBegin = '0';
1.197 + }
1.198 + }
1.199 + }
1.200 +
1.201 + /* If negative and neither -0.0 nor NaN, output a leading '-'. */
1.202 + if (sign &&
1.203 + !(word0(d) == Sign_bit && word1(d) == 0) &&
1.204 + !((word0(d) & Exp_mask) == Exp_mask &&
1.205 + (word1(d) || (word0(d) & Frac_mask)))) {
1.206 + *--numBegin = '-';
1.207 + }
1.208 + return numBegin;
1.209 +}
1.210 +
1.211 +
1.212 +/* Let b = floor(b / divisor), and return the remainder. b must be nonnegative.
1.213 + * divisor must be between 1 and 65536.
1.214 + * This function cannot run out of memory. */
1.215 +static uint32_t
1.216 +divrem(Bigint *b, uint32_t divisor)
1.217 +{
1.218 + int32_t n = b->wds;
1.219 + uint32_t remainder = 0;
1.220 + ULong *bx;
1.221 + ULong *bp;
1.222 +
1.223 + JS_ASSERT(divisor > 0 && divisor <= 65536);
1.224 +
1.225 + if (!n)
1.226 + return 0; /* b is zero */
1.227 + bx = b->x;
1.228 + bp = bx + n;
1.229 + do {
1.230 + ULong a = *--bp;
1.231 + ULong dividend = remainder << 16 | a >> 16;
1.232 + ULong quotientHi = dividend / divisor;
1.233 + ULong quotientLo;
1.234 +
1.235 + remainder = dividend - quotientHi*divisor;
1.236 + JS_ASSERT(quotientHi <= 0xFFFF && remainder < divisor);
1.237 + dividend = remainder << 16 | (a & 0xFFFF);
1.238 + quotientLo = dividend / divisor;
1.239 + remainder = dividend - quotientLo*divisor;
1.240 + JS_ASSERT(quotientLo <= 0xFFFF && remainder < divisor);
1.241 + *bp = quotientHi << 16 | quotientLo;
1.242 + } while (bp != bx);
1.243 + /* Decrease the size of the number if its most significant word is now zero. */
1.244 + if (bx[n-1] == 0)
1.245 + b->wds--;
1.246 + return remainder;
1.247 +}
1.248 +
1.249 +/* Return floor(b/2^k) and set b to be the remainder. The returned quotient must be less than 2^32. */
1.250 +static uint32_t quorem2(Bigint *b, int32_t k)
1.251 +{
1.252 + ULong mask;
1.253 + ULong result;
1.254 + ULong *bx, *bxe;
1.255 + int32_t w;
1.256 + int32_t n = k >> 5;
1.257 + k &= 0x1F;
1.258 + mask = (1<<k) - 1;
1.259 +
1.260 + w = b->wds - n;
1.261 + if (w <= 0)
1.262 + return 0;
1.263 + JS_ASSERT(w <= 2);
1.264 + bx = b->x;
1.265 + bxe = bx + n;
1.266 + result = *bxe >> k;
1.267 + *bxe &= mask;
1.268 + if (w == 2) {
1.269 + JS_ASSERT(!(bxe[1] & ~mask));
1.270 + if (k)
1.271 + result |= bxe[1] << (32 - k);
1.272 + }
1.273 + n++;
1.274 + while (!*bxe && bxe != bx) {
1.275 + n--;
1.276 + bxe--;
1.277 + }
1.278 + b->wds = n;
1.279 + return result;
1.280 +}
1.281 +
1.282 +
1.283 +/* "-0.0000...(1073 zeros after decimal point)...0001\0" is the longest string that we could produce,
1.284 + * which occurs when printing -5e-324 in binary. We could compute a better estimate of the size of
1.285 + * the output string and malloc fewer bytes depending on d and base, but why bother? */
1.286 +#define DTOBASESTR_BUFFER_SIZE 1078
1.287 +#define BASEDIGIT(digit) ((char)(((digit) >= 10) ? 'a' - 10 + (digit) : '0' + (digit)))
1.288 +
1.289 +char *
1.290 +js_dtobasestr(DtoaState *state, int base, double dinput)
1.291 +{
1.292 + U d;
1.293 + char *buffer; /* The output string */
1.294 + char *p; /* Pointer to current position in the buffer */
1.295 + char *pInt; /* Pointer to the beginning of the integer part of the string */
1.296 + char *q;
1.297 + uint32_t digit;
1.298 + U di; /* d truncated to an integer */
1.299 + U df; /* The fractional part of d */
1.300 +
1.301 + JS_ASSERT(base >= 2 && base <= 36);
1.302 +
1.303 + dval(d) = dinput;
1.304 + buffer = (char*) js_malloc(DTOBASESTR_BUFFER_SIZE);
1.305 + if (!buffer)
1.306 + return nullptr;
1.307 + p = buffer;
1.308 +
1.309 + if (dval(d) < 0.0
1.310 +#if defined(XP_WIN)
1.311 + && !((word0(d) & Exp_mask) == Exp_mask && ((word0(d) & Frac_mask) || word1(d))) /* Visual C++ doesn't know how to compare against NaN */
1.312 +#endif
1.313 + ) {
1.314 + *p++ = '-';
1.315 + dval(d) = -dval(d);
1.316 + }
1.317 +
1.318 + /* Check for Infinity and NaN */
1.319 + if ((word0(d) & Exp_mask) == Exp_mask) {
1.320 + strcpy(p, !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN");
1.321 + return buffer;
1.322 + }
1.323 +
1.324 + /* Output the integer part of d with the digits in reverse order. */
1.325 + pInt = p;
1.326 + dval(di) = floor(dval(d));
1.327 + if (dval(di) <= 4294967295.0) {
1.328 + uint32_t n = (uint32_t)dval(di);
1.329 + if (n)
1.330 + do {
1.331 + uint32_t m = n / base;
1.332 + digit = n - m*base;
1.333 + n = m;
1.334 + JS_ASSERT(digit < (uint32_t)base);
1.335 + *p++ = BASEDIGIT(digit);
1.336 + } while (n);
1.337 + else *p++ = '0';
1.338 + } else {
1.339 + int e;
1.340 + int bits; /* Number of significant bits in di; not used. */
1.341 + Bigint *b = d2b(PASS_STATE di, &e, &bits);
1.342 + if (!b)
1.343 + goto nomem1;
1.344 + b = lshift(PASS_STATE b, e);
1.345 + if (!b) {
1.346 + nomem1:
1.347 + Bfree(PASS_STATE b);
1.348 + js_free(buffer);
1.349 + return nullptr;
1.350 + }
1.351 + do {
1.352 + digit = divrem(b, base);
1.353 + JS_ASSERT(digit < (uint32_t)base);
1.354 + *p++ = BASEDIGIT(digit);
1.355 + } while (b->wds);
1.356 + Bfree(PASS_STATE b);
1.357 + }
1.358 + /* Reverse the digits of the integer part of d. */
1.359 + q = p-1;
1.360 + while (q > pInt) {
1.361 + char ch = *pInt;
1.362 + *pInt++ = *q;
1.363 + *q-- = ch;
1.364 + }
1.365 +
1.366 + dval(df) = dval(d) - dval(di);
1.367 + if (dval(df) != 0.0) {
1.368 + /* We have a fraction. */
1.369 + int e, bbits;
1.370 + int32_t s2, done;
1.371 + Bigint *b, *s, *mlo, *mhi;
1.372 +
1.373 + b = s = mlo = mhi = nullptr;
1.374 +
1.375 + *p++ = '.';
1.376 + b = d2b(PASS_STATE df, &e, &bbits);
1.377 + if (!b) {
1.378 + nomem2:
1.379 + Bfree(PASS_STATE b);
1.380 + Bfree(PASS_STATE s);
1.381 + if (mlo != mhi)
1.382 + Bfree(PASS_STATE mlo);
1.383 + Bfree(PASS_STATE mhi);
1.384 + js_free(buffer);
1.385 + return nullptr;
1.386 + }
1.387 + JS_ASSERT(e < 0);
1.388 + /* At this point df = b * 2^e. e must be less than zero because 0 < df < 1. */
1.389 +
1.390 + s2 = -(int32_t)(word0(d) >> Exp_shift1 & Exp_mask>>Exp_shift1);
1.391 +#ifndef Sudden_Underflow
1.392 + if (!s2)
1.393 + s2 = -1;
1.394 +#endif
1.395 + s2 += Bias + P;
1.396 + /* 1/2^s2 = (nextDouble(d) - d)/2 */
1.397 + JS_ASSERT(-s2 < e);
1.398 + mlo = i2b(PASS_STATE 1);
1.399 + if (!mlo)
1.400 + goto nomem2;
1.401 + mhi = mlo;
1.402 + if (!word1(d) && !(word0(d) & Bndry_mask)
1.403 +#ifndef Sudden_Underflow
1.404 + && word0(d) & (Exp_mask & Exp_mask << 1)
1.405 +#endif
1.406 + ) {
1.407 + /* The special case. Here we want to be within a quarter of the last input
1.408 + significant digit instead of one half of it when the output string's value is less than d. */
1.409 + s2 += Log2P;
1.410 + mhi = i2b(PASS_STATE 1<<Log2P);
1.411 + if (!mhi)
1.412 + goto nomem2;
1.413 + }
1.414 + b = lshift(PASS_STATE b, e + s2);
1.415 + if (!b)
1.416 + goto nomem2;
1.417 + s = i2b(PASS_STATE 1);
1.418 + if (!s)
1.419 + goto nomem2;
1.420 + s = lshift(PASS_STATE s, s2);
1.421 + if (!s)
1.422 + goto nomem2;
1.423 + /* At this point we have the following:
1.424 + * s = 2^s2;
1.425 + * 1 > df = b/2^s2 > 0;
1.426 + * (d - prevDouble(d))/2 = mlo/2^s2;
1.427 + * (nextDouble(d) - d)/2 = mhi/2^s2. */
1.428 +
1.429 + done = false;
1.430 + do {
1.431 + int32_t j, j1;
1.432 + Bigint *delta;
1.433 +
1.434 + b = multadd(PASS_STATE b, base, 0);
1.435 + if (!b)
1.436 + goto nomem2;
1.437 + digit = quorem2(b, s2);
1.438 + if (mlo == mhi) {
1.439 + mlo = mhi = multadd(PASS_STATE mlo, base, 0);
1.440 + if (!mhi)
1.441 + goto nomem2;
1.442 + }
1.443 + else {
1.444 + mlo = multadd(PASS_STATE mlo, base, 0);
1.445 + if (!mlo)
1.446 + goto nomem2;
1.447 + mhi = multadd(PASS_STATE mhi, base, 0);
1.448 + if (!mhi)
1.449 + goto nomem2;
1.450 + }
1.451 +
1.452 + /* Do we yet have the shortest string that will round to d? */
1.453 + j = cmp(b, mlo);
1.454 + /* j is b/2^s2 compared with mlo/2^s2. */
1.455 + delta = diff(PASS_STATE s, mhi);
1.456 + if (!delta)
1.457 + goto nomem2;
1.458 + j1 = delta->sign ? 1 : cmp(b, delta);
1.459 + Bfree(PASS_STATE delta);
1.460 + /* j1 is b/2^s2 compared with 1 - mhi/2^s2. */
1.461 +
1.462 +#ifndef ROUND_BIASED
1.463 + if (j1 == 0 && !(word1(d) & 1)) {
1.464 + if (j > 0)
1.465 + digit++;
1.466 + done = true;
1.467 + } else
1.468 +#endif
1.469 + if (j < 0 || (j == 0
1.470 +#ifndef ROUND_BIASED
1.471 + && !(word1(d) & 1)
1.472 +#endif
1.473 + )) {
1.474 + if (j1 > 0) {
1.475 + /* Either dig or dig+1 would work here as the least significant digit.
1.476 + Use whichever would produce an output value closer to d. */
1.477 + b = lshift(PASS_STATE b, 1);
1.478 + if (!b)
1.479 + goto nomem2;
1.480 + j1 = cmp(b, s);
1.481 + if (j1 > 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here because it messes up odd base output
1.482 + * such as 3.5 in base 3. */
1.483 + digit++;
1.484 + }
1.485 + done = true;
1.486 + } else if (j1 > 0) {
1.487 + digit++;
1.488 + done = true;
1.489 + }
1.490 + JS_ASSERT(digit < (uint32_t)base);
1.491 + *p++ = BASEDIGIT(digit);
1.492 + } while (!done);
1.493 + Bfree(PASS_STATE b);
1.494 + Bfree(PASS_STATE s);
1.495 + if (mlo != mhi)
1.496 + Bfree(PASS_STATE mlo);
1.497 + Bfree(PASS_STATE mhi);
1.498 + }
1.499 + JS_ASSERT(p < buffer + DTOBASESTR_BUFFER_SIZE);
1.500 + *p = '\0';
1.501 + return buffer;
1.502 +}
1.503 +
1.504 +DtoaState *
1.505 +js_NewDtoaState()
1.506 +{
1.507 + return newdtoa();
1.508 +}
1.509 +
1.510 +void
1.511 +js_DestroyDtoaState(DtoaState *state)
1.512 +{
1.513 + destroydtoa(state);
1.514 +}
