Adler-32
Adler-32 – suma kontrolna opracowana przez Marka Adlera w oparciu o sumę kontrolną Fletchera. Jest trochę mniej efektywna przy wykrywaniu przypadkowych przekłamań danych w porównaniu do CRC-32, ale za to znacznie szybciej obliczana przez oprogramowanie.
Algorytm
[edytuj | edytuj kod]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.
Przykładowe obliczenie
[edytuj | edytuj kod]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 modulo, ponieważ wartość żadnej ze zmiennych nie mogła przekroczyć 65521.
Przykładowa implementacja
[edytuj | edytuj kod]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.
Zalety i wady
[edytuj | edytuj kod]- Zarówno w przypadku CRC-32, jak i Adler-32 można z łatwością zmodyfikować dane tak, aby otrzymać taką samą sumę kontrolną jak w przypadku oryginalnych danych w związku z czym algorytmy te nie są dobrym zabezpieczeniem przeciw celowym próbom sfałszowania danych.
- Algorytm Adler-32 można obliczać programowo szybciej niż CRC-32.
- Ze względu na nieoptymalne wykorzystanie dostępnych 32 bitów suma Adler-32 nie jest dobrym rozwiązaniem dla krótkich paczek danych (rzędu kilkuset bajtów).
Krótkie paczki danych
[edytuj | edytuj kod]W przypadku krótkich paczek danych sumy cząstkowe nie osiągają magicznej 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. Słabość tę odkrył w 2001 roku Jonathan Stone i opisał ją: „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. :-)”. Dokładny opis problemu można znaleźć w specyfikacji RFC 3309, która wymaga używania CRC-32 dla SCTP -- Stream Control Transmission Protocol.
Zobacz też
[edytuj | edytuj kod]Linki zewnętrzne
[edytuj | edytuj kod]- P. Deutsch , J-L. Gailly , 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