This lab should be done with your lab partner.

Lab 6 Goals:

• practice with 2D arrays and file I/O in C
• more practice with pointers, dynamic memory allocation, and pass by reference
• designing input files to test correctness of your solution
• timing parts of a program's execution
• writing a Makefile from scratch
• gain expertise in gdb and valgrind for debugging C programs

Lab X Starting point code:

Both you and your partner should do:

1. Get your Lab06 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_Lab06_URL]
   

   Then cd into your Lab06-you-partner subdirectory.

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

Makefile  gol.c  test_bigger.txt test_corners.txt test_edges.txt test_oscillator.txt

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

The starting point code includes: an empty Makefile that you need to implement; gol.c into which you should implement your solution; and osicllator.txt, a sample input file to your program. You should create other input files to test your solution.

Game of Life

For this lab, you will implement a program that plays Conway's Game of Life. Conway's Game of Life is an example of discrete event simulation, where a world of entities live, die, or are born based based on their surrounding neighbors. Each time step simulates another round of living or dying.

Your world is represented by a 2-D array of values (0 or 1). If a grid cell's value is 1, it represents a live object, if it is 0 a dead object. At each discrete time step, every cell in the 2-D grid gets a new value based on the current value of its eight neighbors:

1. A live cell with zero or one live neighbors dies from loneliness.
2. A live cell with four or more live neighbors dies due to overpopulation.
3. A dead cell with exactly three live neighbors becomes alive.

Your 2-D world should be a TORUS; every cell in the grid has exactly eight neighbors. In the torus world, cells on the edge of the grid have neighbors that wrap around to the opposite edge. For example, the grid locations marked with an 'x' are the eight neighbors of the grid cell whose value is shown as 1.

x  1  x  0  0  0  0
x  x  x  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  0
x  x  x  0  0  0  0

Conway's Game of Life description from Wikipedia, shows some example patterns you can use to test the correctness of your solution (like Blinker, Toad or Beacon).

---

Implementation Details

Your program will take two command line arguments. The first is a the name of a configuration file that will specify how to initialize the game playing variables (dimensions of the grid, number of iterations, how to initialize the grid cells). The second will indicate whether or not the game of life board should be printed out after every iteration or not.

Here are some example command lines:

# run with config values read from file1.txt and do not print the board:
./gol file1.txt  0       
# run with config file file2.txt and print the board after each step:
./gol file2.txt  1   

Your program should handle badly formed command lines (e.g. print out an error message and exit).

File Format

The input file format consists of several lines of an ascii file. The first three lines give the dimensions and number of iterations, the fourth line lists the number of coordinate pairs followed by the lines with i j (row index, column index) coordinate values specifying grid cells that should be initialized to 1 (all others should be 0):

num rows
num cols
num iterations
num of following coordinate pairs (set each (i, j) value to 1
i j
i j 
...

Create your own input files in vim (or emacs) by following the file input format.

For example, a file with the following contents generates an interesting pattern that starts in the lower left and walk up to upper right of grid:

30
30
100
5
29 1
28 2
27 0
27 1
27 2

In addition, you will add timing code to your program to time just the GOL computation (the timing should not including the board initialization phase of your code).

Computing Values at Each time step

One problem you will need to solve is how to update each grid cell value at each time step. Because each grid cell's value is based on its neighbor's current value, you cannot update each cell's new value in place (otherwise its neighbors will read the new value and not the current value in computing their new value).

Correctness Testing

Part of this lab involves you designing gol input files that are desgined to test, debug, and varify the correctness of different aspects of your gol solution. We suggest that you start with some input files to test small, simple worlds.

With the starting point code are three test files that you need to implement, use for your own testing, and submit with your solution. You are welcome to, and encouraged to, submit more test files than these three, but these are required:

1. test_bigger.txt: this files should test a larger board size than the oscillator file's board, and should have several patterns on the board that should not interfere with each other. It should be a test of the middle of the board (don't worry about edges or corners here). For example, you could have a few still and/or oscillator patterns on the board in locations that they should not affect each other over time steps.
2. test_edges.txt: this file should create a board used for testing and verifying the correctness of updating edge cells (cells on the north, or south, or east, or west edge of the grid, but not including the corner cells). We suggest creating a small to medium size board for this one, and it is fine if this file includes a test for just one of the 4 edges (north, south, east, or west). However, you should test all edges with separate test files like the one you submit as this example, and you are welcome to submit these other test files.
3. test_corners.txt: this file should create a board used for testing the correctness of updating one or more of the 4 corner cells. Like the test_edges.txt file, this does not need to include a test for all 4 corners simultaneously; it can test just one of the corners. You should, however, make sure you have additional files that you use to test the other 3 corners for correctness.

---

Requirements

• You must use a Makefile to build your program, and you will write one from scratch for this assignment. Use Makefiles from other assignments as a guide. You should use only the following flags to gcc (don't use the -m32 flag for this assignment):

  -g -Wall
  

  Your Makefile should have rules for make and make clean commands. Use Makefiles that I have given you as a guide. Here is some basics on writing makefiles
• The program should take two command line arguments: the config file; and either 1 or 0 to enable or disable printing the board after each step.
• When run with 1 as the second command line option should print out the board after each time step. Use a call to usleep to pause after each time step so the user can "see" the computation better. Before printing out the result of the next timestep, call system("clear") to clear the terminal contents of the previous interation's output; the next interation's ouput will be written to the same spot, animating your gol computation. DO NOT clear the very last iteration's printed result.

  Note: the only calls to usleep and system should be in the print function(s); running with 0 as the second command line option option should include no output of the game board nor any calls to sleep functions during the run.

• The space for the GOL board(s) should be dynamically allocated in the heap. See the example from Weekly lab as well as Arrays in C for more information. Use the "Method 1" option that does a single malloc of a contiguous chunk of N*M int (or char). Do not use int** (or char**) for this assignment.
• You should not use global variables. Instead, the board(s) and other variables should be local varibles that are passed to functions that need them. If a function changes the the value of an argument, remember you need to pass that argument by reference. For array parameters, the caller can modify what is in the bucket values (passing an array is passing its base address to the function).
• Your program should have timing code in your solution around the GOL main computation (don't include grid initialization). And print out the total time for the GOL simulation at the end of the simulation. Use gettimeofday.
• Use the C FILE interface (fopen, etc.) for file I/O. We recommend using the fscanf function for reading in values from the file.
• You should detect and handle all errors, you can call exit(1) if the error is unrecoverable (after printing out an error message of course). This means that any time you call a function that returns a value, there should be a check for error return values and they should be handled: do not just assume that every function call and every system call is always successful.
• You should create test input files for testing the correctness of certain aspects of your program (input files test_bigger.txt, test_edges.txt, and test_corners.txt are required).
• Use usleep and system("clear") in your print code to implement animation of gol.
• Your solution must have at least three functions in addition to main, and likley should have more than this. Think good top-down design, and think about some of the big steps: initializing the game board; updating one round of play; printing the game board; ... main should represent the high-level steps with calls to high-level functions that perform each of the big steps. These functions in turn should use helper functions to implement well-defined pieces of functionality. As a rule, a function should not be longer than a page. There are exceptions, but if you are writing a function that is getting really long, break it up into several parts, each implemented by a separate function.
• You code should be well-commented code and use good modular design. See my C documentation for C references and a C code style guide.
• Your solution should be correct, robust, and free of valgrind errors

---

Useful C functions and Hints

• Look at the weekly lab page and example code from this week to see examples of file I/O, command line arguments, makefiles, and of dynamically allocated 2D arrays: Weekly Lab Week 9
• Implement and test incrementally! Use valgrind as you go to catch memory access errors as you make them.
• Review pointers in C. Here are some C programming references. In particular, my documentation about pointers in C ("C programming for CS31 Students Part 2") and other C pointer documentation may be helpful for this assignment.
  • Remember C-style pass by reference to "return" more than one value from a function.
  • Remember that a function can return a pointer (this may be useful if you have an initialization function that returns a pointer to the malloc'ed and initialized game board.

    int *init_board( ...
    

    Functions that return pointer values, generally return NULL on an error. The caller then will check the return value and decide how to handle a NULL return value.
• man pages for C library functions and system calls, and be careful about who is responsible for allocating and freeing memory space passed to (and returned by) these routines.
• Files in C contains some information about file I/O in C.
  • I'd recommend using fscanf to read in values from the file.
  • Remember that you do not need to read all of a file's contents at once. Your program can read part of the file contents, do something else, and then later read more of the file contents. If you do this, you may need to pass the FILE * to the open file to several functions, so think about where you want to open the file in your code to make this easy to do.
• usleep: pauses the program for some number of micro seconds. This is useful in print mode to slow down your program after each step so that you can see what it is doing. About .2 is a good amount to sleep:

  usleep(200000);  // sleep for 200,000 micro seconds (.2 seconds) 
  

• system("clear"); clears the xterm window so that the next output is at the top of the window (useful for printing the grid at each timestep to the same window location).
• gettimeofday can be used to instrument your program with timers. Call this function before and after the part of the code you want to time and subtract to get total time. 1 second is 1000000 micro seconds. gettimeofday takes a struct timeval by reference and its second argument value should be NULL:

  struct timeval start_time, stop_time;
  ...
  ret = gettimeofday(&start_time, NULL);
  // code you want to time
  ret = gettimeofday(&stop_time, NULL);
  

  The timeval struct is defined in the sys/time.h library (you do not need to define this struct, it is already defined for you):

  struct timeval { 
    time_t      tv_sec;     /* number of seconds */ 
    suseconds_t tv_usec;    /* number of microseconds */ 
  };
  

  gettimeofday gives the time as the number of seconds and microseconds since the Epoch (Jan 1, 1970). A single time value can be calculated by adding these two fields together. However, these field are in different units, so be sure to convert one to one to the other before adding them. See the man page (man gettimeofday for more information.
• atoi converts a string to an integer. For example, int x = atoi("1234"), assigns x the int value 1234. This is useful in your command line parsing functions for converting command line arguments that are read in as strings to their numeric values. See the man page for atoi for other similar functions to convert stings to other numeric types (man atoi).
• Remember CNTRL-C will kill your program if it seems to be stuck in an infinte loop.

Here is an example of what you might see from different runs. I'm printing '@' for 1's and '-' for 0's because it is easier to see than '0' and '1' characters. You do not need to use the same characters as me, but choose characters that are easy to visually distinguish so you can easily see the iterations. The first shows the end board configuration from a run that is initialized to run from the test_oscillator.txt config file. And, the second is the same configuration, but run with 0 as the second parameter (notice the time difference between the two):

# a run with output:
$ ./gol test_oscillator.txt 1 

- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - @ - - - - - - - - - 
- - - - - - - - - @ - - - - - - - - - 
- - - - - - - - - @ - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 

total time for 19 iterations of 19x19 is 2.019754 secs


# a run with 0 as the second parameter should print no ouput
# the total time then measures just the gol computation part because
# the printfs and usleeps should not be executed when passed 0

% gol test_oscillator.txt 0
total time for 19 iterations of 19x19 is 0.000381 secs

The starting configuration of the oscillator file board is:

- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - @ @ @ - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 

As you debug, use config files with small numbers of iterations, and comment out the call to system("clear") so you can examine the results of every iteration.
After completing a well-designed, well-commented, correct solution to the required parts of this assignment, as an extra challenge you can see how your program compares to mine speed-wise, and see if you can tune your program to beat mine: Speed Challenge.

Even if you do not do the extra challange, you may want to read it over to learn a bit more about running timed experiments, and about gcc compiler optimization flags.

Before the Due Date, one of you or your partner should push your solution to 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/Lab06-partner1-partner2 subdirectory)

git add gol.c
git commit
git push

If that doesn't work, take a look at the "Troubleshooting" section of the Using git page.