de către Clifford M. Roche
prefață
O mică înțelegere a matematicii (polinomul de divizare) ar fi utilă, dar scriu acest articol astfel încât să nu fie necesar.
Cu toate acestea, trebuie să înțelegeți C ++ - acest lucru este implicit.
De ce să folosiți CRC32?
Am nevoie pentru unul dintre proiectele lor mai mici - am decis să scrie o cerere pentru actualizări online, care generează pur și simplu o semnătură unică pentru un set de fișiere, compară aceste valori cu semnătura listei de master pe server, și actualizează fișierele care nu se potrivesc cu această semnătură.
Există mai multe moduri în care pot verifica integritatea fișierelor și pot decide dacă trebuie să fie actualizate de pe serverul principal. Timpul de creare / timestamp, dimensiunea fișierului și CRC32 ajung la minte. Există, de asemenea, unele moduri evident mai complicate, cum ar fi contabilizarea fișierelor în baza de date, dar nu este nevoie să complici lucrurile prea mult. Același lucru este valabil pentru majoritatea utilizărilor CRC32 în jocuri. În plus, majoritatea algoritmilor mai complexi încearcă să calculeze mult mai mult decât CRC32.
Crc32, cu toate opțiunile prezentate, este în prezent cea mai potrivită, deoarece nu trebuie să vă faceți griji despre fișierele care sunt de aceeași dimensiune, sau data modificării (de foarte multe ori se întâmplă cu imagini raster, precum și o serie de alte tipuri comune de fișiere de jocuri) și noi Nu există nici un motiv să vă faceți griji cu privire la timpul inexact al creării fișierelor / timestampului datorită schimbării lor. Deși CRC32 algoritm nu este perfect și există întotdeauna posibilitatea ca cele 2 fișierele vor avea aceeași valoare crc32, aceste cazuri sunt atât de rare încât CRC32 devine un candidat ideal pentru generarea unui fișier de semnătură.
Valoarea CRC32 conține un număr de 32 de biți (4 octeți) (cunoscut și ca semnătură), care identifică în mod unificat piesa specificată. Avantajul CRC32 pentru semnăturile de control este că algoritmul său este proiectat astfel încât modificările mici din fișier (fie că se schimbă, șterg sau inseră) ar trebui să producă schimbări majore în semnătura CRC32. CRC32 are 2 ^ 32 de valori posibile; un total de 4.294967E +09.
Din aceste motive, semnăturile CRC32 sunt foarte utile în jocuri, deoarece ne lasă loc creativității. Ele pot fi folosite pentru a verifica fișierul pentru a vedea dacă schimbarea pentru a ajuta la prevenirea tentativelor de a hack joc în scopul de a înșela, sau pot fi utilizate pentru a scana fișiere sau date care sunt transmise pe Internet în timpul jocului, cum ar fi un fișier de hartă, de exemplu, .
Cum funcționează CRC32?
CRC32 este un proces oarecum complex și constă în multe operații matematice. Dar iată cum funcționează de obicei:
Mai întâi vom lua valoarea polinomului, iar cu această valoare vom genera o căutare CRC32. La sfârșitul acestui articol, vă voi arăta cum să creați corect un tabel de prezentare cu acest polinom. În continuare vom lua datele pe care dorim să genereze o semnătură CRC32, iar funcția specială va genera o valoare CRC32 actualizată pentru fiecare octet din fișier, șirul sau structura pe care le verifica. Aceasta se face pentru fiecare octet dintr-un șir, o structură sau un fișier. După finalizare, valoarea cea mai actualizată devine o semnătură.
Inima algoritmului CRC32 este un sistem simplu care ia octetul transmis pentru calcul din setul de date și valoarea curentă a CRC32 pe care o avem și efectuează o căutare în tabelul nostru general. Dacă nu există o valoare curentă CRC32, trebuie să folosim 0xFFFFFFFF. Un pic de matematică, și anume polinomul de divizare, iar funcția va returna valoarea actualizată a CRC32.
Implementarea este foarte simplă.
Deci, clasa noastră va arăta.
clasa ECRC32 # 123;
publice.
static DWORD CRC32ByString # 40; LPCTSTR. DWORD # 41; ;
static DWORD CRC32ByFile # 40; LPCTSTR. DWORD # 41; ;
static DWORD CRC32ByStruct # 40; BYTE *, DWORD. DWORD # 41; ;
privat.
static bool GetFileSize # 40; MÂNER. DWORD # 41; ;
static inline void GetCRC32 # 40; BYTE. DWORD # 41; ;
static DWORD CRC32Table # 91; 256 # 93; ;
# 125; ;
Este simplu - avem o funcție pentru fiecare tip de date pe care intenționăm să o folosim, care va genera semnături CRC32 pentru ele. Avem, de asemenea, două funcții private, unul va calcula dimensiunea fișierului - este necesar ca algoritmii interni să funcționeze corect, al doilea pentru realizarea altei matematici și actualizarea valorii CRC32 pentru un anumit octet.
Există, de asemenea, o matrice statică, pur și simplu stochează tabelul CRC32 pentru noi. De fapt, nu trebuie să păstrați permanent acest tabel, dacă nu doriți. Folosind constructorul și distrugătorul, puteți să creați și să curățați masa numai atunci când intenționați să o utilizați. Pentru scopurile noastre, este mai util să folosiți masa, deoarece aceasta poate reduce în mod semnificativ timpul de procesare.
Crearea unei tabele de căutare
Pentru a crea o tabelă de căutare, trebuie să specificați o valoare polinomial pentru utilizare, care ne va da valorile pe care le folosim în tabelul nostru. Valoarea polinomului pe care o utilizați ar trebui să reducă teoretic probabilitatea dublării semnăturilor în datele dvs., totuși matematica din spatele uneia dintre aceste valori este prea complexă și depășește domeniul de aplicare al acestui articol. Acest lucru este normal, deoarece am ales deja valoarea optimă. Valoarea pe care o vom folosi pentru a crea masa noastră va fi 0x04c11db7.
În consecință, acest polinom este utilizat și de multe alte aplicații și sisteme, cum ar fi WinZip, PKZip și Ethernet.
Notă: va trebui să generați tabelul cel puțin o dată, chiar dacă utilizați o tabelă fixă. Dacă, desigur, folosiți tabelul prezentat în demo-ul meu.
Înainte de a continua - stările standard CRC, pe care trebuie să le reflectăm valorile din tabelul de căutare, ceea ce se poate face prin reflectarea polinomului. În acest caz, 0x04c11db7 devine 0xedb88320. Deși unele ecuații vor reflecta valorile din tabel, pentru că le creează, voi reflecta polinomul. În cele din urmă, acest lucru se termină numai în faptul că folosim mai puține linii de cod.
Notă: Reflecția este un proces simplu de inversare pentru structura binară a unui anumit segment binar. De exemplu, 10100111 va deveni cu reflexia 11100101.
DWORD dwPolynomial = 0xEDB88320;
DWORD * CRC32Table = NULL;
CRC32Table = DWORD nou # 91; 256 # 93; ;
DWORD dwCRC;
pentru # 40; int i = 0; eu <256 ; i ++ )
# 123;
dwCRC = i;
pentru # 40; int j = 8; j> 0; j - # 41;
# 123;
dacă # 40; dwCRC 1 # 41;
dwCRC = # 40; dwCRC >> 1 # 41; ^ dwPolynomial;
altfel
dwCRC >> = 1;
# 125;
CRC32Table # 91; eu # 93; = dwCRC;
# 125;
O buclă simplă prin toate cele 256 intrări și crearea de valori de căutare bazate pe poziția din tabelul polinomului.
În funcție de situația dvs., este posibil să doriți sau nu să cheltuiți ciclurile CPU pentru a salva tabelul de regenerare de fiecare dată când doriți să creați o semnătură. Dacă acesta este cazul dvs., evidențiați acest cod într-o aplicație separată, salvați memoria tabelelor într-un fișier, pe ecran sau oriunde vă simțiți mai confortabil și copiați și lipiți valorile direct în tabel. Deși la un preț de 256 * 4 octeți de memorie (care de fapt nu este mult), veți îmbunătăți considerabil timpul de calcul fără a trebui să recalculați în mod constant mesele.
Pentru cei care încercați să creați o masă utilizând polinomul enumerat mai sus, primele 14 valori ar trebui să arate astfel:
0x00000000. 0x77073096. 0xEE0E612C. 0x990951BA.
0x076DC419. 0x706AF48F. 0xE963A535. 0x9E6495A3.
0x0EDB8832. 0x79DCB8A4. 0xE0D5E91E. 0x97D2D988.
0x09B64C2B. 0x7EB17CBD. 0xE7B82D07. 0x90BF1D91
Calcularea CRC32
Având o masă de căutare, putem privi funcția GetCRC32. Această funcție are un octet și valoarea calculată anterior a CRC32 (dacă există).
inline void ECRC32. GetCRC32 # 40; const BYTE octet. DWORD dwCRC32 # 41; # 123;
dwCRC32 = # 40; # 40; dwCRC32 # 41; >> 8 # 41; ^ CRC32Table # 91; # 40; octet # 41; ^ # 40; # 40; dwCrc32 # 41; 0x000000FF # 41; # 93; ;
# 125;
Primul lucru de reținut este că funcția este integrată. Pentru aceia dintre voi care nu înțeleg această funcție, în cazul în care codul sau de a efectua apeluri care funcționează în loc să apryganiya pentru a plasa funcții în memorie de fiecare dată (care consumă mai multe cicluri), procesorul va insera de fapt o copie a codului funcție în locul, de unde a fost apelată funcția. Poate că funcția durează doar un ciclu sau două, dar se întâmplă de fiecare dată când o funcție se numește, și dacă încercați să calculeze fișierul 4gig valoarea CRC32, veți vedea de ce unul sau două cicluri pentru fiecare bytes prelucrate poate salva de fapt, o mulțime de timp.
Rețineți: utilizarea funcțiilor încorporate nu trebuie luată ușor. Acest lucru poate duce la o creștere foarte importantă a codului final și poate duce în cele din urmă la performanța generală de aplicare scor mai mic, care consuma prea multă memorie (ceea ce duce la o lipsă de resurse și erori în timpul executării de aplicare). În situația noastră, GetCRC32 este numit foarte limitat și, prin urmare, dimensiunea generală a aplicației nu contează.
De asemenea, vă puteți uita la specificația __fastcall. __fastcall funcționează prin trecerea argumentelor către o funcție prin registrele procesorului, spre deosebire de modul standard de a le trece prin stivă. Acest lucru poate duce la o creștere notabilă a vitezei în același mod ca și inline.
Cu octetul transmis și valoarea precedentă a funcției CRC32, acesta efectuează divizarea polinomului, referindu-se la referința tabelului și actualizarea semnăturii CRC32.
Calcul pentru structuri
Cele două funcții principale anterioare sunt nucleul algoritmului nostru CRC32. Tot ce trebuie să faceți este să citiți datele și, utilizând aceste două funcții, să creați o semnătură CRC32 pentru ele.
DWORD ECRC32. CRC32ByStruct # 40; BYTE * byStruct. DWORD dwSize. DWORD dwCRC32 # 41; # 123;
// Asigurați-vă că avem un STUDIU BYTE valabil
dacă # 40; byStruct == NULL # 41; # 123;
întoarcere - 1;
# 125;
// LOOP CITIT STRUCTURA
pentru # 40; DWORD i = 0; eu
byStruct ++;
# 125;
// FINALIZARE
dwCRC32 =
dwCRC32;
retur 0;
# 125;
Înainte de a umple structura cu datele care urmează să fie procesate, este foarte important să inițializați întreaga structură în NULL, deoarece structurile sunt de obicei completate cu până la 8 octeți. Cu alte cuvinte, dacă aveți o structură care are 7 caractere (7 octeți), sizeof (structura) va returna 8 octeți. Ultimul bit va fi inițializat ca o valoare "gunoi" și nu poate fi același dacă re-creați ulterior structura cu aceleași date. Aceasta va schimba valoarea finală a CRC32. Există o altă opțiune - când transferați dimensiunea structurii, dacă cunoașteți mărimea exactă a structurii fără un separator, puteți utiliza această valoare, ceea ce va determina algoritmul nostru să ignore orice octeți suplimentari de delimitare. Cu toate acestea, nu ar trebui să amestecați cele două metode, deoarece acest lucru va duce la diferite neconcordanțe între valorile CRC32 ale celor două structuri identice.
Calculare pentru dosar
Calculul semnăturii CRC pentru dosar este foarte asemănător și, deși funcția care o face pare oarecum mai complicată - în realitate, nu este. Cu toate acestea, trebuie să adăugăm o funcție suplimentară care va calcula dimensiunea fișierului înainte de procesare.
bool ECRC32. GetFileSize # 40; const HANDLE hFile. DWORD dwSize # 41; # 123;
Trebuie să avem un manevră valabilă
dacă # 40; hFile == INVALID_HANDLE_VALUE # 41; # 123;
return false;
# 125;
// ACUM putem obține dimensiunea fișierului
bool bException = false;
dwSize = 0;
încerca # 123;
// SETEAZĂ VALORILE DE MĂRIMI SUPERIOARE ȘI MAI MULTE
dwSize = GetFileSize # 40; hFile. NULL # 41; ;
dacă # 40; dwSize == INVALID_FILE_SIZE # 41; # 123;
bException = adevărat;
dwSize = 0;
# 125;
# 125;
// NECESITATE SCREWED UP
captură # 40; # 41; # 123;
bException = adevărat;
# 125;
întoarce. bException;
# 125;
Această funcție este numită în interiorul CRC32ByFile, deci nu ar trebui să ne îngrijorăm. Ce se întâmplă în ideal - după ce CRC32ByFile a deschis fișierul specificat (cu succes, aș putea adăuga), se va face o încercare de a transfera pointerul fișierului și pointerul la DWORD, care va returna dimensiunea calculată. Funcția returnează adevărat dacă este posibil.
Codul următor citește fișierul și transmite datele către algoritmul nostru CRC32.
// DESCHIDE FIȘIERUL SPECIFIC
dacă # 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;
// Aceasta înseamnă că avem o eroare
dwErrorCode = - 1;
# 125;
// CALCULAREA SEMNĂRII CRC32
altfel # 123;
BYTE cBuffer # 91; 512 # 93; ;
DWORD dwBytesInOut. dwLoop;
bool bSuccess = fals;
bSuccess = ReadFile # 40; hFile. cBuffer. sizeof # 40; cBuffer # 41;.
dwBytesInOut. NULL # 41; ;
în timp ce # 40; bSuccess dwBytesInOut # 41; # 123;
pentru # 40; dwLoop = 0; dwLoop
bSuccess = ReadFile # 40; hFile. cBuffer. sizeof # 40; cBuffer # 41;. dwBytesInOut. NULL # 41; ;
# 125;
# 125;
Aceasta este o mică bucată de cod din funcția reprezentată în demo care duce fișierul, o deschide, umple bufferul cu date, calculează valoarea CRC32 pentru acele date și repetă până când ajunge la sfârșitul fișierului.
Alte aplicații CRC
CRC32, ca și în jocuri, este, de asemenea, folosit în afara jocurilor din aceleași motive - pentru a verifica integritatea fișierelor și a datelor atunci când sunt copiate cumva.
Extinderea excelentă a acestei metode de utilizare, care este de asemenea utilizată pe scară largă în jocuri, va adăuga valoarea CRC32 la pachetele pe care le trimiteți prin Internet; Acest lucru asigură faptul că datele care ajung la destinație sunt aceleași ca și înainte de a le trimite. Deși protocoalele TCP și UDP stochează valorile CRC în anteturi, ele vor verifica doar modul în care fiecare pachet este transmis. Structurile și datele care sunt trimise în mai multe pachete pot fi eventual deteriorate și utilizate în această formă fără verificarea CRC.
CRC poate fi utilizată chiar din motive de securitate pentru a vă asigura că mesajele text și alte tipuri de mesaje nu sunt modificate intenționat. Acesta este sistemul utilizat în mod obișnuit în PGP atunci când semnați un mesaj astfel încât partea care primește poate verifica dacă acesta a fost trimis de dvs., persoanei care la semnat. PGP nu utilizează CRC32 pentru a crea semnături, algoritmul CRC32 este oarecum slab pentru astfel de situații. Alți algoritmi utilizați în acest scop sunt MD5, SHA8, SHA256 etc. Ele sunt numite algoritmi HASH și sunt folosite de obicei în scopuri de securitate.
Dacă trebuie să utilizați un generator de semnături care produce mai multe valori decât CRC32 și ar trebui să aibă o precizie mai mare decât CRC32, acordați atenție acestor trei algoritmi.
În cele din urmă, dacă aveți orice comentarii, întrebări și așa mai departe, puteți găsi cu ușurință în IRC pe canalul #gamedev sub porecla kurifu sau seta.
Trimiteți-le prietenilor: