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

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

1 голос
/ 30 мая 2019

Я пытаюсь написать классическую функцию fib (n) в сборке (intel x86) , которая возвращает 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

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

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

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

n = 6: 3
n = 7: 3
...

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

1 Ответ

1 голос
/ 30 мая 2019

Чего мне не хватает?

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

Вам не нужно enter и leave. Параметры не были переданы.
Индекс rdi проще сохранить при входе fib_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

EDIT

В приведенной ниже версии кода содержатся комментарии, сделанные rcgldr и Peter Cordes .
Этот код теперь удаляет 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
...