Remove limit on bigint multiplication - fixes issue 12833.

runtime/vm/bigint_operations.cc

 // Copyright 2012 Google Inc. All Rights Reserved.
 
 #include "vm/bigint_operations.h"
 
 #include "platform/utils.h"
 
 #include "vm/double_internals.h"
 #include "vm/exceptions.h"
 #include "vm/object_store.h"
 #include "vm/zone.h"
@@ skipping 703 matching lines @@
   }
 
   // Comba multiplication: compute each column separately.
   // Example: r = a2a1a0 * b2b1b0.
   //    r =  1    * a0b0 +
   //        10    * (a1b0 + a0b1) +
   //        100   * (a2b0 + a1b1 + a0b2) +
   //        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.
     //       i == 1,         a1b0 + a0b1 + overflow from i == 0.
     //       i == 2,         a2b0 + a1b1 + a0b2 + overflow from i == 1.
     //       ...
     // The indices into a and b are such that their sum equals i.
     intptr_t a_index = Utils::Minimum(a_length - 1, i);
     intptr_t b_index = i - a_index;
     ASSERT(a_index + b_index == i);
 
     // 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();
 }
 
 
 RawBigint* BigintOperations::Divide(const Bigint& a, const Bigint& b) {
   Bigint& quotient = Bigint::Handle();
   Bigint& remainder = Bigint::Handle();
   DivideRemainder(a, b, &quotient, &remainder);
@@ skipping 887 matching lines @@
 int BigintOperations::CountBits(Chunk digit) {
   int result = 0;
   while (digit != 0) {
     digit >>= 1;
     result++;
   }
   return result;
 }
 
 }  // namespace dart