This lab should be done with your assigned partner:
lab A partner list
lab B partner list

This is also the last lab for which we will assign partners. For all remaining labs, you will work with a partner of your own choosing.

Your partner for lab 5 and beyond must be in the same lab section as you. If you have a partner, both you and your future partner should send email to your lab instructor (Tia for Lab A and Bryce for Lab B) telling us who your lab 5 and beyond partner is. If you would like our help finding a partner, please email your lab instructor and we will help you find a partner before the lab 5 assignment.

Important: Send us your lab5 and beyond partner choice by Sunday noon so that we can help singles find partners.

---

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.

There are three parts to this lab assignment:

1. Part 1: C program with pointers and dynamic memory allocation
2. Part 2: IA32 Loop
3. Part 3: IA32 C-style pass-by-reference
4. Extra Challange: An Extra Challenge (this is NOT a required part of lab 4, and you should not try it until you have completed the first three required parts)

---

Lab 4 Starting point code:

Both you and your partner should do:

1. Get your Lab04 ssh-URL from the GitHub server for our class: CS31-f15
2. On the CS system, cd into your cs31/labs subdirectory

   cd ~/cs31/labs
   

3. Clone a local copy of your shared repo in your private cs31/labs subdirectory:

   git clone [your_Lab04_URL]
   

   Then cd into your Lab04-you-partner subdirectory.

If all was successful, you should see the following files when you run ls:

Makefile    grades.c     grades2.txt          mainCompareA.c  readfile.h
README.md   grades0.txt  loop.s               mainloop.c
compareA.s  grades1.txt  loop_C_goto_version  readfile.c

If this didn't work, or for more detailed instructions see the the Using Git page.

As you and your partner work on your joint solution, you will want to push and pull changes from the master into your local repos frequently.

Educators often want statistical analysis of a set of exam scores. These types of analyses could be done for an exam from a single class or an exam from an entire school district. A useful tool would be a program that computes statistical results for any size data set (i.e. it would work for ten data values or for thousands without re-compilation).

You will implement the program started in grades.c that takes a single command line argument, which is the name of a file of grade values (floats, one per line), and computes and prints out a set of statistics about the data values and prints out a historgram of the grade distribution.

The starting point code comes with three input files that you can use to test your solution.

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 grades.c is the starting point for your program. It contains a prototype for the getvalues function that you need to implement, and it has some code in main that copies the filename command line into a string local variable for you.

Your program should do the following:

1. 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 capacity of the array.

   getvalues returns an array of float values initialized to the values read in from the file, or returns NULL on error (like if malloc fails or if the file cannot be opened). It dynamically allocates the array it returns and uses a doubling re-allocation algorithm as it needs more space (see the Requirements section for details about this algorithm).

2. It then computes the max and min grades, the mean (average), the median (the middle value), and the standard deviation of the set of grade values. It prints out the total number of grades and each of these computed statistics.

3. It creates a histogram from the set of grade values, and prints out the grade histogram.

   A note on histogramming values: Each histogram bucket counts the number of exam scores in a particular range: 0-9, 10-19, 20-29, etc. Exam grades that have a fractional component (e.g. 89.75) should be counted as being in a histogram bucket range based on their whole number part only (e.g. 89.75 is a grade in the 80's not a grade in the 90's).

4. It prints out information about the amount of unused capacity in the array storing the grade values.

Statistic Functions

The statistics you need to compute on the set of values are the following:

1. 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).
2. 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). If the number of values is even, just use the num/2 value as the median.
3. 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 (average) value.

Sample Output

Here is Sample Output from a working program run on the three input files that were included with the starting point code. You should also test your program on other input files that you create.

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:
  1. Call malloc to allocate space for a new array that is twice the size of the current full one.
  2. Copy values from the old full array to the new array (and make the new array the current one).
  3. 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.

• You may have written code for lab 2 that would be useful, or useful as a reference, for this lab assignment.

• Use double variables 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 four function-worthy functions, be well commented, and use meaningful variable names.

• All TODO comments in the starting point code should be removed in the code your submit (these are my comments to you, not your comments describing what your code does).

• You may assume that the set of grade values are between 0.0 and 100.0. Grade values such as 67.5 or 70.25 are valid (don't assume whole number grades only).

• The histogram counts the number of grades within each range. You may assume range widths of 10 values: 0-9, 10-19, etc.

• You may use a statically declared array for the histogram, or you can dynamically allocate it if you'd like.

• Your program must be free of valgrind errors.

• See the lab 2 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.

For this part, you will act like a compiler and generate IA32 instructions for part of a C program. 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 see 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 already copied onto the stack for you, and is in the the caller's stack frame. Its value can be accessed relative to the %ebp pointer at ebp + 8:

  esp ---->    # loop's stack frame:
  
  
    ebp-0x8    # space for one local variable (for res or for i)
    ebp-0x4    # space for one local variable (for the other one)
  ebp ---->
               # main's stack frame:
    ebp+0x8:   # space for the parameter (x)
  

  Note: 8 and 0x8 are the same value. But be careful the representation you are using for literal values--be sure that you are using the value you think you are (e.g. 10 and 0x10 are not the same value).
• 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 at the week 4 Wednesday lab page and in-lab examples for how to use gdb to examing code at the IA32 instruction level.
• look in mainloop.c for the call to your loop function to help you see how it is called.
• The IA32 Cheatsheet is available at the bottom of the class webpage: Resources

For this problem you will also act like a compiler and generate IA32 code translation for part of a C function. In the file named changeA.s finish the IA32 implementation of the changeA function that changes the value of the int pointed to by x to the value of y.

void changeA(int *x, int y);

This function takes one int, x, passed by reference (the parameter points to the storage location of its argument), and one int, y, passed by value. After the call, if the value of the fist argument is greater than the value of the second argument, it should be set to the second. Otherwise, it is unchanged by the call. A call to changeA would look like (see mainchangeA.c for another example):

int a, b;
a = 10;
b = 8;
printf("%d %d\n", a, b);  // prints: 10 8 
changeA(&a, b);       // changes a's value to b's if a > b
printf("%d %d\n", a, b);  // prints: 8 8  (a's value was changed to b's) 
a = 3;
b = 11;
printf("%d %d\n", a, b);  // prints: 3 11 
changeA(&a, b);       // changes a's value to b's if a > b
printf("%d %d\n", a, b);  // prints: 3 11  (a's value wasn't changed to b's)

The changeA.s file already contains some IA32 instructions that set up up and tear down the stack frame associated with the function. You will add IA32 instructions to the body of this IA32 function to perform the "change A" operation.

In mainchangeA.c is code to test your implementation. Run make to build an executable, mainchangeA, that links in your changeA.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 ---->    # changeA's stack frame:
  
  ebp ---->
               # main's stack frame:
    ebp+0x8:   first parameter value  (&a)
    ebp+0xc:   second parameter value (b)
  

• 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 changeA would look like. Then convert it to a C goto version.
• 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 changeA.
• Design and test incrementally. See if you can get the changeA function to change a's value to b without the conditional part first. Once that works, then try adding in the conditional part.
• Look at your Tuesday's lecture notes about pointer variables and Last week and Thursday's lecture notes about IA32 functions.
• Look at Week 4's Wednesday lab page for tips on using gdb (or ddd) to step through code at the IA32 instruction level. Set a breakpoint in changeA, 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)
  

This is NOT a required part of the Lab 4 assignment. DO NOT try this until you have finished all regular parts of this lab (Parts 1-3). Extra Challenge parts are just a way to try something with an added challenge for fun. We will award a nominal amount of extra credit points to your lab score for successful completion of these (and it is all or nothing grading), but they will really have little to no impact on your lab grade: it is much much better to finish the required parts completely and to finish them well, than to try the extra challenge and not submit complete required parts.

Lab 4 Extra Challenge Part

Before the Due Date

Only one of you or your partner needs to push your solution from one of your local repos to the GitHub remote repo. (it doesn't hurt if you both push, but the last pushed version before the due date is the one we will grade, so be careful that you are pushing the version you want to submit for grading):

From one of your local repos (in your ~you/cs31/labs/Lab04-partner1-partner2 subdirectory)

git push

---

Troubleshooting

If git push fails, then there are likely local changes you haven't committed. Commit those first, then try pushing again:

git add grades.c
git commit
git push

Another likely source of a failed push is that your partner pushed, and you have not pulled their changes. Do a git pull. Compile and test that your code still works. Then you can add, commit, and push.

If that doesn't work, take a look at the "Troubleshooting" section of the Using git page. You may need to pull and merge some changes from master into your local. If so, this indicates that your partner pushed changes that you have not yet merged into your local. Anytime you pull into your local, you need to check that the result is that your code still compiles and runs before submitting.