Logo GNT
Actualités Tests & Guides Bons Plans
GTA 6 iPhone 17 Copilot Switch 2 Temu ChatGPT Tesla
OVH Cloud OVH Cloud
Entraide Développement Développement Langage C Valeur vs représentation d'un objet

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.
Signaler un problème avec ce contenu

10 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
3 4 5 6 7
Avatar
Erwan David
Tonton Th écrivait :

On 2013-08-22, Marc Boyer wrote:

Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0
et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres
encodages.



Il me semble même que l'état "NaN" n'est encodé que sur quelques
bits de la représentation mémoire :)



C'est plus compliqué, parcequ'il y a un paquet de NaN différents...
(+0/+0 est différent de -0/+0 par exemple).

--
Les simplifications c'est trop compliqué
Avatar
Samuel DEVULDER
Le 23/08/2013 14:16, Jean-Marc Bourguet a écrit :
Tonton Th writes:

On 2013-08-22, Marc Boyer wrote:

Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0
et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres
encodages.



Il me semble même que l'état "NaN" n'est encodé que sur quelques
bits de la représentation mémoire :)






(de mémoire) Pour un float32, NaN représente les bits suivants:

s111 1111 1qxx xxxx xxxx xxxx xxxx xxxx

s = "signe"
q = "indicateur de NaN silencieux"
x = "libre"

Bref: l'exposant (avec biais) vaut 255.

Question interessante, est-ce que NaN est considere comme une valeur ou
plusieurs? De toute maniere le fait que x != x si x est un NaN offre
pas mal de possibilites de foutre le bazard si on cherche a les mettre
dans des conteneurs associatifs.



Dans le format IEEE754 il y a différents type de NaN: les silencieux
(quiet NaNs) pour lesquels q=1 ci-dessus et ceux qui signalent
(signaling NaNs). Les 22 bits résiduels x servent alors justement à ce
signalement. Cela permet de distinguer plusieurs sortes de NaN, et en
particulier leur cause: 0/0 retourne un NaN qui est différent de celui
de sqrt(-1) qui est lui-même différent de 0*inf, de inf-inf ou de
arc-cos(2.0) ou ln(-1)...

Quand au fait que NaN==NaN répondre faux, je l'interprète via le fait
que NaN n'est justement ni un nombre ni une valeur. C'est pour moi un
panneau indicateur (i.e. pas une valeur) indiquant que quelque chose
s'est mal passé. Et il faut consulter les indications "xxxx" pour
comprendre quel est la nature du problème. En général cela se fait dans
le traitement de la FPE qui sera levée dès que le signaling-NaN sera
utilisée dans un calcul. En corollaire: l'initialisation des flottants
avec des signaling-NaNs peut être une pratique intéressante pour
détecter très tôt l'utilisation de valeurs non-initialisée.

sam.
Avatar
espie
In article <kv1rgd$kjm$,
Marc Boyer wrote:
Le 20-08-2013, candide a écrit :
Par contre, on pourrait avoir des bits "inutilisés", ie sizeof(short)=4,
CHAR_BITS=8, et seulement 16 bits utilisés pour code la valeur, et 16 bits
inutilisés. Dans ce cas, la fonction de hash en effet pourrait renvoyer
des valeurs différentes.



Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas
de page de la Norme :

-------------------------------------------------------------------------
It is possible for objects x and y with the same effective type T to
have the same value when they are accessed as objects of type T, but to
have different values in other contexts. In particular, if == is defined
for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0.
-------------------------------------------------------------------------



Oui. Le cas doit être extrèmement rare avec des entiers, plus commun
avec les flottants.



Apres, hasher des flottants... comment dire ? si t'es pas sur d'etre sur
une implementation iee754 et que tu ne maitrises pas parfaitement ce qui
se passe, bonne chance.
Avatar
espie
In article , Benoit Izac wrote:
C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets
non utilisés) ? Ça ne casse pas l'arithmétique des pointeurs ?



Les amiga 68000 n'en avaient rien a foutre de l'octet de poids fort des
pointeurs.

Du coup, l'amiga basic s'est mis a ne plus marcher sur les miga a base
de 68020.

(question a 0 cents: devinez qui etait l'editeur du basic en question...)
Avatar
Tonton Th
On 2013-08-23, Marc Espie wrote:

C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets
non utilisés) ? Ça ne casse pas l'arithmétique des pointeurs ?



Les amiga 68000 n'en avaient rien a foutre de l'octet de poids fort des
pointeurs.



Pareil sur les Atari ST 68000, d'ailleurs :)

(question a 0 cents: devinez qui etait l'editeur du basic en question...)



Miod ?-)

--
http://weblog.mixart-myrys.org/?post/2013/07/Saucisse-de-geek
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Avatar
espie
In article ,
Tonton Th wrote:
On 2013-08-23, Marc Espie wrote:

C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets
non utilisés) ? Ça ne casse pas l'arithmétique des pointeurs ?



Les amiga 68000 n'en avaient rien a foutre de l'octet de poids fort des
pointeurs.



Pareil sur les Atari ST 68000, d'ailleurs :)

(question a 0 cents: devinez qui etait l'editeur du basic en question...)



Miod ?-)



Je pense qu'il ne va pas apprecier la comparaison...
Avatar
Antoine Leca
Benoit Izac écrivit :
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* ?


Antoine
Avatar
Antoine Leca
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.


Antoine
Avatar
espie
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). Et sauf
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).

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".
Comme d'habitude pour la norme, c'est parce qu'il existe des implementations
qui derogent a la regle.

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...
qui pourraient par exemple faire du controle de parite ou autre possibilite
bizarre (type-check en hardware ou autre).
Avatar
Antoine Leca
candide écrivit :
int hashmapHash(void* key, size_t keySize) {
int h = keySize;
char* data = (char*) key;
size_t i;
for (i = 0; i < keySize; i++) {


[...]

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.



Même avec une chaîne de caractères cela peut poser des problèmes, selon
la manière dont est déterminée la valeur de «keySize» passée à la
fonction: c'est bon si on utilise la longueur utile de la chaîne
(strlen), mais ce n'est plus bon avec la longueur allouée (qui est la
vraie taille de l'objet pointé par «key»), car les octets de bourrage
après le '' sont indéfinis et donc doivent être supposés aléatoires.


Antoine
3 4 5 6 7