Adler-32

Z Wikipedii

Skocz do: nawigacji, szukaj
 Niektóre informacje zawarte w artykule wymagają weryfikacji.
Do weryfikacji: patrz dyskusja

Adler-32 - suma kontrolna opracowana przez Marka Adlera w oparciu o sumę kontrolną Faltchera. Jest trochę mniej efektywna przy wykrywaniu przypadkowych przekłamań danych w porównaniu do 32 bitowego CRC, ale za to znacznie szybciej obliczana przez oprogramowanie.

Spis treści

[edytuj] Algorytm

Sumę kontrolną Adler-32 uzyskuje się poprzez obliczenie dwóch 16 bitowych sum kontrolnych A i B oraz poprzez powiązanie ich bitów w 32 bitową liczbę całkowitą. A jest sumą wszystkich bajtów w danym ciągu danych, a B jest sumą indywidualnych wartości zmiennej A z każdego kroku obliczenia.

Na samym początku A jest inicjalizowane jako 1, a B jako 0. Obydwie zmienne sumowane modulo 65521 (największa liczba pierwsza mniejsza od 216). Bajty są w kolejności Big Endian.

Funkcja może być zdefiniowana jako:

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

gdzie D to ciąg bajtów, dla których jest obliczana suma kontrolna, a n jest długością D.

[edytuj] Przykładowe obliczenie

Suma Alder-32 dla ciągu znaków "Wikipedia" w formacie ASCII jest obliczana następująco:

   Kod ASCII             A                   B

   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
   e: 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  =  398 hex
   B = 4582 = 11E6 hex

   Suma = 11E60398 hex

W tym przykładzie pominięto operację sumy modula, ponieważ wartość żadnej ze zmiennych nie mogła przekroczyć 65521.

[edytuj] Przykładowa implementacja

Zoptymalizowana implementacja w języku C wygląda następująco:

#define MOD_ADLER 65521
       uint8_t *data;   /* Pointer to the data to be summed */
       size_t len;      /* Length in bytes */
       uint32_t a = 1, b = 0;

       while (len) {
               unsigned tlen = len > 5550 ? 5550 : len;
               len -= tlen;
               do {
                       a += *data++;
                       b += a;
               } while (--tlen);
               a = (a & 0xffff) + (a >> 16) * (65536-MOD_ADLER);
               b = (b & 0xffff) + (b >> 16) * (65536-MOD_ADLER);
       }
       /* It can be shown that a <= 0x1013a here, so a single subtract will do. */
       if (a >= MOD_ADLER)
               a -= MOD_ADLER;
       /* It can be shown that b can reach 0xffef1 here. */
       b = (b & 0xffff) + (b >> 16) * (65536-MOD_ADLER);
       if (b >= MOD_ADLER)
               b -= MOD_ADLER;
       return (b << 16) | a;

Sztuczki wykorzystane dla zwiększenia wydajności:

  • Dzięki wykorzystaniu większych (32 bitowych) tymczasowych sum można sumować większe ilości danych, zanim zajdzie konieczność wykonania sumy modulo 65521. Jest wymagane, aby została wykonana suma modulo 65521, zanim suma ulegnie przepełnieniu, co spowodowałoby wykonanie nieprawidłowej sumy modulo 232 = 4294967296.
  • 65536 ≡ 15 mod 65521, więc 65536x ≡ 15x (mod 65521) oraz wyrażenie (x & 0xffff) + (x >> 16)*15 sprowadza się do x modulo 65521. Wykonanie tego tylko raz nie gwarantuje poprawnego wyniku, ale wiadomo, że będzie on zawsze mniejszy niż 0xffff0. Drugie powtórzenie gwarantuje wynik mniejszy niż 65745, po czym pojedyncze odejmowanie warunkowe redukuje sumę do przedziału 0..65520.
  • Liczba 5550 jest największą liczbą sum, które mogą zostać wykonane bez przepełniania b. Każda mniejsza wartość jest także możliwa.

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

Źródło: "http://pl.wikipedia.org/wiki/Adler-32"