I have written z80 code to decompress using lz77 algorithm (with sliding window of 256 bytes). Maybe it is not the best compressor for msx but it is fast, small, easy and only needs 256 bytes of ram to decompress (512 bytes for vram). Other algorithms has better compression ratios but they only work on ram (no vram).
It is perfect to decompress a full screen 5/8 screen to vram.
python compressor
import sys
def compress(values):
out = []
def equal_len(left, right):
length = 0
while left < right and right < len(values) and values[left] == values[right] and length < 255:
length += 1
left += 1
right += 1
return length
def find_back_offset(current_index):
max_back_offset = 0
max_back_len = 0
i = max(0,current_index-255)
while i < current_index:
back_len = equal_len(i, current_index)
if back_len > max_back_len:
max_back_len = back_len
max_back_offset = current_index-i
i += 1
return (max_back_offset, max_back_len)
i = 0
size = 0
while i < len(values):
back_offset, back_len = find_back_offset(i)
i += back_len
next_char = values[i] if i < len(values) else 0
if back_len==0:
out.extend([back_len, next_char])
else:
out.extend([back_len, back_offset, next_char])
i += 1
size += 1
sys.stderr.write("compressing... %d%%\t\t\r" % (i/float(len(values))*100))
sys.stderr.flush()
sys.stderr.write("original %s bytes -> final %s bytes\n" % (len(values), len(out)))
return [size&0xff,size>>8] + out
def uncompress(data):
out = []
i = 2
while i < len(data):
back_len = data[i]
i += 1
if back_len != 0:
back_offset = len(out)-data[i]
i += 1
while back_len > 0:
out.append(out[back_offset])
back_offset += 1
back_len -= 1
out.append(data[i])
i += 1
return out
if __name__ == "__main__":
if sys.argv[1] == "c":
with open(sys.argv[2], "rb") as f:
sys.stdout.buffer.write(bytes(compress(f.read())))
elif sys.argv[1] == "d":
with open(sys.argv[2], "rb") as f:
sys.stdout.buffer.write(bytes(uncompress(f.read())))
decompress from ram to ram
;; IX=ptr to compressed data
decompress2ram:
;; bc=token count
ld c,(ix+0)
ld b,(ix+1)
inc ix
inc ix
;; de=dest
ld de,ram256bytes
;; uncompress loop
loop1:
;; a=len
ld a,(ix+0)
inc ix
or a
jr z,skip
push bc
;; hl=offset
push de
pop hl
ld c,(ix+0) ; back offset
ld b,0
sbc hl bc
inc ix
;; copy from back offset
ld c,a
ldir
pop bc
skip:
;; a=nextchar
ld a,(ix+0)
;; write nextchar
ld (de),a
inc de
inc ix
;; end?
dec bc
ld a,c
or b
jr nz,loop1
ret
decompress from ram to vram
;; IX=ptr to compressed data
decompress2vram:
;; bc=token count
ld c,(ix+0)
ld b,(ix+1)
inc ix
inc ix
;; de=dest (256 bytes align)
ld hl,ram512bytes
ld de,256
add hl,de
ld l,0
ex de,hl
;; uncompress loop
loop1:
;; a=len
ld a,(ix+0)
inc ix
or a
jr z,skip
push bc
ld b,a
;; hl=offset = (de-backoffset) mod 256
ld c,(ix+0) ; back offset
ld a,e
sub c
ld l,a
ld h,d
inc ix
;; copy from back offset
loop2:
ld a,(hl)
inc l ; hl=hl mod 256
ld (de),a
inc e ; de=de mod 25
out (0x98),a
djnz loop2
pop bc
skip:
;; a=nextchar
ld a,(ix+0)
;; write nextchar
out (0x98),a
ld (de),a
inc e ; de=de mod 256
inc ix
;; end?
dec bc
ld a c
or b
jr nz,loop1
ret
