19

SQLite3からの次のコードに関するこの質問に触発されました：

 static int strlen30(const char *z){
    const char *z2 = z;
    while( *z2 ){ z2++; }
    return 0x3fffffff & (int)(z2 - z);
 }

これには、この関数がオーバーフローに役立つことを示すコミットメッセージが伴います。int

私はこの部分に特に興味があります：

 const char *z2 = z;
 while( *z2 ){ z2++; }

私にとって、このループはヌルターミネータを指すz2まで進みます。z2次にz2-z、文字列の長さを算出します。

strlen()この部分に使用して、次のように書き直してみませんか。

return 0x3fffffff & (int)(strlen(z));

なぜ代わりにループ+減算を使用するのstrlen()ですか？ループ+減算でできることとstrlen()できないことは何ですか？

4

2 に答える 2

7

彼らがそれを再実装しなければならなかった理由と、彼らがリターンタイプとしてint代わりにそれを選んだ理由をあなたに言うことはできません。size_tしかし、機能について：

/*
 ** Compute a string length that is limited to what can be stored in
 ** lower 30 bits of a 32-bit signed integer.
 */
static int strlen30(const char *z){
    const char *z2 = z;
    while( *z2 ){ z2++; }
    return 0x3fffffff & (int)(z2 - z);
}



切り捨て、タイプ、オーバーフローに関する標準リファレンス

この規格は、（ISO / IEC 14882：2003（E））3.9.1基本タイプ、4：に記載されています。

符号なしで宣言された符号なし整数は、2 nを法とする算術の法則に従うものとします。ここで、nは、その特定のサイズの整数の値表現のビット数です。41）

..。

41）：これは、結果の符号なし整数型で表現できない結果が、結果の符号なし整数型で表現できる最大値より1大きい数を法として減少するため、符号なし算術がオーバーフローしないことを意味します。

標準のその部分は、符号付き整数のオーバーフロー動作を定義していません。5.式を見ると、5.：

式の評価中に、結果が数学的に定義されていないか、そのタイプの表現可能な値の範囲内にない場合、そのような式が定数式（5.19）でない限り、動作は未定義です。この場合、プログラムは病気です。 -形成された。[注：C ++の既存の実装のほとんどは、整数のオーバーフローを無視します。ゼロによる除算、ゼロ除数を使用した剰余の処理、およびすべての浮動小数点の例外はマシンによって異なり、通常はライブラリ関数によって調整可能です。]

これまでのところオーバーフロー。

配列要素への2つのポインターの減算に関しては、5.7加法演算子、6。：

同じ配列オブジェクトの要素への2つのポインターを差し引くと、結果は2つの配列要素の添え字の差になります。結果の型は、実装定義の符号付き積分型です。このタイプは、ヘッダー（18.1）でptrdiff_tとして定義されているタイプと同じである必要があります。[...]

18.1を見て：

内容は、標準Cライブラリのヘッダーstddef.hと同じです。

それでは、C標準を見てみましょう（私はC99のコピーしか持っていませんが）、7.17一般的な定義：

  1. size_tおよびptrdiff_tに使用される型は、実装がこれを必要とするのに十分な大きさのオブジェクトをサポートしない限り、signedlongintの整数変換ランクよりも大きい整数変換ランクを持つべきではありません。

についてはこれ以上の保証はありませんptrdiff_t。次に、Annex E（ISO / IEC 9899：TC2のまま）は、signed long intの最小の大きさを示しますが、最大ではありません。

#define LONG_MAX +2147483647

さて、の最大値int、のリターンタイプはsqlite - strlen30()何ですか？もう一度C標準に転送するC++の引用をスキップしてみましょう。C99のAnnexEに、次の最小最大値が表示されintます。

#define INT_MAX +32767



切り捨て部分に関する要約

  1. 通常、 32ビット以上の。よりptrdiff_t大きくはありsigned longません。
  2. int少なくとも16ビット長と定義されています。
  3. したがって、2つのポインターを減算すると、プラットフォームに適合しない結果が生じる可能性が intあります。
  4. 上記から、符号付き型の場合、適合しない結果は未定義の動作をもたらすことを覚えています。
  5. strlen30ビット単位またはpointer-subtract-resultに適用されます：
          | 32 bit                         |
ptr_diff  |10111101111110011110111110011111| // could be even larger
&         |00111111111111111111111111111111| // == 3FFFFFFF<sub>16</sub>
          ----------------------------------
=         |00111101111110011110111110011111| // truncated

これにより、ポインター減算結果を最大値3FFFFFFF 16 = 1073741823 10に切り捨てることにより、定義されていない動作が防止されます。

ほとんどのマシンでは、最上位ビットのみが符号を示すため、なぜ彼らがその値を正確に選択したのかはわかりません。最小値を選択することは標準に対して理にかなっている可能性がありますINT_MAXが、1073741823は詳細を知らなくても実際に少し奇妙です（もちろん、関数の上のコメントが言うことを完全に実行します：30ビットに切り捨ててオーバーフローを防ぎます）。



「この部分にstrlen（）を使用してみませんか」

次のように書き直します。

return 0x3fffffff & (int)(strlen(z));

私の推測では、彼らは潜在的な間接参照を避けたかったのだと思います。もう1つの利点は、標準ライブラリへの依存関係が少ないことです。これは、ホストされていないアプリケーションを作成する場合に役立ちます。

ところで、上記の参照から次のように、(int)(strlen(z))ptrdiff_t>の最大値の場合、未定義の動作が発生する可能性があるINT_MAXため、(int)(0x3fffffff & strlen(z))より良いでしょう。

于 2011-07-27T11:22:27.463 に答える
1

なぜループ+減算としてstrlenを再実装するのですか？

本当の答えはプログラマーがそのように感じたということだと思いますが、別の潜在的な正当化/合理化は、ループがインラインである（strlen30それ自体がそうであるかどうかに関係なく）のに対し、多くのシステムstrlenではオフライン関数呼び出しです（例：Linux / GCC）。圧倒的多数のストリングが空または短い場合（長いストリングの「特別な」処理にもかかわらず）、一般的なケースではパフォーマンスがわずかに低下する可能性があります。その可能性だけで、コードを満足させるプログラマーのキータップを得るのに十分かもしれません。より長い文字列の場合、ライブラリstrlenは一般的に最適であると思います（アプリケーション固有の文字列の長さに関する知識が不足していることを考慮に入れて）。

strlen一部のシステムは、独自のインライン化、または空の1文字、場合によっては2文字の文字列をすばやくインラインチェックしてから呼び出すインライン/オフラインハイブリッドの恩恵を受けられない場合があります。

于 2011-07-28T01:15:25.747 に答える