ZX Review #7-8-9-10
08 ноября 1997

Этюды - Процедура составления оптимальной таблицы символов.

(c) Татаринов М., г.Соликамск

   Хочу  предложить   процедуру,
которая будет  полезна  создате-
лям  компрессоров,  использующих
алгоритм Хаффмана (битовая  ком-
прессия).
   Как известно, подобный  метод
требует наличия справочной  таб-
лицы символов.  Чем  меньше  бу-
дет номер символа в таблице, тем
меньше потребуется бит для коди-
ровки этого символа. Данная про-
цедура  составляет  для  каждого
файла оптимальную таблицу.
   Программа работает  следующим
образом: первым делом  подсчиты-
ваются  коэффициенты  повторения
каждого  символа  в  файле,  за-
тем  коэффициенты сортируются, и
идентификаторы этих  коэффициен-
тов упаковываются в таблицу.
   Программа для работы  требует
буфер, максимальный размер кото-
рого равен 3*256=768 байт (т.е.,
если в файле 256 различных  сим-
волов. 3 - это размер одной  за-
писи в  буфере).  Таблица  будет
записана также в начало буфера.
140.
;Программа для составления
;таблицы
;(C) Mat Software'96

MKTREE    LD      A,#FF
          LD      (TSIZE),A
          LD      D,0
;начальный символ - 0
          LD      IX,(TREE)
;адрес буфера
AG        LD      HL,(RAW)
;адрес файла
          LD      BC,(LEN)
;длина файла
          CALL    ONE
          LD      A,D
          CP      #FF
;все символы проверены?
          JR      NC,SORT
;да - идем на сортировку.
          INC     D
;иначе - повтор для всех 256
          JR      AG
ONE       XOR     A
          LD      (PEP),A
          LD      (PEP+1),A
SEEK      LD      A,(HL)
          CP      D
          JR      NZ,NXT
          PUSH    HL
          LD      HL,(PEP)
          INC     HL
          LD      (PEP),HL
          POP     HL
NXT       LD      A,B
          OR      C
          JR      Z,EOF
          DEC     BC
          INC     HL
          JR      SEEK
EOF       LD      HL,(PEP)
          LD      A,H
          OR      L
          RET     Z
          LD      (IX+0),D
          LD      (IX+1),L
          LD      (IX+2),H
          LD      BC,3
          ADD     IX,BC
          LD      HL,TSIZE
          INC     (HL)
          RET

;Процедура сортировки символов

SORT      LD      A,(TSIZE)
          LD      B,A
PS2       LD      IX,(TREE)
          LD      A,(TSIZE)
          LD      C,A
PS1       LD      D,(IX+2)
          LD      E,(IX+1)
          LD      H,(IX+5)
          LD      L,(IX+4)
          AND     A
          SBC     HL,DE
          JR      C,NOPF
          PUSH    BC
          LD      A,(IX+3)
          LD      B,(IX+0)
          LD      (IX+0),A
          LD      (IX+3),B
          LD      A,(IX+4)
          LD      B,(IX+1)
          LD      (IX+1),A
          LD      (IX+4),B
          LD      A,(IX+5)
          LD      B,(IX+2)
          LD      (IX+2),A
          LD      (IX+5),B
          POP     BC
NOPF      LD      DE,3
          ADD     IX,DE
          DEC     C
          JR      NZ,PS1
          DJNZ    PS2

;формирование таблицы

FORM      LD      A,(TSIZE)
          LD      IX,(TREE)
          LD      HL,(TREE)
          LD      B,A
ALL       LD      A,(IX+3)
          INC     HL
          LD      (HL),A
          LD      DE,3
          ADD     IX,DE
          LD      A,B
;вместо DJNZ!
          AND     A
          RET     Z
          DEC     B
          JR      ALL

;переменные:

RAW       DW  0 ;адрес файла
TREE      DW  0 ;адрес буфера
LEN       DW  0 ;длина файла
PEP       DW  0 ;рабочая пере-
                ;менная
TSIZE     DB  0 ;размер таблицы,
;причем если TSIZE=0, то
;размер - 1 байт.
2
   Теперь немного о странном на-
чальном  значении  TSIZE  -  #FF
(-1). Логичнее, казалось бы, ус-
тановка TSIZE в 0.  Однако, если
в файле будет содержаться макси-
мум - 256 различных символов, то
TSIZE, установленный в 0, на вы-
ходе даст тоже 0, поэтому прихо-
дится так изворачиваться.
   И еще: процедура компрессора,
преобразующая код символа в  его
номер в таблице, тоже может сра-
ботать ошибочно при TSIZE = max,
поэтому придется в ней DJNZ  за-
менить на:

          LD      A,B
          AND     A
          JR      NZ,XXXX

   Это, конечно, если Вы не наш-
ли в вашей процедуре лучший  ме-
тод. А вообще-то можно  обойтись
без ухищрений: надо размер TSIZE
определить не в байт, а в слово.
Тогда, правда, придется  жертво-
вать дополнительной  регистровой
парой, а значит, неизбежны  вся-
кие  PUSH'ы и POP'ы, замедляющие
и без того медленную  программу.
Кстати, о скорости. В моей  про-
цедуре компрессии большую  часть
времени  отнимало    составление
таблицы.  Очень  много   времени
уходит  на  сортировку,  поэтому
метод, предложенный  выше, жела-
тельно заменить на более быстрый
(типа алгоритмов  Шелла  и  "пу-
зырька". Советую прочитать в  ZX
РЕВЮ N5, 1994 статью  о  методах
сортировки).

   Прим. ред.: Одним из  наиболее  быстрых
способов сортировки является  метод  "быс-
трой сортировки Хоара".

          *   *   *




Другие статьи номера:

TR-DOS для начинающих - Окончание.

Компьютерная новелла - Prince of Persia.

Компьютерная новелла - Лазерная бригада (по игре Laser Squad).

Перекресток драконов - Игра Rapscallion.

Перекресток драконов - Игра The Runes of Zendos.

Перекресток драконов - Игра The Saga.

Перекресток драконов - Игра Witch's Cauldron.

Перекресток драконов - Создаём Адвентюру. Обзор редакторов.

Перекресток драконов - Создаём словарь к Адвентюрной игре.

Программы, которые мы выбираем - Возможные последствия использования недокументированных команд.

Программы, которые мы выбираем - О замеченных шероховатостях в работе некоторых программ и пожелания к следующим версиям.

Программы, которые мы выбираем - Предложение ко всем авторам программ, печатающих дамп памяти. Программистам, использующим защиту дисков от копирования.

Программы, которые мы выбираем - Несколько предложений по усовершенствованию ассемблера.

Программы, которые мы выбираем - Предложения по доработке ZX Word v2.5.

Программы, которые мы выбираем - Программа "Эмулятор Спектрума" v1.2.

Программы, которые мы выбираем - Что хотелось бы иметь в идеальном ассемблере.

Ретро - 40 лучших процедур: Копирование данных в памяти.

Ретро - 40 лучших процедур: Обмен токена.

Ретро - 40 лучших процедур: Определение адреса БЕЙСИК-строки.

Ретро - 40 лучших процедур: Определение длины БЕЙСИК-программы.

Ретро - 40 лучших процедур: Определение размера свободной памяти.

Ретро - 40 лучших процедур: Поиск и замещение строки.

Ретро - 40 лучших процедур: Поиск подстроки.

Ретро - 40 лучших процедур: Поиск строки.

Ретро - 40 лучших процедур: Составление списка переменных.

Ретро - 40 лучших процедур: увеличение и копирование экрана.

Ретро - 40 лучших процедур: Удаление REM-строк.

Ретро - 40 лучших процедур: Удаление блока программы.

Советы экспертов - Игра Fredloader.

Советы экспертов - Игра Robin of Sherwood: The Touchstones of Rhianon.

Советы экспертов - Игра Scorpions: Die Machines.

Советы экспертов - Игра Terropods.

Страничка iS-DOS - Описание рестартов системы IS DOS.

Форум - Алгоритм распознавания символов.

Форум - Время выполнения недокументированных команд процессора Z80.

Форум - Концепция экрана высокого цветового разрешения.

Форум - Несколько Pokes к играм. Программа Hacman96.

Форум - По поводу новых DOS и BIOS для Спектрума.

Форум - Программа Multicolor на любой модели компьютера. Использование 2-го экрана для Multicolor'а. Демонстрация текста. Электронные журналы.

Форум - Проект ZX Config.

Форум - Усовершенствование Art Studio. Идеи относительно компрессии файлов.

Форум - Эмулятор ZX Spectrum на IBM. По поводу шестнадцатеричной системы счисления. Программа ZX-Stars. Странности в Elita

Форум - Эффекты на бордюре и Multicolor.

Читатель-читателю - ZX Spectrum 128 - новые возможности, новые проблемы.

Читатель-читателю - Группа 'Light'. Спектрум и экспертная система.

Читатель-читателю - Драйвер принтера для Scorpion'а.

Читатель-читателю - Печать чисел в различных системах счисления.

Читатель-читателю - Программирование аркадной игры со скроллингом экрана.

Читатель-читателю - Процедура печати меток ассемблера XAS для монитора-отладчика STS 4.3.

Этюды - Атрибутная бегущая строка. "Гасилка" экрана. Упрощенный вариант процедуры "Занавес". Процедура гащения картинки. Процедура проявления картинки по точкам.

Этюды - Графический эффект "цветные полосы".

Этюды - Драйвер экрана для печати по 64 символа в строке.

Этюды - Комплект защит загрузчиков.

Этюды - Обращение к диску в режиме IM 2. Работа с диском нестандартного формата.

Этюды - Печать символа, увеличенного в 8 раз. Программа "наливания" экрана. Процедура гашения экрана по точкам. Очистка экрана как в Terminator'е. Поиск последовательности символов в памяти. Система перекодировки символьного набора.

Этюды - Программа - каталогизатор дисков.

Этюды - Программа вывода значений амплитуды каналов муз. сопроцессора на бордюр.

Этюды - Программа вывода картинки.

Этюды - Программа зажигания спрайта.

Этюды - Программа очистки заданного окна экрана.

Этюды - Программа сортировки массива по возрастанию. Процедура заполнения экрана заданным атрибутом. Процедура проявления картинки. Эффект летящих навстречу звезд. "Душ", идущий из верхнего левого угла экрана. Процедура "осыпания" картинки по пиксельным линиям. Программа "вытягивания" картинки под углом в 45 градусов. Три процедуры "Scroll".

Этюды - Процедура печати чисел.

Этюды - Процедура прорисовки символа с помощью атрибутов.

Этюды - Процедура проявления картинки. Fade-OUT эффект (картинка уходит за края экрана). Графический эффект "Фонтан". Fade-OUT эффект, имитирующий выключение телевизора. Процедура "зажигания" картинки. Программа плавной прорисовки картинки.

Этюды - Процедура рисования линии.

Этюды - Процедура составления оптимальной таблицы символов.

Этюды - Скроллинг строк текста в заданном окне. Атрибутный скроллер. Диагональный скроллинг.

Этюды - Спрайтовый скроллер. Процедуры проявления экрана.

Этюды - Укороченная процедура индикации амплитуды каналов муз. сопроцессора. Способ вычитания константы из регистровой пары HL.

Этюды - Формула для вычисления дня недели.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Сплетни SCEN'ы - Новости.
Реклама - Реклама и объявления.
Реклама - Реклама и объявления ...

В этот день...   19 сентября