(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 статью о методах
сортировки).
Прим. ред.: Одним из наиболее быстрых
способов сортировки является метод "быс-
трой сортировки Хоара".
* * *
