{C言語}{算法}{strlen()}{論組(ロンぐみ)言語(ゲンゴ)}{〈GNU C Library〉}{実装}{論組技巧}(7)

{GNU libc/string.h/strlen()函数の実装が素晴しい K#D657/645A}

https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=string/strlen.c;hb=2b778ceb4010c28d70de9b8eab20e8d88eed586b

接触元

日時失念

GNU glibcのソースコードに、本当にクールなコードを見つけました。ヘッダファイルのstring.hにあるstrlen関数です。

[...]

で、この関数は文字列を先頭から1文字ずつ検索して、longのワード長の境界にある文字を探すところから始まります。もし途中で文字列の終了を検知したら関数が終了して長さを返します。

for (
  char_ptr = str;
  ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
  ++char_ptr
  ) {
	if (*char_ptr == '\0') return char_ptr - str;
}

そして(まだズボンを降ろすのは早いですよ)、そのポイントから始まる文字列をunsigned long intの配列にキャストします。

longword_ptr = (unsigned long int *) char_ptr;

これでこの関数は、システムのアーキテクチャにより、4文字か8文字の単位でループを回せるようになりました。
文字列の終わりに遭遇した時に、long intの途中にNULLがあることを検知できるようにするため、
いくつかのマジックナンバーを持っています。

// 32 bit architecture
himagic = 0x80808080L;
lomagic = 0x01010101L;
  
// 64 bit architecture
if (sizeof (longword) > 4) {
	himagic = ((himagic << 16) << 16) | himagic;
	lomagic = ((lomagic << 16) << 16) | lomagic;
}

ここまでできたら、メインループが始まります。

for (;;) {
	longword = *longword_ptr++;

各ループにおいて、この関数は文字の組をlong変数にコピーして、文字列のポインタを進めます。
その後にマジックナンバーを適用します。もしビット演算の結果が0以外であれば、
最後のループのどこかにNULLがあることを示します(誤爆の可能性もあります)。

if (((longword - lomagic) & ~longword & himagic) != 0) 

もしNULLがあると思われる場合、キャストした文字列をcharの配列に戻して0の値を検索します。

// note we have to subtract 1 because the pointer is 1 step
// too far ahead
const char *cp = (const char *) (longword_ptr - 1);

// now just check which char is == NULL
if (cp[0] == 0) return cp - str;
if (cp[1] == 0) return cp - str + 1;
if (cp[2] == 0) return cp - str + 2;
if (cp[3] == 0) return cp - str + 3;

// 64 bit architecture
if (sizeof (longword) > 4) {
	if (cp[4] == 0) return cp - str + 4;
	if (cp[5] == 0) return cp - str + 5;
	if (cp[6] == 0) return cp - str + 6;
	if (cp[7] == 0) return cp - str + 7;
}

もしNULLがあれば、この文字列は終了で、ちょっと補正をして正しい長さを返します。
もしなければ誤爆だったことになり、ループを継続します。

直感的には、64ビットCPUならば、複雑なコードのほうが単純なコードよりも8倍高速なはず
[...]
私も自分でテストしました。
[...]
文字列が十分に長ければ、複雑な関数には意味があります。

(1){あれ}