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

src/conversions.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/conversions.h"
 
 #include <limits.h>
 #include <stdarg.h>
 #include <cmath>
 
+#include "src/allocation.h"
 #include "src/assert-scope.h"
 #include "src/char-predicates-inl.h"
 #include "src/codegen.h"
 #include "src/conversions-inl.h"
 #include "src/dtoa.h"
 #include "src/factory.h"
 #include "src/list-inl.h"
 #include "src/strtod.h"
 #include "src/utils.h"
 
@@ skipping 140 matching lines @@
         if (length != 1) {
           builder.AddCharacter('.');
           builder.AddString(decimal_rep + 1);
         }
         builder.AddCharacter('e');
         builder.AddCharacter((decimal_point >= 0) ? '+' : '-');
         int exponent = decimal_point - 1;
         if (exponent < 0) exponent = -exponent;
         builder.AddDecimalInteger(exponent);
       }
-    return builder.Finalize();
+      return builder.Finalize();
     }
   }
 }
 
 
 const char* IntToCString(int n, Vector<char> buffer) {
   bool negative = false;
   if (n < 0) {
     // We must not negate the most negative int.
     if (n == kMinInt) return DoubleToCString(n, buffer);
@@ skipping 225 matching lines @@
     }
     result = builder.Finalize();
   }
 
   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';
+  char buffer[kBufferSize];
+  int cursor = kBufferSize;
+  buffer[--cursor] = '\0';
+  bool negative = value < 0;
+  if (negative) value = -value;
 
-  // 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';
+  // Shift the number by power of the radix until we can represent it
+  // in its full precision as an uint64_t.
+  int decimal_point_shift = 0;
+  if (Double(value).Exponent() < 0) {
+    while (Double(value).Exponent() < 0) {
+      value *= radix;
+      decimal_point_shift--;
+    }
+  } else {
+    while (Double(value / radix).Exponent() > 0) {
+      value /= radix;
+      // Insert trailing zeros.
+      buffer[--cursor] = '0';
+    }
+  }
 
-  // Make sure the value is positive.
-  bool is_negative = value < 0.0;
-  if (is_negative) value = -value;
+  // Construct string from right to left (least significant to most).
+  uint64_t int_value = static_cast<uint64_t>(value);

[Tobias Tebbi, 2016/11/22 18:46:54]

(2/7).toString(3) gives "0.0212010212010212010212010212010211" instead of
"0.0212010212010212010212010212010212"
This is not just the wrong decision weather to round up or down, the last digit
is just wrong. To fix this, we would need to restrict ourseleves to less
significant digits and then do proper rounding on the int value.

+  while (decimal_point_shift < 0) {
+    uint64_t multiple = int_value / radix;
+    uint64_t remainder = int_value - multiple * radix;
+    // Skip trailing zeros after the decimal point.
+    if (remainder > 0) {
+      // Compute digits up to decimal point.
+      while (decimal_point_shift < 0) {
+        uint64_t multiple = int_value / radix;
+        uint64_t remainder = int_value - multiple * radix;
+        buffer[--cursor] = chars[remainder];
+        int_value = multiple;
+        decimal_point_shift++;
+      }
+      // Insert decimal point if there have been fractional digits.
+      if (decimal_point_shift == 0) buffer[--cursor] = '.';
+      break;
+    }
+    int_value = multiple;
+    decimal_point_shift++;
+  }
+  // Compute integer digits.
+  do {
+    uint64_t multiple = int_value / radix;
+    uint64_t remainder = int_value - multiple * radix;
+    buffer[--cursor] = chars[remainder];
+    int_value = multiple;
+  } while (int_value > 0);
 
-  // Get the integer part and the decimal part.
-  double integer_part = std::floor(value);
-  double decimal_part = value - integer_part;
-
-  // Convert the integer part starting from the back.  Always generate
-  // at least one digit.
-  int integer_pos = kBufferSize - 2;
-  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++;
+  if (negative) buffer[--cursor] = '-';
   // 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();
+  char* result = NewArray<char>(kBufferSize - cursor);
+  memcpy(result, buffer + cursor, kBufferSize - cursor);
+  return result;
 }
 
 
 // ES6 18.2.4 parseFloat(string)
 double StringToDouble(UnicodeCache* unicode_cache, Handle<String> string,
                       int flags, double empty_string_val) {
   Handle<String> flattened = String::Flatten(string);
   {
     DisallowHeapAllocation no_gc;
     String::FlatContent flat = flattened->GetFlatContent();
@@ skipping 61 matching lines @@
   char reverse_buffer[kBufferSize + 1];  // Result will be /0 terminated.
   Vector<char> reverse_vector(reverse_buffer, arraysize(reverse_buffer));
   const char* reverse_string = DoubleToCString(d, reverse_vector);
   for (int i = 0; i < length; ++i) {
     if (static_cast<uint16_t>(reverse_string[i]) != buffer[i]) return false;
   }
   return true;
 }
 }  // namespace internal
 }  // namespace v8