Mejores prácticas para operaciones de desplazamiento circular (rotación) en C++

Vea también una versión anterior de esta respuesta en otra pregunta de rotate con algunos detalles más sobre lo que asm gcc/clang produce para x86.

La forma más amigable para el compilador de expresar una rotación en C y C++ que evita cualquier Comportamiento Indefinido parece ser La implementación de John Regehr. Lo he adaptado para rotar por el ancho del tipo (por ejemplo, suponiendo que uint32_t es exactamente de 32 bits de ancho, aunque C/C++ solo garantiza que es al menos ese ancho. Traté de mantenerlo legible dejando fuera cheques para ese tipo de cosas).

#include <stdint.h>   // for uint32_t
#include <limits.h>   // for CHAR_BIT
// #define NDEBUG
#include <assert.h>

static inline uint32_t rotl32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);  // assumes width is a power of 2.

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n<<c) | (n>>( (-c)&mask ));
}

static inline uint32_t rotr32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n>>c) | (n<<( (-c)&mask ));
}

Funciona para cualquier tipo entero sin signo, no solo uint32_t, por lo que podría hacer versiones para otros tamaños.

Ver también una versión de plantilla de C++11 con muchas comprobaciones de seguridad (incluyendo un static_assert que el ancho del tipo es una potencia de 2), que no es el caso en algunos DSP de 24 bits o mainframes de 36 bits, por ejemplo.

Yo recomendaría solo usar la plantilla como un back-end para envoltorios con nombres que incluyan explícitamente el ancho de rotación. Las reglas de promoción de enteros significan que rotl_template(u16 & 0x11UL, 7) haría una rotación de 32 o 64 bits, no 16 (dependiendo del ancho de unsigned long). Even uint16_t & uint16_t es promovido a signed int por las reglas de promoción de enteros de C++, excepto en plataformas donde int no es más amplio que uint16_t.

En x86, esta versión inline a una sola rol r32, cl (o rol r32, imm8) con compiladores que grok, porque el compilador sabe que x86 girar y shift instructions enmascara el shift-count de la misma manera que lo hace la fuente C.

Soporte de compilador para este modismo que evita UB en x86, para uint32_t x y unsigned int n para cambios de conteo de variables:

• clang: reconocido para el recuento de variables gira desde clang3.5, múltiples turnos+o insns antes de eso.
• gcc: reconocido para el conteo de variables gira desde gcc4.9, múltiples turnos+o insns antes de eso. gcc5 y posteriores optimizan la rama y enmascaran en la wikipedia versión, también, usando solo una instrucción ror o rol para conteos de variables.
• icc: soportado para el conteo de variables gira desde ICC13 o anterior. El conteo constante gira usando shld edi,edi,7 que es más lento y toma más bytes que rol edi,7 en algunas CPU (especialmente AMD, pero también algunos Intel), cuando BMI2 no está disponible para rorx eax,edi,25 para guardar un MOV.
• MSVC: x86-64 CL19: Solo se reconoce para rotaciones de recuento constante. (El idioma de wikipedia es reconocido, pero la rama y Y no son optimizado lejos). Utilice el _rotl / _rotr intrínsecos de <intrin.h> en x86 (incluyendo x86-64).

Gcc para ARM utiliza un and r1, r1, #31 para el recuento de variables gira, pero todavía hace la rotación real con una sola instrucción: ror r0, r0, r1. Así que gcc no se da cuenta de que los recuentos de rotación son inherentemente modulares. Como dicen los documentos de ARM, " ROR con longitud de desplazamiento, n, más de 32 es lo mismo que ROR con longitud de desplazamienton-32". Creo que gcc se confunde aquí porque los cambios de izquierda / derecha en el BRAZO saturar la cuenta, por lo que un cambio de 32 o más borrará el registro. (A diferencia de x86, donde los cambios enmascaran la cuenta igual que gira). Probablemente decida que necesita una instrucción AND antes de reconocer el modismo rotate, debido a cómo funcionan los turnos no circulares en ese objetivo.

Los compiladores x86 actuales todavía usan una instrucción adicional para enmascarar un conteo de variables para rotaciones de 8 y 16 bits, probablemente por la misma razón que no evitan el AND on ARM. Esta es una optimización perdida, porque el rendimiento no depende de la cuenta de rotación en cualquier CPU x86-64. (El enmascaramiento de conteos se introdujo con 286 por razones de rendimiento porque manejaba los cambios iterativamente, no con latencia constante como las CPU modernas.)

POR cierto, prefiere rotar a la derecha para las rotaciones de recuento de variables, para evitar que el compilador haga 32-n implementar una rotación a la izquierda en arquitecturas como ARM y MIPS que solo proporcionan una rotación a la derecha. (Esto optimiza away con compile-time-constant contar.)

Dato curioso: ARM realmente no tiene instrucciones dedicadas de cambio / rotación, solo es MOV con el operando de origen pasando por el cambio de barril en modo ROR: mov r0, r0, ror r1. Así que una rotación puede plegarse en un operando de fuente de registro para una instrucción EOR o algo así.

Asegúrese de usar tipos sin signo para n y el valor devuelto, o de lo contrario no será un rotate. (gcc para objetivos x86 hace cambios aritméticos a la derecha, cambiando en copias de la signo-bit en lugar de ceros, lo que lleva a un problema cuando OR los dos valores cambiados juntos. Los desplazamientos a la derecha de enteros con signo negativo son comportamientos definidos por la implementación en C.)

También, asegúrese de que el recuento de cambios es un tipo sin signo, porque (-n)&31 con un tipo con signo podría ser el complemento de uno o signo/magnitud, y no lo mismo que el 2^n modular que se obtiene con un signo o complemento de dos. (Ver comentarios en la entrada del blog de Regehr). unsigned int funciona bien en todos los compiladores He mirado, para cada anchura de x. Algunos otros tipos en realidad vencen el reconocimiento de expresiones idiomáticas para algunos compiladores, así que no use el mismo tipo que x.

Algunos compiladores proporcionan intrínsecos para rotates, que es mucho mejor que inline-asm si la versión portable no genera buen código en el compilador al que se dirige. No hay intrínsecos multiplataforma para ningún compilador que yo sepa. Estas son algunas de las opciones de x86:

• Intel documentos que <immintrin.h> proporciona _rotl y _rotl64 intrínsecos, y lo mismo para el desplazamiento derecho. MSVC requiere <intrin.h>, mientras que gcc requiere <x86intrin.h>. An #ifdef se encarga de gcc vs. icc, pero clang no parece proporcionarlos en ningún lugar, excepto en el modo de compatibilidad MSVC con -fms-extensions -fms-compatibility -fms-compatibility-version=17.00. Y el asm que emite para ellos apesta (enmascaramiento extra y un CMOV).
• MSVC: _rotr8 y _rotr16.
• ccg e icc (no clang): <x86intrin.h> también proporciona __rolb/__rorb para 8 bits girar a la izquierda / derecha, __rolw/__rorw (16-bit), __rold/__rord (32-bit), __rolq/__rorq (64-bit, solo definido para objetivos de 64 bits). Para rotaciones estrechas, la implementación usa __builtin_ia32_rolhi o ...qi, pero las rotaciones de 32 y 64 bits se definen usando shift / or (sin protección contra UB, porque el código en ia32intrin.h solo tiene que trabajar en gcc para x86). GNU C parece no tener ninguna función multiplataforma __builtin_rotate como lo hace para __builtin_popcount (que se expande a lo que es óptimo en el objetivo plataforma, incluso si no es una sola instrucción). La mayoría de las veces obtienes buen código del reconocimiento de expresiones idiomáticas.

// For real use, probably use a rotate intrinsic for MSVC, or this idiom for other compilers.  This pattern of #ifdefs may be helpful
#if defined(__x86_64__) || defined(__i386__)

#ifdef __MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>  // Not just <immintrin.h> for compilers other than icc
#endif

uint32_t rotl32_x86_intrinsic(rotwidth_t x, unsigned n) {
  //return __builtin_ia32_rorhi(x, 7);  // 16-bit rotate, GNU C
  return _rotl(x, n);  // gcc, icc, msvc.  Intel-defined.
  //return __rold(x, n);  // gcc, icc.
  // can't find anything for clang
}
#endif

Presumiblemente algunos compiladores no-x86 también tienen intrínsecos, pero no expandamos esta respuesta de community-wiki para incluirlos a todos. (Tal vez hacer eso en la respuesta existente sobre intrínsecos).

(La versión antigua de esta respuesta sugirió asm inline específico para MSVC (que solo funciona para código x86 de 32 bits), o http://www.devx.com/tips/Tip/14043 para una versión C. Los comentarios responden a eso.)

Asm en línea derrota muchas optimizaciones, especialmente al estilo MSVC porque fuerza que las entradas sean almacenadas / recargadas . Una rotación de GNU C inline-asm cuidadosamente escrita permitiría que el conteo sea un operando inmediato para conteos de cambios constantes en tiempo de compilación, pero aún así no podría optimizarse completamente si el valor a ser desplazado es también una constante en tiempo de compilación después de en línea. https://gcc.gnu.org/wiki/DontUseInlineAsm.