\section{Introducción}
Entre los usos más frecuentes de la extensión \emph{SSE} incluida en los procesadores \emph{Intel} a partir del \emph{Pentium III}, se encuentran, entre otros, el procesamiento de señales, el procesamiento de imágenes, y la simulación de sistemas físicos. Pero también existe otro área de aplicación menos conocido: los \emph{algoritmos de hash}. De ello nos ocupamos en este trabajo.

Son dos los algoritmos de hashing que estudiaremos: el \emph{Secure Hash Algorithm 1} (\emph{SHA-1}), y un miembro de la denominada familia de algoritmos \emph{SHA-2}: el \emph{Secure Hash Algorithm 256} (\emph{SHA-256}). La elección de estos dos algoritmos obedece al hecho de que ambos continúan siendo los algoritmos de hashing de mayor uso hoy día.

Ahora bien, ocurre que ni \emph{SHA-1}, ni \emph{SHA-256} son algoritmos precisamente \emph{vectorizables}: como veremos, los datos computados en una ronda determinada dependen de los datos de la ronda anterior (propiedad implementada a partir de la \emph{Construcción de Merkle-Damgård}\footnote{La \emph{Construcción de Merkle-Damgård}, también conocida como \emph{Función de hash de Merkle-Damgård}, tiene como objetivo incrementar la resistencia a colisiones de los algoritmos de hash empleando funciones de \emph{compresión} de los datos de \emph{una vía} (que son, por definición, resistente a colisiones en sí mismas). Básicamente, estas funciones utilizan como entrada un nuevo bloque de datos y la salida de la aplicación de la misma función sobre el bloque de datos anterior.}), de modo que no existe independencia entre ellos. Esto impide, como consecuencia, un procesamiento paralelo directo, como sí suele suceder en otros casos (por ejemplo, el procesamiento de imágenes).

Sin embargo, veremos que distintas propiedades matemáticas y algunos mecanismos muy rebuscados, combinados con una serie de optimizaciones, nos permitirán vectorizar gran parte del proceso estos dos algoritmos de hash.

El presente trabajo consiste, por lo tanto, en el análisis detallado de cada elemento (propiedades, optimizaciones, estrategias, etc.) que conducirán a la obtención de la versión cuasi-vectorizada de cada uno de los algoritmos de hashing estudiados, para luego evaluar el desempeño de estas implementaciones con sus contraparte escalares.

\subsection{Software y hardware empleados en el proyecto}
Este trabajo originalmente se inició en entorno \emph{Debian Linux Squeeze} de 64 bits, corriendo en una máquina con procesador \emph{Pentium D}, y memoria 2\emph{GB} de RAM \emph{DDR2}. Parte de la implementación de los algoritmos se limitó, por lo tanto, a la extensión \emph{SSE3}.

Posteriormente, el desarrollo continuó en otra máquina con \emph{Debian Linux Wheezy} de 64 bits, procesador \emph{Intel Core I-5 3210M}, 2\emph{GB} de RAM \emph{DDR3}. Como consecuencia del traspaso, optimizamos un tanto más las implementaciones, incorporando nuevas instrucciones incluidas en la mejora \emph{SSSE3} (véase la sección \ref{sha1_implementacion}, \emph{Instrucciones SSSE3 especiales}). De modo que todas las implementaciones de este proyecto se limitan a la extensión suplementaria \emph{SSSE3}.

Todos los algoritmos fueron implementados en \emph{ensamblador}, utilizando \emph{NASM}\footnote{Página web oficial de \emph{NASM}: \texttt{www.nasm.us}}, a excepción de aquellos casos donde se incluyen implementaciones adicionales en lenguaje \emph{C}.

\subsection{Recorrido del trabajo}
Describimos a continuación las distintas partes que componen este trabajo:

\begin{itemize}

\item[-] \textbf{Técnicas algorítmicas de optimización}:

Como paso previo al análisis de los algoritmos de hashing, la sección \ref{tec_alg} se ocupa de la descripción de dos de las primera técnicas algorítmicas que utilizaremos con frecuencia en las implementaciones de los algoritmos del proyecto: \emph{loop unrolling} y \emph{software pipelining}. La primera la aplicamos en todos los casos (esto es, algoritmos escalares y vectorizados); la segunda, solo en el caso de los algoritmos vectorizados.  En el caso del \emph{loop unrolling}, se incluye también una primera experiencia que permite evaluar qué tanto puede mejorar el desempeño de un algoritmo que implementa esta técnica, con respecto a otro que no la implementa. Si bien para este primer ensayo el algoritmo empleado es el \emph{SHA-1}, no entramos en detalles con respecto al mismo, sino hasta la sección que sigue.

\vspace{5pt}
\item[-] \textbf{Algoritmo de hashing SHA-1}:

La sección \ref{sha1} analiza el primer algoritmo de hash que estudiaremos: el algoritmo SHA-1. Este análisis lo componen múltiples secciones, que van desde la definición formal del algoritmo de acuerdo al \emph{fips-180}\footnote{\emph{fips} son las siglas de \emph{Federal Information Processing Standard}, que puede traducirse como \emph{Estándares Federales para el Procesamiento de la Información}. Se trata de documentos emitidos por el \emph{NIST} de los Estados Unidos (\emph{National Institute of Standards and Technology} o, en español, \emph{Instituto Nacional de Estándares y Tecnología}), donde básicamente se definen los estándares y regulaciones para el manejo de la información en computadoras.}, pasando por el análisis detallado de las optimizaciones, propiedades matemáticas y estrategias que permiten su cuasi-vectorización, siguiendo por los detalles a nivel de código de la implementaciones vectorizada, y finalizando con los detalles de la experiencia y los resultados correspondientes.

\vspace{5pt}
\item[-] \textbf{Algoritmo de hashing SHA-256}:

En la sección \ref{sha256} repetimos el recorrido anterior sobre el segundo algoritmo de interés: el algoritmo \emph{SHA-256}.

\vspace{5pt}
\item[-] \textbf{Detalles de las implementaciones y la generación de datos}:

En esta se explican todos los detalles acerca de las aplicaciones desarrolladas y la generación de los datos: estructura de los programas implementados, detalles de los módulos que los componen, el modo de uso de las aplicaciones, los datos de entrada que reciben y la salida que generan, y el modo en que se procesa toda la información generada para obtener los datos de las distintas experiencias.

\vspace{5pt}
\item[-] \textbf{Apéndice - Extensiones especiales de los procesadores Intel}:

Por último, la sección \ref{extensiones} es una apéndice con toda la información acerca de las nuevas extensiones que facilitan las operaciones de los algoritmos de hash que analizamos, cómo así también aquellas que expanden las capacidades de cómputo y que también podemos aprovechar sobre estos algoritmos. Más precisamente, describiremos:

\begin{itemize}
\item[-] La \emph{Intel SHA Extensions}: se trata de un nuevo conjunto de instrucciones que permiten el cómputo de los hash SHA-1 y SHA-256 mediante la aceleración por hardware. Veremos en detalle y con ejemplos, cómo operan cada una de las 7 instrucciones de conforman esta extensión.
\item [-] Las extensiones \emph{AVXs}, en sus variantes \emph{AVX1}, \emph{AVX2} y la \emph{AVX-512}\footnote{Se espera que la extensión \emph{AVX-512} sea lanzada en algún momento del presente año.}: entre sus características más sobresalientes se encuentran la duplicación y cuadruplicación del tamaño de los registros \texttt{XMM} y la incorporación de instrucciones vectoriales avanzadas. Repasaremos rápidamente cada uno de estos elementos, y veremos la manera en que podemos aprovechar estas nuevas características para mejorar los algoritmos de hash estudiados.
\item[-] Extensión \emph{BMI2}: incopora un número importante de instrucciones que operan a nivel de bit sobre registros de propósito general, especialmente útiles en las operaciones de los algoritmos de hash.
\end{itemize}
\end{itemize}
