Il existe de nombreuses options pour calculer la somme de contrôle CRC sur Internet. Mais qu'est-ce qu'une somme de contrôle exactement et pourquoi est-elle calculée de cette manière ? Trouvons-le.
Instructions
Étape 1
Commençons par un peu de théorie. Alors, qu'est-ce que le CRC exactement ? En bref, c'est l'une des variétés de calcul de somme de contrôle. La somme de contrôle est une méthode de vérification de l'intégrité des informations reçues du côté récepteur lors de la transmission sur les canaux de communication. Par exemple, l'une des vérifications les plus simples consiste à utiliser le bit de parité. C'est à ce moment que tous les bits du message transmis sont additionnés, et si la somme s'avère être paire, alors 0 est ajouté à la fin du message, s'il est impair, alors 1. A la réception, la somme des les bits de message sont également comptés et comparés au bit de parité reçu. S'ils diffèrent, des erreurs se sont produites lors de la transmission et les informations transmises ont été déformées.
Mais cette méthode de détection de la présence d'erreurs est très peu informative et ne fonctionne pas toujours, car si plusieurs bits du message sont déformés, la parité de la somme peut ne pas changer. Par conséquent, il existe de nombreux autres contrôles « avancés », y compris le CRC.
En fait, le CRC n'est pas une somme, mais le résultat de la division d'une certaine quantité d'informations (message d'information) par une constante, ou plutôt, le reste de la division d'un message par une constante. Cependant, le CRC est aussi historiquement appelé « somme de contrôle ». Chaque bit du message contribue à la valeur CRC. C'est-à-dire que si au moins un bit du message d'origine change pendant la transmission, la somme de contrôle changera également, et de manière significative. C'est un gros plus d'un tel contrôle, car il vous permet de déterminer sans ambiguïté si le message d'origine a été déformé lors de la transmission ou non.
Étape 2
Avant de commencer à calculer le CRC, un peu plus de théorie est nécessaire.
Quel est le message d'origine doit être clair. C'est une séquence contiguë de bits de longueur arbitraire.
Quelle est la constante par laquelle nous devrions diviser le message original ? Ce nombre est également de n'importe quelle longueur, mais généralement des multiples de 1 octet sont utilisés - 8, 16 et 32 bits. C'est juste plus facile de compter, car les ordinateurs fonctionnent avec des octets, pas avec des bits.
La constante diviseur est généralement écrite comme un polynôme (polynôme) comme ceci: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Ici, le degré du nombre "x" signifie la position du bit un dans le nombre, à partir de zéro, et le bit le plus significatif indique le degré du polynôme et est ignoré lors de l'interprétation du nombre. C'est-à-dire que le nombre précédemment écrit n'est rien de plus que (1) 00000111 en binaire, ou 7 en décimal. Entre parenthèses, j'ai indiqué le chiffre implicite le plus significatif du nombre.
Voici un autre exemple: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Habituellement, certains polynômes standard sont utilisés pour différents types de CRC.
Étape 3
Alors, comment calculez-vous la somme de contrôle? Il existe une méthode de base - diviser un message en polynôme "de front" - et ses modifications afin de réduire le nombre de calculs et, par conséquent, d'accélérer le calcul du CRC. Nous allons voir la méthode de base.
En général, la division d'un nombre par un polynôme s'effectue selon l'algorithme suivant:
1) un tableau (registre) est créé, rempli de zéros, de longueur égale à la longueur de la largeur du polynôme;
2) le message d'origine est complété par des zéros dans les bits les moins significatifs, en une quantité égale au nombre de bits du polynôme;
3) un bit de poids fort du message est entré dans le bit de poids faible du registre, et un bit est déplacé du bit de poids fort du registre;
4) si le bit étendu est égal à "1", alors les bits sont inversés (opération XOR, OU exclusif) dans les bits de registre qui correspondent à ceux du polynôme;
5) s'il y a encore des bits dans le message, passez à l'étape 3);
6) lorsque tous les bits du message sont entrés dans le registre et ont été traités par cet algorithme, le reste de la division reste dans le registre, qui est la somme de contrôle CRC.
La figure illustre la division de la séquence de bits d'origine par le nombre (1) 00000111, ou le polynôme x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Étape 4
Il reste quelques touches supplémentaires. Comme vous l'avez peut-être remarqué, le message peut être divisé par n'importe quel nombre. Comment le choisir ? Il existe un certain nombre de polynômes standard qui sont utilisés pour calculer le CRC. Par exemple, pour CRC32, il peut s'agir de 0x04C11DB7 et pour CRC16, il peut s'agir de 0x8005.
De plus, dans le registre au début du calcul, vous pouvez écrire non pas des zéros, mais un autre nombre.
De plus, pendant les calculs, juste avant d'émettre la somme de contrôle CRC finale, ils peuvent être divisés par un autre nombre.
Et la dernière chose. Les octets du message lors de l'écriture dans le registre peuvent être placés comme le bit le plus significatif "en avant", et vice versa, le moins significatif.
Étape 5
Sur la base de tout ce qui précède, écrivons une fonction. NET de base qui calcule la somme de contrôle CRC en prenant un certain nombre de paramètres que j'ai décrits ci-dessus et en renvoyant la valeur CRC sous la forme d'un nombre non signé de 32 bits.
Public Shared Function GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Facultatif ByVal width As InitReg = 32, Facultatif ByVal initReg As UInteger = & HFFFFFFFFUI, Facultatif ByVal finalXor As UInteger = & HFFFFFFFFUI, Facultatif ByVal reverseBytes, Facultatif Boolean ByVal reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width / 8
'Compléter la largeur du message par des zéros (calcul en octets):
ReDim Conserver les octets (bytes. Length - 1 + widthInBytes)
'Créez une petite file d'attente à partir du message:
Dim msgFifo en tant que nouvelle file d'attente (de booléen) (bytes. Count * 8 - 1)
Pour chaque b Comme octet En octets
Dim ba comme nouveau BitArray ({b})
Si reverseBytes Alors
Pour i en tant qu'entier = 0 à 7
msgFifo. Enqueue (ba (i))
Prochain
Autre
Pour i en tant qu'entier = 7 à 0 pas -1
msgFifo. Enqueue (ba (i))
Prochain
Fin si
Prochain
'Crée une file d'attente à partir des bits de remplissage initiaux du registre:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (De b As Byte In initBytes Take widthInBytes). Reverse
Dim initFifo en tant que nouvelle file d'attente (de booléen) (largeur - 1)
Pour chaque b comme octet dans initBytesReversed
Dim ba comme nouveau BitArray ({b})
Si non reverseBytes Alors
Pour i en tant qu'entier = 0 à 7
initFifo. Enqueue (ba (i))
Prochain
Autre
Pour i en tant qu'entier = 7 à 0 pas -1
initFifo. Enqueue (ba (i))
Prochain
Fin si
Prochain
'Shift et XOR:
Registre Dim As UInteger = 0 'remplit le registre de bits de largeur avec des zéros.
Faire pendant que msgFifo. Count> 0
Dim poppedBit As Integer = CInt (registre >> (largeur - 1)) Et 1' défini avant le registre à décalage.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Si initFifo. Count> 0 Alors
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xou b
Fin si
s'inscrire = s'inscrire << 1
registre = registre ou shiftedBit
Si poppedBit = 1 Alors
registre = registre Xou poly
Fin si
Boucle
'Conversions finales:
Dim crc As UInteger = register 'Le registre contient le reste de la division == somme de contrôle.
Si reverseCrc Alors
crc = refléter (crc, largeur)
Fin si
crc = crc Xor finalXor
crc = crc Et (& HFFFFFFFFUI >> (32 - largeur)) 'masque les bits les moins significatifs.
Retour crc
Fonction de fin
