Crinkler secrets, 4k intro executable compressor at its best

(Edit 5 Jan 2011: New Compression results section and small crinkler x86 decompressor analysis)

If you are not familiar with 4k intros, you may wonder how things are organized at the executable level to achieve this kind of packing-performance. Probably the most important and essential aspect of 4k-64k intros is the compressor, and surprisingly, 4k intros have been well equipped for the past five years, as Crinkler is the best compressor developed so far for this category. It has been created by Blueberry (Loonies) and Mentor (tbc), two of the greatest demomakers around.

Last year, I started to learn a bit more about the compression technique used in Crinkler. It started from some pouet's comments that intrigued me, like "crinkler needs several hundred of mega-bytes to compress/decompress a 4k intros" (wow) or "when you want to compress an executable, It can take hours, depending on the compressor parameters"... I observed also bad comrpession result, while trying to convert some part of C++ code to asm code using crinkler... With this silly question, I realized that in order to achieve better compression ratio, you better need a code that is comrpession friendly but is not necessarily smaller. Or in other term, the smaller asm code is not always the best candidate for better compression under crinkler... so right, I needed to understand how crinkler was working in order to code crinkler-friendly code...

I just had a basic knowledge about compression, probably the last book I bought about compression was more than 15 years ago to make a presentation about jpeg compression for a physics courses (that was a way to talk about computer related things in a non-computer course!)... I remember that I didn't go further in the book, and stopped just before arithmetic encoding. Too bad, that's exactly one part of crinkler's compression technique, and has been widely used for the past few years (and studied for the past 40 years!), especially in compressors like H.264!

So wow, It took me a substantial amount of time to jump again on the compressor's train and to read all those complicated-statistical articles to understand how things are working... but that was worth it! In the same time, I spent a bit of my time to dissect crinkler's decompressor, extract the code decompressor in order to comment it and to compare its implementation with my little-own-test in this field... I had a great time to do this, although, in the end, I found that whatever I could do, under 4k, Crinkler is probably the best compressor ever.

You will find here an attempt to explain a little bit more what's behind Crinkler. I'm far from being a compressor expert, so if you are familiar with context-modeling, this post may sounds a bit light, but I'm sure It could be of some interest for people like me, that are discovering things like this and want to understand how they make 4k intros possible!

RMasm, a new generation of macro assembler

I have not updated this website for a while... that's because I was actively working on a new exciting project called RMasm!

What is RMasm? It's a new generation of macro assembler, using the Ruby language as its main "macro" language and supports, in the beginning, the x86 assembler syntax. You may ask "Why developing another assembler while there are plenty of them around? (look at Nasm, Fasm, Masm, HLA...)". Well, while I was coding the new softsynth for FRequency in assembler (project that is temporally suspended because of RMasm, oops, sorry ulrick for the delay!), I found current assemblers to be very limited by their macro language. Although I was using Masm that is recognized to have a "strong" macro language, I found this language very ugly, not really powerful, syntax hard to learn and in definitive, quite limited.

So i started to think about a new kind of assembler...

Random float number generator using x86 ASM code optimized in size

While I'm working on the next 4k-64k softsynth for FRequency, I need to implement a simple noise generator. In the past, i used to call directly the c rand() function without digging into the internals... Because i have to develop the softsynth using x86 ASM in order to keep it as small as possible, i went through revisiting the problem of generating a random uniform float number in the range [-1,1) or (-1,1], but with size optimization in mind. This is not a common problem as you'll more likely be able to easily find a speed optimized version other the Internet but not a sized one...

I will focus mainly on 3 implementations, so i will not describe an exhaustive list of technique around. I would be glad if you are aware about a smaller implementation! I found quite some interesting results, like a poor performance of the c rand() function, both in terms of speed and uniformity.

Let's recall one of the simplest C random function you can find around :

float Rand() {
    return ((float)rand()/RAND_MAX) * 2.0f - 1.0f;
}

The rand() is generating an integer in the range [0, 32767]. RAND_MAX is equal to the max value 32767. The result is then scaled to the range [-1,1]. Let us first implement this in x86 ASM, just as an exercise.

AsmHighlighter Part II : Automatic x86 asm instruction size evaluation

Following the previous post about AsmHighlighter, I have just released a new version 1.1 of AsmHighlighter that evaluates x86 ASM instruction size for each instructions in your code. The instruction size is inserted in the comment next to the instruction.

When you are coding 4k or 64k (partially) demos in x86 assembler with size optimization in mind, it's sometimes useful to check the instruction size (as it is sometimes not so obvious, x86 has a lot of weird rules for their instruction size, particularly when using eax register on source/destination, or using ebx without an offset...etc).

This feature is available when you perform a formating of your document (Menu Edit/Advanced/Format document or selection, or Ctrl+k, Ctrl+d). Here is a screenshot result:

The magic behind it is that i have discovered a cool managed library called : Fasm Managed from Shynd's. This is a managed .NET dll that can perform dynamic x86 ASM compilation inside a .NET application. The code is simple as below:

byte[] buffer = ManagedFasm.Assemble("mov eax, 0");

Thanks to this great module, it was quite easy to integrate a fast evaluation of a x86 instruction size, although this evaluation is done at the line level, so the evaluation doesn't have any information on labels, defines...etc. But i have integrated a simple (but not perfect) workaround. Also, because this library is using FASM as a compiler, i had to perform some "normalization" on the code (that is mainly targeting MASM syntax), but it's working quite well!


With this instruction size feature, AsmHighlighter is becoming a bit more related to 4k-64k intros coding! ;)

Adding asm x86 Syntax Highlighting to Visual Studio 2008

While i use to develop some part of 4k's intro code in x86 assembler, it is quite annoying to switch from Visual Studio to an external editor in order to have a correct syntax highlighting. I like the principle of an Integrated Development Environment, and VS is a great tool for that. Based on my previous experience on NShader, i have decided to implement a syntax highlighter for x86 ASM... and thanks to NShader's work, it was really easy to code it! For anyone looking for a place to start when developing a LanguageService Package for Visual Studio, this project is easy to follow and gives a basic implementation for syntax highlighting.

So, i have just released AsmHighlighter under codeplex. This is an AddIn for Visual Studio 2008 (it won't work for Express Editions, as they don't allow communities addIns) that enables syntax highlighting for x86 ASM language. MASM syntax is mainly supported and NASM syntax is partially supported. I have no more reason to switch to an external editor! Cool!

Apart from that, the nice thing with MASM is that it is possible to debug directly under Visual Studio, making a mixed C-ASM project much easier to develop (VS is adding building rules for ASM files automatically to your project). On the other hand, i was not able to debug with NASM as nasm cannot generate debug information under the win32 platform...

I also found a cool project called JWasm developed by Japheth : JWasm is a MASM v6 compatible assembler (with v8 bug fixes and improvements)  that is able to output win32,win64 as well as linux elf object files. Quite interesting when you still want to develop with a MASM syntax and be able to export your work under linux without moving to another assembler! Japtheth even provides JWasm.rules files for an integration under Visual Studio. It's even possible to debug JWasm output objects files under VS, that's great!

Now, you may have noticed that all of this is not strictly related to 4k-64k intros coding, but well, you can consider AsmHighlighter as a productivity tool for 4k-64k development! ;)