[C] Rilevare overflow in somma/moltiplicazione

[mfonz85]

Ciao a tutti,
Altro problema da sottoporvi: l'overflow.
In un esercizio che devo fare, mi si chiede di prendere 2 numeri su 1, 2 o 4 byte ciascuno, e farci delle operazioni algebriche di base sopra: addizione, sottrazione, moltiplicazione e divisione, e inserire il risultato in una variabile delle stesse dimensioni di quelle di partenza.
Ovvero, se i due operandi sono 32 e 71, contenuti in variabili da 1 byte, e l'operazione è moltiplicazione, il risultato 32*71 deve essere inserito in una variabile di dimensione 1 byte (come gli operandi) e bisogna controllare la presenza di overflow.
Questo ragionamento và applicato a numeri su 1, 2 e 4 byte e per tutte le operazioni di base.
Ora...c'è un metodo veloce, rapido, efficace, di stra-bella programmazione per rilevare overflow in queste operazioni??

Ho trovato in rete queste macro, che uso per calcolarmi al volo i limiti delle variabili su 1 byte (int8_t), 2 byte (int16_t) e 4 byte (int32_t):

#define __HALF_MAX_SIGNED(type) ((type)1 << (sizeof(type)*8-2))
#define __MAX_SIGNED(type) (__HALF_MAX_SIGNED(type) - 1 + __HALF_MAX_SIGNED(type))
#define __MIN_SIGNED(type) (-1 - __MAX_SIGNED(type))

#define __MIN(type) ((type)-1 < 1?__MIN_SIGNED(type):(type)0)
#define __MAX(type) ((type)~__MIN(type))

Vorrei utilizzare queste per creare delle funzioni di ricerca overflow del tipo

bool isSumOverflow(int32_t a, int32_t b, int8_t bit) {
   if(bit == 1) #CHECK_FOR_OVERFLOW# return 1;
   if(bit == 2) #CHECK_FOR_OVERFLOW# return 1;
   if(bit == 4) #CHECK_FOR_OVERFLOW# return 1;
}

bool isMultOverflow(int32_t a, int32_t b, int8_t bit) {
   if(bit == 1) #CHECK_FOR_MULT_OVERFLOW# return 1;
   if(bit == 2) #CHECK_FOR_MULT_OVERFLOW# return 1;
   if(bit == 4) #CHECK_FOR_MULT_OVERFLOW# return 1;
}

Dove passo su a e b le variabili castate a int32_t per semplicità, e sulla variabile "bit" il numero di bit "veri" delle variabili a e b.

In realtà per la somma già ho una mezza soluzione...

int isSumOverflow(int32_t a, int32_t b, int8_t bit) {
    if(a < 0) a = abs(a);
    if(b < 0) b = abs(b);
    if(bit == 1) return a > 0 && b > 0 && b > (__MAX(int8_t) - a);
    if(bit == 2) return a > 0 && b > 0 && b > (__MAX(int16_t) - a);
    if(bit == 4) return a > 0 && b > 0 && b > (__MAX(int32_t) - a);
    else return 0;
}

Poi per la sottrazione ci si riconduce alla somma, e per la divisione può solo verificarsi underflow (banale).

Per la moltiplicazione invece? Avreste idee?
E per quanto riguarda la somma, avete idee migliori della mia?

[xorshadow]

Guarda qui, fa proprio a caso tuo:
http://msdn.microsoft.com/library/de...re01142004.asp

[andbin]

Originariamente inviato da mfonz85

Ora...c'è un metodo veloce, rapido, efficace, di stra-bella programmazione per rilevare overflow in queste operazioni??

In una somma di due valori con segno, si ha overflow quando avviene uno dei seguenti casi:
- Due numeri entrambi positivi sommati danno come risultato un numero negativo
- Due numeri entrambi negativi sommati danno come risultato un numero positivo

Quindi ti basta verificare i segni degli operandi e del risultato.

[mfonz85]

Originariamente inviato da andbin

In una somma di due valori con segno, si ha overflow quando avviene uno dei seguenti casi:
- Due numeri entrambi positivi sommati danno come risultato un numero negativo
- Due numeri entrambi negativi sommati danno come risultato un numero positivo

Quindi ti basta verificare i segni degli operandi e del risultato.

Ok, quindi la mia soluzione è perfetta

int isSumOverflow(int32_t a, int32_t b, int8_t bit) {
    if(a < 0) a = abs(a);
    if(b < 0) b = abs(b);
    if(bit == 1) return a > 0 && b > 0 && b > (__MAX(int8_t) - a);
    if(bit == 2) return a > 0 && b > 0 && b > (__MAX(int16_t) - a);
    if(bit == 4) return a > 0 && b > 0 && b > (__MAX(int32_t) - a);
    else return 0;
}

Ma per la moltiplicazione?? Di idee semplici non me ne vengono

[andbin]

Originariamente inviato da mfonz85

int isSumOverflow(int32_t a, int32_t b, int8_t bit) {
    if(a < 0) a = abs(a);
    if(b < 0) b = abs(b);
    if(bit == 1) return a > 0 && b > 0 && b > (__MAX(int8_t) - a);
    if(bit == 2) return a > 0 && b > 0 && b > (__MAX(int16_t) - a);
    if(bit == 4) return a > 0 && b > 0 && b > (__MAX(int32_t) - a);
    else return 0;
}

A dire il vero basta una banale macro:

#define IS_OVERFLOW(a,b,r) ((a) < 0 == (b) < 0 && (b) < 0 != (r) < 0)

[mfonz85]

Originariamente inviato da andbin

A dire il vero basta una banale macro:

#define IS_OVERFLOW(a,b,r) ((a) < 0 == (b) < 0 && (b) < 0 != (r) < 0)

ehehe, grazie andbin
sono io che non sono capace di fare queste finezze
implemento subito il tuo codice-capolavoro
ma dimmi un pò...per la moltiplicazione??
non c'è nessuna via oltre a quella di mettersi lì e fare moltiplicazioni e somme parziali fino a che non si arriva all'overflow?? (se c'è)

[mfonz85]

ok, per la moltiplicazione ho avuto l'idea...mi sembra banale, ma credo funzioni...

Se ho un numero massimo, mettiamo caso 32767 numero signed su 16 bit, e devo vedere se 2 numeri moltiplicati tra loro vanno in overflow: trovo il minimo e il massimo tra i 2 numeri e poi divido il massimo numero rappresentabile su 16 bit signed con il massimo fattore della moltiplicazione: se il risultato di questa operazione è minore del secondo fattore, siamo in overflow...altrimenti no

150*160 = 24000 (ok, minore di 32767)
32767 / 160 = 204
204 > 150 (no overflow, perchè il secondo fattore sta dentro il 204)

150*260 = 39000 (overflow)
32767 / 260 = 126
126 < 150 (overflow, il secondo fattore sta fuori dal 126)

#define __HALF_MAX_SIGNED(type) ((type)1 << (sizeof(type)*8-2))
#define __MAX_SIGNED(type) (__HALF_MAX_SIGNED(type) - 1 + __HALF_MAX_SIGNED(type))
#define __MIN_SIGNED(type) (-1 - __MAX_SIGNED(type))

#define __MIN(type) ((type)-1 < 1?__MIN_SIGNED(type):(type)0)
#define __MAX(type) ((type)~__MIN(type))

#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a,b) ((a) > (b) ? (a):(b)) 

int isMultOverflow(int32_t a, int32_t b, int8_t bit) {
    int massimo = max(a,b);
    int minimo = min(a,b);
    if( bit == 1 ) return( minimo > (__MAX(int8_t) / massimo) );
    else if( bit == 2 ) return( minimo > (__MAX(int16_t) / massimo) );
    else if( bit == 4 ) return( minimo > (__MAX(int32_t) / massimo) );
    else return 1;
}

Che programmazione burina, mi sento uno "zappatore del C"

L'ho scritta al volo, così al brucio, ora ci faccio un pò di debugging, non si sa mai...

e tipo fare (l'esempio è in java, è l'unico linguaggio che conosaco per adesso ):

boolean overflow(int fattore1, int fattore2, int valore massimo){ //col III parametro intendo il valore massimo che un tipo può tenere, quindi un signed byte-->127, etc...
fattore1=fattore1<0?-fattore1:fattore1; //trovo il valore assoluto
fattore2=fattore2<0?-fattore2:fattore2;
if(fattore2>massimo/fattore1)
    return true; //c'è overflow
else
    return false;
}

in realtà essendo il negativo del basso valore rappresentabile + grande del valore + grande (tipo per un signed byte gli estremi sono -128 e 127, almeno così in java, scusa la mia ignoranza) allora questa soluzione non funziona alla perfeione, ma si potrebbe modificare in modo da mettere un parametro che indica anche il valore + basso, e poi nell'if comparare il positivo solo se lo xor dei segni dei due fattori è false.

P.S.
dico cazzate?

edit: wow mi sono appena accorto che abbiamo postato la stessa soluzione

[mfonz85]

Originariamente inviato da pisto

e tipo fare (l'esempio è in java, è l'unico linguaggio che conosaco per adesso ):

boolean overflow(int fattore1, int fattore2, int valore massimo){ //col III parametro intendo il valore massimo che un tipo può tenere, quindi un signed byte-->127, etc...
fattore1=fattore1<0?-fattore1:fattore1; //trovo il valore assoluto
fattore2=fattore2<0?-fattore2:fattore2;
if(fattore2>massimo/fattore1)
    return true; //c'è overflow
else
    return false;
}

Accidenti, mi hai fatto accorgere di un errore banale nel mio codice...
Comunque, provo subito il tuo codice, lo trasformo in C e ti dico
...
...
testing...
...
...
La tua funzione va che è una freccia
Adesso vado a correggere l'errore che mi hai fatto scovare nella mia...

Originariamente inviato da pisto

...ma si potrebbe modificare in modo da mettere un parametro che indica anche il valore + basso, e poi nell'if comparare il positivo solo se lo xor dei segni dei due fattori è false.

Aspetta...non ti seguo...

dicevo con quel giro di parole strafigo in cui ho tirato in ballo pure lo xor, che se il numero di segni è dispari allora il risultato è negativo (-*+=-, -*-=+)

quindi, riguardo alla moltiplicazione il problema si pone se un fattore è +-1, infatti puoi moltiplicare +1 per (prendo il caso del byte con segno) 127 in positivo, ma 128 in negativo. quindi bisogna (nella moltiplicazione solo nel caso che un fattore sia 1, nella somma/sttrazione anche negli altri) creare un'intervallo in cui l'altro operatore può stare senza dare un overflow. mi sembra che la funzione giusta sia così:

boolean overflowMolt(int a, int b, int maxValPositivo, int maxValNeg){
boolean segno=~(a<0^b<0);
a=a<0?-a:a;
b=b<0?-b:b;
return segno?b<=maxValPositivo/a:b<=-(maxValNeg/a);
}

per la somma/sottrazione:

boolean overflowSomma(int a, int b, int maxValPositivo, int maxValNeg){
return b>=maxValNeg-a&&b<=maxValPos+a;
}

edit
dimenticavo: se lavori in c, hai la possibilità di fare una funzione direttamente in assembly no? mi pare ci sia un registro (un bit in un registro + ampio) che ti segnala se l'ultima operazione algebrica ha dato un overflow.

[mfonz85]

Originariamente inviato da pisto

dicevo con quel giro di parole strafigo in cui ho tirato in ballo pure lo xor, che se il numero di segni è dispari allora il risultato è negativo (-*+=-, -*-=+)

quindi, riguardo alla moltiplicazione il problema si pone se un fattore è +-1, infatti puoi moltiplicare +1 per (prendo il caso del byte con segno) 127 in positivo, ma 128 in negativo. quindi bisogna (nella moltiplicazione solo nel caso che un fattore sia 1, nella somma/sttrazione anche negli altri) creare un'intervallo in cui l'altro operatore può stare senza dare un overflow. mi sembra che la funzione giusta sia così:

boolean overflowMolt(int a, int b, int maxValPositivo, int maxValNeg){
a=a<0?-a:a;
return b>=maxValNeg/a&&b<=maxValPos/a;
}

per la somma/sottrazione:

boolean overflowSomma(int a, int b, int maxValPositivo, int maxValNeg){
a=a<0?-a:a;
return b>=maxValNeg+a&&b<=maxValPos-a;
}

No...non vanno
Ma strano accidenti, non trovo l'errore...

int overflowMolt(int32_t a, int32_t b, u_int8_t byte){
    a = a < 0 ? -a : a;
    if (byte == 1) return ( (b >= __MIN(int8_t) / a) && (b <= __MAX(int8_t) / a) );
    if (byte == 2) return ( (b >= __MIN(int16_t) / a) && (b <= __MAX(int16_t) / a) );
    if (byte == 4) return ( (b >= __MIN(int32_t) / a) && (b <= __MAX(int32_t) / a) );
}

int overflowSomma(int32_t a, int32_t b, u_int8_t byte){
    a = a < 0 ? -a : a;
    if(byte == 1) return ( (b >= __MIN(int8_t) + a) && (b <= __MAX(int8_t) - a) );
    if(byte == 2) return ( (b >= __MIN(int16_t) + a) && (b <= __MAX(int16_t) - a) );
    if(byte == 4) return ( (b >= __MIN(int32_t) + a) && (b <= __MAX(int32_t) - a) );
}

riguarda il mio messaggio, avrò editato una ventina di volte mentre lo leggev

[mfonz85]

Originariamente inviato da pisto

boolean overflowMolt(int a, int b, int maxValPositivo, int maxValNeg){
boolean segno=~(a<0^b<0);
a=a<0?-a:a;
b=b<0?-b:b;
return segno?b<=maxValPositivo/a:b<=-(maxValNeg/a);
}

Nada, continua a non andare (e purtroppo non riesco ad aiutarti a trovare l'errore: stra programmazione con ?, :, ~, non la capisco )

Originariamente inviato da pisto

dimenticavo: se lavori in c, hai la possibilità di fare una funzione direttamente in assembly no? mi pare ci sia un registro (un bit in un registro + ampio) che ti segnala se l'ultima operazione algebrica ha dato un overflow.

Potrebbero esserci problemi di portabilità in questo caso??
Te lo chiedo perchè il programma che sto facendo deve girare perfettamente su Unix e Solaris...non sarebbe rischioso lavorare direttamente sui registri?
Non saprei proprio da dove partire per l'assembly! Non ho mai provato ad implementarlo in programmi C

nel mio post precedente ho scritto svariate puttanate, compresi degli errori di sintassi (che vergogna )

ecco le versioni che funzionano (testate)

static boolean overflowMolt(int a, int b, int maxValPositivo){
		boolean segno=!(a<0^b<0);
		a=a<0?-a:a;
		b=b<0?-b:b;
		return b>(segno?maxValPositivo:maxValPositivo+1)/a;
	}
	static boolean overflowSomma(int a, int b, int maxValPositivo){
		return b<-a-(maxValPositivo+1)||b>maxValPositivo-a;
	}

in questa versione ho assunto che ilo valore massimo sia minore di uno al valore assoluto del valore minimo (come credo sia praticamente uno standard).

riguardo al segno ^, è XOR, e ! è NOT. riguardo all'assembly invece, l'importante è che il programma giri su un processore compatibile con quello per cui comppili il codice sorgente. quindi è (relativamente, vedi il mac che fino ad un po' di tempo fa girava su un processore diverso) indipendente dal sistema operativo

[mfonz85]

Originariamente inviato da pisto

nel mio post precedente ho scritto svariate puttanate, compresi degli errori di sintassi (che vergogna )

ecco le versioni che funzionano (testate)

static boolean overflowMolt(int a, int b, int maxValPositivo){
		boolean segno=!(a<0^b<0);
		a=a<0?-a:a;
		b=b<0?-b:b;
		return segno?b>maxValPositivo/a:b>(maxValPositivo+1)/a;
	}
	static boolean overflowSomma(int a, int b, int maxValPositivo){
		return b<-a-(maxValPositivo+1)||b>maxValPositivo-a;
	}

in questa versione ho assunto che ilo valore massimo sia minore di uno al valore assoluto del valore minimo (come credo sia praticamente uno standard).

riguardo al segno ^, è XOR, e ! è NOT. riguardo all'assembly invece, l'importante è che il programma giri su un processore compatibile con quello per cui comppili il codice sorgente. quindi è (relativamente, vedi il mac che fino ad un po' di tempo fa girava su un processore diverso) indipendente dal sistema operativo

AVE, o sommo coder
Funziona a meraviglia.
Però adesso l'ho solo provata così...voglio capire come funziona
Grazie

il concetto è quello che avevi trovato tu, o caro discepolo , solo che il mio fa il test sia per il limite minore che per quello maggiore. prendi il limite, lo dividi per un fattore, controlli che l'altro fattore non superi quel risultato.