glibc の strlen は文字列範囲外を読むことで高速に計算する

strlen は、文字列の先頭から終端文字 \0 の直前までの byte 数を返す関数です。自分で実装するなら、1byte ずつ読んで \0 が見つかるまで数えるのが自然だと思います。glibc では、この探索を高速化するために、複数 byte をまとめて読み、ビット演算を使って終端文字を探しています。その読み込みは、文字列の範囲内に収まるとは限りません。

このように複数 byte をまとめて調べる仕組みは、「glibc strlen コードリーディング」(2020年)などでも解説されています。複数 byte を1つの整数として扱い、引き算とビット演算だけで 0 の有無を判定できるのが面白いところです。本記事でも、まずこのアルゴリズムが成り立つ理由を説明します。

その上で、2023年2月6日の変更で加わった工夫を見ていきます。この変更では、文字列の先頭より前から読み始めることで、先頭付近もまとめて処理しています。後半では、この読み方の理由と、余分に読んだ部分を除いて終端文字の位置を求める仕組みを説明します。

今回読むのは、glibc の string/strlen.c にある汎用 C 実装です。glibc にはアーキテクチャごとの実装もあり、例えば x86-64 には SSE2 や AVX2 などを使う実装があります。手元のプログラムが strlen を呼んだときに、必ず今回の C コードが動くわけではありません。

引数は、終端文字 \0 を含む有効な文字列を指しているものとします。

掲載する glibc の C コードは、リンク先から必要な部分を抜粋し、説明で扱う環境に合わせて分岐を省き、関数名や書式、定数の表記を変更したものです。必要な前提や glibc 内部の型、関数は、それぞれを使う箇所で説明します。

1byte ずつ読んで終端文字を探すだけなら、実装は簡単です。次のように書けます。

size_t strlen_byte(const char *str) {
    const char *p = str;
    while (*p != '\0')
        ++p;
    return p - str;
}

この実装では、1byte 読むたびに終端文字かを判定します。複数 byte をまとめて読み、その中に終端文字があるかを一度に判定できれば、探索ループの反復回数を減らせます。これが高速化の狙いです。

ここでは、1byte は 8bit、unsigned long は 64bit として考えます。この場合、unsigned long の値としてメモリを読むと、8byte を1つの整数として扱えます。以降では、このまとめて扱う 8byte をワードと呼びます。

ただし、文字列の先頭から単純に 8byte ずつ読むと問題が起こります。終端文字の位置がわからないので、その先の読めない領域までアクセスしてしまう可能性があるからです。

ページ境界とアラインメント

通常のプロセスの仮想メモリは、ページという単位で管理されています。ページごとに読み書きなどのアクセス権限が設定されているため、あるページを読めても、その隣のページも読めるとは限りません。ここでは、ページ境界が8の倍数のアドレスにあるものとします。

例えば、ページ境界が 0x1000 にあり、0x0ffd から文字列 "AB" が置かれているとします。

address   0x0ffd  0x0ffe  0x0fff | 0x1000 ...
value       'A'     'B'     '\0' | unreadable page
          ^ str                  ^ page boundary

0x0ffd から 8byte を読むと、終端文字の先にある読めないページまでアクセスしてしまいます。文字列自体は読み込み可能なページに収まっているのに、まとめて読むことで不正なアクセスが発生してしまうわけです。

ここで、8byte の読み込みを必ず8の倍数のアドレスから行うことにします。ページ境界も8の倍数なので、1回の読み込みがページをまたぐことはなくなります。上の例なら、0x0ff8 から 0x0fff までの読み込みは、手前のページ内に収まります。

このように、扱うデータの大きさなどに合わせてアドレスを揃えることを、アラインメントを合わせる、あるいはアラインすると言います。今回のワード境界は、8の倍数のアドレスです。

ただし、文字列の先頭がワード境界に揃っているとは限りません。まずは、次のワード境界に着くまで1byte ずつ読み、そこからまとめて読む方法を見ていきます。

なお、ページのアクセス権限と、C 言語で配列の範囲外を読んで良いかは別の話です。これについては、後半で先頭を切り下げて読む際に補足します。

2023年の変更前の実装では、次の3段階で終端文字を探しています。

1. ワード境界に着くまで1byte ずつ読む
2. ワード単位で終端文字を探す
3. 終端文字を含むワードの中を1byte ずつ調べ、位置を特定する

この順番に処理を見ていきます。

ワード境界まで1byte ずつ読む

まず、アドレスが8の倍数になるまで、1byte ずつ読み進めます。途中で終端文字が見つかったら、その時点で長さを返します。

const char *char_ptr;
for (char_ptr = str; ((uintptr_t)char_ptr & 7) != 0; ++char_ptr)
    if (*char_ptr == '\0')
        return char_ptr - str;

アドレスを整数として見たとき、& 7 は下位 3bit を取り出す操作です。これは8で割った余りと同じなので、((uintptr_t)char_ptr & 7) != 0 は、まだ8の倍数になっていないことを表します。

例えば str が 0x1003 なら、次のように読みます。図中の [1] は1byte の読み込みを表します。

address   0x1000   0x1003         0x1008
          |        ^ str          |
before             [1][1][1][1][1][ 8byte ... ]

ページ末尾に終端文字が置かれている場合も、次のページへ進む前に見つけられます。終端文字が見つからずにループを抜けたら、char_ptr はワード境界を指しているので、そこからは 8byte ずつ読めます。

ワードに 0 が含まれるかを調べる

次は、ワードを読み込んで、その中に終端文字が含まれるかを調べます。まずは char_ptr を unsigned long へのポインタに変換し、8byte を1つの整数として読み込みます。

const unsigned long *longword_ptr = (const unsigned long *)char_ptr;
unsigned long longword = *longword_ptr++;

読み込んだ値が longword です。longword_ptr は読み込み後に1つ進み、次のワードを指します。

この longword に対して1byte ずつ比較していては判定の回数が減らないので、次の式を使ってまとめて判定します。

(longword - 0x0101010101010101UL) & ~longword & 0x8080808080808080UL

0x0101010101010101 と 0x8080808080808080 は、0x01 と 0x80 をそれぞれ 8byte 分並べた定数です。

まずは1byte の値 b に対して、(b - 1) & ~b & 0x80 を計算するとどうなるかを見ます。以下の表では b - 1 も 8bit の範囲で考えます。

0 から1を引くと最上位 bit が立ちます。しかし、もともと 0x80 より大きい値でも同じ bit が立つので、~b との AND によってそれを除きます。最後に 0x80 との AND を取れば、調べたい bit だけが残ります。

つまり、1byte の値が 0 のときだけ 0x80 が残ります。

2byte に広げて考える

次は2byte の値 x に対して、(x - 0x0101) & ~x & 0x8080 を計算します。1byte の計算を2つまとめて行えそうですが、引き算は 16bit の整数に対して行われるので、byte の境界を越えて繰り下がりが発生する場合があります。

例えば x = 0x0100 の場合です。下位 byte の 0x00 から 0x01 を引くと、繰り下がりが発生します。そのため、上位 byte の 0x01 からは、定数の 0x01 に加えてさらに1が引かれます。

             x = 0x0100
    x - 0x0101 = 0xffff  (下位 16bit)
            ~x = 0xfeff  (下位 16bit)

0xffff & 0xfeff & 0x8080 = 0x8080

1byte ずつ計算した場合、0x00 の結果は 0x80、0x01 の結果は 0x00 でした。ところが2byte をまとめて計算すると、繰り下がりの影響で 0x01 にも 0x80 が残ります。0 でない byte にも印が付くことがあるのです。

ただし、0 が含まれるかどうかの判定には使えます。どの byte にも 0 がなければ、最下位から順に 0x01 を引いても byte をまたぐ繰り下がりは発生せず、結果は 0 になります。0 があれば、少なくとも下位側から見て最初の 0 の byte には正しく印が付きます。それより下位には 0 がなく、そこまでは byte をまたぐ繰り下がりが発生しないからです。

これは 8byte に広げても同じです。0 でない byte にも印が付く場合はありますが、ワードに 0 が含まれるときだけ式の結果が 0 でなくなります。この式で判定しながらワード単位で読み進めれば、終端文字を含むワードを見つけられます。

このように byte ごとの印を表すビット列を、以降ではマスクと呼びます。

終端文字の位置を特定する

終端文字を含むワードが見つかったので、あとはその中のどこにあるかを調べれば良いです。longword_ptr は次のワードを指しているため、1つ戻したアドレスを char へのポインタに変換し、cp とします。

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

先頭から順に確認し、最初に 0 が見つかったアドレスから str を引けば、文字列の長さが求まります。

これで、ワード境界に揃わない先頭部分と、終端文字を含む最後のワードだけを1byte ずつ調べ、それ以外はワード単位で探索できるようになりました。

size_t strlen_before(const char *str) {
    const char *char_ptr;
    const unsigned long *longword_ptr;
    const unsigned long lomagic = 0x0101010101010101UL;
    const unsigned long himagic = 0x8080808080808080UL;

    for (char_ptr = str; ((uintptr_t)char_ptr & 7) != 0; ++char_ptr)
        if (*char_ptr == '\0')
            return char_ptr - str;

    longword_ptr = (const unsigned long *)char_ptr;
    for (;;) {
        unsigned long longword = *longword_ptr++;
        if (((longword - lomagic) & ~longword & himagic) != 0) {
            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 (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;
        }
    }
}

残る2箇所もまとめて処理するのが、2023年の変更後の実装です。最初からワード単位で読み、終端文字の位置もビット演算で求めるようになりました。

まず型について確認すると、op_t はワードを読み込んで演算するための型で、汎用版では unsigned long に属性を付けたものです。find_t は検索結果のビット列を表す型で、ここでは op_t と同じ型です。今回の前提では、どちらも 64bit の符号なし整数として読めば良いです。

文字列の手前から読み始める

先ほどは、次のワード境界まで1byte ずつ読み進めていました。今度は、文字列の先頭より手前のワード境界から読むことで、この処理を省きます。

PTR_ALIGN_DOWN で、str のアドレスを8の倍数に切り下げ、そこから1ワードを読みます。例えば 0x1003 なら 0x1000 から読むことになります。元の先頭アドレスは、整数として s_int に残しておきます。

const uintptr_t s_int = (uintptr_t)str;
const op_t *word_ptr = (const op_t *)PTR_ALIGN_DOWN(str, sizeof(op_t));
op_t word = *word_ptr;

(uintptr_t)str & ~(uintptr_t)7

変更前との違いを並べると以下のようになります。

address   0x1000   0x1003         0x1008
          |        ^ str          |
before             [1][1][1][1][1][ 8byte ... ]
after     [         8byte        ][ 8byte ... ]

今度は文字列の先頭よりも前を読んでいますが、切り下げるのは最大 7byte です。ページ境界も8の倍数なので、この切り下げによって前のページへ移ることはありません。

これで最初からワードを読めますが、別の問題が生じます。str より前にある byte は文字列の一部ではないので、そこに 0 があっても終端文字として扱ってはいけません。最初のワードでは、0 の位置を求めたあと、文字列より前の部分を除く必要があります。

文字列より前の 0 の影響を除く

変更前と同じ式で 0 を検出し、マスクから文字列より前の部分を捨てれば良さそうに思えます。

ここでは、小さいアドレスの byte が整数の下位側に来る格納順序を前提にします。これをリトルエンディアンと呼びます。この場合、文字列より前の部分はマスクの下位側にあるので、その分だけ右にシフトすれば捨てられます。しかし、これではうまくいかない場合があります。

例えば、ワードの先頭 2byte が 0x00 0x01 で、str が2つ目の 0x01 を指している場合です。数値としての下位 2byte は、先ほど見た 0x0100 になります。

この 2byte だけで計算すると、変更前の式の結果は 0x8080 です。先頭の1byte を捨てても 0x8080 >> 8 = 0x0080 となり、繰り下がりによって 0x01 に付いた印が残ります。これでは、str の指す byte が 0 だと誤って判定してしまいます。

ワード全体に 0 があるかだけを調べる場合には問題ありませんでしたが、一部を捨てるなら、その部分の 0 が他の byte の判定に影響してはいけません。そこで使われているのが find_zero_all です。0 の byte に対応する場所だけを 0x80、それ以外を 0x00 にしたマスクを返します。

0 の byte だけに印を付ける

では、find_zero_all の実装を見てみます。今回のサイズでは以下の式になります。

find_t find_zero_all(op_t x) {
    const op_t m = 0x7f7f7f7f7f7f7f7fUL;
    return ~(((x & m) + m) | x | m);
}

定数 m は、0x7f を 8byte 分並べたものです。やや複雑に見えますが、各 byte が 0 でなければ最上位 bit を立て、最後に全体を反転する、という計算です。

まず x & m で各 byte の最上位 bit を落とします。これにより各 byte は最大でも 0x7f になるので、さらに 0x7f を足しても最大は 0xfe です。隣の byte への繰り上がりは発生しません。

この足し算では、もとの byte の下位 7bit が 0 なら結果は 0x7f、1以上なら結果は 0x80 以上になります。つまり、下位 7bit のどこかが 1 なら、結果の最上位 bit が立ちます。

これだけでは、もとの byte が 0x80 の場合も 0 と同じ扱いになってしまいます。そこで | x により、もともと最上位 bit が立っていた情報を戻します。この時点で、もとの byte が 0 でなければ最上位 bit が立ち、0 なら立たない状態になります。

最後の | m は、判定に使わない下位 7bit をすべて 1 にするためのものです。全体を ~ で反転すると、それらは 0 になり、もとの byte が 0 だった場所にだけ 0x80 が残ります。

各 byte の中だけで計算が完結しているので、隣の byte に余分な印が付くことはありません。文字列の手前が 0x00、先頭が 0x01 の場合も、対応する下位 2byte のマスクは 0x0080 になります。これなら1byte 分右にシフトすると 0 になり、文字列より前の 0 の影響を取り除けます。

文字列より前のマスクを捨てる

正確なマスクが作れたので、次は文字列より前の部分を捨てます。変更後の実装では、この2つの処理を次の行で行っています。

find_t mask = shift_find(find_zero_all(word), s_int);

shift_find は、今回の前提では次のような関数です。

find_t shift_find(find_t mask, uintptr_t s) {
    return mask >> (8 * (s % sizeof(op_t)));
}

s % sizeof(op_t) は、ワード境界から str まで何 byte あるかを表します。その byte 数を bit 数に直し、右にシフトして不要な部分を捨てています。

例えば、str = 0x1003 で文字列 "ABC" が置かれている場合を見ます。下の表は、メモリ上のアドレスが小さい順に上から並べています。マスクの列が find_zero_all の結果です。

一方、マスクを整数として16進数で書くと、上位 byte が左になります。今回は小さいアドレスの byte が下位側なので、0x1000 に対応する 0x80 が右端に来ます。

find_zero_all(word) = 0x0080000000000080
s_int % 8           = 3
mask                = 0x0080000000000080 >> 24
                    = 0x0000000080000000

0x1000 にあった 0 の印は捨てられ、0x1006 にある終端文字の印だけが残りました。シフト後のマスクでは、str に対応する byte が最下位に移っています。

マスクから終端文字の位置を求める

先頭より前の部分を捨てたマスクが 0 でなければ、最初のワード内に終端文字があります。その位置を求めるのが index_first です。

unsigned int index_first(find_t mask) {
    return __builtin_ctzl(mask) / 8;
}

__builtin_ctzl は、unsigned long の値について、最下位から連続する 0 の bit 数を返すコンパイラの組み込み関数です。言い換えると、最下位側で最初に立っている bit の位置がわかります。

先ほどの mask = 0x0000000080000000 では、下位の 31bit が 0 なので、__builtin_ctzl(mask) は 31 になります。これを8で整数除算すると 3 です。

各 byte の印は最上位 bit に付いているので、byte の位置が i なら、その bit の位置は 8 * i + 7 です。したがって8で割れば byte の位置に戻せます。既に str より前の部分をシフトして捨てているため、この 3 がそのまま文字列 "ABC" の長さになります。

この処理は、マスクが 0 でないときだけ行います。

if (mask != 0)
    return index_first(mask);

__builtin_ctzl に 0 を渡した場合の結果は未定義ですが、この条件によって 0 が渡ることはありません。マスクが 0 なら、最初に読んだワードのうち文字列に属する部分には終端文字がないので、次のワードを調べます。

次のワードに進む

最初のワードに終端文字がなければ、次のワードから順に読みます。

do
    word = *++word_ptr;
while (!has_zero(word));

has_zero は、ワードに 0 が含まれているかを返します。その中で呼ばれる find_zero_low は、変更前の実装で、ワードに 0 が含まれるかを判定していたビット演算を行います。

find_t find_zero_low(op_t x) {
    return (x - 0x0101010101010101UL) & ~x & 0x8080808080808080UL;
}

_Bool has_zero(op_t x) {
    return find_zero_low(x) != 0;
}

最初のワードを処理したあとは、文字列より前の部分を捨てる必要がありません。終端文字があるかどうかだけがわかれば良いので、変更前と同じ式が使えます。

find_zero_all でもこの判定はできますが、汎用 C 実装の式に含まれる演算が増えます。find_zero_low は引き算、NOT、AND 2回の計4回、find_zero_all は AND、足し算、OR 2回、NOT の計5回です。glibc のソースが参照している Bit Twiddling Hacks でも、前者は少ない演算で 0 の有無を判定する方法として紹介されています。

実際の命令数や速度はコンパイラや CPU にもよりますが、この使い分けは、必要な情報を少ない演算で得るためと考えられます。変更前の探索も、このループも、すべての byte を正確に判定する必要はないので、find_zero_low の式で十分なわけです。

終端文字を含むワードが見つかったら、そのワード内での位置を求め、文字列全体の長さに直して返します。

index_first_zero は、ワード中でメモリ上最初に現れる 0 の位置を返します。マスクを作る find_zero_low と、そのマスクから位置を求める index_first を組み合わせています。

unsigned int index_first_zero(op_t word) {
    return index_first(find_zero_low(word));
}

ここでも find_zero_low を使って良いのは、下位側から見て最初の 0 の位置は正しく求まるからです。繰り下がりによる余分な印は、それより上位側にしか付きません。リトルエンディアンでは下位側が小さいアドレスに対応するので、index_first でメモリ上最初に現れる 0 の位置を求められます。

index_first_zero(word) が返すのはワード内での byte の位置なので、ワードの先頭アドレスに足せば終端文字のアドレスになります。そこから元の str を引くと、文字列全体の長さが求まります。

return ((const char *)word_ptr) + index_first_zero(word) - str;

word_ptr を const char * にキャストしているのは、足し算をワード単位から byte 単位にするためです。

例えば str = 0x1003、終端文字を含むワードが 0x1010 から始まり、その中の 0 の位置が 2 なら、終端文字のアドレスは 0x1012 です。返す長さは 0x1012 - 0x1003 = 15 になります。

size_t strlen_after(const char *str) {
    const uintptr_t s_int = (uintptr_t)str;
    const op_t *word_ptr = (const op_t *)PTR_ALIGN_DOWN(str, sizeof(op_t));

    op_t word = *word_ptr;
    find_t mask = shift_find(find_zero_all(word), s_int);
    if (mask != 0)
        return index_first(mask);

    do
        word = *++word_ptr;
    while (!has_zero(word));

    return ((const char *)word_ptr) + index_first_zero(word) - str;
}

複数 byte を1つの整数として扱い、0 の有無をまとめて判定するのが、ワード単位の探索の工夫でした。2023年の変更では、さらに先頭を切り下げてワード単位で読み、ビット演算で終端文字の位置を求めることで、最初と最後の1byte ずつの処理をなくしています。

その際、途中の探索では 0 の有無、最後は最初の 0 の位置がわかれば十分ですが、先頭では範囲外の部分を捨てるために各 byte の判定が正しくなければいけません。同じ 0 の検出でも、必要な情報に応じて式を使い分けているわけです。

同じ一連の変更では、指定した範囲から byte を探す memchr にも、この読み方が取り入れられています。先頭を切り下げて読んで範囲外の判定を除き、最後もワード単位で調べてから、見つかった位置が指定範囲内にあるかを確認します。0 以外の値を探す場合も、各 byte と探したい値の XOR を取れば、一致した byte が 0 になるので、今回の 0 の検出を使えます。

また、strcpy も、strlen で長さを求めてから memcpy する実装から、終端文字を探しながらコピーする stpcpy を呼ぶ実装に変わっています。この stpcpy でも、途中はワード単位でコピーし、has_zero で終端文字を調べています。

C 言語を使っていると当たり前のように呼ぶ strlen に、2023年になってもこのような工夫が加わっているのは面白いですね。

Discussion