Е.В. Михальчик
Описание формата сжатия данных 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 | ||||||||||||||||||||||||
|
|
|
Вот наш код в двоичном виде.
| Байт № | +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.