Perto do tempo constante de rotação que não viola os padrões

Eu estou tendo um longo tempo tentando chegar a uma rotação constante de tempo que não viola os padrões C / C ++.

O problema são os casos de borda / canto, onde as operações são chamadas em algoritmos e esses algoritmos não podem ser alterados. Por exemplo, o seguinte é do Crypto ++ e executa o chicote de teste sob o GCC ubsan (ou seja, g++ fsanitize=undefined ):

 $ ./cryptest.exe v | grep runtime misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int' misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int' misc.h:625:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int' misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int' misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int' misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int' 

E o código em misc.h:637 :

 template  inline T rotlMod(T x, unsigned int y) { y %= sizeof(T)*8; return T((x<>(sizeof(T)*8-y))); } 

O ICC da Intel foi particularmente implacável e removeu toda a chamada de function sem o y %= sizeof(T)*8 . Nós corrigimos isso alguns anos atrás, mas deixamos a outra errata no local devido à falta de uma solução de tempo constante.

Há um ponto de dor restante. Quando y = 0 , obtenho uma condição onde 32 - y = 32 e configura o comportamento indefinido. Se eu adicionar uma verificação de if(y == 0) ... , o código não atenderá ao requisito de tempo constante.

Eu olhei para uma série de outras implementações, do kernel do Linux para outras bibliotecas criptográficas. Todos eles contêm o mesmo comportamento indefinido, então parece ser um beco sem saída.

Como posso executar a rotação em tempo quase constante com um número mínimo de instruções?

EDIT : por quase tempo constante , quero dizer evitar o ramo para as mesmas instruções são sempre executadas. Eu não estou preocupado com os tempos de microcódigo da CPU. Embora a previsão de ramificação possa ser ótima em x86 / x64, ela pode não funcionar tão bem em outras plataformas, como o embedded.


Nenhum desses truques seria necessário se o GCC ou o Clang fornecessem um método intrínseco para realizar a rotação em tempo quase constante . Eu até me contentaria em “executar a rotação”, já que eles nem têm isso.

Vinculei essa resposta a todos os detalhes de várias outras perguntas “rotativas”, incluindo essa questão do wiki da comunidade , que deve ser mantida atualizada com as práticas recomendadas.

Eu encontrei uma postagem no blog sobre esse problema, e parece que finalmente é um problema resolvido (com versões de compilador novas o suficiente).

John Regehr, da Universidade de Utah, recomenda a versão “c” de suas tentativas de realizar uma function de rotação. Eu substituí sua afirmação com um bit a bit AND, e descobri que ela ainda compila para um único insn rotativo.

 typedef uint32_t rotwidth_t; // parameterize for comparing compiler output with various sizes rotwidth_t rotl (rotwidth_t x, unsigned int n) { const unsigned int mask = (CHAR_BIT*sizeof(x)-1); // eg 31 assert ( (n<=mask) &&"rotate by type width or more"); n &= mask; // avoid undef behaviour with NDEBUG. 0 overhead for most types / compilers return (x<>( (-n)&mask )); } rotwidth_t rot_const(rotwidth_t x) { return rotl(x, 7); } 

Isso poderia ser modelado no tipo x, mas provavelmente faz mais sentido para uso real, ter a largura no nome da function (como rotl32 ). Normalmente, quando você está girando, sabe a largura desejada e isso é mais importante do que a variável de tamanho em que você está armazenando o valor.

Também certifique-se de usar apenas isso com tipos não assinados. O deslocamento para a direita dos tipos assinados faz uma mudança aritmética, mudando em bits de sinal. (É tecnicamente comportamento dependente da implementação, mas tudo usa o complemento de 2 agora.)

Pabigot, de forma independente, teve a mesma ideia antes de mim e postou no gibhub . Sua versão tem a verificação static_assert de C ++ para torná-lo um erro em tempo de compilation para usar uma contagem de rotação fora do intervalo para o tipo.

Eu testei o meu com o gcc.godbolt.org , com o NDEBUG definido, para contagens rotativas de variables ​​e compile-time-const:

  • gcc: código otimizado com gcc> = 4.9.0 , negativo sem ramificação + deslocamentos + ou com anterior.
    (compile-tempo const count: gcc 4.4.7 está bem)
  • clang: código ideal com clang> = 3.5.0 , negação sem ramificação + deslocamentos + ou com anterior.
    (compile-tempo const rotate count: clang 3.0 está bom)
  • icc 13: código ótimo.
    (compile-time const count com -march = native: gera shld $7, %edi, %edi mais lento shld $7, %edi, %edi . Fino sem -march=native )

Mesmo versões mais recentes do compilador podem manipular o código comum da wikipedia (incluído na amostra godbolt) sem gerar um branch ou cmov. A versão de John Regehr tem a vantagem de evitar um comportamento indefinido quando a contagem de rotação é 0.

Existem algumas advertências com rotações de 8 e 16 bits, mas os compiladores parecem bem com 32 ou 64, quando n é uint32_t . Veja os comentários no código no link godbolt para algumas notas do meu teste de várias larguras de uint*_t . Espero que este idioma seja melhor reconhecido por todos os compiladores para mais combinações de larguras de tipos no futuro. Às vezes, o gcc irá inutilmente emitir um AND ins na contagem de rotação, mesmo que o ISA x86 defina os insins de rotação com o exato E como primeiro passo.

“ótimo” significa tão eficiente quanto:

 # gcc 4.9.2 rotl(unsigned int, unsigned int): movl %edi, %eax movl %esi, %ecx roll %cl, %eax ret # rot_const(unsigned int): movl %edi, %eax roll $7, %eax ret 

Quando inlined, o compilador deve conseguir que os valores estejam nos registros corretos, resultando em apenas uma única rotação.

Com os compiladores antigos, você ainda obterá o código ideal quando a contagem de rotação for uma constante de tempo de compilation. Godbolt permite que você teste com o ARM como alvo, e também usa uma rotação lá. Com contagens variables ​​em compiladores mais antigos, você obtém um pouco de excesso de código, mas nenhuma ramificação ou problemas de desempenho importantes, portanto, esse idioma deve ser seguro para uso em geral.

BTW, eu modifiquei o original de John Regehr para usar CHAR_BIT * sizeof (x), e gcc / clang / icc emiti código ótimo para uint64_t também. No entanto, notei que mudar x para uint64_t enquanto o tipo de retorno da function ainda é uint32_t faz o gcc compilá-lo para deslocamentos / ou. Portanto, tenha cuidado para converter o resultado para 32bits em um ponto de sequência separado, se você quiser o baixo 32b de uma rotação de 64b. Por exemplo, atribua o resultado a uma variável de 64 bits e, em seguida, lance / retorne-o. icc ainda gera um insn rotativo, mas gcc e clang não, por

 // generates slow code: cast separately. uint32_t r = (uint32_t)( (x<>( -n&(CHAR_BIT*sizeof(x)-1) )) ); 

Se alguém puder testar isso com o MSVC, seria útil saber o que acontece lá.

Você pode adicionar uma operação de módulo adicional para evitar a mudança de 32 bits, mas não estou convencido de que isso seja mais rápido do que usar uma verificação if em conjunto com os preditores de ramificação.

 template  inline T rotlMod(T x, unsigned int y) { y %= sizeof(T)*8; return T((x<>((sizeof(T)*8-y) % (sizeof(T)*8)))); } 

Escrever a expressão como T((x<>(sizeof(T)*CHAR_BITS-y-1)>>1)) deve produzir um comportamento definido para todos os valores de y abaixo do tamanho de bit, assumindo T é um tipo sem sinal sem preenchimento.A menos que o compilador tenha um bom otimizador, o código resultante pode não ser tão bom quanto o que teria sido produzido por sua expressão original.Tendo que aturar difícil ler código desajeitado que irá produzir execução mais lenta em muitos compiladores é parte do preço do progresso, no entanto, desde um compilador hipermoderno que é dado

 if (y) do_something(); return T((x<>(sizeof(T)*8-y))); 

pode melhorar a “eficiência” do código, tornando a chamada para do_something incondicional.

PS: Eu gostaria de saber se existem plataformas do mundo real onde mudar a definição de shift-right de modo que x >> y quando y é precisamente igual ao tamanho de bit de x , seria necessário para gerar 0 ou x, mas poderia fazer a escolha de uma forma arbitrária (não especificada), exigiria que a plataforma gerasse código extra ou impediria otimizações genuinamente úteis em cenários não planejados?

Uma alternativa para o módulo extra é multiplicar por 0 ou 1 (graças a !! ):

 template  T rotlMod(T x, unsigned int y) { y %= sizeof(T) * 8; return T((x << y) | (x >> ((!!y) * (sizeof(T) * 8 - y))); }