Na internete existuje veľa možností na výpočet kontrolného súčtu CRC. Čo však vlastne je kontrolný súčet a prečo sa počíta takto? Poďme na to.
Inštrukcie
Krok 1
Po prvé, poďme trochu teórie. Čo to teda CRC vlastne je? Stručne povedané, toto je jedna z odrôd výpočtu kontrolného súčtu. Kontrolný súčet je metóda kontroly integrity prijatých informácií na strane prijímača pri prenose cez komunikačné kanály. Napríklad jednou z najjednoduchších kontrol je použitie paritného bitu. To je prípad, keď sú všetky bity prenášanej správy sčítané a ak sa súčet ukáže ako párny, potom sa na koniec správy pripočíta 0, ak je nepárna, potom 1. Pri príjme je súčet sa tiež počítajú bitové správy a porovnávajú sa s prijatým paritným bitom. Ak sa líšia, došlo počas prenosu k chybám a prenášané informácie boli skreslené.
Ale táto metóda zisťovania prítomnosti chýb je veľmi neinformačná a nie vždy funguje, pretože ak je niekoľko bitov správy skreslených, parita súčtu sa nemusí meniť. Preto existuje oveľa viac „pokročilých“kontrol vrátane CRC.
CRC v skutočnosti nie je súčet, ale výsledok rozdelenia určitého množstva informácií (informačnej správy) konštantou, respektíve zvyšku rozdelenia správy konštantou. CRC sa však tiež historicky označuje ako „kontrolný súčet“. Každý bit správy prispieva k hodnote CRC. To znamená, že ak sa počas prenosu zmení aspoň jeden bit pôvodnej správy, zmení sa tiež kontrolný súčet a to výrazne. To je veľké plus takejto kontroly, pretože vám umožňuje jednoznačne určiť, či bola pôvodná správa počas prenosu skreslená alebo nie.
Krok 2
Predtým, ako začneme počítať CRC, je potrebných trochu viac teórie.
Aká je pôvodná správa, malo by byť jasné. Je to súvislá postupnosť bitov ľubovoľnej dĺžky.
Aká je konštanta, ktorou by sme mali rozdeliť pôvodnú správu? Toto číslo má tiež ľubovoľnú dĺžku, zvyčajne sa však používajú násobky 1 bajtu - 8, 16 a 32 bitov. Je to jednoduchšie počítať, pretože počítače pracujú s bajtmi, nie s bitmi.
Konstanta deliteľa sa zvyčajne píše ako polynóm (polynóm), ako je tento: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Stupeň čísla „x“tu znamená polohu jednobitu v čísle, počnúc od nuly, a najvýznamnejší bit označuje stupeň polynómu a pri interpretácii čísla sa zahodí. To znamená, že predtým napísané číslo nie je nič iné ako (1) 00000111 v binárnom formáte alebo 7 v desatinnom čísle. V zátvorkách som označil implikovanú najvýznamnejšiu číslicu čísla.
Tu je ďalší príklad: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Zvyčajne sa pre rôzne typy CRC používajú niektoré štandardné polynómy.
Krok 3
Ako teda vypočítate kontrolný súčet? Existuje základná metóda - rozdelenie správy na polynomiálny „head-on“- a jej úpravy, aby sa znížil počet výpočtov a podľa toho urýchlil výpočet CRC. Pozrime sa na základnú metódu.
Všeobecne sa delenie čísla polynómom vykonáva podľa nasledujúceho algoritmu:
1) vytvorí sa pole (register) naplnené nulami, ktorých dĺžka sa rovná dĺžke šírky polynómu;
2) pôvodná správa je doplnená nulami v najmenej významných bitoch v množstve rovnajúcom sa počtu bitov polynómu;
3) jeden najvýznamnejší bit správy je vložený do najmenej významného bitu registra a jeden bit je presunutý z najvýznamnejšieho bitu registra;
4) ak je rozšírený bit rovný „1“, potom sú bity invertované (operácia XOR, výhradne OR) v tých registrových bitoch, ktoré zodpovedajú tým v polynóme;
5) ak v správe sú stále bity, prejdite na krok 3);
6) keď všetky bity správy vstúpili do registra a boli spracované týmto algoritmom, zvyšok divízie zostane v registri, čo je kontrolný súčet CRC.
Obrázok ilustruje rozdelenie pôvodnej postupnosti bitov číslom (1) 00000111 alebo polynómom x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Krok 4
Zostáva niekoľko ďalších dotykov. Ako ste si mohli všimnúť, správu je možné rozdeliť na ľubovoľné číslo. Ako si to vybrať? Existuje niekoľko štandardných polynómov, ktoré sa používajú na výpočet CRC. Napríklad pre CRC32 to môže byť 0x04C11DB7 a pre CRC16 to môže byť 0x8005.
Okrem toho do registra na začiatku výpočtu môžete napísať nie nuly, ale nejaké iné číslo.
Počas výpočtov ich tiež môžeme tesne pred vydaním konečného kontrolného súčtu CRC vydeliť iným číslom.
A posledná vec. Bajty správy pri zápise do registra môžu byť umiestnené ako najvýznamnejší bit „vpred“a naopak, najmenej významný.
Krok 5
Na základe všetkého vyššie uvedeného napíšme funkciu Basic. NET, ktorá počíta kontrolný súčet CRC tak, že vezmeme množstvo parametrov, ktoré som popísal vyššie, a vrátime hodnotu CRC ako 32-bitové nepodpísané číslo.
Verejne zdieľaná funkcia GetCrc (ByVal bajty As Byte (), ByVal poly As UInteger, voliteľné ByVal šírka As Integer = 32, voliteľné ByVal initReg As UInteger = & HFFFFFFFFUI, voliteľné ByVal finalXor ako UInteger = & HFFFFFFFFUI, voliteľné ByVal reverzné bajty, voliteľné ByVal reverzné reverseCrc As Boolean = True) Ako UInteger
Dim widthInBytes As Integer = width / 8
„Doplňte šírku správy nulami (výpočet v bajtoch):
ReDim Zachovať bajty (bajty. Dĺžka - 1 + šírkaInBytes)
„Vytvorte zo správy bitový rad:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Pre každé b Ako Byte V bytoch
Dim ba as New BitArray ({b})
Ak reverseBytes Potom
Pre i ako celé číslo = 0 až 7
msgFifo. Enqueue (ba (i))
Ďalšie
Inak
Pre i As Integer = 7 až 0, krok -1
msgFifo. Enqueue (ba (i))
Ďalšie
Koniec Ak
Ďalšie
„Vytvorte rad z počiatočných plniacich bitov registra:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes).
Dim initFifo As New Queue (Of Boolean) (width - 1)
Pre každé b ako Byte In initBytesReversed
Dim ba as New BitArray ({b})
Ak nie je reverseBytes potom
Pre i ako celé číslo = 0 až 7
initFifo. Enqueue (ba (i))
Ďalšie
Inak
Pre i As Integer = 7 až 0, krok -1
initFifo. Enqueue (ba (i))
Ďalšie
Koniec Ak
Ďalšie
„Shift a XOR:
Dim register As UInteger = 0 'vyplňte register so šírkou bitov nulami.
Robiť Kým msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (šírka - 1)) A 1 'definovať pred posuvným registrom.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Ak initFifo. Count> 0 potom
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit X alebo b
Koniec Ak
register = registrovať << 1
register = register Alebo shiftedBit
Ak poppedBit = 1 Potom
register = register Xor poly
Koniec Ak
Slučka
„Konečné prepočty:
Dim crc As UInteger = register 'Register obsahuje zvyšok divízie == kontrolný súčet.
Ak reverseCrc Potom
crc = odrážať (crc, šírka)
Koniec Ak
crc = crc Xor finalXor
crc = crc And (& HFFFFFFFFUI >> (32 - width)) 'maskuje najmenej významné bity.
Vrátiť crc
Koncová funkcia
