Кодирование Хаффмана (часть 3)

Дата публикации 24 авг 2017 | Редактировалось 10 янв 2018

Кодирование Хаффмана. Часть 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

2 4.093
SadKo

SadKo
Владимир Садовников

Регистрация:
4 июн 2007
Публикаций:
8