Assignment 8, due Oct 24Solutions
Part of
the homework for CS:2630, Fall 2019

Background: Look at machine problem 4. It asks you to write a SMAL Hawk version of Quicksort. You won't find that in a textbook or a web search, but you can find plenty of implementations of Quicksort written in C. Most of those sort arrays of integers, not arrays of strings. Look at several of them, find one with code you are comfortable with  aim for simplicity here, because you will end up having to make it work!
a) Give valid C code for a version of Quicksort that sorts an array of pointers to strings, using strcmp to compare strings. (0.5 points)
I spent some time looking at different versions, hoping to find something simple, knowing that each line would expand by the time it was turned into assembly language. The following code is based on the pseudocode for the Hoare partition scheme in the Wikipedia article on Quicksort, with one little optimization: Since we are only sorting one global array, I called it data here, there is no need to pass it as a parameter:
void qsort( int l, int h) { /* sort an array from l to h */ if (l < h) { /* there is work to do */ int low = l  1; int high = h + 1; char * pivot = data[l]; /* could use any item up to h */ for (;;) { /* Hoare partition algorithm */ do { /* low started one below base */ low = low + 1; } while (strcmp( data[low], pivot ) < 0); do { /* high started one above range */ high = high  1; } while (strcmp( data[high], pivot ) > 0); if (low >= high) break; /* high is return value */ char * temp = data[low]; data[low] = data[high]; data[high] = temp; } /* low >= high; equal, both index of values equal to pivot */ qsort( l, high ); qsort( high +1, h ); } }
Here is a second solution, with a big optimization to avoid doing any array indexing. Instead of passing integer array indices, the code expects pointers to array elements as parameters. The logic of the code remains exactly as it was in quicksort with Hoare's partitioning scheme:
void qsort( char * *l, char * *h) { /* sort an array from l to h */ if (l < h) { /* there is work to do */ char * *low = l  1; char * *high = h + 1; char * pivot = *l; /* could use any item up to h */ for (;;) { /* Hoare partition algorithm */ do { /* low started one below base */ low = low + 1; } while (strcmp( *low, pivot ) < 0); do { /* high started one above range */ high = high  1; } while (strcmp( *high, pivot ) > 0); if (low >= high) break; /* high is return value */ char * temp = *low; *low = *high; *high = temp; } /* low >= high; equal, both index of values equal to pivot */ qsort( l, high ); qsort( high + 1, h ); } }
In the above code, note that the expression p+n where p is a pointer to an object of type t increments p to point to the n^{th} consecutive object of type t. That is, it adds n*sizeof(t) to the memory address stored in p.
b) Write a main program to test it on an array of pointers to strings, printing out all the strings with puts after it is sorted. (0.5 points)
Both solutions above can be tested with this array of 10 strings:
char * data[] = { "the", "best", "way", "to", "see", "the", "country", "is", "by", "foot" }; int size = 10;
The following code tests the first version given above:
void main() { int i; qsort( 0, size  1 ); for (i = 0; i < size; i++) { puts( data[i] ); } }
To test the second version, change to call to qsort to the following:
Note: You are advised to run the code to make sure it works, but we just want it on paper. The purpose of this assignment is to set you up for MP4.
a) Write the best Hawk code you can to multiply by 73. (0.5 points)
First, note that 73 is prime, so we can't multiply a bunch of factors. So, look at the binary representation of 73 for a first hack at a solution. 73_{10} = 1001001_{2}.
MOVE R1,R3 ADDSL R3,R1,3 ; * 1001 (* 9 decimal) ADDSL R3,R1,3 ; * 1001001 (* 73 decimal)
Here is a second solution, a bit more adhoc:
MOVE R1,R3 ADDSL R1,R1,3 ; R1 = R3*1001 ADDSL R3,R1,6 ; R3 = R3*1000000 + R3*1001
There are more solutions, but none any faster than these two
b) Write C code equivalent to your answer to part a); a good compiler might replace the expression i*73 with this on a machine like the Intel Pentium where the multiply instruction is at least 10 times slower than an add. (0.5 points)
Each solution above can be written in C:
(((i << 3) + i) << 3) + i ((i << 3) + i) + (i << 6)
Problem: Give SMAL Hawk code for an unsigned divide routine allowing a 64bit dividend. Hint: The code is a surprisingly simple variation on code given in the Hawk manual and the notes. (1 point)
The following code is based on the code captioned "Binary Division on the Hawk" in Chapter 9 of the notes. The only changes required are changes to comments and the deletion of one machine instruction; changed lines in the following are marked with ***:
DIVIDEU: ; expects R3 = low 32 bits of dividend on entry *** ; R4 = high 32 bits of dividend on entry *** ; R5 = divisor, unchanged on return ; uses R6 = i, a loop counter ; returns R3 = quotient ; R4 = remainder ; quotient = low bits of dividend *** ; remainder = high bits of dividend *** LIS R6,32 ; i = 32 DIVLP: ; do { SL R3,1 ; quotient = quotient << 1, sets C bit ADDC R4,R4 ; remainder = (remainder << 1) + C CMP R4,R5 BLTU DIVNO ; if (remainder >= divisor) { SUB R4,R4,R5 ; remainder = remainder  divisor ADDSI R3,1 ; quotient = quotient + 1 DIVNO: ; } ADDSI R6,1 ; i = i  1; BGT DIVLP ; } while (i > 0) JUMPS R1 ; return