x64 程序集中的递归阶乘子例程导致堆栈溢出

Question

我正在实现一个递归算法来计算 x64 程序集中给定数字的阶乘。（我使用的是 AT&T 语法。）

伪代码如下所示：

int factorial(int x){
    if(x == 1){
        return 1;
    }else{
        return x*factorial(x-1);
    }
 }

现在，我在 x64 汇编中的实现：

factorial:  
    #Start of subroutine
    pushq %rbp
    movq %rsp, %rbp 

    cmpq , %rdi   #If rdi == 1, return 1, otherwise return x*factorial(x-1)
    je if           #je : %rdi == 1

    jmp else

if:                 #return 1
    movq , %rax
    jmp factend

else:               #return x*factorial(x-1)
    pushq %rdi      #Save x
    subq ,%rdi    #Calculate x-1

    call factorial  #Calculate factorial from x-1
    popq %rdi       #Get rdi value before decrement
    mulq %rdi       #Multiply with rax, rax is either 1, or result of previous multiplication

    jmp factend     #End this subroutine, continue with previous 

factend:
    #End of subroutine
    movq %rbp, %rsp
    popq %rbp
    ret

然而，这种实施并没有停止。我得到一个分段错误，这是由堆栈溢出引起的。 if 块永远不会执行，子例程与 else 代码一起陷入循环。如果我一步一步地按照我的实现并记下寄存器和堆栈的值，我似乎运行没有遇到问题。这可能是什么原因造成的？

编辑我如何检索输入值：

formatinput: .asciz "%d"

#Get input from terminal
subq , %rsp
leaq -8(%rbp), %rsi
movq [=12=], %rax
movq $formatinput, %rdi
call scanf

#Calculate factorial of input value
movq -8(%rbp), %rdi
movq , %rax
call factorial

另一个编辑

我的完整代码：

#Define main
.global main

.global inout

#Define string to be printed
formatinput: .asciz "%d"
formatoutput: .asciz "%d\n"

str:    .asciz "Assignment %d"


main:


#Start of program   
    movq %rsp, %rbp

    #Print statement
    movq [=13=], %rax
    movq , %rsi
    movq $str, %rdi
    call printf

    call inout

end:
    #Exit program with code 0, no errors
    movq [=13=], %rdi
    call exit

#inout subroutine
inout:  
    #Start of subroutine
    pushq %rbp
    movq %rsp, %rbp

    #Get input from terminal
    subq , %rsp
    leaq -8(%rbp), %rsi
    movq [=13=], %rax
    movq $formatinput, %rdi
    call scanf

    #Calculate factorial of input value
    movq -8(%rbp), %rdi
    movq , %rax
    call factorial
    movq %rax, -8(%rbp)

    #Print result
    movq [=13=], %rax
    movq -8(%rbp), %rsi
    movq $formatoutput, %rdi
    call printf

    movq %rbp, %rsp
    popq %rbp
    ret

#factorial subroutine
# int factorial(int x){
#   if(x == 1){
#       return 1;
#   }else{
#       return x*factorial(x-1);
#   }
# }

factorial:  
    #Start of subroutine
    pushq %rbp
    movq %rsp, %rbp 

    cmpq , %rdi       #If rdi == 1, return 1, otherwise return x*factorial(x-1)
    jg if           #jg : %rdi > 

    jmp else

if:             #return 1
    movq , %rax
    jmp factend

else:               #return x*factorial(x-1)
    pushq %rdi      #Save x
    subq ,%rdi        #Calculate x-1

    call factorial      #Calculate factorial from x-1
    popq %rdi       #Get rdi value before decrement
    mulq %rdi       #Multiply with rax, rax is either 1, or result of previous multiplication

    jmp factend     #End this subroutine, continue with previous 

factend:
    #End of subroutine
    movq %rbp, %rsp
    popq %rbp
    ret

#print test subroutine
print:
    #Start of subroutine
    pushq %rbp
    movq %rsp, %rbp

    pushq %rdi
    pushq %rsi
    pushq %rax

    movq [=13=], %rax
    movq %rdi, %rsi
    movq $formatoutput, %rdi
    call printf

    popq %rsi
    popq %rdi
    popq %rax

    movq %rbp, %rsp
    popq %rbp
    ret

Answer 1

您使用的是 64 位整数，而您的 C 代码使用 int，通常是 32 位。因此，您的 scanf("%d") 不会触及您加载到 %rdi 中的值的高 32 位以传递给 factorial()。
[= 之前那些高位中的任何内容14=] 现在被解释为您传递的数字的一部分，因此 factorial() 不是像 1 这样的输入，而是将其解释为像 18612532834992129 这样的输入，这会导致堆栈溢出。

您可以在 scanf() with movl -8(%rbp), %edi 之后替换 movq -8(%rbp), %rdi，或者将 scanf() 格式说明符从 %d 更改为 %ld。

movl-变体显示了一个关于 x86-64 的有趣花絮：使用 32 位操作隐式清除 64 位寄存器的高 32 位（例外是 xchg %eax, %eax , 因为这个是规范的 nop).

x64 程序集中的递归阶乘子例程导致堆栈溢出

Recursive factorial subroutine in x64 assembly gives stack overflow

recursion

64-bit

assembly

x86-64

att