Meilleures pratiques pour les opérations de décalage circulaire (rotation) en C++

Question

Les opérateurs de décalage gauche et droit (<< et >>) sont déjà disponibles en C++. Cependant, je n'ai pas trouvé comment effectuer des opérations de décalage ou de rotation circulaire.

Comment effectuer des opérations telles que "Rotation à gauche" et "Rotation à droite" ?

Rotation à droite deux fois ici

Initial --> 1000 0011 0100 0010

devrait aboutir :

Final   --> 1010 0000 1101 0000

Un exemple serait utile.

(Note de l'éditeur : De nombreuses façons courantes d'exprimer les rotations en C présentent un comportement non défini si le nombre de rotations est égal à zéro, ou se compilent en plus d'une seule instruction machine de rotation. La réponse à cette question devrait documenter les meilleures pratiques).

Answer 1

Voir aussi une version antérieure de cette réponse à une autre question sur les rotations avec un peu plus de détails sur ce que asm gcc/clang produisent pour x86.

La façon la plus conviviale pour le compilateur d'exprimer une rotation en C et C++ qui évite tout comportement indéfini semble être la suivante La mise en œuvre de John Regehr . Je l'ai adapté pour qu'il pivote en fonction de la largeur du type (en utilisant des types à largeur fixe tels que uint32_t ).

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

Fonctionne pour tous les types d'entiers non signés, pas seulement pour les uint32_t Vous pouvez donc faire des versions pour d'autres tailles.

Véase également une version du modèle C++11 avec de nombreux contrôles de sécurité (dont un static_assert que la largeur du type est une puissance de 2) ce qui n'est pas le cas sur certains DSP 24 bits ou mainframes 36 bits, par exemple.

Je recommande de n'utiliser le modèle que pour les wrappers dont le nom inclut explicitement la largeur de rotation. Les règles de promotion des nombres entiers signifient que rotl_template(u16 & 0x11UL, 7) ferait une rotation de 32 ou 64 bits, pas de 16 (en fonction de la largeur de unsigned long ). Même uint16_t & uint16_t est promu à signed int par les règles de promotion des entiers du C++, sauf sur les plateformes où int n'est pas plus large que uint16_t .

---

Sur x86 cette version en un seul rol r32, cl (o rol r32, imm8 ) avec des compilateurs qui le maîtrisent, parce que le compilateur sait que Instructions de rotation et de décalage x86 masque le comptage des décalages de la même manière que la source C.

Le support du compilateur pour cet idiome d'évitement d'UB sur x86, pour uint32_t x y unsigned int n pour les postes à effectif variable :

• clang : reconnu pour les rotations à compte variable depuis clang3.5, plusieurs décalages+ou insns avant cela.
• gcc : reconnu pour les rotations à compte variable depuis gcc4.9 gcc5 et les versions ultérieures optimisent également la branche et le masque dans la version de wikipedia, en utilisant simplement un fichier de type ror o rol instruction pour les comptes variables.
• icc : supporté pour les rotations à nombre variable depuis ICC13 ou antérieur . Les rotations à nombre constant utilisent shld edi,edi,7 ce qui est plus lent et prend plus d'octets que l'option rol edi,7 sur certains processeurs (en particulier AMD, mais aussi certains Intel), lorsque BMI2 n'est pas disponible pour rorx eax,edi,25 pour sauvegarder un MOV.
• MSVC : x86-64 CL19 : Reconnu uniquement pour les rotations à compte constant. (L'idiome wikipedia est reconnu, mais la branche et le AND ne sont pas optimisés). Utiliser le _rotl / _rotr intrinsèques de <intrin.h> sur x86 (y compris x86-64).

gcc pour ARM utilise un and r1, r1, #31 pour les rotations à nombre variable, mais effectue toujours la rotation réelle avec une seule instruction. : ror r0, r0, r1 . Ainsi, gcc ne réalise pas que les rotate-counts sont intrinsèquement modulaires. Comme le dit la documentation ARM, "ROR avec la longueur de l'équipe, n plus de 32, c'est la même chose que ROR avec une longueur de décalage. n-32 " . Je pense que gcc est confus ici parce que les décalages gauche/droite sur ARM saturent le compte, donc un décalage de 32 ou plus effacera le registre. (Contrairement à x86, où les décalages masquent le compte de la même manière que les rotations). Il décide probablement qu'il a besoin d'une instruction AND avant de reconnaître l'idiome de rotation, à cause de la façon dont les décalages non circulaires fonctionnent sur cette cible.

Les compilateurs x86 actuels utilisent toujours une instruction supplémentaire pour masquer un compte variable pour les rotations de 8 et 16 bits, probablement pour la même raison qu'ils n'évitent pas le AND sur ARM. Il s'agit d'une optimisation manquée, car les performances ne dépendent pas du nombre de rotations sur les processeurs x86-64. (Le masquage des comptes a été introduit avec 286 pour des raisons de performances car il gérait les décalages de manière itérative, et non avec une latence constante comme les CPU modernes).

D'ailleurs, préférez rotate-right pour les rotations à nombre variable, pour éviter que le compilateur fasse 32-n pour implémenter une rotation à gauche sur des architectures comme ARM et MIPS qui ne fournissent qu'une rotation à droite. (Cela permet de s'affranchir des comptages constants en temps de compilation).

Fait amusant : ARM n'a pas vraiment d'instructions dédiées à shift/rotate, c'est juste MOV avec l'instruction opérande source passant par le barrel-shifter en mode ROR : mov r0, r0, ror r1 . Ainsi, une rotation peut se transformer en un opérande de registre-source pour une instruction EOR ou autre.

---

Veillez à utiliser des types non signés pour n et la valeur de retour, sinon ce ne sera pas une rotation. . (gcc pour les cibles x86 effectue des décalages arithmétiques vers la droite, en décalant des copies du bit de signe plutôt que des zéros. OR les deux valeurs décalées ensemble. Le décalage vers la droite d'entiers signés négatifs est un comportement défini par l'implémentation en C).

Aussi, s'assurer que le compte de décalage est un type non signé parce que (-n)&31 avec un type signé pourrait être un complément à un ou un signe/magnitude, et pas la même chose que le modulaire 2^n que vous obtenez avec un type non signé ou un complément à deux. (Voir les commentaires sur l'article du blog de Regehr). unsigned int fonctionne bien sur tous les compilateurs que j'ai examinés, pour chaque largeur de x . Certains autres types vont à l'encontre de la reconnaissance de l'idiome pour certains compilateurs, donc n'utilisez pas simplement le même type que x .

---

Certains compilateurs fournissent des intrinsèques pour les rotations. qui est bien meilleur qu'inline-asm si la version portable ne génère pas un bon code sur le compilateur que vous visez. Il n'y a pas d'intrinsèque multiplateforme pour aucun compilateur que je connaisse. Voici quelques-unes des options pour x86 :

• Les documents d'Intel qui <immintrin.h> fournit _rotl y _rotl64 intrinsèques et de même pour le changement de vitesse à droite. MSVC exige <intrin.h> alors que gcc requiert <x86intrin.h> . Un site #ifdef s'occupe de gcc vs. icc. Clang 9.0 l'a aussi, mais avant cela il ne semble pas les fournir nulle part, sauf en mode de compatibilité MSVC avec -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . Et l'asm qu'il émet pour eux craint (masquage supplémentaire et un CMOV).
• MSVC : _rotr8 y _rotr16 .

• gcc et icc (pas clang) : <x86intrin.h> fournit également __rolb / __rorb pour une rotation gauche/droite de 8 bits, __rolw / __rorw (16 bits), __rold / __rord (32 bits), __rolq / __rorq (64 bits, uniquement défini pour les cibles 64 bits). Pour les rotations étroites, l'implémentation utilise __builtin_ia32_rolhi o ...qi mais les rotations 32 et 64 bits sont définies à l'aide de shift/or (sans aucune protection contre UB, car le code de la section ia32intrin.h ne doit fonctionner que sur gcc pour x86). GNU C ne semble pas disposer d'un système multiplateforme. __builtin_rotate fonctionne de la même manière que pour __builtin_popcount (qui s'étend à tout ce qui est optimal sur la plateforme cible, même si ce n'est pas une seule instruction). La plupart du temps, vous obtenez un bon code grâce à la reconnaissance des idiomes.

  // 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

Vraisemblablement, certains compilateurs non-x86 ont aussi des intrinsèques, mais n'élargissons pas cette réponse de la communauté-wiki pour les inclure tous. (Peut-être le faire dans la réponse existante sur les intrinsèques ).

---

(L'ancienne version de cette réponse suggérait l'asm en ligne spécifique à MSVC (qui ne fonctionne que pour le code 32bit x86), ou bien http://www.devx.com/tips/Tip/14043 pour une version C. Les commentaires répondent à cela).

L'asm en ligne empêche de nombreuses optimisations , surtout le style MSVC, car il oblige les entrées à être stockées/rechargées . Une rotation GNU C inline-asm soigneusement écrite permettrait au compte d'être une opérande immédiate pour les comptes de décalage constants en temps de compilation, mais elle ne pourrait toujours pas être entièrement optimisée si la valeur à décaler est également une constante en temps de compilation après l'inlining. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Answer 2

Comme il s'agit de C++, utilisez une fonction en ligne :

template <typename INT> 
INT rol(INT val) {
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

Variante C++11 :

template <typename INT> 
constexpr INT rol(INT val) {
    static_assert(std::is_unsigned<INT>::value,
                  "Rotate Left only makes sense for unsigned types");
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

Answer 3

La plupart des compilateurs ont des intrinsèques pour cela. Visual Studio par exemple _rotr8, _rotr16

Answer 4

Définitivement :

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}

Answer 5

Que diriez-vous de quelque chose comme ça, en utilisant le jeu de bits standard ...

#include <bitset> 
#include <iostream> 

template <std::size_t N> 
inline void 
rotate(std::bitset<N>& b, unsigned m) 
{ 
   b = b << m | b >> (N-m); 
} 

int main() 
{ 
   std::bitset<8> b(15); 
   std::cout << b << '\n'; 
   rotate(b, 2); 
   std::cout << b << '\n'; 

   return 0;
}

HTH,