mp_lab1_report.tex

% Created 2024-04-18 Thu 18:35
% Intended LaTeX compiler: xelatex
\documentclass[11pt]{article}
\input{~/Github/org-to-latex-export/mytemplate.tex}

\usepackage{polyglossia}
\setmainlanguage[variant=usmax]{english}
\author{Γιώργος Σελιβάνωφ, Λαμπρινός Χατζηιωάννου}
\date{\today}
\title{Εργαστήριο 1}
\hypersetup{
 pdfauthor={Γιώργος Σελιβάνωφ, Λαμπρινός Χατζηιωάννου},
 pdftitle={Εργαστήριο 1},
 pdfkeywords={},
 pdfsubject={description},
 pdfcreator={Emacs 29.2 (Org mode 9.7-pre)}, 
 pdflang={English}}
\begin{document}

\maketitle
\justifying
\section{Main C Function}
\label{sec:org4d2587c}

\begin{quote}
\begin{itemize}
\item Θέλουμε να την κάνουμε να δέχεται input
\item Να δοκιμάζει το input βάσει των συναρτήσεων μας
\item Να δείχνει output
\end{itemize}
\end{quote}

Η τωρινή υλοποίηση λειτουργεί ως εξής:
\begin{enumerate}
\item Λαμβάνουμε ένα αλφαριθμητικό (μέχρι 128 χαρακτήρες) ως είσοδο από τον χρήστη με την χρήση UART
\item Εμφανίζουμε το αλφαριθμητικό μέσω printf
\item Παράγουμε το hash του αλφαριθμητικού,
\item Παράγουμε την ψηφιακή ρίζα του hash
\item Παράγουμε το Sum of Natural Numbers της ψηφιακής ρίζας
\item Εμφανίζουμε όλα τα αποτελέσματα στον χρήστη μέσω UART και printf
\end{enumerate}
\section{Hashing Function}
\label{sec:org5b6cad2}
Παρόλο που φαινόταν δύσκολη κατα την εκφώνηση η συγκεκριμένη
λειτουργία αποδείχτηκε αρκετά εύκολη για την υλοποίηση της σε
assembly. Ουσιαστικά, υλοποιήθηκε ο αλγόριθμος που εμφανίζεται
στο παρακάτω απόσπασμα κώδικα C.

\begin{verbatim}
int hashfunc(char inputString[]) {
  int values[] = {10, 42, 12, 21, 7, 5, 67, 48, 69, 2, 36, 3, 19,
                  1, 14, 51, 71, 8, 26, 54, 75, 15, 6, 59, 13, 25};
  int hash = 0;

  for (int ind = 0; inputString[ind]!='\0'; ind++)
    {
      // ASCII: Caps: (64-91), Lower: (96-123), Digits: (47-58)
      if (inputString[ind] > 64 && inputString[ind] < 91) // Meaning caps
        hash += values[inputString[ind] - 65];
      else if (inputString[ind] > 96 && inputString[ind] < 123) // Meaning lowercase
        hash -= values[inputString[ind] - 97];
      else if (inputString[ind] > 47 && inputString[ind] < 58) // Meaning integer
        hash += inputString[ind] - 48;
    }
  return hash;
}

\end{verbatim}
\section{Digital Root}
\label{sec:org93040ec}
Για την υλοποίηση της ρουτίνας σε Assembly που θα υπολογίζει την
ψηφιακή ρίζα ενός αριθμού, αποφασίσαμε να αντικαταστήσουμε τον
αναδρομικό υπολογισμό του αθροίσματος (\(68 \to 6 + 8 = 14 \to 1 + 4 = 5\))
με μια εναλλακτική μέθοδο: τον υπολογισμό του υπολοίπου της
ευκλείδειας διαίρεσης του αριθμού αυτού με το 9. Οι δύο διαδικασίες
είναι ισοδύναμες (\(68\mod 9 = 5\)), με μοναδική εξαίρεση την περίπτωση
που η ψηφιακή ρίζα του αριθμού είναι 9 και άρα το υπόλοιπό του 0. Μία
απλή αντικατάσταση του 0 με το 9 καθιστά τις 2 αυτές διαδικασίες
πλήρως ταυτόσημες ως προς το αποτέλεσμά τους. Με την χρήση αυτού του
αλγορίθμου εξοικονομούμε αρκετούς κύκλους ρολογιού, καθώς αποφεύγουμε
τα branches του αναδρομικού αλγορίθμου.

Όσον αφορά την υλοποίηση της διαίρεσης με το 9 επιλέχθηκε η χρήση του
πολλαπλασιασμού με αντίστροφο, παρότι ο \textbf{Cortex-M4} διαθέτει έτοιμες
εντολές διαίρεσης. Η επιλογή αυτή έγινε διότι οι εντολές DIV είναι
ιδιαίτερα ακριβές σε κύκλους ρολογιού (2-12) σε σύγκρισή με την UMULL
(που απαιτεί μόνο 1). Αφού ο διαιρέτης είναι σταθερός, ο αντίστροφος
μπορεί απλώς να οριστεί ως μια σταθερά της ρουτίνας.

Περισσότερες πληροφορίες σχετικά με τον τρόπο υπολογισμού του
αντίστροφου και την ορθότητα της μεθόδου μπορούν να βρεθούν στην
δημοσίευση με τίτλο “Division by Invariant Integers using
Multiplication” των Torbjorn Granlund και Peter L. Montgomery\cite{granlundDivisionInvariantIntegers}

Η χρήση των \texttt{.N} suffix στις εντολές που προηγούνται των εντολών \texttt{IT}
γίνεται ώστε να κωδικοποιηθούν από τον compiler με 16-bit, γεγονός που
σύμφωνα με το documentation της ARM για τον \textbf{Cortex-M4} σημαίνει πως η
εκτέλεση της εντολής \texttt{IT} θα ξοδέψει 0 κύκλους ρολογιού, καθώς θα
ενσωματωθεί στην προηγούμενη\cite{DocumentationArmDeveloper}
\section{Sum of Natural Numbers}
\label{sec:org094e030}
Για την υλοποίηση της ρουτίνας Sum of Natural Numbers υλοποιήσαμε ένα
απλό loop:

Όσο ο αριθμός εισόδου είναι μεγαλύτερος του 0, η ρουτίνα τον προσθέτει
στο άθροισμα, τον μειώνει κατά 1 και κάνει branch στην αρχή του loop.
Όταν η συνθήκη παύει να ισχύει, η ρουτίνα επιστρέφει το τρέχον
άθροισμα.
\section{Bibliography}
\label{sec:orgdf1f8cf}
\bibliographystyle{ieeetr} 
\bibliography{../Microprocessors}
\end{document}