Versuchen, zlib/deflate in PNG-Dateien zu verstehen

Question

Ich bin gerade dabei, eine kleine PNG-Bild-I/O-Bibliothek selbst zu Lernzwecken zu schreiben. Mein Problem ist folgendes:

Ich erstellte ein kleines PNG nur 2 mal 2 Pixel in der Dimension und öffnete es in einem Hex-Editor, um seinen Inhalt zu studieren. Dies ist das Bild, das ich mit GIMP erstellt und mit einer Komprimierung von "9" gespeichert habe.

(Bitte beachten Sie, dass dies ein vergrößertes Bild des Original 2 von 2 Pixelbild ist;))

So unkomprimiert Ich denke, dies so etwas wie dies in Erinnerung aussehen würde:

00 00 00 FF 00 00 00 00 FF 00 FF 00 

wenn ohne Alphakanal gespeichert wird.

(Ich habe dies hier nur zur Verdeutlichung angegeben. Ich kenne die Komprimierung und habe nicht erwartet, dieses Byte-Muster in der Datei zu sehen).

I extrahiert, um das IDAT Chunk und gestrippt, um das ID chunk ("IDAT") und der rückstand CRC-Wert und erhielt diese Folge von Bytes:

08 D7 05 C1 01 01 00 00 00 80 10 FF 4F 17 10 48 06 0F FE 02 FE 

Nun sind die ersten beiden Bytes 08 D7 Informationen über den kodierten Block enthalten . Und die letzten vier Bytes 0F FE 02 FE müssen die ADLER32 Prüfsumme sein.

mich Dies lässt schließlich mit den folgenden Bytes:

05 C1 01 01 00 00 00 80 10 FF 4F 17 10 48 06 

in Binärdarstellung Geschrieben diese Bytes sind:

0000 0101 1100 0001 0000 0001 0000 0001 
0000 0000 0000 0000 0000 0000 1000 0000 
0001 0000 1111 1111 0100 1111 0001 0111 
0001 0000 0100 1000 0000 0110 

Um zu verstehen, DEFLATE besser habe ich versucht, diese Sequenz von Hand zu "entpacken" auf zumindest bevor ich es gut genug verstehe, um ein kleines Werkzeug zu schreiben. Aber ich bin wirklich schnell steckengeblieben.

RFC 1951 ("DEFLATE Compressed Data Format Specification") besagt, dass jeder codierte Block mit einem Drei-Bit-Header beginnt. Ein Bit zeigt an, ob dies der letzte Block ist oder nicht und zwei weitere Blöcke zeigen die Komprimierungsmethode an. Da ich davon ausgehe, dass der Encoder hier nur einen Block verwendet (dh der erste Block ist automatisch der letzte) und einen nicht statischen Huffmann-Baum verwendet, suche ich nach der Bitfolge "101", kann sie aber nicht finden Header "100" oder "110").

Auch der RFC besagt, dass es zwei zwei Byte-Werte LEN und NLEN geben muss, die die Länge des Blocks speichern, wo NLEN das Einerkomplement von LEN ist, aber ich bin nicht in der Lage, vier solche Bytes zu finden, die diese Bedingung erfüllen. Ich werde nicht einmal von meinem Glück anfangen, etwas zu finden, das die beiden Huffmann-Bäume repräsentieren könnte.

las ich RFCs 1951 und 1950 ("ZLIB Compressed Data Format Specification" sowie den Wikipedia-Artikel auf zlib, DEFLATE, LZ77 und Huffman-Kodierung sowie mehrere kleine und wenig hilfreich Artikel im Internet und ein paar Antworten auf Stack-Überlauf, aber keine helfen könnte mich mit meinem Unverständnis.

ich würde für jede Hilfe oder Hinweis wirklich dankbar!

Answer 1

ich glaube, Sie fehlen, wie die Bits innerhalb Bytes gepackt sind (siehe zB Abschnitt 3.1.1 von RFC)

Data elements are packed into bytes in order of 
increasing bit number within the byte, i.e., starting 
with the least-significant bit of the byte. 

Wenn also das erste Byte 05 = 0000 0101 das erste Bit ist 1.

(BTW, es ist sicherlich ganz lehr Dinge zu sehen, so viele Details, aber ich frage mich, Wenn Sie nicht zu weit gehen, wenn Sie PNG verstehen wollen.

Wenn Sie zu dem Punkt kommen, an dem Sie den unkomprimierten IDAT-Stream finden, beachten Sie, dass die Pixel mit einem von fünf codiert sind filters pro Zeile, und dass am Anfang jeder Zeile ein zusätzliches Byte steht, das den Filtertyp signalisiert. Sie werden also nicht wirklich die rohen 12 Bytes 00 00 00 FF 00 00 00 00 FF 00 FF 00 finden, sondern stattdessen 12 + 2 = 14 Bytes.

Answer 2

Falls dies hilft, hier ist eine Demontage der IDAT Chunk Inhalt:

! infgen 2.2 output 
! 
zlib 
! 
last 
dynamic 
count 257 2 18 
code 1 1 
code 2 2 
code 18 2 
lens 1 
zeros 138 
zeros 116 
lens 2 2 1 1 
! litlen 0 1 
! litlen 255 2 
! litlen 256 2 
! dist 0 1 
! dist 1 1 
literal 0 0 0 0 255 0 0 0 0 0 255 0 255 0 
end 
! 
adler 

können Sie erhalten die infgen Quellcode here.