linux - 在程序集递归中求解帕斯卡三角 (nCk)

Question

我目前无法从组合问题中得到答案。我的底壳工作得很好。我认为问题在于评估组合(n-1，k)，然后评估组合(n-1，k-1)。

这是我的代码:n 和 k 是用户的输入。

sub esp, 2
push word[n]
push word[k]
call combi
pop word[ans] ;store yung combi value sa ans

;convert to ascii string value
add word[ans], 30h

;print answer
mov eax, 4
mov ebx, 1
mov ecx, ans
mov edx, 2
int 80h

jmp exit


combi:
    mov ebp, esp

    mov ax, word[ebp+4] ;ax = k
    cmp [ebp+6], ax     ;if (n==k)
    je basecase

    cmp word[ebp+4],0   ;cmp k = 0
    je basecase

    ;combi(n-1,k)
    mov ax, [ebp+6] ; ax = n
    mov bx, [ebp+4] ; bx = k

    dec ax ;n-1

    ;execute again
    sub esp, 2
    push ax
    push bx
    call combi
    pop cx      ;stores to cx popped value combi(n-1,k)
    mov ebp, esp ;update pointers

    ;combi(n-1,k-1)
    push ax
    dec bx
    push bx
    call combi
    pop dx     ;stores to dx popped value combi(n-1,k-1)
    mov ebp, esp ;update pointers

    add cx, dx ;combi(n-1,k) + combi(n-1,k-1)

    mov word[ebp+8], cx 
    jmp combi_exit


basecase:
    mov word[ebp+8], 1

combi_exit:
    ret 4

希望得到您的友好回应和绝妙的想法!谢谢!

Answer 1

要修复递归，combi: 的中间部分有问题:

    ...
    call combi
    pop cx      ;stores to cx popped value combi(n-1,k)
;* ^ this freed the allocated space for result
    mov ebp, esp ;update pointers
;* not needed, as you will not use EBP right now, and next call destroys it

    ;combi(n-1,k-1)
    push ax
;* ^ pushing first argument, but no stack space reserved for result
    dec bx
    push bx
    call combi
    ...

要 修复 ，您可以将该部分调整为:

编辑:对于 2+ 深度递归，这将无法正常工作，因为您没有根据需要保留寄存器，整个递归架构需要更加小心，我会选择简单地首先用更简单的设计重写它，而不是解决所有这些小问题。这个“修复”至少会停止段错误。

    ...
    call combi
    mov cx,[esp]      ;stores to cx value combi(n-1,k)
;* ^ keeps the stack space reserved (not popping)
    ;combi(n-1,k-1)
    push ax
    ...

当然还有另一个问题，即您的输出仅对单个数字正确，但只是搜索堆栈溢出和 tag [x86] info对于那些，这里不再重复。

顺便说一句，这个 IMO 源于不幸的过于复杂的使用堆栈，您是否有一些特殊原因为什么要遵循如此复杂的调用约定？在寄存器中提供一些类似自定义快速调用的参数和结果怎么样？它的性能也更高，但就我个人而言，它也更容易正确跟踪事物和处理堆栈。如果我愿意的话，我可能会在稍后将我自己的变体添加到这个答案中......

---

编辑:带有寄存器调用约定的完整工作示例:

文件:so_32b_pascal_triangle.asm

section .text

global _start
_start:
    mov     ecx,5       ; n
    mov     edx,2       ; k
    call    combi
    ; return to linux with sys_exit(result)
    mov     ebx,eax
    mov     eax,1
    int     80h

; ECX = n, EDX = k, returns result in EAX, no other register modified
; (_msfastcall-like convention, but extended to preserve ECX+EDX)
combi:   ; c(n, k) = c(n-1, k-1) + c(n-1, k),   c(i, 0) = c(i, i) = 1
    test    edx,edx     ; k == 0
    je      .basecases  ; c(i, 0) = 1
    cmp     edx,ecx     ; k == n
    je      .basecases  ; c(i, i) = 1
    ; 0 < k < n case:
    dec     ecx         ; n-1
    call    combi       ; EAX = c(n-1, k)
    push    esi
    mov     esi,eax     ; keep c(n-1, k) in ESI
    dec     edx         ; k-1
    call    combi       ; EAX = c(n-1, k-1)
    add     eax,esi     ; EAX = c(n-1, k-1) + c(n-1, k)
    ; restore all modified registers
    pop     esi
    inc     ecx
    inc     edx
    ret                 ; return result in EAX
.basecases:
    mov     eax,1
    ret

编译+运行+结果展示:

...$ nasm -f elf32 -F dwarf -g so_32b_pascal_triangle.asm -l so_32b_pascal_triangle.lst -w+all
...$ ld -m elf_i386 -o so_32b_pascal_triangle so_32b_pascal_triangle.o
...$ ./so_32b_pascal_triangle ; echo $?
10
...$

---

编辑:

并且出于我自己的好奇心，尝试从 C-ish C++ 代码调用它(以验证 fastcall 约定是否按预期工作，即使需要与 C/C++ 的互操作性):

so_32b_pascal_triangle.asm 文件具有相同的combi: 代码，但修改了开头(添加了全局，删除了_start):

section .text

global combi
; ECX = n, EDX = k, returns result in EAX, no other register modified
; (fastcall-like convention, but extended to preserve ECX+EDX)
combi:   ; c(n, k) = c(n-1, k-1) + c(n-1, k),   c(i, 0) = c(i, i) = 1
    ...

文件so_32b_pascal_triangle_Cpp.cpp:

#include <cstdio>
#include <cstdint>

extern "C" __attribute__ ((fastcall)) uint32_t combi(uint32_t n, uint32_t k);

int main()
{
    for (uint32_t n = 0; n < 10; ++n) {
        printf("%*c", 1+2*(10-n), ' ');
        for (uint32_t k = 0; k <= n; ++k) {
            printf("%4d", combi(n, k));
            // 4-char width formatting - works for 3 digit results max.
        }
        printf("\n");
    }
}

构建 + 测试:

$ nasm -f elf32 -F dwarf -g so_32b_pascal_triangle.asm -l so_32b_pascal_triangle.lst -w+all
$ g++ -std=c++17 -c -m32 -O3 -Wall -Wpedantic -Wextra so_32b_pascal_triangle_Cpp.cpp
$ g++ -m32 so_32b_pascal_triangle*.o -o so_32b_pascal_triangle
$ ./so_32b_pascal_triangle
                        1
                      1   1
                    1   2   1
                  1   3   3   1
                1   4   6   4   1
              1   5  10  10   5   1
            1   6  15  20  15   6   1
          1   7  21  35  35  21   7   1
        1   8  28  56  70  56  28   8   1
      1   9  36  84 126 126  84  36   9   1