CSE 378 Homework #4

Due: Wednesday, May 1, 2002

Assignment Goals

The goals of this assignment are to gain further experience with assembly programming and, more specifically, procedure linkage conventions. We'll also ask you to answer a few written questions.

The Program

You'll be writing your old friend, quicksort - a recursive, average-case O(NlogN) sorting routine - in assembly. In case you've forgotten, here's the pseudo-code for quicksort, to sort an array of integers in non-decreasing order: 
void quicksort (integer A[], integer p, integer r) begin
  integer q;
  if p < r then
    q := partition(A, p, r)
    quicksort(A, p, q)
    quicksort(A, q+1, r)
  end if
end quicksort

integer partition (integer A[], integer p, integer q) begin
  integer pivot := A[p]
  integer i := p-1
  integer j := q+1
  while (true)
    repeat j := j-1 until (A[j] <= pivot)
    repeat i := i+1 until (A[i] >= pivot)
    if i < j then
      swap(A[i], A[j])
    else
      return j
    end if
  end loop
end partition
Your job is to write the two functions partition and quicksort, as well as a main. Your main should do the following:
  1. Prompt the user for the size of the data set to sort (non-positive numbers should exit the program).
  2. Prompt the user for a seed for the random number generator.
  3. Generate an array full of random integers. We'll provide a function which you can use to fill an array with random numbers.
  4. Sort the array, by calling your quicksort procedure.
  5. Confirm that the sort was successful. We'll provide a procedure which you can use to test an array for "sortedness."
  6. Repeat...
A sample interaction should look something like this (you must read array size and random seed in this order so we can test your programs; the actual prompts are up to you). User inputs are in bold: 
Enter size of array to sort (max 1000; negative size to quit): 100
Enter the random seed:  23
Array sorted successfully.
Enter size of array to sort (max 1000; negative size to quit):  320
Enter the random seed:  42
Array sorted successfully.
Enter size of array to sort (max 1000; negative size to quit):  -1
Bye.

What We Provide

To make your life easier, we've provided some routines (written in C--) for performing basic utility functions. The specification for these functions is: 
// Takes 3 arguments:
//   array: an address which is the base of an array
//   length: the size of the array
//   seed: a seed for the random number generator
void initRandArray(int* array, int length, int seed);

// Takes two arguments:
//   array: an address which is the base of an array
//   length: the size of the array
// Returns 1 if the array is sorted.  Zero if not.
int isSorted(int* array, int length);
These functions (and a couple other ones you might find helpful) are defined for you (see below for details).

Details

Your program is responsible for allocating space for the array. It should be able to hold at least 1000 integers. You can make the array global or local to main. Making it global is probably the easiest method. You must follow the basic convention described in class. In particular, since you will be interacting with code that has been generated by our compiler, you should use the convention used by the compiler:
  1. The compiler passes all arguments on the stack. This is less efficient, but easier to implement (in the general case) than the real MIPS convention. On procedure entry, the stack pointer points at the first argument. 4($sp) points to the second argument, and so on...
  2. The compiler obeys the MIPS conventions regarding the T and S registers -- in other words, it may crush values in registers $t0-$t9 without saving them first. If it uses $s0-$s7, it will restore them to their previous state.
  3. Return values are returned in register $v0.
  4. $sp and $fp are treated as "callee saved" registers by the compiler: in other words, it will always be put back to the way they were before the call.
During testing, we will call your quicksort (and partition) functions from our own driver program -- hence you must follow the procedure call convention!

Quicksort and partition are not terribly complicated procedures, but because of the recursive nature of quicksort, debugging it can be a real pain. In all, you shouldn't find yourself writing more than a couple pages of code (excepting comments). As always, good design/implementation technique will make your life easier. Start small and work incrementally towards solution (for instance, understanding, writing, testing partition before worrying about quicksort seems logical, but you knew that already).

Putting it all Together

You'll write an assembly file (call it "quicksort.s"). This file should define three functions (main, quicksort, partition). You'll need to assemble this file (to produce quicksort.o). To test everything, you'll need to link quicksort.o with the following files: prologue.o, qlib.o, syscall.o, using a link line like this: java asm.Linker prologue.o quicksort.o qlib.o syscall.o. Here are links to the various files you'll need to build your executable:
  1. qlib.c: helper functions
  2. syscall.s: system call wrappers
  3. prologue.s: a wrapper around main (calls main and then calls exit()).
(You should only have to compile/assemble each of the above once, because they should never change during development.)

References

You'll probably want to keep the following references handy:
  1. Cebollita Main Page
  2. C-- Compiler and Language Overview

Written Questions

Please answer Ex. 2.10, 2.11, and 2.12 from H & P.

Extra Credit

Please check online for extra credit options.
dugan@cs.washington.edu