Remove limit on bigint multiplication - fixes issue 12833.

Fix for Issue 12833

Eliminate limit on size for bignum multiply by storing extra overflow bits for column sums.

R=floitsch@google.com, iposva@google.com

Committed: https://code.google.com/p/dart/source/detail?r=26962

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

LGTM.
Please add a VM team member before submitting.
Please change the title of the CL to something that explains that this is a
bignum change.

https://codereview.chromium.org/23455014/diff/11001/runtime/vm/bigint_operati...
File runtime/vm/bigint_operations.cc (right):

https://codereview.chromium.org/23455014/diff/11001/runtime/vm/bigint_operati...
runtime/vm/bigint_operations.cc:771: accumulator += chunk_a * chunk_b;
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]

PTAL

Siva - can you review for the VM?

https://codereview.chromium.org/23455014/diff/11001/runtime/vm/bigint_operati...
File runtime/vm/bigint_operations.cc (right):

https://codereview.chromium.org/23455014/diff/11001/runtime/vm/bigint_operati...
runtime/vm/bigint_operations.cc:771: accumulator += chunk_a * chunk_b;
On 2013/08/30 07:38:05, floitsch wrote:
> 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).

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

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

A small comment about the comment, but otherwise LGTM.

Thanks for fixing this,
-Ivan

https://codereview.chromium.org/23455014/diff/15001/runtime/vm/bigint_operati...
File runtime/vm/bigint_operations.cc (right):

https://codereview.chromium.org/23455014/diff/15001/runtime/vm/bigint_operati...
runtime/vm/bigint_operations.cc:741: static_cast<DoubleChunk>(kDigitMaxValue) *
kDigitMaxValue;
If I understand this correctly then the values for the current setup are:
kDigitBitSize = 28;
kDigitMaxValue = 0x0FFFFFFF
square = 0xFFFFFFE0000001

https://codereview.chromium.org/23455014/diff/15001/runtime/vm/bigint_operati...
runtime/vm/bigint_operations.cc:742: const DoubleChunk kDoubleChunkMaxValue =
static_cast<DoubleChunk>(-1);
kDoubleChunkMaxValue = 0xFFFFFFFFFFFFFFFF

https://codereview.chromium.org/23455014/diff/15001/runtime/vm/bigint_operati...
runtime/vm/bigint_operations.cc:743: const DoubleChunk left_over_carry =
kDoubleChunkMaxValue >> kDigitBitSize;
left_over_carry = 0x0000000FFFFFFFFF

https://codereview.chromium.org/23455014/diff/15001/runtime/vm/bigint_operati...
runtime/vm/bigint_operations.cc:744: const intptr_t kMaxDigits =
(kDoubleChunkMaxValue - left_over_carry) / square;
kMaxDigits = 0xFFFFFFF000000000 / 0xFFFFFFE0000001 = 256

https://codereview.chromium.org/23455014/diff/15001/runtime/vm/bigint_operati...
runtime/vm/bigint_operations.cc:783: // 2^(kMaxDigits + kDigitBitSize) elements.
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.

[sra1, 2013-08-31 00:14:56]

Committed patchset #3 manually as r26962 (presubmit successful).

[sra1, 2013-08-31 00:45:40]

Thanks, Ivan.

I rewrote the comment, let me know if you want any changes.