Fibonacci n-th number (modulo 2^32) in x86 assembler

fibonacci.asm

; Fibonacci n-th number (modulo 2^32)
;
; input:
; 	ecx = n
; modifies:
; 	eax, ebx, ecx
; ouput:
; 	eax = number
; size:
; 	16 bytes

use32

_fibonacci:
	xor    eax, eax           ; 31 c0
	jecxz  _fibonacci_end     ; e3 0b
	dec    ecx                ; 49
	inc    eax                ; 40
	jecxz  _fibonacci_end     ; e3 07
	xor    ebx, ebx           ; 31 db
_fibonacci_loop:
	xadd   eax, edx           ; 0f c1 d8
	loop   _fibonacci_loop    ; e2 fb
_fibonacci_end:
	ret                       ; c3

I just noticed that I sent wrong first revision (46a201). xadd line (#22) should use ebx instead of edx. Opcode in comment is correct though. The short story behind this snippet can be found in my techblog - post titled Fibonacci in x86 assembler and the scene.

The old techblog, built on faulty (that's why I stopped after 2nd post there) and non-existent now Posterous, is gone (for quite some time already), but I think I can put above mentioned post right here in the comment for archival purposes.

---

Published: 2010-07-19 20:05:00 +0200

Fibonacci in x86 assembler and the scene

My friend gave me once (long time ago) a programming task. Write as short as possible function (in terms of binary form) in x86 32-bit assembler for finding n-th Fibonacci number. No particular calling convention was required. I've quite easily found satisfactory 16 bytes solution. I've used xadd instruction for conciseness (as a name suggest, its result is identical to xchg + add), but losing portability (486+ required). He saved one more byte by using cdq instruction (that converts signed eax to signed edx:eax) for zeroing edx register in one byte. Funny thing is that his first version, which was sent for asmpak inclusion, was exactly like my final one.

http://gist.github.com/481446

Above nasm-compatible snippet is pretty self-explanatory. There is a good reason for not using ebx that I didn't know then. According to System V Application Binary Interface Intel386 Architecture Processor Supplment it is one of five registers (ebp, ebx, edi, esi, esp) belonging to the calling function, i.e. called function must preserve them. But to conform it further to cdecl calling convention you would have to add pop ecx and push ecx (2 bytes: 59 51) at the beginning of the function, because arguments are pushed onto the stack.

I like assembler for its low-level capabilities. It's the only language giving you the full control over what instructions will be executed in CPU. It is also the third language I've ever touched in my whole programming career. Back then (15 years ago?) assembly language wasn't the best target after Basic and Pascal, but it required me to think almost like a processor which was refreshing, entertaining and of course educational.

Nowadays assembler is rarely used to create applications for x86/x86-64 architecture. It is still useful for fine-tuning hot code paths (e.g. compression, especially optimized for different CPUs) though. Deep understanding of assembly language is also crucial for reverse engineering of viruses, rootkits, malware and other software pests. There is also a crack scene and surroundings, tightly connected with RE along with many wise, intelligent and clever people. Cracking per se is not an evil act. It really requires many skills, thorough software (and often hardware) knowledge and analytical thinking. But evil can be further action, i.e. what you do afterward. There are always white hats and black hats. Even if one group is more noticeable than the other one, it doesn't mean you can treat them all as thugs...

Polish crack scene seems dead. This is sad, because it gathered many skilled RE-oriented guys (and girls?) in its time of glory. Once I started a thread in OSnews.pl forum (sorry, Polish only) asking readers-potential-(ex)crackers/reverse-engineers what is going on with all these great people. One month ago (but I spotted it a few hours ago) somebody impersonating ex-AAoCG member (AAoCG was one of the most widely known Polish cracking teams) responded with his theory of why the scene is dead. To make this short, lack of social work to promote its values and some mix of egoism, vanity and omnipresent commercialism. Sounds likely, isn't it? But one thing shocked me. I wanted to believe, due to my infant naivety w.r.t. this subject, that black hats have their own ideals too and, while we may not understand (or rather disagree with) their way of life, they're just giving results of their work for free. If it's not true for all of them, then which behavior is more common? Are black sheep among them actually gray?

Polish cracking scene had ctrl-d - Polish page with cracking and RE news. There was also an asmpak - nice set of assembler snippets - which is no longer available. Don't worry, I have a copy of its last version from 2004.05.01.

asmpak 000Ch: asmpak000Ch.rar

Rule #0 of the internet: you have to constantly backup it!

Beautiful! Is the cdq to zero edx in a single instruction?

@paulfurber Thanks! xor edx, edx is also a single instruction, but it takes more than 1 byte, while cdq fits there. It requires additional assumption regarding eax to be used for zeroing edx (eax < 0x80000000), but the condition is already met here.

I meant single byte - sorry. Thanks for the clarification.

Hey, I got inspired by this to write a similar function using floating point and the phi formula for finding the nth Fibonacci. ecx is the number and it uses the formula round(phi^n / sqrt(5)) to do it where phi is 1+sqrt(5)/2. Not nearly as small as yours but quite quick:

sys_exit        equ     1


SECTION     .data
phi     dt    1.618033988749894848204
sqrt5   dt    2.236067977499789696409

SECTION     .bss
result  resq 1

SECTION     .text
global      _start


_start:
        mov     ecx, 5
        fld     tword [sqrt5]
        fld     tword [phi]
        fld     tword [phi]
fib:    
        fmul    st1
        loop    fib
        fdiv    st2
        fisttp  qword [result] 

Exit: 
        mov     eax, sys_exit
        xor     ebx, ebx
        int     80H

And here's a version using the same formula but runs in linear time :) :

_start:

        fld     tword [sqrt5]
        fld     tword [n]
        fld     tword [phi]

        fyl2x
        fld     st0
        frndint
        fsub    st1, st0
        fxch    st1
        f2xm1
        fld1
        fadd
        fscale
        fdiv    st2
        fistp  qword [result]
Exit: 
...

@paulfurber: Thanks for providing FP versions! They're not as short as I would like them to be, though. :>

Anyway, I'm not FP guy myself, so I won't fiddle with squeezing it as much as possible (please forgive my rude assumption that it is possible), but others are free to do so in the comments!

And sorry for late reply, but unfortunately gists lacks any notification system...