¿Por qué la división de enteros por-1(negativa) da como resultado FPE?

gcc x86

Question

Tengo la tarea de expandir algunos comportamientos aparentemente extraños del código C (ejecutándose en x86). Puedo completar fácilmente todo lo demás, pero este realmente me ha confundido.

Fragmento de código 1 salidas -2147483648

int a = 0x80000000;
int b = a / -1;
printf("%d/n", b);

El fragmento de código 2 no genera nada y proporciona una Floating point exception

int a = 0x80000000;
int b = -1;
int c = a / b;
printf("%d/n", c);

Sé muy bien el motivo del resultado del 1 + ~INT_MIN == INT_MIN de código 1 ( 1 + ~INT_MIN == INT_MIN ), pero no puedo entender cómo puede la división de enteros por -1 generar FPE, ni puedo reproducirlo en mi teléfono Android (AArch64 , CCG 7.2.0). El código 2 solo genera el mismo código que el 1 sin ninguna excepción. ¿Es una característica de error oculto del procesador x86?

La asignación no dijo nada más (incluida la arquitectura de la CPU), pero dado que todo el curso se basa en una distribución de Linux de escritorio, puede asumir con seguridad que es un x86 moderno.

Editar : Me puse en contacto con mi amigo y él probó el código en Ubuntu 16.04 (Intel Kaby Lake, GCC 6.3.0). El resultado fue consistente con lo que se indicara en la asignación (el Código 1 emitió dicho mensaje y el Código 2 se bloqueó con FPE).

Answer 1

Ambos casos son raros, ya que el primero consiste en dividir -2147483648 por -1 y debe dar 2147483648 , y no el resultado que está recibiendo.

0x80000000 no es un número int válido en una arquitectura de 32 bits que representa números en el complemento a dos. Si calcula su valor negativo, volverá a hacerlo, ya que no tiene un número opuesto alrededor de cero. Cuando hace aritmética con enteros con signo, funciona bien para la suma y resta de enteros (siempre con cuidado, ya que es bastante fácil desbordar, cuando agrega el valor más grande a algún int) pero no puede usarlo con seguridad para multiplicar o dividir. Entonces, en este caso, estás invocando Comportamiento indefinido . Siempre se invoca un comportamiento indefinido (o un comportamiento definido de implementación, que es similar, pero no el mismo) en el desbordamiento de enteros con signo, ya que las implementaciones varían ampliamente en la implementación de eso.

Trataré de explicar lo que puede estar sucediendo (sin confianza), ya que el compilador es libre de hacer cualquier cosa, o nada en absoluto.

Concretamente, 0x80000000 como se representa en el complemento a dos es

1000_0000_0000_0000_0000_0000_0000

si complementamos este número, obtenemos (primero complementamos todos los bits, luego agregamos uno)

0111_1111_1111_1111_1111_1111_1111 + 1 =>
1000_0000_0000_0000_0000_0000_0000 !!! the same original number.

sorprendentemente el mismo número ... Tuviste un desbordamiento (no hay un valor positivo de contraparte en este número, ya que nos desbordamos al cambiar el signo), luego sacaste el bit de signo, enmascarando con

1000_0000_0000_0000_0000_0000_0000 &
0111_1111_1111_1111_1111_1111_1111 =>
0000_0000_0000_0000_0000_0000_0000

cuál es el número que usa como divisor, lo que lleva a una división por cero excepción.

Pero como dije antes, esto es lo que puede estar sucediendo en su sistema, pero no estoy seguro, ya que el estándar dice que este es un comportamiento Indefinido y, por lo tanto, puede obtener cualquier comportamiento diferente de su computadora / compilador.

NOTA 1

En lo que respecta al compilador, y el estándar no dice nada sobre los rangos válidos de int que deben implementarse (el estándar normalmente no incluye 0x8000...000 en arquitecturas complementarias de dos) el comportamiento correcto de 0x800...000 en arquitecturas complementarias de dos deben ser, ya que tiene el valor absoluto más grande para un entero de ese tipo, para dar un resultado de 0 al dividir un número por él. Pero las implementaciones de hardware normalmente no permiten dividir por tal número (ya que muchas de ellas ni siquiera implementan división entera con signo, sino que lo simulan desde una división sin signo, por lo que muchas simplemente extraen los signos y hacen una división sin signo) Eso requiere un compruebe antes de la división, y como el estándar dice Comportamiento indefinido , las implementaciones pueden evitar libremente dicha comprobación y no permiten dividir por ese número. Simplemente seleccionan el rango entero para ir de 0x8000...001 a 0xffff...fff , y luego de 0x000..0000 a 0x7fff...ffff , rechazando el valor 0x8000...0000 como no válido.

Answer 2

Aquí hay cuatro cosas:

• gcc -O0 comportamiento gcc -O0 explica la diferencia entre sus dos versiones. (Mientras clang -O0 sucede que los compila a ambos con idiv ). Y por qué obtienes esto incluso con operandos constantes de tiempo de compilación.
• x86 comportamiento de fallas de idiv versus comportamiento de la instrucción de división en ARM

• Si la matemática entera da como resultado que se entregue una señal, POSIX requiere que sea SIGFPE: ¿ En qué plataformas el número entero dividido por cero activa una excepción de punto flotante? Pero POSIX no requiere captura para ninguna operación entera en particular. (Es por eso que está permitido que x86 y ARM sean diferentes).

  La especificación Single Unix define SIGFPE como "Operación aritmética errónea ". Es confusamente llamado así por punto flotante, pero en un sistema normal con la FPU en su estado predeterminado, solo las matemáticas enteras lo elevarán. En x86, solo división entera. En MIPS, un compilador podría usar add lugar de addu para matemática firmada, por lo que podría obtener trampas en el desbordamiento de add firmado. ( gcc usa addu incluso para firmado , pero un detector de comportamiento indefinido podría usar add ).

• C Reglas de comportamiento indefinido (desbordamiento firmado y división específicamente) que permiten a gcc emitir código que puede atrapar en ese caso.

gcc sin opciones es lo mismo que gcc -O0 .

-O0 Reduzca el tiempo de compilación y haga que la depuración produzca los resultados esperados . Este es el valor predeterminado.

Esto explica la diferencia entre sus dos versiones:

gcc -O0 no gcc -O0 no intenta optimizar, sino que también se des-optimiza activamente para hacer un asm que implementa de manera independiente cada instrucción C dentro de una función. Esto permite que el comando de jump gdb funcione de manera segura, permitiéndole saltar a una línea diferente dentro de la función y actuar como si realmente estuviera saltando en la fuente C.

Tampoco puede suponer nada sobre los valores de las variables entre las declaraciones, porque puede cambiar las variables con el set b = 4 . Obviamente, esto es catastróficamente malo para el rendimiento, por lo que el código -O0 ejecuta varias veces más lento que el código normal, y por qué la optimización para -O0 específicamente no tiene sentido . También hace que la salida de -O0 asm sea realmente ruidosa y difícil de leer para un humano , debido a todo el almacenamiento / recarga y la falta de las optimizaciones más obvias.

int a = 0x80000000;
int b = -1;
// debugger can stop here on a breakpoint and modify b.
int c = a / b; // a and b have to be treated as runtime variables, not constants.
printf("%d/n", c);

Puse su código dentro de las funciones en el explorador del compilador Godbolt para obtener el asm para esas declaraciones.

Para evaluar a/b , gcc -O0 tiene que emitir código para recargar b de la memoria, y no hacer suposiciones sobre su valor.

Pero con int c = a / -1; , no puede cambiar el -1 con un depurador , por lo que gcc puede implementar esa declaración de la misma manera que implementaría int c = -a; , con una instrucción x86 neg eax o AArch64 neg w0, w0 , rodeada por una carga (a) / store (c). En ARM32, es un rsb r3, r3, #0 (resta inversa: r3 = 0 - r3 ).

Sin embargo, clang5.0 -O0 no hace esa optimización. Todavía usa idiv para a / -1 , por lo que ambas versiones idiv en x86 con clang. ¿Por qué "optimiza" gcc? Consulte Deshabilitar todas las opciones de optimización en GCC . gcc siempre se transforma a través de una representación interna, y -O0 es solo la cantidad mínima de trabajo necesaria para producir un binario. No tiene un modo "tonto y literal" que intente hacer que el asm se parezca tanto a la fuente como sea posible.

x86 idiv vs AArch64 sdiv :

x86-64:

 # int c = a / b from x86_fault()
mov eax, DWORD PTR [rbp-4]
cdq # dividend sign-extended into edx:eax
idiv DWORD PTR [rbp-8] # divisor from memory
mov DWORD PTR [rbp-12], eax # store quotient

A diferencia de imul r32,r32 , no hay idiv 2 operandos que no tenga una entrada de dividendo en la mitad superior. De todos modos, no es que importe; gcc solo lo está usando con edx = copias del bit de signo en eax , por lo que realmente está haciendo un cociente 32b / 32b => 32b + resto. idiv , idiv plantea #DE en:

• divisor = 0
• El resultado firmado (cociente) es demasiado grande para el destino.

El desbordamiento puede ocurrir fácilmente si usa el rango completo de divisores, por ejemplo, para int result = long long / int con una sola división 64b / 32b => 32b. Pero gcc no puede hacer esa optimización porque no está permitido hacer código que fallará en lugar de seguir las reglas de promoción de enteros C y hacer una división de 64 bits y luego truncar a int . Tampoco se optimiza incluso en los casos en que se sabe que el divisor es lo suficientemente grande como para no poder #DE

Al realizar la división 32b / 32b (con cdq ), la única entrada que puede desbordarse es INT_MIN / -1 . El cociente "correcto" es un entero con signo de 33 bits, es decir, un 0x80000000 positivo con un bit de signo de cero 0x80000000 para convertirlo en un entero con signo de complemento positivo de 2. Como esto no cabe en eax , idiv genera una excepción #DE . El núcleo luego entrega SIGFPE .

AArch64:

 # int c = a / b from x86_fault() (which doesn''t fault on AArch64)
ldr w1, [sp, 12]
ldr w0, [sp, 8] # 32-bit loads into 32-bit registers
sdiv w0, w1, w0 # 32 / 32 => 32 bit signed division
str w0, [sp, 4]

AFAICT, las instrucciones de división de hardware ARM no generan excepciones para dividir entre cero o INT_MIN / -1. O al menos, algunas CPU ARM no lo hacen. dividir por cero excepción en el procesador ARM OMAP3515

La documentación de AArch64 sdiv no menciona ninguna excepción.

Sin embargo, las implementaciones de software de la división de enteros pueden generar: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/ka4061.html . (gcc usa una llamada a la biblioteca para la división en ARM32 de manera predeterminada, a menos que establezca un -mcpu que tenga división HW).

C Comportamiento indefinido.

Como explica PSkocik , INT_MIN / -1 es un comportamiento indefinido en C, como todo desbordamiento de entero con signo. Esto permite a los compiladores usar instrucciones de división de hardware en máquinas como x86 sin verificar ese caso especial. Si no tuviera que fallar, las entradas desconocidas requerirían comparaciones de tiempo de ejecución y verificación de ramales, y nadie quiere que C lo requiera.

Más sobre las consecuencias de UB:

Con la optimización habilitada , el compilador puede asumir que a y b todavía tienen sus valores establecidos cuando se ejecuta a a/b . Luego puede ver que el programa tiene un comportamiento indefinido y, por lo tanto, puede hacer lo que quiera. gcc elige producir INT_MIN como lo haría desde -INT_MIN .

En un sistema de complemento a 2, el número más negativo es su propio negativo. Este es un caso de esquina desagradable para el complemento de 2, porque significa que abs(x) aún puede ser negativo. https://en.wikipedia.org/wiki/Two%27s_complement#Most_negative_number

int x86_fault() {
int a = 0x80000000;
int b = -1;
int c = a / b;
return c;
}

compila esto con gcc6.3 -O3 para x86-64

x86_fault:
mov eax, -2147483648
ret

pero clang5.0 -O3 compila a (sin advertencia incluso con -Wall -Wextra`):

x86_fault:
ret

El comportamiento indefinido realmente es totalmente indefinido. Los compiladores pueden hacer lo que quieran, incluyendo devolver cualquier basura que haya estado en eax en la entrada de la función, o cargar un puntero NULL y una instrucción ilegal. Por ejemplo, con gcc6.3 -O3 para x86-64:

int *local_address(int a) {
return &a;
}
local_address:
xor eax, eax # return 0
ret
void foo() {
int *p = local_address(4);
*p = 2;
}
foo:
mov DWORD PTR ds:0, 0 # store immediate 0 into absolute address 0
ud2 # illegal instruction

Su caso con -O0 no permitió que los compiladores vieran el UB en el momento de la compilación, por lo que obtuvo la salida asm "esperada".

Vea también Lo que todo programador de C debe saber sobre el comportamiento indefinido (la misma publicación de blog LLVM que Basile enlazó).

Answer 3

Con un comportamiento indefinido pueden pasar cosas muy bad , y a veces suceden.

Tu pregunta no tiene sentido en C (lee Lattner en UB ). Pero podría obtener el código del ensamblador (por ejemplo, producido por gcc -O -fverbose-asm -S ) y preocuparse por el comportamiento del código de máquina.

En x86-64 con desbordamiento de enteros de Linux (y también división de enteros por cero, IIRC) emite una señal SIGFPE . Ver signal(7)

Por cierto, en PowerPC la división de enteros por cero se rumorea que da -1 a nivel de máquina (pero algunos compiladores de C generan código adicional para probar ese caso).

El código en su pregunta es un comportamiento indefinido en C. El código ensamblador generado tiene un comportamiento definido (depende del ISA y el procesador).

^{(la tarea se hace para hacerte leer más sobre UB, especialmente el blog de Lattner , que deberías leer absolutamente )}

Answer 4

En x86, si divide utilizando la operación idiv (que no es realmente necesaria para argumentos constantes, ni siquiera para variables que se sabe que son constantes, pero sucedió de todos modos), INT_MIN / -1 es uno de los casos que da como resultado #DE (error de división). Es realmente un caso especial de cociente fuera de rango, en general eso es posible porque idiv divide un dividendo extra ancho por el divisor, por lo que muchas combinaciones causan desbordamiento, pero INT_MIN / -1 es el único caso que no es un div-by-0 al que normalmente puede acceder desde idiomas de nivel superior, ya que generalmente no exponen las capacidades de dividendos extra anchos.

Linux molestamente asigna el #DE a SIGFPE, lo que probablemente ha confundido a todos los que lo trataron la primera vez.

Answer 5

La división int firmada en el complemento a dos no está definida si:

1. el divisor es cero, O
2. el dividendo es INT_MIN (== 0x80000000 si int es int32_t ) y el divisor es -1 (en el complemento de dos, -INT_MIN > INT_MAX , que causa un desbordamiento de enteros, que es un comportamiento indefinido en C)

( https://www.securecoding.cert.org recomienda envolver operaciones de enteros en funciones que verifican estos casos límite)

Como está invocando un comportamiento indefinido al infringir la regla 2, cualquier cosa puede suceder y, como sucede, esta cosa en particular en su plataforma pasa a ser una señal FPE generada por su procesador.