CS:2630, Homework 8, 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:

qsort( data, data + (size-1) );

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.

Background: Chapter 14 of the Hawk manual gives optimal Hawk code for multiplying by constants up to 38.

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₁₀ = 1001001₂.

        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 ad-hoc:

        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)

Background: The code for DIVIDEU given in Chapter 9 divides a 32-bit divisor into a 32-bit dividend, proucing a 32-bit quotient and a 32-bit remainder. In fact, division is well defined for a 32-bit divisor dividing into a 64-bit remainder, so that, for example, 1,000,000,000,000 divided by 1,000,000 gives 1,000,000. The dividend, in this example, can be represented in 40 bits.

Problem: Give SMAL Hawk code for an unsigned divide routine allowing a 64-bit 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

Assignment 8, due Oct 24

Solutions