Garbo/Garbo.cdr/pc/source/mssup201.arc/LZD.ASM

Assembly Source File | 1988-08-25 | 9.3 KB | 449 lines

    title    Lempel-Ziv Decompressor

;Derived from Tom Pfau's public domain assembly code.
;The contents of this file are hereby released to the public domain.
;                                   -- Rahul Dhesi 1988/08/24

UNBUF_IO    equ    1        ;use unbuffered I/O

public    _lzd,memflag,docrc

    include    asmconst.ai
    include macros.ai

;Hash table entry
hash_rec    struc
next    dw    ?            ; prefix code
char    db    ?            ; suffix char
hash_rec    ends

extrn    _addbfcrc:near            ;External C function for CRC

ifdef    UNBUF_IO
extrn    _read:near
extrn    _blockwrite:near
else
extrn    _zooread:near
extrn    _zoowrite:near
endif

;Declare segments
_text    segment byte public 'code'
_text    ends

dgroup    group    _data
    assume ds:dgroup,es:dgroup
_data    segment word public 'data'
extrn    _out_buf_adr:word        ;address of C output buffer
extrn    _in_buf_adr:word        ;address of C input buffer

memflag        db    0        ;Memory allocated?  flag
save_bp        dw    ?
save_sp        dw    ?

input_handle    dw    ?
output_handle    dw    ?
hash_seg    dw    ?
cur_code    dw    ?
old_code    dw    ?
in_code        dw    ?
free_code    dw    first_free

;Note:  for re-entrancy, following 3 must be re-initialized each time
stack_count    dw    0
nbits        dw    9
max_code    dw    512

fin_char    db    ?
k        db    ?
masks        dw    1ffh,3ffh,7ffh,0fffh,1fffh

;Note:  for re-entrancy, following 2 must be re-initialized each time
bit_offset    dw    0
output_offset    dw    0
_data    ends

memory    segment para public 'memory'
hash    label    hash_rec
memory    ends

call_index macro
    mov    bp,bx            ;bx = bx * 3 (3 byte entries)
    shl    bx,1            ;bp = bx
    add    bx,bp            ;bx = bx * 2 + bp
    endm

call_write_char macro
    local    wc$1
    mov    di,output_offset    ;Get offset in buffer
    cmp    di,outbufsiz        ;Full?
    jb    wc$1            ;no
    call    write_char_partial
    sub    di,di            ;so we add zero in next statement
wc$1:    add    di,[_out_buf_adr]    ;di <- buffer address + di
    stosb                ;Store char
    inc    output_offset        ;Increment number of chars in buffer
    endm

add_code macro
    mov    bx,free_code        ;Get new code
    ;call    index            ;convert to address
    call_index
    push    es            ;point to hash table
    mov    es,hash_seg
    mov    al,k            ;get suffix char
    mov    es:[bx].char,al        ;save it
    mov    ax,old_code        ;get prefix code
    mov    es:[bx].next,ax        ;save it
    pop    es
    inc    free_code        ;set next code
    endm

;Start coding
_text    segment
    assume    cs:_text,ds:dgroup,es:dgroup,ss:nothing

write_char_partial proc    near
    push    cx
    mov    cx,di            ;byte count
    call    write_block
    pop    cx
    mov    output_offset,0        ;Restore buffer pointer
    ret
write_char_partial endp

_lzd    proc    near

    push    bp            ;Standard C entry code
    mov    bp,sp
    push    di
    push    si

    push    ds            ;Save ds to be sure
    mov    [save_bp],bp        ;And bp too!
    mov    bx,ds
    mov    es,bx

;Get two parameters, both integers, that are input file handle and
;output file handle
    mov    ax,[bp+4]
    mov    [input_handle],ax
    mov    ax,[bp+6]
    mov    [output_handle],ax

    call    decompress        ;Compress file & get status in AX

    mov    bp,[save_bp]        ;Restore bp
    pop    ds
    pop    si            ;Standard C return code
    pop    di
    mov    sp,bp
    pop    bp
    ret
_lzd    endp

;Note:  Procedure decompress returns AX=0 for successful decompression and
;    AX=1 for I/O error and AX=2 for malloc failure.
decompress    proc    near
    mov    [save_sp],sp        ;Save SP in case of error return

;Initialize variables -- required for serial re-entrancy
    mov    [nbits],9
    mov    [max_code],512
    mov    [free_code],first_free
    mov    [stack_count],0
    mov    [bit_offset],0
    mov    [output_offset],0

    test    memflag,0ffH        ;Memory allocated?
    jnz    gotmem            ;If allocated, continue
    malloc    <((maxmax * 3) / 16 + 20)>    ;allocate it
    jnc    here1
    jmp    MALLOC_err
here1:
    mov    hash_seg,ax        ;Save segment address of mem block
    mov    memflag,0ffh        ;Set flag to remind us later
gotmem:

    mov    ax,inbufsiz
    push    ax            ;byte count
    push    _in_buf_adr        ;buffer address
    push    input_handle        ;zoofile
ifdef    UNBUF_IO
    call    _read
else
    call    _zooread
endif
    add    sp,6

    cmp    ax,-1
    jz    IO_err            ;I/O error
here2:

l1:    call    read_code        ;Get a code
    cmp    ax,eof            ;End of file?
    jne    l2            ;no
    cmp    output_offset,0        ;Data in output buffer?
    je    OK_ret            ;no
    mov    cx,[output_offset]    ;byte count
    call    write_block        ;write block of cx bytes
OK_ret:
    xor    ax,ax            ;Normal return -- decompressed
    ret                ;done
IO_err:
    mov    ax,2            ;I/O error return
    mov    sp,[save_sp]        ;Restore stack pointer
    ret

MALLOC_err:
    mov    ax,1            ;Malloc error return
    mov    sp,[save_sp]        ;Restore stack pointer
    ret

l2:    cmp    ax,clear        ;Clear code?
    jne    l7            ;no
    call    init_tab        ;Initialize table
    call    read_code        ;Read next code
    mov    cur_code,ax        ;Initialize variables
    mov    old_code,ax
    mov    k,al
    mov    fin_char,al
    mov    al,k
    ;call    write_char        ;Write character
    call_write_char
    jmp    l1            ;Get next code
l7:    mov    cur_code,ax        ;Save new code
    mov    in_code,ax
    mov    es,hash_seg        ;Point to hash table
    cmp    ax,free_code        ;Code in table? (k<w>k<w>k)
    jb    l11            ;yes
    mov    ax,old_code        ;get previous code
    mov    cur_code,ax        ;make current
    mov    al,fin_char        ;get old last char
    push    ax            ;push it
    inc    stack_count

;old code -- two memory references
;l11:
;    cmp    cur_code,255        ;Code or character?
;    jbe    l15            ;Char
;    mov    bx,cur_code        ;Convert code to address
;new code -- 0 or 1 memory references
    mov    ax,cur_code
l11:
    ;All paths in must have ax containing cur_code
    cmp    ax,255
    jbe    l15
    mov    bx,ax
;end code
    ;call    index
    call_index
    mov    al,es:2[bx]        ;Get suffix char
    push    ax            ;push it
    inc    stack_count
    mov    ax,es:[bx]        ;Get prefix code
    mov    cur_code,ax        ;Save it
    jmp    l11            ;Translate again
l15:
;old code
;    push    ds            ;Restore seg reg
;    pop    es
;new code
    mov    ax,ds            ;faster than push/pop
    mov    es,ax
;end code
    mov    ax,cur_code        ;Get code
    mov    fin_char,al        ;Save as final, k
    mov    k,al
    push    ax            ;Push it

;old code
;    inc    stack_count
;    mov    cx,stack_count        ;Pop stack
;new code -- slightly faster because INC of memory is slow
    mov    cx,stack_count
    inc    cx
    mov    stack_count,cx
;end code
    jcxz    l18            ;If anything there
l17:    pop    ax
    ;call    write_char
    call_write_char
    loop    l17

;old code
;l18:
;    mov    stack_count,cx        ;Clear count on stack
;new code -- because stack_count is already zero on earlier "jcxz l18"
    mov    stack_count,cx
l18:
;end code

    ;call    add_code        ;Add new code to table
    add_code
    mov    ax,in_code        ;Save input code
    mov    old_code,ax
    mov    bx,free_code        ;Hit table limit?
    cmp    bx,max_code
    jb    l23            ;Less means no
    cmp    nbits,maxbits        ;Still within maxbits?
    je    l23            ;no (next code should be clear)
    inc    nbits            ;Increase code size
    shl    max_code,1        ;Double max code
l23:    jmp    l1            ;Get next code
decompress    endp

read_code    proc    near

;old code
;    mov    ax,bit_offset        ;Get bit offset
;    add    ax,nbits        ;Adjust by code size
;    xchg    bit_offset,ax        ;Swap
;    mov    dx,ax            ;dx <- ax
;new code
    mov    ax,bit_offset
    mov    dx,ax            ;dx <- bit_offset
    add    ax,nbits
    mov    bit_offset,ax
    mov    ax,dx
;end code

    shr    ax,1
    shr    ax,1
    shr    ax,1            ;ax <- ax div 8
    and    dx,07            ;dx <- ax mod 8
    cmp    ax,inbufsiz-3        ;Approaching end of buffer?
    jb    rd0            ;no
    push    dx            ;Save offset in byte
    add    dx,nbits        ;Calculate new bit offset
    mov    bit_offset,dx
    mov    cx,inbufsiz
    mov    bp,ax            ;save byte offset
    sub    cx,ax            ;Calculate bytes left
    add    ax,_in_buf_adr
    mov    si,ax
    mov    di,_in_buf_adr
rep    movsb                ;Move last chars down

    push    bp            ;byte count
    push    di            ;buffer address
    push    input_handle        ;zoofile
ifdef    UNBUF_IO
    call _read
else
    call    _zooread
endif
    add    sp,6

    cmp    ax,-1
    jnz    here4
    jmp    IO_err            ;I/O error

here4:
    xor    ax,ax            ;Clear ax
    pop    dx            ;Restore offset in byte
rd0:
    add    ax,_in_buf_adr
    mov    si,ax
    lodsw                ;Get word
    mov    bx,ax            ;Save in AX
    lodsb                ;Next byte
    mov    cx,dx            ;Offset in byte
    jcxz    rd2            ;If zero, skip shifts
rd1:    shr    al,1            ;Put code in low (code size) bits of BX
    rcr    bx,1
    loop    rd1
rd2:    mov    ax,bx            ;put code in ax
    mov    bx,nbits        ;mask off unwanted bits
    sub    bx,9
    shl    bx,1
    and    ax,masks[bx]
    ret
read_code    endp

init_tab    proc    near
    mov    nbits,9            ;Initialize variables
    mov    max_code,512
    mov    free_code,first_free
    ret
init_tab    endp

comment #
index        proc    near
    mov    bp,bx            ;bx = bx * 3 (3 byte entries)
    shl    bx,1            ;bp = bx
    add    bx,bp            ;bx = bx * 2 + bp
    ret
index        endp
#end comment

docrc    proc    near
;On entry, ax=char count, dx=buffer address.
;Do crc on character count, in buffer.
;****** Update CRC value -- call external C program
    ;External program is:    addbfcrc(buffer, count)
    ;            char *buffer;
    ;            int count;

    push    ax        ;SAVE AX
    push    bx        ;SAVE BX
    push    cx
    push    dx

    push    ax        ;param 2: char count
    push    dx        ;param 1: buffer address
    call    _addbfcrc
    add    sp,4        ;Restore 2 params from stack

    pop    dx
    pop    cx
    pop    bx        ;RESTORE BX
    pop    ax        ;RESTORE AX
    ret
docrc    endp

write_block proc near
;Input:  CX=byte count to write
    push    ax
    push    bx
    push    cx
    push    dx
    push    si            ;may not be necessary to save si & di
    push    di

    push    cx            ;save count

    push    cx            ;count
    push    _out_buf_adr        ;buffer
    push    output_handle        ;zoofile
ifdef    UNBUF_IO
    call    _blockwrite
else
    call    _zoowrite
endif
    add    sp,6

    pop    cx            ;restore count

    ;ax = actual number of bytes written
    cmp    ax,cx            ;all bytes written?
    je    written            ;if yes, OK
    jmp    IO_err
written:
    mov    dx,_out_buf_adr
    call    docrc            ;do crc on ax bytes in buffer dx
    mov    output_offset,0        ;restore buffer ptr to zero

    pop    di
    pop    si
    pop    dx
    pop    cx
    pop    bx
    pop    ax
    ret
write_block endp

_text    ends

    end