Assignments for CS241
Due Friday, February 13th, 5:00 PM
In this assignment, you will write ARM64 assembly programs, more complex than the machine code programs you wrote in Assignment 1. These programs will involve memory access, arrays, procedures, and recursion.
You are encouraged to use the assembler you wrote in Assignment 1 to compile your assembly.
tac.asm)In Unix, there is a utility program called cat which prints out the contents of a file. We will write a program that prints the contents of a file backwards.
Our utility program differs from cat in that it only supports one file at a time. The file must be read from standard input; it cannot be passed as a command line argument.
tac will read bytes from standard input until there are no more bytes to read, then output every thing it read in reverse order. You can assume that the file fits in RAM.
When you load (with ldur xd, [xn, 0]) from the special address 0xc000000000010000, our ARM64 emulator will read one byte (8 bits) from standard input and store the byte in the lower (rightmost) 8 bits of the destination register xd. If the read is successful, the upper 56 bits are filled with zeroes. On the other hand, if the read fails (either there are no bytes left to read due to end-of-file or another error occurs) then the destination register will contain 0xffffffffffffffff (the two's complement encoding of -1).
Likewise, when you store (with stur xd, [xn, 0]) to the special address 0xc000000000010008, the lower 8 bits of xd will be written to standard output.
Special locations in memory that interact with peripheral devices (in this case reading and writing characters) are called Memory-mapped I/O. They are the most common way for a CPU to communicate with other devices. You will see these techniques in greater action if you take CS452 (Real-time Programming).
Testing this program is easiest with cs241.arm64emu. Assemble your program with cs241.binasm as usual, then run the assembled program with cs241.arm64emu. Standard input will work as is expected for any conventional program.
If you're using the web tools, simply enter some standard input before dragging your machine code file into cs241.arm64emu, and its output will be shown.
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 cs241.arm64emu will not.
Using the command-line tools on the student Linux system:
$ cs241.binasm < tac.asm > tac.bin
$ cs241.arm64emu tac.bin
If you do not provide any input (as above), your ARM64 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:
$ cs241.arm64emu kitten.bin < input.txt
Or provide a short input string directly as follows:
$ echo "meowza!" | cs241.arm64emu tac.bin
!azwoem
x0: 0x100000 x16: 0x0
x1: 0xffff8 x17: 0x0
x2: 0xc000000000010008 x18: 0x0
x3: 0x6d x19: 0x0
x4: 0x0 x20: 0x0
x5: 0x0 x21: 0x0
x6: 0x0 x22: 0x0
x7: 0x0 x23: 0x0
x8: 0x8 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.
increasing.asm)Write an ARM64 program that takes an array as input, where register x0 contains the starting address and x1 contains the size (number of elements). The program should determine whether the array is strictly increasing with respect to a custom comparison procedure called compare.
That is, suppose we have an array A of length n, and a procedure called compare which takes two numbers as parameters, in registers x0 and x1. The compare procedure returns the value 1 (in register x0) if the first parameter is considered "less than" the second parameter, and otherwise returns the value 0.
Your program must determine if compare(A[i], A[i+1]) == 1 for each i such that 0 ≤ i ≤ n-2. In other words, do the elements "strictly increase" according to the compare procedure? If so, store 1 in register x0. If not, store 0 in register x0. Then return to the loader (use br x30).
Marmoset will provide the compare procedure and combine it with your program. For testing, you will need to write your own compare procedure, but you should not submit a compare procedure to Marmoset. Doing so will cause an error.
You may assume the array has at least two elements.
The compare procedure will begin with a label compare:, which can be called from your code by loading your desired values into x0 and x1, loading the address of compare into another register (say x5) using `.8byte compare` and the load-skip pattern, then calling blr x5.
Since you are writing a program in this question, not a procedure, you do not need to preserve any registers, except those that are necessary for your program to function correctly. The `compare` procedure will not affect registers x19 through x28, so you do not need to worry about preserving those register values across a call. Registers x0 through x18 need to be manually preserved, however. x30 will also need to be saved somewhere as it is automatically overwritten by the blr instruction used to call the compare procedure.
Marmoset will only check the final result in x0 to determine if your program is correct.
The compare procedure will be consistent with a certain ordering of the array elements, but you do not know what this ordering is. For example, it is possible that the procedure will return 1 for a pair of values even if the first element is not less than the second (when read as a signed integer). The compare procedure might be enforcing a different order on integers, or it may not be interpreting the values as integers at all! Thus, you must use the compare procedure to compare elements, rather than relying on cmp and the conditional branches.
Test your program with cs241.arm64emu using the -a option. Using that option you can enter an array of values (decimal or hexadecimal), which will then be stored in an array in memory which is pointed to by x0. The number of items in the array will be stored in x1.
Marmoset provides its own compare procedure, and will reject your submission if you include a compare procedure. However, you will need still a compare procedure to test your program. A simple workaround is to put the compare procedure in a separate file, and combine them with cat before assembling:
cat increasing.asm compare.asm | cs241.binasm > increasing.bin
With this setup, you don't need to remember to remove the compare procedure you use for testing before each Marmoset submission.
A simple compare procedure example is given below, which simply compares the integer values of the numbers.
compare:
cmp x0, x1
b.lt 12
sub x0, x0, x0
br x30
ldr x0, 8
b 12
.8byte 0x1
br x30
print.asm)Write an ARM64 procedure called print that interprets the value in x0 as a two's complement integer, and prints the decimal (base 10) representation of the integer to standard output, followed by a line feed character (ASCII 0x0A).
Your procedure must preserve the values of all general-purpose registers (x0 to x29). That is, once the procedure stops running, the values in all general purpose registers should be the same as when the procedure was initially called.
Your procedure cannot assume anything about the values of registers. For example, you should not rely on registers being pre-initialized to zero.
Your procedure should start with a label definition like this:
print:
// your code here
If the integer is non-zero, the representation you print should have no leading zeroes.
If the integer is negative, the representation you print should start with a minus sign - (ASCII 0x2D).
Your program should produce the correct output for all 64-bit two's complement integers.
The most basic way to test your procedure is to just run it directly with cs241.arm64emu and ensure standard output corresponds to the value entered in x0. For instance, on the Student Linux server:
$ cs241.arm64emu print.bin 241
241
x0: 0xf1 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.
However, testing procedures is more involved than testing standalone programs. In addition to ensuring the procedure functions correctly, you must ensure that it preserves register values, and that it always works regardless of what values are in registers when it is called. Consider these scenarios:
You can test that registers are preserved by calling cs241.arm64emu with additional arguments to initialize register values.
If Marmoset says your output is wrong, but it "looks correct" in your local testing, use cs241.binview or xxd to ensure you did not accidentally print invisible characters, such as the null character (ASCII 0x00).
stirling.asm)Write an ARM64 procedure called stirling that takes as input two 64-bit unsigned integers, n in x0 and k in x1, such that n ≥ k. For output, it stores the value f(n,k) in x0 using the following recursively defined function:
f(0,0) = 1.
f(i,0) = f(0,i) = 0, for integers i > 0.
f(n,k) = (n-1) * f(n-1,k) + f(n-1,k-1), for integers n > 0 and k > 0.
Your procedure must preserve the values of all general-purpose registers except for x0.
Your procedure cannot assume anything about the values of registers, except that x0 ≥ x1 (when these register values are interpreted as unsigned integers).
Remark: This function computes what are known as the "unsigned Stirling numbers of the first kind".
You may use the table below to check the correctness of your answers for some small values.
If n < k, then f(n,k) is always zero, so these cases are omitted from the table.
n/k 0 1 2 3 4 5 6
0 1
1 0 1
2 0 1 1
3 0 2 3 1
4 0 6 11 6 1
5 0 24 50 35 10 1
6 0 120 274 225 85 15 1
Your procedure should start with a label definition stirling:
Marmoset will test your program will small enough numbers that you do not need to worry about efficiency considerations or overflow.
In addition to checking the result in x0, Marmoset it will also check the other general-purpose registers to make sure they were preserved. Whatever values are in registers (other than x0) before the procedure call should be there unchanged after the call.
Test your program with cs241.arm64emu. Ensure the value in register x0 is correct, and try calling it with other registers initialized to make sure that it preserves them. You can also write your own main program sections to see if it properly returns from a function call (ends with br x30 to the right address).
asm.(cpp/cc/rkt))In this problem, you will write a program that reads a list of ARM64 assembly tokens from standard input and converts it to machine code. Along the way, your program should calculate the location of every label and substitute a label's location everywhere it is used.
The input to the program is a list of tokens: one token per line, with the token type, a space, the token lexeme, and a unix newline character (\n). The token types are the same as what's defined in Assignment 2, Problem 5, with one addition: The NEWLINE token has been added to delineate new lines in the ARM64 assembly input. The NEWLINE token type doesn't have a lexeme. All other tokens are guaranteed to not contain any whitespace in their lexemes.
It is expected that all instructions, labels, and directives (.8byte) must end with a newline, with the exception of the last line of the original program. So for example,
DOTID .8byte
HEXINT 0x44444
ID br
REG x30
...wouldn't be valid, since there should be a NEWLINE between the HEXINT and ID. For something like this, your program should throw an error.
The output of this program is ARM64 machine code on standard output, and a symbol table showing the in-program location of every label on standard error. Each label's lexeme and address must be printed on the same line, with the label lexeme first, a space character, then the location in memory as a positive decimal integer. The labels must be in the same order as they are defined.
Your code is expected to be able to assemble the .8byte directive and all assembly instructions provided in the ARM64 reference sheet (including b.cond and its variants). Combining this program with a tokenizer tool like your solution for Assignment 2, Problem 5 should produce almost all functionality of cs241.binasm (with modifications to your A2P5 solution to also produce newline tokens).
Note: To achieve the above, your solution for A2P5 must be modified to also recognize and create newline tokens.
You are not required to use any of the starter code: you can remove it or change it as you see fit. The correctness of your program is evaluated by checking its output. We are not checking to see if you use compileLine() or not.
If any errors are present in the tokenized input ARM64 assembly program, your assembler must print ERROR on standard error. Your error message can include a description of the error if you so wish (we recommend it, since it makes development and debugging easier). You are not expected to check that the token lexemes of each kind of token actually conform to the token's intended structure; you can assume that this will always be the case.
compileLine).© University of Waterloo. | Design by TEMPLATED.