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
Jean-Marc Bourguet
Vincent Lefevre <vincent+ writes:

Ce n'est pas un warning stupide puisqu'il est justifié: comportement
indéfini (même si en pratique, il y a peu de chance que cela ait un
effet non voulu).


Il me semblait que le critere fondamental d'interet d'un warning,
c'est la proportion de faux positifs qui doit etre faible. Tu es en
train de dire qu'elle est enorme, donc il n'a pas d'interet.

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

U >>= GMP_LIMB_BITS équivaut à U = U >> GMP_LIMB_BITS.


Non.

--
Richard

Avatar
Laurent Deniau
Vincent Lefevre wrote:
Dans l'article <cjucbf$lub$,
Laurent Deniau écrit:


Defini dans tous les cas mais ne fait pas necessairement ce que tu veux
en >32 bits d'ou ma suggestion initiale de passer par le preprocesseur
pour selectionner le code correct. Idem pour le warning du compilo.



Non, la norme dit bien que c'est du comportement indéfini.

6.5.7 Bitwise shift operators
[...]
[#3] The integer promotions are performed on each of the
operands. The type of the result is that of the promoted
left operand. If the value of the right operand is negative
or is greater than or equal to the width of the promoted
left operand, the behavior is undefined.


Si tu cherches une solution portable, definie et simple, c'est possible.
Si tu veux juste me montrer des passages de la norme, j'ai deja la
mienne et je n'ai pas le temps de polemiquer. Dans mes postes, j'ai cite
le preprocesseur plusieurs fois, j'ai utilise un if else et non ?: comme
indice.

D'autre part, ton probleme est de determiner la taille de T en fonction
de GMP_LIMB_BITS, pas la valeur de GMP_LIMB_BITS et c'est un probleme
tres classique discute maintes fois ou la conclusion est toujours la
meme: seul le preprocesseur et l'utilisation des macros de limits.h
permettent de selectionner un code defini et portable.

Pour finir, tu peux regarder le header ffi.h de la bib ffi qui configure
ses ffi_*type*_t en fonction des valeurs de limits.h de facon tres
propre, y compris pour du 64 bits lorsque l'archi est 32 bits. L'ordre
des #if et celui des termes des tests ont leur importance...

a+, ld.


Avatar
Antoine Leca
En 20041006001202$, Vincent Lefevre va escriure:
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),


Oui.

et dans ce cas, il y a comportement indéfini.


Oui. Et alors ?
Le programme n'en sera pas moins strictement conforme.

4. Conformance
[#5] A /strictly conforming program/ shall use only those
features of the language and library specified in this
International Standard.* It shall not produce output
dependent on any unspecified, undefined, or implementation-
^^^^^^^^^
defined behavior, and shall not exceed any minimum
implementation limit.

Autrement dit, si le comportement indéfini est dans du code non évalué, le
compilateur a effectivement le droit de lancer l'exécution (c'est ce que
fera un processeur moderne avec prédiction de branchement, de toute
manière), mais il n'a pas le droit de laisser sortir les dragons pour cela.
Au nid!


Antoine


Avatar
Vincent Lefevre
Dans l'article <41639a82$0$15747$,
Richard Delorme écrit:


U >>= GMP_LIMB_BITS équivaut à U = U >> GMP_LIMB_BITS.


Non.


Si (avec une seule évaluation du U évidemment).

--
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 <ck0fuf$q8h$,
Antoine Leca écrit:

Autrement dit, si le comportement indéfini est dans du code non évalué,
[...]


Mais si le comportement indéfini est dans du code évalué à la
traduction (cf 6.6#2, ce qui est le cas qui me préoccupe)?

--
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 ,
Jean-Marc Bourguet écrit:

Vincent Lefevre <vincent+ writes:

Ce n'est pas un warning stupide puisqu'il est justifié: comportement
indéfini (même si en pratique, il y a peu de chance que cela ait un
effet non voulu).


Il me semblait que le critere fondamental d'interet d'un warning,
c'est la proportion de faux positifs qui doit etre faible. Tu es en
train de dire qu'elle est enorme, donc il n'a pas d'interet.


Je n'ai pas dit cela. Attention, je ne me fixe pas sur une
implémentation particulière. Par exemple, si quelqu'un écrit

int main(void)
{
return 1 >> 32;
}

avec certaines (de nombreuses) implémentations, ça va toujours
fonctionner, mais ce n'est pas du tout portable. Un warning me
semble donc justifié (mais pour ceux qui écrivent du code pour
une plateforme spécifique, il serait bien également que de tels
warnings soient désactivables).

--
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 <20041006111915$,
Vincent Lefevre <vincent+ écrit:

Dans l'article <41639a82$0$15747$,
Richard Delorme écrit:


U >>= GMP_LIMB_BITS équivaut à U = U >> GMP_LIMB_BITS.


Non.


Si (avec une seule évaluation du U évidemment).


D'ailleurs, voilà exactement où c'est dit dans la norme:

6.5.16.2 Compound assignment
[...]
Semantics

[#3] A compound assignment of the form E1 op= E2 differs
from the simple assignment expression E1 = E1 op (E2) only
in that the lvalue E1 is evaluated only once.

--
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 <ck0aia$8sr$,
Laurent Deniau écrit:

Si tu cherches une solution portable, definie et simple, c'est possible.
Si tu veux juste me montrer des passages de la norme, j'ai deja la
mienne et je n'ai pas le temps de polemiquer. Dans mes postes, j'ai cite
le preprocesseur plusieurs fois, j'ai utilise un if else et non ?: comme
indice.


Ah, comment fais-tu le test à l'aide du préprocesseur?

J'ai l'impression qu'on a obligatoirement besoin ou bien d'un cast
(mais impossible dans un #if du préprocesseur) ou bien d'un sizeof
(idem).

D'autre part, ton probleme est de determiner la taille de T en fonction
de GMP_LIMB_BITS, pas la valeur de GMP_LIMB_BITS et c'est un probleme
tres classique discute maintes fois ou la conclusion est toujours la
meme: seul le preprocesseur et l'utilisation des macros de limits.h
permettent de selectionner un code defini et portable.


Je ne vois pas quelle macro permet de donner la taille d'un type entier
*quelconque* (d'ailleurs les types sont aliasés après application du
préprocesseur, je ne vois donc pas comment ça serait possible).

Pour finir, tu peux regarder le header ffi.h de la bib ffi qui configure
ses ffi_*type*_t en fonction des valeurs de limits.h de facon tres
propre, y compris pour du 64 bits lorsque l'archi est 32 bits. L'ordre
des #if et celui des termes des tests ont leur importance...


Ce n'est pas une solution propre. Je n'ai pas envie d'avoir à
retoucher tous mes sources dans 10 ans quand une nouvelle plateforme
apparaîtra (par exemple avec un type sur 512 bits). Et dans mon cas,
le type est défini suivant d'autres critères, si bien que la solution
de ffi.h n'est pas acceptable.

--
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
Laurent Deniau
Vincent Lefevre wrote:
Dans l'article <ck0aia$8sr$,
Laurent Deniau écrit:


Si tu cherches une solution portable, definie et simple, c'est possible.
Si tu veux juste me montrer des passages de la norme, j'ai deja la
mienne et je n'ai pas le temps de polemiquer. Dans mes postes, j'ai cite
le preprocesseur plusieurs fois, j'ai utilise un if else et non ?: comme
indice.



Ah, comment fais-tu le test à l'aide du préprocesseur?

J'ai l'impression qu'on a obligatoirement besoin ou bien d'un cast
(mais impossible dans un #if du préprocesseur) ou bien d'un sizeof
(idem).


Le cast n'est pas un probleme selon tes propos (c'etait ma premiere
question) et il est biensur essentiel pour fixer le type de index_t. Le
choix du unsigned long n'est pas anodin. Il correspond generalement au
plus gros mot processeur (32, 64, 128, ...) et garantit 32 bits si ce
mot est < 32bits. Certe, le cast est sous-optimal si index_t < 32 bits.

D'autre part, unsigned int peut etre 32 bits sur une archi 64 bits et
utiliser unsigned long long pour la definition de index_t serait une
aberration.

sizeof souleve les problemes deja cites dans ce thread.

D'autre part, ton probleme est de determiner la taille de T en fonction
de GMP_LIMB_BITS, pas la valeur de GMP_LIMB_BITS et c'est un probleme
tres classique discute maintes fois ou la conclusion est toujours la
meme: seul le preprocesseur et l'utilisation des macros de limits.h
permettent de selectionner un code defini et portable.



Je ne vois pas quelle macro permet de donner la taille d'un type entier
*quelconque* (d'ailleurs les types sont aliasés après application du
préprocesseur, je ne vois donc pas comment ça serait possible).


Une fois le cast admit, il suffit de verifier GMP_LIMB_BITS par rapport
ULONG_MAX dans l'ordre du plus petit au plus grand pour eviter les
warning (preprocesseur et compilateur). Ca te permet ainsi de definir la
macro GMP_LIMB_SAFE_RSHIFT() qui va bien pour la paire (GMP_LIMB_BITS,
unsigned long).

Pour finir, tu peux regarder le header ffi.h de la bib ffi qui configure
ses ffi_*type*_t en fonction des valeurs de limits.h de facon tres
propre, y compris pour du 64 bits lorsque l'archi est 32 bits. L'ordre
des #if et celui des termes des tests ont leur importance...


Ce n'est pas une solution propre. Je n'ai pas envie d'avoir à
retoucher tous mes sources dans 10 ans quand une nouvelle plateforme
apparaîtra (par exemple avec un type sur 512 bits).


Ce type aura peut d'interet (~ 10^154). Tu as deja regarde ce que vaut
2^128-1 (~ 10^38) ? Ceci dit rien ne t'empeche de prevoir deja ce cas
;-) et de finir la serie de #if par un #else #error facile a reperer
(plus facile qu'un test foireux sur un sizeof).

Et augmenter la serie de cas sera un jeux d'enfant par rapport a tous
les problemes que la nouvelle norme (C2099?) demandera comme
modifications a ton code...

Et dans mon cas,
le type est défini suivant d'autres critères, si bien que la solution
de ffi.h n'est pas acceptable.


J'attends avec impatience ta solution.

a+, ld.