-
-
Save przemoc/481446 to your computer and use it in GitHub Desktop.
; Fibonacci n-th number (modulo 2^32) | |
; | |
; input: | |
; ecx = n | |
; modifies: | |
; eax, ecx, edx | |
; ouput: | |
; eax = number | |
; size: | |
; 15 bytes | |
use32 | |
_fibonacci: | |
xor eax, eax ; 31 c0 | |
jecxz _fibonacci_end ; e3 0a | |
dec ecx ; 49 | |
inc eax ; 40 | |
jecxz _fibonacci_end ; e3 06 | |
cdq ; 99 | |
_fibonacci_loop: | |
xchg eax, edx ; 92 | |
add eax, edx ; 01 d0 | |
loop _fibonacci_loop ; e2 fb | |
_fibonacci_end: | |
ret ; c3 |
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.
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...
I just noticed that I sent wrong first revision (46a201).
xadd
line (#22) should useebx
instead ofedx
. 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.