Is there a better packer than arjm7?

[ross]

WOW.
First test with enhanced offset.
This forcibily require my unpacker, the official one doesn't/can't support offset >32KiB.
I used an offset of 100KB, but theoretically in can work until 16MiB (but better to have a quantum computer in case...)

Zombies.SHP compressed from 245720 to 44918 bytes!
execution time : 3018.983 s (you read that right.. 50 minutes..)

For reference:
65535 RNC (LZ, -m 2)
54966 Crunch-Mania (LZH)
53677 RNC (LZH, -m 1)
52415 gzip (-9)
50553 official zx0 (hardwired offset 32740)
48908 arjm7 (this is a special unfortunate case for arm7 because the file is highly redundant)
46779 aplibx (apultra like performance)
46238 nrv2r (my special version)
46126 rar (max compression)

Yes, beaten all packers using LZ or LZH formats.

And now the speed, standard A500 7Mhz, code and data in chip-ram, Zombies.SHP: 1239ms, 198.32 KB/s!
It's very fast!
Of course I have tested the unpacked data, so the decoder works fine

Maybe I'll edit this post after doing a test with an offset of 256KB (it probably takes half a day to finish )
Now I stop flooding this thread..

[malko]

Originally Posted by ross

[...] Now I stop flooding this thread..

You can continue, it's a pleasure to read
and the last compression ratio are just impressive

[meynaf]

Originally Posted by ross

Zombies.SHP compressed from 245720 to 44918 bytes!

Wait. If we have same zombies.shp file, this even beats arithmetic coding (xpk shri) and burrows-wheeler (bz2) !
Care to share your code ?

[ross]

Originally Posted by NorthWay

I have always thought of LZ as using [offset,length] pairs - typically adding up to 16 bits - but I guess I should think of it as [length[,offset]]

The real strength of this compressor is in fact the extensive use of the rep-match, indeed, it is practically completely designed around it
(while in other compressors it is a secondary factor).
I realized this following the choices of regular match offsets in the decoder, which for a human seem to make no sense, but which in the long term give great results.

The problem with using rep-matches is, to my knowledge so I could be wrong, the lack of a good heuristic algorithm for general use.
While various accelerators exist for LZ parsers, the rep-match problem remains NP-hard (or similar) and therefore the solution in ZX0 is to use brute force.
And since rep-match is in one of the primary paths in the decompression code it has a huge impact on the compression factor (despite the simplicity of the encoding).

Originally Posted by meynaf

Wait. If we have same zombies.shp file, this even beats arithmetic coding (xpk shri) and burrows-wheeler (bz2) !
Care to share your code ?

Attached the encoded data (squeezed a few more bytes, now it is 44874).
You've a PM with (preliminary) code so do no spread
But try it to confirm my decompression speed report and zombie.shp content.

[pink^abyss]

Originally Posted by ross

WOW.
Zombies.SHP compressed from 245720 to 44918 bytes!
execution time : 3018.983 s (you read that right.. 50 minutes..)

And now the speed, standard A500 7Mhz, code and data in chip-ram, Zombies.SHP: 1239ms, 198.32 KB/s!
It's very fast!
Of course I have tested the unpacked data, so the decoder works fine

Super impressive depack speed and ratio Ross! Next of my games won't use Shrinkler anymore i guess (given you plan to this release it as an exe packer). For only packing data it would be a bit too slow for me

[meynaf]

Originally Posted by ross

But try it to confirm my decompression speed report and zombie.shp content.

I can't confirm decompression speed (too fast ).
But content confirmed. Same zombie.shp than mine (as taken from zombie apocalypse 2 game).

To be able to beat the size i had to go to PPM range of compressors. No hope for beating that i think, but perhaps it would be interesting to add a few complexity for faster machines.

However this data is highly compressible. I'd like to see how this compressor performs on different data. If it's able to repetitively beat LZX (~46k here) then it can have interesting applications.

[hitchhikr]

35872 bytes with packfire (but decrunching is a lot slower).

[meynaf]

Record to break is 28280 (WinRK).

[ross]

Originally Posted by pink^abyss

Super impressive depack speed and ratio Ross! Next of my games won't use Shrinkler anymore i guess (given you plan to this release it as an exe packer). For only packing data it would be a bit too slow for me

To tell the truth in this test ZX0 is very much at an advantage because the file contains a considerable amount of LZ match (but in any case it is significant for comparison with other pure LZs!).
So for compression factors such as shrinkler (or even for 'quality' LZH) it is not comparable.
Having an entropic stage in light pre-compressed files (LZ4 or similar) or with fewer match relationships helps a lot this different category of compressors.
Let alone if the entropy compression is arithmetic or even with CM.

But the very interesting thing is the compression factor in relation to the decompression speed, it could replace MANY of existing packers
And during compression you can

Originally Posted by meynaf

I can't confirm decompression speed (too fast ).
But content confirmed. Same zombie.shp than mine (as taken from zombie apocalypse 2 game).

Originally Posted by hitchhikr

35872 bytes with packfire (but decrunching is a lot slower).

The decompression speed target is too much different.
There are some very promising algorithms that use ANS or advanced forms of LZ on the compression forums and some can be ported to 68k,
but the problem is the decompression speed.

EDIT: and yes, for 'extreme' compression and slow decrunching you can use LZMA (packfire ), or the aforementioned shrinkler on 68k (the decoders with a 'mul').

[demoniac]

Impressive results. Haven't touched compression for a long time, but still find this topic interesting.

[malko]

Originally Posted by ross

[...] And during compression you can [...]

I vote for a beer

[ross]

Ok, time for a significative test with the 'alternative' ZX0:

ZX0 v2.1a: Optimal data compressor by Einar Saukas
alternative encoding by ross, beta version
Usage: ZX0.exe [-f] [-c] [-b] [-a] [-mn] [-q] input [output.zx0]
  -f      Force overwrite of output file
  -c      Classic file format (v1.*)
  -b      Compress backwards
  -a      Alternative bitcoding
  -mn     Max offset (n = 0 to 9)
  -q      Quick non-optimal compression

Command line used:

ZX0.exe -a -m9 file

	             unpacked  arjm7   azx0
       dirkernel.tmp     9180   6720   6025
       logo_fade.bin   131160  27284  27248
            main.bin   331380 122194 121677
        ym7Pack0.bin    18672  12402  12479
        ym7Pack1.bin   202162 113136 113483
        ym7Pack2.bin   200448 112806 112660
        ym7Pack3.bin   199646 107798 108418
        ym7Pack4.bin   203764 106350 105815
        ym7Pack5.bin   174760  91400  91068
        ym7Pack6.bin   128800  58362  58054
     CosoPackLz4.bin   218912 142048 146061

Very different from the old test by Leonard

Basically it is now on par with ARJm7, excluding the pre-LZ4-packed Coso_file.
In this case, unfortunately, it is inevitable that many LZ sequences are 'stolen' by the prepack and the entropic part of ARJ wins.

I'd like to try the un-prepacked version, or a version where LZ4 is replaced internally by ZX0.

(I don't tell you how long it took me to pack all the files, even though I made several cores work at the same time with different files..)

[Antiriad_UK]

This is all cool stuff. I wrote a basic lz77 packer once and I never want to go near that again. Keep sharing

[ross]

Originally Posted by ross

Basically it is now on par with ARJm7, excluding the pre-LZ4-packed Coso_file.
In this case, unfortunately, it is inevitable that many LZ sequences are 'stolen' by the prepack and the entropic part of ARJ wins.

I'd like to try the un-prepacked version, or a version where LZ4 is replaced internally by ZX0.

Ok, it took me a while because I wanted to reconstruct the situation as similar as possible to the original: same initial table with positioning, same order of files, same 'empty spaces' for missing/deleted files.
And as I imagined the situation is different.
Not only by replacing LZ4 with ZX0 the original pre-compressed file is much smaller, but also the final file, and with a large margin

Original file 153031 vs 218912.
Packed file 134212 vs 142048!

So for AmigAtari we have a possible substitute

---

I experimented a bit with an entropy stage.
The only point where it seems probable to insert it is for pure literals, because in all other cases I would destroy the properties of the encoder stream or I would just lose speed.

The fastest and most effective seems to be using a prefix-coder constructed using a package-merge algorithm (basically a tabled length-limited canonical huffman) with an adaptive (tree) block subdivider.

I squeezed another ~1700bytes from Zombies.SHP.
Very rough tests point out to me that ARJm7 is systematically beaten.

But I don't know, the decoder becomes much slower and complex.
I don't have a decompressor for 68k yet, but the feeling is that it should unpack faster than ARJm7.

For now I leave it on stand-by, I'm not too convinced.
The beauty of this decompressor is the extreme speed and the good compression, I would not want it to lose its qualities.

Only problem is the very slow compression, so to use only if you are aware of it

[defor]

Originally Posted by ross

For now I leave it on stand-by, I'm not too convinced.
The beauty of this decompressor is the extreme speed and the good compression, I would not want it to lose its qualities.

Two versions then?

Originally Posted by ross

Only problem is the very slow compression, so to use only if you are aware of it

I'm curious how slow is "very slow compression", in your tests on your configuration. Minutes, hours.... days?



Thank you ross for your great work.

[ross]

Originally Posted by defor

Two versions then?

Maybe..

I'm curious how slow is "very slow compression", in your tests on your configuration. Minutes, hours.... days?

Times grow quasi-exponentially with file size.

I'll give you some examples.
CosoPackxxx.bin is made up of more than a hundred small files, ranging in size from 1 to 15KiB.
Pre-compression (which is used to keep the indexed files compressed directly in memory) took less than a couple of minutes for all files.

But the "merged" file (153031 bytes) took about 15/20 minutes.
And from an old message you will have read that Zombies.SHP (245720 bytes) took 50 minutes.

The biggest file I compressed was main.bin (331380 bytes) from AmigaAtari demo: it took like.. hours (3, 4 maybe?)
And in this case I also had another problem: I compiled a 32-bit version and for a moment was afraid that the compression would fail because the memory usage exploded to 3.5GiB!
So maybe it's better if I also compile a 64-bit version..

In fact it was created for 8-bit systems, with files of 64KiB at max, in this cases the times are relatively acceptable.
Yes, I used an old i7 (and alway with maximum compression) but hmm, it's a bit slow
At least you can compress file in batches and using different cores.

[Don_Adan]

Header ZX01 Ross Packer mode 1
Header ZX02 Ross Packer mode 2

[ross]

Einar pointed me out to his new experimental ZX family compressor, ZX5.
Thanks,

Basically it extend the rep-match concept to the last three offset (like LZX).
"..ZX5 compressor is very much slower.." .. this sentence scares me a bit ..


When I have some time I try to play around with it a bit, I think it is not complicated to write a suitable unpacker for 68k starting from my sources (and with acceptable speed losses).
It might be useful to squeeze out a few more bytes
It remains to be seen whether any gain in compression is adequately compensated for by the loss of speed.

[a/b]

Originally Posted by ross

"..ZX5 compressor is very much slower.." .. this sentence scares me a bit ..

Ouch...
For zx0 it didn't take long to figure out I better modify the compressor to produce a script so I can then just bypass optimize(), and compress() the whole thing repeatedly in 1 second instead of waiting 40+minutes each time. So as long as there's no need to mess around with the optimizer it should be fine, one and done, but still... Very much slower .

Anyway, I'm "slightly" behind on this, real life work catching up. How relevant are those numbers of yours above? I have several versions with different sizes and speeds, some with original bitcode and some with modified. Just screwing around for now, still not happy with depacker, trying to combine a few not really compatible optimizations. Testing with my stuff and zombies.shr, don't have any of the other files you mentioned. Zombies compressed with 256k max offsets down to ~44870 bytes and decompressed in 1.228 seconds with a 150ish bytes depacker is kind of best what I have at the moment...

[ross]

Originally Posted by a/b

Ouch...
For zx0 it didn't take long to figure out I better modify the compressor to produce a script so I can then just bypass optimize(), and compress() the whole thing repeatedly in 1 second instead of waiting 40+minutes each time. So as long as there's no need to mess around with the optimizer it should be fine, one and done, but still... Very much slower .

Anyway, I'm "slightly" behind on this, real life work catching up. How relevant are those numbers of yours above? I have several versions with different sizes and speeds, some with original bitcode and some with modified. Just screwing around for now, still not happy with depacker, trying to combine a few not really compatible optimizations. Testing with my stuff and zombies.shr, don't have any of the other files you mentioned. Zombies compressed with 256k max offsets down to ~44870 bytes and decompressed in 1.228 seconds with a 150ish bytes depacker is kind of best what I have at the moment...

The bitcode is quite 'stable' now.

You have a PM