gcc で _BitScanForward & _BitScanReverse 互換関数、MSVC で __builtin_clz & __builtin_ctz 互換関数

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;
}