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 signo 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, aunque 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, según 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 cause un desbordamiento firmado, su programa será tan inválido como si eliminara la referencia a un puntero nulo. Por lo tanto, no puede provocar un comportamiento indefinido y luego intentar detectar el desbordamiento después del hecho, como en el ejemplo anterior de verificación posterior a la condición.
Aunque es probable que la comprobación anterior funcione en muchos compiladores, no puedes contar con ello. 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 indicadores de optimización, porque el compilador asume que un desbordamiento con signo es imposible. Esto rompe totalmente el intento de comprobar si hay 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 números enteros hasta que nos aseguremos de antemano de que realizar dicha suma no resultará en un desbordamiento. Por lo tanto, no provocamos ningún comportamiento indefinido.
Sin embargo, desafortunadamente esta solución es 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 igual al tipo de expresión que el compilador podría optimizar, pensando que el desbordamiento con signo es imposible.
Entonces, ¿hay una solución mejor aquí? ¿Algo que esté garantizado que 1) no causará un comportamiento indefinido y 2) no brindará al compilador la oportunidad de optimizar las comprobaciones de desbordamiento? Estaba pensando que podría haber alguna forma de hacerlo convirtiendo ambos operandos en sin firmar y realizando comprobaciones haciendo su propia aritmética en complemento a dos, pero no estoy realmente seguro de cómo hacerlo.
No, tu segundo código no es correcto, pero estás cerca: si configuras
int half = INT_MAX/2;
int half1 = half + 1;
el resultado de una suma 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 <=ambas comprobaciones.
Pero tampoco su código es óptimo. Lo siguiente serviría:
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, tienes que 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 límites.
Nota en 2023: C23 tendrá el <stdckdint.h>encabezado que implementa dichas comprobaciones de desbordamiento de la misma manera que las funciones integradas de gcc que se mencionan en otras respuestas.
Tu enfoque con la resta es correcto y está bien definido. Un compilador no puede optimizarlo.
Otro enfoque correcto, si tiene disponible un tipo entero más grande, 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 suma y ifla declaración en una intsuma de tamaño - y un único salto de desbordamiento condicional y nunca realizar la suma más grande.
Editar: Como señaló Stephen, tengo problemas para conseguir que un compilador (no tan bueno), gcc, genere el conjunto sensato. El código que genera no es terriblemente lento, pero ciertamente no es óptimo. Si alguien conoce variantes de este código que harán que gcc haga lo correcto, me encantaría verlas.
La forma más rápida posible es utilizar el GCC integrado:
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 utilizar 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 diferente signo que 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. Por lo tanto, puede realizar la suma 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 mucho más rápido que convertir 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
