• Why Should You Care?
• Lines Of Code vs Instructions
• Assembly Is Not A Language?
• Differences Between Hardware
• Why am I writing This?
• Fibonacci Code
• Naming the concepts
• Something Like A Function
• Passing Data To The Function
• Creating Scope
• The Stack, Another Way Of Saving Data.
• Using The Stack To Save Data And Create Scope
• Returning Data To The Caller
• If Statements In Assembly
• Conditional Logic
• Recursion
• Putting Everything Together
• Final Code
• IO In Assembly
• Final Code With IO
• How To Debug Assembly
• Code

If you only code in high level languages and have no idea what your computer does with your code, this post is for you, no previous knowledge of assembly is required just basic knowledge of any popular language, if you can read and understand the following JavaScript code, you're good to go.

function fib(n) {
  if(n < 3) {
    return n - 1;
  }
  return fib(n - 1) + fib(n - 2);
}

fib(1); // return 0
fib(2); // returns 1
fib(3); // also returns 1 (0 + 1)
fib(4); // returns 2 (1 + 1) and so on... 

We're gonna implement this in assembly breaking down each JavaScript concept and implementing the same concept in assembly.

The main problem that I've had learning assembly is that is boring, and the reason why is boring is because you have to understand a lot to do a little, and the thing that you end up doing is not that interesting, so I decided to write this post that tries a different approach.

Why Should You Care?

If you're a JavaScript developer you not going to use assembly in your daily routine and knowing assembly is not gonna make you a better JavaScript developer in any meaningful way, so why should you care?
Well, Knowing assembly will increase your understanding of computing and make you more interested in it, it'll open doors in other areas that might grab your interest, and the most important part, it'll build your narrative about programming, you need to be able to tell a history with the knowledge that you have, to be interested in it, learning assembly will increase your context appreciation and understanding of the whole field, if you feel like you're repeating yourself learning the same concepts over and over just with different names said by different people, maybe it's time to learn something new to expand your view and reignite your interest in programming, at the end of the day you can't be good at something that you don't enjoy and have no interested in, so allow yourself the opportunity of sparkling your interested once more, if you don't know C you can't fully appretiate javascript, if you don't know assembly you can't fully appretiate C, it's important to know where the things that you use come from to understand why they exist, to build meaning, Knowing how to do something is not the same as understanding it, you need a lot of context to understand something, you need to connect the dots, the more context you have the easier it's for you to understand other things in the same area and the deeper is your understanding, you can explain the "why", why something was built the way it was and "why" it's not a good idea to do it differently, what are the downside of a solution, you level of enjoyment and interest in the field also grows, because your mind have a lot more room to wonder in that particular field, so let's get to it.

Lines Of Code vs Instructions

Your computer can't execute the code that you write, let x = 99 your computer has no idea what the previous line of code means, and what do to with it, this line of code needs to be translated to instruction that your CPU can actually execute, the code that you write is called subject code or source code this code needs to be translated to object code real instructions that your CPU can execute, one line of code in a high level language gets translated to multiple instructions that a CPU can actually execute. computers are super dumb, they do not understand any of these high level concepts, they can only do very simple things like:

• Move values to different places in memory
• Add and subtract numbers
• Jump to different instructions

And that's pretty much it, the hardware on your computer is very limited. don't get me wrong, it's amazing that we have circuitry that can actually do these things, but there's a chasm between the concepts in a high level language and what the hardware can actually do. it's the job of the person designing the language to bridge that chasm and implement these high level concepts like functions, recursion and scope using only these very simple tools and that's what we gonna do in this post, we gonna reverse engineer a solution in a high level language(JavaScript) to a low level language(assembly)

Assembly Is Not A Language?

Assembly is not a language, assembly is a family of languages, just like LISP is also a family of languages, if all the code that you write maps directly to a instruction that a machine can do, this language can be called an assembly language, the name "assembly" comes from the fact that what the machine is executing is not exactly the instruction, the machine can execute multiple instructions at once and these instructions are assembled in to binary, the following table illustrates how that happens

So multiple assembly instructions gets assembled to one 16, 32 or 64 bit chunk of data(0000001000000100) that a computer can execute, for example the jump instruction in assembly might be represented by the last 4 bits in these chunks, the first 3 bits represents the move instructions, and so on... you got the idea, you don't need to understand any of this to write assembly, the assembler is smart enough to do it.

An assembly language is made for a specific CPU, since different CPU can do different things and execute different instructions, the difference between what a CPU can do makes the CPU more suited for different tasks, if you need to do a lot of multiplication, using a CPU that can do multiplication on hardware will be a lot better than one that can only add.

Differences Between Hardware

Depending on your task, difference instruction will be more important, and that dictates what instructions will be implemented on hardware, creating chips that can execute complex instructions is expensive but also make the execution of those instructions much faster, that's why people use GPU's for AI, mining crypto and games, GPU's have expensive instructions implemented on hardware, so things that would take a lot of instructions in a regular CPU can be done with a single GPU instruction, GPU makers release documents with these instructions so assembly creators can create a assembly language that maps to these instructions, or even higher level languages like shader languages for example, the following is a pdf document with the instructions for the AMD R700 family if you're curious https://developer.amd.com/wordpress/media/2012/10/R700-Family_Instruction_Set_Architecture.pdf

Why am I writing This?

Most of the tutorials online focus on teaching assembly bottom up, show the instruction tell what the instruction does, then show another instruction and so on, but I think this way of teaching assembly is much more complicated than it needs to be, assembly is not like other high level languages so knowing what a specific instruction do has no value for a python or Javascript developer, because that instruction doesn't map to anything that you already know, saying that MOV moves numbers to registers has no meaning to a high level language developer, the first thing that he's going to think is, what is a register and why would I move numbers to it? So instead of doing this we're going to implement a function that returns the value of a number in a fibonacci sequence, first we're going to write the code in Javascript, then we're going to translate the code to assembly and conceptually "map" each part to the high level code.

Fibonacci Code

Each number in the Fibonacci sequence is the sum of the previous two values expect for the first two values which are 0 and 1
Let's see the javaScript implementation again.

function fib(n) {
  if(n < 3) {
    return n - 1;
  }
  return fib(n - 1) + fib(n - 2);
}

fib(1); // return 0
fib(2); // returns 1
fib(3); // also returns 1 (0 + 1)
fib(4); // returns 2 (1 + 1) and so on... 

Ok now let's talk about the " high level concepts" used in this implementation, the idea is the following.

• name the concepts
• find similar concepts in assembly
• translate the concepts to assembly

Naming the concepts

The first concept is "functions", function fib().. is a
function in JavaScript, we can think about what properties does a function have, let's number the properties and think about them.

1. A function can be called from anywhere in the code.
2. You can pass data to the function.
3. The function have a scope.
4. The function can return data to the caller code execution resumes right after the function call, after the function returns, now we think about something in assembly that is conceptually similar, something that can emulate what we want to do.

Something Like A Function

There are no functions in assembly, but we have something close to it called procedures, if you think about a function in another way, a function is a jump in the program execution, in our example the first line executed was 7: fib(1) this line prompt a jump in the execution to line 1: function fib(n) { in assembly you can name a specific line and tell the program to jump to that line and keep executing the code.

global _start

_start: call Proc
        ret

Proc: push 99
      ret

Code execution starts at _start which is a procedure, the line at start and all following lines will be executed unless we have something to change the next line to be executed, in this case we call another procedure called Proc there's nothing special about the name, it's just a label that's going to be replaced by the address in memory of the next instruction to be executed.

When we run call Proc code execution will jump to line 7, ok so now we have a way of jumping between different parts of the code, the first property that we want, let's look at what is happening.

Above is the code that we just wrote being executed, the first column is the memory address of that line of code, code execution start at the first address, the address is incremented to the next address, and the code on that address is executed, except when we use call, call changes the value of the next line to be executed, so code execution jumps to the instruction push 99, the next line is ret which works like return but can not return values, after that, code execution resumes after the call instruction, ok that's one part of the puzzle now we have a way of changing the execution flow, case 1 is complete.

Passing Data To The Function

Now that we have something that we can call like a function, how do we pass data to it? most of what a higher level language do is managing memory, the biggest benefit of using lanuguages like javascript and python is that you don't need to manage memory yourself, most runtime errors are caused by bad memory allocation, either by the language, OS or the developer in most computers and OSs you have at least 3 ways of saving temporary data that is being used in a process, you have registers, the stack and the heap, registers are the easiest one to understand and use in assembly, an register is a integrated circuit that can save bits, it's hardware, and you have a limited number of those in your computers, a lot of register are used for other tasks by the CPU, so it's not safe to use them, that's why you hear people talking about general purpose registers these are the registers that're safe to be used by your running program, the following image is a list of almost all the registers in an modern computer.

Since a register is hardware, registers are global, even between different programs, if you change the value of a register in one part of your program and then call another library or procedure that reads or change this registers you gonna affect your program or the library that you're using, so it's always a good idea to keep the number of registers that you use to a minimum, just like we do with global variables, The road to programming hell is paved with global variables.

How can we save something in a register?

That's when the MOV instruction comes in, you can move a value to a register MOV RAX, 1 here we're moving the value 1 to the RAX register, and we can do that to save a value and then read it in another part of the program, which is similar to passing data to a function, we can do something like this.

global _start

_start: mov rax, 1
        call Procedure
        ret

Procedure: 
        add rax, 1 ; now the value on rax will be 2 
        ret

In the snippet above we save the value on rax, call the procedure, then read the value from that variable and do something with it, simulating passing values to a function, so 2 is also done.

Creating Scope

Another useful function property is scopes, variables created in a function only exist on that scope and if you recursively call that function passing new values, updating these values won't affect other scopes, this is a key property of functions and is the main reason why they're so useful.

function fib(x) {
  ....
  fib(2);
  ....
}

fib(1);

So can we do something like this in assembly? How can we simulate scope?

As you might have guessed we don't have the concept of a scope in modern CPUs, so we have to simulate one, if you're paying attention the first thing that you would think about would be to use the registers to save and load different scopes depending on what you're executing at that moment, the problem is that we have a very limited number of registers so if we do that we're going to run out of registers to save values pretty fast, they're global as well so abusing registers is not a good idea, OK, so the other general options to save things are the stack and the heap, let's talk about the stack.

The Stack, Another Way Of Saving Data.

Another way of saving data is the stack, the beautiful thing about the stack is it's simplicity,when you run your program the OS reserves some memory for the program to run and sets the address of the beginning of that memory to a register rsp, when you push a value to the stack, it saves this value to the current memory address saved on rsp and increases the memory address to the next one in the stack and saves it on rsp again, when you pop a value, it saves the value on whatever register you tell it to and decreases the rsp memory address number again.

We could do all of that ourselves but x86_64 comes with two instructions that already do all of that for us, push and pop, let's see that happening step by step.

This is the code that we gonna run

global _start

_start: push 99 
        push 99
        pop rax
        pop rbx
        ret

We can push a value to the stack using push, push 99 will push the value 99 to the stack, 99 is 63 in hexadecimal

And this is the stack before running anything

The first column is the memory addresses and each line is the value in memory, when we run push 99 the stack changes

Now we can see our 99 or 63 in hexadecimal there, if we run the next instruct push 99 again, 63 is added to the stack

As you can see we add to the stack in chunks of 64 bits, because my computer is 64 bits if you're using a 32 bit computer you would see a word half the size as the one we're seeing here, you can read more about what word means here here, but basically a word is the size of the data that makes sense to work on a given the computer architecture, you can work with 32 bit registers in a 64 bit computer, but that's going to make your life harder in most cases, let's keep executing our code to see what happens when we pop a value from the stack, pop rax remove the value from the stack and save that value on a register, rax in this case, that's one of the reasons why the default size of the word matters because if we tried to save a 64 bit value in a 32 bit register bad things would happen as you can imagine, rax is a 64 bit register so we can safely do that, let's see what happens to the stack after we pop that value.

Now we only have one 63 again and the value of the registers that points to the top of the stack(RSP) was decreased, if we ran the next pop we gonna remove the next value from the stack and the stack will be in the same state as it was before we started the program, RSP will point to the beginning of the stack. the OS allocates memory for the program and decides which address the stacks starts on.

Using The Stack To Save Data And Create Scope

Now that we know how the stack works, we can use the stack to save and retrieve all register values before calling another procedure, by doing that we can create scope between the different procedure calls, let's see the easiest possible example of that in practice.

_start: mov rax, 1 ; the value that we pass to Procedure
        call Procedure
        ret

Procedure: 
        push rax ; saves rax on the stack
        call ChangeParam ;call a procedure that changes rax
        pop rax ;restore rax original value from the stack 
        ret

ChangeParam:
        add rax, 1; now the value on rax is 2
        ret

Saving the values that we're working on in the stack and restoring them creates scope in the procedure, we could have done the same thing on ChangeParam that's usually the way that we do when we call external libraries, we need to restore the values before calling them, great, now we have a way of creating scope, 3 is done.

Returning Data To The Caller

Well this one is pretty easy, since everything is global in assembly, the caller just needs to read the value in the right place after the call, so if inside the procedure we save the result of the procedure in the RBX register we just need to read the value from that register after the procedure

_start: call Procedure
        mov rax, rbx ; now rbx has the result of proc
        ret

Procedure: 
        mov rbx, 99 
        ret

And with that we're done, now let's analyze the next line of javascript code and do the same thing that we done for the function.

If Statements In Assembly

if(n < 3) {

This is the next executed JavaScript, as you might imagined by now, Assembly x86 doesn't have if statements either, The main function that we want to simulate is Compare two values and based on the result of the comparison jump to different places

Conditional Logic

This one is pretty straight forward, we have CMP in assembly the way that it works is pretty simple, we compare two values, then we use a conditional jump to jump in specific cases, for example we could compare the value on RAX with 1 then do a conditional jump if they're equal.

_start:
  cmp rax,1
  je Proc

Proc:
  push 99

That's pretty much it, not much to talk about here, we have conditional jumps for each comparison greater than(JG), less than(JL), equal(JE) and for some other special cases.

Recursion

The next line is return n -1 we already implemented the return logic, we just need to save the value in the register and use ret to return from a procedure, and for n - 1 we just need to use decrement dec on the register holding the value of n, the last line of javascript is return fib(n - 1) + fib(n - 2); and we also implemented everything that that is to know about this one, the main thing about this line is the fact that is recursive, and we already implemented the idea of a function with scope, so we only need to call the procedure save the data on the stack and the rest that we did to simulate a function call, Now we can put everything together and implement the solution.

Putting Everything Together

Let's go line by line

Function definition

function fib(n) {

Procedure definition

Fib:

If statement

if(n < 3) {

Compare and jump
rax holds the parameter passed to the function

cmp rax,3 
jl L3 ; jump to L3 if rax is less than 3

Inside the if block

return n - 1;

We jump to another part of the code, decrement the register and save the value to another register before returning, since this is the last case we don't need to push rax to the stack again, jumps works in a different way than procedure calls. when you call a procedure ret gonna return you in the line that you called that procedure, when you jump it can look like a procedure but it isn't, the code belongs to the procedure where you used the jump so ret is going to return from that procedure, it works just like a if statement in this case.

L3:
     dec rax
     mov rbx, rax
     ret

return fib(n - 1) + fib(n - 2);

This one is complicated

push rax ; saves the value of rax, rax is n in this context
dec rax  ; decrements rax 
call Fib ; call procedure now with the modified rax value
pop rax  ; pops the original value of rax from the stack
push rbx ; push the result from the previous Fib call 
dec rax  ; decrements rax two times ` n - 2`
dec rax
call Fib ; calls procedure now with the modified rax value
pop rcx  ; pop the result from the *first* Fib call
add rbx, rcx ; add the result from the first Fib call with the second one
ret

As you can see simulating scope is the trickiest part but it's not that hard if you take some time to think about it, we're just using the stack to save stuff that we want to use later and not change the things that we're working right now, the stack is used a lot in this manner, "you don't want to use right now but needs this value later? put it on the stack"

Final Code

global _start
_start:
    mov rax,5
    call Fib 

    ; Some boilerplate code to return control to the OS
    mov eax,1       ; Code for Exit Syscall
    mov ebx,0       ; Return a code of zero 
    int 80H             ; Make kernel call
    ret

Fib:
    cmp rax,3
    jl L3 
    push rax
    dec rax
    call Fib
    pop rax
    push rbx
    dec rax  
    dec rax
    call Fib
    pop rcx
    add rbx, rcx
    ret

L3:  
    dec rax
    mov rbx, rax
    ret

in the case above 5 is the parameter that the fib function receives so the returned value should be 3, 3 is the fifth element in the fibonacci sequence.
if we ran our code and inspects the value of rbx at the end of the execution we get 3

IO In Assembly

One thing that is clearly missing is the ability to pass arguments to our program and to print out the results, I didn't touch on this before because is not really assembly, but we can do that to make our program more useful, the way that something like print("hello world") works is by calling a function of the Kernel that knows how to print things on the screen, we also need to read the arguments passed to the function, transform the numbers in to characters and the characters in to numbers by offsetting the values in the ascii table , I'm not gonna explain this here because the post is already pretty big, the following is the code with IO, you can pass the index in the fibonacci that you want, and the code returns the value in the sequence.

Final Code With IO

%macro  ExitProg 0
    mov eax,1       ; Code for Exit Syscall
    mov ebx,0       ; Return a code of zero 
    int 80H         ; Make kernel call
%endmacro

section .data
    newline db 10,0

section .bss
    printSpace resb 8
    digitSpace resb 100
    digitSpacePos resb 8

section .text

global _start
_start:
    mov rdi, qword [rsp + 16] ; Get the third item in the stack, which is the first argument passed to the program
    movzx rax, byte [rdi]   ; Get the first character 
    sub rax, 48             ; Convert from ASCII to decimal
    call Fib                ; after call Fib `rbx` has the result
    mov rax, rbx            ; moves the result to rax
    call printRAX           ; call procedure to print the result
    mov rax, newline        ; move new line to rax
    call print              ; prints the new line
    ExitProg

Fib:
    cmp rax,3
    jl L3 
    push rax
    dec rax
    call Fib
    pop rax
    push rbx
    dec rax  
    dec rax
    call Fib
    pop rcx
    add rbx, rcx
    ret

L3:  
    dec rax
    mov rbx, rax
    ret

print:
    mov [printSpace], rax
    call printLoop
    ret

printLoop:
    mov cl, [rax]
    cmp cl, 0
    je endPrintLoop
    inc rbx
    inc rax
    jmp printLoop

endPrintLoop:
    mov rax, 1 
    mov rdi, 0 
    mov rsi, [printSpace]
    mov rdx, rbx
    syscall
    ret

printRAX:
    mov rcx, digitSpace
    mov [digitSpacePos], rcx

printRAXLoop:
    mov rdx, 0
    mov rbx, 10
    div rbx
    push rax
    add rdx, 48

    mov rcx, [digitSpacePos]
    mov [rcx], dl
    inc rcx
    mov [digitSpacePos], rcx

    pop rax
    cmp rax, 0
    jne printRAXLoop

printRAXLoop2:
    mov rcx, [digitSpacePos]

    mov rax, 1
    mov rdi, 1
    mov rsi, rcx
    mov rdx, 1
    syscall

    mov rcx, [digitSpacePos]
    dec rcx
    mov [digitSpacePos], rcx

    cmp rcx, digitSpace
    jge printRAXLoop2
    ret

How To Debug Assembly

You can use gdb to debug Assembly but you need to configure it properly, this is the configuration that I use, besides that , to start debugging run

gdb fibonacci

if you needs to pass parameters to the program

gdb --args fibonacci 5

after that you can break on the _start procedure

b _start

run the program

run

Then you can use nexti to go to the next instruction and stepi to step inside a procedure.

i r <register_name> shows the value of a register e.g i r rax

We can print address values of registers and symbols with x/x $rsp to print in hexadecimal and x/d to print as a decimal value.

Code

All code is available here