Хвостовая рекурсия в сборке - PullRequest
Новая
       9

Хвостовая рекурсия в сборке

4 голосов
/ 04 апреля 2011

Я пытаюсь немного изучить ассемблер. Я использую NASM вместо синтаксиса AT & T.

Это моя первая программа, она сравнивает два аргумента командной строки и выводит, какой из них наименьший (предпочтительнее первого в случае, если они равны).

Я думаю, что я делаю это неправильно. Я заметил, что стек растет с каждым «вызовом» сравнения, поэтому я мог бы сделать это лучше с оптимизацией хвостовой рекурсии. Однако я не знаю, как это сделать правильно. Должен ли я заменить все вхождения 'call' здесь чем-то другим, например, jmp? Я читал, что способ перехода также зависит от того, как вы связываетесь с ядром linux и / или libc относительно объектов 'function' (я не связываюсь с libc и поэтому не имею основной 'function'), что меня смущает, поэтому я думал, что приду сюда за простым кратким советом.

Кроме того, еще один вопрос, который у меня возник, заключается в том, насколько глупо делать «jl» сразу после «jg», что может вызвать нежелательное поведение, если переход «jl» фактически изменил содержимое флага, поэтому «jg» также переходит. Есть ли двусторонний «атомный» прыжок? 

section .data
    usage:  db 'Please provide two strings',10
    usageLen:   equ $-usage
    bigger:     db 'It is bigger!',10
    biggerLen: equ $-bigger
    smaller:    db 'It is smaller!',10
    smallerLen: equ $-smaller

section .text
    global _start

_start:
    pop ebx ; argc
    cmp ebx, 3
    jne usage_exit

    pop eax ; argv[0]
    pop eax
    pop ebx
    call compare ;

usage_exit:
    mov eax, 4 ; sys_write
    mov ebx, 1 ; int fd = stdout
    mov ecx, usage 
    mov edx, usageLen 
    int 80h ; call kernel

    mov eax, 1  ; sys_exit
    mov ebx, 0  ; int status = 0
    int 80h ;   call kernel

report:
    mov ecx, eax
    mov edx, ebx 
    mov eax, 4 ; sys_write
    mov ebx, 1 ; int fd = stdout
    int 80h ; call kernel

    mov eax, 1  ; sys_exit
    mov ebx, 0  ; int status = 0
    int 80h ;   call kernel (exit)

compare:
    push eax
    push ebx
    mov eax, [eax]
    mov ebx, [ebx]

    test ax, ax
    jz is_smaller
    test bx, bx
    jz is_bigger

    cmp ax, bx
    jl is_smaller
    jg is_bigger
    ; if the same, try next positions
    pop ebx
    pop eax
    inc eax
    inc ebx
    call compare

is_smaller:
    mov eax, smaller
    mov ebx, smallerLen
    call report

is_bigger:
    mov eax, bigger
    mov ebx, biggerLen
    call report

1 Ответ

5 голосов
/ 04 апреля 2011

Да, вы должны заменить call с jmp с.В общем случае вы должны использовать call, когда ожидаете возобновления выполнения в следующей строке после возврата вызова.В вашем коде выполнение никогда не возвращается, поскольку compare - это просто цикл, поэтому jmp - правильный путь для перехода к следующей итерации.То же самое верно для двух экземпляров call report, которые у вас есть.

Что касается вашего второго вопроса, jl не меняет флаги, поэтому нет проблемы вызвать jg после него.

...