StringToInt rewritten. This version doesn't allocate memory for long decimals...

src/conversions.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 30 matching lines @@
 int HexValue(uc32 c) {
   if ('0' <= c && c <= '9')
     return c - '0';
   if ('a' <= c && c <= 'f')
     return c - 'a' + 10;
   if ('A' <= c && c <= 'F')
     return c - 'A' + 10;
   return -1;
 }
 
-
-// Provide a common interface to getting a character at a certain
-// index from a char* or a String object.
-static inline int GetChar(const char* str, int index) {
-  ASSERT(index >= 0 && index < StrLength(str));
-  return str[index];
-}
-
-
-static inline int GetChar(String* str, int index) {
-  return str->Get(index);
-}
-
-
-static inline int GetLength(const char* str) {
-  return StrLength(str);
-}
-
-
-static inline int GetLength(String* str) {
-  return str->length();
-}
-
-
-static inline const char* GetCString(const char* str, int index) {
-  return str + index;
-}
-
-
-static inline const char* GetCString(String* str, int index) {
-  int length = str->length();
-  char* result = NewArray<char>(length + 1);
-  for (int i = index; i < length; i++) {
-    uc16 c = str->Get(i);
-    if (c <= 127) {
-      result[i - index] = static_cast<char>(c);
-    } else {
-      result[i - index] = 127;  // Force number parsing to fail.
-    }
-  }
-  result[length - index] = '\0';
-  return result;
-}
-
-
 namespace {
 
 // C++-style iterator adaptor for StringInputBuffer
 // (unlike C++ iterators the end-marker has different type).
 class StringInputBufferIterator {
  public:
   class EndMarker {};
 
   explicit StringInputBufferIterator(StringInputBuffer* buffer);
 
@@ skipping 21 matching lines @@
 
 void StringInputBufferIterator::operator++() {
   end_ = !buffer_->has_more();
   if (!end_) {
     current_ = buffer_->GetNext();
   }
 }
 }
 
 
-static inline void ReleaseCString(const char* original, const char* str) {
-}
-
-
-static inline void ReleaseCString(String* original, const char* str) {
-  DeleteArray(const_cast<char *>(str));
-}
-
-
 template <class Iterator, class EndMark>
 static bool SubStringEquals(Iterator* current,
                             EndMark end,
                             const char* substring) {
   ASSERT(**current == *substring);
   for (substring++; *substring != '\0'; substring++) {
     ++*current;
     if (*current == end || **current != *substring) return false;
   }
   ++*current;
   return true;
 }
 
 
 extern "C" double gay_strtod(const char* s00, const char** se);
 
 // Maximum number of significant digits in decimal representation.
 // The longest possible double in decimal representation is
 // (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074
 // (768 digits). If we parse a number whose first digits are equal to a
 // mean of 2 adjacent doubles (that could have up to 769 digits) the result
 // must be rounded to the bigger one unless the tail consists of zeros, so
 // we don't need to preserve all the digits.
 const int kMaxSignificantDigits = 772;
 
-// Parse an int from a string starting a given index and in a given
-// radix.  The string can be either a char* or a String*.
-template <class S>
-static int InternalStringToInt(S* s, int i, int radix, double* value) {
-  int len = GetLength(s);
-
-  // Setup limits for computing the value.
-  ASSERT(2 <= radix && radix <= 36);
-  int lim_0 = '0' + (radix < 10 ? radix : 10);
-  int lim_a = 'a' + (radix - 10);
-  int lim_A = 'A' + (radix - 10);
-
-  // NOTE: The code for computing the value may seem a bit complex at
-  // first glance. It is structured to use 32-bit multiply-and-add
-  // loops as long as possible to avoid loosing precision.
-
-  double v = 0.0;
-  int j;
-  for (j = i; j < len;) {
-    // Parse the longest part of the string starting at index j
-    // possible while keeping the multiplier, and thus the part
-    // itself, within 32 bits.
-    uint32_t part = 0, multiplier = 1;
-    int k;
-    for (k = j; k < len; k++) {
-      int c = GetChar(s, k);
-      if (c >= '0' && c < lim_0) {
-        c = c - '0';
-      } else if (c >= 'a' && c < lim_a) {
-        c = c - 'a' + 10;
-      } else if (c >= 'A' && c < lim_A) {
-        c = c - 'A' + 10;
-      } else {
-        break;
-      }
-
-      // Update the value of the part as long as the multiplier fits
-      // in 32 bits. When we can't guarantee that the next iteration
-      // will not overflow the multiplier, we stop parsing the part
-      // by leaving the loop.
-      static const uint32_t kMaximumMultiplier = 0xffffffffU / 36;
-      uint32_t m = multiplier * radix;
-      if (m > kMaximumMultiplier) break;
-      part = part * radix + c;
-      multiplier = m;
-      ASSERT(multiplier > part);
-    }
-
-    // Compute the number of part digits. If no digits were parsed;
-    // we're done parsing the entire string.
-    int digits = k - j;
-    if (digits == 0) break;
-
-    // Update the value and skip the part in the string.
-    ASSERT(multiplier ==
-           pow(static_cast<double>(radix), static_cast<double>(digits)));
-    v = v * multiplier + part;
-    j = k;
-  }
-
-  // If the resulting value is larger than 2^53 the value does not fit
-  // in the mantissa of the double and there is a loss of precision.
-  // When the value is larger than 2^53 the rounding depends on the
-  // code generation.  If the code generator spills the double value
-  // it uses 64 bits and if it does not it uses 80 bits.
-  //
-  // If there is a potential for overflow we resort to strtod for
-  // radix 10 numbers to get higher precision.  For numbers in another
-  // radix we live with the loss of precision.
-  static const double kPreciseConversionLimit = 9007199254740992.0;
-  if (radix == 10 && v > kPreciseConversionLimit) {
-    const char* cstr = GetCString(s, i);
-    const char* end;
-    v = gay_strtod(cstr, &end);
-    ReleaseCString(s, cstr);
-  }
-
-  *value = v;
-  return j;
-}
-
-
-int StringToInt(String* str, int index, int radix, double* value) {
-  return InternalStringToInt(str, index, radix, value);
-}
-
-
-int StringToInt(const char* str, int index, int radix, double* value) {
-  return InternalStringToInt(const_cast<char*>(str), index, radix, value);
-}
-
 
 static const double JUNK_STRING_VALUE = OS::nan_value();
 
 
 // Returns true if a nonspace found and false if the end has reached.
 template <class Iterator, class EndMark>
 static inline bool AdvanceToNonspace(Iterator* current, EndMark end) {
   while (*current != end) {
     if (!Scanner::kIsWhiteSpace.get(**current)) return true;
     ++*current;
   }
   return false;
 }
 
 
 static bool isDigit(int x, int radix) {
   return (x >= '0' && x <= '9' && x < '0' + radix)
       || (radix > 10 && x >= 'a' && x < 'a' + radix - 10)
       || (radix > 10 && x >= 'A' && x < 'A' + radix - 10);
 }
 
 
+static double SignedZero(bool sign) {
+  return sign ? -0.0 : 0.0;
+}
+
+
 // Parsing integers with radix 2, 4, 8, 16, 32. Assumes current != end.
 template <int radix_log_2, class Iterator, class EndMark>
-    static double InternalStringToIntDouble(Iterator current,
-                                            EndMark end,
-                                            bool sign,
-                                            bool allow_trailing_junk) {
+static double InternalStringToIntDouble(Iterator current,
+                                        EndMark end,
+                                        bool sign,
+                                        bool allow_trailing_junk) {
   ASSERT(current != end);
 
   // Skip leading 0s.
   while (*current == '0') {
     ++current;
-    if (current == end) return sign ? -0.0 : 0.0;
+    if (current == end) return SignedZero(sign);
   }
 
   int64_t number = 0;
   int exponent = 0;
   const int radix = (1 << radix_log_2);
 
   do {
     int digit;
     if (*current >= '0' && *current <= '9' && *current < '0' + radix) {
       digit = static_cast<char>(*current) - '0';
@@ skipping 69 matching lines @@
     return static_cast<double>(number);
   }
 
   ASSERT(number != 0);
   // The double could be constructed faster from number (mantissa), exponent
   // and sign. Assuming it's a rare case more simple code is used.
   return static_cast<double>(sign ? -number : number) * pow(2.0, exponent);
 }
 
 
+template <class Iterator, class EndMark>
+static double InternalStringToInt(Iterator current, EndMark end, int radix) {
+  const bool allow_trailing_junk = true;
+  const double empty_string_val = JUNK_STRING_VALUE;
+
+  if (!AdvanceToNonspace(&current, end)) return empty_string_val;
+
+  bool sign = false;
+  bool leading_zero = false;
+
+  if (*current == '+') {
+    // Ignore leading sign; skip following spaces.
+    ++current;
+    if (!AdvanceToNonspace(&current, end)) return JUNK_STRING_VALUE;
+  } else if (*current == '-') {
+    ++current;
+    if (!AdvanceToNonspace(&current, end)) return JUNK_STRING_VALUE;
+    sign = true;
+  }
+
+  if (radix == 0) {
+    // Radix detection.
+    if (*current == '0') {
+      ++current;
+      if (current == end) return SignedZero(sign);
+      if (*current == 'x' || *current == 'X') {
+        radix = 16;
+        ++current;
+        if (current == end) return JUNK_STRING_VALUE;
+      } else {
+        radix = 8;
+        leading_zero = true;
+      }
+    } else {
+      radix = 10;
+    }
+  } else if (radix == 16) {
+    if (*current == '0') {
+      // Allow "0x" prefix.
+      ++current;
+      if (current == end) return SignedZero(sign);
+      if (*current == 'x' || *current == 'X') {
+        ++current;
+        if (current == end) return JUNK_STRING_VALUE;
+      } else {
+        leading_zero = true;
+      }
+    }
+  }
+
+  if (radix < 2 || radix > 36) return JUNK_STRING_VALUE;
+
+  // Skip leading zeros.
+  while (*current == '0') {
+    leading_zero = true;
+    ++current;
+    if (current == end) return SignedZero(sign);
+  }
+
+  if (!leading_zero && !isDigit(*current, radix)) {
+    return JUNK_STRING_VALUE;
+  }
+
+  if (IsPowerOf2(radix)) {
+    switch (radix) {
+      case 2:
+        return InternalStringToIntDouble<1>(
+                   current, end, sign, allow_trailing_junk);
+      case 4:
+        return InternalStringToIntDouble<2>(
+                   current, end, sign, allow_trailing_junk);
+      case 8:
+        return InternalStringToIntDouble<3>(
+                   current, end, sign, allow_trailing_junk);
+
+      case 16:
+        return InternalStringToIntDouble<4>(
+                   current, end, sign, allow_trailing_junk);
+
+      case 32:
+        return InternalStringToIntDouble<5>(
+                   current, end, sign, allow_trailing_junk);
+      default:
+        UNREACHABLE();
+    }
+  }
+
+  if (radix == 10) {
+    // Parsing with strtod.
+    const int kMaxSignificantDigits = 309;  // Doubles are less than 1.8e308.
+    // The buffer may contain up to kMaxSignificantDigits + 1 digits and a zero

[Florian Loitsch, 2010/03/31 16:50:00]

Maybe add comment:
A number with more than kMaxSignificantDigits digits will be read as Infinity.

[SeRya, 2010/03/31 17:18:08]

The comment 7 lines below says the same. I think that is place more suitable
since digits are dropped there and it explaines why it's safe.

[Florian Loitsch, 2010/04/03 13:10:59]

true. fine with me.

+    // end.
+    const int kBufferSize = kMaxSignificantDigits + 2;
+    char buffer[kBufferSize];
+    int buffer_pos = 0;
+    while (*current >= '0' && *current <= '9') {
+      if (buffer_pos <= kMaxSignificantDigits) {
+        // If the number has more than kMaxSignificantDigits it will be parsed
+        // as infinity.
+        ASSERT(buffer_pos < kBufferSize);
+        buffer[buffer_pos++] = static_cast<char>(*current);
+      }
+      ++current;
+      if (current == end) break;
+    }
+
+    if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
+      return JUNK_STRING_VALUE;
+    }
+
+    ASSERT(buffer_pos < kBufferSize);
+    buffer[buffer_pos++] = '\0';
+    return sign ? -gay_strtod(buffer, NULL) : gay_strtod(buffer, NULL);
+  }
+
+  // TODO(serya): The following legacy code causes accumulating rounding
+  // error for number greater than ~2^56. It should be rewritten using long
+  // arithmetic.
+
+  int lim_0 = '0' + (radix < 10 ? radix : 10);
+  int lim_a = 'a' + (radix - 10);
+  int lim_A = 'A' + (radix - 10);
+
+  // NOTE: The code for computing the value may seem a bit complex at
+  // first glance. It is structured to use 32-bit multiply-and-add
+  // loops as long as possible to avoid loosing precision.
+
+  double v = 0.0;
+  bool done = false;
+  do {
+    // Parse the longest part of the string starting at index j
+    // possible while keeping the multiplier, and thus the part
+    // itself, within 32 bits.
+    unsigned int part = 0, multiplier = 1;
+    while (true) {
+      int d;
+      if (*current >= '0' && *current < lim_0) {
+        d = *current - '0';
+      } else if (*current >= 'a' && *current < lim_a) {
+        d = *current - 'a' + 10;
+      } else if (*current >= 'A' && *current < lim_A) {
+        d = *current - 'A' + 10;
+      } else {
+        done = true;
+        break;
+      }
+
+      // Update the value of the part as long as the multiplier fits
+      // in 32 bits. When we can't guarantee that the next iteration
+      // will not overflow the multiplier, we stop parsing the part
+      // by leaving the loop.
+      const unsigned int kMaximumMultiplier = 0xffffffffU / 36;
+      uint32_t m = multiplier * radix;
+      if (m > kMaximumMultiplier) break;
+      part = part * radix + d;
+      multiplier = m;
+      ASSERT(multiplier > part);
+
+      ++current;
+      if (current == end) {
+        done = true;
+        break;
+      }
+    }
+
+    // Update the value and skip the part in the string.
+    v = v * multiplier + part;
+  } while (!done);
+
+  if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
+    return JUNK_STRING_VALUE;
+  }
+
+  return sign ? -v : v;
+}
+
+
 // Converts a string to a double value. Assumes the Iterator supports
 // the following operations:
 // 1. current == end (other ops are not allowed), current != end.
 // 2. *current - gets the current character in the sequence.
 // 3. ++current (advances the position).
 template <class Iterator, class EndMark>
 static double InternalStringToDouble(Iterator current,
                                      EndMark end,
                                      int flags,
                                      double empty_string_val) {
@@ skipping 15 matching lines @@
   int buffer_pos = 0;
 
   // Exponent will be adjusted if insignificant digits of the integer part
   // or insignificant leading zeros of the fractional part are dropped.
   int exponent = 0;
   int significant_digits = 0;
   int insignificant_digits = 0;
   bool nonzero_digit_dropped = false;
   bool fractional_part = false;
 
-  double signed_zero = 0.0;
+  bool sign = false;
 
   if (*current == '+') {
     // Ignore leading sign; skip following spaces.
     ++current;
     if (!AdvanceToNonspace(&current, end)) return JUNK_STRING_VALUE;
   } else if (*current == '-') {
     buffer[buffer_pos++] = '-';
     ++current;
     if (!AdvanceToNonspace(&current, end)) return JUNK_STRING_VALUE;
-    signed_zero = -0.0;
+    sign = true;
   }
 
   static const char kInfinitySymbol[] = "Infinity";
   if (*current == kInfinitySymbol[0]) {
     if (!SubStringEquals(&current, end, kInfinitySymbol)) {
       return JUNK_STRING_VALUE;
     }
 
     if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
       return JUNK_STRING_VALUE;
     }
 
     ASSERT(buffer_pos == 0 || buffer[0] == '-');
     return buffer_pos > 0 ? -V8_INFINITY : V8_INFINITY;
   }
 
   bool leading_zero = false;
   if (*current == '0') {
     ++current;
-    if (current == end) return signed_zero;
+    if (current == end) return SignedZero(sign);
 
     leading_zero = true;
 
-// It could be hexadecimal value.
+    // It could be hexadecimal value.
     if ((flags & ALLOW_HEX) && (*current == 'x' || *current == 'X')) {
       ++current;
-      if (current == end) return JUNK_STRING_VALUE;  // "0x".
+      if (current == end || !isDigit(*current, 16)) {
+        return JUNK_STRING_VALUE;  // "0x".
+      }
 
       bool sign = (buffer_pos > 0 && buffer[0] == '-');
       return InternalStringToIntDouble<4>(current,
                                           end,
                                           sign,
                                           allow_trailing_junk);
     }
 
     // Ignore leading zeros in the integer part.
     while (*current == '0') {
       ++current;
-      if (current == end) return signed_zero;
+      if (current == end) return SignedZero(sign);
     }
   }
 
   bool octal = leading_zero && (flags & ALLOW_OCTALS) != 0;
 
   // Copy significant digits of the integer part (if any) to the buffer.
   while (*current >= '0' && *current <= '9') {
     if (significant_digits < kMaxSignificantDigits) {
       ASSERT(buffer_pos < kBufferSize);
       buffer[buffer_pos++] = static_cast<char>(*current);
@@ skipping 21 matching lines @@
         goto parsing_done;
       }
     }
 
     if (significant_digits == 0) {
       // octal = false;
       // Integer part consists of 0 or is absent. Significant digits start after
       // leading zeros (if any).
       while (*current == '0') {
         ++current;
-        if (current == end) return signed_zero;
+        if (current == end) return SignedZero(sign);
         exponent--;  // Move this 0 into the exponent.
       }
     }
 
     ASSERT(buffer_pos < kBufferSize);
     buffer[buffer_pos++] = '.';
     fractional_part = true;
 
     // There is the fractional part.
     while (*current >= '0' && *current <= '9') {
@@ skipping 106 matching lines @@
     if (exponent > 999) exponent = 999;  // Result will be Infinity or 0 or -0.
 
     const int exp_digits = 3;
     for (int i = 0; i < exp_digits; i++) {
       buffer[buffer_pos + exp_digits - 1 - i] = '0' + exponent % 10;
       exponent /= 10;
     }
     ASSERT(exponent == 0);
     buffer_pos += exp_digits;
   } else if (!fractional_part && significant_digits <= kMaxDigitsInInt) {
-    if (significant_digits == 0) return signed_zero;
+    if (significant_digits == 0) return SignedZero(sign);
     ASSERT(buffer_pos > 0);
     int num = 0;
     int start_pos = (buffer[0] == '-' ? 1 : 0);
     for (int i = start_pos; i < buffer_pos; i++) {
       ASSERT(buffer[i] >= '0' && buffer[i] <= '9');
       num = 10 * num + (buffer[i] - '0');
     }
     return static_cast<double>(start_pos == 0 ? num : -num);
   }
 
@@ skipping 16 matching lines @@
   } else {
     StringInputBuffer buffer(str);
     return InternalStringToDouble(StringInputBufferIterator(&buffer),
                                   StringInputBufferIterator::EndMarker(),
                                   flags,
                                   empty_string_val);
   }
 }
 
 
+double StringToInt(String* str, int radix) {
+  StringShape shape(str);
+  if (shape.IsSequentialAscii()) {
+    const char* begin = SeqAsciiString::cast(str)->GetChars();
+    const char* end = begin + str->length();
+    return InternalStringToInt(begin, end, radix);
+  } else if (shape.IsSequentialTwoByte()) {
+    const uc16* begin = SeqTwoByteString::cast(str)->GetChars();
+    const uc16* end = begin + str->length();
+    return InternalStringToInt(begin, end, radix);
+  } else {
+    StringInputBuffer buffer(str);
+    return InternalStringToInt(StringInputBufferIterator(&buffer),
+                               StringInputBufferIterator::EndMarker(),
+                               radix);
+  }
+}
+
+
 double StringToDouble(const char* str, int flags, double empty_string_val) {
   const char* end = str + StrLength(str);
 
   return InternalStringToDouble(str, end, flags, empty_string_val);
 }
 
 
 extern "C" char* dtoa(double d, int mode, int ndigits,
                       int* decpt, int* sign, char** rve);
 
@@ skipping 350 matching lines @@
   // Allocate result and fill in the parts.
   StringBuilder builder(result_size + 1);
   builder.AddSubstring(integer_buffer + integer_pos + 1, integer_part_size);
   if (decimal_pos > 0) builder.AddCharacter('.');
   builder.AddSubstring(decimal_buffer, decimal_pos);
   return builder.Finalize();
 }
 
 
 } }  // namespace v8::internal