Блог

В целях самообразования я пытаюсь создать программу, которая преобразует файл png в массив значений RGBA. Однако у меня возникла проблема с декодированием разделов IDAT, которые закодированы в zlib с использованием формата deflate. Проблема, с которой я сталкиваюсь, заключается в том, что я не знаю, как найти, где находится конец сжатого блока. Единственное место в документации, где указана длина, предназначено только для распакованных блоков, однако для блока с таблицами Хаффмана по умолчанию и предоставленными таблицами Хаффмана, похоже, нет способа узнать, где заканчивается блок. Как мне найти конец блока в формате deflate.

Согласно документации по сжатию PNG Deflate / Inflate

Сжатые данные в потоке данных zlib хранятся в виде серии блоков, каждый из которых может представлять необработанные (несжатые) данные, сжатые данные LZ77, закодированные фиксированными кодами Хаффмана, или сжатые данные LZ77, закодированные пользовательскими кодами Хаффмана. Бит маркера в последнем блоке идентифицирует его как последний блок, позволяя декодеру распознавать конец сжатого потока данных. Более подробная информация об алгоритме сжатия и кодировке приведена в спецификации deflate [RFC-1951].

…

В файле PNG, объединение содержимого всех блоков IDAT составляет поток данных zlib как указано выше. Этот поток данных распаковывается в отфильтрованные данные изображения, как описано в другом месте этого документа.

Важно подчеркнуть, что границы между блоками IDAT произвольны и могут находиться в любом месте потока данных zlib. Необязательно существует какая-либо корреляция между границами блока IDAT и границами блока deflate или любой другой особенностью данных zlib. Например, вполне возможно, что завершающее контрольное значение zlib будет разделено на блоки IDAT.*»

И согласно RFC 1951: «DEFLATE Спецификация формата сжатых данных версии 1.3»:

Сжатый набор данных состоит из серии блоков, соответствующих последовательным блокам входных данных. Размеры блоков произвольны, за исключением того, что несжимаемые блоки ограничены 65 535 байтами.

Каждый блок сжимается с использованием комбинации алгоритма LZ77 и кодирования Хаффмана. Деревья Хаффмана для каждого блока не зависят от деревьев Хаффмана для предыдущего или последующих блоков; алгоритм LZ77 может использовать ссылку на дублированную строку, встречающуюся в предыдущем блоке, до 32 Тыс. входных байт ранее.

Каждый блок состоит из двух частей: пары деревьев кода Хаффмана, которые описывают представление части сжатых данных, и части сжатых данных. (Сами деревья Хаффмана сжимаются с использованием кодировки Хаффмана.) Сжатые данные состоят из серии элементов двух типов: литеральных байтов (строк, которые не были обнаружены как дублированные в предыдущих 32K входных байтах) и указателей на дублированные строки, где указатель представлен в виде пары <длина, обратное расстояние>. Представление, используемое в формате «сдувать», ограничивает расстояния до 32 Тыс. байт и длины до 258 байт, но не ограничивает размер блока, за исключением несжимаемых блоков, которые ограничены, как отмечено выше.

Каждый тип значения (литералы, расстояния и длины) в сжатых данных представлен с использованием кода Хаффмана, используя одно дерево кода для литералов и длин и отдельное дерево кода для расстояний. Деревья кода для каждого блока отображаются в компактной форме непосредственно перед сжатыми данными для этого блока.

Итак, чтобы определить конец данного блока, вам нужно будет проанализировать коды Хаффмана блока, чтобы узнать местоположение и тип каждого элемента в сжатых данных, а затем вы можете обрабатывать каждый элемент по мере необходимости, пока не найдете конец последнего элемента в блоке. Раздел 3.2 посвящен техническим деталям форматирования сжатых блоков, в частности разделу 3.2.3:

3.2.3. Сведения о формате блока

Каждый блок сжатых данных начинается с 3 бит заголовка, содержащих следующие данные:

 first bit       BFINAL
next 2 bits     BTYPE
  

Обратите внимание, что биты заголовка не обязательно начинаются с границы байта, поскольку блок не обязательно занимает целое число байтов.

BFINAL устанавливается тогда и только тогда, когда это последний блок набора данных.

BTYPE указывает, как данные сжимаются, следующим образом:

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

Единственное различие между двумя сжатыми случаями заключается в том, как определяются коды Хаффмана для буквенных / длинных и дистанционных алфавитов.

Во всех случаях алгоритм декодирования фактических данных следующий:

 do
    read block header from input stream.
    if stored with no compression
        skip any remaining bits in current partially
            processed byte
        read LEN and NLEN (see next section)
        copy LEN bytes of data to output
    otherwise
        if compressed with dynamic Huffman codes
            read representation of code trees (see
                subsection below)
        loop (until end of block code recognized)
            decode literal/length value from input stream
            if value < 256
                copy value (literal byte) to output stream
            otherwise
                if value = end of block (256)
                    break from loop
                otherwise (value = 257..285)
                    decode distance from input stream

                    move backwards distance bytes in the output
                    stream, and copy length bytes from this
                    position to the output stream.
        end loop
while not last block
  

Обратите внимание, что дублированная ссылка на строку может ссылаться на строку в предыдущем блоке; т. Е. расстояние назад может пересекать одну или несколько границ блока. Однако расстояние не может относиться к началу выходного потока. (Приложение, использующее предустановленный словарь, может отбросить часть выходного потока; расстояние в любом случае может относиться к этой части выходного потока) Также обратите внимание, что строка, на которую ссылается, может перекрывать текущую позицию; например, если последние 2 декодированных байта имеют значения X и Y, ссылка на строку с <length = 5, distance = 2> добавляет X,Y,X, Y,X в выходной поток.