Create a file named program3.s and in that file, write a stylish, well commented MIPS assembly language program that is a direct translation of the C program given below. The program prompts the user for a positive integer, n. Then, the program dynamically allocates (on the heap) an array of n integers. Next, the user is prompted n times to enter an integer — each of which is stored in a successive slot in the array. Once the array has been populated, it is sorted (using a merge sort). Finally, the largest, median, and smallest integers are printed.
Because this program uses procedures, you must (correctly) follow the Official CDA 3101 Stack frame Convention and obey the register usage conventions described in class/lecture. Programs that violate the conventions are worth zero points — it's that important, folks. Why? See hint #2 below.
Good comments are required. In particular:
# program1.s # # by Your Name # gatorlinkid@ufl.edu # # for CDA 3101 # Summer, 2008
addi $t4, -4 # $t4 -= 4 BAD!addi $t4, -4 # count -= 4 GOOD!You are strongly encouraged to look at "Appendix A" which is on the CD that comes with the book. It's in a .pdf file named HP_AppA.pdf in the directory \Content\COD3e\CDSections (Note: you can ignore sections A.7 and A.8; Pages A43-45 will be of particular interest!)
A recursive procedure is implemented just like any other procedure that calls another procedure — the only difference? It jal's to itself. Easy as pie — IFF you obey the conventions: if you don't then implementing this program would be a living hell. And you don't want that, now do you?
Write the simplest functions first and throughly test them before moving on. If you decide not to take this advice, you're just asking for a headache when it comes time to debug the program.
Remember: pointer arithmetic isn't like regular arithmetic when the data are larger than byte size! This code makes extensive use of pointers, so you better be sure you understand them before you begin translating, else you'll waste a lot of time and energy.
The idea of merge sort is classic recursive divide and conquer. Given an unsorted list:
[3 9 1 8 1 7 5 4 6]
/ \
[3 9 1 8] [1 7 5 4 6]
/ \ / \
[3 9] [1 8] [1 7] [5 4 6]
/ \ / \ / \ / \
[3] [9] [1] [8] [1] [7] [5] [4 6]
/ \
[4] [6]
[4] [6]
\ /
[3] [9] [1] [8] [1] [7] [5] [4 6]
\ / \ / \ / \ /
[3 9] [1 8] [1 7] [4 5 6]
\ / \ /
[1 3 8 9] [1 4 5 6 7]
\ /
[1 1 3 4 5 6 7 8 9]
When translating the following code to MIPS assembly code, do not use instructions we did not cover in lecture/discussion: in particular, do not use the division or multiplication instructions.
By the way: this is valid C code and should compile with most modern C compilers [I tested it with gcc]. The code uses // style comments (which first appeared in C++) and are officially supported by the C99 standard. However, they are not ANSI C compatible — but many ANSI C compilers don't complain (unless the a strict ANSI compliance compiler option is enabled).
/* mergesort.c
** an implementation and test code for good old merge sort.
**
** Note: this implementation was written specifically as a template
** to be translated into assembly code for a class programming
** assignment. It was written so as to in so far as possible
** facilitate the translation process. To make the program more
** "understandable" it allocates separate arrays for each sublist
** (it is more efficient to allocate a single large array than lots
** of small ones — it's also possible to write an in-place merge
** sort which doesn't need any additional storage).
**
** by Dave Small - (C) Copyright 2008 — all rights reserved.
** permission granted for non-commercial use with one exception: if
** you have been assigned the task of implementing merge sort for a
** class, you may NOT cheat by using this one in whole or in part (do
** your own darn work — it's for your own good!)
**
** for CDA 3101
**
** 200602.12 - v1.0 created
*/
/*------------------------------------------------------------------------
** Begin code block: do NOT try to translate into MIPS!
** these lines are only necessary for the C program to compile.
*/
#include <stdio.h>
#include <stdlib.h>
int getInt( char* );
int* makeArrayOfInts( int );
int* sort( int*, int );
void copyInts( int*, int*, int );
int* merge( int*, int*, int, int*, int );
void displayResults( int* sortedList, int n );
/* End C only code block
**------------------------------------------------------------------------
*/
int main( void )
{
int n; // number of ints that will be sorted
n = getInt( "How many integer values are you going to give me? " );
if ( n > 0 )
{
int* array; // pointer to an array of ints
array = makeArrayOfInts( n );
array = sort( array, n );
displayResults( array, n );
free( array ); // C only: do NOT try to translate this line into MIPS
}
return 0; // hint: use the syscall exit
}
int getInt( char* prompt )
{
int i;
printf( prompt ); // hint: use a syscall
fflush( stdout ); // C only: do NOT try to translate this line into MIPS
scanf( " %d", &i ); // hint: use a syscall
return i;
}
int* makeArrayOfInts( int n )
{
int i = 0;
int value;
int* array;
// allocate memory for the array
// note 1: use the syscall sbrk to translate the following statement
// note 2: good C style would require checking to see that the
// returned pointers weren't equal to NULL; we will assume a memory
// allocation won't fail.
array = (int*) malloc( sizeof(int) * n );
while( i < n )
{
printf( "There are " );
printf( "%d", (n - i) );
printf( " integers left to enter...\n" );
*(array + i) = getInt( "What's the value of the next int? " );
++i;
}
return array;
}
int* sort( int* list, int listLength )
{
int leftListLength, rightListLength;
int* leftList; // left sublist
int* rightList; // right sublist
if ( listLength > 1 ) // lists of size 1 (or less) are already sorted!
{
int i;
// divide and conquer:
leftListLength = listLength / 2;
rightListLength = listLength - leftListLength;
// [1] -- allocate memory for sublists
// note 1: use the syscall sbrk to translate the following 2 statements
// note 2: good C style would require checking to see that the
// returned pointers weren't equal to NULL; we will assume a memory
// allocation won't fail.
leftList = (int*) malloc( sizeof(int) * leftListLength );
rightList = (int*) malloc( sizeof(int) * rightListLength );
// [2] -- copy each half of list to respective sublist
copyInts( list, leftList, leftListLength );
copyInts( list+leftListLength, rightList, rightListLength );
// [3] -- sort the sublists
leftList = sort( leftList, leftListLength );
rightList = sort( rightList, rightListLength );
// [4] -- merge the sorted lists
list = merge( list, leftList, leftListLength, rightList, rightListLength );
// [5] -- free the memory used by the sublists
free( leftList ); // C only: do NOT try to translate into MIPS
free( rightList ); // C only: do NOT try to translate into MIPS
}
return list;
}
void copyInts( int* src, int* dest, int n )
{
while ( n > 0 )
{
*dest = *src;
++dest;
++src;
--n;
}
return;
}
int* merge( int* list,
int* leftList, int leftListLength,
int* rightList, int rightListLength )
{
int* listHead = list;
// as long as neither sublist is empty, copy the smallest item
// from the sublists into list
while ( ( leftListLength > 0 ) && ( rightListLength > 0 ) )
{
if ( *leftList < *rightList )
{
*list = *leftList;
++leftList;
--leftListLength;
}
else
{
*list = *rightList;
++rightList;
--rightListLength;
}
++list;
}
// if the right sublist emptied out first,
// then copy rest of left sublist to list
while ( leftListLength > 0 )
{
*list = *leftList;
++leftList;
--leftListLength;
++list;
}
// if the left sublist emptied out first,
// then copy rest of right sublist to list
while ( rightListLength > 0 )
{
*list = *rightList;
++rightList;
--rightListLength;
++list;
}
return listHead;
}
void displayResults( int* sortedList, int n )
{
printf( "The minimum of the numbers you gave me was " );
printf( "%d", *sortedList );
printf( ".\n" );
printf( "The median of the numbers you gave me was " );
printf( "%d", *(sortedList + (n / 2)) );
printf( ".\n" );
printf( "The maximum of the numbers you gave me was " );
printf( "%d", *(sortedList + (n - 1)) );
printf( ".\n" );
}
There are two deliverables — the regular hardcopy of the program 3 source code and a CD containing the source code for all the programs you submitted for grading (if you did not submit a program, it of course need not appear on the CD) — which will be collected at the start of lecture on Friday. The CD (not the case) must be labeled Your Name CDA3101 2008S Programs. The hardcopy must conform to the instructions in the course policies' homework & other deliverables section. Follow the submission instructions, otherwise your work will not be graded.