Adler-32 is a
checksum algorithmwhich was invented by Mark Adler. Compared to a cyclic redundancy checkof the same length it trades reliability for speed. Compared to its original form (Fletcher-16), Adler-32 is more reliable than Fletcher-16. However, Adler-32 is slightly less reliable than Fletcher-32 [ [http://www.zlib.net/maxino06_fletcher-adler.pdf Revisiting Fletcher and Adler Checksums] ]
It is a modification of the Fletcher checksum.
The Adler-32 checksum is part of the widely-used
zlibcompression library, as both were developed by Mark Adler.A " rolling checksum" version of Adler-32 is used in the rsyncutility.
An Adler-32 checksum is obtained by calculating two
16-bitchecksums "A" and "B" and concatenating their bits into a 32-bit integer. "A" is the sum of all bytes in the string 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 modulo 65521 (the largest
prime numbersmaller 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 + "D"1 + "D"2 + ... + "D""n" (mod 65521) "B" = (1 + "D"1) + (1 + "D"1 + "D"2) + ... + (1 + "D"1 + "D"2 + ... + "D""n") (mod 65521) = "n"×"D"1 + ("n"-1)×"D"2 + ("n"-2)×"D"3 + ... + "D""n" + "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".
The Adler-32 sum of the
Wikipedia" would be calculated as follows: 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
(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 24-1, 28-1, or 216-1 (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.
The second difference, which has the largest effect on the speed of the algorithm, is that the Adler sums are computed over 8-bit
bytes rather than 16-bit 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 properly implemented (e.g., one found in the Hierarchical_Data_Format) Fletcher's checksum.
An optimized implementation in the C programming language operates as follows:
A few tricks are used here for efficiency:
* Most importantly, by using larger (32-bit) temporary sums, it is possible to sum a great deal of data before needing to reduce modulo 65521. The requirement is that the reduction modulo 65521 must be performed before the sums overflow, which would cause an implicit reduction modulo 232 = 4294967296 and corrupt the computation.
* The magic value 5552 is the largest number of sums that can be performed without overflowing
b. Any smaller value is also permissible; 4096 may be convenient in some cases.
Advantages and disadvantages
* Warning: Like the standard
CRC-32, the Adler-32 checksum can be forged easily and is therefore unsafe for protecting against "intentional" modification.
* It has the benefit over a CRC that it can be computed faster in
* Adler-32 has a weakness for short messages with few hundred bytes, because the checksums for these messages have a poor coverage of the 32 available bits.
Jonathan Stone discovered in 2001 that Adler-32 has a weakness for very short messages. He wrote "Briefly, the problem is that, for very short packets, Adler32 is guaranteed to give poor coverage of the available bits. Don't take my word for it, ask Mark Adler. :-)" The problem is that sum "A" does not wrap for short messages. The maximum value of "A" for a 128-byte message is 32640, which is below the value 65521 used by the modulo operation. An extended explanation can be found in RFC 3309, which mandates the use of
CRC32instead of Adler-32 for SCTP, the Stream Control Transmission Protocol.
List of hash functions
* RFC 1950 - specification, contains example C code
* [http://www.zlib.org ZLib] - implements the Adler-32 checksum
* [http://textop.us/Hashing/Adler-32 Calculate Adler-32 checksum online]
* RFC 3309 - information about the short message weakness and related change to SCTP
* [http://ieeexplore.ieee.org/iel5/8858/4358699/04358707.pdf?arnumber=4358707 Maxino & Koopman] - compares Adler, Fletcher, and CRC checksums
Wikimedia Foundation. 2010.
См. также в других словарях:
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-32 — Adler 32 хеш функция, разработанная Марком Адлером (англ.). Является модификацией контрольной суммы Fletcher (англ.). Вычисляет значение контрольной суммы в соответствии с RFC 1950 для массива байт или его фрагмента. Данный… … Википедия
Adler — Adler … Википедия
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