;***********************************************
;	dhuf_.asm -- Dynamic Huffman routine
;***********************************************
			page	0, 128

include	amscls.inc
$_init	GEN

CGROUP  GROUP   TEXT
DGROUP  GROUP   DATA,BSS

TEXT    segment byte public 'CODE'
        assume  cs:CGROUP, ds:DGROUP, ss:DGROUP
TEXT    ends

DATA    segment word public 'DATA'
DATA    ends

THRESHOLD	equ		3
N_CHAR		equ		(256 + 60 - THRESHOLD + 1)
TREESIZE_C  equ		(N_CHAR * 2)
TREESIZE_P  equ		(128 * 2)
TREESIZE    equ		(TREESIZE_C + TREESIZE_P)
ROOT_C      equ		0
ROOT_P      equ		TREESIZE_C

BSS     segment word public 'DATA'
        public  node_
node_			dw      N_CHAR + 128 dup (?)
        public  total_p_
total_p_		dw		1 dup (?)

BSS     ends

BSS			segment word public 'DATA'
start_		dw		1 dup(?)
end_		dw		1 dup(?)
BSS			ends

DATA    segment word public 'DATA'
DATA    ends

BSS     segment word public 'DATA'
        public  n_max_
n_max_			dw		1 dup (?)
        public  avail_
avail_  		dw      1 dup (?)
        public  n1_
n1_     		dw      1 dup (?)
        public  most_p_
most_p_ 		dw      1 dup (?)
        public  nn_
nn_     		dw      1 dup (?)
        public  nextcount_
nextcount_      dw      2 dup (?)

BSS     ends

TEXT    segment byte public 'CODE'

;
;void start_c_dyn(void)
;

        public  start_c_dyn_
start_c_dyn_	proc	near
	push    cx
	push    dx
	push    si
	push	di
	mov		bx, 512
	mov		ax, maxmatch_
	add		ax, 256 - 2
	$_if <cmp n_max_, ax>, B
		mov		bx, n_max_
		dec		bx
	$_endif
	mov		n1_, bx
	push	ds
	pop		es
	cld
	xor		ax, ax
	mov		cx, TREESIZE_C
	mov		di, offset DGROUP:block_
	rep		stosw
	mov		cx, TREESIZE_C
	mov		di, offset DGROUP:stock_
	$_do
		stosw
		inc		ax
		inc		ax
	$_until <LOOP>
	mov		di, offset DGROUP:node_
	mov		bx, n_max_
	mov		cx, bx
	dec		bx
	shl		bx, 1
	mov		edge_[2], bx
	shl		bx, 1
	push	bx
	mov		ax, 1
	mov		dx, 0ffffh
	$_do
		mov		freq_[bx], ax
		mov		block_[bx], 2
		mov		child_[bx], dx
		mov		[di], bx
		dec		dx
		dec		dx
		dec		bx
		dec		bx
		inc		di
		inc		di
	$_until <LOOP>
	mov     word ptr DGROUP:[avail_], 4
	pop		di
	$_do
		mov		ax, freq_[di]
		add		ax, freq_[di - 2]
		mov		freq_[bx], ax
		mov		child_[bx], di
		mov		parent_[di], bx
		mov		parent_[di - 2], bx
		$_if <cmp ax, freq_[bx + 2]>, E
			mov		si, block_[bx + 2]
		$_else
			mov		si, avail_
			add		avail_, 2
			mov		si, stock_[si]
		$_endif
		mov		block_[bx], si
		mov		edge_[si], bx
		sub		di, 4
		dec		bx
		dec		bx
	$_until , S
	pop		di
	pop		si
	pop		dx
	pop		cx
	ret
start_c_dyn_	endp


;
;static void start_p_dyn(void)
;

start_p_dyn_	proc	near
	push	cx
	mov     freq_[ROOT_P * 2], 1
	mov     child_[ROOT_P * 2], not (N_CHAR * 2)
	mov     node_[N_CHAR * 2], ROOT_P * 2
	mov		bx, avail_
	add		avail_, 2
	mov		bx, stock_[bx]
	mov		block_[ROOT_P * 2], bx
	mov		edge_[bx], ROOT_P * 2
	mov		most_p_, ROOT_P * 2
	mov		ax, 1
	mov		cx, dicbit_
	shl		ax, cl
	mov		nn_, ax
	xor		ax, ax
	mov		nextcount_, 64
	mov		nextcount_[2], ax
	mov		total_p_, 0
	pop		cx
	ret
start_p_dyn_	endp


;
;void decode_start_dyn(void)
;

			public  decode_start_dyn_
decode_start_dyn_	proc	near
	mov		n_max_, 286
	mov		maxmatch_, 256
	call	init_getbits_
	call    start_c_dyn_
	call    start_p_dyn_
	ret
decode_start_dyn_	endp


;
;static void reconst(int start, int end)
;

			public	reconst_
reconst_	proc	near
	push	cx
	push	dx
	push	si
	push	di
	mov		start_, ax
	mov		end_, bx
	mov		si, ax
	mov		di, ax
	$_while <cmp si, end_>, L
		mov		bx, child_[si]
		$_if <or bx, bx>, L
			mov		ax, freq_[si]
			inc		ax
			shr		ax, 1
			mov		freq_[di], ax
			mov		child_[di], bx
			inc		di
			inc		di
		$_endif
		mov		bx, block_[si]
		$_if <cmp edge_[bx], si>, E
			sub		avail_, 2
			mov		ax, bx
			mov		bx, avail_
			mov		stock_[bx], ax
		$_endif
		inc		si
		inc		si
	$_enddo
	dec		di
	dec		di
	dec		si
	dec		si
	mov		bx, si
	dec		bx
	dec		bx
	$_while <cmp si, start_>, GE
		$_while <cmp si, bx>, GE
			mov		ax, freq_[di]
			mov		freq_[si], ax
			mov		ax, child_[di]
			mov		child_[si], ax
			dec		di
			dec		di
			dec		si
			dec		si
		$_enddo
		mov		ax, freq_[bx]
		add		ax, freq_[bx + 2]
		push	bx
		mov		bx, start_
		$_while <cmp ax, freq_[bx]>, B
			inc		bx
			inc		bx
		$_enddo
		$_while <cmp di, bx>, GE
			mov		dx, freq_[di]
			mov		freq_[si], dx
			mov		dx, child_[di]
			mov		child_[si], dx
			dec		si
			dec		si
			dec		di
			dec		di
		$_enddo
		mov		freq_[si], ax
		pop		bx
		inc		bx
		inc		bx
		mov		child_[si], bx
		dec		si
		dec		si
		sub		bx, 6
	$_enddo
	xor		ax, ax
	mov		si, start_
	$_while <cmp si, end_>, L
		mov		di, child_[si]
		$_if <or di, di>, S
			not		di
			mov		node_[di], si
			not		di
		$_else
			mov		parent_[di], si
			mov		parent_[di - 2], si
		$_endif
		mov		dx, freq_[si]
		$_if <cmp dx, ax>, E
			mov		block_[si], bx
		$_else
			mov		bx, avail_
			add		avail_, 2
			mov		bx, stock_[bx]
			mov		block_[si], bx
			mov		edge_[bx], si
			mov		ax, dx
		$_endif
		inc		si
		inc		si
	$_enddo
	pop		di
	pop		si
	pop		dx
	pop		cx
	ret
reconst_	endp

;
;	static int swap_inc(int p)
;

			public	swap_inc_
swap_inc_	proc	near
;	push	dx
;	push	si
;	push	di
	mov		si, ax
	mov		bx, block_[si]
	mov		di, edge_[bx]
	$_if <cmp di, si>, NE
		push	bx
		mov		bx, child_[si]
		mov		dx, child_[di]
		mov		child_[si], dx
		mov		child_[di], bx
		$_if <or bx, bx>, NS
			mov		parent_[bx], di
			mov		parent_[bx - 2], di
		$_else
			not		bx
			mov		node_[bx], di
		$_endif
		mov		bx, dx
		$_if <or bx, bx>, NS
			mov		parent_[bx], si
			mov		parent_[bx - 2], si
		$_else
			not		bx
			mov		node_[bx], si
		$_endif
		mov		si, di
		pop		bx
		jmp		Adjust
	$_endif
	$_if <cmp bx, block_[si + 2]>, E
Adjust:
		add		edge_[bx], 2
		inc		freq_[si]
		mov		ax, freq_[si]
		$_if <cmp ax, freq_[si - 2]>, E
			mov		ax, block_[si - 2]
			mov		block_[si], ax
		$_else
			mov		bx, avail_
			add		avail_, 2
			mov		bx, stock_[bx]
			mov		block_[si], bx
			mov		edge_[bx], si
		$_endif
	$_else
		inc		freq_[si]
		mov		ax, freq_[si]
		$_if <cmp ax, freq_[si - 2]>, E
			sub		avail_, 2
			mov		di, avail_
			mov		stock_[di], bx
			mov		ax, block_[si - 2]
			mov		block_[si], ax
		$_endif
	$_endif
	mov		ax, parent_[si]
;	pop		di
;	pop		si
;	pop		dx
	ret
swap_inc_	endp


;
;	static void update_c(int p)
;

			public	update_c_
update_c_	proc	near
	$_if <cmp freq_[ROOT_C * 2], 8000h>, E
		push	ax
		mov		bx, n_max_
		shl		bx, 1
		dec		bx
		shl		bx, 1
		xor		ax, ax
		call	reconst_
		pop		ax
	$_endif
	inc		freq_[ROOT_C * 2]
	mov		bx, ax
	mov		ax, node_[bx]
	$_do
		call	swap_inc_
	$_until <cmp ax, ROOT_C * 2>, E
	ret
update_c_	endp


;
;	static void update_p(int p)
;

			public	update_p_
update_p_	proc	near
	$_if <cmp total_p_, 8000h>, E
		push	ax
		mov		bx, most_p_
		inc		bx
		inc		bx
		mov		ax, ROOT_P * 2
		call	reconst_
		mov		ax, 0ffffh
		xchg	ax, freq_[ROOT_P * 2]
		mov		total_p_, ax
		pop		ax
	$_endif
	mov		bx, ax
	mov		ax, node_[bx + N_CHAR * 2]
	$_while <cmp ax, ROOT_P * 2>, NE
		call	swap_inc_
	$_enddo
	inc		total_p_
	ret
update_p_	endp


;
;	static void make_new_node(int p)
;

make_new_node_	proc	near
	push	si
	push	di
	mov		di, most_p_
	mov		bx, child_[di]
	mov		child_[di + 2], bx
	not		bx
	lea		si, [di + 2]
	mov		node_[bx], si
	mov		si, ax
	add		si, N_CHAR * 2
	not		si
	mov		child_[di + 4], si
	lea		si, [di + 4]
	mov		child_[di], si
	mov		bx, freq_[di]
	mov		freq_[di + 2], bx
	mov		freq_[di + 4], 0
	mov		bx, block_[di]
	mov		block_[di + 2], bx
	$_if <cmp di, ROOT_P * 2>, E
		mov		freq_[ROOT_P * 2], 0ffffh
		mov		bx, block_[ROOT_P * 2]
		add		edge_[bx], 2
	$_endif
	mov		parent_[di + 2], di
	mov		parent_[di + 4], di
	add		di, 4
	mov		most_p_, di
	mov		bx, ax
	mov		node_[bx + N_CHAR * 2], di
	mov		bx, avail_
	add		avail_, 2
	mov		bx, stock_[bx]
	mov		block_[di], bx
	mov		edge_[bx], di
	call	update_p_
	pop		di
	pop		si
	ret
make_new_node_	endp


;
;	static void encode_c_dyn(int c)
;

encode_c_dyn_	proc	near
	push	cx
	push	dx
	push	si
;	push	di
;	mov		di, -1
;	$_if <cmp ax, n1_>, AE
;		mov		di, ax
;		mov		ax, n1_
;		sub		di, ax
;	$_endif
	shl		ax, 1
	mov		bx, ax
	mov		bx, node_[bx]
	xor		dx, dx
	mov		cx, dx
	$_do
		mov		si, bx
		shr		bx, 1
		shr		bx, 1
		rcr		dx, 1
		rcr		ch, 1
		inc		cx
		mov		bx, parent_[si]
	$_until <cmp bx, ROOT_C * 2>, E
	mov		si, ax
	$_if <cmp cl, 16>, A
		mov		bx, dx
		mov		al, 16
		sub		cl, al
		call	putcode_
		mov		dx, cx
		xor		dl, dl
	$_endif
	mov		ax, cx
	mov		bx, dx
	call	putcode_
;	$_if <or di, di>, NS
;		mov		bx, di
;		mov		ax, 8
;		call	putbits_
;	$_endif
	mov		ax, si
	call	update_c_
;	pop		di
	pop		si
	pop		dx
	pop		cx
	ret
encode_c_dyn_	endp

;
;	ushort decode_c_dyn(void)
;

        public  decode_c_dyn_
decode_c_dyn_	proc	near
	push	cx
	push	dx
	push	si
	push	di
	mov		si, child_[ROOT_C * 2]
	mov		cx, 16
	mov		bx, bitbuf_
	$_do
		$_if <dec cx>, S
			mov		ax, 16
			mov		cx, 15
			call	fillbuf_
			mov		bx, bitbuf_
		$_endif
		shl		bx, 1
		sbb		ax, ax
		shl		ax, 1
		add		si, ax
		mov		si, child_[si]
	$_until <or si, si>, LE
	mov		al, 16
	sub		al, cl
	call	fillbuf_
	not		si
	mov		ax, si
	push	si
	call	update_c_
	pop		si
	shr		si, 1
	$_if <cmp si, n1_>, E
		mov		ax, 8
		call	getbits_
		add		si, ax
	$_endif
	mov		ax, si
	pop		di
	pop		si
	pop		dx
	pop		cx
	ret
decode_c_dyn_	endp


;
;	ushort decode_p_dyn(void)
;

        public  decode_p_dyn_
decode_p_dyn_	proc	near
	push	cx
	push	dx
	push	si
	push	di
	$_while <cmp nextcount_ + 2, 0>, E, AND
	mov		ax, nextcount_
	$_c <cmp count_, ax>, G
		mov		cl, 6 - 1
		shr		ax, cl
		call	make_new_node_
		add		nextcount_, 64
		mov		ax, nextcount_
		$_if <cmp ax, nn_>, AE
			mov		ax, 0ffffh
			mov		nextcount_, ax
			mov		nextcount_ + 2, ax
		$_endif
	$_enddo
	mov		si, child_[ROOT_P * 2]
	mov		cx, 16
	mov		bx, bitbuf_
	$_while <or si, si>, G
		$_if <dec cx>, S
			mov		ax, 16
			mov		cx, 15
			call	fillbuf_
			mov		bx, bitbuf_
		$_endif
		shl		bx, 1
		sbb		ax, ax
		shl		ax, 1
		add		si, ax
		mov		si, child_[si]
	$_enddo
	mov		al, 16
	sub		al, cl
	call	fillbuf_
	not		si
	sub		si, N_CHAR * 2
	mov		ax, si
	push	si
	call	update_p_
	mov		ax, 6
	call	getbits_
	pop		si
	mov		cl, 6 - 1
	shl		si, cl
	add		ax, si
	pop		di
	pop		si
	pop		dx
	pop		cx
	ret
decode_p_dyn_	endp


;
;	void output_dyn(int code, unsigned int pos)
;

				public	output_dyn_
output_dyn_	proc	near
	$_if <cmp ax, 100h>, AE
		push	bx
		call	encode_c_dyn_
		pop		ax
		jmp		encode_p_st0_
	$_endif
	jmp		encode_c_dyn_
output_dyn_	endp


;
;	void encode_end_dyn(void)
;

        public  encode_end_dyn_
encode_end_dyn_	proc	near
	mov		al, 7
	xor		bx, bx
	jmp		putcode_
encode_end_dyn_	endp


        EXTRN   getbits_:near
        EXTRN   fillbuf_:near
        EXTRN   putcode_:near
        EXTRN   putbits_:near
        EXTRN   init_getbits_:near
        EXTRN   encode_p_st0_:near

TEXT    ends

        EXTRN   dicbit_:word
        EXTRN   count_:word
        EXTRN   block_:word
        EXTRN   parent_:word
        EXTRN   child_:word
        EXTRN   maxmatch_:word
        EXTRN   freq_:word
        EXTRN   stock_:word
        EXTRN   edge_:word
        EXTRN   maxmatch_:word
        EXTRN   bitbuf_:word

        END