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