Assignment
LIFE
Background
In this assignment, you will implement a version of Game of Life in MIPS assembler. It is different from the "standard" version in having a finite board. This means that some cells (on the edges) will have fewer than eight neighbours. The size of the board is determined by the data definitions included at the start of the program.
Setting Up
Create a new directory for working on the assignment, change into that directory, and then run the command:
$ unzip/home/cs1521/web/17s2/assigns/ass1/ass1.zip
This will add the following files into the directory:
- life.c ... a working version of the Game of Life in C
- board1.h ... a 10x10 board state, for inclusion in life.c
- board2.h ... a 15x15 board state, for inclusion in life.c
- prog.s ... a template for the Game of Life program in MIPS
- board1.s ... an initial 10x10 board state and board size
- board2.s ... an initial 15x15 board state and board size
The C code in life.c is a working version of the Game of Life. It includes an initial state of the grid, reads a number maxiter for how many iterations to run, and then uses the rules to change the state maxiter times, displaying the state after each iteration. It is not written in a style we would normally use, but is intended to be a little closer to how you would render it in MIPS.
1 #include
2 #include
3
4 #include "board1.h"
5
6 intneighbours(int,int);
7 voidcopyBackAndShow();
8
9 int main(void)
10 {
11 intmaxiters;
12 printf("# Iterations: ");
13 scanf("%d",&maxiters);
14 for(int n =1; n <=maxiters; n++){
15 for(int i =0; i < N;i++){
16 for(int j =0; j < N;j++){
17 intnn=neighbours(i,j);
18 if(board[i][j]==1){
19 if(nn<2)
20 newboard[i][j]=0;
21 elseif(nn==2||nn==3)
22 newboard[i][j]=1;
23 else
24 newboard[i][j]=0;
25 }
26 elseif(nn==3)
27 newboard[i][j]=1;
28 else
29 newboard[i][j]=0;
30 }
31 }
32 printf("=== After iteration %d ===\n", n);
33 copyBackAndShow();
34 }
35 return0;
36 }
37
38 intneighbours(inti,int j)
39 {
40 intnn=0;
41 for(int x =-1; x <=1; x++){
42 for(int y =-1; y <=1; y++){
43 if(i+x <0||i+x > N-1)continue;
44 if(j+y<0||j+y> N-1)continue;
45 if(x ==0&& y ==0)continue;
46 if(board[i+x][j+y]==1)nn++;
47 }
48 }
49 returnnn;
50 }
51
52 voidcopyBackAndShow()
53 {
54 for(int i =0; i < N;i++){
55 for(int j =0; j < N;j++){
56 board[i][j]=newboard[i][j];
57 if(board[i][j]==0)
58 putchar('.');
59 else
60 putchar('#');
61 }
62 putchar('\n');
63 }
64 }
65
Note that the game board does not appear directly in the C code file. Instead it is #include'd, to make it easier (slightly) to include a different initial state in the program. The board1.h file simply contains:
1 // Game of Life on a 10x10 grid
2
3 #define NN 10
4
5 int N = NN;
6
7 char board[NN][NN]={
8 {1,0,0,0,0,0,0,0,0,0},
9 {1,1,0,0,0,0,0,0,0,0},
10 {0,0,0,1,0,0,0,0,0,0},
11 {0,0,1,0,1,0,0,0,0,0},
12 {0,0,0,0,1,0,0,0,0,0},
13 {0,0,0,0,1,1,1,0,0,0},
14 {0,0,0,1,0,0,1,0,0,0},
15 {0,0,1,0,0,0,0,0,0,0},
16 {0,0,1,0,0,0,0,0,0,0},
17 {0,0,1,0,0,0,0,0,0,0},
18
19 };
20 charnewboard[NN][NN];
21
22
Note that the board1.h file contains a global variable which holds the board size. This is used by the C code, rather than referencing the #define'd value, to make it more like what the assembly code does.
The intention of #include'ing the initial board state is that people can write their own starting board states and share them with others without having to reveal their program code. Of course, you've already got the C program code, but this setup is aimed at the MIPS data/code files.
For example, the board1.s file looks like:
1 # board.s... Game of Life on a 10x10 grid
2
3 .data
4
5 N:.word10 # gives board dimensions
6
7 board:
8 .byte1,0,0,0,0,0,0,0,0,0
9 .byte1,1,0,0,0,0,0,0,0,0
10 .byte0,0,0,1,0,0,0,0,0,0
11 .byte0,0,1,0,1,0,0,0,0,0
12 .byte0,0,0,0,1,0,0,0,0,0
13 .byte0,0,0,0,1,1,1,0,0,0
14 .byte0,0,0,1,0,0,1,0,0,0
15 .byte0,0,1,0,0,0,0,0,0,0
16 .byte0,0,1,0,0,0,0,0,0,0
17 .byte0,0,1,0,0,0,0,0,0,0
18
19 newBoard:.space100
20
Note that the definitions are intended to be analogous to the definitions in board.h. One difference is that MIPS assembly code does not have an equivalent to C's #define, and so the board size is repeated as a constant several times within the data definitions.
Exercise
The aim of this exercise is to complete the supplied program skeleton:
1 # prog.s... Game of Life on a NxN grid
2 #
3 # Needs to be combined with board.s
4 # The value of N and the board data
5 # structures come from board.s
6 #
7 # Written by <>, August 2017
8
9 .data
10 main_ret_save:.space4
11
12 .text
13 .globl main
14 main:
15 sw$ra,main_ret_save
16
17 # Your main program code goes here
18
19 end_main:
20 lw$ra,main_ret_save
21 jr$ra
22
23
24 # The other functions go here
25
You must implement the three functions given in the C code: main(), neighbours(), and copyBackAndShow(). You do not need to implement stack-based function calls, but can if you wish.
For testing, you will need to load both a board definition and your program code into the MIPS emulator to get a complete executable program. This is easy in qtspim, where you can load multiple files into the memory before executing them. The spim command only accepts one code file, and so you need to merge a boardX.s file and the prog.s file to create a complete program. A simple way to do this is to run two commands:
$ cat board1.s prog.s>life.s
$ spim -file life.s
# Iterations: 3
=== After iteration 1 ===
##........
##........
.###......
....#.....
....#.....
...##.#...
...##.#...
..##......
.###......
..........
=== After iteration 2 ===
##........
..........
####......
..#.#.....
....#.....
..........
..........
.#........
.#.#......
..#.......
=== After iteration 3 ===
..........
..........
.###......
..#.#.....
...#......
..........
..........
..#.......
.#........
..#.......
$
In order to conduct testing, you could compile the life.c program, run it to collect the expected output, then run the SPIM version to collect the observed output, and compare them, e.g.
$ dcc life.c... or gcc -std=c99 if doing at home ...
$ echo 3 | ./a.out>c.out
$ echo 3 | spim -file life.s>mips.out
$ diff c.outmips.out
... we expect no output here ...
$
If the output from diff is empty, then the MIPS program is behaving as expected.
You should try this for at least the two supplied boards. Remember that you will need to edit life.c to change what's #include'd, then re-compile, and then build a new life.s by merging prog.s with the corresponding boardX.s and repeating the above testing.
It would be great if people created new, more interesting, initial board state files and made them available for others to use in their testing.
Things you should not do:
- use a cross-compiler to convert the above C code to MIPS assembler
- copy Victor Torres' or anyone else's solution from an online source like GitHub