Category : OS/2 Files
Archive   : ZOO21E.ZIP
Filename : LZC.ASM

title Lempel-Ziv Compressor
; $Source: /usr/home/dhesi/zoo/RCS/lzc.asm,v $
; $Id: lzc.asm,v 1.4 91/07/07 09:36:18 dhesi Exp $

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

include asmconst.ai
include macros.ai

check_gap equ 4000 ;Check ratio every so many bits
scale_limit equ 32000 ;scale down if bitsout > scale_limit
rat_thresh equ 0ffffh ;don't reset if rat > rat_thresh

;Hash table entry
hash_rec struc
first dw ? ; First entry with this value
next dw ? ; Next entry along chain
char db ? ; Suffix char
hash_rec ends

extrn docrc:near ;Procedure for block CRC in lzd.asm

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

;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
extrn memflag:byte ;got memory? flag

save_sp dw ?

bytesin dw ? ;count of bytes read
bitsout dw ? ;count of bits written
ratio dw ? ;recent ratio
ratflag db ? ;flag to remind us to check ratio
even
bit_interval dw ? ;interval at which to test ratio

input_handle dw ?
input_seg dw ?
output_handle dw ?
output_seg dw ?
hash_seg dw ?
prefix_code dw ?
free_code dw ?
max_code dw ?
nbits dw ?
k db ?
even
bit_offset dw ?
input_offset dw 0
input_size dw 0
ifdef OS2
selector dw 0
endif
_DATA ends

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

add_code macro
local ac1,ac2,ac3
mov bx,free_code ;Get code to use
push ds ;point to hash table
mov ds,hash_seg
or di,di ;First use of this prefix?
jz ac1 ;zero means yes
mov [si].next,bx ;point last use to new entry
jmp short ac2
ac1: mov [si].first,bx ;Point first use to new entry
ac2: cmp bx,maxmax ;Have we reached code limit?
je ac3 ;equal means yes, just return

;call index ;get address of new entry
call_index ;macro for speed

mov [si].first,-1 ;initialize pointers
mov [si].next,-1
mov [si].char,al ;save suffix char
inc es:free_code ;adjust next code
ac3: pop ds ;restore seg reg
endm

read_char macro ;Macro for speed
local m$1,m$2,m$3,m$4
inc [bytesin] ;Maintain input byte count for ratio
mov di,input_offset ;Anything left in buffer?
cmp di,input_size
jb m$1 ;less means yes

mov cx,inbufsiz
call doread ;read block

cmp ax,-1
jnz m$3
jmp IO_err ;input error
m$3:
mov dx,_in_buf_adr ;for docrc
call docrc
or ax,ax ;Anything left?
jz m$2 ;zero means no, finished
mov input_size,ax ;Save bytes read
mov input_offset,0 ;Point to beginning of buffer
mov di,0
m$1:
mov si,_in_buf_adr
add si,di
lodsb ;Read it in
inc input_offset ;Adjust pointer
clc ;Success
jmp short m$4
m$2: stc ;Nothing left
m$4:
endm

;Start writing code
_TEXT segment
assume cs:_TEXT,ds:DGROUP,es:DGROUP,ss:nothing

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

push ds ;Save ds to be sure
mov bx,ds
mov es,bx

;Get two parameters, both integers, that are input file handle and
;output file handle
ifdef UNBUF_IO
mov ax,[bp+4]
mov [input_handle],ax
mov ax,[bp+6]
mov [output_handle],ax
else
mov ax,[bp+4]
mov [input_handle],ax
mov ax,[bp+6]
mov [input_seg],ax
mov ax,[bp+8]
mov [output_handle],ax
mov ax,[bp+10]
mov [output_seg],ax
endif

call compress ;Compress file
;Status received back in AX
pop ds
pop si ;Standard C return code
pop di
mov sp,bp
pop bp
ret

_lzc endp

compress proc near
mov [save_sp],sp ;Save SP in case of error return

;Initialize variables for serial re-entrancy
mov [bit_offset],0
mov [input_offset],0
mov [input_size],0

test memflag,0ffH ;Memory allocated?
jnz gotmem ;If allocated, continue
ifdef OS2
invoke DOSALLOCSEG, maxmax*5+512, addr selector, 0
or ax,ax
je ok1
jmp MALLOC_err1
ok1:
mov ax,selector
jmp short here1
else
malloc <((maxmax * 5) / 16 + 20)> ;allocate it
jnc here1
jmp MALLOC_err1
endif
here1:
mov hash_seg,ax ;Save segment address of mem block
mov memflag,0ffh ;Set flag to remind us later
gotmem:

l1: call init_table ;Initialize the table and some vars
mov ax,clear ;Write a clear code
call write_code
;call read_char ;Read first char
read_char ;macro for speed
l4:

;new code to check compression ratio
test [ratflag],0FFH ;Time to check ratio?
jz rd$1 ;Skip checking if zero
call check_ratio
rd$1:
xor ah,ah ;Turn char into code
l4a: mov prefix_code,ax ;Set prefix code
;call read_char ;Read next char
read_char ;macro for speed
jc l17 ;Carry means eof
mov k,al ;Save char in k
mov bx,prefix_code ;Get prefix code

call lookup_code ;See if this pair in table

jnc l4a ;nc means yes, new code in ax
;call add_code ;Add pair to table
add_code ;Macro for speed
push bx ;Save new code
mov ax,prefix_code ;Write old prefix code
call write_code
pop bx
mov al,k ;Get last char
cmp bx,max_code ;Exceed code size?

jnb l4$
jmp l4
l4$:
cmp nbits,maxbits ;Currently less than maxbits?
jb l14 ;yes
mov ax,clear ;Write a clear code
call write_code
call init_table ;Reinit table
mov al,k ;get last char
jmp l4 ;Start over
l14: inc nbits ;Increase number of bits
shl max_code,1 ;Double max code size
jmp l4 ;Get next char
l17: mov ax,prefix_code ;Write last code
call write_code
mov ax,eof ;Write eof code
call write_code
mov ax,bit_offset ;Make sure buffer is flushed to file
cmp ax,0
je OK_ret
mov dx,ax ;dx <- ax
shr ax,1
shr ax,1
shr ax,1 ;ax <- ax div 8
and dx,07 ;dx <- ax mod 8
;If extra bits, make sure they get
je l17a ;written
inc ax
l17a: call flush
OK_ret:
xor ax,ax ;Normal return -- compressed
ret
IO_err:
mov ax,2 ;I/O error return
mov sp,[save_sp] ;Restore stack pointer
ret

MALLOC_err1: ;hash table alloc error
mov ax,1 ;Malloc error return
mov sp,[save_sp] ;Restore stack pointer
ret
compress endp

init_table proc near
mov [bytesin],0 ;Input byte count
mov [bitsout],0 ;Output bit count
mov [ratio],0
mov [ratflag],0
mov [bit_interval],check_gap

mov nbits,9 ;Set code size to 9
mov max_code,512 ;Set max code to 512
push es ;Save seg reg
mov es,hash_seg ;Address hash table
mov ax,-1 ;Unused flag
mov cx,640 ;Clear first 256 entries
mov di,offset hash ;Point to first entry
rep stosw ;Clear it out
pop es ;Restore seg reg
mov free_code,first_free ;Set next code to use
ret ;done
init_table endp

write_code proc near
push ax ;Save code
mov cx,nbits
add [bitsout],cx ;Maintain output bit count for ratio
sub [bit_interval],cx
jg rd$2 ;OK if not reached interval
mov [ratflag],1 ;else set flag -- check ratio soon
rd$2:
mov ax,bit_offset ;Get bit offset
mov cx,nbits ;Adjust bit offset by code size
add bit_offset,cx

mov dx,ax ;dx <- ax
shr ax,1
shr ax,1
shr ax,1 ;ax <- ax div 8
and dx,07 ;dx <- ax mod 8

;Now ax contains byte offset and
;dx contains bit offset within that byte (I think)

cmp ax,outbufsiz-4 ;Approaching end of buffer?
jb wc1 ;less means no
call flush ;Write the buffer

push dx ;dx contains offset within byte
add dx,nbits ;adjust by code size
mov bit_offset,dx ;new bit offset
pop dx ;restore dx

;ax is an index into output buffer. Next, ax <- address of buffer[ax]
add ax,[_out_buf_adr]
mov si,ax ;put in si
mov al,byte ptr [si] ;move byte to first position

;put value of al into first byte of output buffer
push bx
mov bx,[_out_buf_adr]
mov [bx],al
pop bx
xor ax,ax ;Byte offset of zero
wc1: add ax,[_out_buf_adr] ;Point into buffer
mov di,ax ;Destination
pop ax ;Restore code
mov cx,dx ;offset within byte
xor dx,dx ;dx will catch bits rotated out
jcxz wc3 ;If offset in byte is zero, skip shift
wc2: shl ax,1 ;Rotate code
rcl dx,1
loop wc2
or al,byte ptr [di] ;Grab bits currently in buffer
wc3: stosw ;Save data
mov al,dl ;Grab extra bits
stosb ;and save
ret
write_code endp

flush proc near
push ax ;Save all registers
push bx ;AX contains number of bytes to write
push cx
push dx

push si ;may not be necessary to save si & di
push di

push ax ;save byte count

push ax ;byte count
push _out_buf_adr ;buffer address
ifdef UNBUF_IO
push output_handle ;zoofile
call _blockwrite
else
push output_seg ;zoofile
push output_handle ;zoofile
call _zoowrite
endif
add sp,6

pop cx ;recover byte count

cmp ax,cx

jz here2
jmp IO_err ;I/O error

here2:
pop di
pop si

pop dx
pop cx
pop bx
pop ax
ret
flush endp

lookup_code proc near
push ds ;Save seg reg
mov ds,hash_seg ;point to hash table

;call index ;convert code to address
call_index ;macro for speed

mov di,0 ;flag
mov bx,[si].first
cmp bx,-1 ;Has this code been used?
je gc4 ;equal means no
inc di ;set flag
gc2:
;call index ;convert code to address
call_index ;macro for speed

cmp [si].char,al ;is char the same?
jne gc3 ;ne means no
clc ;success
mov ax,bx ;put found code in ax
pop ds ;restore seg reg
ret ;done
gc3:
mov bx,[si].next
cmp bx,-1 ;More left with this prefix?
je gc4 ;equal means no
jmp gc2 ;try again
gc4: stc ;not found
pop ds ;restore seg reg
ret ;done
lookup_code endp

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

check_ratio proc near
push ax


; mov dl,'*' ;'*' printed means checking ratio
; call sendout

;Getting ready to check ratios. If bitsout is over scale_limit,
;then we scale down both bitsout and bytesin by a factor
;of 4. This will avoid overflow.
mov cx,[bitsout]
cmp cx,scale_limit
jb scale_ok

mov cl,2
shr [bytesin],cl
shr [bitsout],cl

scale_ok:
;Note MASM bug: "mov ah,high [bytesin]" and
;"mov al,low [bytesin]" don't work.
mov ah,byte ptr [bytesin]
mov dl,byte ptr [bytesin+1]

sub al,al
sub dh,dh ;dx:ax = 8 * bitsin = 256 * bytesin
mov cx,[bitsout] ;cx <- bitsout
or cx,cx ;Division by zero?
jnz candivide ;No -- go ahead divide
mov ax,0FFFFH ;yes -- assume max poss value
jmp short divided
candivide:
;Calculate cx as (bytesin * 256) / bitsout = bitsin * 8 / bitsout
div cx ;ax <- rat <- dx:ax / cx
shl ax,1
shl ax,1 ;rat <- 4 * bytes_in / bytes_out
divided:
;Enter here with ax = rat = bitsin / bitsout.

; call print_data ;print info for debugging

;If rat > rat_thresh then ratio is good; do not reset table
; cmp ax,rat_thresh
; ja ratdone

;Compare rat against ratio
mov bx,ax ;save rat in bx
cmp ax,[ratio] ;cmp rat,ratio
jb ratless ;trouble if ratio is now smaller
mov ax,[ratio]
call mul7 ;ax <- 7 * ratio
add ax,bx ;ax = 7 * ratio + rat
shr ax,1
shr ax,1
shr ax,1 ;ax = (7 * ratio + rat) / 8
mov [ratio],ax ;ratio = (7 * ratio + rat) / 8
jmp short ratdone
ratless: ;ratio is going down, so...
mov [bytesin],0
mov [bitsout],0

; mov dl,'#' ;'#' printed means table reset
; call sendout

mov ax,clear ;Write a clear code
call write_code
call init_table ;Reinit table
ratdone:
mov [ratflag],0
mov [bit_interval],check_gap
pop ax
ret
check_ratio endp

comment #
sendout proc near ;char in dl send to console
push ax
call _outchar
pop ax
ret
sendout endp
# end comment

mul7 proc near ;multiply ax by 7
push dx
mov dx,7
mul dx ;dx:ax <- 7 * ax
pop dx
ret
mul7 endp


comment #
mul3 proc near ;multiply ax by 3
push dx
mov dx,3
mul dx ;dx:ax <- 3 * ax
pop dx
ret
mul3 endp
# end comment

comment #
mul1_125 proc near ;multiply ax by 1.125
push bx
mov bx,ax
shr bx,1
shr bx,1
shr bx,1 ;bx = n / 8
add ax,bx ;ax <- n + n / 8
pop bx
ret
mul1_125 endp
# end comment

comment #
print_data proc near
;Debugging -- print bytesin, bitsout, rat, and ratio
push ax
push bx
push cx
push dx

push ax ;print rat
call _prtint
add sp,2

push [ratio] ;print ratio
call _prtint
add sp,2

push [bytesin]
call _prtint
add sp,2

push [bitsout]
call _prtint
add sp,2

pop dx
pop cx
pop bx
pop ax
ret
print_data endp
# end comment

;doread reads cx characters and stores them in input buffer
;return value from zooread is returned in ax
doread proc near ;reads block
push bx
push cx
push dx
push si
push di

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

pop di
pop si
pop dx
pop cx
pop bx
ret
doread endp

_TEXT ends

end