Notes:
COMP2611 Fall 2020 Homework #3
No late submission will be accepted
This is an individual assignment; all works must be your own. You can discuss with your friends but never show your code to others.
Write your code in given MIPS assembly skeleton files. Add your own code under TODOs in the skeleton code. Keep other parts of the skeleton code unchanged.
Make procedure calls with the registers as specified in the skeleton (if there are any), otherwise the provided procedures may not work properly. Preserve registers whenever necessary. (Refer to the MIPS register convention on slide 76 of the ISA note set.)
Test your MIPS program with MARS emulator and make sure it can be assembled and executed. Otherwise 0 mark will be assigned.
Zip the three finished MIPS assembly files into a single zip file, homework3_
Submit your work to Canvas -> COMP2611 -> Homework 3. You can upload multiple times if there are any changes in your solution. Only the latest one before the deadline will be marked.
Task 1: Sort Array and Remove Duplicated Items (20 points)
Task 1 is to sort the given integer array in descending order and then remove the duplicated items.
Refer to the C++ implementation below and implement the sort() function in sort.s. Write your code under TODOs.
Example:
The original array is
1 874454468
The array after deleting duplicates is 87654 1
Note:
The skeleton code implements main(), print() and removeDuplicates() already. Read the skeleton code carefully before you start. It helps you to get familiar with usage of MIPS syscall, register convention and stack. Follow such convention and good practice when write you own MIPS code for all programming tasks.
Your MIPS implementation of sort() should roughly follow the C++ implementation.
Preserve registers whenever necessary, e.g. with stack. Refer to the MIPS register convention on slide 76 of the ISA note set.
Properly comment your MIPS code.
Marks will be deducted if not following the above requirements.
Mars simulator help and MIPS syscall reference is available at
https://courses.missouristate.edu/KenVollmar/MARS/Help/MarsHelpIntro.html
Reference C++ Implementation:
#include
int removeDuplicates(int a[], int n) {// A[] is sorted in ascending order already if (a == NULL) return 0;
int index = 0;
for (int i = 1; i < n; i++)
if (a[index] != a[i]) a[++index] = a[i];
return index + 1; }
void sort(int a[], int n) { /*n is the size of the array a */ int i, j, temp;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - 1 - i; j++)
if (a[j + 1] > a[j]) { /* compare the two neighbours */ temp = a[j]; /* swap a[j] and a[j+1] */
a[j] = a[j + 1];
a[j + 1] = temp; }
}
void print(int a[], int n) {
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl; }
int main(){ int A[10];
srand(time(NULL));
for (int i = 0; i < 10; i++)
A[i] = rand() % 8 + 1;
sort(A, 10);
cout << "The original array is" << endl; print(A, 10);
int length = removeDuplicates(A, 10);
cout << "The array after deleting duplicates is" << endl; print(A, length);
return 0;
}
Task 2: Draw a House (20 points)
Task 1 should have prepared your ability to write a decent MIPS program. Task 2 is to implement a MIPS program from scratch to draw a house with roof. The skeleton code drawHouse.s only provides the data segment.
The program reads a character (using MARS syscall 12) and house size (>=6) from user and then prints a simple house. Refer to the C++ code for size computation of each part.
Note:
Refer to the C++ implementation. Your MIPS program must follow similar structure and should implement each function.
Preserve registers whenever necessary, e.g. with stack. Refer to the MIPS register convention on slide 76 of the ISA note set.
Properly comment your MIPS code.
Marks will be deducted if not following the above requirements.
Reference C++ Implementation:
#include
void printLine (char symbol, int numSpace, int numSymbol) { for (int i=0; i
printLine (symbol, interval, 3*size – 2*interval); }
}
int main() {
char symbol;
int size;
cout << "Enter the symbol for House: ";
cin >> symbol;
cout << "Enter the size for House(size >= 6): “; cin >> size;
cout << endl;
printHouse (symbol, size);
return 0;
}
Task 3: Run-length encoding (20 marks)
The run-length encoding is a way to compress strings by recording the number of consecutive repeated letters. For example, the run-length encoding of AAAAA is 5A, because the letter A is repeated 5 times.
Task 3 is to implement a procedure to encode strings. For example, the input string is COOOOOMMMMPP, and the output run-length coded string should be 1C5O4M2P. The algorithm is described in the reference C++ implementation. You should implement run_encoding() in skeleton.
Your solution will be grade with several test cases. For simplicity, you can always assume:
The input string is not empty and consists of uppercase English letters only.
The length of both the input string and output string will be less than 1000.
Note:
Refer to the C++ implementation. Your MIPS program must follow similar structure and should implement each function.
Preserve registers whenever necessary, e.g. with stack. Refer to the MIPS register convention on slide 76 of the ISA note set.
Properly comment your MIPS code.
Marks will be deducted if not following the above requirements.
Reference C++ Implementation:
#include
using namespace std; char str1[1000]; // input
char str2[1000]; // output
int addLetter (int num_letter, int str2_p, char buffered_letter) { while (num_letter) {
int value = 0;
if (num_letter >= 100) {
value = num_letter/100;
num_letter %= 100;
} else if (num_letter >= 10) {
value = num_letter/10;
num_letter %= 10; } else {
value = num_letter;
num_letter %= 1; }
str2[str2_p] = value + ‘0’;
str2_p += 1; }
str2[str2_p] = buffered_letter; str2_p += 1;
return str2_p;
}
void runEncoding() { int len = 0;
int str2_p = 0;
int num_letter = 1; // number of current letter char cur_letter;
char buffered_letter = 0;
while (str1[len] != 0) {
len ++; }
for (int i=0; i
runEncoding();
cout << "The run-length encoding of the string is:" << endl;
cout << str2 << endl;
return 0; }