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 222 matching lines @@
         }
         builder.AddPadding('0', extra + (p - builder.position()));
       }
     }
     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";
+
+  // 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);
+  }
+
+  // Compute integer digits.
+  do {
+    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;
+}
+
 
-char* DoubleToRadixCString(double value, int radix) {
-  DCHECK(radix >= 2 && radix <= 36);
-
-  // 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;
-
-  // 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++;
-  // 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();
-}
-
-
 // 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();
     DCHECK(flat.IsFlat());
     if (flat.IsOneByte()) {
       return StringToDouble(unicode_cache, flat.ToOneByteVector(), flags,
@@ skipping 58 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