;***********************************************
;	maketree.asm -- makes Huffman tree
;***********************************************
			page	0, 128

include	amscls.inc
$_init	GEN

TEXT	segment	byte	public	'CODE'
TEXT	ends

DATA	segment word	public	'DATA'
DATA	ends

BSS		segment word	public	'DATA'
extrn	right_:word
extrn	left_:word

extrn	nchar:word
extrn	n2:word
extrn	avail_mt:word
extrn	heapsize:word
extrn	freq:word
extrn	sort:word
extrn	bitlen:word
extrn	code:word
extrn	depth:word
extrn	heap:word
extrn	len_cnt:word
extrn	start:word
extrn	weight:word
BSS		ends

DGROUP	group	DATA, BSS

TEXT	segment	byte	public	'CODE'
	assume	cs:TEXT, ds:DGROUP
;---------------------------------------------------------------
;	static void count_len(short i)  /* call with i = root */
;
;---------------------------------------------------------------
public	count_len
count_len	proc	near
	$_if <cmp bx, n2>, B
		mov		bx, depth
		$_if <cmp bx, 16 * 2>, A
			mov		bx, 16 * 2
		$_endif
		inc		len_cnt[bx]
		ret
	$_endif
	add		depth, 2
	push	bx
	mov		bx, left_[bx]
	call	count_len
	pop		bx
	push	bx
	mov		bx, right_[bx]
	call	count_len
	pop		bx
	shr		left_[bx], 1
	shr		right_[bx], 1
	sub		depth, 2
	ret
count_len	endp

;---------------------------------------------------------------
;	static void downheap(short i)
;	                          bx
;---------------------------------------------------------------
public	downheap
downheap	proc	near
	push	cx
	push	dx
	push	si
	push	di
	push	bp
	mov		si, heap[bx]
	push	si
	mov		bp, freq
	mov		cx, ds:[bp + si]
	mov		si, bx
	$_while <TRUE>
		shl		si, 1
		$_break , <cmp si, heapsize>, A
		mov		di, heap[si]
		mov		ax, ds:[bp + di]
		$_if , B, AND
			mov		di, heap[si + 2]
			mov		dx, ds:[bp + di]
		$_c  <cmp ax, dx>, A
			mov		ax, dx
			add		si, 2
		$_endif
		$_break , <cmp cx, ax>, BE
		mov		di, heap[si]
		mov		heap[bx], di
		mov		bx, si
	$_enddo
	pop		heap[bx]
	pop		bp
	pop		di
	pop		si
	pop		dx
	pop		cx
	ret
downheap	endp

;---------------------------------------------------------------
;	short make_tree(short nparm, ushort freqparm[], 
;	                         cx               bx
;	                uchar lenparm[], ushort codeparm[])
;	                           di                 ax
;---------------------------------------------------------------
public	make_tree_
make_tree_	proc	near
	push	cx
	push	dx
	push	si
	push	di
	push	bp
	mov		nchar, ax
	mov		freq, bx
	mov		bitlen, cx
	mov		code, dx
	shl		ax, 1
	mov		n2, ax
	mov		avail_mt, ax

	xor		ax, ax
	cld
	push	ds
	pop		es
	mov		di, cx
	mov		cx, nchar
	rep		stosb

	mov		cx, nchar
	mov		di, freq
	lea		dx, 2[di]
	mov		bx, offset DGROUP:heap
	jmp		make_tree_1
	$_do
		add		bx, 2
		mov		[bx], di
		sub		[bx], dx
make_tree_1:
		xor		ax, ax					; set ZERO flag
	$_until <repz scasw>, Z

	sub		bx, offset DGROUP:heap
	mov		heapsize, bx
	$_if <cmp bx, 4>, B
		mov		ax, heap[2]
		mov		di, ax
		add		di, code
		mov		word ptr [di], 0
		jmp		return
	$_endif
	shr		bx, 1
	and		bx, 0fffeh
	$_do
		push	bx
		call	downheap
		pop		bx
	$_until <sub bx, 2>, Z
	mov		di, code
	$_do
		mov		si, heap[2]
		$_if <cmp si, n2>, B
			mov		[di], si
			add		di, 2
		$_endif

		mov		bx, heapsize
		sub		heapsize, 2
		mov		ax, heap[bx]
		mov		heap[2], ax

		mov		bx, 2
		call	downheap

		mov		dx, heap[2]
		$_if <cmp dx, n2>, B
			mov		[di], dx
			add		di, 2
		$_endif

		mov		bx, avail_mt
		add		avail_mt, 2

		mov		left_[bx], si
		mov		right_[bx], dx
		mov		heap[2], bx

		mov		bp, freq
		mov		ax, [si + bp]
		mov		si, dx
		add		ax, [si + bp]
		mov		dx, bx
		add		bx, bp
		mov		[bx], ax

		mov		bx, 2
		call	downheap
	$_until <cmp heapsize, 2>, BE
	mov		bx, dx
	push	dx
;---------------------------------------------------------------
;	static void make_len(short root)
;---------------------------------------------------------------
public	make_len
make_len:
	xor		ax, ax
	mov		di, offset DGROUP:len_cnt
	mov		cx, 17
	rep		stosw
	mov		depth, ax
	call	count_len
	xor		dx, dx
	mov		cx, 15
	mov		si, offset DGROUP:len_cnt + 2
	$_do
		lodsw
		shl		ax, cl
		add		dx, ax
	$_until <LOOP>
	add		dx, [si]
	$_if , NZ
		sub		len_cnt[16 * 2], dx
		mov		cx, dx
		$_do
			mov		di, offset DGROUP:len_cnt + 15 * 2
			$_while <cmp word ptr [di], 0>, E
				sub		di, 2
			$_enddo
			dec		word ptr [di]
			add		word ptr [di + 2], 2
		$_until <LOOP>
	$_endif
	mov		di, offset DGROUP:len_cnt + 16 * 2
	mov		si, code
	mov		al, 16
	$_do
		mov		cx, [di]
		jcxz	make_len_1
		$_do
			mov		bx, [si]
			add		si, 2
			shr		bx, 1
			add		bx, bitlen
			mov		[bx], al
		$_until <LOOP>
make_len_1:
		sub		di, 2
		dec		al
	$_until , Z
;---------------------------------------------------------------
;	void make_code(short nchar, uchar bitlen[], ushort code[])
;---------------------------------------------------------------
public	make_code
make_code:
	xor		ax, ax
;;;
	mov		start, ax
	mov		weight, ax
;;;
	mov		si, offset DGROUP:len_cnt + 2
	mov		di, offset DGROUP:start + 2
	mov		bx, offset DGROUP:weight + 2
	mov		cx, 16
	$_do
		stosw
		mov		dx, [si]
		add		si, 2
		dec		cx
		shl		dx, cl
		add		ax, dx
		mov		dx, 1
		shl		dx, cl
		inc		cx
		mov		[bx], dx
		add		bx, 2
	$_until <LOOP>
	xor		bx, bx
	mov		cx, nchar
	mov		si, bitlen
	mov		di, code
	$_do
		lodsb
		shl		al, 1
		mov		bl, al
		mov		ax, start[bx]
		stosw
		mov		ax, weight[bx]
		add		start[bx], ax
	$_until <LOOP>
;---------------------------------------------------------------
	pop		ax
return:
	shr		ax, 1
	pop		bp
	pop		di
	pop		si
	pop		dx
	pop		cx
	ret
make_tree_	endp
TEXT	ends
		end