Istnieje wiele opcji obliczania sumy kontrolnej CRC w Internecie. Ale czym właściwie jest suma kontrolna i dlaczego jest obliczana w ten sposób? Rozwiążmy to.
Instrukcje
Krok 1
Najpierw trochę teorii. Czym dokładnie jest CRC? Krótko mówiąc, jest to jedna z odmian obliczania sumy kontrolnej. Suma kontrolna to metoda sprawdzania integralności odebranych informacji po stronie odbiorcy podczas transmisji przez kanały komunikacyjne. Na przykład jednym z najprostszych testów jest użycie bitu parzystości. Dzieje się tak, gdy sumuje się wszystkie bity przesłanej wiadomości, a jeśli suma okaże się parzysta, to na końcu wiadomości dodawane jest 0, jeśli nieparzyste, to 1. Przy odbiorze suma bity komunikatu są również zliczane i porównywane z odebranym bitem parzystości. Jeśli się różnią, to wystąpiły błędy podczas transmisji i przesyłane informacje były zniekształcone.
Ale ta metoda wykrywania obecności błędów jest bardzo mało informacyjna i nie zawsze działa, ponieważ jeśli kilka bitów wiadomości jest zniekształconych, parzystość sumy może się nie zmienić. Dlatego istnieje znacznie więcej „zaawansowanych” kontroli, w tym CRC.
W rzeczywistości CRC nie jest sumą, ale wynikiem podzielenia pewnej ilości informacji (komunikatu informacyjnego) przez stałą, a raczej pozostałości z dzielenia wiadomości przez stałą. Jednak CRC jest również historycznie określana jako „suma kontrolna”. Każdy bit wiadomości ma wpływ na wartość CRC. Oznacza to, że jeśli co najmniej jeden bit oryginalnej wiadomości zmieni się podczas transmisji, suma kontrolna również się zmieni, i to znacząco. To duży plus takiego sprawdzenia, ponieważ pozwala jednoznacznie określić, czy oryginalna wiadomość została zniekształcona podczas transmisji, czy nie.
Krok 2
Zanim zaczniemy obliczać CRC, potrzebna jest trochę więcej teorii.
Jakie jest oryginalne przesłanie powinno być jasne. Jest to ciągła sekwencja bitów o dowolnej długości.
Jaka jest stała, według której powinniśmy podzielić oryginalną wiadomość? Ta liczba również ma dowolną długość, ale zwykle używa się wielokrotności 1 bajtu - 8, 16 i 32 bitów. Po prostu łatwiej policzyć, ponieważ komputery pracują na bajtach, a nie na bitach.
Stała dzielnika jest zwykle zapisywana jako wielomian (wielomian) w następujący sposób: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Tutaj stopień liczby „x” oznacza pozycję jednego bitu w liczbie, zaczynając od zera, a najbardziej znaczący bit wskazuje stopień wielomianu i jest odrzucany podczas interpretacji liczby. Oznacza to, że poprzednio zapisana liczba to nic więcej niż (1) 00000111 w systemie binarnym lub 7 w systemie dziesiętnym. W nawiasach wskazałem dorozumianą najbardziej znaczącą cyfrę liczby.
Oto kolejny przykład: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 10000000000000101 = 0x8005 = 32773.
Zwykle dla różnych typów CRC używane są niektóre standardowe wielomiany.
Krok 3
Jak więc obliczyć sumę kontrolną? Istnieje podstawowa metoda - dzielenie wiadomości na wielomian "z przodu" - i jej modyfikacje w celu zmniejszenia liczby obliczeń i odpowiednio przyspieszenia obliczeń CRC. Przyjrzymy się podstawowej metodzie.
Ogólnie dzielenie liczby przez wielomian odbywa się według następującego algorytmu:
1) tworzona jest tablica (rejestr) wypełniona zerami o długości równej długości wielomianu;
2) oryginalny komunikat jest uzupełniony zerami w najmniej znaczących bitach, w ilości równej liczbie bitów wielomianu;
3) jeden najbardziej znaczący bit komunikatu zostaje wpisany do najmniej znaczącego bitu rejestru, a jeden bit jest przesunięty z najbardziej znaczącego bitu rejestru;
4) jeśli rozszerzony bit jest równy „1”, to bity są odwracane (operacja XOR, wyłączne OR) w tych bitach rejestru, które odpowiadają bitom wielomianu;
5) jeśli w wiadomości nadal są bity, przejdź do kroku 3);
6) gdy wszystkie bity komunikatu weszły do rejestru i zostały przetworzone przez ten algorytm, w rejestrze pozostaje pozostała część dzielenia, czyli suma kontrolna CRC.
Rysunek przedstawia podział oryginalnego ciągu bitów przez liczbę (1) 00000111 lub wielomian x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Krok 4
Pozostało jeszcze kilka dodatkowych akcentów. Jak zapewne zauważyłeś, wiadomość można podzielić dowolną liczbą. Jak to wybrać? Istnieje wiele standardowych wielomianów używanych do obliczania CRC. Na przykład dla CRC32 może to być 0x04C11DB7, a dla CRC16 może to być 0x8005.
Ponadto w rejestrze na początku obliczeń możesz wpisać nie zera, ale inną liczbę.
Również podczas obliczeń, bezpośrednio przed wydaniem końcowej sumy kontrolnej CRC, można je podzielić przez inną liczbę.
I ostatnia rzecz. Bajty wiadomości podczas zapisu do rejestru mogą być umieszczane jako najbardziej znaczący bit „do przodu” i odwrotnie, jako najmniej znaczący.
Krok 5
W oparciu o powyższe, napiszmy funkcję Basic. NET, która oblicza sumę kontrolną CRC, biorąc liczbę parametrów, które opisałem powyżej i zwracając wartość CRC jako 32-bitową liczbę bez znaku.
Publiczna funkcja współdzielona GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Opcjonalna ByVal width As Integer = 32, Opcjonalna ByVal initReg As UInteger = & HFFFFFFFFUI, Opcjonalna ByVal finalXor As UInteger = & HFFFFFFFFUI, Opcjonalna ByVal reverseBytes, Opcjonalna Boolean reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = szerokość / 8
'Uzupełnij szerokość wiadomości zerami (obliczanie w bajtach):
ReDim Zachowaj bajty (bytes. Length - 1 + widthInBytes)
'Utwórz kolejkę bitową z wiadomości:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Dla każdego b jako bajt w bajtach
Dim ba As New BitArray ({b})
Jeśli reverseBytes Wtedy
Dla i jako liczba całkowita = 0 do 7
msgFifo. Kolejka (ba (i))
Następny
W przeciwnym razie
Dla i As Integer = 7 do 0 Krok -1
msgFifo. Kolejka (ba (i))
Następny
Zakończ, jeśli
Następny
'Utwórz kolejkę z początkowych bitów wypełnienia rejestru:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes). Reverse
Dim initFifo As New Queue (Boolean) (szerokość - 1)
Dla każdego b jako bajt w initBytesReversed
Dim ba As New BitArray ({b})
Jeśli nie reverseBytes Wtedy
Dla i jako liczba całkowita = 0 do 7
initFifo. Enqueue (ba (i))
Następny
W przeciwnym razie
Dla i As Integer = 7 do 0 Krok -1
initFifo. Enqueue (ba (i))
Następny
Zakończ, jeśli
Następny
'Shift i XOR:
Rejestr Dim As UInteger = 0 'wypełnij rejestr szerokości bitów zerami.
Dopóki msgFifo. Count> 0
Dim poppedBit As Integer = CInt (rejestr >> (szerokość - 1)) I 1 'zdefiniuj przed rejestrem przesuwnym.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Jeśli initFifo. Count> 0 Wtedy
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
bit przesunięty = bit przesunięty Xor b
Zakończ, jeśli
rejestr = rejestr << 1
rejestr = rejestr lub przesunięty bit
Jeśli poppedBit = 1 Wtedy
rejestr = rejestr Xor poli
Zakończ, jeśli
Pętla
'Ostateczne konwersje:
Dim crc As UInteger = register 'Rejestr zawiera resztę z dzielenia == suma kontrolna.
Jeśli reverseCrc Wtedy
crc = odzwierciedlać (crc, szerokość)
Zakończ, jeśli
crc = crc Xlub końcowyXor
crc = crc I (& HFFFFFFFFUI >> (32 - szerokość)) 'maskuje najmniej znaczące bity.
Zwróć crc
Koniec funkcji
