Hay muchas opciones para calcular la suma de comprobación CRC en Internet. Pero, ¿qué es exactamente una suma de comprobación y por qué se calcula de esta manera? Vamos a resolverlo.
Instrucciones
Paso 1
Primero, obtengamos un poco de teoría. Entonces, ¿qué es exactamente CRC? En resumen, esta es una de las variedades de cálculo de suma de comprobación. La suma de comprobación es un método para comprobar la integridad de la información recibida en el lado del receptor cuando se transmite por canales de comunicación. Por ejemplo, una de las comprobaciones más sencillas es utilizar el bit de paridad. Aquí es cuando se suman todos los bits del mensaje transmitido, y si la suma resulta ser par, entonces se agrega 0 al final del mensaje, si es impar, entonces 1. Al recibir, la suma de los Los bits de mensaje también se cuentan y se comparan con el bit de paridad recibido. Si difieren, entonces se produjeron errores durante la transmisión y la información transmitida se distorsionó.
Pero este método para detectar la presencia de errores es muy poco informativo y no siempre funciona, porque si varios bits del mensaje están distorsionados, es posible que la paridad de la suma no cambie. Por lo tanto, hay muchas más comprobaciones "avanzadas", incluido el CRC.
De hecho, CRC no es una suma, sino el resultado de dividir una cierta cantidad de información (mensaje de información) por una constante, o mejor dicho, el resto de dividir un mensaje por una constante. Sin embargo, la CRC también se conoce históricamente como una "suma de control". Cada bit del mensaje contribuye al valor CRC. Es decir, si al menos un bit del mensaje original cambia durante la transmisión, la suma de comprobación también cambiará, y de manera significativa. Esta es una gran ventaja de dicha verificación, ya que le permite determinar sin ambigüedades si el mensaje original se distorsionó durante la transmisión o no.
Paso 2
Antes de comenzar a calcular el CRC, se necesita un poco más de teoría.
Cuál es el mensaje original debe quedar claro. Es una secuencia contigua de bits de longitud arbitraria.
¿Cuál es la constante por la que debemos dividir el mensaje original? Este número también tiene cualquier longitud, pero normalmente se utilizan múltiplos de 1 byte: 8, 16 y 32 bits. Es más fácil contar, porque las computadoras trabajan con bytes, no con bits.
La constante del divisor generalmente se escribe como un polinomio (polinomio) como este: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Aquí, el grado del número "x" significa la posición del bit en el número, comenzando desde cero, y el bit más significativo indica el grado del polinomio y se descarta al interpretar el número. Es decir, el número escrito anteriormente no es más que (1) 00000111 en binario o 7 en decimal. Entre paréntesis, indiqué el dígito implícito más significativo del número.
Aquí hay otro ejemplo: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Por lo general, se utilizan algunos polinomios estándar para diferentes tipos de CRC.
Paso 3
Entonces, ¿cómo se calcula la suma de comprobación? Existe un método básico - dividir un mensaje en un polinomio "frontalmente" - y sus modificaciones para reducir el número de cálculos y, en consecuencia, acelerar el cálculo CRC. Veremos el método básico.
En general, la división de un número por un polinomio se realiza de acuerdo con el siguiente algoritmo:
1) se crea una matriz (registro), llena de ceros, de longitud igual a la longitud del ancho del polinomio;
2) el mensaje original se complementa con ceros en los bits menos significativos, en una cantidad igual al número de bits del polinomio;
3) se introduce un bit más significativo del mensaje en el bit menos significativo del registro, y se mueve un bit desde el bit más significativo del registro;
4) si el bit extendido es igual a "1", entonces los bits se invierten (operación XOR, OR exclusivo) en aquellos bits de registro que corresponden a los del polinomio;
5) si todavía hay bits en el mensaje, vaya al paso 3);
6) cuando todos los bits del mensaje ingresaron al registro y fueron procesados por este algoritmo, el resto de la división permanece en el registro, que es la suma de verificación CRC.
La figura ilustra la división de la secuencia de bits original por el número (1) 00000111, o el polinomio x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Paso 4
Quedan un par de toques adicionales. Como habrás notado, el mensaje se puede dividir por cualquier número. ¿Cómo elegirlo? Hay una serie de polinomios estándar que se utilizan para calcular el CRC. Por ejemplo, para CRC32 podría ser 0x04C11DB7 y para CRC16 podría ser 0x8005.
Además, en el registro al comienzo del cálculo, puede escribir no ceros, sino algún otro número.
Además, durante los cálculos, inmediatamente antes de emitir la suma de comprobación CRC final, se pueden dividir por algún otro número.
Y lo ultimo. Los bytes del mensaje al escribir en el registro se pueden colocar como el bit más significativo "hacia adelante", y viceversa, el menos significativo.
Paso 5
Basándonos en todo lo anterior, escribamos una función básica. NET que calcule la suma de comprobación CRC tomando una serie de parámetros que describí anteriormente y devolviendo el valor CRC como un número sin signo de 32 bits.
Función pública compartida GetCrc (ByVal bytes como Byte (), ByVal poly como UInteger, Opcional ByVal ancho como Integer = 32, Opcional ByVal initReg As UInteger = & HFFFFFFFFUI, Opcional ByVal finalX o como UInteger = & HFFFFFFFFUI, Opcional ByVal reverseBytes, Opcional Boolean ByVal reverseCrc As Boolean = True) Como UInteger
Dim widthInBytes As Integer = width / 8
'Complemente el ancho del mensaje con ceros (cálculo en bytes):
ReDim Preservar bytes (bytes. Length - 1 + widthInBytes)
'Crea una cola de bits a partir del mensaje:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Para cada b como byte en bytes
Dim ba como nuevo BitArray ({b})
Si reverseBytes entonces
Para i como entero = 0 a 7
msgFifo. Enqueue (ba (i))
Próximo
Demás
Para i como entero = 7 a 0 Paso -1
msgFifo. Enqueue (ba (i))
Próximo
Terminara si
Próximo
'Cree una cola a partir de los bits de relleno iniciales del registro:
Dim initBytes como byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes). Reverse
Dim initFifo como nueva cola (de booleano) (ancho - 1)
Para cada b como byte en initBytesReversed
Dim ba como nuevo BitArray ({b})
Si no es reverseBytes, entonces
Para i como entero = 0 a 7
initFifo. Enqueue (ba (i))
Próximo
Demás
Para i como entero = 7 a 0 Paso -1
initFifo. Enqueue (ba (i))
Próximo
Terminara si
Próximo
'Shift y XOR:
Dim registro Como UInteger = 0 'llene el registro de ancho de bits con ceros.
Hacer mientras msgFifo. Count> 0
Dim poppedBit As Integer = CInt (registro >> (ancho - 1)) Y 1 'define antes del registro de desplazamiento.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Si initFifo. Count> 0 Entonces
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Terminara si
registrar = registrar << 1
registrar = registrar O shiftedBit
Si poppedBit = 1 Entonces
registrar = registrar Xor poli
Terminara si
Lazo
'Conversiones finales:
Dim crc As UInteger = register 'El registro contiene el resto de la división == suma de comprobación.
Si reverseCrc Entonces
crc = reflejar (crc, ancho)
Terminara si
crc = crc Xor finalXor
crc = crc Y (& HFFFFFFFFUI >> (32 - ancho)) 'enmascaran los bits menos significativos.
Volver crc
Función final
