Алгоритмы Зива-Лемпела (LZ) >>

Е.В. Михальчик

Описание формата сжатия данных Deflate

Домашняя страница

 По формату сжатия данных Deflate есть документ::  "Deflate compressed data format specification" rfc1951.pdf. Т.к. этот документ страдает краткостью и полным отсутствием примеров, здесь я привожу два примера декодирования данных, сжатых методом статического и динамического дефлета . Uncompressed метод не рассматриваю, т.к. слишком просто.

Для того чтобы понять, содержание этой странички необходимо внимательно прочитать документ "Deflate compressed data format specification" rfc1951.pdf.. Я не занимаюсь переводами :).

Т.к. Deflate - это цепочки бит, упаковынные в байты, я вставил данные в таблицы в двоичном виде и разделил битовые слова разными цветами, по принципу red, green, blue. А по сему, если Ваш Explorer настроен на игнорирование цветов, советую на время просмотра отключить эту фичу. Для описания чисел, в тексте используются три системы счисления HEX? DEC и BIN. И поскольку меня ломает писать 10d , 1Fh и 011100b, договоримся сразу:  

  • Все цифры черного цвета понимай как десятичные
  • Песочным цветом обозначены HEX  числа
  • Темно синим выделены двоичные данные.

Итак Deflate.

Первый пример - статический Deflate.

Вот код, текста  "Deflate late" полученный методом статического  Haffmana:

 72 49 4D CB 49 2C 49 55 00

Первое, на что надо обратить внимание - это порядок следования бит. Закодированные данные представлены цепочкой бит, которую надо считывать. В каком порядке считывать биты? Простое правило: все, что закодировано кодами Хаффмана идет старшим битом вперед или справа на лево.  Все остальное идет младшим битом вперед. т.е. старший бит слева.  Это не логично,т.к. для кодов Хаффмана длина заранее неизвесна. При этом биты следует считывать в порядке нумерации, как показано в таблице.

Байт 1 байт 2 байт 3
7 6 5 4 3 2 1 0
15 14 13 12 11 10 9 8
23 22 21 20 19 18 17 16

 

Вот наш код в двоичном виде.

Байт № +0 +1 +2 +3
0 01110011 01001001 01001101 11001011
4 01001001 00101100 01001001 01010101
8 00000000 00010001 00000000  

Рассмотрим подробно.

Код состоит из блоков, каждый блок начинается с 3 битного заголовка. Читаем первый  бит  заголовка (0 байт красный) = 1- это признак последнего  блока , 1= блок последний. Следующие два бита (0 байт зеленый ) = 01 - это тип блока 1 = статический Хаффман. Дальше должен идти статический  код Хаффмана, значит читаем биты справа на лево (0,1 байт синий) сначала с 3го до 7го , в первом байте ( 01110 ), потом с 0-го во втором (100). Получилось 01110100=72 .Это код из диапазона 00110000-10111111,  для цифр 0-143. Значит отнимаем 72-30, получилось  42 - это код символа 'D'. Читаем следующий код (1,2 байт красный) 10010101=95, это код из того же диапазона, отнимаем 30 получилось 55 - код символа 'e'. Далее по тому же принципу читаем 96 (2,3 зеленый ) , 9C (3,4 синий), 91 (4,5 красный),  A4 (5,6 зеленый) , 95 (6,7 синий) и 50 (7,8 красный). Получилось "Deflate". Дальше идет 7-битный код Хаффмана (8,9 байт зеленый) = 02. Это код из диапазона (0000000-0010111 - 256-279) т.е. получается 256+2=258. Из описания Deflate rfc1951, понятно, что это длина-смещение. Т.е. сначала надо считать доп биты. В нащем случае их количество равно 0, однако если бы надо было читать доп биты, то они читались бы с лева на право в прямом порядке. Итак дополнительных битов нет, берем из таблицы длину, для 258 = 4. Далее идет смещение. Читаем 5 бит (9 байт синий) опять же в прямом порядке, слева на право. Получается 4. Для смещения 4 надо считать один доп. бит. Читаем его (9 байт красный). Он равен 0. Итого смещение равно Dist + доп. бит получается 5. Мы имеем слово "Deflate " на выходе. И мы получили длина=4 смещение=5, т.е. копируем "late" получилось "Deflate late", что и требовалось доказать. Дальше читаем (10 байт зеленый ) 0000000 - это 256 = признак конца блока, т.к. в заголовке мы имели признак того, что блок последний, на этом все.

Надеюсь со статическим дефлятом все ясно, переходим к динамическому.

Вот пример № 2:

Текст = "Congratulations on becoming an MCP. Please be advised that effective immediately[0D][0A]"

Байт № +0 +1 2 +3 +4 +5 +6 +7
0 00001100 11001000 01000001 00001010 10000000 00100000 00010000 00000101
8 11010000 01111101 11010000 00011101 11111110 00001001 10111010 10000100

Читаем 1ый бит=0 - не последний блок. Тип (0 байт зеленый) =2 динамический Дефлят. Значит дальше читаем HLIT-257  (0 синий) =1, HDIST-1 (1  красный) = 8 и HCLEN-4 (1,2 зеленый) = E.

Итого имеем: HLIT=258, HDIST=9, HCLEN=18

Далее следует code lengths for code lengths алфавит. Читаем , (начиная с 2 байта красный по 8 байт синий )  18  трехбитных значений. Эти коды читаются в прямом порядке с лева на право, получаем коды длин для алфавита.

символ алфавита длин 16 17 18 0 8 7 9 6 10 5 11 4 12 3 13 2 14 1 15
длина кода символа 0 4 4 2 0 0 0 2 0 2 0 4 0 5 0 0 0 5 -

Далее, следуя указаниям rfc1951 нам следует построить коды для  алфавита длин кодов, зная их длину.  Однако ни слова НЕТ о том, в каком порядке строить коды. Ведь если алфавит задан именно в такой последовательности, то можно подумать, что и коды  строятся для такой же последовательности цифр, т.е. 0 для 0, 1 для 6, 2 для 5, С для 17, D для 18,  E для 4, 1E для 3, 1F для 1. Однако это не так.

Как оказалось коды надо строить  расположив алфавит в нормальном порядке.

Алфавит кодов длин длина кода  код (двоичный)
0 2 00
1 5 11110
2 0  
3 5 11111
4 4 1100
5 2 01
6 2 10
7 0  
8 0  
9 0  
10 0  
11 0  
12 0  
13 0  
14 0  
15 -  
16 0  
17 4 1101
18 4 1110

Дальше надо считать длины кодов алфавита CWL для HLIT, т.е. 258  символов, закодированные кодами, которые мы только что получили..Ищем полученные коды, начиная с 8 байта (крачный), т.к. это коды Хаффмана, читаем в обратном порядке - справа на лево. (8,9 красный) 1101 - это код 17, значит считываем 3 доп бита, что харрактерно в прямом порядке, (9 зеленый)  111 это 7.  Значит для основного алфавита получаем repeat code length of 0 ( 3+7=)10 times.  Значит первые 10 символов алфавита имеют длину кода = 0. Читаем дальше (9 синий) 10, (10 байт) 00,00,10, получили длины кодов для символов 0A,0B,0C,0D = 0A=6,0B,0C=0,0D=6.

Байт № +0 +1 2 +3 +4 +5 +6 +7
8 11010000 01111101 11010000 00011101 11111110 00001001 10111010 10000100
16 11101011 10100000 00101011 01001100 11111010 10110101 00000001 00011101
24 00100001 00100111 10100001 11011011 11010111 01011011 10111110 11010000

Дальше читаем (10,11 красный) 1110 - это код 18, значит читаем 7 доп. бит. в прямом порядке (11,12  зеленый)=0000111 получаем 11+7=18 нулей для символов с 0Е по 1F. Дальше читаем (12 синий ) 11111 - это 3, длина для символа 20. Дальше опять идет код 18 (12,13 красный) ,  7 доп бит (13,14 зеленый) дают 2+11=13 нулей. Дальше считываем (14 синий ) 10 это 6 бит, длина кода для символа 2E. (14 красный) 1110-код 18 (14,15 зеленый)  7 доп. бит 0001001 = 9. Имеем 11+9=20 нулей для символов с 2F по 42.

Дальше коротко: 43 = 5 (см. 15 байт синий 01=2 = 5),  [17]^9 (см. 16 байт красный 1101 это 17 и 16 зеленый 110=6 это 3 доп. бита получается 3+6=9 т.е. [17]^9), 4D=6, 4E=0, 4F=0, 50=6, [18]^16, 61=4, 62=6, 63=5, 64=5, 65=3, 66=5, 67=5, 68=6, 69=4, 6A=0, 6B=0, 6C=5, 6D=5, 6E=4, 6F=5, 70=0, 71=0, 72=6, 73=5, 74=4, 75=6, 76=5, 77=0, 78=0, 79=6, [18]^134, 100=6, 101=6,

Начиная с 28 байта зеленый,  считываем коды для 8 символов из алфавита смещений. 0=1, [17]^7, 8=1.

Таким образом мы получили длины кодов для алфавита CWL.. Зная длины кодов получаем коды Хаффмана:

Коды для алфавита кодов и длин кодов
Код символа длина кода код Хаффмана Код символа длина кода код Хаффмана Код символа длина кода код Хаффмана Код символа длина кода код Хаффмана
00-09 0 - 44-4C 0 - 66 5 10011 72 6 111011
0A 6 110100 4D 6 110111 67 5 10100 73 5 11000
0B,0C 0 - 4E,4F 0 - 68 6 111010 74 4 0111
0D 6 110101 50 6 111000 69 4 0101 75 6 111100
0E-1F 0 - 51-60 0 - 6A,6B 0 - 76 5 11001
20 3 000 61 4 0100 6C 5 10101 77,78 0 -
21-2D 0 - 62 6 111001 6D 5 10110 79 6 111101
2E 6 110110 63 5 10001 6E 4 0110 80-FF 0 -
2F-42 0 - 64 5 10010 6F 5 10111 100 6 111110
43 5 10000 65 3 001 70,71 0 0 101 6 111111

 

Коды для алфавита смещений
Код символа длина кода код Хаффмана
0 1 0
1-8 0 -
8 1 1

Дальше начиная с 30 байта красный считываем собственно текст, используя полученные коды.

Байт № +0 +1 2 +3 +4 +5 +6 +7
24 00100001 00100111 10100001 11011011 11010111 01011011 10111110 11010000
32 10101101 11011100 11100010 01001111 00010101 11010111 01101110 00000011
40 11011101 01110000 00110010 11110110 10100110 01010110 00100000 10000110
48 00111101 00011100 00011011 10001110 01001010 00011001 11111100 00011111
56 10010010 10100110 00001110 00100110 11111000 00100101 00001110 11100110
64 11001100 11101000 00111010 00001001 01101101 10001101 01001001 11000101
72 01011001 11011111 01110101 11111001 00000110 00000000    

Получилось: 43  6F 6E  67  72  61  74 75 6C 61 74 69 6F 6E 73 20 6F 6E 20 62 65 63 6F 6D 69 6E 67 20 61 6E 20 4D 43 50 2E

20 50 6C 65 61 73 65

что в переводе на язык символов означает "Congratulations on becoming an MCP. Please"

обратим внимание на байт  54 красный, где мы сейчас и находимся. считываем код 111111 это код символа 101, т.е это не символ, а длина повторения 257. Здесь мы должны считать доп. биты, однако для 257 их количество равно 0. Значит получаем длину повторения равную 3 для 257.  Теперь надо считать смещение (distance) , а для этого надо выбрать код из алфавита смещений. Т.к. в алфавите смещений всего два кода 0 и 1 выбираем один бит (байт 55 бит 1 зеленый) он равен 1, что означает код смещение = 8.  Смотрим в таблицу из rfc1951, для кода смещение 8 мы должны считать 3 доп. бита (55 синий) и в результате получить смещение в диапазоне 17-24. В нашем случае 17+7 будет 24. Итого отматываем 24 символа назад это будет указывать на " becoming an... " и копируем 3 символа. В результате получается

"Congratulations on becoming an MCP. Please be"

Дальше, читаем следующий код (55 красный)  это 20.  Ну и дальше можно продолжать в том же духе до (75,76 байта красный), где мы считаем код кода 256(111110)-конец блока.  После чего идет трехбитный заголовок следующего блока, который статический и последний. Он тут же заканчивается семью 0.