Overflow con i signed int
pozz
www.embeddedgurus.net/stack-overflow/) mi sono imbattutto, per la
prima volta seriamente, nel problema dell'overflow tra due int.
A quanto pare, quando c'è overflow in un'operazione tra int (quindi
con segno), il risultato è completamente indefinito e dipendente dal
compilatore (citando, "overflowing a signed integer type could result
in World War 3 starting").
E' per questo che è sempre meglio utilizzare gli unsigned quando
possibile. Il problema è cosa succede se ho due numeri che possono
essere anche negativi. Come fare per fare delle differenze, per
esempio?
Se volessi scrivere una funzione che compara due interi, come si fa?
---
int cmpint (int a, int b) {
return a-b;
}
---
E' chiaro che, fin quando a e b assumono valori positivi o molti altri
valori "banali", la funzione ritorna correttamente il risultato del
confronto. Ma cosa succede se, per esempio, su un'architettura a 16
bit, a=30000 e b=-31000? A quanto pare non è dato sapere...
La cosa strana è che ho visto fare differenze tra interi anche nel
kernel di linux dove potrebbe esserci overflow.
Stavo studiano l'implementazione dei timer in linux e stavo leggendo
questa pagina di Alessandro Rubini:
http://www.linux.it/~rubini/docs/time/time.html
Qui si spiega che esiste la variabile jiffies, definita unsigned long,
incrementata ad ogni IRQ del timer (HZ volte al secondo). Quindi se
voglio fermarmi per 1/10 di secondo, basta che faccio qualcosa del
genere:
unsigned long to = jiffies + HZ/10;
while (time_before(jiffies, to))
;
La macro time_before() è definita proprio per far fronte a problemi di
wrapping. Infatti in include/linux/jiffies.h:
---
/*
* These inlines deal with timer wrapping correctly. You are
* strongly encouraged to use them
* 1. Because people otherwise forget
* 2. Because if the timer wrap changes in future you won't have
to
* alter your driver code.
*
* time_after(a,b) returns true if the time a is after time b.
*
* Do this with "<0" and ">=0" to only test the sign of the result. A
* good compiler would generate better code (and a really good
compiler
* wouldn't care). Gcc is currently neither.
*/
#define time_after(a,b) \
(typecheck(unsigned long, a) && \
typecheck(unsigned long, b) && \
((long)(b) - (long)(a) < 0))
#define time_before(a,b) time_after(b,a)
---
Ma se guardiamo la time_after(), da cui si ricava la time_before(),
vediamo che il test viene fatto forzando una differenza tra signed. E
a questo punto non potrebbe iniziare la World War 3? :)
FtM
> Leggendo uno degli articoli di Nigel Jones sul suo blog (http://www.embeddedgurus.net/stack-overflow/) mi sono imbattutto, per la
> prima volta seriamente, nel problema dell'overflow tra due int.
>
> A quanto pare, quando c'è overflow in un'operazione tra int (quindi
> con segno), il risultato è completamente indefinito e dipendente dal
> compilatore (citando, "overflowing a signed integer type could result
> in World War 3 starting").
>
sì (o almeno su una DeathStation (cit.))
> E' per questo che è sempre meglio utilizzare gli unsigned quando
> possibile.
solo quando serve l'overflow
> Il problema è cosa succede se ho due numeri che possono
> essere anche negativi. Come fare per fare delle differenze, per
> esempio?
>
con una differenza. Se può sforare si usa un tipo più "capiente".
> Se volessi scrivere una funzione che compara due interi, come si fa?
> ---
> int cmpint (int a, int b) {
> return a-b;}
>
questa sottrae, non compara.
> ---
> E' chiaro che, fin quando a e b assumono valori positivi o molti altri
> valori "banali", la funzione ritorna correttamente il risultato del
> confronto. Ma cosa succede se, per esempio, su un'architettura a 16
> bit, a=30000 e b=-31000? A quanto pare non è dato sapere...
>
a meno che non sai cosa fa il compilatore.
> La cosa strana è che ho visto fare differenze tra interi anche nel
> kernel di linux dove potrebbe esserci overflow.
certamente possibile ma poco plausibile.
il kernel linux compila *solo* con il gcc. Se va bene con quello
allora pace.
pozz
> > E' per questo che è sempre meglio utilizzare gli unsigned quando
> > possibile.
>
> solo quando serve l'overflow
A questo punto penso che sia meglio utilizzare sempre gli unsigned
tranne
nel caso in cui servano effettivamente i negativi, piuttosto che
utilizzare
i signed tranne in cui serve l'overflow.
Non trovi?
Il classico indice di un array o di un ciclo si potrebbe sempre
dichiarare
come unsigned evitando qualsiasi problema nel caso dovesse succedere
un overflow.
> > Il problema è cosa succede se ho due numeri che possono
> > essere anche negativi. Come fare per fare delle differenze, per
> > esempio?
>
> con una differenza. Se può sforare si usa un tipo più "capiente".
Beh, certo. In molti casi, però, non si può (architetture embedded)
oppure non si vuole per evitare operazioni poco efficienti, oppure
perchè si sta facendo una funzione generica i cui parametri sono
signed e possono assumere qualsiasi valore (vedi l'esempio della
funzione sotto).
> > Se volessi scrivere una funzione che compara due interi, come si fa?
> > ---
> > int cmpint (int a, int b) {
> > return a-b;}
>
> questa sottrae, non compara.
>
> > ---
> > E' chiaro che, fin quando a e b assumono valori positivi o molti altri
> > valori "banali", la funzione ritorna correttamente il risultato del
> > confronto. Ma cosa succede se, per esempio, su un'architettura a 16
> > bit, a=30000 e b=-31000? A quanto pare non è dato sapere...
>
> a meno che non sai cosa fa il compilatore.
Certo, ma in quel caso la funzione non sarebbe portabile.
> > La cosa strana è che ho visto fare differenze tra interi anche nel
> > kernel di linux dove potrebbe esserci overflow.
>
> certamente possibile ma poco plausibile.
Cosa sarebbe poco plausibile?
Ah ok, se è così che funziona... pensavo si perdesse più tempo per
cercare di rendere il codice più portabile sia in termini di
piattaforma che
di compilatore.
FtM
> tranne
> nel caso in cui servano effettivamente i negativi, piuttosto che
> utilizzare
> i signed tranne in cui serve l'overflow.
> Non trovi?
>
> Il classico indice di un array o di un ciclo si potrebbe sempre
> dichiarare
> come unsigned evitando qualsiasi problema nel caso dovesse succedere
> un overflow.
>
Non capisco.. se serve il segno usi un tipo con il segno, altrimenti
no. Perché tutti questi problemi?
> > > La cosa strana è che ho visto fare differenze tra interi anche nel
> > > kernel di linux dove potrebbe esserci overflow.
>
> > certamente possibile ma poco plausibile.
>
> Cosa sarebbe poco plausibile?
>
Che nel kernel di linux ci siano errori così banali di cui nessuno si
è ancora accorto. Che ci siano errori banali nel codice è certamente
possibile (come si è visto anche poco tempo fa, non so se ricordi - il
deferenziamento di puntatori a NULL nell'implementazione del TAP, se
non sbaglio).
> > > Ma se guardiamo la time_after(), da cui si ricava la time_before(),
> > > vediamo che il test viene fatto forzando una differenza tra signed. E
> > > a questo punto non potrebbe iniziare la World War 3? :)
>
> > il kernel linux compila *solo* con il gcc. Se va bene con quello
> > allora pace.
>
> Ah ok, se è così che funziona... pensavo si perdesse più tempo per
> cercare di rendere il codice più portabile sia in termini di
> piattaforma che
> di compilatore.
Pensavi male. Un sistema operativo è parte di ciò che ti permette,
astraendo lo hardware, di poter scrivere codice portabile a livello
utente. Dalla libreria standard in giù (libc/libm, kernel/drivers,
bootloader) non ti puoi proprio aspettare del codice portabile -
ovviamente.