Fast algorithm for double->string conversion.

test/cctest/test-grisu3.cc

+// Copyright 2006-2008 the V8 project authors. All rights reserved.
+
+#include <stdlib.h>
+
+#include "v8.h"
+
+#include "platform.h"
+#include "cctest.h"
+#include "diy_fp.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 long double ComposeDouble(
+    char* buffer, int sign, int length, int point) {
+  int k = point - length;
+  // Integrate exponent into buffer.
+  buffer[length] = 'e';
+  snprintf(&buffer[length+1], kBufferSize - length - 1, "%d", k);
+  long double result;
+  sscanf(buffer, "%Lf", &result);  // NOLINT
+  if (sign) {
+    result *= -1;
+  }
+  return result;
+}
+
+
+static bool IsCorrect(double v, char* buffer, int sign, int length, int point) {
+  return v == static_cast<double>(ComposeDouble(buffer, sign, length, point));
+}
+
+// IsRounded relies on the precision of long doubles. There might be false
+// positives and negatives.
+static bool IsRounded(double v, char* buffer, int sign, int length, int point) {
+  long double lv = v;
+  long double lbuffer;
+  long double unit;
+  char temp_buffer[20];
+  int k = point - length;
+  int i = 0;
+
+  temp_buffer[i++] = '1';
+  unit = ComposeDouble(temp_buffer, 0, 1, 1 + k);
+  lbuffer = ComposeDouble(buffer, sign, length, point);
+  return MyFabsL(2 * (lbuffer - lv)) < unit;
+}
+
+
+static bool IsShortest(
+    double v, char* buffer, int sign, int length, int point) {
+  // Now test if a shorter version would still yield the same result.
+  // Not an exhaustive test, but better than nothing.
+
+  if (length == 1) return true;
+
+  char last_digit = buffer[length - 1];
+
+  if (buffer[length - 1] == '0') return false;
+
+  if (v == static_cast<double>(ComposeDouble(buffer, sign, length - 1, point)))
+    return false;
+
+  if (buffer[length-2] != '9') {
+    buffer[length - 2]++;
+    if (v == static_cast<double>(ComposeDouble(buffer, sign, length-1, point)))
+      return false;
+    buffer[length - 2]--;
+  }
+  buffer[length - 1] = last_digit;
+  return true;
+}
+
+
+TEST(DoubleTestFunctions) {
+  char buffer[kBufferSize];
+
+  strncpy(buffer, "12345", kBufferSize);
+  CHECK(IsCorrect(123.45, buffer, 0, 5, 3));
+  strncpy(buffer, "12345", kBufferSize);
+  CHECK(IsCorrect(1.2345, buffer, 0, 5, 1));
+  strncpy(buffer, "12345", kBufferSize);
+  CHECK(!IsCorrect(1.2344, buffer, 0, 5, 1));
+  strncpy(buffer, "12345", kBufferSize);
+  CHECK(!IsCorrect(1.2345, buffer, 0, 5, 2));
+  strncpy(buffer, "12345", kBufferSize);
+  CHECK(!IsCorrect(1.2345, buffer, 0, 4, 1));
+
+  strncpy(buffer, "1234", kBufferSize);
+  CHECK(IsRounded(123.44, buffer, 0, 4, 3));
+  strncpy(buffer, "1234", kBufferSize);
+  CHECK(!IsRounded(123.4500000000001, buffer, 0, 4, 3));
+  strncpy(buffer, "1234", kBufferSize);
+  CHECK(IsRounded(123.44999999, buffer, 0, 4, 3));
+  strncpy(buffer, "1234", kBufferSize);
+  CHECK(IsRounded(123.44999999, buffer, 0, 3, 3));
+
+  strncpy(buffer, "1234567000000000000000000001", kBufferSize);
+  CHECK(IsShortest(123.45, buffer, 0, 5, 3));
+  strncpy(buffer, "1234567000000000000000000001", kBufferSize);
+  CHECK(IsShortest(123.4567, buffer, 0, 7, 3));
+  strncpy(buffer, "1234567000000000000000000001", kBufferSize);
+  CHECK(!IsShortest(123.4567, buffer, 0, strlen(buffer), 3));
+
+  strncpy(buffer, "123456699999999999999999999999999999", kBufferSize);
+  CHECK(!IsShortest(123.4567, buffer, 0, strlen(buffer), 3));
+  strncpy(buffer, "123456699999999999999999999999999999", kBufferSize);
+  CHECK(IsShortest(123.456, buffer, 0, 6, 3));
+}
+
+
+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 (status) {
+    CHECK(IsCorrect(v, buffer, sign, length, point));
+    CHECK(IsRounded(v, buffer, sign, length, point));
+    CHECK(IsShortest(v, buffer, sign, length, point));
+  }
+
+  uint64_t largest_denormal64 = V8_2PART_UINT64_C(0x000FFFFF, FFFFFFFF);
+  v = Double(largest_denormal64).value();
+  status = grisu3(v, buffer, &sign, &length, &point);
+  if (status) {
+    CHECK(IsCorrect(v, buffer, sign, length, point));
+    CHECK(IsRounded(v, buffer, sign, length, point));
+    CHECK(IsShortest(v, buffer, sign, length, point));
+  }
+}
+
+
+static double random_double() {
+  uint64_t double64 = 0;
+  for (int i = 0; i < 8; i++) {
+    double64 <<= 8;
+    double64 += rand() % 256;  // NOLINT
+  }
+  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 (!status) continue;
+    succeeded++;
+    CHECK(IsCorrect(v, buffer, sign, length, point));
+    CHECK(IsRounded(v, buffer, sign, length, point));
+    CHECK(IsShortest(v, buffer, sign, length, point));
+  }
+  CHECK_GT(succeeded*1.0/total, 0.99);
+  CHECK(needed_max_length);
+}