Adler32

Adler32

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 для массива байт или его фрагмента. Данный… …   Википедия

  • FFmpeg — infobox software name = FFmpeg developer = FFmpeg team programming language = C operating system = Cross platform genre = Multimedia framework latest release version = 0.4.9 pre1 latest release date = 2004 07 10 license = GNU Lesser General… …   Wikipedia

  • 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

  • Comparison of archive formats — There are many popular computer data archive formats for creating and maintaining archive files. The tables below compare many popular archive formats. Contents 1 Features 1.1 Purpose 1.2 Filename extension 1 …   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 — 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

Share the article and excerpts

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