Что такое код udm_crc32

Содержание

Crc-32

11.02.2012, 22:06

Расчет CRC
С Наступающим форумчане. ) подскажите пожалуйста можно ли как-то расcчитать CRC для многобайтового.

CRC-16 для файла
Есть код для подсчета crc16 (Modbus) для бинарного файла, если файл превышает заданный размер.

Подсчет CRC заданной структуры
Добрый день, есть стандартная функция подсчета контрольной суммы (взято с вики): unsigned short.

Контрольная Сумма (CRC, MD5)
Здраствуйте дорогие программисты. Вот в чём проблема!! Есть такая програмка.

CRC-контрольная сумма отправляемого сообщения
Здравствуйте. У меня такая проблема: я не очень разбираюсь в программирование, а начальство дало.

12.02.2012, 11:52 2 12.02.2012, 21:35 [ТС] 3 12.02.2012, 21:35

CRC
Помогите, пожалуйста, с CRC. А то я уже для CRC16 давно сделал, а для CRC32 уже неделю бьюсь(((.

CRC 16
Собсна есть алгоритм на C,но проблема в том что C я не знаю :D может есть у кого на C# или скилл.

STM32F030 CRC
Добрый день! У меня не сходится аппаратный расчет CRC. Полином фиксированный 0x4C11DB7 Начальное.

Что такое код udm_crc32

by Clifford M. Roche

Предисловие

В этой статье я намерен передать основные аспекты CRC32 алгоритма. Это относительно простая статья, прежде всего источник информации — демо для Borland C++ и MSVC++ NET. (которые должны быть легко переносимы на MSVC++6) также доступен с настоящей статьей.

Небольшое понимание математики (многочлен деления) было бы полезно, но я пишу эту статью так, чтобы оно не потребовалось. Вы, однако, должны понимать C++ — это само собой подразумевается.

Зачем использовать CRC32?

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

Есть несколько способов, которыми я могу проверить целостность файлов и решить, требуется ли обновить их с главного сервера. Приходят на ум время создания/таймстамп, размер файла и CRC32. Есть и некоторые, очевидно, более сложные способы, такие как учет файлов в базе данных, однако нет необходимости слишком всё усложнять. То же самое касается большинства видов применения CRC32 в играх. Кроме того, большинство из более сложных алгоритмов примеряют гораздо больше вычислений, чем CRC32.

CRC32, изо всех представленных вариантов, в настоящее время является наиболее приемлемым, поскольку вам не придется беспокоиться о файлах, которые имеют одинаковый размер или дату изменения (очень часто такое бывает с растровыми изображениями, а также несколькими другими распространенными типами игровых файлов) и у нас нет повода беспокоиться о неточном времени создания файла/таймстампа из-за их изменения. Хотя CRC32 не совершенный алгоритм, и всегда есть шанс, что 2 файла будет иметь одинаковое значение CRC32, случаи эти настолько редки, что CRC32 становится идеальным кандидатом для генерации подписи файла.

CRC32 значение содержит 32-битное (4-байтовое) число (также известное как подпись), что однозначно определяет указанный кусок данных. Преимуществом CRC32 для контрольных подписей является и то, что его алгоритм устроен так, что небольшие изменения в файле (будь то изменение, удаление или вставка) должны вызывать большие изменения в подписи CRC32. CRC32 имеет 2 ^ 32 возможных значений; в общей сложности 4.294967E +09.

По этим причинам подписи CRC32 очень полезны в играх, так как оставляет нам простор для творчества. Они могут быть использованы для проверки файлов, чтобы увидеть, были ли изменены, чтобы помочь предотвратить попытки взлома игры с целью читерства, или они могут быть использованы для проверки файлов или данных, которые передаются по интернету во время игры, такие как файл карты, например.

Как CRC32 работает?

CRC32 это несколько сложный процесс, и состоит он из многих математических операций. Но вот как он, как правило, работает:

Сначала мы собираемся взять значение многочлена, и с этим значением мы генерируем CRC32 поиска. В конце этой статьи я покажу, как правильно создать обзорную таблицу с данным многочленом. Далее мы возьмём данные, для которых хотим сгенерировать подпись CRC32, и специальная функция сгенерирует обновлённое значение CRC32 для каждого байта в файле, строке или структуре, которую мы проверяем. Это делается для каждого байта в строке, структуре или файле. После завершения самое обновлённое значение становится подписью.

Сердце алгоритма CRC32 — простая система, которая принимает переданный байт для вычисления из набора данных, и текущее значение CRC32, которое есть у нас, и выполняет поиск в нашей обзорной таблице. Если нет текущего значения CRC32, мы должны использовать 0xFFFFFFFF. Немного математики, а именно — многочлен деления, и функция вернет обновленное значение CRC32.

Реализация очень проста.

Класс

Так наш класс будет выглядеть.

><
public :
static DWORD CRC32ByString ( LPCTSTR , DWORD & ) ;
static DWORD CRC32ByFile ( LPCTSTR , DWORD & ) ;
static DWORD CRC32ByStruct ( BYTE *, DWORD , DWORD & ) ;

private :
static bool GetFileSize ( HANDLE , DWORD & ) ;
static inline void GetCRC32 ( BYTE , DWORD & ) ;

static DWORD CRC32Table [ 256 ] ;
> ;

Всё просто — у нас есть функция для каждого типа данных, который мы планируем использовать, которая будет генерировать для них CRC32 подписи. У нас также есть две приватные функций, одна будет вычислять размер файла — необходимо для правильной работы внутренних алгоритмов, вторая для выполнения другой математики и обновления значения CRC32 для конкретного байта.

Существует также один статический массив, он просто хранит для нас таблицу CRC32. На самом деле вам не нужно хранить эту таблицу постоянно, если не хотите. Используя конструктор и деструктор, вы можете создавать и очищать таблицу только тогда, когда планируете использовать её. Для наших целей более целесообразно использовать таблицу, так как это может значительно уменьшить время обработки.

Создание таблицы подстановки

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

Следовательно, этот многочлен также используется многими другими приложениями и системами, такими как WinZip, PKZip, и Ethernet.

Примечание: Вам нужно будет генерировать таблицу по крайней мере один раз, даже если вы используете фиксированную таблицу. Если, конечно, вы используете таблицу, представленную в моём демо.

Прежде чем продолжить — стандартные CRC состояния, которые мы должны отражать значениями в нашей таблице поиска, что может быть сделано, отражая многочлен. В этом случае 0x04c11db7 становится 0xedb88320. Хотя некоторые уравнения будут отражать значения в таблице, поскольку они их и создают, я собираюсь отражать многочлен. В конечном счёте это заканчивается лишь тем, что мы используем меньше строк кода.

Примечание: Отражение — это простой процесс реверса бинарной структуры данного бинарного сегмента. Например, 10100111 станет при отражении 11100101.

DWORD dwPolynomial = 0xEDB88320 ;
DWORD * CRC32Table = NULL ;

CRC32Table = new DWORD [ 256 ] ;

DWORD dwCRC ;
for ( int i = 0 ; i 256 ; i ++ )
<
dwCRC = i ;

CRC32Table [ i ] = dwCRC ;
>

Простой цикл через все 256 записей и создав значения поиска, основанного на позиции в таблице многочлена.

В зависимости от вашей ситуации вы можете хотеть или не хотеть тратить циклы процессора, чтобы сохранить регенерирующую таблицу каждый раз, когда Вы хотите создать подпись. Если это ваш случай, просто выделите этот код в отдельное приложение, сохраняйте дамп таблиц в файл, на экран, или где вам наиболее удобно, и копируйте и вставляйте значения прямо в таблицу. Хотя и ценой 256 * 4 байт памяти (что на самом деле не много), вы резко улучшите врёмя расчета без необходимости постоянно пересчитывать таблицы.

Для тех из вас, кто пытается создать таблицу использованием полиномиальных перечисленных выше первых 14 значений должен выглядеть следующим образом:

Рассчет CRC32

Имея таблицу поиска, мы можем взглянуть на функцию GetCRC32. Эта функция принимает один байт и предыдущее вычисленное значение CRC32 (если таковое существует).

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

Обратите внимание: использование встроенных функций не следует воспринимать легкомысленно. Это может привести к весьма значительному увеличению объема итогового кода и может в конечном итоге счёте привести к снижению общей производительности приложения, потребляя слишком много памяти (что что приводит к недостатку ресурсов и ошибкам во время выполнения приложения). В нашей ситуации GetCRC32 вызывается весьма ограниченно и, таким образом, общий размер приложения не имеет значения.

Вы также можете посмотреть на спецификацию __fastcall. __fastcall работает путем передачи аргументов в функцию через регистры процессора, в отличие от стандартного способа прохождения их через стек. Это может привести к заметному увеличению скорости так же, как это делает inline.

С переданным байтом и предыдущим его CRC32 значением функциия выполняет деление многочлена, со ссылкой ссылкой на таблицу, и обновление CRC32 подписи.

Расчет для структур

Две предыдущих основные функции — ядро нашего CRC32 алгоритма. Все, что осталось сделать — прочитать данные и, используя эти две функции, создать CRC32 подпись для них.

DWORD ECRC32 :: CRC32ByStruct ( BYTE * byStruct , DWORD dwSize , DWORD & dwCRC32 ) <

// MAKE SURE WE HAVE A VALID BYTE STREAM
if ( byStruct == NULL ) <
return — 1 ;
>

// LOOP TO READ THE STRUCTURE
for ( DWORD i = 0 ; i dwSize ; i ++ ) <
GetCRC32 ( * byStruct , dwCRC32 ) ;
byStruct ++;
>

// FINISH UP
dwCRC32 =

dwCRC32 ;
return 0 ;
>

Функция принимает в BYTE указатель на базовый адрес структуры, и проходит в цикле через каждый байт этой структуры, передавая значение каждого байта в GetCRC32 вместе с предыдущим значением CRC32. В ситуации, когда предыдущие CRC32 значение неизвестно, мы просто присваиваем значение 0xFFFFFFFF.

Перед заполнением структуры с данными, которые будут обработаны, очень важно, инициализировать всю структуру в NULL, потому что структуры, как правило, дополняются до 8 байт. Другими словами, если у вас есть структура, которая имеет 7 символов (7 байт), sizeof(структура) вернёт 8 байт. Последний бит будет инициализирован как «мусорное» значение и не может быть такими же, если вы воссоздать структуру позже с теми же данными. Это будет изменять итоговое значение CRC32. Существует еще один вариант — при передаче размера структуры, если вы знаете точный размер структуры без разделителя, вы можете использовать это значение, что заставит наш алгоритм игнорировать любые дополнительные байты-разделители. Однако не следует смешивать два метода, поскольку это будет приводить к различным несовпадениям CRC32 значения двух идентичных структур.

Расчет для файла

Расчет подписи CRC для файла очень похож, и хотя функция, делающая это, кажется несколько более сложной — в действительности это не так. Однако мы должны добавить дополнительную функцию, которая будет вычислять размер файла перед обработкой.

// NOW WE CAN GET THE FILE SIZE
bool bException = false ;
dwSize = 0 ;

try <
// SETS THE UPPER AND LOWER SIZE VALUES
dwSize = GetFileSize ( hFile , NULL ) ;

if ( dwSize == INVAL >) <
bException = true ;
dwSize = 0 ;
>
>

// SOMETHING SCREWED UP
catch ( . ) <
bException = true ;
>

Эта функция вызывается внутри CRC32ByFile, поэтому мы не должны о ней сильно беспокоиться. Что происходит в идеале — после того, как CRC32ByFile открыла указанный файл (успешно, мог бы я добавить), будет сделана попытка передать указатель файла и указатель на DWORD, который вернет рассчитанный размер. Функция возвращает true, если это удалось.

Следующий код на самом деле читает файл и передает данные в наш CRC32 алгоритм.

// OPEN THE SPECIFIED FILE
if ( ( hFile = CreateFile ( strFileName , GENERIC_READ ,
FILE_SHARE_READ , NULL , OPEN_EXISTING , FILE_ATTRIBUTE_NORMAL
| FILE_FLAG_SEQUENTIAL_SCAN , NULL ) ) == INVAL >) <
// THIS MEANS THAT WE HAVE AN ERROR
dwErrorCode = — 1 ;
>

// CALCULATE THE CRC32 SIGNATURE
else <
BYTE cBuffer [ 512 ] ;
DWORD dwBytesInOut , dwLoop ;
bool bSuccess = false ;

bSuccess = ReadFile ( hFile , cBuffer , sizeof ( cBuffer ) ,
& dwBytesInOut , NULL ) ;

while ( bSuccess && dwBytesInOut ) <
for ( dwLoop = 0 ; dwLoop dwBytesInOut ; dwLoop ++ ) ;
GetCRC32 ( cBuffer [ dwLoop ] , dwCRC32 ) ;
bSuccess = ReadFile ( hFile , cBuffer , sizeof ( cBuffer ) , & dwBytesInOut , NULL ) ;
>
>

Это небольшой фрагмент кода из функции, представленой в демо, который принимает файл, открывает его, заполняет буфер данными, вычисляет CRC32-значение для этих данных и повторяется, пока не дойдёт до конца файла.

Другие применения CRC

CRC32, как и в играх, также используется вне игр по тем же причинам — для проверки целостности файлов и данных, когда они каким-то способом копируются.

Великолепное расширение подобного метода использования, которое также широко используются в играх, будет добавить значение CRC32 в пакеты, которые вы посылаете по Интернету; это гарантирует, что данные, которые поступают в место назначения — те же, какими были перед отправкой. Хотя TCP и UDP протоколы хранят значения CRC в заголовках, они будут только проверять, как передаётся каждый пакет. Структуры и данные, которые отправляются в нескольких пакетах, могут в итоге прийти повреждёными и использованными в таком виде без проверки CRC.

CRC может даже быть использована в целях безопасности, чтобы убедиться, что текстовые сообщения и другие типы сообщений не изменены намеренно. Это система, которая обычно используется в PGP при подписании сообщения таким образом, что получающая сторона может проверить, что оно было отправлено действительно вами, тем, кто его подписал. PGP не использует CRC32 для создания подписей, алгоритм CRC32 несколько слаб для таких ситуаций. Другие общие алгоритмы, используемые для этих целей — это MD5, SHA8, SHA256 и т.д. Они называются HASH-алгоритмы и используются обычно в целях безопасности.

Если вам нужно использовать генератор подписей, который производит большее количество значений, чем CRC32 и должен иметь большую, чем CRC32, точность, обратите внимание на эти три алгоритма.

И наконец, если у вас есть какие-либо замечания, вопросы, и так далее, вы легко можете найти меня в irc на канале #gamedev под ником kurifu или seta.

Что такое CRC?

— Помнишь, в школе всякой ерундой маялись типа «загадай число, сделай то, сделай это, а сейчас я его угадаю!»

— Возьми любой файл. Вычисли его CRC32. Допиши его в конец файла в обратном порядке (например, 3432AA8D как 8DAA3234). Вычисли CRC32 получившегося файла. Это магия! Я угадаю его! Оно равно 2144DF1C.

— Ого. Ты владеешь черной магией.

По мотивам bash.org.ru

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

Расшифровывается эта аббревиатура как cyclic redundancy check, или, говоря по-русски, циклический избыточный код. Может показаться, что за таким сложным и громоздким названием кроется что-то очень сложное, но на самом деле, с точки зрения конечного пользователя, всё предельно просто. CRC — это просто контрольное значение, которое способно служить подтверждением целостности данных.

Ключи CRC могут быть разной длины. Как правило, наиболее широко используются 16-, 32- и 64-битные ключи. Впрочем, также достаточно часто применяются и ключи другой длины — например, 12-битные. Существует множество различных алгоритмов вычисления CRC, которые, кстати, как ни странно, до сих пор до конца не стандартизованы. По сути, все алгоритмы заключаются в делении с остатком многочлена, соответствующего входным данным, на некоторый заранее известный делитель. Степень полинома, генерируемого из входных данных, должна быть равна длине контрольной суммы, то есть, например, при использовании CRC16 нужно генерировать многочлен 16-й степени.

Суть использования CRC заключается в том, что вероятность получения точно такого же CRC при какой-либо перестановке в исходных данных исчезающе мала, то есть, фактически, в обычной жизни CRC стопроцентно гарантирует сохранность и уникальность полученных данных. Например, вероятность того, что случайно измененные данные будут иметь такое же CRC, как и исходные, в случае с использованием 64-битной контрольной суммы будет равна 5•10 -20 .

Как просто посчитать контрольную сумму CRC (CRC32 — CRC16 — CRC8)

Для начала давайте немного разберёмся в теории. Итак, что же такое CRC? Если кратко, это одна из разновидностей подсчёта контрольной суммы. Контрольная сумма — это метод проверки целостности принятой информации на стороне приёмника при передаче по каналам связи. Например, одна из простейших проверок — использование бита чётности. Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной — то 1. При приёме также подсчитывается сумма битов сообщения, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче возникли ошибки, и передаваемая информация была искажена.

Но такой способ определения наличия ошибок — очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более «продвинутых» проверок, в том числе CRC.

По сути, CRC — это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее — остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют «контрольная сумма». В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.

Прежде чем приступать к вычислению CRC, понадобится ещё немного теории.
Что такое исходное сообщение должно быть понятно. Это непрерывная последовательность битов произвольной длины.

Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту — 8, 16 и 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.

Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x^8 + x^2 + x^1 + x^0. Здесь степень числа «x» означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число — это не что иное как (1)00000111 в двоичной системе счисления, или 7 в десятичной. В скобках я указал подразумеваемый старший разряд числа.
Вот ещё пример: x^16 + x^15 + x^2 + x^0 = (1)1000000000000101″ = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC.

Так как же считать контрольную сумму? Существует базовый метод — деление сообщения на полином «в лоб» — и его модификации в целях уменьшения количества вычислений и, соответственно, ускорения расчёта CRC. Мы рассмотрим именно базовый метод.

В общем виде, деление числа на многочлен выполняется по такому алгоритму:
1) создаётся массив (регистр), заполненный нулями, равный по длине разрядности полинома;
2) исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома;
3) в младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит;
4) если выдвинутый бит равен «1», то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме;
5) если в сообщении ещё есть биты, переходим к шагу 3);
6) когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.

Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x^8 + x^2 + x^1 + x^0.

Осталась ещё пара дополнительных штрихов. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.
Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число.

Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC могут делить на какое-то другое число.

И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом «вперёд», так и наоборот, младшим.

На основании всего вышеизложенного, давайте напишем функцию на языке Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.

Public Shared Function GetCrc(ByVal bytes As Byte(), ByVal poly As UInteger, Optional ByVal w >
Dim w >
‘Дополняем сообщение width нулями (расчёт в байтах):
ReDim Preserve bytes(bytes.Length — 1 + widthInBytes)

‘Создаём очередь битов из сообщения:
Dim msgFifo As New Queue(Of Boolean)(bytes.Count * 8 — 1)
For Each b As Byte In bytes
Dim ba As New BitArray()
If reverseBytes Then
For i As Integer = 0 To 7
msgFifo.Enqueue(ba(i))
Next
Else
For i As Integer = 7 To 0 Step -1
msgFifo.Enqueue(ba(i))
Next
End If
Next

‘Создаём очередь из битов начального заполнения регистра:
Dim initBytes As Byte() = BitConverter.GetBytes(initReg)
Dim initBytesReversed As IEnumerable(Of Byte) = (From b As Byte In initBytes Take widthInBytes).Reverse
Dim initFifo As New Queue(Of Boolean)(width — 1)
For Each b As Byte In initBytesReversed
Dim ba As New BitArray()
If Not reverseBytes Then
For i As Integer = 0 To 7
initFifo.Enqueue(ba(i))
Next
Else
For i As Integer = 7 To 0 Step -1
initFifo.Enqueue(ba(i))
Next
End If
Next

‘Сдвиг и XOR:
Dim register As UInteger = 0 ‘заполняем width-разрядный регистр нулями.
Do While msgFifo.Count > 0

Dim poppedBit As Integer = CInt(register >> (width — 1)) And 1 ‘определить перед сдвигом регистра.

Dim shiftedBit As Byte = Convert.ToByte(msgFifo.Dequeue)
If initFifo.Count > 0 Then
Dim b As Byte = Convert.ToByte(initFifo.Dequeue)
shiftedBit = shiftedBit Xor b
End If

register = register > (32 — width)) ‘маскируем младшие разряды.

Что такое код udm_crc32

Понятие циклические коды достаточно широкое [3] . В англоязычной литературе CRC расшифровывается двояко в зависимости от контекста: Cyclic Redundancy Code или Cyclic Redundancy Check [4] . Под первой расшифровкой понимают математический феномен циклических кодов, под второй — конкретное применение этого феномена как хэш-функции.

Помехоустойчивое кодирование

Первые попытки создания кодов с избыточной информацией начались задолго до появление современных ПК. К примеру, ещё в шестидесятых годах прошлого века Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекампа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих прием RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).

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

Контрольная сумма

В самом общем своем виде контрольная сумма представляет собой некоторое значение, построенное по определенной схеме на основе кодируемого сообщения. Проверочная информация при систематическом кодировании дописывается в конец сообщения — после полезных данных. На принимающей стороне абонент знает алгоритм вычисления контрольной суммы: соответственно, программа имеет возможность проверить корректность принятых данных.

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

Математическое описание

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

Каждой конечной последовательности битов взаимно однозначно сопоставляется двоичный полином , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

Количество различных многочленов степени меньшей равно , что совпадает с числом всех двоичных последовательностей длины .

Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

— многочлен, представляющий значение CRC. — многочлен, коэффициенты которого представляют входные данные. — порождающий многочлен. — степень порождающего многочлена.

Умножение осуществляется приписыванием нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2 N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хэш-функции в контексте каждого конкретного применения.

Тем не менее, существует множество стандартизированных образующих многочленов, обладающих хорошими математическими и корреляционными свойствами (минимальное число коллизий, простота вычисления). В статье приведены некоторые из них, а также соответствующие реализации на языке Си.

Вычисление CRC

Параметры алгоритма

Говоря о формировании контрольной суммы CRC, в первую очередь нужно упомянуть о полиноме-генераторе. Существует огромное множество многочленов, участвующих в формировании cyclic reduntancy code; многие из них указаны в конце статьи.

Другим параметром конкретного алгоритма вычисления контрольной суммы является размер слова, или суммарное количество регистров — информационных ячеек, используемых для вычисления численного значения хэша. При этом обязательно учитывается то, что размер слова и степень образующего контрольную сумму полинома совпадают. На практике более всего распространены 8, 16 и 32 — битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.

И последний параметр, важный при описании определенной методики — начальные состояния регистров (стартовое слово). Это последняя из трех значимых характеристик; зная их в совокупности, мы можем восстановить алгоритм вычисления CRC, если данная модификация методики не имеет специфических особенностей, таких, как обратный порядок обработки битов.

Описание процедуры

Из файла берется первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старый старший бит, а младший бит освобождается — его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

Наиболее используемые и стандартизованные полиномы

В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу. [1] [5]

Этот парадокс касается и выбора многочлена-генератора: зачастую стандартизованные полиномы не являются самыми эффективными в плане статистических свойств соответствующего им check reduntancy code .

При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа ученых занималась исследованием порождающих многочленов разрядности до 16, [1] 24 и 32 бит, [6] [7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния. [7] Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.

Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга [8] . Использование другого полинома — CRC-32C — позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше — поэтому в наши дни он тоже пользуется популярностью. [7] К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.

Ниже в таблице перечислены наиболее распространенные многочлены — генераторы CRC.На практике вычисление CRC может включать пре- и пост-инверсию, а также обратный порядок обработки битов. В проприетарных реализациях CRC для усложнения анализа кода применяют ненулевые начальные значения регистров.

Название Полином Представления: [9] нормальное / реверсированное / реверсированное от обратного
CRC-1 (используется в аппаратном контроле ошибок; также известен как бит чётности) 0x1 / 0x1 / 0x1
CRC-4-ITU (ITU G.704 [10] ) 0x3 / 0xC / 0x9
CRC-5-EPC (Gen 2 RF >[11] ) 0x09 / 0x12 / 0x14
CRC-5-ITU (ITU G.704 [12] ) 0x15 / 0x15 / 0x1A
CRC-5-USB (USB token packets) 0x05 / 0x14 / 0x12
CRC-6-ITU (ITU G.704 [13] ) 0x03 / 0x30 / 0x21
CRC-7 (системы телекоммуникации, ITU-T G.707 [14] , ITU-T G.832 [15] , MMC, SD) 0x09 / 0x48 / 0x44
CRC-8-CCITT (ATM HEC), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99) 0x07 / 0xE0 / 0x83
CRC-8-Dallas/Maxim (1-Wire bus) 0x31 / 0x8C / 0x98
CRC-8 (ETSI EN 302 307 [16] , 5.1.4) 0xD5 / 0xAB / 0xEA [1]
CRC-8-SAE J1850 0x1D / 0xB8 / 0x8E
CRC-10 0x233 / 0x331 / 0x319
CRC-11 (FlexRay [17] ) 0x385 / 0x50E / 0x5C2
CRC-12 (системы телекоммуникации [18] [19] ) 0x80F / 0xF01 / 0xC07
CRC-15-CAN 0x4599 / 0x4CD1 / 0x62CC
CRC-16-IBM (Bisync, Modbus, USB, ANSI X3.28 [20] , многие другие; также известен как CRC-16 и CRC-16-ANSI) 0x8005 / 0xA001 / 0xC002
CRC-16-CCITT (X.25, HDLC, XMODEM, Bluetooth, SD и др.) 0x1021 / 0x8408 / 0x8810 [1]
CRC-16-T10-DIF (SCSI DIF) 0x8BB7 [21] / 0xEDD1 / 0xC5DB
CRC-16-DNP (DNP, IEC 870, M-Bus) 0x3D65 / 0xA6BC / 0x9EB2
CRC-16-Fletcher Not a CRC; see Fletcher’s checksum Used in Adler-32 A & B CRCs
CRC-24 (FlexRay [17] ) 0x5D6DCB / 0xD3B6BA / 0xAEB6E5
CRC-24-Radix-64 (OpenPGP) 0x864CFB / 0xDF3261 / 0xC3267D
CRC-30 (CDMA) 0x2030B9C7 / 0x38E74301 / 0x30185CE3
CRC-32-Adler Not a CRC; see Adler-32 See Adler-32
CRC-32-IEEE 802.3 (V.42, MPEG-2, PNG [22] , POSIX cksum) 0x04C11DB7 / 0xEDB88320 / 0x82608EDB [7]
CRC-32C (Castagnoli) (iSCSI, G.hn payload) 0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0 [7]
CRC-32K (Koopman) 0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B [7]
CRC-32Q (aviation; AIXM [23] ) 0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-64-ISO (HDLC — ISO 3309) 0x000000000000001B / 0xD800000000000000 / 0x800000000000000D
CRC-64-ECMA-182 [24] 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49

Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.

Попытки описания алгоритмов CRC

Одной из самых известных является методика Ross N. Williams [25] . В ней используются следующие параметры:

  • Название алгоритма (name);
  • Степень порождающего контрольную сумму многочлена(w >Примеры спецификаций некоторых алгоритмов CRC

    Примеры программ для вычисления CRC на языке C

    Некоторые из этих алгоритмов заимствованы у Ross Williams [26] .

    Реализации алгоритмов/Циклический избыточный код

    Примеры программ для вычисления CRC. Некоторые из этих алгоритмов заимствованы у Ross Williams [1] .

    Содержание

    CRC-4 [ править ]

    CRC-8 [ править ]

    CRC-16 [ править ]

    CRC-CCITT отличается от классического CRC-16, так как использует другой полином и порядок данных.

    CRC-32 [ править ]

    Алгоритм CRC32 основан на примитивном полиноме 0xEDB88320 (зеркальное отображение полинома 0x04C11DB7).

    Программная реализация на C [ править ]

    Получили распространение несколько методов программного расчета CRC:

    • оригинальный алгоритм с побитовым вводом данных:

    Вычисление CRC32 строк в compile-time

    По своей программистской природе я очень не люблю неоптимальность и избыточность в коде. И вот, читая в очередной раз на работе исходный код нашего проекта, вновь наткнулся на одну особенность в способе реализации перевода строк продукта на разные языки.

    Локализация здесь осуществляется довольно нехитро. Все строки, требующие перевода, оборачиваются в макрос _TR() :

    Макрос возвращает нужную версию текста в зависимости от текущего используемого языка. Определён он следующим образом:

    Здесь происходит обращение к глобальному объекту g_Translator , который в функции Translate() считает в рантайме crc32 от указанной строки, ищет в своей xml-базе перевод с совпадающей контрольной суммой и возвращает его.

    Не буду судить насколько такое решение оправдано, но оно проверено временем и показало себя достаточно надёжным. И всё бы ничего, но такое решение не лишено недостатков: по сути, функция делает лишнюю работу — контрольные суммы можно было бы подсчитать один раз на этапе компиляции, и использовать в дальнейшем уже готовые числовые значения. Это также избавило бы от необходимости хранить в исполняемом образе дублирующиеся строки, ведь они уже есть во внешнем xml-файле с переводами.

    Немного погуглив по запросу «compile-time crc32» я быстро понял, что задача это не самая тривиальная, а готовых решений мне найти так и не удалось.

    Использовать шаблонное метапрограммирование в чистом виде здесь, к сожалению, не получится. Любое обращение к символам строки, используемой в качестве параметра шаблона, не даёт компилятору свернуть рекурсивные вызовы шаблонной функции. Напрмер, в этой статье рассматривается создание только таблицы для расчётов crc32. А из полностью standard-compliant решений нашлось только одно — Boost.MPL. Здесь предлагается использовать следующую форму записи:

    Вместо использования строковых литералов предлагается разбивать строку на кусочки и отдавать отдельными параметрами шаблона. Но помимо причудливости используемой записи, чтобы преобразовать все 2450 строк проекта к такому виду, пришлось бы писать внешний кодогенератор и учить всю команду проекта новой форме записи.
    Проскакивали на форумах также сообщения, что в новом C++11 эта идея реализуема с использованием классического шаблонного метапрограммирования и ключевого слова constexpr , но, к сожалению, так просто перевести проект с длинной родословной на новый стандарт не представляется возможным.

    Была и другая идея с использованием кодогенератора. Можно было бы сделать pre-build event, на котором приводить переводимые строки к такому виду:

    Но опять же, хотелось чего-то универсального… Хотелось такой волшебный _TR() , который просто оставит после себя чистый crc32 без лишних телодвижений. И тогда я начал изобретать свой велосипед.

    Попытка №1. Чистые макросы

    На этом этапе в моей голове теплила надежду только одна мысль: кроме шаблонов до компиляции просчитываются макросы — нужно использовать их!

    Я создал новый проект в Visual Studio, выставив настройки оптимизации на максимальный inline и максимальную скорость. Анализировать успешность/неуспешность свёртывания строк до хеша я решил в известном user-mode отладчике OllyDbg, поэтому хотелось бы видеть в результирующем ехе только по одной маленькой секции на код и данные без лишнего мусора. Для этого я отключил С-runtime, что вкупе с несколькими другими приёмчиками позволило на выходе получить пустой ехе размером всего 2 Кб.

    После нескольких экспериментов я выдал простейшую реализацию расчёта crc32 для строк не более 3 символов:

    В реализации макросами основная проблема заключается в том, что мы не можем развернуть цикл расчёта crc на нужное количество итераций по длине строки, как в шаблонном метапрограммировании. Макрос всегда будет пересчитывать столько итераций, сколько в него заложить изначально. Например, в примере выше строка «1» всё равно бы просчитывалась в 4 итерации (максимальные 3 символа + ‘\0’), несмотря на то, что длина у неё всего один символ. Обходится это условной операцией, которая подсовывает значение crc с предыдущей итерации, в случае если строка уже просчитана до последнего символа.

    Запустив полученный ехе в отладчике, я увидел заветное PUSH 884863D2 , правильность расчёта которого легко подтверждается первым попавшимся онлайн-калькулятором crc32.

    Пришло время посмотреть насколько сильно упадёт скорость компиляции, если растиражировать макрос на длину строки, позволявшей покрыть требования проекта. Самая длинная строка в базе переводов была чуть короче 350 символов, так что хотелось заложиться хотя бы на предел в 500 символов.

    Таким образом, я сгенерировал тело макроса, в сокращённой форме выглядившее примерно так:

    Но тут меня ждало разочарование, когда компилятор выдал своё холодное: «fatal error C1009: compiler limit: macros nested too deeply». Опытным путём тогда удалось выяснить, что предел вложенности находится где-то в районе 300.

    Попытка №2. Функция __forceinline

    Потом еще были несколько попыток вместо вложенных макросов использовать inline-функции, но всё в итоге скатывалось либо к схожей ошибке (точно не помню, но компилятор ругался на слишком сложную грамматику), либо к непомерно долгой компиляции.

    После всех мучений я практически был готов отказаться от этой идеи, но всё же решил попробовать написать одну большую __forceinline функцию с кучей последовательных расчётов и проверками длины строки (я почему-то был уверен, что такое компилятор никогда в жизни не свернёт в константу):

    И это сработало! Компилятор довольно шустро сворачивал весь код в одно число, не оставляя в результирующем бинарнике ни самих строк, ни даже таблицу Crc32Table . Для правильной компиляции такой реализации достаточно только ключа /O2. Оставалось только дописать перегруженную версию метода g_Translator.Translate() с crc32 в качестве параметра, и дело в шляпе.

    После внедрения кода в проект, компиляция релизной сборки стала дольше на 1-2 минуты, но зато бинарник стал легче на 200 Кб, и теперь он не заставляет заниматься процессоры пользователей ненужной работой, позволяя их ноутбукам работать от батареи чуточку дольше :)

    CRC: как защитить программу

    Всем нам свойственно ошибаться, но иногда мы вовремя обнаруживаем свои ошибки. Пусть ты не сможешь умножить в уме 790 г. колбасы на 134 рубля 50 копеек, но если продавщица говорит: «115 рублей, молодой человек», то ты можешь прикинуть (около 120 рублей умножить на 1/4 килограмма будет 30 рублей, 130 минус 30 — сто рублей) и понять, что эта добрая тетя пытается тебя обдурить, присвоив себе десятку.
    Компьютеры тоже ошибаются. Сбоит память, на винчестерах появляются бэдблоки, мыши в колодцах грызут телефонные кабели. Так в информацию вносятся ошибки, которые нужно обнаруживать и по возможности исправлять.

    Чтобы найти ошибку, к сообщению добавляют контрольную сумму (checksum). В самом простом случае это сумма всех байтов сообщения. Например:

    Сообщение: 12 34 56
    Контрольная сумма: 12+34+56=102

    После передачи в это сообщение могут быть внесены помехи, например, так:

    Искаженное сообщение: 12 36 56, контрольная сумма 102

    Если теперь сложить байты сообщения, результат не совпадет с контрольной суммой. Так программа может сделать вывод, что данные были повреждены, и принять меры (например, еще раз запросить пакет TCP/IP или выдать сообщение, что архив поврежден).

    CRC, или циклический избыточный код, — это улучшенный (и усложненный) вариант контрольной суммы. В этой статье будет рассказано об алгоритме CRC32, который применяется в протоколе TCP/IP, архиваторах Zip и Rar. Затем я расскажу тебе, как защитить свою программу от модификаций, проверяя ее
    CRC.

    Чем плоха контрольная сумма

    Во-первых, если просто складывать байты, то старшие биты будут изменяться реже, чем младшие. То есть, если мы складываем

    12 34 56, контрольная сумма 102
    12 34 56 23, контрольная сумма 125
    12 34 56 23 45, контрольная сумма 170

    результат останется в пределах двух сотен. Если контрольная сумма записана в 32-разрядное или 64-разрядное слово, старшие байты будут содержать нули. Это не есть хорошо, так как все биты контрольной суммы должны быть равноценными.

    Во-вторых, сообщения с переставленными байтами будут иметь одну и ту же сумму:

    12 34 56, контрольная сумма 102
    56 12 34, контрольная сумма 102

    Несмотря на все эти недостатки, разные варианты контрольной суммы используются довольно широко, например, в штрих-кодах (barcode). У меня в руках банка консервированной кукурузы, на которой написан такой штрих-код:

    5 998483 710125

    Это код EAN-13 (тринадцать цифр). Правило для его проверки такое: сложи цифры на четных позициях, умножь сумму на три и добавь цифры на нечетных позициях. Должно получиться число, которое делится на десять:

    9 + 8 + 8+ 7 + 0 + 2 = 34
    5 + 9 + 4 + 3 + 1 + 1 + 5 = 28
    34 * 3 + 28 = 130, делится на 10

    А чтобы это условие выполнялось, последнюю цифру, 5, делают контрольной суммой. То есть складывают по этим правилам все остальные цифры, а последнюю цифру вычисляют как 10 минус последняя цифра суммы. Контрольная сумма нужна затем, чтобы сканер в супермаркете не считывал неправильный код если упаковка грязная или продавщица случайно закрыла код рукой. Если интересно, можешь проверить по этому правилу штрих-коды на любых упаковках пищевых продуктов (но не книг — у них другой код, ISBN).

    Есть очень простой, короткий и быстрый (примерно в 10 раз быстрее CRC) способ подсчета контрольной суммы. Берем по 4 байта из файла, и делаем с ними логическую операцию XOR. То, что получится в результате, — контрольная сумма.

    unsigned long XORCount(void* data, size_t bytesread)
    // data — сообщение, size_t — его длина
    <
    *(long*)(data + bytesread) = 0; // Подписать 4 нулевых байта
    bytesread /= sizeof(long);
    while(bytesread—)
    sum ^= *(long*)data, data+=sizeof(long);
    // Первые 4 байта XOR вторые 4 байта XOR третьи.
    return sum;
    >

    В этой контрольной сумме все байты используются полностью, среди них нет более значимых или менее значимых. Теоретическая вероятность того, что контрольная сумма окажется правильной для испорченного файла — 1 шанс на 2 ^ 32. Но операция XOR обладает таким свойством, что A XOR A = 0. Поэтому для сообщений

    12 34 A6 7B 91 92 93 94 91 92 93 94
    12 34 A6 7B 12 34 56 78 12 34 56 78
    12 34 A6 7B 00 00 00 00 00 00 00 00

    контрольная сумма будет одинаковой, как и для любых других, содержащих четное число одинаковых четверок байт (или же просто 8, 16, 24 или 32 одинаковых байт). И если вместо NOP’ов записать в исполнимый файл нули или любые другие байты (но число байт обязательно кратно 8), то программа этого не обнаружит. Все это плохо, но не смертельно, поэтому этим алгоритмом вполне можно пользоваться, если нужна высокая скорость проверки.

    Что такое CRC

    Запомни простую формулу: CRC = сообщение % полином

    То есть все сообщение (файл, архив) делим по модулю на некоторую константу (ее называют полиномом). Остаток от деления и есть CRC. О том, как весь файл можно разделить на число, я скажу чуть ниже, а пока — урок арифметики. Но не обычной арифметики, а полиномиальной.
    Что же это за арифметика такая? Это двоичная арифметика без переносов и заемов. Если сложить 1+1 в обычной двоичной арифметике, получится 10 (переносим единицу). Если вычесть 10–1, получится 1 (занимаем единицу).

    В полиномиальной арифметике:

    0+0 = 0 0–0=0
    0+1 = 1 0–1=1 (не занимаем!)
    1+0 = 1 1–0=1
    1+1 = 0 (не переносим!) 1–1=0

    Видно, что сложение в полиномиальной арифметике — это то же, что и вычитание. И если тебя мучили таблицами истинности на уроках информатики, ты сразу вспомнишь, что это операция XOR. В учебниках по дискретной математике ее обозначают кружком с косым крестиком внутри. Я буду обозначать эту операцию крышкой ^, как в Си.
    В полиномиальной арифметике 100 плюс 110 равно 10, но 100 минус 110 тоже равно 10. Нет ни знака, ни определенного порядка битов. Все биты равнозначны, и это очень важное свойство для CRC. Если переставить несколько битов в обоих слагаемых, те же биты будут переставлены в сумме:

    1010 ^ 1100=01 10, поменяем местами первые два и последние два бита:
    1010 ^ 0011=10 01 (а теперь сравни 19+34=53 и 91+43=134, а не 35).

    Биты можно представить как коэффициенты многочлена (полинома). Поэтому арифметику называют полиномиальной, а делитель в алгоритмах CRC — полиномом. В общем, все это математические заморочки, но знать будет не лишнее.

    Умножение в полиномиальной арифметике нам не понадобится, а вот о делении нужно сказать подробнее. Делим, как во втором классе, уголком, но вместо вычитания используем операцию XOR:
    Сообщение: 1101010
    Полином: 101

    1101010
    ^101
    ====
    111010
    ^101
    ===
    10010
    ^101
    ===== получили 0, сдвигаемся на 2 бита
    110
    ^101
    ===
    11

    Именно так считают CRC. Заметь, что в каждом столбике мы вычитаем старшие биты 1–1=0. В следующих битах могут быть любые числа. Один раз мы получили ноль в старшем бите, и нам пришлось сдвинуться вправо на 2 бита, а не на один. Итак, можно записать такой алгоритм (это не рабочий код, он только показывает алгоритм):

    // data — сообщение (битовая строка), POLY — полином
    while(length(data) > length(POLY)) <
    r = TOPBIT(data); // Выделяем старший бит data
    data

    В столбиках мы сдвигали полином 101 вправо, каждый раз вычитая его из сообщения. В этом алгоритме полином остается на месте, но мы «двигаем» делимое влево. Если старший бит r равен нулю, мы сдвигаемся еще на один бит, не вычитая POLY. Константа POLY равна полиному без старшей единицы, то есть 01. Обрати на это внимание: первую единицу писать незачем, так как двоичное число всегда начинается с единицы.
    Как работает этот код, легче понять на примере. Возьмем то же сообщение 1101010 и тот же полином 101 (сравни со столбиком выше):

    Шаг 1. r = 1 // Отделили первый бит
    data = 101010 // r=1, поэтому делаем XOR
    ^01
    ======
    111010
    Шаг 2. r = 1
    data = 11010
    ^01
    =====
    10010
    Шаг 3. r = 1
    data = 0010
    ^01
    ====
    0110
    Шаг 4. r = 0 // XOR не делаем
    data = 110
    Шаг 5. r = 1
    data = 10
    ^01
    ==
    11

    Итак, алгоритм в целом понятен: делим нацело data на POLY, получаем crc. И при делении 0–1=1, 1+1=0 без переноса.

    Сложность состоит в том, что сообщение может весить пару мегабайт. Как же разделить его на полином? Заметь, что при каждом проходе цикла у нас меняются только 2 первых бита data. Значит, можно проходить по
    всему сообщению, читая в каждый момент времени небольшую порцию данных (в нашем случае — первые два бита).

    Как работает табличная реализация

    Но у этого алгоритма есть еще один недостаток: он обрабатывает по одному биту сообщения. Например, для мегабайтного файла он сделает 8 миллионов проходов цикла, и каждый раз будет извлекать отдельные биты. Согласись, это никуда не годится!
    Есть общепринятый трюк, который ускоряет подсчет CRC чуть ли не в десятки раз. Идея такова: будем обрабатывать по байту за один проход цикла. Когда мы делим байт на полином, у нас в остатке получается некоторое число, причем оно не зависит от других байтов сообщения. Вот это число мы можем хранить в таблице для каждого делимого байта. Имея такую таблицу, будем получать CRC для каждого байта за один проход.
    Сейчас я расскажу, как построить такую таблицу и что конкретно в ней будет находиться. Чтобы не маяться с длинными таблицами, возьмем байт, равный 3 битам, и короткий полином 111. Пусть сообщение состоит из 5 бит, назовем их abcde. Пройдем наш старый алгоритм по шагам:

    Шаг 1. if(a) // Запись условная, это не рабочий код
    bc ^= 11;
    Шаг 2. if(b)
    cd ^= 11; // Полином 110 без первой единицы
    Шаг 3. if(c)
    de ^= 11;

    Когда мы подсчитали bcd и перешли на второй шаг, бит a уже не нужен, и на дальнейшие подсчеты он никак не влияет. Когда дошли до последнего шага, оказались ненужными биты a и b. А после третьего шага сыграл свою роль бит c, который теперь сходит со сцены.
    То, что поменялись биты abc, уже не важно, потому что на четвертом, пятом и так далее шаге они не будут использоваться. Но на этих трех шагах как-то изменились биты de. И изменились они в зависимости от битов abc. Давай переберем все значения abc, начиная с 000 и до 111.

    000 (a=0, b=0, c=0) — ни одно из условий не выполняется, поэтому биты def не изменились.
    001 (a=0, b=0, c=1) — условие if(c) выполнилось. Я запишу это так:
    abc
    001def
    ^11
    010 — условие if(b) выполнилось, но после добавления единицы к c выполнилось также if(c). Запишем под чертой результат операции XOR над двумя соответствующими числами в битах de:
    abc
    010de
    ^11
    ^11
    ==
    01
    011 — выполнилось условие if(b), но бит c был при этом обнулен, поэтому if(c) не сработало:
    abc
    011de
    ^11
    ==
    10
    100 — сработало условие if(a), которое вызвало if(b). В результате бит d будет подвергнут операции XOR с единицей (далее будем говорить проще, XOR’ится с единицей):
    abc
    100de
    ^11
    ^11
    ==
    10
    101 — аналогично, но бит c обнулился, и результат — нулевой:
    abc
    101de
    ^11
    ==
    00

    То же самое ты можешь написать для 110 и 111. Довольно муторное дело, но в нем нет ничего сложного. Сделаем массив T с индексами от 000 до 111, в котором будем хранить результаты наших вычислений:

    индекс значение
    000 00
    001 11
    010 01
    011 10
    100 10
    101 00
    110 11
    111 00

    Теперь рассчитать CRC можно, что называется, в два притопа, три прихлопа. Смотри:

    de ^= t[abc]; // Код условный, не рабочий.
    gh ^= t[def]; // t — массив, abc def ghi — сообщение
    crc = ghi;

    Если вынести текущий изменяемый байт в отдельную переменную, расширить байт до 8 бит и взять 32-битный полином, получим почти готовый код для расчета
    CRC:

    static const long t[256] = <
    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
    0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
    0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd,
    // И так далее, все 256 элементов смотри в коде к статье
    >

    unsigned long CRCCount(char* buff, size_t bufflen)
    <
    unsigned long crc = CRCINIT;
    while(bufflen—)
    crc = t[crc >> 24] ^ ((crc > 24] ^ (сrс Подчищаем «хвосты»
    сrс = t[сrс >> 24] ^ (сrс > 24] ^ (сrс > 24] ^ (сrс Вернуть инвертированный crc — см. ниже
    >

    Здесь на каждом шаге мы выбираем элемент из таблицы T по значению старшего байта (crc >> 24) и XOR’им его с очередным байтом. Этот байт у нас каждый раз сдвигается влево, а на его место приходит новый из сообщения (*buff++). Все эти сдвиги нужны для того, чтобы использовать длинный 32-битный полином, который XOR’ится с четырьмя соседними байтами сразу.
    В последних четырех строчках мы проводим через серию XOR’ов и сдвигаем влево оставшийся в младшем байте crc последний байт файла. По правилам вычисления CRC все символы должны «уйти» влево, за пределы переменной. На этом заканчивается вычисление CRC — остатка от деления сообщения на полином в полиномиальной арифметике.
    Итак, в таблице хранятся сдвинутые и проXORенные значения полинома. Конкретные сдвиги зависят от индекса массива, который есть предыдущий байт (abc или crc >> 24), а значение следующего байта (def или (crc crc = CRCINIT;
    while (bufflen—)
    crc = t[(crc >> 24 ^ *buff++) & 0xFF] ^ (crc

    Это позволяет избавиться от четырех последних строчек, хотя не делает алгоритм ни проще, ни быстрее. Кстати, скобки вокруг (crc while(bufflen—)
    crc = t[(crc ^ *buff++) & 0xFF] ^ (crc >> 8);

    Такой код будет давать перевернутый CRC, и именно его ты скорее всего найдешь на сайтах для программистов и в различных FAQ по CRC. Еще раз повторюсь, что именно так считают CRC большинство программ.

    Из-за путаницы с перевернутыми алгоритмами можно найти описание алгоритма с полиномом 0x04C11DB7 и другого алгоритма с полиномом 0xEDB88320. На самом деле это одно и то же, только авторы первого алгоритма переворачивали байты при каждом проходе цикла, а во втором алгоритме переделали сдвиг (crc > 8), выделили младший байт вместо старшего и записали задом наперед полином:

    EDB88320 = 11101101101110001000001100100000
    04C11DB7 = 00000100110000010001110110110111

    После вычисления CRC32 его обычно инвертируют (заменяют единицы нулями, а нули единицами). Это записывается либо как crc ^= 0xFFFF FFFF, либо crc =

    crc. Второй вариант быстрее и короче, поэтому мы будем пользоваться им.

    Ищем оптимальный алгоритм

    Табличная реализация CRC совсем непохожа на деление в полиномиальной арифметике. Еще более забавные вещи начнутся, когда мы будем оптимизировать этот алгоритм.
    Массив t[], конечно, можно рассчитывать заранее и записывать в константы, как показано выше. Но есть более оптимальный путь — генерировать этот массив при запуске программы. На это уходят буквально доли секунды, а программа становится на килобайт (256 элементов умножить на 4 байт) короче:

    static unsigned long t[256]; // Таблица для подсчета CRC
    void CRCInit()
    <
    for (int i = 0; i 0; j—) // Для каждого бита
    if(t[i] & 1) // Если младший бит
    t[i] = (t[i]>>1) ^ CRCPOLY;
    else
    t[i] >>= 1;
    >
    >

    Особых пояснений этот алгоритм не требует, потому что он делает то же, что мы делали вручную, когда рассчитывали таблицу t[]: проходит по всем битам abcdefhi, и если бит равен единице, XOR’ит следующие биты с полиномом. Длина байта здесь равна 8 символам, а полином 32-битный. Алгоритм перевернутый. В «прямом» алгоритме будет отличаться только вложенный цикл:

    t[i] = i 0; j—) // Для каждого бита
    if(t[i] & 0x80000000) // Если старший бит
    t[i] = (t[i]

    Оба алгоритма можно очень хорошо разогнать, если развернуть вложенный цикл и убрать условие. Я напишу «турбореактивную» версию перевернутого алгоритма, так как почти всегда ты будешь пользоваться именно им:

    for (int i = 0; i > 1) ^ CRCPOLY, иначе
    // x = (x >> 1) ^ 0 = x >> 1;
    x = (x>>1) ^ (CRCPOLY & (-(signed long)(x & 1)));
    x = (x>>1) ^ (CRCPOLY & (-(signed long)(x & 1)));
    x = (x>>1) ^ (CRCPOLY & (-(signed long)(x & 1)));

    Эта программа выполняется на Duron-800 за 12 микросекунд, тогда как исходная версия — за 35 мксек. Ускорение просто невероятное, но толку от него немного, потому что инициализация таблицы занимает очень небольшую часть от общего времени работы алгоритма. Проще говоря, 12 микросекунд не отличишь на глаз от тридцати пяти (одна микросекунда — миллионная доля секунды).
    Затем я попробовал частично развернуть цикл подсчета
    CRC:

    crc = CRCINIT;
    bufflen /= 4; // bufflen должно быть кратно 4. Для хвостов
    while(bufflen—) // следует использовать обычный алгоритм
    < x = *(long*)buff;
    crc = t[(crc ^ x) & 0xFF] ^ (crc >> 8);
    crc = t[(crc ^ x >> 8) & 0xFF] ^ (crc >> 8);
    crc = t[(crc ^ x >> 16) & 0xFF] ^ (crc >> 8);
    crc = t[(crc ^ x >> 24) & 0xFF] ^ (crc >> 8);
    buff += 4;
    >
    crc =

    crc; // Инвертировать CRC

    Это дает некоторый прирост скорости, но этот прирост невелик (не больше 5%). Так или иначе, конечная версия моей программы для подсчета CRC использует именно этот алгоритм и динамическую генерацию таблицы
    t[].

    Как защитить свою программу от взлома

    Ты можешь подсчитать CRC своего exe’шника, сравнить его с CRC, хранящимся в том же exe’шнике, и убедиться, что программа не была повреждена / взломана. Идея не нова, и она используется, в частности, в Total Commander (на проверке CRC прокололись многие крэкеры, написавшие патчи к
    TC). В exe’шниках DOS и Windows уже предусмотрены поля для контрольной суммы (16-битной по смещению 0x12..0x13 от начала файла и 32-битной по смещению 0x8-0xB от начала PE-заголовка). Самым простым вариантом будет использовать их. В компоновщике Link для MSVC++ предусмотрена опция /RELEASE, которая заставляет пересчитывать контрольную сумму после каждой компиляции программы. А Win32 API имеет функцию MapFileAndCheckSum для проверки этой суммы. Если нужно защитить программу от повреждений и вирусов, это действительно лучший вариант — всего-то пара строчек кода.
    Но такая «защита» не остановит ни одного крэкера. Придется придумать что-нибудь получше, а именно считать CRC самостоятельно. В заголовке exe’шника есть куча неиспользуемых и зарезервированных полей, в которые можно записать CRC. Я выбрал поле 0x2C из заголовка MS-DOS. Чтобы не получилось так, что CRC файла изменился из-за того, что мы вписали в этот же файл CRC, будем считать CRC начиная со смещения 0x40 (пропускаем заголовок MS-DOS). Получаем имя данного exe’шника функцией GetModuleFileName, открываем его, подсчитываем CRC и сравниваем с хранящимся в файле:

    #define QUANT 1024 // Читать по 1024 байт файла
    #define CRCPOLY 0xEDB88320
    #define CRCINIT 0xFFFFFFFF
    int CRCCheckThisExe()
    < // Проверить целостность exe (возвращает 1,
    // если программа была изменена)
    char FileName[MAX_PATH]; HANDLE hFile; DWORD bytesread;
    char data[QUANT], *p; unsigned long crc, x;

    GetModuleFileName(NULL, FileName, MAX_PATH);
    hFile = CreateFile(FileName, GENERIC_READ, FILE_SHARE_READ,
    NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL |
    FILE_FLAG_SEQUENTIAL_SCAN, NULL);
    if(hFile == INVALID_HANDLE_VALUE)
    return 0;
    // Читать со смещения 40
    SetFilePointer(hFile, 0x40, NULL, FILE_BEGIN);
    CRCInit(); // Создать массив t
    crc = CRCINIT;
    for(;;) // Подсчет CRC
    <
    ReadFile(hFile, data, QUANT, &bytesread, NULL);
    p = data;
    if(bytesread != QUANT) // Досчитываем остаток
    <
    while(bytesread—)
    crc = t[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
    break; // Выйти, когда файл закончился
    >
    // Так как bytesread == QUANT, bytesread кратно 4
    bytesread /= 4;
    while(bytesread—)
    < x = *(long*)p;
    crc = t[(crc ^ x) & 0xFF] ^ (crc >> 8);
    crc = t[(crc ^ x >> 8) & 0xFF] ^ (crc >> 8);
    crc = t[(crc ^ x >> 16) & 0xFF] ^ (crc >> 8);
    crc = t[(crc ^ x >> 24) & 0xFF] ^ (crc >> 8);
    p += 4;
    >
    >
    // Считать CRC из файла и сравнить с рассчитанным
    SetFilePointer(hFile, 0x2C, NULL, FILE_BEGIN);
    x = 0;
    ReadFile(hFile, &x, sizeof(x), &bytesread, NULL);
    CloseHanlde(hFile);
    return x != crc;
    >

    Как показывает опыт, на скорость расчета CRC сильно влияет размер считываемого куска QUANT. Я получал хорошие результаты при QUANT = 1024 и QUANT = 2048. Ты можешь подобрать другие значения. По идее, они должны быть кратны размеру сектора диска (512 байт), но можно еще попробовать учесть, что мы считываем файл не с начала, а со смещения 0x40.

    Считает и записывает CRC в exe’шник отдельная программа, CRCMaker. Ее можно прописать в свойства проекта (Post-build step), чтобы после каждой компиляции CRC пересчитывался автоматически.
    Чтобы усилить защиту, нужно «размазать» вычисление CRC по всей твоей программе. При запуске программы вызови GetModuleFileName и сохрани путь в глобальной переменной. Затем где-то в другом месте открой файл и начни подсчет CRC. Хороших результатов можно добиться, если подсчитывать CRC при простое программы (когда пользователь не работает с клавиатурой и мышью или когда переключился в другую программу). Два значения CRC — рассчитанное и взятое из файла — нужно записать в глобальные переменные и в нескольких точках программы сверять между собой. Лучше не выдавать никаких предупреждающих сообщений, а сразу выходить из программы. Все это более или менее обезопасит твою прогу от цепких лап любителей
    SoftIce.

    Что еще почитать на тему CRC

    Ross Williams. A painless guide to CRC error detection algorithms. — ftp://www.internode.net.au/clients/rocksoft/papers/crc_v3.txt
    (русский перевод см. http://www.rsdn.ru/article/files/classes/SelfCheck/crcguide.pdf). Очень подробное описание принципа подсчета CRC, но не слишком оптимальные алгоритмы. Можно почитать, если ты хочешь разобраться в математических подробностях.

    FAQ по CRC. — http://faqs.org.ru/progr/common/crc_faq.rar. Самые короткие и вразумительные алгоритмы вычисления CRC из всех, что я встречал. На Си, Паскале, ассемблере. Там же — как взломать CRC (подобрать сообщение под заданный
    CRC).

    Алексей Кирюшкин. Защита исполняемых файлов от искажений. —
    http://www.rsdn.ru/article/files/classes/selfcheck.xml. Автор предлагает хранить CRC в разделе данных и находить его по некоторой сигнатуре. Неплохой способ, хотя он немного сложнее, чем хранение CRC в заголовках exe’шника.

    Скачать пример программы можно отсюда. Программа XakepCRC проверяет CRC файлов, но она также защищает себя от взлома с помощью CRC. Заголовочные файлы из каталога CRClib ты можешь использовать в своих программах.

    Что такое код udm_crc32

    Передаю файл с серверной части по кускам на PDA.
    При передаче куска также передаю его контрольную сумму CRC32.
    После передачи смотрю, что получил визуально.
    Отправляемый и принимаемый куски совершенно одинаковые.
    Но если я вычисляю контрольную сумму принятого куска на PDA, то она
    не равна контрольной сумме, посчитаной для отправляемого куска на сервере.
    Может быть дело в кодировке? Я использую Encoding.UTF8
    Кодировка на PDA отличается от кодировки на нормальном компе.
    Тогда вопрос, как же вачислять контрольные суммы там и сям, чтобы они были равны.

    Алгоритм вычисления CRC32 следующий

    public static uint CalculateCRC(System.IO.Stream stream)
    <
    stream.Position = 0;

    const int buffer_size = 1024;
    const uint POLYNOMIAL = 0xEDB88320;

    uint result = 0xFFFFFFFF;
    uint Crc32;

    byte] buffer = new byte[buffer_size];
    uint] table_CRC32 = new uint[256];

    //
    // Чтение из буфера
    //
    int count = stream.Read(buffer, 0, buffer_size);

    //
    // Вычисление CRC
    //
    while (count > 0)
    <
    for (int i = 0; i > 8)
    ^ table_CRC32[(buffer[i])
    ^ ((result) & 0x000000FF)];
    >

    CRC32: на STM32 как на компе или на компе как на STM32.

    Все знают, что в STM32F1xx, STM32F2xx, STM32F4xx есть аппаратный блок CRC32 с полиномом 0x04C11DB7.
    И он, в общем-то, работает. Но только контрольная сумма почему-то не совпадает с таковой, рассчитанной софтварно.
    В гугле обычно 2 типа вопросов:

    1. Как хардварно посчитать на STM32 побайтовую CRC
    2. Как посчитать софтово CRC так, чтоб она совпала с хардовой на STM32

    Причём, на первый вопрос ответ везде отрицательный. Так ли это? Попробуем разобраться.

    Софтварно CRC32 обычно считается побайтово и (как в эзернете) — младшим битом вперёд, сдвиг LSFR — вправо, в сторону младшего бита, поэтому используется реверсированный полином 0xEDB88320.
    Регистр данных же в CRC блоке STM32 — 32х-битный и сдвигается в сторону старшего бита.
    Чтоб понять, почему так, немного иллюстрации:

    • Во-первых, CRC — побитовая функция. параллельный подсчёт CRC — плюшки из следствий математики двоичных полиномов.
    • порядок загрузки бит в LSFR не должен нарушаться в зависимости от разрядности и остроконечности архитектуры

    Смотрим на рисунок: все биты поступают по порядку, цветами я пометил биты, которые соответствуют друг другу для прямого и зеркального полиномов, нумерация байтов совпадает со смещением в памяти.
    Т.е., CRC32 на STM32 можно посчитать так же, как и принято в ethernet. Для этого надо реверсировать входные слова и реверсировать в итоге контрольную сумму. Это работает только для длины, кратной 4.
    Сперва совтварная реализация.
    Инициализируем таблицы остатков для быстрого вычисления CRC:

    Побайтовое вычисление «нормальной CRC»:

    Вычисление CRC как на CRC блоке STM32:

    Тут я применил htonl чтоб байты в слове были в определённом порядке независимо от LE/BE: сначала в LSFR заправляется байт, который лежит в памяти по смещению 3 (как на рисунке). Ещё, остаток сообщения, не влезающий в 4х-байтовое слово дополняется нулями справа и CRC досчитвается дальше.
    Можно писать конструкцию типа такой (вычислять CRC кусками):

    Вот то, что получается:
    crc32_byte(«123456789») = CBF43926
    crc32_stm32(«123456789») = 500E6FA8
    crc32_byte(«12345678») = 9AE0DAAF
    crc32_stm32(«12345678») = 0103AB06

    Теперь код для STM32:
    Сперва чисто хардварная CRC (ей соответствует софтовая crc32_stm32):

    Далее сделаем «как на софте», или «как в ethernet». Благо, в ARM есть инструкция для реверсирования бит.
    Но это не всё. Ведь если пораскинуть мозгами, то можно добавить вкусную плюшку — сосчитать-таки побайтовую CRC на аппаратном блоке.
    Нужно просто вычислить полином-остаток от оставшегося куска и добавить его к уже посчитанной пословно CRC. Остаток — это по сути та же CRC, но с начальным состоянием LSFR=0 (см инициализацию таблицы остатков). Но вот беда — CRC_ResetDR может установить регистр CRC только в 0xFFFFFFFF. Слава яйцам, что нам надо именно 0, а не что-то ещё. Одно из свойств CRC состоит в том, что если к сообщению приписать его CRC, то CRC нового сообщения будет равна 0. Другими словами, если мы подадим в регистр CRC то, что мы из него считали, то в результате получится 0. Теперь осталось заправить в регистр кусочек из одного, двух или трёх оставшихся байт — et voila, забираем наш полином-остаток и добавляем его к CRC.
    Ниже код:

    Вот, как-то так, думаю, многим пригодится.

    это, если кому надо, реальные ethernet-фреймы с CRC32 FCS

    Илон Маск рекомендует:  Что такое код dlgdirselectcombobox
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL