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 21t2final_q0.c:
// COMP1521 21T2 … final exam, question 0
#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
Sample solution for 21t2final_q0.c
// COMP1521 21T2 … final exam, question 0
#include
#include
int count_leading_zeroes(uint32_t x) { int leading_zero_count = 0;
for (int i = 8 * (sizeof x) – 1; i >= 0; i–) {
unsigned ith_msb = (x >> i) & 1; if (ith_msb != 0) {
return leading_zero_count; }
leading_zero_count++; }
return leading_zero_count; }
// using gcc intrinsic – faster but not portable
int count_leading_zeroes1(uint32_t x) { return x ? __builtin_clz(x) : 32;
}
Question 1 (10 MARKS)
You have been given 21t2final_q1.c:
// COMP1521 21T2 … final exam, question 1
#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
Sample solution for 21t2final_q1.c
// COMP1521 21T2 … final exam, question 1
#include
#define BITS 8
void and(bool x[BITS], bool y[BITS], bool result[BITS]) { for (int i = 0; i < BITS; i++) {
result[i] = x[i] && y[i]; }
}
void or(bool x[BITS], bool y[BITS], bool result[BITS]) { for (int i = 0; i < BITS; i++) {
result[i] = x[i] + y[i]; }
}
void xor(bool x[BITS], bool y[BITS], bool result[BITS]) { for (int i = 0; i < BITS; i++) {
result[i] = x[i] != y[i]; }
}
void not(bool x[BITS], bool result[BITS]) { for (int i = 0; i < BITS; i++) {
result[i] = !x[i]; }
}
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 21t2final_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 21t2final_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: odd_parity_str:
.text
main:
.asciiz “the parity is even\n”
.asciiz “the parity is odd\n”
$v0, 5
li 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 21t2final_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 21t2final_q2.s
3
the parity is even
1521 spim -file 21t2final_q2.s 4
the parity is odd
1521 spim -file 21t2final_q2.s 5
the parity is even
1521 spim -file 21t2final_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
Sample solution for 21t2final_q2.s
# 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”
$v0, 5 $t0, $v0
.text
main:
li syscall move
# input is in $t0
li $t1, 0
li $t2, 0 main__loop:
srlv $t3, $t0, $t1
andi $t3, $t3, 1
addu $t2, $t2, $t3
addiu $t1, $t1, 1
bne $t1, 32, main__loop
rem $t0, $t2, 2
bnez $t0, main__parity_odd la $a0, even_parity_str
b main__end
main__parity_odd:
la $a0, odd_parity_str
main__end:
li $v0, 4 syscall
li $v0, 0 jr $ra
Question 3 (10 MARKS)
You have been given 21t2final_q3.c:
// COMP1521 21T2 … final exam, question 3
#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
Sample solution for 21t2final_q3.c
// COMP1521 21T2 … final exam, question 3 #include
#include
void cp(char *path_from, char *path_to) {
// Question sepcified – n error checking is necessary FILE *file_from = fopen(path_from, “r”);
assert(file_from);
FILE *file_to = fopen(path_to, “w+”); assert(file_to);
int byte;
while ((byte = fgetc(file_from)) != EOF) {
fputc(byte, file_to); }
}
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 21t2final_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
Sample solution for 21t2final_q4.c
// COMP1521 21T2 ... final exam, question 4 ... example solution
#include
long mul(long a, long b_) { unsigned long b = b_;
if (a == 17) {
return (b << 4) + b;
}
if (a == -3) {
return -(b << 2) + b; }
if (a == 60) {
return (b << 6) - (b << 2);
}
if (a == -112) {
return -(b << 7) + (b << 4); }
// Invalid inputs will simply abort.
abort(); }
Question 5 (10 MARKS)
You have been given 21t2final_q5.c:
// COMP1521 21T2 ... final exam, question 5
#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
Sample solution for 21t2final_q5.c
// COMP1521 21T2 … final exam, question 5
#include
void
print_utf8_count (FILE *file) {
unsigned long totals[4] = { 0 };
int byte;
while ((byte = fgetc (file)) != EOF) {
int rune_size;
if (! (byte & 0x80)) rune_size = 1; else if (! (byte & 0x20)) rune_size = 2;
else if (! (byte & 0x10)) rune_size = 3; else if (! (byte & 0x08)) rune_size = 4; else abort();
totals[rune_size – 1]++;
for (int i = 0; i < rune_size - 1; i++) {
fgetc (file);
} }
for (int i = 1; i <= 4; i++) {
printf("%d-byte UTF-8 characters: %lu\n", i, totals[i - 1]);
} }
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 4865792074686572 6521205468616e6b |Heythere!Thank| 00000030 7320666f72206a6f 696e696e67207573 |sforjoiningus| 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 6521205468616e6b 7320666f72206a6f |e!Thanksforjo| 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 4865792074686572 6521205468616e6b |Heythere!Thank| 000000a0 7320666f72206a6f 696e696e67207573 |sforjoiningus| 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 6521205468616e6b 7320666f72206a6f |e!Thanksforjo| 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 6521205468616e6b 7320666f72206a6f |e!Thanksforjo| 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 4865792074686572 6521205468616e6b |Heythere!Thank| 00000070 69 6e 69 6e 67 20 75 73 2e 00 00 00 00 00 00 00 |ining us........| 000000a0 7320666f72206a6f 696e696e67207573 |sforjoiningus| 000000e0 69 6e 69 6e 67 20 75 73 2e 00 00 00 00 00 00 00 |ining us........| 000000d0 6521205468616e6b 7320666f72206a6f |e!Thanksforjo| 00000030 7320666f72206a6f 696e696e67207573 |sforjoiningus| 00000080 90 00 54 00 00 00 00 00 48 00 54 00 00 00 00 00 |..T.....H.T.....| 00000090 4865792074686572 6521205468616e6b |Heythere!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 21t2final_q6.c:
// COMP1521 21T2 ... final exam, question 6
#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
00000080
00000040
00000030
00000060
00000050
00000010
00000070
00000000
cat hello.c
cat: hello.c: No such file or directory cat hello.dump.shuf | ./final_q6 hello.c cat hello.c
2f20666f7220636f 6d70313532312032 |/forcomp15212| 29 3b 0a 09 72 65 74 75 72 6e 20 30 3b 0a 7d 0a |);..return 0;.}.| 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 64 69 6f |.#include
// 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
Sample solution for 21t2final_q6.c
// COMP1521 21T2 … final exam, question 6 #include
#include
void convert_hexdump_to_bytes(FILE *hexdump_input, FILE *byte_output) { int offset;
while (fscanf(hexdump_input, “%x”, &offset) == 1) { fseek(byte_output, offset, SEEK_SET);
for (int i = 0; i < 16; i++) { int byte;
fscanf(hexdump_input, "%x", &byte); fputc(byte, byte_output);
}
int byte;
while ((byte = fgetc(hexdump_input)) != '\n' && byte != EOF) {
} }
}
Question 7 (10 MARKS)
You have been given 21t2final_q7.c:
// COMP1521 21T2 ... final exam, question 7 #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
Sample solution for 21t2final_q7.c
// COMP1521 21T2 … final exam, question 7 #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) { DIR *from = opendir(dir_from);
mkdir(dir_to, NEW_DIR_MODE);
struct dirent *dirent;
while ((dirent = readdir(from)) != NULL) {
char *filename = dirent->d_name;
if (!strcmp(filename, “.”) || !strcmp(filename, “..”)) {
continue; }
size_t from_size = strlen(dir_from) + strlen(filename) + 2; char *file_from = malloc(from_size);
snprintf(file_from, from_size, “%s/%s”, dir_from, filename);
size_t to_size = strlen(dir_to) + strlen(filename) + 2; char *file_to = malloc(to_size);
snprintf(file_to, to_size, “%s/%s”, dir_to, filename);
struct stat statbuf; stat(file_from, &statbuf);
if (S_ISDIR(statbuf.st_mode)) { cp_directory(file_from, file_to);
} else {
FILE *from_file = fopen(file_from, “r”); FILE *to_file = fopen(file_to, “w”);
int byte;
while ((byte = fgetc(from_file)) != EOF) {
fputc(byte, to_file); }
fclose(from_file); fclose(to_file);
} }
closedir(from); }
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
00000010000100011000000000100000 02118020
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
00100000000100000000010111110001
201005F1
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 21t2final_q8.c:
// COMP1521 21T2 … final exam, question 8
#include
#include “21t2final_q8.h”
#include “21t2final_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 21t2final_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 21t2final_q8.h are the definitions of Word, the Instruction structure,
the Register enumeration, and forward-declarations of functions. Do not change this file.
In 21t2final_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 21t2final_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:
0b100000 (OP_SPECIAL_ADD)
0b100001 (OP_SPECIAL_ADDU) 0b100010 (OP_SPECIAL_SUB) 0b100011 (OP_SPECIAL_SUBU)
like addi:
(bits 25..21 are base) (bits 25..21 are base)
add 0b000000 (OP_SPECIAL) addu 0b000000 (OP_SPECIAL) sub 0b000000 (OP_SPECIAL) subu 0b000000 (OP_SPECIAL)
addi 0b001000 (OP_ADDI) addiu 0b001001 (OP_ADDIU)
lb 0b100000 (OP_LB) lw 0b100011 (OP_LW)
When your program is complete, it should behave like the following:
./21t2final_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
Sample solution for 21t2final_q8.c
// COMP1521 21T2 … final exam, question 8
#include
#include “21t2final_q8.h”
#include “21t2final_q8_opcodes.h”
// One approach: a bitfielded struct and/or union
typedef struct insn {
Word operands : 26; Word opcode : 6;
} insn;
typedef struct insn_special { Word opcode2 : 6;
Word flags : 5;
Register rd : 5;
Register rt : 5;
Register rs : 5;
Word opcode : 6; } insn_special;
typedef struct insn_imm { Word imm : 16; Register rt : 5; Register rs : 5;
Word opcode : 6; } insn_imm;
Instruction decode_instruction(Word insn_word) {
Word *iword = &insn_word;
insn *ix = (insn *)iword;
insn_special *is = (insn_special *)iword; insn_imm *im = (insn_imm *)iword;
Instruction i = { .op = “[unknown]” }; switch (ix->opcode) {
case OP_SPECIAL:
switch (is->opcode2) { case OP_SPECIAL_ADD: case OP_SPECIAL_ADDU: case OP_SPECIAL_SUB: case OP_SPECIAL_SUBU:
i = (Instruction){ .uses_rs = true,
.rs = is->rs, .uses_rt = true, .rt = is->rt, .uses_rd = true, .rd = is->rd };
if (is->opcode2 == OP_SPECIAL_ADD) strcpy(i.op, “add”);
if (is->opcode2 == OP_SPECIAL_ADDU) strcpy(i.op, “addu”);
if (is->opcode2 == OP_SPECIAL_SUB) strcpy(i.op, “sub”);
if (is->opcode2 == OP_SPECIAL_SUBU) strcpy(i.op, “subu”);
break; }
break;
case OP_ADDI:
case OP_ADDIU:
i = (Instruction){ .uses_rs = true,
.rs = im->rs, .uses_rt = true,
.rt = im->rt, .uses_imm = true, .imm = im->imm };
if (ix->opcode == OP_ADDI)
strcpy(i.op, “addi”);
if (ix->opcode == OP_ADDIU)
strcpy(i.op, “addiu”); break;
case OP_LB: case OP_LW:
i = (Instruction){ .uses_base = true, .base = im->rs,
.uses_rt = true,
.rt = im->rt, .uses_imm = true, .imm = im->imm };
if (ix->opcode == OP_LB)
strcpy(i.op, “lb”);
if (ix->opcode == OP_LW)
strcpy(i.op, “lw”); break;
}
return i; }
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.
For example:
echo -n Base64 | 1521 spim -file 21t2final_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
Sample solution for 21t2final_q9.s
# COMP1521 21T2 … final exam, question 9
.globl main
.globl base64_init .globl base64_putbyte .globl base64_finish
.text
main: main__prologue:
addiu $sp, $sp, -4
sw $ra, ($sp) main__body:
jal base64_init
main__getc_cond:
## if ((c = getchar()) != EOF) goto main__getc_f
jal getchar
bltz $v0, main__getc_f
## base64_putbyte(c)
move $a0, $v0
jal base64_putbyte
j main__getc_cond
main__getc_f:
jal base64_finish
## putchar(‘\n’)
li $v0, 11 li $a0, ‘\n’ syscall
main__epilogue:
lw $ra, ($sp) addiu $sp, $sp, 4
## return 0;
li $v0, 0 jr $ra
########################################################################
.data
.align 3 b64_buffer:
.space 2 .align 3
b64_bits:
.space 4
######################################################################## # .TEXT
.text
base64_init:
# Arguments: none # Returns: 0
# Frame: none
# Uses: none
# Clobbers: none
sh $zero, b64_buffer sw $zero, b64_bits
jr $ra
######################################################################## # .TEXT
.text
base64_lookup:
## Arguments:
## – $a0: bits (uint8_t) ## Returns: uint8_t ## Frame: none
## Uses: none ## Clobbers: none
.data
BASE64_LOOKUP:
.asciiz
“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/”
.text
li $v0, 0x3f
and $v0, $a0, $v0
lb $v0, BASE64_LOOKUP($v0) jr $ra
######################################################################## # .TEXT
.text
base64_putbyte:
## Arguments:
## – $a0: byte (uint8_t)
## Returns:
## Frame:
## Uses:
## Clobbers: $t0, $t1, $t2
0
none
$t0, $t1, $t2
b64putb__prologue:
addiu $sp, $sp, -4 sw $ra, ($sp)
b64putb__body:
## b64_buffer <<= 8;
lh $t0, b64_buffer sll $t0, $t0, 8
sh $t0, b64_buffer
## b64_buffer |= byte;
lh $t0, b64_buffer or $t0, $t0, $a0
sh $t0, b64_buffer
## b64_bits += 8
lw $t1, b64_bits addiu $t1, $t1, 8 sw $t1, b64_bits
b64putb__bits_cond:
## if (b64_bits < 6) goto b64putb__bits_f
lw $t1, b64_bits
li $t2, 6
blt $t1, $t2, b64putb__bits_f
## b64_bits -= 6
sub $t1, $t1, $t2 sw $t1, b64_bits
## part = b64_buffer >> b64_bits
lh $t0, b64_buffer srlv $t0, $t0, $t1
## base64_lookup (part)
move $a0, $t0
jal base64_lookup
## putchar (base64_lookup (part)) move $a0, $v0
li $v0, 11
syscall
j b64putb__bits_cond
b64putb__bits_f:
b64putb__epilogue:
lw $ra, ($sp)
addiu $sp, $sp, 4
## return 0
li $v0, 0 jr $ra
######################################################################## # .TEXT
.text
base64_finish:
## Arguments: none ## Returns: 0
## Frame: none ## Uses: none ## Clobbers: none
b64fini__prologue:
addiu $sp, $sp, -4 sw $ra, ($sp)
b64fini__body:
## if (b64_bits <= 0) goto b64fini_bits_f
lw $t0, b64_bits
blez $t0, b64fini__bits_f
## padding = 6 - b64_bits
li $t1, 6
sub $t1, $t1, $t0
## b64_buffer <<= padding;
lh $t0, b64_buffer sllv $t0, $t0, $t1
## base64_lookup (b64_buffer)
move $a0, $t0
jal base64_lookup
## putchar (base64_lookup (b64_buffer)) move $a0, $v0
li $v0, 11
syscall
b64fini__padding_cond:
## if (padding <= 0) goto b64fini__padding_f
blez $t1, b64fini__padding_f ## putchar ('=');
li $a0, '='
li $v0, 11
syscall
## padding -= 2;
addiu $t1, $t1, -2
j b64fini__padding_cond
b64fini__padding_f:
b64fini__bits_f:
## b64_bits = 0;
sw $zero, b64_bits
b64fini__epilogue:
lw $ra, ($sp) addiu $sp, $sp, 4
## return 0;
li $v0, 0
jr $ra
######################################################################## # .TEXT
.text
getchar:
# This is a very simple `getchar(3)’-alike, because while # service call 12 should get a single character, it can’t! #
# (You may recognise this code from `snake.s’.)
#
# Arguments: none
# Returns:
# Frame:
# Uses:
# Clobbers: $a0, $a1, $v0
la $a0, getchar_buf
the byte read, or -1 if failed.
none
$a0, $a1, $v0
li $a1, 2 li $v0, 8 syscall
.data
.align
getchar_buf:
# syscall 8: read_string
2
.space 2
.text
lb $v0, getchar_buf
beq $v0, 0, getchar__nul j getchar__default
getchar__nul:
li $v0, -1 getchar__default:
jr $ra