strlen 小話

文字列の長さを計算するのに、まだ1バイトずつ 0x00 と比較しているの？

glibc の strlen はこういう実装らしい。たとえば4バイト(32ビット)を一度に判定して、その中に 0x00 が含まれるかを見て、そこから詳しく探すというやり方だ。

たとえば32ビットのレジスタなら、一度に4バイトを探せる。

uint32_t no_zero_byte(uint32_t v)
{
    const uint32_t himagic = 0x80808080;
    const uint32_t lomagic = 0x01010101;

    return ((v - lomagic) & ~v & himagic);
}

これは何なんだ？ 0x00 - 0x01 は桁借りを起こす。桁借りした後の値は 0xFF で、これは 0x00 を反転させたものと同じだ。この点を軸に計算が展開されている。

まず、文字列は連続したバイト列なので、そのまま32ビット値として読み出せる。それを v とする。

そして、あるバイトが 0x00 なら、そのバイトから 0x01 を引いたときに桁借りが発生するはずだ。それが (v - lomagic) だ。& ~v を使うと、桁借りが発生したかどうかを判定できる。

桁借りが最上位ビットを越える場合、そのバイトは 0xFF になる。そこで & himagic でもう一段判定する。

どうしても分からないなら、この具体例で

いま調べている文字列の4バイトが {0x11, 0x22, 0x33, 0x00} だとする。

すると、そのアドレスから直接32ビット値として読み出した v は 0x00332211 になる。

v - 0x01010101 = 0xFF322110

~v = 0xFFCCDDEE

(v - 0x01010101) & ~v = 0xFF000100     // 意味着发生了借位

FF000100 & 0x80808080 = 0x80000000 // 意为着发生了超出最高位的借位，也就是找到了0x00的位置，是第4个字节

いま調べている文字列の4バイトが {0x11, 0x22, 0x33, 0x44} の場合。

すると、そのアドレスから直接32ビット値として読み出した v は 0x44332211 になる。

v - 0x01010101 = 0x43322110

~v  = 0xBBCCDDEE

(v - 0x01010101) & ~v =  0x03000100

利点

一部のチップでは、if(v == 0x00) のような判定は非常に時間がかかる。このような単純なビット演算で値を求めれば、その問題を避けられる。