Welcome to Part 2 of my tutorial on coding. This time, we'll be focusing on registers, memory and the stack. This tutorial is quite a bit more involved than the first one. Pay close attention and follow along as these are critical skills if you hope to master coding. Let's get started...
Bits & Bytes
Before we dive into the first subject of registers, let's take a side street through the concept of bits and bytes. If you're new to coding, this is a core concept.
A bit is a number that can be either 0 or 1. You can think of it like a switch that's on or off. Or you can think of it like a boolean that's true or false. Bits are useful because, given enough of them, you can represent any number or data structure you can imagine. In fact, bit-based numbers are just base 2 numbers where the "normal" numbers we deal with are base 10. A shorter way to say bit-based is "binary."
Let's consider some binary numbers to build some clarity:
decimal 0 = binary 0
decimal 1 = binary 1
decimal 2 = binary 10
decimal 3 = binary 11
decimal 4 = binary 100
decimal 5 = binary 101
decimal 69 = binary 1000101
Open up your Windows calculator and put it in programmer mode to experiment with binary numbers on your own as well. It's really easy and will help you better understand this concept.
Interestingly enough, the computer doesn't offer single bit storage. It always provides data access in larger chunks. So, let's talk about bytes, words, double words and quad words.
There are 8 bits in a byte. They can hold whole numbers between 0 and 255. Bytes are the smallest unit of storage available to you in x86 Assembly.
There are 16 bits in a word. They can hold whole numbers between 0 and 65,535.
There are 32 bits in a double word. They can hold whole numbers between 0 and 4,294,967,295.
There are 64 bits in a quad word. They can hold whole numbers between 0 and 18,446,744,073,709,551,615. Holy crap, that's a big number!
What About Decimals?
The computer isn't limited to dealing with whole numbers. There are several techniques for storing fractions and decimals. For sake of clarity, we won't be digging into that concept now. But, I will cover it in detail in an upcoming tutorial. For now, let's stick with whole numbers.
Like I've said before, code is nothing but a collection of functions that do stuff. Invariably, the stuff that code does has to do with manipulating data. In x86 Assembly, there are two kinds of data: registers and memory. Registers are variables hard-wired into the CPU of your computer. Nearly every operation you have the computer perform involves modifying registers.
On modern x86 machines, there are seven general purpose registers: EAX, EBX, ECX, EDX, ESI, EDI and EBP. These registers are where the bulk of your coding will take place. I know the names of these registers seem odd, but stick with them and they'll make sense.
Each one of these registers is 32 bits wide. Sometimes you want to deal with numbers smaller than 32 bits. That's okay, because each of these general purpose registers can be accessed in multiple ways.
Take EAX for example. If I want to access the low 16 bits of EAX, I can use the register AX to do so. Similarly, if I want to access the low 8 bits of AX, I can use the register AL to do so. Similarly, there's a special register AH for accessing the high 8 bits of AX. Consider this figure for some clarity:
This same breakdown applies to all of the general purpose registers. EBX has BX, BH and BL. ECX has CX, CH and CL. EDX has DX, DH and DL. While EAX, EBX, ECX and EDX have both word-sized aliases and byte-sized aliases, ESI, EDI, and EBP do not. They only have the word-sized aliases (i.e. SI, DI, and BP).
There are also six segment registers: CS, DS, ES, FS, GS and SS. Segment registers are generally reserved for very low-level coding, so we'll ignore them for now.
Stack Pointer Register
There's one very special register, ESP, that's used solely for storing the current stack pointer. While you can store anything you want in this register, that's generally a bad idea. We'll talk about this register in great detail in the stack section below.
Instruction Pointer Register
There's another special register that's used by the computer to track what instruction is being executed in your program. This register is called EIP and it contains the address of the next instruction that will be executed in your program. You can't really access this register directly, but it's there tracking your program's execution.
Certain operations, like comparisons, generate a logical result. Those results (among other things) are stored in the EFLAGS register. EFLAGS is 32-bits wide and contains several true/false values you can query in your code. You generally don't modify this register directly, but understanding what's contained in it can be helpful. If you're interested, click here for more details.
The second form of data in x86 Assembly is memory. Understanding the basics of memory is a critical skill for budding coders to master.
The first question you should ask is: "What is memory?" Memory is, for purposes of coding, a collection of bytes that contains data. While registers provide a small working set for manipulating data, memory opens up a much larger area for doing your computations and storing program state.
We touched on this concept a bit in the first tutorial. Do you recall the data section we defined there? That section is just a collection of bytes containing "Hello World!" followed by a zero. It's a collection of 13 bytes.
In simple cases, like the static data section for your program, memory is allocated automatically for you. In more complex cases, you'll need to allocate your own memory. The operating system (Windows in this case) provides functions you can use to allocate chunks of memory. You can then use that memory to store whatever you like.
Remember that you need to free your memory when you're done with it! Windows provides functions to return memory back to the operating system so that other programs can use it. I'll show you an example of this process in a future tutorial.
Every byte of memory in your program has a unique address. This address is expressed as a 32 bit number that can be used to find the byte. When I say pointer, what I mean is a 32-bit number that can be used to find a particular byte in memory. That's all a pointer is... a unique number that "points" at a byte in memory.
From your program's point of view, memory is allocated in contiguous blocks of bytes. For example, when you request a block of 1,000 bytes to be allocated you will receive a unique address to the first byte of that block. The last byte in that block can be addressed by adding 999 to the unique address returned. Why not add 1000 to get to that last byte? Because the unique address returned to you points at the first byte. Adding 1000 to that address will give you the first byte past your allocated block.
One thing to always remember is to never access invalid pointers. An invalid pointer is one that points to a byte of memory that you don't own. If you do, your program will likely crash.
Pointer arithmetic is just basic arithmetic. Since pointers are just numbers you can add to them and subtract from them. Learning to manage pointers into blocks of memory is a fundamental skill that many programmers never master... to their detriment! Resolve to yourself that you will take the time to master this most critical of skills.
There's a special area of memory that's allocated for you called the stack. This memory is used in two main ways:
- Storing temporary variables for your functions.
- Passing parameters to your functions.
Why is this area of memory called a stack? Because, just like a stack of blocks, you "push" things onto the top of the stack. And, just like a stack of blocks, it's not safe to remove things from the bottom. You "pop" things off the top of the stack. Push to the top and pop from the top. In algorithm speak, this is a last in first out structure (LIFO). That means the last thing you push on to the stack will be the first thing you pop off.
The funny thing about the stack in x86 Assembly is that it grows downwards. By that, I mean that when you push a value onto the stack, the stack pointer is decreased by the size of what you pushed. Similarly, when you pop a value off of the stack, the stack pointer is increased by the size of what you popped.
Understanding what's on the stack and how it works is important when you're writing Assembly code. Pay close attention when we go over the push & pop instructions below!
There are several new instructions you should know about before we dig into the example code for this tutorial.
When you want to copy a values in your program, use the move instruction. This instruction can be used to:
- Copy a register to a register (i.e. mov eax, ebx)
- Copy a register to a memory address (i.e. mov [eax], ebx)
- Copy bytes at a memory address to a register (i.e. mov ebx, [eax])
- Copy a constant to a register (i.e. mov eax, 0)
- Copy a constant to a memory address (i.e. mov [eax], 0)
The destination of the move is the first register/address. The source of the move is the second register/address. So, "mov eax, ebx" means to set the value of eax to the value of ebx. The ebx register remains unchanged by that operation.
You cannot copy values at a memory address to a memory address directly with mov. You need to copy them into a register first. That is, "mov [eax], [ebx]" is not allowed. You would need to "mov ecx, [ebx]" then move "[eax], ecx." Confusing, I know, but it's a limitation of the instruction set.
Let's take a moment to understand the use of brackets in the above examples. When I write "mov [eax], ebx", what I'm telling the compiler is to generate code that copies the 32 bit value stored in ebx to the memory address stored in eax. The eax register is not modified by this operation, but the bytes pointed to by eax are. The brackets mean interpret this value as a pointer to memory and not a numeric value.
When you want to push the value of a register or bytes at a memory address onto the stack, use the push instruction. This instruction can be used to:
- Push the value of a register onto the top of the stack (i.e. push eax)
- Push bytes stored in memory onto the top of the stack (i.e. push dword [eax])
- Push the value of a constant onto the top of the stack (i.e. push 1)
Push needs to know the size of the thing being pushed so it can adjust the stack pointer appropriately. When pushing registers, the size is already known. "push eax" pushes the 32 bit value stored in eax onto the stack. "push ax" pushes the 16 bit value store in ax onto the stack.
When pushing values in memory the compiler needs more information because the size of the value you're pushing is unknown. So, you need to let the compiler know the size. Thus, to push a 32 bit value pointed to by eax you would "push dword [eax]." The "dword" stands for "double word."
One caveat... you cannot push single bytes onto the stack using push. The minimum size that can be pushed onto the stack is 16 bits (word).
When you want to pop a value off the top of the stack and stores it in a register or memory location, use the pop instruction.
Push and pop are really similar, so the same information above applies here. Just remember that pop undoes the action of a push.
CMP <register/address>, <register/address/constant>
When you want to compare two values in your program, use this instruction. This instruction can be used to:
- Compare a register to a register (i.e. cmp eax, ebx)
- Compare a register to a value stored in memory (i.e. cmp eax, [ebx])
- Comapre a register to a constant (i.e. cmp eax, 0)
- Compare a value stored in memory to a constant (i.e. cmp [eax], 0)
This instruction cannot be used to compare two values stored in memory directly. One of the values must be copied into a register first. So, "cmp [eax], [ebx]" is not valid. You'd need to "mov ecx, [eax]" and then "cmp ecx, [ebx]."
The results of this comparison can be one (or more) of the following:
- Not equal
These results are stored in the EFLAGS register and can be acted on by the instructions: JE, JNE, JG, JGE, JL, JLE.
When you want to jump to another instruction in your program based on the result of the last comparison executed in your program. These instructions can be used to:
- Set the instruction pointer (EIP) to the value stored in a register (i.e. jne eax)
- Set the instruction pointer (EIP) to a label in your program (i.e. jne main)
The version of this instruction you use depends on the kind of result you're checking for:
- JE means "jump if equal"
- JNE means "jump if not equal"
- JG means "jump if greater than"
- JGE means "jump if greater than or equal to"
- JL means "jump if less than"
- JLE means "jump if less than or equal to"
- JMP means "jump no matter what"
When you want to call a function in your program, use the call instruction. This instruction can be used to:
- Call a function whose pointer is stored in a register (i.e. call eax)
- Call a function whose pointer is stored in a memory location (i.e. call [printf])
Notice that you are always using a pointer when you use this instruction. This is because functions are stored in memory just like everything else in your program. When you "call" a function, all you are doing is telling the computer to jump to another instruction pointed to by your register or address.
Call actually does one more thing. It pushes the current instruction pointer (EIP) onto the stack so that, when the function is done, it can resume executing where the call was made.
In pseudo-code, "call eax" becomes:
- push eip
- jmp eax
When you're done in your function, use the ret instruction. This instruction sets the instruction pointer (EIP) to the 32 bit value stored at the top of the stack.
In pseudo-code, "ret" becomes:
- pop eip
When you want to add or subtract two values in your program, use these instructions. These instructions can:
- Add or Subtract a constant to a register (i.e. add eax, 1)
- Add or Subtract a constant to a value stored in memory (i.e. sub [eax], 1)
- Add or Subtract a register to a register (i.e. add eax, ebx)
- Add or Subtract a register to a value stored in memory (i.e. sub [eax], ebx)
- Add or Subtract a value stored in memory to a register (i.e. add eax, [ebx])
As usual, the thing being modified by these instructions is the first parameter.
Example by Code
Whew, we've covered a lot here. I think it's time to tie all of these concepts together with a nice example program. I'll be building on the Hello World! program from the first tutorial. Here's what our new program will do:
- Print "Hello World!"
- Reverse "Hello World!" such that it becomes "!dlroW olleH".
- Print the reversed string.
The algorithm for reversing the string is straightforward:
- Get the length of the string.
- Make a pointer to the first and last byte of the string.
- Swap the first and last bytes in the string.
- Add 1 to the first byte pointer.
- Subtract 1 from the last byte pointer.
- If last byte pointer is less than first byte pointer then done.
- Goto 3.
Source Code & Blow by Blow
Let's break down this program like we did before. Since it's getting longer, I'll do it in sections. The sections of the program that are the same as the first tutorial won't be covered. Go read that tutorial if you need a refresher.
Data Section Changes
You'll notice that I changed the data section to "writable" on line 6 as well as adding a new string called "NewLine." The NewLine string will allow us to add a line break between our two strings when we display the results.
I changed the data section to writable so that our reverse function can change HelloWorld without causing a crash.
Changes to Main
I added a new call to print "NewLine" on line 93. I also added a call to our ReverseString function on line 97. Finally, we display the results by calling printf again to show our reversed string on line 100.
Note that I push the pointer to "HelloWorld" on line 96 so that the ReverseString function can access it.
New Function: ReverseString
I've added a new function called ReverseString that, of course, reverses a string based on the algorithm outlined above. Let's break this function down bit by bit:
The first thing we do in any function is to save any registers that we plan on modifying. We do this by pushing each one of them onto the stack.
Line 19 shows "mov ebp,esp." We do this to save the stack pointer before we push our general purpose registers. We'll be using ebp as the base pointer for accessing the parameter passed to us.
At line 19, ebp was set to the value of esp. So, ebp points to esp+16. To access our string pointer, we need to add 8 to ebp. This is why we save the stack pointer at the beginning of our program. So that we can continue to push values onto the stack without getting confused as to where our parameters are.
Lines 37 - 46 count the number of bytes in our string. Notice how we just add 1 to esi at line 43 to advance to the next byte in the string. This is a prime example of pointer arithmetic.
Once we have a pointer to the zero byte in our string, we compute the actual length. We do this by a simple subtraction at line 51. We use ecx as a temporary for esi because we'll want to use esi again in a moment.
Once we have the length stored in ecx, we see if it's equal to zero. If it is we jump to the end of the function.
Otherwise we adjust esi so that it points to the byte just before the zero byte. If we didn't do that then we'd swap the zero byte to the front of the string and would see nothing when we printed it out!
Lines 64 to 67 do the actual swap. Line 70 adds one to edi, which points at the first byte in the string. Line 73 subtracts one from esi, which points at the last byte in the string.
Lines 76-77 checks to see if we're done swapping. This occurs when esi < edi.
Here's the output of this program in action:
Holy crap, we've covered a lot of ground here. If you've followed along, you should know:
- The difference between a bit, byte, word and dword.
- The basics about x86 registers.
- The basics about memory.
- What a pointer is.
- What the stack is and how to manipulate it.
- Several new instructions: mov, push, pop, call, ret, cmp, jmp, jne, jl, etc.
- How to reverse a string in Assembly!
That's enough for today. Spend some time monkeying with the program I've provided. Again, you can get a copy of it here. Take the time to understand it and you'll be well on your way to making more complex programs!
If you don't understand something or need clarity, don't hesitate to ask me in the comments!