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;
   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++) {
     // 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.
+    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);
 
   Clamp(result);
   return result.raw();
 }
 
 
 RawBigint* BigintOperations::Divide(const Bigint& a, const Bigint& b) {
   Bigint& quotient = Bigint::Handle();
@@ skipping 889 matching lines @@
 int BigintOperations::CountBits(Chunk digit) {
   int result = 0;
   while (digit != 0) {
     digit >>= 1;
     result++;
   }
   return result;
 }
 
 }  // namespace dart