Написание рекурсивной факториальной функции в x86-64

Следующая ассемблерная программа печатает факториал числа:

SYS_EXIT = 60
.globl _start
_start:
    # run 4! --> 4*3*2*1 = 24
    mov $4,  %edi   
    call factorial
    mov %eax, %edi
    mov $SYS_EXIT, %eax
    syscall

.type factorial @function
factorial:

    # if it is the base case, return 1 and exit
    cmp $1, %edi  
    jne _factorial
    mov $1, %eax
    ret

_factorial:
    # if not the base case, set up the stack frame
    push %rbp
    mov %rsp, %rbp

    push %rdi    # move the current value or n to the stack, 
    dec %rdi     # so we can pop it later and multiple by the factorial(n-1) function
    call factorial
    pop %rbx
    mul %rbx    # multiples eax (return of factorial) by previoud rdi (n)

    # clean up the stack frame
    mov %rbp, %rsp
    pop %rbp
    ret

Вот пример вывода:

$ как factorial.s -o factorial.o && ld factorial.o -o factorial && ./factorial; эхо $?
24

Как программа выглядит? Любая обратная связь будет принята с благодарностью!

1 ответ
1

Обработка ввода

По крайней мере, на первый взгляд кажется, что это неправильно обрабатывает факториал нуля. 0! равно 1, поэтому исправить это довольно просто, изменив jne _factorial к ja _factorial:

# if it is the base case, return 1 and exit
cmp $1, %edi  
ja _factorial
mov $1, %eax
ret

Поскольку факториал не определен (по крайней мере, обычно) для отрицательных чисел, я обработал ввод как беззнаковый. Если вы хотите рассматривать его как подписанный, вы должны использовать jg вместо того ja.

Регистрация использования

mul дает результат в edx:eaxне только в eax, поэтому обычно нужно очистить edx прежде чем вы начнете умножать.

Кадр стека

Я бы немного переписал функцию, чтобы использовать внутреннюю функцию для рекурсии. Эта внутренняя функция будет использовать чисто регистровое соглашение о вызовах, чтобы избежать установки фрейма стека для каждого вызова.

Используя синтаксис Intel, я бы написал код примерно в таком порядке:

; when first called, input value in edi
; and edx:eax containing 0:1
; result: factorial in edx:eax
;
internal_factorial:
    mul eax, edi
    sub edi, 1
    jz  done
    call internal_factorial
done:
    ret

Тогда основная процедура будет выглядеть примерно так:

factorial:
    mov eax, 1    ; prepare our 64-bit result value in edx:eax
    xor edx, edx
    cmp edi, eax  ; check for (either) base case
    jbe do_ret    ; if it's not a base case, compute the factorial
    call internal_factorial
do_ret:
    ret

  • Почему вы обнуляете edx? Он никогда не читается, только записывается ( mul) в OP, и в остальном он полностью не используется в вашей версии.

    – 1201 ProgramAlarm

  • @ 1201ProgramAlarm: очистка EDX позволяет вызывающему абоненту фактически получить результат в edx: eax, а не только в eax. В зависимости от предыдущего состояния процессора это также может улучшить скорость. Процессор обнаруживает очистку регистра (например, с помощью xor reg, reg или sub reg, reg), поэтому впоследствии он знает, что операции, влияющие на этот регистр, не зависят от его предыдущего состояния, поэтому он может выполнять два набора операций параллельно.

    – Джерри Гроб

  • Один операнд mul перезаписывает rdx, предыдущее состояние не имеет значения. Это div перед которым rdx обычно следует обнулять

    – Гарольд

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *