\documentclass[12pt]{article}
% \pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
%\setlength{\textheight}{8.75in}
%\setlength{\columnsep}{2.0pc}
%\setlength{\textwidth}{6.8in}
%\setlength{\footheight}{0.0in}
%\setlength{\topmargin}{0.0in}
%\setlength{\headheight}{0.0in}
%\setlength{\headsep}{0.0in}
%\setlength{\oddsidemargin}{-.19in}
%\setlength{\evensidemargin}{-.19in}
%\setlength{\parindent}{1pc}

\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}

%\newenvironment{code}{\def\@listi{\parsep-20pt\topsep-20pt\partopsep-20pt}%
%\texttt\bgroup\begin{tabbing}%
%longlabel:\= opcode\= longoperands\= reallylongcomments\kill}%
%{\end{tabbing}\egroup}

%\newenvironment{code}{\par\texttt\bgroup\begin{minipage}{8in}%
%\begin{tabbing}%
%longlabel: \= opcode \= longoperands \= reallylongcomments \kill}%
%{\end{tabbing}\end{minipage}\egroup\par}

\newenvironment{code}{\setlength{\topsep}{0pt}\texttt\bgroup\begin{tabbing}%
label::\= opcode\= longeroperands\= reallyreallylongcomments\kill}%
{\end{tabbing}\egroup}

\begin{document}

\title{Computer Science 371 \\
Homework 2 solutions}

\author{Dr. Stephen Bloch}

\maketitle

Assignment: problems 3.1--3.8, 3.11--3.17.

\begin{description}

\pagebreak[2]
\item[3.1]
\begin{code}
\> addi \> \$5,\$5,-1
\end{code}

\pagebreak[2]
\item[3.2]
\begin{code}
\> move \> \$5,\$0
\end{code}
which is actually a pseudo-operation standing for something like
\begin{code}
\> add \> \$5,\$0,\$0
\end{code}

\pagebreak[2]
\item[3.3]
\begin{code}
\> sw \> \$0,1000
\end{code}
which actually stands for something like
\begin{code}
\> sw \> \$0,1000(\$0)
\end{code}
Note that $1000 < 32767$, and so the number 1000 fits inside the signed
16-bit offset field of an I-format instruction.

\pagebreak[2]
\item[3.4]
\begin{code}
\> addi \> \$5,\$5,1 \\
\> blt \> \$5,\$6,L1
\end{code}
which actually stands for something like
\begin{code}
\> addi \> \$5,\$5,1 \\
\> slt \> \$1,\$5,\$6 \\
\> bne \> \$0,\$1,L1
\end{code}

\pagebreak[2]
\item[3.5]
\begin{code}
\> addi \> \$5,\$5,-1 \\
\> bgt \> \$5,\$0,L1
\end{code}
which actually stands for something like
\begin{code}
\> addi \> \$5,\$5,-1 \\
\> slt \> \$1,\$5,\$6 \\
\> bne \> \$0,\$1,L1
\end{code}
Note that if we assume (as would normally be true in practice) that
\texttt{\$5}
is positive to begin with, \texttt{sobgtr} is equivalent to \texttt{sobnz},
\emph{i.e.}, ``subtract one and branch if not equal to zero.''  This could be
converted into MIPS as two instructions:
\begin{code}
\> addi \> \$5,\$5,-1 \\
\> bne \> \$5,\$0,L1
\end{code}

\pagebreak[2]
\item[3.6]
\begin{code}
\> addi \> \$11,\$12,100
\end{code}

\pagebreak[2]
\item[3.7]
\begin{code}
\> la \> \$11,4000000 \\
\> lw \> \$12,44(\$11) \> \# note $44 = 4 \cdot 11$ \\
\> add \> \$12,\$12,\$13 \\
\> sw \> \$12,40(\$11) \> \# note $40 = 4 \cdot 10$
\end{code}
which actually stands for something like
\begin{code}
\> lui \> \$11,61 \> \# $4000000 / 65536$ \\
\> ori \> \$11,\$11,2304 \> \# $4000000 \bmod 65536$ \\
\> lw \> \$12,44(\$11) \\
\> add \> \$12,\$12,\$13 \\
\> sw \> \$12,40(\$11)
\end{code}

\pagebreak[2]
\item[3.8]
\begin{code}
loop: \> lw \> \$3,0(\$4) \> \# Read next word from source \\
\> addi \> \$2,\$2,1 \> \# Increment count words copied \\
\> sw \> \$3,0(\$5) \> \# Write to destination \\
\> addi \> \$4,\$4,4 \> \# Advance pointer to next source \\
\> addi \> \$5,\$5,4 \> \# Advance pointer to next dest \\
\> bne \> \$3,\$0,loop \> \# Loop if word copied $\neq$ zero
\end{code}

\pagebreak[2]
\item[3.11]
You can do this in several ways.  I like the following:
\begin{code}
\> j \> test \\
Loop: \> add \> \$19,\$19,\$20 \\
test: \> mult \> \$9,\$19,\$10 \\
\> lw \> \$8,Sstart(\$9) \\
\> beq \> \$8,\$21,Loop
\end{code}
Notice that this code segment does an extra jump at the beginning, but
in return it saves a jump every time through the loop.  If the loop is
iterated ten times, for example, the old code executes 5 instructions
each of the first nine times, and 3 instructions the last time, for a
total of 48 instructions; the new code, by contrast, executes 1
instruction at the beginning, 4 instructions each of the first nine
times, and 3 instructions the last time, for a total of 40 instructions.

\pagebreak[2]
\item[3.12]
\begin{code}
\> beq \> \$19,\$20,L1
\end{code}

\pagebreak[2]
\item[3.13]
\begin{code}
\> bne \> \$19,\$20,L1
\end{code}

\pagebreak[2]
\item[3.14]
For the following couple of problems, note that the MIPS machine really
has only two branch instructions, \texttt{beq} and \texttt{bne}, and only one
condition-setting instruction \texttt{slt} that we've heard about; the
others are all pseudo-instructions.

We'd like to say
\begin{code}
\> blt \> \$19,\$20,L1
\end{code}
but the MIPS has no \texttt{blt} instruction.  So instead we do
\begin{code}
\> slt \> \$1,\$19,\$20 \> \# is $\$19 < \$20$? \\
\> bne \> \$1,\$0,L1 \> \# if so, branch
\end{code}

\pagebreak[2]
\item[3.15]
We'd like to say
\begin{code}
\> ble \> \$19,\$20,L1
\end{code}
but the MIPS has no \texttt{ble} instruction.  So instead we do
\begin{code}
\> slt \> \$1,\$20,\$19 \> \# is $\$20 < \$19$? \\
\> beq \> \$1,\$0,L1 \> \# if not, then $\$19 \leq \$20$ so branch
\end{code}

\pagebreak[2]
\item[3.16]
We'd like to say
\begin{code}
\> bgt \> \$19,\$20,L1
\end{code}
but the MIPS has no \texttt{bgt} instruction.  So instead we do
\begin{code}
\> slt \> \$1,\$20,\$19 \> \# is $\$20 < \$19$? \\
\> bne \> \$1,\$0,L1 \> \# if so, then $\$19 > \$20$ so branch
\end{code}

\pagebreak[2]
\item[3.17]
We'd like to say
\begin{code}
\> bge \> \$19,\$20,L1
\end{code}
but the MIPS has no \texttt{bge} instruction.  So instead we do
\begin{code}
\> slt \> \$1,\$19,\$20 \> \# is $\$19 < \$20$? \\
\> beq \> \$1,\$0,L1 \> \# if not, then $\$19 \geq \$20$ so branch
\end{code}
% \item[3.18]
% The format of a branch instruction requires a 16-bit offset (indicating
% where to branch to).  If there were also an opcode (6 bits), a register
% to compare with (5 bits), and another immediate number (16 bits), the
% whole instruction would be 43 bits long, and wouldn't fit into a 32-bit
% word.
% 
% If the designers of the MIPS architecture had considered branch
% instructions comparing a register with an immediate \emph{really}
% important, they could have invented a family of "compare immediate and
% branch" instructions, but after allowing for the opcode, register to
% compare with, and offset, only 5 bits would remain to specify the
% immediate number.  This would allow only immediate numbers between 0 and
% 31, or (more likely) between -16 and 15.  (We'll discuss in chapter 4
% why -16--15 is a reasonable range.)
% 
% \begin{code}
%  \> addi \> \$1,\$0,14 \\
%  \> beq \> \$2,\$1,L1
% \end{code}
% which actually stands for the two instructions
% \begin{code}
%  \> sge \> \$1,\$19,\$20 \\
%  \> bne \> \$1,\$0,L1
% \end{code}
% 
% \item[3.19]
% \begin{code}
%  \> la \> \$8,1500 \> \# address of a \\
%  \> la \> \$9,2000 \> \# address of b \\
% 
%  \> move \> \$15,\$0 \> \# initialize i \\
%  \> j \> test \\
% loop: \> muli \> \$11,\$15,4 \> \# compute \\
% 
% test: \> li \> \$10,100 \> \# is i <= 100? \\
%  \> ble \> \$15,\$10,loop \> \# if so, go through loop \\
%  \>  \>  \> \# if not, go on from here
\end{description}

\end{document}
