js/src/util/DoubleToString.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /*
   8  * Portable double to alphanumeric string and back converters.
   9  */
  10
  11 #include "util/DoubleToString.h"
  12
  13 #include "mozilla/EndianUtils.h"
  14
  15 #include "js/Utility.h"
  16
  17 using namespace js;
  18
  19 #if MOZ_LITTLE_ENDIAN()
  20 #  define IEEE_8087
  21 #else
  22 #  define IEEE_MC68k
  23 #endif
  24
  25 #ifndef Long
  26 #  define Long int32_t
  27 #endif
  28
  29 #ifndef ULong
  30 #  define ULong uint32_t
  31 #endif
  32
  33 /*
  34 #ifndef Llong
  35 #define Llong int64_t
  36 #endif
  37
  38 #ifndef ULlong
  39 #define ULlong uint64_t
  40 #endif
  41 */
  42
  43 // dtoa.c requires that MALLOC be infallible. Furthermore, its allocations are
  44 // few and small. So AutoEnterOOMUnsafeRegion is appropriate here.
  45 static inline void* dtoa_malloc(size_t size) {
  46   AutoEnterOOMUnsafeRegion oomUnsafe;
  47   void* p = js_malloc(size);
  48   if (!p) oomUnsafe.crash("dtoa_malloc");
  49
  50   return p;
  51 }
  52
  53 static inline void dtoa_free(void* p) { return js_free(p); }
  54
  55 #define NO_GLOBAL_STATE
  56 #define NO_ERRNO
  57 #define Omit_Private_Memory  // This saves memory for the workloads we see.
  58 #define MALLOC dtoa_malloc
  59 #define FREE dtoa_free
  60 #include "dtoa.c"
  61
  62 /* Let b = floor(b / divisor), and return the remainder.  b must be nonnegative.
  63  * divisor must be between 1 and 65536.
  64  * This function cannot run out of memory. */
  65 static uint32_t divrem(Bigint* b, uint32_t divisor) {
  66   int32_t n = b->wds;
  67   uint32_t remainder = 0;
  68   ULong* bx;
  69   ULong* bp;
  70
  71   MOZ_ASSERT(divisor > 0 && divisor <= 65536);
  72
  73   if (!n) return 0; /* b is zero */
  74   bx = b->x;
  75   bp = bx + n;
  76   do {
  77     ULong a = *--bp;
  78     ULong dividend = remainder << 16 | a >> 16;
  79     ULong quotientHi = dividend / divisor;
  80     ULong quotientLo;
  81
  82     remainder = dividend - quotientHi * divisor;
  83     MOZ_ASSERT(quotientHi <= 0xFFFF && remainder < divisor);
  84     dividend = remainder << 16 | (a & 0xFFFF);
  85     quotientLo = dividend / divisor;
  86     remainder = dividend - quotientLo * divisor;
  87     MOZ_ASSERT(quotientLo <= 0xFFFF && remainder < divisor);
  88     *bp = quotientHi << 16 | quotientLo;
  89   } while (bp != bx);
  90   /* Decrease the size of the number if its most significant word is now zero.
  91    */
  92   if (bx[n - 1] == 0) b->wds--;
  93   return remainder;
  94 }
  95
  96 /* Return floor(b/2^k) and set b to be the remainder.  The returned quotient
  97  * must be less than 2^32. */
  98 static uint32_t quorem2(Bigint* b, int32_t k) {
  99   ULong mask;
 100   ULong result;
 101   ULong* bx;
 102   ULong* bxe;
 103   int32_t w;
 104   int32_t n = k >> 5;
 105   k &= 0x1F;
 106   mask = (ULong(1) << k) - 1;
 107
 108   w = b->wds - n;
 109   if (w <= 0) return 0;
 110   MOZ_ASSERT(w <= 2);
 111   bx = b->x;
 112   bxe = bx + n;
 113   result = *bxe >> k;
 114   *bxe &= mask;
 115   if (w == 2) {
 116     MOZ_ASSERT(!(bxe[1] & ~mask));
 117     if (k) result |= bxe[1] << (32 - k);
 118   }
 119   n++;
 120   while (!*bxe && bxe != bx) {
 121     n--;
 122     bxe--;
 123   }
 124   b->wds = n;
 125   return result;
 126 }
 127
 128 /* "-0.0000...(1073 zeros after decimal point)...0001\0" is the longest string
 129  * that we could produce, which occurs when printing -5e-324 in binary.  We
 130  * could compute a better estimate of the size of the output string and malloc
 131  * fewer bytes depending on d and base, but why bother? */
 132 #define DTOBASESTR_BUFFER_SIZE 1078
 133 #define BASEDIGIT(digit) \
 134   ((char)(((digit) >= 10) ? 'a' - 10 + (digit) : '0' + (digit)))
 135
 136 char* js_dtobasestr(DtoaState* state, int base, double dinput) {
 137   U d;
 138   char* buffer; /* The output string */
 139   char* p;      /* Pointer to current position in the buffer */
 140   char* pInt;   /* Pointer to the beginning of the integer part of the string */
 141   char* q;
 142   uint32_t digit;
 143   U di; /* d truncated to an integer */
 144   U df; /* The fractional part of d */
 145
 146   MOZ_ASSERT(base >= 2 && base <= 36);
 147
 148   dval(d) = dinput;
 149   buffer = js_pod_malloc<char>(DTOBASESTR_BUFFER_SIZE);
 150   if (!buffer) return nullptr;
 151   p = buffer;
 152
 153   if (dval(d) < 0.0) {
 154     *p++ = '-';
 155     dval(d) = -dval(d);
 156   }
 157
 158   /* Check for Infinity and NaN */
 159   if ((word0(d) & Exp_mask) == Exp_mask) {
 160     strcpy(p, !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN");
 161     return buffer;
 162   }
 163
 164   /* Output the integer part of d with the digits in reverse order. */
 165   pInt = p;
 166   dval(di) = floor(dval(d));
 167   if (dval(di) <= 4294967295.0) {
 168     uint32_t n = (uint32_t)dval(di);
 169     if (n) do {
 170         uint32_t m = n / base;
 171         digit = n - m * base;
 172         n = m;
 173         MOZ_ASSERT(digit < (uint32_t)base);
 174         *p++ = BASEDIGIT(digit);
 175       } while (n);
 176     else
 177       *p++ = '0';
 178   } else {
 179     int e;
 180     int bits; /* Number of significant bits in di; not used. */
 181     Bigint* b = d2b(PASS_STATE di, &e, &bits);
 182     if (!b) goto nomem1;
 183     b = lshift(PASS_STATE b, e);
 184     if (!b) {
 185     nomem1:
 186       Bfree(PASS_STATE b);
 187       js_free(buffer);
 188       return nullptr;
 189     }
 190     do {
 191       digit = divrem(b, base);
 192       MOZ_ASSERT(digit < (uint32_t)base);
 193       *p++ = BASEDIGIT(digit);
 194     } while (b->wds);
 195     Bfree(PASS_STATE b);
 196   }
 197   /* Reverse the digits of the integer part of d. */
 198   q = p - 1;
 199   while (q > pInt) {
 200     char ch = *pInt;
 201     *pInt++ = *q;
 202     *q-- = ch;
 203   }
 204
 205   dval(df) = dval(d) - dval(di);
 206   if (dval(df) != 0.0) {
 207     /* We have a fraction. */
 208     int e, bbits;
 209     int32_t s2, done;
 210     Bigint* b = nullptr;
 211     Bigint* s = nullptr;
 212     Bigint* mlo = nullptr;
 213     Bigint* mhi = nullptr;
 214
 215     *p++ = '.';
 216     b = d2b(PASS_STATE df, &e, &bbits);
 217     if (!b) {
 218     nomem2:
 219       Bfree(PASS_STATE b);
 220       Bfree(PASS_STATE s);
 221       if (mlo != mhi) Bfree(PASS_STATE mlo);
 222       Bfree(PASS_STATE mhi);
 223       js_free(buffer);
 224       return nullptr;
 225     }
 226     MOZ_ASSERT(e < 0);
 227     /* At this point df = b * 2^e.  e must be less than zero because 0 < df < 1.
 228      */
 229
 230     s2 = -(int32_t)(word0(d) >> Exp_shift1 & Exp_mask >> Exp_shift1);
 231 #ifndef Sudden_Underflow
 232     if (!s2) s2 = -1;
 233 #endif
 234     s2 += Bias + P;
 235     /* 1/2^s2 = (nextDouble(d) - d)/2 */
 236     MOZ_ASSERT(-s2 < e);
 237     mlo = i2b(PASS_STATE 1);
 238     if (!mlo) goto nomem2;
 239     mhi = mlo;
 240     if (!word1(d) && !(word0(d) & Bndry_mask)
 241 #ifndef Sudden_Underflow
 242         && word0(d) & (Exp_mask & Exp_mask << 1)
 243 #endif
 244     ) {
 245       /* The special case.  Here we want to be within a quarter of the last
 246          input significant digit instead of one half of it when the output
 247          string's value is less than d.  */
 248       s2 += Log2P;
 249       mhi = i2b(PASS_STATE 1 << Log2P);
 250       if (!mhi) goto nomem2;
 251     }
 252     b = lshift(PASS_STATE b, e + s2);
 253     if (!b) goto nomem2;
 254     s = i2b(PASS_STATE 1);
 255     if (!s) goto nomem2;
 256     s = lshift(PASS_STATE s, s2);
 257     if (!s) goto nomem2;
 258     /* At this point we have the following:
 259      *   s = 2^s2;
 260      *   1 > df = b/2^s2 > 0;
 261      *   (d - prevDouble(d))/2 = mlo/2^s2;
 262      *   (nextDouble(d) - d)/2 = mhi/2^s2. */
 263
 264     done = false;
 265     do {
 266       int32_t j, j1;
 267       Bigint* delta;
 268
 269       b = multadd(PASS_STATE b, base, 0);
 270       if (!b) goto nomem2;
 271       digit = quorem2(b, s2);
 272       if (mlo == mhi) {
 273         mlo = mhi = multadd(PASS_STATE mlo, base, 0);
 274         if (!mhi) goto nomem2;
 275       } else {
 276         mlo = multadd(PASS_STATE mlo, base, 0);
 277         if (!mlo) goto nomem2;
 278         mhi = multadd(PASS_STATE mhi, base, 0);
 279         if (!mhi) goto nomem2;
 280       }
 281
 282       /* Do we yet have the shortest string that will round to d? */
 283       j = cmp(b, mlo);
 284       /* j is b/2^s2 compared with mlo/2^s2. */
 285       delta = diff(PASS_STATE s, mhi);
 286       if (!delta) goto nomem2;
 287       j1 = delta->sign ? 1 : cmp(b, delta);
 288       Bfree(PASS_STATE delta);
 289       /* j1 is b/2^s2 compared with 1 - mhi/2^s2. */
 290
 291 #ifndef ROUND_BIASED
 292       if (j1 == 0 && !(word1(d) & 1)) {
 293         if (j > 0) digit++;
 294         done = true;
 295       } else
 296 #endif
 297           if (j < 0 || (j == 0
 298 #ifndef ROUND_BIASED
 299                         && !(word1(d) & 1)
 300 #endif
 301                             )) {
 302         if (j1 > 0) {
 303           /* Either dig or dig+1 would work here as the least significant digit.
 304              Use whichever would produce an output value closer to d. */
 305           b = lshift(PASS_STATE b, 1);
 306           if (!b) goto nomem2;
 307           j1 = cmp(b, s);
 308           if (j1 > 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here
 309                        * because it messes up odd base output such as 3.5 in
 310                        * base 3.  */
 311             digit++;
 312         }
 313         done = true;
 314       } else if (j1 > 0) {
 315         digit++;
 316         done = true;
 317       }
 318       MOZ_ASSERT(digit < (uint32_t)base);
 319       *p++ = BASEDIGIT(digit);
 320     } while (!done);
 321     Bfree(PASS_STATE b);
 322     Bfree(PASS_STATE s);
 323     if (mlo != mhi) Bfree(PASS_STATE mlo);
 324     Bfree(PASS_STATE mhi);
 325   }
 326   MOZ_ASSERT(p < buffer + DTOBASESTR_BUFFER_SIZE);
 327   *p = '\0';
 328   return buffer;
 329 }
 330
 331 DtoaState* js::NewDtoaState() { return newdtoa(); }
 332
 333 void js::DestroyDtoaState(DtoaState* state) { destroydtoa(state); }
 334
 335 /* Cleanup pollution from dtoa.c */
 336 #undef Bias