CS 241 — Summer 2024 — Assignment 1 / Out of 10 marks

In this assignment, you will write short machine code programs with arithmetic and memory access.

You will use two tools in this assignment: cs241.wordasm, and mips.twoints.

The cs241.wordasm (web version) tool is a mips assembler that only supports the .word directive. It is the same as the cs241.binasm tool, but it will reject your program if you use any other assembly instruction. To write your machine code, first determine the binary encoding of an instruction. For example:

      1010 1010 1010 1010 0101 0101 0101 0101

Translate the instruction to a hexadecimal value:

      0xAAAA5555

And in your assembly file, we write this hexadecimal value as:

      .word 0xAAAA5555

You will use the cs241.wordasm tool in problems 1, 2, 3, 4, and 5.

The mips.twoints (web version) tool loads a MIPS program from a binary file into memory starting at location 0. It then reads two integers, stores them into registers $1 and $2, and runs your program. When your program returns to the instruction whose address is stored in register $31, prints the values of all the registers and exits. You will use the mips.twoints tool for problems 1, 2, 3, 4, and 5. Run this tool using the command mips.twoints $FILE_NAME, replacing $FILE_NAME with the name of a file containing your machine code.

You can access these tools as a web application on the course website, 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, but we cannot guarantee 100% availability of the browser-based tools.

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 at the beginning. After spending a release token, it will take twelve hours to regenerate; in total you will obtain three release tokens at most for each question. 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: Return to Loader [1 mark: 1 public / 0 release / 0 secret] (filename: jr31.hex)

Write a MIPS program in machine code that returns to the address saved in register $31.

To test your program, first use the cs241.wordasm tool to assemble your program. Then use mips.twoints to run your assembled program. Using the command-line tools on the student Linux system:

$ cs241.wordasm < jr31.hex > jr31.mips
$ mips.twoints jr31.mips
Enter value for register 1: 0
Enter value for register 2: 0
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000000   $02 = 0x00000000   $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

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

Problem 2: Add Two Numbers [1 mark: 1 public / 0 release / 0 secret] (filename: add.hex)

Write a mips program in machine code that adds the value in register $1 to the value in register $2, places the sum in register $3, and returns.

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

Problem 3: Multiplication [1 mark: 1 public / 0 release / 0 secret] (filename: mult.hex)

Register $1 and register $2 hold signed integer values. Write a mips program in machine code that multiplies the values in registers $1 and $2, and puts the result in register $3. Assume that -(2^31) ≤ $1 * $2 < 2^31.

Enter value for register 1: 2
Enter value for register 2: 3
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000002   $02 = 0x00000003   $03 = 0x00000006   $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

Problem 4: 2*$1 + 1 [1 mark: 1 public / 0 release / 0 secret] (filename: 2x-1.hex)

Register $1 holds a signed 2s-complement 32-bit integer. Write a mips program in machine code that multiplies the value in register $1 by 2, and adds 1. Put the result in register $3. Assume that -(2^31) ≤ 2*$1+1 < 2^31.

Enter value for register 1: 2
Enter value for register 2: 3
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000002   $02 = 0x00000001   $03 = 0x00000005   $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

Problem 5: Self Modifying Code [2 marks: 1 public / 1 release / 0 secret] (filename: self-modifying.hex)

Register $1 holds an integer >= 0 and < 31. Let's call the value in $1 is x. Do not modify the value in register $2.

The last two instructions in your program must be:

• Add the value of $0 to $2 and put the result in $0
• Return to the address stored in register $31

Write a mips program in machine code that modifies the second last instruction. Instead of adding $0 to $2 and putting the result in $0, it will add $0 to $2 and put the result in $x.

Enter value for register 1: 19
Enter value for register 2: 0xAAAA5555
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000013   $02 = 0xaaaa5555   $03 = 0x00020020   $04 = 0x00000800   
$05 = 0x00029820   $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 = 0xaaaa5555   $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 6: Assembler Machine Code Generation [4 marks: 0 public / 1 release / 3 secret] (filename: asm.cpp xor asm.rkt)

Updates and Clarifications

• The asm.cpp c++ starter code was patched to add missing entries for multu and lis. (13 May)
• Specifically noted that the .word directive is not implemented in the starter code, and support for it does not need to be add. .word is not used in any of the test cases on Marmoset. (16 May)

You will write a code generator for a simple mips assembler.

You may use c++ xor racket to complete this assignment.

Starter code is provided. The starter code implements a trivial scanner. This scanner is sufficient for this assignment, but is ineffective for any language more complex than our mips assembly language. Do all of your work in the starter file provided, it is the file you will submit to Marmoset.

• c++: asm.cpp
• racket: asm.rkt

If you use the c++ starter code, you can compile the code with:

      g++ -g -O0 -fPIC -std=gnu++20 -Wall -Wextra -pedantic-errors -Wno-unused-parameter -o asm asm.cpp

And run the code with:

      ./asm < input.asm

If you use the racket starter code, you can run the code with:

      racket asm.rkt < input.asm

You are not required to use the starter code, and you are allowed to change the starter code in any way you see fit. However, the starter code does not purposefully contain any bugs or issues that will cause you to lose marks on this assignment. We strongly recommend that you use the starter code and do not modify it, other than adding your implementation of compileLine.

We will not reuse the starter code in future assignments.

The input to the assembler will have each assembly instruction on only one line.

All immediate values are specified as positive values.

Your assembler does not have to handle labels.

You will implement a compileLine function. The function takes a string indicating which assembly instruction you are compiling, plus each parameter for the instruction. If the assembly instruction takes only one parameter, then parameters two and three are set to 0. If the assembly instruction takes two parameters, then parameter three is set to 0.

In c++, compileLine is defined as:

      /** For a given instruction, returns the machine code for that instruction.
       *
       * @param[out] word The machine code for the instruction
       * @param instruction The name of the instruction
       * @param one The value of the first parameter
       * @param two The value of the second parameter, 0 if the instruction has < 2 parameter
       * @param three The value of the third parameter, 0 if the instruction has < 3 parameter
       */
       bool compileLine(uint32_t &          word,
                        const std::string & instruction,
                        uint32_t            one,
                        uint32_t            two,
                        uint32_t            three)
       {
           word = 0;
           // Your implementation goes here!
           return true;
       }

In racket, compileLine is defined as:

      #| For a given instruction, returns the machine code for that instruction.
       *
       * @param instruction The name of the instruction
       * @param one The value of the first parameter
       * @param two The value of the second parameter, 0 if the instruction has < 2 parameter
       * @param three The value of the third parameter, 0 if the instruction has < 3 parameter
       *
       * Raises an exception if the encoding is invalid.
      |#
      (define (compile-line instruction one two three) 0) ; Your implementation goes here

We are providing a combination scanner and tokenizer. You can assume that all input to the assembler will scan and tokenize successfully, and that for every line of input, the compileLine function will be invoked properly.

You can use the xxd or the cs241.binview (web version) command in Unix to convert your binary output back to hexadecimal so you can read it.

      $ echo "jr \$0" | ./asm | xxd
      00000000: 0000 0008                                ....

In any case where the input is not a valid assembly program, your assembler should print an appropriate error message to standard error indicating the nature of the problem. Each error message must start with the string ERROR: (in all capital letters, followed by a colon), and end with a newline. When an error occurs, your program must not print any additional output on standard out. If more than one error is present in an assembly instruction, more than one error can be printed, but only one error has to be printed.

You only need to identify errors in the values of parameters one, two, or three.

Your assembler should not crash in any ways, even if the input is not a valid assembly language program. Your assembler should not silently ignore errors in the input program. c++ solutions cannot leak resources.

The output of your program should be a valid mips program (or the empty mips program), potentially with one or more error message on standard error.

You do not need to support the .word directive. The starter code doesn't check for the .word directive. None of the test cases on Marmoset use .word.

After implementing a few instructions, it would be wise to look ahead and consider what early design decisions will have a positive effect on the remainder of instructions.

The instructions you need to implement are: