Le mystère du CRC et du sens de lecture, selon linux

[watchinofoye]

Bonjour les gars (et les filles aussi, je sais que vous êtes là, pas la peine de le nier) !

Après de longues heures à plancher dessus, j'avoue que j'ai les yeux qui brûlent.
Pour les besoins d'un projet professionnel, je dois calculer le CRC d'une trame SHDLC, en utilisant le polynôme x16 + x12 + x5 + 1 (c'est à dire le CRC-16-CCITT), avec une valeur initiale de 0xFFFF.
Comme pour un autre aspect du projet, j'ai été contraint de me plonger dans une partie du code source de linux, j'ai fini par trouver les fichiers .c et .h correspondant au CRC-CCITT. Et j'avoue ne pas avoir pu m'empêcher de hurler intérieurement concernant la méthode de calcul.
Alors j'ai moi aussi eu ma période "je-mets-toutes-les-opérations-sur-une-même-ligne" et pour diverses raisons (question de lisibilité notamment), j'ai fini par arrêter de le faire. Alors est-ce que quelqu'un peut m'expliquer dans quel sens je dois lire ça :

static inline u16 crc_ccitt_byte(u16 crc, const u8 c)
{
	return (crc >> 8) ^ crc_ccitt_table[(crc ^ c) & 0xff];
}

Pour info, voici la fonction "crc_ccitt" qui appelle la fonction précédente :

 Cliquez pour afficher

/**
 *	crc_ccitt - recompute the CRC for the data buffer
 *	@crc: previous CRC value
 *	@buffer: data pointer
 *	@len: number of bytes in the buffer
 */
u16 crc_ccitt(u16 crc, u8 const *buffer, size_t len)
{
	while (len--)
		crc = crc_ccitt_byte(crc, *buffer++);
	return crc;
}

Et pour finir la fameuse "crc_ccitt_table" :

 Cliquez pour afficher

/*
 * This mysterious table is just the CRC of each possible byte. It can be
 * computed using the standard bit-at-a-time methods. The polynomial can
 * be seen in entry 128, 0x8408. This corresponds to x^0 + x^5 + x^12.
 * Add the implicit x^16, and you have the standard CRC-CCITT.
 */
u16 const crc_ccitt_table[256] = {
	0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
	0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
	0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
	0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
	0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
	0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
	0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
	0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
	0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
	0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
	0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
	0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
	0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
	0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
	0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
	0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
	0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
	0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
	0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
	0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
	0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
	0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
	0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
	0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
	0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
	0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
	0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
	0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
	0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
	0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
	0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
	0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
};

Si quelqu'un pouvait m'aider, ce serait franchement la bienvenue parce que là j'en peux plus...
Merci d'avance.
-----

[lou_ibmix_xi]

Mon analyse rapide:
crc_ccitt_table est une "look-up table", technique classique où on calcule à l'avance tous les résultats possibles d'une fonction et on se sert de la variable comme indice du tableau, donc la case 0 est l'évaluation de ton polynôme pour la valeur 0 et ainsi de suite jusqu'à la case 255 qui est le résultat du polynôme sur la valeur 255. Cette technique permet d'optimiser la vitesse d'exécution au détriment de la mémoire.

(crc ^ c) & 0xff

tu fais un xor bits à bits entre le CRC et le caractère, et tu ne gardes que les bits de poids faible, ton résultat est donc compris entre 0 et 255.

crc_ccitt_table[(crc ^ c) & 0xff];

ça tombe bien puisque le résultat tu l'utilises en indice de ton tableau, qui je te le rappelle reviens à calculer ton polynôme.

(crc >> 8)

Tu ne gardes que les 8 bits de poids fort du CRC, mais attention tu transformes le résultats en un octet (autrement dit, tu transformes l'octet de poids fort en poids faible avec des zéros devant, 0xABCD devient 0x00AB)

(crc >> 8) ^ crc_ccitt_table[(crc ^ c) & 0xff];

ou-exclusif entre ces deux résultats intermédiaires...

Comme pour un autre aspect du projet, j'ai été contraint de me plonger dans une partie du code source de linux, j'ai fini par trouver les fichiers .c et .h correspondant au CRC-CCITT.

Quand on commence "à mettre les mains dans le cambouis" d'UNIX, il faut utiliser les outils d'UNIX, un

find . -name "*.c" | xargs grep -i ccitt

dans le dossier des sources du noyau t'aurais peut-être fais gagner du temps pour trouver le fichier concerné...

En espérant avoir éclairé ta lanterne

[watchinofoye]

Je n'ai pas galéré pour trouver ces fichiers, je te rassure.

Ah m..., c'est vrai ! Les parenthèses, prioritaires sur le xor ! >.<

Ben, merci. Finalement, je ne suis pas plus avancé puisque même avec cette table et ces fonctions le CRC ne correspond pas à celui attendu !
Je vais tester un dernier truc et je vous tiens au courant si ça marche ou pas (dans ce dernier cas, je solliciterai sûrement votre aide).

[polo974]

comment est déclaré ton u16?
unsigned est indispensable, pour la taille tu peux la retrouver en faisant un sizeof(u16), mais 2, 4 ou 8 ne devrait pas changer le résultat (à optimiser selon architecture).

comment est appelé la fonction?

crc=crc_ccitt((u16) 0xFFFF, buffer, len);

il ne faut pas oublier l'init...

sinon, s'il y avait un bug là-dessus, ça se saurait...

[A voir en vidéo sur Futura]

[watchinofoye]

C'est le u16 de linux et j'ai bien vérifié que c'était bien un unsigned short int (par contre j'ai râlé en voyant que u32 était défini avec un unsigned int...). Je n'ai pas oublier l'init de 0xFFFF (oui je passe directement la constante).
Ce n'est pas un bug, c'est juste que la doc que j'étudie me donne une trame avec un CRC et que je ne trouve pas le bon alors que j'utilise l'algorithme indiqué. Et j'espérais qu'en utilisant le code de linux j'allais trouver une explication à cette mascarade. Et finalement, je me trouve devant encore plus de WTF...
J'ai même trouvé un code quasi similaire à celui de linux mais dont les valeurs de la table étaient différentes. Et même là, ça ne marche pas.

Comment de cette trame (exemple donné dans la doc et retrouvé dans un programme de test fourni) 05 F9 04 00 on arrive à ce CRC C3 E5, en utilisant le CRC-16-CCITT (big endian (MSB et MSb), Polynôme x16 + x12 + x5 + 1 que je retrouve partout et où il est même mentionné à chaque fois qu'il est "utilisé pour HDLC")) ? Je me dis que le constructeur a fait un truc super tordu mais en même temps je ne vois pas l'intérêt de faire ça. Pour l'instant, je continue à chercher.

Si quelqu'un peut apporter une réponse à cette question, son aide serait la bienvenue.

[Chanur]

Et quelle valeur tu obtiens, pour la trame 05 F9 04 00 ?

[watchinofoye]

Ce site là me donne ces résultats :


Les fonctions de linux, telles quelles, me donnent : 56 BF.
Là c'est avec les fonctions telles quelles, et j'ai remarqué que le fichier appelant la fonction de calcul du CRC effectue un complément à 1 juste après, ce qui me donne... A9 40

L'équivalent (trouvé là) me donne bizarrement deux résultats différents :
27 CB pour l'implémentation loop drive et B9 C3 pour l'implémentation table drive (D8 34 et 46 3C avec le complément à 1, dans le doute...)
Une différence qui me laisse perplexe quant à l'efficacité de ces implémentations.

J'ai essayé de retranscrire les résultats obtenus (j'ai sûrement tenté d'autres choses, tout aussi peu concluantes...). J'ai tenté de changer l'endianness, avant que je ne trouve l'indication du MSB/MSb bien cachée dans la doc.

Je ne sais trop quoi penser de tout ça...
Dans le doute, je considère que la doc et le programme de test donnent le bon résultat et que je dois essayer de faire ce calcul sous toutes les coutures jusqu'à tomber sur la bonne formule... Quoi de mieux pour faire perdre du temps dans un projet qu'une doc mal expliquée, n'est-ce pas ?

[watchinofoye]

Après avoir apporté une petite correction de types, j'ai enfin réussi à obtenir des résultats équivalents pour la version trouvée sur ABC électronique : 27 CB (D8 34 avec le complément à 1).

[Chanur]

Comment de cette trame (exemple donné dans la doc et retrouvé dans un programme de test fourni) 05 F9 04 00 on arrive à ce CRC C3 E5

en envoyant les octets en ordre inverse (00 04 F9 05),t en faisant un complément à 1 sur le résultat et en prenant en ordre inverse les octets du résultat !

[watchinofoye]

Intéressant. Une démonstration ne serait pas de refus (j'essaye mais ça ne me donne rien de concluant, je m'y prends peut-être mal).

[Chanur]

Mon code source :

#include <stdio.h>
#include <stdlib.h>

/*
 * This mysterious table is just the CRC of each possible byte. It can be
 * computed using the standard bit-at-a-time methods. The polynomial can
 * be seen in entry 128, 0x8408. This corresponds to x^0 + x^5 + x^12.
 * Add the implicit x^16, and you have the standard CRC-CCITT.
 */
unsigned short crc_ccitt_table[256] =
    {
    0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
    0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
    0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
    0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
    0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
    0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
    0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
    0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
    0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
    0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
    0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
    0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
    0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
    0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
    0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
    0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
    0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
    0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
    0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
    0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
    0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
    0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
    0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
    0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
    0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
    0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
    0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
    0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
    0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
    0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
    0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
    0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
    };

unsigned short crc_ccitt_byte(unsigned short crc, const unsigned char c)
    {
    return (crc >> 8) ^ crc_ccitt_table[(crc ^ c) & 0xff];
    }

/**
 *    crc_ccitt - recompute the CRC for the data buffer
 *    @crc: previous CRC value
 *    @buffer: data pointer
 *    @len: number of bytes in the buffer
 */
unsigned short crc_ccitt (unsigned short crc, unsigned char const *buffer, size_t len)
    {
    while (len--)
        crc = crc_ccitt_byte(crc, *buffer++);
    return crc ^ 0xffff;
    }

int main()
    {
    union
        {
        unsigned int valeur_numerique;
        unsigned char chaine[4];
        } trame;
    trame.valeur_numerique = 0x05F90400;
    printf ("0x%08x => 0x%04x\n", trame.valeur_numerique, crc_ccitt (0xffff, trame.chaine, 4));
    trame.valeur_numerique = 0x0004F905;
    printf ("0x%08x => 0x%04x\n", trame.valeur_numerique, crc_ccitt (0xffff, trame.chaine, 4));
    return 0;
    }

[watchinofoye]

Han ! O.O
Grâce à toi j'ai pu trouver ce qui clochait dans mon algo : la taille que je passais était trop longue de un p**ain d'octet.
J'ai pu tester avec l'exemple de trame de réponse, ça correspond aussi.

C'est nickel ! Génial ! Merci ! Je jubile ! Tu m'as libéré ! \o/

Petite remarque : seul la table issue de linux fonctionne pour le coup.

[Chanur]

Petite remarque : seul la table issue de linux fonctionne pour le coup.

J'imagine qu'il doit y avoir le même genre de bricolage à faire pour les autres : changer l'ordre des octets ou des bits ou faire des compléments à 1 ou changer la valeur initiale, etc ...

[watchinofoye]

Peut-être. En tout cas tant que j'ai un calcul de CRC opérationnel, c'est parfait !

Encore merci, Chanur