Programming From The Ground Up Chapter 4

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.