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

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

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

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

  • 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

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ż

Linki zewnętrzne