Cyclic redundancy checking (crc32), уроки і приклади програмування

by Clifford M. Roche

Передмова

Невелике розуміння математики (многочлен ділення) було б корисно, але я пишу цю статтю так, щоб воно не було потрібно. Ви, однак, повинні розуміти 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.

Реалізація дуже проста.

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

class ECRC32 # 123;
public.
static DWORD CRC32ByString # 40; LPCTSTR. DWORD # 41; ;
static DWORD CRC32ByFile # 40; LPCTSTR. DWORD # 41; ;
static DWORD CRC32ByStruct # 40; BYTE *, DWORD. DWORD # 41; ;

private.
static bool GetFileSize # 40; HANDLE. DWORD # 41; ;
static inline void GetCRC32 # 40; BYTE. DWORD # 41; ;

static DWORD CRC32Table # 91; 256 # 93; ;
# 125; ;

Все просто - у нас є функція для кожного типу даних, який ми плануємо використовувати, яка буде генерувати для них CRC32 підпису. У нас також є дві приватні функцій, одна буде обчислювати розмір файлу - необхідно для правильної роботи внутрішніх алгоритмів, друга для виконання іншої математики та поновлення значення CRC32 для конкретного байта.

Існує також один статичний масив, він просто зберігає для нас таблицю CRC32. Насправді вам не потрібно зберігати цю таблицю постійно, якщо не хочете. Використовуючи конструктор і деструктор, ви можете створювати і очищати таблицю тільки тоді, коли плануєте використовувати її. Для наших цілей більш доцільно використовувати таблицю, так як це може значно зменшити час обробки.

Створення таблиці підстановки

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

Отже, цей многочлен також використовується багатьма іншими додатками і системами, такими як WinZip, PKZip, і Ethernet.

Примітка: Вам потрібно буде генерувати таблицю принаймні один раз, навіть якщо ви використовуєте фіксовану таблицю. Якщо, звичайно, ви використовуєте таблицю, представлену в моєму демо.

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

Примітка: Відображення - це простий процес реверсу бінарної структури даного бінарного сегмента. Наприклад, 10100111 стане при відображенні 11100101.

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

CRC32Table = new DWORD # 91; 256 # 93; ;

DWORD dwCRC;
for # 40; int i = 0; i <256 ; i ++ )
# 123;
dwCRC = i;

for # 40; int j = 8; j> 0; j - # 41;
# 123;
if # 40; dwCRC 1 # 41;
dwCRC = # 40; dwCRC >> 1 # 41; ^ DwPolynomial;
else
dwCRC >> = 1;
# 125;

CRC32Table # 91; i # 93; = DwCRC;
# 125;

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

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

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

0x00000000. 0x77073096. 0xEE0E612C. 0x990951BA.
0x076DC419. 0x706AF48F. 0xE963A535. 0x9E6495A3.
0x0EDB8832. 0x79DCB8A4. 0xE0D5E91E. 0x97D2D988.
0x09B64C2B. 0x7EB17CBD. 0xE7B82D07. 0x90BF1D91

розрахунок CRC32

Маючи таблицю пошуку, ми можемо поглянути на функцію GetCRC32. Ця функція приймає один байт і попереднє обчислене значення CRC32 (якщо таке існує).

inline void ECRC32. GetCRC32 # 40; const BYTE byte. DWORD dwCRC32 # 41; # 123;
dwCRC32 = # 40; # 40; dwCRC32 # 41; >> 8 # 41; ^ CRC32Table # 91; # 40; byte # 41; ^ # 40; # 40; dwCrc32 # 41; 0x000000FF # 41; # 93; ;
# 125;

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

Зверніть увагу: використання вбудованих функцій не слід сприймати легковажно. Це може привести до дуже значного збільшення обсягу підсумкового коду і може в кінцевому підсумку рахунку призвести до зниження загальної продуктивності додатка, споживаючи занадто багато пам'яті (що що призводить до нестачі ресурсів і помилок під час виконання програми). У нашій ситуації GetCRC32 викликається дуже обмежено і, таким чином, загальний розмір програми не має значення.

Ви також можете подивитися на специфікацію __fastcall. __fastcall працює шляхом передачі аргументів на функцію через регістри процесора, на відміну від стандартного способу проходження їх через стек. Це може привести до помітного збільшення швидкості так же, як це робить inline.

З переданим байтом і попереднім його CRC32 значення функції виконує ділення многочлена, з посиланням посиланням на таблицю, і оновлення CRC32 підпису.

Розрахунок для структур

Дві попередні основні функції - ядро ​​нашого CRC32 алгоритму. Все, що залишилося зробити - прочитати дані і, використовуючи ці дві функції, створити CRC32 підпис для них.

DWORD ECRC32. CRC32ByStruct # 40; BYTE * byStruct. DWORD dwSize. DWORD dwCRC32 # 41; # 123;

// MAKE SURE WE HAVE A VALID BYTE STREAM
if # 40; byStruct == NULL # 41; # 123;
return - 1;
# 125;

// LOOP TO READ THE STRUCTURE
for # 40; DWORD i = 0; i GetCRC32 # 40; * ByStruct. dwCRC32 # 41; ;
byStruct ++;
# 125;

// FINISH UP
dwCRC32 =

dwCRC32;
return 0;
# 125;

Перед заповненням структури з даними, які будуть оброблені, дуже важливо, форматувати всю структуру в NULL, тому що структури, як правило, доповнюються до 8 байт. Іншими словами, якщо у вас є структура, яка має 7 символів (7 байт), sizeof (структура) поверне 8 байт. Останній біт буде инициализирован як "відро" значення і не може бути такими ж, якщо ви відтворити структуру пізніше з тими ж даними. Це буде змінювати підсумкове значення CRC32. Існує ще один варіант - при передачі розміру структури, якщо ви знаєте точний розмір структури без роздільник, ви можете використовувати це значення, що змусить наш алгоритм ігнорувати будь-які додаткові байти-роздільники. Однак не слід змішувати два методи, оскільки це буде призводити до різних несовпадениям CRC32 значення двох ідентичних структур.

Розрахунок для файлу

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

bool ECRC32. GetFileSize # 40; const HANDLE hFile. DWORD dwSize # 41; # 123;
// WE HAVE TO HAVE A VALID HANDLE
if # 40; hFile == INVALID_HANDLE_VALUE # 41; # 123;
return false;
# 125;

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

try # 123;
// SETS THE UPPER AND LOWER SIZE VALUES
dwSize = GetFileSize # 40; hFile. NULL # 41; ;

if # 40; dwSize == INVALID_FILE_SIZE # 41; # 123;
bException = true;
dwSize = 0;
# 125;
# 125;

// SOMETHING SCREWED UP
catch # 40 ;. # 41; # 123;
bException = true;
# 125;

return. bException;
# 125;


Ця функція викликається всередині CRC32ByFile, тому ми не повинні про неї сильно турбуватися. Що відбувається в ідеалі - після того, як CRC32ByFile відкрила вказаний файл (успішно, міг би я додати), буде зроблена спроба передати покажчик файлу і покажчик на DWORD, який поверне розрахований розмір. Функція повертає true, якщо це вдалося.

Наступний код насправді читає файл і передає дані в наш CRC32 алгоритм.

// OPEN THE SPECIFIED FILE
if # 40; # 40; hFile = CreateFile # 40; strFileName. GENERIC_READ.
FILE_SHARE_READ. NULL. OPEN_EXISTING. FILE_ATTRIBUTE_NORMAL
| FILE_FLAG_SEQUENTIAL_SCAN. NULL # 41; # 41; == INVALID_HANDLE_VALUE # 41; # 123;
// THIS MEANS THAT WE HAVE AN ERROR
dwErrorCode = - 1;
# 125;

// CALCULATE THE CRC32 SIGNATURE
else # 123;
BYTE cBuffer # 91; 512 # 93; ;
DWORD dwBytesInOut. dwLoop;
bool bSuccess = false;

bSuccess = ReadFile # 40; hFile. cBuffer. sizeof # 40; cBuffer # 41 ;.
dwBytesInOut. NULL # 41; ;

while # 40; bSuccess dwBytesInOut # 41; # 123;
for # 40; dwLoop = 0; dwLoop GetCRC32 # 40; cBuffer # 91; dwLoop # 93 ;. dwCRC32 # 41; ;
bSuccess = ReadFile # 40; hFile. cBuffer. sizeof # 40; cBuffer # 41 ;. dwBytesInOut. NULL # 41; ;
# 125;
# 125;

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

Інші застосування CRC

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

Чудове розширення подібного методу використання, яке також широко використовуються в іграх, буде додати значення CRC32 в пакети, які ви посилаєте по Інтернету; це гарантує, що дані, які надходять в місце призначення - ті ж, якими були перед відправкою. Хоча TCP і UDP протоколи зберігають значення CRC в заголовках, вони будуть тільки перевіряти, як передається кожен пакет. Структури і дані, які відправляються в декількох пакетах, можуть в результаті прийти пошкоджених і використаними в такому вигляді без перевірки CRC.

CRC може навіть бути використана в цілях безпеки, щоб переконатися, що текстові повідомлення та інші типи повідомлень не змінені навмисно. Це система, яка зазвичай використовується в PGP при підписанні повідомлення таким чином, що сторона, яка отримує може перевірити, що воно було відправлено дійсно вами, тим, хто його підписав. PGP не використовує CRC32 для створення підписів, алгоритм CRC32 кілька слабкий для таких ситуацій. Інші загальні алгоритми, використовувані для цих цілей - це MD5, SHA8, SHA256 і т.д. Вони називаються HASH-алгоритми і використовуються зазвичай в цілях безпеки.

Якщо вам потрібно використовувати генератор підписів, який виробляє більшу кількість значень, ніж CRC32 і повинен мати більшу, ніж CRC32, точність, зверніть увагу на ці три алгоритму.

І нарешті, якщо у вас є які-небудь зауваження, питання, і так далі, ви легко можете знайти мене в irc на каналі #gamedev під ніком kurifu або seta.