A commonly used UNIX command is sort. In its simplest form, it reads lines from standard input, sorts them into ascending (i.e. alphabetical, i.e. lexicographic) order as defined by the strcmp function, and prints them to standard output. For example, if the file proverb contains these lines:
Learning is a treasure which accompanies its owner everywhere. -- Chinese proverb
then the command
--> sort < proverb
prints these lines to standard output:
-- Chinese proverb Learning is a accompanies its owner everywhere. treasure which
This assignment asks you to create your own version of the sort command in C and in SPARC assembly language, as specified below.
For simplicity, your sort1 program should assume that standard input contains no more than 2048 lines. If standard input contains more than 2048 lines, then sort1 should ignore all lines beyond the 2048th.
Your sort1 program should assume that no line of standard input contains more than 1023 characters. (The terminating newline character is included in that count.) It need not work properly when a line of standard input contains more than 1023 characters, but it should not corrupt memory. Hint: You will find the fgets and fputs functions useful.
The program's primary data structure should be an array of pointers. Each pointer should point to the zero'th character of a null-terminated array of characters (i.e., a string). Each string should contain the characters of one line of standard input. The program should dynamically allocate the memory occupied by each string. The amount of memory allocated for each string should be less than or equal to 1024 bytes, depending upon the length of the string.The program should be modular. Each function should be relatively small, and should have a single well-defined purpose.
The program should use these functions to sort the array of strings:
void swap(char *ppcArray[], int iOne, int iTwo)
/* Swap ppcArray[iOne] and ppcArray[iTwo]. */
{
char *pcTemp;
pcTemp = ppcArray[iOne];
ppcArray[iOne] = ppcArray[iTwo];
ppcArray[iTwo] = pcTemp;
}
int partition(char *ppcArray[], int iLeft, int iRight)
/* Divide ppcArray[iLeft...iRight] into two partitions so elements
in the first partition are <= elements in the second partition.
Return the index of the element that marks the partition
boundary. */
{
int iFirst = iLeft-1;
int iLast = iRight;
while (1)
{
while (strcmp(ppcArray[++iFirst ], ppcArray[iRight]) < 0)
;
while (strcmp(ppcArray[iRight], ppcArray[--iLast]) < 0)
if (iLast == iLeft)
break;
if (iFirst >= iLast)
break;
swap(ppcArray, iFirst, iLast);
}
swap(ppcArray, iFirst, iRight);
return iFirst;
}
void quicksort(char *ppcArray[], int iLeft, int iRight)
/* Sort ppcArray[iLeft...iRight] in ascending order. */
{
if (iRight > iLeft)
{
int iMid = partition(ppcArray, iLeft, iRight);
quicksort(ppcArray, iLeft, iMid - 1);
quicksort(ppcArray, iMid + 1, iRight);
}
}
Those functions implement the quicksort algorithm as presented in Princeton's
COS 126 course.Create a file named sort2.c that is the same as sort1.c except that the definitions of the quicksort, partition, and swap functions have been removed. Then create a file named sort2.S containing SPARC assembly language versions of quicksort, partition, and swap. When linked together, sort2.c and sort2.S thus create sort2 -- a (presumably) faster version of your sort1 program. The functionality of sort2 should be the same as that of sort1.
You should implement swap as a leaf subroutine, as defined in your Paul textbook in Section 7.9. Note that, from the calling subroutine's point of view, a properly designed leaf subroutine is indistinguishable from a non-leaf subroutine. You should design your swap subroutine so its caller (partition) does not know that swap is a leaf subroutine.
Suggestion: Create sort2.S by translating functions from C to assembly language one at a time. Here is how you might proceed:
Repeat steps 2 through 4 for each of the three functions.
In accord with the purpose of the assignment, you should not use a C compiler to produce your assembly language functions. Rather you should produce them manually.
We suggest that you not use the m4 preprocessor. We suggest that you use the C preprocessor to define symbolic constants.
You need not optimize your assembly language functions, but we encourage you to do so. In particular, we encourage you to use registers instead of memory whenever possible. We will give you extra credit -- up to 5% -- if you minimize the use of "nop" instructions and optimize "if," "while," and "for" constructs.
You should submit:
Your readme file should contain:
Submit your work electronically via the command:
/u/cs217/bin/submit 6 sort1.c sort2.c sort2.S makefile readme