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* CRC32Table = NULL;CRC32Table = new DWORD[256];DWORD dwCRC;
for(int i = 0; i < 256; i++)
{
dwCRC = i;for(int j = 8; j > 0; j—)
{
if(dwCRC & 1)
dwCRC = (dwCRC >> 1) ^ dwPolynomial;
else
dwCRC >>= 1;
}CRC32Table[i] = dwCRC;
}
Простой цикл через все 256 записей и создав значения поиска, основанного на позиции в таблице многочлена.
В зависимости от вашей ситуации вы можете хотеть или не хотеть тратить циклы процессора, чтобы сохранить регенерирующую таблицу каждый раз, когда Вы хотите создать подпись. Если это ваш случай, просто выделите этот код в отдельное приложение, сохраняйте дамп таблиц в файл, на экран, или где вам наиболее удобно, и копируйте и вставляйте значения прямо в таблицу. Хотя и ценой 256 * 4 байт памяти (что на самом деле не много), вы резко улучшите врёмя расчета без необходимости постоянно пересчитывать таблицы.
Для тех из вас, кто пытается создать таблицу использованием полиномиальных перечисленных выше первых 14 значений должен выглядеть следующим образом:
0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91
Рассчет CRC32
Имея таблицу поиска, мы можем взглянуть на функцию GetCRC32. Эта функция принимает один байт и предыдущее вычисленное значение CRC32 (если таковое существует).
dwCRC32 = (( dwCRC32 ) >> 8 )^ CRC32Table[( byte )^(( dwCrc32 ) & 0x000000FF )];
}
Первое, что нужно отметить — это то, что функция является встроенной. Для тех из вас, кто не понимает этой особенности, где бы ваш код ни делал вызов этой функции, вместо прыгания на место функции в памяти каждый раз (что потреблять несколько циклов), процессор будет на самом деле вставить копию кода функции в то место, откуда функция была вызвана. Может быть, функция и занимает только цикл или два, но это происходит каждый раз, когда функция вызывается, и если вы попытаетесь вычислить 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;
}
dwCRC32 = 0xFFFFFFFF;
// 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 для файла очень похож, и хотя функция, делающая это, кажется несколько более сложной — в действительности это не так. Однако мы должны добавить дополнительную функцию, которая будет вычислять размер файла перед обработкой.
// WE HAVE TO HAVE A VALID HANDLE
if( hFile == INVALID_HANDLE_VALUE ){
return false;
}// 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 == INVALID_FILE_SIZE ){
bException = true;
dwSize = 0;
}
}// SOMETHING SCREWED UP
catch( … ) {
bException = true;
}return !bException;
}
Эта функция вызывается внутри CRC32ByFile, поэтому мы не должны о ней сильно беспокоиться. Что происходит в идеале — после того, как CRC32ByFile открыла указанный файл (успешно, мог бы я добавить), будет сделана попытка передать указатель файла и указатель на DWORD, который вернет рассчитанный размер. Функция возвращает true, если это удалось.
Следующий код на самом деле читает файл и передает данные в наш CRC32 алгоритм.
if(( hFile = CreateFile( strFileName, GENERIC_READ,
FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL
| FILE_FLAG_SEQUENTIAL_SCAN, NULL )) == INVALID_HANDLE_VALUE ){
// 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.