- __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)
00000000 10110011 11111100 11010100
のとき、上位ビットの連続する 0 の数は8個なので、戻り値は 8 となる。
全ビットが0のときの戻り値は未定義。
- int __builtin_ctz(unsigned int)
00000000 10110011 11111100 11010100
のとき、下位ビットの連続する 0 の数は2個なので、戻り値は 2 となる。
全ビットが0のときの戻り値は未定義。
- unsigned char _BitScanForward(unsigned long *Index, unsigned long 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)
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; }
No comments:
Post a Comment