On the 31st of October 2009, sometime in the afternoon, the topic of Fibonacci came up, on the computer science channel for the University of Adelaide. I think the weeks coding activity for first years was to write a recursive Fibonacci algorithm. That said, future post will be why recursive Fibonacci is the wrong way of thinking about the problem. I was in my third year and for fun I decided that instead I would write an iterative one, in p in C. After that was done was still not happy with that as being an end point so I decided it was time to learn a little bit of X86 assembly. So the logical step here was to translate the algorithm I wrote to x86 assembly which goes a little as follows:

fib.x86.asm

        .text
.globl _fib

# Fibonacci in x86 assembly by Sean Donno <darkdonno@gmail.com> 
#
# Paramter n is in  0x8(esp) store in ebx
# Return via eax (last)
# ecx = n  (loaded from 0x(esp)
# ebx = secondlast
# eax = last  (and the value returned)
 
_fib:
    pushl %ebp
    movl  %esp, %ebp
    pushl %ebx
    pushl %ecx
    # Saved Registers
 
    movl 8(%ebp), %ecx          # ecx = n
    movl $0, %ebx               # ebx = secondlast = 1
    movl $1, %eax               # eax = last = 0
    jmp    fib2
fib1:
    add  %ebx, %eax             # last = last + secondlast
    neg  %ebx
    add  %eax, %ebx             # secondlast = secondlast + last
    dec  %ecx                   # n = n  1
fib2:
    cmp  $0, %ecx
    jne  fib1                   # if n != 0 goto fib1
 
    # Restore registers and return
    popl %ecx
    popl %ebx
    popl %ebp 
    ret

Code available on Google Docs at https://docs.google.com/Doc?docid=0AXW7elIWGgADZGR6ZHJkMl8xMzd6ZHBxNmhk&hl=en, I really wish WordPress had support this JavaScript syntax highlighter so it provides a a plain version, and can do line numbers, and colouring on the fly, it might and I just haven’t looked hard enough. At the time of writing this i am using hosting at wordpress.com so to the best of my knowledge installing any plugins are not possible.

The comments make more sense when you can compare it to the C version, a while later I followed this up with a version for DLX, for those who haven’t gone to the University of Adelaide (UofA), DLX is a a RISC processor designed by Hennessy and Patterson, who worked on the MIPS architecture, and its a slightly slimmer version of MIPS, that is taught in the Computer Systems course at UofA.  For some comparison the DLX version is 10 instructions, but passes arguments via registers instead of a stack, which is what 7 of the instructions is the x86 version does. There are 15  lines of comments in the traditional ‘function’ commenting style used in the course, which outnumbers the actual lines of code.

Advertisements