CS 241 -- Spring 2012 -- Assignment 1

In this assignment, you will practice using the CSCF UNIX environment and begin writing very simple programs in MIPS machine language.

You must prepare and test your solutions using tools available on the CSCF Student UNIX Computing Environment. You must submit your solutions to the Marmoset automatic grading system available at https://marmoset.student.cs.uwaterloo.ca, which will run them on a number of test inputs and grade them automatically. You may submit your solutions as many times as you wish prior to the submission deadline (though the number of test runs is limited; see below). Your mark is determined entirely by the set of test inputs for which your best submission generates the correct answer.

You must test your submissions prior to submitting them to Marmoset. You should not be using Marmoset as the only means of testing your solutions.

Marmoset will test your assignment using two kinds of tests: public tests and release tests. For each problem, there is one public test input, which is included as an example in this document at the end of each problem (except Problem 8). Marmoset allows you to view the output of your code when executed with the public test input. Once your code passes the public test, you may ask Marmoset to run it on the remaining release tests. Marmoset will not show you the output from these tests, but it will tell you how many tests you passed, and the names of the first two tests that you failed. Marmoset also provides the test input for most release tests. You can use this information to fix your code and resubmit. For some problems, the test input and output of one "blind" test are never released.

To encourage you to start the assignment early, the number of release test runs that you may request for each problem is limited to three in every 12-hour period. Marmoset gives you three release test tokens for each problem. Each test run uses up one token. The token is returned to you 12 hours after the test run request.

Submission deadline: Thursday, May 10, 2012 at 10:00 pm

Important Note: For this and future assignments, be sure to enter the command source /u/cs241/setup to gain access to the CS 241 tools.

Part I. Getting Started

Read and work through Unix - The Bare Essentials. You may, for additional context, wish to read the CSCF Getting Started with UNIX guide or the Introduction to X and UNIX Tutorial.

In the CSCF UNIX environment, use the command vimtutor to start a tutorial about the vim editor.

Use the vim editor (or its graphical equivalents gvim or evim) to create a file called hello.txt that contains the following two lines: 

Hello
from Unix

You may check to see that you have done this correctly by viewing the file using the Unix command cat as described in Unix - The Bare Essentials. You may further check your file using the Unix command wc which lists the number of lines, the number of words, and the number of characters in the file: 

% wc hello.txt
      2       3      16 hello.txt

Problem 1 (7 marks of 60)(filename: hello.txt)

When you are satisfied that your file hello.txt contains exactly the text above, submit it to Marmoset for grading as problem 1. Note that the filename must be hello.txt, not HELLO.TXT. In general, files submitted to Marmoset must have exactly the name specified in the problem statement, including the same use of upper and lower case letters.

Problem 2 (7 marks of 60)(filename: wget.txt)

The wget command (short for "web get") is useful for downloading a file from a URL on the World Wide Web into your local directory. Further details about wget are available by executing the command man wget. (The command man (short for "manual") displays information information about a Unix command (its "man page"). Try, for example, man wc to learn more about the word count command. man will display the document one screen at a time. Hit the spacebar to advance to the next screen.)

You will find wget useful throughout this term; whenever we provide starter files for assignments, wget provides a convenient means of fetching these into your working directory.

Use the wget command to fetch this document (the one you are reading right now) from the World Wide Web into your local Unix directory. Then rename the file to wget.txt and submit it to Marmoset.

Part II. Creating binary files with cs241.wordasm

We have provided the tool cs241.wordasm that may be used to create a file whose binary content is specified using hexadecimal notation. cs241.wordasm reads the hexadecimal representation of several 32-bit words on standard input. On standard output, it outputs a file containing, for each of the input words, the four bytes containing the 32 bits represented by the word (8 bits per byte). On each line of input, any characters after a semicolon (;) are assumed to be comments and ignored. Example: 
% cat > input
.word 0x43533234  ; C(43) S(53) 2(32) 4(34)
.word 0x3120726f  ; 1(31) space(20) r(72) o(6f)
.word 0x636b730a  ; c(63) k(6b) s(73) newline(0a)
% java cs241.wordasm < input
CS241 rocks
% java cs241.wordasm < input > output
% xxd < output
0000000: 4353 3234 3120 726f 636b 730a            CS241 rocks.
Note that the xxd Unix command shows the contents of the file both as hexadecimal numbers and as ASCII characters.

Problem 3 (8 marks of 60) (filename: helloworld.hex)

Write a hexadecimal representation (using the .word notation) of a file with exactly the same content as hello.txt submitted for problem 1. You may find it useful to use the UNIX command man ascii to get an ASCII code chart. Before submitting to Marmoset, run the cs241.wordasm tool with your solution as standard input to check that your output is identical to hello.txt.

Unix includes a command, diff, to compare two files. Try it!

Part III. MIPS Machine Language Programming

The mips.twoints tool loads a MIPS machine language program from a file into memory starting at location 0. It then reads two integers, stores them into registers 1 and 2, runs your program, and, when your program returns to the instruction whose address is stored in register 31, prints the values of all the registers and exits. Run this tool using the command java mips.twoints mycode.mips, replacing mycode.mips with the name of a file containing your machine code.

Since MIPS machine language is encoded in binary, not text, you cannot create it directly using an editor like vim. You must specify your machine language program in hexadecimal and use cs241.wordasm to translate it to (binary) machine language.

For each of the following problems, create the hexadecimal representation of a MIPS machine language program that solves the problem. Test your program using cs241.wordasm and mips.twoints as follows: 

% vim mycode.hex
% java cs241.wordasm < mycode.hex > mycode.mips
% java mips.twoints mycode.mips
Enter value for register 1: 1
Enter value for register 2: 2
Running MIPS program.
...

Each problem specifies a filename for the file that you will submit. You must use the specified filename for the testing scripts to work correctly.

Scratch registers used to hold temporary results may be used and do not need to be set back to 0.

Problem 4 (8 marks of 60) (filename: a1p4.hex)

Write the hexadecimal notation for a MIPS machine language program that returns to the address saved in register 31. This is the only thing your program should do.

Example of running the program: 

Enter value for register 1: 1
Enter value for register 2: 2
Running MIPS program.
MIPS program completed normally.
...

Problem 5 (8 marks of 60) (filename: a1p5.hex)

Write the hexadecimal notation for a MIPS machine language program that copies the value in register 1 to register 3, then adds the values in register 1 and 3 placing the result in register 4 and then returns.

Example of running the program: 

Enter value for register 1: 2
Enter value for register 2: 3
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000002   $02 = 0x00000003   $03 = 0x00000002   $04 = 0x00000004   
...

Problem 6 (8 marks of 60) (filename: a1p6.hex)

Write the hexadecimal notation for a MIPS machine language program that determines the maximum of the values in registers 1 and 2 interpreted as two's complement integers, places it in register 3, and returns.

Example of running the program: 

Enter value for register 1: 3
Enter value for register 2: 5
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000003   $02 = 0x00000005   $03 = 0x00000005   $04 = 0x00000001   
...

Problem 7 (7 marks of 60) (filename: a1p7.hex)

Write the hexadecimal notation for a MIPS machine language program that adds 1 to the value in register 1 placing the result in register 3 and then returns.

Example of running the program: 

Enter value for register 1: 2
Enter value for register 2: 5
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000002   $02 = 0x00000005   $03 = 0x00000003 ...

Problem 8 (7 marks of 60) (filename: a1p8.hex)

Write the hexadecimal notation for a MIPS machine language program that interprets the value in register 1 as the address of a word in memory, and places the address of the following word in memory in register 3 and then returns.