Cerca del tiempo constante gira que no viola los estándares

Estoy teniendo un gran problema tratando de hacer una rotación de tiempo constante que no viole los estándares de C / C ++.

El problema son los casos de borde / esquina, donde las operaciones son llamadas en algoritmos y esos algoritmos no pueden ser cambiados. Por ejemplo, el siguiente es de Crypto ++ y ejecuta el arnés de prueba bajo GCC ubsan (es decir, 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' 

Y el código en misc.h:637 :

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

El ICC de Intel fue particularmente despiadado y eliminó toda la llamada de función sin y %= sizeof(T)*8 . Lo arreglamos hace unos años, pero dejamos la otra errata en el lugar debido a la falta de una solución de tiempo constante.

Hay un punto de dolor restante. Cuando y = 0 , obtengo una condición donde 32 - y = 32 , y configura el comportamiento indefinido. Si agrego un cheque para if(y == 0) ... , entonces el código no cumple con el requisito de tiempo constante.

He analizado varias otras implementaciones, desde el kernel de Linux hasta otras bibliotecas criptográficas. Todos ellos contienen el mismo comportamiento indefinido, por lo que parece ser un callejón sin salida.

¿Cómo puedo realizar la rotación en tiempo casi constante con un número mínimo de instrucciones?

EDITAR : cerca del tiempo constante , me refiero a evitar la twig por lo que siempre se ejecutan las mismas instrucciones. No estoy preocupado por los tiempos de microcódigo de la CPU. Mientras que la predicción de bifurcación puede ser excelente en x86 / x64, es posible que no funcione tan bien en otras plataformas, como las integradas.


Ninguno de estos trucos sería necesario si GCC o Clang proporcionan un intrínseco para realizar la rotación en tiempo casi constante . Incluso me conformaría con “realizar la rotación”, ya que ni siquiera tienen eso.

He vinculado esta respuesta con todos los detalles de varias otras preguntas de “rotación”, incluida esta pregunta wiki de la comunidad , que debe mantenerse actualizada con las mejores prácticas.

Encontré una publicación de blog sobre este tema, y ​​parece que finalmente es un problema resuelto (con versiones de comstackdor lo suficientemente nuevas).

John Regehr de la Universidad de Utah recomienda la versión “c” de sus bashs de hacer una función de rotación. Reemplacé su afirmación con un Y a nivel de bit, y encontré que todavía se comstack a una única entrada de rotación.

 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); } 

Esto podría ser una plantilla en el tipo de x, pero probablemente tenga más sentido para el uso real, tener el ancho en el nombre de la función (como rotl32 ). Por lo general, cuando está girando, sabe qué ancho desea, y eso importa más que la variable de tamaño en la que está almacenando el valor actualmente.

También asegúrese de usar esto solo con tipos sin firmar. El desplazamiento a la derecha de los tipos con signo realiza un desplazamiento aritmético, cambiando en bits de signo. (Es un comportamiento técnicamente dependiente de la implementación, pero ahora todo se basa en el complemento 2).

Pabigot independientemente tuvo la misma idea antes que yo, y la publicó en gibhub . Su versión tiene C ++ static_assert checking para que sea un error en tiempo de comstackción para usar un conteo de rotaciones fuera del rango para el tipo.

Probé la mía con gcc.godbolt.org , con NDEBUG definido, para conteos de rotación variables y en tiempo de comstackción:

  • gcc: código óptimo con gcc> = 4.9.0 , neg + shift sin ramificación + o con anterior.
    (conteo de tiempo en tiempo de comstackción: gcc 4.4.7 está bien)
  • clang: código óptimo con clang> = 3.5.0 , neg + shift sin ramificación + o con anterior.
    (tiempo de comstackción en tiempo de rotación cuenta: clang 3.0 está bien)
  • icc 13: código óptimo.
    (conteo de const de tiempo de comstackción con -march = native: genera shld $7, %edi, %edi más lento shld $7, %edi, %edi . Fine sin -march=native )

Incluso las versiones de comstackdor más nuevas pueden manejar el código común de wikipedia (incluido en la muestra de godbolt) sin generar una twig o cmov. La versión de John Regehr tiene la ventaja de evitar el comportamiento indefinido cuando el recuento de rotación es 0.

Hay algunas advertencias con rotaciones de 8 y 16 bits, pero los comstackdores parecen estar bien con 32 o 64, cuando n es uint32_t . Ver los comentarios en el código en el enlace de godbolt para algunas notas de mi prueba varios anchos de uint*_t . Esperemos que este modismo sea mejor reconocido por todos los comstackdores para obtener más combinaciones de anchos de tipos en el futuro. A veces, gcc emitirá inútilmente un AND en el recuento de rotación, aunque el x86 ISA define los insns de rotación con ese AND exacto como el primer paso.

“óptimo” significa tan eficiente como:

 # 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 

Cuando está en línea, el comstackdor debería ser capaz de organizar los valores para que estén en los registros correctos en el primer lugar, lo que da como resultado una sola rotación.

Con los comstackdores más antiguos, aún obtendrá el código ideal cuando el recuento de rotación sea una constante en tiempo de comstackción. Godbolt te permite probar con ARM como objective, y también usó una rotación allí. Con los conteos variables en los comstackdores más antiguos, obtienes un poco de hinchazón de código, pero sin ramificaciones ni problemas mayores de rendimiento, por lo que este modismo debería ser seguro de usar en general.

Por cierto, modifiqué el original de John Regehr para usar CHAR_BIT * sizeof (x), y gcc / clang / icc también emiten el código óptimo para uint64_t . Sin embargo, sí noté que al cambiar x a uint64_t mientras el tipo de devolución de función sigue siendo uint32_t hace que gcc lo compile en uint32_t / or. Así que tenga cuidado de arrojar el resultado a 32 bits en un punto de secuencia separado, si quiere que giren los 32b bajos de un 64b. es decir, asigne el resultado a una variable de 64 bits y luego vuélvalo a enviar / devolver. icc todavía genera una entrada rotar, pero gcc y clang no, por

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

Si alguien puede probar esto con MSVC, sería útil saber qué sucede allí.

Puede agregar una operación de módulo adicional para evitar el desplazamiento en 32 bits, pero no estoy seguro de que esto sea más rápido que usar una verificación if junto con los predictores de bifurcación.

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

Escribir la expresión como T((x< >(sizeof(T)*CHAR_BITS-y-1)>>1)) debería arrojar un comportamiento definido para todos los valores de y por debajo del tamaño del bit, asumiendo que T es un tipo sin signo sin relleno. A menos que el comstackdor tenga un buen optimizador, el código resultante puede no ser tan bueno como el que habría producido su expresión original. Tener que soportar un código difícil de leer que no funcionará la ejecución más lenta en muchos comstackdores es parte del precio del progreso, sin embargo, desde un comstackdor hipermoderno que se da

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

podría mejorar la “eficiencia” del código haciendo que la llamada a do_something incondicional.

PD: Me pregunto si hay plataformas del mundo real donde cambiar la definición de shift-right para que x >> y cuando y sea ​​exactamente igual al tamaño de bit de x , se requiera que produzca 0 o x, pero podría hacer la elección de una manera arbitraria (no especificada), ¿requeriría la plataforma generar código adicional o excluiría optimizaciones genuinamente útiles en escenarios no artificiales?

Una alternativa al módulo adicional es multiplicar por 0 o 1 (¡gracias a !! ):

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