Threefish - Part II
Como prometido aos meus fiéis leitores ontem, hoje vamos ver como optimizar a cifra Threefish de 250 ciclos por byte (em 32 bit) para algo mais útil na prática.
Em primeiro lugar, e de longe mais relevante, vamos eliminar todos os loops e branches da função. Estes não apenas ocupam recursos que podiam estar a ser usados na cifração em si, mas impedem o uso de todas as unidades de execução. Em segundo lugar, queremos eliminar os acessos à memória desnecessários e manter o máximo de dados possível em registos: substituímos os arrays por variáveis para facilitar esta tarefa ao compilador. Infelizmente, não existem registos para toda a gente (em x86) e vamos sempre ter de aceder à stack para guardar alguns dados. Mas não faz mal. Assim sendo, ficamos com uma função do género:
void ThreefishEncrypt(const ThreefishKey ks, u8 *in, u8 *out)
{
u64 *p = (u64*)in;
u64 v0, v1, v2, v3;
u64 f0, f1, f2, f3;
int i, d;
v0 = p[0];
v1 = p[1];
v2 = p[2];
v3 = p[3];
/* start of round 0 */
v0 += ks->subkey[0][0];
v1 += ks->subkey[0][1];
v2 += ks->subkey[0][2];
v3 += ks->subkey[0][3];
MIX(f1, f0, v1, v0, 5);
MIX(f3, f2, v3, v2, 56);
v0 = f0; v1 = f3; v2 = f2; v3 = f1;
/* start of round 1 */
MIX(f1, f0, v1, v0, 36);
MIX(f3, f2, v3, v2, 28);
v0 = f0; v1 = f3; v2 = f2; v3 = f1;
/* start of round 2 */
MIX(f1, f0, v1, v0, 13);
MIX(f3, f2, v3, v2, 46);
v0 = f0; v1 = f3; v2 = f2; v3 = f1;
......
((u64*)out)[0] = v0 + ks->subkey[ROUNDS/4][0];
((u64*)out)[1] = v1 + ks->subkey[ROUNDS/4][1];
((u64*)out)[2] = v2 + ks->subkey[ROUNDS/4][2];
((u64*)out)[3] = v3 + ks->subkey[ROUNDS/4][3];
}
Esta versão já é substancialmente mais rápida - passamos de 250 para 80 ciclos por byte. Em 64 bit passamos de 50 para 11!
Será que ainda podemos acelerar o processo?
A resposta é sim.
Recorrendo às instruções SSE2 presentes em essencialmente todos os CPUs x86 actuais, podemos cifrar 2 blocos simultaneamente por essencialmente o custo de um. Como é que isto é conseguido?
void ThreefishEncryptSSE2(const ThreefishKey ks, u8 *in, u8 *out)
{
__m128i *p = (__m128i*)in;
__m128i v0, v1, v2, v3;
__m128i f0, f1, f2, f3;
__m128i t0, t1, t2, t3;
__m128i k0, k1, k2, k3;
t0 = _mm_load_si128(&p[0]);
t1 = _mm_load_si128(&p[1]);
t2 = _mm_load_si128(&p[2]);
t3 = _mm_load_si128(&p[3]);
v0 = _mm_unpacklo_epi64(t0, t2);
v1 = _mm_unpackhi_epi64(t0, t2);
v2 = _mm_unpacklo_epi64(t1, t3);
v3 = _mm_unpackhi_epi64(t1, t3);
t0 = _mm_load_si128((__m128i*)&(ks->subkey[0][0]));
t1 = _mm_load_si128((__m128i*)&(ks->subkey[0][2]));
k0 = _mm_shuffle_epi32(t0, 0x44);
k1 = _mm_shuffle_epi32(t0, 0xEE);
k2 = _mm_shuffle_epi32(t1, 0x44);
k3 = _mm_shuffle_epi32(t1, 0xEE);
/* Round 0 */
v0 = _mm_add_epi64(v0, k0);
v1 = _mm_add_epi64(v1, k1);
v2 = _mm_add_epi64(v2, k2);
v3 = _mm_add_epi64(v3, k3);
/* load next subkey */
t0 = _mm_load_si128((__m128i*)&(ks->subkey[1][0]));
t1 = _mm_load_si128((__m128i*)&(ks->subkey[1][2]));
k0 = _mm_shuffle_epi32(t0, 0x44);
k1 = _mm_shuffle_epi32(t0, 0xEE);
k2 = _mm_shuffle_epi32(t1, 0x44);
k3 = _mm_shuffle_epi32(t1, 0xEE);
/* mix */
f0 = _mm_add_epi64(v0, v1);
f1 = _mm_xor_si128(_mm_xor_si128(_mm_slli_epi64(v1, 5),_mm_srli_epi64(v1, 64-5)), f0);
f2 = _mm_add_epi64(v2, v3);
f3 = _mm_xor_si128(_mm_xor_si128(_mm_slli_epi64(v3, 56),_mm_srli_epi64(v3, 64-56)), f2);
/* permute */
v0 = f0;
v1 = f3;
v2 = f2;
v3 = f1;
....
/* Round 71 */
/* mix */
f0 = _mm_add_epi64(v0, v1);
f1 = _mm_xor_si128(_mm_xor_si128(_mm_slli_epi64(v1, 59),_mm_srli_epi64(v1, 64-59)), f0);
f2 = _mm_add_epi64(v2, v3);
f3 = _mm_xor_si128(_mm_xor_si128(_mm_slli_epi64(v3, 50),_mm_srli_epi64(v3, 64-50)), f2);
/* permute */
v0 = _mm_add_epi64(f0, k0);
v1 = _mm_add_epi64(f3, k1);
v2 = _mm_add_epi64(f2, k2);
v3 = _mm_add_epi64(f1, k3);
// unpack
t0 = _mm_unpacklo_epi64(v0, v1);
t1 = _mm_unpacklo_epi64(v2, v3);
t2 = _mm_unpackhi_epi64(v0, v1);
t3 = _mm_unpackhi_epi64(v2, v3);
// place holder
p = (__m128i*)out;
_mm_store_si128(&p[0], t0);
_mm_store_si128(&p[1], t1);
_mm_store_si128(&p[2], t2);
_mm_store_si128(&p[3], t3);
}
Em primeiro lugar, carregamos os dois blocos para registos XMM. No entanto, quando fazemos isto, os inteiros de 64 bits dentro dos blocos ficam na ordem errada. Através da instrução PUNPCKLQDQ e PUNPCKHQDQ alteramos a ordem dos blocos de a0a1 a2a3 b0b1 b2b3 para a0b0 a1b1 a2b2 a3b3. Assim já podemos facilmente processar os dois blocos como se o estivessemos a fazer no caso acima, sem SSE2.
Ainda de notar é também o truque necessário para suportar o mesmo formato das subkeys: através de 2 loads e 4 shuffles, essencialmente extendemos a subchave a0 a1 a2 a3 para a0a0 a1a1 a2a2 a3a3.
Após as 72 iterações, temos de retornar os inteiros à ordem original, novamente com as instruções PUNPCKLQDQ e PUNPCKHQDQ. Após isto só nos resta armazenar as variáveis no buffer de saída.
Será que todo este trabalho vale a pena? Mais uma vez, sim. No modo CTR, passamos de 80 ciclos por byte (acima) para 26. Podemos ainda melhorar este número? Quebrando a compatibilidade com o formato das subchaves acima, podemos. Trocamos então 2 loads + 4 shuffles por 4 loads. Isto leva-nos ao resultado final de 19 ciclos por byte em 32 bit e 10 ciclos por byte em 64 bit. Isto não é óptimo, mas está bastante perto do óptimo num Core 2.
Para obter melhores desempenhos ainda, particularmente no modo CTR, poderíamos utilizar as variantes com blocos maiores do Threefish, e.g. 512 ou 1024 bits. Estas facilmente iriam parar aos 10 ou menos ciclos por byte em 32 bits. No entanto, blocos deste tamanho são incómodos para os tamanhos típicos de payloads cifradas - só para mensagens relativamente grandes é que faz sentido utilizar estas variantes.
O código utilizado para estas experiências está aqui. Não está bem comentado nem bem organizado - é apenas o resultado de experimentação. Divirtam-se.
