Summer 2011 CS61C Homework 2 : C and MIPS Programming
TA: Sean Soleyman

Due on Sunday 07-03-2011 at 11:59PM


Part 1: Life 1D

The Simulation Process

For hw2, you will be implementing an elementary cellular automaton, also known as Life 1D. A cellular automaton is composed of a space of cells, which can be dead or alive, and a rule describing the transition from one generation of cells to the next; each cell in the next generation depends on the 5 cells surrounding its position in the current generation. In Life 1D, the cells live in a 1-dimensional array.

Note: Some of you might be familiar with this game/assignment, but take notice that this version depends on 5 cells above it instead of 3.

For example, here is an array of 7 cells. The value 7 was chosen arbitrarily for this example.

Cells are shaded if they are alive, otherwise they are dead. Therefore, only the center cell in this example is alive (Your initial row will look similar no matter how long it is; only the center cell starts out alive).

We produce the next generation of cells using a rule that ranges from 0-4294967295. Note that such a number can be represented with 32 bits. For our example, we will consider the rule 3141592653, which is equal to 0b10111011010000001110011001001101. Each bit in this binary number corresponds to whether the child cell of the pattern representing its position will be dead or alive.

Position (decimal) Position (binary)Dead/Alive
0 0b00000 1
1 0b00001 0
2 0b00010 1
3 0b00011 1
4 0b00100 0
5 000b101 0
6 0b00110 1
7 0b00111 0
and so on...
 
30 0b11110 0
31 0b11111 1
Looking at the 3rd column from top to bottom is the same as looking at the binary representation of your rule from right to left.

Here is the same table graphically. Note again that the 5 cells above represent its place in binary and the one below represents whether the corresponding bit is on or off in the rule number.


We have to check each cell in the array to see whether it will be alive or dead in the next generation. We use the dead/aliveness of that cell along with the dead/aliveness of its 2 left and 2 right neighbors as a 5-bit number, which we use to index the rule.

For example, starting with the same 7 cell array, we first look at the leftmost cell.

It's dead, as well as its four neighbors (for our purposes, we will assume all cells off the world are dead). This corresponds to 0b00000, which for rule 3141592653 is 1 (i.e. on, alive). This means that in the corresponding cell for the array representing the next generation, it will be alive.

Repeat the process for the second cell from the left. This one is 0b00001, so in the next generation it will be dead. What about the third cell?

We can see that this cell is dead as well as its left neighbors, but its immediate right neighbor is alive. This corresponds to 0b00010, which for rule 3141592653 is 1 (i.e. on, alive). Therefore, the third cell of the next generation will also be alive.

The fourth cell corresponds to 0b00100, which is dead. We can repeat this process for the remaining cells to produce the following next generation array.

By repeatedly applying this generation process and putting each new generation below the previous one, we can produce a pattern.

You will be writing a C program to do this for any rule and number of rows.

For context and a full description of this problem, read Wolfram's Elementary Cellular Automata .

Problem 1 (50% Of Grade)

You are to implement a one-dimensional variant of Conway's Game of Life, heretofore called "Life 1D". Specifically, you will write the following program in C (from scratch), which takes 2 command line arguments, rows and rule. The rows value determines the size of the picture, which will be (rows+1) high and (2*rows+1) wide. The first row consists of all dead cells except the center cell, which is alive. Note that since the number of columns is always odd, there's always a definite center. We use rows+1 because rows really refers to the number of generated rows, which doesn't include the aforementioned initial row. which supports the following:
Usage: Life1D <rows> <rule>
    This program simulates 1D Life: the simplest class of one-dimensional
    cellular automata in a <ROWS=rows+1> x <COLS=2*rows+1> grid starting
    with a single live cell in the middle of the top row using rule <rule>.
    These 1D rules are defined in Wolfram's Elementary Cellular Automata:
    http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
    This program will print to stdout data in plain PBM file format.
    This output can be easily viewed using the display command or 
    converted to a another format using the pbmto* and ppmto* utilities. 
    A plain ASCII PBM file can be created by adding a header line 
    "P1 <WIDTH> <HEIGHT>" and followed by a grid of data 
    (0 = dead = white, 1 = live = black).  Add a comment on the first 
    line with a brief description of the image.
  Arguments:
    <rows> is a positive integer specifying the number of rows to generate
    (not counting the first "seed row" which is all dead except for a central
    live cell). The columns are computed automatically -- enough so that
    the rule, if it were to grow in the normal triangular pattern, would
    just perfectly reach the edge. Off the board is considerered "dead".
    <rule> is a number from 0-4294967295 specifying the rule to use.

Examples:

    unix% ./Life1D 3 58979
    P1 7 4 ## 3 rows of Life1D (Rule 58979) by Yourfirstname Yourlastname
    0 0 0 1 0 0 0
    1 1 0 0 0 0 1
    1 0 0 0 1 0 0
    0 0 0 0 0 0 0
    unix% ./Life1D 5 32384626
    P1 11 6 ## 5 rows of Life1D (Rule 32384626) by Yourfirstname Yourlastname
    0 0 0 0 0 1 0 0 0 0 0
    0 0 0 1 0 1 0 0 0 0 0
    0 1 0 1 1 0 0 0 0 0 0
    0 1 0 1 0 1 0 0 0 0 0
    0 1 1 1 1 0 0 0 0 0 0
    0 0 0 0 0 1 0 0 0 0 0
    unix% ./Life1D 4 4338327
    P1 9 5 ## 4 rows of Life1D (Rule 4338327) by Yourfirstname Yourlastname
    0 0 0 0 1 0 0 0 0
    1 1 1 1 1 0 0 1 1
    1 0 0 0 0 0 0 0 1
    1 0 0 1 1 1 1 1 1
    1 1 0 1 0 0 0 0 0
    unix% ./Life1D 17 3141592653
    P1 35 18 ## 17 rows of Life1D (Rule 3141592653) by Yourfirstname Yourlastname
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1
    1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0
    0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 0
    1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1
    0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0
    1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1
    0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 0
    1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0
    0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0
    1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0
    0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1
    1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0
    0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0
    1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0
    0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1
    1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0

Output Format

In order for your assignment to be graded properly, it must follow these output guidelines:
  1. The first line printed out in your program MUST follow this format
      P1 [a] [b] ## [c] rows of Life1D (Rule [d]) by [e]
    where [a] is the number of displayed cols, [b] is the number of displayed rows, [c] is the <row> parameter. [d] is the <rule> parameter, [e] is YOUR name

  2. Do not have any extraneous whitespace characters at the end of the row. Meaning, each row print out ends with "0\n" or "1\n", not "0 \n" or "1 \n".

  3. All rows end with a newline character. Meaning, after your program exits, the UNIX prompt starts on a new line and not on the same line as your last row.

  4. You must have spaces in between your columns (just like you see in the examples above) when you print out a row. Meaning, this is invalid (no spaces between columns):
       000010000
       000010100
       000010010
    
    and this is valid:
       0 0 0 0 1 0 0 0 0
       0 0 0 0 1 0 1 0 0
       0 0 0 0 1 0 0 1 0
    
  5. There can be any number of command line arguments and they are not necessarily integers. If the input doesn't satisfy the constraints (i.e., rows or rule aren't valid integers in the specified range, or too many/few arguments), you should print the Usage string above (just copy it into your code). It can also be found at ~cs61c/hw/02/usage.txt or here.

  6. Your program should be contained in a single file named Life1D.c. It should compile correctly using the following command:
    gcc -o Life1D -std=c99 Life1D.c

Test your code!

Test your code to see if they generate the examples above, then try a few rules of your own and verify that they're correct for a few rows. (If they are, then there's little reason to be wrong when producing more rows.) You can generate a gif image by piping the output into ppmtogif and redirecting the output to a file. E.g.,
unix% ./Life1D 3 58979 | ppmtogif > Life1D_3_60.gif
Here are the gifs resulting from the examples above:

Life1D 3 58979

Life1D 5 32384626

Life1D 4 4338327

Part 2: MIPS Programming

Problem 2 (10% Of Grade)

Show the single MIPS instruction or minimal sequence of instructions for the following valid C statements:

Assume that a corresponds to register $s0 and b corresponds to register $s1. $a0 contains a pointer to x[0], and x is an array of 32-bit integers.

Store your solution in a text file called hw2q2.

Problem 3 (10% Of Grade)

In this problem, $a0 is an integer argument while $a1 is a pointer to (ie: the address of) a large array. The value in $a0 can be any integer and the size of the array that $a1 points to is big enough (as long as you don't dereference memory before $a1, you won't be accessing memory that isn't yours) for the code to work correctly.

Convert this MIPS code to C and briefly explain what it does (as a multiple-line C comment). Specifically, what is in the array as the function returns?

addi$t1 $zero 31
addi$t0 $zero 31
loop:srlv$t3 $a0 $t1
andi$t3 $t3 1
addi$t3 $t3 48
sub$t4 $t0 $t1
add$t2 $a1 $t4
sb$t3 0($t2)
beq$t1 $zero done
subi$t1 $t1 1
jloop
done:sb$zero 1($t2)
jr$ra

Your function should be stored in a file called hw2q3.c. The file need not compile to an executable program (since it has no main procedure), but it should be possible for someone to copy and paste its contents into a valid c file. The function prototype is as follows:

void foo(int a0,char* a1);

Problem 4 (10% Of Grade)

Write the following VectorMult function as a MIPS subroutine (a procedure that can be called with jal VectorMult):

struct vector {
    int x;
    int y;
};

void VectorMult(struct vector** vectors, int len, int scale) {
       ...
}

The function VectorMult takes an array of pointers to struct vector ($a0) and multiplies each of the struct vector by scale ($a2). The vector length is stored in len ($a1). The product of vector (x1,y1) and integer scale is simply (x1 * scale, y1 * scale). The function should replace each of the vector in vectors by the corresponding product.

You can assume that the integer x is stored at a lower memory address than y. Therefore, if the address of a struct vector is 0x50000, than the member x is located at 0x50000, and the member y is located at 0x50004.

Save your answer to a file named hw2q4.s.

Problem 5 (20% Of Grade)

Write two recursive MIPS functions: one called remove and one called print, that will remove a value and print the contents of, respectively, the linked list set up in hw2q5.s. The skeleton code follows:

.data
L9: .word 9 0
L8: .word 8 L9
L7: .word 7 L8
L6: .word 6 L7
L5: .word 5 L6
L4: .word 4 L5
L3: .word 3 L4
L2: .word 2 L3
L1: .word 1 L2
L0: .word 0 L1

.text
main:   la $a0 L0
        addi $a1 $0 9
        move $s0 $a0
        jal remove
        move $a0 $v0
        jal print
        addiu $v0 $zero 10
        syscall

remove:

print:  

Save your answer to a file named hw2q5.s.

Especially for remove, you'd probably do yourself a big favor by writing a bit of C code first. A correctly working program will print "012345678" (Note the lack of punctuation or newlines). You are not permitted to change the initial data structure in the .data segment, the main routine, or anything else before the "remove:" label.

Submission

Create a directory called hw2 for your assignment submission. It should contain the following files: Life1D.c, hw2q2, hw2q3.c, hw2q4.s, hw2q5.s. From within this directory run "submit hw2". Be certain that your Life1D program accepts command line arguments for <rows> and <rule>, and that you do not interactively prompt for these values. Otherwise, your program will hang and fail the grading script.