Since this crash occurs with particularly large operands, I took a look at the dependence of this bug upon operand sizes. D's BigInt (and BigUint) is represented internally as an array of uint (regardless of whether it's a 32-bit and 64-bit compile).
The initial bug-report is with operand of 52 and 82 uints. I took a look at other nearby sizes, and noticed that this bug lives in a narrow sector starting around operand sizes 48 and 74 (in uints). The sector starts there and grows wider as it goes:
http://kirr.homeunix.org/temp/d-bug-16264-operand-size-table.png
Code used to fill this table (compile a.d into a.exe, then run test.pl):
===== a.d start =====
import std.conv: to;
import std.internal.math.biguintcore;
void main(string[] args)
{
uint alen = to!uint(args[1]);
uint blen = to!uint(args[2]);
string unitstr = args[3];
string astr = ``, bstr = ``;
for (int i = 0; i < alen; i++) astr ~= unitstr;
for (int i = 0; i < blen; i++) bstr ~= unitstr;
BigUint a, b;
a.fromHexString(astr);
b.fromHexString(bstr);
assert(a.uintLength() == alen);
assert(b.uintLength() == blen);
BigUint c = BigUint.mul(a,b); // Crashes
}
===== a.d end =====
===== test.pl start =====
my ($mina,$maxa,$minb,$maxb) = (40,80,70,120);
print ' ';
for (my $b = $minb; $b <= $maxb; $b++) { printf " %3d", $b; }
print "\n";
for (my $a = $mina; $a <= $maxa; $a++)
{
printf " %3d", $a;
for (my $b = $minb; $b <= $maxb; $b++)
{
my $e = system("a.exe $a $b FFFFFFFF 2>nul");
print ' ', ($e ? 1 : 0);
}
print "\n";
}
===== test.pl end =====
I also checked 32-bit compiles - no crashes with any of these operand sizes.
Comment #3 by kkryukov — 2016-07-12T02:15:54Z
Here is the reason 32-bit BigUint multiplication works: std/internal/math/biguintcore.d has the following:
version(D_InlineAsm_X86)
{
import std.internal.math.biguintx86;
}
else
{
import std.internal.math.biguintnoasm;
}
So, 32-bit compile uses the seemingly correct std.internal.math.biguintx86. On the other hand, 64-bit compile uses std.internal.math.biguintnoasm - buggy, untested and apparently never used in the real world.
Comment #4 by kkryukov — 2016-07-12T03:36:18Z
Actually I've no idea why the 32-bit compile works with my initial test. If I add the following unittest into biguintcore.d, and compile in 32-bit (dmd.exe -main -unittest biguintcore.d), it crashes too.
unittest
{
BigUint a, b;
a.fromDecimalString(
`207672245542926038535480439528441949928508406405023044025560363701392340829` ~
`852529131306106648201340460604257466180580583656068555417076345439694125326` ~
`843947164365500055567495554645796102453565953360564114634705366335703491527` ~
`429426780005741168078089657359833601261803592920462081364401456331489106355` ~
`199133982282631108670436696758342051198891939367812305559960349479160308314` ~
`068518200681530999860641597181672463704794566473241690395901768680673716414` ~
`243691584391572899147223065906633310537507956952626106509069491302359792769` ~
`378934570685117202046921464019396759638376362935855896435623442486036961070` ~
`534574698959398017332214518246531363445309522357827985468581166065335726996` ~
`711467464306784543112544076165391268106101754253962102479935962248302404638` ~
`21737237102628470475027851189594709504`);
b.fromDecimalString(
`335690982744637013564796917901053301979460129353374296317539383938630086938` ~
`465898213033510992292836631752875403891802201862860531801760096359705447768` ~
`957432600293361240407059207520920532482429912948952142341440301429494694368` ~
`264560802292927144211230021750155988283029753927847924288850436812178022006` ~
`408597793414273953252832688620479083497367463977081627995406363446761896298` ~
`967177607401918269561385622811274398143647535024987050366350585544531063531` ~
`7118554808325723941557169427279911052268935775`);
BigDigit[] cdata = new BigDigit[a.uintLength() + b.uintLength()];
mulInternal(cdata, a.data, b.data); // Crashes
}
Also, this test is a bit further reduction.
Note that the crash disappears if you change the operand sizes (by adding or removing a few lines in either a or b), so it's specific to particular length of the operands.
The crash message is now more specific:
"core.exception.AssertError@m\biguintcore.d(1190): Bigint Internal Error: Asymmetric Karatsuba"
So I think it's related to how mulInternal divides the operands before calling mulKaratsuba.
However, this bug is now probably applies to both 32-bit and 64-bit!
This blocks D's BigUint (and be extension BigInt) use in any non-toy calculation.
Comment #5 by kkryukov — 2016-07-12T04:48:44Z
Looks like it might be the same issue with #11599 ( https://issues.dlang.org/show_bug.cgi?id=11599 )
If so, "Asymmetric Karatsuba" bug is known since 2013, and stays unfixed. Which practically means that no one uses D's BigInt in large calculations.
Comment #6 by github-bugzilla — 2017-10-28T13:22:14Z
