Adler-32

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

История

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

Алгоритм

Контрольная сумма Adler-32 получается путём вычисления двух 16-битных контрольных сумм A и Б и конкатенации их бит в 32-битное целое. А равняется сумме всех байт в строке плюс один, а Б является суммой всех отдельных значений А на каждом шаге. В начале выполнения функции Adler-32, А инициализируется единицей, а Б нулем. Суммы берутся по модулю 65521 (самое большое простое число меньшее чем 2¹⁶). Байты записываются в сетевом порядке, Б занимает 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 вычисляются по модулю <math>2^{4}</math>-1, <math>2^{8}</math>-1, <math>2^{16}</math>-1 (в зависимости от используемого количества бит), которые являются составными числами. Это изменение в алгоритме было сделано с целью достижения лучшего перемешивания бит. Использование простого числа позволяет функции Adler-32 замечать различия в некоторых комбинациях байт, которые функция Fletcher неспособна зафиксировать. Третье отличие, которое наиболее сильным образом влияет на скорость алгоритма, заключается в том, что суммы функции Adler-32 вычисляются над 8-битными, а не над 16-битными словами, что приводит к удвоению числа итераций цикла. Это приводит к тому, что вычисление контрольной суммы Adler-32 занимает от полутора до двух раз большее количество времени чем контрольная сумма Fletcher для данных разбитых на 16-битные слова. Для данных разбитых на байты, Adler-32 работает быстрее чем алгоритм Fletcher.

Хотя контрольная сумма Adler не определена официально для других длин слов данных, можно использовать самое большое простое целое меньшее 2⁴=16 и 2⁸=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⁻⁵. Лучшее перемешивание бит, которое обеспечивает контрольная сумма 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 — количество программных инструкций, приходящихся на байт, T_size — размер таблицы (в случае если необходим просмотр), T-look — число просмотров на байт, P_udb — вероятность не обнаруженных групповых ошибок, P_uds — вероятность не обнаруженных единичных ошибок.
Вероятности не обнаруженных ошибок в таблице, приведённой выше, вычислены в предположении равномерной распределённости данных.

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

«Хорошая» хеш-функция отличается более-менее равномерным распределением вычисленных значений. Очевидно, что Adler-32 не удовлетворяет этому требованию для коротких данных (максимальное значение A для 128-байтного сообщения равняется 32640, которое ниже чем 65521 — число по которому берется операция модуля). Из-за этого недостатка разработчики протокола SCTP предпочли этому алгоритму CRC32, так как в сетевом протоколе необходимо хеширование коротких последовательностей байт.

Точно как и для CRC32, для Adler-32 можно легко сконструировать коллизию, то есть для данного хеша найти другие исходные данные, имеющие то же значение функции.

Имеет преимущество над CRC32 в том, что она быстрее вычисляется программными средствами.

Пример реализации на языке 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, реализующий алгоритм.
• В Perl существует Digest::Adler32, см. CPAN.
• Частная реализация для Python.
• В PHP доступна через функцию [ru.php.net/manual/en/function.hash.php hash()]
• Для Erlang доступны несколько встроенных функций (BIF) [www.erlang.org/doc/man/erlang.html adler32(…)]
• Для Go доступна в стандартной библиотеке [golang.org/pkg/hash/adler32/ "hash/adler32"]

Литература

• Theresa C. Maxino, Philip J. Koopman [www.ece.cmu.edu/~koopman/pubs/maxino09_checksums.pdf The Effectiveness of Checksums for Embedded Control Networks] // IEEE Trans. on Dependable and Secure Computing. — 2009. — С. 59-72.
• Theresa Maxino [www.zlib.net/maxino06_fletcher-adler.pdf Revisiting Fletcher and Adler Checksums] // DSN 2006 Student Forum. — 2006.

Отрывок, характеризующий Adler-32

В балагане, в который поступил Пьер и в котором он пробыл четыре недели, было двадцать три человека пленных солдат, три офицера и два чиновника.
Все они потом как в тумане представлялись Пьеру, но Платон Каратаев остался навсегда в душе Пьера самым сильным и дорогим воспоминанием и олицетворением всего русского, доброго и круглого. Когда на другой день, на рассвете, Пьер увидал своего соседа, первое впечатление чего то круглого подтвердилось вполне: вся фигура Платона в его подпоясанной веревкою французской шинели, в фуражке и лаптях, была круглая, голова была совершенно круглая, спина, грудь, плечи, даже руки, которые он носил, как бы всегда собираясь обнять что то, были круглые; приятная улыбка и большие карие нежные глаза были круглые.
Платону Каратаеву должно было быть за пятьдесят лет, судя по его рассказам о походах, в которых он участвовал давнишним солдатом. Он сам не знал и никак не мог определить, сколько ему было лет; но зубы его, ярко белые и крепкие, которые все выкатывались своими двумя полукругами, когда он смеялся (что он часто делал), были все хороши и целы; ни одного седого волоса не было в его бороде и волосах, и все тело его имело вид гибкости и в особенности твердости и сносливости.
Лицо его, несмотря на мелкие круглые морщинки, имело выражение невинности и юности; голос у него был приятный и певучий. Но главная особенность его речи состояла в непосредственности и спорости. Он, видимо, никогда не думал о том, что он сказал и что он скажет; и от этого в быстроте и верности его интонаций была особенная неотразимая убедительность.
Физические силы его и поворотливость были таковы первое время плена, что, казалось, он не понимал, что такое усталость и болезнь. Каждый день утром а вечером он, ложась, говорил: «Положи, господи, камушком, подними калачиком»; поутру, вставая, всегда одинаково пожимая плечами, говорил: «Лег – свернулся, встал – встряхнулся». И действительно, стоило ему лечь, чтобы тотчас же заснуть камнем, и стоило встряхнуться, чтобы тотчас же, без секунды промедления, взяться за какое нибудь дело, как дети, вставши, берутся за игрушки. Он все умел делать, не очень хорошо, но и не дурно. Он пек, парил, шил, строгал, тачал сапоги. Он всегда был занят и только по ночам позволял себе разговоры, которые он любил, и песни. Он пел песни, не так, как поют песенники, знающие, что их слушают, но пел, как поют птицы, очевидно, потому, что звуки эти ему было так же необходимо издавать, как необходимо бывает потянуться или расходиться; и звуки эти всегда бывали тонкие, нежные, почти женские, заунывные, и лицо его при этом бывало очень серьезно.
Попав в плен и обросши бородою, он, видимо, отбросил от себя все напущенное на него, чуждое, солдатское и невольно возвратился к прежнему, крестьянскому, народному складу.
– Солдат в отпуску – рубаха из порток, – говаривал он. Он неохотно говорил про свое солдатское время, хотя не жаловался, и часто повторял, что он всю службу ни разу бит не был. Когда он рассказывал, то преимущественно рассказывал из своих старых и, видимо, дорогих ему воспоминаний «христианского», как он выговаривал, крестьянского быта. Поговорки, которые наполняли его речь, не были те, большей частью неприличные и бойкие поговорки, которые говорят солдаты, но это были те народные изречения, которые кажутся столь незначительными, взятые отдельно, и которые получают вдруг значение глубокой мудрости, когда они сказаны кстати.
Часто он говорил совершенно противоположное тому, что он говорил прежде, но и то и другое было справедливо. Он любил говорить и говорил хорошо, украшая свою речь ласкательными и пословицами, которые, Пьеру казалось, он сам выдумывал; но главная прелесть его рассказов состояла в том, что в его речи события самые простые, иногда те самые, которые, не замечая их, видел Пьер, получали характер торжественного благообразия. Он любил слушать сказки, которые рассказывал по вечерам (всё одни и те же) один солдат, но больше всего он любил слушать рассказы о настоящей жизни. Он радостно улыбался, слушая такие рассказы, вставляя слова и делая вопросы, клонившиеся к тому, чтобы уяснить себе благообразие того, что ему рассказывали. Привязанностей, дружбы, любви, как понимал их Пьер, Каратаев не имел никаких; но он любил и любовно жил со всем, с чем его сводила жизнь, и в особенности с человеком – не с известным каким нибудь человеком, а с теми людьми, которые были перед его глазами. Он любил свою шавку, любил товарищей, французов, любил Пьера, который был его соседом; но Пьер чувствовал, что Каратаев, несмотря на всю свою ласковую нежность к нему (которою он невольно отдавал должное духовной жизни Пьера), ни на минуту не огорчился бы разлукой с ним. И Пьер то же чувство начинал испытывать к Каратаеву.
Платон Каратаев был для всех остальных пленных самым обыкновенным солдатом; его звали соколик или Платоша, добродушно трунили над ним, посылали его за посылками. Но для Пьера, каким он представился в первую ночь, непостижимым, круглым и вечным олицетворением духа простоты и правды, таким он и остался навсегда.
Платон Каратаев ничего не знал наизусть, кроме своей молитвы. Когда он говорил свои речи, он, начиная их, казалось, не знал, чем он их кончит.
Когда Пьер, иногда пораженный смыслом его речи, просил повторить сказанное, Платон не мог вспомнить того, что он сказал минуту тому назад, – так же, как он никак не мог словами сказать Пьеру свою любимую песню. Там было: «родимая, березанька и тошненько мне», но на словах не выходило никакого смысла. Он не понимал и не мог понять значения слов, отдельно взятых из речи. Каждое слово его и каждое действие было проявлением неизвестной ему деятельности, которая была его жизнь. Но жизнь его, как он сам смотрел на нее, не имела смысла как отдельная жизнь. Она имела смысл только как частица целого, которое он постоянно чувствовал. Его слова и действия выливались из него так же равномерно, необходимо и непосредственно, как запах отделяется от цветка. Он не мог понять ни цены, ни значения отдельно взятого действия или слова.


Получив от Николая известие о том, что брат ее находится с Ростовыми, в Ярославле, княжна Марья, несмотря на отговариванья тетки, тотчас же собралась ехать, и не только одна, но с племянником. Трудно ли, нетрудно, возможно или невозможно это было, она не спрашивала и не хотела знать: ее обязанность была не только самой быть подле, может быть, умирающего брата, но и сделать все возможное для того, чтобы привезти ему сына, и она поднялась ехать. Если князь Андрей сам не уведомлял ее, то княжна Марья объясняла ото или тем, что он был слишком слаб, чтобы писать, или тем, что он считал для нее и для своего сына этот длинный переезд слишком трудным и опасным.
В несколько дней княжна Марья собралась в дорогу. Экипажи ее состояли из огромной княжеской кареты, в которой она приехала в Воронеж, брички и повозки. С ней ехали m lle Bourienne, Николушка с гувернером, старая няня, три девушки, Тихон, молодой лакей и гайдук, которого тетка отпустила с нею.
Ехать обыкновенным путем на Москву нельзя было и думать, и потому окольный путь, который должна была сделать княжна Марья: на Липецк, Рязань, Владимир, Шую, был очень длинен, по неимению везде почтовых лошадей, очень труден и около Рязани, где, как говорили, показывались французы, даже опасен.
Во время этого трудного путешествия m lle Bourienne, Десаль и прислуга княжны Марьи были удивлены ее твердостью духа и деятельностью. Она позже всех ложилась, раньше всех вставала, и никакие затруднения не могли остановить ее. Благодаря ее деятельности и энергии, возбуждавшим ее спутников, к концу второй недели они подъезжали к Ярославлю.
В последнее время своего пребывания в Воронеже княжна Марья испытала лучшее счастье в своей жизни. Любовь ее к Ростову уже не мучила, не волновала ее. Любовь эта наполняла всю ее душу, сделалась нераздельною частью ее самой, и она не боролась более против нее. В последнее время княжна Марья убедилась, – хотя она никогда ясно словами определенно не говорила себе этого, – убедилась, что она была любима и любила. В этом она убедилась в последнее свое свидание с Николаем, когда он приехал ей объявить о том, что ее брат был с Ростовыми. Николай ни одним словом не намекнул на то, что теперь (в случае выздоровления князя Андрея) прежние отношения между ним и Наташей могли возобновиться, но княжна Марья видела по его лицу, что он знал и думал это. И, несмотря на то, его отношения к ней – осторожные, нежные и любовные – не только не изменились, но он, казалось, радовался тому, что теперь родство между ним и княжной Марьей позволяло ему свободнее выражать ей свою дружбу любовь, как иногда думала княжна Марья. Княжна Марья знала, что она любила в первый и последний раз в жизни, и чувствовала, что она любима, и была счастлива, спокойна в этом отношении.