New compression tool for Megadrive: LZ4W

Talk about development tools here

Moderator: BigEvilCorporation

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: New compression tool for Megadrive: LZ4W

Post by Stef » Tue Sep 27, 2016 8:20 pm

That is what i meant by random access (mean you can unpack only part of packed data). Iin fact you cannot just "resume" a chunk you partially started to unpack. The compression scheme (based on LZW) work on previously unpacked data so you cannot do that.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: New compression tool for Megadrive: LZ4W

Post by Sik » Wed Sep 28, 2016 5:18 am

I think the idea is to have the ability to pause the decompression. You can decompress the first bytes, then use that, then keep decompressing later. That should be doable with pretty much any algorithm as long as you can afford keeping the spent memory around. You just need the code to allow you to do it.
Sik is pronounced as "seek", not as "sick".

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: New compression tool for Megadrive: LZ4W

Post by Stef » Wed Sep 28, 2016 9:08 am

The main problem is that you cannot really control how much you want to decompress. Or you have to modify code in a way it makes it much slower. Also that need sort of preservation of current state (buffer content and pointer position). I think that at least on case of my LZ4W unpack code the performance impact of adding that ability will be huge really. I can eventually add a method will allow to set a minimal amount of wanted unpacked data so the method try to exit when we have enough data. But I think at least that it will work on block so at worst it will unpack 30 extras byte... Need to think about it. I'm not sure that would give a big advantage in compression ratio compared to just pack very small chunks but I can eventually try ;-)

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: New compression tool for Megadrive: LZ4W

Post by Miquel » Wed Sep 28, 2016 2:57 pm

Stef, you don't have to code anything, I only want to know if it's doable. For example, I didn't thought of the possibility of reusing the decompressed buffer, as you mentioned.

To simplify the problem, I'm going to use a permanent 4KB buffer on MD RAM and limit any compressed buffer, on ROM, to that size. It seems to me, that the only state valid variables at the main loop of the decompression code in 68000 asm are the 2 pointers, stored in a0 and a1 registers, so it could be as simple as storing this 2 register into a global variable and check the current decompressed size to decide if we need to exit.

¿ Is there available a C (or C++) version of the compression algorithm ?
HELP. Spanish TVs are brain washing people to be hostile to me.

cero
Very interested
Posts: 338
Joined: Mon Nov 30, 2015 1:55 pm

Re: New compression tool for Megadrive: LZ4W

Post by cero » Wed Sep 28, 2016 6:01 pm

If speed is not critical, measure if you get better compression by doing small blocks with zlib vs interruptable lz4w. Zlib decompression was about 23.1kb/s IIRC, or 394 bytes per frame.

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: New compression tool for Megadrive: LZ4W

Post by Miquel » Fri Sep 30, 2016 11:13 am

What I'm looking for is decompression while in game, then I need something very light. Currently this game is a vertical shooter at 60hz with up to 30/40 objects on screen, so no much cpu left.
HELP. Spanish TVs are brain washing people to be hostile to me.

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: New compression tool for Megadrive: LZ4W

Post by Stef » Fri Sep 30, 2016 4:54 pm

Miquel wrote:Stef, you don't have to code anything, I only want to know if it's doable. For example, I didn't thought of the possibility of reusing the decompressed buffer, as you mentioned.

To simplify the problem, I'm going to use a permanent 4KB buffer on MD RAM and limit any compressed buffer, on ROM, to that size. It seems to me, that the only state valid variables at the main loop of the decompression code in 68000 asm are the 2 pointers, stored in a0 and a1 registers, so it could be as simple as storing this 2 register into a global variable and check the current decompressed size to decide if we need to exit.

¿ Is there available a C (or C++) version of the compression algorithm ?
Unfortunately no, there is no C version of the code. As i designed it for speed, i only wrote an assembly version of the unpacker. But honestly the code is damn simple and should be easy to modify to add a length verification to exit at some point. I guess you can do it at each block start, that should be enough then you return how many byte were unpacked to you can resume unpacking at next iteration (correctly providing the input/output pointers) :)

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: New compression tool for Megadrive: LZ4W

Post by Miquel » Sat Oct 01, 2016 9:38 pm

Thanks Stef, the reason I want the code to be in C++ is because I have a tool that builds/compiles all the resources, so I just want to integrate it to that code/program; and perhaps later I will customize the compressor too. First, as soon as I have time I will convert it to c and play a little bit with it to understand it.
HELP. Spanish TVs are brain washing people to be hostile to me.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: New compression tool for Megadrive: LZ4W

Post by Sik » Sat Oct 01, 2016 10:36 pm

The build tool should not have to care about the decompressor though, only about the compressor.
Sik is pronounced as "seek", not as "sick".

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: New compression tool for Megadrive: LZ4W

Post by Stef » Sun Oct 02, 2016 10:00 am

Yeah as Sik said, you only requires the compressor then. And it's currently available in java format (lz4w.jar), I believe the sources are included in the jar file if you want.

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: New compression tool for Megadrive: LZ4W

Post by Miquel » Sun Oct 02, 2016 4:41 pm

I already ported the java code to C++, if somebody wants it I can post it here.

What I'm going to do is limit the size of decompressed buffer to 4KB, create a buffer of that size on RAM, decompress each frame at least 32bytes and upload that tile thought DMA on vblank.

That will be enough to keep having new sprites, new objects, every few seconds, and hopefully don't decrease cpu performance too much; while conserving ROM.
HELP. Spanish TVs are brain washing people to be hostile to me.

Post Reply