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

 Хочу предложить процедуру, которая будет полезна создателям компрессоров, использующих алгоритм Хаффмана (битовая компрессия).

  Как известно, подобный метод требует наличия справочной таблицы символов. Чем меньше будет номер символа в таблице, тем меньше потребуется бит для кодировки этого символа. Данная процедура составляет для каждого файла оптимальную таблицу.

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

  Программа для работы требует буфер, максимальный размер которого равен 3*256=768 байт (т.е., если в файле 256 различных символов. 3 - это размер одной записи в буфере). Таблица будет записана также в начало буфера. 140.

	;Программа для составления
	;таблицы


 
	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

          LD      A,B
          AND     A
          JR      NZ,XXXX