addressinglab.tex

%%
%% AddressingLab (c) 2021-22 Christopher A. Bohn
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%     http://www.apache.org/licenses/LICENSE-2.0
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%%

\input{../../common/assignment.tex}
\input{../../common/semester.tex}

\renewcommand{\labnumber}{\addressinglabnumber}
\renewcommand{\labname}{x86 Addressing Modes Lab}
\renewcommand{\shortlabname}{addressinglab}
\renewcommand{\collaborationrules}{\addressinglabcollaboration}
\renewcommand{\duedate}{\addressinglabdue}
\pagelayout
\begin{document}
\labidentifier

%\usepackage{fullpage}
%\usepackage{enumitem}



In this assignment, you will practice creating the source and destination for
x86 assembly language instructions. There is no design effort required for this
lab assignment, and \textbf{you should be able to complete it during lab time}.

The instructions are written assuming you will edit and run the code on
\runtimeenvironment. If you wish, you may edit the code in a different
environment; however, you will not be able to assemble and link an executable
on MacOS nor on Windows.

\section*{Learning Objectives}

After successful completion of this assignment, students will be able to:
\begin{itemize}
\item Write x86 assembly instructions using an immediate value as the source
\item Write x86 assembly instructions using registers as the source and/or
    destination
\item Write x86 assembly instructions using memory as the source or destination
\item Use the common x86 memory addressing modes
\end{itemize}

\subsection*{Continuing Forward}

The original purpose of this lab was to improve students' familiarity with
x86 addressing modes to improve their performance on the exam. This improved
familiarity will also serve you well on two upcoming labs, one in which you have
to be able to interpret functions in assembly code, and one in which you will
have to write short snippets of assembly code as part of a buffer overflow
attack.

\section*{During Lab Time}

During your lab period, the TAs will provide a refresher on the format of x86
assembly instructions, including \texttt{mov} instructions and arithmetic instructions, of the nomenclature used to specify the operand sizes, and of the role of each component of the most-general
form of memory addressing: $D(R_b, R_i, S)$. During the remaining time, the TAs
will be available to answer questions.

During your lab period (and only during your lab period), you may discuss problem decomposition and solution design with your lab partner.
\textit{Be sure to add your name and your partner's name to the top of your source code files.}
To receive full credit for the work you and your partner do during lab time, you must be an active participate in the partnership.
In accordance with the School of Computing's Academic Integrity Policy, we reserve the right to adjust your calculated grade if you merely ``tag along'' and let your partner do all the thinking.

\textbf{You should be able to complete this lab assignment during lab time};
however, it is not due until \duedate.

\section*{Scenario}

You've settled into a comfortable routine at the Pleistocene Petting Zoo. While
your job isn't quite as exciting as that of the saber-toothed tigers' dentist,
it still has something new and interesting almost every day.

Archie announces that he heard that hand-crafted assembly code can be faster
than high-level language code. You try to explain that while this may have been
true decades ago, modern optimizing compilers generate code faster than what a
typical programmer can achieve with assembly code. Archie doesn't believe you
and instists that you write the zoo's new cipher program in x86 assembly code.

\hspace{1cm}

In this assignment, you won't have to write the entire functions in assembly \
language; most of that has already been done for you. Instead, there are ten
lines of assembly code that you will need to complete, demonstrating an
understanding of x86 operands and memory addressing modes. The assembly code
has a few optimizations, so some of it may not be immediately recognizable.


\section{Caesar Cipher Function}

The first of the three functions is the Caesar Cipher itself. Here is the
equivalent C code:

\lstinputlisting[firstline=21, lastline=37, numbers=left]{addressinglab.c}

\subsection{Subtract Using an Immediate Operand}\label{task1}

In this task, you will insert the assembly instruction that corresponds to
line~6 and part of line~7 in the function's C code. Specifically, we are
combining the \lstinline{-'A'} from line 6 with the \lstinline{key + 26} to
create a temporary variable equal to \lstinline{key + 26 - 'A'}. The
\lstinline{key} value is initially in register \lstinline{%edx}; since we will
not need this value again, the assembly instruction can safely overwrite
\lstinline{%edx}.

Find the line in \textit{addressinglab.s} that says \\
\texttt{\#\#\#\#\# PLACE INSTRUCTION FOR TASK \ref{task1} ON NEXT LINE \#\#\#\#\#} \\
On the next line, insert a \lstinline{subl} instruction that subtracts the
immediate value \lstinline{39} from the contents of register \lstinline{%edx}
and places the difference in register \lstinline{%edx}.

% subl $39, %edx

Do not delete the \texttt{\#\#\#\#\# PLACE INSTRUCTION...} comment, and do not
delete or modify any other instructions.

% \subsection{Increment a Register's Content}\label{task2}
%
% An earlier instruction had already made a copy of the character currently
% pointed to by the \lstinline{text} pointer, so we are now free to increment the
% \lstinline{text} pointer from line~13. The next line of assembly code will do
% just that. The \lstinline{text} pointer is in the \lstinline{%rsi} register.
%
% Find the line in \textit{addressinglab.s} that says \\
% \texttt{\#\#\#\#\# PLACE INSTRUCTION FOR TASK \ref{task2} ON NEXT LINE \#\#\#\#\#} \\
% On the next line, insert an \lstinline{incq} instruction to increase the
% address in \lstinline{%rsi} by 1.
%
% % incq %rsi
%
% Do not delete the \texttt{\#\#\#\#\# PLACE INSTRUCTION...} comment, and do not
% delete or modify any other instructions.

\subsection{Add the Contents of Two Registers}\label{task3}

You can now add the value computed in Task~\ref{task1} to the copy of the
character previously pointed to by the \lstinline{text} pointer, as part of
line~7. The character is in the \lstinline{%al} register, and the value from
Task~\ref{task1} is in register \lstinline{%edx}. In this task, you will first
sign-extend the one-byte character so that it can be added to the 32-byte
value, and then you will perform the addition.

Find the line in \textit{addressinglab.s} that says \\
\texttt{\#\#\#\#\# PLACE INSTRUCTIONS FOR TASK \ref{task3} ON NEXT TWO LINES \#\#\#\#\#} \\
On the next line, insert a \lstinline{movsbl} instruction. This instruction is
like a \lstinline{mov} instruction except that it \textit{s}ign-extends a
\textit{b}yte so that it becomes a \textit{l}ong word (using the IA32
nomenclature that a ``long word'' occupies 4 bytes). The source for this
instruction is the \lstinline{%al} register, and the destination is
\lstinline{%eax}.

On the next line after that, insert an \lstinline{addl} instruction to add the
contents of \lstinline{%eax} and \lstinline{%edx}, leaving the sum in
\lstinline{%eax}.

% movsbl %al, %eax
% addl %edx, %eax

Do not delete the \texttt{\#\#\#\#\# PLACE INSTRUCTIONS...} comment, and do not
delete or modify any other instructions.

\subsection{Store a Value in Memory}\label{task4}

The next assembly instruction you will introduce combines part of line~8 and
line~10. Register \lstinline{%al} will hold either
\lstinline{(char)(reduced_character+'A')} from line 28 or it will hold the
character previously pointed to by \lstinline{text}. This character needs to be
placed in memory at the address pointed to by the \lstinline{target} pointer.
Register \lstinline{%r8} holds that address.

Find the line in \textit{addressinglab.s} that says \\
\texttt{\#\#\#\#\# PLACE INSTRUCTION FOR TASK \ref{task4} ON NEXT LINE \#\#\#\#\#} \\
On the next line, insert a \lstinline{movb} instruction to copy the character.
The source for the instruction is the \lstinline{%al} register. The destination
is the memory location pointed to by the \lstinline{%r8} register; that is, you
will need to dereference the address in \lstinline{%r8}.

% movb %al, (%r8)

Do not delete the \texttt{\#\#\#\#\# PLACE INSTRUCTION...} comment, and do not
delete or modify any other instructions.

\subsection{Load a Value from Memory}\label{task5}

Now you will load the next character to be enciphered. This character is
pointed to by the \lstinline{text} pointer, and this pointer is in register
\lstinline{%rsi}. You will place the character in the 32-bit register
\lstinline{%eax}.

Find the line in \textit{addressinglab.s} that says \\
\texttt{\#\#\#\#\# PLACE INSTRUCTION FOR TASK \ref{task5} ON NEXT LINE \#\#\#\#\#} \\
On the next line, insert a \lstinline{movzbl} instruction to copy the
character. \lstinline{movzbl} is like \lstinline{movsbl}, except that it
\textit{z}ero-extends the byte. The source for the instruction is the memory
location pointed to by \lstinline{%rsi}, and the destination is register
\lstinline{%eax}.

% movzbl (%rsi), %eax

Do not delete the \texttt{\#\#\#\#\# PLACE INSTRUCTION...} comment, and do not
delete or modify any other instructions.

\subsection*{Check Your Progress}

You have now completed the \function{caesar_cipher} function. We strongly
recommend that you confirm that this function works before moving on to the
remaining tasks. Generate the executable with the command:

\texttt{gcc -std=c99 -Wall -o addressinglab addressingdriver.c addressinglab.s}

Run the program with a few manual tests. For example, ``ZEBRA'' with the key
\texttt{1} enciphers to ``AFCSB''. (Note that the \function{caesar_cipher}
function will only encipher uppercase letters.) If the function does not
perform correctly go back and double-check each of the six instructions you
placed in it.


\section{Sentence to Uppercase Function}

The second of the three functions converts lowercase letters in a sentence
to uppercase letters. Here is the equivalent C code:

\lstinputlisting[firstline=39, lastline=45, numbers=left]{addressinglab.c}

Both tasks for this function are for line~4.

\subsection{Index Arrays as the Source}\label{task6}

Your next task is to convert lowercase letters to uppercase letters. As an
efficiency gain, the repeated calls to \function{toupper} on line~4 have been
replaced with a lookup table. The base address for the \lstinline{sentence}
array is in \lstinline{%r15}; the base address for the lookup table is in
\lstinline{%rcx}, and the loop index \lstinline{i} is in \lstinline{%rbx}.

Find the line in \textit{addressinglab.s} that says \\
\texttt{\#\#\#\#\# PLACE INSTRUCTIONS FOR TASK \ref{task6} ON NEXT TWO LINES \#\#\#\#\#} \\
On the next line, insert a \lstinline{movsbq} instruction. \lstinline{movsbq}
is like \lstinline{movsbl} except that it sign-extends the byte so that it
becomes a \textit{q}uad word (using the Intel64 nomenclature that a ``quad
word'' occupies 8 bytes). The source is a location in the \lstinline{sentence}
array: use the indexed addressing mode. The base address is \lstinline{%r15};
the index is \lstinline{%rbx}, and each array element is 1 byte. The
destination for this instruction is \lstinline{%rdx}.

On the next line after that you will use the \function{toupper} lookup table.
To preserve the illusion that the program called the \function{toupper}
function, the lookup table stores integers (\function{toupper}'s specification
states that it returns an \lstinline{int}). Insert a \lstinline{movzbl}
instruction. The source is a location in the lookup table array: use the indexed
addressing mode. The base address is \lstinline{%rcx}; the index is the
character from the previous instruction in \lstinline{%rdx}, and each array
element is 4 bytes in size. The destination for this instruction is
\lstinline{%ecx}.

% movsbq (%r15,%rbx), %rdx
% movzbl (%rcx,%rdx,4), %ecx

Do not delete the \texttt{\#\#\#\#\# PLACE INSTRUCTIONS...} comment, and do not
delete or modify any other instructions.

\subsection{Index an Array as the Destination}\label{task7}

The other part of line~4 is casting the integer from Task~\ref{task6} to a
\lstinline{char} and storing it in the \lstinline{destination} array. The
array's base address is in \lstinline{%r14}, and as before the loop index is in
\lstinline{%rbx}.

Find the line in \textit{addressinglab.s} that says \\
\texttt{\#\#\#\#\# PLACE INSTRUCTION FOR TASK \ref{task7} ON NEXT LINE \#\#\#\#\#} \\
On the next line, use a \lstinline{movb} instruction to move the lower 8 bits
of the integer into the \lstinline{destination} array. The instructions's
source is \lstinline{%cl}, and the destination is a location in the array. The
array's base address is \lstinline{%r14}; the index is \lstinline{%rbx}, and
each array element is 1 byte.

% movb %cl, (%r14,%rbx)

Do not delete the \texttt{\#\#\#\#\# PLACE INSTRUCTION...} comment, and do not
delete or modify any other instructions.

\subsection*{Check Your Progress}

You have now completed the \function{sentence_to_uppercase} function. We
strongly recommend that you confirm that this function works before moving on
to the remaining tasks. In \textit{addressingdriver.c}'s \function{main}
function, un-comment this line:

\begin{lstlisting}
capitalized_plaintext = sentence_to_uppercase(capitalized_plaintext, plaintext);
\end{lstlisting}
Then generate the executable with the command:

\texttt{gcc -std=c99 -Wall -o addressinglab addressingdriver.c addressinglab.s}

Run the program with a few manual tests. For example, ``ZebrA'' with the key
\texttt{1} enciphers to ``AFCSB'', and the deciphered text will be ``ZEBRA''.
If the function does not perform correctly go back and double-check each of the
three instructions you placed in it.


\section{Cipher Validation Function}

The third function validates that the plaintext and ciphertext are a valid pair
by confirming that they are both the length specified by the package's
\lstinline{sentence_length} field and that the inverse of the package's
\lstinline{key} field will decipher the ciphertext back to the plaintext. (See
\textit{addressinglab.h} for the field details of the
\lstinline{cipher_package} structure.) Here is the equivalent C code:

\lstinputlisting[firstline=47, lastline=54, numbers=left, breaklines=true, breakatwhitespace=true]{addressinglab.c}

\subsection{Access Fields in a Struct}\label{task8}

Your final task is to position arguments into the correct registers for the
call to \function{caesar_cipher} in line~5. The \lstinline{deciphered_text}
pointer has already been placed in the correct register; you do not need to
take care of that. Each of the other two arguments is a field in the
\lstinline{cipher_package} structure. The base address for \lstinline{package}
is in \lstinline{%rbx}.

Find the line in \textit{addressinglab.s} that says \\
\texttt{\#\#\#\#\# PLACE INSTRUCTIONS FOR TASK \ref{task8} ON NEXT TWO LINES \#\#\#\#\#} \\
On the next line, use a \lstinline{movq} instruction to copy
\lstinline{package->ciphertext} into \lstinline{%rsi}. Use the displacement
addressing mode in the source operand. The base address is \lstinline{%rbx},
and the \lstinline{ciphertext} field is positioned 8 bytes after the base
address.

On the next line after that, you need to place \lstinline{-(package->key)} into
\lstinline{%edx}. Register \lstinline{%edx} contains the value \lstinline{0},
so we can generate \lstinline{-(package->key)} by subtracting
\lstinline{package->key} from the content of \lstinline{%edx} and placing the
result in \lstinline{%edx}. Insert a \lstinline{subl} instruction to accomplish
this. Use displacement mode addressing to access \lstinline{package->key}, which
is $20_{10}$ bytes after the base address that is in \lstinline{%rbx}.

% movq 8(%rbx), %rsi
% subl 20(%rbx), %edx

Do not delete the \texttt{\#\#\#\#\# PLACE INSTRUCTIONS...} comment, and do not
delete or modify any other instructions.

\subsection*{Check Your Program}

You have now completed the \function{validate_cipher} function, and with it,
the Pleistocene Petting Zoo's cipher program. In \textit{addressingdriver.c}'s
\function{main} function, un-comment all of the lines. Generate the executable
with the command:

\texttt{gcc -std=c99 -Wall -o addressinglab addressingdriver.c addressinglab.s}

Run the program with a few manual tests. All cipher packages generated by the
\function{main} function are valid, and so any input you use should produce the
report ``Cipher package is valid.'' If \function{validate_cipher} does not
perform correctly go back and double-check each of the two instructions you
placed in it.


\section*{Turn-in and Grading}

When you have completed this assignment, upload \textit{addressinglab.s} to
\filesubmission.

This assignment is worth 10 points. \\

\begin{description}
\rubricitem{1}{Task~\ref{task1}:~\nameref{task1}}
% \rubricitem{1}{Task~\ref{task2}:~\nameref{task2}}
\rubricitem{2}{Task~\ref{task3}:~\nameref{task3}}
\rubricitem{1}{Task~\ref{task4}:~\nameref{task4}}
\rubricitem{1}{Task~\ref{task5}:~\nameref{task5}}
\rubricitem{2}{Task~\ref{task6}:~\nameref{task6}}
\rubricitem{1}{Task~\ref{task7}:~\nameref{task7}}
\rubricitem{2}{Task~\ref{task8}:~\nameref{task8}}
\end{description}

\section*{Epilogue}

Archie is hurriedly packing is trunk, like he's about to leave on a
short-notice urgent trip. Before charging out the door, he pauses to tell you,
``H.Awk~Aye just stole some of our samples. I need to track him down before he
sells them to the Supersized Safari Syndicate. I guess this means you're in
charge of the Zoo's computer system now. Don't worry, you'll be fine. What
could possibly go wrong?''

\textit{To be continued...}

\end{document}