CS87 Lab 1

Lab 1: C Warm-up Assignment
Due: Wednesday, Jan 25 before 1 am (late Tuesday night)

This, and all, lab assignments should be done with a partner. See the Wed lab page for information about how you can set up a git repository for your joint lab 1 project.

Lab 1 Partners
Katherine Bertaut and Ames Bielenberg	Nick Felt and Chloe Stevens
Steven Hwang and Jordan Singleton	Phil Koonce and Sam White
Luis Ramirez and Kyle Erf	Niels Verosky and Elliot Weiser

Introduction

This lab is designed to give you some practice with writing and debugging C programs. In particular, you will use the following in your solution to this lab:

writing a program in several modules (.c files and .h files with shared definitions)
C-style pass by reference
using the different parts of memory (globals, locals, and heap)
C scoping (using static and extern)
using a makefile
parsing command line arguments
C file I/O
using gdb and valgrind to debug your program

Sequential 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:

A live cell with zero or one live neighbors dies from loneliness.
A live cell with four or more live neighbors dies due to overpopulation.
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).

Your program will take a number of command line options for initializing the game playing variables (dimensions of the grid, number of iterations, how to initialize the grid), and other options to print out the grid as the computation proceeds or write result to an output file.

In addition, you will add timing code to your program to time the GOL computation (not including the initialization or output phases).

Getting Started

Start by creating a git repository for you and your partner's lab1 solution.

If you'd like, you could use the C code from Wednesday's lab as the starting point for your lab1 solution (you should rename files, wipe out most of their contents, and change the Makefile of course):

cp ~newhall/public/cs87/lab1/* .

Implementation Details

Your solution should use support multiple command line arguments that specify how to initialize the game variables, including the the size of the board, the number of time steps, and the initial configuration of the board (use getopt to parse command line arguments.) Your program should work for any size game board, thus the board should be dynamically allocated using malloc based on its M and N dimension values read in from a file or given as command line arguments.

Command line options

The following are the set of command lines your program must support:

    ./gol {-n n -m m -n k [-s] | -f infile} [-x] [-o outfile] 
       -n  n:      number of rows in the game board
       -m  m:      number of columns in the game board
       -k  k:      number of iterations
       -s:         initialize to oscillator board (default is random)
       -f infile:  read in all board config info from a file
       -x:         don't print board out after every iteration
       -o outfile: print result board to output file
       -h:         print out this help message

You may additionally add other command line options to initialize the game board to other pre-set patterns ([-s | -b | ... ]).

The command line options specify how to initialize the game and how to run the simulation.

There are two ways to initialize the game:

The -f command line option means that the GOL problem size and initial state are read in from a file:
```
./gol -f startfile1           # initialize to values read in from a file
```

or the -n -m -k [-s] command line options are used to specifying the dimensions, number of iterations, and the starting point world initial configuration:

./gol -n 20 -m 30 -k 100 -s   # initialize 20x30 board to an oscillator pattern
./gol -n 20 -m 30 -k 100      # initialize 20x30 board to a random pattern
                              # setting about 25% of randomly selected 
                              # cells to 1 works well, but you can decide

These two modes are independent---you cannot have a command line with both the -f and -m options.

The -x and -o outfile options are optional and work with either initialization mode. The -x option is useful for running timing tests of different sized problems of the sequential version of GOL (we may use this later in the semester). Here are some example command lines:

# initialize 20x30 board to an oscillator pattern, output final
# board to a file named "outfile" in the same format as the infile format
./gol -n 20 -m 30 -k 100 -s  -o outfile

# initialize program from data read in from "infile" and output the final
# board to a file named "outfile" in the same format as the infile format
./gol -f infile -o outfile

# init from a file and do not print any output to stdout for this run
./gol -f infile -x

Your program should handle badly formed command lines (e.g. print out an error message and exit instead of using incompatible or incomplete command line options).

File Format

The input (and ouput) file format consists of several lines of an ascii file. The first three lines give the dimensions and number of iterations, the fourth line has a number of coordinate pairs followed by the lines with i j coordinate values specifying grid cells that should be set 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 
...

For example, this is an interesting pattern that will start in lower left and walk up to upper right of grid:

A good way to check if your output file is correct is to try to use it as an input file to a subsequent run.

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).

Requirements

You must use a makefile

You must have at least two different modules: gol.c with functions to initialize the game board in different ways ((1) random, (2) oscillator or (3) from file. It should also contain a gol function that plays one iteration of the game of life; main.c should contain main program control flow, command line parsing, printing and timing code and functions. Functions exported by gol.c and called in main.c should have prototypes in a gol.h included by main.c.

Runs without the -x 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. The only calls to sleep should be in the print function(s); running with the -x option should include no stdout output nor any calls to sleep functions during the run.

Space for the GOL board(s) should be dynamically allocated in the heap. See Arrays in C for options on how to do this. It is more efficient to use a single malloc of a contiguous chunk of N*M int (or char).
Make appropriate use of static and extern. The only global variables you should use are those used to store values of parsed command line arguments. The board(s) should be a local variable (do not use global variables for for these, instead pass the board(s) to functions that need them).
You should have command line option to read in initial config from an input file, as well as at least 2 functions to initialize game board in different ways (random (default), and an oscillator pattern (-s option)). You are welcome to add additional initial configuration patterns as additional command line options.
Have timing code in your solution around the GOL main computation (don't include grid initialization or outputing the result to a file). Use gettimeofday.
Use perror to report errors from system calls
You can use either the Unix file interface (open, etc.) or the C FILE interface (fopen, etc.) for file I/O (I recommend using C 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.
Your solution should be correct, robust, and free of valgrind errors
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.

Useful C and Unix Utilities

getopt command line parsing.
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.
rand and srand: C library random number generator and seeding function (pass srand time(NULL) to seed with current time).
Files in C: I'd recommend using fscanf to read in values from the file.
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). The curses library could also be useful for this.
use perror to print out error messages from failed system calls.
gettimeofday can be used to instrument your programs with timers. Call this function before and after the part of the code you want to time and subtract to get total time. See the man page for gettimeofday. 1 second is 1000000 micro seconds.
Remember C-style pass by reference to "return" more than one value from a function. Some C programming references.
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 3 atoi).

Example output

Here is an example of what you might see from different runs. The first shows just the start and end board configuration from a run that is initialized to a very simple oscillator pattern, and the second is the same configuration, but run with -x (notice the time difference between the two):

# a run with output:
$ gol -n 11 -m 11 -k 21 -s

start board:

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

end board:

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

total time for 21 iterations of 11x11 is 5.493663 secs

# a run with no output (-x) measures just the gol 
computation (not the printfs):
$  gol -n 11 -m 11 -k 21 -s -x
total time for 21 iterations of 11x11 is 1.001186 secs

What to Hand in

Submit a single tar file with the following contents using cs87handin (see Unix Tools for more information on script, dos2unix, make, and tar):

A README file with:
1. Your name and your partner's name
2. If you have not fully implemented some functionality, then list the parts that work (and how to test them if it is not obvious) so that you can be sure to receive credit for the parts you do have working.
All the source files needed to compile, run and test your code (Makefile, .c files, .h files, and optional test scripts). Please do not submit object (.o) or executable files (I can build these using your Makefile).

Lab 1: C Warm-up Assignment Due: Wednesday, Jan 25 before 1 am (late Tuesday night)

Contents: