Discussion :

[killer crok]

Connaissez vous une fonction de hachage qui prendrait entre 2 et 50 octets en entree et qui resort un mot de 2 octets??


Il est possible que ca n'existe pas, j'ai regarde les standards de fonction de hachage mais elle prenne 512 bits en entree et resorte des trucs sur 128 bits.

Merci.

[D[r]eadLock]

Je ne connais pas exactement les proprietes des fonctions de hachage, mais je propose: de faire :
. soit additions sur 2 octets (tu decoupe ton mot par tranches de 2 octets (pour le dernier tu mettre une valeur arbitraire tq la repartission soit maximun (donc 0x7F, 128).
. soit xor sur 2 octets toujours (pour le rajout 0xAA me semble bien).

Apres tu fais des tests pour voir les repartitions en fonctions des mots que tu as.

Tu peux peut-etre ameliorer la repartition, en ajoutant des decalages sur les octets (voire sur les paires) pour ameliorer encore la repartition

[gl]

Ca depends beaucoup de ce que tu souhaite hache! Il faudrait precise r un peu ta question

Mais si tu veux quelque chose qui fonctionne sans etre forcement optimal je te conseille de partir de qqch de simple (une addition ou un XOR comme le suggere D[r]eadLock) et d'affiner ensuite pour resoudre le probleme de colisions trop nombreuses.

[killer crok]

Je peut pas vraiment preciser ce que c'est, c'est confidenciel, de toute maniere se sont des octets.

En fait je bosse sur de l'embarque, donc il faut que ca aille vite et que ca prenne pas de place (je sais je veux le beurre et l'argent du beurre mais on y arrive!)

Par contre le truc de l'addition peut etre pas mal, mais je peut savoir que je vais pas avoir des milliers de collisions?

(cette fonction est assez importante pour la securite de mon truc)

[D[r]eadLock]

Par contre le truc de l'addition peut etre pas mal, mais je peut savoir que je vais pas avoir des milliers de collisions?

Tu fais les tests sur des exemples de codes/mots que tu vas avoir a traiter. Et tu regarde ce que ca donne (le nombre de mot par code produit par exemple).

Forme toi pour t'améliorer en lisant des cours et tutoriels pour la programmation C : http://c.developpez.com/cours/

[killer crok]

Le probleme c'est que mes mots vont de 2 à 50 octets, donc si ils faut que je fasse presque toutes les combinaisons et que je traites les données ca va me prendre un peu de temps pour avoir une fonction optimisé!!

J'ai trouve une fonction toute conne je suis en train de faire des tests, mais si vous avez d'autres propositions...

(la fonction que j'ai, consiste à calculer un modulo avec un nombre premier, pour ceux qui y auraient penser)

[gl]

Je peut pas vraiment preciser ce que c'est, c'est confidenciel, de toute maniere se sont des octets.

Je ne voulais pas savoir a quoi correspondais les donnees, mais plutot la repartition de celle ci, si la presence de chaque valeur est equiprobable, n'importe quelle focntion simple (additin, XOR, etc.) donne de bon resultat.
Si certain bit sont plus present que d'autre, il faut trouver autre chose. Et si certains sont toujours a une valeur particuliere, on peut ne pas en tenir compte dans le hachage.

[Ol']

Il ne faut pas perdre de vue de le résultat doit être très différent pour deux entrées relativement proches. Alors, les additions, c'est pas top.

Ol'

[hot metal]

Salut

un petit code maison

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
 
#define rotl(x,y) ((x>>y)|(x<<(8-y)))
#define rotr(x,y) ((x<<y)|(x>>(8-y)))
 
int main(int argc, char * argv[])
{
        unsigned char variable[100],hash[2];
        int x,y,len;
 
        memset(hash,0,2);
        sprintf(variable,"tess");
        len = strlen(variable);
        for(x=0;x<8;x++)
        {
                for(y=0;y<len-2;y++)
                        hash[0]=(rotl(variable[y],x)^0x55)^(rotr(variable[y+1],x)^hash[1]);
 
                for(y=len-1;y>0;y--)
                        hash[1]+=((rotl(variable[y],x)^0x55)^rotr(variable[y-1],x))^hash[0];
 
        }
 
        printf("tess -> hash[0] = 0x%02X - hash[1] = 0x%02X\n",hash[0],hash[1]);
 
        memset(hash,0,2);
        sprintf(variable,"test");
        len = strlen(variable);
        for(x=0;x<8;x++)
        {
                for(y=0;y<len-2;y++)
                         hash[0]=(rotl(variable[y],x)^0x55)^(rotr(variable[y+1],x)^hash[0]);
                for(y=len-1;y>0;y--)
                        hash[1]+=((rotl(variable[y],x)^0x55)^rotr(variable[y-1],x))^hash[0];
        }
 
        printf("test -> hash[0] = 0x%02X - hash[1] = 0x%02X\n",hash[0],hash[1]);
 
        return(0);
}

Resultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
tess -> hash[0] = 0x20 - hash[1] = 0xD6
test -> hash[0] = 0xFF - hash[1] = 0x7F

[Musaran]

Il ne faut pas perdre de vue de le résultat doit être très différent pour deux entrées relativement proches.

Pourquoi ?
Tant que c'est différent, c'est bon, non ?

[killer crok]

Merci de votre aide, j'ai trouvé ce qu'il me faut.

[D[r]eadLock]

Merci de votre aide, j'ai trouvé ce qu'il me faut.

Par curiosite, algo retenu ?

[killer crok]

J'ai fait un mix entre l'algo de Hot metal et la fonction qui consiste à calculer le modulo par un nombre premier sur la chaine à hacher.

Voila merci.