1 files changed, 56 insertions, 0 deletions
diff --git a/report/report.tex b/report/report.tex
index c2eb999..ea6822b 100644
--- a/report/report.tex
+++ b/report/report.tex
@@ -146,6 +146,62 @@ addresses around.
 \end{figure}
 
 \section{Implementation}
+This four phase design has been converted into Assembly code using the x86 64 instruction set.
+Furthermore the design has been split up in modules, where each module is a collection of closely
+related functions. For example \textit{Array\_maker.s} contains functions meant to parse data.
+All functions in this program follow the x86 calling conventions, with a few exceptions
+where all registers are preserved. Below is a detailed explanation of some of the more 
+interesting functions.
+
+\subsection{Insertion-sort}
+This is a classic implementation of the iterative insertion-sort. The function takes three arguments:
+address of the array of pointers to each coordinate, number of coordinates and which coordinate dimension to sort by.
+The first step of this algorithm is to check the number of coordinates with a compare statement, if n $\le$ 1,
+the array is already sorted and nothing should be done. Otherwise the algorithm initializes two indices i and j,
+representing the outer and inner loop in insertion-sort. A snippet of the algorithm is seen below.
+
+\begin{algorithm}[H]
+\caption{Isertion-sort inner Loop}
+\SetAlgoNoLine
+\SetKw{KwCmp}{cmpq}
+\SetKw{KwJl}{jl}
+\SetKw{KwMov}{movq}
+\SetKw{KwJge}{jge}
+\SetKw{KwDec}{decq}
+\SetKw{KwJmp}{jmp}
+
+\textbf{inner\_loop:} \\
+\KwCmp{$0$, \%r14} \tcp*[r]{if j < 0 stop and insert the key}
+\KwJl insert\_key \\
+
+\KwMov{$(\%rdi, \%r14, 8)$, \%r10} \tcp*[r]{pointer to key → r10}
+\KwMov{$(\%r10, \%rdx, 8)$, \%r11} \tcp*[r]{key → r11}
+
+\KwCmp{\%r11, \%r9} \\
+\KwJge insert\_key \tcp*[r]{if A[i] >= A[j] stop}
+
+\KwMov{\%r10, $8(\%rdi, \%r14, 8)$} \tcp*[r]{A[j+1] = pointer to key of j}
+
+\KwDec{\%r14} \tcp*[r]{move to j - 1}
+\KwJmp inner\_loop \\
+
+\textbf{insert\_key:} \tcp*[r]{Insert the key here}
+
+\end{algorithm}
+
+The two registers R8 and R9 save the current index and value of "i" while R10
+and R11 are used for "j". The formula for loading the value of an element consists of two steps:
+firstly loading the pointer to the element, and secondly loading the actual value of this pointer. This
+is a result of implementing an array of pointers to allow more flexibility, instead of directly using the array coordinates.
+Lines 3 and 4 of the pseudo code demonstrate how this process is done. Each pointer is 8-bytes, therefore the correct pointer
+is calculated by adding index * 8 to RDI, which stores the head of the pointer array. Next, because each value is also 8 bytes,
+RDX * 8 to the pointer, where RDX is the coordinate dimension the algorithm uses to sort, can be used to retrieve the actual value of this pointer.
+After loading the values, compare statements can be used to find the correct placement of each coordinate.
+Like the standard insertion-sort, this implementation creates a sorted part on the left side of the array. Therefore
+the first compare checks if A[i] is equal or bigger than A[j], if this is the case A[i] can not be smaller than any element
+at j or before. Otherwise the algorithm keeps searching for the correct placement of A[i] in the sorted part by decreasing j and repeating
+the inner loop. If j at some point hits 0, the element A[i] is the current smallest coordinate
+and should be inserted there. This process continues until R15 which holds the index of "i" is greater than the number of coordinates.
 
 \section{Evaluation}
 \begin{itemize}