Adler 32

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 beschrieben.

Der Adler-32-Algorithmus ist einfacher und lässt sich schneller berechnen als die bekannte Zyklische Redundanzprüfung (cyclic redundancy check), bietet aber auch weniger Sicherheit beim Erkennen von zufälligen Bitfehlern.

Algorithmus

Der Algorithmus berechnet zwei Summen s1 und s2. s1 ist die Summe aller Datenbytes und wird am Anfang des Algorithmus auf 1 initialisiert, s2 ist die Summe aller s1-Werte. Beide Summen werden modulo 65.521 (die größte Primzahl < 216) berechnet.

Obwohl der Algorithmus sehr einfach ist, sei hier eine Beispielimplementierung in C angegeben:

  /* Beispielcode zur Berechnung der Adler-32-Prüfsumme */
 
  uint32_t adler32(const void *buf, size_t buflength) {
 
     const uint8_t *buffer = (const uint8_t*)buf;
 
     uint32_t s1 = 1;
     uint32_t s2 = 0;
 
     for (size_t n = 0; n < buflength; n++) {
        s1 = (s1 + buffer[n]) % 65521;
        s2 = (s2 + s1) % 65521;
     }
 
     return (s2 << 16) | s1;
  }

Anmerkung Beispielimplementierung

Diese Beispielimplementierung ist nicht auf Geschwindigkeit, sondern auf Klarheit und Lesbarkeit hin optimiert. So muss etwa die recht langsame Modulo-Operation nicht bei jedem Datenbyte durchgeführt werden, sondern nur, wenn ein Überlauf der Variablen s1 oder s2 droht. Bei einer Bitbreite von 32 Bit (was bei der Verwendung von int nicht gewährleistet ist, daher oben uint32_t gemäß C99) genügt eine Durchführung der Modulo-Operation alle 5552 Bytes. Bei 64 Bit (uint64_t) breiten s1 und s2 würde sogar die Durchführung der Modulo-Operation alle 380.368.439 Bytes genügen, wodurch aber keine merkliche Geschwindigkeitsverbesserung erzielt werden kann. Näheres siehe Restklassenring.

Die hohe Anzahl der Sprünge verringert bei Prozessoren mit Pipeline die effektive Ausnutzung der quasi parallelen Ausführung einzelner Befehle. Es empfiehlt sich daher die einzelnen Daten in maximal 5552 Byte große Teilblöcke zu zerlegen, nach denen erst eine Modulo-Operation ausgeführt wird. Diese Blöcke sollten wiederum in 16 Byte große Untereinheiten zerlegt werden, die in einem Schleifendurchlauf zusammengerechnet werden. Durch dieses sogenannte Loop-Unrolling lässt sich in etwa 25–30 % Geschwindigkeitszuwachs auf modernen Prozessoren bei genügend großen Daten erzeugen.

Schwächen von Adler-32

Ein optimaler Prüfsummenalgorithmus erzeugt eine Prüfsumme, die möglichst gleichverteilt über ihren Wertebereich ist. Dies ist bei Adler-32 für kurze Datenfolgen (< 128 Byte) nicht gegeben, da der Wert für s1 nicht überläuft.

Durch die einfache arithmetische Struktur von Adler-32 kommt es zudem zu vielen Kollisionen, insbesondere auch bei ähnlichen Eingabewerten. Wird beispielsweise Byte n der Eingabe um k erhöht, Byte n+1 um 2×k erniedrigt und Byte n+2 um k erhöht, bleiben sowohl s1 (die Summe aller Bytes), als auch s2 (die Summe aller Zwischenwerte von s1) unverändert. Dieses gilt für beliebige Positionen n in der Eingabe, und alle positiven oder negativen Werte von k, soweit die betrachteten Bytes nicht überlaufen. Im Ergebnis kann die 32-Bit-Prüfsumme Adler-32 noch nicht einmal eine 24-Bit-Eingabe zuverlässig absichern.

Lediglich einfache und doppelte Bitfehler werden zuverlässig erkannt, und zwar durch die Summen s1 beziehungsweise s2. Treten jedoch Bursts von drei oder mehr Bitfehlern auf, wie im obigen Beispiel, ist eine sichere Erkennung nicht gewährleistet.

Aus diesem Grunde wurde unter anderem in der Implementierung des Stream Control Transmission Protocols der verwendete Prüfsummenalgorithmus Adler-32 durch CRC-32 ersetzt, da hier recht oft nur kurze Datenströme benutzt werden und die Schwäche von Adler-32 zutage tritt.

Auch ist es verhältnismäßig leicht, durch beabsichtigte Modifikation einen Datenstrom mit gleicher Prüfsumme zu erzeugen. Deshalb kann Adler-32 die Integrität der Daten nicht garantieren. Wenn eine solche Sicherheit gefordert ist, müssen kryptografische Hash-Funktionen wie beispielsweise SHA zum Einsatz kommen.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Adler-32 — Adler 32  хеш функция, разработанная Марком Адлером (англ.). Является модификацией контрольной суммы Fletcher (англ.). Вычисляет значение контрольной суммы в соответствии с RFC 1950 для массива байт или его фрагмента. Данный… …   Википедия

  • Adler-32 — is a checksum algorithm which was invented by Mark Adler. Compared to a cyclic redundancy check of the same length it trades reliability for speed. Compared to its original form (Fletcher 16), Adler 32 is more reliable than Fletcher 16. However,… …   Wikipedia

  • 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

  • Adler-32 — est une fonction de hashage inventée par Mark Adler et dérivée de la fonction de Fletcher. Sommaire 1 Caractéristiques 2 Algorithme[2] 2.1 Optimisation …   Wikipédia en Français

  • Adler — The term Adler, the German word for the bird of prey eagle , is both the last name of many people and an emblematic bird (notably in heraldry, bannistics, numismatics etc.) featured on many blazons since the feudal age, including the present… …   Wikipedia

  • Adler's Appetite — Also known as Suki Jones Origin Los Angeles, California, U.S. Genres Heavy metal[1] Years active …   Wikipedia

  • Adler (Fluss) — Zusammenfluss von Adler und Elbe in Hradec KrálovéVorlage:Infobox Fluss/KARTE fehlt …   Deutsch Wikipedia

  • Adler (Lokomotive) — Adler Nummerierung: 118 (Fabriknummer des Herstellers) Anzahl: 1 Hersteller: Robert Stephenson Co., Newcastle …   Deutsch Wikipedia

  • Adler Mannheim — Größte Erfolge Deutscher Meister 1980, 1997, 1998, 1999, 2001, 2007 Deutscher Vizemeister 1982, 1983, 1985, 1987, 2002, 2005 Deutscher Pokalsieger 2003, 2007 Deutscher Vizepokalsieger 2006 …   Deutsch Wikipedia

  • Adler Trumpf 1,7 EV — Adler Trumpf 1,7 Liter AV Cabriolet (1935) Adler Trumpf 1,7 Liter Cabriolet (1934) …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”