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