GNU strlen を読む

2009-03-15 02:50

Hacker News でみかけた Glibc’s strlen implementation: Probably not what you’d guess というスレッドが面白かった。スレッドでは GNU の他に OpenBSD (べたな C, i386, x86-64) と Apple (SSE3 を使っている) にもリンクがあるんだけど、ここでは GNU strlen の実装についてだけ説明します。

実装

GNU strlen は文字列から long word 単位でおおまかに NUL っぽいものを探してから、バイト単位でこまかく探す、という方法をとっている。

strlen.c にある strlen は、トリッキーなところを丁寧にコメントで補っているせいもあってやや長い。まず、strlen の引数の str のアドレスが long word にそろっていない場合、最初の for ループにはいる。

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

このループはふつうに文字単位で回っていて、NUL でも抜けられる。ただ、さらに終了条件としてポインタのアドレスの下の桁も見ていることに注意してほしい。もし NUL がなくても、文字列の先頭が long word にそろった時点でこのループは終了してしまう。

次に、char* を long int* にキャストして himagic と lomagic という定数を定義している。

  longword_ptr = (unsigned long int *) char_ptr;

  /* ... */
  magic_bits = 0x7efefeffL;
  himagic = 0x80808080L;
  lomagic = 0x01010101L;

magic_bits は #if 0 の中でだけ使っている == 使っていないので無視していい。himagic は 0×80808080 で2進数だと

1000 0000 1000 0000 1000 0000 1000 0000

こう表せる。lomagic は 0×01010101 なので

0000 0001 0000 0001 0000 0001 0000 0001

こうだ。実装では long word が 32bit より長いマシンではこのパターンをもう一回くりかえし、64bit より上のマシンだと abort している。

ここから long word 単位のループにはいる。for 文直後のコメントは magic_bits 時代のものだと思う。

  for (;;)
    {
      /* ... */

      longword = *longword_ptr++;

      if (
#if 0
...
#else
          ((longword - lomagic) & himagic)
#endif
          != 0)
        {

たとえば “hi” だと longword - lomagic は

  h           i           NUL
  0110 1000   0110 1001   0000 0000   XXXX XXXX
- 0000 0001 | 0000 0001 | 0000 0001 | 0000 0001

  0110 0111   0110 0111   1111 1111   XXXX XXXX

NUL から1を引いたときに上から繰り下がって、NUL の桁の全ビットが立つ。X は未定義なのでここではスルーしてほしい。

これに himagic を & すると

  0110 0111   0110 0111   1111 1111   XXXX XXXX
& 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000

  0000 0000   0000 0000   1000 0000   XXXX XXXX

ここで結果が 0 にならない場合、longword のなかの文字のどれかが NUL である可能性があるので、if のなかで文字単位で探している。

        {
          const char *cp = (const char *) (longword_ptr - 1);

          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;
          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;
            }
        }

日本人としては、ループから if に入る条件が char の MSB が立たないことを期待しすぎていると思った。

感想

NUL 終端文字列の長さをとる処理はどうやっても O(n) だ。Joel Spolsky は NUL 終端文字列を「文字列を格納する最悪の方法のひとつ」と評しているし、文字列の長さは番兵で表現せずに別の場所にいれておいたほうがいいと思う。

とはいえ、計算上はどうしようもない問題でも、計算機上ではまだ工夫の余地があるというのは面白かった。教科書的にはアルゴリズムで O(n) の定数を削るよりもデータ構造を検討するべきなんだけど、これ libc ですからね。

Leave a Reply