Cercando di comprendere zlib/deflate nei file PNG

Question

Attualmente sono nel mezzo della scrittura di una piccola libreria I/O immagine PNG per scopi di apprendimento. Il mio problema è il seguente:

Ho creato un piccolo PNG solo 2 per 2 pixel in dimensione e l'ho aperto in un editor esadecimale per studiarne il contenuto. Questa è l'immagine che ho creato usando GIMP e memorizzata con una compressione di "9".

(Si prega di notare che questa è un'immagine ingrandita dell'originale 2 immagine 2 pixel per;))

quindi credo che non compresso, questo sarebbe simile a questo in memoria:

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

se memorizzato senza un canale alfa.

(l'ho dichiarato solo qui per chiarezza, so di compressione e non mi aspettavo di vedere questo modello di byte nel file).

ho estratto il pezzo IDAT e spogliato l'ID pezzo ("IDAT") e il valore CRC tailing e ottenuto questa sequenza di byte:

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

Ora i primi due byte 08 D7 contengono informazioni sul blocco codificato . E gli ultimi quattro byte 0F FE 02 FE devono essere il checksum ADLER32.

Questo in ultima analisi, mi lascia con i seguenti byte:

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

Scritto in rappresentazione binaria questi byte sono:

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 

Per comprendere sgonfiare meglio ho cercato di "spacchettare" questa sequenza a mano a Almeno prima che lo capisca abbastanza bene da scrivere un piccolo strumento. Ma mi sono bloccato molto velocemente.

RFC 1951() afferma che ogni blocco codificato inizia con un'intestazione a tre bit. Un bit indica se questo è l'ultimo blocco e altri due blocchi che indicano il metodo di compressione. Dato che presumo che l'encoder abbia usato solo un blocco qui (ovvero che il primo blocco sia automaticamente l'ultimo) e abbia utilizzato un albero Huffmann non statico, sto cercando la sequenza di bit "101" ma non riesco a trovarla (e non trovo altre probabili intestazioni "100" o "110").

Anche la RFC dice che ci devono essere due a due valori di byte LEN e nLen memorizzare la lunghezza del blocco in cui nLen è il complemento a uno dei LEN ma ancora una volta non riesco a trovare quattro di questi byte che soddisfano questa condizione. Non avrò nemmeno la fortuna di trovare qualcosa che possa rappresentare i due alberi di Huffmann.

Ho letto le RFC 1951 e 1950 ("ZLIB Compressed Data Format Specification" nonché gli articoli di Wikipedia su zlib, DEFLATE, LZ77 e Huffman, oltre a numerosi articoli piccoli e piuttosto inutili sul Web e alcune risposte su Stack Overflow, ma nessuna mi potrebbe aiutare con la mia mancanza di comprensione.

sarei davvero grato per qualsiasi aiuto o suggerimento!

Answer 1

Penso che non trovi il modo bit sono confezionati all'interno di byte (si veda ad esempio la sezione 3.1.1 di 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. 

Quindi, se il primo byte è 05 = 0000 0101 il primo bit è 1.

(a proposito, è sicuramente molto istruttivo guardare le cose in modo più dettagliato, ma mi chiedo se non stai andando un po 'troppo lontano se intendi comprendere PNG.)

Inoltre, quando arrivi al punto in cui trovi lo stream IDAT non compresso, tieni presente che i pixel sono codificati con uno dei cinque filters per riga e che all'inizio di ogni riga c'è un byte in più che segnala il tipo di filtro. Quindi, non troverai i 12 byte originali 00 00 00 FF 00 00 00 00 FF 00 FF 00, ma 12 + 2 = 14 byte.

Answer 2

Nel caso in cui questo aiuta, ecco un disassemblaggio dei contenuti Chunk IDAT:

! 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 

È possibile ottenere il codice sorgente di infgenhere.