1 // Copyright 2011 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_CONVERSIONS_INL_H_ 6 #define V8_CONVERSIONS_INL_H_ 7 8 #include <limits.h> // Required for INT_MAX etc. 9 #include <float.h> // Required for DBL_MAX and on Win32 for finite() 10 #include <stdarg.h> 11 #include <cmath> 12 #include "src/globals.h" // Required for V8_INFINITY 13 14 // ---------------------------------------------------------------------------- 15 // Extra POSIX/ANSI functions for Win32/MSVC. 16 17 #include "src/conversions.h" 18 #include "src/double.h" 19 #include "src/platform.h" 20 #include "src/scanner.h" 21 #include "src/strtod.h" 22 23 namespace v8 { 24 namespace internal { 25 26 inline double JunkStringValue() { 27 return BitCast<double, uint64_t>(kQuietNaNMask); 28 } 29 30 31 inline double SignedZero(bool negative) { 32 return negative ? uint64_to_double(Double::kSignMask) : 0.0; 33 } 34 35 36 // The fast double-to-unsigned-int conversion routine does not guarantee 37 // rounding towards zero, or any reasonable value if the argument is larger 38 // than what fits in an unsigned 32-bit integer. 39 inline unsigned int FastD2UI(double x) { 40 // There is no unsigned version of lrint, so there is no fast path 41 // in this function as there is in FastD2I. Using lrint doesn't work 42 // for values of 2^31 and above. 43 44 // Convert "small enough" doubles to uint32_t by fixing the 32 45 // least significant non-fractional bits in the low 32 bits of the 46 // double, and reading them from there. 47 const double k2Pow52 = 4503599627370496.0; 48 bool negative = x < 0; 49 if (negative) { 50 x = -x; 51 } 52 if (x < k2Pow52) { 53 x += k2Pow52; 54 uint32_t result; 55 #ifndef V8_TARGET_BIG_ENDIAN 56 Address mantissa_ptr = reinterpret_cast<Address>(&x); 57 #else 58 Address mantissa_ptr = reinterpret_cast<Address>(&x) + kIntSize; 59 #endif 60 // Copy least significant 32 bits of mantissa. 61 memcpy(&result, mantissa_ptr, sizeof(result)); 62 return negative ? ~result + 1 : result; 63 } 64 // Large number (outside uint32 range), Infinity or NaN. 65 return 0x80000000u; // Return integer indefinite. 66 } 67 68 69 inline double DoubleToInteger(double x) { 70 if (std::isnan(x)) return 0; 71 if (!std::isfinite(x) || x == 0) return x; 72 return (x >= 0) ? std::floor(x) : std::ceil(x); 73 } 74 75 76 int32_t DoubleToInt32(double x) { 77 int32_t i = FastD2I(x); 78 if (FastI2D(i) == x) return i; 79 Double d(x); 80 int exponent = d.Exponent(); 81 if (exponent < 0) { 82 if (exponent <= -Double::kSignificandSize) return 0; 83 return d.Sign() * static_cast<int32_t>(d.Significand() >> -exponent); 84 } else { 85 if (exponent > 31) return 0; 86 return d.Sign() * static_cast<int32_t>(d.Significand() << exponent); 87 } 88 } 89 90 91 template <class Iterator, class EndMark> 92 bool SubStringEquals(Iterator* current, 93 EndMark end, 94 const char* substring) { 95 ASSERT(**current == *substring); 96 for (substring++; *substring != '\0'; substring++) { 97 ++*current; 98 if (*current == end || **current != *substring) return false; 99 } 100 ++*current; 101 return true; 102 } 103 104 105 // Returns true if a nonspace character has been found and false if the 106 // end was been reached before finding a nonspace character. 107 template <class Iterator, class EndMark> 108 inline bool AdvanceToNonspace(UnicodeCache* unicode_cache, 109 Iterator* current, 110 EndMark end) { 111 while (*current != end) { 112 if (!unicode_cache->IsWhiteSpaceOrLineTerminator(**current)) return true; 113 ++*current; 114 } 115 return false; 116 } 117 118 119 // Parsing integers with radix 2, 4, 8, 16, 32. Assumes current != end. 120 template <int radix_log_2, class Iterator, class EndMark> 121 double InternalStringToIntDouble(UnicodeCache* unicode_cache, 122 Iterator current, 123 EndMark end, 124 bool negative, 125 bool allow_trailing_junk) { 126 ASSERT(current != end); 127 128 // Skip leading 0s. 129 while (*current == '0') { 130 ++current; 131 if (current == end) return SignedZero(negative); 132 } 133 134 int64_t number = 0; 135 int exponent = 0; 136 const int radix = (1 << radix_log_2); 137 138 do { 139 int digit; 140 if (*current >= '0' && *current <= '9' && *current < '0' + radix) { 141 digit = static_cast<char>(*current) - '0'; 142 } else if (radix > 10 && *current >= 'a' && *current < 'a' + radix - 10) { 143 digit = static_cast<char>(*current) - 'a' + 10; 144 } else if (radix > 10 && *current >= 'A' && *current < 'A' + radix - 10) { 145 digit = static_cast<char>(*current) - 'A' + 10; 146 } else { 147 if (allow_trailing_junk || 148 !AdvanceToNonspace(unicode_cache, ¤t, end)) { 149 break; 150 } else { 151 return JunkStringValue(); 152 } 153 } 154 155 number = number * radix + digit; 156 int overflow = static_cast<int>(number >> 53); 157 if (overflow != 0) { 158 // Overflow occurred. Need to determine which direction to round the 159 // result. 160 int overflow_bits_count = 1; 161 while (overflow > 1) { 162 overflow_bits_count++; 163 overflow >>= 1; 164 } 165 166 int dropped_bits_mask = ((1 << overflow_bits_count) - 1); 167 int dropped_bits = static_cast<int>(number) & dropped_bits_mask; 168 number >>= overflow_bits_count; 169 exponent = overflow_bits_count; 170 171 bool zero_tail = true; 172 while (true) { 173 ++current; 174 if (current == end || !isDigit(*current, radix)) break; 175 zero_tail = zero_tail && *current == '0'; 176 exponent += radix_log_2; 177 } 178 179 if (!allow_trailing_junk && 180 AdvanceToNonspace(unicode_cache, ¤t, end)) { 181 return JunkStringValue(); 182 } 183 184 int middle_value = (1 << (overflow_bits_count - 1)); 185 if (dropped_bits > middle_value) { 186 number++; // Rounding up. 187 } else if (dropped_bits == middle_value) { 188 // Rounding to even to consistency with decimals: half-way case rounds 189 // up if significant part is odd and down otherwise. 190 if ((number & 1) != 0 || !zero_tail) { 191 number++; // Rounding up. 192 } 193 } 194 195 // Rounding up may cause overflow. 196 if ((number & (static_cast<int64_t>(1) << 53)) != 0) { 197 exponent++; 198 number >>= 1; 199 } 200 break; 201 } 202 ++current; 203 } while (current != end); 204 205 ASSERT(number < ((int64_t)1 << 53)); 206 ASSERT(static_cast<int64_t>(static_cast<double>(number)) == number); 207 208 if (exponent == 0) { 209 if (negative) { 210 if (number == 0) return -0.0; 211 number = -number; 212 } 213 return static_cast<double>(number); 214 } 215 216 ASSERT(number != 0); 217 return std::ldexp(static_cast<double>(negative ? -number : number), exponent); 218 } 219 220 221 template <class Iterator, class EndMark> 222 double InternalStringToInt(UnicodeCache* unicode_cache, 223 Iterator current, 224 EndMark end, 225 int radix) { 226 const bool allow_trailing_junk = true; 227 const double empty_string_val = JunkStringValue(); 228 229 if (!AdvanceToNonspace(unicode_cache, ¤t, end)) { 230 return empty_string_val; 231 } 232 233 bool negative = false; 234 bool leading_zero = false; 235 236 if (*current == '+') { 237 // Ignore leading sign; skip following spaces. 238 ++current; 239 if (current == end) { 240 return JunkStringValue(); 241 } 242 } else if (*current == '-') { 243 ++current; 244 if (current == end) { 245 return JunkStringValue(); 246 } 247 negative = true; 248 } 249 250 if (radix == 0) { 251 // Radix detection. 252 radix = 10; 253 if (*current == '0') { 254 ++current; 255 if (current == end) return SignedZero(negative); 256 if (*current == 'x' || *current == 'X') { 257 radix = 16; 258 ++current; 259 if (current == end) return JunkStringValue(); 260 } else { 261 leading_zero = true; 262 } 263 } 264 } else if (radix == 16) { 265 if (*current == '0') { 266 // Allow "0x" prefix. 267 ++current; 268 if (current == end) return SignedZero(negative); 269 if (*current == 'x' || *current == 'X') { 270 ++current; 271 if (current == end) return JunkStringValue(); 272 } else { 273 leading_zero = true; 274 } 275 } 276 } 277 278 if (radix < 2 || radix > 36) return JunkStringValue(); 279 280 // Skip leading zeros. 281 while (*current == '0') { 282 leading_zero = true; 283 ++current; 284 if (current == end) return SignedZero(negative); 285 } 286 287 if (!leading_zero && !isDigit(*current, radix)) { 288 return JunkStringValue(); 289 } 290 291 if (IsPowerOf2(radix)) { 292 switch (radix) { 293 case 2: 294 return InternalStringToIntDouble<1>( 295 unicode_cache, current, end, negative, allow_trailing_junk); 296 case 4: 297 return InternalStringToIntDouble<2>( 298 unicode_cache, current, end, negative, allow_trailing_junk); 299 case 8: 300 return InternalStringToIntDouble<3>( 301 unicode_cache, current, end, negative, allow_trailing_junk); 302 303 case 16: 304 return InternalStringToIntDouble<4>( 305 unicode_cache, current, end, negative, allow_trailing_junk); 306 307 case 32: 308 return InternalStringToIntDouble<5>( 309 unicode_cache, current, end, negative, allow_trailing_junk); 310 default: 311 UNREACHABLE(); 312 } 313 } 314 315 if (radix == 10) { 316 // Parsing with strtod. 317 const int kMaxSignificantDigits = 309; // Doubles are less than 1.8e308. 318 // The buffer may contain up to kMaxSignificantDigits + 1 digits and a zero 319 // end. 320 const int kBufferSize = kMaxSignificantDigits + 2; 321 char buffer[kBufferSize]; 322 int buffer_pos = 0; 323 while (*current >= '0' && *current <= '9') { 324 if (buffer_pos <= kMaxSignificantDigits) { 325 // If the number has more than kMaxSignificantDigits it will be parsed 326 // as infinity. 327 ASSERT(buffer_pos < kBufferSize); 328 buffer[buffer_pos++] = static_cast<char>(*current); 329 } 330 ++current; 331 if (current == end) break; 332 } 333 334 if (!allow_trailing_junk && 335 AdvanceToNonspace(unicode_cache, ¤t, end)) { 336 return JunkStringValue(); 337 } 338 339 SLOW_ASSERT(buffer_pos < kBufferSize); 340 buffer[buffer_pos] = '\0'; 341 Vector<const char> buffer_vector(buffer, buffer_pos); 342 return negative ? -Strtod(buffer_vector, 0) : Strtod(buffer_vector, 0); 343 } 344 345 // The following code causes accumulating rounding error for numbers greater 346 // than ~2^56. It's explicitly allowed in the spec: "if R is not 2, 4, 8, 10, 347 // 16, or 32, then mathInt may be an implementation-dependent approximation to 348 // the mathematical integer value" (15.1.2.2). 349 350 int lim_0 = '0' + (radix < 10 ? radix : 10); 351 int lim_a = 'a' + (radix - 10); 352 int lim_A = 'A' + (radix - 10); 353 354 // NOTE: The code for computing the value may seem a bit complex at 355 // first glance. It is structured to use 32-bit multiply-and-add 356 // loops as long as possible to avoid loosing precision. 357 358 double v = 0.0; 359 bool done = false; 360 do { 361 // Parse the longest part of the string starting at index j 362 // possible while keeping the multiplier, and thus the part 363 // itself, within 32 bits. 364 unsigned int part = 0, multiplier = 1; 365 while (true) { 366 int d; 367 if (*current >= '0' && *current < lim_0) { 368 d = *current - '0'; 369 } else if (*current >= 'a' && *current < lim_a) { 370 d = *current - 'a' + 10; 371 } else if (*current >= 'A' && *current < lim_A) { 372 d = *current - 'A' + 10; 373 } else { 374 done = true; 375 break; 376 } 377 378 // Update the value of the part as long as the multiplier fits 379 // in 32 bits. When we can't guarantee that the next iteration 380 // will not overflow the multiplier, we stop parsing the part 381 // by leaving the loop. 382 const unsigned int kMaximumMultiplier = 0xffffffffU / 36; 383 uint32_t m = multiplier * radix; 384 if (m > kMaximumMultiplier) break; 385 part = part * radix + d; 386 multiplier = m; 387 ASSERT(multiplier > part); 388 389 ++current; 390 if (current == end) { 391 done = true; 392 break; 393 } 394 } 395 396 // Update the value and skip the part in the string. 397 v = v * multiplier + part; 398 } while (!done); 399 400 if (!allow_trailing_junk && 401 AdvanceToNonspace(unicode_cache, ¤t, end)) { 402 return JunkStringValue(); 403 } 404 405 return negative ? -v : v; 406 } 407 408 409 // Converts a string to a double value. Assumes the Iterator supports 410 // the following operations: 411 // 1. current == end (other ops are not allowed), current != end. 412 // 2. *current - gets the current character in the sequence. 413 // 3. ++current (advances the position). 414 template <class Iterator, class EndMark> 415 double InternalStringToDouble(UnicodeCache* unicode_cache, 416 Iterator current, 417 EndMark end, 418 int flags, 419 double empty_string_val) { 420 // To make sure that iterator dereferencing is valid the following 421 // convention is used: 422 // 1. Each '++current' statement is followed by check for equality to 'end'. 423 // 2. If AdvanceToNonspace returned false then current == end. 424 // 3. If 'current' becomes be equal to 'end' the function returns or goes to 425 // 'parsing_done'. 426 // 4. 'current' is not dereferenced after the 'parsing_done' label. 427 // 5. Code before 'parsing_done' may rely on 'current != end'. 428 if (!AdvanceToNonspace(unicode_cache, ¤t, end)) { 429 return empty_string_val; 430 } 431 432 const bool allow_trailing_junk = (flags & ALLOW_TRAILING_JUNK) != 0; 433 434 // The longest form of simplified number is: "-<significant digits>'.1eXXX\0". 435 const int kBufferSize = kMaxSignificantDigits + 10; 436 char buffer[kBufferSize]; // NOLINT: size is known at compile time. 437 int buffer_pos = 0; 438 439 // Exponent will be adjusted if insignificant digits of the integer part 440 // or insignificant leading zeros of the fractional part are dropped. 441 int exponent = 0; 442 int significant_digits = 0; 443 int insignificant_digits = 0; 444 bool nonzero_digit_dropped = false; 445 446 enum Sign { 447 NONE, 448 NEGATIVE, 449 POSITIVE 450 }; 451 452 Sign sign = NONE; 453 454 if (*current == '+') { 455 // Ignore leading sign. 456 ++current; 457 if (current == end) return JunkStringValue(); 458 sign = POSITIVE; 459 } else if (*current == '-') { 460 ++current; 461 if (current == end) return JunkStringValue(); 462 sign = NEGATIVE; 463 } 464 465 static const char kInfinityString[] = "Infinity"; 466 if (*current == kInfinityString[0]) { 467 if (!SubStringEquals(¤t, end, kInfinityString)) { 468 return JunkStringValue(); 469 } 470 471 if (!allow_trailing_junk && 472 AdvanceToNonspace(unicode_cache, ¤t, end)) { 473 return JunkStringValue(); 474 } 475 476 ASSERT(buffer_pos == 0); 477 return (sign == NEGATIVE) ? -V8_INFINITY : V8_INFINITY; 478 } 479 480 bool leading_zero = false; 481 if (*current == '0') { 482 ++current; 483 if (current == end) return SignedZero(sign == NEGATIVE); 484 485 leading_zero = true; 486 487 // It could be hexadecimal value. 488 if ((flags & ALLOW_HEX) && (*current == 'x' || *current == 'X')) { 489 ++current; 490 if (current == end || !isDigit(*current, 16) || sign != NONE) { 491 return JunkStringValue(); // "0x". 492 } 493 494 return InternalStringToIntDouble<4>(unicode_cache, 495 current, 496 end, 497 false, 498 allow_trailing_junk); 499 500 // It could be an explicit octal value. 501 } else if ((flags & ALLOW_OCTAL) && (*current == 'o' || *current == 'O')) { 502 ++current; 503 if (current == end || !isDigit(*current, 8) || sign != NONE) { 504 return JunkStringValue(); // "0o". 505 } 506 507 return InternalStringToIntDouble<3>(unicode_cache, 508 current, 509 end, 510 false, 511 allow_trailing_junk); 512 513 // It could be a binary value. 514 } else if ((flags & ALLOW_BINARY) && (*current == 'b' || *current == 'B')) { 515 ++current; 516 if (current == end || !isBinaryDigit(*current) || sign != NONE) { 517 return JunkStringValue(); // "0b". 518 } 519 520 return InternalStringToIntDouble<1>(unicode_cache, 521 current, 522 end, 523 false, 524 allow_trailing_junk); 525 } 526 527 // Ignore leading zeros in the integer part. 528 while (*current == '0') { 529 ++current; 530 if (current == end) return SignedZero(sign == NEGATIVE); 531 } 532 } 533 534 bool octal = leading_zero && (flags & ALLOW_IMPLICIT_OCTAL) != 0; 535 536 // Copy significant digits of the integer part (if any) to the buffer. 537 while (*current >= '0' && *current <= '9') { 538 if (significant_digits < kMaxSignificantDigits) { 539 ASSERT(buffer_pos < kBufferSize); 540 buffer[buffer_pos++] = static_cast<char>(*current); 541 significant_digits++; 542 // Will later check if it's an octal in the buffer. 543 } else { 544 insignificant_digits++; // Move the digit into the exponential part. 545 nonzero_digit_dropped = nonzero_digit_dropped || *current != '0'; 546 } 547 octal = octal && *current < '8'; 548 ++current; 549 if (current == end) goto parsing_done; 550 } 551 552 if (significant_digits == 0) { 553 octal = false; 554 } 555 556 if (*current == '.') { 557 if (octal && !allow_trailing_junk) return JunkStringValue(); 558 if (octal) goto parsing_done; 559 560 ++current; 561 if (current == end) { 562 if (significant_digits == 0 && !leading_zero) { 563 return JunkStringValue(); 564 } else { 565 goto parsing_done; 566 } 567 } 568 569 if (significant_digits == 0) { 570 // octal = false; 571 // Integer part consists of 0 or is absent. Significant digits start after 572 // leading zeros (if any). 573 while (*current == '0') { 574 ++current; 575 if (current == end) return SignedZero(sign == NEGATIVE); 576 exponent--; // Move this 0 into the exponent. 577 } 578 } 579 580 // There is a fractional part. We don't emit a '.', but adjust the exponent 581 // instead. 582 while (*current >= '0' && *current <= '9') { 583 if (significant_digits < kMaxSignificantDigits) { 584 ASSERT(buffer_pos < kBufferSize); 585 buffer[buffer_pos++] = static_cast<char>(*current); 586 significant_digits++; 587 exponent--; 588 } else { 589 // Ignore insignificant digits in the fractional part. 590 nonzero_digit_dropped = nonzero_digit_dropped || *current != '0'; 591 } 592 ++current; 593 if (current == end) goto parsing_done; 594 } 595 } 596 597 if (!leading_zero && exponent == 0 && significant_digits == 0) { 598 // If leading_zeros is true then the string contains zeros. 599 // If exponent < 0 then string was [+-]\.0*... 600 // If significant_digits != 0 the string is not equal to 0. 601 // Otherwise there are no digits in the string. 602 return JunkStringValue(); 603 } 604 605 // Parse exponential part. 606 if (*current == 'e' || *current == 'E') { 607 if (octal) return JunkStringValue(); 608 ++current; 609 if (current == end) { 610 if (allow_trailing_junk) { 611 goto parsing_done; 612 } else { 613 return JunkStringValue(); 614 } 615 } 616 char sign = '+'; 617 if (*current == '+' || *current == '-') { 618 sign = static_cast<char>(*current); 619 ++current; 620 if (current == end) { 621 if (allow_trailing_junk) { 622 goto parsing_done; 623 } else { 624 return JunkStringValue(); 625 } 626 } 627 } 628 629 if (current == end || *current < '0' || *current > '9') { 630 if (allow_trailing_junk) { 631 goto parsing_done; 632 } else { 633 return JunkStringValue(); 634 } 635 } 636 637 const int max_exponent = INT_MAX / 2; 638 ASSERT(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2); 639 int num = 0; 640 do { 641 // Check overflow. 642 int digit = *current - '0'; 643 if (num >= max_exponent / 10 644 && !(num == max_exponent / 10 && digit <= max_exponent % 10)) { 645 num = max_exponent; 646 } else { 647 num = num * 10 + digit; 648 } 649 ++current; 650 } while (current != end && *current >= '0' && *current <= '9'); 651 652 exponent += (sign == '-' ? -num : num); 653 } 654 655 if (!allow_trailing_junk && 656 AdvanceToNonspace(unicode_cache, ¤t, end)) { 657 return JunkStringValue(); 658 } 659 660 parsing_done: 661 exponent += insignificant_digits; 662 663 if (octal) { 664 return InternalStringToIntDouble<3>(unicode_cache, 665 buffer, 666 buffer + buffer_pos, 667 sign == NEGATIVE, 668 allow_trailing_junk); 669 } 670 671 if (nonzero_digit_dropped) { 672 buffer[buffer_pos++] = '1'; 673 exponent--; 674 } 675 676 SLOW_ASSERT(buffer_pos < kBufferSize); 677 buffer[buffer_pos] = '\0'; 678 679 double converted = Strtod(Vector<const char>(buffer, buffer_pos), exponent); 680 return (sign == NEGATIVE) ? -converted : converted; 681 } 682 683 } } // namespace v8::internal 684 685 #endif // V8_CONVERSIONS_INL_H_ 686