[解決済み] C++における循環シフト(rotate)操作のベストプラクティス

質問

C++では、左シフト、右シフトの演算子（<<と>>）がすでに利用可能です。 しかし、円形のシフトや回転の操作を行う方法が分かりませんでした。

左回転(")や右回転(")のような操作は、どのように行うことができますか？

ここで右回転を2回行う

Initial --> 1000 0011 0100 0010

になるはずです。

Final   --> 1010 0000 1101 0000

例があると助かります。

(編集者注：Cで回転を表現する多くの一般的な方法は、回転カウントがゼロの場合、未定義の動作に悩まされますし、単一の回転機械命令以上にコンパイルされます。 この質問の回答はベストプラクティスを文書化する必要があります)。

どのように解決するのですか?

以前のバージョンの 別の回転質問でこの答え を参照してください。

CとC++でrotateを表現する最もコンパイラに優しい方法は、未定義の振る舞いを避けることです。 John Regehr の実装です。 . 私はこれを、型の幅によって回転するように適応させました（たとえば 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 ));
}

のみならず、あらゆる符号なし整数型に対して動作します。 uint32_t のみならず、あらゆる符号なし整数型に対して動作するので、他のサイズのバージョンも作ることができます。

参照 また、C++11 テンプレート版 を含む）、安全性チェックの多い static_assert 型幅が2の累乗であることなど) これは、たとえば一部の 24 ビット DSP や 36 ビットメインフレームではそうではありません。

私は、明示的に回転幅を含む名前を持つラッパー用のバックエンドとしてのみ、このテンプレートを使用することをお勧めします。

整数進呈の規則では rotl_template(u16 & 0x11UL, 7) は16ビットではなく、32または64ビットの回転を行うことになります。 (の幅に依存する）。 unsigned long ). さらに uint16_t & uint16_t が昇格して signed int に昇格します。ただし、C++の整数昇格の規則により int よりも広くないプラットフォームでは uint16_t .

x86の場合 このバージョンでは は単一の rol r32, cl (または rol r32, imm8 ) を理解するコンパイラでは、コンパイラは x86 ローテートおよびシフト命令 が C ソースと同じようにシフト カウントをマスクすることをコンパイラーは知っているからです。

x86 では、この UB を回避するイディオムのコンパイラサポートは uint32_t x と unsigned int n は可変カウントシフトの場合です。

• clang: clang3.5以降、可変カウントのローテート、それ以前は複数のシフト+またはインスのために認識されるようになりました。
• gcc: gcc4.9 以降、可変長のローテートとして認識されるようになりました。 gcc5 以降では、wikipedia のバージョンでもブランチとマスクが最適化され、単に ror または rol 命令を使用します。
• icc ICC13以前から可変カウント回転に対応 . 一定カウントのローテートでは shld edi,edi,7 よりも遅く、より多くのバイトを消費します。 rol edi,7 は、一部の CPU (特に AMD、一部の Intel) では、BMI2 が利用できない場合 rorx eax,edi,25 を使用して MOV を保存します。
• MSVC: x86-64 CL19: 定数カウントのローテートのみ認識されます。 (wikipedia のイディオムは認識されますが、分岐と AND は最適化されません)。 このため _rotl / _rotr からの直訳 <intrin.h> を x86 (x86-64 を含む) 上で使用できるようになりました。

ARM 用の gcc は and r1, r1, #31 を使いますが、実際のローテートは1つの命令 : ror r0, r0, r1 . つまり、gccはrotate-countsが本質的にモジュール化されていることに気づいていないのです。 ARMのドキュメントにあるように "シフト長でROR。 n とあるように、32以上のRORは、シフト長 n-32 "です。 . ARMの左右シフトはカウントを飽和させるので、32以上のシフトはレジスタをクリアするため、gccはここで混乱するのだと思います。 (x86とは異なり、シフトは回転と同じようにカウントをマスクします)。 おそらく、rotateイディオムを認識する前に、AND命令が必要だと判断したのでしょう。

現在の x86 コンパイラーは、8 ビットおよび 16 ビットのローテートに対して可変カウントをマスクするために、おそらく ARM で AND を回避しないのと同じ理由で、まだ余分な命令を使用しています。 これは、どの x86-64 CPU でもパフォーマンスがローテート カウントに依存しないため、最適化が見落とされています。 (カウントのマスキングは 286 で導入されましたが、これは 286 が最近の CPU のように一定の遅延でシフトを処理するのではなく、反復的にシフトを処理するためです)。

ところで、コンパイラに 32-n を実行させるのを避けるためです。 (これは、コンパイル時に一定のカウントで最適化されます)。

面白いことに、ARM には専用のシフト/ローテート命令はなく、単に MOV に ソース オペランドは ROR モードでバレル シフターを通過します。 : mov r0, r0, ror r1 . つまり、ローテートはEOR命令などのレジスタ・ソース・オペランドに折り畳むことができるわけです。

には必ず符号なしを使用してください。 n と戻り値に符号なしを使用すること。そうしないと、rotate . (x86ターゲット用のgccは算術右シフトを行い、ゼロではなく符号ビットのコピーをシフトするため、次のような問題が発生します。 OR を実行したときに問題になります。 負の符号付き整数の右シフトは、C 言語では実装で定義された動作です)。

また シフト回数が符号なし型であることを確認してください。 というのも (-n)&31 は符号付きタイプでは 1 の補数または符号/倍数であり、符号なしまたは 2 の補数で得られるモジュラー 2^n とは異なるからです。 (Regehr のブログ記事へのコメント参照)。 unsigned int は、私が調べた全てのコンパイラで、どの幅の x . 他のいくつかの型はコンパイラによってはイディオム認識に負けるので、 単に x .

いくつかのコンパイラはローテート用のイントリンシックスを提供します。 これは、移植可能なバージョンがターゲットにしているコンパイラで良いコードを生成しない場合、inline-asm よりもはるかに優れています。 私が知っている限りでは、どのコンパイラにもクロスプラットフォームの intrinsics はありません。 これらは、x86 のオプションの一部です。

• Intel のドキュメントでは <immintrin.h> が提供する _rotl と _rotl64 直訳 であり、右シフトでも同じです。 MSVCでは <intrin.h> を要求しているのに対し、gccは <x86intrin.h> . また #ifdef は gcc と icc を区別します。 Clang 9.0にもありますが、それ以前はどこにも提供されていないようです。 という MSVC 互換性モード以外では -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . そして、それらのために生成される asm は最悪です (余分なマスクと CMOV)。
• MSVC。 _rotr8 と _rotr16 .
• gcc と icc (clang ではありません)。 <x86intrin.h> も提供します。 __rolb / __rorb 8bit の場合、左右に回転します。 __rolw / __rorw (16ビット)です。 __rold / __rord (32ビット)です。 __rolq / __rorq (64ビット、64ビットターゲットにのみ定義される)。 狭いローテートでは、実装は __builtin_ia32_rolhi または ...qi のコードでは、32ビットと64ビットの回転はshift/orで定義されています（UBに対する保護がないため）。 ia32intrin.h のコードは x86 用の gcc 上で動作しなければならないので、UB に対する保護はありません)。 GNU C にはクロスプラットフォームな __builtin_rotate のための関数がないように見えます。 __builtin_popcount (のように機能します（単一命令でなくても、ターゲットプラットフォームで最適なものに拡張されます）。 ほとんどの場合、イディオム認識から良いコードを得ることができます。

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

おそらく、非x86コンパイラにもイントリンシックがあるのでしょうが、このコミュニティ-wikiの回答を広げてすべてを含めるのはやめましょう。 (たぶん を参照してください。 ).

(この回答の古いバージョンでは、MSVC 固有のインライン asm (32 ビット x86 コードにのみ有効) を提案していましたが、または http://www.devx.com/tips/Tip/14043 を提案しました。 コメントはそれに対する返信です)。

インラインasmは多くの最適化を打ち負かす , 特にMSVCスタイルでは、入力の保存/読み込みを強制するため . 注意深く書かれた GNU C の inline-asm ローテートでは、コンパイル時定数シフトカウントのためにカウントを即時オペランドにすることができますが、インライン化後にシフトされる値もコンパイル時定数である場合は、まだ完全に最適化されないことがあります。 https://gcc.gnu.org/wiki/DontUseInlineAsm .