RZM - a dull ROLZ compression engine

[Hahobas]

Actually, for a context mixer whose inner loop has a couple of branches, its quite easy to predict the branching behaviour.

Yeah, with CCM I bet that is the case. Looking forward to a new version, and if youre in the mood we could try a 64bit version . If you dont have a 64bit machine you could just use QEMU and run a 64bit VM. Id be happy to test the 32bit vs 64.

Im glad youre not giving up on CCM, its by far my favorite compressor.

[toffer]

Do you have any other tips for us? I was quiet surprised how less i know about gcc's switches and things like this - what a shame, i'm using gcc for years...

BTW: Christian, how do you model bits? Do you use any mapping like paq's states, or do you directly model bits by counters?

[Christian]

Do you have any other tips for us? I was quiet surprised how less i know about gccs switches and things like this - what a shame, im using gcc for years...

Same here - I tried a few switches and always lost interest after a couple of minutes.


toffer
I use small state machines - should be similar to paq states.

[toffer]

One of the things on my todo list is to generate several state machines for different orders. Do you have any experience with this? I did a state machine, which is more efficient than paq's at order 0. But i don't want to waste my time in doing this for every order...

[Christian]

One of the things on my todo list is to generate several state machines for different orders. Do you have any experience with this?

I tried, but I rejected the approach because improvements were a mixed bag - and I wanted to keep the code small. Additionally, mixing/SSE cushions the effect, too.

Good night.

[encode]

By the way, Criss, do you plan to release the source of your compressors? (CCM, RZM, SLUG,...)

[Christian]

No plans anymore. For me, it's a must to have the source in a nice state before releasing it. But e.g., I never even 'cleaned' CCM's source because I already moved on to RZM and stuff. There are so many OS programs whose source code is a living hell - I don't want to contribute to that. Additionally, I do not think, CCM's source would be of great use. Most people would just rip some ideas out of it and that's it.
Currently I'm working on something new, which is not 'directly' related to compression. So, again no spare time to tidy up...

[toffer]

No plans anymore. For me, its a must to have the source in a nice state before releasing it. But e.g., I never even cleaned CCMs source because I already moved on to RZM and stuff. There are so many OS programs whose source code is a living hell - I dont want to contribute to that. Additionally, I do not think, CCMs source would be of great use. Most people would just rip some ideas out of it and thats it.
Currently Im working on something new, which is not directly related to compression. So, again no spare time to tidy up...

As i said in some other post i mostly like the idea of information interchange (not the copy and paste thing...)

[Bulat Ziganshin]

i'm interested in using rzm in freearc. how about releasing it under GPL license?

[encode]

As i said in some other post i mostly like the idea of information interchange (not the copy and paste thing...)

...or paper/post describing some ideas and principles...

[Christian]

As i said in some other post i mostly like the idea of information interchange (not the copy and paste thing...)

I like information interchange much better than copy&paste, too. Insight is much better than blind trust.

...or paper/post describing some ideas and principles...

Honestly, I work on data compression one or two hours a week - as a hobby, of course. Sometimes more and most of the time much less. But I can think of many things more interesting/important than writing a paper about my compressors. Btw., I recall, that youve planned writing a paper about ROLZ yourself. But still, you can send me mail, if you have some questions.

how about releasing it under GPL license?

I have no plans for that.

Btw., for now, work on CCM/RZM/... is frozen. I just cant stand all those requests I get. Maybe I have to get a thicker skin for data compression.

[encode]

Btw., I recall, that youve planned writing a paper about ROLZ yourself.

Its done some time ago (in Russian though):
http://ru.wikipedia.org/wiki/ROLZ

[Christian]

Here's a new compilation of RZM. Nothing really new, but I moved to GCC 4.3.0 using profile optimization. Thanks again to Hahobas (and of course the GCC guys) who pointed my at this technique. It might be a tiny tiny bit faster - or not. Just try it out.

RZM 0.07f

[Christian]

One more new compile. Acutally, this includes a little bugfix, too. Now, memory allocation for compression really is ~258M. Additionally, compression and decompresssion speed are slightly faster than 0.07e.

Download RZM 0.07h

[Bulat Ziganshin]

0.07e?

[Bulat Ziganshin]

this new site prohibits downloaders from Russia

[Christian]

So, I'll upload all files to Rapidshare and their funny cats ... again.
But this has to wait for tomorrow - perhaps LovePimple can host the files before that.

[Christian]

this new site prohibits downloaders from Russia

Maybe you can try to use a proxy. Anyway, sorry for the inconvenience.

[encode]

Try out the Send Space:
http://www.sendspace.com/

[Bulat Ziganshin]

i don't had more luck with rapidshare because there are many thousands users sharing the same IP due to our provider's NAT

actually, i'm not hungry about others' programs and LovePimple page is enough for me, i noted it just to inform you that it may be inconvenient for other users

[Bulat Ziganshin]

http://www.sendspace.com/

successfully tried to upload & dl file here

[LovePimple]

Thanks Chris!

Mirror: Download

[Black_Fox1]

How about a googlepages web? Shelwien is using that and there was no complaint so far. Additionaly, no dogs, cats, timeouts and whatsoever

[Christian]

RZM now has a homepage to circumvent the web hosting nuisance.

Thanks for clue the BlackFox. The latest problems finally made me create a small home page. Curiously, googlepages is very slow for me - although, the homepage is like 2 or 3 kb.

[encode]

By the way, Criss, can you explain how do you perform a string search? Do you use hashing or BT? And how do you deal with ROLZ nature? As you posted above, you keep an offset table:
offsets[win[i-1]][...]
Just thinking about an improved ROLZ scheme. With LZPM, I use hash chains, to determine the match index I keep the char count in the hash element with actual offset. If we will add a phrase per each byte, I think we may simplify the search...

[Christian]

By the way, Criss, can you explain how do you perform a string search? Do you use hashing or BT?

In RZM I use binary trees. Of course, Slug uses hashing for speed reasons.
I described the idea of string-insertion for binary trees in the tornado 0.4 topic. If you understand it then string search is easy. Since RZM uses optimal parsing it needs to search at each position - therefore, you just search while inserting the string for the current position.

And how do you deal with ROLZ nature? As you posted above, you keep an offset table:
offsets[win[i-1]][...]

The size of each table is fixed (as it is hinted on Slugs homepage) to 64K entries. RZM adds one offset for each step - additionally it keeps some long distance offsets for better handling of compressed data.

If we will add a phrase per each byte, I think we may simplify the search...

Is this related to hash chaining? If not, what exactly do you mean?

[encode]

I described the idea of string-insertion for binary trees in the tornado 0.4 topic.

OK, will carefully read this topic.

Is this related to hash chaining?

Yes, Im just thinking, how we can translate the real offsets into match indexes. In other words, we may use pure LZ77 with MINMATCH=4 (as BALZ v1.04) and then drop first byte of a match as a literal and encode match length of three, plus, an offset as index. Generally speaking, LZPM does it exactly in such way, but for offset->index translation LZPM keeps byte counts - i.e. cnt[c] - keeps count of cs. Thus, match index = cnt[c]-node.cnt;

Although, you may test the latest BALZ, its not that worser than LZPM, in most cases its even better, especially on binary data. So, now Im thinking about further improving LZ77 scheme especially in offset coding, maybe better buffered offsets technique, etc.

[Bulat Ziganshin]

Christian, is rzm still limited to files <2gb?

and - how about adding faster lazy-parsing compression mode?

[Christian]

Christian, is rzm still limited to files <2gb?

Yes.

and - how about adding faster lazy-parsing compression mode?

Great idea, but sadly - no time. And originally, RZM is about strong asymmetric compression.