Как читать и декодировать блок zlib и блок deflate в файле изображения png
Недавно я начал писать декодер png для развлечения. И для понимания формата и сжатия я прочитал следующее
Спецификация PNG (переносимая сетевая графика), версия 1.2)
RFC 1950 («Спецификация формата сжатых данных ZLIB»)
RFC 1951 («Спецификация формата сжатых данных DEFLATE»)
И, следовательно, я имею простое представление о формате и сжатии.
Итак, сначала я решил реализовать простой декодер, который будет декодировать простой файл изображения png, и для этого я выбрал простое изображение png, содержащее один фрагмент IDAT, который содержит один блок zlib и блок deflate.
И используемый файл изображения это Файл изображения, используемый для декодирования
И я извлек блок zlib из файла изображения, и в шестнадцатеричном редакторе он выглядит так Шестнадцатеричный вид IDAT CHUNK
И бинарное представление части, отмеченной красным, это Двоичное представление блока zlib
Теперь из того, что я понял, прочитав спецификации, я расшифровал это следующим образом. Декодированное двоичное представление блока zlib
BFINAL=КОНЕЧНЫЙ БЛОК
BTYPE=ДИНАМИЧЕСКИЙ ХАФФМАН
HLIT=29
HDРАСП=29
ХКЛЕН=11
Части, отмеченные зеленым цветом, представляют собой (HCLEN + 4) длины кода для алфавита длины кода.
Длины чтения следующие: 6,6,0,2,3,3,5,4,4,4,3,6,4,6,5.
Сгенерированные коды Хаффмана для приведенных выше длин кода в битах следующие: Сгенерированный код Хаффмана
И после присвоения им соответствующей длины алфавита выглядит следующим образом (Примечание: длина алфавита 18 не используется, поскольку длина его кода равна нулю) Присвоенные коды Хаффмана
Теперь, когда я начал декодировать код Хаффмана для (HLIT+257) длин кодов кодов Хаффмана для буквенных/длинных алфавитов, используя назначенные коды Хаффмана, я получил первый декодированный алфавит как 16, но это невозможно, поскольку алфавит 16 копирует предыдущий алфавит длины кода, но это невозможно, так как это первый декодированный алфавит.
Следовательно, в моем понимании формата есть некоторая ошибка, и я не могу понять это, и здесь мне нужна помощь.
Ответы 1
То, как вы представляете коды, не имеет смысла, поскольку вы показываете кучу нулей, которые не являются частью кодов, поэтому вы не можете сказать, какова их длина. Также вы показываете коды в обратном порядке по сравнению с тем, как они отображаются в байтах.
Что еще более важно, вы каким-то образом неправильно поняли задания. Вот правильные коды, показывающие только биты в кодах, в правильном порядке битов, с правильными назначениями:
00 - 0
010 - 7
110 - 8
001 - 11
0101 - 5
1101 - 6
0011 - 10
1011 - 12
00111 - 9
10111 - 13
001111 - 3
101111 - 4
011111 - 16 (followed by two bits, +3 is the repeat count)
111111 - 17 (followed by three bits, +3 is the zeros count)
Первый код длины кода — 001111, что говорит о том, что литерал 0 имеет длину кода 3.