Optimise Bignum layout. (#107)

* Use memset to clear bignum.

* Improve data locality.

* Reduce size of bignum.
diff --git a/double-conversion/bignum.cc b/double-conversion/bignum.cc
index 7e504fe..f089715 100644
--- a/double-conversion/bignum.cc
+++ b/double-conversion/bignum.cc
@@ -26,6 +26,7 @@
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include <algorithm>
+#include <cstring>
 
 #include "bignum.h"
 #include "utils.h"
@@ -33,10 +34,20 @@
 namespace double_conversion {
 
 Bignum::Bignum()
-    : bigits_buffer_(), bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
-  for (int i = 0; i < kBigitCapacity; ++i) {
-    bigits_[i] = 0;
-  }
+    : used_digits_(0), exponent_(0) {
+  std::memset(bigits_buffer_, 0, sizeof(Chunk) * kBigitCapacity);
+}
+
+
+Bignum::Chunk& Bignum::RawBigit(int index) {
+  DOUBLE_CONVERSION_ASSERT(static_cast<unsigned>(index) < kBigitCapacity);
+  return bigits_buffer_[index];
+}
+
+
+const Bignum::Chunk& Bignum::RawBigit(int index) const {
+  DOUBLE_CONVERSION_ASSERT(static_cast<unsigned>(index) < kBigitCapacity);
+  return bigits_buffer_[index];
 }
 
 
@@ -50,10 +61,11 @@
 void Bignum::AssignUInt16(uint16_t value) {
   DOUBLE_CONVERSION_ASSERT(kBigitSize >= BitSize(value));
   Zero();
-  if (value == 0) return;
-
+  if (value == 0) {
+    return;
+  }
   EnsureCapacity(1);
-  bigits_[0] = value;
+  RawBigit(0) = value;
   used_digits_ = 1;
 }
 
@@ -62,12 +74,13 @@
   const int kUInt64Size = 64;
 
   Zero();
-  if (value == 0) return;
-
+  if (value == 0) {
+    return;
+  }
   int needed_bigits = kUInt64Size / kBigitSize + 1;
   EnsureCapacity(needed_bigits);
   for (int i = 0; i < needed_bigits; ++i) {
-    bigits_[i] = value & kBigitMask;
+     RawBigit(i) = value & kBigitMask;
     value = value >> kBigitSize;
   }
   used_digits_ = needed_bigits;
@@ -78,11 +91,11 @@
 void Bignum::AssignBignum(const Bignum& other) {
   exponent_ = other.exponent_;
   for (int i = 0; i < other.used_digits_; ++i) {
-    bigits_[i] = other.bigits_[i];
+    RawBigit(i) = other.RawBigit(i);
   }
   // Clear the excess digits (if there were any).
   for (int i = other.used_digits_; i < used_digits_; ++i) {
-    bigits_[i] = 0;
+    RawBigit(i) = 0;
   }
   used_digits_ = other.used_digits_;
 }
@@ -143,7 +156,7 @@
     for (int j = 0; j < kBigitSize / 4; j++) {
       current_bigit += HexCharValue(value[string_index--]) << (j * 4);
     }
-    bigits_[i] = current_bigit;
+    RawBigit(i) = current_bigit;
   }
   used_digits_ = needed_bigits - 1;
 
@@ -153,7 +166,7 @@
     most_significant_bigit += HexCharValue(value[j]);
   }
   if (most_significant_bigit != 0) {
-    bigits_[used_digits_] = most_significant_bigit;
+    RawBigit(used_digits_) = most_significant_bigit;
     used_digits_++;
   }
   Clamp();
@@ -193,15 +206,15 @@
   int bigit_pos = other.exponent_ - exponent_;
   DOUBLE_CONVERSION_ASSERT(bigit_pos >= 0);
   for (int i = 0; i < other.used_digits_; ++i) {
-    Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
-    bigits_[bigit_pos] = sum & kBigitMask;
+    Chunk sum = RawBigit(bigit_pos) + other.RawBigit(i) + carry;
+    RawBigit(bigit_pos) = sum & kBigitMask;
     carry = sum >> kBigitSize;
     bigit_pos++;
   }
 
   while (carry != 0) {
-    Chunk sum = bigits_[bigit_pos] + carry;
-    bigits_[bigit_pos] = sum & kBigitMask;
+    Chunk sum = RawBigit(bigit_pos) + carry;
+    RawBigit(bigit_pos) = sum & kBigitMask;
     carry = sum >> kBigitSize;
     bigit_pos++;
   }
@@ -223,13 +236,13 @@
   int i;
   for (i = 0; i < other.used_digits_; ++i) {
     DOUBLE_CONVERSION_ASSERT((borrow == 0) || (borrow == 1));
-    Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
-    bigits_[i + offset] = difference & kBigitMask;
+    Chunk difference = RawBigit(i + offset) - other.RawBigit(i) - borrow;
+    RawBigit(i + offset) = difference & kBigitMask;
     borrow = difference >> (kChunkSize - 1);
   }
   while (borrow != 0) {
-    Chunk difference = bigits_[i + offset] - borrow;
-    bigits_[i + offset] = difference & kBigitMask;
+    Chunk difference = RawBigit(i + offset) - borrow;
+    RawBigit(i + offset) = difference & kBigitMask;
     borrow = difference >> (kChunkSize - 1);
     ++i;
   }
@@ -259,13 +272,13 @@
   DOUBLE_CONVERSION_ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1);
   DoubleChunk carry = 0;
   for (int i = 0; i < used_digits_; ++i) {
-    DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
-    bigits_[i] = static_cast<Chunk>(product & kBigitMask);
+    DoubleChunk product = static_cast<DoubleChunk>(factor) * RawBigit(i) + carry;
+    RawBigit(i) = static_cast<Chunk>(product & kBigitMask);
     carry = (product >> kBigitSize);
   }
   while (carry != 0) {
     EnsureCapacity(used_digits_ + 1);
-    bigits_[used_digits_] = carry & kBigitMask;
+    RawBigit(used_digits_) = carry & kBigitMask;
     used_digits_++;
     carry >>= kBigitSize;
   }
@@ -283,16 +296,16 @@
   uint64_t low = factor & 0xFFFFFFFF;
   uint64_t high = factor >> 32;
   for (int i = 0; i < used_digits_; ++i) {
-    uint64_t product_low = low * bigits_[i];
-    uint64_t product_high = high * bigits_[i];
+    uint64_t product_low = low * RawBigit(i);
+    uint64_t product_high = high * RawBigit(i);
     uint64_t tmp = (carry & kBigitMask) + product_low;
-    bigits_[i] = tmp & kBigitMask;
+    RawBigit(i) = tmp & kBigitMask;
     carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
         (product_high << (32 - kBigitSize));
   }
   while (carry != 0) {
     EnsureCapacity(used_digits_ + 1);
-    bigits_[used_digits_] = carry & kBigitMask;
+    RawBigit(used_digits_) = carry & kBigitMask;
     used_digits_++;
     carry >>= kBigitSize;
   }
@@ -363,7 +376,7 @@
   // First shift the digits so we don't overwrite them.
   int copy_offset = used_digits_;
   for (int i = 0; i < used_digits_; ++i) {
-    bigits_[copy_offset + i] = bigits_[i];
+    RawBigit(copy_offset + i) = RawBigit(i);
   }
   // We have two loops to avoid some 'if's in the loop.
   for (int i = 0; i < used_digits_; ++i) {
@@ -373,13 +386,13 @@
     int bigit_index2 = 0;
     // Sum all of the sub-products.
     while (bigit_index1 >= 0) {
-      Chunk chunk1 = bigits_[copy_offset + bigit_index1];
-      Chunk chunk2 = bigits_[copy_offset + bigit_index2];
+      Chunk chunk1 = RawBigit(copy_offset + bigit_index1);
+      Chunk chunk2 = RawBigit(copy_offset + bigit_index2);
       accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
       bigit_index1--;
       bigit_index2++;
     }
-    bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
+    RawBigit(i) = static_cast<Chunk>(accumulator) & kBigitMask;
     accumulator >>= kBigitSize;
   }
   for (int i = used_digits_; i < product_length; ++i) {
@@ -388,16 +401,16 @@
     // Invariant: sum of both indices is again equal to i.
     // Inner loop runs 0 times on last iteration, emptying accumulator.
     while (bigit_index2 < used_digits_) {
-      Chunk chunk1 = bigits_[copy_offset + bigit_index1];
-      Chunk chunk2 = bigits_[copy_offset + bigit_index2];
+      Chunk chunk1 = RawBigit(copy_offset + bigit_index1);
+      Chunk chunk2 = RawBigit(copy_offset + bigit_index2);
       accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
       bigit_index1--;
       bigit_index2++;
     }
-    // The overwritten bigits_[i] will never be read in further loop iterations,
+    // The overwritten RawBigit(i) will never be read in further loop iterations,
     // because bigit_index1 and bigit_index2 are always greater
     // than i - used_digits_.
-    bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
+    RawBigit(i) = static_cast<Chunk>(accumulator) & kBigitMask;
     accumulator >>= kBigitSize;
   }
   // Since the result was guaranteed to lie inside the number the
@@ -507,26 +520,26 @@
     // This naive approach is extremely inefficient if `this` divided by other
     // is big. This function is implemented for doubleToString where
     // the result should be small (less than 10).
-    DOUBLE_CONVERSION_ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
-    DOUBLE_CONVERSION_ASSERT(bigits_[used_digits_ - 1] < 0x10000);
+    DOUBLE_CONVERSION_ASSERT(other.RawBigit(other.used_digits_ - 1) >= ((1 << kBigitSize) / 16));
+    DOUBLE_CONVERSION_ASSERT(RawBigit(used_digits_ - 1) < 0x10000);
     // Remove the multiples of the first digit.
     // Example this = 23 and other equals 9. -> Remove 2 multiples.
-    result += static_cast<uint16_t>(bigits_[used_digits_ - 1]);
-    SubtractTimes(other, bigits_[used_digits_ - 1]);
+    result += static_cast<uint16_t>(RawBigit(used_digits_ - 1));
+    SubtractTimes(other, RawBigit(used_digits_ - 1));
   }
 
   DOUBLE_CONVERSION_ASSERT(BigitLength() == other.BigitLength());
 
   // Both bignums are at the same length now.
   // Since other has more than 0 digits we know that the access to
-  // bigits_[used_digits_ - 1] is safe.
-  Chunk this_bigit = bigits_[used_digits_ - 1];
-  Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
+  // RawBigit(used_digits_ - 1) is safe.
+  Chunk this_bigit = RawBigit(used_digits_ - 1);
+  Chunk other_bigit = other.RawBigit(other.used_digits_ - 1);
 
   if (other.used_digits_ == 1) {
     // Shortcut for easy (and common) case.
     int quotient = this_bigit / other_bigit;
-    bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
+    RawBigit(used_digits_ - 1) = this_bigit - other_bigit * quotient;
     DOUBLE_CONVERSION_ASSERT(quotient < 0x10000);
     result += static_cast<uint16_t>(quotient);
     Clamp();
@@ -585,7 +598,7 @@
   }
   // We add 1 for the terminating '\0' character.
   int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
-      SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
+      SizeInHexChars(RawBigit(used_digits_ - 1)) + 1;
   if (needed_chars > buffer_size) return false;
   int string_index = needed_chars - 1;
   buffer[string_index--] = '\0';
@@ -595,14 +608,14 @@
     }
   }
   for (int i = 0; i < used_digits_ - 1; ++i) {
-    Chunk current_bigit = bigits_[i];
+    Chunk current_bigit = RawBigit(i);
     for (int j = 0; j < kHexCharsPerBigit; ++j) {
       buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
       current_bigit >>= 4;
     }
   }
   // And finally the last bigit.
-  Chunk most_significant_bigit = bigits_[used_digits_ - 1];
+  Chunk most_significant_bigit = RawBigit(used_digits_ - 1);
   while (most_significant_bigit != 0) {
     buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
     most_significant_bigit >>= 4;
@@ -611,10 +624,10 @@
 }
 
 
-Bignum::Chunk Bignum::BigitAt(int index) const {
+Bignum::Chunk Bignum::BigitOrZero(int index) const {
   if (index >= BigitLength()) return 0;
   if (index < exponent_) return 0;
-  return bigits_[index - exponent_];
+  return RawBigit(index - exponent_);
 }
 
 
@@ -626,8 +639,8 @@
   if (bigit_length_a < bigit_length_b) return -1;
   if (bigit_length_a > bigit_length_b) return +1;
   for (int i = bigit_length_a - 1; i >= (std::min)(a.exponent_, b.exponent_); --i) {
-    Chunk bigit_a = a.BigitAt(i);
-    Chunk bigit_b = b.BigitAt(i);
+    Chunk bigit_a = a.BigitOrZero(i);
+    Chunk bigit_b = b.BigitOrZero(i);
     if (bigit_a < bigit_b) return -1;
     if (bigit_a > bigit_b) return +1;
     // Otherwise they are equal up to this digit. Try the next digit.
@@ -656,9 +669,9 @@
   // Starting at min_exponent all digits are == 0. So no need to compare them.
   int min_exponent = (std::min)((std::min)(a.exponent_, b.exponent_), c.exponent_);
   for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
-    Chunk chunk_a = a.BigitAt(i);
-    Chunk chunk_b = b.BigitAt(i);
-    Chunk chunk_c = c.BigitAt(i);
+    Chunk chunk_a = a.BigitOrZero(i);
+    Chunk chunk_b = b.BigitOrZero(i);
+    Chunk chunk_c = c.BigitOrZero(i);
     Chunk sum = chunk_a + chunk_b;
     if (sum > chunk_c + borrow) {
       return +1;
@@ -674,7 +687,7 @@
 
 
 void Bignum::Clamp() {
-  while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
+  while (used_digits_ > 0 && RawBigit(used_digits_ - 1) == 0) {
     used_digits_--;
   }
   if (used_digits_ == 0) {
@@ -685,14 +698,12 @@
 
 
 bool Bignum::IsClamped() const {
-  return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
+  return used_digits_ == 0 || RawBigit(used_digits_ - 1) != 0;
 }
 
 
 void Bignum::Zero() {
-  for (int i = 0; i < used_digits_; ++i) {
-    bigits_[i] = 0;
-  }
+  std::memset(bigits_buffer_, 0, sizeof(Chunk) * used_digits_);
   used_digits_ = 0;
   exponent_ = 0;
 }
@@ -709,10 +720,10 @@
     int zero_digits = exponent_ - other.exponent_;
     EnsureCapacity(used_digits_ + zero_digits);
     for (int i = used_digits_ - 1; i >= 0; --i) {
-      bigits_[i + zero_digits] = bigits_[i];
+      RawBigit(i + zero_digits) = RawBigit(i);
     }
     for (int i = 0; i < zero_digits; ++i) {
-      bigits_[i] = 0;
+      RawBigit(i) = 0;
     }
     used_digits_ += zero_digits;
     exponent_ -= zero_digits;
@@ -727,12 +738,12 @@
   DOUBLE_CONVERSION_ASSERT(shift_amount >= 0);
   Chunk carry = 0;
   for (int i = 0; i < used_digits_; ++i) {
-    Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
-    bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
+    Chunk new_carry = RawBigit(i) >> (kBigitSize - shift_amount);
+    RawBigit(i) = ((RawBigit(i) << shift_amount) + carry) & kBigitMask;
     carry = new_carry;
   }
   if (carry != 0) {
-    bigits_[used_digits_] = carry;
+    RawBigit(used_digits_) = carry;
     used_digits_++;
   }
 }
@@ -749,17 +760,17 @@
   Chunk borrow = 0;
   int exponent_diff = other.exponent_ - exponent_;
   for (int i = 0; i < other.used_digits_; ++i) {
-    DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
+    DoubleChunk product = static_cast<DoubleChunk>(factor) * other.RawBigit(i);
     DoubleChunk remove = borrow + product;
-    Chunk difference = bigits_[i + exponent_diff] - (remove & kBigitMask);
-    bigits_[i + exponent_diff] = difference & kBigitMask;
+    Chunk difference = RawBigit(i + exponent_diff) - (remove & kBigitMask);
+    RawBigit(i + exponent_diff) = difference & kBigitMask;
     borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
                                 (remove >> kBigitSize));
   }
   for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
     if (borrow == 0) return;
-    Chunk difference = bigits_[i] - borrow;
-    bigits_[i] = difference & kBigitMask;
+    Chunk difference = RawBigit(i) - borrow;
+    RawBigit(i) = difference & kBigitMask;
     borrow = difference >> (kChunkSize - 1);
   }
   Clamp();
diff --git a/double-conversion/bignum.h b/double-conversion/bignum.h
index ec2991a..d42532f 100644
--- a/double-conversion/bignum.h
+++ b/double-conversion/bignum.h
@@ -125,16 +125,15 @@
   void BigitsShiftLeft(int shift_amount);
   // BigitLength includes the "hidden" digits encoded in the exponent.
   int BigitLength() const { return used_digits_ + exponent_; }
-  Chunk BigitAt(int index) const;
+  Chunk& RawBigit(int index);
+  const Chunk& RawBigit(int index) const;
+  Chunk BigitOrZero(int index) const;
   void SubtractTimes(const Bignum& other, int factor);
 
-  Chunk bigits_buffer_[kBigitCapacity];
-  // A vector backed by bigits_buffer_. This way accesses to the array are
-  // checked for out-of-bounds errors.
-  Vector<Chunk> bigits_;
   int used_digits_;
   // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
   int exponent_;
+  Chunk bigits_buffer_[kBigitCapacity];
 
   DOUBLE_CONVERSION_DISALLOW_COPY_AND_ASSIGN(Bignum);
 };