From c4d95bde5fcda18b19766fe8ec2912c1ebede4e4 Mon Sep 17 00:00:00 2001 From: Navid Samanghoon Date: Sun, 26 Oct 2025 12:21:48 +0100 Subject: Explained insertion-sort --- report/report.tex | 56 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) 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} -- cgit v1.2.3-70-g09d2