Структура сжатого блока Deflate

Question

У меня проблемы с пониманием алгоритма Deflate (RFC 1951).

TL; DR Как разобрать сжатый блок Deflate 4be4 0200?

Я создал файл с буквой и новой строкой a\n и запустил gzip a.txt. Результирующая файл a.txt.gz:

1f8b 0808 fe8b eb55 0003 612e 7478 7400 

4be4 0200 

07a1 eadd 0200 0000 

Я понимаю, что первая строка заголовка с дополнительной информацией, а последняя строка CRC32 плюс размер входа (RFC 1951). Эти двое не беспокоят меня.

Но как интерпретировать сжатый блок (средняя линия)?

Вот шестнадцатеричное и двоичное представление этого:

4be4 0200 

0100 1011 
1110 0100 
0000 0010 
0000 0000 

Насколько я понял, как-то эти из них:

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

• первый бит BFINAL
• следующие 2 бита BTYPE

... на самом деле в конечном итоге на конце первого байта: 0100 1 . (Я пропущу вопрос, почему бы кто-нибудь назвать «заголовок» то, что на самом деле в хвосте что-то другое.)

RFC содержит что-то, что, насколько я понимаю, должно быть объяснение этому:

• элементы данных упакованы в байты в порядке увеличение номера бита в пределах байта, то есть, начиная с наименее значимым битом байта.
• Элементы данных, отличные от кодов Хаффмана, упакованы , начиная с наименее значимого бита данных элемент.
• Коды Хаффмана упакованы, начиная с самого- Значительная часть кода.

Другими словами, если бы нужно было распечатать сжатые данные, как последовательность байтов, начиная с первого байта в правого края и перейти к влево, с наиболее значимый Значительный бит каждого байта слева, как обычно, был бы , способный анализировать результат справа налево, с фиксированной шириной элементов в правильном порядке MSB-to-LSB и кодах Хаффмана в бит-обратном порядке (т. е. с первым битом кода в относительной позиции LSB ).

Но, к сожалению, я не понимаю этого объяснения.

Возврат на мои данные. ОК, поэтому BFINAL установлен, и BTYPE - это что? 10 или 01?

Как интерпретировать остальную информацию в этом сжатом блоке?

Answer 1

Сначала давайте посмотрим на шестнадцатеричное представление сжатых данных в виде последовательности байтов (вместо серии 16-битных значений тупоконечника как в вашем вопросе):

4b e4 02 00 

Теперь позволяет преобразовать те шестнадцатеричные байты в двоичный:

01001011 11100100 00000010 000000000 

в соответствии с RFC, биты упакованы «начиная с наименее значимым битом байта». Наименее значимый бит байта - это самый младший бит байта. Таким образом, первый бит первого байта это один:

01001011 11100100 00000010 000000000 
    ^
     first bit 

Второй бит это один:

01001011 11100100 00000010 000000000 
    ^
     second bit 

Третий бит:

01001011 11100100 00000010 000000000 
    ^
    third bit 

И так далее. Когда вы пройдете все биты в первом байте, вы начнете с младшего значащего бита второго байта. Таким образом, девятый бит это один:

01001011 11100100 00000010 000000000 
       ^
       ninth bit 

И, наконец, последний бит, тридцать второй бит, это один:

01001011 11100100 00000010 000000000 
         ^
          last bit 

Значение BFINAL является первым битом в сжатых данных , и поэтому содержится в одном бите с надписью «первый бит» выше. Это значение равно 1, что указывает на то, что это последний блок в сжатых данных.

Значение BTYPE хранится в следующих двух битах данных. Это биты с надписью «второй бит» и «третий бит» выше. Вопрос только в том, какой бит из двух является наименее значимым битом и который является самым значительным битом. Согласно RFC, «Элементы данных, отличные от кодов Хаффмана, упаковываются , начиная с младшего значащего элемента данных». Это означает, что первый из этих двух бит, один с пометкой «второй бит», является наименее значимым. Это означает, что значение BTYPE равно 01 в двоичном формате. и поэтому указывает, что блок сжимается с использованием фиксированных кодов Хаффмана.

И это легкая часть. Декодирование остальной части сжатого блока сложнее (и с более реалистичным примером - намного сложнее). Правильное объяснение того, как это будет делать этот ответ слишком долго (и ваш вопрос слишком широк) для этого сайта. Я дам вам подсказку, но следующие три элемента в данных - коды Хаффмана 10010001 ('a'), 00111010 ('\ n') и 0000000 (конец потока). Остальные 6 бит не используются и не являются частью сжатых данных.

Примечание: чтобы понять, как декодировать сжатые данные с дефлятой, вам нужно будет понять, что такое Huffman codes. Приведенный вами RFC предполагает, что вы это делаете. Вы также должны знать, как работает LZ77 compression, хотя документ более или менее объясняет, что вам нужно знать.