Jump to content
rensoup

Any compressor between rle and lz4 ?

Recommended Posts

I've been using the LZS technique to compress for a program I'm writing.  It seems fast enough.  I'm also working on my own compression technique for a package.  The latter uses LZ77, Adaptive Huffman Codes, two alternate methods of compressing literals, a method of shortening repeated LZ77 blocks and a method of writing data not in the range of a power of 2.  It's very large and slow.  :(   I could use a little help with that.  You can Google Wikipedia.com for Stac Compression for information on the LZS (Lempil Ziv Stac) technique.  As for my technique, I could use a little advice.  :) 

Share this post


Link to post
Share on other sites
16 hours ago, Harry Potter said:

I've been using the LZS technique to compress for a program I'm writing.  It seems fast enough.  I'm also working on my own compression technique for a package.  The latter uses LZ77, Adaptive Huffman Codes, two alternate methods of compressing literals, a method of shortening repeated LZ77 blocks and a method of writing data not in the range of a power of 2.  It's very large and slow.  :(   I could use a little help with that.  You can Google Wikipedia.com for Stac Compression for information on the LZS (Lempil Ziv Stac) technique.  As for my technique, I could use a little advice.  :) 

 

The core idea of LZS, which is first Adaptive-Huffman coding the lengths and offsets in hundreds of test files, and then coming up with a Static-Huffman coding scheme that averages out the results from all of those files so that you can avoid the time-consuming Adaptive-Huffman step ... well that is basically where most of the different LZ-style compressors came from in the late 80s and early 90s, just using different coding schemes.

 

When you do the testing, you find that short matches, or short runs of unmatched-literals, are far more common than long runs. You also find that match offsets are more commonly close to the current data than far away from it.  This leads to the kind of encoding schemes that you commonly see today (for 8-bit and 16-bit micros).

 

While I encourage you to have fun experimenting with creating your own format, because you will learn a lot ... you will find that you'll have a very hard time beating LZSA1 and LZSA2, which are pretty optimized versions of that scheme.

 

Better compression seems to need a slightly more adaptive solution, and Huffman is one way of doing that, but it has decompression-speed and code-size penalties that ususally aren't worth the trouble on old computers.

 

Elias gamma coding is another scheme that does seem to offer worthwhile benefits, as show by the aPLib and ZX0 compressors.

 

Improvements beyond those tend to involve some really clever, but slow, techniques that just aren't well suited to run on older hardware.

 

 

If you are writing your compressor to run on the Atari itself, then some of the compression speedup techniques just won't be available to you because of the limited memory size.

 

If you are writing your compressor to run on a modern PC, then I suggest that you take a look at Jørgen Ibsen's BriefLZ compressor, and note its use of hash chains for finding match repeats, which seems to be the 1st step in speeding up a simple LZ-style compressor.

  • Like 2

Share this post


Link to post
Share on other sites
On 3/29/2021 at 1:57 PM, elmer said:

I've now written, and experimented with optimizing, a decompressor for ZX0 ... and it's an interesting format. :)

 

After taking a look at ZX0 decompressor in the bitfire project, I decided to do some more optinmization work on my ZX0 decompressor, and to optimize the code for the fact that match and literal lengths are almost-always less than 256 bytes.

 

The result is an approx 9% improvement in decompression speed, at a cost of adding 4 bytes of code, so the decompressor is now 196 bytes long.

 

Tobias's bitfire decompressor is between 0% and 3% faster to decompress, depending upon the data file, but it is 15% (30 bytes) longer, so I'm happy with the tradeoff.

 

I have applied the same optimization to my LZSA1 and LZSA2 decompressors, so while the ZX0 decompressor is better than before, it is still 25% slower than LZSA2.

 

 

zx0_6502.mad

Edited by elmer
  • Like 3

Share this post


Link to post
Share on other sites
On 4/4/2021 at 1:47 PM, elmer said:

I have applied the same optimization to my LZSA1 and LZSA2 decompressors, so while the ZX0 decompressor is better than before, it is still 25% slower than LZSA2.

I have tried to improve my ZX0 (not DX0 as I was incorrectly saying earlier) a few times over the previous months, but while I can make some small improvements to the speed ... the cost in terms of the size increase is never worth it (IMHO).

 

The same happens with the changes in ZX0 for the "new" improvements (targeted at the Z80 CPU) ... the 6502 decompressor is both slower and longer if that "new" format is used, so I recommend folks to just use the option to write out the "old" or "classic" ZX0 format, and to use the assemly-language code that I posted earlier to decompress it.

 

The REALLY BIG news is that Emmanuel Marty released his own much, much, much faster ZX0 compressor a few days ago, and this should now (hopefully) make ZX0 a good replacement for general-purpose development, and it will probably relegate LZSA2 to the trash-bin, along with so many other "great-in-their-time" ideas. ;)

 

You can find Emmanuel Marty's new compressor here ...

 

https://github.com/emmanuel-marty/salvador

Edited by elmer
  • Like 1

Share this post


Link to post
Share on other sites

Some quick testing shows that, yes, the new compressor turns ZX0 into something that is (IMHO) usable for development! ;-)

 

File         Size    Compressor       Time
==========================================
PoPCore.bin  40,164
PoPCore.lz2  23,922  lzsa.exe -f2     1.0s
PoPCore.zx0  23,310  zx0.exe -quick   2.5s
PoPCore.zx0  22,655  salvador.exe     1.0s
PoPCore.zx0  22,646  zx0.exe         35.5s

 

  • Like 3

Share this post


Link to post
Share on other sites

Whoops ... there was a small bug in my ZX0 decompressor when handling matches that were a multiple of 256 bytes long ... which are so rare that it didn't get caught earlier.

 

Luckily, the fix actually saves a few bytes and makes the decompressor a liitle faster! ;-)

 

Since nobody is complaining about the decompressor size, I've kept it at the same 196 bytes long, and added another 2 branch-unlikely optimizations to make it a tiny bit faster.

 

Here is the fixed decompressor ...

 

 

 

zx0_6502.mad

  • Like 4

Share this post


Link to post
Share on other sites

I have some ways to better the technique, but most of them I want to keep secret for now.  Of the techniques I don't mind revealing, only one helped me noticeably, and it only helped me slightly.  Should I reveal it here?  I also ask you to try to add Adaptive Huffman Codes to the technique.

Share this post


Link to post
Share on other sites
20 minutes ago, Harry Potter said:

Should I reveal it here?

Are you really sure we are worthy? 🙄
(Tell it or keep it but don't make a fuss about it...)

  • Haha 3

Share this post


Link to post
Share on other sites
32 minutes ago, Irgendwer said:

Are you really sure we are worthy? 🙄
(Tell it or keep it but don't make a fuss about it...)

My years of experience with compression is that if people want to keep their method secret it usually doesn't work, or is an old concept they were not aware of.

 

Perhaps Harry Potter could look into recursive compression. That would be really great to have on the memory limited Atari!

Edited by ivop

Share this post


Link to post
Share on other sites

My technique is simple: If an LZ77 block is found, check the next byte.  If it results in a larger LZ77 block size, don't compress the current byte.

 

BTW, I want to hide the technique for only a short while.  If it succeeds, I want to reveal it a couple years after its debut.  As far as it working, it is in its Alpha stages, so it currently does not work.  :(

Share this post


Link to post
Share on other sites
44 minutes ago, ivop said:

it usually doesn't work

 

19 minutes ago, Harry Potter said:

so it currently does not work

 

Point made.

  • Thanks 1
  • Haha 1

Share this post


Link to post
Share on other sites
1 hour ago, Harry Potter said:

My technique is simple: If an LZ77 block is found, check the next byte.  If it results in a larger LZ77 block size, don't compress the current byte.

 

So, you're talking about "lazy" coding the matches instead of the traditional "greedy" coding. Yes, that definitely helps the compression!

 

This is not new,  and I'm afraid that you're a couple of decades behind the state-of-the-art.

 

The next step beyond what you're proposing is obvious, and that is to look 2 bytes ahead.

 

The cool programmers these days are using "optimal" coding of the compressed stream, but that takes some pretty-sophisticated techniques that just make my head hurt! ;)

  • Like 1

Share this post


Link to post
Share on other sites
1 hour ago, Harry Potter said:

At least you like my idea.  :)

Of course - ideas that have been proven for decades are usually liked.

Share this post


Link to post
Share on other sites
1 hour ago, Harry Potter said:

Should I reveal my technique here now?  Or should I debug it first?

Since I'm sure you don't like to waste our time with half-baked or half-working (only the deflating works, but not inflating) software, take your time establishing a full round-trip tool chain before publishing.

 

You're welcome!

  • Like 3

Share this post


Link to post
Share on other sites

What an effort for just a single block. I go to my basement and immediately find lots of blocks and bricks. 

  • Haha 2

Share this post


Link to post
Share on other sites
On 11/30/2021 at 3:29 PM, Harry Potter said:

Hi!  I just applied MTF to the ZX0 technique and saved one more block.  :)  I need to debug it now.  Should I reveal my technique here now?  Or should I debug it first?

 

So, you applied a move-to-front transform on the input stream, and it improved the compression (just like it was designed to do) ... congratulations!

 

https://en.wikipedia.org/wiki/Move-to-front_transform

 

Unfortunately, the decompression is now slower than before, and it needs to keep a bunch of extra information around, thus using more memory.

 

Whether the time-vs-space tradeoff is worth it to you, is something that only you can decide ... but I'm glad that you're having fun experimenting.

Share this post


Link to post
Share on other sites

I tweaked the technique a little further and bought some more points but not a whole block.  :)  Now, I'm down to 19 blocks.  BTW, elmer, I probably only need 256 bytes for the MTF buffer, 64 bytes for the data to compress and no more than 512 bytes for the rest of the MTF code and data.  So, everything should fit.

Share this post


Link to post
Share on other sites

Milestone achieved! 18 blocks!  :)  I increased the sliding dictionary size by 256 bytes.  Now, it's 3.25k.  I will up it to 3.5k.  I have 4k allocated to the LZ buffer, but some of it is unused, as the program fills the buffer at 3800 bytes used.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...