¿Cómo hacer un doble fragmento sin un comportamiento indefinido?

Question

EDIT Advertencia de salud pública: esta pregunta incluye una suposición falsa sobre el comportamiento indefinido. Ver respuesta aceptada

Después de leer recent blog post, he estado pensando mucho acerca de la practicidad de evitar todos los estándares: suposiciones indefinidas en los códigos C y C++. Aquí hay un fragmento cortado de C++, para hacer un sin firmar, además de 128 bits ...

void c_UInt64_Pair::operator+= (const c_UInt64_Pair &p) 
{ 
    m_Low += p.m_Low; 
    m_High += p.m_High; 

    if (m_Low < p.m_Low) m_High++; 
} 

Esto se basa claramente en supuestos sobre el comportamiento de desbordamiento. Obviamente, la mayoría de las máquinas pueden admitir un entero binario del tipo correcto (aunque quizás construyendo fragmentos de 32 bits o lo que sea), pero aparentemente hay una posibilidad creciente de que el optimizador pueda explotar el comportamiento no definido de las normas aquí. Es decir, la única forma en que la condición m_Low < p.m_Low puede pasar es si m_Low += p.m_Low se desborda, lo que es un comportamiento indefinido, por lo que el optimizador puede decidir legalmente que la condición siempre falla. En cuyo caso, este código simplemente se rompe.

La pregunta es, por lo tanto ...

¿Cómo se puede escribir una versión razonablemente eficiente de los anteriores sin depender de un comportamiento indefinido?

Supongamos que tiene un entero de máquina binaria de 64 bits apropiado, pero que tiene un compilador malintencionado que siempre interpretará su comportamiento indefinido de la peor manera posible (o imposible). Además, suponga que no tiene tiene alguna biblioteca incorporada, intrínseca especial o lo que sea que lo haga por usted.

EDITAR pequeña aclaración - esto no es sólo acerca de la detección de desbordamiento, sino también asegurar que tanto m_Low y m_High terminan con el módulo correcto 2^64 resultados, que es también normas no definido.

Answer 1

A partir del estándar C++ 1998, 3.9.1 (4): "Los enteros sin signo, declarados sin signo, obedecerán las leyes del módulo aritmético 2^n donde n es el número de bits en la representación del valor de ese tamaño particular de entero." Tenga en cuenta que "entero", aquí, se refiere a cualquier tipo de entero en lugar de solo int.

Por lo tanto, suponiendo que esos son enteros sin signo, como sugiere el "UInt64" en el tipo, este comportamiento se define en C++ y debería funcionar como se esperaba.

Answer 2

Si desea un método realmente eficiente, tendrá que codificar en algo que no sea C o C++. Para razonablemente eficiente, debe asegurarse de que el desbordamiento nunca ocurra, y detectar y compensar cuando lo haría.

Básicamente, para cada componente de 64 bits, necesita calcular por separado las adiciones utilizando los 63 bits bajos y los bits más altos. A partir de estos cálculos separados puede calcular cuál fue el total de 64 bits y si hubo un acarreo.

Luego, cuando hagas el agregado superior de 64 bits, agregas el acarreo, si hay uno. Si se produce un acarreo, se ha desbordado su variable de 128 bits y tendrá que desencadenar una excepción o manejar el caso.