Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 12 sur 12
  1. #1
    Membre à l'essai Avatar de Array
    Inscrit en
    juillet 2007
    Messages
    210
    Détails du profil
    Informations personnelles :
    Âge : 23

    Informations forums :
    Inscription : juillet 2007
    Messages : 210
    Points : 24
    Points
    24

    Par défaut 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

  2. #2
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    Par défaut

    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre à l'essai Avatar de Array
    Inscrit en
    juillet 2007
    Messages
    210
    Détails du profil
    Informations personnelles :
    Âge : 23

    Informations forums :
    Inscription : juillet 2007
    Messages : 210
    Points : 24
    Points
    24

    Par défaut

    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?

  4. #4
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    Par défaut

    Citation Envoyé par Array Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre à l'essai Avatar de Array
    Inscrit en
    juillet 2007
    Messages
    210
    Détails du profil
    Informations personnelles :
    Âge : 23

    Informations forums :
    Inscription : juillet 2007
    Messages : 210
    Points : 24
    Points
    24

    Par défaut

    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.

  6. #6
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    Par défaut

    Citation Envoyé par Array Voir le message
    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

    Reste(x) = (a/q)*Diviseur(x) + b.x + c
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Membre à l'essai Avatar de Array
    Inscrit en
    juillet 2007
    Messages
    210
    Détails du profil
    Informations personnelles :
    Âge : 23

    Informations forums :
    Inscription : juillet 2007
    Messages : 210
    Points : 24
    Points
    24

    Par défaut

    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!

  8. #8
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    Par défaut

    Citation Envoyé par Array Voir le message
    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).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    Par défaut

    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)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #10
    Membre à l'essai Avatar de Array
    Inscrit en
    juillet 2007
    Messages
    210
    Détails du profil
    Informations personnelles :
    Âge : 23

    Informations forums :
    Inscription : juillet 2007
    Messages : 210
    Points : 24
    Points
    24

    Par défaut

    Citation Envoyé par pseudocode Voir le message
    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.

  11. #11
    Invité de passage
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    novembre 2013
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : Industrie

    Informations forums :
    Inscription : novembre 2013
    Messages : 3
    Points : 0
    Points
    0

    Par défaut

    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 ?

  12. #12
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    Par défaut

    Citation Envoyé par PavillonNoir Voir le message
    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
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •