Let it 'C'

Prior to compilation, all C code is first processed by a pre-processor, called cpp. All cpp directives are prefixed by a "#" (pronounce "pound-sign", "sharp-sign", or more recently "hash-tag"). The pre-processor is used for defining constants, macros, and including files. Essentially, cpp inserts or replaces blocks of text where referenced.

In the example shown below a constant "N" is defined and referenced in the program. One can consider that everywhere that the symbol "N" appears in the program, where it is not part of a variable name, is substituted with the given constant value, "8" in this case. A cpp macro called "SWAP" is also defined as a shorthand for a three C statements. By convention capital letters are used for cpp constants and macro arguments. These arguments are substituted with the actual text supplied when the macro is invoked.

Within the macro a temporary variable "t" is defined. Notice that the declaration of "t" includes the "register" type modifier, which tells the compiler to store the variable being declared in a CPU register (if possible), to optimize access.

Now compile the following C program and copy the generated assembly code into the simulator

#define N 8
#define SWAP(X,Y) {register int t = X; X = Y; Y = t;}

int x = 2;
int y = 5;
int a[N] = { 6, 5, 8, 4, 2, 7, 1, 3 };

main() {
    SWAP(x,y);
    SWAP(a[1],a[2]);
}

Notice how labels are generated for the variables, "x", "y", and "a", and the function "main()". However, there is no label generated for the macro "SWAP". Examine the generated code to see if you can find the code fragments associated with the two SWAP instances.

main() {
    int x, y, z;
    x = POW2(0);
    y = POW2(10);
    z = POW2(7) - POW2(3);
}

In this example we examine several of the most frequently used C-statements and the assembly code generated by them. The function "min()" takes two arguments. The first, is the address of an "array" and the second is the "size" of the array in words. The function scans the array searching for the smallest value and returns its index. Compile the C-program shown below and load it into the miniMIPS simulator.

#define N 8

int a[N] = { 6, 5, 8, 4, 2, 7, 1, 3 };

int min(int array[], int size) {
    int i;
    int minIndex = 0;
    int minValue = array[0];

    for (i = 1; i < size; i++)
        if (array[i] < minValue) {
            minValue = array[i];
            minIndex = i;
        }
    return minIndex;
}

main() {
    return min(a,N);
}

Scan through the generated assembly code to examine the code generated for the "for-loop" and the "if" statements. Also notice how the "array" and "size" arguments to min() are passed in the registers $4 and $5, and min()'s return value is placed in $2. This is an example of the procedure linking convention discussed in class.

Selection sort is a classic sorting algorithm.  It operates iteratively by enforcing the invariant that the element in position i must be smaller than all elements in positions i+n after i iterations.  For example, after the first iteration, the element in the first position is less than all later elements. Another way to state this is that the algorithm puts the smallest element first, then it puts the smallest of the remaining elements second, then it puts the smallest of the remaining element third, etc.  The outcome is a sorted array.

The implementation shown below, specifies the position of the next minimum element using a pointer variable 'p', which is initialized to the address of 'a'.  In subsequent iterations, p is set to point to subsequent elements of 'a' using the ++ operator.

#define N 8
#define SWAP(X,Y) {register int t = X; X = Y; Y = t;}

int a[N] = { 6, 5, 8, 4, 2, 7, 1, 3 };

int min(int array[], int size) {
    int i;
    int minIndex = 0;
    int minValue = array[0];
    for (i = 1; i < size; i++)
        if (array[i] < minValue) {
            minValue = array[i];
            minIndex = i;
        }
    return minIndex;
}

main() {
    int i, j;
    int *p = a;
    for (i = 0; i < N-1; i++) {
        j = min(p,N-i);
        SWAP(a[i],a[i+j]);
        p++;
    }
}

Set a breakpoint at the "halt:" label, and then run the program. You can verify that the array "a" is sorted using a memory dump. Simply enter any address or label (in this case enter "a") into the textbox  to the right of the "Memory Dump" button and then press [Memory Dump]. This should popup a dialog showing the contents of memory locations following the specified address.

Note that the "array" argument to "min()" is an address of a memory location. This illustrates an important use of pointers seen in many programming languages. Arguments can either be a pointer to a variable in memory, which then can be accessed and modified by the called function (call-by-reference), or a argument can be a copy of the contents of a variable, which can be used by the calling function, but changes to it are invisible to the calling function (call-by-value). In C arrays and composite data structures are passed using call-by-reference, while built-in data types (char, short, int, float, and double) are passed using call-by-value. However, it is possible to specfiy call-by-reference for a built-in type  using the "address-of" operator (e.x. foo(&x);) and declaring the corresponding function argument as a pointer type (e.x. int foo(int *x) { ... }).

An alternative to selection sort is the faster "quick sort" algorithm.  Rather than searching for the smallest remaining value in each pass, quick sort chooses a "pivot" value and partitions the array values according to those that are above and below the pivot value. It then "quick sorts" the two partitions. It continues in this fashion until the partition is only one value, in which case there is nothing to do, so it returns. The version of "quick sort" shown below operates in place. This means that after partitioning, lower values are located at array entries with smaller indices than the pivot value and higher values are at higher indices. Compile and load into the simulator the code shown below.

#define N 8
#define SWAP(X,Y) {register int t = X; X = Y; Y = t;}

int a[N] = { 6, 5, 8, 4, 2, 7, 1, 3 };

void quicksort(int array[], int low, int high) {
    int pivot,i,j,k;
    if (low < high) {
        k = (low+high)>>1;
	SWAP(array[low],array[k]);
	pivot = array[low];
	i = low+1;
	j = high;
	while (i <= j) {
            while ((i <= high) && (array[i] <= pivot))
                i++;
            while ((j >= low) && (array[j] > pivot))
	        j--;
            if (i < j)
                SWAP(array[i],array[j]);
        }
	SWAP(array[low],array[j]);
        quicksort(array, low, j-1);
        quicksort(array, j+1, high);
    }
}

main() {
    quicksort(a,0,N-1);
}

Step through the first call to quicksort. Notice how, after the second SWAP() macro finishes executing, the array contents are partitioned.