Adler-32


Adler-32

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

Содержание

История

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

Алгоритм

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

 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 — строка байт для которых должна быть вычислена контрольная сумма, а 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(…)

Примечания

Литература


Wikimedia Foundation. 2010.

Смотреть что такое "Adler-32" в других словарях:

  • Adler — Adler …   Deutsch Wörterbuch

  • Adler — (v. mittelhochdt. adelare, urspr. edelaar zu Aar) steht für: Adler (Familienname), einen Familiennamen Adler (Biologie), Trivialbezeichnung für verschiedene Greifvögel Echte Adler, die Vertreter der Gattung Aquila Adler (Sternbild), ein Sternbild …   Deutsch Wikipedia

  • Adler — Adler …   Википедия

  • Adler-32 — is a checksum algorithm which was invented by Mark Adler. Compared to a cyclic redundancy check of the same length it trades reliability for speed. Compared to its original form (Fletcher 16), Adler 32 is more reliable than Fletcher 16. However,… …   Wikipedia

  • Adler — es un nombre alemán común; significa águila . El término Adler puede referirse a: ● Adler (automóvil), un automóvilo de principios del siglo XX ● Adler (supermercado), un supermercado en Polonia ● Adler Mannheim, un equipo de hockey alemán ●… …   Enciclopedia Universal

  • Adler I — auf dem N O K p1 …   Deutsch Wikipedia

  • Adler XI — an der Seebrücke Heringsdorf p1 …   Deutsch Wikipedia

  • ADLER — ADLER, family originally from frankfurt . There are different theories as to the origin of the family name. According to one, the early members of the family lived in a house bearing the sign of an eagle (Ger. Adler). The main branch, whose… …   Encyclopedia of Judaism

  • ADLER — ADLER, U.S. theatrical family. The founder was JACOB ADLER (1855–1926), one of the leading Jewish actor managers of his time, and a reformer of the early Yiddish theater. Born in Odessa, he first acted with amateurs, and in 1879 joined one  … …   Encyclopedia of Judaism

  • Adler-32 — ist ein einfacher, von Mark Adler entwickelter Prüfsummenalgorithmus. Er wird unter anderem von der zlib Bibliothek benutzt, um (zufällige Übertragungs )Fehler im komprimierten Datenstrom zu erkennen. In RFC 1950 wird der Algorithmus genau… …   Deutsch Wikipedia

Книги

Другие книги по запросу «Adler-32» >>