View source for Adler-32

{{Short description|Computer checksum algorithm}}
'''Adler-32''' is a [[checksum]] [[algorithm]] written by [[Mark Adler]] in 1995,<ref>{{Cite web|url=http://zlib.net/fossils/zlib-0.71.tar.gz|title=First appearance of Adler-32 (see ChangeLog and adler32.c)}}</ref> modifying [[Fletcher's checksum]]. Compared to a [[cyclic redundancy check]] of the same length, it trades reliability for speed. Adler-32 is more reliable than [[Fletcher-16]], and slightly less reliable than [[Fletcher-32]].<ref>{{Cite web|url=http://www.zlib.net/maxino06_fletcher-adler.pdf|title=Revisiting Fletcher and Adler Checksums}}</ref>

== History ==

The Adler-32 checksum is part of the widely used [[zlib]] compression library, as both were developed by [[Mark Adler]].
A "[[rolling checksum]]" version of Adler-32 is used in the [[rsync]] utility.

== Calculation ==
An Adler-32 checksum is obtained by calculating two [[16-bit]] checksums ''A'' and ''B'' and concatenating their bits into a 32-bit integer. ''A'' is the sum of all [[byte]]s in the stream plus one, and ''B'' is the sum of the individual values of ''A'' from each step.

At the beginning of an Adler-32 run, ''A'' is initialized to 1, ''B'' to 0. The sums are done [[modular arithmetic|modulo]] 65521 (the largest [[prime number]] smaller than 2<sup>16</sup>). The bytes are stored in network order ([[endianness|big endian]]), ''B'' occupying the two most significant bytes.

The function may be expressed as

 ''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''×''D''<sub>1</sub> + (''n''−1)×''D''<sub>2</sub> + (''n''−2)×''D''<sub>3</sub> + ... + ''D''<sub>''n''</sub> + ''n'' (mod 65521)
 
 ''Adler-32''(''D'') = ''B'' × 65536 + ''A''

where ''D'' is the string of bytes for which the checksum is to be calculated, and ''n'' is the length of ''D''.

==Example==
The Adler-32 sum of the [[ASCII]] string "<code>Wikipedia</code>" would be calculated as follows:
{| class="wikitable" border="1"
|-
!Character
!ASCII code
!
! colspan="3" | A
!
! colspan="3" | B
|-
| colspan="12" | <small>(shown as base 10)</small>
|-
|   W
| style="text-align: right" |87  || 
| style="text-align: right; border-right: hidden" |    1 +
| style="text-align: right; border-right: hidden" |  87 =
| style="text-align: right" |  88 || 
| style="text-align: right; border-right: hidden" |    0 +
| style="text-align: right; border-right: hidden" |  88 =
| style="text-align: right" |   88
|-
|   i
| style="text-align: right" |105 || 
| style="text-align: right; border-right: hidden" |   88 +
| style="text-align: right; border-right: hidden" | 105 =
| style="text-align: right" | 193 || 
| style="text-align: right; border-right: hidden" |   88 +
| style="text-align: right; border-right: hidden" | 193 =
| style="text-align: right" |  281
|-
|   k
| style="text-align: right" |107 || 
| style="text-align: right; border-right: hidden" |  193 +
| style="text-align: right; border-right: hidden" | 107 =
| style="text-align: right" | 300 || 
| style="text-align: right; border-right: hidden" |  281 +
| style="text-align: right; border-right: hidden" | 300 =
| style="text-align: right" |  581
|-
|   i
| style="text-align: right" |105 || 
| style="text-align: right; border-right: hidden" |  300 +
| style="text-align: right; border-right: hidden" | 105 =
| style="text-align: right" | 405 || 
| style="text-align: right; border-right: hidden" |  581 +
| style="text-align: right; border-right: hidden" | 405 =
| style="text-align: right" |  986
|-
|   p
| style="text-align: right" |112 || 
| style="text-align: right; border-right: hidden" |  405 +
| style="text-align: right; border-right: hidden" | 112 =
| style="text-align: right" | 517 || 
| style="text-align: right; border-right: hidden" |  986 +
| style="text-align: right; border-right: hidden" | 517 =
| style="text-align: right" | 1503
|-
|   e
| style="text-align: right" |101 || 
| style="text-align: right; border-right: hidden" |  517 +
| style="text-align: right; border-right: hidden" | 101 =
| style="text-align: right" | 618 || 
| style="text-align: right; border-right: hidden" | 1503 +
| style="text-align: right; border-right: hidden" | 618 =
| style="text-align: right" | 2121
|-
|   d
| style="text-align: right" |100 || 
| style="text-align: right; border-right: hidden" |  618 +
| style="text-align: right; border-right: hidden" | 100 =
| style="text-align: right" | 718 || 
| style="text-align: right; border-right: hidden" | 2121 +
| style="text-align: right; border-right: hidden" | 718 =
| style="text-align: right" | 2839
|-
|   i
| style="text-align: right" |105 || 
| style="text-align: right; border-right: hidden" |  718 +
| style="text-align: right; border-right: hidden" | 105 =
| style="text-align: right" | 823 || 
| style="text-align: right; border-right: hidden" | 2839 +
| style="text-align: right; border-right: hidden" | 823 =
| style="text-align: right" | 3662
|-
|   a
| style="text-align: right" |97  || 
| style="text-align: right; border-right: hidden" |  823 +
| style="text-align: right; border-right: hidden" |  97 =
| style="text-align: right" | 920 || 
| style="text-align: right; border-right: hidden" | 3662 +
| style="text-align: right; border-right: hidden" | 920 =
| style="text-align: right" | 4582
|}
 
 A =  920 =  0x398  (base 16)
 B = 4582 = 0x11E6
 Output = (0x11E6 << 16) + 0x398 = 0x11E60398 = 300286872

The modulo operation had no effect in this example, since none of the values reached 65521.

==Comparison with the Fletcher checksum==

The first difference between the two algorithms is that Adler-32 sums are calculated modulo a prime number, whereas Fletcher sums are calculated modulo 2<sup>4</sup>−1, 2<sup>8</sup>−1, or 2<sup>16</sup>−1 (depending on the number of bits used), which are all [[composite number]]s. Using a prime number makes it possible for Adler-32 to catch differences in certain combinations of bytes that Fletcher is unable to detect.

The second difference, which has the largest effect on the speed of the algorithm, is that the Adler sums are computed over 8-bit [[byte]]s rather than 16-bit [[Word (data type)|words]], resulting in twice the number of loop iterations.  This results in the Adler-32 checksum taking between one-and-a-half to two times as long as Fletcher's checksum for 16-bit word aligned data. For byte-aligned data, Adler-32 is faster than a properly implemented Fletcher's checksum (e.g., one found in the [[Hierarchical Data Format]]).

==Example implementation==
In [[C (programming language)|C]], an inefficient but straightforward implementation is :
<syntaxhighlight lang="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;
}
</syntaxhighlight>
See the [[zlib]] source code for a more efficient implementation that requires a fetch and two additions per byte, with the modulo operations deferred with two remainders computed every several thousand bytes, a technique first discovered for Fletcher checksums in 1988. {{code|js-adler32}} provides a similar optimization, with the addition of a trick that delays computing the "15" in 65536 - 65521 so that modulos become faster: it can be shown that {{code|((a >> 16) * 15 + (a & 65535)) % 65521}} is equivalent to the naive accumulation.<ref>{{cite web |title=adler32.js |url=https://github.com/SheetJS/js-adler32/blob/master/adler32.js |publisher=Sheet JS |date=3 July 2019}}</ref>

== Advantages and disadvantages ==
* Like the standard [[CRC-32]], the Adler-32 checksum can be forged easily and is therefore unsafe for protecting against ''intentional'' modification.
* It's faster than CRC-32 on many platforms.<ref>{{cite journal |author=Theresa C. Maxino, Philip J. Koopman |date=January 2009 |title=The Effectiveness of Checksums for Embedded Control Networks |journal=IEEE Transactions on Dependable and Secure Computing |url=http://www.ece.cmu.edu/~koopman/pubs/maxino09_checksums.pdf }}</ref>
* Adler-32 has a weakness for short messages with a few hundred bytes, because the checksums for these messages have a poor coverage of the 32 available bits.

==Weakness==

Adler-32 is weak for short messages because the sum ''A'' does not wrap. The maximum sum of a 128-byte message is 32640, which is below the value 65521 used by the modulo operation, meaning that roughly half of the output space is unused, and the distribution within the used part is nonuniform. An extended explanation can be found in {{IETF RFC|3309}}, which mandates the use of
[[CRC-32C]] instead of Adler-32 for [[Stream Control Transmission Protocol|SCTP]], the Stream Control Transmission Protocol.<ref>{{IETF RFC|3309}}</ref> Adler-32 has also been shown to be weak for small incremental changes,<ref>{{Cite web|url=https://cbloomrants.blogspot.com/2010/08/08-21-10-adler32.html|title = Cbloom rants: 08-21-10 - Adler32|date = 21 August 2010}}</ref> and also weak for strings generated from a common prefix and consecutive numbers (like auto-generated label names by typical code generators).<ref>{{Cite web|url=https://www.strchr.com/hash_functions|title=Hash functions: An empirical comparison - strchr.com|website=www.strchr.com}}</ref>

==See also ==
* [[List of hash functions]]

==Notes==
{{reflist}}

==External links==
* {{IETF RFC|1950}} – specification, contains example [[C (programming language)|C]] code
* [http://zlib.net ZLib] – implements the Adler-32 checksum in [https://github.com/madler/zlib/blob/v1.2.11/adler32.c adler32.c]
* [https://www.google.com/chrome Chrome] – uses an [[SIMD]] implementation of Adler-32 [https://chromium.googlesource.com/chromium/src/third_party/zlib/+/master/adler32_simd.c adler32_simd.c]
* {{IETF RFC|3309}} – information about the short message weakness and related change to SCTP

[[Category:Checksum algorithms]]