So you want to be a coder... (Part 2 - Registers, Memory and The Stack)

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.

Bits

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.

  The Windows calculator in programmer mode.  Use it!

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.

Bytes

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.

Words

There are 16 bits in a word.  They can hold whole numbers between 0 and 65,535.

Double Words

There are 32 bits in a double word.  They can hold whole numbers between 0 and 4,294,967,295.

Quad Words

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.

---

Registers

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.

General 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:

Just keep in mind that AX, AH and AL are all part of EAX.  So, changing AX changes the value of EAX.

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).

Segment Registers

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.

Flags

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.

---

Memory

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.

Allocating Memory

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.

Freeing Memory

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.

Pointers

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.

---

The Stack

There's a special area of memory that's allocated for you called the stack.  This memory is used in two main ways:

1. Storing temporary variables for your functions.
2. 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!

---

New Instructions

There are several new instructions you should know about before we dig into the example code for this tutorial.

MOV <register/address>,<register/address/constant>

When you want to copy a values in your program, use the move instruction.  This instruction can be used to:

1. Copy a register to a register (i.e. mov eax, ebx)
2. Copy a register to a memory address (i.e. mov [eax], ebx)
3. Copy bytes at a memory address to a register (i.e. mov ebx, [eax])
4. Copy a constant to a register (i.e. mov eax, 0)
5. 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. 

PUSH <register/address/constant>

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:

1. Push the value of a register onto the top of the stack (i.e. push eax)
2. Push bytes stored in memory onto the top of the stack (i.e. push dword [eax])
3. 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).

POP <register/address>

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:

1. Compare a register to a register (i.e. cmp eax, ebx)
2. Compare a register to a value stored in memory (i.e. cmp eax, [ebx])
3. Comapre a register to a constant (i.e. cmp eax, 0)
4. 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:

1. Equal
2. Not equal
3. Greater
4. Lesser

These results are stored in the EFLAGS register and can be acted on by the instructions: JE, JNE, JG, JGE, JL, JLE.

JE/JNE/JG/JGE/JL/JLE/JMP <register/label>

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:

1. Set the instruction pointer (EIP) to the value stored in a register (i.e. jne eax)
2. 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:

1. JE means "jump if equal"
2. JNE means "jump if not equal"
3. JG means "jump if greater than"
4. JGE means "jump if greater than or equal to"
5. JL means "jump if less than"
6. JLE means "jump if less than or equal to"
7. JMP means "jump no matter what"

CALL <register/address>

When you want to call a function in your program, use the call instruction.  This instruction can be used to:

1. Call a function whose pointer is stored in a register (i.e. call eax)
2. 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

RET

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

ADD/SUB <register/address>,<constant/register/address>

When you want to add or subtract two values in your program, use these instructions.  These instructions can:

1. Add or Subtract a constant to a register (i.e. add eax, 1)
2. Add or Subtract a constant to a value stored in memory (i.e. sub [eax], 1)
3. Add or Subtract a register to a register (i.e. add eax, ebx)
4. Add or Subtract a register to a value stored in memory (i.e. sub [eax], ebx)
5. 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:

1. Print "Hello World!"
2. Reverse "Hello World!" such that it becomes "!dlroW olleH".
3. Print the reversed string.

 The algorithm for reversing the string is straightforward:

1. Get the length of the string.
2. Make a pointer to the first and last byte of the string.
3. Swap the first and last bytes in the string.
4. Add 1 to the first byte pointer.
5. Subtract 1 from the last byte pointer.
6. If last byte pointer is less than first byte pointer then done.
7. Goto 3.

Source Code & Blow by Blow

Click here to download the source code for this tutorial.

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.

Line 28 stores a pointer to the string pushed onto the stack at line 96.  To understand why we use "[ebp+8]", consider how the stack looks as of line 28:

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!

This is the meat of the function.  In it, we swap the first and last bytes repeatedly until there's nothing left to swap.

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.

The last thing we do in this function is to pop all of the registers that we've pushed and return.  Easy!

Here's the output of this program in action:

Conclusion

Holy crap, we've covered a lot of ground here.  If you've followed along, you should know:

1. The difference between a bit, byte, word and dword.
2. The basics about x86 registers.
3. The basics about memory.
4. What a pointer is.
5. What the stack is and how to manipulate it.
6. Several new instructions: mov, push, pop, call, ret, cmp, jmp, jne, jl, etc.
7. 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!

Comments

[Question]

Very interesting tutorial.
As you can guess, i've got a few questions incoming.

General Registers :
You seem to imply that all named registers, EAX, EBX, ECX, EDX, ESI, EDI and EBP, are essentially the same.
But is that correct ?
A minor difference that can be extrapolated from your tutorial is that registers A, B, C & D can be accessed "partially" (AL,AH, AX). The same does not look possible on EDI, EDI & EBP.
I guess there are probably other subtle differences.
I'm asking because your sample program uses ESI & EDI.

Push instruction :
Is that a single opcode ?
Or is that a macro translated into a few opcodes ?
I'm asking because, last time i learned assembler (quite a long time ago), it was on a CPU for which "push on stack" was a completely hand-made construction. But i guess x86 are more optimised.

call & ccall instructions :
I guess now that call is probably an opcode, while ccall is probably a macro, consisting of a few push followed by a call.
It would be interesting to know a bit more about it, and the difference with stdcall (which was present in previous tutorial).

ret instruction :
if it is equivalent to "pop eip", then that means that previously pushed data is still on the stack, and must be manually cleaned (or used, maybe sometimes the result of the function is there).
Which makes it all the more interesting to understand what ccall & stdcall are doing, especially if some manual cleaning is required afterwards (well, more probably, i guess it is embedded into the macro...)

Regards

[Stephen Nichols]

These are all good questions. Let me answer each one in turn:

You're right to point out that there are differences between the registers. ESI, EDI, ESP and EBP do not have the byte-sized aliases. They do, however, have the word-sized aliases (i.e. SI, DI SP and BP). I've updated the tutorial text to clarify this.

ESI and EDI are generally used as indexers, although there's no requirement that they're used that way. Just habit on my part.

All of the instructions that I laid out in this tutorial are single instructions (single opcode) and not macros.

You're right about ccall (and stdcall for that matter). Those are macros for the two calling conventions provided by Flatasm. I'll be going into more detail on calling conventions soon. The main differences are:

1. ccall supports variable numbers of arguments. This makes it the responsibility of the caller to clean up the stack after making a call.

2. stdcall supports a fixed number of arguments. This makes it the responsibility of the callee to cean up the stack at the end of the function. The ReverseString function in this tutorial is an example of stdcall.

By way of example:

ccall Function,arg1,arg2,... becomes

push arg1
push arg2
...
call Function
add esp, (size of all args pushed)

stdcall Function,arg1,arg2,... becomes

push arg1
push arg2
...
call Function

Whenever you call a function in x86, the EIP of the return address is pushed onto the stack. When you return from a function (using RET), that saved EIP is restored and execution continues. As you pointed out, it's critical that you clean up your stack before exiting the function (depending on your calling convention). If you don't then your code will crash.

This is one of the reasons that buffer overruns on the stack can be so troublesome to debug. Imagine a buffer overrun that stomps on the return address for your function. When your function returns in that case, it returns to a bogus pointer. Nasty.

[Mark Williams]

Firstly can I say, Please keep this tutorial going. It's just what I have been searching for. It is GREAT!. I have a feeling I am missing the first prerequisite for programming but hopefully I can muddle through with the others. I am trying to come to terms with the Stack and associated instructions, in particular the "push ebp" before the "mov ebp,esp". Why is [ebp+8] used instead of [esp+24]?. Thanks again writing this Tutorial.

[Stephen Nichols]

Oh, I'll keep it going. Been really busy the past two weeks.

Generally speaking, ebp is called the "base pointer." And for good reason. We use it as the pointer to the base of the stack frame in our functions.

We do this because each time you push a value onto the stack esp is modified (decreased by the size of the thing you're pushing). Using esp to find other values on the stack makes things really annoying. The only real exception to this is when you're doing things relative to the current stack pointer on purpose.

I hope that helps!

[ClarkTeegan]

Which methons do you personally use to look for info for your future posts and which search websites or techniques do you mostly use?

[Albert1]

I read you didn't go to college... well, you're better than many professors at explaining this stuff!

[Stephen Nichols]

Thanks!

Yeah, I'm a high school dropout actually. It really makes telling my kids to stick with school difficult. We homeschool though so it's not too hard to stick with it. :)