Question 3

Deadline	Friday, September 22, 11:59pm
Name on Marmoset	Q3A, Q3B
To Submit	Q3A: `hello241.card` Q3B: `die.card`
Marking Scheme	Q3A: 50% Q3B: 50%

MIPS Machine Language Programming

In the early days of computing, punched cards were used to specify programs. These can be thought of as a binary data format where the two possible states are "hole punched" and "hole not punched". These holes would be used to control the presence or absence of electrical signals, and these electrical signals were the "machine language", the patterns of "0s and 1s" that control the computer's behaviour.

In this assignment, you will create your own "digital punched cards" by typing 0s and 1s into a text file. Then, you will use cs241.bits (or the program you wrote in From Characters to Bits) to convert your "card" to an actual MIPS machine language program, which can be run on the mips.twoints MIPS emulator.

Creating and Executing a MIPS Machine Language Program

Here is an example of a "card" describing a simple machine language program. The program loads a binary value (the unsigned representation of the decimal number 241) into register $1, then returns by jumping to the return address stored in register $31.

00000000000000000000100000010100
00000000000000000000000011110001
00000011111000000000000000001000

Unlike on actual punched cards, you can include spacing for readability, since cs241.bits will ignore any characters other than 0s and 1s. For example, it would be valid to write the above program like this:

000000 00000 00000 00001 00000 010100
00000000 00000000 00000000 11110001
000000 11111 00000 00000 00000 001000

However, if you try to load either of the above "cards" directly into mips.twoints, it will not understand the meaning of all these ASCII characters and it will crash. The machine only understands machine language. First, run the file through cs241.bits:

cs241.bits < program.card > program.mips

The file program.mips now contains actual MIPS machine code that the MIPS emulator can understand. Pass this file to mips.twoints as a command line argument (not using redirection):

mips.twoints program.mips

The mips.twoints emulator will ask you for two integers as input, which will be placed in $1 and $2 before the program starts. Here is an example.

mips.twoints program.mips
Enter value for register 1: 1
Enter value for register 2: 2
Running MIPS program.
MIPS program completed normally.
$01 = 0x000000f1   $02 = 0x00000002   $03 = 0x00000000   $04 = 0x00000000
$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

Notice that $1 contains 0xf1 (241 in decimal) as a result of running the program, while $2 still contains the original value of 2 that we entered, because it was not modified by the program.

MIPS Machine Language Reference

The table below describes some of the instructions available in MIPS machine language. Not all available instructions are shown, but the instructions below are sufficient to complete the question.

Register Format Instructions
Instruction Opcode Register $s Register $t Register $d Unused Function Behaviour

Add 000000 sssss ttttt ddddd 00000 100000 $d = $s + $t

Subtract 000000 sssss ttttt ddddd 00000 100010 $d = $s - $t

Load Immediate & Skip 000000 00000 00000 ddddd 00000 010100 $d = MEM[PC]; PC += 4

Jump Register 000000 sssss 00000 00000 00000 001000 PC = $s

Immediate Format Instructions
Instruction Opcode Register $s Register $t Immediate i Behaviour

Load Word 100011 sssss ttttt iiii iiii iiii iiii $t = MEM[$s + i]

Store Word 101011 sssss ttttt iiii iiii iiii iiii MEM[$s + i] = $t

Register Format Instructions
Instruction	Opcode	Register $s	Register $t	Register $d	Unused	Function	Behaviour
Add	000000	sssss	ttttt	ddddd	00000	100000	$d = $s + $t
Subtract	000000	sssss	ttttt	ddddd	00000	100010	$d = $s - $t
Load Immediate & Skip	000000	00000	00000	ddddd	00000	010100	$d = MEM[PC]; PC += 4
Jump Register	000000	sssss	00000	00000	00000	001000	PC = $s
Immediate Format Instructions
Instruction	Opcode	Register $s	Register $t	Immediate i	Behaviour
Load Word	100011	sssss	ttttt	iiii iiii iiii iiii	$t = MEM[$s + i]
Store Word	101011	sssss	ttttt	iiii iiii iiii iiii	MEM[$s + i] = $t

Part A: Hello 241 (50% of question mark)

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

Copy the value in $1 to $2.
Store the two's complement encoding of -241 in $4.
Add the value in $2 to the value in $4, storing the result in $1.
Flip the bits of the value in $2. (Change all 0 bits to 1 bits, and all 1 bits to 0 bits)
Return to the loader.

Submit the "program card" to Marmoset (the text file with 0s and 1s, not the actual machine language file) with the filename: hello241.card

Clarifications

After the program ends, we will check that the values in $2, $4, and $1 are correct, and that your program completed normally (didn't crash with an error). The values in other registers do not matter. So, you are free to use other registers for temporary values if needed.

Example

cs241.bits < hello241.card > 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 = 0xffffff0e   $03 = 0x00000000   $04 = 0xffffff0f
$05 = 0x00000000   $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 = 0x00000000
$21 = 0x00000000   $22 = 0x00000000   $23 = 0x00000000   $24 = 0x00000000
$25 = 0x00000000   $26 = 0x00000000   $27 = 0x00000000   $28 = 0x00000000
$29 = 0x00000000   $30 = 0x01000000   $31 = 0x8123456c

Explanation:

$1 contains zero because it contained 241 at the start, then we copied the value 241 into $2, then added $2 to the value in $4 (which is -241) and stored the result (zero) in $1.
$2 contains 0xffffff0e which is 1111 1111 1111 1111 1111 1111 0000 1110 in binary. This is because we copied 241 into $2, and 241 is 0000 0000 0000 0000 0000 0000 1111 0001 in binary. After flipping the bits we get the final value of $2.
$4 contains 0xffffff0f which is the hexadecimal version of the 32-bit two's complement representation of -241.
The values of other registers do not matter as long as $1, $2 and $4 are correct. For other registers, your values may differ from the ones shown above depending on how you implement some of the steps.

Part B: Dynamic Instruction Execution (50% of question mark)

Write a MIPS machine language program that interprets the value in $1 as a MIPS instruction, executes this instruction, then returns.

Assume: The program will be loaded at address 0.
Assume: The instruction in $1 will not crash the MIPS machine when executed, and will not modify PC or $31.
Restriction: Outside of the step where the instruction in $1 is executed, the program must not modify general-purpose registers ($1 to $31).

Submit the "program card" to Marmoset (the text file with 0s and 1s, not the actual machine language file) with the filename: die.card

Clarifications

After the program ends, we will check the values of registers that are modified by the instruction in $1 to verify that you actually executed the instruction. We will also check the values of general-purpose registers that are not modified by the instruction in $1, to ensure your program doesn't modify them.

Example

The MIPS instruction 00000000010000100001000000100000 doubles the value in $2. We can write this binary word in hexadecimal as 0x00421020.

cs241.bits < die.card > die.mips
mips.twoints die.mips
Enter value for register 1: 0x00421020
Enter value for register 2: 2
Running MIPS program.
MIPS program completed normally.
$01 = 0x00421020   $02 = 0x00000004   $03 = 0x00000000   $04 = 0x00000000
$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