From TheBestLinks.com
Adler-32 is a checksum algorithm which was invented by Mark Adler. It is almost as reliable as a 32-bit cyclic redundancy check for protecting against accidental modification of data, such as distortions occurring during a transmission, but can be forged easily and is therefore unsafe for protecting against intentional modification. It has the benefit over CRC:s that it can be computed faster. It is a modification of the Fletcher checksum, which in its original form is slightly faster but less reliable.
The algorithm
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 bytes in the string, 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 modulo 65521 (the largest prime number smaller than 216). The bytes are stored in network order (big endian), B occupying the two most significant bytes.
The function may be expressed as
A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + 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 Wikipedia would be calculated as follows:
ASCII code A B
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
B = 4582 = 11E6 hex
Output: 11E60398 hex
Note that the modulo operation was left out in this demonstration since none of the values reached 65521.
Comparison with the Fletcher checksum
The difference between the two algorithms is that Adler-32 sums are calculated modulo a prime number, whereas Fletcher sums are calculated modulo 24, 28, or 216 (depending on the number of bits used), which are all composite numbers. Using a prime number makes it possible for Adler-32 to catch differences in certain combinations of bytes that Fletcher is unable to detect.
Fletcher is faster for this reason; the operation X modulo 2n is equal to extracting the n least significant bits of X (or calculating X (binary and) 2n-1). This is possible in a single step on almost any processor, whereas calculating X modulo 65521 requires time-consuming integer division.
External links
- RFC 1950 (http://www.faqs.org/rfcs/rfc1950.html) - specification, contains example C code
- ZLib (http://www.zlib.org) - implements the Adler-32 checksum
Related links
Top visited
0 of
0 links
[no links posted yet]
>> place link >>
Discussion
Last posted
0 of
0 messages
[no messages posted yet]
>> post message >>
Watch
You can
add this article to your own "watchlist" and receive e-mail notification about all changes in this page.
