Pratiques exemplaires pour les opérations de rotation en C++

Voir aussi une version antérieure de cette réponse sur un autre pivoter question avec un peu plus de détails sur ce qu'il asm gcc/clang produire pour x86.

la façon la plus conviviale pour un compilateur d'exprimer une rotation en C et C++ qui évite tout comportement non défini semble être l'implémentation de John Regehr . Je l'ai adapté pour tourner par la largeur du type (par exemple en supposant que uint32_t est exactement 32 bits de large, bien que C / C++ garantit seulement qu'il est au moins que large. J'ai essayé de rester lisible en laissant des chèques pour ce genre de chose).

#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 n'importe quel type entier non signé, pas seulement uint32_t , donc vous pouvez faire des versions pour d'autres tailles.

voir aussi un C++11 Modèle version avec beaucoup de contrôles de sécurité (y compris un static_assert que la largeur du type est une puissance de 2) , ce qui n'est pas le cas sur certains DSPs 24 bits ou ordinateurs centraux 36 bits, par exemple.

Je ne recommande d'utiliser le modèle que comme arrière-plan pour les enveloppes avec des noms qui incluent explicitement la largeur de rotation. entier-règles de promotion signifie que rotl_template(u16 & 0x11UL, 7) ferait une rotation de 32 ou 64 bits, pas 16 (selon la largeur de unsigned long ). Même uint16_t & uint16_t est promu à signed int par les règles de promotion integer de C++, sauf sur plates-formes où int n'est pas plus large que uint16_t .

sur x86 , cette version inlines à un seul rol r32, cl (ou rol r32, imm8 ) avec des compilateurs qui grok il, parce que le compilateur sait que x86 tourner et instructions de changement masquer le changement-compter de la même façon que le C source fait.

soutien de compilateur pour cette UB-éviter idiome sur x86, pour uint32_t x et unsigned int n pour les postes à nombre variable:

• clang: reconnu pour les rotations à comptage variable depuis clang3.5, plusieurs équipes+ou insns avant cela.
• gcc: reconnu pour les rotations à comptage variable depuis gcc4.9 , postes multiples+ou insns avant cela. gcc5 et plus tard optimiser la branche et le masque dans la version Wikipédia, aussi, en utilisant juste un ror ou rol instructions pour les comptes variables.
• cpi: pris en charge pour la variable de comptage tourne depuis ICC13 ou plus tôt . Les rotations à comptage Constant utilisent shld edi,edi,7 qui est plus lent et prend plus d'octets que rol edi,7 sur certains CPU (en particulier AMD, mais aussi certains Intel), quand BMI2 n'est pas disponible pour rorx eax,edi,25 pour sauver un MOV.
• MSVC: x86-64 CL19: reconnu uniquement pour les rotations à nombre constant. (L'idiome Wikipédia est reconnu, mais la branche et et ne sont pas optimisés à l'extérieur). Utilisez le _rotl / _rotr intrinsics de <intrin.h> sur x86 (y compris x86-64).

gcc pour bras utilise un and r1, r1, #31 pour les rotations à nombre variable, mais fait encore la rotation réelle avec une seule instruction : ror r0, r0, r1 . Ainsi, gcc ne se rend pas compte que les comptes de rotation sont intrinsèquement modulaires. Comme le disent les docs ARM, "ROR with shift length, n , plus de 32 est le même que ROR avec la longueur de poste n-32 . Je pense que gcc se confond ici parce que les décalages gauche / droite sur le bras saturent le compte, donc un décalage de 32 ou plus va effacer le registre. (Contrairement à x86, où les changements masquent le même nombre que les rotations). Il décide probablement qu'il a besoin d'une instruction et avant de reconnaître l'idiome de rotation, en raison de la façon dont les quarts non-circulaires travaillent sur cette cible.

compilateurs x86 actuels utilisent toujours un instruction pour masquer un compte de variable pour 8 et 16-bit tourne, probablement pour la même raison qu'ils n'évitent pas le et sur le bras. Il s'agit d'une optimisation manquée, car la performance ne dépend pas du nombre de rotations sur N'importe quel CPU x86-64. (Le masquage des comptes a été introduit avec 286 pour des raisons de performance parce qu'il gérait les changements de façon itérative, pas avec une latence constante comme les CPU modernes.)

BTW, préfèrent tourner-à droite pour la variable-compte tourne, pour éviter de faire le compilateur faire 32-n pour implémenter une rotation à gauche sur des architectures comme ARM et MIPS qui ne fournissent qu'une rotation à droite. (Ceci optimise la suppression avec des comptes de compilations à temps constant.)

fait Amusant: le BRAS n'a pas vraiment dédié décalage/rotation des instructions, c'est juste MOV avec le source et l'opérande de passer par le barrel shifter en ROR mode : mov r0, r0, ror r1 . Ainsi une rotation peut se plier dans un opérande registre-source pour une instruction EOR ou quelque chose.

assurez-vous d'utiliser des types non signés pour n et la valeur de retour, Ou bien ce ne sera pas une rotation . (gcc pour les cibles x86 fait des déplacements arithmétiques à droite, le déplacement dans les copies du signe-bit plutôt que des zéros, conduisant à un problème quand vous OR les deux valeurs déplacées ensemble. Les déplacements vers la droite des entiers signés négatifs sont définis par la mise en œuvre du comportement en C.)

aussi, assurez-vous que le décompte des équipes est un type non signé , parce que (-n)&31 avec un type signé pourrait être son complément ou signe/magnitude, et pas le même que le 2^n modulaire que vous obtenez avec le complément non signé ou deux. (Voir les commentaires sur le blog de Regehr). unsigned int n'est bien sur chaque compilateur que j'ai regardé, pour chaque largeur de x . Certains autres types en fait battre l'idiom-reconnaissance pour certains compilateurs, donc ne pas utiliser le même type que x .

certains compilateurs fournissent des intrinsèques pour les rotations , ce qui est beaucoup mieux que inline-asm si la version portable ne génère pas de bon code sur le compilateur que vous ciblez. Il n'y a pas d'intrinsèques multiplateformes pour les compilateurs que je connais. Voici quelques-unes des options x86:

• documents Intel que <immintrin.h> fournit _rotl et _rotl64 intrinsics , idem pour le poste de droite. MSVC exige <intrin.h> , tandis que gcc exige <x86intrin.h> . Un #ifdef s'occupe de gcc vs. icc, mais clang ne semble pas les fournir n'importe où, 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 une CMOV).
• MSVC: _rotr8 et _rotr16 .
• de gcc et de la cci (pas de bruit): <x86intrin.h> fournit aussi __rolb / __rorb de 8 bits vers la gauche/droite, __rolw / __rorw (16-peu), __rold / __rord (32-peu), __rolq / __rorq (64-bits, défini uniquement pour les 64 bits cibles). Pour les rotations étroites, l'implémentation utilise __builtin_ia32_rolhi ou ...qi , mais les rotations 32 et 64 bits sont définies en utilisant shift/ or (sans protection contre UB, parce que le code dans ia32intrin.h n'a qu'à travailler sur gcc pour x86). GNU C ne semble pas avoir de fonctions multiplateformes __builtin_rotate comme il le fait pour __builtin_popcount (qui s'étend à tout ce qui est optimal sur la plate-forme cible, même si ce n'est pas une seule instruction). La plupart du temps, vous obtenez un bon code de la reconnaissance idiom.

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

probablement certains compilateurs non-x86 ont intrinsèques, aussi, mais ne pas étendre cette réponse de communauté-wiki pour les inclure tous. (Peut-être faire cela dans la réponse existante au sujet d'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 http://www.devx.com/tips/Tip/14043 pour une version C. Les commentaires répondent à cela.)

Inline asm Bat many optimisations , surtout de type MSVC car il force les entrées à être stockées/rechargées . Une rotation en ligne-asm GNU C soigneusement écrite permettrait d'avoir un comptage immédiat pour les décomptes de décalage en fonction de la constante de temps de compilation, mais elle ne pourrait pas encore être entièrement optimisée si la valeur à décaler est aussi une constante de temps de compilation après l'incrustation. https://gcc.gnu.org/wiki/DontUseInlineAsm .