calculo - crc32 function

¿Cómo se calcula una suma de comprobación CRC32? (5)

Tal vez simplemente no lo estoy viendo, pero CRC32 parece innecesariamente complicado o insuficientemente explicado en cualquier lugar que pueda encontrar en la web.

Entiendo que es el resto de una división aritmética no basada en el acarreo del valor del mensaje, dividido por el polinomio (generador), pero la implementación real del mismo se me escapa.

He leído Una guía sin dolor para los algoritmos de detección de errores CRC , y debo decir que no fue indoloro. Repasa bien la teoría, pero el autor nunca llega a un simple "esto es". Él dice cuáles son los parámetros del algoritmo CRC32 estándar, pero no explica con claridad cómo se llega a él.

La parte que me atrapa es cuando dice "esto es" y luego agrega: "por cierto, puede invertirse o empezarse con diferentes condiciones iniciales", y no da una respuesta clara de cuál es el camino final de calcular una suma de comprobación CRC32 dados todos los cambios que acaba de agregar.

¿Hay una explicación más simple de cómo se calcula CRC32?

Intenté codificar en C cómo se forma la tabla:

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; }

pero esto parece generar valores inconsistentes con los valores que he encontrado en otras partes de Internet. Podría usar los valores que encontré en línea, pero quiero entender cómo fueron creados.

Cualquier ayuda para aclarar estos números increíblemente confusos sería muy apreciada.

Además de la comprobación de redundancia cíclica de Wikipedia y la computación de artículos de CRC , encontré un documento titulado Revertir CRC - Teoría y práctica ^* para que sea una buena referencia.

Existen esencialmente tres enfoques para calcular un CRC: un enfoque algebraico, un enfoque orientado a bits y un enfoque basado en tablas. En Reversing CRC - Theory and Practice ^* , cada uno de estos tres algoritmos / enfoques se explica en teoría acompañado en el APÉNDICE por una implementación para el CRC32 en el lenguaje de programación C.

^{* Enlace PDF} ^{Invertir CRC - Teoría y práctica.} ^{HU Berlin Public Report} ^{SAR-PR-2006-05} ^{Mayo de 2006} ^Autores: ^{Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich}

El polinomio para CRC32 es:

0x 04 C1 1D B7
x ²⁶ + x ²³ + x ²² + x ¹⁶ + x ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ² + x + 1

que funciona para estar en binario:

100 1100 0001 0001 1101 1011 0111

Siéntase libre de contar los 1s y 0s, pero encontrará que coinciden con el polinomio, donde 1 es el bit 0 (o el primer bit) x es el bit 1 (o el segundo bit).

¿Por qué este polinomio? Porque es necesario que haya un polinomio estándar dado y el estándar fue establecido por IEEE 802.3. También es extremadamente difícil encontrar un polinomio que detecte diferentes errores de bit de manera efectiva.

Puede pensar en el CRC-32 como una serie de "Aritmética binaria sin portadores", o básicamente "operaciones XOR y desplazamiento". Esto se llama técnicamente aritmética polinomial.

CRC primer, Capítulo 5

Para entenderlo mejor, piense en esta multiplicación:

(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 suponemos que x es la base 2, obtenemos:

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

CRC primer Chp.5

¿Por qué? Porque 3x ^ 3 es 11x ^ 11 (pero solo necesitamos 1 o 0 dígito previo) así que llevamos:

=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

Pero los matemáticos cambiaron las reglas para que fuera mod 2. Así que, básicamente, cualquier mod 2 polinomial binario es solo una adición sin carry o XOR. Entonces nuestra ecuación original se ve así:

=( 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)

Sé que esto es un acto de fe, pero esto está más allá de mi capacidad como programador de líneas. Si eres un hard-core CS-student o ingeniero, desafío desafiarlo. Todos se beneficiarán de este análisis.

Entonces, para resolver un ejemplo completo:

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

Ahora dividimos el Mensaje aumentado por el Poly usando la aritmética de CRC. Esta es la misma división que antes:

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 división produce un cociente, que tiramos, y un resto, que es la suma de control calculada. Esto termina el cálculo. Normalmente, la suma de comprobación se agrega al mensaje y se transmite el resultado. En este caso, la transmisión sería: 11010110111110.

CRC primer, Capítulo 7

Solo usa un número de 32 bits como tu divisor y usa toda tu transmisión como dividendo. Tire el cociente y conserve el resto. Seleccione el resto al final de su mensaje y tiene un CRC32.

Revisión promedio de tipo:

QUOTIENT ---------- DIVISOR ) DIVIDEND = REMAINDER

Tome los primeros 32 bits.
Shift bits
Si 32 bits son menores que DIVISOR, vaya al paso 2.
XOR 32 bits por DIVISOR. Ve al paso 2.

(Tenga en cuenta que la secuencia debe ser divisible por 32 bits o que debe rellenarse. Por ejemplo, se debe rellenar una secuencia ANSI de 8 bits. También al final de la secuencia, la división se detiene).

Para IEEE802.3, CRC-32. Piense en todo el mensaje como un flujo de bits en serie, agregue 32 ceros al final del mensaje. A continuación, DEBE invertir los bits de CADA byte del mensaje y hacer un complemento de 1 los primeros 32 bits. Ahora divida por el polinomio CRC-32, 0x104C11DB7. Finalmente, debe complementar el 1 el resto de 32 bits de esta división, biselar cada uno de los 4 bytes del resto. Esto se convierte en el CRC de 32 bits que se agrega al final del mensaje.

La razón de este procedimiento extraño es que las primeras implementaciones Ethernet serializarían el mensaje un byte a la vez y transmitirían el bit menos significativo de cada byte primero. El flujo de bits en serie luego pasó por un cálculo de registro de desplazamiento en serie CRC-32, que simplemente se complementó y se envió por cable una vez que se completó el mensaje. La razón para complementar los primeros 32 bits del mensaje es para que no obtenga un CRC de cero, incluso si el mensaje fue todo ceros.

Pasé un tiempo tratando de descubrir la respuesta a esta pregunta, y finalmente publiqué un tutorial sobre CRC-32 hoy: tutorial de hash CRC-32 - Comunidad AutoHotkey

En este ejemplo, demuestro cómo calcular el hash CRC-32 para la cadena 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

Un CRC es bastante simple; usted toma un polinomio representado como bits y los datos, y divide el polinomio en los datos (o representa los datos como un polinomio y hace lo mismo). El resto, que está entre 0 y el polinomio es el CRC. Su código es un poco difícil de entender, en parte porque está incompleto: temp y testcrc no están declarados, por lo que no está claro qué se está indexando y cuántos datos se están ejecutando a través del algoritmo.

La forma de entender los CRC es tratar de calcular algunos utilizando un pequeño fragmento de datos (16 bits más o menos) con un polinomio corto, 4 bits, tal vez. Si practicas de esta manera, realmente entenderás cómo puedes codificarlo.

Si lo hace con frecuencia, un CRC es bastante lento para computar en software. El cálculo de hardware es mucho más eficiente y solo requiere unas pocas puertas.