Fast decompression

Prophet (2200)

22-10-2006, 11:03

I need a decompression algorithm that is faster than bitbuster and pletter but still gives decent compression ratio. I need to decompress 60kB/s (decompressed size) and I can use around 75% of the CPU for decompression. Only RLE is fast enough but doesn't give me good enough compression.

Anyone know of any good alternatives?

Por wolf_

Ambassador_ (10109)

22-10-2006, 11:11

Perhaps make your own? The first 4m required 7mhz because it used BB, then we made our own comp/decomp (which is a bit tailormade for those images) and now it uses 50% of a normal z80.

Por Edwin

Paragon (1182)

22-10-2006, 12:14

With 60kB/s I doubt you can do much more than RLE on a standard z80. I would suggest to modify RLE with some simple algorithm that improves the compression ratio for your specific type of data.

Por dvik

Prophet (2200)

23-10-2006, 06:38

With 60kB/s there is indeed not that much time to do decompression. I also need to out the decompressed data. I did my own compression that works quite well with my data. Its not as good as bitbuster but quite a lot better than plain RLE.
For each output byte, I use one bit that tells whether the output value should be the same as the previous value or if its a different value. If its a different value I then read the new output value. The good thing with the algorithm is that decompression is faster than bitbuster but the compressed size is about 20% bigger than bitbuster on my data. Not ideal, but not too bad either.

Por ARTRAG

Enlighted (6935)

23-10-2006, 10:51

I have not clear how your actual solution works, anyway it seems that your data
have an highrate of repeated values.

In order to reduce the # of encoded bits you could think to encode differences between successive values.

If your data have lots of repeated values you get long runs of zeros,
(that you could try to encode in some special way)

Por cax

Prophet (3740)

23-10-2006, 11:48

Tried RNC PRO ?

Por Prodatron

Paragon (1843)

23-10-2006, 16:23

On the CPC we had "Crown Cruncher" which made very good results and had a light speed decompressor (also kind of RLE).
If you are interested I could disassemble the decompressor and post it here.

Por BiFi

Enlighted (4348)

23-10-2006, 16:30

sounds interesting

Por ARTRAG

Enlighted (6935)

23-10-2006, 16:35

Please yes!
It would be great!
but do not forget to post the encoder too

Por Prodatron

Paragon (1843)

23-10-2006, 17:30

Here is the decruncher (by Crown of BENG! aka Andreas Stefan Winter).
I didn't disassemble the code of the cruncher, but you can download the program here:
http://genesis8.free.fr/frontend/utility/crunch14.zip

The source should just give an idea, if this could be useful for you or not. Unfortunately I don't know anything about the MSX crunchers yet.

        di
        call #000f          ;find out current address (normalley there is always a #c9 at #000f)
        dec sp
        dec sp
        pop hl
        ld bc,#c758
        add hl,bc
        ld e,(hl)           ;de=destination address
        inc hl
        ld d,(hl)
        ld bc,#0011
        add hl,bc
.l8292                      ;main loop
        ld a,(hl)
        inc hl
        ld c,(hl)
        cp #ff              ;** -1 = end of crunched data
        ret z
        nop
        nop
        cp #50
        jr nc,l82a6
        inc a               ;** 0-79 = copy data 1:1 (length=code+1)
        ld c,a
        ld b,#00
        ldir
        jr l8292
.l82a6
        cp #a0
        jr nc,l82b2
        sub #4d             ;** 80-159 = fill with zeros (length=code-77)
        ld c,a
        ld b,#00
        xor a
        jr l8322
.l82b2
        cp #f0
        jr nc,l82bf
        sub #9c             ;** 160-239 = fill with the next byte (length=code-156)
        ld c,a
        ld b,#00
        ld a,(hl)
        inc hl
        jr l8322
.l82bf
        cp #fd
        jr nz,l82c8
        ld b,#00            ;** #fd = copy up to 255 bytes...
        inc hl
        jr l82cf
.l82c8
        cp #fe
        jr nz,l82db
        inc hl              ;** #fe = copy up to 65535 bytes...
        ld b,(hl)
        inc hl
.l82cf
        push de             ;** ...from an already decrunched area
        ld e,(hl)
        inc hl
        ld d,(hl)
        inc hl
        ex (sp),hl
        ex de,hl
        ldir
        pop hl
        jr l8292
.l82db
        sub #f0
        jr nz,l82eb
        ld a,(hl)           ;** #f0 = copy up to 255 new bytes
        inc hl
        add #51
        ld c,a
        ld b,#00
        jr nc,l82f1
        inc b
        jr l82f1
.l82eb
        dec a
        jr nz,l82f5
        inc hl              ;** #f1 = copy up to 65535 new bytes
        ld b,(hl)
        inc hl
.l82f1
        ldir
.l82f3
        jr l8292
.l82f5
        dec a
        jr nz,l8300
        xor a               ;** others = different fill methodes
        push af
        ld a,(hl)
        inc hl
        add #53
        jr l8313
.l8300
        dec a
        jr nz,l8309
        inc hl
        ld b,(hl)
        inc hl
        xor a
        jr l8322
.l8309
        dec a
        jr nz,l831c
        ld a,(hl)
        inc hl
        push af
        ld a,(hl)
        inc hl
        add #54
.l8313
        ld c,a
        ld b,#00
        jr nc,l8319
        inc b
.l8319
        pop af
        jr l8322
.l831c
        ld a,(hl)
        inc hl
        ld c,(hl)
        inc hl
        ld b,(hl)
        inc hl
.l8322                      ;** repeat the same value x times
        push hl
        dec bc
        ld h,d
        ld l,e
        inc de
        ld (hl),a
        ldir
        pop hl
        jr l82f3

Por ARTRAG

Enlighted (6935)

23-10-2006, 17:32

how do you read the bin files?