Adler-32 — геш-функція, яку розробив . Модифікація контрольної суми Флетчера. Обчислює значення контрольної суми відповідно до RFC 1950 для масиву байтів або його фрагмента. Від CRC32 цей алгоритм розрахунку контрольної суми відрізняється продуктивністю. Використовується в бібліотеці Zlib. Rolling checksum версія функції використовується в утиліті rsync.
Історія Так само, як і у випадку контрольної суми Флетчера, під час розробляння суми Adler стояло завдання отримати контрольну суму з ефективністю виявлення помилок порівнянною з CRC. Хоча показники пошуку помилок контрольних сум Adler і Флетчера практично такі ж, як і у відносно слабких CRC, але в деяких важливих випадках вони поводяться значно гірше, ніж хороші CRC.
Алгоритм Контрольну суму Adler-32 отримують обчисленням двох 16-бітових контрольних сум A і Б та конкатенації їхніх бітів у 32-бітове ціле. А дорівнює сумі всіх байтів у рядку плюс один , а Б — сума всіх окремих значень А на кожному кроці. На початку виконання функції Adler-32 А ініціалізується одиницею, а Б — нулем. Суми беруться за модулем 65521 (найбільше просте число менше від 216). Байти записуються в мережевому порядку, Б займає 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 обчислюються за модулем -1, -1, -1 (залежно від використовуваної кількості біт), які є складеними числами. Цю зміну в алгоритмі зроблено з метою досягти кращого перемішування біт. Використання простого числа дає змогу функції Adler-32 помічати відмінності в деяких комбінаціях байт, які функція Fletcher неспроможна зафіксувати. Третя відмінність, яка найбільше впливає на швидкість алгоритму, полягає в тому, що суми функції Adler-32 обчислюються над 8-бітовими, а не над 16-бітовими словами, що призводить до подвоєння кількості ітерацій циклу. Як наслідок, обчислення контрольної суми Adler-32 займає у півтора-два рази більше часу, ніж контрольної суми Fletcher для даних, розбитих на 16-бітові слова. Для даних, розбитих на байти, Adler-32 працює швидше, ніж алгоритм Fletcher.
Хоча контрольна сума Adler не визначена офіційно для інших довжин слів даних, можна використовувати найбільше просте ціле менше 24 = 16 і 28 = 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−5.
Краще перемішування біт, яке забезпечує контрольна сума Adler, мало дати кращі показники пошуку помилок, ніж у суми Fletcher. Але, як свідчить RFC 3385, Fletcher-32 працює краще, ніж Adler-32 на 8 KB. Контрольна сума Adler перевищує суму Fletcher тільки у випадку 16-бітових контрольних сум, і при цьому тільки в тій ділянці цих сум, де відстань Геммінга дорівнює 3. Проблема в тому, що, попри краще перемішування біт завдяки використанню як модуля операції простого числа, в результаті виходить менша кількість слів. Найчастіше це зводить нанівець позитивний ефект кращого перемішування. Отже, контрольна сума Fletcher перевищує суму Adler у всіх випадках, крім суми Adler-16, яка застосовується до коротких слів даних. Навіть збільшення ефективності пошуку помилок, можливо, не варте збільшення обчислювальних накладних витрат, спричиненого використанням модульних операцій.
Порівняння з іншими контрольними сумами Автори RFC 3385 провели порівняння ефективності виявлення помилок. Зведення отриманих результатів наведено в таблиці: Алгоритм d Block i/байт Tsize T-look Pudb Puds Adler-32 3 219 3 - - 10−36 10−35 Fletcher-32 3 219 2 - - 10−37 10−36 IEEE-802 3 216 2,75 218 0,5/b 10−41 10−40 CRC32C 3 231−1 2,75 218 0,5/b 10−41 10−40 У таблиці: d — найменша відстань на блоці довжини Block, Block — довжина блоку в бітах, i/байт — кількість програмних інструкцій, що припадають на байт, Tsize — розмір таблиці (в разі, якщо необхідний перегляд), T-look — кількість переглядів на байт, Pudb — ймовірність невиявлених групових помилок, Puds — ймовірність невиявлених поодиноких помилок. Імовірності невиявлених помилок у таблиці обчислено з припущенням рівномірної розподіленості даних.
Переваги та недоліки «Хороша» геш-функція відрізняється більш-менш рівномірним розподілом обчислених значень. Очевидно, що Adler-32 не задовольняє цю вимогу для коротких даних (найбільше значення A для 128-байтового повідомлення дорівнює 32640, менше, ніж 65521 — число, за яким береться операція модуля). Через цей недолік розробники протоколу SCTP надали перевагу алгоритму CRC32, оскільки в мережевому протоколі необхідне гешування коротких послідовностей байтів.
Так само як і для CRC32, для Adler-32 можна легко сконструювати колізію, тобто для даного геша знайти інші початкові дані, що мають таке саме значення функції.
Має перевагу над CRC32 в тому, що швидше обчислюється програмними засобами.
Приклад реалізації мовою C Наведений код містить просту реалізацю алгоритму мовою Сі: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.
Adler-32 в інших мовах програмування
У Java існує клас java.util.zip.Adler32, що реалізує алгоритм. У стандартній бібліотеці D, std.zlib: adler32 У Perl існує Digest::Adler32, див. CPAN. Часткова реалізація для Python. У PHP доступна через функцію hash() Для Erlang доступні кілька вбудованих функцій (BIF) adler32(…) Для Go доступна в стандартній бібліотеці «hash/adler32»
Примітки
Література