c - 汇编 x86/C - 递归二项式系数段错误/打印帕斯卡三角形

Question

我编写了一些代码(主程序在 c 中，子程序在汇编 x86 中)来递归计算所有二项式系数并打印出 n=10 的所有二项式系数，受 m<=n 限制。

所以基本上我试图输出 n=10 的帕斯卡三角形。 (没有三角形的完整格式)

我的问题是我在编译时遇到段错误，并且无法弄清楚如何打印递归函数生成的各个值。

Segmentation fault (core dumped)

这是主程序:

#include <stdio.h>

unsigned int result,m,n,i;
unsigned int binom(int,int);
int main(){

n=10;


for (i=0; i<n+1;i++){
printf("i=%d | %d \n", i, binom(n,i) );
}

return;


}

以及递归子程序:

    .text
    .globl  binom

binom: 
    mov     $0x00, %edx     #for difference calculation
    cmp     %edi, %esi          #m=n?
    je      equalorzero         #jump to equalorzero for returning of value 1
    cmp     $0x00, %esi         #m=0?
    je      equalorzero     
    cmp     $0x01, %esi         #m=1?

    mov     %esi,%edx
    sub     %edi, %edx
    cmp     $0x01, %edx         # n-m = 1 ?
    je      oneoronedifference  

    jmp     otherwise

equalorzero:
    add     $1, %eax            #return 1
    ret 

oneoronedifference:
    add     %edi, %eax          #return n
    ret

otherwise:
    sub     $1, %edi            #binom(n-1,m) 
    call    binom       
    sub     $1, %esi            #binom(n-1,m-1)
    call    binom

这就是 gcc 给我的

./runtimes
i=0 | 12 
Segmentation fault (core dumped)

Answer 1

汇编代码的两个主要问题是:1)您既不添加也不返回两个递归调用的总和； 2)您没有将本地变量保存在堆栈中，因此它们会被递归调用清除——一旦从调用返回，您就使用了错误的值。这是我对您的代码的修改，其中一些更改是由于我在 OSX 下编写的:

递归子程序:

    .text
    .globl  _binom

_binom:
    pushq   %rbp                 # allocate space on stack for locals
    movq    %rsp, %rbp
    subq    $24, %rsp

    cmpl    %edi, %esi           # m == n ?
    je      equalorzero          # jump to equalorzero for returning of value 1
    cmpl    $0, %esi             # m == 0 ?
    je      equalorzero     

    movl    %esi, %edx
    subl    %edi, %edx
    cmpl    $1, %edx             # n - m == 1 ?
    je      oneoronedifference  

    subl    $1, %edi             # binom(n - 1, m) 
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    callq   _binom

    movl    %eax, -12(%rbp)      # save result to stack

    movl    -4(%rbp), %edi
    movl    -8(%rbp), %esi
    subl    $1, %esi             # binom(n - 1, m - 1)
    callq   _binom

    addl    -12(%rbp), %eax      # add results of the two recursive calls
    addq    $24, %rsp            # release locals space on stack
    popq    %rbp
    retq

equalorzero:
    movl    $1, %eax             # return 1
    addq    $24, %rsp            # release locals space on stack
    popq    %rbp
    retq

oneoronedifference:
    movl    %edi, %eax           # return n
    addq    $24, %rsp            # release locals space on stack
    popq    %rbp
    retq

主程序:

#include <stdio.h>

extern unsigned int binom(int, int);

int main() {

    int n = 10;

    for (int i = 0; i <= n; i++) {
        printf("i=%d | %d\n", i, binom(n, i));
    }

    return 0;
}

结果:

i=0 | 1
i=1 | 10
i=2 | 45
i=3 | 120
i=4 | 210
i=5 | 252
i=6 | 210
i=7 | 120
i=8 | 45
i=9 | 10
i=10 | 1