L'algorithme de somme de contrôle BSD (en anglais BSD checksum) est un algorithme de somme de contrôle très utilisé. Il a été implémenté dans les distributions BSD et est également disponible dans l'utilitaire en ligne de commande GNU sum.
Code de l'algorithme Ci-dessous la partie correspondant à la somme de contrôle BSD du code source C de GNU sum (sous licence GPL). Ce code calcule une somme de contrôle de 16 bits en sommant tous les octets du flux d'entrée. Pour éviter les failles posées par un simple ajout d'octets, les bits de la somme de contrôle sont permutés de façon circulaire vers la droite de 1 bit à chaque itération.
int bsdChecksumFromFile(FILE *fp) /* fp: gestionnaire du fichier d'entree */ { int ch; /* Le dernier caractère lu. */ int checksum = 0; /* La somme de contrôle modulo 2^16. */
while ((ch = getc(fp)) != EOF) { checksum = (checksum >> 1) + ((checksum & 1) << 15); checksum += ch; checksum &= 0xffff; /* ET binaire équivalent à un modulo 2^16 */
return checksum; }
Le code ci-dessous est un fragment de code java qui calcule une somme de contrôle de 8 bits de long. Il ajoute chaque bit du tableau d'entrée après avoir effectué une permutation circulaire de la somme de contrôle. byte checksum(byte[] input) { byte checksum = 0; for (byte cur_byte: input) { checksum = (byte) (((checksum & 0xFF) >> 1) | (checksum << 7)); // Permuation circulaire checksum = (byte) (checksum + cur_byte); // Ajouter le segment suivant
return checksum; }
Explication de l'algorithme comme mentionné ci-dessus, cet algorithme calcule une somme de contrôle en segmentant les données et en ajoutant à chaque segment un accumulateur dont les bits sont permutés de façon circulaire entre chaque sommation. Pour veiller à ce que la somme de contrôle soit sur 4 bits, on applique une opération modulo 2^4 qui est équivalente à un ET bit à bit avec le masque 1111.
Exemple : Somme de contrôle 4-bit avec des segments de 4-bit de long (big-endian)
Entrée: 101110001110 Premier tour : Somme de contrôle: 0000 seg : 1011 a) Permutation circulaire de la somme de contrôle : 0000 → 0000 b) Ajout du segment et modulo : 0000 + 1011 = 1011 → 1011 & 1111 = 1011 Deuxième tour : Somme de contrôle : 1011 seg : 1000 a) Permutation circulaire de la somme de contrôle: 1011 → 1101 b) Ajout du segment et modulo : 1101 + 1000 = 10101 → 10101 & 1111 = 0101 Troisième tour : Somme de contrôle : 0101 seg : 1110 a) Permutation circulaire de la somme de contrôle: 0101 → 1010 b) Ajout du segment et modulo : 1010 + 1110 = 11000 → 11000 & 1111 = 1000 Somme de contrôle finale : 1000
Notes et références
Annexes Articles connexes Somme de contrôle Berkeley Software Distribution Liste de fonctions de hachage
Liens externes Code source de sum dans le dépôt officiel de FreeBSD Page de manuel de GNU sum Page de téléchargement de Coreutils --- find and unpack the newest version of the coreutils package, cf src/sum.c
Catégorie:Somme de contrôle