Mais um blog inútil.

Outubro 7, 2009

As constantes do Skein

Filed under: Serious Business — dongs @ 2:21

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.

Comentar

widgeon
widgeon
widgeon
widgeon