DoubleToString.cpp (9004B)
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