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..00b6721819b6fada8b666c380096adcbc27ff656 100644
--- a/runtime/vm/bigint_operations.cc
+++ b/runtime/vm/bigint_operations.cc
@@ -721,32 +721,31 @@ 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;

[Ivan Posva, 2013/08/30 21:28:13]

If I understand this correctly then the values for the current setup are:
kDigitBitSize = 28;
kDigitMaxValue = 0x0FFFFFFF
square = 0xFFFFFFE0000001

   const DoubleChunk kDoubleChunkMaxValue = static_cast<DoubleChunk>(-1);

[Ivan Posva, 2013/08/30 21:28:13]

kDoubleChunkMaxValue = 0xFFFFFFFFFFFFFFFF

   const DoubleChunk left_over_carry = kDoubleChunkMaxValue >> kDigitBitSize;

[Ivan Posva, 2013/08/30 21:28:13]

left_over_carry = 0x0000000FFFFFFFFF

   const intptr_t kMaxDigits = (kDoubleChunkMaxValue - left_over_carry) / square;

[Ivan Posva, 2013/08/30 21:28:13]

kMaxDigits = 0xFFFFFFF000000000 / 0xFFFFFFE0000001 = 256

-  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.
+  DoubleChunk accumulator_overflow = 0;
   for (intptr_t i = 0; i < result_length; i++) {
     // Example: r = a2a1a0 * b2b1b0.
     //   For i == 0, compute a0b0.
@@ -761,17 +760,31 @@ 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.
+    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;
+        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));
+    // Overflow becomes the initial accumulator for the next column.
+    accumulator = accumulator_overflow & kDigitMask;
+    // And the overflow from the overflow becomes the new overflow.  This is
+    // unlikely to be non-zero since it implies a single column sum with
+    // 2^(kMaxDigits + kDigitBitSize) elements.

[Ivan Posva, 2013/08/30 21:28:13]

That description is a bit abstract to me. But filling in the values from above I
get:
2 ^ (256 + 28) elements
And that is enough elements to qualify for rather unlikely. Since it all is
dependent on kDigitBitSize you could expand the comment to say that for a
kDigitBitSize of 28 the overflow happens with so many elements.

+    accumulator_overflow = (accumulator_overflow >> kDigitBitSize);
   }
   ASSERT(accumulator == 0);
+  ASSERT(accumulator_overflow == 0);
 
   Clamp(result);
   return result.raw();