CRC32, Question de calcul

Bonjour,

Je tentais de comprendre ce qu'est le calcul d'un crc32 mais je n'arrive pas aux même résultats qu'un autre site...

Séquence à "checksummer"(hex) : E2D376D023BD173
Polynome(décimal) : 1378484732
Polynome(hex) : 522A01FC

Puisque le bit le plus significatif du polynome est 2^30, je décale vers la gauche de 30 bits la séquence puis je divise avec la "division modulo 2".

Cependant...

J'arrive à, en décimal, 707916420 comme valeur de CRC32.
J'ai consigné la démarche du calcul, fait à la main... ici

Or, j'ai voulu me vérifier et ai fait le même calcul avec un calculateur en ligne... le résultat donne 672253872 selon ce calculateur

Quelqu'un pourrait-il me dire ce que je fais de mauvais? J'ai ré-essayé deux fois la même chose et vraiment j'arrive toujours au même résultat...

Aidez-moi svp.

Array

Ta division de polynome a l'air correcte.

Pour ton calculateur de CRC "online", il faut faire attention au sens de lecture des données.

Habituellement le premier octet des données (le plus à gauche) représente les coefficients de polynome les plus faible. Plus on avance dans les données, plus les coefficients augmentent. Cela permet de faire le calcul au fur et a mesure de la lecture des donnés.

Oh... je crois avoir découvert quelque chose...
Est-il vrai que le 32ème bit dans un crc32 doit toujours être 1? Pourquoi est-ce ainsi?
Ça voudrais dire qu'on aurait 33 bits au total dans le polynome... non?

Citation:

---

Envoyé par Array

Oh... je crois avoir découvert quelque chose...
Est-il vrai que le 32ème bit dans un crc32 doit toujours être 1? Pourquoi est-ce ainsi?
Ça voudrais dire qu'on aurait 33 bits au total dans le polynome... non?

---

Le polynome d'un CRC32 est de degré... 32. On à donc 33 coefficients dans ce polynome (du terme x^0 au terme x^32). Si on veut représenter le polynome diviseur, il faut effectivement 33 bits.

Cela dit, durant les calculs, on ne s'intéresse qu'au reste de la division. Ce reste est forcément de degré inférieur à 32. On n'a donc besoin que de 32 bits pour représenter le reste.

Pourquoi le 33 ème bit doit absolumenet être 1? Si c'est le cas... alors il y a possibilité d'un "remainder" plus grand que 2^32-1.

Par exemple si j'ai un polynome égal à x^34-1, alors je pourrais avoir un remainder égal à x^34-2 ce n'est pas impossible si je considère l'arithmétique fait comme une division bien entendu.

Citation:

---

Envoyé par Array

Pourquoi le 33 ème bit doit absolumenet être 1? Si c'est le cas... alors il y a possibilité d'un "remainder" plus grand que 2^32-1.

Par exemple si j'ai un polynome égal à x^34-1, alors je pourrais avoir un remainder égal à x^34-2 ce n'est pas impossible si je considère l'arithmétique fait comme une division bien entendu.

---

Non, le degré du reste est forcément strictement inférieur au degré du diviseur.

P(x) = Quotient(x)*Diviseur(x) + Reste(x)

Sinon, on pourrait rediviser le reste par le diviseur. Par exemple:

Reste(x) = a.x^2 + b.x + c
Diviseur(x) = q.x^2

:arrow: Reste(x) = (a/q)*Diviseur(x) + b.x + c

Oui effectivement je l'admet. Mais cette propriété est présente uniquement parce que, en arithmétique modulo 2, 1101 n'est pas plus grand ni plus petit que 1001 par exemple (autrement dit, parce que l'on ignore les "carry").

Merci beaucoup!

Citation:

---

Envoyé par Array

Oui effectivement je l'admet. Mais cette propriété est présente uniquement parce que, en arithmétique modulo 2, 1101 n'est pas plus grand ni plus petit que 1001 par exemple (autrement dit, parce que l'on ignore les "carry").

---

C'est vrai pour tous les polynomes, qu'on soit dans R (réels) ou Z/nZ. Le reste est toujours d'un degré *strictement* inférieur au diviseur.

Même dans le cas extrême où l'on divise par un polynome de degré 0 (=une constante): dans ce cas le reste est le polynome nul, et le polynome nul à un degré inférieur à 0 (usuellement -infini).

Quoi qu'il en soit, calculer un CRC revient a calculer le reste d'une division de polynome binaire (i.e dans le corps Z/2Z). Dans ce corps, la multiplication par "x" est un décalage de 1 bit. L'addition et la soustraction est un "ou exclusif" (XOR).

Par exemple, calculer le CRC 32bits sur le message "0xFF" revient à effectuer le calcul suivant:

  CRC( 0xFF (hexa) )
= CRC( 11111111 (binaire) )
= CRC( 1.x^7 + 1.x^6 + 1.x^5 + 1.x^4 + 1.x^3 + 1.x^2 + 1.x^1 + 1.x^0 )

= (x^7+x^6+x^5+x^4+x^3+x^2+x^1+x^0) * x^32  modulo POLYCRC(x)
= (x^39+x^38+x^37+x^36+x^35+x^34+x^33+x^32) modulo POLYCRC(x)

avec le polynome CRC32 habituel

POLYCRC(x) = x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^+1

on obtient:

  CRC( 0xFF (hexa) )
= x^31+x^29+x^28+x^24+x^23+x^22+x^21+x^20+x^18+x^17+x^16+x^14+x^7+x^5+x^4+x^2
= 10110001111101110100000010110100 (binaire)
= B1F740B4 (hexa)

En pratique, on ne fait pas la division sur le polynome complet du message. On met à jour le CRC a chaque bit du message.

Code:

---

1 2 3 4

CRC(x)=0 Pour chaque bit "b" du message CRC(x) = (CRC(x) * x^1 + b*x^32) modulo POLYCRC(x) Fin pour

---

ATTENTION: Pour le calcul du "vrai" CRC32, on initialise le CRC avec des bits à "1", et au final on inverse tous les bits. Cette modification permet de prendre en compte les "zeros" en début/fin de message.

Code:

---

1 2 3 4 5

CRC(x) = x^31 + ... + x^1 + x^0 Pour chaque bit "b" du message CRC(x) = (CRC(x) * x^1 + b*x^32) modulo POLYCRC(x) Fin pour CRC(x) = CRC(x) - (x^31 + ... + x^1 + x^0)

---

Citation:

---

Envoyé par pseudocode

C'est vrai pour tous les polynomes, qu'on soit dans R (réels) ou Z/nZ. Le reste est toujours d'un degré *strictement* inférieur au diviseur.

Même dans le cas extrême où l'on divise par un polynome de degré 0 (=une constante): dans ce cas le reste est le polynome nul, et le polynome nul à un degré inférieur à 0 (usuellement -infini).

---

Oui effectivement ... je m'excuse. Moment d'égarement...
Merci bcp pour les explications.

Bonjour,

Je suis automaticien et on me demande de développer un fonction de messagerie et d'intégrer un mécanisme CRC32 afin de faire du contrôle d'intégrité. Je me documente depuis un certain temps et je n'arrive pas bien à comprendre.
Est-ce que le valeur du polynôme est fixée par une "norme" ou bien on peut le choisir ?

Citation:

---

Envoyé par PavillonNoir

Bonjour,

Je suis automaticien et on me demande de développer un fonction de messagerie et d'intégrer un mécanisme CRC32 afin de faire du contrôle d'intégrité. Je me documente depuis un certain temps et je n'arrive pas bien à comprendre.
Est-ce que le valeur du polynôme est fixée par une "norme" ou bien on peut le choisir ?

---

Le terme "CRC32" fait usuellement référence à un polynome bien particulier. J'ai donné un lien un peu plus haut avec une liste des polynomes couramment utilisés: http://en.wikipedia.org/wiki/Cyclic_...ndardized_CRCs