Adler-32
Adler-32 to suma kontrolna, która została stworzona przez Marka Adlera, opierając się na sumie kontrolnej Fletchera. Chociaż jest nieco mniej skuteczna w wykrywaniu przypadkowych błędów w danych w porównaniu do CRC-32, jej obliczenia są znacznie szybsze.
Algorytm
Suma kontrolna Adler-32 jest uzyskiwana przez obliczenie dwóch 16-bitowych sum kontrolnych: A i B, a następnie połączenie ich w jedną 32-bitową liczbę całkowitą. Zmienna A reprezentuje sumę wszystkich bajtów w danym ciągu danych, natomiast B jest sumą wartości zmiennej A na każdym etapie obliczeń.
Na początku A jest ustawione na 1, a B na 0. Obie zmienne są sumowane z użyciem operacji modulo 65521 (największa liczba pierwsza mniejsza od 2^16). Bajty są interpretowane w kolejności Big Endian.
Funkcja może być zdefiniowana w następujący sposób:
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órego obliczana jest suma kontrolna, a n to długość D.
Przykładowe obliczenie
Suma Adler-32 dla ciągu znaków „Wikipedia” w formacie ASCII obliczana jest w następujący sposób:
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 modulo, ponieważ żadna z wartości zmiennych nie przekroczyła 65521.
Przykładowa implementacja
Przykładowa, zoptymalizowana implementacja w języku C wygląda następująco:
W celu zwiększenia wydajności zastosowano następujące techniki:
Dzięki użyciu większych (32-bitowych) tymczasowych sum można sumować większe ilości danych, zanim zajdzie potrzeba przeprowadzenia operacji modulo 65521. Należy wykonać tę operację przed wystąpieniem przepełnienia, które mogłoby prowadzić do błędnego wyniku przy obliczaniu modulo 2^32 = 4294967296.
65536 ≡ 15 mod 65521, co oznacza, że 65536x ≡ 15x (mod 65521), a wyrażenie (x & 0xffff) + (x >> 16)*15 sprowadza się do x modulo 65521. Wykonanie tej operacji tylko raz nie gwarantuje poprawnego wyniku, ale wiemy, że będzie on zawsze mniejszy niż 0xffff0. Drugie powtórzenie zapewnia wynik mniejszy niż 65745, a pojedyncze odejmowanie warunkowe redukuje sumę do zakresu 0..65520.
Liczba 5550 to maksymalna liczba sum, które mogą zostać obliczone bez ryzyka przepełnienia zmiennej b. Każda mniejsza wartość również jest dopuszczalna.
Zalety i wady
Zarówno CRC-32, jak i Adler-32 są podatne na modyfikacje danych w taki sposób, że uzyskuje się tę samą sumę kontrolną, co oznacza, że algorytmy te nie są skuteczne w obronie przed celowymi próbami sfałszowania danych.
Jednakże obliczenia dla Adler-32 mogą być realizowane programowo szybciej niż dla CRC-32.
Ze względu na nieoptymalne wykorzystanie dostępnych 32 bitów, suma Adler-32 nie jest najlepszym rozwiązaniem dla krótkich paczek danych (rzędu kilkuset bajtów).
Krótkie paczki danych
W przypadku krótkich paczek danych sumy cząstkowe nie osiągają optymalnej wartości 65521. Na przykład dla paczki 128 bajtów maksymalna wartość sumy cząstkowej A wynosi 32640 i nie jest na niej przeprowadzana operacja modulo. Problem ten został zidentyfikowany przez Jonathana Stone’a w 2001 roku, który zauważył: „W skrócie, dla krótkich paczek danych Adler-32 nie gwarantuje optymalnego wykorzystania dostępnych bitów. Nie wierzcie mi na słowo, zapytajcie Marka Adlera. :-)”. Szczegółowy opis problemu można znaleźć w specyfikacji RFC 3309, która zaleca stosowanie CRC-32 dla SCTP — Stream Control Transmission Protocol.
Zobacz też
Linki zewnętrzne
P.P. Deutsch P.P., J-L.J.L. Gailly J-L.J.L., ZLIB Compressed Data Format Specification version 3.3, RFC 1950, IETF, maj 1996, DOI: 10.17487/RFC1950, ISSN 2070-1721, OCLC 943595667 (ang.). – specyfikacja, zawiera przykładową implementację w języku C