integer overflow

Le
Taurre
Bonjour à tous,

J'ai une question au sujet de l'arithmétique entière.
Je sais que lorsque l'on dépasse la capacité d'un int, comme ceci par
exemple:


int n = INT_MAX + 1;


il s'agit d'un comportement indéterminé et on ne peut donc pas être
certains d'obtenir INT_MIN comme valeur. La même réflexion vaudrait
pour un unsigned int.

Cependant, j'aimerais savoir ce qu'il en est pour les types entier
d'une taille inférieur à celle d'un int. Par exemple, si j'utilise un
champ de bits non signé de trois bits. Est-ce que je suis garantit
que, si ce dernier vaut 7 et que je l'incrémente, j'obtienne 0 ou
s'agit-il d'un comportement indéterminé?

Merci d'avance pour vos réponses.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
espie
Le #23589321
In article Taurre
Bonjour à tous,

J'ai une question au sujet de l'arithmétique entière.
Je sais que lorsque l'on dépasse la capacité d'un int, comme ceci par
exemple:


int n = INT_MAX + 1;


il s'agit d'un comportement indéterminé et on ne peut donc pas être
certains d'obtenir INT_MIN comme valeur. La même réflexion vaudrait
pour un unsigned int.



Non. Les unsigned int ont un comportement determine. L'intervalle de valeur
est defini par l'implementation, mais UINT_MAX+1 vaut 0.

Cependant, j'aimerais savoir ce qu'il en est pour les types entier
d'une taille inférieur à celle d'un int. Par exemple, si j'utilise un
champ de bits non signé de trois bits. Est-ce que je suis garantit
que, si ce dernier vaut 7 et que je l'incrémente, j'obtienne 0 ou
s'agit-il d'un comportement indéterminé?



Non, rien de plus garanti, voire encore moins que pour les entiers. Il est
fortement deconseille d'utiliser des champs de bits pour avoir un comportement
defini...
Antoine Leca
Le #23589311
Taurre écrivit :
J'ai une question au sujet de l'arithmétique entière.
Je sais que lorsque l'on dépasse la capacité d'un int, comme ceci par
exemple:

int n = INT_MAX + 1;

il s'agit d'un comportement indéterminé et on ne peut donc pas être
certains d'obtenir INT_MIN comme valeur.



Clairement. Imagine par exemple le cas d'une machine en signe +
magnitude, donc où le signe est dans le bit de poids fort ; si aucune
précaution n'est prise au niveau matériel ou implémentation, INT_MAX+1
vaut... -0 !


La même réflexion vaudrait pour un unsigned int.



Mauvaise pioche. Les types entier non signés en C sont particuliers, ils
implémentent l'arithmétique sur l'intervalle [0, UINT_MAX]; donc
UINT_MAX+1 vaut 0, et (unsigned)INT_MAX + 1 vaut une valeur parfaitement
définie par l'implémentation (qui peut être 0).


Cependant, j'aimerais savoir ce qu'il en est pour les types entier
d'une taille inférieur à celle d'un int.



Comment fais-tu en C pour faire une opération arithmétique sur un entier
de taille strictement inférieure à celle d'un int ?


Par exemple, si j'utilise un
champ de bits non signé de trois bits. Est-ce que je suis garantit
que, si ce dernier vaut 7 et que je l'incrémente, j'obtienne 0 ou
s'agit-il d'un comportement indéterminé?



Ni l'un ni l'autre ; tu es sûr d'obtenir 8, ce qui me paraît éminemment
raisonnable.


Maintenant, en dehors des considérations arithmétiques, si ta question
est, quelle sera la valeur du champ de bits si on y stocke 8 ? la
réponse est 0 parce qu'il est unsigned, en cohérence avec le point
ci-dessus; si le champ était signed tu aurais un comportement indéfini;
sinon, il faut regarder comment ton compilateur traite les champs int.


Antoine
Pascal J. Bourguignon
Le #23589631
Antoine Leca
Taurre écrivit :
Cependant, j'aimerais savoir ce qu'il en est pour les types entier
d'une taille inférieur à celle d'un int.



Comment fais-tu en C pour faire une opération arithmétique sur un entier
de taille strictement inférieure à celle d'un int ?




unsigned char f(unsigned char c){
unsigned char r=1;
r+=c;
return(r);
}

gcc -S -o c.s c.c ; cat c.s
.file "c.c"
.text
.globl f
.type f, @function
f:
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
movq %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl %edi, %eax
movb %al, -20(%rbp)
movb $1, -1(%rbp)
movzbl -20(%rbp), %eax
addb %al, -1(%rbp) ; <-------------------------
movzbl -1(%rbp), %eax
leave
ret
.cfi_endproc
.LFE0:
.size f, .-f
.ident "GCC: (Gentoo 4.4.5 p1.2, pie-0.4.5) 4.4.5"
.section .note.GNU-stack,"",@progbits

Mais ce n'est qu'une optimisation, sémantiquement, c'est comme si on
faisait l'opération sur un int.


Par exemple, si j'utilise un
champ de bits non signé de trois bits. Est-ce que je suis garantit
que, si ce dernier vaut 7 et que je l'incrémente, j'obtienne 0 ou
s'agit-il d'un comportement indéterminé?



Ni l'un ni l'autre ; tu es sûr d'obtenir 8, ce qui me paraît éminemment
raisonnable.

Maintenant, en dehors des considérations arithmétiques, si ta question
est, quelle sera la valeur du champ de bits si on y stocke 8 ? la
réponse est 0 parce qu'il est unsigned, en cohérence avec le point
ci-dessus; si le champ était signed tu aurais un comportement indéfini;
sinon, il faut regarder comment ton compilateur traite les champs int.



Exactement.


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
Tonton Th
Le #23589721
On 07/21/2011 11:33 AM, Antoine Leca wrote:

Par exemple, si j'utilise un
champ de bits non signé de trois bits. Est-ce que je suis garantit
que, si ce dernier vaut 7 et que je l'incrémente, j'obtienne 0 ou
s'agit-il d'un comportement indéterminé?



Ni l'un ni l'autre ; tu es sûr d'obtenir 8, ce qui me paraît éminemment
raisonnable.



Objection, votre honneur !

-------------------------------------------------------------------------
:~/Essais/C$ cat bitfields.c
#include int main(int argc, char *argv[])
{
int foo;
struct {
unsigned int field : 3;
} bf;
bf.field = 0;
for (foo=0; foo<10; foo++) {
printf("%7d", foo);
bf.field++;
printf("%7d", bf.field);
puts("");
}
return 0;
}
:~/Essais/C$ gcc -Wall bitfields.c -o bitfields
:~/Essais/C$ ./bitfields
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0
8 1
9 2
:~/Essais/C$
-------------------------------------------------------------------------

--

Nous vivons dans un monde étrange/
http://foo.bar.quux.over-blog.com/
Pierre Maurette
Le #23590271
Taurre :
Bonjour à tous,

J'ai une question au sujet de l'arithmétique entière.
Je sais que lorsque l'on dépasse la capacité d'un int, comme ceci par
exemple:


int n = INT_MAX + 1;


il s'agit d'un comportement indéterminé et on ne peut donc pas être
certains d'obtenir INT_MIN comme valeur. La même réflexion vaudrait
pour un unsigned int.

Cependant, j'aimerais savoir ce qu'il en est pour les types entier
d'une taille inférieur à celle d'un int. Par exemple, si j'utilise un
champ de bits non signé de trois bits. Est-ce que je suis garantit
que, si ce dernier vaut 7 et que je l'incrémente, j'obtienne 0 ou
s'agit-il d'un comportement indéterminé?



Les types à taille fixe intN_t et uintN_t de stdint.h ont quand ils
existent (!!) une représention garantie. Je ne suis pas sûr de ce que
dit la norme sur leur comportement au dépassement pour les types
signés. Mais il me semble que la prévisibilité de la représentation
induit celle de l'arithmétique, avec un cast un peu glauque au besoin.
stdint.h est C99 mais c'est une extension courante. Il est possible
d'ajouter stdint.h dans un projet Visual Studio. Je ne sais pas s'il
peut y avoir des effets pervers (en plus des problèmes de printf) à
utiliser stdint.h dans un projet C89.

--
Pierre Maurette
Antoine Leca
Le #23590321
Tonton Th écrivit :
On 07/21/2011 11:33 AM, Antoine Leca wrote:

Par exemple, si j'utilise un
champ de bits non signé de trois bits. Est-ce que je suis garantit
que, si ce dernier vaut 7 et que je l'incrémente, j'obtienne 0 ou
s'agit-il d'un comportement indéterminé?



Ni l'un ni l'autre ; tu es sûr d'obtenir 8, ce qui me paraît éminemment
raisonnable.



Objection, votre honneur !


for (foo=0; foo<10; foo++) {



L'opération arithmétique d'incrémentation s'écrit

foo + 1


Tu utilises un opérateur du langage, qui d'une part implique une
opération, et d'autre part a des « effets de bord » (en l'occurrence un
stockage), lesquels ne sont pas des propriétés arithmétiques.

Dans la partie que tu as coupée, j'explicite pourquoi le 8 se transforme
en 0.


Antoine
Antoine Leca
Le #23590691
Pierre Maurette écrivit :
Les types à taille fixe intN_t et uintN_t de stdint.h ont quand ils
existent (!!)



Le correctif technique nº2 à C99 a rendu obligatoire la définition de
ces types si la machine sous-jacente en dispose.

une représention garantie. Je ne suis pas sûr de ce que
dit la norme sur leur comportement au dépassement pour les types signés.



Rien de particulier, comportement indéfini dans le cas le plus général.
Par exemple, il est parfaitement possible d'avoir une arithmétique
saturée pour ces types, en particulier si leur taille est supérieure ou
égale à celle de int ; ou de déclencher un déroutement...

Par contre, pour les types de taille strictement inférieure, comme le
résultat des opérateurs arithmétiques sera int


Mais il me semble que la prévisibilité de la représentation induit celle
de l'arithmétique, avec un cast un peu glauque au besoin.



Certes, avec /des/ transtypages tu peux forcer le comportement
«habituel». Mais bon, trois transtypages à chaque opérateur binaire,
cela va vite faire lourd voire indigeste...

intN_t x,y,z;

#if 0 /* possible dépassement */
(x + y) * z
#else
(intN_t)( (uintN_t)(intN_t)( (uintN_t)x + (uintN_t)y ) * (uintN_t)z )
#endif

stdint.h est C99 mais c'est une extension courante. Il est possible
d'ajouter stdint.h dans un projet Visual Studio. Je ne sais pas s'il
peut y avoir des effets pervers (en plus des problèmes de printf) à
utiliser stdint.h dans un projet C89.



Je n'en vois pas non plus.


Antoine
Tonton Th
Le #23590741
On 07/21/2011 03:30 PM, Antoine Leca wrote:

for (foo=0; foo<10; foo++) {



L'opération arithmétique d'incrémentation s'écrit

foo + 1



Boucle cosmétique, l'essentiel est entre les deux printf,
et répond à la question traitée. Maintenant, il y a peut
être 20 ans que ça marche par miracle ;)

--

Nous vivons dans un monde étrange/
http://foo.bar.quux.over-blog.com/
espie
Le #23591131
In article Pierre Maurette
Je ne suis pas sûr de ce que
dit la norme sur leur comportement au dépassement pour les types
signés. Mais il me semble que la prévisibilité de la représentation
induit celle de l'arithmétique, avec un cast un peu glauque au besoin.



Non, l'arithmetique sur les types signes fait toujours n'importe quoi en
cas de depassement.

La representation est juste la pour te garantir que tu peux caster des
valeurs raisonnables entre le type uint et le type int correspondant, et
essayer de dire que ca va etre n bits de valeur, 1 bit de signe, et m bits
de padding...

Au final, l'arithmetique sur les unsigned est previsible, et cette histoire
de representation permet de rendre une bonne part des transtypages
unsigned <-> signed, previsibles (e.g., dans les bons intervalles de valeur).

Combiner les deux releve quand meme de la haute voltige et du tube d'aspirine...
Antoine Leca
Le #23591341
On dirait qu'une phrase a sauté... :-(

Antoine Leca a écrit :
Pierre Maurette écrivit :
une représention garantie. Je ne suis pas sûr de ce que
dit la norme sur leur comportement au dépassement pour les types signés.



Rien de particulier, comportement indéfini dans le cas le plus général.


Par contre, pour les types de taille strictement inférieure, comme le
résultat des opérateurs arithmétiques sera int



[...], selon les opérateurs, le résultat pourra être défini.
Par exemple, la somme ou la différence de deux int8_t (ou 3, jusqu'à 256
en fait) ne posera pas de soucis, d'éventuels débordements resteront
toujours définis.

return (int8_t)(-128) + (int8_t)(-128) + (int8_t)(-128);

donne bien -384, comme attendu (?); de même

return (int8_t)(-128) + (int8_t)(-128) + (int8_t)(-128);

Idem pour la multiplication de 2 int8_t, [-16256..16384] c'est OK.


Antoine
Publicité
Poster une réponse
Anonyme