In this lab you will write your first RISC-V assembly program. Your task is to write a function that prints the contents of a circular queue.
A queue is a data structure in which data elements can be stored (referred to as "enqueuing"). Elements of a queue can later be retrieved (known as "dequeuing") in a First In, First Out ("FIFO") order, meaning that elements are dequeued in the order that they were enqueued. Some important terminology: the position in memory at which the next element is to be enqueued is called the "tail", and the position of the next element to be dequeued is called the "head". The FIFO model creates an issue in memory that can create inefficiency: if a limited amount of memory is allocated for a queue, and the head is always located at the first position in that memory, then what happens when an element is dequeued? The head would then contain no active element, and thus the following element would need to be shifted to fill in the gap. Unfortunately, this shift creates another gap, so every other element in the queue would need to be shifted in the same manner, which is a costly operation.
A modified version of the queue data structure, called a circular queue, can avoid this inefficiency. By allowing the head to point to different locations in the memory allocated for the queue, shifting becomes unnecessary. However, if one only allowed the head to move and nothing else, the queue's capacity (the number of elements that can fit in the queue) would decrease every time the head moved closer to the end of the memory space for the queue. The avoid this issue, the queue is made "circular" by allowing the head and tail to go back to the beginning of the memory space for the queue when it reaches the end of it. The queue is empty when the head and tail point to the same position. In order to enable differentiating between a full and an empty queue, we allocate space for one more element than the queue's actual capacity, meaning one element must always be left empty.1 With this design, a circular queue is full when the tail is pointing at the element right before the head. An element that is dequeued is not cleared in memory, the head simply points at the next element. Therefore, the data will still be in memory, it is just no longer within the bounds of the circular queue and should no longer be accessed. That data will be overwritten when the tail reaches that position and a new element is enqueued in its place.
The input to this assignment is a file containing three separate lines of text:
This file is read by the assembly code provided to you in the
common.s file. Thus, when your code starts the queue will
be already stored in memory. The code in common.s expects
the content of the input file to be correct and consistent. Therefore,
if you create new input files, make sure that it follows the
specification above.
Write a RISC-V assembly program for the function
printQueue that prints every element in a circular
queue in the order that they were enqueued. The elements of the
circular queue will be ASCII characters, meaning they will each be
stored as an individual byte and can be loaded with lb.
The printQueue function is prints the characters in
the queue, in order, to standard output. The way to do this in
RISC-V is to use the PrintChar syscall. This can be
done by loading the value 11 into register
a7, loading the character you want to print into
register a0, and then using the ecall
instruction.
The RISC-V rem instruction will likely be useful in
solving this lab. This instruction has the form rem d, s,
t (where d, s, and t
are integer registers) and will store the remainder of
s divided by t into register
d. This operation is equivalent to modulo or
% in many programming languages. Remainder can be very
helpful in looping around a circular queue. For example, say that
the capacity of the queue is 3. As mentioned previously, this means
that the memory space containing the queue has room for 4 elements,
though one is restricted. This means that the offsets in memory at
which there can be a valid element of the queue are 0, 1, 2, and
3. Conveniently, the remainder of any number divided by 4 will be
between 0 and 3, and as the number being divided by 4 increments,
the remainder will increment within this range until it loops back
around to the other side of the range. For example, the remainder of
10 / 4 is 2, the remainder of 11 / 4 is 3, and the remainder of 12 /
4 is 0, having looped back around. This can be used to iterate over
the elements of the circular queue.
An illustration of how printQueue operates. The
position pointed to by the tail, and the reserved position, both
contain data ('l' and 'y', respectively). These characters are not
to be printed because they are not in the queur. They are in this
illustration as a reminder that dequeued elements are not cleared
from memory, they simply no longer belong to the circular queue. The
tail points to the position at which the next element is to be
enqueued and thus it does not point to an active element, so its
content is not to be printed.
common.s File When your program starts executing, the circular queue and all its
elements will already be stored in memory. Your program will
receive three memory addresses: (1) the address of the first byte of
the memory space containing the queue; (2) the address of the
element that is the head o the queue; (3) the address of the element
that is the tail of the queue. Your program will also receive the
total capacity of your queue, meaning the number of elements that
can be contained in the queue (do keep in mind that the circular
queue is stored using capacity + 1 bytes because one
space must be reserved in order to differentiate between a full and
an empty queue). These arguments will be provided in
registers a0, a1, a2, and
a3. You must use the label printQueue: at
the start of your code as the very first label under the
.text directive.
printQueue:a0: the capacity of the queue.
a1: address of the memory where the circular queue is stored.a2: address of the memory pointed to by the head.a3: address of the memory pointed to by the tail.a0: the number of elements in the circular queue.PrintChar syscall.jr ra
Thus, make sure to include this instruction at the end of your
subroutine so that it can work well with the automated grading scripts.
When RARS starts executing, it looks for a main:
label where it will find the user code. This common.s file, that is included in your
solution template, contains a main function that sets
up the circular queue in memory, and then calls your
printQueue function using arguments as described
above. You are encouraged to read the code in the
common.s file to understand how the whole program
works.
Here are some instructions to aid you in running and testing the program using the files that were provided in the original git repo.
Guarantees:
The Code directory contains the following files and directories:
queue.s: this is where you will write the code for
the printQueue function.common.s: loads a circular queue alongside head and
tail indexes; calls your printQueue function; and
then prints the returned value.Tests/: a directory that contains test cases. To
generate your own, make sure that the head index is on the first
line, the tail index is on the second line, and the queue is on
the third (and final) line. Each line should be separated by a
newline character, and there should not be a newline character
at the end of the file. Some text editors automatically add a
newline at the end of a file, to avoid this issue, you can write
your test case .txt file using RARS.You can use CheckMyLab to assess the correctness of your assignment. To access CheckMyLab, you must use the University of Alberta virtual private network. If you have not yet set up the VPN, instructions can be found here. Once connected to the University of Alberta VPN, you can access CheckMyLab. Log in with your CCID and select the assignment, "229_Fa20 - Lab #2: Lab_CircularQueue".
On the CheckMyLab assignment page you can:
.include "common.s" with all of the code
from common.s. Do this with a copy of your
solution because you need to submit a solution that contains the line
.include "common.s". After running your solution on some selected tests
from the pool, you can view how your program's output and the expected output
differs. If the output doesn't match for a test case, it might be helpful to
download it and test it yourself.printQueue.s file should not contain a main label.
This file is only provided to demonstrate clean and readable coding practices.
There is 1 file to submit for this assignment:
printQueue.s, should contain the
assembly program you wrote in the last step. For the file printQueue.s, make sure to keep the line
".include "common.s"" and make sure that you do
not add a main label.