www.Manuel-Einfalt.de

Das DEFLATE-Datenformat
Auch wenn Datenkompression in den letzten Jahren an Bedeutung verloren hat, sind Datenformate wie zum Beispiel ZIP oder GZIP (in Kombination mit TAR) immer noch sehr beliebte Containerformate, die bei der Archivierung von Dateien zum Einsatz kommen. Auch beim Versand von großen Dateien per Email wird häufig noch komprimiert, da einige Email-Provider eine Obergrenze bei der Größe der Anhänge festgelegt haben.
Die Kompression von Daten im ZIP- bzw. GZIP- Format wird mit dem Deflate-Datenformat (eine Mischung aus Huffman-Codierung und Lempel-Ziv Algorithmus) erzielt. Eine ausführliche Spezifikation des Formats gibt es im RFC1951.

Da diese Spezifikation sehr theoretisch ist, möchte ich hier ein übersichtliches Beispielprogramm in C++ anbieten, welches die Eigentümlichkeiten vom Deflate-Datenformat nachvollziehbar macht. Das Programm entpackt eine GZIP-Datei (das GZIP-Format ist im Vergleich zum ZIP-Format einfacher aufgebaut und der Code bleibt hierdurch übersichtlicher). Ich habe mich bemüht, die "Vokabeln" des RFC1951 weitestgehend zu übernehmen (BFINAL, BTYPE, ...), sodass möglichst offensichtlich ist, was die einzelnen Zeilen des Codes bewirken. Zuletzt bleibt noch zu sagen, dass ich bei diesem Programm keineswegs Wert auf Laufzeit-Effizienz gelegt habe, denn dieser Code macht Gebrauch von abstrakten Datentypen in Form von Klassen. Dies sollte die Lesbarkeit um einiges verbessern. Für eine effizientere Laufzeit sorgt eine hardwarenähere Programmierung, die sich mit einfachen Mitteln erreichen lässt, aber für kryptischen Code sorgen sollte.

Download Beispielcode

Beispiel einer Textdatei, die mit DEFLATE gepackt wurde

Nun betrachten wir die verschiedenen Bestandteile einer GZIP-Datei (diese gibt es in binärer Form hier als Download). Hier wurden 44 Byte ASCII-Text in zwei DEFLATE-Blöcke (BTYPE 00 = keine Kompression und BTYPE 01 = Kompression mit fixed huffman codes) gepackt. Der aufmerksame Leser wird bemerken, dass die gepackte Datei 52 Byte groß, und somit größer als die Originaldatei, ist. Der Grund dafür ist, dass ich für dieses Beispiel die Datei in 2 Deflate-Blöcke aufgeteilt habe. Für einen GZIP-Compressor wäre dies absolut unüblich, da diese Datei am besten mit einem einzigen DEFLATE-Block (BTYPE 01) komprimiert wäre.
Dieses etwas künstlichere Beispiel habe ich konstruiert, damit der Fall nicht zu trivial ist.

00000000  1f 8b 08 00 01 00 00 00  00 03 00 16 00 e9 ff 64  |.............éÿd|
00000010  69 65 73 20 69 73 74 20  64 65 72 20 31 2e 20 62  |ies ist der 1. b|
00000020  6c 6f 63 6b 0a 43 11 35  82 89 02 00 3a 96 da f1  |lock.C.5....:.Úñ|
00000030  2c 00 00 00                                       |,...|
00000034

Nun zum Inhalt der Datei:
Die ersten 10 Byte und die letzten 8 Byte sind Bestandteil des GZIP-Dateiformats. Für weiterführende Informationen hierzu siehe RFC1952 (2.3. Member format)

Richten wir unsere Aufmerksamkeit auf den ersten Datenblock:

00000000  1f 8b 08 00 01 00 00 00  00 03 00 16 00 e9 ff 64  |.............éÿd|
00000010  69 65 73 20 69 73 74 20  64 65 72 20 31 2e 20 62  |ies ist der 1. b|
00000020  6c 6f 63 6b 0a 43 11 35  82 89 02 00 3a 96 da f1  |lock.C.5....:.Úñ|
00000030  2c 00 00 00                                       |,...|
00000034

Die hier markierten Bytes sind ein nichtkomprimierter Datenblock. Folgende Bedeutung haben die einzelnen Bytefelder:

00: Dieses Byte enthält ein Bit BFINAL=0 und zwei Bit BTYPE=00, d.h. der Block ist nicht der letzte Block des Datenstroms und ist unkomprimiert. Die restlichen 5 Bit dieses Bytes bleiben ungenutzt, da die Daten eines unkomprimierten Datenblocks immer eine ganzzahlige Menge Bytes belegen. Um das zu gewährleisten, werden in dem Byte, welches die Header-Informationen enthält, Padding-Bits eingefügt.

16 00: 0x0016 = 22 Dezimal, gibt die Anzahl der Bytes im Datenblock an.

e9 ff: 0xffe9 = 0x0016^0xffff (siehe Definition nlen)

Der zweite Block liegt in komprimierter Form vor:

00000000  1f 8b 08 00 01 00 00 00  00 03 00 16 00 e9 ff 64  |.............éÿd|
00000010  69 65 73 20 69 73 74 20  64 65 72 20 31 2e 20 62  |ies ist der 1. b|
00000020  6c 6f 63 6b 0a 43 11 35  82 89 02 00 3a 96 da f1  |lock.C.5....:.Úñ|
00000030  2c 00 00 00                                       |,...|
00000034

Beim komprimierten Block ist es nun hilfreich, die Bytes von rechts nach links der Reihe nach aufzuschreiben (also umgekehrt zur derzeitigen Reihenfolge, siehe hierzu RFC1951: 3.1.1. Packing into bytes):

	00 02 89 82 35 11 43

und dann jedes einzelne Byte binär darzustellen:

	0000 0000 0000 0010 1000 1001 1000 0010 0011 0101 0001 0001 0100 0011

Nun lesen wir die farblich voneinander getrennten Bitfelder von rechts nach links. Es ist dabei darauf zu achten, dass Huffman-Codes (also literal/length und distance Codes) "MSB-to-LSB" im Datenstrom platziert sind, d.h. das MSB steht entgegen der üblichen Notation rechts.

1: BFINAL=1 (letzter Block im Datenstrom)

01: BTYPE=01 (=1 dezimal, d.h. fixed huffman)

01 0100 0: Code 266, (length=13,14)

0: Extrabit ==> Länge: 13

0001 0: Code 8, (distance=17-24)

101: Extrabits ==> Distanz: 22

010 0011 0: Code 50 (ASCII: '2')

01 1000 0: Code 262 (length=8)

000 10: Code 8, (distance=17-24)

10 1: Extrabits ==> Distanz: 22

0 0000 00: Code 256: EOF

0000 000: 7 Bits ungenutzt, Deflate-Blöcke werden im GZIP-Format immer zu ganzzahligen Bytes aufgefüllt.

Spätestens nach dieser detaillierten Untersuchung eines komprimierten Datenblocks mit fixed Huffman Codes sollte klar sein, warum ich keinen Datenblock mit dynamic Huffman Codes in dieses Beispiel eingefügt habe. Dies bleibt dem interessierten Leser als Übung überlassen.