CS 241 — Spring 2023 — Assignment 1 / 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:

• cs241.binasm
• mips.twoints
• cs241.wordasm
• mips.stdin
• cs241.binview

You can access these tools at the links above, or use them on the student Linux environment (linux.student.cs.uwaterloo.ca). To use them on the student Linux environment, log on and type the command source /u/cs241/setup. You can add this command to your .profile file if you want to have these commands available every time you log in. Then you will be able to use the tools just by typing their name. Because the server is frequently overloaded, you should have a development environment on your own machine that does not depend on logging into the Student server. The browser-based tools will work from any system (and if the servers hosting them go down, we will put them at an alternate location).

The web-based tools are new this term. If you encounter any issues with them, ask on Piazza.

Ultimately, your code has to work on the student Linux environment, but you're strongly recommended to develop it on your own systems. None of the programs written in the class will be in any way specific to our servers, so they should behave the same way on your own system. If you're running Windows, however, you should probably get a Unix-like environment such as WSL (pronounced "weasel").

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:

• Public tests: The results of these tests are visible as soon as the tests finish running by clicking the "view" link in the "detailed test results" column on the submission log.
• Release tests: Not all problems have these tests; typically they appear in problems worth more than one mark. If a problem has release tests, once you pass the public tests, you will be given the option to view release test results. This option is on the "detailed test results" page, at the bottom. However, releasing the results costs one "release token". You get one release token per problem. After spending a release token, it will take one hour to regenerate. You are encouraged to start assignments early to get more chances to spend release tokens.
• Secret tests: These tests are completely hidden from you. You will not see any indication that they exist on Marmoset until four days after the assignment deadline, when they will become visible. (The four-day wait is to account for students who are using slip days and short-term absences to work on the assignment after the deadline.) However, the assignment specification will indicate when a problem has secret test marks, and how many marks.

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:

• Copy the value in register 1 to register 2.
• Store the two's complement encoding of -241 in register 4.
• Add the value in register 2 to the value in register 4, storing the result in register 1.
• Terminate the program by returning to the loader.

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.

Using the web tools, you can simply drag in your assembly file into cs241.binasm and the MIPS binary will be downloaded, then drag the MIPS binary into mips.twoints to run it. Using the command-line tools on the student Linux system:

$ 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.

• If the integer in register 1 divides the integer in register 2, place the value 1 in register 3.
• Otherwise, place the value 0 in register 3.

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:

• Only one file is supported, no concatenation.
• The file must be read from standard input; it cannot be passed as a command line argument.
• The kitten utility will also store the total number of bytes read from standard input in register 3 before terminating.

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:

• The data provided to the program on standard input has been replicated exactly on standard output.
• Register 3 contains the total number of bytes in the data provided on standard input.

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 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.

Using the web tools, simply enter some standard input before dragging your machine code file into mips.stdin, and its output will be shown above.

Be very careful of terminating newlines! The standard on Linux is that each line of text ends with a newline (a single "line feed" character, ASCII code 0x0a). Linux tools and text editors will typically add a newline automatically, but the text entry box in the web version of mips.stdin will not.

Using the command-line tools on the student Linux system:

$ 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

Note that the byte count is 10 ($3 = 0x0000000a) even though "Meow meow" has 9 characters. This is because when using the <<< syntax, Bash will append a newline to the end of the input string automatically.

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.

• If the number is in the range -128 to 127, output one byte to standard output representing the 8-bit two's complement encoding of the number.
• Otherwise, output one byte to standard output representing the 8-bit unsigned encoding of the number.

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

• It is a string encoded using ASCII and terminated by a line feed character (ASCII code 0x0A).
• The line feed character only appears once in the input, as the last character.
• Aside from the line feed, only these eleven ASCII characters can appear in the input: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', and '-' (minus sign).
• The '-' (minus sign) character cannot appear anywhere except as the first character of the input, and it might not appear at all.
• If the input starts with a '-' (minus sign), then it represents a decimal number in the range -128 to -1, inclusive. The first character after the '-' will never be a '0'. That is, leading zeroes in negative numbers are not allowed.
• If the input does not start with a '-' (minus sign), then it represents a decimal number in the range 0 to 255. If the first character is '0', then there are no other characters in the string, and the number represented is 0 (zero). That is, leading zeroes in positive numbers are not allowed.
• The input only represents a single number. Once you encounter the terminating line feed character, you have read all digits of the number.
• The input will not be empty, nor will it consist only of a single '-' sign. It will contain at least one digit character.

Testing

Use cs241.binasm and mips.stdin for testing.

In the web version of mips.stdin, make sure you explicitly put the required line feed (i.e., newline at the end of your input)! Using the command-line tools on the student Linux system, 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. At first, you may want to test with decimal values that have ASCII equivalents, and make sure they print as expected; for instance, 97 is 'a'. For more sophisticated testing, 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