integer overflow
Taurre
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.
Marc Espie
Taurre <jerome....@yahoo.fr> wrote:
>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
> 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
> 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
>> 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 !
-------------------------------------------------------------------------
tth@plop:~/Essais/C$ cat bitfields.c
#include <stdio.h>
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;
}
tth@plop:~/Essais/C$ gcc -Wall bitfields.c -o bitfields
tth@plop:~/Essais/C$ ./bitfields
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0
8 1
9 2
tth@plop:~/Essais/C$
-------------------------------------------------------------------------
--
Nous vivons dans un monde étrange/
http://foo.bar.quux.over-blog.com/
Pierre Maurette
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
> 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
> 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
>> 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 ;)
Marc Espie
Pierre Maurette <maurett...@free.fr> wrote:
>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
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
Taurre
Donc si je résume bien, les entiers non signés ont un comportement
déterminé si on dépasse la valeur maximale de leur intervalle sauf
s'il s'agit d'un champ de bits?
Lucas Levrel
> 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 ;)
En fait, Antoine n'a pas laissé la bonne ligne, mais sa remarque reste
valable. Dans :
> bf.field++;
il y a deux opérations :
bf.field=bf.field+1;
l'addition 7+1, qui donne 8, et l'affectation de 8 à bf.field, qui donne
0.
--
LL
Marc Espie
Oui. Plus precisement, les champs de bits ont regulierement des petits
soucis d'implementation qui font qu'il vaut mieux ne pas trop compter sur
leur semantique precise...
alors que pour les entiers non signes, c'est etudie pour !
Tonton Th
>>> 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 ;)
>
> En fait, Antoine n'a pas laissé la bonne ligne, mais sa remarque reste
> valable. Dans :
>> bf.field++;
> il y a deux opérations :
> bf.field=bf.field+1;
> l'addition 7+1, qui donne 8, et l'affectation de 8 à bf.field, qui donne 0.
Mais dans ce cas-là, pour moi, ce n'est plus une incrémentation,
mais une addition. bf.field++ est différent de bar=bf.field+1
puisque on sort du contexte du bitfield, et qu'il y a donc une
promotion, non ?
Antoine Leca
> Mais dans ce cas-là, pour moi, ce n'est plus une incrémentation,
> mais une addition.
Ah! maintenant je comprend, tu parlais d'un autre langage C, le tien.
Dans la norme du langage, il est écrit (6.3.6 Additive operators)
[#2:] [...] (Incrementing is equivalent to adding 1.)
Ou un peu avant (6.3.2.4 Postfix increment and decrement operators)
[#2:] [...] After the result is obtained, the value of the
operand is incremented. (That is, the value 1 of the
appropriate type is added to it.) See the discussions of
additive operators and compound assignment for [...]
Désolé pour la confusion, je n'avais pas compris.
> bf.field++ est différent de bar=bf.field+1
> puisque on sort du contexte du bitfield, et qu'il y a donc une
> promotion, non ?
Non (enfin, pour moi, et dans le cadre de la machine abstraite).
Il y a promotion pour le champ de bit, exactement comme il y a promotion
pour un type entier d'ordre inférieur à int (en utilisant les notions de
C99).
Évidemment, un compilateur est en droit d'optimiser cela à son goût ;
par exemple pour un champ de taille 1, en utilisant XOR.
Antoine
Antoine Leca
> Merci infiniment pour vos r�ponses.
> Donc si je r�sume bien, les entiers non sign�s ont un comportement
> d�termin� si on d�passe la valeur maximale de leur intervalle sauf
> s'il s'agit d'un champ de bits?
Je n'�crirais pas cela. Mais la remarque de Marc est plus juste que
d'�ventuelles pr�cisions sur ce que devrait faire les compilateurs : si
tu cherches � �crire des programmes portables tout en privil�giant la
compacit�, il vaut mieux �viter les champs de bits et �crire le code
�quivalent avec des op�rations binaires (&, |, ^) et des masques.
Antoine