Адлер-32 - Adler-32

Adler-32 - это алгоритм контрольной суммы , который был написан Марком Адлером в 1995 году и представляет собой модификацию контрольной суммы Флетчера . По сравнению с циклической проверкой избыточности такой же продолжительности, здесь надежность торгуется на скорость (отдавая предпочтение последнему). Адлер-32 более надежен, чем Флетчер-16 , и немного менее надежен, чем Флетчер-32 .

История

Контрольная сумма Adler-32 является частью широко используемой библиотеки сжатия zlib , поскольку обе были разработаны Марком Адлером . Версия Adler-32 с « скользящей контрольной суммой » используется в утилите rsync .

Алгоритм

Контрольная сумма Adler-32 получается путем вычисления двух 16-битных контрольных сумм A и B и объединения их битов в 32-битное целое число. A - это сумма всех байтов в потоке плюс один, а B - это сумма отдельных значений A с каждого шага.

В начале цикла Adler-32 A инициализируется значением 1, B - 0. Суммы производятся по модулю 65521 (наибольшее простое число меньше 2 ¹⁶ ). Байты хранятся в сетевом порядке ( big endian ), B занимает два самых значимых байта.

Функция может быть выражена как

A = 1 + D₁ + D₂ + ... + D_n (mod 65521)

B = (1 + D₁) + (1 + D₁ + D₂) + ... + (1 + D₁ + D₂ + ... + D_n) (mod 65521)
  = n×D₁ + (n−1)×D₂ + (n−2)×D₃ + ... + D_n + n (mod 65521)

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

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

Пример

Сумма Adler-32 строки ASCII " Wikipedia " будет рассчитана следующим образом:

Характер	Код ASCII	А			B
(показано как база 10)
W	87	1 +	87 =	88	0 +	88 =	88
я	105	88 +	105 =	193	88 +	193 =	281
k	107	193+	107 =	300	281+	300 =	581
я	105	300 +	105 =	405	581+	405 =	986
п	112	405+	112 =	517	986+	517 =	1503
е	101	517 +	101 =	618	1503+	618 =	2121
d	100	618 +	100 =	718	2121 +	718 =	2839
я	105	718 +	105 =	823	2839 +	823 =	3662
а	97	823+	97 =	920	3662 +	920 =	4582

A =  920 =  0x398  (base 16)
B = 4582 = 0x11E6
Output = 0x11E6 << 16 + 0x398 = 0x11E60398

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

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

Первое различие между двумя алгоритмами заключается в том, что суммы Адлера-32 вычисляются по модулю простого числа, тогда как суммы Флетчера вычисляются по модулю 2 ⁴ -1, 2 ⁸ -1 или 2 ¹⁶ -1 (в зависимости от количества используемых битов). , которые являются составными числами . Использование простого числа позволяет Adler-32 улавливать различия в определенных комбинациях байтов, которые Флетчер не может обнаружить.

Второе отличие, которое оказывает наибольшее влияние на скорость алгоритма, заключается в том, что суммы Адлера вычисляются по 8-битным байтам, а не по 16-битным словам , что приводит к удвоению количества итераций цикла. Это приводит к тому, что контрольная сумма Adler-32 занимает от полутора до двух раз больше, чем контрольная сумма Флетчера для данных с выравниванием по 16-битному слову. Для данных, выровненных по байтам, Adler-32 работает быстрее, чем правильно реализованная контрольная сумма Флетчера (например, найденная в формате иерархических данных ).

Пример реализации

В C неэффективная, но простая реализация:

const uint32_t MOD_ADLER = 65521;

uint32_t adler32(unsigned char *data, size_t len) 
/* 
    where data is the location of the data in physical memory and 
    len is the length of the data in bytes 
*/
{
    uint32_t a = 1, b = 0;
    size_t index;
    
    // Process each byte of the data in order
    for (index = 0; index < len; ++index)
    {
        a = (a + data[index]) % MOD_ADLER;
        b = (b + a) % MOD_ADLER;
    }
    
    return (b << 16) | a;
}

См. Исходный код zlib для более эффективной реализации, которая требует выборки и двух добавлений на байт, с отложенными операциями по модулю с двумя остатками, вычисляемыми каждые несколько тысяч байтов, метод, впервые обнаруженный для контрольных сумм Флетчера в 1988 году. js-adler32 Обеспечивает аналогичную оптимизацию с добавление уловки, которая задерживает вычисление «15» в 65536 - 65521, так что модули становятся быстрее: можно показать, что ((a >> 16) * 15 + (a & 65535)) % 65521 это эквивалентно наивному накоплению.

Преимущества и недостатки

Как и стандартный CRC-32 , контрольную сумму Adler-32 можно легко подделать, и поэтому она небезопасна для защиты от преднамеренного изменения.
Это быстрее, чем CRC-32 на многих платформах.
Adler-32 имеет слабость к коротким сообщениям с несколькими сотнями байтов, потому что контрольные суммы для этих сообщений плохо покрывают 32 доступных бита.

Слабое место

Adler-32 слаб для коротких сообщений, потому что сумма A не переносится. Максимальная сумма 128-байтового сообщения составляет 32640, что ниже значения 65521, используемого операцией по модулю, что означает, что примерно половина выходного пространства не используется, а распределение внутри используемой части неравномерно. Расширенное объяснение можно найти в RFC 3309 , который требует использования CRC32C вместо Adler-32 для SCTP , протокола передачи управления потоком. Adler-32 также оказался слабым для небольших инкрементальных изменений, а также слабым для строк, созданных из общего префикса и последовательных чисел (например, автоматически сгенерированных имен меток типичными генераторами кода).

Смотрите также

Список хеш-функций

Ноты

внешние ссылки

RFC 1950 - спецификация, содержит пример кода C
ZLib - реализует контрольную сумму Adler-32 в adler32.c
Chrome - использует SIMD- реализацию Adler-32 adler32_simd.c
RFC 3309 - информация о слабости коротких сообщений и связанных изменениях в SCTP

Languages

In other projects