THE UNIVERSITY OF NEW SOUTH WALES
TERM 2, 2021
COMP1521: COMPUTER SYSTEMS FUNDAMENTALS
Final Exam
— Friday, 13 August 2021 —
10 questions — 100 marks
10 minutes reading; 3 hours working
Examination Information
Examination Instructions and Conditions
You can start reading the text of this examination at Friday 13 August 13�50, Sydney time.
You can start working on examination questions at Friday 13 August 14�00, Sydney time.
You must stop working on examination questions at Friday 13 August 17�30, Sydney time. Only submissions
before this time will be marked.
For students with approved examination extensions from UNSW Equitable Learning Services, you should
continue working until your extended working time expires.
You must not communicate with anyone via any medium during the examination — this includes, but is not
limited to, communications via email, telephone, instant-message, talking, hot-air balloon, … — except for
COMP1521 staff, via cs1521. .edu.au.
You must not get help from anyone during this exam, except for COMP1521 staff.
You must not use code-synthesis tools, such as GitHub Copilot, during this exam.
You must not communicate your exam answers to any other person, even after the end of the exam.
Some students have extended time to complete the exam.
You must ensure that, during and after the examination, no other person can access your work.
You must not place your examination work in a location accessible to any other person, whether they be a
student in the course or otherwise. This includes file sharing services such as Dropbox or GitHub.
Your zPass should not be disclosed to any other person. If you have disclosed your zPass, you should change it
immediately.
This is an open-book examination: you may use your papers or books. You may not create or modify materials
on the Internet except as would be reasonably required to complete the exam
on the Internet, except as would be reasonably required to complete the exam.
Deliberate violation of exam conditions is academic misconduct,
and will be referred to the UNSW Student Conduct and Integrity Unit.
Troubleshooting
If you are having issues working on the exam at CSE, please try the following:
if you are using VLAB: try logging out and logging back in — you will very likely be connected to a different
server, which may make your connection better. If the problem persists, try using SSH instead: instructions at
if you are using SSH: try logging out and logging back in. If the problem persists, try using VLAB instead:
instructions at
if you are using VSCode: try disconnecting and reconnecting; or try changing servers from
vscode.cse.unsw.edu.au to vscode2.cse.unsw.edu.au.
If you still have problems, contact COMP1521 staff via cs1521. .edu.au — we will try to help you fix
the problem; and, if we can fix the problem, we may also be able to give you extra time.
If you have a problem that cannot be fixed and you cannot complete the exam, you should apply for special
consideration. This will require evidence of a problem, and you should take screenshots documenting the problem.
For example:
error messages,
screen not loading
timestamped speed tests,
power outage maps, or
messages or information from your internet provider regarding the issues experienced.
You must also contact course staff via cs1521. .edu.au as soon as it is clear the issue cannot be
fixed.
Fit-to-Sit
This exam is covered by UNSW’s Fit-to-Sit policy. That means that, by sitting this exam, you are declaring yourself
well enough to do so. You will be unable to apply for special consideration after the exam for circumstances affecting
you before it began. If you have questions, or you feel unable to complete the exam, contact
cs1521. .edu.au.
Examination Structure
This examination has 10 questions, worth a total of 100 marks.
Questions are worth equal marks.
All 10 questions are practical questions.
You must answer each question in a separate file. Each question specifies the name of the file to use. These are
named after the corresponding question number. Make sure you use exactly this file name.
When you finish working on a question, you should submit your files using the give command specified in the
question. You should not wait until the submission deadline to submit your answers. Running autotests does
not automatically submit your code.
You may submit as many times as you like; only the last submission will be marked.
You can verify what submissions you have made with 1521 classrun -check final_q
Available Resources: Documentation
https://www.cse.unsw.edu.au/~learn/homecomputing/ssh/
https://taggi.cse.unsw.edu.au/FAQ/Logging_In_With_SSH/
https://www.cse.unsw.edu.au/~learn/homecomputing/vlab/
You may find this language documentation useful during this exam:
C quick reference
MIPS Quick Reference Card
MIPS Instruction Reference
SPIM Documentation
MIPS Quick Tutorial
You may also access:
manual entries via the man command, and
Texinfo pages via the info command.
Getting Started
Set up for the exam by creating a new directory called exam_final, changing to this directory, and fetching the
provided code by running these commands:
$ mkdir -m 700 exam_final
$ cd exam_final
$ 1521 fetch exam_final
Or you can download the provided code as a zip file or a tar file.
If you make a mistake, and need a new copy of a particular file, you can do the following:
$ rm broken-file
$ 1521 fetch exam_final
Only files that don’t exist will be recreated. All other files will remain untouched.
Question 0 (10 �����)
Count leading zeroes is an operation on a list of bits that counts how many zero-bits are present before the first
one-bit, starting from the most-significant bit.
For example, in the case of an 8-bit number,
count_leading_zeroes(0b10000000) == 0
count_leading_zeroes(0b01111111) == 1
count_leading_zeroes(0b00101010) == 2
count_leading_zeroes(0b00001110) == 4
count_leading_zeroes(0b00000001) == 7
count_leading_zeroes(0b00000000) == 8
You must implement this operation for 32-bit values.
You have been given final_q0.c:
https://cgi.cse.unsw.edu.au/~cs1521/21T2/resources/cheatsheets/c-qrc.pdf
https://cgi.cse.unsw.edu.au/~cs1521/21T2/resources/MIPS32-QRC.pdf
https://cgi.cse.unsw.edu.au/~cs1521/21T2/resources/MIPS32-II-r5.04.pdf
https://cgi.cse.unsw.edu.au/~cs1521/21T2/resources/spim-guide.html
https://cgi.cse.unsw.edu.au/~cs1521/21T2/resources/spim-tute.html
https://manpages.debian.org/jump?q=man.1
https://manpages.debian.org/jump?q=info.1
https://cgi.cse.unsw.edu.au/~cs1521/21T2/exam/final/provided.zip
https://cgi.cse.unsw.edu.au/~cs1521/21T2/exam/final/provided.tar
// COMP1521 21T2 … final exam, question 0
#include
#include
#include
int
count_leading_zeroes (uint32_t x)
{
// TODO
return 42;
}
Add code to the function count_leading_zeroes so that it counts and returns the amount of leading zeroes of a 32-
bit unsigned integer x.
For example:
# 33554432 == 0x02000000
$ ./final_q0 33554432
6
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q0
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q0 final_q0.c
To verify your submissions for this activity:
$ 1521 classrun -check final_q0
Question 1 (10 �����)
You have been given final_q1.c:
// COMP1521 21T2 … final exam, question 1
#include
#include
#include
#include
#define BITS 8
void
and (bool x[BITS], bool y[BITS], bool result[BITS])
{
// TODO
}
void
or (bool x[BITS], bool y[BITS], bool result[BITS])
{
// TODO
}
void
xor (bool x[BITS], bool y[BITS], bool result[BITS])
{
// TODO
}
void
not (bool x[BITS], bool result[BITS])
{
// TODO
}
Add code to the following functions:
and (bitwise AND)
or (bitwise OR)
xor (bitwise XOR)
not (bitwise NOT / bitwise negation)
such that they perform their respective bitwise operations on given arrays of 8 (i.e., BITS) booleans. A boolean with
the value true represents a 1 bit, and a boolean with the value false represents a 0 bit.
You must store the result of your bitwise operation in the provided result array in each function.
You must not modify the provided x and y boolean arrays. You may only modify the result array.
final_q1_main.c provides some code to let you test each of these functions.
For example:
$ ./final_q1 -and 10110101 01101001
10110101 &
01101001
========
00100001
$ ./final_q1 -or 10110101 01101001
10110101 |
01101001
========
11111101
$ ./final_q1 -xor 10110101 01101001
10110101 ^
01101001
========
11011100
$ ./final_q1 -not 10110101
~10110101
========
01001010
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q1
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q1 final_q1.c
To verify your submissions for this activity:
$ 1521 classrun -check final_q1
Question 2 (10 �����)
A parity check is a simple way to provide an integrity check for a value. Often, when we transmit data, we will also
transmit its parity, which can allow a receiver to verify they have read the correct data.
A number is defined to have even parity, if the amount of 1 bits in the number is even.
Conversely, a number is defined to have odd parity, if the amount of 1 bits in the number is odd.
For example, checking the parity of some 8-bit numbers:
0b00000000: zero 1 bits are set ⇒ even parity
0b00000001: one 1 bit is set ⇒ odd parity
0b00000010: one 1 bit is set ⇒ odd parity
0b00000011: two 1 bits are set ⇒ even parity
You have been given final_q2.c, which contains code that implements a parity checker:
// COMP1521 21T2 … final exam, question 2
#include
#include
int
main (void)
{
uint32_t n;
scanf (“%d”, &n);
int bit_idx = 0;
int n_bits_set = 0;
while (bit_idx != 32) {
int bit = (n >> bit_idx) & 1;
n_bits_set = n_bits_set + bit;
bit_idx++;
}
if (n_bits_set % 2 != 0) {
printf (“the parity is odd\n”);
} else {
printf (“the parity is even\n”);
}
return 0;
}
You have also been given final_q2.s, a stub MIPS program that reads an integer and prints
“the parity is even\n”:
# COMP1521 21T2 … final exam, question 2
.data
even_parity_str: .asciiz “the parity is even\n”
odd_parity_str: .asciiz “the parity is odd\n”
.text
main:
li $v0, 5
syscall
move $t0, $v0
# input is in $t0
# TODO
li $v0, 4
la $a0, even_parity_str
syscall
li $v0, 0
jr $ra
Add code to final_q2.s such that it prints out whether a 32-bit number, read from standard input, has odd or even
parity.
If the parity is even, you should print “the parity is even\n”.
If the parity is odd, you should print “the parity is odd\n”.
For example:
$ 1521 spim -file final_q2.s
3
the parity is even
$ 1521 spim -file final_q2.s
4
the parity is odd
$ 1521 spim -file final_q2.s
5
the parity is even
$ 1521 spim -file final_q2.s
6
the parity is even
NOTE:
The correct strings to print are already provided for you in the .data segment
You do not have to perform any error checking.
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q2
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q2 final_q2.s
To verify your submissions for this activity:
$ 1521 classrun -check final_q2
Question 3 (10 �����)
You have been given final_q3.c:
// COMP1521 21T2 … final exam, question 3
#include
#include
#include
void
cp (char *path_from, char *path_to)
{
// TODO
}
Add code to the function cp so that it copies the content from the file located at path_from into a file located at
path_to.
If there is not an existing file located at path_to, a new file should be created. If there is an existing file located at
path_to, it should be overwritten.
It should copy all bytes from the file. i.e. once cp has been executed, the files located at path_from and at path_to
should be identical.
For example:
$ cat a
hello
$ cat b
goodbye
$ cat c
cat: c: No such file or directory
$ ./final_q3 a b
$ cat a
hello
$ cat b
hello
$ ./final_q3 a c
$ cat c
hello
NOTE:
You do not have to perform any error checking.
You can assume there is a file located at path_from.
You can assume that you have permissions to read from the file located at path_from.
You can assume that you have permissions to write to a file located at path_to.
You may not call any external programs
You are not permitted to run any external programs.
You are not permitted to use system, popen, posix_spawn, fork, exec, or any of their equivalents.
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q3
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q3 final_q3.c
To verify your submissions for this activity:
$ 1521 classrun -check final_q3
Question 4 (10 �����)
Multiplication is often an “expensive” operation — it can take a substantial amount of time and energy to do, and not
just in hardware — so we often prefer to reduce multiplication into bitwise operations, or into simple additions or
subtractions, which are often far cheaper.
For example, let’s say we wish to multiply some value by 7 without using *. Because 7 is 8 – 1, we can restate
multiplying by seven as multiplying by eight, then subtracting the original multiplicand once:
. We now have multiplication by a power of two, which we can convert to a
bitwise-left-shift; and subtraction is a permitted operation. In C, we would express this as (b << 3) - b.
You have been given final_q4.c:
// COMP1521 21T2 ... final exam, question 4
#include
long
mul (long a, long b_)
{
unsigned long b = b_;
// NOTE: Maximum 5 operations allowed
// for each multiplication
// NOTE: Permitted operations:
// [x + y, x – y, -x, x << y]
if (a == 7) {
// Two operations:
// 1 2
return (b << 3) - b;
}
if (a == 17) {
return 42; // TODO
}
if (a == -3) {
return 42; // TODO
}
if (a == 60) {
return 42; // TODO
}
if (a == -112) {
return 42; // TODO
}
// Invalid inputs will simply abort.
abort();
}
Add code to the function mul so it performs when is one of 17, -3, 60, or -112.
As is worked above, the case where is 7 has already been provided for you.
You may not use multiplication, *.
You may only use the operations + (two-operand addition), - (one-operand negation), - (two-operand subtraction),
and << (two-operand bitwise-left-shift).
Additionally, you may only use five of these operations to do each multiplication. Autotest will not warn you
about this, but it will be checked in marking.
You may not use floating-point operations to approximate an answer.
b
b × 7 = b × 8 − b = b × 2
3
− b
a × b a
a
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q4
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q4 final_q4.c
To verify your submissions for this activity:
$ 1521 classrun -check final_q4
Question 5 (10 �����)
You have been given final_q5.c:
// COMP1521 21T2 ... final exam, question 5
#include
#include
#include
void
print_utf8_count (FILE *file)
{
unsigned long amount_1_byte = 0;
unsigned long amount_2_byte = 0;
unsigned long amount_3_byte = 0;
unsigned long amount_4_byte = 0;
// TODO
printf(“1-byte UTF-8 characters: %lu\n”, amount_1_byte);
printf(“2-byte UTF-8 characters: %lu\n”, amount_2_byte);
printf(“3-byte UTF-8 characters: %lu\n”, amount_3_byte);
printf(“4-byte UTF-8 characters: %lu\n”, amount_4_byte);
}
Add code to the function print_utf8_count such that it prints out what number of UTF-8 characters in file are of
which size in bytes.
For example:
$ cat utf8_file.txt
you are doing great
det går strålande
你做的很好
🤔💻🙌🤗🎉🎓
$ ./final_q5 utf8_file.txt
1-byte UTF-8 characters: 38
2-byte UTF-8 characters: 2
3-byte UTF-8 characters: 5
4-byte UTF-8 characters: 6
NOTE:
You do not have to perform any error checking.
You can assume there is a valid file that you can read in file.
You can assume that file contains only valid UTF-8 text.
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q5
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q5 final_q5.c
To verify your submissions for this activity:
$ 1521 classrun -check final_q5
Question 6 (10 �����)
Binary data is really hard for humans to read. It is common to render binary data as a hexdump to make it more
readily accessible, and hexdumps are very common in a range of fields, from networking to security.
A hexdump looks like:
$ cat tina_arena.dump
00000000 f0 00 00 00 00 00 00 00 b8 00 54 00 00 00 00 00 |……….T…..|
00000010 20 00 54 00 00 00 00 00 00 00 00 00 00 00 00 00 | .T………….|
00000020 48 65 79 20 74 68 65 72 65 21 20 54 68 61 6e 6b |Hey there! Thank|
00000030 73 20 66 6f 72 20 6a 6f 69 6e 69 6e 67 20 75 73 |s for joining us|
00000040 2e 00 00 00 00 00 00 00 58 00 54 00 00 00 00 00 |……..X.T…..|
00000050 10 00 54 00 00 00 00 00 48 65 79 20 74 68 65 72 |..T…..Hey ther|
00000060 65 21 20 54 68 61 6e 6b 73 20 66 6f 72 20 6a 6f |e! Thanks for jo|
00000070 69 6e 69 6e 67 20 75 73 2e 00 00 00 00 00 00 00 |ining us……..|
00000080 90 00 54 00 00 00 00 00 48 00 54 00 00 00 00 00 |..T…..H.T…..|
00000090 48 65 79 20 74 68 65 72 65 21 20 54 68 61 6e 6b |Hey there! Thank|
000000a0 73 20 66 6f 72 20 6a 6f 69 6e 69 6e 67 20 75 73 |s for joining us|
000000b0 2e 00 00 00 00 00 00 00 c8 00 54 00 00 00 00 00 |……….T…..|
000000c0 80 00 54 00 00 00 00 00 48 65 79 20 74 68 65 72 |..T…..Hey ther|
000000d0 65 21 20 54 68 61 6e 6b 73 20 66 6f 72 20 6a 6f |e! Thanks for jo|
000000e0 69 6e 69 6e 67 20 75 73 2e 00 00 00 00 00 00 00 |ining us……..|
000000f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |…………….|
It contains three distinct sections:
the address column: this starts at 0x00000000, and increases by 0x10 (or 16 in base 10) each line;
the data columns: after the address, we receive 16 2-digit hexadecimal values, typically grouped into two
blocks of eight values each, which represents the actual data of the file!
the human readable stripe: at the very end of each line, between the vertical bars (|) is the human readable
version of this line. We will ignore it for the purposes of this exercise.
In this question, given a hexdump, you must reconstruct the original file that was dumped. However, the given
hexdump’s lines may not be in order — for example:
$ cat tina_arena.dump.shuf
00000060 65 21 20 54 68 61 6e 6b 73 20 66 6f 72 20 6a 6f |e! Thanks for jo|
000000b0 2e 00 00 00 00 00 00 00 c8 00 54 00 00 00 00 00 |……….T…..|
00000000 f0 00 00 00 00 00 00 00 b8 00 54 00 00 00 00 00 |……….T…..|
00000040 2e 00 00 00 00 00 00 00 58 00 54 00 00 00 00 00 |……..X.T…..|
000000c0 80 00 54 00 00 00 00 00 48 65 79 20 74 68 65 72 |..T…..Hey ther|
00000020 48 65 79 20 74 68 65 72 65 21 20 54 68 61 6e 6b |Hey there! Thank|
00000070 69 6e 69 6e 67 20 75 73 2e 00 00 00 00 00 00 00 |ining us……..|
000000a0 73 20 66 6f 72 20 6a 6f 69 6e 69 6e 67 20 75 73 |s for joining us|
000000e0 69 6e 69 6e 67 20 75 73 2e 00 00 00 00 00 00 00 |ining us……..|
000000d0 65 21 20 54 68 61 6e 6b 73 20 66 6f 72 20 6a 6f |e! Thanks for jo|
00000030 73 20 66 6f 72 20 6a 6f 69 6e 69 6e 67 20 75 73 |s for joining us|
00000080 90 00 54 00 00 00 00 00 48 00 54 00 00 00 00 00 |..T…..H.T…..|
00000090 48 65 79 20 74 68 65 72 65 21 20 54 68 61 6e 6b |Hey there! Thank|
00000050 10 00 54 00 00 00 00 00 48 65 79 20 74 68 65 72 |..T…..Hey ther|
000000f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |…………….|
00000010 20 00 54 00 00 00 00 00 00 00 00 00 00 00 00 00 | .T………….|
You have been given final_q6.c:
// COMP1521 21T2 … final exam, question 6
#include
#include
#include
void
convert_hexdump_to_bytes (FILE *hexdump_input, FILE *byte_output)
{
// TODO
// Hint: `man 3 fscanf`
// Hint: `man 3 fseek`
// Hint: See question text for
// third hint.
}
Add code to the function convert_hexdump_to_bytes such that, given a hexdump of a file on hexdump_input, it
writes the data the hexdump represents into the given byte_output file.
You should make careful use of the address column to ensure correct ordering of the data!
HINT:
fscanf: fscanf(hexdump_input, “%x”, …)
fseek … but you should not try to fseek on hexdump_input: as it is piped input, you will never be able to
seek backwards. Instead, consider how seeking byte_output may help you.
Try implementing only ordered input first, as in the first example above. (This is a partial solution, and
could be awarded partial marks.)
NOTE:
You can assume that hexdump_input points to an already-open, valid file that you can read from.
You can assume that byte_output points to an already-open, valid, truncated file that you can write to.
http://man7.org/linux/man-pages/man3/fscanf.3.html
http://man7.org/linux/man-pages/man3/fseek.3.html
http://man7.org/linux/man-pages/man3/fseek.3.html
You can assume that hexdump will always contain the address 0x00000000, which will refer to the first 16
bytes of the file.
Although the ordering of lines may be out-of-order, each individual lines’ contents will be entirely in-order.
You can assume that there will be no missing lines; i.e., there will be no gaps in the hexdump.
There will be no empty lines in the hexdump input.
A line will never be incomplete. There will always be 16 values per line.
The human readable stripe — the end of each line, between the vertical bars, |..hello, there!.| —
should be entirely ignored.
You do not need to support squeezed output (i.e., there will be no lines consisting of a single *).
You are not permitted to run any external programs.
You are not permitted to use system, popen, posix_spawn, fork, exec, or any of their equivalents.
You do not have to perform any error checking.
In final_q6_main.c is code to read a hexdump on standard input, and write it to a named file on standard output,
which you can use for testing.
For example:
$ cat hello.dump.shuf
00000020 2f 20 66 6f 72 20 63 6f 6d 70 31 35 32 31 20 32 |/ for comp1521 2|
00000080 29 3b 0a 09 72 65 74 75 72 6e 20 30 3b 0a 7d 0a |);..return 0;.}.|
00000040 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 64 69 6f |.#include
00000010 72 6f 67 72 61 6d 20 77 72 69 74 74 65 6e 0a 2f |rogram written./|
00000070 68 65 6c 6c 6f 2c 20 77 6f 72 6c 64 21 5c 6e 22 |hello, world!\n”|
00000000 2f 2f 20 68 65 6c 6c 6f 20 77 6f 72 6c 64 20 70 |// hello world p|
$ cat hello.c
cat: hello.c: No such file or directory
$ cat hello.dump.shuf | ./final_q6 hello.c
$ cat hello.c
// hello world program written
// for comp1521 21t2 final exam!
#include
int
main (void) {
printf(“hello, world!\n”);
return 0;
}
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q6
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q6 final_q6.c
To verify your submissions for this activity:
To verify your submissions for this activity:
$ 1521 classrun -check final_q6
Question 7 (10 �����)
You have been given final_q7.c:
// COMP1521 21T2 … final exam, question 7
#include
#include
#include
#include
#include
#include
const mode_t NEW_DIR_MODE = S_IRWXU | S_IRWXG | S_IROTH | S_IXOTH;
void
cp_directory (char *dir_from, char *dir_to)
{
// TODO
// hint:
// – `man 3 opendir`
// – `man 3 readdir`
// – `man 3 closedir`
// – `man 2 mkdir`
}
Add code to the function cp_directory so that it copies the directory located at dir_from into a new directory
located at dir_to.
It should copy all the contents of the existing directory into the new directory, including both files and directories that
are contained. In other words, cp_directory should recursively copy.
For example:
$ ls
a final_q7
$ find a
a
a/hello
a/dir
a/dir/world
$ cat a/hello
hello there
$ cat a/dir/world
world!
$ ./final_q7 a b
$ ls
a b final_q7
$ find b
b
b/hello
b/dir
b/dir/world
$ cat b/hello
hello there
$ cat b/dir/world
world!
HINT:
See opendir, readdir, closedir, mkdir. stat.
You may find recursion to be helpful in this question.
NOTE:
You do not have to perform any error checking.
You can assume there is a directory located at dir_from.
You can assume that you have permissions to read from the directory located at dir_from.
You can assume that the directory located at dir_from only contains regular files and directories.
You can assume that there is not an existing directory at dir_to.
You can assume that you have permissions to write to a directory at dir_to.
The newly directory’s mode should be the given NEW_DIR_MODE.
You are not permitted to run any external programs.
You are not permitted to use system, popen, posix_spawn, fork, exec, or any of their equivalents.
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q7
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q7 final_q7.c
To verify your submissions for this activity:
http://man7.org/linux/man-pages/man3/opendir.3.html
http://man7.org/linux/man-pages/man3/readdir.3.html
http://man7.org/linux/man-pages/man3/closedir.3.html
http://man7.org/linux/man-pages/man2/mkdir.2.html
http://man7.org/linux/man-pages/man2/stat.2.html
$ 1521 classrun -check final_q7
Question 8 (10 �����)
So far, we’ve explored MIPS assembly, which we’ve fed to SPIM to run. SPIM works in two steps: first, it takes the
assembly and assembles it into real MIPS machine code; and second, it runs that machine code. Assembly
statements, like
addi $s0, $zero, 1521
add $s0, $s0, $s1
map one-to-one onto actual instructions the machine can execute, though the form the machine sees them is much
less legible — in hexadecimal, the above instructions become 0x201005f1 and 0x02118020. This encoding is a key
part of the instruction set architecture, alongside the registers and instructions, but it’s a much more obscure part,
usually only of interest to those writing compilers, assemblers, debuggers, simulators, and exam questions.
We’ll present instruction encodings like this:
the first row contains the lowest and highest bit, and the number of bits, that a field needs — 31, 6, 26, means
that the instruction goes from bit 31 to bit 26 inclusive, and is 6 bits wide;
the second row contains the names of the fields; if it’s in UPPERCASE or just a number, it’s a constant value; if it’s
in italics, it’s some sort of value to extract, like a register or immediate;
the third row displays an actual instruction’s bits; and
the fourth row displays the bits, grouped in hexadecimal.
For the add instruction above, the encoding looks like:
31 6 26 25 5 21 20 5 16 15 5 11 10 5 6 5 6 0
SPECIAL rs rt rd 00000 ADD
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 2 1 1 8 0 2 0
And for addi, the encoding looks a little different, to support the immediate value:
31 6 26 25 5 21 20 5 16 15 16 0
ADDI rs rt immediate
0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1
2 0 1 0 0 5 F 1
For this question, you need to transform the sequence of bytes that the machine would understand back into a
human-comprehensible form.
You have been given final_q8.c:
// COMP1521 21T2 … final exam, question 8
#include
#include
#include
#include
#include
#include “final_q8.h”
#include “final_q8_opcodes.h”
Instruction
decode_instruction (Word insn_word)
{
Instruction i = { .op = “[unknown]” };
/// TODO: complete this function.
return i;
}
You need to complete a function decode_instruction that takes an instruction encoded in Word, an unsigned 32-bit
integer value, and fills out the Instruction structure (defined in final_q8.h), which is made up of:
char op[INSN_LENGTH]: a field that will contain a string corresponding to the operation being performed — in
the above example, add;
bool uses_rs :1, uses_rt :1, uses_rd :1, uses_base :1, uses_imm :1: a series of Boolean bitfields
(either true or false, and exactly only one bit wide) indicating whether the rs, rt, rd, base or imm fields,
respectively, are used by this instruction — in the above example, add uses rd, rs, and rt;
Register rs, rt, rd, base: the particular register used — in the above, add’s rd and rs are $s0, and rt is
$s1; and
Word imm: an immediate value used — add takes no immediate value, though, for example, addi does.
In final_q8.h are the definitions of Word, the Instruction structure, the Register enumeration, and forward-
declarations of functions. Do not change this file.
In final_q8_opcodes.h is a (huge) table of #define’d bit-constants that represent the various opcodes known to
MIPS — even though you won’t need all of them. Do not change this file.
In final_q8_main.c are
register_names, an array of register names indexed by Register;
main, which takes a sequence of hexadecimal values as command-line arguments, and, for each command line
argument, reads it from a string into a Word, calls decode_instruction on that value, and calls
show_instruction on the result;
show_instruction, a function that attempts to print out an Instruction in a human-readable way.
While MIPS has a few hundred instructions, for this exercise you only need to implement eight, which use the two
layouts described above —
operation bits 31 to 26 bits 5 to 0
like add:
add 0b000000 (OP_SPECIAL) 0b100000 (OP_SPECIAL_ADD)
operation bits 31 to 26 bits 5 to 0
addu 0b000000 (OP_SPECIAL) 0b100001 (OP_SPECIAL_ADDU)
sub 0b000000 (OP_SPECIAL) 0b100010 (OP_SPECIAL_SUB)
subu 0b000000 (OP_SPECIAL) 0b100011 (OP_SPECIAL_SUBU)
like addi:
addi 0b001000 (OP_ADDI)
addiu 0b001001 (OP_ADDIU)
lb 0b100000 (OP_LB) (bits 25..21 are base)
lw 0b100011 (OP_LW) (bits 25..21 are base)
When your program is complete, it should behave like the following:
$ ./final_q8 0x201005f1 0x02118020
addi $s0 $zero 1521
add $s0 $s0 $s1
You are not permitted to run any external programs.
You are not permitted to use system, popen, posix_spawn, fork, exec, or any of their equivalents.
If you’re feeling creative, you could try implementing some other instructions. See the full MIPS32 manual.
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q8
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q8 final_q8.c
To verify your submissions for this activity:
$ 1521 classrun -check final_q8
Question 9 (10 �����)
Base-64 encoding is a common way of turning a sequence of bytes that may not be printable into a sequence of
definitely-printable bytes. It is commonly used in places where transmitting printable characters is required, but
where the data to be transmitted is not. For example, non-text email attachments are traditionally encoded to
Base64.
Base-64 considers its input in chunks of six bits at a time, and converting them via a lookup table into ASCII
characters. A sequence of three potentially-unprintable bytes will encode to four characters. If there are not enough
bytes at the end of input, the padding character ‘=’ is appended to the output to correct its length.
B a s e 6 4
4 2 6 1 7 3 6 5 3 6 3 4
ASCII
Hexadecimal
Binary
Base64 Q m F z Z T Y 0
010000100110000101110011011001010011011000110100
final_q9.c contains a C program that takes a sequences of bytes on standard input and calculates their base-64
encoding
A B C D E F G H
I J K L M N O P
Q R S T U V W X
Y Z a b c d e f
g h i j k l m n
o p q r s t u v
w x y z 0 1 2 3
4 5 6 7 8 9 + /
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
m
o
s
t-
s
ig
n
ifi
c
a
n
t
3
b
it
s
least-significant 3 bits
encoding.
final_q9.s contains some MIPS assembly code that reads in characters and prints
them out. It also contains an implementation of getchar, which behaves as the C
implementation would.
Modify final_q9.s such that it calculates the base-64 encoding of bytes read from
standard input.
For example:
$ echo -n Base64 | 1521 spim -file final_q9.s
QmFzZTY0
You should assume that all input bytes are possible. Base-64 is intended to allow encoding arbitrary bytes.
However, note that neither qtspim nor xspim have a conventional standard-input stream, and therefore it is not
possible to correctly detect the end of input. The provided getchar attempts to approximate it, but only spim can
receive an end-of-input, and cannot correctly indicate when it was reached, making it impossible to distinguish
between reading the NUL byte and the end of input. You do not need to fix this. You should be able to base64-
encode a NUL byte, even if one would not (in the provided code) be able to read this input.
When you think your program is working, you can run some simple automated tests:
$ 1521 autotest final_q9
When you are finished working on this activity, you must submit your work by running give:
$ give cs1521 final_q9 final_q9.s
To verify your submissions for this activity:
$ 1521 classrun -check final_q9
Submission
When you are finished working on a question, submit your work by running give.
You can run give multiple times. Only your last submission will be marked.
Don’t submit any questions you haven’t attempted.
Do not leave it to the deadline to submit your answers. Submit each question when you finish working on it. Running
autotests does not automatically submit your code.
You can check if you have made a submission with 1521 classrun -check final_q
$ 1521 classrun -check final_q0
$ 1521 classrun -check final_q1
…
$ 1521 classrun -check final_q9
Remember you have until Friday 13 August 17�30, Sydney time, to complete this exam (not including any extra time
provided by ELS conditions).
— END OF EXAMINATION. —
COMP1521 21T2 C S F d l i b h b
COMP1521 21T2: Computer Systems Fundamentals is brought to you by
the School of Computer Science and Engineering
at the University of New South Wales, Sydney.
For all enquiries, please email the class account at .edu.au
CRICOS Provider 00098G
https://www.cse.unsw.edu.au/
https://www.unsw.edu.au/
mailto:@cse.unsw.edu.au