Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Tail recursion in assembly

Tags:

x86

assembly

nasm

I'm trying to learn assembly a bit. I use NASM instead of AT&T syntax.

This is my first program, it compares the two command line arguments and outputs which one is the smallest (favouring the first in case they're equal).

I think I'm doing this wrong. I noticed that the stack grows with each "call" of compare, so I could probably make this better with tail recursion optimization. However, I don't know how to do it correctly. Should I replace all occurrences of 'call' here with something else, like jmp? I read that the manner of jumping also depends on how you link with the linux kernel and/or libc regarding 'function' objects (I do not link with libc and so do not have a main 'function'), which confuses me so I thought I'd come here for simple short advice.

Also, another question I had is how foolish it is to do "jl" immediately followed by "jg", which might cause unwanted behaviour if the "jl" jump actually changed the flag contents so "jg" also jumps. Is there a two-way 'atomic' jump?

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
like image 603
buddhabrot Avatar asked Apr 04 '11 15:04

buddhabrot


People also ask

What is tail recursion with example?

Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. For example the following C++ function print() is tail recursive.

What is tail recursion?

(algorithmic technique) Definition: A special form of recursion where the last operation of a function is a recursive call. The recursion may be optimized away by executing the call in the current stack frame and returning its result rather than creating a new stack frame.

When should I use tail recursion?

Anything you would use an imperative loop for should be tail recursive: traversing arrays, linked lists, ranges of integers for math calculations, etc. The exception is if you know the size is bounded.

What is recursion and tail recursion?

In computer programming, a function that calls itself, either directly or indirectly, is a recursive function. When this call happens at the end of the function, it is called tail recursion.


1 Answers

Yes, you should replace the calls with jmps. In general, you should use call when you expect execution to resume on the following line when the call returns. In your code, execution never returns since compare is just a loop, so jmp is the correct way to go to the next iteration. The same is true for the two instances of call report you have.

As for your second question, jl doesn't change the flags, so there is no problem calling jg after it.

like image 178
interjay Avatar answered Sep 27 '22 19:09

interjay