Ciklusos redundanciaellenőrzés (crc32), leckék és programozási példák

Clifford M. Roche által

előszó

A matematika (a szétválasztási polinom) kevés értelmezése hasznos lehet, de ezt a cikket azért írom, hogy nem feltétlenül szükséges. Önnek azonban meg kell értenie a C ++ -ot - ez magától értetődő.

Miért használja a CRC32-et?

Kellett ez az egyik a kisebb projektek - úgy döntöttem, hogy írjon egy kérelmet az online frissítéseket, amelyek egyszerűen létrehoz egy egyedi aláírás egy sor fájl, összehasonlítja ezeket az értékeket az aláírás törzslistájában a szerveren, és frissíti a fájlokat, amelyek nem felelnek meg az aláírást.

Számos mód van arra, hogy ellenőrizzem a fájlok sértetlenségét és eldönthessem, hogy a fő szerverről frissíteni kell őket. A létrehozás / időbélyeg idő, a fájlméret és a CRC32 elképzelhető. Vannak olyan nyilvánvalóan bonyolultabb módszerek is, például a fájlok nyilvántartása az adatbázisban, de nem kell bonyolítani a dolgokat túlságosan. Ugyanez érvényes a CRC32 legtöbb játékfelhasználására is. Ezenkívül a legtöbb összetettebb algoritmus sokkal több számítást próbál ki, mint a CRC32.

A CRC32, az összes bemutatott lehetőségek, jelenleg a legmegfelelőbb, mivel nem kell aggódnia a fájlok, amelyek az azonos méretű, vagy módosítás dátuma (igen gyakran előfordul, raszteres képek, valamint számos más közös típusú játék fájlokat), és mi nincs okunk aggódni pontatlan ideje fájl létrehozása / időbélyege miatt változik. Bár CRC32 algoritmus nem tökéletes, és mindig van esély arra, hogy a 2 fájlt lesz ugyanazt az értéket CRC32, ezekben az esetekben olyan ritka, hogy CRC32 lesz az ideális jelölt a generáció egy aláírás fájlt.

A CRC32 érték egy 32 bites (4 bájtos) számot (más néven aláírásként) tartalmaz, amely egyedileg azonosítja a megadott adatot. A CRC32 előnye az ellenőrző aláírások számára az, hogy algoritmusa úgy van megtervezve, hogy a kis változások a fájlban (akár változóak legyenek, akár törölhetők vagy beilleszthetők legyenek) nagy változásokat kell okozniuk a CRC32 aláírásban. A CRC32 2 ^ 32 lehetséges értéket tartalmaz; összesen 4.294967E +09.

Ezen okok miatt a CRC32 aláírások nagyon hasznosak a játékokban, mivel a kreativitás helyét hagyja. Ezeket fel lehet használni, hogy ellenőrizze a fájl látni, hogy a változás, amely segít megelőzni megpróbálja csapkod a játék céljára csalás, vagy fel lehet használni, hogy átvizsgálja a fájlokat vagy adatokat továbbítanak az interneten keresztül a játék során, mint például a térkép fájl, például .

Hogyan működik a CRC32?

A CRC32 egy kissé összetett folyamat, és sok matematikai műveletből áll. De itt van, hogy általában működik:

Először a polinom értéke lesz, és ezzel az értékkel CRC32 keresést generálunk. A cikk végén megmutatom, hogyan hozhat létre helyesen áttekintő táblát ezzel a polinommal. Következő vesszük az adatokat, hogy azt akarjuk, hogy létrehoz egy CRC32 aláírását, és a speciális funkciót generál frissített CRC32 értéket minden egyes bájt a fájlban, string vagy szerkezet, amit ellenőrizni. Ez minden karakterláncban, struktúrában vagy fájlban található. A befejezés után a legfrissebb érték az aláírás.

A CRC32 algoritmus szíve egy egyszerű rendszer, amely a továbbított bájtot kiszámolja az adatkészletből, és a CRC32 aktuális értékét, amit keresünk, és keresést végez a áttekintő táblázatban. Ha nincs aktuális CRC32 érték, használnunk kell a 0xFFFFFFFF értéket. Egy kis matematika, vagyis a megosztási polinom, és a függvény visszaadja a CRC32 frissített értékét.

A megvalósítás nagyon egyszerű.

Tehát az osztályunk kinézni fog.

osztályú ECRC32 # 123;
nyilvánosság számára.
statikus DWORD CRC32ByString # 40; LPCTSTR. DWORD # 41; ;
statikus DWORD CRC32ByFile # 40; LPCTSTR. DWORD # 41; ;
statikus DWORD CRC32ByStruct # 40; BYTE *, DWORD. DWORD # 41; ;

privát.
statikus bool GetFileSize # 40; Kezelni. DWORD # 41; ;
statikus inline void GetCRC32 # 40; BYTE. DWORD # 41; ;

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

Egyszerű - minden olyan típusú adatnak van funkciója, amelyet használni akarunk, ami CRC32 aláírásokat generál számukra. Két magánfunkciójuk is van, az egyik kiszámolja a fájlméretet - a belső algoritmusok megfelelő működéséhez, a második pedig egy másik matematika elvégzéséhez és egy adott byte CRC32 értékének frissítéséhez.

Van egy statikus tömb, egyszerűen tárolja a CRC32 táblát számunkra. Valójában nem kell állandóan tartania ezt a táblát, ha nem akarja. A konstruktor és a destructor használatával csak akkor hozhatja létre és tisztíthatja meg a táblát, ha azt tervezi. Célunk célszerűbb az asztal használata, mivel ez jelentősen csökkentheti a feldolgozási időt.

Keresési táblázat létrehozása

Keresési tábla létrehozásához meg kell adnia egy polinomi értéket a felhasználáshoz, amely megadja nekünk a táblázatban használt értékeket. A polinomiális értéknek elméletileg csökkentenie kell a duplikált aláírások valószínűségét az adatokban, azonban az egyik ilyen érték mögötti matematika túl bonyolult és túlmutat e cikkben. Ez normális, mert már választottuk az optimális értéket. A táblázat létrehozásához használt érték 0x04c11db7 lesz.

Következésképpen ezt a polinomot számos más alkalmazás és rendszer használja, például WinZip, PKZip és Ethernet.

Megjegyzés: Az asztalt legalább egyszer kell létrehoznia, még akkor is, ha fix táblázatot használ. Ha természetesen a demóban bemutatott táblázatot használod.

Mielőtt folytatnánk - a standard CRC-állapotok, amelyeknek tükrözniük kell a keresési táblázatban szereplő értékeket, amelyek a polinom tükrözésével hajthatók végre. Ebben az esetben 0x04c11db7 lesz 0xedb88320. Bár egyes egyenletek tükrözik a táblázatban szereplő értékeket, mivel létrehozzák őket, a polinomot tükrözni fogom. Végül ez csak az a tény, hogy kevesebb kódot használunk.

Megjegyzés: A reflexió egy egyszerű fordított eljárás az adott bináris szegmens bináris szerkezetére. Például a 10100111 a 11100101 tükrözésével válik.

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

CRC32Table = új DWORD # 91; 256 # 93; ;

DWORD dwCRC;
mert # 40; int i = 0; én <256 ; i ++ )
# 123;
dwCRC = i;

mert # 40; int j = 8; j> 0; j - # 41;
# 123;
ha # 40; dwCRC 1 # 41;
dwCRC = # 40; dwCRC >> 1 # 41; ^ dwPolynomial;
más
dwCRC >> = 1;
# 125;

CRC32Table # 91; én # 93; = dwCRC;
# 125;

Egy egyszerű hurok az összes 256 bejegyzésen és a keresési értékek létrehozása a polinomiagában található pozíció alapján.

A helyzetétől függően előfordulhat, hogy nem kíván költeni CPU ciklust a regeneráló tábla mentéséhez, amikor aláírást szeretne létrehozni. Ha ez a helyzet, egyszerűen jelölje ki ezt a kódot egy különálló alkalmazásban, mentse el a táblák dumpját a fájlra, a képernyőre vagy bárhol a legkényelmesebbé, majd másolja be és illessze be az értékeket közvetlenül a táblába. Bár 256 * 4 bájtnyi memória áron (ami valójában nem sok), drámaian javíthatja a számítási időt anélkül, hogy folyamatosan újraszámozná az asztalokat.

Azok számára, akik a fent felsorolt ​​polinommal próbálnak táblát létrehozni, az első 14 értéknek így kell kinéznie:

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

Calculation CRC32

Miután megkerestük a keresési táblázatot, megnézzük a GetCRC32 funkciót. Ez a függvény egy byte-ot és a CRC32 előző számított értékét veszi (ha létezik).

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;

Az első dolog megjegyezni, hogy a funkció be van építve. Azoknak, akik nem értik ezt a funkciót, ahol a kódot, vagy hívásokat kezdeményezhetnek, ami működik, hanem apryganiya helyre funkciók a memóriában minden alkalommal (ami többet fogyasztanak ciklus), a processzor valójában be egy példányt a funkció kódot a helyén, ahonnan a függvényt hívták. Lehet, hogy a függvény csak egy ciklust, vagy kettő, de ez történik minden alkalommal, amikor egy függvény meghívásakor és ha megpróbál kiszámításához CRC32 érték 4gig fájlt, látni fogja, hogy miért egy vagy két ciklus minden egyes feldolgozott bájtok ténylegesen menteni egy csomó időt.

Kérjük, vegye figyelembe: a beépített funkciók használata nem szabad könnyedén figyelembe venni. Ez ahhoz vezethet, hogy egy nagyon jelentős növekedés a végső kódot, és végül a pontszám összességében alacsonyabb alkalmazások teljesítményét, fogyaszt túl sok memóriát (ami vezet forráshiány és a hibák az alkalmazás során végrehajtását). A helyzetünkben a GetCRC32-t nagyon korlátozottnak nevezzük, ezért az alkalmazás teljes mérete nem számít.

Az __fastcall specifikációkat is megtekintheti. A __fastcall úgy működik, hogy argumentumokat ad át egy függvénynek a processzor regiszterein keresztül, ellentétben a szabványos átirányítással. Ez a sebesség gyorsabb növekedéséhez vezethet ugyanúgy, mint az inline.

A továbbított bájt és a korábbi CRC32 funkcióértékével a polinomiális megosztást hajtja végre, hivatkozva a táblázat referenciájára és a CRC32 aláírási frissítésre.

A szerkezetek számítása

A két korábbi fő funkció a CRC32 algoritmus lényege. Mindössze annyit kell tennie, hogy elolvassa az adatokat, és e két funkció használatával hozzon létre egy CRC32 aláírást számukra.

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

FIGYELEM VESZÉLYES, HOGY VALÓ BÁZIS ÁLMÁNYÁT
ha # 40; byStruct == NULL # 41; # 123;
visszatérés - 1;
# 125;

// LOOP A SZERKEZET ELLENÉRE
mert # 40; DWORD i = 0; én GetCRC32 # 40; * byStruct. dwCRC32 # 41; ;
byStruct ++;
# 125;

// FINISH UP
dwCRC32 =

dwCRC32;
visszatérés 0;
# 125;

Mielőtt a felépítendő adatokat feltöltené a feldolgozandó adatokkal, nagyon fontos az egész struktúra NULL-ban történő inicializálása, mivel a struktúrákat általában legfeljebb 8 bájttal egészítik ki. Más szóval, ha olyan struktúrája van, amely 7 karakterből áll (7 byte), a sizeof (struktúra) 8 bájtot ad vissza. Az utolsó bit inicializálódik "szemét" értékként, és nem lehet ugyanaz, ha később ugyanazokkal az adatokkal újra létrehozza a struktúrát. Ez megváltoztatja a CRC32 végső értékét. Van egy másik lehetőség - ha a struktúra méretét átmásoljuk, ha tudod a struktúra pontos méretét elválasztó nélkül, használd ezt az értéket, ami az algoritmusunkra figyelmen kívül hagy minden további határoló bájtot. Mindazonáltal nem szabad összekeverni a két módszert, mert ez különböző eltéréseket eredményez a két azonos struktúra CRC32 értékei között.

Fájlszámítás

A fájl CRC aláírásának kiszámítása nagyon hasonló, és bár ez a funkció némileg bonyolultabbnak tűnik - valójában nem. Azonban meg kell adnunk egy kiegészítő funkciót, amely kiszámítja a fájlméretet a feldolgozás előtt.

bool ECRC32. GetFileSize # 40; const HANDLE hFile. DWORD dwSize # 41; # 123;
// VONATKOZÓAN KELL HASZNÁLNI
ha # 40; hFile == INVALID_HANDLE_VALUE # 41; # 123;
return false;
# 125;

// MOST ELFOGADNI A FÁJL MÉRETE
bool bException = hamis;
dwSize = 0;

megpróbál # 123;
// A FELSŐ ÉS ALSÓ MÉRET ÉRTÉKÉT
dwSize = GetFileSize # 40; hFile. NULL # 41; ;

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

// VÁLOGATOTT VAGY MINDEN
fogás # 40;. # 41; # 123;
bException = true;
# 125;

visszatéréshez. bException;
# 125;

Ezt a funkciót a CRC32ByFile belsejében hívják, így nem szabad aggódnunk. Mi történik az ideális esetben - miután a CRC32ByFile megnyitotta a megadott fájlt (sikeresen hozzáadhattam), kísérletet fog tenni a fájlmutató és a mutató DWORD fájlba való átvitelére, amely visszaadja a kiszámított méretet. A funkció akkor igaz, ha lehetséges.

A következő kód ténylegesen elolvassa a fájlt, és átadja az adatokat a CRC32 algoritmusunknak.

// NYOMJA MEG A MEGFIGYELT FÁJL
ha # 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;
Ez azt jelenti, hogy hiba van
dwErrorCode = - 1;
# 125;

// A CRC32 ALAPÍTVÁNY Kalkulálása
más # 123;
BYTE cBuffer # 91; 512 # 93; ;
DWORD dwBytesInOut. dwLoop;
bool bSuccess = hamis;

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

míg # 40; bSuccess dwBytesInOut # 41; # 123;
mert # 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;

Ez egy kicsi kódkód a demóban megjelenő függvényből, amely átveti a fájlt, megnyitja azt, kitölti a puffer adatait, kiszámolja az adatok CRC32 értékét, és megismétli, amíg el nem éri a fájl végét.

Egyéb CRC alkalmazások

A CRC32-et, hasonlóan a játékokhoz, ugyanazon okok miatt kívül is használják a játékokon - a fájlok és az adatok sértetlenségének ellenőrzésére, amikor valahogy másolják őket.

Ez a felhasználási mód, amelyet széles körben használnak a játékokban, kiválóan bővíti a CRC32 értéket az Interneten keresztül küldött csomagokhoz; Ez biztosítja, hogy a rendeltetési helyre érkező adatok ugyanazok legyenek, mint a küldés előtt. Bár a TCP és UDP protokollok CRC értékeket tárolnak a fejlécekben, csak ellenőrizni fogják az egyes csomagok továbbítását. A több csomagban elküldött struktúrák és adatok végül károsodhatnak és használhatók ebben a formában CRC ellenőrzés nélkül.

A CRC biztonsági okokból is felhasználható annak biztosítására, hogy a szöveges üzenetek és más típusú üzenetek szándékosan nem változnak meg. Ez a rendszer, amelyet általában a PGP-ben használnak, amikor aláírja az üzenetet oly módon, hogy a fogadó fél ellenőrizheti, hogy az Ön által küldött, az aláíró személy számára. A PGP nem használja a CRC32-et aláírás létrehozásához, a CRC32 algoritmus némileg gyenge az ilyen helyzetekben. Az erre a célra használt egyéb közös algoritmusok az MD5, SHA8, SHA256 stb. Ezeket HASH algoritmusoknak nevezik, és általában biztonsági célokat szolgálnak.

Ha olyan aláíró generátort kell használni, amely több értéket produkál, mint a CRC32, és nagyobb pontossággal kell rendelkeznie, mint a CRC32, akkor vegye figyelembe a három algoritmust.

Végül, ha bármilyen megjegyzésed, kérdéseid vannak, és így tovább, könnyen megtalálhatsz irc-ban a #gamedev csatornán a kurifu becenév alatt.