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/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, &current, 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, &current, 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, &current, 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, &current, 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, &current, 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, &current, 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(&current, end, kInfinityString)) {
 477       return JunkStringValue();
 478     }
 479
 480     if (!allow_trailing_junk &&
 481         AdvanceToNonspace(unicode_cache, &current, 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, &current, 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_