%% -*- Mode: LATEX -*-

\documentclass[11pt]{rhitcsse}

\input{cs232_defs}
\title{Lab 4 - \textsc{MIPS} Procedures II}

\begin{document}

\maketitle

\section{Objectives}

Following completion of this lab you should be able to:
\latex{\vspace*{-\topsep}\vspace*{-\partopsep}}
\begin{itemize}{}
  \latex{\setlength{\itemsep}{0in}}
  \item Call and pass arguments to procedures in \textsc{MIPS}
  programs.
  \item Return from procedures.
  \item Save and restore registers.
  \item Correctly manage the stack.
  \item Discuss register allocation strategies.
\end{itemize}


\section{General}

Be sure to follow the \textsc{MIPS} procedure calling conventions as
described in your book (Section 3.6 and Appendix A.6).

\textbf{The required output format is mandatory}.


\section{Sort Static Array}

\htmladdnormallink{\texttt{sort.asm}}{../labs/sort.asm} contains the
main function of a program to sort an array.  It also contains a
couple of helper procedures -- \textit{shift} and \textit{print}.  It
calls the procedure \textit{sort} that you will write which in turn
should calls the procedure \textit{shift}.  Make sure that you
understand the procedure calling convention implemented in this code.

Modify \texttt{sort.asm} by adding a procedure called \textit{sort}
which implements insertion sort.  \textbf{Do not} modify the code for
\textit{main}, \textit{shift} or \textit{print}.  \textit{sort} should
implement the algorithm shown in the following C code:
\begin{verbatim}
        void
        sort(int n, int V[]) {
          int i, j, key;

          for (j=1; j<n; j++) {
            key = V[j];
            i = j-1;
            while ((i >= 0) && (V[i] > key)) {
              shift(i, V);
              i--;
            }
            V[i+1] = key;
          }
        }.
\end{verbatim}
\texttt{V} is a global array, but is passed as an argument to
\textit{sort}.  Make sure you understand the algorithm.  As part of
the comment block for you procedure be sure to document the register
allocation.  Test you program using several different arrays.


\section{Sort a Dynamic Array}

Copy the code in file \texttt{sort.asm} to
\texttt{dsort.asm}.  Modify \texttt{dsort.asm} to:
\latex{\vspace*{-\topsep}\vspace*{-\partopsep}}
\begin{enumerate}
  \latex{\setlength{\itemsep}{0in}}
  \item Prompt the user for the size $k$ of the input array
  with the string ``How many numbers?''.  You may choose to restrict
  the range of $k$, however do it correctly and document it.
  \item Dynamically allocate an array of size $k$ in memory
  using the \texttt{SPIM} system call \textit{sbrk}\footnote{See page
    A-49 of your text for more information.}.  This system call
  expects an integer $i$ in register \$a0 and returns a pointer
  to a block of $i$ \textbf{bytes} of memory in register \$v0.
  \item Prompt the user for $k$ integers and store them in the
  dynamically allocated array.
  \item Print the input array.
  \item Sort the array and print it.
\end{enumerate}
Be sure to thoroughly test your program.  Executing the program should
look like this:
\begin{verbatim}
How many numbers? 5
Input: 1
Input: 2
Input: 3
Input: 4
Input: 5
The input array: 1 2 3 4 5
The sorted array: 1 2 3 4 5
\end{verbatim}


\section{Peer review}

Prior to submitting your lab, get another group to look at your
\textit{sort} procedure.  Each group should review \textbf{exactly}
one other groups procedure.  The reviewing group should submit a brief
written statement about whether or not the procedure follows the
\texttt{MIPS} procedure calling conventions.  Also include some
general comments about the strengths and weakness of the procedure as
coded.


\section{Turning It In}

When the lab is complete (not later than 12 December 2001), upload all
of your files (\texttt{sort.asm} and \texttt{dsort.asm} to:
\begin{center}
  \texttt{/Class/cs/cs232/turnin/<}\textit{section}\texttt{>/<}%
  \textit{username}\texttt{>/lab4/}.
\end{center}

\end{document}

% Local Variables:
% mode:latex
% End:
