Karoshi MSX Community
28 de Mayo de 2017, 10:52:46 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias:
 
   Inicio   Ayuda Buscar Calendario Ingresar Registrarse  
Páginas: [1]
  Imprimir  
Autor Tema: lz77 compression  (Leído 5242 veces)
0 Usuarios y 1 Visitante están viendo este tema.
samsaga2
Karoshi Fan
**
Mensajes: 76


Ver Perfil Email
« : 15 de Enero de 2015, 04:36:05 pm »

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
Código:
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
Código:
    ;; 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
Código:
    ;; 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
En línea
Páginas: [1]
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.21 | SMF © 2013, Simple Machines XHTML 1.0 válido! CSS válido!