Jak działa CRC (Cyclic Redundancy Check)

Jakiś czas temu w pracy dostałem zadanie uruchomienia modułu sprzętowego CRC na procesorze PIC32. W trakcie pracy wyszły pewne problemy, do rozwiązania których niezbędne było opanowanie teorii związanej z obliczaniem sum kontrolnych CRC. Zadanie to skłoniło mnie do dokładniejszej analizy problemu i podzielania się rezultatami w tym artykule.

CRC (Cyclic Redundancy Check) to kod o określonej z góry długości wygenerowany z ciągu danych wejściowych dodawany do oryginalnej wiadomości w celu zapewnienia integralności danych. CRC jest wykorzystywane między innymi do wykrywania przekłamań wiadomości przesyłanych przez łącza komunikacyjne, czy do sprawdzania poprawności danych zapisywanych na dysku. Zasada działania jest prosta. Nadawca (lub np. proces zapisujący dane na dysk) oblicza CRC dla wiadomości, którą chce wysłać i dodaje je do wysyłanych danych. Odbiorca (lub np. proces odczytujący dane z dysku) również oblicza sumę kontrolną danych, które otrzymał i porównuje ją z wartością CRC wysłaną przez nadawcę. Jeśli wyniki się różnią, doszło do przekłamania informacji.

Arytmetyka CRC

CRC jest algorytmem opartym na dzieleniu. Jest ono wykonywane za pomocą specjalnej arytmetyki różniącej się nieco od klasycznej. W arytmetyce CRC nie występują przeniesienia. Oznacza to, że dodawanie i odejmowanie są równoważne operacji XOR.

Dodawanie binarne:
1 + 0 = 1
0 + 0 = 0
1 + 1 = 10 -> normalnie najstarszy bajt wyniku przenieśli byśmy do dodawania kolejnego bajtu, ale przy obliczaniu CRC tak nie robimy i zostaje 0.
Odejmowanie binarne:
1 – 1 = 0
1 – 0 = 1
0 – 1 = -1 -> normalnie byśmy przenieśli 1 ze starszego bajtu i dostali 10 – 1 = 1, i starszy bajt zmniejszony o 1, przy obliczaniu CRC nie zmniejszamy starszego bitu i zostaje 1.

Wielomiany CRC

Dzielenie CRC jest zbliżone do dzielenia wielomianów, gdzie zależność między kolejnymi potęgami nie jest znana, dlatego nie można stosować przeniesień. Wielomian jest zapisywany jako liczba binarna. Stopień wielomianu odpowiada liczbie bitów, a kolejne bity oznaczają następne potęgi. Jeżeli bit wynosi 1, potęga wchodzi w skład wielomianu, jeśli 0 – nie. Najwyższy bit zawsze wynosi 1 i jest pomijany w binarnej reprezentacji wielomianu.

Przeanalizujmy to na przykładzie. Mamy liczbę szesnastkową 0xA, w reprezentacji binarnej to 1010. Mamy więc 4 bity, czyli stopień wielomianu to 4. Najwyższa potęga zawsze wynosi 1 i nie jest zapisywana w reprezentacji binarnej. Na początku wielomianu mamy więc x^4. Jedynki występują jeszcze na bitach 3 i 1 licząc najmłodszy bit jako 0. Ostatecznie wielomian o reprezentacji binarnej 1010 ma postać:

1 * x^4 + 1 * x^3 + 0 * x^2 + 1 * x^1 + 0 * x^0

Wielomian CRC (w angielskiej nomenklaturze CRC poly) to wielomian przez który dzielimy dane wejściowe w algorytmie CRC. Dla różnych wielomianów sumy kontrolne dla tych samych danych wejściowych są różne.

Obliczanie CRC

Dzielenie CRC jest dosyć podobne do dzielenia pisemnego. Najłatwiej będzie to przedstawić na przykładzie. Weźmy ciąg danych 0xA53(binarnie 101001010011) i wielomian 0x6(binarnie 0110). Do ciągu danych dopisujemy tyle zer ile bitów jest w naszym wielomianie. Musimy więc dopisać 4 zera otrzymując 1010010100110000. Do wielomianu dodajemy 1 na najstarszym bicie otrzymując 10110. Możemy teraz przystąpić do dzielenia pisemnego. Dzielenie przedstawiłem jako kod źródłowy. Po prawej stronie opis co aktualnie się dzieje. Opis trochę wychodzi poza widoczne okno, dlatego trzeba scrollować na boki. Nie chciałem przenosić opisów do kolejnych linii, żeby dobrze było widać dzielenie. Mam nadzieję, że taka forma przedstawienia treści będzie wystarczająco czytelna.

Przedstawiony algorytm można zaimplementować, ale będzie on bardzo powolny ze względu na operacje na każdym bicie z osobna. W dalszej części artykułu opiszę, jak przyspieszyć obliczenia na procesorze.

Algorytm z użyciem lookup table

Dla każdego bitu dzielnej reszta jest XORowana z wielomianem albo z zerem. Oznacza to, że dla zadanego wielomianu i każdej możliwej kombinacji k pierwszych bitów danej możemy wyznaczyć wartość, jaką należy zXORować z resztą. Wartości te możemy obliczyć wcześniej i umieścić w tablicy (lookup table), żeby algorytm z nich korzystał. Dla stopnia wielomianu n i ilości bitów danej k (w praktyce stosuje się wyłącznie k=8 aby działać na pojedynczych bajtach) pojedyncza iteracja algorytmu  będzie miała postać:

Ten algorytm nosi nazwę Indirect CRC. Taka implementacja ma jednak pewną wadę. Jak pamiętacie z poprzedniego rozdziału, gdzie liczyliśmy CRC pisemnie, do danych trzeba było dodać na końcu zera. Tutaj również należy dodać na końcu zera i wykonać dla nich dodatkowe iteracje, żeby wszystkie bajty danych przeszły całe dzielenie. Okazuje się, że można zmodyfikować algorytm tablicowy tak, żeby nie trzeba było dodawać zer.

Ten algorytm nosi nazwę Direct CRC.

Modyfikacje algorytmu

Algorytm CRC we wszystkich przedstawionych powyżej wariantach nie radzi sobie dobrze z danymi wejściowymi składającymi się z samych zer, albo posiadających zera na początku. W pierwszym przypadku suma kontrolna wyniesie 0. W drugim – taka sama suma zostanie wygenerowana dla tych samych danych wejściowych poprzedzonych różną ilością zer. Czyli na przykład 0x0000AAAABBBBCCCC będzie miało taką samą sumę kontrolną, jak 0xAAAABBBBCCCC. Żeby wyeliminować ten problem, stosuje się seeda, czyli początkowa wartość zmiennej przechowującej resztę z dzielenia jest inicjowana jakąś niezerową wartością.

Aby uzyskać ten sam wynik, należy podać innego seeda do algorytmu Direct, niż do Indirect. Aby seeda Indirect przekonwertować na Direct, należy uruchomić algorytm Indirect na ciągu danych o długości wielomianu składającym się z samych zer i z podanym seedem, który chcemy przekonwertować. Konwersji w drugą stronę można dokonać robiąc bit po bicie operację odwrotną do dzielenia CRC, jak w kodzie poniżej:

Przykłady konwersji seedów między dwoma typami algorytmu można znaleźć w kodzie, który udostępniłem na GitHubie – link w rozdziale Implementacja CRC.

Inną częstą modyfikacją algorytmu jest dodanie operacji XOR na końcowym wyniku z pewną stałą. Czasem również odwracane są bity w kolejnych bajtach danych wejściowych i w zwracanym wyniku.

Wybór wielomianu

Sumy CRC dla różnych ciągów danych powinny przyjmować różne wartości z równo rozłożonym prawdopodobieństwem. Poza tym niewielka zmiana ciągu wejściowego powinna powodować znaczącą zmianę sumy kontrolnej. W ten sposób zapewniamy lepszą ochronę przed kolizją, czyli takim przekłamaniem wartości, które daje tą samą sumę kontrolną. Do tego celu najlepiej używać wielomianów o odpowiednich właściwościach. Najlepiej wybrać jeden z popularnych wielomianów wykorzystywanych w istniejących protokołach takich jak Modbus, czy Ethernet. Na anglojęzycznej Wikipedii można znaleźć listę popularnych wielomianów: https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Standards_and_common_use

Generowanie tablicy lookup

Aby wygenerować samemu tablicę lookup, należy wziąć każdy możliwy ciąg bitów o zadanej długości (np. 8 bitów dla tablicy o 256 elementach), dopełnić go zerami do długości wielomianu i wykonać na otrzymanej liczbie dzielenie CRC. Link do kodu generującego lookup table można znaleźć w rozdziale Implementacja CRC. Jeżeli chcemy skorzystać z gotowej tablicy, w internecie można znaleźć skrypty generujące tablice online.

Implementacja CRC

Aby pokazać działanie przedstawionej tutaj teorii w praktyce, postanowiłem napisać bibliotekę CRC posiadającą następujące funkcje:

  •  Obliczanie Direct i Indirect CRC.
  • Generowanie lookup table.
  • Konwersja seeda z Direct na Indirect.
  • Wybór długości wielomianu – maximum 32.
  • Odwracanie bitów na wejściu.
  • Odwracanie bitów na wyjściu.

W projekcie zawarłem plik main.c prezentujący funkcje biblioteki – generowanie lookup table, obliczanie metodą direct i indirect oraz konwersja seedów pomiędzy obiema metodami. W pliku crc.h znajdują się definy, którymi można zmieniać długość wielomianu oraz obracać bity na wejściu i na wyjściu z funkcji obliczającej CRC. Ewentualne XORowanie wartości końcowej nie jest robione w funkcji bibliotecznej, należy je samemu przeprowadzić na otrzymanym wyniku. Kod źródłowy można znaleźć na GitHubie pod adresem: https://github.com/ucgosupl/crc

Na koniec – wracając do sprzętowego bloku CRC Microchipa. Jest on zaimplementowany na bazie LFSR (Linear Feedback Shift Register) i realizuje Indirect CRC. Oznacza to, że aby uzyskać rezultat zgodny z Direct CRC, należy użyć przekonwertowanego seeda i dodać na końcu wiadomości zera. Oczywiście nie znajdziemy tej informacji w dokumentacji.

2 Comments

  1. bieżemy -> bierzemy

Dodaj komentarz

Your email address will not be published.

*

© 2017 ucgosu.pl

Theme by Anders NorénUp ↑