Desbordamiento de enteros en C: estándares y compiladores

8 minutos de lectura

avatar de usuario
Charles

Editado para incluir una referencia estándar adecuada gracias a Carl Norum.

Los estados estándar C

Si una condición excepcional ocurre durante la evaluación de una expresión (es decir, si el resultado no está definido matemáticamente o no está en el rango de valores representables para su tipo), el comportamiento es indefinido.

¿Existen modificadores del compilador que garanticen ciertos comportamientos en el desbordamiento de enteros? Me gustaría evitar los demonios nasales. En particular, me gustaría forzar al compilador a ajustarse al desbordamiento.

En aras de la singularidad, tomemos el estándar como C99 y el compilador como gcc. Pero estaría interesado en respuestas para otros compiladores (icc, cl) y otros estándares (C1x, C89). De hecho, solo para molestar a la multitud de C/C++, incluso agradecería respuestas para C++0x, C++03 y C++98.

Nota: La norma internacional ISO/IEC 10967-1 puede ser relevante aquí, pero por lo que pude ver, solo se mencionó en el anexo informativo.

avatar de usuario
carpintero mate

Echa un vistazo a -ftrapv y -fwrapv:

-ftrapv

Esta opción genera trampas para el desbordamiento con signo en las operaciones de suma, resta y multiplicación.

-fwrapv

Esta opción le indica al compilador que suponga que el desbordamiento aritmético con signo de la suma, la resta y la multiplicación se ajusta utilizando la representación de complemento a dos. Esta bandera habilita algunas optimizaciones y deshabilita otras. Esta opción está habilitada de forma predeterminada para el front-end de Java, según lo exige la especificación del lenguaje Java.

  • Excelente, justo lo que quería ver. ¿Hay algo comparable para los tipos sin firmar?

    – Charles

    9 de septiembre de 2010 a las 17:53

  • @Charles, no los necesita para tipos sin firmar: el comportamiento de desbordamiento ya está bien definido para ellos (vea mi respuesta).

    –Carl Norum

    9 sep 2010 a las 18:00

  • @Charles – 6.2.5 párrafo 9: “Un cálculo que involucre operandos sin signo nunca puede desbordarse, porque un resultado que no puede ser representado por el tipo entero sin signo resultante se reduce módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante”.

    –Carl Norum

    9 de septiembre de 2010 a las 18:10


  • Tenga en cuenta que -fwrapv lo hace no garantía de que el desbordamiento se envolverá. Todo lo que hace es decirle al optimizador que puede asumir que ese es el caso. Si realmente es cierto depende de la arquitectura de su máquina.

    – café

    10 de septiembre de 2010 a las 2:20

  • @caf: ¿Sabe si hay diferencias sobre cómo -fwrapv y -fno-strict-overflow afectan las transformaciones que pueden afectar el comportamiento de ajuste, por ejemplo, convertir “int1+int2+long1” en “(int1+long1)+long2”? Creo que sería útil tener una opción para habilitar un ajuste preciso y una opción para aceptar explícitamente cualquier resultado que sea congruente con el resultado correcto (modificar el tamaño del entero), ya que cada comportamiento puede ser necesario en ciertas situaciones.

    – Super gato

    04/04/2016 a las 15:50

avatar de usuario
carl norum

Para su respuesta C99, creo 6.5 Expresionesel párrafo 5 es lo que estás buscando:

Si una condición excepcional ocurre durante la evaluación de una expresión (es decir, si el resultado no está definido matemáticamente o no está en el rango de valores representables para su tipo), el comportamiento es indefinido.

Eso significa que si obtiene un desbordamiento, no tiene suerte, no se garantiza ningún tipo de comportamiento. Los tipos sin firmar son un caso especial y nunca se desbordan (6.2.5 Tipospárrafo 9):

Un cálculo que involucre operandos sin signo nunca puede desbordarse, porque un resultado que no puede ser representado por el tipo entero sin signo resultante se reduce módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante.

C ++ tiene las mismas declaraciones, redactadas de manera un poco diferente:

  • 5 expresionespárrafo 4:

    Si durante la evaluación de una expresión, el resultado no está definido matemáticamente o no está en el rango de valores representables para su tipo, el comportamiento es indefinido. [Note: most existing implementations of C++ ignore integer overflows. Treatment of division by zero, forming a remainder using a zero divisor, and all floating point exceptions vary among machines, and is usually adjustable by a library function. —endnote]

  • 3.9.1 Tipos fundamentalespárrafo 4:

    Enteros sin signo, declarados unsignedobedecerá las leyes de la aritmética módulo 2^norte donde norte es el número de bits en la representación de valor de ese tamaño particular de entero.

  • Sí, eso es lo que estaba buscando. (Aunque la referencia me confundió al principio, ese es el párrafo 5 de 6.5, no la sección 6.5.5.) ¿Conoce alguna forma de evitar esto? El ajuste en el desbordamiento es común, y hay muchas ocasiones en las que quiero que esto suceda. ¿Algún compilador popular tiene un interruptor que les haga prometer que se envuelven?

    – Charles

    9 de septiembre de 2010 a las 17:49

  • @Charles, el comportamiento indefinido no está definido. Puede tener suerte con su compilador en particular: consulte su documentación para obtener una declaración que le dé tranquilidad. En gccpor ejemplo, puede consultar el -fstrict-overflow y -fwrapv banderas

    –Carl Norum

    9 de septiembre de 2010 a las 17:52


En C99 el comportamiento general se describe en 6.5/5

Si una condición excepcional ocurre durante la evaluación de una expresión (es decir, si el resultado no está definido matemáticamente o no está en el rango de valores representables para su tipo), el comportamiento es indefinido.

El comportamiento de los tipos sin firmar se describe en 6.2.5/9, que básicamente establece que las operaciones en tipos sin firmar nunca conducen a una condición excepcional.

Un cálculo que involucre operandos sin signo nunca puede desbordarse, porque un resultado que no puede ser representado por el tipo entero sin signo resultante se reduce módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante.

El compilador GCC tiene una opción especial -ftrapvcuyo objetivo es detectar el desbordamiento en tiempo de ejecución de las operaciones con enteros con signo.

Para completar, me gustaría agregar que Clang ahora tiene “construcciones aritméticas verificadas” como una extensión de idioma. Aquí hay un ejemplo usando la multiplicación sin signo verificada:

unsigned x, y, result;
...
if (__builtin_umul_overflow(x, y, &result)) {
    /* overflow occured */
    ...
}
...

http://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins

6.2.5 párrafo 9 es lo que estás buscando:

El rango de valores no negativos de un tipo entero con signo es un subrango del correspondiente tipo entero sin signo, y la representación del mismo valor en cada tipo es la misma.31) Un cálculo que involucre operandos sin signo nunca puede desbordarse, porque un resultado que no puede ser representado por el tipo entero sin signo resultante se reduce módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante.

Todas las publicaciones anteriores comentaban sobre el estándar C99, pero de hecho esta garantía ya estaba disponible antes.

El párrafo 5 del artículo 6.1.2.5 Tipos

de los estados estándar C89

Un cálculo que involucre operandos sin signo nunca puede desbordarse, porque un resultado que no puede ser representado por el tipo de entero sin signo resultante se reduce módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo de entero sin signo resultante.

Tenga en cuenta que esto permite a los programadores de C reemplazar todas las divisiones sin signo por alguna constante para ser reemplazada por una multiplicación con el elemento inverso del anillo formado por la aritmética de intervalo de módulo 2^N de C.

Y esto se puede hacer sin ninguna “corrección” ya que sería necesario aproximar la división con una multiplicación de punto fijo con el valor recíproco.

En su lugar, se puede usar el Algoritmo Euclidiano Extendido para encontrar el Elemento inverso y usarlo como multiplicador. (Por supuesto, para mantener la portabilidad, también se deben aplicar operaciones AND bit a bit para garantizar que los resultados tengan el mismo ancho de bit).

Puede valer la pena comentar que la mayoría de los compiladores de C ya implementan esto como una optimización. Sin embargo, dichas optimizaciones no están garantizadas y, por lo tanto, aún podría ser interesante para los programadores realizar dichas optimizaciones manualmente en situaciones donde la velocidad importa, pero las capacidades del optimizador C son desconocidas o particularmente débiles.

Y como comentario final, la razón por la que intentar hacerlo: las instrucciones a nivel de máquina para la multiplicación suelen ser mucho más rápidas que las de la división, especialmente en CPU de alto rendimiento.

avatar de usuario
jaredpar

No estoy seguro de si hay algún modificador de compilador que pueda usar para imponer un comportamiento uniforme para los desbordamientos en C/C++. Otra opción es utilizar el SafeInt<T> plantilla. Es una plantilla de C++ multiplataforma que proporciona comprobaciones definitivas de desbordamiento/subdesbordamiento para todo tipo de operaciones con enteros.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad