Exercise 1: Fixing square

The file lab10.S contains a copy of the square() function that was used as an example in Lab 9. This function prints a number and its square. It saves its return address in X20, but it really should save the return address on the stack. (That's because square() could be called by a function that is depending on its value of X20 being saved. Remember that X2 is a "callee-saved register.")

As an easy first exercise, you should modify square() so that it saves the return address on the stack. (Always remember that the stack pointer should be a multiple of 16. Don't forget to retrieve the return address from the stack and restore the stack pointer to its original value before returning from the function!)

Exercise 2: Selection Sort

Selection Sort is a well-known algorithm for sorting an array of numbers. If there is a function maxLoc(B,count) that returns the index of the largest array element among B[0], B[1], ..., B[count-1], then selectionSort can be written as follows in C:

void selectionSort( long long int B[], long long int count ) {
    while ( count > 0 ) {
        long lont int loc = maxLoc( B, count ); // index of largest
        count = count - 1;
        long long int temp1 = B[count];  // swap B[count] and B[loc]
        long long int temp2 = B[loc];
        B[count] = temp2;
        B[loc] = temp1;
    }
}

The maxLoc function is already defined in lab10.S. Your job is to write selectionSort. There is already a "stub" function that does nothing. Since selectionSort calls maxLoc, it will need to save the return address and other values on the stack. (Remember that your selectionSort function must work with any implementation of maxLoc, so it can't depend on how this particular maxLoc uses registers. And to make sure that it will work when called by any other function, your selectionSort cannot use any callee-saved registers unless it saves their original values before using them and restores their values before returning.)

Exercise 3: Quicksort

Quicksort is another well-known function for sorting an array of numbers. It uses a subroutine that I call "quicksortStep". (You can read about Quicksort in Javanotes Section 9.1.3, if you are not familiar with it, but you do not need to understand how it works to do this exercise.) Quicksort can be written as follows in C, using quicksortStep:

void quicksort( double[] A, long long int low, long long int high) {
     if ( low >= high) {
         return;
     }
     else {
         long long int mid = quicksortStep( A, low, high );
         quicksort( A, low, mid - 1 );
         quicksort( A, mid + 1, high );
     } 
}

The quicksortStep function is already defined in lab10.S. Your job is to write quicksort. There is already a "stub" function that does nothing. Since quicksort calls itself, as well as quicksortStep, it will need to save the return address and other values on the stack.

(Warning: I didn't understand how the debugger's "Step Over" command works for a recursive function call in assembly language, and it cost me some time to realize what was happening. It does not run the entire call of the function, including any further recursive calls that it might make. It just stops at the next instruction the next time that the computer gets to that instruction. That might happen in a nested recursive call. For example, if you Step Over "BL quicksort" it does not mean that the entire quicksort process will be completed.)

Exercise 4: concat

The final exercise is to implement a function, concat, that takes two strings as parameters and returns a new string that contains the concatenation of the two parameter strings. For example, the value of concat("Hello","World") would be the string "HelloWorld". The memory for the new string should be created using the standard function malloc. You will also use two standard string manipulation functions: strlen(s), which returns the length of the string s, and strcpy(dest,src), which copies all the characters from src, including the zero at the end, into memory starting at address dest. In C, the concat function can be written as follows

char* concat( char* a, char* b ) {
    long long int aLength = strlen(a);
    long long int bLength = strlen(b);
    long long int cLength = aLength + bLength + 1;
           // the "+1" is to allow for the zero at the end
    char* newString = malloc( cLength );
    strcpy(newString, a);
    char* bPosition = newString + aLength;  // Adds aLength to the address.
    strcpy(bPosition, b);
    return newString;
}

As usual, there is a stub function in lab10.S for you to complete. You will need to add .extern declarations for malloc, strlen, and strcpy to lab10.S.