Fastest depacker

[Antiriad_UK]

I like this comment in the depack source, ross.

bclr	d2,d2		; ;)

The mind boggles

[ross]

Originally Posted by antiriad_uk

the mind boggles

Magia!

[hooverphonique]

Interesting thread, this!

I'm looking for a fast depacker (comparable to LZ4) for iteratively depacking, from a compressed stream, a fixed output amount of data (0.5-1kB) into the same buffer each frame, similar to depacking a media stream, except it's not media data.

Do any of you have suggestions for such a thing?

[a/b]

LZ4 can depack in-place but you have to do several extra steps. I don't have a working m68k code, it's on my todo list since I didn't need it "right now", but a prototype in C works fine. You'd have to:
- revert source data (last byte comes first)
- compress with regular lz4
- reverse contents of compressed data blocks (and if there's more than one, revert them as well), for better performance you can leave 16bit match offsets in little-endian format (faster conversion from unaligned 16bit to aligned big-endian)
- modify the decompressor to work from end to start (change postinc to predec for the most part)

[hooverphonique]

Thanks a/b. I'm not looking for in-place decompression per se, but being able to call the decompressor iteratively to get a fixed size chunk of decompressed bytes out of the same compressed stream.

But maybe it'll be easier to just compress each (or several for better ratio?) chunk separately instead of the whole stream of chunks... Hmm...

[ross]

If the blocks are so small I wouldn't even worry about in-place decompression.
I would put the data block directly on stack and forward unpack from there.

But one important thing is not clear: the LZ window should refer to already decompressed data or every block should refer exclusively to own vocabulary?
Because it would make a huge difference in compression efficiency.

EDIT: posted before seeing the previous message

[Galahad/FLT]

Just so we don't get any unnecessary mod action, i'm happy for the thread to go in whatever direction it goes in, its all helpful and people are being helped

[Antiriad_UK]

Couldn't sleep this morning so added Cranker and PackFire (large model) to my framework to give them all a go.

Remember CPU is 99% busy in lev3 interrupt and depacking only happening outside lev3 interrupt so interrupt hell, but I'm mostly interested in relative performance anyway. I depacked 4 times to make it easier to time with stopwatch (So scientific )

Original file is a raw image depacked 4 times : 4 x 40960 bytes
Last column is just rough speed vs LZ4. I've seen someone quote shrinkler as about 22 times slower than lz so looks about right.

LZ4		9247 bytes	4.7s	(1x)
Cranker		8556 bytes	6.2s 	(1.3x)
Doynamite68k	8125 bytes	8.5s	(1.8x)
nrv2s		7840 bytes	9.7s	(2.0x)
Shrinkler	6528 bytes	110s	(23x)
PackFire	6432 bytes	219s	(46x)

Just so this table not trying to make Shrinkler/PackFire look slow. Packfire does this test in 23s when interrupts turned off. Gets hard to measure the others then though. Definitely a case of choosing the right tool for the job.

I was looking to use Cranker to compress my final exe as it's so fast but it looks pretty good for data too (and does in-place). Choice paralysis!

Edit: Table fixed.

[Don_Adan]

Originally Posted by Antiriad_UK

Couldn't sleep this morning so added Cranker and PackFire (large model) to my framework to give them all a go.

Remember CPU is 99% busy in lev3 interrupt and depacking only happening outside lev3 interrupt so interrupt hell, but I'm mostly interested in relative performance anyway. I depacked 4 times to make it easier to time with stopwatch (So scientific )

Original file is a raw image depacked 4 times : 4 x 40960 bytes
Last column is just rough speed vs LZ4. I've seen someone quote shrinkler as about 22 times slower than lz so looks about right.

LZ4		9247 bytes	4.7s	(1x)
Cranker		8556 bytes	6.2s 	(1.3x)
Doynamite68k	8125 bytes	8.5s	(1.8x)
nrv2s		7840 bytes	9.7s	(2.0x)
Shrinkler	6528 bytes	110s	(23x)
PackFire	6432 bytes	219s	(46x)

Just so this table not trying to make Shrinkler/PackFire look slow. Packfire does this test in 23s when interrupts turned off. Gets hard to measure the others then though. Definitely a case of choosing the right tool for the job.

I was looking to use Cranker to compress my final exe as it's so fast but it looks pretty good for data too (and does in-place). Choice paralysis!

Edit: Table fixed.

You can add Arj mode 7 and xpk_SHR3 for comparison.

[hooverphonique]

Originally Posted by ross

But one important thing is not clear: the LZ window should refer to already decompressed data or every block should refer exclusively to own vocabulary?
Because it would make a huge difference in compression efficiency.

Good question, Ross, and the answer is probably, that best compression is achieved with a vocabulary that "slowly" updates, i.e. not for each block, but also not static over the whole stream.

[Antiriad_UK]

Originally Posted by Don_Adan

You can add Arj mode 7 and xpk_SHR3 for comparison.

Not managed to get that arj depacker code to work yet. I think the util that was suggested Windows was arjbeta.exe. The depacker code barfs at that but think it’s because the resulting file is an archive so you have to work out how to skip to the right offset in the file first.

[Don_Adan]

Originally Posted by Antiriad_UK

Not managed to get that arj depacker code to work yet. I think the util that was suggested Windows was arjbeta.exe. The depacker code barfs at that but think it’s because the resulting file is an archive so you have to work out how to skip to the right offset in the file first.

You must skip some bytes at begining of packed file with arjbeta.exe. You can check Turrican 2 (WT version).

[ross]

Originally Posted by Don_Adan

You can add Arj mode 7 and xpk_SHR3 for comparison.

Yes, ARJ7m absolutely deserves to enter the test list.
Never checked xpk_SHR3, I should do it.

Originally Posted by hooverphonique

Good question, Ross, and the answer is probably, that best compression is achieved with a vocabulary that "slowly" updates, i.e. not for each block, but also not static over the whole stream.

Ok, so that's what I had in mind to do but I never did

Originally Posted by Antiriad_UK

Not managed to get that arj depacker code to work yet.

Now you can

[Antiriad_UK]

Originally Posted by ross

Yes, ARJ7m absolutely deserves to enter the test list.

Now you can

Thanks for the arj file. Added to the toolbox

LZ4		9247 bytes	4.7s	(1x)
Cranker		8556 bytes	6.2s 	(1.3x)
Doynamite68k	8125 bytes	8.5s	(1.8x)
nrv2s		7840 bytes	9.7s	(2.0x)
Arj m7		7276 bytes	16.4s	(3.4x)
Shrinkler	6528 bytes	110s	(23x)
PackFire	6432 bytes	219s	(46x)

I can see why Dan said they used lz4+arj as required for De Profundis - they sit at opposite ends of the "reasonable" speed vs compression scale it seems.

[DanScott]

LZ4 was essential for the infinite roto-zoomer... had 128 frames to decompress the next image to be used, with about 30-45% of a frame free for the background decompression (actually less, as there was a LOT of copper action happening too)

ARJ was mainly used for the compression of each demo part (to be loaded decompressed in the background)

[VladR]

Hi guys. Just joined the board. Happy to be here !

I'm working on a 4 KB demo for Atari Jaguar and am in need of some serious packer. I don't mind abysmal depacking times, as it can't possibly be that long with just couple KBs.

Is Shrinkler achieving best compression ratio ?

Obviously, there is going to be a threshold where depacker, regardless of its compression ratio, is simply too big for a 4 KB executable.

Are there any known 4-KB specific depackers with best ratio ? I don't mind implementing it by myself, I just need to avoid scenario where I implement something and a week later find out I should have implemented a different depacker.

The target data payload is:
68000 code
GPU RISC code
DSP RISC code
gfx data
audio data

[Galahad/FLT]

Originally Posted by VladR

Hi guys. Just joined the board. Happy to be here !

I'm working on a 4 KB demo for Atari Jaguar and am in need of some serious packer. I don't mind abysmal depacking times, as it can't possibly be that long with just couple KBs.

Is Shrinkler achieving best compression ratio ?

Obviously, there is going to be a threshold where depacker, regardless of its compression ratio, is simply too big for a 4 KB executable.

Are there any known 4-KB specific depackers with best ratio ? I don't mind implementing it by myself, I just need to avoid scenario where I implement something and a week later find out I should have implemented a different depacker.

The target data payload is:
68000 code
GPU RISC code
DSP RISC code
gfx data
audio data

Im sure someone can give you good advice on this as there are quite a few demo programmers that are adept on different retro computing formats.

[ross]

Originally Posted by VladR

Is Shrinkler achieving best compression ratio ?

Obviously, there is going to be a threshold where depacker, regardless of its compression ratio, is simply too big for a 4 KB executable.

Yes, Shrinkler is perfect for 4KB demo/intro, normally has the best compression ratio compared to all other compressors.
Depacker code also is very tiny (but be prepared for long depacking, also on 4KB of datas).

[VladR]

Originally Posted by ross

Yes, Shrinkler is perfect for 4KB demo/intro, normally has the best compression ratio compared to all other compressors.
Depacker code also is very tiny (but be prepared for long depacking, also on 4KB of datas).

Thanks!


I just tried using it on my current build (without audio yet) with option -d and it compressed 3,904 Bytes into 2,080 -> 52.7 %
But, I do have a 1,024 Bytes of Heightmap terrain data there (which will shrink to 256 soon), so not sure how that affects the ratio.


Nice !


Looks like there is even a 68000 depacker source already and it's just 3 pages of code, so that shouldn't be an issue at all (as I worried initially).




Just curious - can it even take more than a second to depack 8 KB on a 13.3 MHz 68000 ? I will, eventually, find out, just wondering if some kind of visual loading progress is even needed for such miniscule size ?


Anything around 2-3 seconds is not a big deal when the compo is running. If it was 10 seconds, then yeah - I would need some loading screen.


Worst case scenario, I could implement it on GPU, though such RISC code might easily take double to triple the size of 68000, so I'd rather not go that route...


I think I saw some timing benchmarks around in this thread, so I'll reread from first page...

[VladR]

Originally Posted by leonard

if anyone is interested by a fast LZ4 68k depacker, you can use one of my three version here: (tiny, normal and fast )

https://github.com/arnaud-carre/lz4-68k

If you need extreme packing ratio and you don't care of decompression time then use Shrinkler.
If you need very good packing ratio with average depacking speed ( about 15KiB/s, same speed as floppy loading), use ARJ mode 7
If you need almost same good packing ratio than ARJ mode 7 and about 2 times faster depacking, use UPX (nrv2b )
If you need extremly fast depacking speed withtout ridiculous packing ratio, use LZ4

I did a ATARI depacking benchmark, you can look results here: https://ibb.co/JKtQFVt

first column is the packed binary file size ( smaller is better ). Then the name of the file ( you have lz77, pft=packfire tiny, lz, am7=arj mode 7, shk=shrinkler

the number between bracket () is the decompressor code size.

Then the last column is the decompressor speed ( number of 50hz tick to depack). Smaller is faster.

That is an awesome benchmark. Thanks for the work involved!


So, if I'm reading it right, Shrinkler takes more than an order of magnitude longer than the fastest one ? Wow, I guess I won't be using it for my 4 MB demos It also appears that ~3KB were decompressed in exactly 1 second (49 vbls out of 50), which is just about my target size.