These programs are a file compressor and decompressor based on the
Limpel-Ziv algorithm.
title lzcomp - file compressor using limpel-ziv algorithm
;Tom Pfau
;Digital Equipment Corporation
;Parsippany, NJ
;Constants
clear equ 256 ;Clear code
eof equ 257 ;End of file marker
first_free equ 258 ;First free code
maxmax equ 4096 ;Max code + 1
include macros.mlb
;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
;Declare Segments
code segment byte public 'code'
code ends
stack segment word stack 'stack'
dw 128 dup (?)
stack ends
data segment word public 'data'
data ends
memory segment para public 'memory'
hash label hash_rec
memory ends
;Start writing code
code segment
assume cs:code,ds:data,es:data,ss:stack
start proc far
mov bx,seg hash ;End of program
mov ax,ds ;Start of program
sub bx,ax ;Program size
inc bx ;Make sure
setmem bx ;Set our size
mov bx,data ;Set up data segment addressability
mov es,bx
mov ds,bx
print input_prompt ;Get input file name
input input_file
print crlf
print output_prompt ;And output
input output_file
print crlf
mov al,input_file+1 ;Terminate file names with nulls
xor ah,ah
mov si,ax
mov input_file+2[si],0
mov al,output_file+1
mov si,ax
mov output_file+2[si],0
hopen input_file+2,0
mov input_handle,ax
hcreat output_file+2,0
mov output_handle,ax
call compress ;Compress file
hclose input_handle ;Close in and out
hclose output_handle
exit ;Done
start endp
data segment
input_prompt db 'Input file: $'
output_prompt db 'Output file: $'
input_file db 80,0,80 dup (?)
output_file db 80,0,80 dup (?)
crlf db 13,10,'$'
input_handle dw ?
output_handle dw ?
data ends
compress proc near
malloc 1280 ;Allocate space for hash table
mov hash_seg,ax ;Save segment address
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
l4: xor ah,ah ;Turn char into code
l4a: mov prefix_code,ax ;Set prefix code
call read_char ;Read next char
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
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?
jl l4 ;less means no
cmp nbits,12 ;Currently less than 12 bits?
jl 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 l18
mov cx,8 ;convert bits to bytes
xor dx,dx
div cx
or dx,dx ;If extra bits, make sure they get
je l17a ;written
inc ax
l17a: call flush
l18: ret
compress endp
data segment
hash_seg dw ?
prefix_code dw ?
free_code dw ?
max_code dw ?
nbits dw ?
k db ?
data ends
init_table proc near
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 ax,bit_offset ;Get bit offset
mov cx,nbits ;Adjust bit offset by code size
add bit_offset,cx
mov cx,8 ;Convert bit offset to byte offset
xor dx,dx
div cx
cmp ax,1020 ;Approaching end of buffer?
jl 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
add ax,offset output_data ;Point to last byte
mov si,ax ;put in si
mov al,byte ptr [si] ;move byte to first position
mov output_data,al
xor ax,ax ;Byte offset of zero
wc1: add ax,offset output_data ;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
data segment
bit_offset dw ?
output_data db 1024 dup (?)
data ends
flush proc near
push ax ;Save all registers
push bx ;AX contains number of bytes to write
push cx
push dx
hwrite output_handle,output_data,ax ;write output file
pop dx
pop cx
pop bx
pop ax
ret
flush endp
read_char proc near
mov di,input_offset ;Anything left in buffer?
cmp di,input_size
jl rd1 ;less means yes
hread input_handle,input_data,1024 ;Read next chunk of input
cmp ax,0 ;Anything left?
je rd2 ;equal means no, finished
mov input_size,ax ;Save bytes read
mov input_offset,0 ;Point to beginning of buffer
mov di,0
rd1: lea si,input_data[di] ;Point at character
lodsb ;Read it in
inc input_offset ;Adjust pointer
clc ;Success
ret
rd2: stc ;Nothing left
ret
read_char endp
data segment
input_data db 1024 dup (?)
input_offset dw 0
input_size dw 0
data ends
lookup_code proc near
push ds ;Save seg reg
mov ds,hash_seg ;point to hash table
call index ;convert code to address
mov di,0 ;flag
cmp [si].first,-1 ;Has this code been used?
je gc4 ;equal means no
inc di ;set flag
mov bx,[si].first ;Get first entry
gc2: call index ;convert code to address
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: cmp [si].next,-1 ;More left with this prefix?
je gc4 ;equal means no
mov bx,[si].next ;get next code
jmp gc2 ;try again
gc4: stc ;not found
pop ds ;restore seg reg
ret ;done
lookup_code endp
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
add_code proc near
mov bx,free_code ;Get code to use
push ds ;point to hash table
mov ds,hash_seg
cmp di,0 ;First use of this prefix?
je ac1 ;equal 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
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
ret
add_code endp
code ends
end start
title lzdcmp - file decompressor using limpel-ziev algorithm
;Tom Pfau
;Digital Equipment Corporation
;Parsippany, NJ
;Constants
clear equ 256
eof equ 257
first_free equ 258
maxmax equ 4096
include macros.mlb
;Hash table entry
hash_rec struc
next dw ? ; prefix code
char db ? ; suffix char
hash_rec ends
;Declare segments
code segment byte public 'code'
code ends
stack segment word stack 'data'
dw 128 dup (?)
stack ends
data segment word public 'data'
data ends
memory segment para public 'memory'
hash label hash_rec
memory ends
;Start coding
code segment
assume cs:code,ds:data,ss:stack,es:data
start proc far
mov bx,seg hash ;End of program
mov ax,ds ;Beginning of program
sub bx,ax ;Size of program
inc bx ;Make sure
setmem bx ;Set program size
mov bx,data ;Address data segment
mov es,bx
mov ds,bx
print input_prompt ;Get file names
input input_file
print crlf
print output_prompt
input output_file
print crlf
mov al,input_file+1 ;Terminate with nulls
xor ah,ah
mov si,ax
mov input_file+2[si],0
mov al,output_file+1
mov si,ax
mov output_file+2[si],0
hopen input_file+2,0 ;Open input and output
mov input_handle,ax
hcreat output_file+2,0
mov output_handle,ax
call decompress ;Decompress files
hclose input_handle
hclose output_handle
exit ;Done
start endp
data segment
input_prompt db 'Input file: $'
output_prompt db 'Output file: $'
input_file db 80,0,80 dup (?)
output_file db 80,0,80 dup (?)
crlf db 13,10,'$'
input_handle dw ?
output_handle dw ?
data ends
decompress proc near
malloc 768 ;Allocate space for hash table
mov hash_seg,ax ;Save segment address
hread input_handle,input_buffer,1024 ;Read from input
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 l1a ;no
hwrite output_handle,output_buffer,output_offset ;Flush buffer
l1a: ret ;done
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
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? (kkk)
jl 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
l11: cmp cur_code,255 ;Code or character?
jle l15 ;Char
mov bx,cur_code ;Convert code to address
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: push ds ;Restore seg reg
pop es
mov ax,cur_code ;Get code
mov fin_char,al ;Save as final, k
mov k,al
push ax ;Push it
inc stack_count
mov cx,stack_count ;Pop stack
jcxz l18 ;If anything there
l17: pop ax
call write_char
loop l17
l18: mov stack_count,cx ;Clear count on stack
call add_code ;Add new code to table
mov ax,in_code ;Save input code
mov old_code,ax
mov bx,free_code ;Hit table limit?
cmp bx,max_code
jl l23 ;Less means no
cmp nbits,12 ;Still within twelve bits?
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
data segment
hash_seg dw ?
cur_code dw ?
old_code dw ?
in_code dw ?
free_code dw first_free
stack_count dw 0
nbits dw 9
max_code dw 512
fin_char db ?
k db ?
data ends
read_code proc near
mov ax,bit_offset ;Get bit offset
add ax,nbits ;Adjust by code size
xchg bit_offset,ax ;Swap
mov cx,8 ;Calculate byte offset
xor dx,dx
div cx
cmp ax,1021 ;Approaching end of buffer?
jl rd0 ;no
push dx ;Save offset in byte
add dx,nbits ;Calculate new bit offset
mov bit_offset,dx
mov cx,1024 ;1k buffer
mov bp,ax ;save byte offset
sub cx,ax ;Calculate bytes left
add ax,offset input_buffer ;Point to char
mov si,ax
lea di,input_buffer ;Point to beginning of buffer
rep movsb ;Move last chars down
hread input_handle,[di],bp ;Fill rest of buffer
xor ax,ax ;Clear ax
pop dx ;Restore offset in byte
rd0: add ax,offset input_buffer ;Point to char
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
data segment
masks dw 1ffh,3ffh,7ffh,0fffh
input_buffer db 1024 dup (?)
bit_offset dw 0
data ends
init_tab proc near
mov nbits,9 ;Initialize variables
mov max_code,512
mov free_code,first_free
ret
init_tab endp
write_char proc near
mov di,output_offset ;Get offset in buffer
cmp di,1024 ;Full?
jl wc1 ;no
push ax ;Save registers
push cx
hwrite output_handle,output_buffer,di ;Write buffer to file
pop cx
pop ax
mov di,0 ;Point to beginning of buffer
mov output_offset,di
wc1: lea di,output_buffer[di] ;Point into buffer
stosb ;Store char
inc output_offset ;Increment number of chars in buffer
ret
write_char endp
data segment
output_offset dw 0
output_buffer db 1024 dup (?)
data ends
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
add_code proc near
mov bx,free_code ;Get new code
call index ;convert to address
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
ret
add_code endp
code ends
end start
|
Главная
Каталог файлов
