Просмотр кода страницы Adler-32

{{falseredirect|Fletcher's checksum}}
'''Adler-32''' — [[хеш-функция]], разработанная [[Адлер, Марк|Марком Адлером]]. Является модификацией контрольной суммы [[Контрольная сумма Флетчера|Флетчера]]. Вычисляет значение [[контрольная сумма|контрольной суммы]] в соответствии с RFC 1950 для массива байт или его фрагмента. Данный алгоритм расчёта контрольной суммы отличается от [[CRC|CRC32]] производительностью. Adler-32 используется в библиотеке [[Zlib]]. [[Кольцевой хеш|Rolling checksum]] версия функции используется в утилите [[rsync]].

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

== Алгоритм ==
Контрольная сумма Adler-32 получается путём вычисления двух 16-битных контрольных сумм '''A''' и '''Б''' и конкатенации их бит в 32-битное целое. '''А''' равняется сумме всех байт в строке плюс один, а '''Б''' является суммой всех отдельных значений '''А''' на каждом шаге. В начале выполнения функции Adler-32 '''А''' инициализируется единицей, а '''Б''' — нулём. Суммы берутся по модулю 65521 (самое большое простое число, меньшее, чем 2<sup>16</sup>). Байты записываются в [[Сетевой порядок байт|сетевом порядке]], '''Б''' занимает 2 старших байта.

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

  ''A'' = 1 + ''D''<sub>1</sub> + ''D''<sub>2</sub> + ... + ''D''<sub>''n''</sub> (mod 65521)
  ''B'' = (1 + ''D''<sub>1</sub>) + (1 + ''D''<sub>1</sub> + ''D''<sub>2</sub>) + ... + (1 + ''D''<sub>1</sub> + ''D''<sub>2</sub> + ... + ''D''<sub>''n''</sub>) (mod 65521)
    = ''n''&times;''D''<sub>1</sub> + (''n''-1)&times;''D''<sub>2</sub> + (''n''-2)&times;''D''<sub>3</sub> + ... + ''D''<sub>''n''</sub> + ''n'' (mod 65521)
 
  ''Adler-32''(''D'') = ''B'' &times; 65536 + ''A''
где D — строка байт, для которых должна быть вычислена контрольная сумма, а n — длина D.

== Пример ==
Значение Adler-32 для ASCII строки «Wikipedia» вычисляется следующим образом:
    ASCII code          A                   B
    <small>(в десятиричном виде)</small>
    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 [[hexadecimal|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<sup>4</sup>=16 и 2<sup>8</sup>=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<sup>−5</sup>.
[[Файл:Probability of undetected error fletcher adler comparison.jpg|thumbnail|300px| '''Рисунок1''' Вероятность необнаруженных ошибок для контрольных сумм Adler и Fletcher для частоты битовых ошибок 10<sup>−5</sup>.]]
Лучшее перемешивание бит, которое обеспечивает контрольная сумма Adler, должно было привести к лучшим показателям поиска ошибок, чем у суммы Fletcher. Но, как показывает RFC 3385, Fletcher-32 работает лучше, чем Adler-32 на 8 KB. Контрольная сумма Adler превосходит сумму Fletcher только в случае 16-битных контрольных сумм, и при этом только в той области этих сумм, где [[расстояние Хэмминга]] равно 3. Проблема в том, что, несмотря на то, что простое число, использованное в качестве модуля операции, приводит к лучшему перемешиванию бит, в результате получается меньшее количество правильных значений проверочных контрольных сумм, доступных для кодовых слов. В большинстве случаев это сводит на нет положительный эффект лучшего перемешивания. Таким образом, контрольная сумма Fletcher превосходит сумму Adler во всех случаях, кроме суммы Adler-16, применяемой к коротким словам данных. Даже увеличение эффективности поиска ошибок, возможно, не стоит увеличения вычислительных накладных расходов, к которым приводит использование модульных операций.

== Сравнение с другими контрольными суммами ==
Авторы RFC 3385 провели сравнение эффективности обнаружения ошибок. Свод полученных ими результатов представлен в таблице:<br>
{| class="wikitable" border="1"
|-
! Алгоритм
! d
! Block
! i/byte
! T<sub>size</sub>
! T-look
! P<sub>udb</sub>
! P<sub>uds</sub>
|-
| Adler-32
| 3
| 2<sup>19</sup>
| 3
| -
| -
| 10<sup>−36</sup>
| 10<sup>−35</sup>
|-
| Fletcher-32
| 3
| 2<sup>19</sup>
| 2
| -
| -
| 10<sup>−37</sup>
| 10<sup>−36</sup>
|-
| IEEE-802
| 3
| 2<sup>16</sup>
| 2.75
| 2<sup>18</sup>
| 0.5/b
| 10<sup>−41</sup>
| 10<sup>−40</sup>
|-
| CRC32C
| 3
| 2<sup>31</sup>−1
| 2.75
| 2<sup>18</sup>
| 0.5/b
| 10<sup>−41</sup>
| 10<sup>−40</sup>

|}<br>
В таблице: d — минимальное расстояние на блоке длины Block, Block — длина блока в битах, i/byte — количество программных инструкций, приходящихся на байт, T<sub>size</sub> — размер таблицы (в случае, если необходим просмотр), T-look — число просмотров на байт, P<sub>udb</sub> — вероятность необнаруженных групповых ошибок, P<sub>uds</sub> — вероятность необнаруженных единичных ошибок.<br>
Вероятности необнаруженных ошибок в таблице, приведённой выше, вычислены в предположении равномерной распределённости данных.

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

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

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

== Пример реализации на языке C ==
Простой реализацией алгоритма на [[Си (язык программирования)|языке Си]] является следующий код:
<source lang="c">
uint32_t adler32( const unsigned char* buf, size_t buf_length )
{
    uint32_t s1 = 1;
    uint32_t s2 = 0;
  
    while( buf_length-- )
    {
        s1 = ( s1 + *( buf++ ) ) % 65521;
        s2 = ( s2 + s1 ) % 65521;
    }
    return ( s2 << 16 ) + s1;
 }
</source>
Эффективную реализацию смотрите в коде библиотеки [[zlib]].

== Adler-32 в других языках программирования ==
* В [[Java]] существует класс java.util.zip.Adler32, реализующий алгоритм.<ref>{{Cite web |url=https://docs.oracle.com/javase/8/docs/api/java/util/zip/Adler32.html |title=Adler32 (Java Platform SE 8) |access-date=2015-12-24 |archive-date=2015-12-25 |archive-url=https://web.archive.org/web/20151225051144/https://docs.oracle.com/javase/8/docs/api/java/util/zip/Adler32.html |deadlink=no }}</ref>
* В стандартной библиотеке [[D (язык программирования)|D]], [https://dlang.org/phobos/std_zlib.html#.adler32 std.zlib : adler32]

* В [[Perl]] существует Digest::Adler32, см. [[CPAN]].<ref>{{Cite web |url=https://metacpan.org/pod/Digest::Adler32 |title=Digest::Adler32 на CPAN |access-date=2014-01-12 |archive-date=2014-01-12 |archive-url=https://web.archive.org/web/20140112215836/https://metacpan.org/pod/Digest::Adler32 |deadlink=no }}</ref>
* Частная реализация для [[Python]].<ref>[http://snippets.dzone.com/user/mcandre/tag/Adler32 Adler32 code<!-- Заголовок добавлен ботом -->] {{Wayback|url=http://snippets.dzone.com/user/mcandre/tag/Adler32 |date=20071104050611 }} {{webarchive|url=https://web.archive.org/web/20071104050611/http://snippets.dzone.com/user/mcandre/tag/Adler32 |date=2007-11-04 }}</ref>
* В PHP доступна через функцию [http://ru.php.net/manual/en/function.hash.php hash()]
* Для [[Erlang]] доступны несколько встроенных функций (BIF) [http://www.erlang.org/doc/man/erlang.html adler32(…)]
* Для [[Go (язык программирования)|Go]] доступна в стандартной библиотеке [http://golang.org/pkg/hash/adler32/ «hash/adler32»]

== Примечания ==
{{примечания}}

== Литература ==
* {{статья|автор=Theresa C. Maxino, Philip J. Koopman|заглавие=The Effectiveness of Checksums for Embedded Control Networks|ссылка=http://www.ece.cmu.edu/~koopman/pubs/maxino09_checksums.pdf|издание=IEEE Trans. on Dependable and Secure Computing|год=2009|страницы=59—72}}
* {{статья|автор=Theresa Maxino|заглавие=Revisiting Fletcher and Adler Checksums|ссылка=http://www.zlib.net/maxino06_fletcher-adler.pdf|издание=DSN 2006 Student Forum|год=2006}}

{{Хеш-алгоритмы}}