rilevamento della moltiplicazione di overflow di uint64_t con C

Question

Esiste un modo efficiente e portatile per verificare quando le operazioni di moltiplicazione con gli operandi int64_t o uint64_t hanno un overflow in C?

Ad esempio, per l'aggiunta di uint64_t posso fare:

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

Ma non può arrivare a una semplice espressione simile per la moltiplicazione.

Tutto ciò che accade a me è rompere gli operandi in parti alte e basse uint32_t ed eseguire la moltiplicazione di quelle parti mentre si verifica un overflow, qualcosa di veramente brutto e probabilmente inefficiente.

Update 1: Alcuni codice di riferimento attuare diversi approcci aggiunto

Update 2: Jens metodo Gustedt aggiunto

programma di 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); 
} 

Finora, caso 4 che utilizza il punto mobile per filtrare la maggior parte dei casi è il più veloce quando si presume che gli overflow siano molto insoliti, almeno sul mio computer dove sono solo due t è più lento del caso del nulla.

Caso 5, è del 30% più lento di 4, ma esegue sempre la stessa, non v'è alcun numero di casi speciali che richiedono un'elaborazione più lenta come accade con 4.

Answer 1

Se si vuole evitare la divisione come in Ambroz' risposta:

Prima di tutto bisogna vedere che il più piccolo dei due numeri, dicono a, è a meno di 2 , altrimenti il ​​risultato verrà comunque traboccare. Sia b decomposto nelle due parole a 32 bit che è b = + d.

Il calcolo quindi non è così difficile, ho trovato:

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); 
} 

quindi questo sono due moltiplicazioni, due turni, alcune aggiunte e controlli di condizione. Questo potrebbe essere più efficiente della divisione perché, per esempio, le due moltiplicazioni possono essere pipeline in paralle. Dovresti fare un benchmark per vedere cosa funziona meglio per te.

Answer 2

realtà, lo stesso principio può essere usato per la moltiplicazione:

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; 

Per numeri interi simili, è possibile che sia necessario un caso per ciascuna combinazione di segni.

Answer 3

Domanda correlata con alcune (auspicabilmente) risposte utili: Best way to detect integer overflow in C/C++. Inoltre non copre uint64_t solo;)

Answer 4

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; 

Questo metodo confronta (possibilmente traboccante) il risultato di una normale moltiplicazione con il risultato della moltiplicazione, che non può eccedere. Tutti i calcoli sono modulo (2^32 - 1).

È più complicato e (molto probabilmente) non più veloce del metodo di Jens Gustedt.

Dopo alcune piccole modifiche può moltiplicarsi con precisione a 96 bit (ma senza controllo di overflow). Cosa potrebbe essere più interessante, l'idea di questo metodo può essere usata per controllare l'overflow per una serie di operazioni aritmetiche (moltiplicazioni, aggiunte, sottrazioni).

Alcune domande hanno risposto alla

Prima di tutto, circa "your code is not portable". Sì, il codice non è portatile perché utilizza uint64_t, che è richiesto nella domanda originale. A rigor di termini, non è possibile ottenere una risposta portatile con (u)int64_t perché non è richiesto dallo standard.

A proposito di "once some overflow happens, you can not assume the result value to be anything". Lo standard dice che gli iteger non firmati non possono eccedere. Capitolo 6.2.5, punto 9:

Un calcolo coinvolge operandi unsigned può mai troppopieno, perché un risultato che non può essere rappresentato dal tipo intero senza segno risultante viene ridotta modulo il numero che è maggiore di uno rispetto grande valore che può essere rappresentato dal tipo risultante.

Quindi la moltiplicazione a 64 bit senza segno viene eseguita modulo 2^64, senza overflow.

Ora circa il "logic behind". "Funzione hash" non è la parola corretta qui. Uso solo i calcoli modulo (2^32 - 1). Il risultato della moltiplicazione può essere rappresentato come n*2^64 + m, dove m è il risultato visibile e n significa quanto superiamo. Dal 2^64 = 1 (mod 2^32 - 1), possiamo calcolare [true value] - [visible value] = (n*2^64 + m) - m = n*2^64 = n (mod 2^32 - 1). Se il valore calcolato di n non è zero, c'è un overflow. Se è zero, non c'è overflow. Eventuali collisioni sono possibili solo dopo n >= 2^32 - 1. Ciò non accadrà mai poiché controlliamo che uno dei moltiplicativi sia inferiore a 2^32.

Answer 5

Potrebbe non rilevare overflow esatte, ma in generale è possibile verificare il risultato della vostra moltiplicazione su una scala logaritmica:

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; 

Dipende se si ha realmente bisogno di fare la moltiplicazione fino a esigere UINT64_MAX, altrimenti questo un modo molto portatile e conveniente per controllare le moltiplicazioni di grandi numeri.