¿Venís de leer la intro?
En esta parte, vemos como se implementa en C, utilizando 32 bits aunque la arquitectura sea de 64. No tiene nada de especial en sí, es la implementación de la wikipedia adaptada a C.
Optimizaciones en la implementación
Encadenamiento
Las claves que estamos explorando miden menos de 56 bytes, entonces no hace falta hacer el proceso de encadenamiento, en el cual se va tomando lo hecho previamente y se aplica sobre cada nuevo bloque.
Padding
Normalmente, como los mensajes que se están hasheando tienen distintas longitudes y no suelen ser congruentes con la longitud del bloque, al último bloque se le hace un padding, esto es un relleno.
En este caso, todos los mensajes son el último y necesitan el padding por entrar sobradamente en el bloque. Pero las claves miden siempre los mismo, tienen el mismo padding, no hace falta recalcular. En realidad casi que ni hace falta calcular, se puede hardcodear, pero no hace diferencia en la performance.
Loop unroll
Un loop unroll consiste en tomar el cuerpo de un for y repetirlo tantas veces como se vaya a ejectuar, ajustando los valores para que el resultado sea el mismo, por ejemplo:
int accum = 0;
for (int i=0; i < 4; ++i) {
accum += i;
}
Se convierte en
int accum = 0;
accum += 0;
accum += 1;
accum += 2;
accum += 3;
Si tenés una mínima noción de matemáticas me podrías decir que para ese cálculo se puede usar una fórmula de un solo paso, pero estoy haciendo el ejemplo más sencillo posible.
Al eliminar las decisiones, funciona mejor el pipeline de la CPU y mejora la performance, además el cáluco de i se hace en tiempo de pensarlo:
Los rendimientos por watt y por dolar son medio medio a ojo, no le prestés mucha antención.
Pero mi objetivo no es la performance en esta etapa, sino apuntar a la implementación final en FPGA donde será implementado así.
Hack rumbo a SIMD
Considerá que MD5 es un algoritmo de 32 bits y la arquitectura predominante en server/desktop/laptop es 64 bits. Esto nos deja en la situación de que se pueden calcular dos hashes simultáneos. Aun que es rehacker el rendimiento no es el esperado asi que no perdamos tiempo con esto.
 |
| Hack 64 bits |
Sin embargo el concepto es importante, pues nos prepara para la siguiente parte, donde tener más bits pasa de ser hack a una feature.
Video
- https://www.youtube.com/channel/UCKsHdgvwvmCNnGD1Az8SSUQ
Código
- https://github.com/cpantel/Forzando-Brutalmente-MD5/tree/master/v1_cpu
- https://github.com/cpantel/Forzando-Brutalmente-MD5/tree/master/v1_cpu_unroll
- https://github.com/cpantel/Forzando-Brutalmente-MD5/tree/master/v2_hack
No hay comentarios:
Publicar un comentario