Detectando la multiplicación de uint64_t enteros desbordados con C

multiplication integer-overflow

Question

¿Hay alguna manera eficiente y portátil de verificar cuándo se desbordan los operandos de las operaciones de multiplicación con int64_t o uint64_t en C?

Por ejemplo, para la adición de uint64_t puedo hacer:

if (UINT64_MAX - a < b) overflow_detected();
else sum = a + b;

Pero no puedo llegar a una expresión simple similar para la multiplicación.

Todo lo que se me ocurre es dividir los operandos en partes altas y bajas de uint32_t y realizar la multiplicación de esas partes mientras se verifica el desbordamiento, algo realmente feo y probablemente ineficiente también.

Actualización 1 : Se agregaron algunos códigos de referencia que implementan varios enfoques.

Actualización 2 : Método Jens Gustedt agregado

programa de benchmarking:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define N 100000000

int d = 2;

#define POW_2_64 ((double)(1 << 31) * (double)(1 << 31) * 4)

#define calc_b (a + c)
// #define calc_b (a + d)

int main(int argc, char *argv[]) {
    uint64_t a;
    uint64_t c = 0;
    int o = 0;
    int opt;

    if (argc != 2) exit(1);

    opt = atoi(argv[1]);

    switch (opt) {

    case 1: /* faked check, just for timing */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if (c > a) o++;
            c += b * a;
        }
        break;

    case 2: /* using division */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if (b && (a > UINT64_MAX / b)) o++;
            c += b * a;
        }
        break;

    case 3: /* using floating point, unreliable */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if ((double)UINT64_MAX < (double)a * (double)b) o++;
            c += b * a;
        }
        break;

    case 4: /* using floating point and division for difficult cases */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            double m = (double)a * (double)b;
            if ( ((double)(~(uint64_t)(0xffffffff)) < m ) &&
                 ( (POW_2_64 < m) ||
                   ( b &&
                     (a > UINT64_MAX / b) ) ) ) o++;
            c += b * a;
        }
        break;

    case 5: /* Jens Gustedt method */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            uint64_t a1, b1;
            if (a > b) { a1 = a; b1 = b; }
            else       { a1 = b; b1 = a; }
            if (b1 > 0xffffffff) o++;
            else {
                uint64_t a1l = (a1 & 0xffffffff) * b1;
                uint64_t a1h = (a1 >> 32) * b1 + (a1l >> 32);
                if (a1h >> 32) o++;
            }
            c += b1 * a1;
        }
        break;

    default:
        exit(2);
    }
    printf("c: %lu, o: %u/n", c, o);
}

Hasta ahora, el caso 4 que usa un punto flotante para filtrar la mayoría de los casos es el más rápido cuando se supone que los desbordamientos son muy inusuales, al menos en mi computadora, donde es solo dos veces más lento que el caso de no hacer nada.

El caso 5, es un 30% más lento que el 4, pero siempre funciona igual, no hay ningún número de caso especial que requiera un procesamiento más lento como ocurre con el 4.

Answer 1

En realidad, el mismo principio puede usarse para la multiplicación:

uint64_t a;
uint64_t b;
...
if (b != 0 && a > UINT64_MAX / b) { // if you multiply by b, you get: a * b > UINT64_MAX
    < error >
}
uint64_t c = a * b;

Para los enteros con signo se puede hacer algo similar, es probable que necesite un caso para cada combinación de signos.

Answer 2

Es posible que no detecte desbordamientos exactos, pero en general puede probar el resultado de su multiplicación en una escala logarítmica:

if (log(UINT64_MAX-1) - log(a) - log(b) < 0) overflow_detected(); // subtracting 1 to allow some tolerance when the numbers are converted to double
else prod = a * b;

Depende de si realmente necesita hacer la multiplicación hasta el valor UINT64_MAX exacto, de lo contrario, esta es una forma muy portátil y conveniente de verificar multiplicaciones de números grandes.

Answer 3

Pregunta relacionada con algunas respuestas útiles (con suerte): la mejor manera de detectar el desbordamiento de enteros en C / C ++ . Además, no cubre solo uint64_t ;)

Answer 4

Si quieres evitar la división como en la respuesta de Ambroz:

Primero debe ver que el menor de los dos números, por ejemplo a , es menor que 2 ³² , de lo contrario, el resultado se desbordará de todos modos. Sea b descompuesto en las dos palabras de 32 bits que es b = c 2 ³² + d .

El cálculo entonces no es tan difícil, me parece:

uint64_t mult_with_overflow_check(uint64_t a, uint64_t b) {
  if (a > b) return mult_with_overflow_check(b, a);
  if (a > UINT32_MAX) overflow();
  uint32_t c = b >> 32;
  uint32_t d = UINT32_MAX & b;
  uint64_t r = a * c;
  uint64_t s = a * d;
  if (r > UINT32_MAX) overflow();
  r <<= 32;
  return addition_with_overflow_check(s, r);
}

así que estas son dos multiplicaciones, dos turnos, algunas adiciones y comprobaciones de condición. Esto podría ser más eficiente que la división porque, por ejemplo, las dos multiplicaciones se pueden canalizar en paralelo. Tendría que hacer una prueba comparativa para ver qué funciona mejor para usted.

Answer 5

case 6:
    for (a = 0; a < N; a++) {
        uint64_t b = a + c;
        uint64_t a1, b1;
        if (a > b) { a1 = a; b1 = b; }
        else       { a1 = b; b1 = a; }
        uint64_t cc = b1 * a1;
        c += cc;
        if (b1 > 0xffffffff) o++;
        else {
            uint64_t a1l = (a1 & 0xffffffff) + (a1 >> 32);
            a1l = (a1 + (a1 >> 32)) & 0xffffffff;
            uint64_t ab1l = a1l * b1;
            ab1l = (ab1l & 0xffffffff) + (ab1l >> 32);
            ab1l += (ab1l >> 32);
            uint64_t ccl = (cc & 0xffffffff) + (cc >> 32);
            ccl += (ccl >> 32);
            uint32_t ab32 = ab1l; if (ab32 == 0xffffffff) ab32 = 0;
            uint32_t cc32 = ccl; if (cc32 == 0xffffffff) cc32 = 0;
            if (ab32 != cc32) o++;
        }
    }
    break;

Este método compara (posiblemente el desbordamiento) del resultado de la multiplicación normal con el resultado de la multiplicación, que no puede desbordarse. Todos los cálculos son módulo (2 ^ 32 - 1).

Es más complicado y (lo más probable) no más rápido que el método de Jens Gustedt.

Después de algunas pequeñas modificaciones, se puede multiplicar con una precisión de 96 bits (pero sin control de desbordamiento). Lo que puede ser más interesante, la idea de este método se puede usar para verificar el desbordamiento de una serie de operaciones aritméticas (multiplicaciones, sumas, restas).

Algunas preguntas respondidas

En primer lugar, sobre "your code is not portable" . Sí, el código no es portátil porque utiliza uint64_t , que se solicita en la pregunta original. Estrictamente hablando, no puede obtener ninguna respuesta portátil con (u)int64_t porque no es un requisito estándar.

Acerca de "once some overflow happens, you can not assume the result value to be anything" . Estándar dice que los itegers sin firmar no pueden desbordarse. Capítulo 6.2.5, punto 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 en módulo, el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante.

Por lo tanto, la multiplicación de 64 bits sin firmar se realiza en el módulo 2 ^ 64, sin desbordamiento.

Ahora sobre la "logic behind" . "Función hash" no es la palabra correcta aquí. Sólo uso los cálculos de módulo (2^32 - 1) . El resultado de la multiplicación se puede representar como n*2^64 + m , donde m es el resultado visible, y n significa cuánto desbordamos. Como 2^64 = 1 (mod 2^32 - 1) , podemos calcular [true value] - [visible value] = (n*2^64 + m) - m = n*2^64 = n (mod 2^32 - 1) . Si el valor calculado de n no es cero, hay un desbordamiento. Si es cero, no hay desbordamiento. Cualquier colisión es posible solo después de n >= 2^32 - 1 . Esto nunca sucederá ya que verificamos que uno de los multiplicandos sea menor que 2^32 .