高速strlen

以下はＣにおけるストリングの表現法から生じたもの。
Ｃのストリング表現は明示的な長さを持たず、末尾０によりあらわされる。
高速なstrlenの実現にはワード境界に至るまで1byteずつロード・検査し、
その中に０が含まれているかを調べればよい。
ビッグエンディアンであれば左から見て最初の０のバイトの添え字を戻す関数があればよい。

※本ではintが4byteの環境でした。私の環境では2byteなので、longを使用して本に合わせてあります。

テストプログラム

#include <stdio.h>

int zbytel( unsigned long );
long nlz2( unsigned long );

void main ( void )
{
	x = 0xffffff00;

         /* x:0xffffff00 zbytel( x ):3 */
	printf( " x:%lx, zbytel( x ):%d\n", x, zbytel( x ) );
}

単純な検査による最左の０のバイトの検出

・zbytel

int zbytel ( unsigned long x )
{
	if      ( ( x >> 24 ) == 0 )	{ return( 0 ); }
	else if ( ( x & 0x00ff0000 ) == 0 )	{ return( 1 ); }
	else if ( ( x & 0x0000ff00 ) == 0 )	{ return( 2 ); }
	else if ( ( x & 0x000000ff ) == 0 )	{ return( 3 ); }
	else				{ return( 4 ); }
}

分岐不要コードによるによる最左の０のバイトの検出

・zbytel

int zbytel ( unsigned long x )
{
	unsigned long y;
	long n;
	
	y = ( x & 0x7f7f7f7f ) + 0x7f7f7f7f;
	y = ~( y | x | 0x7f7f7f7f );
	n = nlz2( y ) >> 3;
	return( n );
}

nlzは
こちらのサイト
も参考にさせていただきました。

レジスタの中のビット列の左側 Leftmost bit から見て 0 が連続している数をNumber of Leading Zero (NLZ) という (0 の場合には 32 が返る)。
言い換えると 0 ビット目から見て 1 が最初に立っているビット位置のことである (1 がどこにも立っていない場合には 32 が返るとする)。
同様にレジスタの中のビット列の右側 Rightmost bit からみて 0がいくつ連続しているかを Number of Training Zero (NTZ) と呼ぶ。

例をあげると

NLZ こっちから 0 の数を数える → 0000010010000100
NTZ 0000010010000100 ← こっちから 0 の数を数える

32-bit 値 0000010010000100 の場合、 NLZ は 5 で、NTZ は 2 となる。

・nlz

long nlz2( unsigned long x )
{
	unsigned long y;
	long n = 32;
	
	y = x >> 16; if (y != 0){ n = n - 16 ; x = y; }
	y = x >>  8; if (y != 0){ n = n -  8 ; x = y; }
	y = x >>  4; if (y != 0){ n = n -  4 ; x = y; }
	y = x >>  2; if (y != 0){ n = n -  2 ; x = y; }
	y = x >>  1; if (y != 0){ return n - 2; }
 	return( n - x );
}

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか