コグノスケ

未来から過去へ表示(*) link

過去から未来へ表示

もっと前

2007年11月2日 >>> 2007年11月2日

もっと後

2007年11月2日

permalink

編集する

どうせやるならとことんやろう

今日はコードを2つ紹介（出典: ハッカーのたのしみ, Henry S. Warren, Jr., 滝沢ら訳）しますがどれもメチャクチャわかりづらいです。どちらも可読性なんかかなぐり捨ててとにかく効率を追った、ある意味潔いコードです。GNU netcatも中途半端に読みづらい変なコードを書くくらいなら、このくらいやって欲しかったなあ。

本についてですけど、前半はまだわかる気がしますが、後半はあまりにも頑張りすぎていて全然わからんです…。こういうコードを読んでいると、根性っていうか、ハッカー達の職人魂みたいなものを感じますよ。

ビット計算は奥は深い

さて1になっているビットを数える処理ですが、比較的わかりやすいコードを一つ例にとってみようと思います。


unsigned int x;
int count;

x = (x & 0x55555555) + ((x >>  1) & 0x55555555);
x = (x & 0x33333333) + ((x >>  2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >>  4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >>  8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);

count = x;

以上は32ビット用のコードです。ぱっと見だと、なんじゃこりゃ？って感じですね。このコードでは隣り合う桁を足していきます。最初は隣の1桁、次は2桁、次は4桁という風に倍々ゲームにしていきます。
では8ビットで検証してみます。

 x           = [   1][   0][   1][   1][   0][   1][   0][   0]
 1ビット毎の :     1,    0,    1,    1,    0,    1,    0,    0
 1の個数    :

 x           = [   1][   0][   1][   1][   0][   1][   0][   0]
 x>>1        =       [   1][   0][   1][   1][   0][   1][   0][   0]
 0x55        = [   0][   1][   0][   1][   0][   1][   0][   1]
 
 x&0x55      = [   0][   0][   0][   1][   0][   1][   0][   0]
 (x>>1)&0x55 =       [   1][   0][   1][   0][   0][   0][   0][   0]
 x           = [   0     1][   1     0][   0     1][   0     0]
 2ビット毎の :   1 + 0 = 1,  1 + 1 = 2,  0 + 1 = 1,  0 + 0 = 0
 1の個数    :

 x           = [   0     1][   1     0][   0     1][   0     0]
 x>>2        =             [   0     1][   1     0][   0     1][   0     0]
 0x33        = [   0][   0][   1][   1][   0][   0][   1][   1]

 x&0x33      = [   0     0][   1     0][   0     0][   0     0]
 (x>>2)&0x33 =             [   0     1][   0     0][   0     1][   0     0]
 x           = [   0     0     1     1][   0     0     0     1]
 4ビット毎の :               1 + 2 = 3,              1 + 0 = 1
 1の個数    :

 x           = [   0     0     1     1][   0     0     0     1]
 x>>4        =                         [   0     0     1     1][   0     0     0     1]
 0x0f        = [   0][   0][   0][   0][   1][   1][   1][   1]

 x&0x0f      = [   0     0     0     0][   0     0     0     1]
 (x>>4)&0x0f =                         [   0     0     1     1][   0     0     0     1]
 x           = [   0     0     0     0     0     1     0     0]
 8ビット毎の :                                       3 + 1 = 4
 1の個数    :
よってxには1が4つ含まれていた。

このように検証してみますと、1の数を倍々でまとめていって最後にはxの右端にビットの個数が集約されて計算されることが分かります。凄いんですけど、なんともトリッキーですねえ。

もう一つ似たようなコードで、パリティを求める処理が書けます。単純にパリティを求めるならば、全てのビットのxorを取れば良いのですが、この本では以下のように書きます。


unsigned int x, y;
int parity;

y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >> 16);

parity = y & 1;

以上は32ビット用のコードです。やはりこれもぱっと見では、なんじゃこりゃ？って感じです。これも2進数の1桁分, 2桁分, 4桁分…とxorを取っていって最後に32桁分のxorがyの右端に来るという仕掛けです。
では8ビットでの計算の結果をご覧下さい。

 x    = [   7][   6][   5][   4][   3][   2](   1)(   0)
                                                `-----| xor
 x>>1 =       [   7][   6][   5][   4][   3][   2](   1)[   0]
 
 y    = [   7][ 7,6][ 6,5][ 5,4][ 4,3]( 3,2)[ 2,1]( 1,0)
                                          `-----------| xor
 y>>2 =             [   7][ 7,6][ 6,5][ 5,4][ 4,3]( 3,2)[ 2,1][ 1,0]
 
 y    = [   7][ 7,6][ 7-5]( 7-4)[ 6-3][ 5-2][ 4-1]( 3-0)
                              `-----------------------| xor
 y>>4 =                         [   7][ 7,6][ 7-5]( 7-4)[ 6-3][ 5-2][ 4-1][ 3-0]
 
 y    = [   7][ 7,6][ 7-5][ 7-4][ 7-3][ 7-2][ 7-1]( 7-0)
                                                  ~~~~~~

このように検証してみますと、うまく各桁が一回ずつxorされるようにずらしながら計算していることがわかります。最後に yの右端に全てのビットのxorが計算されているのが見事ですね。

今時トリッキーなコードは嫌われる

現在はコンピュータが十分高速化していて、ソフトウェアの規模も大きくなっているため、速度より保守性を重視します。要は遅くて良いから誰もが読める普通のコードが求められます。どんなに速くても誰も理解できないトリッキーなコードは歓迎されません。

ただしそれは商業サーバー用のプログラムとかPC用のプログラムでの話。もっと特殊な分野、例えば究極の速度を求める超高性能計算（計算用のライブラリとか）や、ハードがショボショボな組み込み機器などは、無駄に使えるCPUやメモリがありません。というわけで、まだまだトリッキーなコードも出番があるんじゃないかなあ？

編集者:すずき(2007/11/06 20:17)