Hey all, I'm working on some simple compression and decompression routines to be used on teh eZ80 and Z80 calcs. First up is LZ77 compression and I know KermM mentioned interest in writing a computer-side compression program.
I will be editing this first post with actual Z80 and eZ80 routines as I make them
So the pseudo-code for LZ77 compression:
Code:
Some notes:
Searching for the largest matching substring should start at most 65535 bytes before the current read_head or the beginning of the source data (whichever is smaller).
Valid matches must be 259 bytes or less and this is match_size
match_offset is the number bytes before read_head where the match occurs
Code:
I will be editing this first post with actual Z80 and eZ80 routines as I make them
So the pseudo-code for LZ77 compression:
Code:
;Variables:
; write_head points to the start of the output data and auto-increments when used
; read_head points to the start of the input
find the byte that occurs least frequently in the data. This will be our "escape byte."
#if you need to allocate RAM for the output data, allocate a number of bytes equal to 1+original size + number of occurences of the escape byte in the original data.
escape byte -> (write_head) #remember this auto increments write_head
while read_head != eof
search for the largest matching sub-string (up to 259 bytes long)
If match< (5+number of occurences of the escape byte)
escape_byte -> (write_head)
match_size-4 -> (write_head)
match_offset_LSB ->(write_head)
match_offset_MSB ->(write_head)
read_head+match_size -> read_head
ELSE
(read_head) -> temp
read_head++
temp -> (write_head)
if temp = escape_byte
0 -> (write_head)
Some notes:
Searching for the largest matching substring should start at most 65535 bytes before the current read_head or the beginning of the source data (whichever is smaller).
Valid matches must be 259 bytes or less and this is match_size
match_offset is the number bytes before read_head where the match occurs
Code:
lz77_decompress:
;;Inputs: HL points to compressed data
;; DE points to where the data is decompressed to
;; BC is the size of the compressed data
;; A is the escape byte
cp (hl) \ jr z,esc \ ldi \ jp pe,loop \ ret
.esc
push af
inc hl
ld a,(hl)
or a
jr nz,$+5
ld (de),a
jr a
push bc
inc hl
ld c,(hl)
inc hl
ld b,(hl)
push hl
ld h,d
ld l,e
sbc hl,bc
add a,4
ld c,a
ld a,0
rla
ld b,a
ldir
pop hl
pop bc
dec bc
dec bc
.a
pop af
dec bc
cpi
jp pe,lz77_decompress
ret
