[解決済み] C/C++の符号付きオーバーフローを検出する

質問

一見したところ、この質問は どのように整数のオーバーフローを検出するのですか？ と重複しているように見えますが、実際には大きく異なります。

符号なし整数のオーバーフローを検出するのは非常に簡単ですが、符号なし整数のオーバーフローを検出するのは 符号付き のオーバーフローを検出することは、ほとんどの人が考えているよりも実際には難しいことがわかりました。

最も明白で、しかし素朴な方法は、次のようなものでしょう。

int add(int lhs, int rhs)
{
 int sum = lhs + rhs;
 if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
  /* an overflow has occurred */
  abort();
 }
 return sum; 
}

これの問題は、C 規格によれば、符号付き整数のオーバーフローは 未定義の動作です。 言い換えれば、標準によれば、符号付きオーバーフローを引き起こした時点で、そのプログラムはヌルポインタをデリファレンスした場合と同様に無効となります。 したがって、未定義の動作を引き起こし、上記のポスト条件チェックの例のように、オーバーフローを事後的に検出しようとすることはできません。

上記のチェックが多くのコンパイラで動作する可能性があるとしても、それを当てにすることはできません。 実際、C 標準では符号付き整数のオーバーフローは未定義とされているため、一部のコンパイラー (GCC など) では を最適化し、上記のチェックを削除します。 最適化フラグが設定されている場合、コンパイラは符号付きオーバーフローが不可能であると仮定しているためです。 これは、オーバーフローをチェックする試みを完全に壊してしまいます。

そこで、オーバーフローをチェックするためのもう一つの可能な方法は、次のようになります。

int add(int lhs, int rhs)
{
 if (lhs >= 0 && rhs >= 0) {
  if (INT_MAX - lhs <= rhs) {
   /* overflow has occurred */
   abort();
  }
 }
 else if (lhs < 0 && rhs < 0) {
  if (lhs <= INT_MIN - rhs) {
   /* overflow has occurred */
   abort();
  }
 }

 return lhs + rhs;
}

これはより有望と思われます。なぜなら、そのような加算を実行してもオーバーフローが起こらないことを事前に確認するまでは、実際に2つの整数を加算することはないからです。 したがって、未定義の動作を引き起こすことはありません。

しかし、この解決策は残念ながら最初の解決策よりもずっと効率的ではありません。なぜなら、加算操作がうまくいくかどうかをテストするためだけに減算操作を実行しなければならないからです。 また、この (小さな) パフォーマンス ヒットを気にしないとしても、このソリューションが適切であるとはまだ完全に確信していません。 式 lhs <= INT_MIN - rhs という式は、符号付きオーバーフローが不可能であると考え、コンパイラーが最適化する可能性のある式の種類にそっくりです。

では、より良い解決策はあるのでしょうか？ 1) 未定義の動作を引き起こさないこと、2) オーバーフロー チェックを最適化する機会をコンパイラーに与えないことが保証されているものはありますか? 両方のオペランドを符号なしにキャストし、独自の 2 補数演算をロールバックしてチェックを実行することによってそれを行う何らかの方法があるかもしれないと考えていましたが、それを行う方法はよくわかりません。

どのように解決するのですか?

引き算を使ったアプローチは正しく、よく定義されています。コンパイラはそれを最適化することはできません。

より大きな整数型が利用可能な場合のもう一つの正しいアプローチは、より大きな型で演算を実行し、その結果を変換する際により小さな型に収まるかどうかをチェックすることです。

int sum(int a, int b)
{
    long long c;
    assert(LLONG_MAX>INT_MAX);
    c = (long long)a + b;
    if (c < INT_MIN || c > INT_MAX) abort();
    return c;
}

優れたコンパイラであれば、全体の足し算と if ステートメントを int -の大きさの足し算と単一の条件付きジャンプオンオーバーフローに変換し、実際には大きい方の足し算を実行することはありません。

編集してください。 Stephenが指摘したように、私は（あまり良くない）コンパイラであるgccがまともなasmを生成するのに苦労しています。生成されるコードはひどく遅いわけではありませんが、確かに最適とは言えません。もし誰かが gcc が正しいことをするようになるこのコードのバリエーションを知っているなら、私はそれを見るのが大好きです。