Адлер-32
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 занимает два наиболее значимых байта.
Функция может быть выражена как
A = 1 + D1 + D2 + ... + Dn (mod 65521) B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521) = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521) Adler-32(D) = B × 65536 + A
где D — строка байтов, для которой должна быть вычислена контрольная сумма, а — длина D. n
Пример [ править ]
Сумма Adler-32 строки ASCII " Wikipedia"будет рассчитываться следующим образом:
| Характер | ASCII-код | А | Б | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| (показано как основание 10) | |||||||||||
| В | 87 | 88 | 88 | ||||||||
| я | 105 | 193 | 281 | ||||||||
| к | 107 | 300 | 581 | ||||||||
| я | 105 | 405 | 986 | ||||||||
| п | 112 | 517 | 1503 | ||||||||
| и | 101 | 618 | 2121 | ||||||||
| д | 100 | 718 | 2839 | ||||||||
| я | 105 | 823 | 3662 | ||||||||
| а | 97 | 920 | 4582 | ||||||||
A = 920 = 0x398 (base 16) B = 4582 = 0x11E6 Output = (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)
/*
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 эквивалентно наивному накоплению. [3]
Преимущества и недостатки [ править ]
- Как и стандартный CRC-32 , контрольную сумму Adler-32 можно легко подделать, и поэтому она небезопасна для защиты от преднамеренной модификации.
- На многих платформах это быстрее, чем CRC-32. [4]
- Adler-32 имеет слабость к коротким сообщениям длиной в несколько сотен байт, поскольку контрольные суммы этих сообщений плохо охватывают 32 доступных бита.
Слабость [ править ]
Adler-32 слаб для коротких сообщений, поскольку сумма A не переносится. Максимальная сумма 128-байтового сообщения равна 32640, что ниже значения 65521, используемого операцией по модулю. Это означает, что примерно половина выходного пространства не используется, а распределение внутри используемой части неравномерно. Расширенное объяснение можно найти в RFC 3309 , который требует использования CRC32C вместо Adler-32 для SCTP , протокола передачи управления потоком. [5] Также было показано, что Adler-32 неэффективен для небольших постепенных изменений. [6] а также слаб для строк, сгенерированных из общего префикса и последовательных чисел (например, автоматически генерируемых имен меток типичными генераторами кода). [7]
См. также [ править ]
Примечания [ править ]
- ^ «Первое появление Adler-32 (см. журнал изменений и adler32.c)» .
- ^ «Возвращаясь к контрольным суммам Флетчера и Адлера» (PDF) .
- ^ "adler32.js" . Лист Дж.С. 3 июля 2019 г.
- ^ Тереза К. Максино, Филип Дж. Купман (январь 2009 г.). «Эффективность контрольных сумм для встроенных сетей управления» (PDF) . Транзакции IEEE для надежных и безопасных вычислений .
- ^ RFC 3309
- ^ "Cbloom разглагольствует: 21.08.10 - Адлер32" . 21 августа 2010 г.
- ^ «Хеш-функции: эмпирическое сравнение — strchr.com» . www.strchr.com .
Внешние ссылки [ править ]
- RFC 1950 - спецификация, содержит пример C. кода
- ZLib – реализует контрольную сумму Adler-32 в adler32.c.
- Chrome – использует SIMD- реализацию Adler-32 adler32_simd.c.
- RFC 3309 — информация о слабости коротких сообщений и связанных с этим изменениях в SCTP.