crit-bit 木 (その3)

crit-bit木Ruby で試したものですが、 本番の C 言語の落ち穂拾いをしてみます。

D. J. Bernsteinqhasm の C 言語で記述したソースコードの中に含まれている crit-bit 木 の挿入手続きは次のような goto を使った箇所があります。 ここでは、 挿入したいキーと木の中から見つけた critical bits が一致する文字列で、 共通する接頭ビット列の長さを求めています。 newbyte へ一致するバイト数、 newotherbits へ最初の一致しないビットをゼロにしたビット反転マスク・パターンを求めます。

なお、 両方の文字列が一致するときを特別扱いして、 値 1 で手続きから戻ります。

  uint32 newbyte;
  uint32 newotherbits;
  for (newbyte = 0; newbyte < ulen; ++newbyte) {
    if (p[newbyte] != ubytes[newbyte]) {
      newotherbits = p[newbyte] ^ ubytes[newbyte];
      goto different_byte_found;
    }
  }
  if (p[newbyte] != 0) {
    newotherbits = p[newbyte];
    goto different_byte_found;
  }
  return 1; different_byte_found:
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;

ここで、 p は木から探した文字列の先頭バイトへのポインタで、 ubytes はキー文字列の先頭バイトへのポインタです。 両方の文字列ともに、 ゼロ終端であることを前提にしています。 ulen は ubytes が先頭を指している文字列のバイト長です。

これを goto を使わずに、 簡潔な記述に書き直してみます。 まず、 for ループを繰り返す条件は、 p と ubytes の両方の newbyte 位置のバイトが一致するときです。 ただし、 両方共ヌル文字で一致するときは、 両方の文字列が終端まで同一であることを意味しており、 手続きから戻らねばなりません。 そのとき、 newbyte は ulen になっています。

  for (newbyte = 0; p[newbyte] == ubytes[newbyte]; ++newbyte)
    if (newbyte == ulen)
      return 1;
  newotherbits = p[newbyte] ^ ubytes[newbyte]);
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;

コンパイラの最適化が賢いなら、 バイトの一致判定が排他的論理和結果のゼロ判定と等価であることを利用して、 4 行目を 1 行目に取り込んでくれるかもしれません。 中間変数が減り、 レジスタ割当が有利になるので、 そうなって欲しいところです。 ですが、 ここでは賢くないコンパイラのために、 可読性を落として、 手作業で最適化向けの記述にしておきます。

  for (newbyte = 0; (newotherbits = p[newbyte] ^ ubytes[newbyte]) == 0; ++newbyte)
    if (newbyte == ulen)
      return 1;
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;