Implement BigintOperations::ToDecimalCString.

runtime/vm/bigint_operations.cc

Index: runtime/vm/bigint_operations.cc
diff --git a/runtime/vm/bigint_operations.cc b/runtime/vm/bigint_operations.cc
index d46e78513244b24b6067289a067e70dde5a3a93a..d58cad7de6581fe0156478bdb5a111307981f095 100644
--- a/runtime/vm/bigint_operations.cc
+++ b/runtime/vm/bigint_operations.cc
@@ -336,6 +336,76 @@ const char* BigintOperations::ToHexCString(const Bigint& bigint,
 }
 
 
+const char* BigintOperations::ToDecimalCString(
+    const Bigint& bigint, uword (*allocator)(intptr_t size)) {
+  intptr_t length = bigint.Length();
+  // We guard against overflows by using 64 bit computations.

[siva, 2012/03/02 19:31:45]

On 64 bit machines the signed_length is actually a 64 bit quantity, should you
restrict that to an int32_t value so that we are sure the 64 bit computation
does not result in overflows on a 64 bit machine?

[floitsch, 2012/03/05 14:28:17]

Refactored.

+  int64_t bit_length = length * kDigitBitSize;
+  // Approximate the size of the resulting string. We prefer overestimating
+  // to not allocating enough.
+  // log10(2) ~= 0.30102999566398114.
+  int64_t decimal_length = (bit_length * 30103 / 100000) + 1;
+  // Add one byte for the trailing \0 character.
+  int64_t required_size = decimal_length + 1;
+  if (bigint.IsNegative()) {
+    required_size++;
+  }
+  // TODO(floitsch): what to do if we had an overflow?
+  if (required_size != static_cast<intptr_t>(required_size)) {

[siva, 2012/03/02 19:31:45]

I think we should assert here instead of silently returning "".

[floitsch, 2012/03/05 14:28:17]

That's why there was a TODO. Now throwing an OOM-exception.

+    return "";
+  }
+  // We will fill the result in the inverse order and then exchange at the end.
+  char* result =
+      reinterpret_cast<char*>(allocator(static_cast<intptr_t>(required_size)));

[siva, 2012/03/02 19:31:45]

ASSERT(result != NULL);

[floitsch, 2012/03/05 14:28:17]

Done.

+  int result_pos = 0;
+
+  // We divide the input into pieces of ~27 bits which can be efficiently
+  // handled.
+  const intptr_t kDivisorValue = 100000000;
+  const int kPowerOfTen = 8;
+  ASSERT(pow(10, kPowerOfTen) == kDivisorValue);
+  ASSERT(static_cast<Chunk>(kDivisorValue) < kDigitMaxValue);
+  ASSERT(Smi::IsValid(kDivisorValue));
+  const Smi& divisor_smi = Smi::Handle(Smi::New(kDivisorValue));
+  const Bigint& divisor = Bigint::Handle(NewFromSmi(divisor_smi));
+
+  // Rest contains the remaining bigint that needs to be printed.
+  Bigint& rest = Bigint::Handle(bigint.raw());
+  Bigint& quotient = Bigint::Handle();
+  Bigint& remainder = Bigint::Handle();
+  while (!rest.IsZero()) {
+    DivideRemainder(rest, divisor, &quotient, &remainder);
+    ASSERT(remainder.Length() == 1);
+    intptr_t part = static_cast<intptr_t>(remainder.GetChunkAt(0));
+    for (int i = 0; i < kPowerOfTen; i++) {
+      result[result_pos++] = '0' + part % 10;

[siva, 2012/03/02 19:31:45]

'0' + (part % 10);
to make it clear for operator precedence challenged folks.

[floitsch, 2012/03/05 14:28:17]

Done.

+      part /= 10;
+    }
+    ASSERT(part == 0);
+    rest = quotient.raw();
+  }
+  // Move the resulting position back until we don't have any zeroes anymore.

[siva, 2012/03/02 19:31:45]

// This is done so that we can remove all leading zeros.

[floitsch, 2012/03/05 14:28:17]

Done.

+  while (result_pos > 1 && result[result_pos - 1] == '0') {
+    result_pos--;
+  }
+  if (bigint.IsNegative()) {
+    result[result_pos++] = '-';
+  }
+  // Reverse the string.
+  int i = 0;
+  int j = result_pos - 1;
+  while (i < j) {
+    char tmp = result[i];
+    result[i] = result[j];
+    result[j] = tmp;
+    i++;
+    j--;
+  }

[siva, 2012/03/02 19:31:45]

ASSERt(result_pos >= 0);

[floitsch, 2012/03/05 14:28:17]

Done.

+  result[result_pos] = '\0';
+  return result;
+}
+
+
 bool BigintOperations::FitsIntoSmi(const Bigint& bigint) {
   intptr_t bigint_length = bigint.Length();
   if (bigint_length == 0) {