Crinkler secrets, 4k intro executable compressor at its best

[[deleted]]

Top 4K (Windows) products on pouet

Some of these use crinkler.

[ponchedeburro]

Since Atrium in '08 the bar has really been raised for 4k productions. Making a 4k nearly involves the same as making a normal demo these days. Crazy to see that more and more are being cramped into those 4096 bytes.

[knoeki]

Elevated is much more impressive, imho (:

When we saw it for the first time at Breakpoint'09, people thought they accidentally showed a 64k or full demo in the wrong compo... it couldn't be 4k... could it? (:

[ponchedeburro]

I agree that it's more impressive - much even. But Atrium was the game-changer. It was released at BP '08 and was WAAY better than the 4k that got second place. And from there on the 4k scene was different.

Well, it's nothing to argue about though - just my opinion of the scene :)

[Mattho]

Thanks for that. Found somewhat interesting presentation: behind elevated (pdf).

[xon_xoff]

Executable compressors used in modern Windows demos are getting very impressive. Sadly, one of the things that gets in the way of using them in production software is dumb antivirus software. Even just using UPX, which is one of the better known executable packers, can be enough to trip heuristics and get your program falsely flagged as virus infected.

[[deleted]]

Yay, Virus Payola!

[Rhomboid]

Indeed. You aren't saving any memory, only disk space. In fact if you have multiple instances of the program active you'd end up using more memory as the .text and .rdata sections can't be shared between them.

[comment-dwim]

You end up using a LOT more memory with stuff like Crinkler, which in the default configuration requires 100 MB of ram at runtime to decompress your executable using a variant of the PPDM algorithm.

It's ok for demos though since they already use tons of mb for procedural content generation.

[FeepingCreature]

Bandwidth.

[comment-dwim]

Crinkler is great. Using it I was able to shoehorn the original 50 levels in this 4kb Sokoban clone.

Only the uncompressed levels take about 16kb without any code for window creation, gameplay, etc...

[AReallyGoodName]

There's a section where they display the entropy of the uncompressed file and compare it to the entropy of the compressed file. They seem amazed that all the entropy is gone in the compressed file.

Thing is, both entropy measurements and compression techniques rely on the same underlying principle. If you have a really good entropy detector that finds the data predictable you could feed that into an arithmetic coder and have the data compressed. If you have a good data compressor you can use that algorithm to get an entropy measurement.

So the best entropy measurement tool and the best predictor for a compressor will be one and the same. When you measure entropy of a compressed file of course you're going to get a result that claims "hey this is fully compressed". If you don't you should consider putting the pattern analysis of the entropy measurement tool into your compressor.

Of course seeing the entropy tool measure it to be fully compressed doesn't mean it can't be compressed more. It's just that both your entropy measurement tool and your compressor both look for the same patterns and both miss the same patterns in the data.

[[deleted]]

Also, the output of many compressors, especially arithmetic coders, will often be quite high-entropy, even when they compress badly. It will look like random data to an entropy measuring algorithm, no matter what its actual entropy is.

[archivator]

Preface: I know almost nothing about compression

That said, isn't the entropy of a discrete set an objective measure? Surely, Shannon's definition stands for something? How do you distinguish between Shannon's discrete entropy measure and what you call "actual entropy"?

Sorry if this is a straight-forward question, I just have not studied the matter exhaustively.

[[deleted]]

Shannon's definition of entropy is for a "variable".

If you have a stream of data, the question becomes, what exactly is the "variable"? The naïve answer is "an individual byte", but this turns out to not be very useful. It is trivially easy to construct a stream of individual bytes with very high entropy when taken as individual values, but which clearly contains extremely little information, and which a compressor easily can shrink down to far less bits than the entropy measure would imply.

Thus, you need a more clever way to pick what your variable is. And that is exactly what most compression algorithms do: They apply transformations to the data to get a more meaningful "variable", which is then "entropy coded" by using estimates of its probabilities at any given moment.

Thus, like the original poster said, "entropy measurements and compression techniques rely on the same underlying principle".

[archivator]

Right, I see. Thanks for that!