¿CRC32 es aditivo?

En varios lugares he leído que crc32 es aditivo y por lo tanto: CRC (A xor B) = CRC (A) xor CRC (B).

La statement anterior fue refutada por el siguiente código que escribí:

import zlib def crc32(data): return zlib.crc32(data) & 0xffffffff print crc32(chr(ord("A") ^ ord("B"))) print crc32("A") ^ crc32("B") 

Salida del progtwig:

 1259060791 2567524794 

¿Podría alguien proporcionar un código adecuado que pruebe esta teoría o señalarme dónde he fallado?

    El CRC es aditivo en el sentido matemático, ya que el hash del CRC es solo un valor remanente de una división sin carga de todos los datos (tratados como un entero gigante) dividido por la constante polinómica. Usando tu ejemplo, es similar a este tipo de cosas:

    7 mod 5 = 2

    6 mod 5 = 1

    (7 mod 5) + (6 mod 5) = 3

    (7 + 6) mod 5 = 3

    En esa analogía, ‘5’ es nuestro polinomio CRC.

    Aquí hay un ejemplo para jugar (basado en gcc):

     #include  #include  int main(void) { unsigned int crc_a = __builtin_ia32_crc32si( 0, 5); printf( "crc(5) = %08X\n", crc_a ); unsigned int crc_b = __builtin_ia32_crc32si( 0, 7); printf( "crc(7) = %08X\n", crc_b ); unsigned int crc_xor = crc_a ^ crc_b; printf( "crc(5) XOR crc(7) = %08X\n", crc_xor ); unsigned int crc_xor2 = __builtin_ia32_crc32si( 0, 5 ^ 7); printf( "crc(5 XOR 7) = %08X\n", crc_xor2 ); return 0; } 

    La salida es la esperada:

     plxc15034> gcc -mcrc32 -Wall -O3 crctest.c plxc15034> ./a.out crc(5) = A6679B4B crc(7) = 1900B8CA crc(5) XOR crc(7) = BF672381 crc(5 XOR 7) = BF672381 

    Debido a que este código utiliza la instrucción x86 CRC32, solo se ejecutará en un Intel i7 o más reciente. La función intrínseca toma el hash CRC en ejecución como primer parámetro y los nuevos datos se acumulan como segundo parámetro. El valor de retorno es el nuevo CRC en ejecución.

    El valor inicial de CRC en ejecución de 0 en el código anterior es crítico. Al usar cualquier otro valor inicial, entonces el CRC no es “aditivo” en el sentido práctico porque efectivamente ha descartado información sobre el número entero en el que se está dividiendo. Y esto es exactamente lo que está pasando en tu ejemplo. Las funciones CRC nunca inicializan ese valor CRC inicial en cero, pero generalmente -1. La razón es que un CRC inicial de 0 permite que cualquier número de 0 iniciales en los datos simplemente caiga sin cambiar el valor de CRC en ejecución, que permanece en 0. Así que, inicializar el CRC a 0 es matemáticamente correcto, pero a efectos prácticos de cálculo hash, es lo último que querrías.

    El algoritmo CRC-32 se basa en la división polinomial, con algunos pasos adicionales agregados. El rest polinomio puro es aditivo.

    Con eso quiero decir: mod (poly1 + poly2, poly3) = mod (mod (poly1, poly3) + mod (poly2, poly3), poly3)

    El algoritmo CRC-32 se basa en esto, y no es aditivo. Para calcular el CRC-32 de una matriz de bytes m:

    1. XOR los primeros 4 bytes por 0xFFFFFFFF.
    2. Trate los bytes anteriores como potencias polinomiales superiores y trate los bits de orden inferior como potencias polinomiales superiores. Por ejemplo, los bytes 0x01 0x04 serían el polinomio x ^ 15 + x ^ 3.
    3. Multiplica el polinomio por x ^ 32.
    4. Tome el rest de este polinomio dividido por el polinomio CRC-32, 0x104C11DB7. El polinomio restante tiene grado <32.
    5. Trate las potencias inferiores como bits de orden superior. Por ejemplo, el polinomio x ^ 2 sería el entero de 32 bits 0x40000000.
    6. XOR el resultado por 0xFFFFFFFF.

    La operación de rest polinomial puro se encuentra en el paso # 4. Los pasos 1 y 6 hacen que el algoritmo CRC-32 no sea aditivo. Entonces, si deshace el efecto de los pasos # 1 y # 6, entonces puede modificar el algoritmo CRC-32 para que sea aditivo.

    (Ver también: Python CRC-32 woes )

    Si a, b y c son de la misma longitud, CRC (a) xo CRC (b) xor CRC (c) es igual a CRC (a xor b xor c). Volviendo a su formulación original, significa que CRC (a xor b) es igual a CRC (a) xor CRC (b) xor CRC (z), donde z es una secuencia de ceros de la misma longitud que las otras dos secuencias.

    Esto implicaría que cada posición de bit del resultado CRC solo es controlada por la posición de bit equivalente en la entrada. Considera tu ejemplo con B == 0.

    La relación que está describiendo es más probable que sea cierta para algunos algoritmos de sum de comprobación primitiva o aditiva.