Adler-32

Z Wikipedii

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

1 Algorytm
2 Przykładowe obliczenie
3 Przykładowa implementacja
4 Zobacz też
5 Linki zewnętrzne

[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 2¹⁶). Bajty są w kolejności Big Endian.

Funkcja może być zdefiniowana jako:

 A = 1 + D₁ + D₂ + ... + D_n (mod 65521)
 B = (1 + D₁) + (1 + D₁ + D₂) + ... + (1 + D₁ + D₂ + ... + D_n) (mod 65521)
   = n×D₁ + (n-1)×D₂ + (n-2)×D₃ + ... + D_n + 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 2³² = 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

RFC 1950 - specyfikacja, zawiera przykładową implementację w języku C
ZLib - zawiera implementację sumy kontrolnej Adler-32
Wylicz sumę kontrolną Adler-32 online

ASTD współorganizatorem Międzynarodowego Kongresu Kadry

W dniach 24-27 listopada odbędzie się Międzynarodowy Kongres Kadry - VIII edycja Kongresu Kadry, po raz pierwszy w wydaniu międzynarodowym.

Obrady WTO na razie bez przełomu

W toczących się od poniedziałku rozmowach w Genewie na temat zniesienia barier w światowym handlu w ramach tzw. rundy z Dauhy do soboty nie udało się wypracować porozumienia.

Absurdalne zapisy blokują unijne dotacje

Bardzo dobry projekt może nie dostać dofinansowania, jeżeli np. przedsiębiorca wypełni wniosek... czarnym długopisem. Takie wątpliwe wymogi wymyślają urzędnicy - czytamy w "Rzeczpospolitej".

KE zamroziła ponad 2 mld euro dla Bułgarii

Komisja Europejska zamroziła znacznie więcej środków dla Bułgarii, niż ogłoszone w środę 825 mln euro z przedakcesjnych funduszy ISPA, PHARE i SAPARD - napisał bułgarski dziennk "Sega".

Betacom: 35 proc. zysku na dywidendę?

Zarząd Betacom zamierza wnioskować do Rady Nadzorczej i WZA o przeznaczenie na wypłatę dywidendy około 35 proc. zysku netto za rok obrotowy 2007/08. W kolejnych latach zarząd planuje rekomendować wypłatę dywidendy na poziomie 25-35 proc. zysku - poinformowała spółka w raporcie rocznym.

Linki: Strona g��wna

Encyklopedia