Deflate aufblasen

[Leonidas]

Hi,

Ich hatte die letzten Tage überlegt, dass es nett wäre, wenn ich mal DEFLATE (RFC 1951) implementieren würde, also den Algorithmus hinter zlib (RFC 1950) und gzip (RFC 1952) sowie ZIP. Dazu wollte ich erstmal den Dekompressor schreiben, jedoch passt die Spec nicht zu den Testdaten die ich generiert habe.

Also, angenommen diese Daten:

Code: Alles auswählen

printf 'Blah blah blah blah blah!' | openssl zlib -e | xxd
# Python-zlib-Modul geht genauso
00000000: 789c 73ca 49cc 5048 c224 1401 6f19 0875  x.s.I.PH.$..o..u

Den zlib-Header zu parsen Klappt ganz gut, CM = 8 (Deflate) CINFO = 7; FLEVEL = 2 (Default), etc. das Problem ist jetzt, wenn ich versuche den ersten Datenblock zu parsen:

Code: Alles auswählen

3.2.3. Details of block format

         Each block of compressed data begins with 3 header bits
         containing the following data:

            first bit       BFINAL
            next 2 bits     BTYPE

         Note that the header bits do not necessarily begin on a byte
         boundary, since a block does not necessarily occupy an integral
         number of bytes.

         BFINAL is set if and only if this is the last block of the data
         set.

         BTYPE specifies how the data are compressed, as follows:

            00 - no compression
            01 - compressed with fixed Huffman codes
            10 - compressed with dynamic Huffman codes
            11 - reserved (error)

Der zlib-Header ist in meinem Fall 16 Bit (FDICT=0) also ist 0x73 das erste Byte vom ersten Datenblock. Wenn ich mir das jetzt in Binär anzeigen lasse bekomme ich "01110011", was sich auf BFINAL=0 und BTYPE=11 übersetzt. Das würde ein ungültiger Block sein. Aber zlib kann diese Daten problemlos wieder entpacken, also kann es nicht ein Fehler in den Daten sein, sondern in meinem Verständnis. Kann mir jemand aufzeigen, was das eigentlich sein sollte?

Hier noch der Ausschnitt aus der zlib-Beschreibung, die ich als Referenz nutze.

Code: Alles auswählen

   2.2. Data format

      A zlib stream has the following structure:

           0   1
         +---+---+
         |CMF|FLG|   (more-->)
         +---+---+

      (if FLG.FDICT set)

           0   1   2   3
         +---+---+---+---+
         |     DICTID    |   (more-->)
         +---+---+---+---+

         +=====================+---+---+---+---+
         |...compressed data...|    ADLER32    |
         +=====================+---+---+---+---+

[Sirius3]

@Leonidas: das erste Bit ist gesetzt, wegen 3, was BFINAL=1 bedeutet. Die nächsten 2 Bit sind dann 01 also fixed Huffman codes. Es wird also von lo nach hi bits gezählt.

[Leonidas]

Ja, stimmt. Man muss die Bits in einem Byte "rückwährts" lesen, dann funktioniert es auch. Habs inzwischen hinbekommen Fixed Huffman zu parsen, muss jetzt noch dynamischen Huffman rausparsen. Und den Code etwas effizienter machen.