js/src/jsdtoa.cpp

   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 ***** */
  39
  40 /*
  41  * Portable double to alphanumeric string and back converters.
  42  */
  43 #include "jstypes.h"
  44 #include "jsstdint.h"
  45 #include "jsdtoa.h"
  46 #include "jsprf.h"
  47 #include "jsapi.h"
  48 #include "jsprvtd.h"
  49 #include "jsnum.h"
  50 #include "jsbit.h"
  51 #include "jslibmath.h"
  52 #include "jscntxt.h"
  53
  54 #include "jsobjinlines.h"
  55
  56 #ifdef IS_LITTLE_ENDIAN
  57 #define IEEE_8087
  58 #else
  59 #define IEEE_MC68k
  60 #endif
  61
  62 #ifndef Long
  63 #define Long int32
  64 #endif
  65
  66 #ifndef ULong
  67 #define ULong uint32
  68 #endif
  69
  70 /*
  71 #ifndef Llong
  72 #define Llong JSInt64
  73 #endif
  74
  75 #ifndef ULlong
  76 #define ULlong JSUint64
  77 #endif
  78 */
  79
  80 #define NO_GLOBAL_STATE
  81 #define MALLOC js_malloc
  82 #define FREE js_free
  83 #include "dtoa.c"
  84
  85 /* Mapping of JSDToStrMode -> js_dtoa mode */
  86 static const uint8 dtoaModes[] = {
  87     0,   /* DTOSTR_STANDARD */
  88     0,   /* DTOSTR_STANDARD_EXPONENTIAL, */
  89     3,   /* DTOSTR_FIXED, */
  90     2,   /* DTOSTR_EXPONENTIAL, */
  91     2};  /* DTOSTR_PRECISION */
  92
  93 double
  94 js_strtod_harder(DtoaState *state, const char *s00, char **se, int *err)
  95 {
  96     double retval;
  97     if (err)
  98         *err = 0;
  99     retval = _strtod(state, s00, se);
 100     return retval;
 101 }
 102
 103 char *
 104 js_dtostr(DtoaState *state, char *buffer, size_t bufferSize, JSDToStrMode mode, int precision,
 105           double dinput)
 106 {
 107     U d;
 108     int decPt;        /* Offset of decimal point from first digit */
 109     int sign;         /* Nonzero if the sign bit was set in d */
 110     int nDigits;      /* Number of significand digits returned by js_dtoa */
 111     char *numBegin;   /* Pointer to the digits returned by js_dtoa */
 112     char *numEnd = 0; /* Pointer past the digits returned by js_dtoa */
 113
 114     JS_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL
 115                                     ? DTOSTR_STANDARD_BUFFER_SIZE
 116                                     : DTOSTR_VARIABLE_BUFFER_SIZE(precision)));
 117
 118     /*
 119      * Change mode here rather than below because the buffer may not be large
 120      * enough to hold a large integer.
 121      */
 122     if (mode == DTOSTR_FIXED && (dinput >= 1e21 || dinput <= -1e21))
 123         mode = DTOSTR_STANDARD;
 124
 125     dval(d) = dinput;
 126     numBegin = dtoa(PASS_STATE d, dtoaModes[mode], precision, &decPt, &sign, &numEnd);
 127     if (!numBegin) {
 128         return NULL;
 129     }
 130
 131     nDigits = numEnd - numBegin;
 132     JS_ASSERT((size_t) nDigits <= bufferSize - 2);
 133     if ((size_t) nDigits > bufferSize - 2) {
 134         return NULL;
 135     }
 136
 137     memcpy(buffer + 2, numBegin, nDigits);
 138     freedtoa(PASS_STATE numBegin);
 139     numBegin = buffer + 2; /* +2 leaves space for sign and/or decimal point */
 140     numEnd = numBegin + nDigits;
 141     *numEnd = '\0';
 142
 143     /* If Infinity, -Infinity, or NaN, return the string regardless of mode. */
 144     if (decPt != 9999) {
 145         JSBool exponentialNotation = JS_FALSE;
 146         int minNDigits = 0;  /* Min number of significant digits required */
 147         char *p;
 148         char *q;
 149
 150         switch (mode) {
 151             case DTOSTR_STANDARD:
 152                 if (decPt < -5 || decPt > 21)
 153                     exponentialNotation = JS_TRUE;
 154                 else
 155                     minNDigits = decPt;
 156                 break;
 157
 158             case DTOSTR_FIXED:
 159                 if (precision >= 0)
 160                     minNDigits = decPt + precision;
 161                 else
 162                     minNDigits = decPt;
 163                 break;
 164
 165             case DTOSTR_EXPONENTIAL:
 166                 JS_ASSERT(precision > 0);
 167                 minNDigits = precision;
 168                 /* Fall through */
 169             case DTOSTR_STANDARD_EXPONENTIAL:
 170                 exponentialNotation = JS_TRUE;
 171                 break;
 172
 173             case DTOSTR_PRECISION:
 174                 JS_ASSERT(precision > 0);
 175                 minNDigits = precision;
 176                 if (decPt < -5 || decPt > precision)
 177                     exponentialNotation = JS_TRUE;
 178                 break;
 179         }
 180
 181         /* If the number has fewer than minNDigits, end-pad it with zeros. */
 182         if (nDigits < minNDigits) {
 183             p = numBegin + minNDigits;
 184             nDigits = minNDigits;
 185             do {
 186                 *numEnd++ = '0';
 187             } while (numEnd != p);
 188             *numEnd = '\0';
 189         }
 190
 191         if (exponentialNotation) {
 192             /* Insert a decimal point if more than one significand digit */
 193             if (nDigits != 1) {
 194                 numBegin--;
 195                 numBegin[0] = numBegin[1];
 196                 numBegin[1] = '.';
 197             }
 198             JS_snprintf(numEnd, bufferSize - (numEnd - buffer), "e%+d", decPt-1);
 199         } else if (decPt != nDigits) {
 200             /* Some kind of a fraction in fixed notation */
 201             JS_ASSERT(decPt <= nDigits);
 202             if (decPt > 0) {
 203                 /* dd...dd . dd...dd */
 204                 p = --numBegin;
 205                 do {
 206                     *p = p[1];
 207                     p++;
 208                 } while (--decPt);
 209                 *p = '.';
 210             } else {
 211                 /* 0 . 00...00dd...dd */
 212                 p = numEnd;
 213                 numEnd += 1 - decPt;
 214                 q = numEnd;
 215                 JS_ASSERT(numEnd < buffer + bufferSize);
 216                 *numEnd = '\0';
 217                 while (p != numBegin)
 218                     *--q = *--p;
 219                 for (p = numBegin + 1; p != q; p++)
 220                     *p = '0';
 221                 *numBegin = '.';
 222                 *--numBegin = '0';
 223             }
 224         }
 225     }
 226
 227     /* If negative and neither -0.0 nor NaN, output a leading '-'. */
 228     if (sign &&
 229             !(word0(d) == Sign_bit && word1(d) == 0) &&
 230             !((word0(d) & Exp_mask) == Exp_mask &&
 231               (word1(d) || (word0(d) & Frac_mask)))) {
 232         *--numBegin = '-';
 233     }
 234     return numBegin;
 235 }
 236
 237
 238 /* Let b = floor(b / divisor), and return the remainder.  b must be nonnegative.
 239  * divisor must be between 1 and 65536.
 240  * This function cannot run out of memory. */
 241 static uint32
 242 divrem(Bigint *b, uint32 divisor)
 243 {
 244     int32 n = b->wds;
 245     uint32 remainder = 0;
 246     ULong *bx;
 247     ULong *bp;
 248
 249     JS_ASSERT(divisor > 0 && divisor <= 65536);
 250
 251     if (!n)
 252         return 0; /* b is zero */
 253     bx = b->x;
 254     bp = bx + n;
 255     do {
 256         ULong a = *--bp;
 257         ULong dividend = remainder << 16 | a >> 16;
 258         ULong quotientHi = dividend / divisor;
 259         ULong quotientLo;
 260
 261         remainder = dividend - quotientHi*divisor;
 262         JS_ASSERT(quotientHi <= 0xFFFF && remainder < divisor);
 263         dividend = remainder << 16 | (a & 0xFFFF);
 264         quotientLo = dividend / divisor;
 265         remainder = dividend - quotientLo*divisor;
 266         JS_ASSERT(quotientLo <= 0xFFFF && remainder < divisor);
 267         *bp = quotientHi << 16 | quotientLo;
 268     } while (bp != bx);
 269     /* Decrease the size of the number if its most significant word is now zero. */
 270     if (bx[n-1] == 0)
 271         b->wds--;
 272     return remainder;
 273 }
 274
 275 /* Return floor(b/2^k) and set b to be the remainder.  The returned quotient must be less than 2^32. */
 276 static uint32 quorem2(Bigint *b, int32 k)
 277 {
 278     ULong mask;
 279     ULong result;
 280     ULong *bx, *bxe;
 281     int32 w;
 282     int32 n = k >> 5;
 283     k &= 0x1F;
 284     mask = (1<<k) - 1;
 285
 286     w = b->wds - n;
 287     if (w <= 0)
 288         return 0;
 289     JS_ASSERT(w <= 2);
 290     bx = b->x;
 291     bxe = bx + n;
 292     result = *bxe >> k;
 293     *bxe &= mask;
 294     if (w == 2) {
 295         JS_ASSERT(!(bxe[1] & ~mask));
 296         if (k)
 297             result |= bxe[1] << (32 - k);
 298     }
 299     n++;
 300     while (!*bxe && bxe != bx) {
 301         n--;
 302         bxe--;
 303     }
 304     b->wds = n;
 305     return result;
 306 }
 307
 308
 309 /* "-0.0000...(1073 zeros after decimal point)...0001\0" is the longest string that we could produce,
 310  * which occurs when printing -5e-324 in binary.  We could compute a better estimate of the size of
 311  * the output string and malloc fewer bytes depending on d and base, but why bother? */
 312 #define DTOBASESTR_BUFFER_SIZE 1078
 313 #define BASEDIGIT(digit) ((char)(((digit) >= 10) ? 'a' - 10 + (digit) : '0' + (digit)))
 314
 315 char *
 316 js_dtobasestr(DtoaState *state, int base, double dinput)
 317 {
 318     U d;
 319     char *buffer;        /* The output string */
 320     char *p;             /* Pointer to current position in the buffer */
 321     char *pInt;          /* Pointer to the beginning of the integer part of the string */
 322     char *q;
 323     uint32 digit;
 324     U di;                /* d truncated to an integer */
 325     U df;                /* The fractional part of d */
 326
 327     JS_ASSERT(base >= 2 && base <= 36);
 328
 329     dval(d) = dinput;
 330     buffer = (char*) js_malloc(DTOBASESTR_BUFFER_SIZE);
 331     if (!buffer)
 332         return NULL;
 333     p = buffer;
 334
 335     if (dval(d) < 0.0
 336 #if defined(XP_WIN) || defined(XP_OS2)
 337         && !((word0(d) & Exp_mask) == Exp_mask && ((word0(d) & Frac_mask) || word1(d))) /* Visual C++ doesn't know how to compare against NaN */
 338 #endif
 339        ) {
 340         *p++ = '-';
 341         dval(d) = -dval(d);
 342     }
 343
 344     /* Check for Infinity and NaN */
 345     if ((word0(d) & Exp_mask) == Exp_mask) {
 346         strcpy(p, !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN");
 347         return buffer;
 348     }
 349
 350     /* Output the integer part of d with the digits in reverse order. */
 351     pInt = p;
 352     dval(di) = floor(dval(d));
 353     if (dval(di) <= 4294967295.0) {
 354         uint32 n = (uint32)dval(di);
 355         if (n)
 356             do {
 357                 uint32 m = n / base;
 358                 digit = n - m*base;
 359                 n = m;
 360                 JS_ASSERT(digit < (uint32)base);
 361                 *p++ = BASEDIGIT(digit);
 362             } while (n);
 363         else *p++ = '0';
 364     } else {
 365         int e;
 366         int bits;  /* Number of significant bits in di; not used. */
 367         Bigint *b = d2b(PASS_STATE di, &e, &bits);
 368         if (!b)
 369             goto nomem1;
 370         b = lshift(PASS_STATE b, e);
 371         if (!b) {
 372           nomem1:
 373             Bfree(PASS_STATE b);
 374             js_free(buffer);
 375             return NULL;
 376         }
 377         do {
 378             digit = divrem(b, base);
 379             JS_ASSERT(digit < (uint32)base);
 380             *p++ = BASEDIGIT(digit);
 381         } while (b->wds);
 382         Bfree(PASS_STATE b);
 383     }
 384     /* Reverse the digits of the integer part of d. */
 385     q = p-1;
 386     while (q > pInt) {
 387         char ch = *pInt;
 388         *pInt++ = *q;
 389         *q-- = ch;
 390     }
 391
 392     dval(df) = dval(d) - dval(di);
 393     if (dval(df) != 0.0) {
 394         /* We have a fraction. */
 395         int e, bbits;
 396         int32 s2, done;
 397         Bigint *b, *s, *mlo, *mhi;
 398
 399         b = s = mlo = mhi = NULL;
 400
 401         *p++ = '.';
 402         b = d2b(PASS_STATE df, &e, &bbits);
 403         if (!b) {
 404           nomem2:
 405             Bfree(PASS_STATE b);
 406             Bfree(PASS_STATE s);
 407             if (mlo != mhi)
 408                 Bfree(PASS_STATE mlo);
 409             Bfree(PASS_STATE mhi);
 410             js_free(buffer);
 411             return NULL;
 412         }
 413         JS_ASSERT(e < 0);
 414         /* At this point df = b * 2^e.  e must be less than zero because 0 < df < 1. */
 415
 416         s2 = -(int32)(word0(d) >> Exp_shift1 & Exp_mask>>Exp_shift1);
 417 #ifndef Sudden_Underflow
 418         if (!s2)
 419             s2 = -1;
 420 #endif
 421         s2 += Bias + P;
 422         /* 1/2^s2 = (nextDouble(d) - d)/2 */
 423         JS_ASSERT(-s2 < e);
 424         mlo = i2b(PASS_STATE 1);
 425         if (!mlo)
 426             goto nomem2;
 427         mhi = mlo;
 428         if (!word1(d) && !(word0(d) & Bndry_mask)
 429 #ifndef Sudden_Underflow
 430             && word0(d) & (Exp_mask & Exp_mask << 1)
 431 #endif
 432             ) {
 433             /* The special case.  Here we want to be within a quarter of the last input
 434                significant digit instead of one half of it when the output string's value is less than d.  */
 435             s2 += Log2P;
 436             mhi = i2b(PASS_STATE 1<<Log2P);
 437             if (!mhi)
 438                 goto nomem2;
 439         }
 440         b = lshift(PASS_STATE b, e + s2);
 441         if (!b)
 442             goto nomem2;
 443         s = i2b(PASS_STATE 1);
 444         if (!s)
 445             goto nomem2;
 446         s = lshift(PASS_STATE s, s2);
 447         if (!s)
 448             goto nomem2;
 449         /* At this point we have the following:
 450          *   s = 2^s2;
 451          *   1 > df = b/2^s2 > 0;
 452          *   (d - prevDouble(d))/2 = mlo/2^s2;
 453          *   (nextDouble(d) - d)/2 = mhi/2^s2. */
 454
 455         done = JS_FALSE;
 456         do {
 457             int32 j, j1;
 458             Bigint *delta;
 459
 460             b = multadd(PASS_STATE b, base, 0);
 461             if (!b)
 462                 goto nomem2;
 463             digit = quorem2(b, s2);
 464             if (mlo == mhi) {
 465                 mlo = mhi = multadd(PASS_STATE mlo, base, 0);
 466                 if (!mhi)
 467                     goto nomem2;
 468             }
 469             else {
 470                 mlo = multadd(PASS_STATE mlo, base, 0);
 471                 if (!mlo)
 472                     goto nomem2;
 473                 mhi = multadd(PASS_STATE mhi, base, 0);
 474                 if (!mhi)
 475                     goto nomem2;
 476             }
 477
 478             /* Do we yet have the shortest string that will round to d? */
 479             j = cmp(b, mlo);
 480             /* j is b/2^s2 compared with mlo/2^s2. */
 481             delta = diff(PASS_STATE s, mhi);
 482             if (!delta)
 483                 goto nomem2;
 484             j1 = delta->sign ? 1 : cmp(b, delta);
 485             Bfree(PASS_STATE delta);
 486             /* j1 is b/2^s2 compared with 1 - mhi/2^s2. */
 487
 488 #ifndef ROUND_BIASED
 489             if (j1 == 0 && !(word1(d) & 1)) {
 490                 if (j > 0)
 491                     digit++;
 492                 done = JS_TRUE;
 493             } else
 494 #endif
 495             if (j < 0 || (j == 0
 496 #ifndef ROUND_BIASED
 497                 && !(word1(d) & 1)
 498 #endif
 499                 )) {
 500                 if (j1 > 0) {
 501                     /* Either dig or dig+1 would work here as the least significant digit.
 502                        Use whichever would produce an output value closer to d. */
 503                     b = lshift(PASS_STATE b, 1);
 504                     if (!b)
 505                         goto nomem2;
 506                     j1 = cmp(b, s);
 507                     if (j1 > 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here because it messes up odd base output
 508                                  * such as 3.5 in base 3.  */
 509                         digit++;
 510                 }
 511                 done = JS_TRUE;
 512             } else if (j1 > 0) {
 513                 digit++;
 514                 done = JS_TRUE;
 515             }
 516             JS_ASSERT(digit < (uint32)base);
 517             *p++ = BASEDIGIT(digit);
 518         } while (!done);
 519         Bfree(PASS_STATE b);
 520         Bfree(PASS_STATE s);
 521         if (mlo != mhi)
 522             Bfree(PASS_STATE mlo);
 523         Bfree(PASS_STATE mhi);
 524     }
 525     JS_ASSERT(p < buffer + DTOBASESTR_BUFFER_SIZE);
 526     *p = '\0';
 527     return buffer;
 528 }
 529
 530 DtoaState *
 531 js_NewDtoaState()
 532 {
 533     return newdtoa();
 534 }
 535
 536 void
 537 js_DestroyDtoaState(DtoaState *state)
 538 {
 539     destroydtoa(state);
 540 }