Számos lehetőség van a CRC ellenőrző összeg kiszámítására az interneten. De mi is pontosan az ellenőrző összeg, és miért számítják ki így? Találjuk ki.
Utasítás
1. lépés
Először is vegyünk egy kis elméletet. Mi tehát pontosan a CRC? Röviden, ez az ellenőrző összeg kiszámításának egyik fajtája. Az ellenőrző összeg egy módszer a vett információk integritásának ellenőrzésére a vevő oldalon kommunikációs csatornákon történő továbbításkor. Például az egyik legegyszerűbb ellenőrzés a paritásbit használata. Ekkor összesítik az átvitt üzenet összes bitjét, és ha az összeg párosnak bizonyul, akkor az üzenet végéhez 0-t adunk, ha páratlan, akkor 1. Fogadásakor az üzenet összege az üzenetbiteket is megszámoljuk és összehasonlítjuk a vett paritásbitekkel. Ha eltérnek egymástól, akkor hibák történtek az átvitel során, és az átvitt információ torzult.
De ez a módszer a hibák jelenlétének észlelésére nagyon informatív és nem mindig működik, mert ha az üzenet több bitje torzul, az összeg paritása nem változhat. Ezért sokkal több "speciális" ellenőrzés van, beleértve a CRC-t is.
Valójában a CRC nem összeg, hanem annak eredménye, hogy egy bizonyos mennyiségű információt (információs üzenetet) elosztunk egy konstanssal, vagy inkább az üzenet elosztásával fennmaradó részével. A CRC-t azonban történelmileg "ellenőrző összegnek" is nevezik. Az üzenet minden bitje hozzájárul a CRC értékéhez. Vagyis ha az eredeti üzenet legalább egy bitje változik az átvitel során, akkor az ellenőrző összeg is változik, és jelentősen. Ez egy nagy plusz egy ilyen ellenőrzésnek, mivel lehetővé teszi, hogy egyértelműen meghatározza, hogy az eredeti üzenet torzult-e az átvitel során, vagy sem.
2. lépés
Mielőtt elkezdenénk számítani a CRC-t, egy kicsit több elméletre van szükség.
Mi az eredeti üzenet, világosnak kell lennie. Ez tetszőleges hosszúságú bitek összefüggő sorozata.
Mi az a konstans, amellyel fel kellene osztanunk az eredeti üzenetet? Ez a szám szintén bármilyen hosszúságú, de általában 1 bájt többszörösét használják - 8, 16 és 32 bit. Csak könnyebb megszámolni, mert a számítógépek bájttal dolgoznak, nem bitekkel.
Az osztóállandót általában polinomként (polinomként) írjuk így: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Itt az "x" szám mértéke az egy bit helyét jelenti a számban, nullától kezdve, a legjelentősebb bit pedig a polinom mértékét jelzi, és a szám értelmezésekor elvetésre kerül. Vagyis az előzőleg írt szám nem más, mint (1) 00000111 bináris formában, vagy 7 decimálisban. Zárójelben feltüntettem a szám implicit legjelentősebb számjegyét.
Itt van egy másik példa: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Általában néhány szokásos polinomot használnak a különböző típusú CRC-khez.
3. lépés
Tehát hogyan számolja ki az ellenőrző összeget? Létezik egy alapvető módszer - az üzenet felosztása polinomra "front-on" - és annak módosításai a számítások számának csökkentése és ennek megfelelően a CRC számításának felgyorsítása érdekében. Megnézzük az alapvető módszert.
Általában a szám polinommal történő felosztását a következő algoritmus szerint hajtják végre:
1) létrejön egy tömb (regiszter), amely nullákkal van kitöltve, hossza megegyezik a polinom szélességének hosszával;
2) az eredeti üzenetet nullákkal egészítik ki a legkevésbé jelentős bitekben, a polinom bitjeinek számával megegyező mennyiségben;
3) az üzenet egy legjelentősebb bitjét a regiszter legkevésbé jelentő bitjébe írják be, és egy bitet a nyilvántartás legjelentősebb bitjéből;
4) ha a kibővített bit egyenlő "1" -vel, akkor a bitek megfordulnak (XOR művelet, kizárólagos OR) azokban a regiszterbitekben, amelyek megfelelnek a polinomban levőknek;
5) ha még mindig vannak bitek az üzenetben, folytassa a 3. lépéssel;
6) Amikor az üzenet összes bitje belépett a regiszterbe és ezen algoritmus feldolgozta őket, az osztás fennmaradó része a nyilvántartásban marad, ami a CRC ellenőrző összeg.
Az ábra szemlélteti az eredeti bitsorozat felosztását az (1) 00000111 számmal vagy az x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0 polinommal.
4. lépés
Van még néhány további érintés. Mint észrevette, az üzenet tetszőleges számmal felosztható. Hogyan válasszuk ki? A CRC kiszámításához számos szabványos polinom létezik. Például a CRC32 esetében 0x04C11DB7, a CRC16 esetében pedig 0x8005 lehet.
Ezenkívül a számítás elején található regiszterbe nem nullákat írhat, hanem valamilyen más számot.
A számítások során, közvetlenül a végleges CRC ellenőrző összeg kiadása előtt, fel lehet őket osztani más számmal.
És az utolsó dolog. Az üzenet bájtjai, amikor a regiszterbe írnak, elhelyezhetők a legjelentősebb "előre" bitként, és fordítva, a legkevésbé jelentős bitként.
5. lépés
A fentiek alapján írjunk egy Basic. NET függvényt, amely kiszámítja a CRC ellenőrző összegét úgy, hogy számos olyan paramétert vesz fel, amelyet fent leírtam, és a CRC értékét 32 bites előjel nélküli számként adta vissza.
Nyilvános megosztott függvény GetCrc (ByVal bájtok byte-ként (), ByVal poly mint UInteger, Opcionális ByVal szélességek Integer = 32, Opcionális ByVal initReg As UInteger = & HFFFFFFFFUI, Opcionális ByVal finalXor As UInteger = & HFFFFFFalFal Berse, Opcionális By reverseCrc As Boolean = True) UInteger-ként
Dim widthInBytes As Integer = szélesség / 8
'Kiegészítse az üzenet szélességét nullákkal (számítás bájtban):
ReDim Bájtok megőrzése (bájtok. Hossz - 1 + szélességInBytes)
'Hozzon létre egy kis sort az üzenetből:
Dim msgFifo új várólistaként (logikai értékből) (bájtok száma * 8 - 1)
Minden b bájtra bájtban
Dim ba új BitArray-ként ({b})
Ha reverseBytes Akkor
Mert i As egész szám = 0 és 7 között
msgFifo. Enqueue (ba (i))
Következő
Más
Az i As egész szám = 7-től 0-ig -1
msgFifo. Enqueue (ba (i))
Következő
Vége Ha
Következő
'Hozzon létre egy sort a regiszter kezdeti kitöltő bitjeiből:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed as IEnumerable (Of Byte) = (b-ből Byte-ként In InitBytes vegye a widthInBytes értéket).
Dim initFifo, mint új várólista (logikai értékből) (szélesség - 1)
Minden b bájtra az initBytesReversedben
Dim ba új BitArray-ként ({b})
Ha nem reverseBytes Akkor
Mert i As egész szám = 0 és 7 között
initFifo. Enqueue (ba (i))
Következő
Más
Az i As egész szám = 7-től 0-ig -1
initFifo. Enqueue (ba (i))
Következő
Vége Ha
Következő
„Shift és XOR:
Dim register Mivel UInteger = 0 'töltse ki a szélességű bites regisztert nullákkal.
Do while msgFifo. Count> 0
Dim poppedBit As Integer = CInt (regisztráció >> (szélesség - 1)) És 1 'határozza meg a shift regiszter előtt.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Ha az initFifo. Count> 0 Akkor
Dim b As Byte = Konvertálás ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Vége Ha
regisztráció = regisztráció << 1
register = regisztráció Vagy shiftedBit
Ha poppedBit = 1 Akkor
regisztráció = regisztráció Xor poly
Vége Ha
Hurok
'Végső konverziók:
Dim crc As UInteger = register 'A regisztráció a == ellenőrző összeg maradékát tartalmazza.
Ha fordítottCrc Akkor
crc = visszaverődés (crc, szélesség)
Vége Ha
crc = crc Xor finalXor
crc = crc És (& HFFFFFFFFUU >> (32 - szélesség)) 'eltakarja a legkevésbé jelentős biteket.
Vissza crc
Funkció befejezése
