\documentclass[12pt]{article}
\usepackage{fullpage}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
% \newcommand{\doteq}{\stackrel{.}{=}}

\title{CSC 371 homework 4 \\
due 22 Nov, 1995}
\author{Dr. Bloch}

\newenvironment{code}{\setlength{\topsep}{0pt}\texttt\bgroup\begin{tabbing}%
reallylonglabel::\= longopcode\= extremelylongoperands\= reallyreallylongcomments\kill}%
{\end{tabbing}\egroup}

\begin{document}
\maketitle
\begin{description}
\item[8.4]
\textbf{Answer:} In SAL,
\begin{code}
\>	.data	\\
i: \>	.word	\\
a: \>	.word	\\
b: \>	.word	\\
c: \>	.word	\\
\>	.text	\\
\>	move	\>	i,1	\\
forloop: \> add	\>	a,a,b	\\
\>	bge	\>	a,5,endloop	\\
\>	move	\>	c,a	\\
endloop: \> add	\>	i,i,1	\\
\>	ble	\>	i,20,forloop
\end{code}

In MAL,
\begin{code}
\# \>	Register \>	Use	\\
\# \>	\$t0	\>	loop counter i	\\
\# \>	\$t1	\>	a	\\
\# \>	\$t2	\>	b	\\
\# \>	\$t3	\>	c	\\
\>	.text	\\
\>	move	\>	\$t0,1	\\
forloop: \> add	\>	\$t1,\$t1,\$t2	\\
\>	bge	\>	\$t1,5,endloop	\\
\>	move	\>	\$t3,\$t1	\\
endloop: \> add	\>	\$t0,\$t0,1	\\
\>	ble	\>	\$t0,20,forloop
\end{code}

\pagebreak

\item[8.5]
\textbf{Answer:}
\begin{code}
\>		.data	\\
array:	\>	.word	\>	0:35	\\
	\>	.text	\\
\#	\>	Register	\>	Use	\\
\#	\>	\$t0		\>	array element address	\\
\#	\>	\$t1		\>	value to store; also serves	\\
\#	\>			\>	as loop counter	\\
\#	\>	\$t2		\>	array element offset	\\
	\>	move		\>	\$t1,68	\\
	\>	\# value to store in last array element	\\
	\>	add		\>	\$t2,\$t1,\$t1	\\
	\>	\# twice that value is the offset	\\
	\>	la		\>	\$t0,array	\\
	\>	add		\>	\$t0,\$t0,\$t2	\\
loop:	\>	sw		\>	\$t1,0(\$t0)	\\
	\>	add		\>	\$t0,\$t0,-4	\\
	\>	add		\>	\$t1,\$t1,-2	\\
	\>	bgez		\>	\$t1,loop
\end{code}

\item[8.8]
\textbf{Answer:} 
\begin{code}
\>	.data	\\
string:	\>	.byte	\>	0:80	\\
prompt:	\>	.asciiz	\>	"What phrase do you want to test for palindromehood?$\backslash$n"	\\
yes$\_$msg:	\>	.asciiz	\>	"Yes, it's a palindrome.$\backslash$n"	\\
no$\_$msg:	\>	.asciiz	\>	"No, it's not a palindrome.$\backslash$n"	\\
	\\
	\\
\>	.text	\\
\#	\>	Register	\>	Use	\\
\#	\>	\$t0	\>	ptr to left end of string	\\
\#	\>	\$t1	\>	ptr to right end of string	\\
\#	\>	\$t2	\>	char from left end of string	\\
\#	\>	\$t3	\>	char from right end of string	\\
\#	\>	\$t4	\>	char ptr for I/O loops	\\
\#	\>	\$t5	\>	current char for I/O loops	\\
$\_$$\_$start:	\\
\# At this point in the textbook we hadn't yet discussed procedures in	\\
\# MAL, so I'll do the string I/O with in-line loops.	\\
	\\
\# Print the prompt, stopping at a null character.	\\
\>	la	\>	\$t4,prompt	\\
promptloop:	\>	lbu	\>	\$t5,0(\$t4)	\\
\>	beqz	\>	\$t5,getstring	\\
\>	putc	\>	\$t5	\\
\>	add	\>	\$t4,\$t4,1	\\
\>	b	\>	promptloop	\\
	\\
\# Input the string, stopping at a newline.	\\
getstring:	\>	la	\>	\$t4,string	\\
getloop:	\>	getc	\>	\$t5	\\
\>	beq	\>	\$t5,'$\backslash$n',gotstring	\\
\>	sb	\>	\$t5,0(\$t4)	\\
\>	add	\>	\$t4,\$t4,1	\\
\>	b	\>	getloop	\\
gotstring:	\>	sb	\>	\$0,0(\$t4)	\# not strictly necessary	\\
\>		\\
\# Set up left and right end pointers.	\\
\>	la	\>	\$t0,string	\\
\>	sub	\>	\$t2,\$t4,1	\\
	\\
\# The main loop:	\>	compare the characters at left and right ends.	\\
testloop:	\>	ble	\>	\$t2,\$t0,is$\_$palindrome	\\
\>	lbu	\>	\$t1,0(\$t0)	\\
\>	lbu	\>	\$t3,0(\$t2)	\\
\>	bne	\>	\$t1,\$t3,isnt$\_$palindrome	\\
\>	add	\>	\$t0,\$t0,1	\\
\>	sub	\>	\$t2,\$t2,1	\\
\>	b	\>	testloop	\\
	\\
is$\_$palindrome:	\>	la	\>	\$t4,yes$\_$msg	\\
\>	b	\>	msgloop	\\
	\\
isnt$\_$palindrome:	\>	la	\>	\$t4,no$\_$msg	\\
	\\
\# Print the appropriate message.	\\
msgloop:	\>	lbu	\>	\$t5,0(\$t4)	\\
\>	beqz	\>	\$t5,end	\\
\>	putc	\>	\$t5	\\
\>	add	\>	\$t4,\$t4,1	\\
\>	b	\>	msgloop	\\
	\\
end:	\>	done
\end{code}

\pagebreak

\item[9.1]
\textbf{Answer:} 
Procedures in a high-level language serve at least purposes: abstraction
and avoidance of duplication.  By \emph{abstraction} I mean separating
the grungy details of \emph{how} to perform a particular task from the
higher-level fact that it needs to be done.  The top level of a
well-abstracted program is a short sequence of statements, each
describing some major task that needs to be done, so that the reader can
easily see what tasks are being done in what order without worrying
about how each is accomplished.  By \emph{avoidance of duplication} I
mean that if the same code is to be performed at several different
places in the program, it need only be written (and, more importantly,
debugged!) once.  This not only saves computer memory and disk space,
but more importantly avoids the scenario in which you find a bug in
a piece of code that appears in several different places, and you 
absent-mindedly fix it in some but not all of those places.

Procedures in assembly language serve essentially the same purposes.
The abstraction purpose is perhaps less valuable, since assembly
language provides less support for things like parameter-passing, but on
the other hand assembly language is typically so hard to read that any
abstraction we can do will help.  The avoidance-of-duplication purpose
is probably the historically first reason for procedures in assembly,
since early computers had so little memory.

\item[9.6]
\textbf{Answer:} Two things can go wrong with this method.  First, if
the total number of variables used by procedures in the program is
greater than the number of available registers, variables obviously
cannot all be permanently assigned to distinct registers.  Second and
more subtly, this approach doesn't work with recursive procedures: in
most languages (including C, Scheme, and Pascal), each invocation of a
recursive procedure must have \emph{its own copies} of the variables
declared in that procedure.

\item[10.2]
Hand assemble the following MAL code.  Start instructions at address
\texttt{0x0008 8800}.
\begin{code}
\>	and \>	\$5,\$6,\$18 \\
\>	beq \>	\$5,\$0,br1 \\
\>	lui \>	\$20,0x66aa \\
br1: \>	lb \>	\$9,-8(\$20)
\end{code}

\textbf{Answer:}
\begin{description}
\item[$0x0008 8800$:]
The \texttt{and} instruction is R-format: the first 6 bits are 0,
the next 5 are the index of the first source register (\$6),
the next 5 are the index of the second source register (\$18),
the next 5 are the index of the destination register (\$5),
and the last 11 are $00000100100$.  All in all, the instruction 
to be stored at location $0x0008 8800$ is
$000000$ $00110$ $10010$ $00101$ $00000$ $100100$
(broken down into fields), or
$0000$ $0000$ $1101$ $0010$ $0010$ $1000$ $0010$ $0100$
(broken down into 4-bit
groups).
\item[$0x0008 8804$:]
The \texttt{beq} instruction is I-format: the first 6 bits are $000100$,
the next 5 are the index of the first source register (\$5),
the next 5 are the index of the second source register (\$0),
and the remaining 16 are the offset in words from the instruction after
the \texttt{beq} to the destination instruction.  The instruction after
this one is at address $0x0008 8808$.  We haven't yet assembled
the instruction at label \texttt{br1}, but we can see that it's two
instructions after this one.  Since all MIPS instructions are exactly 4
bytes long, this means it'll be at address $0x0008 880C$.  So the offset
is $0x0008880C - 0x00088808 = 4 \mbox{bytes} = 1 \mbox{word}$.
Thus the instruction to be stored at
location $0x0008 8804$ is 
$000100$ $00101$ $00000$ $0000000000000001$
(in fields), or
$0001$ $0000$ $1010$ $0000$ $0000$ $0000$ $0000$ $0001$
(in 4-bit groups).
\item[$0x0008 8808$:]
The \texttt{lui} instruction is I-format: the first 6 bits are $001111$,
the next 5 are always $00000$,
the next 5 are the index of the destination register (\$20),
and the remaining 16 are the value to be stored.  Thus at address
$0x0008 8808$ we store the binary instruction
$001111$ $00000$ $10100$ $0110011010101010$
(in fields), or
$0011$ $1100$ $0001$ $0100$ $0110$ $0110$ $1010$ $1010$
(in 4-bit groups).
\item[$0x0008 880C$:]
The \texttt{lb} instruction is I-format: the first 6 bits are $100000$,
the next 5 are the index of the base register (\$20),
the next 5 are the index of the source register (\$9),
and the remaining 16 are the offset in bytes, expressed as a 16-bit
two's-complement integer.  Writing 8 in 16-bit binary gives
$0000000000001000$, so $-8$ in two's-complement form is
$1111111111111000$.
Thus at address $0x0008 880C$ we store the
instruction
$100000$ $10100$ $01001$ $1111111111111000$
(in fields), or
(in 4-bit groups)
$1000$ $0010$ $1000$ $1001$ $1111$ $1111$ $1111$ $1000$
.
\end{description} 
Thus the complete binary code is

\begin{tabular}{cc}
Address & Contents \\
\hline
0x0008 8800 & 0x00D2 2824 \\
0x0008 8804 & 0x10A0 0001 \\
0x0008 8808 & 0x3C14 66AA \\
0x0008 880C & 0x8289 FFF8
\end{tabular}

\item[10.5]
Disassemble the following MIPS RISC code.  Make up label names when
needed.  The code starts at address $0x00400000$.

\begin{tabular}{cc}
Address & Contents \\
\hline
0x0040 0000 & 0x8161 0000 \\
0x0040 0004 & 0x0068 A020 \\
0x0040 0008 & 0x0083 A004 \\
0x0040 000C & 0x0681 FFFD
\end{tabular}

\textbf{Answer:}
\begin{description}
\item[$0x0040 0000$:] The hex number $0x8161 0000$ is
$10000001011000010000000000000000$ in binary.  The first 6 bits,
$100000$, indicate an \texttt{lb} instruction, which is I-format, so we
reformat the bits in fields as
$100000$ $01011$ $00001$ $0000000000000000$.
This makes it easy to see that the base register is \$11, the
destination register is \$1, and the offset is 0, so the instruction is
\texttt{lb \$1, 0(\$11)}.

\item[$0x0040 0004$:] The hex number $0x0068 A020$ is
$00000000011010001010000000100000$ in binary.  The first 6 bits,
$000000$, indicate an R-format instruction, so we reformat the bits in
fields as
$000000$ $00011$ $01000$ $10100$ $00000$ $100000$.
The last 6 bits, $100000$, indicate an \texttt{add} instruction.
The registers are $R_s = \$3$, $R_t = \$8$, and $R_d = \$20$, so
the instruction in assembly-language form would be
\texttt{add \$20,\$3,\$8}.

\item[$0x0040 0008$:] The hex number $0x0083 A004$ is
$00000000100000111010000000000100$ in binary.  The first 6 bits again
indicate an R-format instruction, which breaks down into fields as
$000000$ $00100$ $00011$ $10100$ $00000$ $000100$.
The last 6 bits indicate an \texttt{sllv} instruction, and the registers
are $R_s=\$4$, $R_t=\$3$, and $R_d=\$20$, so the instruction would be
written in assembly language as
\texttt{sllv \$20,\$3,\$4}.

\item[$0x0040 000C$:] The hex number $0x0681 FFFD$ is
$00000110100000011111111111111101$ in binary.  The first 6 bits,
$000001$, indicate a \texttt{bltz} or \texttt{bgez} instruction,
which is I-format, with fields
$000001$ $10100$ $00001$ $1111111111111101$.
Note that since the 3rd field is 1 rather than 0, it's a \texttt{bgez}
instruction.
The offset is the
two's-complement representation of $-3$, and $R_s = \$20$, so the
instruction is \texttt{bgez \$20,back}, where the label \texttt{back}
should be attached to the instruction 3 words before location $0x0040
0010$, \emph{i.e.} the instruction at location $0x0040 0004$.
\end{description}
So the disassembled code is
\begin{code}
\>	lb \>	\$1,0(\$11) \\
back: \> add \>	\$20,\$3,\$8 \\
\>	sllv \>	\$20,\$3,\$4 \\
\>	bgez \>	\$20,back
\end{code}

\item[10.6]
\textbf{Answer:} 
If we really need to branch to somewhere more than $\pm 2^{15}$ words
away, we need to use a \texttt{j} instruction instead
of a \texttt{b}, \texttt{beq}, etc.\@ instruction.  If the branch in
question is unconditional (\emph{i.e.} the \texttt{b} instruction),
this is no problem: the assembler can simply replace the \texttt{b}
instruction with a \texttt{j} instruction containing the absolute
address of the destination.  

If, on the other hand, the branch is
conditional, we have a slight problem.  The statement
\texttt{beq \$3,\$4,there} has the same effect as the code
\begin{code}
\>	bne \>	\$3,\$4,dontjump \\
\>	j \>	there \\
dontjump:
\end{code}
except that the latter allows a wider range of values for
\texttt{there}, so we'd like to replace the first statement with the
above code sequence.  Unfortunately, the above code sequence takes 2
words to represent, not 1, and this produces a ``glitch'' in the
assembler's address calculations.

In assembling the code for problem 10.3, we took advantage of the fact
that every TAL instruction takes exactly one word, or 4 bytes, to
represent; this allowed us to calculate the address of a branch
destination before assembling all the instructions.  If, however,
a \texttt{beq} instruction may in practice be replaced by the two-word
instruction sequence above, any addresses appearing after the glitch will
be shifted 4 bytes from where we originally thought they were, which means
any branch instructions from before the glitch that branch to labels
after the glitch must be corrected by adding 1 (word) to their offsets.
This is an assembly technique known as \emph{backpatching}.

An alternate approach is \emph{two-pass assembly}, in which the
assembler reads the program twice from start to finish: the first time
to calculate addresses of everything, and the second time to actually
generate the binary code.

Yet another approach to the problem is to have a \emph{jump table}
somewhere nearby, containing jump instructions to each of the distant
destinations this program needs to jump to.  Thus the branch
(conditional or unconditional) can simply point to the jump table rather
than directly to the destination itself.

\item[10.16]
\textbf{Answer:}
An incorrect branch decision will be made if the numbers, interpreted as
two's-complement integers, are in a different order from their
interpretations as unsigned integers.  For numbers with leftmost bit 0, both
representations have the same ordering, and for numbers with leftmost bit
1, both representations have the same ordering, but if one number has
leftmost bit 0 and the other has leftmost bit 1, there could be trouble.
For example, consider $\$11 = 10000000000000000000000000000000$ and
$\$12 = 00000000000000000000000000000001$.  As two's-complement
integers, they represent $-2^{31}$ and $1$ respectively, so the
instruction \texttt{blt \$11,\$12,repeat\_loop} will branch.  But their
unsigned difference is $01111111111111111111111111111111$, which
represents the two's-complement integer $2^{31}-1$, which is positive,
so the code segment
\begin{code}
\> subu \> \$1,\$11,\$12 \\
\> bltz \> \$1,repeat\_loop
\end{code}
doesn't branch to \texttt{repeat\_loop}.

Similarly, if $\$11 = 00000000000000000000000000000001$, representing
the two's complement integer $1$, and
$\$12 = 10000000000000000000000000000010$, representing the
two's complement integer $-(2^{15}-2)$, the
\texttt{blt} will not branch because $1 \geq -(2^{15}-2)$.
But their unsigned difference is
$10000000000000000000000000000001$, which the \texttt{bltz} will treat
as a negative number, and it \emph{will} branch.
\end{description}
\end{document}
