Ganzzahlüberlauf in C: Standards und Compiler

Bearbeitet, um dank Carl Norum die richtige Standardreferenz aufzunehmen.

Der C-Standard besagt

Wenn ein außergewöhnlicher Zustand während der Auswertung eines Ausdrucks auftritt (d. h. wenn das Ergebnis nicht mathematisch definiert ist oder nicht im Bereich darstellbarer Werte für seinen Typ liegt), ist das Verhalten undefiniert.

Gibt es Compiler-Schalter, die bestimmte Verhaltensweisen bei Ganzzahlüberlauf garantieren? Ich möchte nasale Dämonen vermeiden. Insbesondere möchte ich den Compiler zwingen, bei Überlauf umzubrechen.

Nehmen wir der Eindeutigkeit halber den Standard C99 und den Compiler gcc an. Mich würden aber Antworten für andere Compiler (icc, cl) und andere Standards (C1x, C89) interessieren. Um die C/C++-Menge zu ärgern, würde ich sogar Antworten für C++0x, C++03 und C++98 schätzen.

Hinweis: Die internationale Norm ISO/IEC 10967-1 könnte hier relevant sein, aber soweit ich das beurteilen konnte, wurde sie nur im informativen Anhang erwähnt.

Schauen Sie sich an -ftrapv und -fwrapv:

-ftrapv

Diese Option generiert Traps für vorzeichenbehafteten Überlauf bei Additions-, Subtraktions- und Multiplikationsoperationen.

-fwrapv

Diese Option weist den Compiler an, anzunehmen, dass der vorzeichenbehaftete arithmetische Überlauf von Addition, Subtraktion und Multiplikation unter Verwendung einer Zweierkomplementdarstellung umläuft. Dieses Flag aktiviert einige Optimierungen und deaktiviert andere. Diese Option ist standardmäßig für das Java-Front-End aktiviert, wie von der Java-Sprachspezifikation gefordert.

Für Ihre C99-Antwort, denke ich 6.5 AusdrückeAbsatz 5 ist das, wonach Sie suchen:

Wenn ein außergewöhnlicher Zustand während der Auswertung eines Ausdrucks auftritt (d. h. wenn das Ergebnis nicht mathematisch definiert ist oder nicht im Bereich darstellbarer Werte für seinen Typ liegt), ist das Verhalten undefiniert.

Das heißt, wenn Sie einen Überlauf bekommen, haben Sie Pech – keinerlei Verhalten garantiert. Typen ohne Vorzeichen sind ein Sonderfall und laufen nie über (6.2.5 TypenAbsatz 9):

Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen, da ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen ganzzahligen Typ dargestellt werden kann, modulo um die Zahl reduziert wird, die um eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann.

C++ hat die gleichen Anweisungen, etwas anders formuliert:

• 5 AusdrückeAbsatz 4:

  Wenn während der Auswertung eines Ausdrucks das Ergebnis nicht mathematisch definiert ist oder nicht im Bereich darstellbarer Werte für seinen Typ liegt, ist das Verhalten undefiniert. [Note: most existing implementations of C++ ignore integer overflows. Treatment of division by zero, forming a remainder using a zero divisor, and all floating point exceptions vary among machines, and is usually adjustable by a library function. —endnote]

• 3.9.1 GrundtypenAbsatz 4:

  Ganzzahlen ohne Vorzeichen, deklariert unsignedmuss den Gesetzen der Arithmetik modulo 2^ gehorchenn wo n ist die Anzahl der Bits in der Wertdarstellung dieser bestimmten Ganzzahlgröße.

In C99 ist das allgemeine Verhalten in 6.5/5 beschrieben

Wenn ein außergewöhnlicher Zustand während der Auswertung eines Ausdrucks auftritt (d. h. wenn das Ergebnis nicht mathematisch definiert ist oder nicht im Bereich darstellbarer Werte für seinen Typ liegt), ist das Verhalten undefiniert.

Das Verhalten von vorzeichenlosen Typen wird in 6.2.5/9 beschrieben, der im Wesentlichen besagt, dass Operationen auf vorzeichenlosen Typen niemals zu einer Ausnahmebedingung führen

Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen, da ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen ganzzahligen Typ dargestellt werden kann, modulo um die Zahl reduziert wird, die um eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann.

Der GCC-Compiler hat eine spezielle Option -ftrapvdas den Laufzeitüberlauf von Operationen mit vorzeichenbehafteten Ganzzahlen abfangen soll.

Der Vollständigkeit halber möchte ich hinzufügen, dass Clang jetzt “checked arithmetic builtins” als Spracherweiterung hat. Hier ist ein Beispiel für die Verwendung einer geprüften vorzeichenlosen Multiplikation:

unsigned x, y, result;
...
if (__builtin_umul_overflow(x, y, &result)) {
    /* overflow occured */
    ...
}
...

http://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins

6.2.5 Absatz 9 ist das, wonach Sie suchen:

Der Bereich nicht negativer Werte eines vorzeichenbehafteten Integer-Typs ist ein Teilbereich des entsprechenden vorzeichenlosen Integer-Typs, und die Darstellung desselben Werts in jedem Typ ist gleich.31) Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen, da ein Ergebnis dies nicht kann durch den resultierenden ganzzahligen Typ ohne Vorzeichen dargestellt werden, wird modulo um die Zahl reduziert, die um eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann.

Die vorherigen Postings kommentierten alle den C99-Standard, aber tatsächlich gab es diese Garantie schon früher.

Der 5. Absatz von Abschnitt 6.1.2.5 Typen

der C89-Standardstaaten

Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen, da ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen Integertyp dargestellt werden kann, modulo um die Zahl reduziert wird, die um eins größer ist als der größte Wert, der durch den resultierenden vorzeichenlosen Integertyp dargestellt werden kann.

Beachten Sie, dass dies C-Programmierern ermöglicht, alle vorzeichenlosen Divisionen durch eine Konstante zu ersetzen, die durch eine Multiplikation mit dem inversen Element des Rings ersetzt wird, der durch Cs Modulo-2^N-Intervall-Arithmetik gebildet wird.

Und das ganz ohne „Korrektur“, wie sie durch eine Annäherung der Division durch eine Festkomma-Multiplikation mit dem Kehrwert notwendig wäre.

Stattdessen kann der erweiterte euklidische Algorithmus verwendet werden, um das inverse Element zu finden und es als Multiplikator zu verwenden. (Um portabel zu bleiben, sollten natürlich auch bitweise UND-Operationen angewendet werden, um sicherzustellen, dass die Ergebnisse die gleichen Bitbreiten haben.)

Es lohnt sich zu erwähnen, dass die meisten C-Compiler dies bereits als Optimierung implementieren. Solche Optimierungen sind jedoch nicht garantiert, und daher könnte es für Programmierer immer noch interessant sein, solche Optimierungen manuell in Situationen durchzuführen, in denen es auf Geschwindigkeit ankommt, aber die Fähigkeiten des C-Optimierers entweder unbekannt oder besonders schwach sind.

Und als letzte Bemerkung der Grund, warum man es überhaupt versucht: Die Anweisungen auf Maschinenebene für die Multiplikation sind typischerweise viel schneller als die für die Division, insbesondere auf Hochleistungs-CPUs.

Ich bin mir nicht sicher, ob es Compilerschalter gibt, die Sie verwenden können, um ein einheitliches Verhalten für Überläufe in C/C++ zu erzwingen. Eine weitere Möglichkeit ist die Verwendung von SafeInt<T> Schablone. Es ist eine plattformübergreifende C++-Vorlage, die definitive Überlauf-/Unterlaufprüfungen für alle Arten von Ganzzahloperationen bietet.

• http://safeint.codeplex.com/