operator - operadores bitwise c++

Rotación casi constante de tiempo que no viola los estándares

Question

Estoy pasando un mal rato tratando de encontrar una rotación de tiempo constante que no viole los estándares C / C ++.

El problema son los casos de borde / esquina, donde las operaciones se llaman en algoritmos y esos algoritmos no se pueden cambiar. 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 <class T> inline T rotlMod(T x, unsigned int y)
{
    y %= sizeof(T)*8;
    return T((x<<y) | (x>>(sizeof(T)*8-y)));
}

El ICC de Intel fue particularmente despiadado, y eliminó toda la llamada de función sin el y %= sizeof(T)*8 . Lo arreglamos hace unos años, pero dejamos las otras erratas en su 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 establece el comportamiento indefinido. Si agrego una marca para if(y == 0) ... , entonces el código no cumple con el requisito de tiempo constante.

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

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

EDITAR : por tiempo casi constante , me refiero a evitar la rama para que siempre se ejecuten las mismas instrucciones. No me preocupan los tiempos de microcódigo de la CPU. Si bien 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 proporcionaran un intrínseco para realizar la rotación en un tiempo casi constante . Incluso me conformaría con "realizar la rotación" ya que ni siquiera tienen eso.

Answer 1

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

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

podría mejorar la "eficiencia" del código al hacer que la llamada a do_something incondicional.

PD: Me pregunto si hay plataformas del mundo real en las que 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 manera arbitraria (no especificada), requeriría que la plataforma genere código adicional o impediría optimizaciones realmente útiles en escenarios no ideados?

Answer 2

He vinculado a esta respuesta los detalles completos de varias otras preguntas de "rotación", incluida esta pregunta de la wiki comunitaria , que debe mantenerse actualizada con las mejores prácticas.

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

John Regehr de la Universidad de Utah recomienda la versión "c" de sus intentos de hacer una función de rotación. Reemplacé su afirmación con un AND bit a bit, y descubrí que todavía se compila en un solo rotar insn.

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);  // e.g. 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) | (x>>( (-n)&mask ));
}

rotwidth_t rot_const(rotwidth_t x)
{
  return rotl(x, 7);
}

Esto podría estar basado en el tipo de x, pero probablemente tenga más sentido para un 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 es más importante que la variable de tamaño en la que almacena actualmente el valor.

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

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

Probé el mío con gcc.godbolt.org , con NDEBUG definido, para recuentos de rotación variables y de tiempo de compilación:

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

Incluso las versiones más recientes del compilador pueden manejar el código comúnmente proporcionado por wikipedia (incluido en la muestra de godbolt) sin generar una rama o cmov. La versión de John Regehr tiene la ventaja de evitar un comportamiento indefinido cuando el conteo de rotación es 0.

Hay algunas advertencias con rotaciones de 8 y 16 bits, pero los compiladores parecen estar bien con 32 o 64, cuando n es uint32_t . Vea los comentarios en el código en el enlace godbolt para algunas notas de mis pruebas de varios anchos de uint*_t . Esperemos que este modismo sea mejor reconocido por todos los compiladores para más combinaciones de anchos de tipo en el futuro. A veces, gcc emitirá inútilmente un AND AND en el recuento de rotación, aunque el x86 ISA define los rotar insns con ese AND exacto como 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 compilador debe poder organizar los valores para que estén en los registros correctos en primer lugar, lo que resulta en una sola rotación.

Con compiladores más antiguos, aún obtendrá el código ideal cuando el conteo de rotación es una constante de tiempo de compilación. Godbolt te permite probar con ARM como objetivo, y también utilizó una rotación allí. Con recuentos variables en compiladores más antiguos, obtienes un poco de hinchazón de código, pero no hay ramificaciones o problemas importantes de rendimiento, por lo que este idioma 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 emite un código óptimo para uint64_t . Sin embargo, noté que cambiar x a uint64_t mientras el tipo de retorno de la función todavía es uint32_t hace que gcc lo compile en cambios / o. Por lo tanto, tenga cuidado de emitir el resultado a 32 bits en un punto de secuencia separado, si desea que gire el 32b bajo de 64b. es decir, asignar el resultado a una variable de 64 bits, luego emitirlo / devolverlo. icc todavía genera un rotar insn, pero gcc y clang no lo hacen, por

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

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

Answer 3

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

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

Answer 4

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

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