c - マジック ビットが glibc の strlen 関数をどのように改善しているか

Question

glibc の strlenのソースを調べていました。彼らはmagic bits文字列の長さを見つけるために使用しました。誰かがそれがどのように機能しているのか説明してください。ありがとうございました

Answer 1

この関数が文字列を調べているとしましょう -- コメントで説明されているように、一度に 4 バイト (4 バイトであると想定しlong intsています) -- 現在の「チャンク」は次のようになります。

'\3'     '\3'     '\0'     '\3'
00000011 00000011 00000000 00000011  (as a string: "\x03\x03\x00\x03")

strlen 関数は、この文字列の最初のゼロ バイトを探しているだけです。最初に、各 4 バイト チャンクについて、最初にこのショートカットをチェックすることによって、そこにゼロ バイトがあるかmagic_bitsどうかを判断します。この値に 4 バイトを追加します。

01111110 11111110 11111110 11111111

この値にゼロ以外のバイトを追加すると、キャリーが伝播することによって、ゼロでマークされたホールに 1 がオーバーフローします。チャンクの場合、次のようになります。

  11111111 111111          1 1111111   Carries
  00000011 00000011 00000000 00000011  Chunk
  01111110 11111110 11111110 11111111  Magic bits
+ -----------------------------------
  10000010 00000001 11111111 00000010
  ^      ^        ^        ^         

(穴ビットは でマークされてい^ます。)

そして、コメントから：

       /* Look at only the hole bits.  If any of the hole bits
          are unchanged, most likely one of the bytes was a
          zero.  */

チャンクにゼロがない場合、すべてのホール ビットが に設定され1ます。ただし、バイトが 0 であるため、伝播するキャリーによって 1 つのホール ビットが満たされませんでした。その後、それがどのバイトであったかを確認できます。

基本的に、検索を 1 バイトの比較に絞り込む前に、ビット加算マジックを 4 バイトのチャンクに適用してゼロをスキャンすることにより、strlen の計算を高速化します。