BCM v0.08 - The ultimate BWT-based file compressor!

[michael maniscalco]

[*]Invented new conception in BWT-output encoding. Still no cheating or tricks like M03

I just noticed this line. How is it a "trick" or "cheating" to get full order context modeling of the BWT for encoding?

M03 doesn't involve any preprocessing, alphabet reordering, RLE or secondary transforms or any filtering of any kind. It's basically optimal parsing of the BWT string along all context boundaries for each context order and nothing more. Hardly "cheating" ...

[encode]

At the first sight M03 looks like CM with BWT-structures to access the statistics...

[encode]

The compressor is featured in the BWT comparison.

[encode]

Currently I'm working under BCM v0.09. And again have many proofs that proper CM is supreme to anything. As example, order-0 CM works better than MTF+order-0 CM. Yep, MTF may help with dummy coders, but with even simple CM it only hurts. MTF stage makes data more stationary, but removes some correlations and adds some noise thus compression with CM degrades very seriously. So, I think the future of BWT-output coding is more advanced CM coders. Furtunately, we have unlimited ideas and ways here. As example, I invented a very special model that is derived from ICM idea. And such standalone model provides 213,886 bytes on book1!!! And it's close to the BBB result, being super-fast, because the complexity of this model is equal to two[!] counters! I'm still under heavy experiments and very creative ideas about BWT-output encoding... Additionally, I'm playing with different contexts for CM and various ideas such as QLFC...

[Yuri Grille.]

This is a optimized bcm in only (48.7 KB)

[removed]

Enjoy this good compressor

[encode]

I think that a difference in a few KB not worth such slow launch... Better I will release a small size-optimized compile of the BCM... Anyway, I always prefer to keep the ONE speed-optimized compile of the compressor!

[Yuri Grille.]

I think that a difference in a few KB not worth such slow launch... Better I will release a small size-optimized compile of the BCM... Anyway, I always prefer to keep the ONE speed-optimized compile of the compressor!

Yes ,this is true , I make this with the purpose to make a very small size to you send this to the benchmarks , when you open this .exe is a liter slow. Sorry my bad English

[Skymmer]

This is a optimized bcm in only (48.7 KB)

I wonder what packer and manipulations it made with. Surely its kkrunchy. But I was able to shrink it down to 51 200 bytes only with latest kkrunchy v0.23a4_asm07 so I think some other things have been done also. Yuri, can you give a comment on it please ?

[encode]

BWT, a quite suspicious file:
http://www.virustotal.com/ru/analisi...bda-1244580064

[Black_Fox]

It's the same sad story as with UPack...

[encode]

Anyway, I decided to prohibit such things. We should use a stable, free and clean EXE-packers, such as UPX.
Each version of BCM must have ONE executable, without slow "re-packs" and hacks. All versions should be provided by the author.
If someone will spread another versions of BCM or any of my work, that user will be banned...

[nanoflooder]

Why At which point encode.su has become a refuge of reliable and stable software?

I'm not being offensive, I'm just curious

[encode]

Why At which point encode.su has become a refuge of reliable and stable software?

I'm not being offensive, I'm just curious

My programs are reliable and stable. It's the prime target - the QUALITY of my work. The quality of all details is on the first place. Very carefully design and testing of a code and a program... I'm extremely pedantic here. And the main thing, programs should not be detected as a threats by AVs.

[Yuri Grille.]

[the message accidentally has been deleted, sorry]

The reason to use upx is because the mostly Antivirus can unpack this.

[encode]

The reason to use upx is because the mostly Antivirus can unpack this.

Additionally, and the most important thing, UPX has official unpacking...

[Yuri Grille.]

Why you delete my post "accidentally" , this is a free forum ??.

I'm not steeling you software only I make a optimization to less some kb, please don't delete my post.

THis is some like original post:
-----------------------------------------------------------------------
I am using the secret version kkrunchy v0.25 , you don't have this version because I'm the creator of this software . Jajajajaj

No that is false , this optimization is a manual optimization of the program with a hex editor and Olly debugger , always the compilers of high level like the BCM put unnecessary data on the .exe , you can replace this data with null data to make "more easy" to the .exe packer , this can be a easy work or difficult on dependency of the program , if you need I can make a manual "How to optimize .exe" , but I need the help of somebody to help me with the English , because I speack spanish and I don't have a advance knowledge of the good English.

http://sites.google.com/site/compactamos/descargas

etc......

[encode]

Accidentally means accidentally!

I have a Spanish translator... If you will post rude messages, you know what will happen!

[Yuri Grille.]

Sorry me ,but don't delete my "no rude post".

[encode]

Finally, new BCM beats M03 at ENWIK5!
Actually, using ICM with SSE is questionable. So, new BCM have no ICM models. Instead, I added a few SSE stages...

[Intrinsic]

Why you delete my post "accidentally" , this is a free forum ??.

I'm not steeling you software only I make a optimization to less some kb, please don't delete my post.

THis is some like original post:
-----------------------------------------------------------------------
I am using the secret version kkrunchy v0.25 , you don't have this version because I'm the creator of this software . Jajajajaj

If you are saying you are the author of kkrunchy, then stop talking crap, i know who the author of kkrunchy is, and you are not him. Just like you claimed back in the psd thread you were the creator of a method for "shrinking" psd files although it had already been around for many many years.

[Bulat Ziganshin]

Intrinsic, he is joking - read entire post!

and psd trick is so simple that he should find it independently

[encode]

With a new approach, ~209100 bytes on book1 is easily possible. Anyway, my goal is ~208xxx bytes...

[encode]

Yes!
I've got ~208xxx bytes on book!

[encode]

This time the compression gain will be much bigger (v0.08 -> v0.09) than previously (v0.07 -> v0.0. Unfortunately, the cost of an extra compression is an extra processing time. Anyway, new BCM is just a next level...

[encode]

BCM v0.09 has been written. And it's HARDCORE! Apart from much improved CM, I did many very important optimizations, some parts of the code was completely rewritten. Anyway, even with such extreme optimizations new BCM is notable slower. Personally, I think that such extra and record breaking BWT compression worth it. I just need to do some additional tests and optimizations to get its full potential. Also, I think that BCM v0.09 will be kind of a final version. Or at least I will do some break in its development.

OK, here are some results of the release candidate (plus previous results, for comparison):
book1 -> 208,863 bytes (209,826 bytes)
calgary.tar -> 775,924 bytes (779,619 bytes)
world95.txt -> 463,939 bytes (466,250 bytes)
fp.log -> 548,714 bytes (557,226 bytes)
ENWIK8 -> 20,638,938 bytes (20,744,613 bytes)
bible.txt -> 721,809 bytes (725,091 bytes)
3200.txt-> 3,644,158 bytes (3,660,195 bytes)

[Shelwien]

I just checked and bwmonstr's result on book1
with alphabet reordering is 203928.
And 205397 by default.

Did you finally believe that its not really possible to go under 208k
with standard BWT and postcoding, or what?

[encode]

Well, I think that it is possible to get ~207xxx bytes on book1 using a standard BWT and direct coding (with no alphabet reordering or transformations of any kind). My CM already can produce about 208400 bytes on book1. It is complex enough, but I easily can imagine something a far more complex. The problem is, using an extremely complex CM will kill any BWT benefits - better use pure CM in this case...
For sure, with direct coding ~205xxx on book1 is not really possible.
Don't know what the heck BWMonstr is, Sami keep silence. Anyway, it's too way slow. M03 is OK, but again it's too slow, and furthermore, new BCM v0.09 both faster and has a higher compression than M03...

[encode]

Shelwien changed the direction of the further BCM development. Of course I always may add some extra models and dynamic mixing to beat BWTmix... But it will be SLOW! So, what is the goal? Overloaded BWT with a PAQ speed? Nope! Now I think to make BCM more lighter and faster. Since it's not the strongest anymore, I will do it really practical. I already did some serious and fundamental speed/structure optimization with my unreleased BCM... Anyway, the idea is to keep the most important models with a static mixing plus one SSE. Heavy versions may have lots of models with dynamic mixing, many SSE stages... It's cool, but again better use just a CM - we loose all of the advantages of BWT. At the same time, experience with such over-weighed CM-back-ends as unreleased BCM009 and BWTmix really help to find out what kind of models/techniques are the best and how close the lighter CM is...

[Shelwien]

> Of course I always may add some extra models and dynamic mixing to beat BWTmix...
> But it will be SLOW!

Not necessarily. Well, it might be, if you'd really just _add_ something.
But current BWTmix model is really simple, and doesn't use SSE or fsm
counters, so there're certainly ways to beat it.

> keep the most important models with a static mixing plus one SSE

Don't forget about fsm. Basically, it should be possible to approximate
a few counters (maybe even with some small contexts) + dynamic mixing + SSE
by a pair of lookup tables (p=P[state] and state=update[state][bit])
Well, with increasing original state size (all counters, mixer and SSE states)
it becomes harder to enumerate all submodel states and determine which are
relevant, but that's what makes it interesting
And a pair of counters with static mixing is an obvious target for that.

> At the same time, experience with such over-weighed
> CM-back-ends as unreleased BCM009 and BWTmix really help
> to find out what kind of models/techniques are the best
> and how close the lighter CM is...

Well, as I was always saying... its just rational to get as
much compression as possible - basically to estimate
the data redundancy, and only after that start to optimize
on speed, knowing the cost of compression you're losing.

And BWTmix is not really "overweighted" - its just a very
straightforward implementation, which probably would be
able to reach the speed of bcm008 if optimized.

But as a result of such statements, I'm currently working
on speed optimization, instead of SSE2 and stuff, contrary
to my theory
Well, its just a rangecoder optimization for now, so I hope
that it won't mess up the prediction stage. Btw, I managed
to reduce the number of rc calls more than in half:
http://shelwien.googlepages.com/p2.txt
Well, somehow it didn't improve the speed right away, but
that's probably because of some compiler weirdness

It was like this:

if( DECODE ) {
  dbit = rc.BProcess<1,1>( p0 );
  if( dbit ) { UPDATE(1) } else { UPDATE(0) }
}

and now its like this:

if( DECODE ) {
  dbitx = (p0>=hSCALE); //p0>>(SCALElog-1);
  int pr = p0 + ((SCALE-p0-p0)&(-dbitx));
  if( pr<M_p0lim+M_p1lim ) {
    if( pr<M_p0lim ) {
      if( b0count<0 ) dec_dist( rc, b0count, 0, M_ex0wr, M_ex0mw );
      dbit = (b0count>0); b0count--;
    } else {
      if( b1count<0 ) dec_dist( rc, b1count, 1, M_ex1wr, M_ex1mw );
      dbit = (b1count>0); b1count--;
    }
  } else {
    dbit = rc.BProcess<1,1>( pr );
  }
  dbit ^= dbitx;

  if( dbit ) { UPDATE(1) } else { UPDATE(0) }
}

And these counts are up to millions on enwik8, so
I'm not sure what exactly takes away the time saved
on rangecoder calls.

Anyway, seems like I'm going to keep experimenting with
BWT postcoders too, for a while, as there're many more ideas
which I'd like to try out .

[encode]

Inspired by Shelwien, started experimenting with the dynamic mixing. Written my own high-precise dynamic mixer... Optimizer just started, will see what will happen...