| Assignments for CS 241 | ||
|---|---|---|
| ← Assignment 2 | Assignment 3 | Assignment 4 → |
| Monday, Oct 21 at 8:00 am | ||
| P1 • P2 • P3 • P4 • P5 | ||
In this assignment, you will write mips 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 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).
Similarly, when 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.
Special locations in memory that interact with peripheral devices (in this case reading and writing characters) is called Memory-mapped I/O and is the most common way for a CPU to communicate with other devices. You will see these techniques if you take cs452.
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 < tac.asm > tac.mips
$ mips.stdin tac.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 tac.mips <<< "Meow meow"
Running MIPS program.
woem woeMMIPS 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
increasing.asm)Write a MIPS program that takes an array as input, where register 1 contains the starting address and register 2 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 array elements as parameters, in registers 1 and 2. The compare procedure returns the value 1 (in register 3) if the first parameter is considered "less than" the second parameter, and otherwise returns the value 0.
Then, 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 3. If not, store 0 in register 3. Then return to the loader.
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.
You may assume the array has at least two elements.
The compare procedure will begin with a label compare:. It takes its first parameter in $1 and its second parameter in $2. It returns the result of the comparison in $3. The result is 1 if the value in $1 is considered "less than" the value in $2, and otherwise, the result is 0. The compare procedure will preserve all registers except for $3.
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.
Marmoset will only check the final result in $3 to determine if your program is correct.
Thecompare 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 the procedure will return 1 for a pair of elements even if, when interpreted as integers, the first element is not less than the second. 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 slt or sltu.
Test your program with mips.array. This tool works similarly to mips.twoints and mips.stdin, but it prompts you to enter an array. In the web-based version, you can simply enter the values for the array, one per line. In the command-line version on the student Linux server, enter the size of the array, followed by each element of the array. It will then place the starting address of the array in $1, and the size in $2.
Ensure the value in register 3 is correct.
Marmoset provides its own compare procedure, and will reject your submission if you include a compare procedure. But you will need 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.mips
With this setup, you don't need to remember to remove the compare procedure you use for testing before each Marmoset submission.
print.asm)Write a MIPS procedure called print that interprets the value in $1 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.
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 print:
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 32-bit two's complement integers.
Marmoset will test your procedure with various main programs. In addition to checking standard output, it will also check if registers are preserved. Whatever values are in registers before the procedure call should be there unchanged after the call.
The most basic way to test your procedure is to just run it directly with mips.twoints and ensure standard output corresponds to the value entered in $1. For instance, on the Student Linux server:
$ mips.twoints print.mips
Enter value for register 1: 241
Enter value for register 2: 0
Running MIPS program.
241
MIPS program completed normally.
$01 = 0x000000f1 $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
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:
Try writing main programs that call the procedure multiple times with different assortments of register values to test that you have truly written it correctly.
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 a MIPS procedure called stirling that takes as input two 32-bit unsigned integers, n = $1 and k = $2, such that n ≥ k, and stores the value f(n,k) in $3 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 $3.
Your procedure cannot assume anything about the values of registers, except that $1 ≥ $2 (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.
Marmoset will test your procedure with various main programs. In addition to checking the result in $3, it will also check the other general-purpose registers to make sure they were preserved. Whatever values are in registers (other than $3) before the procedure call should be there unchanged after the call.
Only general-purpose registers (numbered registers) need to be preserved. So not hi, lo, PC, etc.
Test your program with mips.twoints. Ensure the value in register 3 is correct. Since this is a procedure, test it with various main programs that put different values in registers, and ensure general-purpose registers other than $3 are preserved.
asm.cpp)In this problem, you will write a program that reads a list of mips assembly tokens from standard in, will calculate the location of every label, and will substitute a labels location everywhere the label is used.
The output of this program is a symbol table on standard error, and a parameter list for compileLine (from assignment 1) on standard out. Each numerical parameter must be printed as an unsigned decimal number.
The symbol table must be printed on standard error. The label's lexeme and its address must be printed on the same line, with the label lexeme first, a space character, then the location in memory as a decimal number. The labels must be in the same order as they are defined.
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. 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 from the mips assembly input. The NEWLINE token type doesn't have a lexeme.
Consider the mips assembly program:
foo:
beq $0, $1, bar
bar:
add $1, $2, $3
The tokenization of this program is:
LABEL foo:
NEWLINE
ID beq
REG $0
COMMA ,
REG $1
COMMA ,
ID bar
NEWLINE
LABEL bar:
NEWLINE
ID add
REG $1
COMMA ,
REG $2
COMMA ,
REG $3
NEWLINE
The output on standard error must be:
foo 0
bar 4
The output of the assembler on standard out will be a list of parameters for compileLine(), one line per call to compileLine, space separated, with no quote characters. The integer parameters must be printed in decimal, unsigned, and with however many bits the parameter is in the machine code. Your output cannot contain any labels--it must replace every label use with the label address. For the example input above, the output must be:
beq 0 1 0
add 1 2 3
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 mips assembly program, your assembler must print ERROR on standard error. It must stop processing input and terminate. Your error message can include a description of the error, at your digression.
Each mips instruction will be on only one line.
Your assembler is required to handle the .word directive. For the line .word X, your program should output word Y 0 0, where Y is whatever value X is when interpreted as an unsigned decimal number.
Two new tools are provided cs241.tokenizer and cs241.compileline. cs241.tokenizer accepts a mips assembly program and prints a list of tokens suitable for this problem. cs241.compileline accepts the output of this problem and assembles it into mips machine code.
.word directives (June 6)std::vector tokens was shadowed in the while that read the contents of the input file. The WHITESPACE token type was vestigial and was removed. (9 June)stouint32 was changed to stouint64 (and to not use the underlying function stoi, but use stol). (10 June)stouint64 was fixed to return a uint64_t. (12 June)