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