段错误在d为过大的输入

Question

以下d程序崩溃输入939971或更高，但不为输入939970或更低：

#!/usr/bin/rdmd --shebang -w -d-debug --relocation-model=pic 
    import std.stdio; 
import std.bigint; 
import std.conv; 
import std.array; 
//extern (C) void fibonacci (int* pointer, int length); 
int main(string[] args) 
{ 
    args.popFront(); 
    foreach(size_t i, string a; args) { 
    writeln(fibonacci(to!BigInt(a))); 
    } 
    return 0; 
} 



BigInt fibonacci (BigInt input) 
{ 
    struct FibMatrix 
    { 
    BigInt a; 
    BigInt b; 
    BigInt d; 

    this(bool test) 
    { 
     a = 1; 
     if (test) { 
     b = 1; d = 0; 
     } else { 
     b = 0; d = 1; 
     } 
    } 

    void square() 
    { 
     BigInt f = b^^2; 
     b = b*(a + d); 
     a = a^^2 + f; 
     d = d^^2 + f; 
    } 

    void opOpAssign(string op, FibMatrix) (FibMatrix input) 
    { 
     static if (op == "*") 
     { 
     BigInt temp1 = b * input.b; 
     d *= input.d; 
     d += temp1; 
     b *= input.d; 
     b += a*input.b; 
     a *= input.a; 
     a += temp1; 
     } else static assert(0, "Unsupported operator"); 
    } 
    } 
    if (input == 0) { 
    return BigInt(0); 
    } else { 
    input -= 1; 
    } 
    FibMatrix base = FibMatrix(true); 
    FibMatrix result = FibMatrix(false); 
    version (none) 
    { 
    writeln (result.a); 
    writeln (result.b); 
    writeln (result.d); 
    } 
    if (input % 2 == 1) { 
    result *= base; 
    } 
    version (none) 
    { 
    writeln (result.a); 
    writeln (result.b); 
    writeln (result.d); 
    } 
    input /= 2; 
    while (input > 0) { 
    base.square(); 
    if (input % 2 == 1) { 
     result *= base; 
    } 
    input /= 2; 
    } 
    return result.a; 
} 

堆栈跟踪：

#0 0x0000003c51b492e6 in __memcpy_ssse3_back() from /lib64/libc.so.6 
#1 0x000000000043d6d8 in std.internal.math.biguintcore.inplaceSub()() 
#2 0x000000000043c340 in std.internal.math.biguintcore.mulKaratsuba()() 
#3 0x000000000043c519 in std.internal.math.biguintcore.mulKaratsuba()() 
#4 0x000000000043ad34 in std.internal.math.biguintcore.mulInternal()() 
#5 0x000000000043a7ef in std.internal.math.biguintcore.BigUint.mul()() 
#6 0x000000000040a8a6 in std.bigint.BigInt.__T10opOpAssignVAyaa1_2aTS3std6bigint6BigIntZ.opOpAssign()() 
#7 0x0000000000403f00 in std.bigint.BigInt.__T8opBinaryVAyaa1_2aTS3std6bigint6BigIntZ.opBinary()() 
#8 0x000000000040456b in getints.fibonacci()() 
#9 0x00000000004035d9 in getints.fibonacci()() 
#10 0x0000000000402f4a in D main() 
#11 0x000000000045bfea in rt.dmain2._d_run_main()() 
#12 0x000000000045bc06 in _d_run_main() 
#13 0x0000003c51a21b45 in __libc_start_main() from /lib64/libc.so.6 
#14 0x0000000000402d29 in _start() 

看起来像一个错误在火卫一对我 - 我是否正确？

Answer 1

问题是std.BigInt中的一个错误，它在乘以过大的BigInt值时导致崩溃。这可能是因为Karatsuba乘法算法的实现不好，因为阻止它被使用来修复问题，迫使它使用乘法BigInts的标准方法（对于这样的大输入效率较低，但没有bug ）。

Answer 2

我认为您的应用程序进程正在达到堆栈大小限制。什么我到达这里时，我编译和运行是：

object.Error: Access Violation 
---------------- 
0x0041DDDC 
---------------- 
Press any key to continue . . . 

0x0041DDDC是一个熟悉的号码 - 这恰恰是4MB（4 * 1024 * 1024）。所以我的第一个猜测是 - 你达到了堆栈大小限制。

更新：挖掘什么是DMD设置的默认堆栈大小导致发现this thread on D forum的一点点。根据该线程，DMD显然设置了4k千字节（4mb）的堆栈大小，我相信这解释了为什么我们得到了上述错误。