Desbordamiento firmado en C ++ y comportamiento indefinido (UB)

Me pregunto sobre el uso de código como el siguiente

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Si el ciclo se repite a lo largo de los ntiempos, entonces factorse multiplica por tiempos 10exactos n. Sin embargo, factorsolo se usa después de haber sido multiplicado por 10un total de n-1veces. Si suponemos que factornunca se desborda, excepto en la última iteración del bucle, pero puede desbordarse en la última iteración del bucle, ¿debería ser aceptable ese código? En este caso, el valor de factornunca se utilizará después de que se haya producido el desbordamiento.

Estoy debatiendo si un código como este debería ser aceptado. Sería posible poner la multiplicación dentro de una declaración if y simplemente no hacer la multiplicación en la última iteración del ciclo cuando puede desbordarse. La desventaja es que satura el código y agrega una rama innecesaria que necesitaría verificar en todas las iteraciones de bucle anteriores. También podría repetir el ciclo una vez menos y replicar el cuerpo del ciclo una vez después del ciclo, nuevamente, esto complica el código.

El código real en cuestión se usa en un bucle interno ajustado que consume una gran parte del tiempo total de la CPU en una aplicación de gráficos en tiempo real.

Los compiladores suponen que un programa C ++ válido no contiene UB. Considere por ejemplo:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Si x == nullptrluego lo desreferencia y le asigna un valor es UB. Por lo tanto, la única forma en que esto podría terminar en un programa válido es cuando x == nullptrnunca dará verdadero y el compilador puede asumir bajo la regla como si, lo anterior es equivalente a:

*x = 5;

Ahora en tu código

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

La última multiplicación de factorno puede suceder en un programa válido (el desbordamiento firmado no está definido). Por lo tanto, la asignación a resultno puede suceder. Como no hay forma de bifurcarse antes de la última iteración, tampoco puede ocurrir la iteración anterior. Eventualmente, la parte del código que es correcta (es decir, nunca ocurre un comportamiento indefinido) es:

// nothing :(

El comportamiento del intdesbordamiento no está definido.

No importa si lees factorfuera del cuerpo del bucle; si se ha desbordado para entonces, entonces el comportamiento de su código en, después y algo paradójicamente antes de que el desbordamiento sea indefinido.

Un problema que puede surgir al mantener este código es que los compiladores se están volviendo cada vez más agresivos cuando se trata de la optimización. En particular, están desarrollando un hábito en el que suponen que el comportamiento indefinido nunca ocurre. Para que este sea el caso, pueden eliminar el forbucle por completo.

¿No puede usar un unsignedtipo para factoraunque debería preocuparse por la conversión no deseada de inta unsigneden expresiones que contengan ambos?

Puede ser perspicaz considerar los optimizadores del mundo real. El desenrollado de bucles es una técnica conocida. La idea básica del desenrollamiento del ciclo operativo es que

for (int i = 0; i != 3; ++i)
    foo()

podría implementarse mejor detrás de escena como

 foo()
 foo()
 foo()

Este es el caso fácil, con un límite fijo. Pero los compiladores modernos también pueden hacer esto para límites variables:

for (int i = 0; i != N; ++i)
   foo();

se convierte

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Obviamente, esto solo funciona si el compilador sabe que N <= 3. Y ahí es donde volvemos a la pregunta original. Debido a que el compilador sabe que no se produce un desbordamiento firmado , sabe que el bucle puede ejecutarse un máximo de 9 veces en arquitecturas de 32 bits. 10^10 > 2^32. Por lo tanto, puede desenrollar un bucle de 9 iteraciones. ¡Pero el máximo previsto era 10 iteraciones! .

Lo que podría suceder es que obtenga un salto relativo a una instrucción de ensamblaje (9-N) con N = 10, por lo que un desplazamiento de -1, que es la instrucción de salto en sí. Ups Esta es una optimización de bucle perfectamente válida para C ++ bien definido, pero el ejemplo dado se convierte en un bucle infinito ajustado.

Cualquier desbordamiento de entero con signo da como resultado un comportamiento indefinido, independientemente de si el valor desbordado se lee o no.

Tal vez en su caso de uso pueda sacar la primera iteración del bucle, convirtiendo esto

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

dentro de esto

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

Con la optimización habilitada, el compilador podría desenrollar el segundo bucle anterior en un salto condicional.

Este es UB; en términos de ISO C ++, el comportamiento completo de todo el programa no está especificado para una ejecución que finalmente llega a UB. El ejemplo clásico es que, en lo que respecta al estándar C ++, puede hacer que los demonios salgan volando de tu nariz. (Recomiendo no usar una implementación donde los demonios nasales sean una posibilidad real). Ver otras respuestas para más detalles.

Los compiladores pueden "causar problemas" en el momento de la compilación para las rutas de ejecución que pueden ver que conducen a una UB visible en tiempo de compilación, por ejemplo, supongamos que nunca se alcanzan esos bloques básicos.

Consulte también Lo que todo programador de C debe saber sobre el comportamiento indefinido (blog LLVM). Como se explica allí, UB de desbordamiento firmado permite a los compiladores probar que los for(... i <= n ...)bucles no son infinitos, incluso para desconocidos n. También les permite "promover" los contadores de bucle int al ancho del puntero en lugar de rehacer la extensión de signo. (Entonces, la consecuencia de UB en ese caso podría ser acceder fuera de los elementos bajos de 64k o 4G de una matriz, si esperaba un ajuste firmado ien su rango de valores).

En algunos casos, los compiladores emitirán una instrucción ilegal como x86 ud2para un bloque que probablemente cause UB si alguna vez se ejecuta. (Tenga en cuenta que una función puede no siempre ser llamado, por lo que los compiladores pueden no en los estribos General Ir y romper otras funciones, o incluso los posibles caminos a través de una función que no golpeó UB. Es decir, el código de máquina que compila al mosto todavía trabajo para todas las entradas que no conducen a UB.)

Probablemente la solución más eficiente es pelar manualmente la última iteración para factor*=10evitar lo innecesario .

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

O si el cuerpo del bucle es grande, considere simplemente usar un tipo sin signo para factor. Luego, puede dejar que se multiplique el desbordamiento sin signo y simplemente se ajustará bien a una potencia de 2 (el número de bits de valor en el tipo sin signo).

Esto está bien incluso si lo usa con tipos con signo, especialmente si su conversión sin signo-> con signo nunca se desborda.

La conversión entre sin signo y el complemento de 2 con signo es libre (mismo patrón de bits para todos los valores); el ajuste del módulo para int -> unsigned especificado por el estándar C ++ se simplifica al uso del mismo patrón de bits, a diferencia del complemento o signo / magnitud.

Y unsigned- >igned es igualmente trivial, aunque está definido por la implementación para valores mayores que INT_MAX. Si no está utilizando el enorme resultado sin firmar de la última iteración, no tiene nada de qué preocuparse. Pero si es así, vea ¿La conversión de sin firmar a firma no está definida? . El caso del valor no encaja está definido por la implementación , lo que significa que una implementación debe elegir algún comportamiento; los cuerdos simplemente truncan (si es necesario) el patrón de bits sin signo y lo usan como firmado, porque eso funciona para valores dentro del rango de la misma manera sin trabajo adicional. Y definitivamente no es UB. Por lo tanto, los grandes valores sin signo pueden convertirse en enteros con signo negativo. por ejemplo, después de que int x = u; gcc y clang no se optimicenx>=0como siempre es cierto, incluso sin ellos -fwrapv, porque definieron el comportamiento.

Si puede tolerar algunas instrucciones de ensamblaje adicionales en el bucle, en lugar de

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

puedes escribir:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

para evitar la última multiplicación. !factorno introducirá una rama:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Este código

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

también da como resultado un ensamblaje sin ramificación después de la optimización:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Compilado con GCC 8.3.0 -O3)

No mostraste lo que está entre paréntesis de la fordeclaración, pero voy a asumir que es algo como esto:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Simplemente puede mover el incremento de contador y la verificación de terminación de bucle al cuerpo:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

El número de instrucciones de montaje en el bucle seguirá siendo el mismo.

Inspirado en la presentación de Andrei Alexandrescu "La velocidad se encuentra en la mente de las personas".

Considere la función:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

Según la justificación publicada, los autores de la Norma habrían esperado que si se invocara esta función en (por ejemplo) una computadora común de 32 bits con argumentos de 0xC000 y 0xC000, promover los operandos de *a signed intcausaría que el cálculo produjera -0x10000000 , que cuando se convierte en unsignedproduciría la 0x90000000umisma respuesta que si hubieran unsigned shortpromovido a unsigned. No obstante, gcc a veces optimizará esa función de manera que se comportaría sin sentido si se produce un desbordamiento. Cualquier código en el que alguna combinación de entradas pueda causar un desbordamiento debe procesarse con la -fwrapvopción a menos que sea aceptable permitir a los creadores de entradas mal formadas deliberadamente ejecutar código arbitrario de su elección.

¿Por qué no esto?

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;

Hay muchas caras diferentes de Comportamiento indefinido, y lo que es aceptable depende del uso.

circuito interno ajustado que consume una gran parte del tiempo total de la CPU en una aplicación de gráficos en tiempo real

Eso, por sí mismo, es un poco inusual, pero sea como sea ... si este es el caso, entonces la UB probablemente esté dentro del reino "permisible, aceptable" . La programación de gráficos es conocida por hacks y cosas feas. Siempre y cuando "funcione" y no demore más de 16.6 ms en producir un marco, por lo general, a nadie le importa. Pero aún así, tenga en cuenta lo que significa invocar a UB.

Primero, está el estándar. Desde ese punto de vista, no hay nada que discutir y no hay forma de justificar, su código es simplemente inválido. No hay si ni cuándo, simplemente no es un código válido. También podría decir que es medio dedo desde su punto de vista, y el 95-99% del tiempo estará listo para ir de todos modos.

Luego, está el lado del hardware. Hay algunas arquitecturas poco comunes y extrañas en las que esto es un problema. Estoy diciendo "poco común, raro" porque en la arquitectura que conforma el 80% de todas las computadoras (o las dos arquitecturas que juntas conforman el 95% de todas las computadoras) el desbordamiento es un "sí, lo que sea, no me importa" cosa en el nivel de hardware. Seguro que obtienes un resultado basura (aunque aún predecible), pero no suceden cosas malas.
Eso no esEn el caso de todas las arquitecturas, es muy posible que tenga una trampa en el desbordamiento (aunque viendo cómo habla de una aplicación de gráficos, las posibilidades de estar en una arquitectura tan extraña son bastante pequeñas). ¿Es la portabilidad un problema? Si es así, es posible que desee abstenerse.

Por último, está el lado del compilador / optimizador. Una razón por la cual el desbordamiento no está definido es que simplemente dejarlo así fue más fácil de hacer frente al hardware una vez. Pero otra razón es que, por ejemplo, x+1se garantiza que siempre será mayor que x, y el compilador / optimizador puede explotar este conocimiento. Ahora, para el caso mencionado anteriormente, se sabe que los compiladores actúan de esta manera y simplemente eliminan los bloques completos (existió un exploit de Linux hace algunos años que se basó en que el compilador eliminó algún código de validación debido exactamente a esto).
Para su caso, dudaría seriamente de que el compilador haga algunas optimizaciones especiales, extrañas. Sin embargo, qué sabes, qué sé yo. En caso de duda, pruébalo. Si funciona, estás listo para irte.

(Y finalmente, por supuesto, hay una auditoría de código, puede que tenga que perder el tiempo discutiendo esto con un auditor si no tiene suerte).