{"id":1597,"date":"2021-11-03T16:45:41","date_gmt":"2021-11-03T16:45:41","guid":{"rendered":"https:\/\/cas.cybercop-training.ch\/?page_id=1597"},"modified":"2021-11-03T20:47:18","modified_gmt":"2021-11-03T20:47:18","slug":"a11-assembly-exercise","status":"publish","type":"page","link":"https:\/\/cas.cybercop-training.ch\/index.php\/a11-assembly-exercise\/","title":{"rendered":"A11: Assembly Exercise"},"content":{"rendered":"

Assignment Series #A11 – Journeyman’s Piece<\/h1>\n

Part 2 – Calculate Factorial in Assembly (Using the AT&T Syntax)<\/h2>\n

Write a program which calculates the factorial up to a command line argument given<\/p><\/blockquote>\n

I start by creating a file called main.s<\/code><\/p>\n

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

content of main.s:<\/h3>\n
.globl _start\r\n.section .text\r\n_start:\r\n  mov $1, %rax\r\n  mov $0, %rbx\r\n  int $0x80<\/pre>\n
The rax<\/code> and rbx<\/code> are both general-purpose registers.[1]
\nThe int<\/code> instruction is an interruption. When we use the 0x80 code<\/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]
\nThe code of the system call is stored in the rax register<\/code>. 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.
\nThe $<\/code> is used to indicate constant values. If we omit it, it would be interpreted as a memory address instead.<\/p>\n
The same code in C would look like this:<\/p>\n
int main()\r\n{\r\n  return 0;\r\n}<\/pre>\n
The stack is a contiguous region of memory reserved for the program by the operating system. [3]<\/p>\n
\"\"<\/p>\n
There’s a special register called rsp<\/code> (stack pointer) that points to the top of the stack. It’s possible to store things in the stack by using the mov<\/code> instruction.<\/p>\n
If we want to store two values in the stack, 1 and 2 it could be accomplished that way:<\/p>\n
sub $16, %rsp\r\nmov $1, %rax\r\nmov $2, %rbx\r\nmov %rax, 16(%rsp)\r\nmov %rbx, 8(%rsp)<\/pre>\n
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]
\nIn the above example, we are using 8 bytes<\/code> of the stack to store the value 1<\/code> and equally 8 bytes<\/code> to store the value 2<\/code>, 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)<\/p>\n
push<\/code> subtracts the stack pointer by 8 and stores the parameter into the current address pointed by the stack pointer. pop<\/code> moves the data stored in the address currently pointed by the stack pointer to a register and adds the stack pointer by 8.<\/p>\n
Recursive factorial function<\/h3>\n
Next I’ll create a file called factorial.s<\/code><\/p>\n
.globl factorial\r\n.type factorial,@function\r\nfactorial:<\/pre>\n
Calling<\/code> a function is simply jumping to the memory address where this function is defined.<\/p>\n
Adding call function to main.s<\/code>:<\/p>\n
.globl _start\r\n.section .text\r\n_start:\r\n  push $5\r\n  call factorial\r\n  add $8, %rsp\r\n  mov %rax, %rbx\r\n  mov $1, %rax\r\n  int $0x80<\/pre>\n
In this case, 5<\/code> will be first the argument for the factorial function: The number we want to calculate the factorial.
\nAfter that, we use the call instruction<\/code>. 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.<\/p>\n
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<\/code>)<\/p>\n
The C Code for this would look like this:<\/p>\n
int factorial(int);\r\nint main()\r\n{\r\n  return factorial(5);\r\n}<\/pre>\n
Implementing Recursing function to factorial.s<\/code><\/p>\n
.globl factorial\r\n.type factorial,@function\r\nfactorial:\r\n  push %rbp\r\n  mov %rsp, %rbp\r\n  mov 16(%rbp), %rbx # Get the first parameter\r\n  # Check recursion base\r\n  cmp $1, %rbx\r\n  je factorial_base\r\nfactorial_base:\r\n  # Return value 1\r\n  mov $1, %rax\r\nfactorial_end:\r\n  # Restore pointer\r\n  mov %rbp, %rsp\r\n  pop %rbp # Restore context\r\n  ret # Return<\/pre>\n
First, we compare the parameter value to one (through the cmp instruction<\/code>). Then, we check if the parameter value is equal to one<\/code>. If so, we jump to the factorial_base<\/code> label. This conditional jump is accomplished by the je instruction<\/code> (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.<\/p>\n
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<\/code>.<\/p>\n
The factorial_end<\/code> label will restore the stack pointer to where it was when the function was called and will then restore the base pointer register.<\/p>\n
Implement the recursive calls to factorial.s<\/code><\/p>\n
.globl factorial\r\n.type factorial,@function\r\nfactorial:\r\n  push %rbp\r\n  mov %rsp, %rbp\r\n  mov 16(%rbp), %rbx # Get the first parameter\r\n  # Check recursion base\r\n  cmp $1, %rbx\r\n  je factorial_base\r\n  # Decrease the value of parameter\r\n  dec %rbx\r\n  # Call factorial recursively\r\n  push %rbx\r\n  call factorial\r\n  add $8, %rsp\r\n  # Multiply the current parameter by the recursive call return value\r\n  mov 16(%rbp), %rbx\r\n  imul %rbx, %rax\r\n  # Finish function\r\n  jmp factorial_end\r\nfactorial_base:\r\n  # Return value 1\r\n  mov $1, %rax\r\nfactorial_end:\r\n  # Restore pointer\r\n  mov %rbp, %rsp\r\n  pop %rbp # Restore context\r\n  ret # Return<\/pre>\n
Once the recursive function has been finished, its return value is stored in the rax register<\/code>. Before multiplying the current parameter by the return value of the recursive call, we first need to restore its original value.<\/p>\n
We accomplish it by calling: mov 16(%rbp), %rbx<\/code>. We then multiply<\/code> the value of rbx by rax<\/code> and store the result in rax through the imul instruction. After it, we jump to the end of our function (factorial_end).<\/p>\n
The C code for this would look like this:<\/p>\n
int factorial(int n)\r\n{\r\n  if (n == 1) return 1;\r\n  return n * factorial(n - 1);\r\n}<\/pre>\n
Generating executable code<\/h2>\n
as main.s -o main.o<\/p>\n
as factorial.s -o factorial.o<\/p><\/blockquote>\n
\"\"<\/p>\n
Link the two objects to one executable:<\/h3>\n
ld main.o factorial3.o -o main<\/p><\/blockquote>\n
\"\"<\/p>\n
Execute main and check return value<\/h3>\n
\"\"<\/p>\n
A value of 120<\/code> is returned. That’s the factorial of 5<\/code><\/p>\n
Ressources<\/h2>\n
https:\/\/en.wikipedia.org\/wiki\/Processor_register<\/a> [1]
\nhttps:\/\/en.wikipedia.org\/wiki\/System_call<\/a> [2]
\nhttps:\/\/stackoverflow.com\/questions\/32418750\/stack-and-heap-locations-in-ram<\/a> [3]
\nhttps:\/\/en.wikipedia.org\/wiki\/Stack_(abstract_data_type<\/a>) [4]<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1597","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cas.cybercop-training.ch\/index.php\/wp-json\/wp\/v2\/pages\/1597","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cas.cybercop-training.ch\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cas.cybercop-training.ch\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cas.cybercop-training.ch\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/cas.cybercop-training.ch\/index.php\/wp-json\/wp\/v2\/comments?post=1597"}],"version-history":[{"count":3,"href":"https:\/\/cas.cybercop-training.ch\/index.php\/wp-json\/wp\/v2\/pages\/1597\/revisions"}],"predecessor-version":[{"id":1617,"href":"https:\/\/cas.cybercop-training.ch\/index.php\/wp-json\/wp\/v2\/pages\/1597\/revisions\/1617"}],"wp:attachment":[{"href":"https:\/\/cas.cybercop-training.ch\/index.php\/wp-json\/wp\/v2\/media?parent=1597"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}