- Update runtime/third_party/double-conversion to version 1.1.5.

runtime/third_party/double-conversion/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 "strtod.h"
 #include "bignum.h"
 #include "cached-powers.h"
-#include "double.h"
+#include "ieee.h"
 
 namespace double_conversion {
 
 // 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;
 // 2^64 = 18446744073709551616 > 10^19
 static const int kMaxUint64DecimalDigits = 19;
 
@@ skipping 56 matching lines @@
 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,
+static void CutToMaxSignificantDigits(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);
 }
 
+
+// Trims the buffer and cuts it to at most kMaxSignificantDecimalDigits.
+// If possible the input-buffer is reused, but if the buffer needs to be
+// modified (due to cutting), then the input needs to be copied into the
+// buffer_copy_space.
+static void TrimAndCut(Vector<const char> buffer, int exponent,
+                       char* buffer_copy_space, int space_size,
+                       Vector<const char>* trimmed, int* updated_exponent) {
+  Vector<const char> left_trimmed = TrimLeadingZeros(buffer);
+  Vector<const char> right_trimmed = TrimTrailingZeros(left_trimmed);
+  exponent += left_trimmed.length() - right_trimmed.length();
+  if (right_trimmed.length() > kMaxSignificantDecimalDigits) {
+    (void) space_size;  // Mark variable as used.
+    ASSERT(space_size >= kMaxSignificantDecimalDigits);
+    CutToMaxSignificantDigits(right_trimmed, exponent,
+                              buffer_copy_space, updated_exponent);
+    *trimmed = Vector<const char>(buffer_copy_space,
+                                 kMaxSignificantDecimalDigits);
+  } else {
+    *trimmed = right_trimmed;
+    *updated_exponent = exponent;
+  }
+}
+
+
 // 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 94 matching lines @@
   switch (exponent) {
     case 1: return DiyFp(UINT64_2PART_C(0xa0000000, 00000000), -60);
     case 2: return DiyFp(UINT64_2PART_C(0xc8000000, 00000000), -57);
     case 3: return DiyFp(UINT64_2PART_C(0xfa000000, 00000000), -54);
     case 4: return DiyFp(UINT64_2PART_C(0x9c400000, 00000000), -50);
     case 5: return DiyFp(UINT64_2PART_C(0xc3500000, 00000000), -47);
     case 6: return DiyFp(UINT64_2PART_C(0xf4240000, 00000000), -44);
     case 7: return DiyFp(UINT64_2PART_C(0x98968000, 00000000), -40);
     default:
       UNREACHABLE();
-      return DiyFp(0, 0);
   }
 }
 
 
 // If the function returns true then the result is the correct double.
 // Otherwise it is either the correct double or the double that is just below
 // the correct double.
 static bool DiyFpStrtod(Vector<const char> buffer,
                         int exponent,
                         double* result) {
@@ skipping 97 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).
+// Returns
+//   - -1 if buffer*10^exponent < diy_fp.
+//   -  0 if buffer*10^exponent == diy_fp.
+//   - +1 if buffer*10^exponent > diy_fp.
 // 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 == Double::Infinity()) {
-    return guess;
-  }
-
-  DiyFp upper_boundary = Double(guess).UpperBoundary();
-
+static int CompareBufferWithDiyFp(Vector<const char> buffer,
+                                  int exponent,
+                                  DiyFp diy_fp) {
   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());
+  Bignum buffer_bignum;
+  Bignum diy_fp_bignum;
+  buffer_bignum.AssignDecimalString(buffer);
+  diy_fp_bignum.AssignUInt64(diy_fp.f());
   if (exponent >= 0) {
-    input.MultiplyByPowerOfTen(exponent);
+    buffer_bignum.MultiplyByPowerOfTen(exponent);
   } else {
-    boundary.MultiplyByPowerOfTen(-exponent);
+    diy_fp_bignum.MultiplyByPowerOfTen(-exponent);
   }
-  if (upper_boundary.e() > 0) {
-    boundary.ShiftLeft(upper_boundary.e());
+  if (diy_fp.e() > 0) {
+    diy_fp_bignum.ShiftLeft(diy_fp.e());
   } else {
-    input.ShiftLeft(-upper_boundary.e());
+    buffer_bignum.ShiftLeft(-diy_fp.e());
   }
-  int comparison = Bignum::Compare(input, boundary);
+  return Bignum::Compare(buffer_bignum, diy_fp_bignum);
+}
+
+
+// Returns true if the guess is the correct double.
+// Returns false, when guess is either correct or the next-lower double.
+static bool ComputeGuess(Vector<const char> trimmed, int exponent,
+                         double* guess) {
+  if (trimmed.length() == 0) {
+    *guess = 0.0;
+    return true;
+  }
+  if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) {
+    *guess = Double::Infinity();
+    return true;
+  }
+  if (exponent + trimmed.length() <= kMinDecimalPower) {
+    *guess = 0.0;
+    return true;
+  }
+
+  if (DoubleStrtod(trimmed, exponent, guess) ||
+      DiyFpStrtod(trimmed, exponent, guess)) {
+    return true;
+  }
+  if (*guess == Double::Infinity()) {
+    return true;
+  }
+  return false;
+}
+
+double Strtod(Vector<const char> buffer, int exponent) {
+  char copy_buffer[kMaxSignificantDecimalDigits];
+  Vector<const char> trimmed;
+  int updated_exponent;
+  TrimAndCut(buffer, exponent, copy_buffer, kMaxSignificantDecimalDigits,
+             &trimmed, &updated_exponent);
+  exponent = updated_exponent;
+
+  double guess;
+  bool is_correct = ComputeGuess(trimmed, exponent, &guess);
+  if (is_correct) return guess;
+
+  DiyFp upper_boundary = Double(guess).UpperBoundary();
+  int comparison = CompareBufferWithDiyFp(trimmed, exponent, upper_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();
   }
 }
 
+float Strtof(Vector<const char> buffer, int exponent) {
+  char copy_buffer[kMaxSignificantDecimalDigits];
+  Vector<const char> trimmed;
+  int updated_exponent;
+  TrimAndCut(buffer, exponent, copy_buffer, kMaxSignificantDecimalDigits,
+             &trimmed, &updated_exponent);
+  exponent = updated_exponent;
 
-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);
-    return Strtod(Vector<const char>(significant_buffer,
-                                     kMaxSignificantDecimalDigits),
-                  significant_exponent);
-  }
-  if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) {
-    return Double::Infinity();
-  }
-  if (exponent + trimmed.length() <= kMinDecimalPower) {
-    return 0.0;
+  double double_guess;
+  bool is_correct = ComputeGuess(trimmed, exponent, &double_guess);
+
+  float float_guess = static_cast<float>(double_guess);
+  if (float_guess == double_guess) {
+    // This shortcut triggers for integer values.
+    return float_guess;
   }
 
-  double guess;
-  if (DoubleStrtod(trimmed, exponent, &guess) ||
-      DiyFpStrtod(trimmed, exponent, &guess)) {
+  // We must catch double-rounding. Say the double has been rounded up, and is
+  // now a boundary of a float, and rounds up again. This is why we have to
+  // look at previous too.
+  // Example (in decimal numbers):
+  //    input: 12349
+  //    high-precision (4 digits): 1235
+  //    low-precision (3 digits):
+  //       when read from input: 123
+  //       when rounded from high precision: 124.
+  // To do this we simply look at the neigbors of the correct result and see
+  // if they would round to the same float. If the guess is not correct we have
+  // to look at four values (since two different doubles could be the correct
+  // double).
+
+  double double_next = Double(double_guess).NextDouble();
+  double double_previous = Double(double_guess).PreviousDouble();
+
+  float f1 = static_cast<float>(double_previous);
+  float f2 = float_guess;
+  float f3 = static_cast<float>(double_next);
+  float f4;
+  if (is_correct) {
+    f4 = f3;
+  } else {
+    double double_next2 = Double(double_next).NextDouble();
+    f4 = static_cast<float>(double_next2);
+  }
+  (void) f2;  // Mark variable as used.
+  ASSERT(f1 <= f2 && f2 <= f3 && f3 <= f4);
+
+  // If the guess doesn't lie near a single-precision boundary we can simply
+  // return its float-value.
+  if (f1 == f4) {
+    return float_guess;
+  }
+
+  ASSERT((f1 != f2 && f2 == f3 && f3 == f4) ||
+         (f1 == f2 && f2 != f3 && f3 == f4) ||
+         (f1 == f2 && f2 == f3 && f3 != f4));
+
+  // guess and next are the two possible canditates (in the same way that
+  // double_guess was the lower candidate for a double-precision guess).
+  float guess = f1;
+  float next = f4;
+  DiyFp upper_boundary;
+  if (guess == 0.0f) {
+    float min_float = 1e-45f;
+    upper_boundary = Double(static_cast<double>(min_float) / 2).AsDiyFp();
+  } else {
+    upper_boundary = Single(guess).UpperBoundary();
+  }
+  int comparison = CompareBufferWithDiyFp(trimmed, exponent, upper_boundary);
+  if (comparison < 0) {
     return guess;
+  } else if (comparison > 0) {
+    return next;
+  } else if ((Single(guess).Significand() & 1) == 0) {
+    // Round towards even.
+    return guess;
+  } else {
+    return next;
   }
-  return BignumStrtod(trimmed, exponent, guess);
 }
 
 }  // namespace double_conversion