Jak obliczana jest suma kontrolna CRC32?

103

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.

aquanar
źródło
9
Wygląda na to, że Twój kod do generowania tabeli CRC32 jest poprawny. Twój lsbit-first ( odwrócony ) wielomian CRC32 0xEDB88320można również zapisać msbit-first ( normalny ) jako 0x04C11DB7. Czy wartości tabeli, które znalazłeś w innym miejscu, zostały wygenerowane przy użyciu tego samego wielomianu CRC?
jschmier
1
@jschmier cześć, czuję, że jestem o krok za tym facetem zadającym pytania? stackoverflow.com/questions/62168128/…
bluejayke
Jeśli ktoś jest zaciekawiony, aby przeczytać „Bezbolesny przewodnik po algorytmach wykrywania błędów CRC”, do którego link znajduje się powyżej, ten oryginalny adres URL jest wężowany, ale Google z łatwością znalazł kilka kopii, w tym tę: zlib.net/crc_v3.txt
Stéphane,

Odpowiedzi:

118

Wielomian dla CRC32 to:

x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1

Lub szesnastkowo i binarnie:

0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111

Najwyższy wyraz (x 32 ) zwykle nie jest jawnie zapisywany, więc zamiast tego można go przedstawić w postaci szesnastkowej, tak jak

0x 04 C1 1D B7

Możesz policzyć jedynki i zera, ale przekonasz się, że pasują do wielomianu, gdzie 1jest bitem 0 (lub pierwszym bitem) i xbitem 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:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Jeśli przyjmiemy, że x jest podstawą 2, otrzymamy:

x^7 + x^3 + x^2 + x^1 + x^0

Czemu? Ponieważ 3x ^ 3 to 11x ^ 11 (ale potrzebujemy tylko 1 lub 0 przed cyfrą), więc przenosimy:

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

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:

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

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:

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

Teraz dzielimy powiększoną wiadomość przez Poly, używając arytmetyki CRC. To taki sam podział jak poprzednio:

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

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:

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER
  1. Weź pierwsze 32 bity.
  2. Przesuwaj bity
  3. Jeśli 32 bity są mniejsze niż DIVISOR, przejdź do kroku 2.
  4. XOR 32 bity firmy DIVISOR. Przejdź do kroku 2.

(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).

ilkkachu
źródło
13
+1 dla „Średniej recenzji faceta” na końcu - może rozważ przeniesienie tego w prawo na górę - coś w rodzaju TL; DR: P
aaronsnoswell
4
@abstractnature Pamiętaj, że dzielimy wielomiany, a nie tylko liczby binarne. Nie możemy zrobić "normalnego" odejmowania, ponieważ nie możemy "pożyczyć" $ x ^ n $ od $ x ^ {n + 1} $; są to różne rzeczy. Ponadto, skoro bity mają tylko 0 lub 1, czym w ogóle byłoby -1? Naprawdę pracujemy w pierścieniu wielomianów ze współczynnikami w polu $ Z / 2Z $, które ma tylko dwa elementy, 0 i 1, i gdzie $ 1 + 1 = 0 $. Umieszczając współczynniki w polu, wówczas wielomiany tworzą tak zwaną domenę euklidesową, co w zasadzie pozwala na dokładne zdefiniowanie tego, co próbujemy zrobić.
calavicci
6
Wystarczy wyjaśnić, że rzeczywisty wielomian to 100000100110000010001110110110111 = 0x104C11DB7. MSB jest niejawna, ale nadal powinna być brana pod uwagę w implementacji. Ponieważ będzie on zawsze ustawiony, ponieważ wielomian musi mieć 33 bity (więc reszta może mieć 32 bity), niektórzy ludzie pomijają MSB.
Felipe T.
2
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.
rcgldr
2
@MarcusJ - 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.
rcgldr
11

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.

Pavlo Bobrek
źródło
2
Jak dotąd jest to najlepsza odpowiedź, chociaż zamieniłbym 'odwrócenie bitów każdego z 4 bajtów' na 'odwrócenie bitów 4 bajtów, traktując je jako jedną jednostkę' np. 'Abcdefgh ijklmnop qrstuvwx yzABCDEF' na 'FEDCBAzy xwvutsrq ponmlkji hgfedcba ”. Zobacz też: Samouczek skrótu CRC-32 - Społeczność AutoHotkey .
vafylec
1
cześć, jaka dokładnie ta „wiadomość”? stackoverflow.com/questions/62168128/…
bluejayke
10

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.

Trąba powietrzna
źródło
1
Dla CRC32 lub CRC32b, czy otrzymujemy znaczenie kolizji hash dla dwóch różnych ciągów, czy otrzymujemy ten sam CRC
indianwebdevil
1
cześć, jestem trochę zdezorientowany, co masz na myśli mówiąc „podziel wielomiany na dane”? stackoverflow.com/questions/62168128/… czym jest X w wielomianu reprezentowanym przez? Czy używam pozostałych bajtów z fragmentu?
bluejayke
7

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

jschmier
źródło
cześć, możesz trochę rozwinąć?
bluejayke
7

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”:

calculate the CRC-32 hash for the ASCII string 'abc':

inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7

011000010110001001100011
reverse bits in each byte:
100001100100011011000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR the first 4 bytes with 0xFFFFFFFF:
01111001101110010011100111111111000000000000000000000000

'CRC division':
01111001101110010011100111111111000000000000000000000000
 100000100110000010001110110110111
 ---------------------------------
  111000100010010111111010010010110
  100000100110000010001110110110111
  ---------------------------------
   110000001000101011101001001000010
   100000100110000010001110110110111
   ---------------------------------
    100001011101010011001111111101010
    100000100110000010001110110110111
    ---------------------------------
         111101101000100000100101110100000
         100000100110000010001110110110111
         ---------------------------------
          111010011101000101010110000101110
          100000100110000010001110110110111
          ---------------------------------
           110101110110001110110001100110010
           100000100110000010001110110110111
           ---------------------------------
            101010100000011001111110100001010
            100000100110000010001110110110111
            ---------------------------------
              101000011001101111000001011110100
              100000100110000010001110110110111
              ---------------------------------
                100011111110110100111110100001100
                100000100110000010001110110110111
                ---------------------------------
                    110110001101101100000101110110000
                    100000100110000010001110110110111
                    ---------------------------------
                     101101010111011100010110000001110
                     100000100110000010001110110110111
                     ---------------------------------
                       110111000101111001100011011100100
                       100000100110000010001110110110111
                       ---------------------------------
                        10111100011111011101101101010011

remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53
XOR the remainder with 0xFFFFFFFF:
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
0b00110101001001000100000111000010 = 0x352441C2

thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2
vafylec
źródło
1
Jeśli chcesz uzyskać większą prędkość, niektórzy inżynierowie w firmie Intel opracowali około 2006 r. Metodę wykorzystującą zwykle 4 lub 8 bajtów magistrali danych maszyny jednocześnie. Artykuł naukowy: static.aminer.org/pdf/PDF/000/432/446/ ... Projekt na Sourceforge: sourceforge.net/projects/slicing-by-8 Ogólna strona crc: create.stephan-brumme.com/crc32
Alan Corey
1
Cześć, dzięki, wygląda świetnie, ale jak dokładnie otrzymujesz wartość wielomianu? co dokładnie reprezentuje X? A kiedy mówi x ^ 32, czy to x do potęgi 32, czy operator bitowy ^? stackoverflow.com/questions/62168128/…
bluejayke
1

Aby zredukować crc32 do przyjmowania przypomnienia, musisz:

  1. Odwróć bity w każdym bajcie
  2. xor pierwsze cztery bajty z 0xFF (ma to na celu uniknięcie błędów w początkowych zerach)
  3. Dodaj dopełnienie na końcu (ma to na celu uwzględnienie ostatnich 4 bajtów w hashu)
  4. Oblicz przypomnienie
  5. Ponownie odwróć bity
  6. xor ponownie wynik.

W kodzie to jest:


func CRC32 (file []byte) uint32 {
    for i , v := range(file) {
        file[i] = bits.Reverse8(v)
    }
    for i := 0; i < 4; i++ {
        file[i] ^= 0xFF
    }

    // Add padding
    file = append(file, []byte{0, 0, 0, 0}...)
    newReminder := bits.Reverse32(reminderIEEE(file))

    return newReminder ^ 0xFFFFFFFF
}

gdzie reminderIEEE jest czystym przypomnieniem na GF (2) [x]

Gabriel Furstenheim
źródło
1
mam trochę (zamierzona gra słów) kłopotów ze zrozumieniem tego? stackoverflow.com/questions/62168128/…
bluejayke
1
hej @bluejayke, sprawdź tę bibliotekę github.com/furstenheim/sparse_crc32/blob/master/main.go implementuje crc32 dla rzadkich plików, możesz tam zobaczyć szczegółowe szczegóły obliczeń. Nie jest zoptymalizowany, więc jest łatwiejszy do śledzenia niż normalne implementacje. Możliwe, że nie rozumiesz części GF (2) [x]. Zasadniczo x ^ 3 + x oznacza 1010, x ^ 4 + x + 1 oznacza 10011. Następnie musisz wykonać dzielenie, na przykład x ^ 3 + x to x * (x ^ 2 + 1). więc przypomnienie o x ^ 3 + x po x wynosi 0, ale po x ^ 2 byłoby x ^ 2 * x + x, to znaczy przypomnieniem byłoby x.
Gabriel Furstenheim
1
@bluejayke i reminderIEEE oznacza przypomnienie przeciwko dobrze znanemu wielomianowi, wielomianowi IEEE
Gabriel Furstenheim
witam ponownie, dziękuję za odpowiedź. Po prostu próbuję zrozumieć (dla celów javascript), co oznacza "x" w wielomianu. Czy „x” jest jakimś hasłem oznaczającym coś, czego tu brakuje? Jest mnóstwo terminów, które mnie wprawiają w zakłopotanie, nigdy wcześniej nie słyszałem o CRC32, a nawet po przeszukaniu nie mogłem znaleźć tego właściwie wyjaśnionego. Na przykład w przypadku pliku PNG mówi, że muszę wziąć „CRC dla każdego fragmentu”, czy to oznacza „dla wszystkich danych w porcji”? Ale jak mam go „podłączyć” do wielomianu? Co oznacza „x”? Również kiedy mówi x ^ 32, jest to jak Math.pow (x, 32) lub bitowe ^
bluejayke
1
Cześć @bluejayke, x to abstrakcja ułatwiająca obliczenia. Nie oczekuje się, że zostanie on niczym zastąpiony. x ^ 2 Mam na myśli x * x, jako formalne mnożenie. Tutaj chrisballance.com/wp-content/uploads/2015/10/CRC-Primer.html można znaleźć ładne wyjaśnienie tego podziału. Próbowałem z moją odpowiedzią wypełnić lukę między podziałem (w tym linku) a rzeczywistymi obliczeniami
Gabriel Furstenheim