Comment une somme de contrôle CRC32 est-elle calculée?

102

Peut-être que je ne le vois tout simplement pas, mais CRC32 semble soit inutilement compliqué, soit insuffisamment expliqué partout où je pourrais trouver sur le Web.

Je comprends que c'est le reste d'une division arithmétique non basée sur le report de la valeur du message, divisé par le polynôme (générateur), mais l'implémentation réelle de celui-ci m'échappe.

J'ai lu un guide indolore sur les algorithmes de détection d'erreur CRC , et je dois dire que ce n'était pas indolore. Cela passe assez bien en revue la théorie, mais l'auteur n'arrive jamais à un simple «c'est ça». Il dit quels sont les paramètres de l'algorithme CRC32 standard, mais il néglige d'exposer clairement comment vous y parvenez.

La partie qui me comprend, c'est quand il dit "c'est ça" et ajoute ensuite, "oh au fait, ça peut être inversé ou démarré avec des conditions initiales différentes", et ne donne pas une réponse claire de la manière finale de calculer une somme de contrôle CRC32 compte tenu de tous les changements qu'il vient d'ajouter.

  • Existe-t-il une explication plus simple de la façon dont le CRC32 est calculé?

J'ai essayé de coder en C comment la table est formée:

for (i = 0; i < 256; i++)
{
    temp = i;

    for (j = 0; j < 8; j++)
    {
        if (temp & 1)
        {
            temp >>= 1;
            temp ^= 0xEDB88320;
        }
        else {temp >>= 1;}
    }
    testcrc[i] = temp;
}

mais cela semble générer des valeurs incompatibles avec les valeurs que j'ai trouvées ailleurs sur Internet. Je pourrais utiliser les valeurs que j'ai trouvées en ligne, mais je veux comprendre comment elles ont été créées.

Toute aide pour clarifier ces chiffres incroyablement déroutants serait très appréciée.

aquanar
la source
9
Votre code pour générer la table CRC32 semble être correct. Votre polynôme CRC32 lsbit-first ( inversé ) de 0xEDB88320peut également être écrit msbit-first ( normal ) comme 0x04C11DB7. Les valeurs de table que vous avez trouvées ailleurs ont-elles été générées en utilisant le même polynôme CRC?
jschmier
1
@jschmier salut, j'ai l'impression d'être un pas derrière ce gars qui pose les questions? stackoverflow.com/questions/62168128/…
bluejayke
Si quelqu'un d'autre est curieux de lire "Un guide indolore pour les algorithmes de détection d'erreur CRC" lié à ci-dessus, cette URL d'origine est jetée mais Google en a facilement trouvé plusieurs copies, y compris celle-ci: zlib.net/crc_v3.txt
Stéphane

Réponses:

114

Le polynôme pour CRC32 est:

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

Ou en hexadécimal et binaire:

0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111

Le terme le plus élevé (x 32 ) n'est généralement pas écrit explicitement, il peut donc être représenté en hexadécimal comme

0x 04 C1 1D B7

N'hésitez pas à compter les 1 et les 0, mais vous constaterez qu'ils correspondent au polynôme, où 1 est le bit 0 (ou le premier bit) et le xbit 1 (ou le deuxième bit).

Pourquoi ce polynôme? Parce qu'il doit y avoir un polynôme donné standard et que le standard a été défini par IEEE 802.3. Il est également extrêmement difficile de trouver un polynôme qui détecte efficacement différentes erreurs sur les bits.

Vous pouvez considérer le CRC-32 comme une série d '«arithmétique binaire sans portage», ou fondamentalement «opérations XOR et décalage». C'est ce qu'on appelle techniquement l'arithmétique polynomiale.

Pour mieux le comprendre, pensez à cette multiplication:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Si nous supposons que x est la base 2, nous obtenons:

x^7 + x^3 + x^2 + x^1 + x^0

Pourquoi? Parce que 3x ^ 3 est 11x ^ 11 (mais nous n'avons besoin que de 1 ou 0 pré-chiffre), nous reportons donc:

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

Mais les mathématiciens ont changé les règles pour que ce soit le mod 2. Donc, fondamentalement, tout polynôme binaire mod 2 est juste une addition sans report ni XOR. Donc, notre équation originale ressemble à:

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

Je sais que c'est un acte de foi, mais cela dépasse mes capacités en tant que programmeur en ligne. Si vous êtes un étudiant ou un ingénieur en CS inconditionnel, je mets au défi de décomposer cela. Tout le monde bénéficiera de cette analyse.

Donc, pour élaborer un exemple complet:

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

Maintenant, nous divisons le Message augmenté par le Poly en utilisant l'arithmétique CRC. C'est la même division que précédemment:

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

La division donne un quotient, que nous jetons, et un reste, qui est la somme de contrôle calculée. Cela met fin au calcul. Habituellement, la somme de contrôle est ensuite ajoutée au message et le résultat est transmis. Dans ce cas, la transmission serait: 11010110111110.

Utilisez uniquement un nombre 32 bits comme diviseur et utilisez l'intégralité de votre flux comme dividende. Jetez le quotient et conservez le reste. Tack le reste à la fin de votre message et vous avez un CRC32.

Critique moyenne des gars:

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER
  1. Prenez les 32 premiers bits.
  2. Bits de décalage
  3. Si 32 bits sont inférieurs à DIVISOR, passez à l'étape 2.
  4. XOR 32 bits par DIVISOR. Passez à l'étape 2.

(Notez que le flux doit être divisible par 32 bits ou il doit être complété. Par exemple, un flux ANSI 8 bits devrait être complété. Également à la fin du flux, la division est interrompue.)

ilkkachu
la source
13
+1 pour le "Average Guy Review" à la fin - peut-être envisager de déplacer ce droit vers le haut - une sorte de TL; DR: P
aaronsnoswell
4
@abstractnature N'oubliez pas que nous divisons des polynômes, pas seulement des nombres binaires. Nous ne pouvons pas faire de soustraction "normale" car nous ne pouvons pas "emprunter" $ x ^ n $ à $ x ^ {n + 1} $; ce sont différents types de choses. De plus, puisque les bits ne sont que 0 ou 1, que serait même -1? Vraiment, nous travaillons dans l'anneau des polynômes avec des coefficients dans le champ $ Z / 2Z $, qui n'a que deux éléments, 0 et 1, et où $ 1 + 1 = 0 $. En plaçant les cofficients dans un champ, les polynômes forment alors ce qu'on appelle un domaine euclidien, ce qui permet simplement à ce que nous essayons de faire d'être bien défini en premier lieu.
calavicci
6
Juste pour clarifier le polynôme réel est 100000100110000010001110110110111 = 0x104C11DB7. Le MSB est implicite, mais doit toujours être pris en compte dans une implémentation. Comme il sera toujours défini car le polynôme doit avoir une longueur de 33 bits (le reste peut donc être de 32 bits), certaines personnes omettent le MSB.
Felipe T.
2
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 ... If we assume x is base 2 then we get: x^7 + x^3 + x^2 + x^1 + x^0. Ce n'est pas ainsi que les maths fonctionnent. Les coefficients du polynôme sont mod (2) ou GF (2), les x sont laissés seuls, ce qui donne x ^ 6 + x ^ 5 + x ^ 4 + x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0 (puisque 3 mod (2) = 1). Tack the remainder on the end of your message- techniquement, le reste est soustrait des 0 bits qui ont été ajoutés au message, mais comme il s'agit de maths mod (2), l'addition et la soustraction sont les mêmes que XOR, et les zéro bits XOR avec le reste sont les mêmes comme le reste.
rcgldr
2
@MarcusJ - Why did you append four 0s though?- les algorithmes logiciels pour calculer le crc ajoutent efficacement les 0, même si ce n'est pas apparent. Si vous affichez le calcul CRC en utilisant la division longue main, alors des 0 doivent être ajoutés pour que l'exemple de division apparaisse correctement.
rcgldr
11

Pour IEEE802.3, CRC-32. Considérez le message entier comme un flux de bits série, ajoutez 32 zéros à la fin du message. Ensuite, vous DEVEZ inverser les bits de CHAQUE octet du message et faire un complément à 1 sur les 32 premiers bits. Divisez maintenant par le polynôme CRC-32, 0x104C11DB7. Enfin, vous devez compléter par 1 le reste de 32 bits de cette division en inversant chacun des 4 octets du reste. Cela devient le CRC 32 bits qui est ajouté à la fin du message.

La raison de cette étrange procédure est que les premières implémentations Ethernet sérialiseraient le message un octet à la fois et transmettraient d'abord le bit le moins significatif de chaque octet. Le train de bits série est ensuite passé par un calcul de registre à décalage CRC-32 série, qui a simplement été complété et envoyé sur le fil une fois le message terminé. La raison de compléter les 32 premiers bits du message est que vous n'obteniez pas un CRC tout à zéro même si le message était entièrement à zéro.

Pavlo Bobrek
la source
2
C'est la meilleure réponse ici jusqu'à présent, même si je remplacerais «bit-reverse chacun des 4 octets», par «bit-reverse les 4 octets, en les traitant comme une seule entité», par exemple «abcdefgh ijklmnop qrstuvwx yzABCDEF» par «FEDCBAzy xwvutsrq ponmlkji hgfedcba ». Voir aussi: Tutoriel de hachage CRC-32 - Communauté AutoHotkey .
vafylec
1
salut, quel "message" exact, y faites-vous marche arrière? stackoverflow.com/questions/62168128/…
bluejayke
10

Un CRC est assez simple; vous prenez un polynôme représenté sous forme de bits et de données, et vous divisez le polynôme en données (ou vous représentez les données sous forme de polynôme et faites la même chose). Le reste, qui est compris entre 0 et le polynôme est le CRC. Votre code est un peu difficile à comprendre, en partie parce qu'il est incomplet: temp et testcrc ne sont pas déclarés, donc on ne sait pas ce qui est indexé et combien de données sont exécutées dans l'algorithme.

La façon de comprendre les CRC est d'essayer d'en calculer quelques-uns en utilisant un court morceau de données (16 bits environ) avec un polynôme court - 4 bits, peut-être. Si vous pratiquez de cette façon, vous comprendrez vraiment comment vous pouvez procéder pour le coder.

Si vous le faites fréquemment, un CRC est assez lent à calculer dans un logiciel. Le calcul matériel est beaucoup plus efficace et ne nécessite que quelques portes.

Tourbillon
la source
1
Pour CRC32 ou CRC32b, obtenons-nous une signification de collision de hachage pour deux chaînes différentes
Obtenons
1
salut, je suis un peu confus ce que vous entendez par "diviser les polynômes en données"? stackoverflow.com/questions/62168128/… qu'est-ce que X dans le polynôme représenté par? Dois-je utiliser les autres octets du bloc?
bluejayke
7

En plus du contrôle de redondance cyclique Wikipedia et du calcul des articles CRC , j'ai trouvé un article intitulé Reversing CRC - Theory and Practice * comme une bonne référence.

Il existe essentiellement trois approches pour calculer un CRC: une approche algébrique, une approche orientée bits et une approche basée sur les tables. Dans Reversing CRC - Theory and Practice * , chacun de ces trois algorithmes / approches est expliqué en théorie accompagné dans l'ANNEXE d'une implémentation du CRC32 dans le langage de programmation C.

* PDF Lien
inversant CRC - Théorie et pratique.
HU Berlin Public Report
SAR-PR-2006-05
Mai 2006
Auteurs:
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich

jschmier
la source
salut, pouvez-vous élaborer un peu?
bluejayke
7

J'ai passé un moment à essayer de trouver la réponse à cette question, et j'ai finalement publié un tutoriel sur CRC-32 aujourd'hui: Tutoriel de hachage CRC-32 - AutoHotkey Community

Dans cet exemple, je montre comment calculer le hachage CRC-32 pour la chaîne ASCII 'abc':

calculate the CRC-32 hash for the ASCII string 'abc':

inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7

011000010110001001100011
reverse bits in each byte:
100001100100011011000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR the first 4 bytes with 0xFFFFFFFF:
01111001101110010011100111111111000000000000000000000000

'CRC division':
01111001101110010011100111111111000000000000000000000000
 100000100110000010001110110110111
 ---------------------------------
  111000100010010111111010010010110
  100000100110000010001110110110111
  ---------------------------------
   110000001000101011101001001000010
   100000100110000010001110110110111
   ---------------------------------
    100001011101010011001111111101010
    100000100110000010001110110110111
    ---------------------------------
         111101101000100000100101110100000
         100000100110000010001110110110111
         ---------------------------------
          111010011101000101010110000101110
          100000100110000010001110110110111
          ---------------------------------
           110101110110001110110001100110010
           100000100110000010001110110110111
           ---------------------------------
            101010100000011001111110100001010
            100000100110000010001110110110111
            ---------------------------------
              101000011001101111000001011110100
              100000100110000010001110110110111
              ---------------------------------
                100011111110110100111110100001100
                100000100110000010001110110110111
                ---------------------------------
                    110110001101101100000101110110000
                    100000100110000010001110110110111
                    ---------------------------------
                     101101010111011100010110000001110
                     100000100110000010001110110110111
                     ---------------------------------
                       110111000101111001100011011100100
                       100000100110000010001110110110111
                       ---------------------------------
                        10111100011111011101101101010011

remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53
XOR the remainder with 0xFFFFFFFF:
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
0b00110101001001000100000111000010 = 0x352441C2

thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2
vafylec
la source
1
Si vous voulez plus de vitesse, il y avait une méthode élaborée par certains ingénieurs d'Intel vers 2006 en utilisant généralement 4 ou 8 octets de la largeur du bus de données de la machine simultanément. Article académique: static.aminer.org/pdf/PDF/000/432/446/… Projet sur Sourceforge: sourceforge.net/projects/slicing-by-8 Page crc générale: create.stephan-brumme.com/crc32
Alan Corey
1
Salut merci a l'air génial, mais comment obtenez-vous exactement la valeur polynomiale? que représente exactement X? Et quand il dit x ^ 32, est-ce x à la puissance de 32, ou l'opérateur au niveau du bit ^? stackoverflow.com/questions/62168128/…
bluejayke
1

Afin de réduire crc32 à prendre le rappel, vous devez:

  1. Inverser les bits sur chaque octet
  2. x ou les quatre premiers octets avec 0xFF (ceci pour éviter les erreurs sur les 0 en tête)
  3. Ajouter un padding à la fin (c'est pour faire participer les 4 derniers octets au hachage)
  4. Calculer le rappel
  5. Inversez à nouveau les bits
  6. x ou le résultat à nouveau.

Dans le code c'est:


func CRC32 (file []byte) uint32 {
    for i , v := range(file) {
        file[i] = bits.Reverse8(v)
    }
    for i := 0; i < 4; i++ {
        file[i] ^= 0xFF
    }

    // Add padding
    file = append(file, []byte{0, 0, 0, 0}...)
    newReminder := bits.Reverse32(reminderIEEE(file))

    return newReminder ^ 0xFFFFFFFF
}

où reminderIEEE est le pur rappel sur GF (2) [x]

Gabriel Furstenheim
la source
1
Im ayant un peu (jeu de mots) de la difficulté à comprendre cela? stackoverflow.com/questions/62168128/…
bluejayke
1
hé @bluejayke, consultez cette bibliothèque github.com/furstenheim/sparse_crc32/blob/master/main.go elle implémente le crc32 pour les fichiers épars, vous pouvez y voir les détails les plus fins du calcul. Il n'est pas optimisé, il est donc plus facile à suivre que les implémentations normales. Il se peut que vous ne compreniez pas la partie GF (2) [x]. Fondamentalement, x ^ 3 + x signifie 1010, x ^ 4 + x + 1 signifie 10011. Ensuite, vous devez effectuer une division, par exemple x ^ 3 + x est x * (x ^ 2 + 1). donc le rappel de x ^ 3 + x sur x est 0, mais sur x ^ 2 ce serait x ^ 2 * x + x, c'est-à-dire que le rappel serait x.
Gabriel Furstenheim
1
@bluejayke and reminderIEEE signifie rappel contre un polynôme bien connu, le polynôme IEEE
Gabriel Furstenheim
salut encore, merci pour votre réponse. J'essaie juste de comprendre (à des fins javascript) ce que représente le "x" dans le polynôme. "X" est-il une sorte de mot de code pour quelque chose qui me manque ici? Il y a beaucoup de termes qui me déroutent ici, je n'ai jamais entendu parler de CRC32 auparavant, et même après une recherche, je ne pouvais pas le trouver réellement expliqué. Pour un PNG par exemple, il dit que je dois prendre le "CRC pour chaque morceau", est-ce que cela signifie "pour toutes les données du morceau"? Mais comment puis-je le «brancher» sur le polynôme? Que représente "x"? Aussi quand il dit x ^ 32, c'est comme Math.pow (x, 32) ou le
bitwise
1
Salut @bluejayke, x est une abstraction pour faciliter les calculs. Il ne devrait pas être remplacé par quoi que ce soit. x ^ 2 Je veux dire x * x, en tant que multiplication formelle. Ici chrisballance.com/wp-content/uploads/2015/10/CRC-Primer.html vous pouvez trouver une belle explication de cette division. Ce que j'ai essayé avec ma réponse était de combler le vide entre la division (dans ce lien) et le calcul réel
Gabriel Furstenheim