少し遅れましたが2回目です。glibcのstrlen()は早くなる工夫をしているという話。
strlen()は遅いからあんま使うなみたいなのは、また別の話で。
概要
glibc strlen コードリーディング - JUNのブログ
この方のブログに全部詳しく書いてあるのですが、自分理解用に書いてみます。なお説明を簡単にするため32bit環境（1word＝32bit）の前提で書きます。
glibc版のstrlen()は３手順で構成されていて、
- １．ロングワード境界まで1文字づつ進める
- ２．ロングワード単位でnullが含まれてないか調べる
- ３．nullが含まれていたら1文字づつ調べる
となっています。strlenを愚直に実装するなら、1文字づつ調べるので文字数回のループが必要ですが、glibc版は手順２．のとおり4文字づつ調べられるので、ループ数が1/4回（64bitなら1/8回）で済む。実際、ブログの方が計測した結果64bitで10倍くらい早かったようです。
ただ、手順２．の中でbit演算を何回も実行してるので、それ込みで何で10倍も速いのかよく分かってないです。単純にbit演算が早いって事だけかもしれない。
やってみる
手順１と３は分かり易いので、２．について書いてみます。
ロングワード単位となってますが、結局１バイトに対するbit演算を４バイト一気になってるだけなので、１バイト分だけ考えます。null（＝00000000）と、それ以外を見分けたい。大文字Z（＝0x5A）で試します。
himagic = 0x80808080L; lomagic = 0x01010101L; for (;;) { longword = *longword_ptr++; if (((longword - lomagic) & ~longword & himagic) != 0) { }
上のif文が真なら、つまり「longword - lomagic」と「~longword & himagic」で同じbitが立っていれば、このロングワードにnullが含まれている事になります。
$ man ascii 8進 10進 16進 文字 8進 10進 16進 文字 000 0 00 NUL '\0' (ヌル文字) 100 64 40 @ 001 1 01 SOH (ヘッダー開始) 101 65 41 A (snip) 032 26 1A SUB (置換) 132 90 5A Z (snip) 077 63 3F ? 177 127 7F DEL
まず「longword - lomagic」。Zは 0x5A = 01011010 なので、01011010 - 00000001 = 01011001。nullは 00000000なので、00000000 - 00000001 = 11111111。続いて「~longword & himagic」は、~01011010 = 10100101、10100101 & 10000000 = 10000000。nullは ~00000000 = 11111111、11111111 & 10000000 = 10000000。これをif文に代入すると、確かに求めたい結果になりました。
- Z ：01011001 & 10000000 ＝ 0
- null：11111111 & 10000000 ≠ 0
ポイント
0x80以下（10000000以下）について考えると、「longword - 00000001」は最上位bitが0になります。一方、「~longword & 1000000」は最上位bitのみが1になります。つまり、&を取ると0 & 1 = 0になりますね。
次に0x81以上（10000001以上）について考える（文字コードって7Fまででは無い…？）と、今度は逆で「longword - 00000001」は最上位bitが1、「~longword & 1000000」は「~longword 」は最上位bitを含めて全て0になります。つまり、&を取ると1 & 0 = 0。
という訳で、null以外を仕分けられました。「バイト内に1つ以上1が含まれている」というのを、こうやって検出するんですねー、すごい。
なんか、工夫すれば汎用的になりそう？例えば0xFFだけを仕分けたい場合や、他にもそれ以外の任意の値とか。bitの性質（？）を理解出来ればこの辺すらすら出来そうだけど数学脳がないのでむずい。ちょっと考えてみる。
とりあえず以上です
