CS 241 — Spring 2022 — Assignment 1

Due Friday, May 20, 5:00pm / Out of 10 marks

In this assignment, you will write short assembly language programs involving arithmetic, branches, loops, and input/output.

You will make use of various tools available on the student Linux enviroment (linux.student.cs.uwaterloo.ca):

To access these tools, log on and type the command source /u/cs241/setup. Then you will be able to use the tools just by typing their name. They do not get copied into a folder, they are simply accessible from anywhere on the system after you run the setup command. However, you must run the setup command every time you log in, unless you set it up to run automatically.

You will submit your solutions to Marmoset, which will run your solution against some automated tests. Each problem specifies a required filename that you must use for your Marmoset submission.

There are three kinds of tests:

The source /u/cs241/setup command also gives you access to marmoset_submit, a command line tool for submitting to Marmoset, which you may find useful.

Problem 1: Hello 241 (filename: hello241.asm) [1 mark]

Write a MIPS assembly program that performs the following steps, in order:

Testing

To test your program, first use the cs241.binasm tool to assemble your program. Then use mips.twoints to run your assembled program with different initial values of registers 1 and 2. Ensure that registers 2, 4 and 1 have the expected values, and that the MIPS emulator prints "MIPS program completed normally" rather than an error message.

$ cs241.binasm < hello241.asm > hello241.mips
$ mips.twoints hello241.mips
Enter value for register 1: 241
Enter value for register 2: 0
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000000   $02 = 0x000000f1   $03 = 0x00000000   $04 = 0xffffff0f
$05 = 0x00000000   $06 = 0x00000000   $07 = 0x00000000   $08 = 0x00000000
$09 = 0x00000000   $10 = 0x00000000   $11 = 0x00000000   $12 = 0x00000000
$13 = 0x00000000   $14 = 0x00000000   $15 = 0x00000000   $16 = 0x00000000
$17 = 0x00000000   $18 = 0x00000000   $19 = 0x00000000   $20 = 0x00000000
$21 = 0x00000000   $22 = 0x00000000   $23 = 0x00000000   $24 = 0x00000000
$25 = 0x00000000   $26 = 0x00000000   $27 = 0x00000000   $28 = 0x00000000
$29 = 0x00000000   $30 = 0x01000000   $31 = 0x8123456c

Problem 2: Hello 0xf1 (filename: hello0xf1.asm) [1 mark]

Write a MIPS assembly program that performs the same steps as the "Hello 241" program from the previous problem, but only uses the .word directive.

Testing

To assemble your program, you should use cs241.wordasm, a special restricted MIPS assembler that only supports .word directives. It works the same as cs241.binasm but will reject your program if it uses any MIPS assembly features other than .word directives.

Marmoset will use cs241.wordasm to assemble your program, so your program will be rejected by Marmoset if it uses disallowed features.

Problem 3: The Divides Relation (filename: divides.asm) [3 marks, 1 secret]

An integer m divides an integer n if there exists an integer k such that n = km.

Write a MIPS program that interprets the values in register 1 and register 2 as unsigned integers.

Then terminate the program by returning to the loader.

Remark: There are no errors or omissions in the definition of divides given above. For example, the Spring 2018 MATH 135 Course Notes use the same definition (page 47).

Testing

Test your program with cs241.binasm and mips.twoints. Ensure that register 3 is correct and no errors occur.

Problem 4: The Kitten Utility (filename: kitten.asm) [2 marks]

In this problem, we will write a simpler version of the Unix utility cat. This utility can be used to display the contents of files on the command line, and also allows you to concatenate multiple files together.

Our version will be called kitten and it will have the following differences and limitations:

To be more precise, you are to write a MIPS program that terminates normally (without errors), such that the following things are true when the program terminates:

Input & Output in MIPS

Input: If you load (with lw) from the special address 0xffff0004, MIPS will read one byte (8 bits) from standard input and store the byte in the destination register (padded with 0s to turn it into a 32-bit word). If there are no bytes left to read (the “end of file” is reached) then the destination register will contain 0xffffffff (the two's complement encoding of -1).

Output: If you store (with sw) to the special address 0xffff000c, MIPS will take the least significant byte (rightmost 8 bits) of the source register and write this byte to standard output.

Testing

Testing this program is easiest with mips.stdin. This is a variant of mips.twoints that is suitable for testing programs that use standard input rather than taking input in registers.

Assemble with cs241.binasm as usual, then run the assembled program with mips.stdin.

$ cs241.binasm < kitten.asm > kitten.mips
$ mips.stdin kitten.mips

If you do not provide any input (as above), your MIPS program will take input via the terminal. To indicate that you're done entering input, press Ctrl+D when the cursor is on a blank line. If there's stuff on the line, you will need to hit Enter first, then Ctrl+D.

You can also provide input from a file via redirection:

$ mips.stdin kitten.mips < input.txt

Or provide a short input string directly as follows:

$ mips.stdin kitten.mips <<< "Meow meow"
Running MIPS program.
Meow meow
MIPS program completed normally.
$01 = 0x00000000   $02 = 0x00000000   $03 = 0x0000000a   $04 = 0x00000000
$05 = 0xffffffff   $06 = 0x00000000   $07 = 0x00000000   $08 = 0x00000000
$09 = 0x00000000   $10 = 0x00000000   $11 = 0x00000001   $12 = 0x00000000
$13 = 0x00000000   $14 = 0x00000000   $15 = 0x00000000   $16 = 0x00000000
$17 = 0x00000000   $18 = 0x00000000   $19 = 0x00000000   $20 = 0xffff000c
$21 = 0xffff0004   $22 = 0xffffffff   $23 = 0x00000000   $24 = 0x00000000
$25 = 0x00000000   $26 = 0x00000000   $27 = 0x00000000   $28 = 0x00000000
$29 = 0x00000000   $30 = 0x01000000   $31 = 0x8123456c

As you can see, the output will be mixed in with the information the MIPS emulator prints about the registers. To suppress the MIPS emulator information, you can redirect standard error to /dev/null as follows:

$ mips.stdin kitten.mips <<< "Meow meow" 2> /dev/null
Meow meow

You may also want to redirect standard output to a file, as follows:

$ mips.stdin kitten.mips < input.txt > output.txt

The file output.txt will contain the contents of standard output, without any MIPS register information. You can then compare it to input.txt with diff to see if there are any differences (there should not be):

$ diff input.txt output.txt

Finally, you can check that the number of bytes in register 3 is correct using the wc command:

$ wc -c < input.txt

This will print the number of bytes in decimal (note that mips.stdin displays register values in hexadecimal).

Problem 5: Reading Decimal Numbers (filename: decimal.asm) [3 marks, 1 secret]

When you write something like .word -241 in a MIPS program, the assembler, cs241.binasm, will convert it to the 32-bit two's complement binary representation of -241 as it translates your program to machine code. But how does this conversion process work?

In this problem, you will implement this conversion process, but only for 8-bit numbers to keep things simple.

Write a MIPS program that reads an ASCII string, representing a decimal number in the range -128 to 255 followed by a newline, from standard input.

Finally, terminate the program and return to the loader.

Clarifications

Your program can assume the following about the input received on standard input:

You will not receive input that does not meet these specifications, and no error checking is required.

Testing

Use cs241.binasm and mips.stdin for testing.

The easiest way to test is probably to use the Bash <<< syntax for providing short strings as standard input. This syntax will automatically append the required line feed character.

$ mips.stdin decimal.mips <<< "241" > output.bin

Verifying the output is correct is a bit tricky. If you send the single byte of output to the terminal, it will try to interpret it as text, which could lead to confusing output. Instead, redirect output to a file as above, and use cs241.binview to view the output byte in a human-readable form:

$ cs241.binview output.bin
11110001