Folco (./1) :
yop©,


J'aimerais faire un checksum sur deux octets de chaines de caractères contenant ces symboles : a-z, A-Z, 0-9, '_', '.'.

Le problème, c'est que additionner deux mots de même longueur me donnera des résultats proches, et sûrement plus de collisions que si j'additionnais les termes d'une string comprenant des caractères allant de 0 à 255.

Les collisions ne sont pas graves (sauf pour les perfs), les checksums sont justes destinés à accélérer la recherche d'une chaine dans une table de structures {short Checksum, char* Ptr}, sans à avoir à faire des strcmp sur chaque entrée (je code en 68k, et le gain en vitesse est très significatif).

Qui plus est, la somme des lettres d'une string, même "grande", ne dépassera jamais plus d'une douzaine de bits, sur les 16 disponibles dans le champ Checksum.
Ma méthode de checksum qui consiste à additionner juste les caractères des strings les uns aux autres me semble donc peu efficace.

Quel méthode me permettrait donc d'avoir un checksum bien plus efficace (ie plus de bits utilisés, moins de collisions) sans pour autant perdre trop en performance au moment du calcul du-dit checksum ?

Tu viens d'inventer... le tableau de hashage (hash table) ^^

Si tu hash des octets sur une valeur calculé en 16bits, une rotation entre chaque nouvelles valeur permet un minimum d'effet d'avalanche sur le resultat final. Calculer un hash "correct" est proche de la crypto.

un exemple de CRC tout con: unsigned short crc(char *value, int size) { unsigned short crc = 0xDEAD; // toujours mettre une valeur d'initialisation for (i = 0; i < size; i++) { c = value[i] crc = c ^ (crc); crc = ((crc << 8) & 0xFF00) | ((crc >> 8) & 0xFF); crc += c; } return crc; }

Par contre se limiter a certain caractere n'a pas de sens, tout ce que tu vas faire, c'est de complexifier inutilement ton code, autant travailler sur un octet, tu gagneras en vitesse et en lisibilitée