Assignments for CS241
Due Friday, January 23rd, 5:00 PM
In this assignment, you will write short machine code programs with arithmetic and memory access. You will also complete a rudimentary assembler for ARM64.
You will use two tools in this assignment: cs241.wordasm, and cs241.arm64emu. Details of how to use and setup the tools will be provided below.
The cs241.wordasm (web version) tool is an ARM64 assembler that only supports the .8byte directive (in addition to comments). It is functionally 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, say you want to encode the instruction sub x0, x3, x1, which corresponds to the following bit pattern (in big-endian)
[11001011 001] [00001] [011000] [00011] [00000]
Opcode xm (1) Flags xn (3) xd (0)
Then, you must translate the individual bytes of the instruction to a hexadecimal value:
Bin: 11001011 00100001 01100000 01100000
Hex: CB 21 60 60
And in your assembly file, we write this hexadecimal value as:
.8byte 0xCB216060
Although the value itself is written in big-endian, the .8byte directive will encode it in little-endian format when assembling the program. Thus, the assembled binary file will contain the bytes 60 60 21 CB in that order, if viewed using a tool like xxd or cs241.binview.
Since each .8byte instruction encodes an 8 byte little-endian value at a time, and each individual instruction only occupies 4 bytes, instructions must be grouped together in pairs. Otherwise, you may end up with zero padding which doesn't form a valid instruction. As an example, if you have an instruction encoded as 0x8B216060 followed by an instruction encoded as 0xDEADBEEF, you would need to write it on a single line as
.8byte 0xDEADBEEFCB216060
As opposed to
.8byte 0xCB216060 // Implicitly codes the raw value 0 after the instruction, which may cause it to crash!;
.8byte 0xDEADBEEF
This may seem rather counter-intuitive, as you seemingly encode the second instruction before the first. Remember, in little-endian, the least-significant bytes come first, so the instruction that appears to be second (as written in big-endian) is actually first.
You will use the cs241.wordasm tool in problems 1 through 5.
The cs241.arm64emu (web version) tool loads an ARM64 program from a binary file into memory starting at location 0. It then preloads a list of user-provided numbers into the ARM64 registers sequentially. You will use this tool for problems 1 through 5. Run the tool using the command cs241.arm64emu $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 .bashrc 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 (unless the web server is down, of course).
Ultimately, your code has to work on the student Linux environment, so you will still likely have to use the student environment for testing. However, we strongly recommended to develop your programs on your own systems. None of the programs written in 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:
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.
br30.hex)Write an ARM64 program in machine code that branches to the address saved in register x30 (the link register).
To test your program, first use the cs241.wordasm tool to assemble your program. Then use cs241.arm64emu to run your assembled program. Using the command-line tools on the student Linux system:
$ cs241.wordasm < br30.hex > br30.arm
$ cs241.arm64emu br30.arm
x0: 0x0 x16: 0x0
x1: 0x0 x17: 0x0
x2: 0x0 x18: 0x0
x3: 0x0 x19: 0x0
x4: 0x0 x20: 0x0
x5: 0x0 x21: 0x0
x6: 0x0 x22: 0x0
x7: 0x0 x23: 0x0
x8: 0x0 x24: 0x0
x9: 0x0 x25: 0x0
x10: 0x0 x26: 0x0
x11: 0x0 x27: 0x0
x12: 0x0 x28: 0x0
x13: 0x0 x29: 0x1000000
x14: 0x0 x30: 0xfffffe4
x15: 0x0 sp: 0x1000000
pc: 0xfffffe4 instr: hlt
flags: vczn
Program exited normally.
Alternatively, using the web tools, you can simply drag in your assembly file into
cs241.binasm and the ARM64 binary will be downloaded, then drag
the ARM64 binary into cs241.arm64emu to run it.
add.hex)Write an ARM64 program in machine code that adds the value in register x0 to the value in register x1, places the sum in register x5, and returns (branches to x30).
$ cs241.wordasm < add.hex > add.arm
$ cs241.arm64emu add.arm 30 25
x0: 0x1e x16: 0x0
x1: 0x19 x17: 0x0
x2: 0x0 x18: 0x0
x3: 0x0 x19: 0x0
x4: 0x0 x20: 0x0
x5: 0x37 x21: 0x0
x6: 0x0 x22: 0x0
x7: 0x0 x23: 0x0
x8: 0x0 x24: 0x0
x9: 0x0 x25: 0x0
x10: 0x0 x26: 0x0
x11: 0x0 x27: 0x0
x12: 0x0 x28: 0x0
x13: 0x0 x29: 0x1000000
x14: 0x0 x30: 0xfffffe4
x15: 0x0 sp: 0x1000000
pc: 0xfffffe4 instr: hlt
flags: vczn
Program exited normally.
mult.hex)Registers x0 and x1 hold signed integer values. Write an ARM64 program in machine code that multiplies the values in registers x0 and x1, and puts the result in register x5. Assume that -(2^31) ≤ x1 * x2 < 2^31.
$ cs241.wordasm < mult.hex > mult.arm
$ cs241.arm64emu mult.arm 30 25
x0: 0x1e x16: 0x0
x1: 0x19 x17: 0x0
x2: 0x0 x18: 0x0
x3: 0x0 x19: 0x0
x4: 0x0 x20: 0x0
x5: 0x2ee x21: 0x0
x6: 0x0 x22: 0x0
x7: 0x0 x23: 0x0
x8: 0x0 x24: 0x0
x9: 0x0 x25: 0x0
x10: 0x0 x26: 0x0
x11: 0x0 x27: 0x0
x12: 0x0 x28: 0x0
x13: 0x0 x29: 0x1000000
x14: 0x0 x30: 0xfffffe4
x15: 0x0 sp: 0x1000000
pc: 0xfffffe4 instr: hlt
flags: vczn
Program exited normally.
2x-1.hex)Register x0 holds a signed 2's-complement 32-bit integer. Write an ARM64 program in machine code that multiplies the value in register x0 by 2, then subtracts 1 from it, and places the result in register x5. Assume that -(2^31) ≤ 2*$1-1 < 2^31.
$ cs241.wordasm < 2x-1.hex > 2x-1.arm
$ cs241.arm64emu 2x-1.arm 20
x0: 0x28 x16: 0x0
x1: 0x1 x17: 0x0
x2: 0x0 x18: 0x0
x3: 0x0 x19: 0x0
x4: 0x0 x20: 0x0
x5: 0x27 x21: 0x0
x6: 0x0 x22: 0x0
x7: 0x0 x23: 0x0
x8: 0x0 x24: 0x0
x9: 0x0 x25: 0x0
x10: 0x0 x26: 0x0
x11: 0x0 x27: 0x0
x12: 0x0 x28: 0x0
x13: 0x0 x29: 0x1000000
x14: 0x0 x30: 0xfffffe4
x15: 0x0 sp: 0x1000000
pc: 0xfffffe4 instr: hlt
flags: vczn
Program exited normally.
self-modifying.hex)Register x0 holds an integer >= 0 and < 30. Let's denote the value in x0 as v. Do not change the value in register x1.
The last two instructions in your program must be:
xzr to x1 and put the result in x1x30Write an ARM64 program in machine code that modifies its own second-to-last instruction. Instead of adding xzr to x1 and putting the result in x1, it will add xzr to x1 and put the result in xv (e.g. if v = 20, then this will set x20 = x1). Modifying other registers in the process is fine.
$ cs241.binasm < self-modifying.asm > self-modifying.arm
$ cs241.arm64emu self-modifying.arm 5 4094
x0: 0x5 x16: 0x0
x1: 0xffe x17: 0x0
x2: 0x1 x18: 0x0
x3: 0xd61f03c08b3f6025 x19: 0x0
x4: 0x0 x20: 0x0
x5: 0xffe x21: 0x0
x6: 0x0 x22: 0x0
x7: 0x0 x23: 0x0
x8: 0x0 x24: 0x0
x9: 0x0 x25: 0x0
x10: 0x0 x26: 0x0
x11: 0x0 x27: 0x0
x12: 0x0 x28: 0x0
x13: 0x0 x29: 0x1000000
x14: 0x0 x30: 0xfffffe4
x15: 0x0 sp: 0x1000000
pc: 0xfffffe4 instr: hlt
flags: vcZn
Program exited normally.
asm.cc xor asm.rkt)You will write a code generator for a simple ARM64 assembler.
You may use C++ or Racket to complete this assignment.
Starter code is provided below. The starter code implements a simple scanner. This scanner is sufficient for this assignment, but is ineffective for any language more complex than our ARM64 assembly language. Do all of your work in the starter file provided; it is the file you will submit to Marmoset.
If you use the C++ starter code, you can compile the code with:
g++ -g -O0 -fPIC -std=c++20 -Wall -Wextra -pedantic-errors -Wno-unused-parameter -o asm asm.cc
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 (compile-line in the Racket starter code). If there are any discovered bugs with the starter code, please report them to us on Piazza as soon as possible.
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 integer values (which may be negative). Depending on how many bits are available for the immediate value in the instruction, your assembler should handle negative values correctly, implementing two's complement representation.
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 will be set to 0. If the assembly instruction takes two parameters, then parameter three will be 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,
int one,
int two,
int three)
{
// Your implementation goes here!
}
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
The starter code we provide is a combination of a 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. Your job is only to convert the arguments to compileLine to valid ARM64 assembly.
You can use the xxd command in Unix or the cs241.binview (web version) tool to convert your binary output back to hexadecimal so you can read it.
$ echo "br x30" | cs241.binasm | xxd
00000000: c003 1fd6 ....
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. That is, your assembler should throw an error if the values provided are out of bounds for the specific instruction. The starter code will not necessarily do this; you will likely need to implement such checking yourself within compileCode.
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 ARM64 program (or the empty program), potentially with one or more error messages on standard error.
You do not need to support the .8byte directive. The starter code doesn't check for the .8byte directive, and none of the test cases on Marmoset use .8byte. You also do not need to support the various conditioned variants of b.cond.
Hints:
cs241.binasm to ensure that your encoding is correct. Use cs241.binview or xxd to view the hexadecimal/binary encoding of both outputs, and compare them.
The instructions you need to implement are listed below.
| Instruction | Machine Code Instruction (Big-endian) |
Parameters passed to compileLine |
|||
|---|---|---|---|---|---|
instruction |
one |
two |
three |
||
| Add | 10001011 001 mmmmm 011000 nnnnn ddddd |
add | d | n | m |
| Subtract | 11001011 001 mmmmm 011000 nnnnn ddddd |
sub | d | n | m |
| Multiply | 10011011 000 mmmmm 011111 nnnnn ddddd |
mul | d | n | m |
| Multiply Overflow Signed | 10011011 010 mmmmm 011111 nnnnn ddddd |
smulh | d | n | m |
| Multiply Overflow Unsigned | 10011011 110 mmmmm 011111 nnnnn ddddd |
umulh | d | n | m |
| Divide Signed | 10011010 110 mmmmm 000011 nnnnn ddddd |
sdiv | d | n | m |
| Divide Unsigned | 10011010 110 mmmmm 000010 nnnnn ddddd |
udiv | d | n | m |
| Compare | 11101011 001 mmmmm 011000 nnnnn 11111 |
cmp | n | m | 0 |
| Branch to Register | 11010110 000 11111 000000 nnnnn 00000 |
br | n | 0 | 0 |
| Branch and Link Register | 11010110 001 11111 000000 nnnnn 00000 |
blr | n | 0 | 0 |
| Load Register | 11111000 010 iiiiiiiii 00 nnnnn ddddd |
ldur | d | n | i |
| Store Register | 11111000 000 iiiiiiiii 00 nnnnn ddddd |
stur | d | n | i |
| PC-Relative Load | 01011000 iiiiiiii iiiiiiii iii ddddd |
ldr | d | i | 0 |
| Branch | 000101 ii iiiiiiii iiiiiiii iiiiiiii |
b | i | 0 | 0 |
© University of Waterloo. | Design by TEMPLATED.