Is there a better packer than arjm7?

[leonard]

Hi! didn't read that thread for a while, a lot of interesting things here!

Ross, so you have a modifyed zx0 packer than can beat arjm7 on AmigAtari data files?

[ross]

Originally Posted by leonard

Ross, so you have a modifyed zx0 packer than can beat arjm7 on AmigAtari data files?

Yes, and you could probably also reinsert (some?) 'deleted' modules from the CosoPack.
However, you must remove the support for LZ4 and replace the pre-compressed ones always with ZX0.
I don't think anyone would notice the speed change for pre-packed.
But beware that the support for unpack-when-loading is completely to be invented/implemented.

To tell the truth in the past few days I have not looked at the ZX0 code (too many other things) and I would like to try ZX5 (which I think can be ported to 68k very easily).
Also I would like to understand if some a/b's ideas can be adapted.

[ross]

First release using 68k ZX0 on Amiga:
http://eab.abime.net/showthread.php?t=108712

It's implemented like 'stacker', with game cylinders packed stand-alone, in a big indexed virtual disk.
The other single files are also compressed with ZX0 (apart from the initial module which is ADPCM encoded with the decoding done during the beginning of the intro, but that doesn't count ).

Actually in the end I had so much space left that I could also have used another packer, but that compression factor at that speed is unbeatable!

[introspec]

Hi guys, I did a lot of work on fast decompression for Z80 and I think some of our tech could be useful for you as well. ZX0 is an amazing format with a couple of very modern tricks, so it can compete (almost!) with zip-style compressors, even though it does not come with an entropy coder. The compressor is terrily slow, but if you can afford to lose, maybe, 0.3-0.5% compression (at most), there is a new packer written by Emmanuel Marty that is orders of magnitude faster: https://github.com/emmanuel-marty/salvador
On some files it beats the original compressor too.

Since you mentioned LZ4 several times in this thread, I think that you may also want to have a look at LZSA compressor, also written by Emmanuel Marty: https://github.com/emmanuel-marty/lzsa
It comes with 2 compression formats: LZSA1 and LZSA2. LZSA1 was designed intentionally to compete with LZ4 and it does beat LZ4 both in compression ratio and in decompression speed (basically, it requires less work in the main loop, so correctly designed decompressor should always beat LZ4). LZSA2 is somewhere in between LZSA1 and ZX0 - compresses approximately at the level of NRV2B, but can be decompressed much faster, due to the active use of bytes and nibbles in the compressed stream.

Last but not least, I created the compression ratio/decompression speed diagrams listed earlier in this thread. It is important to understand that they were generated for (mostly) my decompressors and for Z80. I have no way of testing 68k decompressors, esp in terms of the decompression speed, so your mileage may vary depending how well optimized your decompressors are. I have examples of Z80 decompressors that I could make twice as fast as they were originally, so please be careful when comparing the compressors with each other. Just any decompressor will not automatically get you onto the Pareto frontier.

[ross]

@introspec: thanks for the post (and welcome).
Your name ring me a bell.. probably I've seen you 'elsewhere' before

I'll check "salvador", but this sentence needs to be deepened:
"The compressor can pack files of any size, however, due to the 31.5 KB window size, files larger than 128-256 KB will get a better ratio with apultra."
With the original source of ZX0 it is trivial to enlarge the compression window (so much so that in my command line version it can go up to 2^23).
Maybe the same thing can be done in this optimized version , it's a focal point for the 68k if you want to achieve noticeable compression factors.

Also LZSA2 could be interesting.

[introspec]

Originally Posted by ross

Your name ring me a bell.. probably I've seen you 'elsewhere' before

encode.su? or pouet.net, most likely. In any case, as ZX Spectrum coder, I am likely to recognize more nicks of Amiga coders, than Amiga coders who would recognize mine. The whole history of Spectrum scene, esp. in the East, is just a large Amiga appreciation society.

Originally Posted by ross

I'll check "salvador", but this sentence needs to be deepened:
"The compressor can pack files of any size, however, due to the 31.5 KB window size, files larger than 128-256 KB will get a better ratio with apultra."
With the original source of ZX0 it is trivial to enlarge the compression window (so much so that in my command line version it can go up to 2^23).
Maybe the same thing can be done in this optimized version , it's a focal point for the 68k if you want to achieve noticeable compression factors.

Well, the limit to 32K window in the design of ZX0 is mostly a performance and complexity optimization on the decompression side. It does not harm the compression too much, because our files are rarely larger than ~40K. I am sure that increasing the window size in the Salvador is trivial too, and because it does its match searching via suffix arrays, it would scale to larger window sizes much better too. Of course it won't be ZX0 format after this, so an extension would be needed - a different stopping condition most likely. I'll mention this to Emmanuel, the additional compressor option may be an easy way to do it.

Originally Posted by ross

Also LZSA2 could be interesting.

LZSA is designed to offer multiple choices along the Pareto frontier, so it does not make much sense to focus specifically on LZSA2 or LZSA1. In situations where only compression ratio matters ZX0 would offer better compression. However, when decompression speed becomes a consideration, you typically want to compress as much as you can given a fixed decompression time. LZSA allows you to do something approximating this behaviour.

This is a more up-to-date version of the diagram from earlier in the thread:

As you can see, LZSA1 and LZSA2 offer multiple points along the Pareto frontier. This is achieved by providing an option to avoid compressing some of the costlier (in decompression speed) matches, which reduces the compression ratio while increasing decompression speed. So you can decompress significant amounts of data in realtime, and if the speed is a bit too slow for your specific data, you can lose some of the compression ratio to speed things up. Or conversely, you might recognize that you have plenty of spare time left and switch to a higher-compression variation of the algorithm.

[introspec]

Originally Posted by ross

With the original source of ZX0 it is trivial to enlarge the compression window (so much so that in my command line version it can go up to 2^23).
Maybe the same thing can be done in this optimized version , it's a focal point for the 68k if you want to achieve noticeable compression factors.

Can you document the specific format extension that you are using for your project? I.e., to have larger window size, you had to modify the end of the stream marker. How exactly did you do it? Did you make any other changes to the compressed data format?

[ross]

Originally Posted by introspec

Can you document the specific format extension that you are using for your project? I.e., to have larger window size, you had to modify the end of the stream marker. How exactly did you do it? Did you make any other changes to the compressed data format?

Yes, bitcode is slightly different and end code marker is moved to literal run path.
Everything has been thought to be as fast as possible for 68k architecture (and it is much faster that original decoder).
Now the elias bits are inserted in/for two different configurations: positive or negative return numbers, depending on usage;
as I use unrolled code it's not a problem at all, but you cannot use anymore subroutines to extract bits.

The single bit 'unrelated' to the offset (which is used for the length of the match and is in the LSB position of the read byte) is moved in main bitcode stream, and in its place, but in the MSB position, is inserted a (Elias) bit that tells me if I have a short (7-bit) offset or a long one, to be completed with the streamed elias-gamma bits (to form a possible 2^23 offset, encoded as negative).

The exit is moved to literals run for two reasons:
- can eventually shorten the bitcode (and add a free helper for in-place unpack)
- it's the only way to handle >32k literals that can overflow the bitcoding
It basically add an escape code to copy till 163835 (repeatable 'ad infinitum') bytes at a time; it requires exactly two bytes +1bit (to re-align to bit stream).

If your encoding ends with a match (both rep and normal) then add the specific 31-bit code for the output without further copying (direct exit).
If your encoding ends with literals you can free use a copy till 32764 bytes.
If your encoding ends with >32764 you can use the escape code (literals overflow) until you end the queue.
During normal code flow you can use directly till 32769 byte of literals.
This way there is also an escape code usable to facilitate in-place unpack.

Well, yes, can be confusing without examples, but 68k handle it very well with some implicit properties
Probably the source code is better for a correct understanding (both encoder and decoder).

[introspec]

Originally Posted by ross

Yes, bitcode is slightly different and end code marker is moved to literal run path.
[...]
Now the elias bits are inserted in/for two different configurations: positive or negative return numbers, depending on usage; as I use unrolled code it's not a problem at all, but you cannot use anymore subroutines to extract bits.
[...]
Probably the source code is better for a correct understanding (both encoder and decoder).

Obviously, I understand that this may be a part of some closed-source project, but do you have at least an open-source decompressor, so that we can figure out the format? Because I do not think your notes are sufficient to implement the algorithm consistently.