Wykrywanie podpisanego przepełnienia w C / C ++

Na pierwszy rzut oka to pytanie może wydawać się duplikatem pytania Jak wykryć przepełnienie liczb całkowitych? jednak w rzeczywistości jest znacząco inny.

Odkryłam, że podczas wykrywania przepełnienia całkowitą bez znaku jest dość trywialne, wykrywanie podpisane przepełnienie w C / C ++ jest rzeczywiście trudniejsze, niż sądzi większość ludzi.

Najbardziej oczywistym, ale naiwnym sposobem byłoby coś takiego:

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

Problem polega na tym, że zgodnie ze standardem C przepełnienie liczb całkowitych ze znakiem jest niezdefiniowanym zachowaniem. Innymi słowy, zgodnie ze standardem, gdy tylko spowodujesz przepełnienie ze znakiem, Twój program będzie tak samo nieprawidłowy, jak gdybyś wyłuskał wskaźnik zerowy. Nie możesz więc spowodować niezdefiniowanego zachowania, a następnie spróbuj wykryć przepełnienie po fakcie, tak jak w powyższym przykładzie sprawdzania warunku końcowego.

Mimo że powyższe sprawdzenie prawdopodobnie zadziała na wielu kompilatorach, nie możesz na to liczyć. W rzeczywistości, ponieważ standard C mówi, że przepełnienie ze znakiem całkowitym jest niezdefiniowane, niektóre kompilatory (takie jak GCC) zoptymalizują powyższe sprawdzenie, gdy ustawione są flagi optymalizacji, ponieważ kompilator zakłada, że ​​przepełnienie ze znakiem jest niemożliwe. To całkowicie przerywa próbę sprawdzenia przepełnienia.

Tak więc inny możliwy sposób sprawdzenia przepełnienia to:

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

Wydaje się to bardziej obiecujące, ponieważ tak naprawdę nie dodajemy do siebie dwóch liczb całkowitych, dopóki nie upewnimy się z góry, że wykonanie takiego dodania nie spowoduje przepełnienia. W ten sposób nie powodujemy żadnego niezdefiniowanego zachowania.

Jednak to rozwiązanie jest niestety dużo mniej wydajne niż rozwiązanie początkowe, ponieważ musisz wykonać operację odejmowania, aby sprawdzić, czy operacja dodawania zadziała. I nawet jeśli nie przejmujesz się tym (małym) hitem wydajnościowym, nadal nie jestem do końca przekonany, że to rozwiązanie jest odpowiednie. Wyrażenie lhs <= INT_MIN - rhswygląda dokładnie tak, jak rodzaj wyrażenia, które kompilator może zoptymalizować, myśląc, że przepełnienie ze znakiem jest niemożliwe.

Czy jest tutaj lepsze rozwiązanie? Coś, co gwarantuje, że 1) nie spowoduje nieokreślonego zachowania i 2) nie zapewni kompilatorowi możliwości optymalizacji kontroli przepełnienia? Pomyślałem, że może być jakiś sposób na zrobienie tego przez rzutowanie obu operandów na niepodpisane i wykonywanie sprawdzeń przez zwijanie własnej arytmetyki uzupełnień do dwóch, ale nie jestem pewien, jak to zrobić.

Twoje podejście do odejmowania jest poprawne i dobrze zdefiniowane. Kompilator nie może go zoptymalizować.

Innym poprawnym podejściem, jeśli masz dostępny większy typ liczby całkowitej, jest wykonanie arytmetyki w większym typie, a następnie sprawdzenie, czy wynik pasuje do mniejszego typu podczas konwersji z powrotem

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

Dobry kompilator powinien przekonwertować całe dodawanie i ifinstrukcję na intdodatek o małej wielkości i pojedynczy warunkowy przepełnienie skoku i nigdy nie wykonywać większego dodawania.

Edycja: Jak wskazał Stephen, mam problem ze znalezieniem (niezbyt dobrego) kompilatora, gcc, do wygenerowania rozsądnego asm. Kod, który generuje, nie jest zbyt wolny, ale z pewnością nieoptymalny. Jeśli ktoś zna warianty tego kodu, które sprawią, że gcc zrobi dobrze, z przyjemnością je zobaczę.

Nie, twój drugi kod jest nieprawidłowy, ale jesteś blisko: jeśli ustawiłeś

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

wynikiem dodawania jest INT_MAX. ( INT_MAXjest zawsze liczbą nieparzystą). Więc to jest poprawny wpis. Ale w swojej rutynie będziesz miał INT_MAX - half == half1i przerwał. Fałszywie pozytywny.

Ten błąd można naprawić, wprowadzając <zamiast <=obu kontroli.

Ale także twój kod nie jest optymalny. Zrobiłoby to:

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

Aby zobaczyć, że jest to poprawne, musisz symbolicznie dodać lhsnierówności po obu stronach, a to daje dokładnie warunki arytmetyczne, które wynikają poza granicami.

IMHO, najbardziej wschodnim sposobem radzenia sobie z kodem C ++ wrażliwym na przepełnienie jest użycie SafeInt<T>. Jest to wieloplatformowy szablon C ++ hostowany na plexie kodu, który zapewnia gwarancje bezpieczeństwa, których tutaj potrzebujesz.

• http://safeint.codeplex.com/

Uważam, że jest bardzo intuicyjny w użyciu, ponieważ zapewnia wiele takich samych wzorców użycia, jak normalne operacje numeryczne i wyraża przepływy powyżej i poniżej za pomocą wyjątków.

W przypadku gcc, z informacji o wydaniu gcc 5.0 widzimy, że teraz zawiera dodatkowo __builtin_add_overflowdo sprawdzenia przepełnienia:

Dodano nowy zestaw wbudowanych funkcji dla arytmetyki ze sprawdzaniem przepełnienia: __builtin_add_overflow, __builtin_sub_overflow i __builtin_mul_overflow oraz dla kompatybilności z clang również innymi wariantami. Te polecenia wbudowane mają dwa integralne argumenty (które nie muszą mieć tego samego typu), argumenty są rozszerzane do typu ze znakiem o nieskończonej precyzji, na nich jest wykonywany znak +, - lub *, a wynik jest przechowywany w zmiennej całkowitej wskazanej na przez ostatni argument. Jeśli przechowywana wartość jest równa wynikowi nieskończonej precyzji, funkcje wbudowane zwracają false, w przeciwnym razie true. Typ zmiennej całkowitej, w której będzie przechowywany wynik, może być inny niż typy dwóch pierwszych argumentów.

Na przykład:

__builtin_add_overflow( rhs, lhs, &result )

Możemy zobaczyć z dokumentu gcc Wbudowane funkcje do wykonywania arytmetyki z przepełnieniem sprawdzania, że:

[...] te wbudowane funkcje mają w pełni zdefiniowane zachowanie dla wszystkich wartości argumentów.

clang zapewnia również zestaw sprawdzonych wbudowanych arytmetycznych :

Clang zapewnia zestaw wbudowanych, które implementują sprawdzoną arytmetykę dla aplikacji krytycznych dla bezpieczeństwa w sposób szybki i łatwy do wyrażenia w C.

w tym przypadku wbudowany wyglądałby tak:

__builtin_sadd_overflow( rhs, lhs, &result )

Jeśli używasz asemblera wbudowanego, możesz sprawdzić flagę przepełnienia . Inną możliwością jest użycie typu danych safeint . Polecam przeczytanie tego artykułu na temat Integer Security .

Najszybszym możliwym sposobem jest użycie wbudowanego GCC:

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

Na x86, GCC kompiluje to do:

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

który wykorzystuje wbudowaną funkcję wykrywania przepełnienia procesora.

Jeśli nie masz nic przeciwko używaniu wbudowanych GCC, następnym najszybszym sposobem jest użycie operacji bitowych na bitach znaku. Podpisane przepełnienie dodatkowo występuje, gdy:

• oba operandy mają ten sam znak i
• wynik ma inny znak niż operandy.

Bit znaku ~(lhs ^ rhs)jest włączony, jeśli operandy mają ten sam znak, a bit znaku lhs ^ sumjest włączony, jeśli wynik ma inny znak niż operandy. Możesz więc dodać w postaci bez znaku, aby uniknąć niezdefiniowanego zachowania, a następnie użyć bitu znaku ~(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;
}

To kompiluje się w:

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

co jest dużo szybsze niż przesyłanie na typ 64-bitowy na maszynie 32-bitowej (z 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

Możesz mieć więcej szczęścia przy konwersji na 64-bitowe liczby całkowite i testowaniu podobnych warunków. Na przykład:

#include <stdint.h>

...

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

Możesz przyjrzeć się bliżej, jak będzie tutaj działać rozszerzenie znaku, ale myślę, że jest poprawne.

Co powiesz na:

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

Myślę, że to powinno działać dla każdego uzasadnionego INT_MINi INT_MAX(symetrycznego lub nie); funkcję, jak pokazano klipy, ale powinno być oczywiste, jak uzyskać inne zachowania).

Oczywistym rozwiązaniem jest konwersja na unsigned, aby uzyskać dobrze zdefiniowane zachowanie przepełnienia bez znaku:

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

Zastępuje to niezdefiniowane zachowanie przepełnienia podpisem zdefiniowaną przez implementację konwersją wartości spoza zakresu między podpisanymi a niepodpisanymi, więc musisz sprawdzić dokumentację kompilatora, aby dokładnie wiedzieć, co się stanie, ale powinno być przynajmniej dobrze zdefiniowane i powinien postępować właściwie na każdej maszynie z uzupełnieniem dwójki, która nie generuje sygnałów o konwersjach, czyli prawie na każdej maszynie i kompilatorze języka C zbudowanych w ciągu ostatnich 20 lat.

W przypadku dodania dwóch longwartości, przenośny kod może podzielić longwartość na części niskie i wysokie int(lub na shortczęści, jeśli longma taki sam rozmiar jak 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'

Korzystanie z asemblacji wbudowanej jest najszybszym sposobem, jeśli jest przeznaczony dla określonego procesora:

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'

Myślę, że to działa:

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

Użycie volatile powstrzymuje kompilator przed optymalizacją testu, ponieważ uważa, że summogło się to zmienić między dodawaniem a odejmowaniem.

Używając gcc 4.4.3 dla x86_64, assembler dla tego kodu wykonuje dodawanie, odejmowanie i testowanie, chociaż przechowuje wszystko na stosie i niepotrzebne operacje na stosie. Nawet próbowałemregister volatile int sum = ale montaż był taki sam.

W przypadku wersji z samą int sum =(brakiem ulotnym lub rejestrem) funkcja nie wykonała testu i dodała tylko jedną leainstrukcję ( leajest to Load Effective Address i jest często używana do dodawania bez dotykania rejestru flag).

Twoja wersja zawiera większy kod i dużo więcej skoków, ale nie wiem, która byłaby lepsza .

Według mnie najprostszym sprawdzeniem byłoby sprawdzenie znaków operandów i wyników.

Przyjrzyjmy się sumie: przepełnienie może wystąpić w obu kierunkach, + lub -, tylko wtedy, gdy oba operandy mają ten sam znak. I, oczywiście, przepełnienie nastąpi, gdy znak wyniku nie będzie taki sam jak znak argumentów.

Więc taki czek wystarczy:

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

Edycja: jak zasugerował Nils, jest to poprawny ifstan:

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

I od kiedy instrukcja

add eax, ebx 

prowadzi do nieokreślonego zachowania? W odniesieniu do zestawu instrukcji Intel x86 nie ma czegoś takiego.