Reimplement Number.prototype.toString with non-default radix.

src/conversions.cc

Index: src/conversions.cc
diff --git a/src/conversions.cc b/src/conversions.cc
index 7867719968d2f89e279dc9632d1c0341d02202fb..fb09d18a407f6780283e2b8bdcc468015a747884 100644
--- a/src/conversions.cc
+++ b/src/conversions.cc
@@ -8,6 +8,7 @@
 #include <stdarg.h>
 #include <cmath>
 
+#include "src/allocation.h"
 #include "src/assert-scope.h"
 #include "src/char-predicates-inl.h"
 #include "src/codegen.h"
@@ -168,7 +169,7 @@ const char* DoubleToCString(double v, Vector<char> buffer) {
         if (exponent < 0) exponent = -exponent;
         builder.AddDecimalInteger(exponent);
       }
-    return builder.Finalize();
+      return builder.Finalize();
     }
   }
 }
@@ -411,76 +412,83 @@ char* DoubleToPrecisionCString(double value, int p) {
   return result;
 }
 
-
 char* DoubleToRadixCString(double value, int radix) {
   DCHECK(radix >= 2 && radix <= 36);
-
+  DCHECK(std::isfinite(value));
+  DCHECK_NE(0.0, value);
   // Character array used for conversion.
   static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
 
-  // Buffer for the integer part of the result. 1024 chars is enough
-  // for max integer value in radix 2.  We need room for a sign too.
-  static const int kBufferSize = 1100;
-  char integer_buffer[kBufferSize];
-  integer_buffer[kBufferSize - 1] = '\0';
-
-  // Buffer for the decimal part of the result.  We only generate up
-  // to kBufferSize - 1 chars for the decimal part.
-  char decimal_buffer[kBufferSize];
-  decimal_buffer[kBufferSize - 1] = '\0';
-
-  // Make sure the value is positive.
-  bool is_negative = value < 0.0;
-  if (is_negative) value = -value;
-
-  // Get the integer part and the decimal part.
-  double integer_part = std::floor(value);
-  double decimal_part = value - integer_part;
+  // Temporary buffer for the result. We start with the decimal point in the
+  // middle and write to the left for the integer part and to the right for the
+  // fractional part. 1024 characters either way with additional space for sign
+  // and decimal point should be sufficient.
+  static const int kBufferSize = 2100;
+  char buffer[kBufferSize];
+  int integer_cursor = kBufferSize / 2;
+  int fraction_cursor = integer_cursor;
+
+  bool negative = value < 0;
+  if (negative) value = -value;
+
+  // Split the value into an integer part and a fractional part.
+  double integer = std::floor(value);
+  double fraction = value - integer;
+  // We only compute fractional digits up to the input double's precision.
+  double delta = 0.5 * (Double(value).NextDouble() - value);
+  if (fraction > delta) {
+    // Insert decimal point.
+    buffer[fraction_cursor++] = '.';
+    do {
+      // Shift up by one digit.
+      fraction *= radix;
+      delta *= radix;
+      // Write digit.
+      int digit = static_cast<int>(fraction);
+      buffer[fraction_cursor++] = chars[digit];
+      // Calculate remainder.
+      fraction -= digit;
+      // Round to even.
+      if (fraction > 0.5 || (fraction == 0.5 && (digit & 1))) {
+        if (fraction + delta > 1) {
+          // We need to back trace already written digits in case of carry-over.
+          while (true) {
+            fraction_cursor--;
+            if (fraction_cursor == kBufferSize / 2) {
+              CHECK_EQ('.', buffer[fraction_cursor]);
+              // Carry over to the integer part.
+              integer += 1;
+              break;
+            }
+            char c = buffer[fraction_cursor];
+            // Reconstruct digit.
+            int digit = c > '9' ? (c - 'a' + 10) : (c - '0');
+            if (digit + 1 < radix) {
+              buffer[fraction_cursor++] = chars[digit + 1];
+              break;
+            }
+          }
+          break;
+        }
+      }
+    } while (fraction > delta);
+  }
 
-  // Convert the integer part starting from the back.  Always generate
-  // at least one digit.
-  int integer_pos = kBufferSize - 2;
+  // Compute integer digits.
   do {
-    double remainder = modulo(integer_part, radix);
-    integer_buffer[integer_pos--] = chars[static_cast<int>(remainder)];
-    integer_part -= remainder;
-    integer_part /= radix;
-  } while (integer_part >= 1.0);
-  // Sanity check.
-  DCHECK(integer_pos > 0);
-  // Add sign if needed.
-  if (is_negative) integer_buffer[integer_pos--] = '-';
-
-  // Convert the decimal part.  Repeatedly multiply by the radix to
-  // generate the next char.  Never generate more than kBufferSize - 1
-  // chars.
-  //
-  // TODO(1093998): We will often generate a full decimal_buffer of
-  // chars because hitting zero will often not happen.  The right
-  // solution would be to continue until the string representation can
-  // be read back and yield the original value.  To implement this
-  // efficiently, we probably have to modify dtoa.
-  int decimal_pos = 0;
-  while ((decimal_part > 0.0) && (decimal_pos < kBufferSize - 1)) {
-    decimal_part *= radix;
-    decimal_buffer[decimal_pos++] =
-        chars[static_cast<int>(std::floor(decimal_part))];
-    decimal_part -= std::floor(decimal_part);
-  }
-  decimal_buffer[decimal_pos] = '\0';
-
-  // Compute the result size.
-  int integer_part_size = kBufferSize - 2 - integer_pos;
-  // Make room for zero termination.
-  unsigned result_size = integer_part_size + decimal_pos;
-  // If the number has a decimal part, leave room for the period.
-  if (decimal_pos > 0) result_size++;
-  // Allocate result and fill in the parts.
-  SimpleStringBuilder 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();
+    double multiple = std::floor(integer / radix);
+    int digit = static_cast<int>(integer - multiple * radix);
+    buffer[--integer_cursor] = chars[digit];
+    integer = multiple;
+  } while (integer > 0);
+
+  // Add sign and terminate string.
+  if (negative) buffer[--integer_cursor] = '-';
+  buffer[fraction_cursor++] = '\0';
+  // Allocate new string as return value.
+  char* result = NewArray<char>(fraction_cursor - integer_cursor);
+  memcpy(result, buffer + integer_cursor, fraction_cursor - integer_cursor);
+  return result;
 }