Bignum implementation of Strtod.

src/strtod.cc

 // Copyright 2010 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 13 matching lines @@
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include <stdarg.h>
 #include <limits.h>
 
 #include "v8.h"
 
 #include "strtod.h"
+#include "bignum.h"
 #include "cached-powers.h"
 #include "double.h"
 
 namespace v8 {
 namespace internal {
 
 // 2^53 = 9007199254740992.
 // Any integer with at most 15 decimal digits will hence fit into a double
 // (which has a 53bit significand) without loss of precision.
 static const int kMaxExactDoubleIntegerDecimalDigits = 15;
@@ skipping 32 matching lines @@
   1000000000000000.0,
   10000000000000000.0,
   100000000000000000.0,
   1000000000000000000.0,
   10000000000000000000.0,
   100000000000000000000.0,  // 10^20
   1000000000000000000000.0,
   // 10^22 = 0x21e19e0c9bab2400000 = 0x878678326eac9 * 2^22
   10000000000000000000000.0
 };
-
 static const int kExactPowersOfTenSize = ARRAY_SIZE(exact_powers_of_ten);
 
-
-extern "C" double gay_strtod(const char* s00, const char** se);
-
-static double old_strtod(Vector<const char> buffer, int exponent) {
-  // gay_strtod is broken on Linux,x86. For numbers with few decimal digits
-  // the computation is done using floating-point operations which (on Linux)
-  // are prone to double-rounding errors.
-  // By adding several zeroes to the buffer gay_strtod falls back to a slower
-  // (but correct) algorithm.
-  const int kInsertedZeroesCount = 20;
-  char gay_buffer[1024];
-  Vector<char> gay_buffer_vector(gay_buffer, sizeof(gay_buffer));
-  int pos = 0;
-  for (int i = 0; i < buffer.length(); ++i) {
-    gay_buffer_vector[pos++] = buffer[i];
-  }
-  for (int i = 0; i < kInsertedZeroesCount; ++i) {
-    gay_buffer_vector[pos++] = '0';
-  }
-  exponent -= kInsertedZeroesCount;
-  gay_buffer_vector[pos++] = 'e';
-  if (exponent < 0) {
-    gay_buffer_vector[pos++] = '-';
-    exponent = -exponent;
-  }
-  const int kNumberOfExponentDigits = 5;
-  for (int i = kNumberOfExponentDigits - 1; i >= 0; i--) {
-    gay_buffer_vector[pos + i] = exponent % 10 + '0';
-    exponent /= 10;
-  }
-  pos += kNumberOfExponentDigits;
-  gay_buffer_vector[pos] = '\0';
-  return gay_strtod(gay_buffer, NULL);
-}
-
+// Maximum number of significant digits in the decimal representation.
+// In fact the value is 772 (see conversions.cc), but to give us some margin
+// we round up to 780.
+static const int kMaxSignificantDecimalDigits = 780;
 
 static Vector<const char> TrimLeadingZeros(Vector<const char> buffer) {
   for (int i = 0; i < buffer.length(); i++) {
     if (buffer[i] != '0') {
       return buffer.SubVector(i, buffer.length());
     }
   }
   return Vector<const char>(buffer.start(), 0);
 }
 
 
 static Vector<const char> TrimTrailingZeros(Vector<const char> buffer) {
   for (int i = buffer.length() - 1; i >= 0; --i) {
     if (buffer[i] != '0') {
       return buffer.SubVector(0, i + 1);
     }
   }
   return Vector<const char>(buffer.start(), 0);
 }
 
 
+static void TrimToMaxSignificantDigits(Vector<const char> buffer,
+                                       int exponent,
+                                       char* significant_buffer,
+                                       int* significant_exponent) {
+  for (int i = 0; i < kMaxSignificantDecimalDigits - 1; ++i) {
+    significant_buffer[i] = buffer[i];
+  }
+  // The input buffer has been trimmed. Therefore the last digit must be
+  // different from '0'.
+  ASSERT(buffer[buffer.length() - 1] != '0');
+  // Set the last digit to be non-zero. This is sufficient to guarantee
+  // correct rounding.
+  significant_buffer[kMaxSignificantDecimalDigits - 1] = '1';
+  *significant_exponent =
+      exponent + (buffer.length() - kMaxSignificantDecimalDigits);
+}
+
 // Reads digits from the buffer and converts them to a uint64.
 // Reads in as many digits as fit into a uint64.
 // When the string starts with "1844674407370955161" no further digit is read.
 // Since 2^64 = 18446744073709551616 it would still be possible read another
 // digit if it was less or equal than 6, but this would complicate the code.
 static uint64_t ReadUint64(Vector<const char> buffer,
                            int* number_of_read_digits) {
   uint64_t result = 0;
   int i = 0;
   while (i < buffer.length() && result <= (kMaxUint64 / 10 - 1)) {
@@ skipping 212 matching lines @@
     // Too imprecise. The caller will have to fall back to a slower version.
     // However the returned number is guaranteed to be either the correct
     // double, or the next-lower double.
     return false;
   } else {
     return true;
   }
 }
 
 
+// Returns the correct double for the buffer*10^exponent.
+// The variable guess should be a close guess that is either the correct double
+// or its lower neighbor (the nearest double less than the correct one).
+// Preconditions:
+//   buffer.length() + exponent <= kMaxDecimalPower + 1
+//   buffer.length() + exponent > kMinDecimalPower
+//   buffer.length() <= kMaxDecimalSignificantDigits
+static double BignumStrtod(Vector<const char> buffer,
+                           int exponent,
+                           double guess) {
+  if (guess == V8_INFINITY) {
+    return guess;
+  }
+
+  DiyFp upper_boundary = Double(guess).UpperBoundary();
+
+  ASSERT(buffer.length() + exponent <= kMaxDecimalPower + 1);
+  ASSERT(buffer.length() + exponent > kMinDecimalPower);
+  ASSERT(buffer.length() <= kMaxSignificantDecimalDigits);
+  // Make sure that the Bignum will be able to hold all our numbers.
+  // Our Bignum implementation has a separate field for exponents. Shifts will
+  // consume at most one bigit (< 64 bits).
+  // ln(10) == 3.3219...
+  ASSERT(((kMaxDecimalPower + 1) * 333 / 100) < Bignum::kMaxSignificantBits);
+  Bignum input;
+  Bignum boundary;
+  input.AssignDecimalString(buffer);
+  boundary.AssignUInt64(upper_boundary.f());
+  if (exponent >= 0) {
+    input.MultiplyByPowerOfTen(exponent);
+  } else {
+    boundary.MultiplyByPowerOfTen(-exponent);
+  }
+  if (upper_boundary.e() > 0) {
+    boundary.ShiftLeft(upper_boundary.e());
+  } else {
+    input.ShiftLeft(-upper_boundary.e());
+  }
+  int comparison = Bignum::Compare(input, boundary);
+  if (comparison < 0) {
+    return guess;
+  } else if (comparison > 0) {
+    return Double(guess).NextDouble();
+  } else if ((Double(guess).Significand() & 1) == 0) {
+    // Round towards even.
+    return guess;
+  } else {
+    return Double(guess).NextDouble();
+  }
+}
+
+
 double Strtod(Vector<const char> buffer, int exponent) {
   Vector<const char> left_trimmed = TrimLeadingZeros(buffer);
   Vector<const char> trimmed = TrimTrailingZeros(left_trimmed);
   exponent += left_trimmed.length() - trimmed.length();
   if (trimmed.length() == 0) return 0.0;
+  if (trimmed.length() > kMaxSignificantDecimalDigits) {
+    char significant_buffer[kMaxSignificantDecimalDigits];
+    int significant_exponent;
+    TrimToMaxSignificantDigits(trimmed, exponent,
+                               significant_buffer, &significant_exponent);
+    trimmed =
+        Vector<const char>(significant_buffer, kMaxSignificantDecimalDigits);
+    exponent = significant_exponent;
+  }
   if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) return V8_INFINITY;
   if (exponent + trimmed.length() <= kMinDecimalPower) return 0.0;
 
-  double result;
-  if (DoubleStrtod(trimmed, exponent, &result) ||
-      DiyFpStrtod(trimmed, exponent, &result)) {
-    return result;
+  double guess;
+  if (DoubleStrtod(trimmed, exponent, &guess) ||
+      DiyFpStrtod(trimmed, exponent, &guess)) {
+    return guess;
   }
-  return old_strtod(trimmed, exponent);
+  return BignumStrtod(trimmed, exponent, guess);
 }
 
 } }  // namespace v8::internal