C++ での循環シフト (回転) 操作のベストプラクティス

asm gcc/clang が x86 用に生成するものについての詳細を含む、別のローテーションの質問に関するこの回答の以前のバージョンも参照してください。

未定義の動作を回避する、C および C++ でローテーションを表現する最もコンパイラーフレンドリーな方法は、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 だけでなく、任意の符号なし整数型で機能します、他のサイズのバージョンを作成できます。

多くの安全性チェック (static_assert を含む) を備えた C++11 テンプレートバージョンも参照してください。タイプ幅が 2 のべき乗であること)

テンプレートは、回転幅を明示的に含む名前を持つラッパーのバックエンドとしてのみ使用することをお勧めします。 整数昇格規則は rotl_template(u16 & 0x11UL, 7) を意味します 16 ではなく、32 ビットまたは 64 ビットのローテーションを行います (unsigned long の幅に応じて）。 uint16_t & uint16_t でも signed int に昇格 int のプラットフォームを除き、C++ の整数昇格規則によります。 uint16_t より広くない .

x86 の場合 、このバージョンは単一の rol r32, cl にインライン化されます (または rol r32, imm8 ) それを grok するコンパイラを使用します。コンパイラは、x86 の回転命令とシフト命令が C ソースと同じようにシフトカウントをマスクすることを認識しているためです。

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

clang:clang3.5 以降の可変カウントローテーション、それ以前の複数のシフト+または insns で認識されます。
gcc:gcc4.9 以降、可変カウントローテーション、複数のシフト+またはその前の insns で認識されます。 gcc5 以降では、ror のみを使用して、ウィキペディアバージョンでもブランチとマスクを最適化します。または rol 可変カウントの指示。
icc:ICC13 以前から可変カウントローテーションでサポートされています。定数カウントのローテーションでは shld edi,edi,7 を使用しますこれは遅く、rol edi,7 よりも多くのバイトを必要とします一部の CPU (特に AMD、一部の Intel) では、rorx eax,edi,25 で BMI2 が利用できない場合 MOV を保存します。
MSVC:x86-64 CL19:定数カウントのローテーションでのみ認識されます。 (ウィキペディアのイディオムは認識されますが、ブランチと AND は最適化されていません)。 _rotl を使用 / _rotr <intrin.h> の組み込み関数 x86 (x86-64 を含む)。

ARM 用の gcc は and r1, r1, #31 を使用します可変カウントローテーション用ですが、実際のローテーションは 1 つの命令で行います :ror r0, r0, r1 .そのため、gcc は、回転カウントが本質的にモジュールであることを認識していません。 ARM ドキュメントが言うように、「シフト長の ROR、n 、32 以上はシフト長 n-32 の ROR と同じ「.ARMの左/右シフトはカウントを飽和させるため、gccはここで混乱すると思います.32以上のシフトはレジスタをクリアします.(x86とは異なり、シフトは回転と同じようにカウントをマスクします.おそらくそれを決定します.そのターゲットで非循環シフトがどのように機能するかにより、rotate イディオムを認識する前に AND 命令が必要です。

現在の x86 コンパイラは、おそらく ARM で AND を回避しないのと同じ理由で、8 ビットと 16 ビットのローテーションの変数カウントをマスクするために追加の命令を使用しています。パフォーマンスは x86-64 CPU のローテーションカウントに依存しないため、これは最適化の失敗です。 (カウントのマスキングは、パフォーマンス上の理由から 286 で導入されました。これは、最新の CPU のように一定の待ち時間ではなく、シフトを反復的に処理するためです。)

ところで、コンパイラが 32-n を実行するのを避けるために、可変カウントの回転には右回転を優先してください右回転のみを提供する ARM や MIPS などのアーキテクチャに左回転を実装します。 (これにより、コンパイル時の定数カウントが最適化されます。)

楽しい事実:ARM には専用のシフト/回転命令は実際にはありません。ROR モードでソースオペランドがバレルシフターを通過する MOV です:mov r0, r0, ror r1 .したがって、回転は、EOR 命令などのレジスタソースオペランドにフォールドできます。

n には必ず符号なしタイプを使用してくださいと戻り値、またはそれ以外の場合は回転しません . (x86 ターゲットの gcc は算術右シフトを行い、0 ではなく符号ビットのコピーをシフトするため、OR 2 つのシフトされた値が一緒に。負の符号付き整数の右シフトは、C の実装定義の動作です。)

また、シフトカウントが符号なしタイプであることを確認してください 、なぜなら (-n)&31 符号付きの型は、1 の補数または符号/大きさである可能性があり、符号なしまたは 2 の補数で得られるモジュラー 2^n とは異なります。 (Regehr のブログ投稿のコメントを参照してください)。 unsigned int x のすべての幅について、私が調べたすべてのコンパイラでうまくいきます .他のいくつかの型は、実際には一部のコンパイラのイディオム認識を無効にするため、x と同じ型を使用しないでください。 .

一部のコンパイラはローテーション用の組み込み関数を提供します これは、対象のコンパイラでポータブルバージョンが適切なコードを生成しない場合、inline-asm よりもはるかに優れています。私が知っているコンパイラには、クロスプラットフォームの組み込み関数はありません。これらは x86 オプションの一部です:

Intel は <immintrin.h> を文書化しています _rotl を提供と _rotl64 組み込み関数、および右シフトについても同じです。 MSVC には <intrin.h> が必要です、gcc では <x86intrin.h> が必要ですが、 . #ifdef gcc 対 icc を処理しますが、-fms-extensions -fms-compatibility -fms-compatibility-version=17.00 を使用した MSVC 互換モードを除いて、clang はどこにもそれらを提供していないようです .そして、それが発する asm は最悪です (余分なマスキングと CMOV)。
MSVC:_rotr8 と _rotr16 .
gcc および icc (clang ではない):<x86intrin.h> __rolb も提供 /__rorb 8 ビットの左/右回転の場合、__rolw /__rorw (16 ビット)、__rold /__rord (32 ビット)、__rolq /__rorq (64 ビット、64 ビットターゲットに対してのみ定義)。狭い回転の場合、実装は __builtin_ia32_rolhi を使用しますまたは ...qi 、ただし、32 ビットと 64 ビットのローテーションは shift/or を使用して定義されます (ia32intrin.h のコードのため、UB に対する保護はありません)。 x86 の gcc でのみ動作する必要があります)。 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 コードでのみ機能します)、または C バージョンの場合は http://www.devx.com/tips/Tip/14043 が提案されました。コメントはそれに返信しています。 .)

インライン asm は多くの最適化を無効にします 、特にMSVCスタイルは、入力の保存/再ロードを強制するためです。慎重に作成された GNU C inline-asm の回転により、カウントをコンパイル時定数シフトカウントの直接オペランドにすることができますが、シフトする値がコンパイル時定数でもある場合、完全に最適化することはできませんでした。インライン化後。 https://gcc.gnu.org/wiki/DontUseInlineAsm .

これは C++ であるため、インライン関数を使用します:

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

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

C++20 std::rotl と std::rotr

届きました！ http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html <bit> に追加する必要がありますヘッダー。

cppreference によると、使用方法は次のようになります:

#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t i = 0b00011101;
    std::cout << "i          = " << std::bitset<8>(i) << '\n';
    std::cout << "rotl(i,0)  = " << std::bitset<8>(std::rotl(i,0)) << '\n';
    std::cout << "rotl(i,1)  = " << std::bitset<8>(std::rotl(i,1)) << '\n';
    std::cout << "rotl(i,4)  = " << std::bitset<8>(std::rotl(i,4)) << '\n';
    std::cout << "rotl(i,9)  = " << std::bitset<8>(std::rotl(i,9)) << '\n';
    std::cout << "rotl(i,-1) = " << std::bitset<8>(std::rotl(i,-1)) << '\n';
}

出力を与える:

i          = 00011101
rotl(i,0)  = 00011101
rotl(i,1)  = 00111010
rotl(i,4)  = 11010001
rotl(i,9)  = 00111010
rotl(i,-1) = 10001110

GCC、GCC 9.1.0 with g++-9 -std=c++2a にサポートが到着したら試してみますまだサポートしていません。

提案には次のように書かれています:

そして：

std::popcount 1 ビットの数をカウントするためにも追加されました:32 ビット整数で設定されたビット数をカウントする方法は?

C++ での循環シフト (回転) 操作のベスト プラクティス

C++ での循環シフト (回転) 操作のベストプラクティス