src/v8/src/conversions-inl.h

   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/platform/platform.h"
  18 #include "src/conversions.h"
  19 #include "src/double.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   DCHECK(**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   DCHECK(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, &current, 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, &current, 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   DCHECK(number < ((int64_t)1 << 53));
 206   DCHECK(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   DCHECK(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, &current, 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         DCHECK(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, &current, end)) {
 336       return JunkStringValue();
 337     }
 338
 339     SLOW_DCHECK(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       DCHECK(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, &current, 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, &current, 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(&current, end, kInfinityString)) {
 468       return JunkStringValue();
 469     }
 470
 471     if (!allow_trailing_junk &&
 472         AdvanceToNonspace(unicode_cache, &current, end)) {
 473       return JunkStringValue();
 474     }
 475
 476     DCHECK(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       DCHECK(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         DCHECK(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     DCHECK(-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, &current, 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_DCHECK(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_