lz77 compression

Por samsaga2

Resident (53)

imagem de samsaga2

15-01-2015, 16:32

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
Entrar ou registrar-se para comentar

Por PingPong

Prophet (3460)

imagem de PingPong

16-01-2015, 22:14

nice!

Por johnsonjeven

Supporter (1)

imagem de johnsonjeven

12-10-2016, 08:17

LZF is conceptually very similar to LZ77. Generally speaking most modern compression algorithms give roughly the same compression, and with regard to the number of cores that you can use at once, it is up to you to decide how many you want to use. Generally speaking (unless you are creating large archives) there is no reason to need more than one though. In addition, with multiple cores doing the compression, the bottleneck may become the hard drive. Legacy zip compression is akin to the Deflate method in 7-zip, and will offer the most compatibility between different compression software.

John

Por Uninteresting

Expert (102)

imagem de Uninteresting

13-10-2016, 21:44

Thanks! If/when I get back to working on my current project, I'll be sure to give this a go. So far I've used just a Huffman decoder I wrote, but it has many flaws hindering its usability.

Por MicroTech

Champion (386)

imagem de MicroTech

14-10-2016, 09:56

Cool

Por Metalion

Paladin (1013)

imagem de Metalion

14-10-2016, 10:01

samsaga2 wrote:

Other algorithms has better compression ratios but they only work on ram (no vram).

Actually, that's not true. Several years ago, I wrote variations of Pletter and Bitbuster algorythms, for direct VRAM decompression on MSX1.
https://www.msx.org/news/software/en/vram-depackers-bitbuste...

But anyway, great work on the LZ77.