Adler-32

Adler-32 — геш-функція, яку розробив Марк Адлер^[en]. Модифікація контрольної суми Флетчера. Обчислює значення контрольної суми відповідно до RFC 1950 для масиву байтів або його фрагмента. Від CRC32 цей алгоритм розрахунку контрольної суми відрізняється продуктивністю. Використовується в бібліотеці Zlib. Rolling checksum версія функції використовується в утиліті rsync.

Так само, як і у випадку контрольної суми Флетчера, під час розробляння суми Adler стояло завдання отримати контрольну суму з ефективністю виявлення помилок порівнянною з CRC. Хоча показники пошуку помилок контрольних сум Adler і Флетчера практично такі ж, як і у відносно слабких CRC, але в деяких важливих випадках вони поводяться значно гірше, ніж хороші CRC.

Контрольну суму Adler-32 отримують обчисленням двох 16-бітових контрольних сум A і Б та конкатенації їхніх бітів у 32-бітове ціле. А дорівнює сумі всіх байтів у рядку плюс один , а Б — сума всіх окремих значень А на кожному кроці. На початку виконання функції Adler-32 А ініціалізується одиницею, а Б — нулем. Суми беруться за модулем 65521 (найбільше просте число менше від 2¹⁶). Байти записуються в мережевому порядку, Б займає 2 старші байти.

Функцію можна виразити як:

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

де D — рядок байтів, для яких слід обчислити контрольну суму, а n — довжина D.

Значення Adler-32 для ASCII рядка «Wikipedia» обчислюється так:

 Код ASCII AB
 (У десятковому вигляді)
 W: 87 1 + 87 = 88 0 + 88 = 88
 i: 105 88 + 105 = 193 88 + 193 = 281
 k: 107193 + 107 = 300281 + 300 = 581
 i: 105300 + 105 = 405581 + 405 = 986
 p: 112405 + 112 = 517986 + 517 = 1503
 e: 101517 + 101 = 618 1503 + 618 = 2121
 d: 100618 + 100 = 718 2121 + 718 = 2839
 i: 105718 + 105 = 823 2839 + 823 = 3662
 a: 97823 + 97 = 920 3662 + 920 = 4582

 A = 920 = 398 hex (base 16)
 B = 4582 = 11E6 hex

 Output = 300286872 = 11E60398 hex

Операція додавання за модулем не має в цьому прикладі ніякого ефекту, оскільки жодне зі значень не досягло 65521.

Алгоритм обчислення контрольної суми Adler ідентичний алгоритму обчислення суми Fletcher крім деяких відмінностей. Перша відмінність полягає в тому, що у випадку функції Adler сума А ініціалізується значенням 1. Друга відмінність між двома алгоритмами в тому, що сума в алгоритмі Adler-32 обчислюється за модулем простого числа 65521, тоді як суми Fletcher обчислюються за модулем ${\displaystyle 2^{4}}$-1, ${\displaystyle 2^{8}}$-1, ${\displaystyle 2^{16}}$-1 (залежно від використовуваної кількості біт), які є складеними числами. Цю зміну в алгоритмі зроблено з метою досягти кращого перемішування біт. Використання простого числа дає змогу функції Adler-32 помічати відмінності в деяких комбінаціях байт, які функція Fletcher неспроможна зафіксувати. Третя відмінність, яка найбільше впливає на швидкість алгоритму, полягає в тому, що суми функції Adler-32 обчислюються над 8-бітовими, а не над 16-бітовими словами, що призводить до подвоєння кількості ітерацій циклу. Як наслідок, обчислення контрольної суми Adler-32 займає у півтора-два рази більше часу, ніж контрольної суми Fletcher для даних, розбитих на 16-бітові слова. Для даних, розбитих на байти, Adler-32 працює швидше, ніж алгоритм Fletcher.

Хоча контрольна сума Adler не визначена офіційно для інших довжин слів даних, можна використовувати найбільше просте ціле менше 2⁴ = 16 і 2⁸ = 256, щоб, з метою порівняння, реалізувати 8- і 16-бітові контрольні суми Adler. Маючи схожий алгоритм, контрольна сума Adler має продуктивність, схожу із сумою Fletcher. Усі 2-бітові помилки виявлено для слів даних довжиною менше, ніж M*(k/2) біт, де k — розмір контрольної суми, M — модуль суми Adler. Як і у випадку з контрольною сумою Fletcher, найгірше значення ймовірності невиявленої помилки спостерігається за однакової кількості нулів та одиниць у кожному блоці даних. Adler-8 і Adler-16 виявляють усі групові помилки завдовжки менше, ніж k/2 біт. Adler-32 виявляє всі групові помилки завдовжки трохи більше 7 біт. Рисунок1 показує залежність імовірності невиявлених помилок для контрольних сум Adler та Fletcher для частоти бітових помилок 10⁻⁵.

Краще перемішування біт, яке забезпечує контрольна сума Adler, мало дати кращі показники пошуку помилок, ніж у суми Fletcher. Але, як свідчить RFC 3385, Fletcher-32 працює краще, ніж Adler-32 на 8 KB. Контрольна сума Adler перевищує суму Fletcher тільки у випадку 16-бітових контрольних сум, і при цьому тільки в тій ділянці цих сум, де відстань Геммінга дорівнює 3. Проблема в тому, що, попри краще перемішування біт завдяки використанню як модуля операції простого числа, в результаті виходить менша кількість слів. Найчастіше це зводить нанівець позитивний ефект кращого перемішування. Отже, контрольна сума Fletcher перевищує суму Adler у всіх випадках, крім суми Adler-16, яка застосовується до коротких слів даних. Навіть збільшення ефективності пошуку помилок, можливо, не варте збільшення обчислювальних накладних витрат, спричиненого використанням модульних операцій.

Автори RFC 3385 провели порівняння ефективності виявлення помилок. Зведення отриманих результатів наведено в таблиці:

У таблиці: d — найменша відстань на блоці довжини Block, Block — довжина блоку в бітах, i/байт — кількість програмних інструкцій, що припадають на байт, T_size — розмір таблиці (в разі, якщо необхідний перегляд), T-look — кількість переглядів на байт, P_udb — ймовірність невиявлених групових помилок, P_uds — ймовірність невиявлених поодиноких помилок. Імовірності невиявлених помилок у таблиці обчислено з припущенням рівномірної розподіленості даних.

«Хороша» геш-функція відрізняється більш-менш рівномірним розподілом обчислених значень. Очевидно, що Adler-32 не задовольняє цю вимогу для коротких даних (найбільше значення A для 128-байтового повідомлення дорівнює 32640, менше, ніж 65521 — число, за яким береться операція модуля). Через цей недолік розробники протоколу SCTP надали перевагу алгоритму CRC32, оскільки в мережевому протоколі необхідне гешування коротких послідовностей байтів.

Так само як і для CRC32, для Adler-32 можна легко сконструювати колізію, тобто для даного геша знайти інші початкові дані, що мають таке саме значення функції.

Має перевагу над CRC32 в тому, що швидше обчислюється програмними засобами.

Наведений код містить просту реалізацю алгоритму мовою Сі:

uint32_t adler32( const unsigned char* buf, size_t buf_length )
{
  uint32_t s1 = 1;
  uint32_t s2 = 0;
 
  while( buf_length-- )
  {
    s1 = ( s1 + *( buf++ ) ) % 65521;
    s2 = ( s2 + s1 ) % 65521;
  }
  return ( s2 << 16 ) + s1;
 }

Ефективну реалізацію дивіться в коді бібліотеки zlib.

• У Java існує клас java.util.zip.Adler32, що реалізує алгоритм.^[1]
• У стандартній бібліотеці D, std.zlib: adler32
• У Perl існує Digest::Adler32, див. CPAN.^[2]
• Часткова реалізація для Python.
• У PHP доступна через функцію hash()
• Для Erlang доступні кілька вбудованих функцій (BIF) adler32(…)
• Для Go доступна в стандартній бібліотеці «hash/adler32»

• Theresa C. Maxino, Philip J. Koopman. The Effectiveness of Checksums for Embedded Control Networks // IEEE Trans. on Dependable and Secure Computing. — 2009. — 30 серпня. — С. 59—72.
• Theresa Maxino. Revisiting Fletcher and Adler Checksums // DSN 2006 Student Forum. — 2006. — 30 серпня.