Ypsilon Scheme Systemのソースを読んでみた

Ypsilon Scheme Systemのソースを読んでみました。読んだのはobject_heap.cpp中のbytes_to_bucket関数、これだけです。

inline int
bytes_to_bucket(int x)
{
	int bucket = 0;
	if (x > 8) {
            x = x - 1;          	    /* (1) */
            x = x | (x >>  1);  	    /* (2) */
            x = x | (x >>  2);  	    /* (3) */
            x = x | (x >>  4);  	    /* (4) */
            x = x | (x >>  8);  	    /* (5) */
            x = x | (x >> 16);  	    /* (6) */
	    x = (x + 1) >> 4;	            /* (7) */
	    while (x) {
                bucket = bucket + 1;       
                x = x >> 1;
            }
	}
	return bucket;
}

はじめ、全然何やってるか分かりませんでした。
特に分かりにくい(2)〜(6)を良く見てみます。説明の為、xを2進数でabcdefghijklmnopqrとします。a〜rには0か1の数が入ります。

(2)の実行後は次の2つの数のorになります。

    abcdefghijklmnopqr
    0abcdefghijklmnopq

(3)の実行後は次の4つの数のorになります

    abcdefghijklmnopqr
    0abcdefghijklmnopq
    00abcdedfhijklmnop
    000abcdedfhijklmno

同様に進めていって(6)の実行後は次のような数を全部orを取った数になります。

    abcdefghijklmnopqr
    0abcdefghijklmnopq
    00abcdedfhijklmnop
    000abcdedfhijklmno
    0000abcdefghijklmn
    00000abcdefghijklm
    000000abcdefghijkl
    0000000abcdefghijk
    00000000abcdefghij
    000000000abcdefghi
           :
    00000000000000000a

つまり、(6)を実行した時点で元の数xの最も左で1になっているビットから右が全部1になった数になります。
さらに、(1)でxを1引いて(7)で1足しているところから、結局、やっていることはこんな感じです。

1. xが2の累乗(256とか1024とか)だとそのまま、そうじゃなければそれより大きい最小の2の累乗を求める。
2. その累乗を16で割る
3. 求めた累乗の数が2の何乗か求める。つまり、log2(x)を求める

条件分岐を使うともっと分かりやすく書けそうですが、パイプラインのストールが発生してもっと遅くなるなーって気がします。
最初からこんな感じだと先が長そうですが、得るものは大きそうです。