Existuje mnoho možností pro výpočet kontrolního součtu CRC na internetu. Ale co přesně je kontrolní součet a proč se počítá tímto způsobem? Pojďme na to přijít.
Instrukce
Krok 1
Nejprve pojďme trochu teorie. Co přesně je tedy CRC? Stručně řečeno, jedná se o jednu z variant výpočtu kontrolního součtu. Kontrolní součet je metoda kontroly integrity přijímaných informací na straně přijímače při přenosu přes komunikační kanály. Jednou z nejjednodušších kontrol je například použití paritního bitu. To je, když jsou všechny bity přenášené zprávy sečteny, a pokud se součet ukáže jako sudý, pak se na konec zprávy přidá 0, pokud je lichá, pak 1. Při příjmu je součet bity zpráv se také počítají a porovnávají s přijatým paritním bitem. Pokud se liší, došlo během přenosu k chybám a přenášené informace byly zkresleny.
Ale tato metoda detekce přítomnosti chyb je velmi neinformativní a ne vždy funguje, protože pokud je zkresleno několik bitů zprávy, parita součtu se nemusí změnit. Existuje tedy mnohem více „pokročilých“kontrol, včetně CRC.
CRC ve skutečnosti není součet, ale výsledek rozdělení určitého množství informací (informační zprávy) konstantou, respektive zbytku rozdělení zprávy konstantou. CRC se však také historicky označuje jako „kontrolní součet“. Každý bit zprávy přispívá k hodnotě CRC. To znamená, že pokud se během přenosu změní alespoň jeden bit původní zprávy, změní se také kontrolní součet, a to výrazně. To je velká výhoda takové kontroly, protože vám umožňuje jednoznačně určit, zda byla původní zpráva během přenosu zkreslena nebo ne.
Krok 2
Než začneme počítat CRC, je zapotřebí trochu více teorie.
Jaká je původní zpráva by měla být jasná. Jedná se o souvislou sekvenci bitů libovolné délky.
Jaká je konstanta, kterou bychom měli rozdělit původní zprávu? Toto číslo má také libovolnou délku, ale obvykle se používají násobky 1 bajtu - 8, 16 a 32 bitů. Počítání je snazší, protože počítače pracují s bajty, ne s bity.
Konstanta dělitele se obvykle píše jako polynom (polynom), jako je tento: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Zde míra čísla „x“znamená pozici jednobitu v čísle, počínaje od nuly, a nejvýznamnější bit označuje stupeň polynomu a je při interpretaci čísla vyřazen. To znamená, že dříve napsané číslo není nic jiného než (1) 00000111 v binárním formátu nebo 7 v desítkovém formátu. V závorkách jsem označil implicitní nejvýznamnější číslici čísla.
Zde je další příklad: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Obvykle se pro různé typy CRC používají některé standardní polynomy.
Krok 3
Jak tedy spočítat kontrolní součet? Existuje základní metoda - rozdělení zprávy na polynomiální „čelní“- a její úpravy, aby se snížil počet výpočtů a podle toho urychlil výpočet CRC. Podíváme se na základní metodu.
Obecně se dělení čísla polynomem provádí podle následujícího algoritmu:
1) je vytvořeno pole (registr), vyplněné nulami, stejné délky jako délka polynomiální šířky;
2) původní zpráva je doplněna nulami v nejméně významných bitech v množství rovnajícím se počtu bitů polynomu;
3) jeden nejvýznamnější bit zprávy je zadán do nejméně významného bitu registru a jeden bit je přesunut z nejvýznamnějšího bitu registru;
4) je-li rozšířený bit roven „1“, pak jsou bity invertovány (operace XOR, výlučně OR) v těch registrových bitech, které odpovídají těm v polynomu;
5) pokud jsou ve zprávě stále bity, přejděte ke kroku 3);
6) když všechny bity zprávy vstoupily do registru a byly zpracovány tímto algoritmem, zbytek divize zůstane v registru, což je kontrolní součet CRC.
Obrázek ilustruje rozdělení původní bitové sekvence číslem (1) 00000111 nebo polynomem x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Krok 4
Zbývá několik dalších dotyků. Jak jste si možná všimli, zprávu lze rozdělit na libovolné číslo. Jak vybrat? Existuje několik standardních polynomů, které se používají k výpočtu CRC. Například pro CRC32 to může být 0x04C11DB7 a pro CRC16 to může být 0x8005.
Navíc do registru na začátku výpočtu můžete psát ne nuly, ale nějaké jiné číslo.
Rovněž je lze během výpočtů, bezprostředně před vydáním konečného kontrolního součtu CRC, vydělit jiným číslem.
A poslední věc. Bajty zprávy při zápisu do registru lze umístit jako nejvýznamnější bit „vpřed“a naopak jako nejméně významný.
Krok 5
Na základě všeho výše, pojďme napsat základní funkci. NET, která vypočítá kontrolní součet CRC tím, že vezme řadu parametrů, které jsem popsal výše, a vrátí hodnotu CRC jako 32bitové nepodepsané číslo.
Sdílená veřejná funkce GetCrc (ByVal bajty As Byte (), ByVal poly As UInteger, volitelná šířka ByVal As Integer = 32, volitelná ByVal initReg As UInteger = & HFFFFFFFFUI, volitelná ByVal finalXor jako UInteger = & HFFFFFFFFUI, volitelná ByVal reverbytean, volitelná ByVal reverzní reverseCrc As Boolean = True) Jako UInteger
Dim widthInBytes As Integer = width / 8
„Doplňte šířku zprávy nulami (výpočet v bajtech):
ReDim Zachovat bajty (bajty Délka - 1 + widthInBytes)
„Vytvořte ze zprávy bitovou frontu:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Pro každé b jako bajt v bajtech
Dim ba jako nový BitArray ({b})
If reverseBytes Then
Pro i As Integer = 0 až 7
msgFifo. Enqueue (ba (i))
další
Jiný
Pro i As Integer = 7 až 0, krok -1
msgFifo. Enqueue (ba (i))
další
Konec Pokud
další
„Vytvořte frontu z počátečních výplňových bitů registru:
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)
Pro každé b jako Byte In initBytesReversed
Dim ba jako nový BitArray ({b})
Pokud ne reverseBytes Then
Pro i As Integer = 0 až 7
initFifo. Enqueue (ba (i))
další
Jiný
Pro i As Integer = 7 až 0, krok -1
initFifo. Enqueue (ba (i))
další
Konec, pokud
další
„Shift a XOR:
Ztlumit registr Jako UInteger = 0 'vyplňte registr šířkových bitů nulami.
Do While msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) And 1 'define before shift register.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Pokud initFifo. Count> 0 pak
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xnebo b
Konec Pokud
registrovat = registrovat << 1
register = register Nebo shiftedBit
Pokud poppedBit = 1 Pak
register = registr Xor poly
Konec Pokud
Smyčka
„Konečné převody:
Dim crc As UInteger = register 'Registr obsahuje zbytek divize == kontrolní součet.
Pokud reverseCrc Pak
crc = odrážet (crc, šířka)
Konec, pokud
crc = crc Xor finalXor
crc = crc And (& HFFFFFFFFUI >> (32 - width)) 'maskují nejméně významné bity.
Zpět crc
Ukončit funkci
