As constantes do Skein
Oi,
Os leitores que acompanham este blol com certeza já leram os meus posts anteriores sobre o Threefish, a cifra por trás do Skein. Já vimos como melhorar o desempenho da mesma utilizando as extensões SSE2. Há pouco reparei num detalhe que não tinha na altura — algumas das constantes utlilizadas nas rotações do Skein são múltiplos de 8. Isto permite-nos efectuar a rotação como uma permutação de bytes, como demostrado neste post.
Nas especificações originais do Skein, existiam 13 constantes múltiplas de 8: 1 para a versão de 256 bits, 2 para a de 512 bits e 10 para a de 1024 bits. As rotações implementadas na versão SSE2 são sensivelmente da forma:
; rotate xmm0 left by 5 bits movdqa xmm1, xmm0 psllq xmm0, 5 psrlq xmm1, (64-5) pxor xmm0, xmm1
Quando a rotação é por um múltiplo de 8, isto pode ser convertido para:
; rotate xmm0 left by 8 bits pshufb xmm0, oword [ROT8]
Num processador actual (i.e. Core 2 45 nm ou Core i7), a versão SSE2 custa-nos pelo menos 1+1+0.33+0.33 = 2.66 ciclos. Com scheduling apropriado, a versão SSSE3 custa-nos 1 ciclo. Para aproximar a melhoria de desempenho possível com esta pequena alteração, vejamos o que acontece quando utilizamos esta optimização.
Uma cifração no Threefish de 256 bits necessita de 72*6 + 72 = 504 operações, excluindo loads, stores e permutações de variáveis inteiras. No caso de 256 bits, apenas uma das constantes é 0 (mod 8), significando que 72/8 = 9 rotações podem ser substituídas por um pshufb. Se 9 em 504 operações podem ser aceleradas 2.66 vezes, temos um speedup de 1.1%, quase insignificante.
No entanto, a versão actualizada do Skein tem novas constantes, incluindo 4 multiplos de 8 para 256 bits. Isto dá-nos um speedup possível de 4.7%. Note-se que estes números são puramente teóricos; o facto de este novo método libertar um registo pode evitar spills de registos para a stack, causando speedups bastante maiores que o esperado.
