Как найти n-й элемент последовательности Фибоначчи в сборке, используя стек и рекурсию

Я пытаюсь написать классическую функцию fib(n) в сборке (Интел х86), которая возвращает n-й элемент последовательности Фибоначчи.

Я довольно легко написал итеративную версию, но у меня возникли проблемы с попыткой манипулировать рекурсией. Вот что я пробовал:

.intel_syntax noprefix

.text

# unsigned fib(unsigned)
.globl fib

fib_n:
    enter 0, 0

    mov eax, 0

    # n = 0 or n = 1
    cmp edi, 1
    jbe end

    mov eax, 1

    # n == 2
    cmp edi, 2
    je end

    # n > 2, entering recursion

    # fib(n-1)
    push rdi
    dec edi

    call fib_n
    mov r8d, eax 

    pop rdi

    # fib(n-2)
    push rdi
    sub edi, 2

    call fib_n
    mov r9d, eax

    pop rdi

    # fib(n) = fib(n-1) + fib(n-2)
    mov eax, r8d
    add eax, r9d

end:
    leave
    ret

Я ожидаю, что вызовы, помеченные как #фиб(n-1) и #фиб(n-1), будут хранить результаты местный eax в регистрах r8d и r9d, а затем просто добавлять их и возвращать через eax, но вот что я получаю на выходе:

n = 1 (1-й эл): 0 (отлично работает)
n = 2:1 (отлично работает)
n = 3:1 (отлично работает)

(неправильные результаты)
п = 4: 2
п = 5: 2

п = 6:3
п = 7:3
...

Я также пытался поместить в стек rax и rdi, но все равно получаю неправильные результаты. Что мне не хватает?

Обратите внимание, что это может занять некоторое время для больших значений n, так как общее количество вызовов будет 2*fib(n)-1. Максимальное значение для 32-битных целых чисел без знака равно fib(47) = 2971215073, поэтому количество вызовов будет равно 5942430145 (5,94 миллиарда).

— 30.05.2019 21:39

recursion assembly x86 stack fibonacci

30.05.2019 18:46

Учебная записка [Medium] Leetcode#22 Generate Parentheses

На этот раз мы собираемся решить еще одну классическую проблему, связанную с парными скобками, так называемую генерацию скобок.

739

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

What am I missing?

Регистр r8d не сохраняется при рекурсивных вызовах.

Вам не нужны enter и leave. Никакие параметры не были переданы.
Легче сохранить индекс rdi на входе выдумка_n.

fib_n:
    push    rdi
    xor     eax, eax
    cmp     edi, 2
    jb      end            ; fib(1) = 0
    mov     eax, 1
    je      end            ; fib(2) = 1
    dec     edi
    call    fib_n          ; -> EAX
    push    rax            ; (1) Preserve intermediate result!
    dec     edi    
    call    fib_n          ; -> EAX
    add     eax, [rsp]     ; fib(n) = fib(n-2) + fib(n-1)
    add     rsp, 8         ; (1)
end:
    pop     rdi
    ret

РЕДАКТИРОВАТЬ

Приведенная ниже версия кода включает комментарии, сделанные rcgldr и Питер Кордес.
Этот код теперь удаляет 5 базовых случаев и стал намного чище.

fib_n:
    cmp     edi, 5         ; n
    jb      .LT5           ; Base-cases
    push    rdi            ; (1) Preserve n
    dec     edi            ; n-1
    call    fib_n          ; -> EAX
    push    rax            ; (2) Preserve intermediate result!
    dec     edi            ; n-2
    call    fib_n          ; -> EAX
    pop     rdi            ; (2) Restore intermediate result
    add     eax, edi       ; fib(n) = fib(n-2) + fib(n-1)
    pop     rdi            ; (1) Restore n
    ret
.LT5:
    mov     eax, edi       ; n < 5
    cmp     edi, 2
    cmc
    sbb     eax, 0         ; fib(0) = 0, fib(1) = 1
    ret                    ; fib(2) = 1, fib(3) = 2, fib(4) = 3

Я понимаю свою ошибку. Но я не понимаю последние две строки вашего кода: add eax, [rsp] add rsp, 8 В eax уже есть результат fib(n-2), но где я использовал сохраненный fib(n-1) значение, которое было помещено в стек (т.е. я не понимаю, как рсп указывает на это значение). Кроме того, зачем нужно удалять 8 байт вместо 4, когда функция имеет только один параметр, используемый регистром рди?

— 30.05.2019 20:49

Редактировать: я пытаюсь понять, как выглядит стек в момент инструкции: добавить рсп, 8. Я предполагаю, что [rsp] = rax (поскольку rax последний раз помещался в стек), [rsp + 4] = rdi (это будет явно извлечено в конце метки), но что находится по адресу [rsp + 8] и как это управляет рекурсией?

— 30.05.2019 21:23

В математике fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, ... .

— 30.05.2019 21:29

@alexein777 push rax хранит 8 байт в стеке. Это результат fib(n-1). Как только fib(n-2) находится в eax, я могу добавить младшие 4 байта, которые есть в стеке, чтобы получить fib(n). В дальнейшем мне нужно удалить все байты 8, чтобы сбалансировать стек.

— 30.05.2019 22:14

@alexein777 [rsp]=rax, [rsp+8]=rdi, [rsp+16]=обратный адрес` 64-битная версия использует 8 байты! 1-й удаляется с помощью add rsp,8, 2-й удаляется с помощью pop rdi, а 3-й удаляется с помощью ret.

— 30.05.2019 22:17

@rcgldr: хороший улов. Так что вместо xor-zero EAX сделайте mov eax, edi вместо return n if (n<2). Но, вероятно, все же стоит еще один je взять fib(2) как еще один базовый случай, который возвращает 1 вместо n, потому что это отрезает еще 2 calls.

— 31.05.2019 00:48

@SepRoland Спасибо за разъяснения, теперь я хорошо понимаю. Еще один вопрос: будет ли поп-ракс вместо добавить рсп, 8 иметь тот же эффект?

— 31.05.2019 16:12

@alexein777 @alexein777 Использование pop rax наверняка повысит rsp на 8, но это также уничтожит результат, который у нас был готов в регистре EAX! Чтобы узнать о другом и более чистом способе кодирования этой проблемы, см. мой отредактированный ответ.

— 02.06.2019 16:34

30.05.2019 20:31