\section{El algoritmo de hashing \emph{SHA-1}}\label{sha1}
\subsection{Descripción}
El algoritmo SHA-1 es una función de hash que toma un conjunto de datos de entrada, y devuelve un valor de hash de 160 bits de longitud.

Si bien el algoritmo está definido para datos a nivel de bit, en el contexto de este trabajo, en el que los datos de entrada en realidad son archivos, la menor unidad de almacenamiento pasa a ser el \emph{Byte}. De manera que todos los algoritmos estudiados en este trabajo operan a nivel de \emph{Byte}.

Con el objeto de describir el algoritmo SHA-1 de la manera más comprensible, a continuación haremos una descripción general del mismo, para luego especificar un pseudocódigo con todos los detalles.

En términos generales, podemos dividir el algoritmo SHA-1 en dos etapas: (1) el \emph{padding} o agregado de datos, y (2) el procesamiento de los datos que generan el valor de hash:

\begin{enumerate}
\item Padding o relleno de los datos de entrada:
\begin{itemize}
\item El algoritmo realiza un padding (agregado de datos) en los datos de entrada, con el objeto de que la longitud total de esos datos sea siempre múltiplo de 64 bytes.
\item Básicamente, el padding consiste en agregar algunos bytes al final de los datos de entrada.
\item Los detalles acerca de este proceso se describen en la sección \ref{sha1_padding}.
\end{itemize}
\vspace{5pt}
\item Procesamiento de los datos:
\begin{itemize}
\item Inmediatamente después del padding, los datos de entrada se parten en bloque de 64 bytes, que se procesan de forma secuencial.
\item El procesamiento de cada bloque tiene como resultado la actualización del valor de hash devuelto por el algoritmo.
\item Cada uno de los bloques de 64 bytes de los datos de entrada se considera un vector de 16 valores \texttt{DWORD}.
\item El cómputo realizado durante la actualización del valor de hash utiliza esos 16 \texttt{DWORDs} de cada bloque.
\end{itemize}
\end{enumerate}

El siguiente pseudocódigo es la descripción formal del algoritmo SHA-1, de acuerdo al \emph{fips-180}\footnote{Véase nota 3.}, para un conjunto de datos de entrada \texttt{m} de cualquier longitud:
\clearpage

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{12pt}\textbf{Función} \texttt{SHA-1}\\
\vspace{3pt}
\hspace{18pt}\textbf{- Entrada}: conjunto de datos $m$ de cualquier longitud en bytes\\
\hspace{18pt}\textbf{- Salida}: vector $h[5]$ de \texttt{DWORD} con el valor del hash SHA-1\\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Variables locales. \\
\hspace{24pt}// \\
\hspace{24pt}$h[5]$: \hspace{3pt} vector de \texttt{DWORD} \hspace{18pt} // Valor de hash. \\
\hspace{24pt}$w[80]$: vector de \texttt{DWORD} \hspace{18pt} // Vector denominado \emph{Message Schedule}. \\
\hspace{24pt}$a, \ b, \ c, \ d, \ e, \ f, \ k$: \texttt{DWORD} \hspace{3pt} // Variables denominadas de \emph{estado}. \\
\hspace{24pt}$aux$: \texttt{DWORD} \hspace{68pt} // Variable auxiliar. \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Inicialización del vector $h$. \\
\hspace{24pt}// \\
\hspace{24pt}$h[0] =$ \texttt{0x67452301} \\
\hspace{24pt}$h[1] =$ \texttt{0xEFCDAB89} \\
\hspace{24pt}$h[2] =$ \texttt{0x98BADCFE} \\
\hspace{24pt}$h[3] =$ \texttt{0x10325476} \\
\hspace{24pt}$h[4] =$ \texttt{0xC3D2E1F0} \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Padding o relleno. Después del padding, los datos de entrada $m$ \\
\hspace{24pt}// se extenderán en algunos bytes, y su tamaño total será múltiplo \\
\hspace{24pt}// de 64 bits. \\
\hspace{24pt}// \\
\hspace{24pt}$m = \ $ \texttt{Padding}$(m)$ \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Procesamiento de cada bloque de 64 bytes de los datos \\
\hspace{24pt}// de entrada $m$ para generar el hash. \\
\hspace{24pt}//\\
\hspace{24pt}\textbf{Para} cada bloque $b$ de 64 bytes en los datos $m$, \textbf{hacer}\\
\vspace{10pt}
\hspace{36pt}$a = h[0]$ \\
\hspace{36pt}$b = h[1]$ \\
\hspace{36pt}$c = h[2]$ \\
\hspace{36pt}$d = h[3]$ \\
\hspace{36pt}$e = h[4]$ \\
\vspace{10pt}
\hspace{36pt}// \\
\hspace{36pt}// Copia directa de los 16 \texttt{DWORDs} correspondientes al bloque $b$ \\
\hspace{36pt}// en los primeros 16 elementos del vector $w$. \\
\hspace{36pt}// \\
\hspace{36pt}\textbf{Para} \texttt{i} = 0 hasta 15 \textbf{hacer} \\
\vspace{3pt}
\hspace{48pt}$w[i] = b[i]$ \\
\vspace{3pt}
\hspace{36pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{36pt}// \\
\hspace{36pt}// Extensión del vector $w$: los elementos del vector $w$ a partir \\
\hspace{36pt}// del 16 se obtienen mediante la siguiente función, expresada \\
\hspace{36pt}// en términos de elementos previos del vector $w$. \\
\hspace{36pt}// \\
\hspace{36pt}\textbf{Para} $i = 16$ hasta 79 \textbf{hacer} \\
\vspace{3pt}
\hspace{48pt}$w[i] = \left(w[i-3] \oplus w[i-8] \oplus w[i-14] \oplus w[i-16]\right) \hookleftarrow 1$ \\
\vspace{3pt}
\hspace{36pt}\textbf{Fin Para} \\
\newpage
\vspace{10pt}
\hspace{36pt}// \\
\hspace{36pt}// Actualización de las variables de estado $a$, $b$, $c$, $d$ y $e$. \\
\hspace{36pt}// \\
\hspace{36pt}\textbf{Para} $i = 0$ hasta 79, \textbf{hacer} \\
\vspace{10pt}
\hspace{48pt}\textbf{Si} $(0 \le i \le 19)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{60pt}$f = \left(b \wedge c\right) \vee \left(\left(\neg \ b\right) \wedge d\right)$ \\
\hspace{60pt}$k =$ \texttt{0x5A827999} \\
\vspace{5pt}
\hspace{48pt}\textbf{Sino Si} $(20 \le i \le 39)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{60pt}$f = b \oplus c \oplus d$ \\
\hspace{60pt}$k =$ \texttt{0x6ED9EBA1} \\
\vspace{5pt}
\hspace{48pt}\textbf{Sino Si} (40 $\le$ \texttt{i} $\le$ 59) \textbf{entonces} \\
\vspace{3pt}
\hspace{60pt}$f = \left(b \wedge c\right) \vee \left(b \wedge d\right) \vee \left(c \wedge d\right)$ \\
\hspace{60pt}$k =$ \texttt{0x8F1BBCDC} \\
\vspace{5pt}
\hspace{48pt}\textbf{Sino} \\
\vspace{3pt}
\hspace{60pt}$f = b \oplus c \oplus d$ \\
\hspace{60pt}$k =$ \texttt{0xCA62C1D6} \\
\vspace{5pt}
\hspace{48pt}\textbf{Fin Si} \\
\vspace{10pt}
\hspace{48pt}$aux = (a \hookleftarrow 5) + f + e + k + w[i]$ \\
\hspace{48pt}$e = d$ \\
\hspace{48pt}$d = c$ \\
\hspace{48pt}$c = b \hookleftarrow 30$ \\
\hspace{48pt}$b = a$ \\
\hspace{48pt}$a = aux$ \\
\vspace{5pt}
\hspace{36pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{36pt}// \\
\hspace{36pt}// Actualización del valor de hash. \\
\hspace{36pt}// \\
\hspace{36pt}$h[0] = h[0] + a$ \\
\hspace{36pt}$h[1] = h[1] + b$ \\
\hspace{36pt}$h[2] = h[2] + c$ \\
\hspace{36pt}$h[3] = h[3] + d$ \\
\hspace{36pt}$h[4] = h[4] + e$ \\
\vspace{5pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{24pt}\textbf{Devolver} $h$ \\
\vspace{10pt}
\hspace{12pt}\textbf{Fin Función} \\
\end{flushleft}
}

\subsection{Padding en el algoritmo SHA-1}\label{sha1_padding}
\noindent El proceso de padding se puede resumir de la siguiente forma:

\begin{enumerate}
\item Inmediatamente después del último byte de los datos de entrada $m$, se agrega el byte \texttt{0x80}.
\item A continuación, se agrega una cantidad $n$ de bytes \texttt{0x0} (que se describe más adelante), que puede ser nula.
\item Se computa el tamaño $t$ en bits de los datos de entrada $m$ originales (esto es, sin el padding).
\item El valor obtenido $t$ se expresa en un \texttt{QWORD}, en formato \emph{Big-Endian} (esto es, el byte más significativo se ubica en la posición de memoria más significativa).
\item Asumiento que el tamaño en bytes de los datos de entrada $m$ originales es $s$, el nuevo tamaño después del padding queda definido por:
\begin{displaymath}
s + 1 + n + 8
\end{displaymath}
\item El valor $n$ debe ser tal que la suma total produzca el menor múltiplo de 64.

\end{enumerate}

\noindent \textbf{Ejemplo}:
\begin{itemize}
\item[-] Sea \texttt{f} un archivo de tamaño 0 bytes.
\item[-] El tamaño de los datos después del padding queda definido como:
\begin{displaymath}
0 + 1 + n + 8 = 9 + n
\end{displaymath}
\item[-] El menor múltiplo de 64 que puede obtenerse es precisamente 64, con lo cual:
\begin{displaymath}
9 + n = 64 \Rightarrow n = 55
\end{displaymath}
\item[-] Luego, los datos de entrada adquieren la siguiente estructura tras el padding:

\begin{center}
\texttt{0x80 | 0x0 ... 0x0 | 0x0000000000000000}
\end{center}
donde:
\begin{enumerate}
\item \texttt{0x80}: es el byte agregado al final de los datos. Dado que el archivo \texttt{f} del ejemplo no tiene datos, este byte ocupa el primer lugar.
\item \texttt{0x0 ... 0x0}: es la cadena de 55 bytes de valores \texttt{0x0} correspondientes al padding.
\item \texttt{0x0000000000000000}: es el valor \texttt{QWORD} expresado en \emph{Big-Endian} con el tamaño en bits de los datos originales, en este caso 0.
\end{enumerate}
\end{itemize}
\noindent \textbf{Otro ejemplo}:
\begin{itemize}
\item[-] Sea \texttt{f} un archivo de tamaño 55 bytes.
\item[-] El tamaño de los datos después del padding queda definido por:
\begin{displaymath}
55 + 1 + n + 8 = 64
\end{displaymath}
\item[-] El menor múltiplo de 64 que puede obtenerse es precisamente 64, con lo cual:
\begin{displaymath}
64 + n = 64 \Rightarrow n = 0
\end{displaymath}
\item[-] De modo que no es necesario agregar ningún byte \texttt{0x0}, y los datos de entrada adquieren la siguiente estructura tras el padding:
\begin{center}
55 bytes de datos de \texttt{f | 0x80 | 0x00000000000001B8}
\end{center}
Donde \texttt{0x00000000000001B8} es el \texttt{QWORD} en \emph{Big-Endian} con el tamaño en bits de los datos originales de \texttt{f} (esto es, 55 Bytes $\times$ $8 = 440$ bits, que en hexadecimal es \texttt{0x01B8}).
\end{itemize}
\noindent \textbf{Otro ejemplo más}:
\begin{itemize}
\item[-] Sea f un archivo de tamaño 56 bytes.
\item[-] El tamaño de los datos después del padding queda definido como:
\begin{displaymath}
56 + 1 + n + 8 = 65
\end{displaymath}
\item[-] El menor múltiplo de 64 que puede obtenerse es 128, con lo cual:
\begin{displaymath}
65 + n = 128 \Rightarrow n = 63
\end{displaymath}
\newpage
\item[-] Luego, será necesario agregar 63 bytes \texttt{0x0}, y los datos de entrada se extienden de la siguiente forma:
\begin{center}
56 bytes de datos de \texttt{f | 0x80 | 0x0 0x0 ... 0x0 | 0x00000000000001C0}
\end{center}
\end{itemize}

\noindent El siguiente pseudocódigo es la descripción formalmente el proceso de padding del algoritmo SHA-1:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{12pt}\textbf{Función} \texttt{Padding} \\
\vspace{3pt}
\hspace{18pt}- \textbf{Entrada}: conjunto de datos m de cualquier longitud \\
\hspace{18pt}- \textbf{Salida}:  conjunto de datos m extendido \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Variables locales. \\
\hspace{24pt}// \\
\hspace{24pt}$r, s, t$: entero \\
\hspace{24pt}$q$: \texttt{QWORD} \\
\vspace{10pt}
\hspace{24pt}$t =$ \texttt{tamaño}$(m)$ \\
\hspace{24pt}$s = t + 9$ \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Determinamos el tamaño total de los datos $m$ cuando le \\
\hspace{24pt}// sumamos los 9 bytes correspondientes al byte \texttt{0x80}, seguido \\
\hspace{24pt}// por el valor \texttt{QWORD} asociado al tamaño en bits de los datos $m$. \\
\hspace{24pt}// \\
\hspace{24pt}$r = s \ \bmod \ 64$ \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Si al sumar los 9 bytes al tamaño de $m$ no obtuvimos un \\
\hspace{24pt}// múltiplo de 64, extenderemos el número de bytes que \\
\hspace{24pt}// agregaremos para alcanzar el primer múltiplo de 64. \\
\hspace{24pt}// \\
\hspace{24pt}\textbf{Si} $(r \neq 0)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{36pt}$s = s + (64 - r)$ \\
\vspace{3pt}
\hspace{24pt}\textbf{Fin Si} \\
\vspace{10pt}
\hspace{24pt}\textbf{Extender} $m$ en $s$ bytes \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// La variable $t$ almacena el tamaño de los datos $m$ originales antes \\
\hspace{24pt}// de la extensión. La utilizamos como índice para insertar el primer \\
\hspace{24pt}// byte del padding. \\
\hspace{24pt}// \\
\hspace{24pt}$m[t] = $ \texttt{0x80} \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Rellenamos con la cantidad de ceros que correspondan. \\
\hspace{24pt}// \\
\hspace{24pt}\textbf{Para} $i = t+1$ hasta $($\texttt{tamaño}$(m) - 9)$, \textbf{hacer} \\
\vspace{3pt}
\hspace{36pt}$m[i] =$ \texttt{0x0} \\
\vspace{3pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Obtenemos el valor \texttt{QWORD} en formato \emph{Big-Endian} del tamaño \\
\hspace{24pt}// en bits de los datos $m$ originales. \\
\hspace{24pt}// \\
\hspace{24pt}$q = $ \texttt{BigEndian\_QWORD}$(t \times 8)$ \\
\newpage
\hspace{24pt}// \\
\hspace{24pt}// Copiamos cada byte del \texttt{QWORD} en los últimos 8 bytes de $m$. \\
\hspace{24pt}// \\
\hspace{24pt}\textbf{Para} $i = 0$ hasta $i = 7$, \textbf{hacer} \\
\vspace{3pt}
\hspace{36pt}$m[$\texttt{tamaño}$(m) - 8 + i] = q[i]$ \\
\vspace{3pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{24pt}\textbf{Devolver} $m$ \\
\vspace{10pt}
\hspace{12pt}\textbf{Fin Función} \\
\end{flushleft}
}

\subsection{Análisis del algoritmo SHA-1 y estrategia de vectorización}
\subsubsection{Primera optimización del algoritmo SHA-1}
Si repasamos la estructura general del algoritmo SHA-1 y abstraemos los ciclos que lo componen, obtenemos algo como lo siguiente:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{48pt}$...$ \\
\vspace{10pt}
\hspace{12pt}\textbf{Para} cada bloque $b$ de 64 bytes en los datos $m$, \textbf{hacer} \\
\vspace{10pt}
\hspace{48pt}$...$ \\
\vspace{10pt}
\hspace{24pt}\textbf{Para} $i = 0$ hasta 15, \textbf{hacer} \\
\vspace{3pt}
\hspace{36pt}$w[i] = b[i]$ \\
\vspace{3pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{48pt}$...$ \\
\vspace{10pt}
\hspace{24pt}\textbf{Para} $i = 16$ hasta 79, \textbf{hacer} \\
\vspace{3pt}
\hspace{36pt}$w[i] = \left(w[i-3] \oplus w[i-8] \oplus w[i-14] \oplus w[i-16]\right) \hookleftarrow 1$ \\
\vspace{3pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{48pt}$...$ \\
\vspace{10pt}
\hspace{24pt}\textbf{Para} $i = 0$ hasta 79, \textbf{hacer} \\
\vspace{3pt}
\hspace{48pt}$...$ \\
\vspace{3pt}
\hspace{36pt}$aux = ... + w[i]$ \\
\vspace{3pt}
\hspace{48pt}$...$ \\
\vspace{3pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{48pt}$...$ \\
\vspace{10pt}
\hspace{12pt}\textbf{Fin Para} \\
\vspace{5pt}
\hspace{48pt}$...$ \\
\end{flushleft}
}

Es fácil ver que el cuerpo del ciclo externo lo componen, en realidad, otros dos ciclos que van de 0 a 79; el primero de ellos partido en dos etapas (la primera, de 0 a 15, y la segunda de 16 a 79).

Por otra parte, se observa que en las rondas:
\begin{itemize}
\item De 0 a 15, el cómputo del $w[i]$ se obtiene de forma directa accediendo a los datos.
\item De 16 a 79, el cómputo del $w[i]$ requiere de otros $w$ previos, en el rango $w[i-16]$ a $w[i-3]$. Pero estos elementos, siempre existen.
\item De 0 a 79, se efectúa una lectura sobre el elemento $w[i]$.
\end{itemize}
por lo que no existe ningún tipo de dependencia especial que impida que los cómputos en el cuerpo de cada ciclo puedan realizarse en un único ciclo anidado, que cubra el rango 0 a 79. De esta forma, obtenemos la primera optimización del algoritmo mediante la siguiente transformación:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{48pt}$...$ \\
\vspace{5pt}
\hspace{12pt}\textbf{Para} cada bloque $b$ de 64 bytes en los datos $m$, \textbf{hacer} \\
\vspace{5pt}
\hspace{48pt}$...$ \\
\vspace{5pt}
\hspace{24pt}\textbf{Para} $i = 0$ hasta 79, \textbf{hacer} \\
\vspace{5pt}
\hspace{36pt}\textbf{Si} $(i < 16)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{48pt}$w[i] = b[i]$ \\
\vspace{3pt}
\hspace{36pt}\textbf{Sino} \\
\vspace{3pt}
\hspace{48pt}$w[i] = \left(w[i-3] \oplus w[i-8] \oplus w[i-14] \oplus w[i-16]\right) \hookleftarrow 1$ \\
\vspace{3pt}
\hspace{36pt}\textbf{Fin Si} \\
\vspace{5pt}
\hspace{48pt}$...$ \\
\vspace{5pt}
\hspace{36pt}$aux = ... + w[i]$ \\
\vspace{5pt}
\hspace{48pt}$...$ \\
\vspace{5pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{5pt}
\hspace{48pt}$...$ \\
\vspace{5pt}
\hspace{12pt}\textbf{Fin Para} \\
\vspace{5pt}
\hspace{48pt}... \\
\end{flushleft}
}

Esta nueva versión del algoritmo SHA-1 es la que emplearemos como base tanto en la versión escalar como en la vectorizada. El pseudocódigo que sigue es la descripción completa de nuestro nuevo algoritmo SHA-1 optimizado:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{12pt}\textbf{Función} \texttt{SHA-1}\\
\vspace{3pt}
\hspace{18pt}\textbf{- Entrada}: conjunto de datos $m$ de cualquier longitud en bytes\\
\hspace{18pt}\textbf{- Salida}: vector $h[5]$ de \texttt{DWORD} con el valor del hash SHA-1\\
\vspace{10pt}
\hspace{24pt}$h[5]$: \hspace{3pt} vector de \texttt{DWORD} \hspace{18pt} // Valor de hash. \\
\hspace{24pt}$w[80]$: vector de \texttt{DWORD} \hspace{18pt} // Vector denominado \emph{Message Schedule}. \\
\hspace{24pt}$a, \ b, \ c, \ d, \ e, \ f, \ k$: \texttt{DWORD} \hspace{3pt} // Variables denominadas de \emph{estado}. \\
\hspace{24pt}$aux$: \texttt{DWORD} \hspace{68pt} // Variable auxiliar. \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Inicialización del vector $h$. \\
\hspace{24pt}// \\
\hspace{24pt}$h[0] =$ \texttt{0x67452301} \\
\hspace{24pt}$h[1] =$ \texttt{0xEFCDAB89} \\
\hspace{24pt}$h[2] =$ \texttt{0x98BADCFE} \\
\hspace{24pt}$h[3] =$ \texttt{0x10325476} \\
\hspace{24pt}$h[4] =$ \texttt{0xC3D2E1F0} \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Padding o relleno. Después del padding, los datos de entrada $m$ \\
\hspace{24pt}// se extenderán en algunos bytes, y su tamaño total será múltiplo \\
\hspace{24pt}// de 64 bits. \\
\hspace{24pt}// \\
\hspace{24pt}$m = \ $\texttt{Padding}$(m)$ \\
\newpage
\hspace{24pt}// \\
\hspace{24pt}// Procesamiento de cada bloque de 64 bytes de los datos \\
\hspace{24pt}// de entrada $m$ para generar el hash. \\
\hspace{24pt}//\\
\hspace{24pt}\textbf{Para} cada bloque $b$ de 64 bytes en los datos $m$, \textbf{hacer}\\
\vspace{5pt}
\hspace{36pt}$a = h[0]$ \\
\hspace{36pt}$b = h[1]$ \\
\hspace{36pt}$c = h[2]$ \\
\hspace{36pt}$d = h[3]$ \\
\hspace{36pt}$e = h[4]$ \\
\vspace{10pt}
\hspace{36pt}\textbf{Para} $i = 0$ hasta 79, \textbf{hacer} \\
\vspace{10pt}
\hspace{48pt}// \\
\hspace{48pt}// Procesamiento del vector $w$ (Message Schedule). \\
\hspace{48pt}// \\
\hspace{48pt}\textbf{Si} $(i < 16)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{60pt}$w[i] = b[i]$ \\
\vspace{5pt}
\hspace{48pt}\textbf{Sino} \\
\vspace{3pt}
\hspace{60pt}$w[i] = \left(w[i-3] \oplus w[i-8] \oplus w[i-14] \oplus w[i-16]\right) \hookleftarrow 1$ \\
\vspace{5pt}
\hspace{48pt}\textbf{Fin Si} \\
\vspace{10pt}
\hspace{48pt}// \\
\hspace{48pt}// Actualización de las variables $a$, $b$, $c$, $d$ y $e$. \\
\hspace{48pt}// \\
\hspace{48pt}\textbf{Si} (0 $\le$ \texttt{i} $\le$ 19) \textbf{entonces} \\
\vspace{3pt}
\hspace{60pt}$f = \left(b \wedge c\right) \vee \left(\left(\neg \ b\right) \wedge d\right)$ \\
\hspace{60pt}$k =$ \texttt{0x5A827999} \\
\vspace{5pt}
\hspace{48pt}\textbf{Sino Si} $(20 \le i \le 39)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{60pt}$f = b \oplus c \oplus d$ \\
\hspace{60pt}$k =$ \texttt{0x6ED9EBA1} \\
\vspace{5pt}
\hspace{48pt}\textbf{Sino Si} $(40 \le i \le 59)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{60pt}$f = \left(b \wedge c\right) \vee \left(b \wedge d\right) \wedge \left(c \wedge d\right)$ \\
\hspace{60pt}$k =$ \texttt{0x8F1BBCDC} \\
\vspace{5pt}
\hspace{48pt}\textbf{Sino} \\
\vspace{3pt}
\hspace{60pt}$f = b \oplus c \oplus d$ \\
\hspace{60pt}$k =$ \texttt{0xCA62C1D6} \\
\vspace{5pt}
\hspace{48pt}\textbf{Fin Si} \\
\vspace{10pt}
\hspace{48pt}$aux = (a \hookleftarrow 5) + f + e + k + w[i]$ \\
\hspace{48pt}$e = d$ \\
\hspace{48pt}$d = c$ \\
\hspace{48pt}$c = b \hookleftarrow 30$ \\
\hspace{48pt}$b = a$ \\
\hspace{48pt}$a = aux$ \\
\vspace{5pt}
\hspace{36pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{36pt}// \\
\hspace{36pt}// Actualización del valor de hash. \\
\hspace{36pt}// \\
\hspace{36pt}$h[0] = h[0] + a$ \\
\hspace{36pt}$h[1] = h[1] + b$ \\
\hspace{36pt}$h[2] = h[2] + c$ \\
\hspace{36pt}$h[3] = h[3] + d$ \\
\hspace{36pt}$h[4] = h[4] + e$ \\
\vspace{5pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{24pt}\textbf{Devolver} $h$ \\
\hspace{12pt}\textbf{Fin Función} \\
\end{flushleft}
}

\subsubsection{Análisis de la factibilidad de la vectorización}\label{sha1_vectorizacion}
Si por un momento nos abstraemos del ciclo anidado, notaremos que el ciclo externo no hace más que inicializar las variables estado al comienzo, y actualizar el vector con el valor de hash al finalizar. No hay optimización posible en estas operaciones.

Analicemos ahora el ciclo anidado. Se distinguen dos partes esenciales en la nueva versión optimizada del algoritmo SHA-1:

\begin{enumerate}
\item El procesamiento del vector $w$ (message schedule).
\item La actualización de las variables de estado $a$, $b$, $c$, $d$ y $e$.
\end{enumerate}
donde la segunda depende de la primera.

En el caso de la actualización de las variables de estado, es fácil ver que existe una circularidad que obliga indefectiblemente al procesamiento secuencial. Esta circularidad queda definida en el último bloque de código del ciclo anidado:

\begin{flushleft}
\hspace{24pt}$aux = (a \hookleftarrow 5) + f + e + k + w[i]$ \\
\hspace{24pt}$e = d$ \\
\hspace{24pt}$d = c$ \\
\hspace{24pt}$c = b \hookleftarrow 30$ \\
\hspace{24pt}$b = a$ \\
\hspace{24pt}$a = aux$ \\
\end{flushleft}

\noindent y está dada por el siguiente esquema:

\vspace{12pt}
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.60]{img/circularidad_sha1.png}
\caption{dependencia circular en el algoritmo SHA-1}\label{circularidad_sha1}
\end{figure}

De esta forma, cualquier posibilidad de vectorización en esta etapa queda descartada.

Analicemos ahora la operatoria sobre el vector \texttt{w}:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{36pt}\textbf{Para} $i = 0$ hasta 79, \textbf{hacer} \\
\vspace{10pt}
\hspace{48pt}\textbf{Si} $(i < 16)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{60pt}$w[i] = b[i]$ \\
\vspace{5pt}
\hspace{48pt}\textbf{Sino} \\
\vspace{3pt}
\hspace{60pt}$w[i] = (w[i-3] \oplus w[i-8] \oplus w[i-14] \oplus w[i-16]) \hookleftarrow 1$ \\
\vspace{5pt}
\hspace{48pt}\textbf{Fin Si} \\
\vspace{5pt}
\hspace{48pt}$...$\\
\vspace{5pt}
\hspace{36pt}\textbf{Fin Para}\\
\vspace{10pt}
\end{flushleft}
}

Para el primer caso en la sentencia de decisión, la vectorización es inmediata: basta con acceder al buffer con los datos de entrada y cargar 4 \texttt{DWORDs} en cualquier registro \texttt{XMM}. Este proceso podrá repetirse unas 4 veces. A partir del elemento 16, entramos en la sección alternativa de la sentencia \textbf{Si}, y los elementos del vector $w$ se computan siguiendo la expresión más compleja, dependiente de cuatro elementos del previos: $w[i-3]$, $w[i-8]$, $w[i-4]$ y $w[i-16]$.

Veamos qué ocurre si pretendemos repetir el procedimiento anterior, procesando de forma simultánea los cuatro elementos $w[i]$, $w[i+1]$, $w[i+2]$ y $w[i+3]$:

\begin{itemize}
\item $w[i]$ requiere de: $w[i-3]$, $w[i-8]$, $w[i-14]$ y $w[i-16]$
\item $w[i+1]$ requiere de: $w[i-2]$, $w[i-7]$, $w[i-13]$ y $w[i-15]$
\item $w[i+2]$ requiere de: $w[i-1]$, $w[i-6]$, $w[i-12]$ y $w[i-14]$
\item $w[i+3]$ requiere de: $w[i]$, $w[i-5]$, $w[i-11]$ y $w[i-13]$
\end{itemize}

Como puede observarse, el problema es $w[i+3]$: este elemento requiere de $w[i]$, que se encuentra, al igual que el propio $w[i+3]$, en pleno proceso de cómputo en nuestro cálculo vectorizado.

Una posibilidad es reducir el cómputo vectorizado a los primeros 3 elementos $w[i]$, $w[i+1]$ y $w[i+2]$, y luego repetir el procedimiento para w[i+3] de forma individual, utilizando el ya calculado $w[i]$. Esta alternativa claramente es poco performante, ya que fuerza a la repetición del cómputo y perjudica la idea de la vectorización.

Afortunadamente, existe otra alternativa mucho más eficiente, que se basa en la siguiente propiedad:

\vspace{5pt}

\noindent \textbf{Propiedad}: \emph{Distributividad de la operación \emph{rotación} a nivel de bit.}

Sean:
\begin{itemize}
\item $A$ y $B$ dos valores binarios de igual longitud $n$ en bits.
\item $L$ un operador lógico binario cualquiera a nivel de bit.
\item $r$ un valor entero en el rango $0 \le r \le n$
\item $\hookleftarrow$ la operación \emph{rotación a izquierda} a nivel de bit.
\end{itemize}

Entonces:
\begin{displaymath}
L(A,B) \hookleftarrow r = L(A \hookleftarrow r, B \hookleftarrow r)
\end{displaymath}

\noindent \textbf{Demostración}:

Expresemos $A$ y $B$ a nivel de bit:
\begin{align*}
A &= a_{0}\ a_{1}\ a_{2}\ \ldots\ a_{n}\\
B &= b_{0}\ \ b_{1}\ b_{2}\ \ldots\ b_{n}
\end{align*}

donde $a_i$ y $b_j$ corresponden al bit $i-$ésimo y $j-$ésimo de $A$ y $B$, $0\le i,j \le n$, respectivamente.

Dado que $L$ es un operador lógico binario a nivel de bit, $L(A,B)$ puede escribirse como:
\begin{displaymath}
  L(A,B) = L(a_{0}, b_{0}) \ L(a_{1}, b_{1}) \ \ldots \ L(a_{n}, b_{n}) = \ c_{0} \ c_{1}  \ldots \ c_{n}
\end{displaymath}

Con lo cual:
\begin{equation}\label{eq1}
L(A,B) \hookleftarrow r = c_{r} \ c_{r+1} \ c_{r+2} \ \ldots \ c_{n} \ c_{0} \ c_{1} \ \ldots \ c_{r-1}
\end{equation}

Por otra parte:
\begin{equation}\label{eq2}
\begin{split}
L(A \hookleftarrow r, \ B \hookleftarrow r) = L(a_{r}\ a_{r+1} \ \ldots \ a_{n}\ a_{0}\ a_{1}\ \ldots \ a_{r-1}, \ b_{r}\ b_{r+1}\ \ldots \ b_{n}\ b_{0}\ b_{1}\ \ldots \ b_{r-1}) = \\
  = L(a_{r},b_{r}) \ L(a_{r+1},b_{r+1}) \ \ldots \ L(a_{n}, b_{n}) \ L(a_{0}, b_{0}) \ L(a_{1}, b_{1}) \ \ldots \ L(a_{r-1}, b_{r-1}) = \\
  = c_{r} \ c_{r+1} \ \ldots \ c_{n} \ c_{0} \ c_{1} \ \ldots c_{r-1}
\end{split}
\end{equation}

De donde resulta que $(\ref{eq1})$ y $(\ref{eq2})$ son iguales, como queríamos demostrar. $\blacksquare$

Volviendo a nuestro problema, la propiedad anterior posibilita reescribir la expresión:

\begin{center}
$w[i+3] = (w[i] \oplus w[i-5] \oplus w[i-11] \oplus w[i-13]) \hookleftarrow 1$
\end{center}

de la siguiente forma:

\begin{center}
$w[i+3] = (w[i] \hookleftarrow 1) \oplus \left((w[i-5] \oplus w[i-11] \oplus w[i-13]\right) \hookleftarrow 1)$
\end{center}

A su vez, la conmutatividad de la operación lógica $\oplus$ permite modificar el orden de los términos:

\begin{center}
$w[i+3] = \left((w[i-5] \oplus w[i-11] \oplus w[i-13]) \hookleftarrow 1 \right) \oplus (w[i] \hookleftarrow 1)$
\end{center}

Finalmente, aprovechamos la identidad:

\begin{displaymath}
A \oplus 0 = 0 \oplus  A = A
\end{displaymath}

Y reescribimos la expresión anterior como:

\begin{center}
$w[i+3] = \left[(0 \oplus w[i-5] \oplus w[i-11] \oplus w[i-13]) \hookleftarrow 1 \right] \oplus (w[i] \hookleftarrow 1)$
\end{center}

Con todo, podemos ahora realizar el cómputo los cuatro elementos $w[i]$, $w[i+1]$, $w[i+2]$ y el problemático $w[i+3]$ de forma simultánea, reemplazando al elemento $w[i]$ requerido y no disponible para el cómputo de $w[i+3]$ por el valor 0, y realizando un ajuste al final para completar el cómputo del $w[i+3]$. Este ajuste consiste en realizar una rotación a izquierda en un 1 bit sobre una copia del elemento $w[i]$ ya obtenido, y luego ejecutar la $\oplus$ entre este último y el $w[i+3]$ parcial para obtener el valor definitivo.

El siguiente esquema ilustra la propuesta. Cada grupo horizontal de elementos \texttt{w} puede ser almacenado en registros \texttt{XMM}, y las operaciones $\oplus$ sobre cada elemento se realizan fácilmente mediante la instrucción \texttt{PXOR} (los detalles se describen en la sección \ref{sha1_codigo}):

\begin{center}
{\tabulinesep=1.2mm
\begin{tabu}{|c|c|c|c|}
\hline
$w[i-3]$ & $w[i-2]$ & $w[i-1]$ & \textbf{0} \\
$\oplus$ & $\oplus$ & $\oplus$ & $\oplus$ \\
$w[i-8]$ & $w[i-7]$ & $w[i-6]$ & $w[i-5]$ \\
$\oplus$ & $\oplus$ & $\oplus$ & $\oplus$ \\
$w[i-14]$ & $w[i-13]$ & $w[i-12]$ & $w[i-11]$ \\
$\oplus$ & $\oplus$ & $\oplus$ & $\oplus$ \\
$w[i-16]$ & $w[i-15]$ & $w[i-14]$ & $w[i-13]$ \\
$\requals$ & $\requals$ & $\requals$ & $\requals$ \\
$w'[i]$ & $w'[i+1]$ & $w'[i+2]$ & $w'[i+3]$ \\
\hline
$\Downarrow$ & $\Downarrow$ & $\Downarrow$ & $\Downarrow$ \\
$(w'[i] \hookleftarrow 1)$ & $(w'[i+1] \hookleftarrow 1)$ & $(w'[i+2] \hookleftarrow 1)$ & $(w'[i+3] \hookleftarrow 1)$ \\
$\requals$ & $\requals$ & $\requals$ & $\requals$ \\
\textbf{w[i]} & \textbf{w[i+1]} & \textbf{w[i+2]} & $w''[i+3]$ \\
\hline
$\oplus$ & $\oplus$ & $\oplus$ & $\oplus$ \\
$0$ & $0$ & $0$ & (\textbf{w[i]} $\hookleftarrow 1$) \\
$\requals$ & $\requals$ & $\requals$ & $\requals$ \\
\hline
\textbf{w[i]} & \textbf{w[i+1]} & \textbf{w[i+2]} & \textbf{w[i+3]} \\
\hline
\end{tabu}}
\end{center}

\newpage
\subsubsection{Propiedad de \emph{Max Locktyukhin}}
Max Locktyukhin\footnote{Max Locktyukhin es un \emph{Software Performance Engineer} de la \emph{Intel Corp.}, especialista en procesos de optimización tanto a nivel de hardware como de software.}, ingeniero ruso de Intel, se ocupó del algoritmo SHA-1, y observó la siguiente propiedad:
\begin{quote}
El cómputo de la extensión de $w$ del algoritmo SHA-1, para toda ronda $i$, $i \geq 32$, puede calcularse como:
\begin{displaymath}
w[i] = (w[i-6] \oplus w[i-16] \oplus w[i-28] \oplus w[i-32]) \hookleftarrow 2
\end{displaymath}
\end{quote}

\noindent \textbf{Demostración}:

La demostración se basa en la siguiente idea:

\noindent \textbf{Propiedad}

Sean $a$ y $b$ dos valores enteros positivos cualesquiera, tales que $i-a \geq 0$ e $i-b \geq 0$.

Si:

% Reseteamos el contador de las ecuaciones.
\setcounter{equation}{0}

\begin{equation}
w[i] = w[i-a] \oplus w[i-b] \label{eq:ml_prop1_1}
\end{equation}

entonces:
\begin{equation}
w[i] = w[i-2a] \oplus w[i-2b] \label{eq:ml_prop1_2}
\end{equation}

\noindent \textbf{Demostración}:

Según $(\ref{eq:ml_prop1_1})$, $w[i-a]$ y $w[i-a]$ pueden obtenerse como:
\begin{equation}
w[i-a] = w[i-a-a] \oplus w[i-b-a] = w[i-2a] \oplus w[i-b-a]\label{eq:ml_eq1}
\end{equation}
\begin{equation}
w[i-b] = w[i-a-b] \oplus w[i-b-b] = w[i-a-b] \oplus w[i-2b]\label{eq:ml_eq2}
\end{equation}

Reemplazando $(\ref{eq:ml_eq1})$ y $(\ref{eq:ml_eq2})$ en $(\ref{eq:ml_prop1_1})$, resulta:
\begin{equation}
w[i] = (w[i-2a] \oplus w[i-b-a]) \oplus (w[i-a-b] \oplus w[i-2b])\label{eq:ml_eq3}
\end{equation}

Por la conmutatividad de la operación $\oplus$, podemos reacomodar los términos de $(\ref{eq:ml_eq3})$ de la siguiente forma:
\begin{equation}
w[i] = (w[i-2a] \oplus w[i-2b]) \oplus (w[i-b-a] \oplus w[i-a-b])\label{eq:ml_eq4}
\end{equation}

Se observa que el último paréntesis de $(\ref{eq:ml_eq4})$ vale 0, puesto que se trata de una $\oplus$ entre elementos iguales ($w[i-a-b]$). Con lo cual:
\begin{equation}
w[i] = (w[i-2a] \oplus w[i-2b]) \oplus 0 = w[i-2a] \oplus w[i-2b] \label{eq:ml_eq5}
\end{equation}

De donde puede verse que $(\ref{eq:ml_eq5})$ es igual a $(\ref{eq:ml_prop1_2})$, como queríamos demostrar. $\blacksquare$

\noindent \textbf{Lema}:

Sea $B$ un valor binario cualquiera de longitud $n$ en bits, y $r$ y $s$ dos enteros positivos tales que $0 \leq r,s \leq n$. Entonces, vale la identidad:
\begin{displaymath}
(B \hookleftarrow r) \hookleftarrow s = B \hookleftarrow (r + s)
\end{displaymath}

La demostración es trivial.
\newpage
\setcounter{equation}{0}
\noindent \textbf{Corolario}:

Sea:
\begin{equation}
w[i] = (w[i-a] \oplus w[i-b]) \hookleftarrow r \label{eq:corolario_1}
\end{equation}

Entonces:
\begin{equation}
  w[i] = (w[i-2a] \oplus w[i-2b]) \hookleftarrow 2r \label{eq:corolario_2}
\end{equation}

\noindent \textbf{Demostración}:
\begin{equation}
  w[i-a] = (w[i-2a] \oplus w[i-b-a]) \hookleftarrow r \label{eq:corolario_3}
\end{equation}
\begin{equation}
  w[i-b] = (w[i-a-b] \oplus w[i-2b]) \hookleftarrow r \label{eq:corolario_4}
\end{equation}

Reemplazando $(\ref{eq:corolario_3})$ y $(\ref{eq:corolario_4})$ en $(\ref{eq:corolario_1})$:
\begin{displaymath}
w[i] = (((w[i-2a] \oplus w[i-b-a]) \hookleftarrow r) \oplus ((w[i-a-b] \oplus w[i-2b])) \hookleftarrow r)) \hookleftarrow r
\end{displaymath}

Por la propiedad de distributividad de la operación de rotación:
\begin{displaymath}
w[i] = (((w[i-2a] \oplus w[i-b-a]) \oplus (w[i-a-b] \oplus w[i-2b])) \hookleftarrow r) \hookleftarrow r
\end{displaymath}

Aplicando el \emph{Lema 1} y la conmutatividad de la operación $\oplus$:
\begin{displaymath}
w[i] = ((w[i-2a] \oplus w[i-2b]) \oplus (w[i-a-b] \oplus w[i-b-a])) \hookleftarrow r + r = (w[i-2a] \oplus w[i-2b]) \hookleftarrow 2r
\end{displaymath}

como queríamos demostrar. $\blacksquare$

De esta forma, extendiendo el corolario anterior al caso de 4 elementos $w$ en lugar de 2, la propiedad de Max Locktyukhin se demuestra de forma inmediata.

La propiedad de Max Locktyukhin permite, ahora sí, el procesamiento simultáneo de 4 elementos del vector $w$ sin operaciones adicionales. Tiene la desventaja, sin embargo, de que funciona para valores de índice $i \ge 32$, dado que el elemento más chico del cual depende es $w[i-32]$.

Este inconveniente de alguna forma se ve compensado por una situación bastante afortunada: los elementos $w[i-16]$, $w[i-28]$ y $w[i-32]$ quedan alineados correctamente para el caso del procesamiento vectorizado en registros \texttt{XMM}. El elemento $w[i-6]$ es el único que requiere ser reubicado en el registro, pero existen instrucciones que realizan esa operación (los detalles se describen en la sección \ref{sha1_implementacion}, \emph{Instrucciones SSSE3 especiales}).

\subsection{Resumen de la estrategia de vectorización del algoritmo \emph{SHA-1}}
Del análisis anterior del algoritmo SHA-1, resultó que solo el procesamiento del vector $w$, denominado \emph{Message Schedule}, está libre de circularidades y dependencias especiales que impidan la posibilidad de vectorización.

Apuntamos, por tanto, a esta etapa, y como resultado del análisis y de las disintas propiedades lógicas que hemos visto, encontramos 3 situaciones que dan lugar al procesamiento paralelo:

\begin{enumerate}
\item Rondas 0 a 15:
\begin{itemize}
\item El proceso es inmediato.
\item Basta con cargar 16 bytes en algún registro \texttt{XMM} directo del buffer con los datos.
\item Esos 16 bytes corresponden a 4 elementos \texttt{DWORD} del vector $w$.
\end{itemize}

\item Rondas 16 a 31:
\begin{itemize}
\item A partir de la ronda 16 comienza el cómputo complejo de los elementos del vector $w$.
\item Por las características del cálculo, donde el elemento más adelantado depende del primero en el mismo proceso de cómputo, el tratamiento vectorizado capaz de procesar 4 elementos de forma simultánea debe, en principio, acotarse a solo 3.
\item Sin embargo, diversas propiedades lógicas mostraron que es posible avanzar con el cómputo vectorizado de los 4 elementos hasta la última operación.
\item En ese momento, el valor requerido por el elemento más adelantado es reemplazado por un valor neutro en el marco de la operación lógica en cuestión.
\item Producto de este truco, se obtienen los primeros tres elementos vectorizados, y con ajuste de bajo de costo, es posible obtener el restante.
\end{itemize}
\item Rondas 32 a 79:
\begin{itemize}
\item La propiedad de \emph{Max Locktyukhin}, permite el procesamiento vectorizado de todos elementos del vector $w$ sin inconveniente.
\end{itemize}
\end{enumerate}

\subsection{Detalles de la implementación del algoritmo SHA-1 vectorizado}\label{sha1_implementacion}
A continuación se describen las ideas más importantes incluidas en la implementación de nuestra versión vectorizada del algoritmo SHA-1. Los detalles específicos a nivel de código se detallan en la sección \ref{sha1_codigo}.

\begin{enumerate}
\item \emph{Loop unrolling} y \emph{software pipelining}:

Todos los algoritmos en este trabajo han sido implementados siguiendo la técnica del \emph{loop unrolling}, y adicionalmente en el caso vectorizado, el \emph{pipelining}, que se describen en la sección \ref{sha1_codigo}. Como se explicó, el objetivo es favorecer la performance evitando el \emph{overhead} asociado a las instrucciones requeridas en el chequeo de las condiciones de los ciclos. En el caso de nuestra implementación, desplegaremos el ciclo \texttt{for} anidado, que se desplaza en el rango 0 a 79. De modo que cada una de las 80 rondas se computan secuencialmente. Además, el \emph{software pipelining} se implementa con un \emph{prólogo} y \emph{epílogo} que procesan 16 elementos del vector $w$. Tal como se explicará en la sección correspondiente, esto es posible gracias a las macros.

\vspace{5pt}
\item Vector $w$ almacenado en búffer circular que emplea registros \texttt{XMM}:

El vector $w$ es de uso frecuente en el cómputo del valor del hash SHA-1. Resultaría muy conveniente mantenerlo de alguna forma en registros del CPU, en lugar de la memoria. En principio, no disponemos de registros suficientes para almacenarlo completamente, dada su extensión de 80 elementos \texttt{DWORDs}.

Sin embargo, no es necesario mantener la totalidad de sus elementos en memoria: de los análisis previos observamos que la dependencia más lejana para un $w[i]$ determinado, es $w[i-32]$, situación que aparece en la propiedad de Max Locktyukhin. De modo que para toda ronda basta con almacenar los 32 elementos de $w$ precedentes. Con esa idea, implementamos un buffer circular compuesto por 8 registros \texttt{XMM}:

\begin{verbatim}
  XMM0 =    w[i] |  w[i+1] |  w[i+2] |  w[i+3] -> W0
  XMM1 =  w[i+4] |  w[i+5] |  w[i+6] |  w[i+7] -> W1
  XMM2 =  w[i+8] |  w[i+9] | w[i+10] | w[i+11] -> W2
  XMM3 = w[i+12] | w[i+12] | w[i+13] | w[i+14] -> W3
  XMM4 = w[i+16] | w[i+17] | w[i+18] | w[i+19] -> W4
  XMM5 = w[i+20] | w[i+21] | w[i+22] | w[i+23] -> W5
  XMM6 = w[i+24] | w[i+25] | w[i+26] | w[i+27] -> W6
  XMM7 = w[i+28] | w[i+29] | w[i+30] | w[i+31] -> W7
\end{verbatim}

Las cotas del buffer están dadas por los elementos $w[i] ... w[i+31]$. Esta es precisamente la distancia de dependencia más grande entre dos elementos de w, en las fórmulas vectorizadas que analizamos en las secciones anteriores.

El buffer es circular porque los elementos a partir de $w[i+32]$ se almacenan comenzando desde el principio, sobreescribiendo los valores anteriores.
\newpage
\item Cómputo de $w+k$:

La participación de los elementos de $w$ en el cómputo del valor de hash SHA-1 aparece en el cálculo de una de las variables de estado del algoritmo:
\begin{displaymath}
aux = (a \hookleftarrow 5) + f + e + k + w[i]
\end{displaymath}
Notemos que el valor de $k$ es uno de cuatro constantes predefinidas, que se selecciona según el número de ronda:
\begin{flushleft}
\hspace{24pt}Rondas  0 a 19: \hspace{2pt} $k = k0 = $ \texttt{0x5A827999} \\
\hspace{24pt}Rondas 20 a 39: $k = k1 = $ \texttt{0x6ED9EBA1} \\
\hspace{24pt}Rondas 40 a 59: $k = k2 = $ \texttt{0x8F1BBCDC} \\
\hspace{24pt}Rondas 60 a 79: $k = k3 = $ \texttt{0xCA62C1D6} \\
\end{flushleft}

Es fácil ver que el $k$ asociado a cualquier grupo de elementos $w[i]$, $w[i+1]$, $w[i+2]$ y $w[i+3]$ en el cómputo vectorizado es siempre el mismo para los cuatro:

\begin{tabular}{cccccccc}
$w[0] \rightarrow k0$ & ... & $w[16] \rightarrow k0$ & $w[20] \rightarrow k2$ & ... & $w[40] \rightarrow k3$ & ... & $w[76] \rightarrow k4$ \\
$w[1] \rightarrow k0$ & ... & $w[17] \rightarrow k0$ & $w[21] \rightarrow k2$ & ... & $w[41] \rightarrow k3$ & ... & $w[77] \rightarrow k4$ \\
$w[2] \rightarrow k0$ & ... & $w[18] \rightarrow k0$ & $w[22] \rightarrow k2$ & ... & $w[42] \rightarrow k3$ & ... & $w[78] \rightarrow k4$ \\
$w[3] \rightarrow k0$ & ... & $w[19] \rightarrow k0$ & $w[23] \rightarrow k2$ & ... & $w[43] \rightarrow k3$ & ... & $w[79] \rightarrow k4$ \\
\end{tabular}

Con todo, resulta conveniente aprovechar esta propiedad y realizar la suma también de forma vectorizada. Almacenaremos para ello las constantes $k$ en otros cuatro registros \texttt{XMM}:

\begin{verbatim}
  XMM8  = 0x5A827999 | 0x5A827999 | 0x5A827999 | 0x5A827999 -> K0
  XMM9  = 0x6ED9EBA1 | 0x6ED9EBA1 | 0x6ED9EBA1 | 0x6ED9EBA1 -> K1
  XMM10 = 0x8F1BBCDC | 0x8F1BBCDC | 0x8F1BBCDC | 0x8F1BBCDC -> K2
  XMM11 = 0xCA62C1D6 | 0xCA62C1D6 | 0xCA62C1D6 | 0xCA62C1D6 -> K3
\end{verbatim}

\vspace{5pt}
\item Vector del hash y variables de estado en registros:

Tanto el vector $h$ donde se computa el valor de hash SHA-1, como las 5 variables de estado $a$, $b$, $c$, $d$ y $e$, también son de uso frecuente. De modo que para favorecer la performance los almacenamos en registros escalares. La sección \ref{sha1_codigo} muestra los detalles.

\vspace{5pt}
\item Optimización del proceso de actualización de las variables de estado:

En la sección \ref{sha1_vectorizacion} comprobamos que el proceso de actualización de las variables de estado $a$, $b$, $c$, $d$, y $e$ no puede vectorizarse debido a una dependencia circular que existe entre ellas. Sin embargo, esa circularidad da lugar a otra forma de optimización.

Repasemos las operaciones en el proceso de actualización de estas variables:
\begin{align*}
&aux = (a \hookleftarrow 5) + f + e + k + w[i] \\
&e = d \\
&d = c \\
&c = b \hookleftarrow 30 \\
&b = a \\
&a = aux \\
\end{align*}
La implementación más inmediata de este proceso consistiría, en primer lugar, del cómputo de la variable $aux$, para luego copiar el valor de $d$ en $e$, el de $c$ en $d$, etc. Es decir, existe un overhead importante producto del movimiento de datos entre las variables.

Sin embargo, ese overhead no es necesario: basta con aplicar las operaciones sobre las variables que sí se ven modificadas, y luego reinterpretarlas a todas como si hubieran sido rotadas (esto es, la variable $a$ pasa a interpretarse como $b$, la variable $b$ como $c$, y así sucesivamente). Veamos con más detalle esta idea:
\newpage
\begin{itemize}
\item Ronda 0:

Solo modificamos las variables $b$ y $e$:
\begin{align*}
&b =  b \hookleftarrow 30 \\
&e \mathrel{+}= (a \hookleftarrow 5) +  f + e + k + w[i]
\end{align*}

\item Ronda 1:

Reinterpretamos el orden de las variables:
\begin{center}
$a$ ahora es la que antes era $e$ \\
$b$ ahora es la que antes era $a$ \\
$c$ ahora es la que antes era $b$ \\
$d$ ahora es la que antes era $c$ \\
$e$ ahora es la que antes era $d$ \\
\end{center}

Con lo cual, la actualización ahora es:
\begin{align*}
&a = a \hookleftarrow 30 \\
&d \mathrel{+}= (e \hookleftarrow 5) + ...
\end{align*}

\item  Ronda 2:
\begin{center}
$a$ ahora es la que antes era $d$ \\
$b$ ahora es la que antes era $e$ \\
$c$ ahora es la que antes era $a$ \\
$d$ ahora es la que antes era $b$ \\
$e$ ahora es la que antes era $c$ \\
\end{center}

La actualización ahora es:
\begin{align*}
&e = e \hookleftarrow 30 \\
&c \mathrel{+}= (d \hookleftarrow 5) + ...
\end{align*}
\end{itemize}

y así sucesivamente. Como resultado, el código de actualización de las variables se simplifica considerablemente. De modo que en la implementación, como veremos, la macro que se ocupa de este proceso computa de a dos rondas por vez, en lugar de una, para que este proceso no se vuelva demasiado atómico.

\item \emph{Interleaving} o entrelazado:

Cuando en la sección \ref{sha1_vectorizacion} analizamos las posibilidades de vectorización del algoritmo SHA-1, encontramos dos partes o etapas bien diferenciadas: el procesamiento del vector $w$, y la actualización de las variables de estado (que son las que, en definitiva, generan el valor de hash).

Vimos que la segunda depende de la primera, dado que para cualquier ronda $i$ la segunda etapa requiere del elemento $w[i]$. Vimos además que la segunda etapa no puede vectorizarse debido a una dependencia circular que existe entre sus variables.

Como consecuencia, la segunda etapa solo puede avanzar de a un paso a la vez vez, mientras que la primera puede hacerlo de a cuatro, producto de la vectorización.

Esta situación fuerza algún tipo de coordinación entre el avance de una y otra etapa. El objetivo es evitar que el cómputo de los elementos de $w$ se adelante lo suficiente como para sobreescribir un elemento aun no consumido por la segunda etapa.

Son varias las alternativas para coordinar este avance: computar 4 elementos de $w$, consumir 4, computar otros 4 $w$, etc.; computar los 32 $w$, consumir los 32, computar otros 32, etc.

Sin embargo, existe otra estrategia que, si bien es más compleja, no solo da lugar a un esquema de coordinación mucho más homogéneo, sino que también favorece considerablemente el interleaving o entrelazado entre las instrucciones escalares e instrucciones \emph{SIMD}: se trata de la partición del cómputo vectorizado en cuatro fases, donde cada fase quedará determinada por el número de ronda.

Es importante destacar que, a partir de esta idea, el número de ronda cumple dos funciones en el marco del cómputo vectorizado: sirve como discriminante entre las tres formas de cómputo del vector $w$ (copia directa (rondas 0 a 15), computo cuasi-vectorizado (rondas 16 a 31); cómputo vectorizado (\emph{Max Locktyukhin}) (rondas 32 a 79)), y además funciona como selector de una de las cuatro fases en el proceso de cálculo.

Veamos, entonces, cómo se desarrolla el cómputo vectorizado de $w$ para las primeras 8 rondas:
\begin{itemize}
\item[-] Ronda 0: fase 0 del cómputo vectorizado de $w[0]$, $w[1]$, $w[2]$ y $w[3]$.
\item[-] Ronda 1: fase 1 del cómputo vectorizado de $w[0]$, $w[1]$, $w[2]$ y $w[3]$.
\item[-] Ronda 2: fase 2 del cómputo vectorizado de $w[0]$, $w[1]$, $w[2]$ y $w[3]$.
\item[-] Ronda 3: fase 3 del cómputo vectorizado de $w[0]$, $w[1]$, $w[2]$ y $w[3]$ (completado).

\vspace{12pt}
El registro \texttt{XMM0}, alias \texttt{W0}, incluye ahora el valor de $w[0]$, $w[1]$, $w[2]$ y $w[3]$.
\vspace{12pt}
\item[-] Ronda 4: fase 0 del cómputo vectorizado de w[4], w[5], w[6] y w[7].
\item[-] Ronda 5: fase 1 del cómputo vectorizado de w[4], w[5], w[6] y w[7].
\item[-] Ronda 6: fase 2 del cómputo vectorizado de w[4], w[5], w[6] y w[7].
\item[-] Ronda 7: fase 3 del cómputo vectorizado de w[4], w[5], w[6] y w[7] (completado).

\vspace{12pt}
El registro \texttt{XMM1}, alias \texttt{W1}, incluye ahora el valor de $w[4]$, $w[5]$, $w[6]$ y $w[7]$.

\hspace{24pt} ...
\end{itemize}

Como podemos observar, este esquema requiere que el cómputo vectorizado se inicie lo suficientemente antes que el cómputo escalar que actualiza las variables de estado, de manera tal que al iniciar este último ya existan elementos de $w$ calculados. En la sección \ref{sha1_codigo} veremos que en la implementación del algoritmo SHA-1 vectorizado nos adelantamos al cómputo escalar tanto como los primeros 16 elementos del vector $w$ (aquellos que obtenemos directamente del buffer), como resultado de la aplicación del \emph{software pipelining}.

\vspace{5pt}
\item Instrucciones \emph{SSSE3} especiales.

Se describen a continuación dos instrucciones incluidas en la extensión SSSE3 que resultan de especial utilidad para la implementación del cómputo vectorizado, como así también la desventaja de no contar con una instrucción que permita realizar una rotación empaquetada, y el modo en que solventamos el problema.

\begin{itemize}
\item Instrucción \texttt{PSHUFB}

Hemos visto que los datos para los primeros 16 elementos del vector $w$ (rondas 0 a 15) se obtienen directamente desde el buffer. En nuestro caso vectorizado, cargamos de 4 DWORDs de forma simultánea en un registro XMM, mediante una instrucción como la siguiente:

\begin{verbatim}
  MOVDQU XMM0, [BUFFER_PTR]
\end{verbatim}

Ocurre que la lectura directa del buffer acarrea un inconveniente: los bytes en el buffer figuran de manera secuencial siguiendo el mismo orden original que tenían en el archivo. Podemos decir, por lo tanto, que el contenido del archivo se carga en memoria en formato 'Big-Endian': el byte menos significativo se ubica en la posición más baja de memoria, mientras que el más significativo en la más alta. Veamos un ejemplo:

Sea \texttt{BUFFER\_PTR} un puntero a datos en memoria:
\begin{verbatim}
    ...

  BUFFER_PTR:      0x00
  BUFFER_PTR + 1:  0x01
  BUFFER_PTR + 2:  0x02
  BUFFER_PTR + 3:  0x03
    ...

  BUFFER_PTR + 13: 0x0D
  BUFFER_PTR + 14: 0x0E
  BUFFER_PTR + 15: 0x0F
\end{verbatim}
Sea la instrucción:
\begin{verbatim}
  MOVDQU XMM0, [BUFFER_PTR]
\end{verbatim}
El contenido del registro XMM0 es exactamente el siguiente:
\begin{verbatim}
  XMM0: 0x00010203 | 0x04050607 | 0x08090A0B | 0x0C0D0E0F
\end{verbatim}
Cada \texttt{DWORD} figura en formato \emph{Big-Endian}, cuando en realidad la arquitectura Intel representa los valores en formato \emph{Little-endian} (el byte más significativo se ubica en la posición más baja, mientras que el menos significativo en la más alta).

Afortunadamente, la extensión SSSE3 incluye la instrucción \texttt{PSHUFB}. \texttt{PSHUFB} ejecuta un \emph{shuffling} o reordenamiento empaquetado a nivel de byte especialmente útil en situaciones como estas.

Trabaja con dos operandos: un registro \texttt{XMM} sobre el cual llevará a cabo el reordenamiento, y otro registro \texttt{XMM} (o una posición de memoria) donde se especifica la reubicación de cada byte del primero.

Para comprender la mecánica de esta instrucción, consideramos que cada byte de un registro \texttt{XMM} se enumera de izquierda a derecha, y de 0 a 7. Entonces, la constante de reubicación debería ser la siguiente:
\begin{verbatim}
  little_endian_bytes_shuffling_values DB 0x03, 0x02, 0x01, 0x00,\
					  0x07, 0x06, 0x05, 0x04,\
					  0x0b, 0x0a, 0x09, 0x08,\
					  0x0f, 0x0e, 0x0d, 0x0c
\end{verbatim}

Esta constante establece tiene el siguiente efecto: el byte en la posición 0 (el primero) en el registro \texttt{XMM}, lo reubica al byte en la posición 3; el byte en la posición 1 lo reubica a la posición 2, y así sucesivamente.

Con lo cual, retomando el ejemplo anterior, debería incluirse la siguiente instrucción para reubicar los \texttt{DWORDs} en formato Little-endian:
\begin{verbatim}
  PSHUFB XMM0, [little_endian_bytes_shuffling_values]
\end{verbatim}
El formato de cada valor DWORD ahora es el correcto:
\begin{verbatim}
  XMM0: 0x03020100 | 0x07060504 | 0x0B0A0908 | 0x0F0D0E0C
\end{verbatim}
El resultado es que convertimos 4 \texttt{DWORDs} en \emph{Little-endian} empleando una sola instrucción.

\vspace{5pt}
\item Instrucción \texttt{PALIGNR}

En la sección \ref{sha1_vectorizacion} vimos que el cómputo vectorizado complejo de $w$ se divide en dos partes: la primera, abarca las rondas 16 a 31, y ejecuta el cómputo siguiendo la definición original del algoritmo SHA-1:
\begin{displaymath}
w[i] = \left(w[i-3] \oplus w[i-8] \oplus w[i-14] \oplus w[i-16]\right) \hookleftarrow 1
\end{displaymath}

la segunda, abarca las rondas 32 a 79, y opera con la expresión de \emph{Max Locktyukhin}:
\begin{displaymath}
w[i] = (w[i-6] \oplus w[i-16] \oplus w[i-28] \oplus w[i-32]) \hookleftarrow 2
\end{displaymath}

Teniendo en cuenta que el vector $w$ es almacenado en el buffer descrito en el ítem 2 anterior, donde cada registro \texttt{XMM} del buffer almacena cuatro elementos de $w$, comenzando siempre por índices múltiplo de 4, encontraremos la dificultad de que los elementos $w[i]$ no quedan correctamente alineadas en los cómputos paralelos. Veamos como ejemplo el segundo caso, y consideremos el cómputo vectorizado en la ronda 32:

Nos interesa obtener $w[32]$, $w[33]$, $w[34]$, $w[35]$:

\vspace{12pt}
\begin{flushleft}
\hspace{62pt}$w[32]$\quad$w[33]$\quad$w[34]$\quad$w[35]$\hspace{8pt}$\leftarrow w[i]$ \\
\hspace{24pt}\texttt{XMM0}: \hspace{12pt}$w[0]$\hspace{13pt}$w[1]$\hspace{16pt}$w[2]$\hspace{15pt}$w[3]$\hspace{13pt}$\leftarrow w[i-32]$ \\
\hspace{24pt}\texttt{XMM1}: \hspace{12pt}$w[4]$\hspace{13pt}$w[5]$\hspace{16pt}$w[6]$\hspace{15pt}$w[7]$\hspace{13pt}$\leftarrow w[i-28]$ \\
\hspace{100pt}...\\
\hspace{24pt}\texttt{XMM4}: \quad$w[16]$\quad$w[17]$\quad$w[18]$\quad$w[19]$\quad$\leftarrow w[i-16]$ \\
\hspace{100pt}...\\
\hspace{24pt}\texttt{XMM6}: \quad$w[24]$\quad$w[25]$\quad$w[26]$\quad$w[27]$ \\
\hspace{24pt}\texttt{XMM7}: \quad$w[28]$\quad$w[29]$\quad$w[30]$\quad$w[31]$
\end{flushleft}
\vspace{12pt}

Observamos que tres de los cuatro términos en el cómputo paralelo quedan perfectamente alineados: $w[i-32]$, $w[i-28]$ y $w[i-16]$. El término restante, $w[i-6]$, se encuentra, en cambio, repartido entre los registros \texttt{XMM6}, y \texttt{XMM7}. En concreto, necesitamos almacenar en algún registro \texttt{XMM} auxiliar lo siguiente:

\begin{flushleft}
\hspace{24pt}$w[26]$\quad$w[27]$\quad$w[28]$\quad$w[29]$\quad$\leftarrow w[i-6]$
\end{flushleft}

Podemos obtener este resultado mediante copias de los registos \texttt{XMM6} y \texttt{XMM7}, seguido por desplazamientos a derecha y a izquierda, y una operación lógica como la \texttt{XOR}. Sin embargo, la extensión \emph{SSSE3} incluye la instrucción \texttt{PALIGNR}, que realiza esta operación en un solo paso. \texttt{PALIGNR} requiere de 3 operandos: dos registros \texttt{XMM}, y un valor inmediato que indica el número de bytes que se desplaza un puntero ficticio a derecha. Veamos cómo funcionaría en el caso de nuestro ejemplo:

\begin{verbatim}
  MOVDQU  XMM10, XMM6     ; Hacemos una copia del registro XMM6
	                          ; para no destruir el buffer.

  PALIGNR XMM10, XMM7, 8  ; XMM10 = w[26]  w[27]  w[28]  w[29]
\end{verbatim}
\vspace{12pt}
\texttt{PALIGNR} opera así:

\begin{enumerate}
\item Concatena los registros \texttt{XMM10} y \texttt{XMM7}:

\begin{displaymath}
  w[24] \hspace{10pt} w[25] \hspace{5pt} w[26] \hspace{5pt} w[27] \hspace{5pt} w[28] \hspace{5pt} w[29]  \hspace{5pt} w[30] \hspace{5pt} w[31]
\end{displaymath}

\item Considera al elemento de la izquierda ($w[24]$) como el primero, y se desplaza a la derecha tantos bytes como lo indique el tercer operando. En nuestro caso, el tercer operando vale 8. Si tenemos en cuenta que cada $w[i]$ es un \texttt{DWORD} (es decir, tienen longitud de 4 bytes), el resultado es que el el puntero ficticio se desplaza al elemento $w[26]$:

\begin{displaymath}
  w[24] \hspace{5pt} w[25] \hspace{5pt} \underset{\uparrow}{w[26]} \hspace{5pt} w[27] \hspace{5pt} w[28] \hspace{5pt} w[29] \hspace{5pt} w[30] \hspace{5pt} w[31]
\end{displaymath}

\item Finalmente, la operación extrae los 16 bytes siguientes a partir del puntero ficticio, y los copia en el registro \texttt{XMM} de destino (en nuestro caso, \texttt{XMM10}).
\begin{displaymath}
\texttt{XMM10} = w[26] \hspace{5pt} w[27] \hspace{5pt} w[28] \hspace{5pt} w[29]
\end{displaymath}
\end{enumerate}

\item Ausencia de instrucciones de rotación empaquetada.

Lamentablemente la extensión SSSE3 no incluye una instrucción que permita ejecutar rotaciones empaquetadas sobre los registros SIMD, operación requerida como último paso en la obtención de los $w$. Sin embargo, la siguiente identidad nos permitirá emularla:

Sea $A$ un valor binario de longitud n en bits, y $r$ un valor entero, $0 \leq r \leq n$. Entonces:

\begin{displaymath}
A \hookleftarrow r = \left(A \ll r) \vee (A \gg (n - r)\right)
\end{displaymath}
o también:
\begin{displaymath}
A \hookleftarrow r = \left(A \ll r) \oplus (A \gg (n - r)\right)
\end{displaymath}
Al igual que las anteriores, la demostración es inmediata, operando a nivel de bit. De forma análoga, se prueba el caso para la rotación a derecha.

De manera que empleando desplazamientos a izquierda y derecha, y la operación lógica \texttt{OR} (o alternativamente \texttt{XOR}), podemos ejecutar una operación de rotación.

Como ejemplo, supongamos que debemos rotar a izquierda en 20 bits a cada \texttt{DWORD} (32 bits) empaquetado en el registro \texttt{XMM0}. El procedimiento es el siguiente:
\begin{verbatim}
  MODQU XMM1, XMM0
  PSLLD XMM0, 20
  PSRLD XMM1, 12    ; 12 = 32 - 20
  POR   XMM0, XMM1
\end{verbatim}
\end{itemize}
\end{enumerate}

\subsection{Análisis del código}\label{sha1_codigo}

Habiendo descripto las estrategias para la vectorización del algoritmo SHA-1, los detalles relativos a la  implementación de estas ideas, las técnicas algorítmicas incluidas que favorecen la performance, las características especiales de la extensión SSSE3, el modo en que resolvemos algunos inconvenientes, pasamos ahora al análisis del código ensamblador del módulo que implementa el cómputo vectorizado del algoritmo, incluyendo los comentarios que correspondan para facilitar su comprensión en el código:

\begin{itemize}
\item Vector de hash \texttt{H} y variables de estado \texttt{A}, \texttt{B}, \texttt{C}, \texttt{D}, y \texttt{E} en registros:
\begin{verbatim}
  %xdefine H0 RDX
  %xdefine H1 RDX + 4
  %xdefine H2 RDX + 8
  %xdefine H3 RDX + 12
  %xdefine H4 RDX + 16

    ...

  %xdefine A R11D
  %xdefine B R12D
  %xdefine C R13D
  %xdefine D R14D
  %xdefine E R15D
\end{verbatim}

\item Buffer circular para el vector $w$:
\begin{verbatim}
  %xdefine W0 XMM0  ; w[i]    | w[i+1] | w[i+2] | w[i+3]
  %xdefine W1 XMM1  ; w[i+4]  |       ...       | w[i+7]
  %xdefine W2 XMM2  ; w[i+8]  |       ...       | w[i+11]
  %xdefine W3 XMM3  ; w[i+12] |       ...       | w[i+15]
  %xdefine W4 XMM4  ; w[i+16] |       ...       | w[i+19]
  %xdefine W5 XMM5  ; w[i+20] |       ...       | w[i+23]
  %xdefine W6 XMM6  ; w[i+24] |       ...       | w[i+27]
  %xdefine W7 XMM7  ; w[i+28] |       ...       | w[i+31]
\end{verbatim}

\item Constantes $k$ también almacenadas en registros \texttt{XMM}:
\begin{verbatim}
  %xdefine K0 XMM8
  %xdefine K1 XMM9
  %xdefine K2 XMM10
  %xdefine K3 XMM11

    ...

  k1 DD 0x5A827999, 0x5A827999, 0x5A827999, 0x5A827999
  k2 DD 0x6ED9EBA1, 0x6ED9EBA1, 0x6ED9EBA1, 0x6ED9EBA1
  k3 DD 0x8F1BBCDC, 0x8F1BBCDC, 0x8F1BBCDC, 0x8F1BBCDC
  k4 DD 0xCA62C1D6, 0xCA62C1D6, 0xCA62C1D6, 0xCA62C1D6

    ...

  MOVDQU K0, [k1]
  MOVDQU K1, [k2]
  MOVDQU K2, [k3]
  MOVDQU K3, [k4]
\end{verbatim}

\item Macro para la actualización de las variables de estado: actualiza las variables de estado $a$, $b$, $c$, $d$ y $e$ para dos rondas consecutivas:
\begin{verbatim}
  %macro UPDATE_ABCDE 6

    ;
    ; Rondas 0 a 19
    %if (%1 <= 19)
       %xdefine F F1
    ;
    ; Rondas 20 a 39
    %elif (%1 <= 39)
      %xdefine F F2

      ...

    %endif

      ...

    ;
    ; Actualizamos la variable 'E', que en la próxima ronda será
    ; 'A'.
    ;
    ; E = E + f + ROTATE_LEFT(A, 5) + w[i] + k
    ;
    MOV EBX, %2          ; EBX = A1
    ADD %6, EAX          ; E1  = E1 + f
    ROL EBX, 5           ; EBX = ROTATE_LEFT(A1, 5)
    ADD %6, [wk + 4*%1]  ; E1  = E1 + f + ROTATE_LEFT(A1, 5) + w[i] + k
    ADD %6, EBX          ; E1  = E1 + f + ROTATE_LEFT(A1, 5)

      ...

  %endmacro
\end{verbatim}

\item Macros para el cómputo del vector $w$ y $w+k$:
\begin{verbatim}
  ;
  ; Parámetros:
  ;
  ; %1: número de ronda (solo válida para i = 0..15).
  ; %2: dirección del buffer.
  ;
  %macro CALCULATE_WK 2

    %if (%1 < 16)
      CALCULATE_WK_FOR_ROUNDS_0_TO_15 %1, %2
    %elif (%1 < 32)
      CALCULATE_WK_FOR_ROUNDS_16_TO_31 %1
    %elif (%1 < 80)
      CALCULATE_WK_FOR_ROUNDS_32_TO_79 %1
    %endif

  %endmacro

    ...
\end{verbatim}

\newpage
\begin{verbatim}
    ...

  ;
  ; Parámetros:
  ;
  ; %1: número de ronda (solo válida para i = 0..15).
  ; %2: dirección del buffer.
  ;
  %macro CALCULATE_WK_FOR_ROUNDS_0_TO_15 2

    ;
    ; Aplicamos una 'and' al índice 'i'. Esto nos permitirá
    ; distinguir el número de etapa.
    %assign i (%1 & 3)

    ;
    ; Etapa 1: rondas 0, 4, 8, 12. Simplemente leemos del buffer.
    ;
    %if (i == 0)
	        ...

    %elif (i == 1)
	        ...

      PSHUFB W, LITTLE_ENDIAN_BYTES_SHUFFLING
	        ...

    %endif
	        ...

  %endmacro

  ;
  ; Parámetro:
  ;
  ; %1: número de ronda.
  ;
  %macro CALCULATE_WK_FOR_ROUNDS_16_TO_31 1
    ...

  %endmacro

  ;
  ; Parámetro:
  ;
  ; %1: dirección del buffer con los datos.
  ;
  %macro CALCULATE_WK_FOR_ROUNDS_32_TO_79 1
      ...

    MOVDQU  XMM_AUX0, W_MINUS_4     ; XMM_AUX0 = w[i-1] | ... | w[i-4]
    PALIGNR XMM_AUX0, W_MINUS_8, 8  ; XMM_AUX0 = w[i-3] | ... | w[i-6]

    PXOR W, XMM_AUX0 ; W = ...| w[i-32] XOR w[i-28] XOR w[i-16] XOR w[i-6]

      ...

  %endmacro
\end{verbatim}
\newpage
\item Entrada del programa:

Notemos el \emph{prólogo} del \emph{software pipelining}, en el que se procesan los primeros 16 elementos del vector $w$, el \emph{despliegue} del ciclo (\emph{loop unrolling}) combinado con el entrelazado entre las macros \texttt{CALCULATE\_WK} y \texttt{UPDATE\_ABCDE}, y el \emph{epílogo} del \emph{software pipelining} que involucra únicamente a la macro \texttt{UPDATE\_ABCDE} hacia el final.

\begin{verbatim}
    ...

  ;
  ; Calculamos por adelantado 16 elementos del vector W (64
  ; bytes).
  CALCULATE_WK 0, BUFFER_PTR
  CALCULATE_WK 1, BUFFER_PTR
  CALCULATE_WK 2, BUFFER_PTR
  CALCULATE_WK 3, BUFFER_PTR  ; Obtenemos W0: w[0] | w[1] | w[2] | w[3]

    ...

  CALCULATE_WK 12, BUFFER_PTR
  CALCULATE_WK 13, BUFFER_PTR
  CALCULATE_WK 14, BUFFER_PTR
  CALCULATE_WK 15, BUFFER_PTR ; Obtenemos W3: w[12] | ... | w[15]

    ...

  ;
  ; Ciclo del algoritmo desplegado (loop unrolling).
  ;
  loop:

    CALCULATE_WK 16, BUFFER_PTR
    UPDATE_ABCDE 0,  A, B, C, D, E
    CALCULATE_WK 17, BUFFER_PTR

    CALCULATE_WK 18, BUFFER_PTR
    UPDATE_ABCDE 2,  D, E, A, B, C
    CALCULATE_WK 19, BUFFER_PTR     ; Obtenemos w[16] ... w[19].

    CALCULATE_WK 20, BUFFER_PTR
    UPDATE_ABCDE 4,  B, C, D, E, A
    CALCULATE_WK 21, BUFFER_PTR

    CALCULATE_WK 22, BUFFER_PTR
    UPDATE_ABCDE 6,  E, A, B, C, D
    CALCULATE_WK 23, BUFFER_PTR     ; Obtenemos w[20] ... w[23].

      ...

    ;
    ; Cómputo de cierre.
    ;
    UPDATE_ABCDE 64, B, C, D, E, A
    UPDATE_ABCDE 66, E, A, B, C, D
    UPDATE_ABCDE 68, C, D, E, A, B
    UPDATE_ABCDE 70, A, B, C, D, E
    UPDATE_ABCDE 72, D, E, A, B, C
    UPDATE_ABCDE 74, B, C, D, E, A
    UPDATE_ABCDE 76, E, A, B, C, D
    UPDATE_ABCDE 78, C, D, E, A, B

		      ...
\end{verbatim}
\end{itemize}

Notemos que la rotación de las variables de estado cada vez que se invoca a la macro \texttt{UPDATE\_ABCDE} se efectúa en saltos de a dos elementos. Como se explicó en secciones anteriores, esto se debe a que la macro \texttt{UPDATE\_ABCDE} actualiza el valor de las variables para dos rondas consecutivas.

\subsection{Experiencia y resultados}
La experiencia sobre el algoritmo de hash SHA-1 consistió en la contrastación de la performance de la versión vectorizada que obtuvimos, frente a dos versiones escalares: la primera, también en \emph{ensamblador}; la segunda, en lenguaje \emph{C}. Estas últimas se caracterizan por el procesamiento de un elemento por vez en cada iteración (esto es, un elemento del vector $w$, seguido por una ronda que actualiza las variables de estado). Sin embargo, tanto una como otra emplea la técnicas de optimización del \emph{Loop Unrolling}, como así también todas las optimizaciones escalares posibles (como por ejemplo, la rotación de las variables de estado (véase sección \ref{sha1_implementacion}, \emph{Optimización del proceso de actualización...}). De modo que el objetivo en este trabajo también incluyó la optimización de las versiones escalares de los algoritmos estudiados.

Las pruebas para evaluar la performance de cada implementación consistieron en la medición del tiempo de CPU de la ejecución de cada una de las tres versión sobre un grupo de 6 archivos. El tamaño de estos archivos varía en el rango de $0.5$ a $3.0$ \emph{GB}, en saltos de $0.5$ \emph{GB}. Sobre cada archivo, cada implementación se ejecutó media docena de veces, y de todas ellas se computó el promedio.

El gráfico de la figura \ref{fig:sha1_1} muestra los resultados de la experiencia.

\begin{figure}[!ht]
\centering
\includegraphics[scale=0.80]{img/sha1_simd_vs_asm_vs_c_3gb.png}
\caption{SHA-1 - \emph{SIMD} vs \emph{ASM} vs \emph{C}}\label{fig:sha1_1}
\end{figure}

\newpage
El análisis de los datos produjo los siguientes resultados:
\begin{itemize}

\item La versión escalar \emph{ASM} resultó un $11.5\%$ más rápida que la versión escalar en \emph{C}.
\item La versión vectorizada \emph{SIMD} resultó un $29.6\%$ más rápida que la versión escalar en \emph{ASM}.
\item La versión vectorizada \emph{SIMD} resultó ser $37.4\%$ más rápida que la versión escalar en \emph{C}.
\end{itemize}

\subsection{Conclusión}
Es importante volver a recordar ahora que SHA-1 no es un algoritmo diseñado para la paralelización. Por el contrario, la vectorización que obtuvimos es, de hecho, parcial, y fue el resultado de un análisis pormenorizado de las partes que componen este algoritmo, proceso durante el cual buscamos todos los elementos posibles susceptibles a la operatoria \emph{SIMD}.

En este marco, afirmar que la implementación cuasi-vectorizada superó a la escalar -también optimizada- en un $30\%$, resulta un logro muy considerable. Pensemos, por ejemplo, que lo que a la versión escalar en ensamblador le llevaría 5 minutos, la versión vectorizada lo resuelve en $3,5$, lo que significa una diferencia importante.

Por todo esto, consideramos el resultado obtenido como \emph{muy satisfactorio}.

Respecto a los resultados de las versiones escalares, \emph{ASM} vs \emph{C}, ambas optimizadas por igual, y considerando que la compilación realizada incluyó el máximo nivel de optimización para el caso de \emph{C} (opción \texttt{-O3} de \texttt{gcc}), encontramos que la pequeña diferencia de casi el $12\%$ en favor de la versión en ensamblador resulta razonable. Fundamentalmente porque, exceptuando las diferencias del lenguaje, las dos implementaciones son esencialmente idénticas en cuanto a la estructura y a las operaciones realizadas.
