Vorzeichenüberlauf in C / C ++ erkennen

Auf den ersten Blick scheint diese Frage ein Duplikat von Wie erkennt man einen Ganzzahlüberlauf? es ist jedoch tatsächlich deutlich anders.

Ich habe festgestellt, dass das Erkennen eines vorzeichenlosen Ganzzahlüberlaufs zwar ziemlich trivial ist, das Erkennen eines vorzeichenbehafteten Überlaufs in C / C ++ jedoch schwieriger ist, als die meisten Leute denken.

Der naheliegendste und doch naivste Weg, dies zu tun, wäre etwa:

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 dabei ist, dass gemäß dem C-Standard ein vorzeichenbehafteter Ganzzahlüberlauf ein undefiniertes Verhalten ist. Mit anderen Worten, gemäß dem Standard ist Ihr Programm genauso ungültig, als ob Sie einen Nullzeiger dereferenziert hätten, sobald Sie überhaupt einen signierten Überlauf verursachen. Sie können also kein undefiniertes Verhalten verursachen und dann versuchen, den Überlauf nachträglich zu erkennen, wie im obigen Beispiel für die Überprüfung nach der Bedingung.

Obwohl die obige Prüfung wahrscheinlich bei vielen Compilern funktioniert, können Sie sich nicht darauf verlassen. Da der C-Standard besagt, dass ein vorzeichenbehafteter Ganzzahlüberlauf undefiniert ist, optimieren einige Compiler (wie GCC) die obige Prüfung, wenn Optimierungsflags gesetzt sind, da der Compiler davon ausgeht, dass ein vorzeichenbehafteter Überlauf unmöglich ist. Dies unterbricht den Versuch, auf Überlauf zu prüfen, vollständig.

Eine andere Möglichkeit, den Überlauf zu überprüfen, 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;
}

Dies scheint vielversprechender zu sein, da wir die beiden Ganzzahlen erst dann addieren, wenn wir im Voraus sicherstellen, dass das Durchführen einer solchen Addition nicht zu einem Überlauf führt. Daher verursachen wir kein undefiniertes Verhalten.

Diese Lösung ist jedoch leider viel weniger effizient als die ursprüngliche Lösung, da Sie eine Subtraktionsoperation ausführen müssen, um zu testen, ob Ihre Additionsoperation funktioniert. Und selbst wenn Sie sich nicht für diesen (kleinen) Leistungseinbruch interessieren, bin ich immer noch nicht ganz davon überzeugt, dass diese Lösung angemessen ist. Der Ausdruck lhs <= INT_MIN - rhsscheint genau der Art von Ausdruck zu sein, die der Compiler möglicherweise optimiert, da ein signierter Überlauf unmöglich ist.

Gibt es hier also eine bessere Lösung? Etwas, das garantiert 1) kein undefiniertes Verhalten verursacht und 2) dem Compiler keine Möglichkeit bietet, Überlaufprüfungen zu optimieren? Ich dachte, es könnte eine Möglichkeit geben, dies zu tun, indem beide Operanden in vorzeichenlose Zeichen umgewandelt werden und Überprüfungen durchgeführt werden, indem Ihre eigene Zwei-Komplement-Arithmetik gewürfelt wird, aber ich bin mir nicht sicher, wie ich das tun soll.

Ihr Ansatz mit Subtraktion ist korrekt und klar definiert. Ein Compiler kann es nicht weg optimieren.

Ein anderer korrekter Ansatz, wenn Sie einen größeren Ganzzahltyp zur Verfügung haben, besteht darin, die Arithmetik im größeren Typ auszuführen und dann zu überprüfen, ob das Ergebnis in den kleineren Typ passt, wenn Sie es zurückkonvertieren

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

Ein guter Compiler sollte die gesamte Addition und ifAnweisung in eine intAddition in Größe und einen einzelnen bedingten Jump-on-Overflow konvertieren und die größere Addition niemals tatsächlich ausführen.

Bearbeiten: Wie Stephen betonte, habe ich Probleme, einen (nicht so guten) Compiler, gcc, zu bekommen, um den vernünftigen Asm zu generieren. Der Code, den es generiert, ist nicht besonders langsam, aber sicherlich nicht optimal. Wenn jemand Varianten dieses Codes kennt, die gcc dazu bringen, das Richtige zu tun, würde ich sie gerne sehen.

Nein, Ihr 2. Code ist nicht korrekt, aber Sie sind nah dran: wenn Sie einstellen

int half = INT_MAX/2;
int half1 = half + 1;

das Ergebnis einer Addition ist INT_MAX. ( INT_MAXist immer eine ungerade Zahl). Das ist also eine gültige Eingabe. Aber in Ihrer Routine werden Sie haben INT_MAX - half == half1und Sie würden abbrechen. Ein falsches Positiv.

Dieser Fehler kann , indem sie repariert werden , <anstatt <=in beiden Kontrollen.

Aber dann ist auch Ihr Code nicht optimal. Folgendes würde reichen:

int add(int lhs, int rhs)
{
 if (lhs >= 0) {
  if (INT_MAX - lhs < rhs) {
   /* would overflow */
   abort();
  }
 }
 else {
  if (rhs < INT_MIN - lhs) {
   /* would overflow */
   abort();
  }
 }
 return lhs + rhs;
}

Um zu sehen, dass dies gültig ist, müssen Sie lhsauf beiden Seiten der Ungleichungen symbolisch addieren , und dies gibt Ihnen genau die arithmetischen Bedingungen, unter denen Ihr Ergebnis außerhalb der Grenzen liegt.

Meiner Meinung nach ist die Verwendung der östlichsten Methode, um mit überlaufempfindlichem C ++ - Code umzugehen SafeInt<T>. Dies ist eine plattformübergreifende C ++ - Vorlage, die auf Code Plex gehostet wird und die Sicherheitsgarantien bietet, die Sie hier wünschen.

• http://safeint.codeplex.com/

Ich finde es sehr intuitiv zu bedienen, da es viele der gleichen Verwendungsmuster wie normale numerische Operationen bietet und über und unter Flüssen über Ausnahmen ausdrückt.

Für den Fall gcc können wir ab den Versionshinweisen zu gcc 5.0 sehen, dass es jetzt zusätzlich __builtin_add_overflowzur Überprüfung des Überlaufs Folgendes bietet :

Ein neuer Satz integrierter Funktionen für Arithmetik mit Überlaufprüfung wurde hinzugefügt: __builtin_add_overflow, __builtin_sub_overflow und __builtin_mul_overflow und zur Kompatibilität mit clang auch andere Varianten. Diese Buildins haben zwei integrale Argumente (die nicht denselben Typ haben müssen), die Argumente werden auf den vorzeichenbehafteten Typ mit unendlicher Genauigkeit erweitert, +, - oder * werden für diese ausgeführt, und das Ergebnis wird in einer Ganzzahlvariablen gespeichert, auf die verwiesen wird durch das letzte Argument. Wenn der gespeicherte Wert dem Ergebnis mit unendlicher Genauigkeit entspricht, geben die integrierten Funktionen false zurück, andernfalls true. Der Typ der Ganzzahlvariablen, die das Ergebnis enthält, kann sich von den Typen der ersten beiden Argumente unterscheiden.

Zum Beispiel:

__builtin_add_overflow( rhs, lhs, &result )

Aus dem gcc-Dokument können wir die integrierten Funktionen zur Durchführung von Arithmetik mit Überlauf ersehen. Überprüfen Sie Folgendes :

[...] Diese integrierten Funktionen haben ein vollständig definiertes Verhalten für alle Argumentwerte.

clang bietet auch eine Reihe von eingebauten arithmetischen Einbauten :

Clang bietet eine Reihe von integrierten Funktionen, die eine überprüfte Arithmetik für sicherheitskritische Anwendungen auf eine Weise implementieren, die in C schnell und einfach ausgedrückt werden kann.

In diesem Fall wäre das eingebaute:

__builtin_sadd_overflow( rhs, lhs, &result )

Wenn Sie einen Inline-Assembler verwenden, können Sie das Überlauf-Flag überprüfen . Eine andere Möglichkeit besteht darin, dass Sie einen sicheren Datentyp verwenden können . Ich empfehle, dieses Dokument über Integer Security zu lesen .

Der schnellstmögliche Weg ist die Verwendung des integrierten GCC:

int add(int lhs, int rhs) {
    int sum;
    if (__builtin_add_overflow(lhs, rhs, &sum))
        abort();
    return sum;
}

Auf x86 kompiliert GCC dies in:

    mov %edi, %eax
    add %esi, %eax
    jo call_abort 
    ret
call_abort:
    call abort

Hier wird die integrierte Überlauferkennung des Prozessors verwendet.

Wenn Sie mit der Verwendung von GCC-integrierten Funktionen nicht einverstanden sind, können Sie am schnellsten Bitoperationen für die Vorzeichenbits verwenden. Ein signierter Überlauf tritt zusätzlich auf, wenn:

• Die beiden Operanden haben das gleiche Vorzeichen und
• Das Ergebnis hat ein anderes Vorzeichen als die Operanden.

Das Vorzeichenbit von ~(lhs ^ rhs)ist aktiviert, wenn die Operanden das gleiche Vorzeichen haben, und das Vorzeichenbit von lhs ^ sumist aktiviert, wenn das Ergebnis ein anderes Vorzeichen als die Operanden hat. Sie können die Addition also in vorzeichenloser Form durchführen, um undefiniertes Verhalten zu vermeiden, und dann das Vorzeichenbit von ~(lhs ^ rhs) & (lhs ^ sum):

int add(int lhs, int rhs) {
    unsigned sum = (unsigned) lhs + (unsigned) rhs;
    if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000)
        abort();
    return (int) sum;
}

Dies setzt sich zusammen in:

    lea (%rsi,%rdi), %eax
    xor %edi, %esi
    not %esi
    xor %eax, %edi
    test %edi, %esi
    js call_abort
    ret
call_abort:
    call abort

Das ist viel schneller als das Umwandeln in einen 64-Bit-Typ auf einem 32-Bit-Computer (mit gcc):

    push %ebx
    mov 12(%esp), %ecx
    mov 8(%esp), %eax
    mov %ecx, %ebx
    sar $31, %ebx
    clt
    add %ecx, %eax
    adc %ebx, %edx
    mov %eax, %ecx
    add $-2147483648, %ecx
    mov %edx, %ebx
    adc $0, %ebx
    cmp $0, %ebx
    ja call_abort
    pop %ebx
    ret
call_abort:
    call abort

Möglicherweise haben Sie besseres Glück, wenn Sie in 64-Bit-Ganzzahlen konvertieren und ähnliche Bedingungen wie diese testen. Zum Beispiel:

#include <stdint.h>

...

int64_t sum = (int64_t)lhs + (int64_t)rhs;
if (sum < INT_MIN || sum > INT_MAX) {
    // Overflow occurred!
}
else {
    return sum;
}

Vielleicht möchten Sie sich genauer ansehen, wie die Zeichenerweiterung hier funktioniert, aber ich denke, das ist richtig.

Wie wäre es mit:

int sum(int n1, int n2)
{
  int result;
  if (n1 >= 0)
  {
    result = (n1 - INT_MAX)+n2; /* Can't overflow */
    if (result > 0) return INT_MAX; else return (result + INT_MAX);
  }
  else
  {
    result = (n1 - INT_MIN)+n2; /* Can't overflow */
    if (0 > result) return INT_MIN; else return (result + INT_MIN);
  }
}

Ich denke, das sollte für jeden legitimen INT_MINund INT_MAX(symmetrischen oder nicht) funktionieren ; die Funktion wie gezeigt Clips, aber es sollte offensichtlich sein, wie man andere Verhaltensweisen bekommt).

Die naheliegende Lösung besteht darin, in vorzeichenloses Überlaufverhalten zu konvertieren, um das genau definierte vorzeichenlose Überlaufverhalten zu erhalten:

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

Dies ersetzt das undefinierte signierte Überlaufverhalten durch die implementierungsdefinierte Konvertierung von Werten außerhalb des Bereichs zwischen signiert und nicht signiert. Sie müssen daher die Dokumentation Ihres Compilers überprüfen, um genau zu wissen, was passieren wird, aber es sollte zumindest genau definiert sein sollte auf jeder Zwei-Komplement-Maschine, die bei Konvertierungen keine Signale auslöst, das Richtige tun. Dies ist so ziemlich jede Maschine und jeder C-Compiler, die in den letzten 20 Jahren gebaut wurden.

Wenn zwei longWerte hinzugefügt werden, kann portabler Code den longWert in niedrige und hohe intTeile (oder in) aufteilenshort Teile, falls longdiese dieselbe Größe haben wie int):

static_assert(sizeof(long) == 2*sizeof(int), "");
long a, b;
int ai[2] = {int(a), int(a >> (8*sizeof(int)))};
int bi[2] = {int(b), int(b >> (8*sizeof(int))});
... use the 'long' type to add the elements of 'ai' and 'bi'

Die Verwendung der Inline-Assembly ist der schnellste Weg, wenn Sie auf eine bestimmte CPU abzielen:

long a, b;
bool overflow;
#ifdef __amd64__
    asm (
        "addq %2, %0; seto %1"
        : "+r" (a), "=ro" (overflow)
        : "ro" (b)
    );
#else
    #error "unsupported CPU"
#endif
if(overflow) ...
// The result is stored in variable 'a'

Ich denke, dass das funktioniert:

int add(int lhs, int rhs) {
   volatile int sum = lhs + rhs;
   if (lhs != (sum - rhs) ) {
       /* overflow */
       //errno = ERANGE;
       abort();
   }
   return sum;
}

Die Verwendung von flüchtig hält den Compiler davon ab, den Test zu optimieren, weil er das glaubt sum sich dies zwischen der Addition und der Subtraktion geändert hat.

Unter Verwendung von gcc 4.4.3 für x86_64 führt die Assembly für diesen Code die Addition, die Subtraktion und den Test durch, obwohl sie alles auf dem Stapel und nicht benötigte Stapeloperationen speichert. Ich habe es sogar versuchtregister volatile int sum = aber die Montage war dieselbe.

Für eine Version mit nur int sum =(kein flüchtiges oder Register) hat die Funktion den Test nicht durchgeführt und die Addition mit nur einer leaAnweisung durchgeführt ( leaist Load Effective Address und wird häufig verwendet, um eine Addition durchzuführen, ohne das Flags-Register zu berühren).

Ihre Version ist größerer Code und hat viel mehr Sprünge, aber ich weiß nicht, welcher besser wäre .

Für mich wäre die einfachste Überprüfung die Überprüfung der Vorzeichen der Operanden und der Ergebnisse.

Untersuchen wir die Summe: Der Überlauf kann in beide Richtungen + oder - nur auftreten, wenn beide Operanden das gleiche Vorzeichen haben. Und offensichtlich ist der Überlauf, wenn das Vorzeichen des Ergebnisses nicht mit dem Vorzeichen der Operanden übereinstimmt.

Ein Scheck wie dieser reicht also aus:

int a, b, sum;
sum = a + b;
if  (((a ^ ~b) & (a ^ sum)) & 0x80000000)
    detect_oveflow();

Bearbeiten: Wie Nils vorgeschlagen hat, ist dies die richtige ifBedingung:

((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)

Und seit wann die Anweisung

add eax, ebx 

führt zu undefiniertem Verhalten? In der Referenz zum Intel x86-Befehlssatz gibt es so etwas nicht.