Remove limit on bigint multiplication - fixes issue 12833.

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 287540f751f562f812b5dcdf4a6d9493b394122e..6e0f478f4feab64a5ebed22224422e83b0fb358b 100644
--- a/runtime/vm/bigint_operations.cc
+++ b/runtime/vm/bigint_operations.cc
@@ -721,30 +721,28 @@ RawBigint* BigintOperations::Multiply(const Bigint& a, const Bigint& b) {
   //        1000  * (a2b1 + a1b2) +
   //        10000 * a2b2
   //
-  // Each column will be accumulated in an integer of type DoubleChunk. We
-  // must guarantee that the column-sum will not overflow.
+  // Each column will be accumulated in an integer of type DoubleChunk. We must
+  // guarantee that the column-sum will not overflow.  We achieve this by
+  // 'blocking' the sum into overflow-free sums followed by propagating the
+  // overflow.
   //
   // In the worst case we have to accumulate k = Min(a.length, b.length)
   // products plus the carry from the previous round.
   // Each bigint-digit is smaller than beta = 2^kDigitBitSize.
   // Each product is at most (beta - 1)^2.
-  // If we want to use Comba multiplication the following condition must hold:
+
+  // If we want to use Comba multiplication and accumulate into a single
+  // register without overflow, the following condition must hold:
   // k * (beta - 1)^2 + (2^(kDoubleChunkBitSize - kDigitBitSize) - 1) <
   //        2^kDoubleChunkBitSize.
+  // Solving this give the maximum number of digits that can be summed in
+  // between handling the overflow.
   const DoubleChunk square =
       static_cast<DoubleChunk>(kDigitMaxValue) * kDigitMaxValue;
   const DoubleChunk kDoubleChunkMaxValue = static_cast<DoubleChunk>(-1);
   const DoubleChunk left_over_carry = kDoubleChunkMaxValue >> kDigitBitSize;
   const intptr_t kMaxDigits = (kDoubleChunkMaxValue - left_over_carry) / square;
-  if (Utils::Minimum(a_length, b_length) > kMaxDigits) {
-    // 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();
-  }
+  const intptr_t kBlockSize = kMaxDigits - 1;  // -1 for incomming carry.
 
   DoubleChunk accumulator = 0;  // Accumulates the result of one column.
   for (intptr_t i = 0; i < result_length; i++) {
@@ -761,15 +759,25 @@ RawBigint* BigintOperations::Multiply(const Bigint& a, const Bigint& b) {
     // Instead of testing for a_index >= 0 && b_index < b_length we compute the
     // number of iterations first.
     intptr_t iterations = Utils::Minimum(b_length - b_index, a_index + 1);
-    for (intptr_t j = 0; j < iterations; j++) {
-      DoubleChunk chunk_a = a.GetChunkAt(a_index);
-      DoubleChunk chunk_b = b.GetChunkAt(b_index);
-      accumulator += chunk_a * chunk_b;
-      a_index--;
-      b_index++;
+
+    // For large products we need extra bit for the overflow.  The sum is broken
+    // into blocks to avoid dealing with the overflow on each iteration.
+    DoubleChunk accumulator_overflow = 0;
+    for (intptr_t j_block = 0; j_block < iterations; j_block += kBlockSize) {
+      intptr_t j_end = Utils::Minimum(j_block + kBlockSize, iterations);
+      for (intptr_t j = j_block; j < j_end; j++) {
+        DoubleChunk chunk_a = a.GetChunkAt(a_index);
+        DoubleChunk chunk_b = b.GetChunkAt(b_index);
+        accumulator += chunk_a * chunk_b;

[floitsch, 2013/08/30 07:38:05]

In theory the accumulator from the previous run can be "arbitrary" big. Add a
comment explaining that in practice it cannot use more than a bit, though.
Otherwise the numbers would need to be bigger than XYZ and wouldn't fit into
memory. (Something like that).

[sra1, 2013/08/30 18:24:54]

I split the overflow into a digit and an extra overflow.

+        a_index--;
+        b_index++;
+      }
+      accumulator_overflow += (accumulator >> kDigitBitSize);
+      accumulator &= kDigitMask;
     }
-    result.SetChunkAt(i, static_cast<Chunk>(accumulator & kDigitMask));
-    accumulator >>= kDigitBitSize;
+    result.SetChunkAt(i, static_cast<Chunk>(accumulator));
+    accumulator = accumulator_overflow;
+    accumulator_overflow = 0;
   }
   ASSERT(accumulator == 0);