Somme de contrôle BSD
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[modifier | modifier le code]
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[modifier | modifier le code]
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[modifier | modifier le code]
Annexes[modifier | modifier le code]
Articles connexes[modifier | modifier le code]
Liens externes[modifier | modifier le code]
- 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
