Кодирование Хаффмана. Часть 3

Вступление

В прошлой части мы рассмотрели программу на C++, сжимающую данные. Кроме этого, автор соизволил признаться, что написанная программа не является идеалом, и что при определённых наборах частот сжатие будет неверным.
Эта статья посвящена распаковке сжатого файла при помощи программы на ассемблере и дерева, построенного программой сжатия. Опять же следует оговориться: программа не рассчитана на распаковку гигантских файлов, но её в любой момент можно модифицировать так, чтобы подобных проблем не было. Что же касается самого алгоритма распаковки, то он предельно прост, что мы и обсудим в следующих разделах.
Быстрый старт
В качестве компилятора языка Ассемблера я решил выбрать всем полюбившийся FASM (его можно взять по адресу http://www.flatassembler.net/). Это очень удобный, маленький и шустрый компилятор, на нём даже пишут операционную систему MenuetOS (http://www.menuetos.net/). Сам дистрибутив весит немного, и, думаю, этот компилятор однозначно "must have".
Ладно, что-то я удалился от темы. Начнём проектировать. Первым делом нам надо распределить ресурсы программы, то есть определить необходимый ей набор данных. Итак, в данном случае программа должна быть:
1. Небольшой. Иначе выгоды от сжатия данных мы не получим.
2. Быстрой. Это сам собой разумеющийся факт.
3. Простой в использовании.
Пункт 1 достигается за счёт программ типа COM: в них не надо дополнительно описывать сегменты, резервировать место под стек, в них нет стандартного MZ-заголовка, что уже сокращает код, как минимум, на 0x40 байт. Помимо этого, 64 килобайта файла типа COM для подобной программы ― очень даже большая величина. Отсюда, соответственно, и вывод: программа будет иметь формат исполняемого файла типа COM.
Пункт 2 достигается за счёт того, что программа написана на ассемблере, а также подобраны более-менее оптимальные алгоритмы (автор, естественно, не претендует на сверхпроизводительный код).
Так как данная программа ― лишь демонстрационный вариант, то я решил её упростить, а именно: зафиксировать имена входного и выходного файла: входной файл будет называться "data.huf", а выходной ― "data.txt".
Нам будут необходимы файловые дескрипторы входного и выходного файла:

Код (ASM):

1. file_in:
2.   dw 0
3. file_out:
4.   dw 0

Помимо этого, нам нужно построить алгоритм чтения так, чтобы данные из файла читались по-битно. Поэтому приходится объявлять следующие переменные (наподобие того, что мы делали в программе на С++):

Код (ASM):

1. ; Состояние чтения из файла
2. in_byte:
3.   db 0
4. in_count:
5.   db 0
6. out_buf_bytes:
7.   dw 0
8. in_index:
9.   dw 0ffffh

Здесь in_byte ― текущий байт, из которого поочерёдно будут извлекаться биты, in_count ― количество ещё не извлечённых из байта бит, out_buf_bytes ― размер буфера, который следует записать в выходной файл, in_index ― номер текущего байта в буфере ввода.
Объявляем символьные константы имён файлов и сообщений об ошибках:

Код (ASM):

1. ; Соответствующие данные
2. Message_in:
3.   db "Can't open file data.huf$"
4. Message_out:
5.   db "Can't create file data.txt$"
6. in_name:
7.   db "data.huf",0
8. out_name:
9.   db "data.txt",0

Осталось только разрисовать структуру данных в памяти:

Дерево кодирования

Символьные константы сообщений и имен файлов​

Файловые дескрипторы и данные состояния чтения из файла​

Буфер вывода

Буфер ввода

Верхние ячейки соответствуют младшим адресам, нижние ― старшим. Заметим, что буфер вывода и буфер ввода ― довольно-таки объёмные структуры, поэтому поместить их в файл ― значит проиграть в размере декомпрессора. Поэтому следует прибегнуть к стандартной уловке: "зарезервировать" пространство в конце файла:

Код (ASM):

1. ; Буферы данных
2. align 10h
3. ; Структура памяти:
4. ; - Буфер вывода
5. ; - Буфер ввода
6. buffer:

Задать положение и размер буферов помогут следующие константы в начале файла:

Код (ASM):

1. BLOCK_SIZE  = 8192 ; Размер буферов
2. input_buffer = buffer+BLOCK_SIZE ; Адрес буфера ввода

Примитивы
Итак, как и в прошлой статье, пойдём от простого к сложному. И, на мой взгляд, следует начать с функции извлечения байта из буфера ввода в байтовый буфер:

Код (ASM):

1. ; Функция: считать байт из буфера ввода в байтовый буфер
2. read_byte:
3.   pusha
4.   ; Индекс байта в буфере ввода
5.   mov bx, word [in_index]
6.   cmp  bx, BLOCK_SIZE
7.   jb  no_block_load
8.   ; Если номер байта выходит за границы буфера
9.   ; Читаем блок размером BLOCK_SIZE из файла
10.   mov  bx, word [file_in]
11.   mov  cx, BLOCK_SIZE
12.   mov  dx, input_buffer
13.   mov  ah, 3Fh
14.   int 21h
15.   ; И обнуляем счётчик байтов в буфере
16.   xor  bx, bx
17. no_block_load:
18.   ; Извлекаем байт из буфера
19.   mov  al, byte [input_buffer+bx]
20.   ; Увеличиваем счётчик на единицу
21.   inc  bx
22.   ; И заполняем данные о байте
23.   mov  byte [in_byte], al
24.   mov  byte [in_count], 8
25.   mov  word [in_index], bx
26.   popa
27.  ret

Разберёмся, что она выполняет. Первым делом она смотрит, есть ли ещё не считанные байты в буфере ввода (сравнивает содержимое in_index с BLOCK_SIZE). Если больше читать из буфера нечего, то она считывает входной буфер из файла и обнуляет счётчик байтов во входном буфере. После этого программа извлекает байт из буфера ввода, увеличивает счётчик текущего байта на единицу и заполняет данные байтового буфера: количество несчитанных бит (естественно, для байта их количество будет равно 8). Как оказалось, функция совсем несложная. Перейдём к следующей функции:

Код (ASM):

1. ; Функция: считать бит из файла и вернуть его в регистре ax
2. input_bit:
3.   push  dx
4.   push cx
5.   push  bx
6.   ; смотрим, все ли биты байта были считаны
7.   cmp byte [in_count], 0
8.   jne  input_get_bit
9.   ; если байт пуст, то надо считать новый
10.   call read_byte
11.   ; Получаем бит из байта
12. input_get_bit:
13.   xor  ax, ax
14.   mov  dl, byte [in_byte]
15.   mov  al, dl
16.   shr  dl, 1
17.   and  al, 1
18.   mov  byte [in_byte], dl
19.   dec  byte [in_count]
20.   ; Восстанавливаем сохранённые регистры и выходим
21.   pop  bx
22.   pop  cx
23.   pop  dx
24.   ret

Как уже видно из комментария к функции, она должна считать бит из байтового буфера и вернуть ax=1, если считанный бит равен единице и ax=0, если бит равен 0. Первым делом функция смотрит, есть ли ещё в байтовом буфере непрочитанные биты. Если такие биты не имеются, то вызывается функция чтения байта из буфера, уже рассмотренная ранее. После этого из байтового буфера считывается значение, берётся его младший бит и помещается в регистр ax, затем все биты сдвигаются на одну позицию вправо, и новое значение записывается в байтовый буфер. Также уменьшается информация о количестве несчитанных бит в байтовом буфере на единицу. Как видно отсюда, функция опять же не сложная.
Теперь следует объявить функцию, которая записывает буфер вывода в файл. Собственно говоря, эта функция простая и является простой имплементацией функции DOS:

Код (ASM):

1. ; Функция: запись блока в файл
2. put_to_file:
3.   pusha
4.   mov ah, 40h
5.   mov bx, word [file_out]
6.   mov cx, word [out_buf_bytes]
7.   mov dx, buffer
8.   int 21h
9.   popa
10.   ret

Особого ничего интересного в этой функции нет. Просто в файл, описанный дескриптором file_out, записывается out_buf_bytes байт выходного буфера.
Шаги по дереву
Теперь мы имеем необходимый базис функций для того, чтобы организовать декодирование файла. И начнём с самой первой ― декодирование байта:

Код (ASM):

1. ; Функция: пройтись по дереву, получить байт и поместить его в
2. ; выходной буфер
3. decode_byte_func:
4.   pusha
5.   ; Помещаем в bx адрес корня дерева
6.   mov bx, opcode00000000_0000
7.   ; И спускаемся по дереву
8. decode_byte_looping:
9.   ; Если мы достигли конца ветки - выходим
10.   cmp word [bx+2], -1
11.   je  loop_out
12.   ; Считываем бит
13.   call  input_bit ; ax = считанный бит
14.   ; И направляемся по соответствующей ветке
15.   shl  ax, 1
16.   add  bx, ax
17.   mov  bx, word [bx]
18.   ; Шагаем дальше
19.   jmp  decode_byte_looping
20. loop_out:
21.   ; Мы нашли символ - он по адресу [bx]
22.   mov  al, byte [bx]
23.   ; Помещаем символ в буфер
24.   mov  bx, word [out_buf_bytes]
25.   mov  byte [buffer+bx],al
26.   inc bx
27.   mov  word [out_buf_bytes], bx
28.   ; Если мы не достигли конца буфера, осуществляем переход
29.   cmp  bx, BLOCK_SIZE
30.   jb  exit_decode_byte
31.   ; Скидываем буфер в файл
32.   call put_to_file
33.   mov  word [out_buf_bytes], 0
34. exit_decode_byte:
35.   popa
36.  ret

Что же делает эта функция? Первым делом она загружает в регистр bx корень дерева ― сгенерированную написанной в прошлой статье программой метку opcode00000000_0000. После этого осуществляет спуск по дереву от корня к листьям: если текущее положение не является конечным узлом дерева, то вызывается функция считывания бита ― input_bit, после чего, в зависимости от того, какое значение содержится в ax, осуществляется переход по соответствующей ветке в следующий узел, действие повторяется, пока мы не достигнем "финиша". В вершинах (конечных узлах) дерева содержится информация, какой символ соответствует этому узлу ― поэтому программа с лёгкостью извлекает необходимый декодированный символ и помещает его в выходной буфер. После этого увеличивает счётчик байтов в выходном буфере. Если счётчик превышает значение BLOCK_SIZE, то программа записывает буфер в выходной файл и сбрасывает счётчик в ноль.
Но эта функция реализует декодирование лишь одного байта. Рассмотрим теперь декодирование всего файла, чему и посвящена следующая функция:

Код (ASM):

1. ; Функция: декодировать файл
2. decode_file:
3.     pusha
4. decode_loop:
5.     cmp     dword [coded_file_size],0 ; Проверяем, все ли байты декодированы
6.     je      end_decode_loop
7.     dec     dword [coded_file_size] ; Счётчик байтов - 1
8.     call    decode_byte_func ; И декодируем байт
9.     jmp     decode_loop ; Повторяем, пока счётчик не 0
10.     ; сюда приходим, когда файл полностью декодирован
11. end_decode_loop:
12.     ; проверяем, не пуст ли выходной буфер
13.     mov     cx, word [out_buf_bytes]
14.     test    cx, cx
15.     jz      exit_decode_file
16.     ; Если в буфере есть данные, то их надо записать в файл
17.     call    put_to_file
18. exit_decode_file:
19.     popa
20.     ret

Эту функцию автор оставляет на рассмотрение читателя, так как совсем очевидно, что она делает.

int main(int argc, const char *argv[])

Ну что же, теперь мы во всеоружии: у нас есть функция, которая декодирует файл и записывает декодированные данные в выходной файл. Что же, осталось дело не за многим, а именно ― подготовить файловые дескрипторы и вызвать функцию декодирования файла. Это и делает наша функция start:

Код (ASM):

1. ; Точка входа: отсюда начинается выполнение программы
2. start:
3.     ; Устанавливаем сегментные регистры
4.     mov     ax, cs
5.     mov     ds, ax
6.     mov     es, ax
7.     mov     ss, ax
8.     mov     sp, 0FFFEh
9.     ; Открываем файл для чтения (data.huf)
10.     mov     ax, 3D02h
11.     xor     cx, cx
12.     mov     dx, in_name
13.     int     21h
14.     jc      not_open
15.     mov     word [file_in], ax
16.     ; Создаём и открываем файл для записи (data.txt)
17.     mov     ax, 3C00h
18.     xor     cx, cx
19.     mov     dx, out_name
20.     int     21h
21.     jc      not_created
22.     mov     word [file_out], ax
23.     ; Декодируем файл
24.     call    decode_file
25.     ; Закрываем созданный файл
26.     mov     ah, 3Eh
27.     mov     bx, word [file_out]
28.     int     21h
29.     jmp     ok_exit
30.     ; Выводим сообщение об ошибке
31. not_created:
32.     mov     ah, 9
33.     mov     dx, Message_out
34.     int     21h
35.     ; Закрываем открытый для чтения файл
36. ok_exit:
37.     mov     ah, 3Eh
38.     mov     bx, word [file_in]
39.     int     21h
40.     ret
41.     ; Ошибка: файл не был открыт
42. not_open:
43.     mov     ah, 9
44.     mov     dx, Message_in
45.     int     21h
46.     ret

В принципе, эта функция выполняет следующие действия:
1. Установить сегментные регистры эквивалентно cs, установить указатель стека в конец сегмента.
2. Открыть файл для чтения с именем, содержащимся в строке in_name. Если открытие не удалось, то вывести сообщение об ошибке и выйти из программы.
3. Создать и открыть файл для записи с именем, содержащимся в строке out_name. Если создание файла не удалось, то вывести соответствующее сообщение об ошибке и выполнить пункт 6.
4. Вызвать функцию, декодирующую файл ― decode_file.
5. Закрыть выходной файл.
6. Закрыть входной файл и выйти из программы.
Компиляция
Компиляция ― одна из важнейших частей. Нужно сгенерировать файл, декодирующий сжатые данные, а для этого нужно генерировать таблицу декодирования и прилинковать к файлу. В принципе, это легко решается путём включения в исходник директивы:

Код (ASM):

1. ; Собственно говоря, сама таблица декодирования
2. include "map.asm"

Здесь map.asm - созданная программой на С++ таблица декодирования файла.
Таким образом, проглядывается необходимая последовательность действий:
1. Сжать исходный файл, получить сжатые данные и таблицу декодирования.
2. Скомпилировать программу-распаковщик с использованием сгенерированной таблицы.
3. Проверить, работает ли распаковщик, выполнив декомпрессию.
В таких случаях удобно писать bat-файлы. Собственно говоря, что мы и сделаем:

Код (Text):

1. xarch xarch.cpp data.huf map.asm
2. fasm xdecode.asm xdecode.com
3. xdecode

При запуске bat-файла получим следующие файлы:

• data.huf ― сжатый алгоритмом Хафмана файл xarch.cpp.
• map.asm ― дерево декодирования сжатого файла.
• xdecode.com ― программа, декодирующая сжатые данные.

Теперь xdecode.asm и data.huf можно пускать в свободное плавание .
Постскриптум
Перед вами последняя статья из цикла "Кодирование Хафмана". Надеюсь, я смог вложить в неё всю необходимую информацию. Слово, как всегда, остаётся за читателем, потому, как только он сможет оценить, насколько данная статья полезна в повседневной деятельности. Конечно же, все перечисленные методы программирования не идеальны и не претендуют ни на какую абсолютную истину: это обычные примеры, которые всегда можно расширить и дополнить, получив тем самым необходимый результат.
P.P.S.
Здесь должно быть какое-нибудь заумное высказывание, тем или иным способом связанное с изложенным материалом. Но в этот раз, право слова я оставлю читателю. Так что можете писать мне письма с вашими вариантами.
Исходники к статье + FASM расположены в файле huffman.zip

© SadKo 2006​