\section{Algoritmo de hash \emph{SHA-256}}\label{sha256}
\subsection{Descripción}
\emph{SHA-2} es una familia de algoritmos que incluye a los algoritmos SHA-224, SHA-256, SHA-384 y SHA-512. Se tratan de funciones de hash que reciben un conjunto de datos de cualquier longitud, y devuelve un valor de hash de 224, 256, 384 y 512 bits, respectivamente.

SHA-256 es el algoritmo que hemos seleccionado para realizar la segunda experiencia de contrastación entre la versión escalar y una vectorizada.

La estructura del algoritmo SHA-256 es exactamente igual que la del algoritmo SHA-1, lo que nos permitirá simplificar considerablemente las descripciones. Sin embargo, diferen notablemente en el cómputo de sus elementos. A continuación se listan las similitudes y diferencias entre uno y otro:

\begin{itemize}
\item \textbf{Similitudes de SHA-256 con SHA-1}:
\begin{itemize}
\item[-] Recibe como entrada cualquier conjunto de datos.
\item[-] Está definido a nivel de bit, pero a los efectos de este trabajo, donde los datos de entrada lo contituyen los archivos, trabajaremos a nivel de byte.
\item[-] Realiza exactamente el mismo proceso de padding que en SHA-1 sobre los datos de entrada.
\item[-] Tiene la misma estructura de ciclos.
\item[-] Parte los datos de entrada, inmediatamente después del padding, en bloques de 64 bytes, los cuales procesa de forma secuencial.
\item[-] El procesamiento de cada bloque de 64 bytes tiene como resultado la actualización del valor de hash, y consiste en:
\begin{enumerate}
\item Copiar directamente los 16 \texttt{DWORDs} que componen al bloque en los primeros 16 elementos del vector $w$ (\emph{Message Schedule}).
\item Realizar cómputos que extienden la cantidad de elementos del vector $w$.
\item Utilizar el valor del elemento $w$ de la ronda actual, junto al valor de una constante $k$, para actualizar variables de estado.
\item Actualizar las variables de estado en sentido circular.
\item Actualizar el valor de hash.
\end{enumerate}
\end{itemize}

\vspace{5pt}
\item \textbf{Diferencias de SHA-256 con SHA-1}:
\begin{itemize}
\item[-] El valor de hash es de mayor longitud: lo conforma un vector de 8 \texttt{DWORDs}.
\item[-] Las rondas van de 0 a 63, y no de 0 a 79 como en SHA-1.
\item[-] El vector $w$, por lo tanto, se extiende a 63 elementos.
\item[-] El cómputo de los elementos extendidos de $w$ es bastante más complejo.
\item[-] Son 64 las constantes\footnote{Estas constantes $k$ se obtienen de la siguiente manera: se tratan de los primeros 32 bits de la parte decimal de la raíz cúbica de los primeros 64 números primos (es decir, los números primos en el rango 2 a 311, incluyendo a ambas cotas). Por ejemplo, en el caso de 2, el primero de estos valores, procedemos así: computamos la raíz cúbica de 2, conservamos únicamente la parte decimal, y empezamos a convertirla a binario hasta completar un total de 32 bits. Finalmente, convertimos ese valor en hexadecimal. Comprobaremos que el resultado es \texttt{0x428A2F98}} $k$: una asociada a cada $w[i]$, con $0 \leq i \leq 63$.
\item[-] Las variables de estado ahora son 8: $a$, $b$, $c$, $d$, $e$, $f$, $g$ y $h$.
\item[-] La actualización de las variables de estado utiliza a otras variables auxiliares previas, cuyo cómputo también tiene una complejidad importante.
\end{itemize}
\end{itemize}

El \emph{fips-180} describe al algoritmo SHA-256 siguiendo la misma estructura que a SHA-1. Eso implica la inclusión de ciclos anidados inncesarios. Por ese motivo, el pseudocódigo que sigue constituye la versión pulida del algoritmo SHA-256:

\newpage
{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{12pt}\textbf{Función} \texttt{SHA-256} \\
\vspace{3pt}
\hspace{18pt}\textbf{- Entrada}: conjunto de datos $m$ de cualquier longitud en bytes\\
\hspace{18pt}\textbf{- Salida}: vector $hash[8]$ de \texttt{DWORD} con el valor del hash SHA-256\\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Variables locales. \\
\hspace{24pt}// \\
\hspace{24pt}$hash[8]$: vector de  8 \texttt{DWORDs} \hspace{6pt} // Valor de hash.  \\
\vspace{2pt}
\hspace{24pt}$w[63]$: \hspace{9pt}vector de 80 \texttt{DWORDs} \hspace{2pt} // Vector \emph{Message Schedule}. \\
\vspace{2pt}
\hspace{24pt}$a, \ b, \ c, \ d, \ e, \ f, \ g, \ h$: \texttt{DWORD} \hspace{1pt} // Variables de estado. \\
\vspace{2pt}
\hspace{24pt}$k[63]$: vector de \texttt{DWORD} \hspace{32pt} // Vector para las constantes $k$. \\
\vspace{2pt}
\hspace{24pt}$s0, \ s1$: \texttt{DWORD} \hspace{69pt} // Variables auxiliares para el cómputo de $w$. \\
\vspace{2pt}
\hspace{24pt}$S0, \ S1$, maj, ch: \texttt{DWORD} \hspace{26pt} // Variables auxiliares para la actualización \\
\vspace{2pt}
\hspace{24pt}$temp1, temp2:$ \hspace{5pt} \texttt{DWORD} \hspace{27pt} // de las variables de estado. \\
\vspace{10pt}
\hspace{24pt}$k = $\{\texttt{0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5,} \\
\hspace{45pt}\texttt{0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,} \\
\hspace{45pt}\texttt{0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3,} \\
\hspace{45pt}\texttt{0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,} \\
\hspace{45pt}\texttt{0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC,} \\
\hspace{45pt}\texttt{0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,} \\
\hspace{45pt}\texttt{0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7,} \\
\hspace{45pt}\texttt{0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,} \\
\hspace{45pt}\texttt{0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13,} \\
\hspace{45pt}\texttt{0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,} \\
\hspace{45pt}\texttt{0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3,} \\
\hspace{45pt}\texttt{0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,} \\
\hspace{45pt}\texttt{0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5,} \\
\hspace{45pt}\texttt{0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,} \\
\hspace{45pt}\texttt{0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208,} \\
\hspace{45pt}\texttt{0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2}\} \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Inicialización del vector $hash$. \\
\hspace{24pt}// \\
\hspace{24pt}$hash[0] = $\texttt{0x6A09E667} \\
\hspace{24pt}$hash[1] = $\texttt{0xBB67AE85} \\
\hspace{24pt}$hash[2] = $\texttt{0x3C6EF372} \\
\hspace{24pt}$hash[3] = $\texttt{0xA54FF53A} \\
\hspace{24pt}$hash[4] = $\texttt{0x510E527F} \\
\hspace{24pt}$hash[5] = $\texttt{0x9B05688C} \\
\hspace{24pt}$hash[6] = $\texttt{0x1F83D9AB} \\
\hspace{24pt}$hash[7] = $\texttt{0x5BE0CD19} \\
\vspace{10pt}
\hspace{24pt}// \\
\hspace{24pt}// Padding o relleno. Después del padding, los datos de entrada \\
\hspace{24pt}// $m$ se extenderán en algunos bytes, y su tamaño total será \\
\hspace{24pt}// múltiplo de 64 bits. \\
\hspace{24pt}// \\
\hspace{24pt}$m = $\texttt{Padding}$(m)$ \\
\vspace{10pt}
\newpage
\hspace{24pt}// \\
\hspace{24pt}// Procesamiento de cada bloque de 64 bytes de los datos de \\
\hspace{24pt}// 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 = hash[0]$ \\
\hspace{36pt}$b = hash[1]$ \\
\hspace{36pt}$c = hash[2]$ \\
\hspace{36pt}$d = hash[3]$ \\
\hspace{36pt}$e = hash[4]$ \\
\hspace{36pt}$f = hash[5]$ \\
\hspace{36pt}$g = hash[6]$ \\
\hspace{36pt}$h = hash[7]$ \\
\vspace{10pt}
\hspace{36pt}\textbf{Para} $i = 0$ hasta 63, \textbf{hacer} \\
\vspace{5pt}
\hspace{48pt}// \\
\hspace{48pt}// Procesamiento del vector $w$ (\emph{Message Schedule}). \\
\hspace{48pt}// \\
\hspace{48pt}\textbf{Si} $(i < 16)$ \textbf{entonces} \\
\vspace{2pt}
\hspace{60pt}$w[i] = b[i]$ \\
\vspace{3pt}
\hspace{48pt}\textbf{Sino} \\
\vspace{2pt}
\hspace{60pt}$s0 = (w[i-15] \hookrightarrow 7) \oplus (w[i-15] \hookrightarrow 18) \oplus (w[i-15] \gg 3)$ \\
\hspace{60pt}$s1 = (w[i-2] \hookrightarrow 17) \oplus (w[i-2] \hookrightarrow 19) \oplus (w[i-2] \gg 10)$ \\
\hspace{60pt}$w[i] = w[i-16] + s0 + w[i-7] + s1$ \\
\vspace{3pt}
\hspace{48pt}\textbf{Fin Si} \\
\vspace{10pt}
\hspace{48pt}// \\
\hspace{48pt}// Actualización de las variables de estado $a$, $b$, $c$, \\
\hspace{48pt}// $d$, $f$, $g$ y $h$. \\
\hspace{48pt}// \\
\hspace{48pt}$S1 = (e \hookrightarrow 6) \oplus (e \hookrightarrow 11) \oplus (e \hookrightarrow 25)$ \\
\vspace{2pt}
\hspace{48pt}$ch = (e \wedge f) \oplus ((\neg e) \wedge g)$ \\
\vspace{2pt}
\hspace{48pt}$temp1 = h + S1 + ch + k[i] + w[i]$ \\
\vspace{2pt}
\hspace{48pt}$S0 = (a \hookrightarrow 2) \oplus (a \hookrightarrow 13) \oplus (a \hookrightarrow 22)$ \\
\vspace{2pt}
\hspace{48pt}$maj = (a \wedge b) \oplus (a \wedge c) \oplus (b \wedge c)$ \\
\vspace{2pt}
\hspace{48pt}$temp2 = S0 + maj$ \\
\vspace{10pt}
\hspace{48pt}$h = g$ \\
\vspace{2pt}
\hspace{48pt}$g = f$ \\
\vspace{2pt}
\hspace{48pt}$f = e$ \\
\vspace{2pt}
\hspace{48pt}$e = d + temp1$ \\
\vspace{2pt}
\hspace{48pt}$d = c$ \\
\vspace{2pt}
\hspace{48pt}$c = b$ \\
\vspace{2pt}
\hspace{48pt}$b = a$ \\
\vspace{2pt}
\hspace{48pt}$a = temp1 + temp2$ \\
\vspace{5pt}
\hspace{36pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{36pt}// \\
\hspace{36pt}// Actualización del valor de hash. \\
\hspace{36pt}// \\
\hspace{36pt}$hash[0] = hash[0] + a$ \\
\vspace{2pt}
\hspace{36pt}$hash[1] = hash[1] + b$ \\
\vspace{2pt}
\hspace{36pt}$hash[2] = hash[2] + c$ \\
\vspace{2pt}
\hspace{36pt}$hash[3] = hash[3] + d$ \\
\vspace{2pt}
\hspace{36pt}$hash[4] = hash[4] + e$ \\
\vspace{2pt}
\hspace{36pt}$hash[5] = hash[5] + f$ \\
\vspace{2pt}
\hspace{36pt}$hash[6] = hash[6] + g$ \\
\vspace{2pt}
\hspace{36pt}$hash[7] = hash[7] + h$ \\
\vspace{5pt}
\hspace{24pt}\textbf{Fin Para} \\
\vspace{10pt}
\hspace{24pt}\textbf{Devolver} $hash$ \\
\vspace{10pt}
\hspace{12pt}\textbf{Fin Función} \\
\end{flushleft}
}

\subsection{Análisis del algoritmo SHA-256 y estrategia de vectorización}

De la experiencia previa con el algoritmo SHA-1, sabemos que no hay vectorización posible sobre las variables de estado, dada la dependencia circular que existe entre ellas. De modo que el foco lo ponemos, una vez más, en el procesamiento del vector $w$, que en SHA-256 se computa de la siguiente forma:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{48pt}\textbf{Si} $(i < 16)$ \textbf{entonces} \\
\vspace{2pt}
\hspace{60pt}$w[i] = b[i]$ \\
\vspace{3pt}
\hspace{48pt}\textbf{Sino} \\
\vspace{2pt}
\hspace{60pt}$s0 = (w[i-15] \hookrightarrow 7) \oplus (w[i-15] \hookrightarrow 18) \oplus (w[i-15] \gg 3)$ \\
\hspace{60pt}$s1 = (w[i-2] \hookrightarrow 17) \oplus (w[i-2] \hookrightarrow 19) \oplus (w[i-2] \gg 10)$ \\
\hspace{60pt}$w[i] = w[i-16] + s0 + w[i-7] + s1$ \\
\vspace{3pt}
\hspace{48pt}\textbf{Fin Si} \\
\end{flushleft}
}

El objetivo es computar en paralelo los elementos $w[i]$, $w[i+1]$, $w[i+2]$ y $w[i+3]$. Ya vimos que el caso de $0 \leq i < 16$ es trivial. Basta con acceder al buffer y copiar de 4 \texttt{DWORDs} de forma simultánea en algún registro \texttt{XMM}. Veamos lo que ocurre para el cómputo extendido.

En concreto, $w[i]$ depende de los elementos previos $w[i-15]$ (en $s0$), $w[i-2]$ (en $s1$), y $w[i-16]$ y $w[i-7]$. Es fácil ver que el obstáculo para una vectorización inmediata se encuentra en s1: se define en términos de $w[i-2]$, cuya proximidad con $w[i]$ impide el procesamiento de 4 elementos simultáneos, puesto que el cómputo de los $w$ más adelantados, $w[i+2]$ y $w[i+3]$, requieren, respectivamente, de $w[i]$ y $w[i+1]$, que forman parte del mismo proceso de cálculo vectorizado y, por lo tanto, no existen aún.

A diferencia del algoritmo SHA-1, para el que encontramos soluciones simples, claras y directas frente al mismo problema, veremos a continuación que, en el caso del algoritmo SHA-256, esta situación lamentablemente es insalvable. La prueba es muy sencilla:

En primer lugar, debemos persuadirnos de que la expresión de $w[i]$ no puede simplificarse. La razón de esto es que $w[i]$ se define en términos de una suma de varios elementos de $w$ anteriores, en lugar de una operación $\oplus$ como era el caso de SHA-1. No existe, por lo tanto, la posibilidad de anular términos en sustituciones sucesivas. Por el contrario, las sustituciones expanden considerablemente la expresión, incorporando varios nuevos elementos en cada reemplazo.

De modo que la única forma de computar $w[i-2]$ es sencillamente aplicando la definición anterior, resultando:
\begin{align*}
  &s0 = (w[i-17] \hookrightarrow 7) \oplus (w[i-17] \hookrightarrow 18) \oplus (w[i-17] \gg 3) \\
  &s1 = (w[i-4] \hookrightarrow 17) \oplus (w[i-4] \hookrightarrow 19) \oplus (w[i-4] \gg 10) \\
  &w[i-2] = w[i-18] + s0 + w[i-9] + s1
\end{align*}

Como resultado, duplicamos el cómputo que estamos intentado vectorizar, puesto que el cálculo anterior debemos repetirlo para los otros tres elementos: $w[i+1]$, $w[i+2]$ y $w[i+3]$.

Teniendo en cuenta lo anterior, la estrategia más conveniente resulta ser aquella que aplicamos en el algoritmo SHA-1, durante la vectorización de la primera extensión de $w$ (rondas 16 a 31). Esta idea consistía simplemente en realizar el cómputo simultáneo de los cuatro elementos $w[i]$, $w[i+1]$, $w[i+2]$ y $w[i+3]$, hasta el punto en que los dos más adelantados no pueden continuar debido al problema de las dependencias. A partir de allí, completábamos el cálculo de los dos primeros y, una vez obtenidos, los utilizábamos para finalizar el cálculo parcial de los dos restantes.

En nuestro caso, el cómputo simultáneo de $w[i]$, $w[i+1]$, $w[i+2]$ y $w[i+3]$ abarcará la obtención del $s0$ de cada uno, y la suma parcial $w[i]' = w[i-16] + s0 + w[i-7]$, que no incluye a $s1$. A partir de allí, calculamos los $s1$ asociados a los dos primeros, y con ellos completamos la suma parcial que produce finalmente a $w[i]$ y $w[i+1]$. Por último, empleamos los recién calculados $w[i]$ y $w[i+1]$ para generar los s1 asociados a $w[i+2]$ y $w[i+3]$, y con ellos completamos la suma parcial que finalmente los genera.

El resultado es que solo duplicamos el cómputo de s1, a lo que se le agrega una suma adicional. Esto es por lejos mucho más conveniente que duplicar la totalidad del cómputo de la extensión de $w$. Esta será, por lo tanto, la rebuscada estrategia que utilizaremos para intentar vectorizar este segundo algoritmo de hashing.

\subsection{Detalles de la implementación del algoritmo SHA-256 vectorizado}

\subsubsection{Operaciones de rotación}

Como puede observarse del pseudocódigo descripto en la sección \ref{sha256}, el algoritmo SHA-256 utiliza la operación de rotación (a derecha) con mucha frecuencia en sus expresiones. Tanto en aquellas que intentamos vectorizar, y que involucra al vector $w$, como en las operaciones escalares que emplean a las variables de estado y auxiliares.

Ya hemos mencionado que la extensión SSSE3 no cuenta con ninguna instrucción que realice rotaciones empaquetada sobre los registros SIMD. Sin embargo, vimos que podemos emularla combinando desplazamientos a izquierda y derecha empaquetados, y operaciones \texttt{OR} o \texttt{XOR}.

Veamos, por ejemplo, el caso de $s0$:
\begin{displaymath}
s0 = (w[i-15] \hookrightarrow 7) \oplus (w[i-15] \hookrightarrow 18) \oplus (w[i-15] \gg 3)
\end{displaymath}

Operemos sobre la expresión y reemplacemos las rotaciones con la combinación de desplazamiento y operaciones $\oplus$:
\begin{displaymath}
s0 = [(w[i-15] \gg 7) \oplus (w[i-15] \ll 25)] \oplus [(w[i-15] \gg 18) \oplus (w[i-15] \ll 14)] \oplus (w[i-15] \gg 3)
\end{displaymath}

Los términos no solo casi se duplican, sino que, además, el cómputo de esa expresión implica un \emph{overhead} muy importante solo en copias intermedias de $w[i-15]$.

Existe una propiedad análoga a la presentada en \ref{sha1_vectorizacion} (\emph{Distributividad de la operación rotación..}), solo que ahora la aplicaremos para las operaciones de desplazamiento a izquierda y derecha, y que nos permitirá reducir el número de copias de $w[i-15]$ a solo dos:

\noindent \textbf{Propiedad}:

Sean $A$ y $B$ dos valores binarios cualesquiera de longitud $n$ en bits, y $r$ y $s$ dos enteros, $0 \leq r, s \leq n$, con $r \leq s$. Entonces:
\begin{displaymath}
(A \ll r) \oplus (B \ll s) = \left[\left(A \oplus (B \ll (s-r)\right)\right] \ll r
\end{displaymath}

La demostración es inmediata, y se obtiene operando a nivel de bit sobre cada lado de la igualdad.

Retomando la expresión de $s0$, si reacomodamos los términos y aplicamos la propiedad, resulta:

\begin{align*}
s0 = &[(w[i-15] \ll 14) \oplus (w[i-15] \ll 25)] \oplus \\
\oplus &[(w[i-15] \ll 7) \oplus (w[i-15] \gg 18) \oplus (w[i-15] \gg 3)] = \\ \\
= &[(w[i-15] \oplus (w[i-15] \ll 11)) \ll 14] \oplus \\
\oplus &[((w[i-15] \oplus (w[i-15] \gg 18)) \gg 7) \oplus (w[i-15] \gg 3)] = \\ \\
= &[(w[i-15] \oplus (w[i-15] \ll 11)) \ll 14] \oplus \\ 
\oplus &[(((w[i-15] \oplus (w[i-15] \gg 18)) \gg 4) \oplus w[i-15]) \gg 3] \ \blacksquare\\
\end{align*}

Como puede observarse, y a pesar de la falsa mala apariencia que podría generar la extensión de la nueva expresión, ahora solo necesitaremos dos copias de $w[i-15]$: la primera, para computar $w[i-15] \ll 11$, y la segunda, para hacer lo propio con $w[i-15] \gg 18$. Con estos dos valores, y el original $w[i-15]$, podemos obtener cada término encerrado entre corchetes, para luego completar el cálculo con la operación $\oplus$.

Por ejemplo, en el caso de la expresión entre corchetes del lado derecho, deberíamos hacer lo siguiente:
\begin{enumerate}
\item Hacer una copia de $w[i-15]$.
\item Sobre esa copia, hacer $w[i-15] \gg 18$.
\item Computar una \texttt{XOR} sobre la copia ya modificada, y el $w[i-15]$ original.
\item Desplazar ese resultado a derecha 4 bits.
\item Aplicar al resultado una \texttt{XOR} utilizando nuevamente a $w[i-15]$ como segundo operando.
\item Aplicar sobre el resultado otro desplazamiento a derecha en 3 bits.
\end{enumerate}

Notemos que solo empleamos una copia del elemento $w[i-15]$.

Este método lo aplicamos tanto en el cómputo vectorizado, como en el cómputo escalar que actualiza a las variables de estado.

\subsubsection{Otras optimizaciones}
La implementación vectorizada del algoritmo SHA-256 incluye todas las optimizaciones aplicadas en el caso de SHA-1, que son:

\begin{enumerate}
\item \emph{Loop unrolling} y \emph{software pipelining}: la situación es análoga al caso de SHA-1: desplegamos las 63 rondas asociadas al procesamiento de cada bloque de 64 bytes y calculamos por adelantado los 16 primeros elementos del vector $w$, utilizando macros.

\item Vector $w$ almacenado en búffer circular que emplea registros \texttt{XMM}: el vector $w$ se alamcena en registros \texttt{XMM} para evitar el acceso a memoria. A diferencia de SHA-1, este buffer es mucho más reducido, puesto que la dependencia más lejana entre los elementos de $w$ se da con $w[i-16]$. Serán necesarios, por lo tanto, 4 registros \texttt{XMM} para implementar el buffer circular. La sección \ref{sha256_codigo} describe los detalles.

\item Cómputo de $w+k$: al igual que en SHA-1, en el algoritmo SHA-256 cada w calculado se utiliza en una suma que involucra una constante $k$. Esta suma parcial se utiliza para actualizar el valor de una de las variables auxiliares. Por ese motivo, esta operación también se vectoriza.

\item Vector del hash y variables de estado en registros: con fines de optimización, el vector con el valor de hash y las variables de estado se almacenan en registros.

\item Optimización del proceso de actualización de las variables de estado: las rotamos repitiendo la idea aplicada sobre las variables de estado del algoritmo SHA-1 (véase sección \ref{sha1_implementacion}, \emph{Optimización del proceso de actualización...}). De esta forma, evitamos un número considerable de copias innecesarias de los datos.

\item \emph{Interleaving} o entrelazado: nuevamente, dividimos el cómputo vectorizado en 4 etapas, con el objeto de intercalarlo con el cálculo escalar, y de esta forma favorecer la \emph{ejecución fuera de orden}.
\end{enumerate}

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

A continuación describimos cómo y dónde se implementa en el código en esamblador para el módulo vectorizado, cada uno de los aspectos detallados en secciones anteriores:

\begin{itemize}
\item Vector de hash $Hx$, donde $x$ es un valor entre 0 y 7, y variables de estado $A$, $B$, $C$, $D$, $E$, $F$, $G$ y $H$ se almacenan en registros:
\begin{verbatim}
  %xdefine H0 RDX
  %xdefine H1 RDX + 4
  %xdefine H2 RDX + 8
  %xdefine H3 RDX + 12
  %xdefine H4 RDX + 16
  %xdefine H5 RDX + 20
  %xdefine H6 RDX + 24
  %xdefine H7 RDX + 28

    ...

  %xdefine A R8D
  %xdefine B R9D
  %xdefine C R10D
  %xdefine D R11D
  %xdefine E R12D
  %xdefine F R13D
  %xdefine G R14D
  %xdefine H R15D
\end{verbatim}

\item Buffer circular para el vector w y para $w+k$:
\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 WK0 XMM4  ; w[i]    + k[i]    |     ...     | w[i+3]  + k[i+3]
  %xdefine WK1 XMM5  ; w[i+4]  + k[i+4]  |     ...     | w[i+7]  + k[i+7]
  %xdefine WK2 XMM6  ; w[i+8]  + k[i+8]  |     ...     | w[i+11] + k[i+11]
  %xdefine WK3 XMM7  ; w[i+12] + k[i+12] |     ...     | w[i+15] + k[i+15]
\end{verbatim}
\newpage
\item Constantes $k$ en memoria:

El algoritmo SHA-256 emplea 64 constantes $k$ asociadas a cada $w[i]$, $0 \leq i \leq 63$. No disponemos de suficientes registros \texttt{XMM} libres, por lo que estas constantes se almacenan en memoria, y se recuperan luego en la suma vectorizada.
\begin{verbatim}
  k DD 0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B,\
       0x59F111F1, 0x923F82A4, 0xAB1C5ED5, 0xD807AA98, 0x12835B01,\
       0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7,\
       0xC19BF174, 0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC,\
       0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA, 0x983E5152,\
       0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147,\
       0x06CA6351, 0x14292967, 0x27B70A85, 0x2E1B2138, 0x4D2C6DFC,\
       0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,\
       0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819,\
       0xD6990624, 0xF40E3585, 0x106AA070, 0x19A4C116, 0x1E376C08,\
       0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F,\
       0x682E6FF3, 0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208,\
       0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2
\end{verbatim}

\item Macro para la actualización de las variables de estado:
\begin{verbatim}
  %macro UPDATE_ABCDEFGH 9
    %assign s (%1 & 12)/4  ; Selector del elemento WK del 
                           ; buffer (WK0, WK1, WK2, WK3).
    %assign i (%1 & 3)     ; Selector del elemento DWORD
                           ;en el WK anterior.
    %if   (s == 0)
      %xdefine WK WK0
      
    %elif (s == 1)
      %xdefine WK WK1
      
      ...
      
    %endif
    
      ...
      
    ;
    ; Obtenemos 'S1':
    ;
    ;  S1 = ROTATE_RIGHT(E, 6)^ROTATE_RIGHT(E, 11)^ROTATE_RIGHT(E, 25)
    ;
    ; Que puede escribirse:
    ;
    ;  S1 = ROTATE_RIGHT(E^ROTATE_RIGHT(E XOR ROTATE_RIGHT(E, 14), 5), 6)
    ;
    MOV EBX, %6  ; EBX = E
    ROR EBX, 14
    XOR EBX, %6
    ROR EBX, 5
    XOR EBX, %6
    ROR EBX, 6   ; EBX = S1    
      ...
    
  %endmacro
\end{verbatim}
\newpage
\item Macros para el cómputo del vector $w$ y $w+k$:
\begin{verbatim}
  ;
  ; Esta macro centraliza las llamadas a las otras macros que
  ; calculan los elementos del vector WK de forma vectorizada.
  %macro CALCULATE_WK 2

    %if (%1 < 16)
    CALCULATE_WK_FOR_ROUNDS_0_TO_15 %1, %2
    %else
      CALCULATE_WK_FOR_ROUNDS_16_TO_63 %1
    %endif

  %endmacro

    ...
    
  ;
  ; 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)
    
      ...
      
    %else
      MOVDQU WK, [k + (%1 - 3)*4] ; WK = k[i] | ... | k[i+3]
      PADDD  WK, W                ; WK = k[i] + w[i] | ... 
        ...
    %endif

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

    ;
    ; Selector. Nos permitirá movernos de forma circular por los
    ; búfferes W  (w0, w1, w2 y w3) y WK (WK0, WK1, WK2 y WK3).
    %assign s (%1 & 12)/4

    ;
    ; Etapa 1: rondas 16, 20, 24, 28, 32, ... 60
    ;
    %if (i == 0)
    
      ...

    %endif
    
      ...
    ;
    ; s0 = [(w[i-15] XOR (w[i-15] << 11) << 14] XOR
    ;      XOR  [(((w[i-15] XOR (w[i-15] >> 11)) >> 4) XOR w[i-15]) >> 3]
    ;
    MOVDQU  XMM_AUX1, W_MINUS_12      ; XMM_AUX1 = w[i-9]  | ... | w[i-12]
    PALIGNR XMM_AUX1, W_MINUS_16, 4   ; XMM_AUX1 = w[i-12] | ... | w[i-15]
    
      ...
  %endmacro
\end{verbatim}
- Entrada del programa:
\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:

  UPDATE_ABCDEFGH 0,  A, B, C, D, E, F, G, H
  CALCULATE_WK 16, BUFFER_PTR

  UPDATE_ABCDEFGH 1,  H, A, B, C, D, E, F, G
  CALCULATE_WK 17, BUFFER_PTR

  UPDATE_ABCDEFGH 2,  G, H, A, B, C, D, E, F
  CALCULATE_WK 18, BUFFER_PTR

  UPDATE_ABCDEFGH 3,  F, G, H, A, B, C, D, E
  CALCULATE_WK 19, BUFFER_PTR     ; Obtenemos w[16], w[17], w[18] y w[19].
  
    ...
\end{verbatim}
\end{itemize}

Notemos que, a diferencia de SHA-1, la rotación de las variables de estado se realiza en saltos de a un elemento. Esto es así porque el proceso de actualización de estas variables en SHA-256 es mucho más complejo, e involucra un número importante de operaciones. No es necesario, por lo tanto, realizar un procesamiento extendido que sume más instrucciones escalares que favorezcan el \emph{interleaving}.

\subsection{Experiencia y resultados}
En esta segunda experiencia repetimos la idea de evaluar la performance de nuestra versión cuasi-vectorizada del algoritmo SHA-256 con una versión escalar. Sin embargo, en esta oportunidad prescindimos de la versión en \emph{C}, y solo empleamos la versión escalar en ensamblador (\emph{ASM}). Como ya ha sido mencionado en reiteradas oportunidades, la versión escalar incluye todas las optimización posibles.

Las pruebas son exactamente las mismas que las efectuadas para la experiencia del algoritmo SHA-1: media docena de ejecuciones repetidas, empleando cada una de las implementaciones, sobre 6 archivos de datos, que van desde $0.5$ \emph{GB} a los $3.0$ \emph{GB}, en saltos de $0.5$ \emph{GB}. Sobre el total de ejecuciones de cada versión, sobre cada archivo, computamos el promedio. La figura \ref{fig:sha256_1} ilustra el resultado de la experiencia.

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

Del análisis de los datos, se desprende que la versión vectorizada \emph{SIMD} resultó, en promedio, un $8.85\%$ más rápida que la escalar en ensamblador. Es decir, no llega al $10\%$.

\subsection{Conclusión}
A diferencia de lo ocurrido en la experiencia con el algoritmo SHA-1, los resultados obtenidos en el proceso de cuasi-vectorización del algoritmo SHA-256 son bastante pobres. Y esto es algo que, a decir verdad, se anunciaba conforme avanzábamos con el análisis de cada componente de este algoritmo.

La naturaleza compleja de sus expresiones, la insalvable proximidad entre las dependencias, y sobre todo el número de operaciones adicionales requeridas para el tratamiento adecuado de los datos, entre otras dificultades, generaron un \emph{overhead} que claramente afectó la performance de la implementación. De hecho, como consecuencia de lo último, no hubiera sido motivo de sorpresa que la versión escalar obtuviera igual o incluso mejor performance que la versión vectorizada.

En este marco, y considerando las tecnologías a nivel procesador con las que trabajamos, el hecho de que la intrincada versión vectorizada del algoritmo SHA-256 superara a su contraparte escalar en casi un $10\%$ es considerado como un resultado \emph{aceptable}.


