lz77 compression

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