Описание декодера формата 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. Для более удобного восприятия:  

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

Итак Deflate.

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

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

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

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

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

Код состоит из блоков, каждый блок начинается с 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]"

Читаем 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  трехбитных значений. Эти коды читаются в прямом порядке с лева на право, получаем коды длин для алфавита.

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

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

Дальше надо считать длины кодов алфавита 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.

Дальше читаем (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.. Зная длины кодов получаем коды Хаффмана:

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

Получилось: 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

что в переводе на язык символов означает "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.

Remote Control - Программа для удаленного доступа к компьютеру.
ImageConverter - Программа для уменьшения фотографий.
AutoShutdown - Программа для автоматического выключения компьютера.
Work time counter - Простая программа для учета рабочего времени.
ClearFolders - Программа для массового удаления файлов.
SynchronizeFolders - Программа для синхронизации каталогов.
DiskSector - Утилита позволяет осуществлять чтение / запись секторов диска в / из файла.
ROPTest - Программа изображает все 256 вариантов флагов Ternary Raster Operations Codes, помогает определить необходимый код растровой операции.
HEX Dump ActiveX позволяет просматривать и редактировать данные в шестнадцатеричном HEX формате.
15 slide puzzle - 15 slide puzzle game.
BOOTSAVER - Позволяет скопировать загрузочный сектор жесткого диска в файл, восстановить загрузочный сектор из файла, восстановить загрузочную программу IPL1, не меняя таблицу разделов диска.
Генератор кроссвордов. Описание алгоритм компьютерного составления кроссвордов.
Симулятор 80196. Программный симулятор микроконтроллера Intel 80196KR. Имеет встроенный компилятор ассемблера, текстовый редактор, справочную систему. Может создавать HEX файлы.
Ассемблер. Оригинальный компилятор ассемблера х86.
DISKEDIT Программа позволяет просматривать и редактировать сектора дисков. Работает через прерывание INT13.

WPF, XPS, NET. Как установить шрифт из памяти
Нейронные сети. Пример программы и исходный код С++.
Deflate. Подробное описание алгоритма декодирование формата Дефлет. Прмер декодирования с пояснениями.
Программирование драйверов для Windows. Общие вопросы программирования драйверов. Какими средствами пользоваться, где скачать DDK.
Программирование RS232 в Windows. СComBase класс для программирования COM порта.
Программирование потоков в Windows. Класс CBaseThread позволяет организовать несколько рабочих потоков.
Динамический Recordset CDynamicRecordSet - класс модернизирует CRecordSet для более удобной работы с БД из MFC приложений.
Как сохранить, восстановить, отредактировать MBR (Master Boot Record), boot sector, нулевой, загрузочный сектор диска при помощи утилиты debug.exe