Introduction
Welcome back, my fellow nerds. It's been a while. Almost two years, actually, but who's counting? (Me. I am. It's embarrassing.)
If you recall, in the last post, A Stack to rule them all, we learned what functions and procedures are, how to pass parameters through the stack and why the stack moves in steps of 4 or 8 bytes. We also built an itoa function that I promised to explain in detail "in a later post". Well, this is the later post. Surprise.
But explaining a function on its own is a bit boring, so I'm going to sneak it inside something more fun. Have you ever heard of FizzBuzz? It's a tiny program that interviewers love to throw at people to see if they can actually code. The rules are simple. Count from 1 to 100, but if the number is a multiple of 3 print Fizz, if it's a multiple of 5 print Buzz, and if it's a multiple of both print FizzBuzz. In Python it takes about four lines. In Assembly it takes a bit more than that, and a lot more patience.
My intention for this post is to teach you how loops and conditions work in Assembly. Spoiler alert, they don't exist. Not as you know them, at least. Then we'll use them to build FizzBuzz, and we'll give our good old itoa a well deserved upgrade along the way. I'll be assuming you've read the previous NASM posts, or at least that you know what mov, push, call and int 0x80 do. If you don't, go check Your First NASM Program and come back. I'll wait.
Loops? In this economy?
In C you have for, while, do while, if, else, switch... a whole buffet. In Assembly you have labels and jumps. That's it. That's the buffet.
Remember labels? We used them in the last post to mark where a function starts. Well, a label is nothing more than a name for a memory address, so you can put them anywhere you want and jump to them whenever you want. And if you jump back to a label that's above you, congratulations, you've made a loop.
my_first_loop:
; Do something very important here
jmp my_first_loop ; And then do it again. Forever. jmp means jump, and it does exactly what it says on the tin. It tells the CPU "forget about the next instruction, go execute the one at this label instead". The problem is that this loop never ends. It will run until the heat death of the universe, or until you hit Ctrl+C, whichever comes first. We need a way to get out of it, and for that we need to make decisions.
cmp: The judge
Making a decision in Assembly takes two steps. First you compare two things, and then you jump (or not) depending on the result. The comparing part is done by cmp.
cmp eax, 10 ; Compare eax with 10 Now here comes the weird part. cmp doesn't return anything. It doesn't store the result in any register you can use. What it actually does is subtract the second value from the first one (eax - 10 in this case), throw the result to the trash, and keep only some notes about how it went. Was the result zero? Was it negative? Did it overflow? These notes are stored in a special register called EFLAGS, and each note is a single bit called a flag.
You don't need to memorize the flags (I certainly don't). The only one you need for now is the Zero Flag. If both values are equal, the subtraction is 0, so the Zero Flag turns on. That's how the CPU knows two numbers are equal. A bit roundabout, but hey, it's Assembly, what did you expect?
Conditional jumps: The executioners
Once cmp has left its notes, a conditional jump reads them and decides whether to jump or keep going down like nothing happened. There are a bunch of them, but these are the ones you'll use 99% of the time:
| Instruction | Jumps if... | In C |
|---|---|---|
je | Jump if Equal | a == b |
jne | Jump if Not Equal | a != b |
jl | Jump if Less | a < b |
jle | Jump if Less or Equal | a <= b |
jg | Jump if Greater | a > b |
jge | Jump if Greater or Equal | a >= b |
And with that, we can finally build a proper loop. This one counts from 1 to 10:
mov esi, 1 ; i = 1
my_loop:
; Do something with esi here
inc esi ; i++
cmp esi, 10 ; Compare i with 10
jle my_loop ; If i <= 10, go back up Read it from top to bottom. We set esi to 1, do our thing, increase it by one with inc, compare it with 10, and if it's still less or equal, we jump back to my_loop. Once esi becomes 11, jle doesn't jump, and the CPU just continues with whatever is below. That's the whole trick. Every loop you will ever write in Assembly is some variation of this.
You might have noticed that the check is at the bottom. This means the body always runs at least once, which in C would be a do while. Keep that in mind, because it's going to be important later.
And the if?
Same ingredients, different recipe. Instead of jumping back up, you jump forward, over the code you don't want to execute.
cmp eax, 0
jne skip_this ; If eax != 0, skip the next part
; This only runs if eax == 0
skip_this:
; This runs always Notice how the condition is inverted. In C you would write if (eax == 0) { ... }, but in Assembly you say "if it's NOT 0, get out of here". It feels backwards at first, and it is, but you get used to it. Mostly.
Is it divisible?
Now that we know how to loop and how to make decisions, there's only one thing left before we can play FizzBuzz. How do we know if a number is a multiple of 3? Easy, we divide it by 3 and check if there's any remainder. And we already know how to do that, because itoa was doing it all along with div.
mov eax, esi ; The number to divide goes in eax
xor edx, edx ; Clear edx
mov ebx, 3 ; The divisor
div ebx ; eax = esi / 3, edx = esi % 3 div is a bit picky. It doesn't let you choose where the number to divide is, it always divides whatever is in eax. Technically it divides edx and eax glued together as a single 64-bit number, which is why we clear edx first with the classic xor trick. If you forget it, you'll be dividing whatever garbage was left in edx and your results will be... creative. Then, once it's done, the result goes to eax and the remainder goes to edx.
So, to know if esi is a multiple of 3, we just need to check if edx is 0. And we know how to do that now, don't we?
Fizz, Buzz and a cheap trick
Here's where most people (me included, the first time) write three checks. One for 15, one for 3 and one for 5, in that exact order, because if you check 3 first, 15 will print Fizz and call it a day. It works, but there's a lazier way, and lazy is good when every line costs you this much.
If a number is a multiple of 3, print Fizz. Then, independently, if it's a multiple of 5, print Buzz. If it's a multiple of both, it will print Fizz and then Buzz right after, which gives you... FizzBuzz! No special case needed. The only thing we need to remember is whether we printed anything at all, because if we didn't, we have to print the number itself. For that I'm using edi as a little flag. 0 means nothing printed, 1 means something was.
fizzbuzz_loop:
xor edi, edi ; edi = 0 means "nothing printed yet"
; Is it a multiple of 3?
mov eax, esi
xor edx, edx
mov ebx, 3
div ebx ; edx = esi % 3
cmp edx, 0 ; Any remainder?
jne check_five ; If so, skip the Fizz
mov ecx, fizz ; Print "Fizz"
mov edx, fizz_len
call print
mov edi, 1 ; And remember we printed something
check_five:
; Exactly the same thing, but with 5 and Buzz
.
.
.
check_number:
cmp edi, 1 ; Did we print Fizz and/or Buzz?
je next_number ; If so, skip the number Two things might catch your eye here. First, why is the counter in esi and not in ecx, which is literally called the counter register? Because every time we print something, the write syscall needs ecx for the address of the message, and our counter would get trampled. If you check the loop.asm in my repo you'll see past me pushing and popping ecx all over the place to survive this. Using esi is much simpler, since nobody else here touches it.
Second, what the hell is call print? It's a tiny procedure I made because I got tired of writing the same four lines over and over again:
; Procedure. Prints a string to stdout.
; Parameters (in registers this time, not the stack):
; ecx -> address of the string
; edx -> length of the string
print:
mov eax, 4 ; System call number for write
mov ebx, 1 ; File descriptor for stdout
int 0x80
retNotice that this time the parameters go in registers instead of the stack. Last post I told you to push everything onto the stack, and that's the safe bet, but for a tiny procedure like this one, registers are faster and way less of a hassle. Neither is wrong, as long as you document which one you are using. Did I mention you should document your code? I think I did. Twice.
itoa, the sequel
Alright, time to pay my debts. Here's the int_to_str from the last post, with a couple of improvements I'll explain in a second:
int_to_str:
mov eax, [esp + 4] ; Grab the number
mov edi, buffer + 12 ; Point right after the end of the buffer
mov ebx, 10
itoa_loop:
xor edx, edx ; Clear edx for the division
div ebx ; eax = eax / 10, edx = last digit
add dl, '0' ; Convert the digit to ASCII
dec edi ; Move one byte to the left...
mov [edi], dl ; ...and store the character there
test eax, eax ; Anything left to convert?
jnz itoa_loop ; If so, keep going
mov ecx, edi ; Address of the first digit
mov edx, buffer + 12 ; End of the buffer...
sub edx, edi ; ...minus the start = amount of digits
ret First, the idea. If you divide a number by 10, the remainder is its last digit. 4321 divided by 10 is 432, with a remainder of 1. Divide 432 by 10 and you get 43 with a remainder of 2. Keep going until there's nothing left, and you get all the digits... backwards. 1, 2, 3, 4. That's why we start at the end of the buffer and move to the left with dec edi, so the digits end up in the right order.
Then, adding '0' turns the digit into a character you can print. In ASCII, '0' is 48, '1' is 49 and so on, so 1 + 48 = 49 = '1'. Neat.
You might also notice test eax, eax instead of cmp eax, 0. It's the same thing for our purposes. test does an AND between both values and sets the flags, and since a number AND itself is the number itself, the Zero Flag will be on only if eax is 0. People use it out of habit because it's slightly shorter. I use it because I saw people use it.
Now the improvements, and they come with a confession. The old version had a special case to handle the number 0, remember? That's gone, and I didn't replace it with anything. Why? Because the loop is a do while. The check is at the bottom, so the body always runs at least once. If the number is 0, it divides 0 by 10, gets a remainder of 0, writes '0', and leaves. Free special case. Told you it was important.
The second improvement is the return value. The old version didn't return anything useful, and we printed the whole 12-byte buffer every time, including all the empty bytes at the beginning. Your terminal was nice enough to not show them, but they were there, believe me. The new version returns the address of the first digit in ecx and the amount of digits in edx. Those happen to be exactly the registers print wants, so we can call one right after the other. Totally a coincidence. I did not plan that at all.
push esi ; Parameter for int_to_str
call int_to_str ; Returns the string in ecx and its length in edx
add esp, 4 ; Remove the parameter from the stack
call print ; ecx and edx are already set. How convenientWhat about the loop instruction?
Fun fact, x86 has an instruction literally called loop. It decreases ecx by one and jumps to a label if ecx is not 0 yet. Sounds perfect, right? Well, it has two problems. It only works with ecx, which, as we just saw, gets trampled by every single syscall. And on a lot of modern Intel processors it's actually slower than doing dec and jnz by hand. Don't ask me why. The CPU people decided so and who am I to argue.
So it's nice to know it exists, but you'll rarely see it in the wild, and we won't be using it here.
Full code
Here's everything together so you can copy, paste and break it at your leisure. You can also find it in my AssemblyToyPrograms repo, under x86_64/linux/fizzBuzz.
; FizzBuzz in NASM (x86, 32 bits, Linux)
; Prints the numbers from 1 to LIMIT, but:
; - multiples of 3 print "Fizz"
; - multiples of 5 print "Buzz"
; - multiples of both print "FizzBuzz"
LIMIT equ 100
section .bss
buffer resb 12 ; Room for a 32-bit number (10 digits max) and some spare
section .data
fizz db "Fizz"
fizz_len equ $-fizz
buzz db "Buzz"
buzz_len equ $-buzz
newline db 10
section .text
global _start
_start:
mov esi, 1 ; esi is our counter. The syscalls don't touch it
fizzbuzz_loop:
xor edi, edi ; edi = 0 means "nothing printed yet"
; Is it a multiple of 3?
mov eax, esi ; div always divides eax...
xor edx, edx ; ...and edx too, so clean it first
mov ebx, 3
div ebx ; eax = esi / 3, edx = esi % 3
cmp edx, 0 ; Any remainder?
jne check_five ; If so, it's not a multiple of 3. Skip the Fizz
mov ecx, fizz ; Print "Fizz"
mov edx, fizz_len
call print
mov edi, 1 ; And remember we printed something
check_five:
; Is it a multiple of 5?
mov eax, esi
xor edx, edx
mov ebx, 5
div ebx ; edx = esi % 5
cmp edx, 0
jne check_number ; Not a multiple of 5. Skip the Buzz
mov ecx, buzz ; Print "Buzz"
mov edx, buzz_len
call print
mov edi, 1
check_number:
; If we printed Fizz and/or Buzz, we are done with this number
cmp edi, 1
je next_number
; Otherwise print the number itself
push esi ; Parameter for int_to_str
call int_to_str ; Returns the string in ecx and its length in edx
add esp, 4 ; Remove the parameter from the stack
call print ; ecx and edx are already set. How convenient
next_number:
mov ecx, newline ; Print a newline
mov edx, 1
call print
inc esi ; Next number
cmp esi, LIMIT ; Have we reached the limit?
jle fizzbuzz_loop ; while (esi <= LIMIT) { ... }
; Exit program
mov eax, 1 ; System call number for exit
xor ebx, ebx ; Exit code 0
int 0x80
; Procedure. Prints a string to stdout.
; Parameters (in registers this time, not the stack):
; ecx -> address of the string
; edx -> length of the string
; Clobbers eax and ebx
print:
mov eax, 4 ; System call number for write
mov ebx, 1 ; File descriptor for stdout
int 0x80
ret
; Function. Receives a number on the stack and turns it into text.
; Returns:
; ecx -> address of the first digit
; edx -> amount of digits
; Clobbers eax, ebx and edi
int_to_str:
; Same stack as last time:
; ,_________________,
; |_________________|
; |_______ret_______| <-- esp points here
; |_______esi_______|
; |_________________|
mov eax, [esp + 4] ; Grab the number
mov edi, buffer + 12 ; Point right after the end of the buffer
mov ebx, 10
itoa_loop:
xor edx, edx ; Clear edx for the division
div ebx ; eax = eax / 10, edx = last digit
add dl, '0' ; Convert the digit to ASCII
dec edi ; Move one byte to the left...
mov [edi], dl ; ...and store the character there
test eax, eax ; Anything left to convert?
jnz itoa_loop ; If so, keep going
; edi points to the first digit. Build the return values
mov ecx, edi ; Address of the first digit
mov edx, buffer + 12 ; End of the buffer...
sub edx, edi ; ...minus the start = amount of digits
ret You may have spotted LIMIT equ 100 at the top. equ creates a constant, so if you want to FizzBuzz up to 1000 you only have to change it in one place. Go wild.
Compile and run
With cmplasm from the repo, it's a one-liner:
$ ./cmplasm x86_64/linux/fizzBuzz/fizzbuzz.asm Compilation successful: x86_64/linux/fizzBuzz/fizzbuzz
And for those of you who still don't trust me (good, keep it that way), here's how to do it by hand:
$ nasm -f elf32 fizzbuzz.asm -o fizzbuzz.o $ ld -m elf_i386 fizzbuzz.o -o fizzbuzz
Run it, and behold:
$ ./fizzbuzz 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 ...
Hired. Probably.
The end
And that's it. You've learned that loops and ifs are just jumps in disguise, how cmp and the flags work together to make decisions, how to get the remainder of a division, and what itoa was doing all this time. Not bad for a program that prints Fizz a bunch of times.
Next time I want to do something a bit more interactive. So far our programs talk, but they don't listen. We'll fix that by reading what the user types and turning it back into a number (yes, itoa has an evil twin, and it's called atoi). And what better excuse to do that than a little guessing game?
Until then, happy coding, and may your jumps always land where you expect them to.
Comments
Post a Comment