Category : C Source Code
Archive   : LHA211S.ZIP
Filename : MAKETRE_.ASM

;***********************************************
; 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 , B
mov bx, depth
$_if , 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
shl si, 1
$_break , , A
mov di, heap[si]
mov ax, ds:[bp + di]
$_if , B, AND
mov di, heap[si + 2]
mov dx, ds:[bp + di]
$_c , A
mov ax, dx
add si, 2
$_endif
$_break , , 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 , Z

sub bx, offset DGROUP:heap
mov heapsize, bx
$_if , 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>, Z
mov di, code
$_do
mov si, heap[2]
$_if , 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 , 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 , 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
add dx, [si]
$_if , NZ
sub len_cnt[16 * 2], dx
mov cx, dx
$_do
mov di, offset DGROUP:len_cnt + 15 * 2
$_while , E
sub di, 2
$_enddo
dec word ptr [di]
add word ptr [di + 2], 2
$_until
$_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
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
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
;---------------------------------------------------------------
pop ax
return:
shr ax, 1
pop bp
pop di
pop si
pop dx
pop cx
ret
make_tree_ endp
TEXT ends
end</sub>