Adler-32 — это алгоритм контрольной суммы , написанный Марком Адлером в 1995 году, [1] модифицирующий контрольную сумму Флетчера . По сравнению с проверкой циклическим избыточным кодом той же длины, надежность жертвуется скоростью. Адлер-32 более надежен, чем Флетчер-16 , и немного менее надежен, чем Флетчер-32 . [2]
Контрольная сумма Adler-32 является частью широко используемой библиотеки сжатия zlib , поскольку обе были разработаны Марком Адлером . Версия Adler-32 с « скользящей контрольной суммой » используется в утилите rsync .
Контрольная сумма Адлера-32 получается путем вычисления двух 16-битных контрольных сумм A и B и объединения их битов в 32-битное целое число. A — это сумма всех байтов в потоке плюс один, а B — сумма отдельных значений A на каждом шаге.
В начале запуска Adler-32 A инициализируется значением 1, B — 0. Суммы выполняются по модулю 65521 (наибольшее простое число меньше 2 16 ). Байты хранятся в сетевом порядке ( с прямым порядком байтов ), причем B занимает два наиболее значимых байта.
Функция может быть выражена как
А = 1 + Д 1 + Д 2 + ... + Д н (мод 65521)B = (1 + D 1 ) + (1 + D 1 + D 2 ) + ... + (1 + D 1 + D 2 + ... + D n ) (мод 65521) = n × D 1 + ( n −1) × D 2 + ( n −2) × D 3 + ... + D n + n (mod 65521)Адлер-32 ( Д ) = Б × 65536 + А
где D — строка байтов, для которой должна быть вычислена контрольная сумма, а n — длина D.
Сумма Adler-32 строки ASCII " Wikipedia" будет рассчитываться следующим образом:
А = 920 = 0x398 (основание 16)Б = 4582 = 0x11E6Вывод = (0x11E6 << 16) + 0x398 = 0x11E60398 = 300286872
Операция по модулю в этом примере не имела никакого эффекта, поскольку ни одно из значений не достигло 65521.
Первое различие между двумя алгоритмами заключается в том, что суммы Адлера-32 вычисляются по модулю простого числа, тогда как суммы Флетчера вычисляются по модулю 2 4 -1, 2 8 -1 или 2 16 -1 (в зависимости от количества используемых битов). , которые все являются составными числами . Использование простого числа позволяет Adler-32 улавливать различия в определенных комбинациях байтов, которые Флетчер не может обнаружить.
Второе отличие, которое больше всего влияет на скорость алгоритма, заключается в том, что суммы Адлера вычисляются по 8-битным байтам , а не по 16-битным словам , что приводит к удвоению количества итераций цикла. В результате контрольная сумма Адлера-32 занимает от полутора до двух раз больше, чем контрольная сумма Флетчера для 16-битных данных, выровненных по словам. Для данных с байтовым выравниванием Adler-32 работает быстрее, чем правильно реализованная контрольная сумма Флетчера (например, найденная в иерархическом формате данных ).
В C неэффективная, но простая реализация:
const uint32_t MOD_ADLER = 65521 ; uint32_t adler32 ( unsigned char * data , size_t len ) /* где data — это расположение данных в физической памяти, а len — длина данных в байтах */ { uint32_t a = 1 , b = 0 ; индекс size_t ; // Обрабатываем каждый байт данных по порядку ( index = 0 ; index < len ; ++ index ) { a = ( a + data [ index ] ) % MOD_ADLER ; б = ( б + а ) % MOD_ADLER ; } возврат ( б << 16 ) | а ; } См. исходный код zlib для более эффективной реализации, которая требует выборки и двух сложений на байт, с отложенными операциями по модулю с двумя остатками, вычисляемыми каждые несколько тысяч байтов, метод, впервые обнаруженный для контрольных сумм Флетчера в 1988 году. js-adler32Обеспечивает аналогичную оптимизацию с добавление трюка, который задерживает вычисление «15» в 65536–65521, чтобы модули стали быстрее: можно показать, что это ((a >> 16) * 15 + (a & 65535)) % 65521эквивалентно наивному накоплению. [3]
Adler-32 слаб для коротких сообщений, поскольку сумма A не переносится. Максимальная сумма 128-байтового сообщения равна 32640, что ниже значения 65521, используемого операцией по модулю. Это означает, что примерно половина выходного пространства не используется, а распределение внутри используемой части неравномерно. Расширенное объяснение можно найти в RFC 3309, который требует использования CRC32C вместо Adler-32 для SCTP , протокола передачи управления потоком. [5] Adler-32 также оказался слабым для небольших дополнительных изменений, [6] а также слабым для строк, сгенерированных из общего префикса и последовательных чисел (например, автоматически генерируемых имен меток типичными генераторами кода). [7]