Może po prostu tego nie widzę, ale CRC32 wydaje się albo niepotrzebnie skomplikowane, albo niewystarczająco wyjaśnione nigdzie, co mogłem znaleźć w sieci.
Rozumiem, że jest to reszta z arytmetycznego podziału wartości wiadomości nie opartego na przenoszeniu, podzielonej przez wielomian (generujący), ale faktyczna jego implementacja mi umyka.
Przeczytałem Bezbolesny przewodnik po algorytmach wykrywania błędów CRC i muszę powiedzieć, że nie był bezbolesny. Całkiem dobrze omawia teorię, ale autor nigdy nie przechodzi do prostego „to jest to”. Mówi, jakie są parametry dla standardowego algorytmu CRC32, ale zaniedbuje jasno określić, jak do tego dojdziesz.
Część, która mnie dopada, to kiedy mówi „to jest to”, a potem dodaje: „a tak przy okazji, można to odwrócić lub rozpocząć z innymi warunkami początkowymi” i nie daje jasnej odpowiedzi, jaki jest ostateczny sposób obliczenia sumy kontrolnej CRC32 przy uwzględnieniu wszystkich zmian, które właśnie dodał.
- Czy istnieje prostsze wyjaśnienie sposobu obliczania CRC32?
Próbowałem zakodować w C sposób tworzenia tabeli:
for (i = 0; i < 256; i++)
{
temp = i;
for (j = 0; j < 8; j++)
{
if (temp & 1)
{
temp >>= 1;
temp ^= 0xEDB88320;
}
else {temp >>= 1;}
}
testcrc[i] = temp;
}
ale wydaje się, że generuje to wartości niezgodne z wartościami, które znalazłem w innych miejscach w Internecie. I mógłby użyć wartości mogę znaleźć w internecie, ale chcę, aby zrozumieć, w jaki sposób zostały one utworzone.
Każda pomoc w wyjaśnieniu tych niesamowicie zagmatwanych liczb byłaby bardzo mile widziana.
0xEDB88320
można również zapisać msbit-first ( normalny ) jako0x04C11DB7
. Czy wartości tabeli, które znalazłeś w innym miejscu, zostały wygenerowane przy użyciu tego samego wielomianu CRC?Odpowiedzi:
Wielomian dla CRC32 to:
Lub szesnastkowo i binarnie:
Najwyższy wyraz (x 32 ) zwykle nie jest jawnie zapisywany, więc zamiast tego można go przedstawić w postaci szesnastkowej, tak jak
Możesz policzyć jedynki i zera, ale przekonasz się, że pasują do wielomianu, gdzie
1
jest bitem 0 (lub pierwszym bitem) ix
bitem 1 (lub drugim bitem).Dlaczego ten wielomian? Ponieważ musi istnieć standard, podany wielomian, a standard został określony przez IEEE 802.3. Niezwykle trudno jest również znaleźć wielomian, który skutecznie wykrywa różne błędy bitowe.
Możesz myśleć o CRC-32 jako o serii „arytmetyki binarnej bez przenoszenia” lub w zasadzie „operacje XOR i przesunięcia”. Technicznie nazywa się to arytmetyką wielomianową.
Aby lepiej to zrozumieć, pomyśl o tym mnożeniu:
Jeśli przyjmiemy, że x jest podstawą 2, otrzymamy:
Czemu? Ponieważ 3x ^ 3 to 11x ^ 11 (ale potrzebujemy tylko 1 lub 0 przed cyfrą), więc przenosimy:
Ale matematycy zmienili reguły, tak że jest to mod 2. Więc w zasadzie każdy binarny wielomian mod 2 jest po prostu dodawaniem bez przeniesienia lub XOR. Więc nasze oryginalne równanie wygląda następująco:
Wiem, że to skok wiary, ale to przekracza moje możliwości jako programisty liniowego. Jeśli jesteś zagorzałym studentem CS lub inżynierem, wzywam to do rozbicia. Wszyscy skorzystają na tej analizie.
Aby więc opracować pełny przykład:
Teraz dzielimy powiększoną wiadomość przez Poly, używając arytmetyki CRC. To taki sam podział jak poprzednio:
Dzielenie daje iloraz, który odrzucamy, i resztę, czyli obliczoną sumę kontrolną. To kończy obliczenia. Zwykle suma kontrolna jest następnie dołączana do wiadomości, a wynik jest przesyłany. W tym przypadku transmisja wyglądałaby następująco: 11010110111110.
Jako dzielnika używaj tylko liczby 32-bitowej i jako dywidendy używaj całego strumienia. Wyrzuć iloraz i zachowaj resztę. Dodaj resztę na końcu wiadomości i masz CRC32.
Średnia recenzja faceta:
(Należy pamiętać, że strumień musi być podzielny przez 32 bity lub powinien być wypełniony. Na przykład 8-bitowy strumień ANSI musiałby być wypełniony. Również na końcu strumienia podział jest zatrzymywany).
źródło
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 ... If we assume x is base 2 then we get: x^7 + x^3 + x^2 + x^1 + x^0
. Nie tak działa matematyka. Współczynniki wielomianu to mod (2) lub GF (2), x są pozostawione same, co daje x ^ 6 + x ^ 5 + x ^ 4 + x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0 (od 3 mod (2) = 1).Tack the remainder on the end of your message
- technicznie reszta jest odejmowana od 0 bitów, które zostały dołączone do wiadomości, ale ponieważ jest to matematyka mod (2), zarówno dodawanie, jak i odejmowanie są takie same jak XOR, a zerowe bity XOR z resztą są takie same jako reszta.Why did you append four 0s though?
- algorytmy oprogramowania do obliczania CRC skutecznie dodają 0, mimo że nie jest to widoczne. Jeśli pokazujesz obliczenie CRC za pomocą dzielenia z długiej ręki, to należy dodać 0, aby przykład dzielenia był wyświetlany poprawnie.W przypadku IEEE802.3, CRC-32. Pomyśl o całej wiadomości jako o szeregowym strumieniu bitów, dodaj 32 zera na końcu wiadomości. Następnie MUSISZ odwrócić bity KAŻDEGO bajtu wiadomości i uzupełnić jedynkami pierwsze 32 bity. Teraz podziel przez wielomian CRC-32, 0x104C11DB7. Na koniec musisz uzupełnić 1 do 32-bitowej pozostałej części tego podziału, odwrócić bitowo każdy z 4 bajtów pozostałej części. To staje się 32-bitowym CRC, które jest dołączane na końcu wiadomości.
Przyczyną tej dziwnej procedury jest to, że pierwsze implementacje Ethernetu serializowały wiadomość po jednym bajcie i przesyłały najpierw najmniej znaczący bit z każdego bajtu. Szeregowy strumień bitów przeszedł następnie przez szeregowe obliczenia rejestru przesuwnego CRC-32, które zostały po prostu uzupełnione i wysłane przewodem po zakończeniu wiadomości. Powodem uzupełnienia pierwszych 32 bitów wiadomości jest to, że nie otrzymasz zerowego CRC, nawet jeśli wiadomość zawierała same zera.
źródło
CRC jest całkiem proste; bierzesz wielomian reprezentowany jako bity i dane i dzielisz go na dane (lub reprezentujesz dane jako wielomian i robisz to samo). Reszta, która mieści się między 0 a wielomianem, to CRC. Twój kod jest trochę trudny do zrozumienia, częściowo dlatego, że jest niekompletny: temp i testcrc nie są zadeklarowane, więc nie jest jasne, co jest indeksowane i ile danych przechodzi przez algorytm.
Sposobem na zrozumienie CRC jest próba obliczenia kilku przy użyciu krótkiego fragmentu danych (około 16 bitów) z krótkim wielomianem - być może 4-bitowym. Jeśli będziesz ćwiczyć w ten sposób, naprawdę zrozumiesz, jak możesz to zakodować.
Jeśli robisz to często, CRC dość wolno oblicza się w oprogramowaniu. Obliczenia sprzętowe są znacznie wydajniejsze i wymagają tylko kilku bramek.
źródło
Oprócz artykułów z Wikipedii Cyclic redundancy check and Computation of CRC , dobrym źródłem jest artykuł zatytułowany Reversing CRC - Theory and Practice * .
Istnieją zasadniczo trzy podejścia do obliczania CRC: podejście algebraiczne, podejście zorientowane na bit i podejście oparte na tabelach. W Reversing CRC - Theory and Practice * , każdemu z tych trzech algorytmów / podejść wyjaśniono w teorii, któremu towarzyszy implementacja CRC32 w języku programowania C.
* PDF Link
Reversing CRC - Teoria i praktyka.
Raport publiczny HU Berlin
SAR-PR-2006-05
maja 2006
Autorzy:
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich
źródło
Spędziłem chwilę, próbując znaleźć odpowiedź na to pytanie, iw końcu opublikowałem dzisiaj tutorial na temat CRC-32: Samouczek skrótu CRC-32 - Społeczność AutoHotkey
W tym przykładzie pokazuję, jak obliczyć skrót CRC-32 dla ciągu ASCII „abc”:
źródło
^
? stackoverflow.com/questions/62168128/…Następnie zawsze jest kod Rosetta, który pokazuje kod crc32 zaimplementowany w dziesiątkach języków komputerowych. https://rosettacode.org/wiki/CRC-32 i zawiera linki do wielu wyjaśnień i implementacji.
źródło
Aby zredukować crc32 do przyjmowania przypomnienia, musisz:
W kodzie to jest:
gdzie reminderIEEE jest czystym przypomnieniem na GF (2) [x]
źródło