Fast algorithm for double->string conversion.

test/cctest/test-grisu3.cc

Index: test/cctest/test-grisu3.cc
===================================================================
--- test/cctest/test-grisu3.cc	(revision 0)
+++ test/cctest/test-grisu3.cc	(revision 0)
@@ -0,0 +1,217 @@
+// Copyright 2006-2008 the V8 project authors. All rights reserved.
+
+#include <stdlib.h>
+
+#include "v8.h"
+
+#include "platform.h"
+#include "cctest.h"
+#include "double.h"
+#include "grisu3.h"
+
+using namespace v8::internal;
+
+static const int kBufferSize = 50;
+
+TEST(DoubleExtremes) {
+  char buffer[kBufferSize];
+  int length;
+  int point;
+  int sign;
+  bool status;
+  double min_double = 5e-324;
+  status = grisu3(min_double, buffer, &sign, &length, &point);
+  CHECK(status);
+  CHECK_EQ("5", buffer);
+  CHECK_EQ(-323, point);
+
+  double max_double = 1.7976931348623157e308;
+  status = grisu3(max_double, buffer, &sign, &length, &point);
+  CHECK(status);
+  CHECK_EQ("17976931348623157", buffer);
+  CHECK_EQ(309, point);
+}
+
+
+static long double MyFabsL(long double d) {
+  if (d < 0.0)
+    return -d;
+  else
+    return d;
+}
+
+
+
+static bool IsCorrect(double v, char* buffer, int sign, int length, int k) {
+  // First test if the result is correct
+  return v == sign * atof(buffer);
+}
+
+
+static bool IsRounded(double v, char* buffer, int sign, int length, int k) {
+  long double lv = v;
+  long double lbuffer;
+  sscanf(buffer, "%Lf", &lbuffer);
+  lbuffer *= sign;
+  if (buffer[length-1] != '1') {
+    long double lower;
+    buffer[length-1]--;
+    if (v == sign * atof(buffer)) {
+      // The lower buffer is a possible solution too. Let's see if it is closer.
+      sscanf(buffer, "%Lf", &lower);
+      lower *= sign;
+      if (MyFabsL(lv-lower) < MyFabsL(lv-lbuffer))
+        return false;
+    }
+    buffer[length-1]++;
+  }
+  if (buffer[length-1] != '9') {
+    long double bigger;
+    buffer[length-1]++;
+    if (v == sign*atof(buffer)) {
+      sscanf(buffer, "%Lf", &bigger);
+      bigger *= sign;
+      if (MyFabsL(lv-bigger) < MyFabsL(lv-lbuffer))
+        return false;
+    }
+    buffer[length-1]--;
+  }
+  return true;
+}
+
+
+static bool IsShortest(double v, char* buffer, int sign, int length, int k) {
+  // Now test if a shorter version would still yield the same result.
+  // Not an exhaustive test, but better than nothing.
+  buffer[length-1] = 'e';
+  snprintf(&buffer[length], kBufferSize - length - 1, "%d", k+1);
+  if (v == sign * atof(buffer)) return false;
+  if (buffer[length-2] != '9') {
+    buffer[length-2]++;
+    snprintf(&buffer[length], kBufferSize - length - 1, "%d", k+1);
+    if (v == sign * atof(buffer)) return false;
+  }
+  return true;
+}
+
+
+TEST(VariousDoubles) {
+  char buffer[kBufferSize];
+  int length;
+  int point;
+  int sign;
+  int status;
+  status = grisu3(4294967272.0, buffer, &sign, &length, &point);
+  CHECK(status);
+  CHECK_EQ("4294967272", buffer);
+  CHECK_EQ(10, point);
+
+  status = grisu3(4.1855804968213567e298, buffer, &sign, &length, &point);
+  CHECK(status);
+  CHECK_EQ("4185580496821357", buffer);
+  CHECK_EQ(299, point);
+
+  status = grisu3(5.5626846462680035e-309, buffer, &sign, &length, &point);
+  CHECK(status);
+  CHECK_EQ("5562684646268003", buffer);
+  CHECK_EQ(-308, point);
+
+  status = grisu3(-2147483648.0, buffer, &sign, &length, &point);
+  CHECK(status);
+  CHECK_EQ(1, sign);
+  CHECK_EQ("2147483648", buffer);
+  CHECK_EQ(10, point);
+
+  status = grisu3(-3.5844466002796428e+298, buffer, &sign, &length, &point);
+  if (status) {  // Not all grisu3 variants manage to compute this number.
+    CHECK_EQ(1, sign);
+    CHECK_EQ("35844466002796428", buffer);
+    CHECK_EQ(299, point);
+  }
+
+  uint64_t smallest_normal64 = V8_2PART_UINT64_C(0x00100000,00000000);
+  double v = Double(smallest_normal64).value();
+  status = grisu3(v, buffer, &sign, &length, &point);
+  if (sign == 0) {
+    sign = 1;
+  } else {
+    sign = -1;
+  }
+  if (status) {
+    int k = point - length;
+    // Integrate exponent into buffer.
+    buffer[length] = 'e';
+    snprintf(&buffer[length+1], kBufferSize - length - 1, "%d", k);
+    CHECK(IsCorrect(v, buffer, sign, length, k));
+    CHECK(IsRounded(v, buffer, sign, length, k));
+    CHECK(IsShortest(v, buffer, sign, length, k));
+  }
+
+  uint64_t largest_denormal64 = V8_2PART_UINT64_C(0x000FFFFF,FFFFFFFF);
+  v = Double(largest_denormal64).value();
+  status = grisu3(v, buffer, &sign, &length, &point);
+  if (sign == 0) {
+    sign = 1;
+  } else {
+    sign = -1;
+  }
+  if (status) {
+    int k = point - length;
+    // Integrate exponent into buffer.
+    buffer[length] = 'e';
+    snprintf(&buffer[length+1], kBufferSize - length - 1, "%d", k);
+    CHECK(IsCorrect(v, buffer, sign, length, k));
+    CHECK(IsRounded(v, buffer, sign, length, k));
+    CHECK(IsShortest(v, buffer, sign, length, k));
+  }
+}
+
+
+static double random_double() {
+  uint64_t double64 = 0;
+  for (int i = 0; i < 8; i++) {
+    double64 <<= 8;
+    double64 += rand() % 256;
+  }
+  return Double(double64).value();
+}
+
+
+TEST(RandomDoubles) {
+  // For a more thorough testing increase the iteration count.
+  // We also check kGrisu3MaximalLength in here.
+  const int kIterationCount = 100000;
+  int succeeded = 0;
+  int total = 0;
+  char buffer[kBufferSize];
+  int length;
+  int point;
+  int sign;
+  bool needed_max_length = false;
+
+  for (int i = 0; i < kIterationCount; ++i) {
+    double v = random_double();
+    if (v != v) continue;  // NaN
+    if (v == 0.0) continue;
+    total++;
+    int status = grisu3(v, buffer, &sign, &length, &point);
+    CHECK_GE(kGrisu3MaximalLength, length);
+    if (length == kGrisu3MaximalLength) needed_max_length = true;
+    if (sign == 0) {
+      sign = 1;
+    } else {
+      sign = -1;
+    }
+    if (!status) continue;
+    succeeded++;
+    int k = point - length;
+    // Integrate exponent into buffer.
+    buffer[length] = 'e';
+    snprintf(&buffer[length+1], kBufferSize - length - 1, "%d", k);
+    CHECK(IsCorrect(v, buffer, sign, length, k));
+    CHECK(IsRounded(v, buffer, sign, length, k));
+    CHECK(IsShortest(v, buffer, sign, length, k));
+  }
+  CHECK_GT(succeeded*1.0/total, 0.99);
+  CHECK(needed_max_length);
+}