Überschriebenen Überlauf in C / C ++ erkennen
Auf den ersten Blick, diese Frage mag wie eine Kopie der Wie zu erkennen integer-überlauf?aber es ist tatsächlich deutlich anders.
Habe ich gefunden, dass während der Erkennung eine vorzeichenlose integer-überlauf ist ziemlich trivial, das erkennen einer unterzeichnet überlauf in C/C++ ist eigentlich schwieriger, als die meisten Leute denken.
Den meisten offensichtlich, doch naiv, so zu tun, es wäre so etwas wie:
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;
}
Das problem mit diesem ist, dass nach dem C-standard, Ganzzahl-überlauf ist Undefiniertes Verhalten. In anderen Worten, gemäß der Norm, sobald Sie selbst die Ursache unterzeichnet überlauf, Ihr Programm ist genauso hinfällig, wie wenn Sie dereferenziert einen null-Zeiger. Man kann also nicht die Ursache zu undefiniertem Verhalten, und versuchen Sie dann zu erkennen, den überlauf nach der Tat, wie in der oben genannten post-condition check Beispiel.
Obwohl die obige Prüfung ist wahrscheinlich zu arbeiten auf viele Compiler können Sie nicht rechnen. In der Tat, da der C-standard sagt signed integer overflow nicht definiert ist, sind einige Compiler (z.B. GCC) wird optimieren Sie Weg, die obige Prüfung wenn Optimierungs-flags gesetzt sind, da der compiler davon eine signiert überlauf ist unmöglich. Diese völlig unterbricht den Versuch, zu prüfen, für überlauf.
So, eine andere Möglichkeit zu prüfen, für überlauf wäre:
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;
}
Dieser scheint vielversprechend, da wir eigentlich nicht hinzuzufügen, die zwei Ganzzahlen miteinander, bis wir stellen Sie im Voraus sicher, dass die Durchführung solch einer Beurteilung führt nicht zum überlaufen. Also, wir führen nicht irgendwelche undefinierten Verhalten.
Jedoch, diese Lösung ist leider sehr viel weniger effizient als die erste Lösung, da Sie zum durchführen einer subtract-operation, nur um zu testen, ob die addition funktioniert. Und selbst wenn Sie don ' T care über diese (kleinen) Leistungseinbruch, ich bin noch nicht ganz überzeugt, dass diese Lösung ausreichend ist. Der Ausdruck lhs <= INT_MIN - rhs
scheint, genau wie die Art von Ausdruck, der compiler kann optimieren entfernt werden, zu denken, dass signed-überlauf ist unmöglich.
So gibt es eine bessere Lösung? Etwas, das garantiert wird, um 1) führen nicht zu undefiniertem Verhalten, und 2) nicht die compiler die Möglichkeit zur Optimierung entfernt überlauf überprüft? Ich dachte vielleicht gibt es einen Weg, es zu tun, indem man beide Operanden in unsigned und die Durchführung von Kontrollen durch Ihre eigenen Rollen zweier-Komplement-Arithmetik, aber ich bin mir nicht wirklich sicher, wie das zu tun.
InformationsquelleAutor der Frage Channel72 | 2010-10-15
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ihren Ansatz mit der Subtraktion ist richtig und gut definiert. Ein compiler nicht optimieren Sie Weg.
Anderen die richtige Vorgehensweise, wenn Sie eine größere integer-Typ zur Verfügung, um die arithmetische Operationen ausführen, die in den größeren Typ und überprüfen Sie, dass das Ergebnis passt in der kleineren Art, wenn Sie zu konvertieren zurück
Einen guten compiler konvertiert die gesamten neben-und
if
Anweisung in einenint
-size-Zusatz und ein einziger bedingter Sprung-auf-überlauf und eigentlich nie führen Sie die größere neben.Edit: Als Stephen darauf hingewiesen, ich habe Mühe, eine (nicht so gute) compiler gcc, die zum erzeugen der sane asm. Den code den es generiert, ist das nicht furchtbar langsam, aber sicher suboptimal. Wenn jemand weiß, Varianten dieses Codes, die Sie erhalten, gcc, das richtige zu tun, ich würde lieben, Sie zu sehen.
InformationsquelleAutor der Antwort R..
Nein, dein 2. code ist nicht korrekt, aber Sie sind in der Nähe: wenn Sie
das Ergebnis einer addition ist
INT_MAX
. (INT_MAX
ist immer eine ungerade Zahl). Das ist also eine gültige Eingabe. Aber in Ihrer routine haben SieINT_MAX - half == half1
und Sie würde Abbrechen. Ein false positive ist.Dieser Fehler kann repariert werden, indem
<
statt<=
in beiden Prüfungen.Aber dann auch dein code ist nicht optimal. Die folgenden tun würde:
Zu sehen, dass diese gültig ist, müssen Sie symbolisch hinzufügen
lhs
auf beiden Seiten der Ungleichungen, und das gibt Ihnen genau die arithmetischen Bedingungen, die Ihr Ergebnis ist außerhalb des gültigen Bereichs.InformationsquelleAutor der Antwort Jens Gustedt
IMHO, die eastiest Umgang mit überlauf sentsitive C++ - code ist die Verwendung
SafeInt<T>
. Dies ist ein cross-Plattform C++ - template-gehostet-code plex, die für die Sicherheit garantiert, dass Sie den Wunsch hier.Ich finde es sehr intuitiv zu bedienen, wie es bietet viele der gleichen Nutzungsmuster wie normale numerische opertations und drückt über und unter fließt über Ausnahmen.
InformationsquelleAutor der Antwort JaredPar
Für die gcc Fall von gcc 5.0 Release notes können wir sehen, es bietet jetzt eine
__builtin_add_overflow
für die überprüfung von überlauf zusätzlich:Beispiel:
Können wir sehen, aus den gcc-Dokument Built-in-Funktionen zum Durchführen von Arithmetischen mit Überlauf Prüfen:
clang bietet auch eine Reihe von geprüft arithmetische gelieferten:
in diesem Fall die builtin wäre:
InformationsquelleAutor der Antwort Shafik Yaghmour
Wenn Sie inline-assembler können Sie die overflow-flag. Eine andere Möglichkeit ist, welches Sie verwenden können, eine safeint Datentyp. Ich empfehle, Lesen Sie dieses Papier auf Integer-Sicherheit.
InformationsquelleAutor der Antwort rook
Haben Sie vielleicht mehr Glück umwandeln zu 64-bit-Ganzzahlen und Tests zu ähnlichen Bedingungen wie die. Zum Beispiel:
Möchten Sie vielleicht, um einen genaueren Blick auf, wie Zeichen-Erweiterung, die hier arbeiten, aber ich denke, es ist richtig.
InformationsquelleAutor der Antwort Jonathan
Wie etwa:
Ich denke, dass sollte funktionieren für legitim
INT_MIN
undINT_MAX
(symmetrisch oder nicht); die Funktion wie clips, aber es sollte offensichtlich sein, wie man andere Verhaltensweisen).InformationsquelleAutor der Antwort supercat
Schnellste Möglichkeit ist die Verwendung der GCC-builtin:
Auf x86 mit GCC kompiliert diese in:
verwendet der Prozessor integrierten überlauf-Erkennung.
Wenn Sie nicht OK mit der Verwendung von GCC gelieferten, der nächste Schnellste Weg ist, um bit-Operationen auf die Zeichen-bits. Unterzeichnet überlauf zusätzlich tritt auf, wenn:
Dem Vorzeichen-bit des
~(lhs ^ rhs)
ist auf dem iff die Operanden das gleiche Vorzeichen, und das Vorzeichen-bit derlhs ^ sum
ist am iff das Ergebnis hat ein anderes Vorzeichen als die Operanden. So kann man den Zusatz in unsignierter form zu vermeiden, zu undefiniertem Verhalten, und verwenden Sie dann das Vorzeichen-bit der~(lhs ^ rhs) & (lhs ^ sum)
:Diese kompiliert in:
das ist ziemlich viel schneller als die Umwandlung einer 64-bit-geben Sie auf einem 32-bit-Maschine (mit gcc):
InformationsquelleAutor der Antwort tbodt
Mir das einfachste zu überprüfen wäre, überprüfen Sie die Zeichen der Operanden und die Ergebnisse.
Betrachten wir die Summe: der überlauf, der auftreten konnte, in beide Richtungen, + oder -, nur dann, wenn beide Operanden das gleiche Vorzeichen. Und, obviosly, der überlauf sein wird, wenn das Vorzeichen des Ergebnisses ist nicht das gleiche wie das Vorzeichen des Operanden.
So, schauen wie das wird genug sein:
Edit: wie Nils vorgeschlagen, das ist das richtige
if
Zustand:Und seit Wann wird der Unterricht
führt zu undefiniertem Verhalten? Es gibt keine solche Sache in der Intel x86-Befehlssatz refference..
InformationsquelleAutor der Antwort ruslik
Ist die offensichtliche Lösung ist die Konvertierung zu unsigned, um die gut definierten unsigned overflow-Verhalten:
Dieser ersetzt den unbestimmten signed overflow-Verhalten mit der Implementierung definierte Umwandlung von out-of-range-Werte zwischen signed und unsigned, so müssen Sie überprüfen Ihre compiler-Dokumentation genau zu wissen, was passieren wird, aber es sollte zumindest definiert werden, und sollte das richtige tun, auf jede zweier-Komplement-Maschine, die nicht erhöhen Signale auf conversions, die so ziemlich jede Maschine und C-compiler gebaut, der in den letzten 20 Jahren.
InformationsquelleAutor der Antwort Chris Dodd
Im Falle der Zugabe von zwei
long
Werte, portablen code aufteilen können, dielong
- Wert in low und highint
Teile (oder inshort
Teile im Fallelong
hat die gleiche Größe wieint
):Verwendung von inline-assembly ist der Schnellste Weg, wenn ein bestimmtes targeting CPU:
InformationsquelleAutor der Antwort atomsymbol
Ich denke, dass das funktioniert:
Verwendung von volatile hält der compiler die Optimierung Weg, der test, weil es denkt, dass
sum
geändert haben kann, zwischen der addition und der Subtraktion.Mit gcc 4.4.3 für x86_64 die Montage dieser code macht die addition, die Subtraktion und den test, aber es speichert alles auf dem stack und nicht mehr benötigte stack-Operationen. Ich habe sogar versucht
register volatile int sum =
aber die Montage war die gleiche.Für eine version mit nur
int sum =
(keine flüchtigen oder register) die Funktion nicht testen und habe den Zusatz mit nur einemlea
Unterricht (lea
Laden Effektive Adresse und wird oft verwendet, um zu tun, zudem ohne Berührung des flags-Registers).Ihre version ist größer-code und hat viel mehr Sprünge, aber ich weiß nicht, was wäre besser.
InformationsquelleAutor der Antwort nategoose