CSE 378 - Spring 2001

Machine Organization and Assembly Language Programming

Problem Set #3

Due Friday April 20, 2001

SPEC CHANGES/CLARIFICATIONS

1) Your code must demonstrate simple error checking concerning user inputs; ie) user cannot enter an array size > 10000
2) -1 quits, any other negative # should flag an error... ie) -2 is bad.

Assignment Goals

The goals of this assignment are to gain further experience with assembly programming, specifically, procedure linkage conventions.

The Program

You'll be writing your old friend, quicksort - a recursive, average-case O(NlogN) sorting routine - in assembly language. In case you've forgotten, here's the pseudo-code for quicksort, to sort an array of integers in ascending 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 procedures partition and quicksort, as well as a main. Your main should do the following:

Prompt the user for the size of the data set to sort (non-positive numbers should exit the program).
Prompt the user for a seed for the random number generator.
Generate an array full of random integers. We'll provide a procedure which you can use to fill an array with random numbers.
Sort the array, by calling your quicksort procedure.
Confirm that the sort was successful. We'll provide a procedure which you can use to test an array for "sortedness."
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 10000; negative size to quit):  100 
Enter the random seed:   23 
Array sorted successfully.
Enter size of array to sort (max 10000; negative size to quit):   320 
Enter the random seed:   42 
Array sorted successfully.
Enter size of array to sort (max 10000; negative size to quit):   -1 
Bye.

What We Provide

To make your life easier, we've provided some routines for filling an array with random numbers and checking if an array is sorted. The specification for these functions is:

# initRandArray
#  arguments:	$a0	base address of array of words
#		$a1	length of array (integer)
#		$a2	seed for random number generator (integer)
#  return val:	none
#  Fill in the specified number of words starting at the memory location
#  given in $a0.  Behavior is unspecified for non-positive size
#  arrays.

# isSorted
#  arguments:	$a0	base address of array of words
#		$a1	length of array (integer)
#  return val:	1 if sorted; 0 if otherwise
#  Check if given array is sorted in ascending order.
#  By default, arrays of length 1 are "sorted."  The "sortedness" of
#  non-positive length arrays is unspecified.

These routines are automatically loaded in by spim. DO NOT load another file that has these routines. If, for your own edification, you would like to look at the code for these routines, they can be found in /cse/courses/cse378/CurrentQtr/lib/hw3lib.spim. DO NOT load this file into spim.

For those of you using PCSpim at home, we have inserted the code of hw3lib.spim into trap.handler, which spim loads automatically. This is located in the course lib/ directory, i.e. /cse/courses/cse378/CurrentQtr/lib/. You can take a copy of trap.handler home with you, put that in the appropriate place in your PCSpim install, and everything should work. Note that if we update trap.handler (with bug fixes for example), you are responsible for updating any home copy you have. trap.handler will be more up-to-date than hw3lib.spim. Talk to Jon if you have any questions or problems.

Details

Your program is responsible for allocating space for the array. It should be able to hold at least 10,000 integers. You can make the array global, local to main, or allocate it dynamically using one of the syscalls. Making it global is probably the easiest method (although not great programming practice). You will be responsible for following at least the basic calling convention we described in class. In particular, we expect you to follow the guidelines for parameter passing (first four arguments in $a0-$a3, the remainder on the stack), return value (return values are passed via $v0 and $v1), and register use (a callee may not use $s0-$s7 without saving them first, and restoring them afterwards). We'd also like you to follow the stack pointer guidelines presented in class.

You are writing everything from scratch (besides the routines we provide) this time. Of course, you'd probably be wise to start from some gutted version of your 378 machine solution. As always, clarity, simplicity and efficiency are valued, as are legible comments.

Quicksort and partition are not terribly complicated procedures, but because of the recursive nature of quicksort, debugging it can sometimes be a challenge. An hour of thinking about the design will be worth 10 hours of debugging! Good design and implementation techniques will make your life easier. So start small and work incrementally towards your solution (for instance, understanding, writing, and testing partition before worrying about quicksort seems a good tack to take). In all, you shouldn't find yourself writing more than a couple pages of code (excepting comments). And the usual words to the wise apply here: START NOW!

Deliverables

We'd like an electronic submission of your program file(s). Use the command "turnin -c cse378 filename.spim" to submit your code. filename.spim should include your main, quicksort, and partition procedures. Electronic submission is due midnight Friday (4/20)! There are NO book problems to submit this time...