Адлер-32 - Adler-32

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

История

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

Алгоритм

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

В начале пробега Адлер-32, А инициализируется 1, B до 0. Суммы сделаны по модулю 65521 (самый крупный простое число меньше 216). Байты хранятся в сетевом порядке (прямой порядок байтов ), B занимая два самых старших байта.

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

А = 1 + D1 + D2 + ... + Dп (мод. 65521)B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dп) (мод 65521) = п×D1 + (п−1)×D2 + (п−2)×D3 + ... + Dп + п (мод. 65521)Адлер-32(D) = B × 65536 + А

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

Пример

Сумма Адлер-32 ASCII нить "Википедия"будет рассчитываться следующим образом:

ХарактерКод ASCIIАB
(показано как база 10)
W871 +87 =880 +88 =88
я10588 +105 =19388 +193 =281
k107193 +107 =300281 +300 =581
я105300 +105 =405581 +405 =986
п112405 +112 =517986 +517 =1503
е101517 +101 =6181503 +618 =2121
d100618 +100 =7182121 +718 =2839
я105718 +105 =8232839 +823 =3662
а97823 +97 =9203662 +920 =4582
A = 920 = 0x398 (основание 16) B = 4582 = 0x11E6 Выход = 0x11E6 << 16 + 0x398 = 0x11E60398

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

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

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

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

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

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

const uint32_t MOD_ADLER = 65521;uint32_t adler32(беззнаковый char *данные, size_t len) /*     где данные - это расположение данных в физической памяти и     len - длина данных в байтах */{    uint32_t а = 1, б = 0;    size_t индекс;        // Обработка каждого байта данных по порядку    за (индекс = 0; индекс < len; ++индекс)    {        а = (а + данные[индекс]) % MOD_ADLER;        б = (б + а) % MOD_ADLER;    }        возвращаться (б << 16) | а;}

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

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

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

Слабое место

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

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

Примечания

  1. ^ Первое появление Адлера-32 (см. ChangeLog и adler32.c)
  2. ^ Возвращаясь к контрольным суммам Флетчера и Адлера
  3. ^ "adler32.js". Лист JS. 3 июля 2019.
  4. ^ Тереза ​​К. Максино, Филип Дж. Купман (январь 2009 г.). «Эффективность контрольных сумм для встроенных сетей управления» (PDF). Транзакции IEEE о надежных и безопасных вычислениях.
  5. ^ RFC  3309
  6. ^ http://cbloomrants.blogspot.com/2010/08/08-21-10-adler32.html
  7. ^ http://www.strchr.com/hash_functions

внешняя ссылка

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