(C) M. Tatarinov, Solikamsk
I want to offer the procedure,
which will be useful to the creators of compressors using
Huffman (bit compression).
As is known, this method
requires a reference table of characters. The smaller the
number of characters in the table, the require less bits to
encode the symbol. This procedure is for each File optimal
table.
The program works as follows:
as follows: first of all calculated coefficients of the
recurrence each character in the file, then the coefficients
are sorted and IDs of these coefficients are packed into a
table.
Program to work requires
buffer, the maximum size is equal to 3 * 256 = 768 bytes (ie,
If there are 256 different characters. 3 - is the size of one
record in the buffer). The table will be written in the
beginning of the buffer. 140.
; Program to compile
; Table
; (C) Mat Software'96
MKTREE LD A, # FF
LD (TSIZE), A
LD D, 0
; Start symbol - 0
LD IX, (TREE)
; Buffer address
AG LD HL, (RAW)
; Address of the file
LD BC, (LEN)
The length of the file
CALL ONE
LD A, D
CP # FF
And all the characters tested?
JR NC, SORT
Yea - go to the sorting.
INC D
; Otherwise - repeat for all 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
; Procedure for collation
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
, Forming a table
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
And instead DJNZ!
AND A
RET Z
DEC B
JR ALL
; Variables:
RAW DW 0; address of the file
TREE DW 0; buffer address
LEN DW 0; length of the file
PEP DW 0; operating variables
; Mennaya
TSIZE DB 0; size table
, And if TSIZE = 0, then
; Size - 1 bytes.
2
Now a bit of a strange initial value TSIZE - # FF
(-1). Logical, seemingly setting TSIZE to 0. However, if
the file will contain the maximum - 256 different characters,
TSIZE, set to 0, the output will also 0, so you have to dodge
so.
And more: the procedure compressor
converts the character code in its
number in the table, too, may work incorrectly when TSIZE = max,
so you'll need it DJNZ replaced by:
LD A, B
AND A
JR NZ, XXXX
This, of course, if you do not find in your procedure, the
best method. Generally speaking, you can do no tricks: it is
necessary size TSIZE not be determined in bytes, and in word.
Then, however, have to sacrifice an extra register
pair and, therefore, inevitable, and all sorts of PUSH'y POP'y
slowing down already a slow program.
Speaking of speed. In my procedure, most of the compression
time consuming preparation
table. A lot of time
spent on sorting, so
The method proposed above, it is desirable to replace a more
rapid (Such as algorithms, Shell and the "bubble." Advise you
to read in the ZX REVIEW N5, 1994 article on the methods
sorting).
Ca. Ed.: One of the fastest
ways of sorting is the method of "quicksort Hoare.
*
