\section{Apéndice - Extensiones especiales de los procesadores de \emph{Intel}}\label{extensiones}

\subsection{Intel SHA Extensions}\label{intel_sha_extensions}
Como contraparte a todos nuestros esfuerzos en la optimización por software de los algoritmos de hashing que estudiamos, \emph{Intel} lanza en 2015 la microarquitectura \emph{Goldmont}, la primera en incluir la denominada \emph{Intel SHA Extensions}. Se trata de un conjunto de 7 instrucciones que tienen por objeto la aceleración por hardware en el cómputo de los valores de hash para los dos algoritmos que analizamos precisamente en este trabajo: SHA-1 y SHA-256.

Vale destacar que, contrariamente a lo que pudiera suponerse, este nuevo conjunto de instrucciones no realizan la totalidad de los cómputos, sino que, más bien, facilitan diversos cómputos parciales en ambos algoritmos.

Desafortunadamente, el empleo de estas instrucciones es bastante rebuscado, dado que al hecho de tener que lidiar con los aspectos de por sí intrincados de estos dos algoritmos, se le suman algunas presunciones respecto de al contenido de los operandos, muchas de la cuales involucran las optimizaciones descriptas en este trabajo (como por ejemplo, la suma de $w+k$, o la propiedad circular de las variables de estado $a$, $b$, $c$, etc., que deberán especificarse de forma alternada y en registros diferentes, etc.).

El \emph{Intel SHA Extensions} incluye un total de 7 instrucciones, divididas en dos grupos: 4 instrucciones para SHA-1, y 3 instrucciones para SHA-256. A su vez, cada grupo se divide en dos categorías de instrucciones: instrucciones para el cómputo de la extensión del vector $w$, e instrucciones para el cómputo de rondas (actualización de las variables $a$, $b$, $c$, etc.). Todas las instrucciones utilizan como operandos los registros \texttt{XMM}, direcciones de memorias, y operandos inmediatos de 1 byte. Existe además el caso insólito de una instrucción perteneciente al grupo de SHA-1 que requiere como tercer operando al registro explítico \texttt{XMM0}.

La siguiente lista enumera las instrucciones que componen a la extensión SHA de \emph{Intel}:
\begin{itemize}
\item SHA-1:
\begin{itemize}
\item[-] Instrucciones para la extensión de $w$:
\begin{enumerate}
\item \texttt{SHA1MSG1} (\emph{SHA-1 - Message 1})
\item \texttt{SHA1MSG2} (\emph{SHA-1 - Message 2})
\end{enumerate}
\item[-] Instrucciones para la actualización de las variables de estado ($a$, $b$, $c$, $d$ y $e$) en las rondas:
\begin{enumerate}
\item \texttt{SHA1RNDS4} (\emph{SHA-1 - Rounds 4})
\item \texttt{SHA1NEXTE} (\emph{SHA-1 - Next E})
\end{enumerate}
\end{itemize}

\item SHA-256:
\begin{itemize}
\item[-] Instrucciones para la extensión de $w$:
\begin{enumerate}
\item \texttt{SHA256MSG1} (\emph{SHA-256 - Message 1})
\item \texttt{SHA256MSG2} (\emph{SHA-256 - Message 2})
\end{enumerate}
\item[-]Instrucciones para la actualización de las variables de estado ($a$, $b$, $c$, $d$ ... $h$) en las rondas:
\begin{enumerate}
\item \texttt{SHA256RNDS2} (\emph{SHA-256 - Rounds 2})
\end{enumerate}
\end{itemize}
\end{itemize}

Veamos en detalle como funcionan.

\subsubsection{Instrucciones del \emph{Intel SHA Extensions} para SHA-1}

\subsubsection*{- Cómputo de la extensión del \emph{Message Schedule}}

Recordemos antes la expresión para el cómputo de la extensión del vector $w$ (\emph{Message Schedule}) en SHA-1:
\begin{displaymath}
w[i] = (w[i-3] \oplus w[i-8] \oplus w[i-14] \oplus w[i-16]) \hookleftarrow 1
\end{displaymath}

\paragraph{Instrucción \texttt{SHA1MSG1}}
\begin{itemize}
\item[-] \textbf{Definición}:

\texttt{SHA1MSG1 XMM1, XMM2/m128}
\vspace{5pt}
\item[-] \textbf{Detalles}:

Ejecuta el cómputo parcial $w[i-14] \oplus w[i-16]$ de forma vectorizada, en el cálculo para la extensión del vector $w$, y almacena el resultado en \texttt{XMM1}.
\vspace{5pt}
\item[-] \textbf{Operandos}:
\begin{enumerate}
\item \texttt{XMM1}: almacena 4 valores consecutivos del vector $w$ a partir de $w[i-16]$, que son: $w[i-16]$, $w[i-15]$, $w[i-14]$ y $w[i-13]$.
\vspace{3pt}
\item \texttt{XMM2/m128}: almacena 4 valores consecutivos del vector $w$ a partir de $w[i-14]$, que son: $w[i-14]$, $w[i-13]$, $w[i-12]$ y $w[i-11]$ (los dos últimos no se utilizan).
\end{enumerate}

\vspace{5pt}
\item[-] \textbf{Resultado}:

\texttt{XMM1: w[i-14] XOR w[i-16] | ... | w[i-11] XOR w[i-13]}
\end{itemize}

\paragraph{Instrucción \texttt{SHA1MSG2}}

\begin{itemize}
\item[-] \textbf{Definición}:

\texttt{SHA1MSG2 XMM1, XMM2/m128}
\vspace{5pt}
\item[-] \textbf{Detalles}:

Completa el cómputo vectorizado que se inició con \texttt{SHA1MSG1}, para obtener finalmente los nuevos elementos del vector $w$: $w[i]$, $w[i+1]$, $w[i+2]$ y $w[i+3]$. Sin embargo, su aplicación no es directa, como se describe a continuación.
\vspace{5pt}
\item[-] \textbf{Operandos}:
\begin{enumerate}
\item \texttt{XMM1}: almacena 4 valores consecutivos con el cómputo $w[i-8] \oplus w[i-14] \oplus w[i-16]$. Es decir:
\begin{verbatim}
          XMM1: w[i-8] XOR w[i-14] XOR w[i-16] |
                w[i-7] XOR w[i-13] XOR w[i-15] |
                w[i-6] XOR w[i-12] XOR w[i-14] |
                w[i-5] XOR w[i-11] XOR w[i-11]
\end{verbatim}
\vspace{5pt}
Notemos que el cómputo vectorizado parcial $w[i-14] \oplus w[i-16]$ lo obtuvimos de la intrucción \texttt{SHA1MSG1} descripta anteriormente. A ese resultado falta computarle $w[i-8] \oplus ...$ para obtener los valores requeridos en este operando. Esa parte debe realizarse de forma explícita por separado, mediante la instrucción \texttt{PXOR}.
\vspace{5pt}
\item \texttt{XMM2/m128}: almacena 4 valores consecutivos del vector $w$ a partir de $w[i-4]$, que son:  $w[i-4]$, $w[i-3]$, $w[i-2]$ y $w[i-1]$.
\end{enumerate}
\vspace{5pt}
\item[-]\textbf{Resultado}:

\texttt{XMM: w[i], w[i+1], w[i+2] y w[i+3]}
\end{itemize}

\subsubsection*{- Actualización de las variables de estado en las rondas}
Repasemos el cómputo para la actualización de las variables de estado $a$, $b$, $c$, $d$ y $e$ en cada ronda del algoritmo SHA-1:
{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{24pt}\textbf{Si} (0 $\le$ \texttt{i} $\le$ 19) \textbf{entonces} \\
\vspace{3pt}
\hspace{36pt}$f = \left(b \wedge c\right) \vee \left(\left(\neg \ b\right) \wedge d\right)$ \\
\hspace{36pt}$k =$ \texttt{0x5A827999} \\
\vspace{5pt}
\hspace{24pt}\textbf{Sino Si} $(20 \le i \le 39)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{36pt}$f = b \oplus c \oplus d$ \\
\hspace{36pt}$k =$ \texttt{0x6ED9EBA1} \\
\vspace{5pt}
\hspace{24pt}\textbf{Sino Si} $(40 \le i \le 59)$ \textbf{entonces} \\
\vspace{3pt}
\hspace{36pt}$f = \left(b \wedge c\right) \vee \left(b \wedge d\right) \wedge \left(c \wedge d\right)$ \\
\hspace{36pt}$k =$ \texttt{0x8F1BBCDC} \\
\vspace{5pt}
\hspace{24pt}\textbf{Sino} \\
\vspace{3pt}
\hspace{36pt}$f = b \oplus c \oplus d$ \\
\hspace{36pt}$k =$ \texttt{0xCA62C1D6} \\
\vspace{5pt}
\hspace{24pt}\textbf{Fin Si} \\
\vspace{10pt}
\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}
}

\paragraph{Instrucción \texttt{SHA1RNDS4}}

\begin{itemize}
\item[-] \textbf{Definición}:

\vspace{3pt}
\texttt{SHA1RNDS4 XMM1, XMM2/m128, imm8}
\vspace{5pt}
\item[-] \textbf{Detalles}:
Actualiza las variables de estado $a$, $b$, $c$ y $d$ por el equivalente a 4 rondas consecutivas del algoritmo SHA-1. (Nótese la omisión de la variable $e$. Esto se explica en la instrucción que sigue.)
\vspace{5pt}
\item[-] \textbf{Operandos}:
\begin{enumerate}
\item \texttt{XMM1}: almacena las variables de estado $a$, $b$, $c$ y $d$.
\vspace{5pt}
\item \texttt{XMM2/m128}: almacena los siguientes valores: $w[i] + e$, $w[i+1]$, $w[i+2]$ y $w[i+3]$.
\vspace{5pt}
\item \texttt{imm8}: valor de tamaño \texttt{BYTE} que varía entre 0 y 3, y que se utiliza como selector de valores para el par $f$ y $k$, donde 0 equivale al rango $0 \leq i \leq 19$, 1 al rango $20 \leq i \leq 39$, 2 al rango $40 \leq i \leq 59$, y 3 al rango $60 \leq i \leq 79$ (véase la sentencia de decisión en el framento de código incluido al comienzo de esta sección).
\end{enumerate}
\vspace{5pt}
\item[-] \textbf{Resultado}:

Registro \texttt{XMM1} con el valor de las variables $a$, $b$, $c$ y $d$ actualizadas por el equivalente a 4 rondas consecutivas de SHA-1.
\end{itemize}

\paragraph{Instrucción \texttt{SHA1NEXTE}}

\begin{itemize}
\item[-] \textbf{Definición}:

\vspace{3pt}
\texttt{SHA1NEXTE XMM1, XMM2/m128}
\vspace{5pt}
\item[-] \textbf{Detalles}:
Devuelve los valores $w[i] + e$, $w[i+1]$, $w[i+2]$ y $w[i+3]$.

\vspace{5pt}
\item[-] \textbf{Operandos}:
  1) \texttt{XMM1}: almacena las variables de estado $a$, $b$, $c$ y $d$.
  2) \texttt{XMM2/m128}: almacena los siguientes valores: $w[i]$, $w[i+1]$, $w[i+2]$ y $w[i+3]$.

\vspace{5pt}
\item[-] \textbf{Resultado}:

\texttt{XMM1: w[i] + E | w[i+1] | w[i+2] | w[i+3]}

\vspace{5pt}
\item[-] \textbf{Observación}:

La variable $e$ no justifica un cómputo particular, puesto que hacia la cuarta ronda, su valor es el equivalente a la variable $a$ original (es decir, la variable $a$ en la ronda 0), rotada a la izquierda en 30 bits. Esto es consecuencia de la circularidad que vimos que existe entre las variables de estado (véase la sección \ref{sha1_implementacion}, \emph{Optimización del proceso de actualización...}), en donde el valor de la variable $a$ en la ronda 0 pasa a ser el valor de $b$ en la ronda 1, el de $c$ en la ronda 2 con una modificación (es acá que se le aplica la rotación a izquierda en 30 bits), el de $d$ en la ronda 3 (con la modificación anterior) y finalmente el de $e$ en la ronda 4. Por ese motivo, la instrucción realiza este cálculo internamente y ahorra unos pasos más sumándola directamente al elemento $w[i]$, que es, en definitiva, para lo que se usa. De modo la instrucción \texttt{SHA1NEXTE} es complentaria a \texttt{SHA1RNDS4}.
\end{itemize}

\subsubsection{Instrucciones del \emph{Intel SHA Extensions} para SHA-256}

\subsubsection*{- Cómputo de la extensión del \emph{Message Schedule}}
Recordemos antes el cómputo de la extensión del vector $w$ (\emph{Message Schedule}) en SHA-256:
\begin{align*}
&s0 = (w[i-15] \hookrightarrow 7) \oplus (w[i-15] \hookrightarrow 18) \oplus (w[i-15] \gg 3)\\
&s1 = (w[i-2] \hookrightarrow 17) \oplus (w[i-2] \hookrightarrow 19) \oplus (w[i-2] \gg 10)\\
&w[i] = w[i-16] + s0 + w[i-7] + s1
\end{align*}
  
\paragraph{Instrucción \texttt{SHA256MSG1}}
\begin{itemize}
\item[-] \textbf{Definición}:

\vspace{3pt}
\texttt{SHA256MSG1 XMM1, XMM2/m128}
\vspace{5pt}
\item[-] \textbf{Detalles}:

Ejecuta el cómputo parcial $s0 + w[i-16]$, de forma vectorizada, en el cálculo para la extensión del vector $w$, y almacena el resultado en \texttt{XMM1}.

\vspace{5pt}
\item[-] \textbf{Operandos}:
\begin{enumerate}
\item \texttt{XMM1}: almacena 4 valores consecutivos del vector $w$ a partir de $w[i-16]$, que son: $w[i-16]$, $w[i-15]$, $w[i-14]$ y $w[i-13]$.
\vspace{5pt}
\item \texttt{XMM2/m128}: almacena 4 valores consecutivos del vector $w$ a partir de $w[i-12]$, que son: $w[i-12]$, $w[i-11]$, $w[i-10]$ y $w[i-9]$ (los 3 últimos no se utilizan).
\end{enumerate}

\vspace{5pt}
\item[-] \textbf{Resultado}:

\texttt{XMM1: s0 + w[i-16] | s0 + w[i-15] | s0 + w[i-14] | s0 + w[i-13]}
\end{itemize}  
  
\paragraph{Instrucción \texttt{SHA256MSG2}}
\begin{itemize}
\item[-] \textbf{Definición}:

\vspace{3pt}
\texttt{SHA256MSG2 XMM1, XMM2/m128}

\vspace{5pt}
\item[-] \textbf{Detalles}:

Completa el cómputo vectorizado que se inició con \texttt{SHA256MSG1}, para obtener finalmente los nuevos elementos del vector $w$: $w[i]$, $w[i+1]$, $w[i+2]$ y $w[i+3]$. Sin embargo, su aplicación no es directa, como se describe a continuación.

\vspace{5pt}
\item[-] \textbf{Operandos}:
\begin{enumerate}
\item \texttt{XMM1}: almacena 4 valores consecutivos con el cómputo $s0 + w[i-16] + w[i-7]$. Es decir:
\begin{verbatim}
        s0 + w[i-16] + w[i-7] | ... | s0 + w[i-13] + w[i-4]
\end{verbatim}
\vspace{5pt}
Observemos que el cómputo vectorizado parcial $s0 + w[i-16]$ lo obtuvimos de la intrucción \texttt{SHA256MSG1} que se decribió antes. Ese resultado es incompleto, y falta sumarle $w[i-7]$ para obtener los valores requeridos en este operando. Esa parte debe realizarse de forma explícita por separado, mediante la instrucción \texttt{PADDD}. Pero incluso antes de esa suma empaquetada, también será necesario una instrucción PALIGNR, dado que el elemento \texttt{w[i-7]} no es múltiplo de 4. A continuación se muestra un ejemplo donde se realiza esta alineación requerida:
  
Asumiendo:
\begin{verbatim}
  XMM1: w[i-8] | w[i-7] | w[i-6] | w[i-5]
  XMM2: w[i-4] | w[i-3] | w[i-2] | w[i-1]
\end{verbatim}

Entonces:
\begin{verbatim}
    PALIGNR XMM1, XMM2, 4  ; XMM1: w[i-7] | ... | w[i-4]
\end{verbatim}    

\vspace{5pt}
\item \texttt{XMM2/m128}: almacena 4 valores consecutivos del vector $w$ a partir de $w[i-4]$, que son: $w[i-4]$, $w[i-3]$, $w[i-2]$ y $w[i-1]$ (los dos primeros valores no se utilizan).
\end{enumerate}

\vspace{5pt}
\item[-] \textbf{Resultado}:

\texttt{XMM1: w[i], w[i+1], w[i+2] y w[i+3]}
\end{itemize}
  
\subsubsection*{- Actualización de las variables de estado en las rondas}
Repasemos el cómputo para la actualización de las variables de estado $a$, $b$, $c$, $d$, $e$, $f$, $g$ y $h$ en cada ronda del algoritmo SHA-256:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{24pt}$S1 = (e \hookrightarrow 6) \oplus (e \hookrightarrow 11) \oplus (e \hookrightarrow 25)$ \\
\vspace{2pt}
\hspace{24pt}$ch = (e \wedge f) \oplus ((\neg e) \wedge g)$ \\
\vspace{2pt}
\hspace{24pt}$temp1 = h + S1 + ch + k[i] + w[i]$ \\
\vspace{2pt}
\hspace{24pt}$S0 = (a \hookrightarrow 2) \oplus (a \hookrightarrow 13) \oplus (a \hookrightarrow 22)$ \\
\vspace{2pt}
\hspace{24pt}$maj = (a \wedge b) \oplus (a \wedge c) \oplus (b \wedge c)$ \\
\vspace{2pt}
\hspace{24pt}$temp2 = S0 + maj$ \\
\vspace{10pt}
\hspace{24pt}$h = g$ \\
\vspace{2pt}
\hspace{24pt}$g = f$ \\
\vspace{2pt}
\hspace{24pt}$f = e$ \\
\vspace{2pt}
\hspace{24pt}$e = d + temp1$ \\
\vspace{2pt}
\hspace{24pt}$d = c$ \\
\vspace{2pt}
\hspace{24pt}$c = b$ \\
\vspace{2pt}
\hspace{24pt}$b = a$ \\
\vspace{2pt}
\hspace{24pt}$a = temp1 + temp2$ \\
\end{flushleft}
}

\paragraph{Instrucción \texttt{SHA256RNDS2}}
\begin{itemize}
\item[-] \textbf{Definición}:

\vspace{3pt}
\texttt{SHA256RNDS2 XMM1, XMM2/m128, XMM0}

\vspace{5pt}
\item[-] \textbf{Detalles}:
Actualiza las variables de estado $a$, $b$, $c$, $d$, $d$, $e$, $f$, $g$ y $h$ por el equivalente a 2 rondas consecutivas del algoritmo SHA-256.

\vspace{5pt}
\item[-] \textbf{Operandos}:
\begin{enumerate}
\item \texttt{XMM1}: almacena las variables de estado $c$, $d$, $g$ y $h$.
\vspace{3pt}
\item \texttt{XMM2/m128}: almacena las variables de estado $a$, $b$, $e$ y $f$.
\vspace{3pt}
\item \texttt{XMM0}: almacena los valores $w[i] + k[i]$ y $w[i+1] + k[i+1]$; el valor de los dos restantes \texttt{DWORDs} se ignoran.
\end{enumerate}

\vspace{5pt}
\item[-] \textbf{Resultado}:

Registro \texttt{XMM1} con el valor de las variables $a$, $b$, $e$ y $f$ actualizadas por el equivalente a dos rondas de SHA-256.

\vspace{5pt}
\item[-] \textbf{Más detalles}:

Esta instrucción puede parecer, en principio, la más intrincada de todo el conjunto. La confusión aparece a raíz de una optimización que se aprovecha, la cual involucra, una vez más, a la propiedad de circularidad de las variables de estado. Veamos en detalle el porqué de la estructura de los operandos, y el modo en que debe interpretarse el resultado.

En primer lugar, observemos que cuando proyectamos la circularidad de las variables de estado hacia la ronda 2, resulta que la variable $c$ se convierte en la variable $a$, la $d$ en $b$, la $g$ en $e$, y la $h$ en $f$; todas ellas sin modificación alguna:

{\setlength{\parskip}{0cm}
\begin{flushleft}
\hspace{12pt}Ronda 0: \quad $a$ \quad $b$ \quad $c$ \quad $d$ \quad $e$ \quad $f$ \quad $g$ \quad $h$ \\
\vspace{3pt}
\hspace{12pt}Ronda 1: \quad $h'$\quad$a$ \quad $b$ \quad $c$ \quad $d'$\quad$e$ \quad $f$ \quad $g$ \\
\vspace{3pt}
\hspace{12pt}Ronda 2: \quad $g'$\quad$h'$\quad$\underset{\uparrow}{a}$ \quad $\underset{\uparrow}{b}$ \quad $c'$\quad$d'$\quad$\underset{\uparrow}{e}$ \quad $\underset{\uparrow}{f}$
\end{flushleft}
}

Ahora bien, ocurre que los valores de las variables $a$, $b$, $e$ y $f$ en los que se convierten, respectivamente, las variables $c$, $d$, $g$ y $h$ en la ronda 2, se almacenan precisamente en el segundo operando (\texttt{XMM2/m128}). De modo esos valores intactos en el segundo operando se interpretan como los nuevos valores de las variables $c$, $d$, $g$ y $h$ para la ronda 2. Por otra parte, sobre el primer operando, que es el operando de destino, se realizan efectivamente cómputos que generan los nuevos valores de $a$, $b$, $e$ y $f$ correspondientes a la segunda ronda.

Este comportamiento explica lo que al principio parecía una extraña distribución de las variables de estado en los operandos de la instrucción: simplemente se separan las variables que se modifican de las que no. Notemos además que el procesamiento secuencial de las rondas, en saltos de a dos debido a la operatoria de la instrucción, se reduce a una alternancia en la especificación de los operandos:

\begin{verbatim}
   SHA256RNDS2 XMM1, XMM2, XMM0
          ...  
   SHA256RNDS2 XMM2, XMM1, XMM0
          ...  
   SHA256RNDS2 XMM1, XMM2, XMM0
          ...
   SHA256RNDS2 XMM2, XMM1, XMM0
          ...
\end{verbatim}
\end{itemize}

\subsection{Extensiones \emph{AVXs} y \emph{BMI2}}

\subsubsection{Extensiones \emph{AVXs}}
\emph{AVX} son las siglas de \emph{Advanced Vector Extensions}, un conjunto de extensiones y mejoras que involucran la expansión en el tamaño de los registros SIMD y la incorporación de nuevas instrucciones vectoriales, entre otras cosas. Actualmente existen tres versiones, la última próxima a ser lanzada en el mercado: \emph{AVX}, \emph{AVX2} y \emph{AVX-512}

La primera versión de \emph{AVX} fue incorporada en la microarquitectura \emph{Sandy Bridge}, lanzada en 2011 en la línea de procesadores \emph{Core i3}. Uno de las características más especiales de \emph{AVX} no tiene que ver precisamente con la típica expansión en las capacidades y la incorporación de nuevas operaciones. Más bien, es lo que podría considerarse como un cambio en el paradigma en la programación en ensamblador \emph{x86} moderno: la idea de \emph{instrucciones no destructivas}. En concreto, las nuevas instrucciones incorporan un operando adicional que actúa como destino en una operación determinada. De esta forma, se evita la clásica destrucción del primero de los operandos al ejecutar una instrucción, motivo por el cual frecuentemente es obligación hacer copia del valor en otro registro, en la pila o en la memoria.

Con respecto a la expansión de las capacidades de los registros \texttt{XMM}, éstos duplican el tamaño: pasan de 128 a 256 bits. Estos nuevos registros \texttt{XMM} ahora se denominan \texttt{YMM}.

La primera versión de \emph{AVX} es muy limitada en cuanto al número de instrucciones vectoriales capaces de operar sobre los nuevos registros \texttt{YMM}. La gran mayoría de las nuevas instrucciones continúan empleando a los registros \texttt{XMM} o a valores inmediatos \texttt{QWORD} como operandos.

El cambio verdadero se produce con la aparición de \emph{AVX2}, incluida en la microarquitectura \emph{Haswell}, lanzada al mercado en 2013 en la línea de los nuevos procesadores \emph{Core i3}.

La nueva extensión \emph{AVX2} aumenta considerablemente el soporte de las instrucciones \emph{SSE} sobre \emph{AVX}, a la vez que incorpora un número importante de otras nuevas. Pero además incluye optimizaciones de bajo nivel para muchas de estas operaciones.

Las nuevas instrucciones \emph{SSE} para \emph{AVX} implementan el formato no destructivo mediante un operando adicional, y el nombre de estas operaciones es el mismo que en \emph{SSE}, solo que ahora se debe anteponer el prefijo \texttt{'V'}. A continuación ejemplo muy sencillo:

Con \emph{SSE}:
\begin{verbatim}
      ...
   valores1 DD 1, 2, 3, 4
   valores2 DD 5, 6, 7, 8	
      ...

   MOVDQU XMM0, [valores1]  ; XMM0:  1 |  2 |  3 |  4
   MODQU  XMM1, [valores2]  ; XMM1:  5 |  6 |  7 |  8
   PADDD  XMM0, XMM1        ; XMM0:  6 |  8 | 10 | 12
	
\end{verbatim}


Con \emph{AVX2}:
\begin{verbatim}
      ...
   valores1 DD 1,  2,  3,  4,  5,  6,  7,  8
   valores2 DD 9, 10, 11, 12, 13, 14, 15, 16	
      ...

   VMOVDQU YMM0, [valores1]        ; YMM0:   1,  2,  3,  4,  5,  6,  7,  8
   VPADDD  YMM1, YMM0, [valores2]  ; YMM1:  10, 12, 14, 16, 18, 20, 22, 24
	
\end{verbatim}

Notemos el doble del tamaño de los nuevos registros, y la manera en que se agiliza la suma al no tener que hacer copias para evitar la destrucción del registro \texttt{YMM0}.

Con todo, son esencialmente tres las mejoras que podemos aplicar sobre los algoritmos de hash SHA-1 y SHA-256 que hemos estudiado:

\begin{itemize}
\item Cómputo paralelo de 4 elementos consecutivos de la extensión de $w$ (\emph{Message Schedule}) para 2 bloques de datos: los 256 bits en el tamaño de los registros \texttt{YMM} permiten procesar simultáneamente 8 valores \texttt{DWORDs}. Considerando que el cómputo de estos elementos es exactamente el mismo para todos los bloques, resulta visiblemente conveniente aprovechar una misma secuencia de cálculo de $w$ operando de forma simultánea sobre los elementos de dos bloques de datos. Sin embargo, esta estrategia requiere operaciones adicionales para detectar y actuar en consecuencia en aquellos casos donde el total de bloques de los datos no seá múltiplo de dos.

\item Cómputo paralelo de 1 elemento de la extensión de $w$ (\emph{Message Schedule}) para 8 bloques de datos: la estrategia es la misma que la anterior, solo que ahora operamos sobre un único elemento de $w$ para cada bloque.

\item Aprovechar al máximo la ventaja de las operaciones no destructivas, en particular para los desplazamientos a nivel de bit: esto permitirá ahorrarnos las copias de los datos requeridas en el procesamiento en paralelo de los elementos extendidos del vector $w$.
\end{itemize}

La próxima mejora aparecerá de la mano de \emph{AVX-512}. Esta nueva versión de la extensión \emph{AVX} incluye, además de nuevos conjuntos de instrucciones, la duplicación en el número y tamaño de los registros \texttt{YMM}: se trata de los 32 registros \texttt{ZMM}, con un tamaño de 512 bits.

En este caso, las tres estrategias anteriores podrían volver a emplearse sobre los algoritmos de hash estudiados, solo que ahora de manera mucho más extendida, por ejemplo en el procesamiento de archivos de gran tamaño. Quizás sea posible otra variante orientada a aprovechar la capacidad de los registros \texttt{ZMM}, que involucre la carga completa de los bloques de datos en estos registros, y emplee combinaciones del repertorio de las nuevas instrucciones para los cómputos vectorizados. Veremos lo que ocurre cuando esta extensión finalmente esté disponible.

\subsubsection{Extensión \emph{BMI2}}
Además de \emph{AVX2}, la ya mencionada arquitectura \emph{Haswell} introdujo la denominada extensión {BMI2}. Esta extensión incorpora un número importante de nuevas instrucciones no destructivas con operaciones a nivel de bit, pero en este caso para registros de propósito general. Entre ellas, la instrucción \texttt{RORX}, que puede aprovecharse en el algoritmo de hash SHA-256.

La intrucción \texttt{RORX} realiza rotaciones a derecha, y devuelve el resultado en el primero de los tres operandos. Ejemplo:

\begin{verbatim}
   MOV  RAX, 2       ; RAX: 8
   RORX RBX, RAX, 2  ; RBX: 0xC000000000000000 ; RAX: 8
\end{verbatim}

En SHA-256 podemos aprovechar esta instrucción en los cómputos de los elementos $S0$ y $S1$, respectivamente. En concreto, nos ahorraríamos las copias de los datos. Veamos, por ejemplo, el caso de $S1$. La expresión para obtenerlo era la siguiente:

\begin{displaymath}
S1 = (e \hookrightarrow 6) \oplus (e \hookrightarrow 11) \oplus (e \hookrightarrow 25)
\end{displaymath}

El código en ensamblador que emplea a \texttt{RORX} podría ser algo como esto:

\begin{verbatim}
   RORX EAX, E, 6    ; EAX: (E >>> 6)
   RORX EBX, E, 11   ; EBX: (E >>> 11)
   XOR  EAX, EBX     ; EAX: (E >>> 6) XOR (E >>> 11)
   RORX EBX, E, 25   ; EBX: (E >>> 25)
   XOR  EAX, EBX     ; EAX: (E >>> 6) XOR (E >>> 11) XOR (E >>> 25) = S1
\end{verbatim}

