Assignment Series #A11 – Journeyman’s Piece

Part 2 – Calculate Factorial in Assembly (Using the AT&T Syntax)

Write a program which calculates the factorial up to a command line argument given

I start by creating a file called main.s

Every assembly program is composed of three sections: data, bss, and text.
The data section is used to initialize constants. Those constants are preallocated during the program’s initialization.
The bss section is used to declare buffers or dynamically allocated data. Finally, the text section is used to keep the actual code.

content of main.s:

.globl _start
.section .text
_start:
  mov $1, %rax
  mov $0, %rbx
  int $0x80

The rax and rbx are both general-purpose registers.[1]
The int instruction is an interruption. When we use the 0x80 code, we are saying that this interruption must be handled by the Linux operating system. In another words, we are performing a system call.[2]
The code of the system call is stored in the rax register. The 1 is the code for the exit system call. The exit system call takes one parameter, the return value, which is stored in the rbx register. In this case, we are returning the value 0.
The $ is used to indicate constant values. If we omit it, it would be interpreted as a memory address instead.

The same code in C would look like this:

int main()
{
  return 0;
}

The stack is a contiguous region of memory reserved for the program by the operating system. [3]

There’s a special register called rsp (stack pointer) that points to the top of the stack. It’s possible to store things in the stack by using the mov instruction.

If we want to store two values in the stack, 1 and 2 it could be accomplished that way:

sub $16, %rsp
mov $1, %rax
mov $2, %rbx
mov %rax, 16(%rsp)
mov %rbx, 8(%rsp)

A stack is a structure that grows upward, in the sense that it first begins with addresses of higher values and grows towards addresses of lower values. [4]
In the above example, we are using 8 bytes of the stack to store the value 1 and equally 8 bytes to store the value 2, so we need to step down the stack pointer by a value of 16 (we use 8 bytes because on x64 architecture, the registers have 8 bytes. 8 x 8 = 64 bits)

push subtracts the stack pointer by 8 and stores the parameter into the current address pointed by the stack pointer. pop moves the data stored in the address currently pointed by the stack pointer to a register and adds the stack pointer by 8.

Recursive factorial function

Next I’ll create a file called factorial.s

.globl factorial
.type factorial,@function
factorial:

Calling a function is simply jumping to the memory address where this function is defined.

Adding call function to main.s:

.globl _start
.section .text
_start:
  push $5
  call factorial
  add $8, %rsp
  mov %rax, %rbx
  mov $1, %rax
  int $0x80

In this case, 5 will be first the argument for the factorial function: The number we want to calculate the factorial.
After that, we use the call instruction. What the call instruction actually does is just storing the current address into the stack pointer (because we need to know where to return after the function has been finished!) and jumping to the factorial label.

Finally, we increase the stack pointer (because we no longer need the function parameters stored in the stack, we can safely override them to prevent memory leaks) and move the function return (the function return is, by convention, always stored in the rax register) to the rbx so we can display it after the program has been executed (through the echo $? command)

The C Code for this would look like this:

int factorial(int);
int main()
{
  return factorial(5);
}

Implementing Recursing function to factorial.s

.globl factorial
.type factorial,@function
factorial:
  push %rbp
  mov %rsp, %rbp
  mov 16(%rbp), %rbx # Get the first parameter
  # Check recursion base
  cmp $1, %rbx
  je factorial_base
factorial_base:
  # Return value 1
  mov $1, %rax
factorial_end:
  # Restore pointer
  mov %rbp, %rsp
  pop %rbp # Restore context
  ret # Return

First, we compare the parameter value to one (through the cmp instruction). Then, we check if the parameter value is equal to one. If so, we jump to the factorial_base label. This conditional jump is accomplished by the je instruction (jump on equal). The cmp instruction sets a flag in theflags register, which the conditional jump will look up to decide if it will jump or not.

Once within the factorial_base label, we move the value 1 into the rax register. The rax will store the final value of our calculation. The program flow will then move automatically to the label right below, factorial_end.

The factorial_end label will restore the stack pointer to where it was when the function was called and will then restore the base pointer register.

Implement the recursive calls to factorial.s

.globl factorial
.type factorial,@function
factorial:
  push %rbp
  mov %rsp, %rbp
  mov 16(%rbp), %rbx # Get the first parameter
  # Check recursion base
  cmp $1, %rbx
  je factorial_base
  # Decrease the value of parameter
  dec %rbx
  # Call factorial recursively
  push %rbx
  call factorial
  add $8, %rsp
  # Multiply the current parameter by the recursive call return value
  mov 16(%rbp), %rbx
  imul %rbx, %rax
  # Finish function
  jmp factorial_end
factorial_base:
  # Return value 1
  mov $1, %rax
factorial_end:
  # Restore pointer
  mov %rbp, %rsp
  pop %rbp # Restore context
  ret # Return

Once the recursive function has been finished, its return value is stored in the rax register. Before multiplying the current parameter by the return value of the recursive call, we first need to restore its original value.

We accomplish it by calling: mov 16(%rbp), %rbx. We then multiply the value of rbx by rax and store the result in rax through the imul instruction. After it, we jump to the end of our function (factorial_end).

The C code for this would look like this:

int factorial(int n)
{
  if (n == 1) return 1;
  return n * factorial(n - 1);
}

Generating executable code

as main.s -o main.o

as factorial.s -o factorial.o

Link the two objects to one executable:

ld main.o factorial3.o -o main

Execute main and check return value

A value of 120 is returned. That’s the factorial of 5

Ressources

https://en.wikipedia.org/wiki/Processor_register [1]
https://en.wikipedia.org/wiki/System_call [2]
https://stackoverflow.com/questions/32418750/stack-and-heap-locations-in-ram [3]
https://en.wikipedia.org/wiki/Stack_(abstract_data_type) [4]