COMP1521 21T3 —
21T2 Final Exam
Questions
COMP1521 – 21T3
Outline
Timetable
Forum
Instructions
Questions
Question 0
(10 marks)
Question 1
(10 marks)
Question 2
(10 marks)
Question 3
(10 marks)
Question 4
(10 marks)
Question 5
(10 marks)
Question 6
(10 marks)
Question 7
(10 marks)
Question 8
(10 marks)
Question 9
(10 marks)
Submission
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 Monday 29 November 13:50, Sydney time.
You can start working on examination questions
at Monday 29 November 14:00, Sydney time.
You must stop working on examination questions
at Monday 29 November 17:00, 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.
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 21t2final_q
Available Resources: Documentation
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_21t2final,
changing to this directory,
and fetching the provided code by running these commands:
mkdir -m 700 exam_21t2final
cd exam_21t2final
1521 fetch exam_21t2final
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_21t2final
Only files that don’t exist will be recreated.
All other files will remain untouched.
Question 0
(10 marks)
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:
// 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 21t2final_q0
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q0 21t2final_q0.c
To verify your submissions for this activity:
1521 classrun -check 21t2final_q0
Question 1
(10 marks)
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 21t2final_q1
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q1 21t2final_q1.c
To verify your submissions for this activity:
1521 classrun -check 21t2final_q1
Question 2
(10 marks)
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
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 21t2final_q2
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q2 21t2final_q2.s
To verify your submissions for this activity:
1521 classrun -check 21t2final_q2
Question 3
(10 marks)
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
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 21t2final_q3
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q3 21t2final_q3.c
To verify your submissions for this activity:
1521 classrun -check 21t2final_q3
Question 4
(10 marks)
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 bb 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:
b×7=b×8−b=b×23−bb×7=b×8−b=b×23−b.
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 a×ba×b
when aa is one of
17, -3, 60, or -112.
As is worked above,
the case where aa 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.
When you think your program is working,
you can run some simple automated tests:
1521 autotest 21t2final_q4
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q4 21t2final_q4.c
To verify your submissions for this activity:
1521 classrun -check 21t2final_q4
Question 5
(10 marks)
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
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 21t2final_q5
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q5 21t2final_q5.c
To verify your submissions for this activity:
1521 classrun -check 21t2final_q5
Question 6
(10 marks)
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!
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.)
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.
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 21t2final_q6
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q6 21t2final_q6.c
To verify your submissions for this activity:
1521 classrun -check 21t2final_q6
Question 7
(10 marks)
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!
See
opendir,
readdir,
closedir,
mkdir.
stat.
You may find recursion to be
helpful in this question.
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 21t2final_q7
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q7 21t2final_q7.c
To verify your submissions for this activity:
1521 classrun -check 21t2final_q7
Question 8
(10 marks)
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)
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 21t2final_q8
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q8 21t2final_q8.c
To verify your submissions for this activity:
1521 classrun -check 21t2final_q8
Question 9
(10 marks)
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.
final_q9.c contains a C program that
takes a sequences of bytes on standard input
and calculates their base-64 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 21t2final_q9
When you are finished working on this activity,
you must submit your work by running give:
give cs1521 21t2final_q9 21t2final_q9.s
To verify your submissions for this activity:
1521 classrun -check 21t2final_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 21t2final_q
1521 classrun -check 21t2final_q0
1521 classrun -check 21t2final_q1
…
1521 classrun -check 21t2final_q9
Remember you have until Monday 29 November 17:00, Sydney time,
to complete this exam (not including any extra time provided by ELS conditions).
— End of examination. —
COMP1521 21T3: 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
原文
建議更好的譯法