Chapter 4
Know the Concepts
1) What are primitives?
Primitives are the basics which everything else is built off of. These are operations provided by the system as you simply would not be able to write certain functions without primitives.
2) What are calling conventions?
Calling conventions describe how functions expect to get and receive data when they are called. There is no specific calling convention that must be used but in order to interoperate with functions written in other languages you must obey their calling conventions. In this chapter we use the C language calling convention as it is most widely used and the standard for linux platforms.
3) What is the stack?
Each computer program that runs uses a region of memory called the stack that simply enables functions to work properly. A stack can be hard to picture at first but it helps to think of it as a pile of papers. You typically have the paper your working on at the top and future papers under it. When you are done working on the top paper you take it off, or if you need to work on something else immediately you can place it on the top of the stack. This is how a computer stack works as well, u can push and pop values on and off the stack. The computer’s stack actually lives at the very top addresses of memory but what makes it a bit more confusing is that the “top” of the stack is actually at the bottom of the stack’s memory. This is because memory grows downward as we are starting at the top due to architectural considerations.
4) How do pushl and popl affect the stack? What special-purpose register do they affect?
pushl – pushing a value onto the top of the stack using this instruction will push either a register or memory value onto the top of the stack. A pushl instruction the stack will grow, therefore our %esp register (which always points to the top of the stack) must change. A pushl instruction %esp will get subtracted by 4 so that it points to the new top of the stack since it grows downward.
popl – you can pop values off of the top of a stack using this instruction. This will remove the top value from the stack and place it into a register or memory location of choice. Similarly to pushl, popl will add 4 to %esp to set it to move the register to the top of the stack once again.
5) What are local variables and what are they used for?
Local variables are used as data storage for a function while it is processing that is then thrown away once the function returns. Similar to other programming languages it is simply a variable that is only used in that specific function. If the function is called twice the local variable is different for each call of the function. Local variables are not accessible to any other function within a program.
6) Why are local variables so necessary in recursive functions?
As stated above the local variable is for a specific call of a function. In recursion you call a function multiple times before returning a value. Each of these calls require the same variable but with different values set for those variables and this would not be reasonable to do with anything other than local variables.
7) What are %ebp and %esp used for?
%ebp (base pointer register) is a special register used for accessing function parameters and local variables.
%esp (stack pointer register) is initially used for mov %esp, %ebp which allows us to use %esp for other tasks such as calling another function. Basically this situation allows us to use %esp freely while giving us a way to access local variables and parameters for the current function.
8) What is a stack frame?
The stack frame is the collection of all of the stack variables used within a function, this includes the parameters, local variables, and the return address.
Use the Concepts
1) Write a function called square which receives one argument and returns the square of that argument.
Answer for this question is within the answer for question 2.
2) Write a program to test your square function.
#PURPOSE – Given a number, this program returns the
# value of the number squared. Example,
# an input of 2 would return 2*2 = 4
#
.section .data
#This program has no global data
.section .text
.globl _start
.globl square #unneeded unless we want to share
#this function among other programs
_start:
pushl $5 #square takes one argument – the
#number we are squaring so it gets
#pushed to the stack
call square #run the square function
addl $4, %esp #
movl %eax, %ebx #square returns the answer in %eax, but
#we want it in %ebx to send it as our exit
#status
movl $1, %eax #call the kernel’s exit function
int $0x80
#This is the function definition
.type square,@function
square:
pushl %ebp #we have to restore %ebp to its prior state
#before returning, so we have to push it
movl %esp, %ebp #this is because we don’t want to modify
#the stack pointer, so we use %ebp
movl 8(%ebp), %eax #this moves the first argument to %eax
#4(%ebp) holds the return address, and
#8(%ebp) holds the first parameter
cmpl $1, %eax #if the number is 1, the result will be
#the same as the value that is already
#stored in %eax. So we can return
je end_square
imull %eax, %eax #multiply the parameter by itself and
#store the value in %eax
jmp end_square #jump to the end of the function as we are
#done
end_square:
movl %ebp, %esp #standard function return stuff.
popl %ebp #we are restoring %ebp and %esp to
#where they were before the function
#started
ret #return to the original function and this will
#also pop the return value
3) Convert the maximum program given in the Section called Finding a Maximum Value in Chapter 3 so that it is a function which takes a pointer to several values and returns their maximum. Write a program that calls maximum with 3 different lists, and returns the result of the last one as the program’s exit status code.
.section .data
#we will have three lists that will be used to test
#our function
data_1:
.long 10, 2, 3, 4, 1,17
data_2:
.long 50, 23, 27, 62, 43
data_3:
.long 7, 21, 28, 16, 127, 221, 5
#VARIABLES
# %edi:index
# %ebx:current value
# %eax:largest value
# %ecx:address of list
.section .text
.globl _start
_start:
pushl $data_2 #push the data we want to test
call max
addl $4, %esp #reset the stack
movl %eax, %ebx
movl $1, %eax
int $0x80
.type max, @function
max:
pushl %ebp #basic function setup
movl %esp, %ebp
movl $0, %edi #set index to 0
movl 8(%ebp), %ecx #get address of the list
movl (%ecx, %edi, 4), %ebx #store first value in %ebx
movl %ebx, %eax #first value is largest so store
#in %eax
max_loop:
cmpl $0, %ebx
je exit_loop
incl %edi
movl (%ecx, %edi, 4), %ebx
cmpl %eax, %ebx
jle max_loop
exit_loop:
movl %ebp, %esp #undo changes made for function
popl %ebp
ret
4) Explain the problems that would arise without a standard calling convention.
Without a standard calling convention there would be loads of issues on a long-term project. Developers would struggle to understand and work on a program without a standard calling convention. Also if the program was meant to work with another programming language it would not be possible without changing nearly the entire program. Standard calling conventions while not necessary are crucial to developing a well managed program.
Going Further
1) Do you think it’s better for a system to have a large set of primitives or a small one, assuming that the larger set can be written in terms of the smaller one?
I’m not necessarily sure on this one but I would imagine a large set of primitives would be better. My reasoning for this is that if a system has a larger set of primitives it means that the system itself has a greater amount of abilities. With programming this would allow us to use the primitives to create a greater amount of functions, possibly making our code more efficient.
2) The factorial function can be written non-recursively. Do so.
.section .data
.section .text
.globl _start
_start:
pushl $4 #pushing argument
call factorial #calling function
addl $4, %esp #move stack pointer back
movl %eax, %ebx #place result into ebx for exit status
movl $1, %eax #exit
int $0x80
#finds the factorial of a value
#INPUT: First and only argument is the number to find the factorial for
#NOTES: number must be greater than one
#Variables:
# %ebx – holds the argument value
# %ecx – holds the index we are multiplying the argument by
# -4(%ebp) – holds the current result
# %eax is used for temporary storage
factorial:
pushl %ebp #save old base pointer
movl %esp, %ebp #make stack pointer the base pointer
subl $4, %esp #get room for local storage
movl 8(%ebp), %ebx #put first argument in %eax
movl %ebx, %ecx #set index to the value of argument
decl %ecx #subtract index by 1 as starting point
movl %ebx, -4(%ebp) #store current result
factorial_loop_start:
movl -4(%ebp), %eax #move current result into %eax
imull %ecx, %eax #multiple current result by index
movl %eax, -4(%ebp) #move new result into storage
decl %ecx #decrease index by 1
cmpl $1, %ecx #if index is 1 jump to end of loop
je end_factorial
jmp factorial_loop_start #if index is not one restart loop
end_factorial:
#movl -4(%ebp), %eax #return value goes in %eax
movl %ebp, %esp #restore stack pointer
popl %ebp #restore base pointer
ret
3) Find an application on the computer you use regularly. Try to locate a specific feature, and practice breaking that feature out into functions. Define the function interfaces between that feature and the rest of the program.
This was more of a visual experience, no specific notes to list.
4) Come up with your own calling convention. Rewrite the programs in this chapter using it. An example of a different calling convention would be to pass paramters in registers rather than the stack, to pass them in a different order, to return values in other registers or memory locations. Whatever you pick, be consistent and apply it throughout the whole program.
I don’t plan on coming up with my own calling convention any time soon therefore, I’m going to skip this question and stick to common practice. Don’t want to start confusing myself by doing things differently.
5) Can you build a calling convention without using the stack? What limitations might it have?
Yes you can certainly build a calling convention without using the stack. This was lead to tons of limitations especially when it comes to variable storage and calling other functions. Without utilizing a stack things will get very messy very fast on any program with more than one function.
6) What test cases should we use in our example program to check to see if it is working properly?
Test cases could be something such as a compare operation that will check to see if your function gets the correct answer. This would mean setting a specific value as the parameter and setting the known correct answer in the code. While this does not cover all cases you can make multiples to test generic types of input possibilities.
Hi CirclesWeRun, I’m also going through the book, and I was really struggling with the third question in ‘use the concepts’. Specifically this line:
movl (%ecx, %edi, 4), %ebx #store first value in %ebx
I wasn’t aware that it’s possible to use a register instead of an address for indexed addressing mode.
I was wondering how you figured that out, and if there are any resources you could point me to that would expand on this.
Also, for the non-recurisive factorial question, I don’t think it’d work with 2! as you have ‘decl %ecx’ twice. To resolve, you could have ‘jle end_factorial’ or move the ‘cmpl $1, %ecx’ above the ‘decl %ecx’
Here’s my solution for comparison 🙂
factorial:
pushl %ebp
movl %esp, %ebp
movl $1, %eax #%eax holds the current result
movl 8(%ebp), %ecx
start_factorial:
cmpl $1, %ecx
jle end_factorial
imull %ecx, %eax
decl %ecx
jmp start_factorial
end_factorial:
movl %ebp, %esp
popl %ebp
ret
LikeLike
Hey, thanks for checking out my blog! I believe the book best explains the possible parameters for the addressing modes towards the end of chapter 2 if I remember correctly. This post on stackoverflow may help as well for this situation.
https://stackoverflow.com/questions/40619087/what-does-movl-eax-edx-4-ecx-instruction-do
Thank you for pointing out my flaw in the factorial problem, you are absolutely correct. I’ll make the necessary changes asap for future reference.
I’ve completed the book but, I have only done the problems up to chapter 5. If you’d like to work together on the remainder of the problems I would love some company! I plan to start the problems again sometime soon.
Thanks,
Circles
LikeLike