%% -*- Mode: LATEX -*-

\documentclass[11pt]{rhitcsse}

\input{cs232_defs}
\title{Lab 2 --- \textsc{MIPS} Byte Addressing and Arrays}

\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 Write loops in \textsc{MIPS} programs.
  \item Understand the limitations of \texttt{beq/bne}, \texttt{j},
  and \texttt{jr}.
  \item Properly access memory in \textsc{MIPS} programs.
  \item Dynamically allocate memory in \textsc{SPIM}.
  \item Understand some of the issues surrounding register allocation.
  \item Use the \textsc{SPIM} system call for printing strings.
\end{itemize}

\section{General}

This and the remaining labs should be done in pairs -- only one
partner should submit the files, the other should put a
\textit{README} in the appropriate directory.

In evaluating your programs the approximate weightings will be:
correctness, 50\%; efficiency (minimum instructions and minimum
registers), 20\%; and, documentation, 30\%.

\textbf{The required output format is mandatory}.

In writing these and other assembly language programs:
\latex{\vspace*{-\topsep}\vspace*{-\partopsep}}
\begin{itemize}{}
  \latex{\setlength{\itemsep}{0in}}
  \item Solve the problem before coding the solution.  Usually this
  means writing the code in a high-level language or pseudo-code
  first, then converting it to assembly language.
  \item \textbf{IMPORTANT:}Write down (perhaps in a comment in your
  code) the purpose that you have in mind for each register that you
  use.  Here's an example of how you might document register use in
  your code.

\begin{verbatim}
# $s0 = i
# $s1 = j
# $s2 = n
# $s3 = key
# $s4 = ptr (address of array)
# $t4 = test
# $t0 = temp
\end{verbatim} %$
\end{itemize}

\section{Find the Minimum}

Copy the code in file
\htmladdnormallink{\texttt{main.asm}}{../labs/main.asm} to
\texttt{min.asm}.  Modify \texttt{min.asm} to print out the minimum
element of the array V (don't print anything but the minimum value,
followed by a newline).  Remember to include proper documentation in
this and all programs you write in these labs.  Try to use only
t-registers.  You may assume that there are exactly 10 elements in the
array.  Test \texttt{min.asm} by changing the contents of the array V.

In \textsc{SPIM} you can check the contents of the array by clicking
\emph{Simulator:Display symbol table}, looking in the ``Messages''
window for the starting address of V (mine's at \texttt{0x10010000}),
and then look in the ``Data Segment'' window at the address of V.  Can
you identify each element of the array?


\section{Rotate Right One}
\latex{\label{sec:rr1}}

Copy the code in file \texttt{min.asm} to \texttt{rotate1.asm}.
Modify \texttt{rotate1.asm} to treat V as a circular array and rotate
its contents one position to the right.  Rotate the array in place.
Specifically, $\textrm{V}(i)$ moves to $\textrm{V}(i+1\ \textrm{mod}\ 
10)$.  After performing the rotation, your program should print the
string ``The rotated array:'' followed by the elements of the rotated
array, each preceded by a single space character, e.g.

\begin{verbatim}
The rotated array: 18 20 56 -90 37 -2 30 10 -66 -4
\end{verbatim}

Here is an example of how you might print out the rotated array.
Note: \$t1 contains 40.
\begin{verbatim}
    .data

message:  .asciiz "The rotated array: "
sep:      .asciiz " "
newline:  .asciiz "\n"

    .text

#----------------------------------------------------------------------
#       Print the rotated array
#----------------------------------------------------------------------

        la      $a0, message    # store pointer to message
        li      $v0, 4          # use system call to ...
        syscall                 # ... print message
        li      $t0, 0          # initialize the index
loop2:  lw      $a0, V($t0)     # get next element
        li      $v0, 1          # use system call to ...
        syscall                 # ... print the element
        la      $a0, sep        # store pointer to sep
        li      $v0, 4          # use system call to ...
        syscall                 # ... print sep
        add     $t0, $t0, 4     # increment the index
        bne     $t0, $t1, loop2 # check if we've printed all the elements
        la      $a0, newline    # store pointer to a new line
        li      $v0, 4          # use system call to ...
        syscall                 # ... print new line
\end{verbatim}


%\section{Rotate Right $k$}

%Copy the code in file \texttt{rotate1.asm} to \texttt{rotatek.asm}.
%Modify \texttt{rotatek.asm} to prompt the user for an integer $k$ and
%rotate the array V to the right $k$ positions.  Prompt the user with
%the string ``Rotate: '', exactly like that.  Assume that the user
%always supplies an input $k$ that is an integer between 1 and 9,
%inclusive.  The rotated array should be printed out as \latex{in
%  Section \ref{sec:rr1}}\html{above}. Executing the program should
%look like this:
%\begin{verbatim}
%Rotate: 2
%The rotated array: -4 18 20 56 -90 37 -2 30 10 -66
%\end{verbatim}


\section{Find the Minimum of a Dynamic Array}
\latex{\label{sec:dyna}}

Copy the code in file \texttt{min.asm} to \texttt{dmin.asm}.  Modify
\texttt{dmin.asm} to:
\latex{\vspace*{-\topsep}\vspace*{-\partopsep}}
\begin{enumerate}
  \item Prompt the user for the size $k$ of the input array with the
  string ``How many numbers? '', exactly like that.  \textbf{Assume}
  that the user always supplies a positive integer that is not bigger
  than the system can handle.
\item Dynamically allocate an array of size $k$ in memory using 
  the \texttt{SPIM} system call \emph{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.

  Here's an example of how you might dynamically allocate memory.
\begin{verbatim}
    .data

prompt:   .asciiz "How many numbers? "

    .text

#----------------------------------------------------------------------
#       Read the number of elements
#----------------------------------------------------------------------

        la      $a0, prompt     # load address of prompt
        li      $v0, 4          # use system call to ...
        syscall                 # ... print prompt
        li      $v0, 5          # use system call for reading ...
        syscall                 # ... an integer i
        move    $t1, $v0        # Copy integer i into $t1
        sll     $t1, $t1, 2     # multiply i by 4 to get total number of bytes

#----------------------------------------------------------------------
#       Allocate space for the array
#----------------------------------------------------------------------

        move    $a0, $t1        # store number of bytes needed
        li      $v0, 9          # use system call for ...
        syscall                 # ... allocating memory
        move    $t4, $v0        # save the base address of array
        add     $t1, $t1, $t4   # save the end of array
\end{verbatim}
  Note: the first element of the array can be loaded using \texttt{lw
    \$t0, 0(\$t4)}, the second can be loaded using \texttt{lw \$t0,
    4(\$t4)}, etc.

\item Prompt the user for $k$ integers (in exactly the format shown in the example below) and store them in the
  dynamically allocated array.
\item Print the input array.
\item Find the minimum element and print it (in exactly the format shown in the example below).
\end{enumerate}
Be sure to test \texttt{dmin.asm} thoroughly.  Executing the program
should look like this:
\begin{verbatim}
How many numbers? 5
Input: 12
Input: 24
Input: 13
Input: 8
Input: 22
The input array: 12 24 13 8 22
Minimum element: 8
\end{verbatim}


%\section{Rotate a Dynamic Array Right One (\textbf{Optional})}

%Copy the code in file \texttt{rotate1.asm} to \texttt{drotate1.asm}.
%Modify \texttt{drotate1.asm} to create an array dynamically as
%\latex{in Step \ref{sec:dyna}}\html{above}, rotate it right one
%position, and print out the rotated array.  Executing the program
%should look like this:
%\begin{verbatim}
%How many numbers? 5
%Input: 12
%Input: 24
%Input: 13
%Input: 8
%Input: 22
%The input array: 12 24 13 8 22
%The rotated array: 22 12 24 13 8
%\end{verbatim}


%\section{Reflection}
%Create a text file called \texttt{reflection.txt}.
%Put a few sentences into it that address the following questions:
%   Hmmm... What to put here???

\vspace*{-0.25in}
\section{Turning It In}

When the lab is complete (not later than 05 December 2001), upload all
of your files (\texttt{min.asm}, \texttt{rotate1.asm}, and
\texttt{dmin.asm}
%\texttt{rotatek.asm}, , and optionally \texttt{drotate1.asm})
to:
\begin{center}
  \texttt{/Class/cs/cs232/turnin/<}\textit{section}%
  \texttt{>/<}\textit{username}\texttt{>/lab2/}.
\end{center}

\end{document}

% Local Variables:
% mode:latex
% End:
