initial commit

2 files changed, 580 insertions, 0 deletions

diff --git a/comp1521/cellular/cellular.s b/comp1521/cellular/cellular.s
new file mode 100644
index 0000000..3bdd7aa
--- /dev/null
+++ b/comp1521/cellular/cellular.s
@@ -0,0 +1,362 @@
+########################################################################
+# COMP1521 20T2 --- assignment 1: a cellular automaton renderer
+
+# Complex logical statements are marked with horizontal bars for readability.
+
+# Maximum and minimum values for the 3 parameters.
+
+MIN_WORLD_SIZE	=    1
+MAX_WORLD_SIZE	=  128
+MIN_GENERATIONS	= -256
+MAX_GENERATIONS	=  256
+MIN_RULE	=    0
+MAX_RULE	=  255
+
+# Characters used to print alive/dead cells.
+
+ALIVE_CHAR	= '#'
+DEAD_CHAR	= '.'
+
+# Maximum number of bytes needs to store all generations of cells.
+
+MAX_CELLS_BYTES	= (MAX_GENERATIONS + 1) * MAX_WORLD_SIZE
+
+	.data
+
+# `cells' is used to store successive generations.  Each byte will be 1
+# if the cell is alive in that generation, and 0 otherwise.
+
+cells:	.space MAX_CELLS_BYTES
+#cells:	.byte 1:MAX_CELLS_BYTES           # Very useful for debugging.
+
+# Some strings you'll need to use:
+
+prompt_world_size:	.asciiz "Enter world size: "
+error_world_size:	.asciiz "Invalid world size\n"
+prompt_rule:		.asciiz "Enter rule: "
+error_rule:		.asciiz "Invalid rule\n"
+prompt_n_generations:	.asciiz "Enter how many generations: "
+error_n_generations:	.asciiz "Invalid number of generations\n"
+
+	.text
+
+    # REGISTERS IN MAIN
+    # $s0: int world_size    (runtime input)
+    # $s1: int rule          (runtime input)
+    # $s2: int n_generations (runtime input)
+    # $s3: int reverse       (0 or 1)
+    # $s4: int g             (loop counters)
+    # $t0 to $t2             (temp variables)
+    # $v0 to $v2             (syscalls and functions)
+
+#--------------------------------BEGIN_MAIN-------------------------------------
+
+main:
+    # No need to store $ra on the stack until we call our own functions.
+
+    la      $a0, prompt_world_size      # printf("Enter world size: ");
+    li      $v0, 4
+    syscall
+    
+    move    $s0, $zero                  # $s0: int world_size = 0;
+    li      $v0, 5                      # scanf("%d", &world_size);
+    syscall
+    move    $s0, $v0
+
+    blt     $s0, MIN_WORLD_SIZE, if0    # if (world_size < MIN_WORLD_SIZE)
+    bgt     $s0, MAX_WORLD_SIZE, if0    # ^|| (world_size > MAX_WORLD_SIZE);
+    b       skip0
+if0:
+    la      $a0, error_world_size       # printf("Invalid world size\n");
+    li      $v0, 4
+    syscall
+    li      $v0, 1                      # return 1;
+    jr      $ra
+    # Despite returning 1, echo $? says '0'. I suspect this is due to spim
+    # returning 0 on the "successful" execution of a program. I am unaware
+    # of how to extract the return value of an emulated mips program.
+
+skip0:
+    la      $a0, prompt_rule            # printf("Enter rule: ");
+    li      $v0, 4
+    syscall
+    
+    move    $s1, $zero                  # $s1: int rule = 0;
+    li      $v0, 5                      # scanf("%d", &world_size);
+    syscall
+    move    $s1, $v0
+
+    blt     $s1, MIN_RULE, if1          # if (world_size < MIN_RULE)
+    bgt     $s1, MAX_RULE, if1          # ^|| (world_size > MAX_RULE);
+    b       skip1
+if1:
+    la      $a0, error_rule             # printf("Invalid world size\n");
+    li      $v0, 4
+    syscall
+    li      $v0, 1                      # return 1;
+    jr      $ra
+
+skip1:
+    la      $a0, prompt_n_generations   # printf("Enter how many generations ");
+    li      $v0, 4
+    syscall
+    
+    move    $s2, $zero                  # $s2: n_generations = 0;
+    li      $v0, 5                      # scanf("%d", &world_size);
+    syscall
+    move    $s2, $v0
+
+    blt     $s2, MIN_GENERATIONS, if2   # if (n_generations < MIN_GENERATIONS)
+    bgt     $s2, MAX_GENERATIONS, if2   # ^|| (n_generations > MAX_GENERATIONS);
+    b       skip2
+if2:
+    la      $a0, error_n_generations    # printf("Invalid world size\n");
+    li      $v0, 4
+    syscall
+    li      $v0, 1                      # return 1;
+    jr      $ra
+
+skip2:
+    li      $a0, '\n'                   # putchar('\n');
+    li      $v0, 11
+    syscall
+
+    move    $s3, $zero                  # $s3: int reverse = 0;
+    blt     $s2, 0, if3                 # if (n_generations < 0);
+    b       skip3
+if3:
+    li      $s3, 1                      # reverse = 1;
+    mul     $s2, $s2, -1                # n_generations = -n_generations;
+
+skip3:
+    la      $t0, cells                  # cells[0][world_size / 2] = 1;
+    li      $t1, 2
+    div     $s0, $t1
+    mflo    $t1
+    add     $t0, $t0, $t1
+    li      $t2, 1
+    sb      $t2, ($t0)
+
+    # After this point we begin to use our functions, so save the stack pointer.
+    sub     $sp, $sp, 4
+    sw      $ra, ($sp)
+
+
+#-------------------------------FIRST_LOOP_START--------------------------------
+    
+    li      $s4, 1                      # for (int g = 1; ($s4: int g = 1)
+loop0:
+    bgt     $s4, $s2, end0              # ^g <= n_generations; (test condition)
+    
+    move    $a0, $s0                    #run_generation(world_size, g, rule);
+    move    $a1, $s4
+    move    $a2, $s1
+    jal     run_generation
+    
+    add     $s4, $s4, 1                 # g++;);   (increment)
+    b       loop0
+end0:
+
+#--------------------------------FIRST_LOOP_END---------------------------------
+#--------------------------------------IF---------------------------------------
+
+    beqz    $s3, skip4                  # if (reverse)
+
+#------------------------------SECOND_LOOP_START--------------------------------
+    move    $s4, $s2                    # for (int g = n_generations; 
+                                        # ($s4: int g = n_generations)
+
+loop1:
+    blt     $s4, 0, end1                # ^g >= 0; (test condition)
+
+    move    $a0, $s0                    # print_generation(world_size, g);
+    move    $a1, $s4
+    jal     print_generation 
+    
+    sub     $s4, $s4, 1                 # g--;);   (decrement)
+    b       loop1
+end1:
+#------------------------------SECOND_LOOP_END----------------------------------
+    b       skip5 
+#------------------------------------ELSE---------------------------------------
+skip4:                                  # else
+#------------------------------THIRD_LOOP_START---------------------------------
+    li      $s4, 0                      # for (int g = 0; ($s4: int g = 0)
+loop2:
+    bgt     $s4, $s2, end2              # ^g <= n_generations; (test_condition) 
+
+    move    $a0, $s0                    # print_generation(world_size, g);
+    move    $a1, $s4
+    jal     print_generation 
+
+    add     $s4, $s4, 1                 # g++;) (increment)
+    b       loop2
+
+end2:
+#-------------------------------THIRD_LOOP_END----------------------------------
+skip5:
+#----------------------------------ELSE_END-------------------------------------
+
+	lw      $ra, ($sp)                  # Load $ra from the stack.
+    add     $sp, $sp, 4                 # Deallocate from the stack, now empty.
+    li      $v0, 0                      # Return 0.
+	jr      $ra
+#----------------------------------MAIN_END-------------------------------------
+
+
+	# Given `world_size', `which_generation', and `rule', calculate
+	# a new generation according to `rule' and store it in `cells'.
+
+    # REGISTERS IN RUN_GENERATION
+    # $a0: int world_size                (passed to function)
+    # $a1: int which_generation          (passed to function)
+    # $a2: int rule                      (passed to function)   
+    # $t0: int x                         (copy of arguments)    CHANGED!
+    # $t1: int left                      (copy of arguments)    CHANGED!
+    # $t2: int centre                    (copy of arguments)    CHANGED!
+    # $t3: int right                     (increment variable)   CHANGED!
+    # $t4 to $t5:                        (temp variables)       CHANGED!
+    # $v0: int                           (syscalls)             CHANGED!
+
+#-----------------------------BEGIN_FUNCTION_0----------------------------------
+run_generation:
+
+    # In this function we are pressed for variables. We will modify $a variables
+    # but continue to preserve them without using the stack as they are
+    # easily reversible changes which we may keep track of and fix before we
+    # return.
+
+#---------------------------------BEGIN_LOOP------------------------------------
+    li      $t0, 0                      # for(int x = 0; ($t0: int x = 0)
+f0loop0:
+    bge     $t0, $a0, f0end0            # ^x < world_size
+
+    li      $t1, 0                      # $t1: int left = 0;
+
+    sub     $a1, $a1, 1                 # which_generation--
+    sub     $t0, $t0, 1                 # x--
+
+    la      $t2, cells                  # $t3 = &cells[which_generation-1][x-1]
+    mul     $t3, $a1, MAX_WORLD_SIZE
+    add     $t3, $t2, $t3
+    add     $t3, $t3, $t0
+
+    add     $t0, $t0, 1                 # x++
+    ble     $t0, 0, f0skip0             # if (x > 0)
+    lb      $t1, ($t3)                  # left = cells[which_generation-1][x-1]
+
+f0skip0:
+    add     $t3, $t3, 1                 # ++t3, access [x] not [x-1]
+    lb      $t2, ($t3)                  # $t2 = cells[which_generation-1][x]
+    
+    add     $t4, $t3, 1                 # copy useful ++$t3 before we use $t3
+
+    li      $t3, 0                      # $t3: int right = 0
+    sub     $a0, $a0, 1                 # world_size--
+    bge     $t0, $a0, f0skip1
+    
+    lb      $t3, ($t4)                  # right = cells[which_generation-1][x+1]
+f0skip1:
+    add     $a0, $a0, 1                 # world_size++
+    add     $a1, $a1, 1                 # which_generation++
+    
+    sll     $t1, $t1, 2                 # int state = left << 2 | centre << 1
+    sll     $t2, $t2, 1                 # ^ | right << 0;
+    or      $t5, $t1, $t2               
+    or      $t5, $t5, $t3
+
+    li      $t1, 1
+    sll     $t5, $t1, $t5               # int bit = 1 << state;
+    and     $t5, $a2, $t5               # int set = rule & bit;
+
+    la      $t2, cells                  # $t2 = &cells[which_generation][x]
+    mul     $t3, $a1, MAX_WORLD_SIZE    
+    add     $t3, $t2, $t3
+    add     $t3, $t3, $t0
+    
+#--------------------------------------IF---------------------------------------
+    beqz    $t5, f0skip2                # if (set)
+
+    li      $t1, 1                      # cells[which_generation][x] = 1;
+    sb      $t1, ($t3)
+
+    b       f0skip3
+f0skip2:
+#------------------------------------ELSE---------------------------------------
+    li      $t1, 0                      # cells[which_generation][x] = 0;
+    sb      $t1, ($t3)
+f0skip3:
+
+    add     $t0, $t0, 1                 # x++ (increment)
+    b       f0loop0
+#-----------------------------------END_ELSE------------------------------------
+f0end0:
+#-----------------------------------END_LOOP------------------------------------
+	jr	$ra                             # return;
+#-------------------------------END_FUNCTION_0----------------------------------
+
+	# Given `world_size', and `which_generation', print out the
+	# specified generation.
+
+    # REGISTERS IN PRINT_GENERATION
+    # $a0: int world_size                (passed to function)   CHANGED!
+    # $a1: int which_generation          (passed to function)
+    # $t0: int world_size                (copy of arguments)    CHANGED!
+    # $t1: int which_generation          (copy of arguments)    CHANGED!
+    # $t2: int x                         (0++, loop counter)    CHANGED!
+    # $t3 to $t4:                        (temp variables)       CHANGED!
+    # $v0                                (syscalls)             CHANGED!
+
+#-----------------------------BEGIN_FUNCTION_1----------------------------------
+print_generation:
+    move    $t0, $a0                    # Copy arguments, to use syscalls.
+    move    $t1, $a1
+
+    move    $a0, $t1                    # printf("%d", which_generation);
+    li      $v0, 1
+    syscall
+
+    li      $a0, '\t'                   # putchar('\t');
+    li      $v0, 11
+    syscall
+
+#-------------------------------FOR_LOOP_START----------------------------------
+    li      $t2, 0                      # for (int x = 0; ($t2: int x = 0)
+f1loop0:
+    bge     $t2, $t0, f1end0            # ^x < world_size; (test condition)
+
+#-------------------------------------IF----------------------------------------
+    la      $t3, cells                  # if(cells[which_generation][x])
+    mul     $t4, $t1, MAX_WORLD_SIZE
+    add     $t4, $t4, $t2
+    add     $t4, $t4, $t3
+    lb      $t4, ($t4)
+    beqz    $t4, f1skip0
+
+    li      $a0, ALIVE_CHAR             # putchar(ALIVE_CHAR);
+    li      $v0, 11
+    syscall
+    b       f1skip1
+
+
+f1skip0:
+#------------------------------------ELSE---------------------------------------
+    li      $a0, DEAD_CHAR              # putchar(DEAD_CHAR);
+    li      $v0, 11
+    syscall
+
+
+f1skip1:
+#----------------------------------ELSE_END-------------------------------------
+    add     $t2, $t2, 1                 # x++;);   (increment)
+    b       f1loop0
+f1end0:
+
+#--------------------------------FOR_LOOP_END-----------------------------------
+
+    li      $a0, '\n'                   # putchar('\n');
+    li      $v0, 11
+    syscall
+
+	jr	$ra                             # return;
+#-------------------------------END_FUNCTION_1----------------------------------
diff --git a/comp1521/cellular/reference.c b/comp1521/cellular/reference.c
new file mode 100644
index 0000000..217275f
--- /dev/null
+++ b/comp1521/cellular/reference.c
@@ -0,0 +1,218 @@
+////////////////////////////////////////////////////////////////////////
+// COMP1521 20T2 --- assignment 1: a cellular automaton renderer
+//
+// This code runs a one-dimensional, three-neighbour cellular automaton.
+// It examines its neighbours and its value in the previous generation
+// to derive the value for the next generation.
+//
+//     . . . . # . . . .
+//     . . . # # # . . .
+//     . . # # . . # . .
+//     . # # . # # # # .
+//     # # . . # . . . #
+//
+// Here, we using '#' to indicate a cell that's alive; and '.' to
+// indicate a cell that is not.
+//
+// Given we examine three neighbours, there are eight states that the
+// prior cells could be in.  They are:
+//
+//     . . .   . . #   . # .   . # #   # . .   # . #   # # .   # # #
+//       0       1       2       3       4       5       6       7
+//
+// For each one, we decide what action to take.  For example, we might
+// choose to have the following `rule':
+//
+//     . . .   . . #   . # .   . # #   # . .   # . #   # # .   # # #
+//       .       #       #       #       #       .       .       .
+//
+// We apply this rule to every cell, to determine whether the next state
+// is alive or dead; and this forms the next generation.  If we print
+// these generations, one after the other, we can get some interesting
+// patterns.
+//
+// The description of the rule above --- by example, showing each case
+// and how it should be handled --- is inefficient.  We can abbreviate
+// this rule by reading it in binary, considering live cells as 1's and
+// dead cells as 0s; and if we consider the prior states to be a binary
+// value too --- the above rule could be 0b00001110, or 30.
+//
+// To use that rule, we would mix together the previous states we're
+// interested in --- left, middle, and right --- which tells us which
+// bit of the rule value gives our next state.
+//
+// The world size, rule and the number of generations, are read from stdin:
+//
+// $ ./cellular
+// Enter world size: 60
+// Enter rule: 30
+// Enter how many generations: 10
+//
+//       0     ..............................#.............................
+//       1     .............................###............................
+//       2     ............................##..#...........................
+//       3     ...........................##.####..........................
+//       4     ..........................##..#...#.........................
+//       5     .........................##.####.###........................
+//       6     ........................##..#....#..#.......................
+//       7     .......................##.####..######......................
+//       8     ......................##..#...###.....#.....................
+//       9     .....................##.####.##..#...###....................
+//       10    ....................##..#....#.####.##..#...................
+//
+// $ ./cellular
+// Enter world size: 60
+// Enter rule: 30
+// Enter how many generations: -10
+//
+// 10   ....................##..#....#.####.##..#...................
+// 9    .....................##.####.##..#...###....................
+// 8    ......................##..#...###.....#.....................
+// 7    .......................##.####..######......................
+// 6    ........................##..#....#..#.......................
+// 5    .........................##.####.###........................
+// 4    ..........................##..#...#.........................
+// 3    ...........................##.####..........................
+// 2    ............................##..#...........................
+// 1    .............................###............................
+// 0    ..............................#.............................
+
+#include <stdio.h>
+#include <stdint.h>
+
+// maximum and minimum values for the 3 parameters
+
+#define MIN_WORLD_SIZE     1
+#define MAX_WORLD_SIZE   128
+#define MIN_GENERATIONS -256
+#define MAX_GENERATIONS  256
+#define MIN_RULE           0
+#define MAX_RULE         255
+
+// characters used to print alive/dead cells
+
+#define ALIVE_CHAR        '#'
+#define DEAD_CHAR         '.'
+
+// `cells' is used to store successive generations.  Each byte will be 1
+// if the cell is alive in that generation, and 0 otherwise.
+
+static int8_t cells[MAX_GENERATIONS + 1][MAX_WORLD_SIZE];
+
+static void run_generation(int world_size, int which_generation, int rule);
+static void print_generation(int world_size, int which_generation);
+
+int main(int argc, char *argv[]) {
+
+    // read 3 integer parameters from stdin
+
+    printf("Enter world size: ");
+    int world_size = 0;
+    scanf("%d", &world_size);
+    if (world_size < MIN_WORLD_SIZE || world_size > MAX_WORLD_SIZE) {
+        printf("Invalid world size\n");
+        return 1;
+    }
+
+    printf("Enter rule: ");
+    int rule = 0;
+    scanf("%d", &rule);
+    if (rule < MIN_RULE || rule > MAX_RULE) {
+        printf("Invalid rule\n");
+        return 1;
+    }
+
+    printf("Enter how many generations: ");
+    int n_generations = 0;
+    scanf("%d", &n_generations);
+    if (n_generations < MIN_GENERATIONS || n_generations > MAX_GENERATIONS) {
+        printf("Invalid number of generations\n");
+        return 1;
+    }
+
+    putchar('\n');
+
+    // negative generations means show the generations in reverse
+    int reverse = 0;
+    if (n_generations < 0) {
+        reverse = 1;
+        n_generations = -n_generations;
+    }
+
+    // the first generation always has a only single cell which is alive
+    // this cell is in the middle of the world
+    cells[0][world_size / 2] = 1;
+
+    for (int g = 1; g <= n_generations; g++) {
+        run_generation(world_size, g, rule);
+    }
+
+    if (reverse) {
+        for (int g = n_generations; g >= 0; g--) {
+            print_generation(world_size, g);
+        }
+    } else {
+        for (int g = 0; g <= n_generations; g++) {
+            print_generation(world_size, g);
+        }
+    }
+
+    return 0;
+}
+
+//
+// Calculate a new generation using rule and store it in cells
+//
+static void run_generation(int world_size, int which_generation, int rule) {
+    for (int x = 0; x < world_size; x++) {
+
+        // Get the values in the left and right neighbour cells.
+        // This requires some care, otherwise we could read beyond the
+        // bounds of the array.  In the cases we are at the limits of
+        // the function, we consider those out-of-bounds cells zero.
+
+        int left = 0;
+        if (x > 0) {
+            left = cells[which_generation - 1][x - 1];
+        }
+
+        int centre = cells[which_generation - 1][x];
+
+        int right = 0;
+        if (x < world_size - 1) {
+            right = cells[which_generation - 1][x + 1];
+        }
+
+        // Convert the left, centre, and right states into one value.
+        int state = left << 2 | centre << 1 | right << 0;
+
+        // And check whether that bit is set or not in the rule.
+        // by testing the corresponding bit of the rule number.
+        int bit = 1 << state;
+        int set = rule & bit;
+
+        if (set) {
+            cells[which_generation][x] = 1;
+        } else {
+            cells[which_generation][x] = 0;
+        }
+    }
+}
+
+//
+// Print out the specified generation
+//
+static void print_generation(int world_size, int which_generation) {
+    printf("%d", which_generation);
+    putchar('\t');
+
+    for (int x = 0; x < world_size; x++) {
+        if (cells[which_generation][x]) {
+            putchar(ALIVE_CHAR);
+        } else {
+            putchar(DEAD_CHAR);
+        }
+    }
+
+    putchar('\n');
+}