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

Studies - The procedure for making optimal symbol table.

(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.


          *