This lab should be done with an assigned partner.
Here is the lab4 partner list.
First run
update31, which will create the directory
structure for your lab 3 assignment:
$ update31
$ cd cs31/labs/04
$ pwd
/home/your_user_name/cs31/labs/04
Sharing files with your partner
Later this semester we will learn a better way to share files, but for
now, you should either email or scp your shared solution to your
partner's directory after a joint editing session. Some suggestions for
using scp, email, or cut-and-paste to
share code with your partner.
Lab 4 Goals:
- To understand and use C pointer variables, dynamic heap memory allocation (malloc/free) and C style "pass by reference"
- To use gdb and valgrind to debug C programs, particularly for
memory access errors.
- To implement C program fragments in IA32, and test them in a real
program
- To use a C program that makes use of: command line
arguments; file I/O; multiple .c and .h files; and library linking.
- To use make and a Makefile to build multiple executable files.
Part 1. C Pointers
Experimental scientists collect data from experiments and often
want to compute some simple statistical analyses over the set of experimental
data. A useful tool would be a program that could compute these
statistical results for any size data set (i.e. it would work for 10 data
values or for 10 million without re-compilation).
For this program you will implement the program started in stats.c
that takes a single command line argument, which is the name of a file of
data values (floats, one per line), and computes and prints out a set of
statistics about the data values.
The starting point code comes with two input files that you can use to
test your solution:
./stats small.txt
Results:
--------
num values: 16
mean: 1.812
median: 2.000
std dev: 1.031
unused array capacity: 4
./stats large.txt
Results:
--------
num values: 94
mean: 1.161
median: 1.000
std dev: 0.788
unused array capacity: 66
This program includes the readfile library code that it links in as well
as linking in the math library:
use the makefile to compile.
You can see how the executable is built from a .c, a .o, and explicitly
linking in the math library (-lm), by reading the Makefile.
In stats.c is the starting point into which you will put your
code. It contains the prototype for the getvalues function that
you need to implement, and has some code to get the filename
command line argument.
Your program should do the following:
- Make a call to getvalues, passing in the filename of the
file containing the data values, and passing in two values by reference:
the address of an int variable to store the size of the array (number
of values read in); and the address of an int variable to store the total
array capacity.
The function will return an array of float values initialized to the values
read in from the file, or NULL on error (like malloc fails or the file cannot
be opened).
- It will then compute the mean (average), the median (the middle value),
the standard deviation of the set of values and print them out.
- It will also print out information about the number of values in the
data set and the amount of unused capacity in the array storing the values.
Statistic Functions
The statistics you need to compute on the set of values are the following:
- mean: the average of the set of values. For example, if
the set is: 5, 6, 4, 2, 7, the mean is 4.8 (24.0/5).
- median: the middle value in the set of values. For example,
if the set is: 5, 6, 4, 2, 7, the median value is 5 (2 and 4 are smaller
and 6 and 7 are larger).
- stddev: is given by the following formula:
Where N is the number of data values, X_i is the ith data value, and
X-hat is the mean values.
Requirements and Hints
- getvalues: The array of values must be dynamically allocated
on the heap by calling malloc. You should start out allocating
an array of 20 float values. As you read in values into the current array,
if you run out of capacity:
- Call malloc to allocate space for a new array that is
twice the size of the current full one.
- Copy values from the old full array to the new array (and make
the new array the current one).
- Free the space allocated by the old array by calling free.
When all of the data values have been read in from the file, the function
should return the filled, dynamically allocated, array to the caller
(the function's return type is float *).
The size and capacity of the array should be "passed" back to the caller
via the pointer parameters that are used for pass-by-reference values.
NOTE: there are other ways to do this
type of alloc and re-alloc in C. However, this is the way I want you to
do it for this assignment: make sure you start out with a dynamically
allocated array of 20 floats, then each time it fills up, allocate a
new array of twice the current size, copy values from the old to new,
and free the old.
- Try getting getvalues to work without the re-allocation and
copying part first (for fewer than 20 values). Once that works, then
go back and get it to work for larger numbers of input values that require
mallocing up new heap space, copying the old values to the new larger space,
and freeing up the old space.
- Use doubles to store and compute the mean and the square root.
- The C math library (in math.h), has functions to compute the square root:
double sqrt(double val);
- Your program must have at least three function-worthy functions, be
well commented, and use meaningful variable names.
- Your program must be free of valgrind errors.
- See the lab 1 assignment for documentation about using the
readfile library (and also look at the readfile.h comments for how to
use its functions).
- Take a look at the weekly lab code and in-class exercises to
remind yourself about malloc, free, pass-by-reference, pointer variables,
dereferencing pointer variables, and dynamically allocated arrays.
- Make use of my C programming resources and links for C references (C pointer
references in particular), and the C Style Guide for tips on good
commenting, avoiding line wrapping, and other programming style tips.
Part 2. Writing a Loop in IA32
In the file named
loop.s finish the implementation of
the following function in IA32:
// this function computes the sum of the first x positive int values
// x: the top of the range of values to sum
// returns: the sum of the values 0 to x inclusive
int loop(int x) {
int res, i;
res = 0;
for(i=1; i <= x; i++) {
res = res + i;
}
return res;
}
In
mainloop.c is a main program that makes a call to this
function.
If you run make, you can build an executable,
mainloop,
that links in your loop.s solution.
Use this to test your solution for correctness.
Hints and Requirements
- In the file loop_C_goto_version you should write
your C goto translation of the loop function above (you do not need
to compile this, I just want to set your application of Step 1 in
converting a C for loop to IA32).
- The basic stack set-up and return code is provided for you in loop.s,
including space for the two local variables res and i.
- The parameter value x is in the stack in the caller's
stack frame. It can be accessed relative to the %ebp pointer:
esp ----> # loop's stack frame:
ebp-0x8 # space for one local variable
ebp-0x4 # space for one local variable
ebp ---->
# main's stack frame:
ebp+0x8: # space for the parameter (x)
- The return value must be stored in register %eax right
before the leave, ret instruction sequence.
- Comment your IA32 instructions with what they are doing in terms of
the C code. As an example:
movl 0x8(%ebp), %eax # load x into R[%eax]
addl $1, %eax # x + 1
Help:
- Draw a picture of the stack, draw where parameter and argument
values are and trace through the instruction execution
to help you determine what IA32 instructions you need to use to implement
loop.
- Try implementing and testing incrementally. For example, first see
if you can add code to return the value of the parameter. Next, try
returning some function of the parameter (like x+10).
- You can use gdb (or ddd) to debug your solution. Set a breakpoint in
loop, and use disass, ni, and print $reg to see values as you go. If you
want to see the value referred to by an address, you need to tell gdb what
type the address points to. For example, if you want to see an int value
at address 0x1234, do:
# re-cast address as an int pointer (int *), then dereference the pointer *
(gdb) *(int *)(0x1234)
- look in mainloop.c for the call to your loop function to help you
see how it is called.
Part 3. Writing a Swap Function in IA32
In the file named
swap.s finish the implementation of
the a swap function that swaps two int values:
void swap(int *x, int *y);
This function takes two ints
passed by reference (the parameters
point to the storage location of their argument variables). After the call,
the two int variables passed to swap should have their values swapped.
A call to swap would look like (see mainswap.c for another example):
int a, b;
a = 10;
b = 8;
printf("%d %d\n", a, b); // prints: 10 8
swap(&a, &b); // swap the values stored in a and b
printf("%d %d\n", a, b); // prints: 8 10
The
swap.s file already contains some IA32 instructions
that set up up and tear down the stack frame associated with the swap
function. You will add IA32 instructions to the body of this IA32 function
to perform swapping operation.
In mainswap.c is code to test your swap implementation.
Run make to build an executable, mainswap, that
links in your loop.s solution and calls it.
Use this to test your solution for correctness.
Hints and Requirements
- The basic stack set-up and return code is provided for you. However,
if you need space for local variables in the stack frame, you need to
explicitly add code to allocate the stack space you need by changing
the value of %esp.
- The parameter values of x and y are on the stack in the caller's
stack frame. They can be accessed relative to the %ebp pointer:
esp ----> # swap's stack frame:
ebp ---->
# main's stack frame:
ebp+0x8: first parameter value
ebp+0xc: second parameter value
- Comment your IA32 instructions with what they are doing in terms of
the C code. As an example:
movl 0x8(%ebp), %eax # load x into R[%eax]
addl $1, %eax # x + 1
Help:
- Start by figuring out what the C code version of swap would look like.
- Draw a picture of the stack, draw where parameter and argument
values are and trace through the instruction execution
to help you determine what IA32 instructions you need to use to implement
swap.
- Try implementing and testing incrementally. For example, first see
if you can set the value pointed to by x to the value pointed to by y.
Once that works, then see if you can add complete the function.
- Look at your Thursday's lecture notes about pointer variables and
the Thursday Weekly lab page for an example of IA32 code for pointers.
- You can use gdb (or ddd) to debug your solution. Set a breakpoint in swap,
and use disass, ni, and print $reg to see values as you go. If you
want to see the value referred to by an address, you need to tell gdb what
type the address points to. For example, if you want to see an int value
at address 0x1234, do:
# re-cast address as an int pointer (int *), then dereference the pointer *
(gdb) *(int *)(0x1234)
Submit
Once you are satisfied with your solutions, hand them in by typing
handin31 at the unix prompt.
Only one of you or your partner should run handin31 to submit
your joint solutions
You may run
handin31
as many times as you like, and only the
most recent submission will be recorded. This is useful if you realize,
after handing in some programs, that you'd like to make a few more
changes to them.