Является ли CRC32 добавка?

Question

В нескольких местах я читал, что crc32 является аддитивным и так: CRC (A xor B) = CRC (A) xor CRC (B).

Приведенное выше утверждение было опровергнуто следующим кодом, который я написал:

import zlib
def crc32(data):
        return zlib.crc32(data) & 0xffffffff

print crc32(chr(ord("A") ^ ord("B")))
print crc32("A") ^ crc32("B")

Вывод программы:

1259060791
2567524794

Может ли кто-нибудь предоставить правильный код, подтверждающий эту теорию, или указать мне, где я потерпел неудачу?

Answer 1

CRC является аддитивным в математическом смысле, так как хэш CRC - это просто остаток от простого переноса всех данных (рассматриваемых как гигантское целое число), разделенных на полиномиальную константу. Используя ваш пример, это похоже на подобные вещи:

7 мод 5 = 2

6 мод 5 = 1

(7 мод 5) + (6 мод 5) = 3

(7 + 6) мод 5 = 3

В этой аналогии «5» является нашим полиномом CRC.

Вот пример для игры (на основе gcc):

#include <stdio.h>
#include <x86intrin.h>

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

Вывод соответствует ожидаемому:

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

Поскольку этот код использует инструкцию x86 CRC32, он будет работать только на Intel i7 или новее. Встроенная функция принимает текущий хэш CRC в качестве первого параметра, а новые данные накапливаются в качестве второго параметра. Возвращаемое значение - новый запущенный CRC.

Первоначальное значение CRC, равное 0, в приведенном выше коде является критическим. Используя любое другое начальное значение, CRC не является «аддитивным» в практическом смысле, потому что вы фактически выбросили информацию о целом числе, на которое делите. И это именно то, что происходит в вашем примере. Функции CRC никогда не инициализируют это начальное значение CRC равным нулю, но обычно -1. Причина в том, что начальный CRC, равный 0, позволяет любому количеству ведущих 0 в данных просто проваливаться без изменения значения текущего CRC, которое остается равным 0. Таким образом, инициализация CRC в 0 является математически обоснованной, но для практических целей расчета хэш, это последнее, что вы хотели бы.

Answer 2

Если a, b и c имеют одинаковую длину, CRC (a) xor CRC (b) xor CRC (c) равно CRC (a xor b xor c).Возвращаясь к вашей первоначальной формулировке, это означает, что CRC (a xor b) равен CRC (a) xor CRC (b) xor CRC (z), где z - последовательность нулей такой же длины, что и две другие последовательности.

Answer 3

Алгоритм CRC-32 основан на полиномиальном делении с добавлением некоторых дополнительных шагов. Чистый полиномиальный остаток является аддитивным.

Я имею в виду: mod (poly1 + poly2, poly3) = mod (mod (poly1, poly3) + mod (poly2, poly3), poly3)

Алгоритм CRC-32 основан на этом и не является аддитивным. Для вычисления CRC-32 байтового массива m:

1. XOR первые 4 байта по 0xFFFFFFFF.
2. Рассматривайте более ранние байты как более высокие степени полинома и обрабатывайте биты более низкого порядка как более высокие степени полинома. Например, байты 0x01 0x04 будут полиномом x ^ 15 + x ^ 3.
3. Умножьте полином на x ^ 32.
4. Возьмите остаток от этого полинома, разделенный на полином CRC-32, 0x104C11DB7. Остальной полином имеет степень <32. </li>
5. Обрабатывать младшие степени как биты более высокого порядка. Например, полином x ^ 2 будет 32-разрядным целым числом 0x40000000.
6. XOR результат на 0xFFFFFFFF.

Операция чистого полиномиального остатка находится на шаге # 4. Именно шаги # 1 и # 6 делают алгоритм CRC-32 неаддитивным. Поэтому, если вы отмените действие шагов # 1 и # 6, то вы можете изменить алгоритм CRC-32, чтобы он был аддитивным.

(См. Также: Python CRC-32 горе )

Answer 4

Это будет означать, что каждая битовая позиция результата CRC определяется только эквивалентной битовой позицией на входе. Рассмотрим ваш пример с B == 0.

Соотношение, которое вы описываете, скорее всего будет верным для некоторых примитивных алгоритмов xor или аддитивных контрольных сумм.