 |
||
| 連載第二回 「続・C/C++のビット操作」 | ||
| H19/04/20 | ||
| 第二回は前回からの続きになるでしょうか、お題は「C/C++のビット操作の限界を超える」ということでまいりましょう。 前回は基本的なビット操作についての話をしましたが、今回はそれ以外のビット操作についてと、基本的ビット操作をより高速に行う方法について話を進めていきます。 |
||
| 標準的なC/C++でサポートしているビット操作以外のものでまず挙げられるのが「ローテーション」です。これはシフト演算の一種で、シフトではじき出されたビットを反対側の端のビットに入れるものです。通常のシフト演算では、シフトによって空いたビットには"0"（算術右シフトの場合のみシフト前の値を保持）を入れますが、ここにはじき出された値が入るわけです。ビットがリング状に並んでいると仮定すると、ぐるぐる回っているように見えるため、このように言います。 ローテーションはアセンブラレベルでは非常に高速な命令のひとつで、最低クロックで実行してしまうCPUもあります。ところがこれを標準的なCで実現しようとするとどうなるでしょうか。ここでは左ローテーションを考えてみましょう。 unsigned int型の変数の内容を1ビット左ローテーションさせます。最上位ビット(bit31)が最下位ビット(bit0)に移動することになりますね。これをCで記述すると、 |
||
|
unsigned int nTmp = 0, nData = 0xf0f0f0f0; if(nData & 0x80000000) nTmp++; nData = (nData << 1) & nTmp;
|
||
|
というようになると思います。任意ビットローテーションに対応させれば、 |
||
|
nTmp = nData >> ( sizeof( unsigned int ) * 8 - ROTATE ); nData = ( nData << ROTATE ) | nTmp;
|
||
| となるでしょうか（"ROTATE"がローテーションビット数=0～31）。いくつかのステップを経て結果を得ています。 では、これをPentium CPUのアセンブラニモニックで記述してみましょう。 |
||
|
ROL nData, ROTATE
|
||
| これでおしましです。現在主流のPentium4 CPUだと、最短クロックで実行してしまいます（レーテンシ=1，スループット=0.5）。呆れるほど高速です。移植の問題が無いのであれば、ここは、 | ||
|
asm { ROL nData, ROTATE }
|
||
| と、インラインアセンブラを利用して記述することによって、驚くほどの高速化が可能です。 Pentium CPUには、RCRとRCLという、キャリーフラグを含めたローテート命令もあり、適切に使用すればさらに優位性を体感できるでしょう。 |
||
| さて、話がインラインアセンブラに及びましたので、ここから先はアセンブラレベル（機械語）の話になります。原則として、CPUはintel社およびAMD社のパソコン向け32bitCPUを対象とします。 | ||
| IA-32（Pentiumシリーズ等の32bitCPU命令体系）には、基本論理演算やシフト、ローテーションの他にもビットを対象にした命令が存在しています。また、Cでは意識することのないCPU内部のフラグもビット処理に関係してきます。一般的なアプリケーションでは通常使用されることは稀なものに、「パリティフラグ(PF)」というフラグがあります。このフラグは、演算の結果、下位8bit中の"1"になっているビットの数が偶数の場合、"1"になるものです。このフラグは自動的に立ってくれるので、1バイト中の"0"または"1"のビットが偶数か奇数かを判断する場合に、究極ともいえる高速性（実質的処理時間はゼロ）で処理が可能になります。もともとは通信データのエラーチェック用（パリティ）の機能と思われますが、暗号やごく単純な疑似乱数（二択）などにも応用が利くと思います。と、これは余談でした。 | ||
| IA-32になって登場した新しいシフト命令があります。それがSHLDとSHRDです。連結シフト命令と呼ばれるもので、指定したレジスタやメモリに別のレジスタを連結した状態でビットシフトを行うものです。見た目は最大64bitのシフトですが、シフトアウトした側は内容が変化しません。これはビットフィールドに分割された変数（レジスタorメモリ）に他の変数の値を順に設定していく場合などに便利です。これもCで等価ルーチンを書くと長く遅いプログラムになります。インラインアセンブラを使用してSHLD／SHRDを利用すると、最短クロックに近いレーテンシおよびスループットで実行してくれます。ちなみに指定できるシフト回数は最大31回です。 記述例を以下に示します。SHRD命令の第2オペランド（シフトアウト側）はレジスタである必要があるため、32bitレジスタEAXに変数の内容を一旦代入しています。（註：実際に応用される場合は、コンパイル後の実行オブジェクトのアセンブルソースを確認し、EAXレジスタの保存が必要な場合はPUSH EAX／POP EAXで挟む必要があります。） |
||
|
unsigned int nData = 0, nSrc1 = 0x00000005, nSrc2 = 0x000000aa; asm { MOV EAX, nSrc1 SHRD nData, EAX, 4 MOV EAX, nSrc2 SHRD nData, EAX, 8 } 実行結果：nData = 0xaa500000
|
||
| 次に、SHLD／SHRDと同様に追加されたビット操作命令にBSF／BSRがあります。これはビット検索命令というもので、レジスタ／メモリ内のビット"1"の最初に現れる位置を探します。bit0側からbit31側に向かって検索する(BSF)場合とその逆(BSR)で使い分けることができます。この命令はCPUレベルでもそこそこ時間がかかるのですが（おそらくというかほぼ確実にマイクロ命令実装）、等価プログラムを組むよりは確実に高速です。BSF命令のＣでの等価プログラムは、 | ||
|
unsigned int nData = 0x00804000, nBase = 0x00000001; int nCnt; for( nCnt = 0; nCnt < sizeof( nData ) * 8; nCnt++ ){ if( nData & nBase ) break; nBase <<= 1; }
|
||
| となるでしょうか。ループを抜けた時点での'nCnt'変数の値がビット位置になり、その値が変数ビットサイズ（この場合は'32'）に達していれば見つからなかった（つまり値がゼロ）ことになります。これがインラインアセンブラを使うと、 | ||
|
asm { BSF EAX, nData }
|
||
| となり、EAXレジスタにビットの位置が入り(0～31)、見つからなかった場合はゼロフラグ(ZF)が立ちます。ポイントはやはりループを構築しなくても良いということでしょう。パイプラインも乱れにくくなります。 | ||
| そしてもう一発。BT／BTS／BTR／BTC命令です。これら4つの命令はすべてビットテストを行うものです。BT命令は指定したレジスタ／メモリの指定したビットをキャリーフラグ(CF)にコピーするもので、BTS／BTR／BTC命令はそれぞれBT命令と同様の処理をした後、テストしたビットをセット(=1)／リセット(=0)／反転します。BT命令だけを見ると、TEST命令（論理ANDを仮実行する）＋ゼロフラグチェックが、BT命令＋キャリーフラグチェックに変わっただけのように感じられるかもしれませんが、そうではありません。それはテストするオペランドがメモリのときによくわかります。BT命令は第1オペランドがテストするレジスタ／メモリ、第2オペランドがビットオフセットなのですが、第1オペランドがメモリを指し、第2オペランドがレジスタの場合、以下のように記述することができます。 | ||
|
unsigned char * pData; char cBit = 0; asm { MOV EAX, 2000 BT pData, EAX SETC cBit } if ( cBit ) { ; *** ビットが1の場合の処理 *** } else { ; *** ビットが0の場合の処理 *** } |
||
|
ビットオフセットに"2000"という数値が指定されている所に注目です。これは決してエラーではなく、正常に実行されます。この場合、第1オペランドで指定されたメモリアドレスから最大-2Gbit～(2G-1)bitのビット列が並んでいるものとして認識されるのです。ですから、上のリストの場合は、pData+250バイト目のbit0がテストされることになります。実行速度はさすがに低速な部類に入りますが（Pentium4では乗算命令よりちょっと速い程度）、それでも等価ルーチンを考えればずっと高速です。ちなみに、SETC命令はキャリーフラグを指定したレジスタ／メモリの1バイトのbit0にコピーする命令です。それ以外のbitは0にリセットされるので、オペランドには0x00か0x01が入ることになります。 |
||
|
以上、IA-32命令独自のビット操作命令を中心にお話をいたしました。 |
||