OVH Cloud OVH Cloud

Decalages d'un nombre de bits pouvant etre >= a la taille du type

134 réponses
Avatar
Vincent Lefevre
J'ai besoin de faire un décalage vers la droite sur un type entier
(disons non signé) générique (i.e. défini par typedef) d'un certain
nombre constant de bits. Le problème est que ce nombre de bits peut
être supérieur ou égal à la taille du type en question. Une idée
sur la façon de faire ça efficacement sans obtenir de comportement
indéfini et sans passer par un outil du style "configure"?

--
Vincent Lefèvre <vincent@vinc17.org> - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA

10 réponses

Avatar
Gabriel Dos Reis
Vincent Lefevre <vincent+ writes:

[...]

| > J'etais pas la, je ne peux donc te donner que des suppositions qui
| > vont de personne n'a trouve le probleme suffisemment important pour en
| > faire une proposition formelle a il y a une machine repandue que je ne
| > connais pas sur laquelle cela pose un probleme.
|
| > La norme est un moyen, pas une fin.
|
| Tu fais ce que tu veux. En ce qui me concerne, je n'ai pas du tout
| envie de revoir mon code dès qu'une nouvelle machine apparaît.

En supposant que tu obtiens un exécutable, parce que la norme ne te le
garantit pas.

-- Gaby
Avatar
Vincent Lefevre
Dans l'article <cjvbua$f0p$,
Charlie Gordon écrit:

Après relecture du standard, il apparait que 1>>32 c'est undefined behavior,
y compris pendant la translation.
Je pense quand même que 1 ? 0 : 1>>32 est sémantiquement correct,
d'ailleurs 6.6 paragraphe 3 prévoit le cas d'expressions constantes dont des
sous-expressions non constantes ne sont jamais évaluées. Par exemple :

3 * sizeof(main(argc,argv))
1 ? 0 : main(argc,argv)

alors pourquoi pas

1 ? 0 : 1>>32


L'implémentation peut ne pas évaluer 1>>32. Mais elle peut aussi
l'évaluer en tant que sous-expression constante (sans chercher à
savoir si la valeur pourra être utilisée ou si elle ne sera jamais
utilisée), et dans ce cas, il y a comportement indéfini. Dans
l'expression avant le "?", tu peux très bien avoir quelque chose
de compliqué, voire indécidable quant à savoir si l'expression
peut avoir une valeur non nulle ou pas (bon, en fait pas
indécidable, car les variables sont de taille finie, mais trop
compliqué à décider dans la pratique).

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA

Avatar
Gabriel Dos Reis
"Charlie Gordon" writes:

| "Charlie Gordon" wrote in message
| news:cjvb19$d09$
| > "Vincent Lefevre" <vincent+ wrote in message
| > news:20041005221856$
| > > Dans l'article <cjv6en$20n$,
| > > Charlie Gordon écrit:
| > >
| > > > Ce warning est stupide parce qu'il n'est produit que pour des valeurs
| > > > constantes de c qui sont plus grandes que la taille du type. Or le
| test
| > > > fait que le comportement indéfini n'est pas invoqué dans ce cas,
| > >
| > > Il l'est. Le test n'a aucun influence ici. Le compilo peut très
| > > bien évaluer des expressions au moment de la traduction (cas des
| > > expressions constantes). Comme pour chaque valeur du terme de
| > > gauche il y a comportement indéfini, l'implémentation peut faire
| > > ce qu'elle veut, à savoir, considérer que la valeur est constante.
| > > Dans ce cas, toutes les contraintes du 6.6 sont satisfaites.
| >
| > Pas du tout ! C'est le code produit qui a un comportement indéfini, pas
| le
| > compilateur.
| > Il peut considérer ce qu'il veut du terme indéfini, le test fait que
| > celui-ci n'est pas exécuté.
| > L'opérateur ?: n'évalue que 2 des 3 termes, et dans le cas présent il
| > n'évalue jamais le terme de droite dont le comportement est indéfini.
|
| Après relecture du standard, il apparait que 1>>32 c'est undefined behavior,
| y compris pendant la translation.
| Je pense quand même que 1 ? 0 : 1>>32 est sémantiquement correct,

Oui, il l'est. Le comportement n'est indéfini que si la branche est
prise. Ce qui n'est pas le cas ici.

Considère

1 ? 0 : *(int*)0

-- Gaby
Avatar
Gabriel Dos Reis
Vincent Lefevre <vincent+ writes:

| Dans l'article <cjvbua$f0p$,
| Charlie Gordon écrit:
|
| > Après relecture du standard, il apparait que 1>>32 c'est undefined behavior,
| > y compris pendant la translation.
| > Je pense quand même que 1 ? 0 : 1>>32 est sémantiquement correct,
| > d'ailleurs 6.6 paragraphe 3 prévoit le cas d'expressions constantes dont des
| > sous-expressions non constantes ne sont jamais évaluées. Par exemple :
|
| > 3 * sizeof(main(argc,argv))
| > 1 ? 0 : main(argc,argv)
|
| > alors pourquoi pas
|
| > 1 ? 0 : 1>>32
|
| L'implémentation peut ne pas évaluer 1>>32. Mais elle peut aussi
| l'évaluer en tant que sous-expression constante (sans chercher à
| savoir si la valeur pourra être utilisée ou si elle ne sera jamais
| utilisée), et dans ce cas, il y a comportement indéfini.

Bah non ; ce n'est pas un comportement possible de la machine
abstraite.

-- Gaby
Avatar
Vincent Lefevre
Dans l'article ,
Gabriel Dos Reis écrit:

Vincent Lefevre <vincent+ writes:

| Dans l'article <cjvbua$f0p$,
| Charlie Gordon écrit:

| > 1 ? 0 : 1>>32
|
| L'implémentation peut ne pas évaluer 1>>32. Mais elle peut aussi
| l'évaluer en tant que sous-expression constante (sans chercher à
| savoir si la valeur pourra être utilisée ou si elle ne sera jamais
| utilisée), et dans ce cas, il y a comportement indéfini.

Bah non ; ce n'est pas un comportement possible de la machine
abstraite.


Sur quoi tu te bases?

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA

Avatar
Vincent Lefevre
Dans l'article <cjvb19$d09$,
Charlie Gordon écrit:

"Vincent Lefevre" <vincent+ wrote in message
news:20041005221856$

Il l'est. Le test n'a aucun influence ici. Le compilo peut très
bien évaluer des expressions au moment de la traduction (cas des
expressions constantes). Comme pour chaque valeur du terme de
gauche il y a comportement indéfini, l'implémentation peut faire
ce qu'elle veut, à savoir, considérer que la valeur est constante.
Dans ce cas, toutes les contraintes du 6.6 sont satisfaites.


Pas du tout ! C'est le code produit qui a un comportement indéfini,
pas le compilateur.


Je n'ai pas dit que le compilateur avait un comportement indéfini,
mais qu'elle avait le droit de faire ce qu'elle veut concernant la
traduction du code en question.

Il peut considérer ce qu'il veut du terme indéfini, le test fait que
celui-ci n'est pas exécuté.


La norme autorise son évaluation au moment de la traduction.

Et il faut impérativement caster (c) en (unsigned) pour que le
modulo soit toujours optimisé en un masque sur les architectures où
la taille est une puissance de 2 (connais-tu des contre-exemples ?),
sinon le code généré pour (c) expression signée non constante sera
inefficace.


Faux. Le compilo peut très bien supposer que c est positif et donc
faire comme si c était non signé. Si c est strictement négatif, c'est
du comportement indéfini et ce n'était donc pas une erreur d'avoir
fait la supposition c >= 0.


C'est inexact !


Non, le compilo peut très bien générer du code correspondant au cas
c >= 0 même si ça fait n'importe quoi pour c < 0.

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA



Avatar
Jean-Marc Bourguet
Vincent Lefevre <vincent+ writes:

Dans l'article ,
Jean-Marc Bourguet écrit:

Vincent Lefevre <vincent+ writes:

Pourquoi est-ce que l'evident

#define SAVE_RSHIFT(v, c) ((sizeof(v) * CHAR_BIT >= (c)) ? 0 : (v) >> (c))

ne te convient pas?


Comportement indéfini.


C'est les bits de padding qui te genent ou il y a qqch que je n'ai pas
vu?


Non, c'est le 6.5.7#3.


Pourquoi? En supposant l'absence de bit de padding le decalage n'est
pas evalue dans sauf si le compilateur peut montrer qu'il n'a pas
d'effet. Meme si ce n'etait pas le cas, le compilateur qui genere du
comportement indefini mechant pour ca dans le cas ou (c) est une
constante est de toute maniere bon a jeter.

J'etais pas la, je ne peux donc te donner que des suppositions qui
vont de personne n'a trouve le probleme suffisemment important
pour en faire une proposition formelle a il y a une machine
repandue que je ne connais pas sur laquelle cela pose un probleme.

La norme est un moyen, pas une fin.


Tu fais ce que tu veux. En ce qui me concerne, je n'ai pas du tout
envie de revoir mon code dès qu'une nouvelle machine apparaît.


Couper les cheveux en 4 dans le sens de la longueur, les yeux bandes
et avec des gands de boxe faut pas exagerer.

A+

--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org




Avatar
Richard Delorme
Dans l'article <41630d88$0$15749$,
Richard Delorme écrit:


Si, comme dans l'exemple de Laurent Deniau, on teste la valeur pour
n'effectuer le décalage que si elle convient, il n'y a plus de
comportement indéfini. Ou alors j'ai manqué un épisode ?



Oui, la section 6.6 de la norme. Cf ma réponse à Charlie sur ce point.



Ben non, je reprends l'exemple de Laurent :

unsigned long U = T;

if (ULONG_MAX == 4294967295UL && GMP_LIMB_BITS > 31) {
U = 0;
} else {
U >>= GMP_LIMB_BITS;
}

T = U;

D'après 6.5.16 1, >>= est un « assignment-operator » or, le paragraphe
6.6 3 dit : « Constant expressions shall not contain assignment, [...],
except when they are contained within a subexpression that is not
evaluated. 95)», donc je ne vois pas ce que vient faire le 6.6 ici. Et
de toute manière :
6.6 11 « The semantic rules for the evaluation of a constant expression
are the same as for nonconstant expressions. »
qui, si j'interprète bien, dit que ce qui marche pour les expressions
non constantes, marche aussi pour les expressions constantes. Donc je ne
comprends pas pourquoi invoquer le 6.6 dans n'importe quel cas.

--
Richard


Avatar
Vincent Lefevre
Dans l'article ,
Jean-Marc Bourguet écrit:

Pourquoi? En supposant l'absence de bit de padding le decalage n'est
pas evalue dans sauf si le compilateur peut montrer qu'il n'a pas
d'effet. Meme si ce n'etait pas le cas, le compilateur qui genere du
comportement indefini mechant pour ca dans le cas ou (c) est une
constante est de toute maniere bon a jeter.


Le problème est l'évaluation (au moment de la traduction) d'une
constante dont le résultat est indéfini. gcc ne produit pas du
code à comportement indéfini, mais génère un warning. C'est
presque tout aussi embêtant et gcc est à jeter. :)

Couper les cheveux en 4 dans le sens de la longueur, les yeux bandes
et avec des gands de boxe faut pas exagerer.


J'observe seulement ce qui se passe dans la pratique.

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA

Avatar
Vincent Lefevre
Dans l'article <4163929d$0$15748$,
Richard Delorme écrit:

Ben non, je reprends l'exemple de Laurent :

unsigned long U = T;

if (ULONG_MAX == 4294967295UL && GMP_LIMB_BITS > 31) {
U = 0;
} else {
U >>= GMP_LIMB_BITS;
}

T = U;

D'après 6.5.16 1, >>= est un « assignment-operator »


U >>= GMP_LIMB_BITS équivaut à U = U >> GMP_LIMB_BITS. Considère la
sous-expression U >> GMP_LIMB_BITS, qui ne contient pas d'affectation.

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA