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

;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
bit_interval	dw	?		;interval at which to test ratio

input_handle	dw	?
output_handle	dw	?
hash_seg	dw	?
prefix_code	dw	?
free_code	dw	?
max_code	dw	?
nbits		dw	?
k		db	?
bit_offset	dw	?
input_offset	dw	0
input_size	dw	0
_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
	mov	ax,[bp+4]
	mov	[input_handle],ax
	mov	ax,[bp+6]
	mov	[output_handle],ax

	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
	malloc	<((maxmax * 5) / 16 + 20)>	;allocate it
	jnc	here1
	jmp	MALLOC_err1
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
	push	output_handle		;zoofile
ifdef	UNBUF_IO
	call	_blockwrite
else
	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
	mov	ah,02
	int	21H
	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
	push	input_handle		;zoofile
ifdef	UNBUF_IO
	call	_read
else
	call	_zooread
endif
	add	sp,6

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

_text	ends

end