PC World 1997 November/PCWorld_1997-11_cd.bin/software/sharware/utility/PACKERS/LZH/LHASRC.EXE/MAKETRE_.ASM

Assembly Source File | 1991-02-11 | 6KB | 311 lines

;***********************************************
;    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