Adler-32 — хеш-функция, разработанная Марком Адлером. Является модификацией контрольной суммы Флетчера. Вычисляет значение контрольной суммы в соответствии с RFC 1950 для массива байт или его фрагмента. Данный алгоритм расчёта контрольной суммы отличается от CRC32 производительностью. Adler-32 используется в библиотеке Zlib. Rolling checksum версия функции используется в утилите rsync.
Так же, как и в случае контрольной суммы Fletcher, при разработке суммы Adler стояла задача получения контрольной суммы с эффективностью обнаружения ошибок, сравнимой с CRC. Хотя показатели поиска ошибок контрольных сумм Adler и Fletcher практически такие же, как и у относительно слабых CRC, но в некоторых важных случаях они ведут себя гораздо хуже, чем хорошие CRC.
Алгоритм
Контрольная сумма Adler-32 получается путём вычисления двух 16-битных контрольных сумм A и Б и конкатенации их бит в 32-битное целое. А равняется сумме всех байт в строке плюс один, а Б является суммой всех отдельных значений А на каждом шаге. В начале выполнения функции Adler-32 А инициализируется единицей, а Б — нулём. Суммы берутся по модулю 65521 (самое большое простое число, меньшее, чем 216). Байты записываются в сетевом порядке, Б занимает 2 старших байта.
Операция сложения по модулю не даёт никакого эффекта в этом примере, так как ни одно из значений не достигло 65521.
Сравнение с контрольной суммой Fletcher
Алгоритм вычисления контрольной суммы 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/byte
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/byte — количество программных инструкций, приходящихся на байт, Tsize — размер таблицы (в случае, если необходим просмотр), T-look — число просмотров на байт, Pudb — вероятность необнаруженных групповых ошибок, Puds — вероятность необнаруженных единичных ошибок.
Вероятности необнаруженных ошибок в таблице, приведённой выше, вычислены в предположении равномерной распределённости данных.
Преимущества и недостатки
«Хорошая» хеш-функция отличается более-менее равномерным распределением вычисленных значений. Очевидно, что Adler-32 не удовлетворяет этому требованию для коротких данных (максимальное значение A для 128-байтного сообщения равняется 32640, которое меньше, чем 65521 — число, по которому берется операция модуля). Из-за этого недостатка разработчики протокола SCTP предпочли этому алгоритму CRC32, так как в сетевом протоколе необходимо хеширование коротких последовательностей байт.
Точно как и для CRC32, для Adler-32 можно легко сконструировать коллизию, то есть для данного хеша найти другие исходные данные, имеющие то же значение функции.
Имеет преимущество над CRC32 в том, что она быстрее вычисляется программными средствами.
Пример реализации на языке C
Простой реализацией алгоритма на языке Си является следующий код: