|
Título: lz77 compression Publicado por: samsaga2 en 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 |