OVH Cloud OVH Cloud

Valeur vs représentation d'un objet

62 réponses
Avatar
candide
Bonjour,

Je suis en train d'examiner le code source de différentes tables de
hachage _génériques_ [ie pouvant hacher n'importe quel type de données
(entiers, structures, etc) et pas seulement des chaînes de caractères].

Je suis surpris que les fonctions de hachage de la clé (qui se présenter
typiquement en void *key) se basent sur la seule représentation de
l'objet à hacher plutôt que sur sa valeur.

Voici un cas typique, cf.
https://github.com/cgjones/android-system-core/blob/master/libcutils/hashmap.c
:


int hashmapHash(void* key, size_t keySize) {
int h = keySize;
char* data = (char*) key;
size_t i;
for (i = 0; i < keySize; i++) {
h = h * 31 + *data;
data++;
}
return h;
}

Si la fonction de hachage ci-dessus est appliquée à une chaîne de
caractères, il me semble qu'elle ne pose aucun problème. En revanche si
la clé est d'un autre type comme int ou même unsigned int, il pourrait
en aller autrement. En effet, la norme du langage C n'assure pas du tout
que deux objets ayant même valeur aient nécessairement même
représentation. Si, par exemple, l'entier disons 421, est susceptible
d'avoir deux représentations différentes (autrement dit memcmp ne
renverrait pas 0) deux clés de même valeur, par exemple, 420+1 et 422-1,
pourraient renvoyer des hash différents : catastrophe.


Merci pour vos réponses.

10 réponses

3 4 5 6 7
Avatar
Benoit Izac
Bonjour,

le 27/08/2013 à 11:47, Antoine Leca a écrit dans le message
<kvhsk5$n1o$ :

Ce qui me gène c'est pourquoi, dans ce cas, memcmp prend en argument des
void* et non des char* ?



La raison est que la conversion de toto* à void* est silencieuse, ce qui
ne serait pas le cas d'une conversion directe (implicite) vers char*

Maintenant, je ne comprend pas en quoi cela pourrait te *gêner* ?



Ce qui me gêne, c'est que lorsque je vois une fonction qui prend en
argument un void*, je m'attends à ce qu'elle marche avec n'importe quoi.
Or ici ce n'est clairement pas le cas et, si j'ai bien compris toute la
discussion, le comportement n'est défini qu'avec des (unsigned) char*
puisque tous les autres types (non entiers je pense) peuvent avoir une
représentation en mémoire différente tout en ayants la même valeur (==).

--
Benoit Izac
Avatar
espie
In article , Benoit Izac wrote:
Bonjour,

le 27/08/2013 à 11:47, Antoine Leca a écrit dans le message
<kvhsk5$n1o$ :

Ce qui me gène c'est pourquoi, dans ce cas, memcmp prend en argument des
void* et non des char* ?



La raison est que la conversion de toto* à void* est silencieuse, ce qui
ne serait pas le cas d'une conversion directe (implicite) vers char*

Maintenant, je ne comprend pas en quoi cela pourrait te *gêner* ?



Ce qui me gêne, c'est que lorsque je vois une fonction qui prend en
argument un void*, je m'attends à ce qu'elle marche avec n'importe quoi.
Or ici ce n'est clairement pas le cas et, si j'ai bien compris toute la
discussion, le comportement n'est défini qu'avec des (unsigned) char*
puisque tous les autres types (non entiers je pense) peuvent avoir une
représentation en mémoire différente tout en ayants la même valeur (==).



Ben memcmp sert a comparer de la memoire. Les gens s'en servent en
pratique pour comparer plein de trucs. Il convient de rappeler quand meme
qu'il y a des choses qui sont implementation-defined dans la norme, et
pas completement indefinies. La representation des entiers, les bits de
bourrage, tout ceci peut etre completement definie par l'implementation.
Auquel cas il est parfaitement possible d'ecrire du code C correct (mais
non portable) qui utilisera memcmp pour comparer d'autres choses.

Evidemment, il faut documenter quelque part les hypotheses en vigueur pour
que le code C qu'on a ecrit fonctionne...
Avatar
Antoine Leca
Marc Espie écrivit :
In article <kvht9h$qqb$,
Antoine Leca wrote:
candide écrivit :
Le 20/08/2013 20:06, Tonton Th a écrit :
Pour les structures, il ne faut surtout pas oublier les
éventuels octets de remplissage dont les valeurs sont
totalement imprévisibles (voir le théorème de Murphy)



La parade classique étant alors de zéroïfier la structure via memset.
Mais d'après certains sur clc, cela ne garantit pas de la
non-réapparition de bits de padding aléatoires lors de l'affectation
ultérieure d'un membre de la structure. Donc hacher des structures de
façon standard semble être assez acrobatique : après chaque affectation
de membre, il faudrait zéroïfier entre les différents membres de la
dite-structure.



Comme tu viens de l'écrire deux phrases avant, on ne sait pas (de
manière portable, c'est-à-dire sans intervention explicite du
compilateur) « zéroïfier » les bits de remplissage ; une solution est de
sérialiser les données structurées, ce qui élimine de fait les octets de
remplissage, mais ne répond pas à tous les cas, cf. flottants.



Ce que tu ecris est un peu ambigu. memset saura zeroifier la totalite d'une
structure, dans un sens tres precis (mettre tous les octets a zero).



Oui, *tous* ; et l'idée est de ne mettre à zéro *que* les octets de
remplissage, puisqu'on souhaite préserver la valeur des membres de la
structure...

erreur de ma part, ca doit marcher sur les implementations freestanding
(flemme de sortir la norme et verifier, mais ca me surprendrait que
memset/memcpy/memmove ne fasse pas partie du coeur des fonctions garanties).



Pour info: <string.h> ne fait pas partie des fonctions garanties ; en
fait, les fonctions garanties sont réduites à celles qui ne nécessitent
pas de code du tout (donc pas besoin de libc.a).


Ce que ca veut dire de precis pour les valeurs, ca par contre, c'est une
autre paire de manches... meme sans les flottants, ne pas oublier que la
representation d'un pointeur nul n'est pas garantie d'etre "tous les bits a 0".



Bonne remarque, et une autre raison en plus des problèmes de bourrage
externe (octets d'alignements) ou interne (genre le cas des pointeurs 24
bits du MC68000 stockés dans 32 bits) pour ne pas essayer de poursuivre
dans cette voie !


Je ne suis meme pas sur que ca soit applicable pour les entiers. Me semble
que la norme est tres precise dans son vocabulaire concernant les unsigned int,
mentionnant explicitement la possibilite d'avoir des bits en plus...



Très clairement, la norme /et/ la réalité autorisent le cas (DSP) où
l'entier sur 40 ou 48 bits est stocké dans 64 bits.


Antoine
Avatar
c.candide
Le vendredi 30 août 2013 10:14:43 UTC+2, Antoine Leca a écrit :


Oui, *tous* ; et l'idée est de ne mettre à zéro *que* les octets de

remplissage, puisqu'on souhaite préserver la valeur des membres de la

structure...






Et ce n'est pas possible (de façon portable) ? La solution naïve ne mar che pas ? La solution naïve c'est de zéroifier séquentiellement entre la fin d'un membre et le début du suivant les éventuels bits de paddin g, pour ça j'ai juste besoin de connaître les adresses des début et f in de chaque zone de padding ce qui est possible en utilisant sizeof sur le s membres de la structures.
Avatar
Antoine Leca
écrivit :
Le vendredi 30 août 2013 10:14:43 UTC+2, Antoine Leca a écrit :
Oui, *tous* ; et l'idée est de ne mettre à zéro *que* les octets de
remplissage, puisqu'on souhaite préserver la valeur des membres de la
structure...



Et ce n'est pas possible (de façon portable) ?



Je ne sais pas le faire.

La solution naïve ne marche pas ? La solution naïve c'est de zéroifier
séquentiellement entre la fin d'un membre et le début du suivant les



Définis « fin d'un membre » ?

éventuels bits de padding,



Mmmm... Avec la méthode dont tu parles (écrire des octets à 0), au plus
tu vas pouvoir éradiquer les _octets_ de bourrage, c'est-à-dire les
octets que le compilateur rajoute entre les membres pour différentes
raisons, de performance ou pour pouvoir avoir des accès correctement
alignés aux membres ou aux éléments d'un tableau de la structure.

Les _bits_ de remplissage sont pour moi un autre concept, celui de bits
sans signification sémantique mais qui font partie de la représentation
des objets en mémoire. On peut avoir des bits de parité, ou des bits
imposé par le matériel, comme par exemple le cas (pas habituel en C,
mais qui peut exister avec d'autres langages) des valeur booléennes
stockées de manière comprimée à 8 par octet, quand on les manipule de
manière individuelle il faut bien « gâcher » 7 bit par objet...

pour ça j'ai juste besoin de connaître les adresses des début et fin
de chaque zone de padding ce qui est possible en utilisant sizeof
sur les membres de la structures.



Il y a au moins trois handicaps à ta solution : cela ne marche dans le
cas général ni pour les champs de bits, ni pour les unions, ni pour les
structures membres d'une autre structure (il faudrait récurer pour
déterminer le bourrage à la fin de la structure).

Par ailleurs, je ne vois pas ce qui oblige le compilateur à utiliser
*tout* l'espace indiqué par sizeof(type) pour ranger chaque membre ; par
exemple 3*sizeof(long double) pour stocker 3 membres long double.
Exemple : avec certains compilateurs amd64, les long doubles sont des
flottants IEEE étendus sur 80 bits (10 octets) ; en général, un élément
isolé est stocké sur 16 octets pour être aligné sur une adresse 64 bits,
ce qui est largement plus facile à manipuler pour le compilateur
(alignement sur la pile); mais pour le CPU, cet alignement n'a pas
vraiment d'importance, donc pour une structure avec 3 membres long
double, il n'est pas nécessaire de gâcher tant d'espace et on peut
imaginer de ranger les membres bord à bord, avec juste 2 octets au bout,
total 30+2 octets soit 2*sizeof(long double) !
La rédaction de 6.5.3.4a4 et 6.7.2.1a14 me semble aller dans ce sens.

Plus exactement, je vois très bien pourquoi les compilateurs NE font PAS
ce genre de compression : il y a bien trop de programmeurs qui vont être
surpris par ce genre d'optimisation et qui vont le considérer comme un
bogue, au motif que cela casse leur code, qui pourrait par exemple faire
un alias entre les 3 membres et un (long double[3]) !


Antoine
Avatar
espie
In article ,
wrote:

Et ce n'est pas possible (de façon portable) ? La solution naïve ne
marche pas ? La solution naïve c'est de zéroifier séquentiellement entre
la fin d'un membre et le début du suivant les éventuels bits de padding,
pour ça j'ai juste besoin de connaître les adresses des début et fin de
chaque zone de padding ce qui est possible en utilisant sizeof sur les
membres de la structures.



Non, pas forcement. Pour tout type, tu as par definition
sizeof(a[10]) = sizeof(a[0]) * 10

ce qui implique que sizeof(T) peut inclure des bits de bourrage pour
l'alignement de l'element suivant dans un tableau (et a fortiori pour ta
structure).
Avatar
candide
Le 30/08/2013 16:48, Antoine Leca a écrit :

Définis « fin d'un membre » ?




Naïvement, ce qui commence à a+n où a est l'adresse du membre et n sa
taille.


Mmmm... Avec la méthode dont tu parles (écrire des octets à 0), au plus
tu vas pouvoir éradiquer les _octets_ de bourrage, c'est-à-dire les
octets que le compilateur rajoute entre les membres pour différentes
raisons, de performance ou pour pouvoir avoir des accès correctement
alignés aux membres ou aux éléments d'un tableau de la structure.

Les _bits_ de remplissage sont pour moi un autre concept, celui de bits
sans signification sémantique mais qui font partie de la représentation
des objets en mémoire. On peut avoir des bits de parité, ou des bits
imposé par le matériel, comme par exemple le cas (pas habituel en C,
mais qui peut exister avec d'autres langages) des valeur booléennes
stockées de manière comprimée à 8 par octet, quand on les manipule de
manière individuelle il faut bien « gâcher » 7 bit par objet...




Tu veux dire alors que ces bits (parité, matériel) sont "incontrôlables"
et vont revenir même si on les éradique ?


Sinon, quelqu'un pourrait-il citer le passage de la norme qui montre que
les bits entre les membres d'une structure peuvent être modifiés à
n'importe quel accès au membre ? cf. ce que j'avais rapporté de mes
lectures sur clc mais qui ne donnaient aucune référence.



pour ça j'ai juste besoin de connaître les adresses des début et fin
de chaque zone de padding ce qui est possible en utilisant sizeof
sur les membres de la structures.



Il y a au moins trois handicaps à ta solution : cela ne marche dans le
cas général ni pour les champs de bits, ni pour les unions, ni pour les
structures membres d'une autre structure (il faudrait récurer pour
déterminer le bourrage à la fin de la structure).



Ça on est d'accord : les unions et les champs de bits, je ne tiens pas à
les utiliser et je vois bien qu'il y a une complication avec des
structures imbriquées mais en pratique, pour des clés d'une table de
hachage on doit pouvoir s'en passer ou sinon appliquer récursivement la
méthode de zéroïfication (à condition qu'elle marche bien sûr déjà sans
imbrication).



Par ailleurs, je ne vois pas ce qui oblige le compilateur à utiliser
*tout* l'espace indiqué par sizeof(type) pour ranger chaque membre ; par
exemple 3*sizeof(long double) pour stocker 3 membres long double.
Exemple : avec certains compilateurs amd64, les long doubles sont des
flottants IEEE étendus sur 80 bits (10 octets) ; en général, un élément
isolé est stocké sur 16 octets pour être aligné sur une adresse 64 bits,
ce qui est largement plus facile à manipuler pour le compilateur
(alignement sur la pile); mais pour le CPU, cet alignement n'a pas
vraiment d'importance, donc pour une structure avec 3 membres long
double, il n'est pas nécessaire de gâcher tant d'espace et on peut
imaginer de ranger les membres bord à bord, avec juste 2 octets au bout,
total 30+2 octets soit 2*sizeof(long double) !




A vrai dire, je n'ai aucun besoin de hacher des flottants et je connais
trop mal ce type pour m'y risquer. Je me limite aux types entiers et
aux agrégats d'entiers. À ce que j'ai compris, il existe au plus trois
types de bits : bit de valeur, bit de signe et bit de padding. D'après
ce que j'ai lu (entre autres, les commentaires du Standard par Derek
Jones), les bits de padding sont en fait très rares. Et, par ailleurs,
pour moi le problème n'est pas tellement la présence de bits de parité
ou autre mais c'est surtout que j'ai une permanence de la représentation
des objets de valeur donnée, c'est à dire que, par exemple, l'entier
421, dans un type donné et fixé, admette toujours la même représentation
tout au long de l'exécution du programme en sorte que si je calcule la
clé en me basant sur la représentation, deux instances de 421 donnent la
même clé.
Avatar
Jean-Marc Bourguet
candide writes:

Le 30/08/2013 16:48, Antoine Leca a écrit :

Définis « fin d'un membre » ?




Naïvement, ce qui commence à a+n où a est l'adresse du mem bre et n sa
taille.


Mmmm... Avec la méthode dont tu parles (écrire des octets à   0), au plus
tu vas pouvoir éradiquer les _octets_ de bourrage, c'est-à-dir e les
octets que le compilateur rajoute entre les membres pour différentes
raisons, de performance ou pour pouvoir avoir des accès correctement
alignés aux membres ou aux éléments d'un tableau de la st ructure.

Les _bits_ de remplissage sont pour moi un autre concept, celui de bits
sans signification sémantique mais qui font partie de la repré sentation
des objets en mémoire. On peut avoir des bits de parité, ou de s bits
imposé par le matériel, comme par exemple le cas (pas habituel en C,
mais qui peut exister avec d'autres langages) des valeur booléennes
stockées de manière comprimée à 8 par octet, quand o n les manipule de
manière individuelle il faut bien « gâcher » 7 bit p ar objet...




Tu veux dire alors que ces bits (parité, matériel) sont "incont rôlables" et
vont revenir même si on les éradique ?



Pire, tu mets une mauvaise valeur et ca crashe.

Ces bits d'une part:

- tu peux deviner leur presence (parce que par exemple il y a plus de
bits que necessaires pour couvrir l'intervalle MIN MAX)

- tu ne peux pas savoir ou ils sont (enfin, tu peux jouer a faire +1
puis voir ce qui change et faire des deductions)

- tu ne peux pas savoir quelles sont les contraintes de l'implementation
(quelques idees comme ca qui ne correspond pas necessairement a quelque
chose de connu: une partie des bits de bourrage correspond a de
l'extension de signe; des bits de parites ou de code de correction
d'erreurs; les entiers et les flottants partagent en fait leur
representation et donc les bits de bourrage c'est l'exposant qui est
fixe; des tags indiquant le type)

Sinon, quelqu'un pourrait-il citer le passage de la norme qui montre que
les bits entre les membres d'une structure peuvent être modifié s à
n'importe quel accès au membre ? cf. ce que j'avais rapporté de mes
lectures sur clc mais qui ne donnaient aucune référence.



Je vais plutot te demander le passage qui l'interdit. Parce que si
c'est pas interdit, c'est autorise.

À ce que j'ai compris, il existe au plus trois types de
bits : bit de valeur, bit de signe et bit de padding. D'après ce que j'ai
lu (entre autres, les commentaires du Standard par Derek Jones), les bits
de padding sont en fait très rares.



Pour les entiers, oui. Se limiter aux implementations qui n'ont pas de
bits de padding dans les entiers est a mon sens raisonnable dans pas mal
de contextes.

Et, par ailleurs, pour moi le problème n'est pas tellement la prà ©sence
de bits de parité ou autre mais c'est surtout que j'ai une permanence
de la représentation des objets de valeur donnée, c'est à dire que,
par exemple, l'entier 421, dans un type donné et fixé, admette
toujours la même représentation tout au long de l'exécutio n du
programme en sorte que si je calcule la clé en me basant sur la
représentation, deux instances de 421 donnent la même clé.



Il reste le probleme de + et -0, mais j'aurais facilement tendance a
ignore les machines en complements a 1 et en grandeur et signe.

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Avatar
espie
In article <5220bd93$0$2317$,
candide wrote:
Sinon, quelqu'un pourrait-il citer le passage de la norme qui montre que
les bits entre les membres d'une structure peuvent être modifiés à
n'importe quel accès au membre ? cf. ce que j'avais rapporté de mes
lectures sur clc mais qui ne donnaient aucune référence.



Candide, toujours aussi drole dans tes questions.

C'est dans l'autre sens. Trouve un passage de la norme qui montre qu'on a
quoi que ce soit comme controle/definition du contenu exact en memoire d'une
structure. Lis attentivement le chapitre 6, en particulier 6.2.6.1
(dans C99) qui demarre par "The representations of all types are unspecified
except as stated in this subclause"...

tout le reste dit "unspecified" des qu'on parle de padding bits ou de
padding bytes.

Le seul truc que j'y repere d'utile (et dont je n'etais pas sur), c'est que
les padding bytes ne modifient pas la nature de la valeur representee:
en particulier ils ne peuvent induire de "trap representation".
Avatar
candide
Le 30/08/2013 21:11, Marc Espie a écrit :


Lis attentivement le chapitre 6, en particulier 6.2.6.1
(dans C99) qui demarre par "The representations of all types are unspecified
except as stated in this subclause"...

tout le reste dit "unspecified" des qu'on parle de padding bits ou de
padding bytes.




Le fait qu'une affectation d'un objet membre d'une structure puisse
modifier la représentation de la structure ailleurs que là où l'objet
affecté est mémorisé est un effet de bord qui doit bien être décrit par
la Norme.

D'après James Kuyper ainsi qu'Eric Sosman sur clc, et Niklas Matthies
sur comp.std.c, le passage de la Norme qui justifie la modification
possible des bits de padding lors d'une affectation est dans ... le
paragraphe auquel tu me renvoies :

"When a value is stored in an object of structure or union type,
including in a member object, the bytes of the object representation
that correspond to any padding bytes take unspecified values." (6.2.6.1p6)


cf. https://groups.google.com/d/msg/comp.lang.c/NMnnP7D6pvk/NysGUf6LuFYJ
et https://groups.google.com/d/msg/comp.std.c/vq8xrccAf2A/nSM42I3v3GMJ


Suite à ces références, j'ai regardé dans les commentaires de la norme
de Derek Jones et c'est bien en 6.2.6.1p6 qu'il justifie le phénomène
(p. 585-6) :


-------------------------------------------------------------------------
When a value is stored in an object of structure or union type,
including in a member object, the bytes of the value stored in structure
value stored in union
object representation that correspond to any padding bytes take
unspecified values.
[...]
Coding Guidelines
A program cannot rely on the padding bits of an object having structure
or union type remaining unchanged when one of its members is modified,
or the entire object is assigned a new value.
-------------------------------------------------------------------------
3 4 5 6 7