|; Fibonacci n-th number (modulo 2^32)|
|; ecx = n|
|; eax, ecx, edx|
|; eax = number|
|; 15 bytes|
|xor eax, eax ; 31 c0|
|jecxz _fibonacci_end ; e3 0a|
|dec ecx ; 49|
|inc eax ; 40|
|jecxz _fibonacci_end ; e3 06|
|cdq ; 99|
|xchg eax, edx ; 92|
|add eax, edx ; 01 d0|
|loop _fibonacci_loop ; e2 fb|
|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
Above nasm-compatible snippet is pretty self-explanatory. There is a good reason for not using
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!
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:
@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...