Erkennen signed-überlauf in C/C++

Nein, dein 2. code ist nicht korrekt, aber Sie sind in der Nähe: wenn Sie

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

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 Sie INT_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:

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

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 Jens Gustedt

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:

Einen neuen Satz von built-in Funktionen für die Arithmetik mit überlauf-Kontrolle wurde Hinzugefügt: __builtin_add_überlauf __builtin_sub_überlauf __builtin_mul_overflow und die Kompatibilität mit clang auch andere Varianten. Diese gelieferten zwei Integrale Argumente (die nicht brauchen, um die gleiche Art), die Argumente erweitert werden, um unendliche Genauigkeit unterzeichnet-Typ, +, - oder * wird durchgeführt, und das Ergebnis wird gespeichert, in einer integer-variable wies auf die durch das Letzte argument. Wenn der gespeicherte Wert ist gleich der unendlichen Präzision führen, die built-in Funktionen false zurück, andernfalls true. Der Typ der integer-variable, die halten wird das Ergebnis anders sein kann, als die Arten der ersten beiden Argumente.

Beispiel:

__builtin_add_overflow( rhs, lhs, &result )

Können wir sehen, aus den gcc-Dokument Built-in-Funktionen zum Durchführen von Arithmetischen mit Überlauf Prüfen:

[...]diese built-in-Funktionen vollständig definiert Verhalten für alle argument-Werte.

clang bietet auch eine Reihe von geprüft arithmetische gelieferten:

Clang bietet eine Reihe von gelieferten, die Umsetzung überprüft Arithmetik für Sicherheits-kritische Anwendungen in einer Weise, die schnell und einfach expressable in C.

in diesem Fall die builtin wäre:

__builtin_sadd_overflow( rhs, lhs, &result )

InformationsquelleAutor Shafik Yaghmour

Schnellste Möglichkeit ist die Verwendung der GCC-builtin:

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

Auf x86 mit GCC kompiliert diese in:

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

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:

• die zwei Operanden haben gleiche Vorzeichen, und
• das Ergebnis hat ein anderes Vorzeichen als die Operanden.

Dem Vorzeichen-bit des ~(lhs ^ rhs) ist auf dem iff die Operanden das gleiche Vorzeichen, und das Vorzeichen-bit der lhs ^ 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):

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

Diese kompiliert 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 ziemlich viel schneller als die Umwandlung einer 64-bit-geben Sie auf einem 32-bit-Maschine (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

InformationsquelleAutor tbodt

Haben Sie vielleicht mehr Glück umwandeln zu 64-bit-Ganzzahlen und Tests zu ähnlichen Bedingungen wie die. 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;
}

Möchten Sie vielleicht, um einen genaueren Blick auf, wie Zeichen-Erweiterung, die hier arbeiten, aber ich denke, es ist richtig.

InformationsquelleAutor Jonathan

Ist die offensichtliche Lösung ist die Konvertierung zu unsigned, um die gut definierten unsigned overflow-Verhalten:

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

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 Chris Dodd

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

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 einem lea 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 nategoose