20T3 Final Exam

You have been given 20t3final_q1.s, a MIPS assembler program that reads one number and then prints it.

Add code to 20t3final_q1.s to make it equivalent to this C program:

// COMP1521 20T3 final exam Q1 C reference

// print (x + y) * (x - y)

#include <stdio.h>

int main(void) {
    int x, y;

    scanf("%d", &x);
    scanf("%d", &y);
    printf("%d\n", (x + y) * (x - y));

    return 0;
}

In other words, it should read two numbers, x and y, and print (x + y) * ( x - y).

For example:

1521 mipsy 20t3final_q1.s
5
8
-39
1521 mipsy 20t3final_q1.s
6
5
11
1521 mipsy 20t3final_q1.s
5
6
-11
1521 mipsy 20t3final_q1.s
42
42
0

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q1

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q1 20t3final_q1.s

To verify your submissions for this activity:

1521 classrun -check 20t3final_q1

You have been given 20t3final_q2.c, a stub of a C program.

Your task is to add code to this function in 20t3final_q2.c:

// given a uint32_t,
// return 1 iff the least significant bit
// is equal to the most significant bit
// return 0 otherwise
int final_q2(uint32_t value) {
    (void) value; // REPLACE ME WITH YOUR CODE
    return 42;    // REPLACE ME WITH YOUR CODE
}

Add code to the function final_q2 so that, given a uint32_t value, it returns 1 iff the least significant (bottom) bit of value is equal to the most significant (top) bit of value

final_q2 should return 0 otherwise.

For example, given the hexadecimal value 0x12345678 which is 00010010001101000101011001111000 in binary, final_q2 should return 1, because the least significant bit is 0 and the most most significant bit is 0.

Similarly, given the hexadecimal value 0x12345679 which is 00010010001101000101011001111001 in binary, final_q2 should return 0, because the least significant bit is 1 and the most most significant bit is 0.

You must only use bitwise operators to implement 20t3final_q2.

For example:

dcc 20t3final_q2.c test_20t3final_q2.c -o 20t3final_q2
./20t3final_q2 0x00000000
20t3final_q2(0x00000000) returned 1
./20t3final_q2 0x00000001
20t3final_q2(0x00000001) returned 0
./20t3final_q2 0x00000100
20t3final_q2(0x00000100) returned 1
./20t3final_q2 0x00000101
20t3final_q2(0x00000101) returned 0
./20t3final_q2 0x12345656
20t3final_q2(0x12345656) returned 1
./20t3final_q2 0x12345657
20t3final_q2(0x12345657) returned 0
./20t3final_q2 0xffffffff
20t3final_q2(0xffffffff) returned 1
./20t3final_q2 0xfffffffe
20t3final_q2(0xfffffffe) returned 0
./20t3final_q2 0x7fffffff
20t3final_q2(0x7fffffff) returned 0
./20t3final_q2 0x7ffffffe
20t3final_q2(0x7ffffffe) returned 1

You can also use make(1) to build your code:

make 20t3final_q2

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q2

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q2 20t3final_q2.c

To verify your submissions for this activity:

1521 classrun -check 20t3final_q2

Write a C program, 20t3final_q3.c, which takes two names of environment variables as arguments. 20t3final_q3.c should print 1 iff both environment variables are set to a similar integer value.

20t3final_q3.c should print 0 otherwise.

Two integer values are similar if they differ by, strictly, less than 10.

So 37 and 42 are similar.

So 52 and 42 are not similar.

An unset environment variable should be assumed to have value 42

The shell command export sets an environment variable to a value; the shell command unset unsets an environment variable.

In the following example, export is used to set the environment variables VAR1, VAR2 and VAR3 and unset is used to ensure environment variable VAR4 is not set.

export VAR1=40
export VAR2=45
export VAR3=55
unset VAR4
dcc 20t3final_q3.c -o 20t3final_q3
./20t3final_q3 VAR1 VAR2
1
./20t3final_q3 VAR3 VAR2
0
./20t3final_q3 VAR2 VAR4
1
./20t3final_q3 VAR4 VAR3
0

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q3

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q3 20t3final_q3.c

To verify your submissions for this activity:

1521 classrun -check 20t3final_q3

You have been given 20t3final_q4.s, a MIPS assembler program that reads one number and then prints it.

Add code to 20t3final_q4.s to make it equivalent to this C program:

// COMP1521 20T3 final exam Q4 C reference

// print low - high

#include <stdio.h>

int main(void) {
    int low = 0;
    int high = 100;
    while (low < high) {
        int x;
        scanf("%d", &x);
        low = low + x;
        high = high - x;
    }
    printf("%d\n", low - high);
    return 0;
}

In other words, it should read numbers until low is greater or equal to high, and print low - high.

For example:

1521 mipsy 20t3final_q4.s
10
20
25
10
1521 mipsy 20t3final_q4.s
1
2
4
8
16
32
26
1521 mipsy 20t3final_q4.s
100
100
1521 mipsy 20t3final_q4.s
10
10
10
10
10
0

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q4

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q4 20t3final_q4.s

To verify your submissions for this activity:

1521 classrun -check 20t3final_q4

We need to a copy a file without some of the bytes at the end of the file.

Write a C program, 20t3final_q5.c which takes 3 arguments.

Its first argument will be an integer, n, the number of bytes not to be included.
Its second argument will be the name of an existing file.
Its third argument will be the name of the file to be created.

20t3final_q5.c should copy the bytes of the existing file to the new file except for the last n bytes.

If the existing file has n bytes or less, the new files should still be created, but with zero bytes.

For example:

dcc 20t3final_q5.c -o 20t3final_q5
echo hello >hello.txt
./20t3final_q5 2 hello.txt new.txt
ls -l hello.txt new.txt
-rw-r--r-- 1 z5555555 z5555555 6 Nov 26 16:28 hello.txt
-rw-r--r-- 1 z5555555 z5555555 4 Nov 26 16:29 new.txt
xxd hello.txt
00000000: 6865 6c6c 6f0a                           hello.
xxd new.txt
00000000: 6865 6c6c                                hell

Note new.txt has the same contents as hello.txt except it is 2 bytes shorter.

The last two bytes of hello.txt (ASCII 'o' and '\n') were not copied to new.txt.

./20t3final_q5 2000 hello.txt file.txt
ls -l hello.txt file.txt
-rw-r--r-- 1 z5555555 z5555555 0 Nov 26 16:30 file.txt
-rw-r--r-- 1 z5555555 z5555555 6 Nov 26 16:28 hello.txt
xxd file.txt

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q5

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q5 20t3final_q5.c

To verify your submissions for this activity:

1521 classrun -check 20t3final_q5

We need to count the number of bits which are set in a file. A bit is said to be set if it is 1.

Write a C program, 20t3final_q6.c, which takes a single filename as its argument.

20t3final_q6.c should read the bytes of the file, counting the number of bits that are set (1) in each byte.

20t3final_q6.c should print one line of output containing the total number of bits which were set.

You must match the output format in the example below exactly.

dcc 20t3final_q6.c -o 20t3final_q6
echo > file0
xxd file0
00000000: 0a                                       .
./20t3final_q6 file0
file0 has 2 bits set
echo hello world > file1
xxd file1
00000000: 6865 6c6c 6f20 776f 726c 640a            hello world.
./20t3final_q6 file1
file1 has 47 bits set
./20t3final_q6 20t3final_q6.0.bin
20t3final_q6.0.bin has 1024 bits set
./20t3final_q6 20t3final_q6.1.bin
20t3final_q6.1.bin has 8084 bits set
./20t3final_q6 20t3final_q6.2.bin
20t3final_q6.2.bin has 9720 bits set

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q6

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q6 20t3final_q6.c

To verify your submissions for this activity:

1521 classrun -check 20t3final_q6

You have been given 20t3final_q7.s, a MIPS assembler program which implements all but one function of this C program.

// COMP1521 20T3 final exam Q7 C reference

#include <stdio.h>

void read_array(int rows, int cols, int a[rows][cols]);
void reflect(int rows, int cols, int a[rows][cols], int b[cols][rows]);
void print_array(int rows, int cols, int a[rows][cols]);

int main(void) {
    int rows;
    int cols;
    scanf("%d", &rows);
    scanf("%d", &cols);
    int array1[rows][cols];
    int array2[cols][rows];
    read_array(rows, cols, array1);
    reflect(rows, cols, array1, array2);
    print_array(rows, cols, array1);
	printf("\n");
    print_array(cols, rows, array2);
}


void read_array(int rows, int cols, int a[rows][cols]) {
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            scanf("%d", &a[r][c]);
        }
    }
}


void reflect(int rows, int cols, int a[rows][cols], int b[cols][rows]) {
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            b[c][r] = a[r][c];
        }
    }
}


void print_array(int rows, int cols, int a[rows][cols]) {
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            printf("%d ", a[r][c]);
        }
        printf("\n");
    }
}

The function which has not been implemented is named reflect.

Add MIPS instructions for the function reflect to 20t3final_q7.s.

There are comments in 20t3final_q7.s which indicate where the MIPS instructions should be added.

20t3final_q7.s should then be equivalent to the above C program:

For example:

1521 mipsy 20t3final_q7.s
1
2
45
37
45 37

45
37
1521 mipsy 20t3final_q7.s
3
2
14
15
16
17
18
19
14 15
16 17
18 19

14 16 18
15 17 19
1521 mipsy 20t3final_q7.s < 20t3final_q7.input.txt
0 1
2 3
4 5
6 7
8 9

0 2 4 6 8
1 3 5 7 9

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q7

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q7 20t3final_q7.s

To verify your submissions for this activity:

1521 classrun -check 20t3final_q7

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q8

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q8 20t3final_q8.s

To verify your submissions for this activity:

1521 classrun -check 20t3final_q8

You have been given 20t3final_q9.s, a MIPS assembler program which implements all but 3 functions of this C program.

// COMP1521 20T3 final exam Q9 C reference

#include <stdio.h>

void sort(int n, int a[]);
int partition(int n, int a[]);
void swap(int *x, int *y);
void read_array(int n, int a[n]);
void print_array(int n, int a[n]);

int main(void) {
    int size;
    scanf("%d", &size);
    int array[size];
    read_array(size, array);
    sort(size, array);
    print_array(size, array);
}

void sort(int n, int a[]) {
    if (n > 1) {
        int p = partition(n, a);
        sort(p, a);
        sort(n - (p + 1), a + p + 1);
    }
}

int partition(int n, int a[]) {
    int pivot_value = a[n - 1];
    int i = 0;
    for (int j = 0; j < n; j++) {
        if (a[j] < pivot_value) {
            swap(&a[i], &a[j]);
            i = i + 1;
        }
    }
    swap(&a[i], &a[n - 1]);
    return i;
}

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void read_array(int n, int a[]) {
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
}

void print_array(int n, int a[]) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

The functions which have not been implemented are named sort, partition and swap.

Add MIPS instructions for the functions sort, partition and swap to 20t3final_q9.s.

There are comments in 20t3final_q9.s which indicate where the MIPS instructions should be added.

20t3final_q9.s should then be equivalent to the above C program.

For example:

1521 mipsy 20t3final_q9.s
3
15
18
9
9 15 18
1521 mipsy 20t3final_q9.s
4
19
4
81
1
1 4 19 81
1521 mipsy 20t3final_q9.s
5
9
4
8
1
7
1 4 7 8 9

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q9

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q9 20t3final_q9.s

To verify your submissions for this activity:

1521 classrun -check 20t3final_q9

Your task is to write a program named 20t3final_q10.c which executes a specified command with arguments it reads from standard input.

Your program should read lines of input from stdin until end-of-file and execute the command once for each line of input.

The command to execute will be specified as your program's first command line argument.

Each line will contain the arguments to execute the command with. The arguments will be separated by one or more spaces.

You must execute the command with posix_spawnp(3).

For example:

dcc 20t3final_q10.c -o 20t3final_q10
./20t3final_q10 cp
file1 file1.backup
file2 file2.backup
file3 file3.backup

cp file1 file1.backup
cp file2 file2.backup
cp file3 file3.backup

For example:

./20t3final_q10 cp file
file.backup1
file.backup2
file.backup3
file.backup4

cp file file.backup1
cp file file.backup2
cp file file.backup3
cp file file.backup4

For example:

./20t3final_q10 ls -l -a
  20t3final_q1.s    
   20t3final_q2.c   20t3final_q3.c      20t3final_q4.s

-rw-r--r-- 1 z5555555 z5555555 42 Nov 28 13:08 20t3final_q1.s
-rw-r--r-- 1 z5555555 z5555555 42 Nov 28 13:21 20t3final_q2.c
-rw-r--r-- 1 z5555555 z5555555 42 Nov 28 13:39 20t3final_q3.c
-rw-r--r-- 1 z5555555 z5555555 42 Nov 28 13:58 20t3final_q4.s

ls -l -a 20t3final_q1.s
ls -l -a 20t3final_q2.c 20t3final_q3.c 20t3final_q4.s

For example:

./20t3final_q10
   This is   a  difficult exam   question!

This is a difficult exam question!

echo This is a difficult exam question!

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q10

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q10 20t3final_q10.c

To verify your submissions for this activity:

1521 classrun -check 20t3final_q10

We need a program to check if the same files are present in two directory trees.

Write a C program, 20t3final_q11.c, which is given either 2 arguments which are the pathnames of directories.

20t3final_q11.c should print a single line of output containing 4 integers:

• number of files which are present at the same position in both directory trees and are the same size.
• number of files which are present at the same position in both directory trees but are different sizes.
• number of files which are present only in the first directory tree.
• number of files which are present only in the second directory tree.

For example, if we are comparing the directory trees dir1 and dir2. and the file dir1/1521/lab09/main.c exists in the first directory tree,

We consider it present in the second directory tree only if the file dir2/1521/lab09/main.c exists.

Other files named main.c elsewhere in the second directory tree, e.g. dir2/2521/lab05/main.c are not counted.

When a file is present at the same relative pathname in both directory tree 20t3final_q11.c does not have check it contains the same contents (bytes), just whether both files are the same size (number of bytes).

For example:
these commands create 2 directory tree named d1 and d2 containing the same 3 files.

mkdir -p d1/b/c
echo hello andrew > d1/file1
echo bye andrew > d1/b/file2
echo 1 > d1/b/c/one
mkdir -p d2/b/c
echo HELLO andrew > d2/file1
echo Bye Andrew > d2/b/file2
echo 2 > d2/b/c/one

find d1 d2 -type f | xargs stat -c '%3s %n'
 13 d1/file1
 11 d1/b/file2
  2 d1/b/c/one
 13 d2/file1
 11 d2/b/file2
  2 d2/b/c/one

dcc 20t3final_q11.c -o 20t3final_q11
./20t3final_q11 d1 d2
3 0 0 0

echo hello everyone >d1/file1
./20t3final_q11 d1 d2
2 1 0 0

echo 3 > d2/b/c/three
./20t3final_q11 d1 d2
2 1 0 1

echo 3 > d1/b/three
./20t3final_q11 d1 d2
2 1 1 1

When you think your program is working, you can run some simple automated tests:

1521 autotest 20t3final_q11

When you are finished working on this activity, you must submit your work by running give:

give cs1521 20t3final_q11 20t3final_q11.c

To verify your submissions for this activity:

1521 classrun -check 20t3final_q11