AES |
Deflate |
X-Face
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-Optimierung. Dies sollte die Lesbarkeit um einiges verbessern. Für eine effizientere Laufzeit sollte eine hardwarenähere Programmierung bzw. die Verwendung anderer Datentypen sorgen, die sich mit einfachen Mitteln erreichen lässt Dies würde aber kryptischen Code produzieren. Diesen Code habe ich mit dem Ziel geschrieben, den Algorithmus möglichst so zu implementieren, wie er im RFC beschrieben wurde.
Download Beispielcode
Beispiel einer komprimierten Textdatei
1. Unkomprimierte & fixed Code Deflate-Blöcke
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. Selbstverständlich würde keine Software eine solche Datei erzeugen, da es in der Kompression denkbar ineffizient ist, eine Textdatei in zwei Blöcke aufzuteilen, von denen einer dann auch noch unkomprimiert 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.
2. Ein Beispiel mit einem dynamischem Datenblock
Hier (*click*) die Beispieldatei lorem_ipsum.txt.gz
00000000 1f 8b 08 00 54 c7 96 5b 00 03 ed 95 4f 4f db 40 |....T..[....OO.@|
00000010 10 c5 ef fe 14 f3 01 c0 dc b9 a1 b6 ea 05 55 42 |..............UB|
00000020 55 cf d5 66 3d 49 a6 ec 3f f6 0f 01 3e 7d df ac |U..f=I..?...>}..|
00000030 1d 12 28 95 b8 95 22 0e 49 ec 78 3d f3 de 9b 9f |..(...".I.x=....|
00000040 bd 97 31 b3 27 49 a5 79 9a a2 8b 99 8a 54 32 9e |..1.'I.y.....T2.|
00000050 eb 09 d9 18 0a db ca b5 65 32 93 24 29 62 85 d8 |........e2.$)b..|
00000060 09 ae 15 9e 88 a5 15 1f 27 aa ec 13 6e 94 60 65 |........'...n.`e|
00000070 6a a1 52 ab e4 cc 0a 85 89 eb 5c 94 c9 9b 4d 30 |j.R.......\...M0|
00000080 64 9c dc 34 33 d2 8f 4a 1c c4 a3 2a 79 d1 83 5b |d..43..J...*y..[|
00000090 9c 1a 7f 42 37 4d 0a 85 58 6a 6e a8 7f c7 d9 4a |...B7M..Xjn....J|
.... Datenblock nicht vollständig aufgeführt ....
00000310 5b 1e 63 de 9c e9 e9 59 ef fc b3 df 37 0c bf 01 |[.c....Y....7...|
00000320 c4 c2 d7 b7 26 0e 00 00 |....&...|
00000328
Wie im ersten Beispiel schreiben wir nun die ersten Bytes des Deflate-Blocks von rechts nach links auf
40 db 4f 4f 95 ed
42 55 05 ea b6 a1 b9 dc c0 01 f3 14 fe ef c5 10
und untersuchen Diese Werte in binärer Form:
0100 0000 1101 1011 0100 1111 0100 1111 1001 0101 1110 1101
1111 0011 0001 0100 1111 1110 1110 1111 1100 0101 0001 0000
1: BFINAL=1 (dezimal: 1)
10: BTYPE (dezimal 2: dynamic codes)
11101: HLIT (dezimal 29, 29+257=286)
10101: HDIST (dezimal 11, 11+1=12)
1100: HCLEN (dezimal 12, 12+4=16)
Anmerkung: Es werden jetzt HCLEN*3=16*3 Bits eingelsen.
{ 111, 100, 110, 011, 010, 011, 011, 011, 000, 100, 000, 100, 000, 101, 000, 111 }
Insgesamt erhalten wir mit 3.2.7 (Reihenfolge beachten!) aus RFC 1951 ein Codelängen-Array: {3, 0, 7, 5, 4, 4, 3, 3, 2, 3, 0, 0, 0, 0, 0, 0, 7, 4, 6}. Dies sind die Längen, der Codes, die die Zahlen 0 bis 18 kodieren.
Hieraus lassen sich die Binärbäume errzeugen, die zum dekodieren der lit/len- bzw. dist-Binärbäme nötig sind.
Anmerkung: Alle bisher eingelesenen Daten waren Integer-Bitfelder. Aus den zuletzt eingelesenen Codelängen wird nun ein Binärbaum berechnet.
Nach diesen Bitfeldern folgen die komprimierten Codelängen für die binären Bäume. Diese sind kodiert wie die Daten (siehe oben) und sind optional durchmischt mit Integer-Bitfeldern (RFC1951: 3.2.7. Compression with dynamic Huffman codes).
Weil die Löngen der Binärbäume nichts neues liefern, werde ich das hier nicht extra aufschreiben und dafür die Größe der Daten in Bytes aufzählen:
Die unkomprimierte Datei lorem_ipsum.txt ist 3622 Bytes groß. Die Datei lorem_ipsum.txt.gz ist 808 Bytes groß. Damit hat sie weniger Bytes als ein drittel der Originaldatei. Der Inhalt der Datei ist wie folgt zusammengesetzt:
(1) gzip-Format: 18 Byte (siehe RFC 1951)
(2) Bitfelder (BFINAL, BTYPE, HLIT, HDIST, HCLEN, len(1-16): 8 Byte + 1 Bit
(3) Codelängen für den lit-/len-Baum: 7 Bit + 36 Byte + 1 Bit = 37 Byte
(4) Codelängen für den dist-Baum: 7 Bit + 9 Byte
(5) komprimierte Daten: 734 Byte + 1 Bit
(5a) 7 Padding-Bits nach dem EOF des Datenblocks. (der letzte Block muss im gzip-File eine ganzzahlige Menge an Bytes belegen.)
Impressum