COMP1521 Computer Systems Fundamentals - Assignment 1: Nonograms in MIPS
Assignment 1: Nonograms in MIPS
version: 1.0 last updated: 2024-09-25 11:30:00
Aims
- to give you experience writing MIPS assembly code
- to give you experience translating C to MIPS
- to give you experience with data and control structures in MIPS
Getting Started
Create a new directory for this assignment called nonograms, change to this directory, and fetch the provided code by running these commands:
mkdir -m 700 nonograms cd nonograms 1521 fetch nonograms
If you're not working at CSE, you can download the provided files as a zip file or a tar file.
This will add the following files into the directory:
nonograms.s: a stub MIPS assembly file to complete.nonograms.c: a reference implementation of nonograms in C.nonograms.simple.c: a copy of the reference implementation of nonograms, for you to simplify.input.txt: example input file.nonograms.mk: a make fragment for compilingnonograms.c.
Nonograms: The Puzzle
1521 mipsy nonograms.s Enter the height: 3 Enter the width: 3 Enter solution: 1 1 -1 -1 Loaded 1 solution coordinates 1 ABC a... 1 b... c... >> m Enter first coord: b Enter second coord: B Enter choice (# to select, x to cross out, . to deselect): # 1 ABC a... 1 b.#. c... Congrats, you won!
nonograms.c is an implementation of a program to play nonograms (also known as Picross).
A nonogram puzzle takes place on a 2D grid, where the player must mark a set of cells, according to number clues placed on the edge of the puzzle.
Each row and column contains a sequence of numbers which correspond to the correct lengths of consecutive runs of marked cells in that row/column. For example, the numbers 2 3 1 mean that row/column has a run of 2 marked cells, then 3 marked cells, then 1 marked cells, with gaps of at least one cell between them.
The m commands allows the player to mark, unmark or cross out (indicate that the cell should definitely be unmarked) a cell based on the row (lowercase letter) and column (uppercase letter).
An example game of nonograms can be seen to the right.
To get a feel for this game, try it out in a terminal:
dcc nonograms.c -o nonograms ./nonograms
You should read through nonograms.c. There are comments throughout it that should help you understand what the program is doing [citation needed] — which you'll need for the next part of the assignment.
Online player
The following is an online version of the game which you may find useful to help understand the game mechanics, as well as to create your own puzzles (you can copy-paste the output of the Current grid box).
If you happen to create any fun/difficult puzzles feel free to post them on the course forum.
nonograms.s: The Assignment
Your task in this assignment is to implement nonograms.s in MIPS assembly.
You have been provided with some assembly and some helpful information in nonograms.s. Read through the provided code carefully, then add MIPS assembly so it executes exactly the same as nonograms.c.
The functions get_command and dump_game_state have already been translated to MIPS assembly for you.
You have to implement the following functions in MIPS assembly:
mainprompt_for_dimensioninitialise_gamegame_loopdecode_coordinateread_solutionlookup_cluecompute_all_cluesmake_moveprint_gamecompute_clueis_game_over
You must translate each function separately to MIPS assembler, following the standard calling conventions used in lectures. When translating a function, you must not make any assumptions about the behaviour or side effects of any function which is called.
Subsets
This assignment is split into three subsets. Later subsets will involve more complex translation.
| Subset | Functions | Performance Weight |
|---|---|---|
| Subset 1 |
| 45% |
| Subset 2 |
| 30% |
| Subset 3 |
| 25% |
The performance mark for the final subset also includes tests which run the program as a whole.
Commands
The get_command function calls various other functions. When translating you should follow the exact behaviour of the C code, however when testing you may find it useful to consult the following table of commands.
| Command | Description | Function called |
|---|---|---|
| m | Allow the player to make a move | make_move |
| q | Exit the program | |
| d | Output debugging information | dump_game_state |
| s | Display clue numbers for the current selection | |
| S | Display clue numbers for the solution | |
| ? | Show the solution grid (for cheating) | print_game |
Running & Testing
To run your MIPS code, simply enter the following in your terminal:
1521 mipsy nonograms.s
Once you have finished your translation, to test your implementation, you can compile the provided C implementation, run it to collect the expected output, run your assembly implementation to collect observed output, and then compare them.
The game takes a lot of input, so it's a good idea to write a file with the input you want to test, and then pipe that into your program.
You have been given a file called input.txt as an example.
dcc nonograms.c -o nonograms cat input.txt | ./nonograms | tee c.out cat input.txt | 1521 mipsy nonograms.s | tee mips.out diff -s c.out mips.out Files c.out and mips.out are identical
Try this for different sequences of inputs. When testing some functions you may find using the d command (which calls dump_game_state) to be useful.
Hints
You should implement all the functions from one subset before moving on to the next.
You may find the provided
get_command, anddump_game_statefunction implementations to be useful guidance for your implementation including comments, label names, indentation and register usage.
Simplified C code
You are encouraged to simplify your C code to remove any loop constructs and if-else statements, and test that your simplified code works correctly before translating it to MIPS, in a separate file nonograms.simple.c.
This file will not be marked - you do not need to submit it.
In order to allow you to check that your simplified code works correctly, we have provided a simple set of automated tests.
You can run these tests by running the following command:
1521 autotest nonograms.simple
Assumptions, Clarifications, and Restrictions
Like all good programmers, you should make as few assumptions as possible.
Your submitted code must be hand-written MIPS assembly, which you yourself have written.
You may not submit code in other languages.
You may not submit compiled output.You may not copy a solution from an online source. e.g. Github.
Your functions will be tested individually. They must exactly match the behaviour of the corresponding C function and they must follow MIPS calling conventions.
You may assume the input provided to
nonograms.swill be correctly formatted. For example, where a number is expected the input will not be a letter.The C code defines constants using
#define. Your MIPS translation should use the corresponding provided named constants, in the places where a#defineis used in the C code. You should not use a#defineconstant in your MIPS translation if it is not used in the corresponding part of the C code.There will be a correctness penalty for assignments that do not follow standard MIPS calling conventions including:
Function arguments are passed in registers
$a0..$a3.Function return values are passed in register
$v0Values in registers
$s0..$s7are preserved across function calls.
If a function changes these registers, it must restore the original value before returning.The only registers' values that can be relied upon across a function call are
$s0..$s7,$gp,$sp, and$fp.
All other registers must be assumed to be have, an undefined value after a function call, except$v0which has the function return value.
If you need clarification on what you can and cannot use or do for this assignment, ask in the class forum.
You are required to submit intermediate versions of your assignment. See below for details.
