gcc には __builtin_clz, __builtin_ctz という組み込み関数があり、MSVC(Microsoft Visual C++) には _BitScanForward, _BitScanReverse という組み込み関数がある。
とあるアプリを Windows でコンパイルしようとしたところ、gcc の場合は __builtin_clz, __builtin_ctz を使っているところがあった。MSVC にも同じような関数があったよなと思い、調べたことを以下の順番で書く。
- __builtin_clz, __builtin_ctz, _BitScanForward, _BitScanReverse の仕様
- MSVC の _BitScanForward, _BitScanReverse を使った __builtin_clz, __builtin_ctz 互換関数
- gcc の __builtin_clz, __builtin_ctz を使った _BitScanForward, _BitScanReverse 互換関数
- ついでに、gcc のインラインアセンブラを使った _BitScanForward, _BitScanReverse 互換関数
__builtin_clz, __builtin_ctz, _BitScanForward, _BitScanReverse の仕様
- int __builtin_clz(unsigned int)
gccの組み込み関数。
clz は Count Leading Zeros の略で、上位ビットの0の個数を返す。
例えば引数の値が二進数で
00000000 10110011 11111100 11010100 のとき、上位ビットの連続する 0 の数は8個なので、戻り値は 8 となる。
全ビットが0のときの戻り値は未定義。
- int __builtin_ctz(unsigned int)
gccの組み込み関数。
ctz は Count Trailing Zeros の略で、下位ビットの0の個数を返す。
例えば引数の値が二進数で
00000000 10110011 11111100 11010100 のとき、下位ビットの連続する 0 の数は2個なので、戻り値は 2 となる。
全ビットが0のときの戻り値は未定義。
- unsigned char _BitScanForward(unsigned long *Index, unsigned long Mask)
MSVCの組み込み関数。
下位ビットから値が1のビットを検索し、最初に見つかった値1のビットの位置を *Index に設定する。全ビットが0のときの戻り値は0で、それ以外の場合は非0値。
例えば引数 Mask の値が二進数で
00000000 10110011 11111100 11010100 のとき、下位ビットから見て最初の1の位置は2(最下位ビットの位置は0)なので、*Index に2を設定したあと、非0の値が戻り値となる。
下位から見て最初の1が見つかるまでのビットはすべて0なので、最初の1の位置は、下位の連続する0の個数と同じ値となる。したがって、__builtin_ctz を使えば _BitScanForward が実装できるし、_BitScanForward を使えば、__builtin_ctz を実装できる。
- unsigned char _BitScanReverse(unsigned long *Index, unsigned long Mask)
MSVCの組み込み関数。
上位ビットから値が1のビットを検索し、最初に見つかった値1のビットの位置を *Index に設定する。全ビットが0のときの戻り値は0で、それ以外の場合は非0値。
例えば引数 Mask の値が二進数で
00000000 10110011 11111100 11010100 のとき、上位ビットから見て最初の1の位置は23(最下位ビットの位置は0)なので、*Index に23を設定したあと、非0の値が戻り値となる。
上位から見て最初の1が見つかるまでのビットはすべて0なので、最初の1の位置は上位の連続する0の個数から簡単な計算で求まる。したがって、__builtin_clz を使えば _BitScanReverse が実装できるし、_BitScanReverse を使えば、__builtin_clz を実装できる。
MSVC の _BitScanForward, _BitScanReverse を使った __builtin_clz, __builtin_ctz 互換関数
#include <intrin.h>
int __builtin_clz(unsigned int n)
{
unsinged long index;
/* n が0のときの __builtin_clz の戻り値は未定義なので、
* _BitScanReverse の戻り値チェックは割愛する。
*/
_BitScanReverse(&index, n);
return 31 - index;
}
int __builtin_ctz(unsigned int n)
{
unsinged long index;
/* n が0のときの __builtin_ctz の戻り値は未定義なので、
* _BitScanForward の戻り値チェックは割愛する。
*/
_BitScanForward(&index, n);
return index;
}
gcc の __builtin_clz, __builtin_ctz を使った _BitScanForward, _BitScanReverse 互換関数
unsigned char inline _BitScanForward(unsigned int *Index, unsigned int Mask)
{
if (Mask) {
*Index = __builtin_ctz(Mask);
return 1;
} else {
/* 戻り値が0のとき、*Index がどうなるかは未定義。*/
return 0;
}
}
unsigned char inline _BitScanForward(unsigned int *Index, unsigned int Mask)
{
if (Mask) {
*Index = 31 - __builtin_clz(Mask);
return 1;
} else {
/* 戻り値が0のとき、*Index がどうなるかは未定義。*/
return 0;
}
}
gcc のインラインアセンブラを使った _BitScanForward, _BitScanReverse 互換関数
unsigned char inline _BitScanForward(unsigned int *Index, unsigned int Mask)
{
unsigned char rv;
__asm(
"bsfl %2, %0;"
"setne %1;"
: "=r"(*Index),"=r"(rv)
: "g"(Mask)
: "cc");
return rv;
}
unsigned char inline _BitScanReverse(unsigned int *Index, unsigned int Mask)
{
unsigned char rv;
__asm(
"bsrl %2, %0;"
"setne %1;"
: "=r"(*Index),"=r"(rv)
: "g"(Mask)
: "cc");
return rv;
}
