Расчет CRC в основном статическом потоке данных

Ответ 1

Да. Вы можете видеть, как в zlib crc32_combine(). Если у вас есть две последовательности A и B, то чистый CRC AB является исключительным или CRC из A0 и CRC 0B, где 0 представляет собой последовательность из нулевых байтов с длиной соответствующей последовательности, то есть B и А соответственно.

Для вашего приложения вы можете предварительно вычислить один оператор, который очень быстро применяет 1020 нулей в CRC ваших первых четырех байтов. Затем вы можете использовать эксклюзивную или с предварительно вычисленным CRC из 1020 байт.

Update:

Вот мое сообщение от 2008 года с подробным объяснением, что @ArtemB обнаружил (о котором я забыл):

crc32_combine() в zlib основан на двух ключевых трюках. Для дальнейшего, мы откладываем тот факт, что стандартный 32-битный CRC является предварительным и пост- кондиционер. Мы с этим справимся позже. Предположим теперь, что CRC, который не имеет такого кондиционирования, и поэтому начинается с регистра, заполненного нули.

Trick # 1: CRC линейны. Поэтому, если у вас есть поток X и поток Y одну и ту же длину и эксклюзивные или два потока побито для получения Z, т.е. Z = X ^ Y (используя обозначение C для исключительного или), то CRC (Z) = CRC (X) ^ CRC (Y). Для рассматриваемой задачи мы имеем два потока A и B различной длины, которую мы хотим объединить в поток Z. Что мы имеем CRC (A) и CRC (B). То, что мы хотим, это быстрый способ для вычисления CRC (Z). Трюк состоит в том, чтобы построить X = A, объединенную с длина (B) нулевых битов и Y = длина (A) нулевых битов, конкатенированных с B. Поэтому, если мы представляем конкатенацию просто путем сопоставления символы, X = A0, Y = 0B, то X ^ Y = Z = AB. Тогда имеем CRC (Z) = CRC (A0) ^ CRC (0B).

Теперь нам нужно знать CRC (A0) и CRC (0B). CRC (0B) прост. Если мы будем кормить пучок нулей для машины CRC, начиная с нуля, регистр по-прежнему заполняется нулями. Так, будто мы ничего не сделали. Поэтому CRC (0B) = CRC (B).

CRC (A0) требует больше работы. Принимая ненулевой CRC и кормление нули на машине CRC не оставляют ее в покое. Каждое изменение нуля содержимое регистра. Итак, чтобы получить CRC (A0), нам нужно установить регистр на CRC (A), а затем пропустить через него длину (B) нулей. Тогда мы можем исключение или результат этого с CRC (B) = CRC (0B), и мы получаем то, что мы хотим, что CRC (Z) = CRC (AB). Вуаля!

Ну, на самом деле вуаля преждевременна. Я был совсем не доволен это ответ. Я не хотел, чтобы расчеты занимали время пропорционально длине B. Это не спасло бы времени, сравнимого просто установить регистр в CRC (A) и запустить поток B через. Я решил, что должен быть более быстрый способ вычислить эффект подачи n нулей в машину CRC (где n = длина (B)). Так что приводит нас к:

Trick # 2: машина CRC - это машина с линейным состоянием. Если мы знаем, что линейное преобразование, которое возникает, когда мы подаем нуль на машину, то мы можем более эффективно выполнять операции над этим преобразованием найти преобразование, которое возникает в результате подачи n нулей в машина.

Преобразование подачи одного нулевого бита в машину CRC полностью представлена ​​бинарной матрицей 32x32. Чтобы применить мы умножаем матрицу на регистр, принимая регистрируется как 32-разрядный вектор-столбец. Для матричного умножения в бинарный (т.е. над полем Галуа 2), роль умножения играет и играет, а роль сложения играет эксклюзивно- or'ing.

Существует несколько различных способов построения магической матрицы, которая представляет собой преобразование, вызванное подачей машины CRC a одиночный нулевой бит. Один из способов - заметить, что каждый столбец матрицы это то, что вы получаете, когда ваш регистр начинается с одного в Это. Итак, первый столбец - это то, что вы получаете, когда регистр равен 100... а затем подать ноль, второй столбец начинается с 0100... и т.д. (Те, которые называются базовыми векторами.) Вы можете видеть это просто путем матричного умножения с этими векторами. Матричное умножение выбирает столбец матрицы соответствующий местоположению единственного.

Теперь за трюк. Когда у нас есть волшебная матрица, мы можем отложить содержимого исходного регистра на некоторое время, и вместо этого использовать преобразование для одного нуля для вычисления преобразования для n нули. Мы могли бы просто умножить n копий матрицы вместе, чтобы получить матрица для n нулей. Но это еще хуже, чем просто запуск n нули через машину. Однако есть простой способ избежать большинства этих матричных умножений, чтобы получить тот же ответ. Предположим, что мы хотите знать преобразование для запуска восьми нулевых бит или одного байт через. Позвольте назвать магическую матрицу, которая представляет собой запущенную ноль через: М. Мы могли бы сделать семь матричных умножений, чтобы получить R = MxMxMxMxMxMxMxM. Вместо этого позвольте начать с MxM и называть это P. Тогда PxP - MxMxMxM. Пусть назовем Q. Тогда QxQ равно R. Итак, теперь мы имеем уменьшил семь умножений до трех. P = MxM, Q = PxP и R = QxQ.

Теперь я уверен, что вы получаете идею для произвольного n числа нулей. Мы может очень быстро генерировать матрицы преобразования M _k, где M _k - это преобразование для прогона 2 ^k. (В абзац выше M ₃ равен R.) Мы можем сделать M ₁ через M _k только с k матричные умножения, начиная с M ₀= M. k, должно быть как как число битов в двоичном представлении n. Мы можем затем выберите те матрицы, в которых есть бинарные представления n и умножить их вместе, чтобы получить преобразование запущенных n нулей через машину CRC. Поэтому, если n = 13, вычислить M ₀ x M ₂ x M ₃.

Если j - номер единицы в двоичном представлении n, то мы просто j - 1 больше матричных умножений. Итак, мы имеем общее число k + j - 1 матричные умножения, где j <= k = floor (logbase2 (n)).

Теперь мы берем нашу быстро построенную матрицу для n нулей и умножаем что CRC (A) получает CRC (A0). Мы можем вычислить CRC (A0) в O (log (n)) времени, а не O (n). Мы исключительны или с CRC (B) и Вуаля! (действительно, на этот раз), у нас есть CRC (Z).

То, что делает zlib crc32_combine().

Я оставлю это как упражнение для читателя относительно того, как бороться с предварительное и пост-кондиционирование регистра CRC. Вам просто нужно примените наблюдения линейности выше. Подсказка: вам не нужно знать Длина (А). Фактически crc32_combine() принимает только три аргумента: CRC (A), CRC (B) и длина (B) (в байтах).