Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(614)

Unified Diff: runtime/vm/bigint_operations.cc

Issue 9536016: Implement BigintOperations::ToDecimalCString. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Address comments. Created 8 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « runtime/vm/bigint_operations.h ('k') | runtime/vm/bigint_operations_test.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: runtime/vm/bigint_operations.cc
diff --git a/runtime/vm/bigint_operations.cc b/runtime/vm/bigint_operations.cc
index d46e78513244b24b6067289a067e70dde5a3a93a..1a12e582e815f794e81a8bcf5b6f357795ac6b50 100644
--- a/runtime/vm/bigint_operations.cc
+++ b/runtime/vm/bigint_operations.cc
@@ -6,6 +6,7 @@
#include "vm/double_internals.h"
#include "vm/exceptions.h"
+#include "vm/object_store.h"
#include "vm/zone.h"
namespace dart {
@@ -336,6 +337,92 @@ const char* BigintOperations::ToHexCString(const Bigint& bigint,
}
+const char* BigintOperations::ToDecimalCString(
+ const Bigint& bigint, uword (*allocator)(intptr_t size)) {
+ // log10(2) ~= 0.30102999566398114.
+ const intptr_t kLog2Dividend = 30103;
+ const intptr_t kLog2Divisor = 100000;
+ // We remove a small constant for rounding imprecision, the \0 character and
+ // the negative sign.
+ const intptr_t kMaxAllowedDigitLength =
+ (kIntptrMax - 10) / kLog2Dividend / kDigitBitSize * kLog2Divisor;
+
+ intptr_t length = bigint.Length();
+ if (length >= kMaxAllowedDigitLength) {
+ // Use the preallocated out of memory exception to avoid calling
+ // into dart code or allocating any code.
+ Isolate* isolate = Isolate::Current();
+ const Instance& exception =
+ Instance::Handle(isolate->object_store()->out_of_memory());
+ Exceptions::Throw(exception);
+ UNREACHABLE();
+ }
+
+ // Approximate the size of the resulting string. We prefer overestimating
+ // to not allocating enough.
+ int64_t bit_length = length * kDigitBitSize;
+ ASSERT(bit_length > length);
+ int64_t decimal_length = (bit_length * kLog2Dividend / kLog2Divisor) + 1;
+ // Add one byte for the trailing \0 character.
+ int64_t required_size = decimal_length + 1;
+ if (bigint.IsNegative()) {
+ required_size++;
+ }
+ ASSERT(required_size == static_cast<intptr_t>(required_size));
+ // 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)));
+ ASSERT(result != NULL);
+ 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;
sra1 2012/04/02 20:03:29 It is funny that the constant called power-of-ten
floitsch 2012/04/03 11:20:52 done in https://chromiumcodereview.appspot.com/995
+ ASSERT(pow(10, kPowerOfTen) == kDivisorValue);
+ ASSERT(static_cast<Chunk>(kDivisorValue) < kDigitMaxValue);
+ ASSERT(Smi::IsValid(kDivisorValue));
+ const Bigint& divisor = Bigint::Handle(NewFromInt64(kDivisorValue));
+
+ // 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);
+ part /= 10;
+ }
+ ASSERT(part == 0);
+ rest = quotient.raw();
+ }
+ // Move the resulting position back until we don't have any zeroes anymore.
+ // This is done so that we can remove all leading zeroes.
+ 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--;
+ }
+ ASSERT(result_pos >= 0);
+ result[result_pos] = '\0';
+ return result;
+}
+
+
bool BigintOperations::FitsIntoSmi(const Bigint& bigint) {
intptr_t bigint_length = bigint.Length();
if (bigint_length == 0) {
« no previous file with comments | « runtime/vm/bigint_operations.h ('k') | runtime/vm/bigint_operations_test.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698