Adler-32
Z Wikipedii
 |
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)*15sprowadza 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
