Adler-32 | это... Что такое Adler-32? (original) (raw)

Adler-32 — хеш-функция, разработанная Марком Адлером (англ.). Является модификацией контрольной суммы Fletcher (англ.). Вычисляет значение контрольной суммы в соответствии с RFC 1950 для массива байт или его фрагмента. Данный алгоритм расчёта контрольной суммы отличается от CRC32 производительностью. Adler-32 используется в библиотеке Zlib. Rolling checksum версия функции используется в утилите rsync.

Содержание

1 История
2 Алгоритм
3 Пример
4 Сравнение с контрольной суммой Fletcher
5 Сравнение с другими контрольными суммами
6 Преимущества и недостатки
7 Пример реализации на языке C
8 Adler-32 в других языках программирования
9 Примечания
10 Литература

История

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

Алгоритм

Контрольная сумма Adler-32 получается путём вычисления двух 16-битных контрольных сумм A и Б и конкатенации их бит в 32-битное целое. А равняется сумме всех байт в строке плюс один, а Б является суммой всех отдельных значений А на каждом шаге. В начале выполнения функции Adler-32, А инициализируется единицей, а Б нулем. Суммы берутся по модулю 65521 (самое большое простое число меньшее чем 216). Байты записываются в сетевом порядке, Б занимает 2 старших байта.
Функция может быть выражена как:

A = 1 + _D_1 + _D_2 + ... + D n (mod 65521) B = (1 + _D_1) + (1 + _D_1 + _D_2) + ... + (1 + _D_1 + _D_2 + ... + D n) (mod 65521) = _n_×_D_1 + (n-1)×_D_2 + (n-2)×_D_3 + ... + D n + n (mod 65521)

Adler-32(D) = B × 65536 + A

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

Пример

Значение Adler-32 для ASCII строки «Wikipedia» вычисляется следующим образом:

ASCII code A B (shown as base 10) 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 (base 16) B = 4582 = 11E6 hex

Output = 300286872 = 11E60398 hex

Операция сложения по модулю не даёт никакого эффекта в этом примере, так как ни одно из значений не достигло 65521.

Сравнение с контрольной суммой Fletcher

Алгоритм вычисления контрольной суммы Adler идентичен алгоритму вычисления суммы Fletcher, за исключением некоторых отличий. Первое отличие состоит в том, что в случае функции Adler сумма А инициализируется значением 1. Второе отличие между двумя алгоритмами в том, что сумма в алгоритме Adler-32 вычисляются по модулю простого числа 65521, когда как суммы Fletcher вычисляются по модулю $2^{4}$ -1, $2^{8}$ -1, $2^{16}$ -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.

Рисунок1 Вероятность необнаруженных ошибок для контрольных сумм Adler и Fletcher для частоты битовых ошибок 10−5.

Лучшее перемешивание бит, которое обеспечивает контрольная сумма Adler, должно было привести к лучшим показателям поиска ошибок чем у суммы Fletcher. Но как показывает RFC 3385, Fletcher-32 работает лучше чем Adler-32 на 8KB. Контрольная сумма 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

Неэффективной, но простой реализацией алгоритма на языке Cи является следующий код:

uint32_t adler32(unsigned char* buf, unsigned int buflength) { uint32_t s1 = 1; uint32_t s2 = 0;

 for (unsigned int n=0; n<buflength; n++)
 {
    s1 = (s1 + buf[n]) % 65521;
    s2 = (s2 + s1)     % 65521;
 }
 return (s2 << 16) + s1;

}

Эффективную реализацию смотрите в коде библиотеки zlib.

Adler-32 в других языках программирования

В Java существует класс java.util.zip.Adler32, реализующий алгоритм.[1]
В Perl существует Digest::Adler32, см. CPAN.[2]
Частная реализация для Python.[3]
В PHP доступна через функцию hash()
Для Erlang доступны несколько встроенных функций (BIF) adler32(…)

Примечания

Литература

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

Хеш-функции
Общего назначения	Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash
Криптографические	JH • HAVAL • Keccak • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94