3.2.3. Детали формата блока
Каждый блок сжатых данных начинается с 3 битового заголовка, содержащего следующие данные:
первый бит BFINAL следующие 2 бита BTYPE
Отметим что биты заголовка не обязательно начинаются на границе байта, так как блок не обязательно занимает целое число байтов.
BFINAL установливается только для последнего блока данных.
BTYPE определяет, как данные сжаты, следующим образом:
- 00 — нет компрессии
- 01 — сжат используя фиксированные коды Huffman-а
- 10 — сжат используя динамические коды Huffman-a
- 11 — зарезервировано (ошибка)
Единственная разница между двумя случаями компрессии состоит в том как определяются коды Huffman-а алфавита символ/длина и алфавита расстояние.
Во всех случаях, алгоритм декодирования данных следующий:
do
считать заголовок блока из входного потока.
если сохранен без применения компрессии
пропустить биты остатка в текущем, частично обработанном байте
считать LEN и NLEN (смотри следующую секцию)
скопировать LEN байт данных в выходной поток
в противном случае
если сжато используя динамические коды Huffman-а
считать представление деревьев (смотри ниже)
loop (до распознания кода конца блока)
декодировать значение (value) символа/длины из входного потока
если значение < 256
скопировать значение (литерального байта) в выходной поток
в противном случае
если значение совпадает с концом блока (256)
выйти из цикла
в противном случае (значение = 257..285)
декодировать расстояние (байт) в входном потоке
сдвинуться назад на декодированное количество в выходном потоке,
и копировать length байт из данной позиции в выходной поток
end loop
while не последний блок
Отметим, что ссылка на дубликат строки может обращатся к предыдущему блоку, то есть, обратное расстояние может пересекать одну или более границ блока. Однако расстояние не может обращаться к данным расположенным перед началом выходного потока. (Приложения использующие предустановленный словарь могут отбрасывать часть выходного потока; расстояние может указывать на такие части выходного потока в любом случае) Отметим также что строка ссылка может перекрывать текущую позицию; например, если последние 2 байта декодрованы как X и Y, а строка ссылка как <длина = 5, расстояние = 2> то данная ссылка дает в выходной поток X,Y,X,Y,X.
Теперь определим каждый метод сжатия.