CRC - (Циклический избыточный код; англ. Cyclic redundancy check) используется для контроля целостности данных при передаче по сети или записи данных на носитель. Разные протоколы используют различные варианты, которые различаются разрядностью и образующими полиномами. Для рассчета CRC используется арифметика Галуа, в частности операция умножения. Умножение в конечном поле Галуа можно разделить на две операции: умножение без переносов и редуцирование. В большинстве случаев программисты не сильно задумываются над математикой и используют готовые таблицы и алгоритмы.
Допустим в нашем распоряжении есть процессорная инструкция умножения без переносов. Мы хотим оптимизировать и тем самым ускорить в несколько раз расчет контрольных сумм CRC, в десятки раз. Целью статьи является разработка общего подхода к синтезу алгоритмов содержащих умножение в конечном поле. Процесс создания алгоритмов для расчета CRC оказался весьма трудоемким. Хотя все эти алгоритмы подобны друг другу, но требуют отладки и расчета коэффициентов.
{Статья большая, я ее буду медленно дописывать и исправлять... прошу прощения за возможные неточности.}
На платформе Intel операции умножения без переносов соответствует инструкция pclmul. На платформе ARMv8-А также есть аналогичные инструкции, на базе которых можно эффективно реализовать операцию умножения без переносов, так называемая инструкция полиномиального умножения (PMULL) разрядностью операнда 64бит. На платформе ARMv7-A+NEON есть поддержка в виде инструкций vmull.p8, векторное полиномиальное умножение 8бит. На платформе ARMv8-М +MVE Helium ожидаем поддержку в виде векторных инструкций полиномиального умножения p8 бит и p16 бит
Все варианты операции CRC отличаются разрядностью, полиномами и порядком следования бит в числе.
В нашем программном обеспечении используются операции CRC:
CRC8/BACnet
CRC16/BAСnet
CRC16/MODBUS
CRC32K/Koopman
Кроме того, мы используем
CRC32С/Castagnoli
CRC32
CRC32B
Для описания алгоритмов я буду использовать инлайн-функции, которые призваны генерировать векторные инструкции. Базовые операции:
REFLECT128 -- Разворачивание последовательности бит в векторе
BSWAP128 -- Переворачивание порядка следования байт в векторе
LOAD128U -- Загрузка данных в векторный регистр без выравнивания
SLL128U -- логический сдвиг влево числа 128 бит.
Умножение без переноса:
CL_MUL32 () -- умножение без переносов двух чисел 32 бита, результат 64 бита
CL_MUL32H() -- старшие 32 бита произведения двух 32 битных чисел
CL_MUL32L() -- младшие 32 бита произведения
CL_MUL128() -- умножение младшей или старшей части вектора 64 бит на старшую или младшую часть второго вектора. Результат - число 128 бит.
Идея оптимизации сводится к накоплению буфера с отложенной операцией редуцирования, операциям сдвига в конечном поле и последующему финальному редуцированию на буфере. Буфером является векторный регистр.
Традиционно обработка CRC ведется на потоке данных, по одному байту. В реальных задачах возникает необходимость расчета CRC при передаче данных по сети или записи на носитель, с расчетом по шапке и телу пакета. Расчет может производится по частям: сначала от шапки пакета, затем от тела пакета или сразу от всего пакета. Когда чтение данных осуществляется блоками, расчет может производится так же по блокам.
Мы хотим разработать скоростной алгоритм, обрабатывать до 16 байт на один цикл, ориентируясь на максимальную разрядность векторного регистра. Планируем использовать операции умножения без переносов. Мы хотим рассчитывать параллельно до 16 контрольных сумм пользуясь тем, что преобразования линейные. Результат параллельного расчета фрагментов сообщения можно складывать. Операция сложения представлена битовой операцией исключающего ИЛИ (⊕). Сложение может выполняться до или после редуцирования.
Редуцирование - это уменьшение разрядности числа после операции умножения без переноса.
Метод ускорения CRC с использованием инструкций умножения без переноса (pclmul) был предложен до нас[2,3], Intel. Однако в литературе представлен только метод для CRC-32. Кроме того, в предложенной методике операция редуцирования выполняется без использования оперций умножения. В данной статье я привожу варианты алгоритмов другой разрядности 8,16,24,32, 64, и нескольких образующих полиномов, привожу методику рассчета сдвиговых коэффициентов, и констант для редуцирования полиномов. Предложен свой вариант алгоритмов для отраженных полиномов, отраженного порядка бит.
Список литературы, рекомендую предварительно ознакомиться:
[1] A painless guide to CRC error detection algorithms
[2] Intel/ Fast CRC Computation Using PCLMULQDQ Instruction
и несколько реализаций на GitHub и в исходниках Apple, в частности BZIP2.
[3] Intel® Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode
M1(x) • xs ⊕ M0(x) = M1 • (xs mod P) ⊕ M0
Эту операцию называют "схлопывание" (folding), слов не хватает, слова "редуцирование" и "сложение" уже заняты и наполнены смыслом. Сразу предлагаем воспользоваться правилом: редуцирование от редуцирования на результат не влияет. Поэтому мы можем сначала выполнить редуцирование сомножителей, а потом применять операцию умножения.
Константы (xs mod P) для разных показателей степени 32 64 96 128 .. можно рассчитать заранее и использовать для ускорения алгоритма.
Допустим, максимальное число, над которым удобно производить операцию "схлопывания" = 128 бит. Это прежде всего определяется разрядностью операции CL_MUL. В нашем случае операция может выполняться над 64 битными числами и результат имеет разрядность 128бит. Тогда определим операцию схлопывания так, преобразование вектора 256 бит [M4:M3:M2:M1] в 128 бит:
[C2:C1] = (M4 • K3) ⊕ (M3 • K4) ⊕ [M2:M1]
-- результат безрассудного умножения имеет разрядность 128 бит
K4 = x128 mod P
K3 = x192 mod P
K4 и K3 - это сдвиговые константы, возведение в степень - это операция сдвига на соответствующее число разрядов. Таким образом мы заменяем операцию сдвига в поле на операцию умножения без переноса. Соответственно, для последующего преобразования в CRC-32 нам понадобится операция редуцирования из 128-в-96 и 96-в-64 бит и финальное редуцирование 64-в-32 бита. Надо научиться рассчитывать константы для сдвигов и схлопывания.
Редукцию Барретта можно было бы определить так:
Операция floor(R(x)/x^32) в конечном поле это просто сдвиг на 32 разряда вправо, а для отраженного полинома - сдвиг влево.
Функция
Операция редуцирования методом Барретта 64-в-32
Такой же алгоритм можно использовать для обратного порядка обработки CRC, обратного порядка следования бит.
Мы только что определили, как выглядит операция поиска обратного (деления с остатком?) не-пойми-чего [1/P] с помощью алгоритма уполовинивания. см
Надо проверить результат barrett_calc. Если все верно, то произведение [1/P]•P должно давать что-то похожее на единицу с достаточной точностью. Проверяем...
(0x104D101DF • 0x104C11DB7) = 1.00000000.490D678D (65 бит);
Результат интересный, на единицу похож смутно, отдаленно, но похож. Если сдвинуть на 64 разряда, то единица получается. А вот в младших 32 битах лежит магическое число, для следующей операции пригодится - обратите внимание остаток равен сдвиговой константе.
Можно проверить ту же операцию на отраженном полиноме.
(0x1F7011641 • 0x1DB710641) = 1.63CD6124.00000001 (65 бит)
Чтобы поверить в магию умножения над отразить все биты в числе, все 65 бит... Короче, это тоже можно считать единицей, с заданной точностью 32 бита. Т.е. полиномы можно умножать задом наперед, но результат будет вывернут.
Правило для умножения без переноса для чисел с отраженным порядком бит выглядит так:
Результат нужно сдвинуть на один разряд. Таким образом, мы можем предложить алгоритм для отраженных полиномов, с использованием той же операции умножения без переносов. Алгоритм будет выглядеть очень похожим, с той лишь разницей, что при работе с отраженными полиномами всегда нужно сдвигать результат умножения на разряд влево.
Мой личный опыт строится на историческом осознании роли CRC и развитии CRC в нашем программном обеспечении, А также из чтения статей и изучения чужого опыта. В контроллерах мы применяем табличные методы расчета CRC. Причем, всегда стоит вопрос минимизации исходного кода прошивки, поэтому мы используем маленькие таблицы. Привожу пример табличного алгоритма, 4бит на шаг алгоритма.
Для синтеза таблиц умножения использую метод...
Как пользоваться редуцированием.
Один шаг над восьмибитными числами, обновляет значение CRC по байтам:
Я пишу серию алгоритмов для обработки по 8 бит, по 16 бит, по 32 по 64. И подбираю операции, отлаживаю для каждого шага. Потом из четырех полученных алгоримов создают пятый, который может работать со всеми длинами. Алгоритм можно вывести из математики, но на самом деле это две паралельные реальности, я смотрю на математику и пишу алгоритм, и наоборот проверяю какие-то действия в алгоритме и переписываю математику, которая этому соответствует. Что-то видно из математики что-то видно из алгоритма.
Кроме того, хочу предложить алгоритм расчета сдвиговой константы для сдвига вправо,x-t mod P(x) . Этот вариант привожу для полноты картины.
После этого все операции сдвига я начал оценивать именно с этой позиции, каждое умножение в поле это сдвиги и набор сдвигов можно представить через операции умножения. Каждый байт сообщения (слово, двойное слово) мы подвергаем сдвигу в поле и в конце должны просуммировать все эти значения. Мы должны решить, как именно разбивать сообщение на группы, на байты и слова. В конечном итоге каждый байт исходного сообщения подвергается своему сдвигу и суммируется с результатом.
Еще одно интересное свойство, которе хотелось бы добавить для полноты изложения - можно предложить обратную операцию, отмена действия UNDO, операция CRC обратима. Можно предложить операцию дописывания шапки сообщения, независимо от тела. Сначала расчитывается CRC от тела сообщения, потом досчитывается CRC от шапки, и в итоге можно вычислить CRC от всего сообщения. И наконец, можно предложить обратное преобразование, которое находит ошибочный бит в сообщении -- восстановление сообщения. Ну и совсем хакерская мысль, можно предложить математическое преобразование, которое меняет сообщение, но сохраняет CRC неизменным. Можно переписать сообщение и подогнать значение CRC, добавив магию в соль.
Итак, начнем с голой идеи. Мне сложно сразу написать правильный, работающий алгоритм, практически невозможно отладить, отладить можно только каждое отдельное действие. Поэтому я создаю алгоритм по шагам. На первом шаге я делаю всего одну опрерацию - редуцирование, - отлаживаю ее.
На втором шаге делаю две операции: редуцирование и сдвиг в поле
M1•(x32 mod P) mod P .
Потом, отлаживаю алгоритм редуцирования и два сдвига,
M2•(x64 mod P)) ⊕ M1•(x32 mod P)) mod P .
Затем - четыре сдвига,
M4•(x128 mod P)) ⊕ M3•(x96 mod P) ⊕ M2•(x64 mod P) ⊕ M1•(x32 mod P) mod P .
Потом делаю алгоритм, который обрабатывает все сообщение целиком с циклическим схлопыванием и финальным редуцированием.
1. Вычисляем, например, CRC32 по словам 32 бита. Алгоритм №.
2. Пишу преобразование двойным словам 64 биата
Теперь хотим развить тему и научиться синтезировать такие же алгоритмы для отраженного порядка бит, отраженных полиномов. Точно также, я начинаю с алгоритма редуцирования и по шагам отлаживаю каждую операцию, каждый сдвиг.xs mod P(x) Надо рассчитать константу xs-1 mod P(x)
K3=X191-32 и K4=X127-32 .
Привожу результат практический:
Привожу наборы констант.
Допустим в нашем распоряжении есть процессорная инструкция умножения без переносов. Мы хотим оптимизировать и тем самым ускорить в несколько раз расчет контрольных сумм CRC, в десятки раз. Целью статьи является разработка общего подхода к синтезу алгоритмов содержащих умножение в конечном поле. Процесс создания алгоритмов для расчета CRC оказался весьма трудоемким. Хотя все эти алгоритмы подобны друг другу, но требуют отладки и расчета коэффициентов.
{Статья большая, я ее буду медленно дописывать и исправлять... прошу прощения за возможные неточности.}
На платформе Intel операции умножения без переносов соответствует инструкция pclmul. На платформе ARMv8-А также есть аналогичные инструкции, на базе которых можно эффективно реализовать операцию умножения без переносов, так называемая инструкция полиномиального умножения (PMULL) разрядностью операнда 64бит. На платформе ARMv7-A+NEON есть поддержка в виде инструкций vmull.p8, векторное полиномиальное умножение 8бит. На платформе ARMv8-М +MVE Helium ожидаем поддержку в виде векторных инструкций полиномиального умножения p8 бит и p16 бит
Все варианты операции CRC отличаются разрядностью, полиномами и порядком следования бит в числе.
В нашем программном обеспечении используются операции CRC:
CRC8/BACnet
CRC16/BAСnet
CRC16/MODBUS
CRC32K/Koopman
Кроме того, мы используем
CRC32С/Castagnoli
CRC32
CRC32B
Для описания алгоритмов я буду использовать инлайн-функции, которые призваны генерировать векторные инструкции. Базовые операции:
REFLECT128 -- Разворачивание последовательности бит в векторе
BSWAP128 -- Переворачивание порядка следования байт в векторе
LOAD128U -- Загрузка данных в векторный регистр без выравнивания
SLL128U -- логический сдвиг влево числа 128 бит.
Умножение без переноса:
CL_MUL32 () -- умножение без переносов двух чисел 32 бита, результат 64 бита
CL_MUL32H() -- старшие 32 бита произведения двух 32 битных чисел
CL_MUL32L() -- младшие 32 бита произведения
CL_MUL128() -- умножение младшей или старшей части вектора 64 бит на старшую или младшую часть второго вектора. Результат - число 128 бит.
Что такое CRC
По сути вот что это такое, с математической точки зрения,
CRC = (M(x) • xt) mod P(x),
где t = deg(P(x)) - степень полинома, M(x)- сообщение(число)
Идея оптимизации сводится к накоплению буфера с отложенной операцией редуцирования, операциям сдвига в конечном поле и последующему финальному редуцированию на буфере. Буфером является векторный регистр.
Традиционно обработка CRC ведется на потоке данных, по одному байту. В реальных задачах возникает необходимость расчета CRC при передаче данных по сети или записи на носитель, с расчетом по шапке и телу пакета. Расчет может производится по частям: сначала от шапки пакета, затем от тела пакета или сразу от всего пакета. Когда чтение данных осуществляется блоками, расчет может производится так же по блокам.
Мы хотим разработать скоростной алгоритм, обрабатывать до 16 байт на один цикл, ориентируясь на максимальную разрядность векторного регистра. Планируем использовать операции умножения без переносов. Мы хотим рассчитывать параллельно до 16 контрольных сумм пользуясь тем, что преобразования линейные. Результат параллельного расчета фрагментов сообщения можно складывать. Операция сложения представлена битовой операцией исключающего ИЛИ (⊕). Сложение может выполняться до или после редуцирования.
Редуцирование - это уменьшение разрядности числа после операции умножения без переноса.
Метод ускорения CRC с использованием инструкций умножения без переноса (pclmul) был предложен до нас[2,3], Intel. Однако в литературе представлен только метод для CRC-32. Кроме того, в предложенной методике операция редуцирования выполняется без использования оперций умножения. В данной статье я привожу варианты алгоритмов другой разрядности 8,16,24,32, 64, и нескольких образующих полиномов, привожу методику рассчета сдвиговых коэффициентов, и констант для редуцирования полиномов. Предложен свой вариант алгоритмов для отраженных полиномов, отраженного порядка бит.
Список литературы, рекомендую предварительно ознакомиться:
[1] A painless guide to CRC error detection algorithms
[2] Intel/ Fast CRC Computation Using PCLMULQDQ Instruction
и несколько реализаций на GitHub и в исходниках Apple, в частности BZIP2.
[3] Intel® Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode
Операция схлопывания
Сообщение М можно разложить на два фрагмента со смещением:M1(x) • xs ⊕ M0(x) = M1 • (xs mod P) ⊕ M0
Эту операцию называют "схлопывание" (folding), слов не хватает, слова "редуцирование" и "сложение" уже заняты и наполнены смыслом. Сразу предлагаем воспользоваться правилом: редуцирование от редуцирования на результат не влияет. Поэтому мы можем сначала выполнить редуцирование сомножителей, а потом применять операцию умножения.
Константы (xs mod P) для разных показателей степени 32 64 96 128 .. можно рассчитать заранее и использовать для ускорения алгоритма.
Допустим, максимальное число, над которым удобно производить операцию "схлопывания" = 128 бит. Это прежде всего определяется разрядностью операции CL_MUL. В нашем случае операция может выполняться над 64 битными числами и результат имеет разрядность 128бит. Тогда определим операцию схлопывания так, преобразование вектора 256 бит [M4:M3:M2:M1] в 128 бит:
[C2:C1] = (M4 • K3) ⊕ (M3 • K4) ⊕ [M2:M1]
-- результат безрассудного умножения имеет разрядность 128 бит
K4 = x128 mod P
K3 = x192 mod P
K4 и K3 - это сдвиговые константы, возведение в степень - это операция сдвига на соответствующее число разрядов. Таким образом мы заменяем операцию сдвига в поле на операцию умножения без переноса. Соответственно, для последующего преобразования в CRC-32 нам понадобится операция редуцирования из 128-в-96 и 96-в-64 бит и финальное редуцирование 64-в-32 бита. Надо научиться рассчитывать константы для сдвигов и схлопывания.
Редукция Barrett'a
Редукция основана на такой идее, которая изначально родилась для целых чисел. Хотим подобрать такое число Ux, чтобы результат умножения Ux*Px - давал единицу с высокой точностью. Например, хотим поделить целое число в конечном поле 32 бита на 10, а операция деления напрочь отсутствует в нашем арсенале. Тогда мы можем найти такое целое число, чтобы результат операции (A*Ux)>>32 в точности давал бы результат A/10 для всех целых чисел. По сути мы ищем такое целое число, чтобы оно работало как multiplicative inverse (обратное число по отношению к образующему полиному).Редукцию Барретта можно было бы определить так:
T1 = floor(R(x)/x^32) * [1/P(x)]; R/P
T2 = floor(T1/x^32) * P(x); int(R/P)*P;
CRC= (R+int(R/P)*P) mod x^32; R-int(R/P)*P
только под делением мы понимаем операцию уполовинивания в поле, под сложением - битовую операцию XOR и под произведением - умножение без переносов, под делением на x^32 понимаем сдивиг на 32 разряда вправо. Короче, математическое определение редуцирования мало что дает на практике. Можно сказать, зная алгоритм редуцирования для целых чисел я угадал, как он будет выглядеть в конечном поле.Операция floor(R(x)/x^32) в конечном поле это просто сдвиг на 32 разряда вправо, а для отраженного полинома - сдвиг влево.
Функция
barrett_calc рассчитывает магическое число Баррета, которое в дальнейшем позволяет редуцировать полином.
/*! Алгоритм №1. рассчитывает константу Барретт'а */
uint64_t barrett_calc(uint64_t poly, int bits)
{
int n = bits;
uint64_t r = poly;
uint64_t v = 0;
while (--n){
if (r & (1ULL<<n)) {
r ^= poly>>(bits-n);
v |= 1ULL<<n;
}
}
if (r) v|=1;// для деления с остатком округляем в большую сторону
return v;
}Операция редуцирования методом Барретта 64-в-32
/*! Алгоритм №2. Редукция Барретт'а*/
uint32_t R (uint32_t v1, uint32_t v0)
{
uint32_t t = CL_MUL32H(v1, U) ^ v1;// U имеет разрядность 33 бита
return CL_MUL32L(t, P) ^ v0;
}
Такой же алгоритм можно использовать для обратного порядка обработки CRC, обратного порядка следования бит.
/*! Алгоритм №3. Редукция Барретт'а для отраженных чисел */
uint32_t RR (uint32_t v1, uint32_t v0)
{
uint32_t t = CL_MUL32L(v1, UR);
return CL_MUL32H(t, PR) ^ t ^ v0;// PR имеет разрядность 33 бита
}
Мы только что определили, как выглядит операция поиска обратного (деления с остатком?) не-пойми-чего [1/P] с помощью алгоритма уполовинивания. см
barrett_calc Надо проверить результат barrett_calc. Если все верно, то произведение [1/P]•P должно давать что-то похожее на единицу с достаточной точностью. Проверяем...
(0x104D101DF • 0x104C11DB7) = 1.00000000.490D678D (65 бит);
Результат интересный, на единицу похож смутно, отдаленно, но похож. Если сдвинуть на 64 разряда, то единица получается. А вот в младших 32 битах лежит магическое число, для следующей операции пригодится - обратите внимание остаток равен сдвиговой константе.
Можно проверить ту же операцию на отраженном полиноме.
(0x1F7011641 • 0x1DB710641) = 1.63CD6124.00000001 (65 бит)
Чтобы поверить в магию умножения над отразить все биты в числе, все 65 бит... Короче, это тоже можно считать единицей, с заданной точностью 32 бита. Т.е. полиномы можно умножать задом наперед, но результат будет вывернут.
Правило для умножения без переноса для чисел с отраженным порядком бит выглядит так:
reflect(A) • reflect(B) == reflect(A • B)<<1
Результат нужно сдвинуть на один разряд. Таким образом, мы можем предложить алгоритм для отраженных полиномов, с использованием той же операции умножения без переносов. Алгоритм будет выглядеть очень похожим, с той лишь разницей, что при работе с отраженными полиномами всегда нужно сдвигать результат умножения на разряд влево.
Мой личный опыт строится на историческом осознании роли CRC и развитии CRC в нашем программном обеспечении, А также из чтения статей и изучения чужого опыта. В контроллерах мы применяем табличные методы расчета CRC. Причем, всегда стоит вопрос минимизации исходного кода прошивки, поэтому мы используем маленькие таблицы. Привожу пример табличного алгоритма, 4бит на шаг алгоритма.
// Алгоритм №4 -- табличный метод 4 бит.
uint32_t CRC32_update (uint32_t crc, uint8_t val){
crc = (crc<<4) ^ CRC32_Lookup4[((crc>>28) ^ (val>>4)) & 0xF ];
crc = (crc<<4) ^ CRC32_Lookup4[((crc>>28) ^ (val )) & 0xF ];
return crc;
}
// Алгоритм №5 -- табличный метод 8 бит.
uint32_t CRC32_update (uint32_t crc, uint8_t val){
crc = (crc<<8) ^ CRC32_Lookup8[((crc>>24) ^ (val )) & 0xFF ];
return crc;
}
[M3:M2:M1]•x8 == ((M3•x8 ⊕ M2)•x8 ⊕ M1)•x8
Для синтеза таблиц умножения использую метод...
// Алгоритмом № Расчет таблицы умножения, прямой порядок
/*! \brief генерация таблицы подстановки CRC
\param poly полином
\param bits число бит в полиноме
\param size число элементов в таблице 16 или 256
*/
void crc_gen_table(uint64_t poly, int bits, int size)
{
uint64_t table[size];// = {0};
uint64_t p =poly;
int i,j;
table[0] = 0;
table[1] = p;
for (i=1;(1<<i)<size;i++)
{
if (p&(1ULL<<(bits-1))) {
p &= ~((~0ULL)<<(bits-1));
p = (p<<1) ^ poly;
} else
p = (p<<1);
table[1<<i] = p;
for(j=1; j<(1<<i); j++) {
table[(1<<i)+j] = p ^ table[j];
}
}
// Распечатать таблицу
printf("POLY=0x%0*"PRIX64"\n", bits/4, poly);
for(i=0;i<size;i++){
printf("0x%0*"PRIX64", ", bits/4, table[i]);
if ((i&0x3)==0x3) printf("\n");
}
}
Алгоритм № -- метод c умножением 8 бит.
[c4:c3:c2:c1] ::= [c3:c2:c1:0]⊕((c4⊕ Mi)•x8 mod P)
Как пользоваться редуцированием.
Один шаг над восьмибитными числами, обновляет значение CRC по байтам:
uint32_t CRC32_update_8 (uint32_t crc, uint8_t data){
uint32_t val=data;
val = BSWAP32(val); // перестановка байт
crc = crc ^ val;
// Barrett's reduction
uint32_t t = CL_MUL32H(crc>>24, 0x04D101DF)^(crc>>24);
uint32_t v = CL_MUL32L(t , 0x04C11DB7)^(crc<< 8);
return v;
}
Я пишу серию алгоритмов для обработки по 8 бит, по 16 бит, по 32 по 64. И подбираю операции, отлаживаю для каждого шага. Потом из четырех полученных алгоримов создают пятый, который может работать со всеми длинами. Алгоритм можно вывести из математики, но на самом деле это две паралельные реальности, я смотрю на математику и пишу алгоритм, и наоборот проверяю какие-то действия в алгоритме и переписываю математику, которая этому соответствует. Что-то видно из математики что-то видно из алгоритма.
uint32_t CRC32_update_32 (uint32_t crc, uint32_t val){
val = BSWAP32(val); // перестановка байт
crc = crc ^ val;
// Barrett's reduction
uint32_t t = CL_MUL32H(crc, 0x04D101DF)^(crc);
uint32_t v = CL_MUL32L(t , 0x04C11DB7);
return v;
}
// Алгоритм №. Расчет сдвиговых констант (xt mod P):
uint64_t xt_mod_P(uint64_t poly, int t, int bits)
{
uint64_t v = poly;
do {
if (v & MSB){ // старший бит проверяем
v = (v<<1) ^ poly;
} else {
v = (v<<1);
}
} while (--t);
return v;
}/* Алгоритм №. Расчет отраженных сдвиговых констант (xt mod P):
poly - отраженный полином 33 бита.
*/
uint64_t xt_mod_P_reflect(uint64_t poly, int t, int bits)
{
uint64_t v = poly;
do {
if (v & 1){
v = (v>>1) ^ poly;
} else {
v = (v>>1);
}
} while (--t);
return v;
}
Кроме того, хочу предложить алгоритм расчета сдвиговой константы для сдвига вправо,
// Алгоритм №. расчет сдвиговых констант, сдвиг вправо
uint64_t xt_mod_P_neg(uint64_t poly, int t, int bits){
uint64_t v=1;
do {
if (v&1)
v = (v>>1) ^ (1ULL<<(bits-1)|poly>>1);
else
v = (v>>1);
} while (--t);
return v;
}
После этого все операции сдвига я начал оценивать именно с этой позиции, каждое умножение в поле это сдвиги и набор сдвигов можно представить через операции умножения. Каждый байт сообщения (слово, двойное слово) мы подвергаем сдвигу в поле и в конце должны просуммировать все эти значения. Мы должны решить, как именно разбивать сообщение на группы, на байты и слова. В конечном итоге каждый байт исходного сообщения подвергается своему сдвигу и суммируется с результатом.
Еще одно интересное свойство, которе хотелось бы добавить для полноты изложения - можно предложить обратную операцию, отмена действия UNDO, операция CRC обратима. Можно предложить операцию дописывания шапки сообщения, независимо от тела. Сначала расчитывается CRC от тела сообщения, потом досчитывается CRC от шапки, и в итоге можно вычислить CRC от всего сообщения. И наконец, можно предложить обратное преобразование, которое находит ошибочный бит в сообщении -- восстановление сообщения. Ну и совсем хакерская мысль, можно предложить математическое преобразование, которое меняет сообщение, но сохраняет CRC неизменным. Можно переписать сообщение и подогнать значение CRC, добавив магию в соль.
Итак, начнем с голой идеи. Мне сложно сразу написать правильный, работающий алгоритм, практически невозможно отладить, отладить можно только каждое отдельное действие. Поэтому я создаю алгоритм по шагам. На первом шаге я делаю всего одну опрерацию - редуцирование, - отлаживаю ее.
На втором шаге делаю две операции: редуцирование и сдвиг в поле
Потом, отлаживаю алгоритм редуцирования и два сдвига,
Затем - четыре сдвига,
Потом делаю алгоритм, который обрабатывает все сообщение целиком с циклическим схлопыванием и финальным редуцированием.
Алгоритм №. Векторный алгоритм рассчета CRC-32
Шаг 1. загрузить вектор с переворотом
[c4:c3:c2:c1] := [M4:M3:M2:M1] ⊕ [crc:0:0:0]
Шаг 2. Цикл для каждого фрагмента 128-бит
[A3:A2:A1] := [c4:c3]•(x192 mod P) ⊕ [c2:c1]•(x128 mod P)
[c4:c3:c2:c1] := [ 0:A3:A2:A1] ⊕ [M4:M3:M2:M1]
Шаг 3. Сдвиги,
[c3:c2:c1] := [с4:c3]•(x96 mod P) ⊕ [с2:c1]•(x32 mod P)
[c2:c1] := [c2:c1] ⊕ с3•(x64 mod P)
Шаг 4. Редуцирование
[T2:T1] := c2•Ux
[c2:c1] := T2•Px ⊕ [c2:c1]
Возвращает: crc = c1
1. Вычисляем, например, CRC32 по словам 32 бита. Алгоритм №.
2. Пишу преобразование двойным словам 64 биата
uint32_t CRC32_update_64 (uint32_t crc, uint8_t* data){
c = BSWAP64(data); // перестановка байт
c = c ^ crc;
// схлопывание [c2:c1]•x32 mod P(x) (96 бит в 64 бита)
с = CL_MUL32(c[1], xt_mod_P(Px, 64))
^ CL_MUL32(c[0], xt_mod_P(Px, 32));
// Barrett's reduction
uint32_t t = CL_MUL32H(crc, Ux)^(crc);
uint32_t v = CL_MUL32L(t , Px);
return v;
}// Алгоритм №.
uint32_t CRC32_update_128(uint32_t crc, uint8_t *data, int len) {
uint64x2_t c;
c = BSWAP128(data); data+=16;
c[1] ^= (uint64_t)crc<<32;
int blocks = (len+15 >> 4);
while (--blocks>0) {
c = CL_MUL64(c[1], K3)
^ CL_MUL64(c[0], K4)
^ BSWAP128(data); data+=16;
}
// схлопывание [c4:c3:c2:c1]•x32 mod P(x) (128бит в 64 бита)
c = CL_MUL32(c[1]>>32, K4)
^ CL_MUL32(c[1]>> 0, K5)
^ CL_MUL32(c[0]>>32, K6)
^ CL_MUL32(c[0]>> 0, K7);
// Редуцирование 64 бит в 32 бит
uint32_t t = CL_MUL32H(c[0]>>32, Ux);
crc = CL_MUL32L(t, Px) ^ c[0];
return crc;
}
Алгоритм №. Векторный алгоритм рассчета CRC-32, 256 бит
Шаг 1. загрузить вектор с переворотом
[c8:c7:c6:c5:c4:c3:c2:c1] := [M8:M7:M6:M5:M4:M3:M2:M1] ⊕ [crc:0:0:0:0:0:0:0]
Шаг 2. Цикл для каждого фрагмента 256-бит
[A3:A2:A1] := [c4:c3]•(x256+64 mod P) ⊕ [c2:c1]•(x256 mod P)
[A7:A6:A5] := [c8:c7]•(x256+64 mod P) ⊕ [c6:c5]•(x256 mod P)
[c8:c7:c6:c5:c4:c3:c2:c1] := [ 0:A7:A6:A5: 0:A3:A2:A1] ⊕ [M8:M7:M6:M5:M4:M3:M2:M1]
Шаг 3. Редуцирование 256 в 128
[c4:c3:c2:c1] := [c4:c3:c2:c1]
⊕ [c8:c7]•(x128+64 mod P) ⊕ [c6:c5]•(x128 mod P)
Шаг 4. если есть фрагмент 128-бит,
[A3:A2:A1] := [c4:c3]•(x192 mod P) ⊕ [c2:c1]•(x128 mod P)
[c4:c3:c2:c1] := [ 0:A3:A2:A1] ⊕ [M4:M3:M2:M1]
Шаг 5. Сдвиги,
[c2:c1] := c4•(x128 mod P) ⊕ c3•(x96 mod P)
⊕ c2•(x64 mod P) ⊕ c1•(x32 mod P)
Шаг 6. Редуцирование
[T2:T1] := c2•Ux
[c2:c1] := T2•Px ⊕ [c2:c1]
Возвращает: crc = c1
Теперь хотим развить тему и научиться синтезировать такие же алгоритмы для отраженного порядка бит, отраженных полиномов. Точно также, я начинаю с алгоритма редуцирования и по шагам отлаживаю каждую операцию, каждый сдвиг.
// Алгоритм №.
uint32_t CRC32K_update_8 (uint32_t crc, uint8_t *data){
uint32_t val;
val = data[0];
crc = crc ^ val;
poly64x2_t c = {crc};
c = SLL128U(c,32+24);// сдвиг влево числа 128 бит
// Barrett's reduction
poly64x2_t t;
t = CL_MUL128(c, (poly64x2_t){Ux,Px}, 0x00);
c ^= CL_MUL128(t, (poly64x2_t){Ux,Px}, 0x10);
return c[1];
}
// Алгоритм №.
uint32_t CRC32K_update_16(uint32_t crc, uint8_t *data){
uint32_t val;
val = *(uint16_t*)data;
crc = crc ^ val;
// подбираю связь между величиной сдвига и шагом алгоритма
poly64x2_t c = {crc};
c = SLL128U(c,32+16);
// Barrett's reduction
poly64x2_t t;
t = CL_MUL128(c, (poly64x2_t){Ux, Px}, 0x00);
c ^= CL_MUL128(t, (poly64x2_t){Ux, Px}, 0x10);
return c[1];
}
// Алгоритм №.
uint32_t CRC32K_update_24(uint32_t crc, uint8_t *data){
uint32_t val=0;
__builtin_memcpy(&val, data,3);
crc = crc ^ val;
// подбираю связь между величиной сдвига и шагом алгоритма
poly64x2_t c = {crc};
c = SLL128U(c,32+8);
// Barrett's reduction
poly64x2_t t;
t = CL_MUL128(c, (poly64x2_t){Ux, Px}, 0x00);
c ^= CL_MUL128(t, (poly64x2_t){Ux, Px}, 0x10);
return c[1];
}
// Алгоритм №.
uint32_t CRC32K_update_32(uint32_t crc, uint8_t *data){
uint32_t val;
val = *(uint32_t*)data;
crc = crc ^ val;
// сдвиги заменяем на умножение
poly64x2_t c = {0,(uint64_t)crc<<32};
c = CL_MUL128(c& 0xFFFFFFFF00000000ULL, (poly64x2_t){K7<<1}, 0x01);
// Barrett's reduction
poly64x2_t t;
t = CL_MUL128(c, (poly64x2_t){Ux, Px}, 0x00);// {Ux, Px}
c ^= CL_MUL128(t, (poly64x2_t){Ux, Px}, 0x10);
return c[1];
}
// Алгоритм №.
uint32_t CRC32K_update_128(uint32_t crc, uint8_t *data){
poly64x2_t c = (poly64x2_t)LOAD128U(data);
c[0]^=crc;
// сдвиги
c = CL_MUL128(c<<32, (poly64x2_t){K4<<1}, 0x00)
^ CL_MUL128(c& 0xFFFFFFFF00000000ULL, (poly64x2_t){K5<<1}, 0x00)
^ CL_MUL128(c<<32, (poly64x2_t){K6<<1}, 0x01)
^ CL_MUL128(c& 0xFFFFFFFF00000000ULL, (poly64x2_t){K7<<1}, 0x01);
// Barrett's reduction
poly64x2_t t;
t = CL_MUL128(c, (poly64x2_t){Ux, Px}, 0x00);// {Ux, Px}
c ^= CL_MUL128(t, (poly64x2_t){Ux, Px}, 0x10);
return c[1];
}
// Алгоритм №.
uint32_t CRC32K_update_N(uint32_t crc, uint8_t *data, int len){
poly64x2_t c = (poly64x2_t)LOAD128U(data);data+=16;
c[0]^=crc;
// Циклическое схлопывание folding
int blocks = (len+15 >> 4);
while (--blocks>0){
c = CL_MUL128(c, (poly64x2_t){K3<<1}, 0x00)
^ CL_MUL128(c, (poly64x2_t){K4<<1}, 0x01);
c = SLL128U(c, 32) ^ (poly64x2_t)LOAD128U(data); data+=16;
}
// Сдвиги редуцирование
c = CL_MUL128(c<<32, (poly64x2_t){K4<<1}, 0x00)
^ CL_MUL128(c& 0xFFFFFFFF00000000ULL, (poly64x2_t){K5<<1}, 0x00)
^ CL_MUL128(c<<32, (poly64x2_t){K6<<1}, 0x01)
^ CL_MUL128(c& 0xFFFFFFFF00000000ULL, (poly64x2_t){K7<<1}, 0x01);
// Barrett's reduction
poly64x2_t t;
t = CL_MUL128(c, (poly64x2_t){Ux, Px}, 0x00);// {Ux, Px}
c ^= CL_MUL128(t, (poly64x2_t){Ux, Px}, 0x10);
return c[1];
}
Алгоритм №. Векторный алгоритм CRC-32B отраженный порядок
Шаг 1. загрузить вектор M, 32x4 =128 бит
[c4:c3:c2:c1] := [M4:M3:M2:M1] ⊕ [0:0:0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит
[A3:A2:A1] := [c2:c1]•(x191 mod P) ⊕ [c4:c3]•(x127 mod P)
[c4:c3:c2:c1] := [A3:A2:A1:0] ⊕ [M4:M3:M2:M1]
Шаг 3. Сдвиги,
[c2:c1] :=
с1•(x127 mod P)
⊕ с2•(x95 mod P)
⊕ с3•(x63 mod P)
⊕ с4•(x31 mod P)
Шаг 4. Редуцирование
[T2:T1] := c1•Ux
[c2:c1] := T1•Px ⊕ [c2:c1]
Возвращает: crc = c2
Алгоритм №. Векторный алгоритм CRC-32B отраженный порядок
Шаг 1. загрузить вектор M, 32x4 =128 бит
[c4:c3:c2:c1] := [M4:M3:M2:M1] ⊕ [0:0:0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит
[A3:A2:A1] := [c2:c1]•(x159 mod P) ⊕ [c4:c3]•(x95 mod P)
[c4:c3:c2:c1] := [0:A3:A2:A1] ⊕ [M4:M3:M2:M1]
Шаг 3. Сдвиги,
[c2:c1] :=
с1•(x127 mod P)
⊕ с2•(x95 mod P)
⊕ с3•(x63 mod P)
⊕ с4•(x31 mod P)
Шаг 4. Редуцирование
[T2:T1] := c1•Ux
[c2:c1] := T1•Px ⊕ [c2:c1]
Возвращает: crc = c2
Привожу результат практический:
CRC-32/BZIP2 poly=0x04c11db7
init=0xffffffff refin=false refout=false xorout=0xffffffff check=0xfc891918
Px = 0x104C11DB7
Ux = 0x104D101DF
K7 = xt_mod_P(Px, 32) = 0x04C11DB7
K6 = xt_mod_P(Px, 64) = 0x490D678D
K5 = xt_mod_P(Px, 96) = 0xF200AA66
K4 = xt_mod_P(Px, 128) = 0xE8A45605
K3 = xt_mod_P(Px, 192) = 0xC5B9CD4C
K2 = xt_mod_P(Px, 512) = 0xE6228B11
K1 = xt_mod_P(Px, 576) = 0x8833794C
CRC-32B poly=0x04c11db7
init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xCBF43926
POLY=0xEDB88320
Таблица умножения:
0x00000000, 0x1DB71064, 0x3B6E20C8, 0x26D930AC,
0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C,
0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C,
BarrettR u = x^64/P(x) Ur=0x1F7011641 Pr=0x1DB710641
[1/p]*p(x) = 163CD612400000001
Test =CBF43926 ..ok
K7( 32-1) = 00000001
K6( 64-1) = B8BC6765
K5( 96-1) = CCAA009E
K4(128-1) = 9BA54C6F
K3(192-1) = 65673B46
CRC-32C (Castagnoli) poly=0x1edc6f41
init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xE3069283
POLY=0x82F63B78
Таблица умножения:
0x00000000, 0x105EC76F, 0x20BD8EDE, 0x30E349B1,
0x417B1DBC, 0x5125DAD3, 0x61C69362, 0x7198540D,
0x82F63B78, 0x92A8FC17, 0xA24BB5A6, 0xB21572C9,
0xC38D26C4, 0xD3D3E1AB, 0xE330A81A, 0xF36E6F75,
BarrettR u = x^64/P(x) Ur=0xDEA713F1 Pr=0x105EC76F1
[1/p]*p(x) = 0DD45AAB800000001
Test =E3069283 ..ok
K7( 32-1) = 00000001
K6( 64-1) = DD45AAB8
K5( 96-1) = 493C7D27
K4(128-1) = 3171D430
K3(192-1) = 3743F7BD
CRC-32K/BACnet (Koopman) poly= 0x741b8cd7 (0xEB31D82E)
init=0xffffffff refin=true refout=true xorout=0xffffffff check=0x2D3DD0AE
POLY=0xEB31D82E
Таблица умножения:
0x00000000, 0x83CF0F3C, 0xD1FDAE25, 0x5232A119,
0x7598EC17, 0xF657E32B, 0xA4654232, 0x27AA4D0E,
0xEB31D82E, 0x68FED712, 0x3ACC760B, 0xB9037937,
0x9EA93439, 0x1D663B05, 0x4F549A1C, 0xCC9B9520,
BarrettR u = x^64/P(x) Ur=0x17D232CD Pr=0x1D663B05D
[1/p]*p(x) = 018C5564C00000001
Test =2D3DD0AE ..ok
K7( 32-1) = 00000001
K6( 64-1) = 18C5564C
K5( 96-1) = 9D65B2A5
K4(128-1) = 69F48E4D
K3(192-1) = CBB06D55
[31.12.2019]
Написал векторный алогоритм для CRC-16 с отраженным порядком.Алгоритм №. Векторный алгоритм CRC-16B отраженный порядок
Шаг 1. загрузить вектор M, 16x8 =128 бит
[c8:c7:c6:c5:c4:c3:c2:c1] := [M8:M7:M6:M5:M4:M3:M2:M1] ⊕ [0:0:0:0:0:0:0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит
[A5:A4:A3:A2:A1] := [c4:c3:c2:c1]•(x191 mod P) ⊕ [c8:c7:c6:c5]•(x127 mod P)
[c8:c7:c6:c5:c4:c3:c2:c1] := [A5:A4:A3:A2:A1:0:0:0] ⊕ [M8:M7:M6:M5:M4:M3:M2:M1]
Шаг 3. Сдвиги,
[c2:c1] :=
с1•(x127 mod P)
⊕ с2•(x111 mod P)
⊕ с3•(x95 mod P)
⊕ с4•(x79 mod P)
⊕ с5•(x63 mod P)
⊕ с6•(x47 mod P)
⊕ с7•(x31 mod P)
⊕ с8•(x15 mod P)
Шаг 4. Редуцирование
[T2:T1] := c1•Ur
[c2:c1] := T1•Pr ⊕ [c2:c1]
Возвращает: crc = c2
Привожу наборы констант.
CRC-16/X25 poly=0x1021
init=0xffff refin=true refout=true xorout=0xffff check=0x906e
POLY=0x8408
Таблица умножения:
0x0000, 0x1081, 0x2102, 0x3183,
0x4204, 0x5285, 0x6306, 0x7387,
0x8408, 0x9489, 0xA50A, 0xB58B,
0xC60C, 0xD68D, 0xE70E, 0xF78F,
BarrettR u = x^16/P(x) Ur=0x1911 Pr=0x10811
[1/p]*p = 00000000019D80001
Test =906E ..ok
K9( 15) = 0001
K8( 31) = 19D8
K7( 47) = 1CBB
K6( 63) = 042B
K5( 79) = 81BF
K4( 95) = 2C27
K3(111) = 8555
K2(127) = 7EEA
K1(191) = A95D
CRC-16/MODBUS poly=0x8005
init=0xffff refin=true refout=true xorout=0x0000 check=0x4b37
POLY=0xA001
Таблица умножения:
0x0000, 0xCC01, 0xD801, 0x1400,
0xF001, 0x3C00, 0x2800, 0xE401,
0xA001, 0x6C00, 0x7800, 0xB401,
0x5000, 0x9C01, 0x8801, 0x4400,
BarrettR u = x^16/P(x) Ur=0x1BFFF Pr=0x14003
[1/p]*p = 000000001D0020001
Test =4B37 ..ok
K9( 15) = 0001
K8( 31) = 9001
K7( 47) = FC01
K6( 63) = D101
K5( 79) = CCC1
K4( 95) = C551
K3(111) = C3FD
K2(127) = C100
K1(191) = CCD0
[01.01.2020]
Зачем публиковать, если нет ни одного ценителя. Ау! Ценители отзовитесь. Нужно публиковать алгоритм?Алгоритм №. Векторный алгоритм CRC-64/XZ отраженный порядок
Шаг 1. загрузить вектор M, 64x2 =128 бит
[c2:c1] := [M2:M1] ⊕ [crc:0]
Шаг 2. Цикл для каждого фрагмента 128-бит
[A2:A1] := c1•(x191 mod P) ⊕ c2•(x127 mod P)
[c2:c1] := [A2:A1] ⊕ [M2:M1]
Шаг 3. Сдвиги,
[c2:c1] := с1•(x127 mod P) ⊕ с2•(x63 mod P)
Шаг 4. Редуцирование
[T2:T1] := c1•Ur
[c2:c1] := T1•Pr ⊕ [c2:c1]
Возвращает: crc = c2
CRC-64/XZ poly=0x42F0E1EBA9EA3693 отраженный порядок
init=0xFFFFFFFFFFFFFFFF refin=true refout=true xorout=0xFFFFFFFFFFFFFFFF check=0x995DC9BBDF1939FA
POLY=0xC96C5795D7870F42
Таблица умножения:
0x0000000000000000, 0x7D9BA13851336649, 0xFB374270A266CC92, 0x86ACE348F355AADB,
0x64B62BCAEBC387A1, 0x192D8AF2BAF0E1E8, 0x9F8169BA49A54B33, 0xE21AC88218962D7A,
0xC96C5795D7870F42, 0xB4F7F6AD86B4690B, 0x325B15E575E1C3D0, 0x4FC0B4DD24D2A599,
0xADDA7C5F3C4488E3, 0xD041DD676D77EEAA, 0x56ED3E2F9E224471, 0x2B769F17CF112238,
BarrettR u = x^128/P(x) Ur=0x9C3E466C172963D5 Pr=0x192D8AF2BAF0E1E85 (65-бит)
[1/p]*p(x) = 48663A84688941C50000000000000001
Test =995DC9BBDF1939FA ..ok
K5( 63) = x63 mod P = 0000000000000001
K4(127) = x127 mod P = DABE95AFC7875F40
K3(191) = x191 mod P = E05DD497CA393AE4
Алгоритм №. Векторный алгоритм CRC-64/WE прямой порядок
Шаг 1. загрузить вектор M с разворотом байт, 64x2 =128 бит
[c2:c1] := [M2:M1] ⊕ [0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит
[A2:A1] := c2•(x192 mod P) ⊕ c1•(x128 mod P)
[c2:c1] := [A2:A1] ⊕ [M2:M1]
Шаг 3. Сдвиги,
[c2:c1] := с2•(x128 mod P) ⊕ с1•(x64 mod P)
Шаг 4. Редуцирование
[T2:T1] := c2•Ux
[c2:c1] := T2•Px ⊕ [c2:c1]
Возвращает: crc = c1
CRC-64/WE poly=0x42F0E1EBA9EA3693
init=0xFFFFFFFFFFFFFFFF refin=false refout=false xorout=0xFFFFFFFFFFFFFFFF check=0x62EC59E3F1A4F00A
POLY=0x42F0E1EBA9EA3693
Таблица умножения:
0x0000000000000000, 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26, 0xC711223CFA3E5BB5,
0x493366450E42ECDF, 0x0BC387AEA7A8DA4C, 0xCCD2A5925D9681F9, 0x8E224479F47CB76A,
0x9266CC8A1C85D9BE, 0xD0962D61B56FEF2D, 0x17870F5D4F51B498, 0x5577EEB6E6BB820B,
0xDB55AACF12C73561, 0x99A54B24BB2D03F2, 0x5EB4691841135847, 0x1C4488F3E8F96ED4,
Barrett u = x^128/P(x) Ux = 0x1578D29D06CC4F872 Px = 0x142F0E1EBA9EA3693
[1/p]*p(x) = 0x1000000000000000005F5C3C7EB52FAB6
Test =62EC59E3F1A4F00A ..ok
K5( 64) = 42F0E1EBA9EA3693
K4(128) = 05F5C3C7EB52FAB6
K3(192) = 4EB938A7D257740E
Вычисление CRC по обному биту
Не знаю какой в этом смылсл, если мы только что представили вычисление CRC по 128 бит за цикл. НО хочется вернуться к истокам. Рассмотрим под микроскопом каждый отдельный бит. Как выглядит операция CRC над битами. Прежде всего можно ввести операцию сдвиг-редуцирование, как основа для построения более сложных выражений:XT(с) := MSB(c)==1? (с<<1)^Px: (c<<1);Такая же операция для отраженного полинома выглядит так:
XT(с) := LSB(c)==1? (с>>1)^Pr: (c>>1);У операции есть свойство группы, которое позволяет выполнять оптимизации:
XT(a ⊕ b) == XT(a) ⊕ XT(b)Опрерация обновления CRC может быть представлена в виде:
Cn := XT(Cn-1 ⊕ dn<<(N-1)), где N -разрядность CRCМожно упростить, раскрыв скобки
Cn := XT(Cn-1) ⊕ dn•Px, где N -разрядность CRCДля двух бит получаем выражение:
Cn+1 := X2•Cn-1 ⊕ [dn+1,dn]•PxМожно продолжить, так выведен алгоритм с таблицей умножения 4 бит.
Cn+3 := X4•Cn-1 ⊕ [dn+3..dn]•PxИЛИ
CRC = (CRC<<4) ^ PMUL(CRC>>(N-4) ^ Data, Px)где PMUL -- операция полиномиального умножения и редуцирования. Умножение на полином Px - это по сути - сдвиг.
Cn+3 := X4•Cn-1 ⊕ [dn+3..dn]•XN
[05.01.2020]
Я увидел возможность для дальнейшей оптимизации алгоритма расчета CRC за счет увеличения разрядности редуцирования до 64бит. При этом можно сократить число сдвиговых операций(операций умножения) при редуцировании. Для этого необходимо пересчитать константы Барретта с увеличением разрядности до 64.Алгоритм №. Векторный алгоритм CRC-32 отраженный порядок
Шаг 1. начальное значение
[с4:c3:c2:c1] := [0:0:0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит, кроме последнего
[с4:c3:c2:c1] := [с4:c3:c2:c1] ⊕ [M4:M3:M2:M1]
[с4:c3:c2:c1] := [c2:c1]•(x31+128 mod P) ⊕ [c4:c3]•(x31+64 mod P)
Шаг 3. Загрузить последний фрагмент
[с4:c3:c2:c1] := [с4:c3:c2:c1] ⊕ [M4:M3:M2:M1]
[c3:c2:c1] := [c2:с1]•(x31+64 mod P) ⊕ [с4:c3]•(x31 mod P)
Шаг 4. Редуцирование
[T4:T3:T2:T1] := [c2:c1]•Ur
[c3:c2:c1] := [T2:T1]•Pr ⊕ [c3:c2:c1]
Возвращает: crc = c3
CRC-32B Zlib CRC-32/ISO-HDLC
poly=0x04C11DB7 refin=true refout=true check=0xCBF43926
Ur = 0xB4E5B025F7011641 Pr = 0x1DB710641
CRC-32C (Castagnoli)
poly=0x1EDC6F41 refin=true refout=true check=0xE3069283
Ur = 0x4869EC38DEA713F1 Pr = 0x105EC76F1
CRC-32K (Koopman) BACnet
poly=0x741B8CD7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0x2D3DD0AE
Ur = 0xC25DD01C17D232CD Pr = 0x1D663B05D
Алгоритм №. Векторный алгоритм CRC-16 отраженный порядок
Шаг 1. начальное значение
[с8...c1] := [0:0:0:0:0:0:0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит, кроме последнего
[с8...c1] := [с8...c1] ⊕ [M8...M1]
[с8...c1] := [c4...c1]•(x15+128 mod P) ⊕ [c8...c5]•(x15+64 mod P)
Шаг 3. Загрузить последний фрагмент
[с8...c1] := [с8...c1] ⊕ [M8...M1]
[c5...c1] := [c4...с1]•(x15+64 mod P) ⊕ [с8...c5]•(x15 mod P)
Шаг 4. Редуцирование
[T8...T1] := [c4...c1]•Ur
[c5...c1] := [T4...T1]•Pr ⊕ [c5...c1]
Возвращает: crc = c5
Алгоритм №. Векторный алгоритм CRC-8 отраженный порядок
Шаг 1. начальное значение
[с16...c1] := [0...0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит, кроме последнего
[с16...c1] := [с16...c1] ⊕ [M16...M1]
[с16...c1] := [c8...c1]•(x7+128 mod P) ⊕ [c16...c9]•(x7+64 mod P)
Шаг 3. Загрузить последний фрагмент
[с16...c1] := [с16...c1] ⊕ [M16...M1]
[c9...c1] := [c8...с1]•(x7+64 mod P) ⊕ [с16...c9]•(x7 mod P)
Шаг 4. Редуцирование
[T16...T1] := [c8...c1]•Ur
[c9...c1] := [T8...T1]•Pr ⊕ [c9...c1]
Возвращает: crc = c9
CRC-8/BAC POLY=0x81 refin=true refout=true
Ur = 0x808182878899AAFF(64 бита) Pr=0x103 (9 бит)
X7 mod P = 0x01
X71 mod P = 0x81
X135 mod P = 0xC1
Алгоритм №. Векторный алгоритм CRC-64 отраженный порядок
Шаг 1. начальное значение
[с2:c1] := [0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит, кроме последнего
[с2:c1] := [с2:c1] ⊕ [M2:M1]
[с2:c1] := c1•K1 ⊕ c2•K2
Шаг 3. Загрузить последний фрагмент
[с2:c1] := [с2:c1] ⊕ [M2:M1]
[c2:c1] := с1•K3 ⊕ с2•K4
Шаг 4. Редуцирование
[T2:T1] := c1•Ur
[c2:c1] := T1•Pr ⊕ [c2:c1]
Возвращает: crc = c2
Алгоритм №. Векторный алгоритм CRC-64 отраженный порядок
Шаг 1. начальное значение
[с2:c1] := [0:crc]
Шаг 2. Цикл для каждого фрагмента 128-бит, кроме последнего
[с2:c1] := [с2:c1] ⊕ [M2:M1]
[с2:c1] := c1•K1 ⊕ c2•K2
Шаг 3. Загрузить последний фрагмент k = (length & 15)
[с2:c1] := [с2:c1] ⊕ [M2:M1]
[c2:c1] := с1•K3(k) ⊕ с2•K4(k)
Шаг 4. Редуцирование
[T2:T1] := c1•Ur
[c2:c1] := T1•Pr ⊕ [c2:c1]
Возвращает: crc = c2
Наборы констант для CRC-16/X-25 BACnet с отраженным порядком
poly=0x1021 init=0xffff refin=true refout=true xorout=0xffff check=0x906e
K1, K2:{0x8E10, 0x81BF} // x^{143}, x^{79}
K3, K4:
[ 1] = {0x4EA8, 0x97B7},// x^{-41},x^{-105}
[ 2] = {0x290C, 0xC1A3},// x^{-33},x^{-97}
[ 3] = {0xCA45, 0x9750},// x^{-25},x^{-89}
[ 4] = {0x1563, 0x5212},// x^{-17},x^{-81}
[ 5] = {0x5188, 0x33C1},// x^{-9}, x^{-73}
[ 6] = {0x0811, 0xD7B6},// x^{-1}, x^{-65}
[ 7] = {0x0100, 0xD06A},// x^{ 7}, x^{-57}
[ 8] = {0x0001, 0xCC8C},// x^{15}, x^{-49}
[ 9] = {0x1189, 0x4EA8},// x^{23}, x^{-41}
[10] = {0x19D8, 0x290C},// x^{31}, x^{-33}
[11] = {0x5ADC, 0xCA45},// x^{39}, x^{-25}
[12] = {0x1CBB, 0x1563},// x^{47}, x^{-17}
[13] = {0x0B44, 0x5188},// x^{55}, x^{-9}
[14] = {0x042B, 0x0811},// x^{63}, x^{-1}
[15] = {0x9FD5, 0x0100},// x^{71}, x^{ 7}
[ 0] = {0x81BF, 0x0001},// x^{79}, x^{15}
Ur=0x859B040B1C581911 Pr=0x10811
[24.04.2021]
Нашел способ использовать один алгоритм с разрядностью 64 бита для расчета CRC-16/CRC-24/CRC-32/CRC-64. Фактически можно использовать алгоритм CRC-64 без изменения со своим набором констант для расчета контрольных сумм меньшей разрядности, например CRC-16. При этом используется правило:
C = A mod P => C•K = A•K mod P•KВ нашем случае К - это свдиг влево на (64-16=48) бит.
Алгоритм №. Векторный алгоритм CRC-64 прямой порядок
Шаг 1. начальное значение
[с2:c1] := [crc<<(64-N):0]
Шаг 2. Цикл для каждого фрагмента 128-бит, кроме последнего
[с2:c1] := [с2:c1] ⊕ [M2:M1]
[с2:c1] := c2•K2 ⊕ c1•K1
Шаг 3. Загрузить последний фрагмент k = (length & 15)
[с2:c1] := [с2:c1] ⊕ [M2:M1]
[c2:c1] := с2•K4(k) ⊕ с1•K3(k)
Шаг 4. Редуцирование
[T2:T1] := c2•Ux ⊕ [c2:c1]
[c2:c1] := T2•Px ⊕ [c2:c1]
Возвращает: crc = c1>>(64-N)
Наборы констант для CRC-16
poly=0x1021 init=0xffff refin=false refout=false xorout=0xffff check=0xd64e
K1, K2:{0xAEFC, 0x650B},// x^{128}, x^{192}
K3, K4:
[ 1] = {0xCBF3000000000000, 0x2AE4000000000000},// x^{-104}, x^{-40}
[ 2] = {0x9B27000000000000, 0x6128000000000000},// x^{-96}, x^{-32}
[ 3] = {0x15D2000000000000, 0x5487000000000000},// x^{-88}, x^{-24}
[ 4] = {0x9094000000000000, 0x9D71000000000000},// x^{-80}, x^{-16}
[ 5] = {0x17B9000000000000, 0x2314000000000000},// x^{-72}, x^{-8}
[ 6] = {0xDBD6000000000000, 0x0001000000000000},// x^{-64}, x^{ 0}
[ 7] = {0xAC16000000000000, 0x0100000000000000},// x^{-56}, x^{ 8}
[ 8] = {0x6266000000000000, 0x1021000000000000},// x^{-48}, x^{16}
[ 9] = {0x2AE4000000000000, 0x3331000000000000},// x^{-40}, x^{24}
[10] = {0x6128000000000000, 0x3730000000000000},// x^{-32}, x^{32}
[11] = {0x5487000000000000, 0x76B4000000000000},// x^{-24}, x^{40}
[12] = {0x9D71000000000000, 0xAA51000000000000},// x^{-16}, x^{48}
[13] = {0x2314000000000000, 0x45A0000000000000},// x^{-8}, x^{56}
[14] = {0x0001000000000000, 0xB861000000000000},// x^{ 0}, x^{64}
[15] = {0x0100000000000000, 0x47D3000000000000},// x^{ 8}, x^{72}
[ 0] = {0x1021000000000000, 0xEB23000000000000},// x^{16}, x^{80}
Ur=0x11303471A041B343 Pr=0x1021000000000000
Наборы констант для CRC-24/OpenPGP
poly=0x864cfb init=0xb704ce refin=false refout=false xorout=0x000000 check=0x21cf02
K1, K2:{0x6243DA, 0xB22B31},// x^{128}, x^{192}
K3, K4:
[ 1] = {0x2471670000000000, 0x7190920000000000},// x^{-96}, x^{-32}
[ 2] = {0xEE50080000000000, 0xC6E2490000000000},// x^{-88}, x^{-24}
[ 3] = {0xCE8F4A0000000000, 0xD19E9A0000000000},// x^{-80}, x^{-16}
[ 4] = {0x1D1CA30000000000, 0xF77C040000000000},// x^{-72}, x^{-8}
[ 5] = {0x6DC6AA0000000000, 0x0000010000000000},// x^{-64}, x^{ 0}
[ 6] = {0x67F3180000000000, 0x0001000000000000},// x^{-56}, x^{ 8}
[ 7] = {0x79152C0000000000, 0x0100000000000000},// x^{-48}, x^{16}
[ 8] = {0xE2DD700000000000, 0x864CFB0000000000},// x^{-40}, x^{24}
[ 9] = {0x7190920000000000, 0x668F480000000000},// x^{-32}, x^{32}
[10] = {0xC6E2490000000000, 0x8309D70000000000},// x^{-24}, x^{40}
[11] = {0xD19E9A0000000000, 0x3609520000000000},// x^{-16}, x^{48}
[12] = {0xF77C040000000000, 0xD9FE8C0000000000},// x^{-8}, x^{56}
[13] = {0x0000010000000000, 0x36EB3D0000000000},// x^{ 0}, x^{64}
[14] = {0x0001000000000000, 0x3B918C0000000000},// x^{ 8}, x^{72}
[15] = {0x0100000000000000, 0xF50BAF0000000000},// x^{16}, x^{80}
[ 0] = {0x864CFB0000000000, 0xFD7E0C0000000000},// x^{24}, x^{88}
Ur=0xF845FE2493242DA4 Pr=0x864CFB0000000000
Наборы констант для CRC-32/BZIP2
poly=0x04c11db7 init=0xffffffff refin=false refout=false xorout=0xffffffff check=0xfc891918
K1, K2:{0xE8A45605, 0xC5B9CD4C},// x^{128}, x^{192}
K3, K4:
[ 1] = {0x052B9A0400000000, 0x876D81F800000000},// x^{-88}, x^{-24}
[ 2] = {0x3C5F6F6B00000000, 0x1ACA48EB00000000},// x^{-80}, x^{-16}
[ 3] = {0xBE519DF400000000, 0xA9D3E6A600000000},// x^{-72}, x^{-8}
[ 4] = {0xD02DD97400000000, 0x0000000100000000},// x^{-64}, x^{ 0}
[ 5] = {0x3C423FE900000000, 0x0000010000000000},// x^{-56}, x^{ 8}
[ 6] = {0xA3011FF400000000, 0x0001000000000000},// x^{-48}, x^{16}
[ 7] = {0xFD7384D700000000, 0x0100000000000000},// x^{-40}, x^{24}
[ 8] = {0xCBF1ACDA00000000, 0x04C11DB700000000},// x^{-32}, x^{32}
[ 9] = {0x876D81F800000000, 0xD219C1DC00000000},// x^{-24}, x^{40}
[10] = {0x1ACA48EB00000000, 0x01D8AC8700000000},// x^{-16}, x^{48}
[11] = {0xA9D3E6A600000000, 0xDC6D9AB700000000},// x^{-8}, x^{56}
[12] = {0x0000000100000000, 0x490D678D00000000},// x^{ 0}, x^{64}
[13] = {0x0000010000000000, 0x1B280D7800000000},// x^{ 8}, x^{72}
[14] = {0x0001000000000000, 0x4F57681100000000},// x^{16}, x^{80}
[15] = {0x0100000000000000, 0x5BA1DCCA00000000},// x^{24}, x^{88}
[ 0] = {0x04C11DB700000000, 0xF200AA6600000000},// x^{32}, x^{96}
Ur=0x04D101DF481B4E5A Pr=0x04C11DB700000000
