Detectando desbordamiento firmado en C / C ++

A primera vista, esta pregunta puede parecer un duplicado de ¿Cómo detectar el desbordamiento de enteros? , sin embargo, en realidad es significativamente diferente.

Descubrí que si bien detectar un desbordamiento de enteros sin firmar es bastante trivial, detectar un desbordamiento con signo en C / C ++ es en realidad más difícil de lo que la mayoría de la gente piensa.

La forma más obvia, pero ingenua, de hacerlo sería algo como:

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

El problema con esto es que de acuerdo con el estándar C, el desbordamiento de enteros con signo es un comportamiento indefinido. En otras palabras, de acuerdo con el estándar, tan pronto como provoque un desbordamiento firmado, su programa es tan inválido como si hubiera desreferenciado un puntero nulo. Por lo tanto, no puede causar un comportamiento indefinido y luego intentar detectar el desbordamiento después del hecho, como en el ejemplo de verificación posterior a la condición anterior.

Aunque es probable que la comprobación anterior funcione en muchos compiladores, no puede contar con ella. De hecho, debido a que el estándar C dice que el desbordamiento de enteros con signo no está definido, algunos compiladores (como GCC) optimizarán la verificación anterior cuando se establezcan los indicadores de optimización, porque el compilador asume que un desbordamiento firmado es imposible. Esto rompe totalmente el intento de verificar el desbordamiento.

Entonces, otra forma posible de verificar el desbordamiento sería:

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

Esto parece más prometedor, ya que en realidad no sumamos los dos enteros juntos hasta que nos aseguremos de antemano de que realizar dicha adición no resultará en un desbordamiento. Por lo tanto, no causamos ningún comportamiento indefinido.

Sin embargo, esta solución es, desafortunadamente, mucho menos eficiente que la solución inicial, ya que debe realizar una operación de resta solo para probar si su operación de suma funcionará. E incluso si no le importa este (pequeño) impacto en el rendimiento, todavía no estoy del todo convencido de que esta solución sea adecuada. La expresión lhs <= INT_MIN - rhsparece exactamente el tipo de expresión que el compilador podría optimizar, pensando que el desbordamiento firmado es imposible.

Entonces, ¿hay una mejor solución aquí? ¿Algo que está garantizado para 1) no causar un comportamiento indefinido y 2) no proporcionar al compilador la oportunidad de optimizar las comprobaciones de desbordamiento? Estaba pensando que podría haber alguna manera de hacerlo convirtiendo ambos operandos a unsigned y realizando comprobaciones rodando su propia aritmética en complemento a dos, pero no estoy realmente seguro de cómo hacerlo.

Su enfoque con la resta es correcto y está bien definido. Un compilador no puede optimizarlo.

Otro enfoque correcto, si tiene un tipo de entero más grande disponible, es realizar la aritmética en el tipo más grande y luego verificar que el resultado se ajuste al tipo más pequeño al volver a convertirlo

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

Un buen compilador debería convertir toda la adición y la ifdeclaración en una intsuma de tamaño y un salto condicional único y nunca realizar la adición más grande.

Editar: como señaló Stephen, tengo problemas para obtener un compilador (no tan bueno), gcc, para generar el cmo. El código que genera no es terriblemente lento, pero ciertamente subóptimo. Si alguien conoce variantes de este código que harán que gcc haga lo correcto, me encantaría verlas.

No, su segundo código no es correcto, pero está cerca: si establece

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

el resultado de una adición es INT_MAX. ( INT_MAXes siempre un número impar). Entonces esta es una entrada válida. Pero en tu rutina tendrás INT_MAX - half == half1y abortarías. Un falso positivo.

Este error se puede reparar poniendo en <lugar de <=ambos cheques.

Pero también su código no es óptimo. Lo siguiente sería suficiente:

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

Para ver que esto es válido, debes sumar simbólicamente lhsen ambos lados de las desigualdades, y esto te da exactamente las condiciones aritméticas de que tu resultado está fuera de los límites.

En mi humilde opinión, la forma más oriental de lidiar con el código C ++ sensible al desbordamiento es usar SafeInt<T>. Esta es una plantilla C ++ multiplataforma alojada en code plex que proporciona las garantías de seguridad que desea aquí.

• http://safeint.codeplex.com/

Lo encuentro muy intuitivo de usar, ya que proporciona muchos de los mismos patrones de uso que las operaciones numéricas normales y expresa flujos por encima y por debajo a través de excepciones.

Para el caso de gcc, de las notas de la versión de gcc 5.0 podemos ver que ahora proporciona un __builtin_add_overflowdesbordamiento para verificar además:

Se ha agregado un nuevo conjunto de funciones integradas para aritmética con verificación de desbordamiento: __builtin_add_overflow, __builtin_sub_overflow y __builtin_mul_overflow y para compatibilidad con clang también otras variantes. Estas incorporaciones tienen dos argumentos integrales (que no necesitan tener el mismo tipo), los argumentos se extienden al tipo con signo de precisión infinita, +, - o * se realiza en ellos, y el resultado se almacena en una variable entera apuntada a por el último argumento. Si el valor almacenado es igual al resultado de precisión infinita, las funciones integradas devuelven falso, de lo contrario verdadero. El tipo de variable entera que contendrá el resultado puede ser diferente de los tipos de los dos primeros argumentos.

Por ejemplo:

__builtin_add_overflow( rhs, lhs, &result )

Podemos ver en el documento gcc Funciones incorporadas para realizar aritmética con desbordamiento Verificando que:

[...] estas funciones integradas tienen un comportamiento completamente definido para todos los valores de los argumentos.

clang también proporciona un conjunto de componentes aritméticos comprobados :

Clang proporciona un conjunto de incorporaciones que implementan aritmética comprobada para aplicaciones críticas de seguridad de una manera rápida y fácilmente expresable en C.

en este caso, el incorporado sería:

__builtin_sadd_overflow( rhs, lhs, &result )

Si usa un ensamblador en línea, puede verificar el indicador de desbordamiento . Otra posibilidad es que puede utilizar un tipo de datos seguro. . Recomiendo leer este documento sobre Integer Security .

La forma más rápida posible es utilizar el GCC incorporado:

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

En x86, GCC compila esto en:

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

que utiliza la detección de desbordamiento incorporada del procesador.

Si no está de acuerdo con el uso de las funciones integradas de GCC, la siguiente forma más rápida es usar operaciones de bits en los bits de signo. Además, el desbordamiento firmado se produce cuando:

• los dos operandos tienen el mismo signo, y
• el resultado tiene un signo diferente al de los operandos.

El bit de signo de ~(lhs ^ rhs)está activado si los operandos tienen el mismo signo y el bit de signo de lhs ^ sumestá activado si el resultado tiene un signo diferente al de los operandos. Entonces puede hacer la adición en forma sin firmar para evitar un comportamiento indefinido, y luego usar el bit de signo de ~(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;
}

Esto se compila en:

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

que es bastante más rápido que la conversión a un tipo de 64 bits en una máquina de 32 bits (con 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

Es posible que tenga más suerte al convertir a enteros de 64 bits y probar condiciones similares como esa. Por ejemplo:

#include <stdint.h>

...

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

Es posible que desee ver más de cerca cómo funcionará la extensión de letreros aquí, pero creo que es correcto.

Qué tal si:

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

Creo que debería funcionar para cualquier legítimo INT_MINy INT_MAX(simétrico o no); la función como se muestra en los clips, pero debería ser obvio cómo obtener otros comportamientos).

La solución obvia es convertir a unsigned, para obtener el comportamiento de desbordamiento sin firmar bien definido:

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

Esto reemplaza el comportamiento de desbordamiento firmado indefinido con la conversión definida por la implementación de valores fuera de rango entre firmados y no firmados, por lo que debe verificar la documentación de su compilador para saber exactamente qué sucederá, pero al menos debería estar bien definido, y debería hacer lo correcto en cualquier máquina de complemento a dos que no genere señales sobre conversiones, que es prácticamente todas las máquinas y compiladores de C construidos en los últimos 20 años.

En caso de agregar dos longvalores, el código portátil puede dividir el longvalor en intpartes bajas y altas (o en shortpartes en caso de que longtenga el mismo tamaño que 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'

El uso del ensamblaje en línea es la forma más rápida si se dirige a una CPU en particular:

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'

Creo que esto funciona:

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

El uso de volatile evita que el compilador optimice la prueba porque cree que sumpuede haber cambiado entre la suma y la resta.

Usando gcc 4.4.3 para x86_64, el ensamblaje de este código hace la suma, la resta y la prueba, aunque almacena todo en la pila y las operaciones de pila innecesarias. Incluso lo intentéregister volatile int sum = pero el montaje fue el mismo.

Para una versión con solo int sum =(no volátil o registro) la función no hizo la prueba e hizo la suma usando solo una leainstrucción ( leaes Load Effective Address y se usa a menudo para hacer sumas sin tocar el registro de banderas).

Tu versión es un código más grande y tiene muchos más saltos, pero no sé cuál sería mejor .

Para mí, la verificación más simple sería verificar los signos de los operandos y de los resultados.

Examinemos la suma: el desbordamiento podría ocurrir en ambas direcciones, + o -, solo cuando ambos operandos tienen el mismo signo. Y, obviamente, el desbordamiento será cuando el signo del resultado no sea el mismo que el signo de los operandos.

Entonces, una verificación como esta será suficiente:

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

Editar: como sugirió Nils, esta es la ifcondición correcta :

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

Y desde cuando la instrucción

add eax, ebx 

conduce a un comportamiento indefinido? No existe tal cosa en la referencia del conjunto de instrucciones Intel x86.