Adler-32

Adler-32 to algorytm sumy kontrolnej napisany przez Marka Adlera w 1995 roku, modyfikujący sumę kontrolną Fletchera . W porównaniu z cykliczną kontrolą redundancji o tej samej długości, zamienia niezawodność na szybkość (preferując tę ​​drugą). Adler-32 jest bardziej niezawodny niż Fletcher-16 i nieco mniej niezawodny niż Fletcher-32 .

Historia

Suma kontrolna Adler-32 jest częścią szeroko stosowanej biblioteki kompresji zlib , ponieważ obie zostały opracowane przez Marka Adlera . W narzędziu rsync używana jest wersja Adler-32 z „ kroczącą sumą kontrolną ” .

Obliczenie

Sumę kontrolną Adler-32 uzyskuje się przez obliczenie dwóch 16-bitowych sum kontrolnych A i B i połączenie ich bitów w 32-bitową liczbę całkowitą. A to suma wszystkich bajtów w strumieniu plus jeden, a B to suma poszczególnych wartości A z każdego kroku.

Na początku przebiegu Adler-32, A jest inicjalizowane na 1, B na 0. Sumy są wykonywane modulo 65521 (największa liczba pierwsza mniejsza niż 2 16 ). Bajty są przechowywane w porządku sieciowym ( big endian ), B zajmuje dwa najbardziej znaczące bajty.

Funkcję można wyrazić jako

 ZA  = 1 +  re  1  +  re  2  + ... +  re  n  (mod 65521)  B  = (1 +  re  1  ) + (1 +  re  1  +  re  2  ) + ... + (1 +  re  1  +  re  2  + ... +  re  n  ) (mod 65521) =  n  ×  re  1  + (  n  −1) ×  re  2  + (  n  −2) ×  re  3  + ... +  re  n  +  n  (mod 65521)  Adler -32  (  re  ) =  b  × 65536 +  ZA

gdzie D to ciąg bajtów, dla którego ma zostać obliczona suma kontrolna, a n to długość D .

Przykład

Suma Adler-32 łańcucha ASCII „ Wikipedia ” zostanie obliczona w następujący sposób:

Postać kod ASCII A B
(pokazane jako podstawa 10)
W 87 1 + 87 = 88 0 + 88 = 88
I 105 88 + 105 = 193 88 + 193 = 281
k 107 193 + 107 = 300 281 + 300 = 581
I 105 300 + 105 = 405 581 + 405 = 986
P 112 405 + 112 = 517 986 + 517 = 1503
mi 101 517 + 101 = 618 1503 + 618 = 2121
D 100 618 + 100 = 718 2121 + 718 = 2839
I 105 718 + 105 = 823 2839 + 823 = 3662
A 97 823 + 97 = 920 3662 + 920 = 4582 
A = 920 = 0x398 (podstawa 16) B = 4582 = 0x11E6 Wyjście = 0x11E6 << 16 + 0x398 = 0x11E60398 = 300286872

Operacja modulo nie dała żadnego efektu w tym przykładzie, ponieważ żadna z wartości nie osiągnęła 65521.

Porównanie z sumą kontrolną Fletchera

Pierwsza różnica między tymi dwoma algorytmami polega na tym, że sumy Adlera-32 są obliczane modulo liczby pierwszej, podczas gdy sumy Fletchera są obliczane modulo 2 4 −1, 2 8 −1 lub 2 16 −1 (w zależności od liczby użytych bitów) , które są liczbami złożonymi . Użycie liczby pierwszej umożliwia Adler-32 wyłapanie różnic w pewnych kombinacjach bajtów, których Fletcher nie jest w stanie wykryć.

Druga różnica, która ma największy wpływ na szybkość algorytmu, polega na tym, że sumy Adlera są obliczane na podstawie 8-bitowych bajtów , a nie 16-bitowych słów , co skutkuje dwukrotnie większą liczbą iteracji pętli. Powoduje to, że suma kontrolna Adler-32 zajmuje od półtora do dwóch razy więcej niż suma kontrolna Fletchera dla 16-bitowych danych wyrównanych do słów. Dla danych wyrównanych bajtowo, Adler-32 jest szybszy niż poprawnie zaimplementowana suma kontrolna Fletchera (np. ta znaleziona w Hierarchical Data Format ).

Przykładowa realizacja

W C nieefektywna, ale prosta implementacja to: 

    

      





          0
     
    
    
       0    
    
              
              
    
    
         
 const  uint32_t  MOD_ADLER  =  65521  ;  uint32_t  adler32  (  unsigned  char  *  data  ,  size_t  len  )  /*  gdzie dane to lokalizacja danych w pamięci fizycznej, a  len to długość danych w bajtach  */  {  uint32_t  a  =  1  ,  b  =  ;  rozmiar_t  indeks  ;  // Przetwórz każdy bajt danych w kolejności  dla  (  index  =  ;  index  <  len  ;  ++  index  )  {  a  =  (  a  +  data  [  index  ])  %  MOD_ADLER  ;  b  =  (  b  +  a  )  %  MOD_ADLER  ;  }  powrót  (  b  <<  16  )  |  za  ;  }

Zobacz kod źródłowy zlib , aby zobaczyć bardziej wydajną implementację, która wymaga pobrania i dwóch dodań na bajt, z operacjami modulo odroczonymi z dwiema resztami obliczanymi co kilka tysięcy bajtów, techniką odkrytą po raz pierwszy dla sum kontrolnych Fletchera w 1988 roku . optymalizacja, z dodatkiem sztuczki, która opóźnia obliczenie „15” w 65536 - 65521, aby modulo stało się szybsze: można wykazać, że ( (a >> 16) * 15 + (a & 65535)) % 65521 jest równoważne do naiwnej akumulacji.

Zalety i wady

  • Podobnie jak standardowy CRC-32 , suma kontrolna Adler-32 może być łatwo sfałszowana i dlatego nie jest bezpieczna dla ochrony przed celową modyfikacją.
  • Jest szybszy niż CRC-32 na wielu platformach.
  • Adler-32 ma słabość do krótkich wiadomości o długości kilkuset bajtów, ponieważ sumy kontrolne tych wiadomości mają słabe pokrycie 32 dostępnych bitów.

Słabość

  Adler-32 jest słaby dla krótkich wiadomości, ponieważ suma A nie zawija się. Maksymalna suma 128-bajtowego komunikatu wynosi 32640, czyli mniej niż wartość 65521 używana przez operację modulo, co oznacza, że ​​mniej więcej połowa przestrzeni wyjściowej jest niewykorzystana, a rozkład w używanej części jest nierównomierny. Rozszerzone wyjaśnienie można znaleźć w RFC 3309 , który nakazuje użycie CRC32C zamiast Adler-32 dla SCTP , Stream Control Transmission Protocol. Wykazano również, że Adler-32 jest słaby w przypadku małych zmian przyrostowych, a także słaby w przypadku ciągów generowanych ze wspólnego przedrostka i kolejnych liczb (jak automatycznie generowane nazwy etykiet przez typowe generatory kodu).

Zobacz też

Notatki

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Adler-32&oldid=1112992237 ”