Является ли CRC32 аддитивным?

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 математически обоснована, но для практических целей расчета хэш, это последнее, что вам нужно.

Алгоритм 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.
5. Относитесь к более низким степеням как к битам более высокого порядка. Например, многочлен x^2 будет 32-битным целым числом 0x40000000.
6. XOR результата на 0xFFFFFFFF.

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

(См. также: Python CRC-32 woes)

Если 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 — последовательность нулей той же длины, что и две другие последовательности.

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

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