25

私は、C/C++ 標準に違反しない一定時間のローテーションを考え出すのにかなりの時間を費やしています。

問題は、操作がアルゴリズムで呼び出され、それらのアルゴリズムを変更できないエッジ/コーナー ケースです。たとえば、次はCrypto++からのもので、 GCC ubsan (つまりg++ fsanitize=undefined)でテスト ハーネスを実行します。

$ ./cryptest.exe v | grep runtime
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:625:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'

そしてのコードmisc.h:637：

template <class T> inline T rotlMod(T x, unsigned int y)
{
    y %= sizeof(T)*8;
    return T((x<<y) | (x>>(sizeof(T)*8-y)));
}

Intel の ICC は特に冷酷で、関数呼び出し全体を削除し、y %= sizeof(T)*8. 数年前に修正しましたが、一定時間の解決策がないため、他のエラータはそのまま残しました。

残りの 1 つの問題点があります。の場合y = 0、条件 where を取得32 - y = 32し、未定義の動作を設定します。のチェックを追加するとif(y == 0) ...、コードは一定時間の要件を満たせなくなります。

Linux カーネルから他の暗号化ライブラリまで、他の多くの実装を見てきました。それらはすべて同じ未定義の動作を含んでいるため、行き止まりのように見えます。

最小数の命令でほぼ一定の時間で回転を実行するにはどうすればよいですか?

編集：ほぼ一定の時間までに、分岐を回避することを意味するため、同じ命令が常に実行されます。CPU マイクロコードのタイミングについては心配していません。分岐予測は x86/x64 では優れているかもしれませんが、組み込みなどの他のプラットフォームではうまく機能しない可能性があります。

GCCまたはClangがほぼ一定の時間で回転を実行する組み込み関数を提供する場合、これらのトリックは必要ありません。彼らにはそれさえないので、私は「回転を実行する」ことさえ解決します。

4

4 に答える 4

12

このコミュニティ wiki の質問を含む、他のいくつかの「ローテーション」の質問の詳細については、この回答にリンクしました。これはベスト プラクティスで最新の状態に保つ必要があります。

この問題に関するブログ投稿を見つけましたが、最終的に解決された問題のようです (十分に新しいコンパイラ バージョンで)。

ユタ大学の John Regehr は、回転関数を作成する試みのバージョン "c" を推奨しています。彼のアサートをビットごとの AND に置き換えたところ、それでも単一の回転 insn にコンパイルされることがわかりました。

typedef uint32_t rotwidth_t;  // parameterize for comparing compiler output with various sizes

rotwidth_t rotl (rotwidth_t x, unsigned int n)
{
  const unsigned int mask = (CHAR_BIT*sizeof(x)-1);  // e.g. 31

  assert ( (n<=mask)  &&"rotate by type width or more");
  n &= mask;  // avoid undef behaviour with NDEBUG.  0 overhead for most types / compilers
  return (x<<n) | (x>>( (-n)&mask ));
}

rotwidth_t rot_const(rotwidth_t x)
{
  return rotl(x, 7);
}

これは x の型でテンプレート化できますが、実際の使用には、関数名に幅を持たせる方がおそらく理にかなっています ( のようにrotl32)。通常、回転しているときは、必要な幅を知っており、現在値を格納しているサイズ変数よりも重要です。

また、これは符号なしの型でのみ使用してください。符号付き型の右シフトは、算術シフトを行い、符号ビットをシフトします。(技術的には実装依存の動作ですが、現在はすべて 2 の補数を使用しています。)

Pabigot は、私より先に同じアイデアを独自に思いつき、gibhub に投稿しました。彼のバージョンには、C++ の static_assert チェックがあり、型の範囲外の回転カウントを使用するとコンパイル時エラーになります。

NDEBUG が定義された gcc.godbolt.org で、変数およびコンパイル時定数のローテーション カウントについてテストしました。

  • gcc: gcc >= 4.9.0、非分岐 neg+shifts+ またはそれ以前の最適なコード。
    (コンパイル時の const カウント: gcc 4.4.7 で問題ありません)
  • clang: clang >= 3.5.0、非分岐 neg+shifts+ またはそれ以前の最適なコード。
    (コンパイル時の const 回転数: clang 3.0 で問題ありません)
  • icc 13: 最適なコード。
    (-march=native を使用したコンパイル時の const カウント: 生成速度が遅くなりますshld $7, %edi, %edi。なしで問題ありません-march=native)

新しいコンパイラ バージョンでも、ブランチや cmov を生成せずに、ウィキペディア (godbolt サンプルに含まれる) から一般的に与えられたコードを処理できます。John Regehr のバージョンには、ローテーション カウントが 0 の場合に未定義の動作が回避されるという利点があります。

8 ビットと 16 ビットのローテーションにはいくつかの注意点がありますが、コンパイラは 32 ビットまたは 64 ビットでも問題ないようnですuint32_t。さまざまな幅のuint*_t. 願わくば、このイディオムがすべてのコンパイラでよりよく認識され、将来の型幅の組み合わせが増えることを願っています。ANDx86 ISA が最初のステップとして正確な AND を使用して回転 insn を定義している場合でも、gcc が回転カウントで insn を無用に発行することがあります。

「最適」とは、次のように効率的であることを意味します。

# gcc 4.9.2 rotl(unsigned int, unsigned int):
    movl    %edi, %eax
    movl    %esi, %ecx
    roll    %cl, %eax
    ret
# rot_const(unsigned int):
    movl    %edi, %eax
    roll    $7, %eax
    ret

インライン化されている場合、コンパイラは最初に値が正しいレジスタに配置されるように調整できる必要があり、その結果、ローテーションは 1 回だけになります。

古いコンパイラでは、ローテーション カウントがコンパイル時の定数である場合でも理想的なコードが得られます。Godbolt では ARM をターゲットとしてテストでき、そこでも回転を使用しました。古いコンパイラで可変カウントを使用すると、コードが少し肥大化しますが、分岐や重大なパフォーマンスの問題は発生しないため、このイディオムは一般的に安全に使用できます。

ところで、John Regehr のオリジナルを CHAR_BIT*sizeof(x) を使用するように変更し、gcc / clang / iccuint64_tも同様に最適なコードを出力しました。ただし、関数の戻り値の型xをwhile に変更すると、gcc がそれを shifts/or にコンパイルすることに気付きました。したがって、64b ローテーションの下位 32b が必要な場合は、別のシーケンス ポイントで結果を 32 ビットにキャストするように注意してください。つまり、結果を 64 ビット変数に代入し、キャストして返します。icc は依然としてローテーション insn を生成しますが、gcc と clang は生成しません。uint64_tuint32_t

// generates slow code: cast separately.
uint32_t r = (uint32_t)( (x<<n) | (x>>( -n&(CHAR_BIT*sizeof(x)-1) )) );

誰でもこれを MSVC でテストできる場合は、そこで何が起こるかを知っておくと役に立ちます。

于 2015-07-18T05:38:17.220 に答える