Fun with Constrained Programming

Believe it or not, RAR files can contain bytecode for a simple x86-like virtual machine called the RarVM. This is designed to provide filters (preprocessors) to perform some reversible transformation on input data to increase redundancy, and thus improve compression.

For example, one filter (likely inspired by LZX, an earlier scheme with a similar feature) is called "Intel E8 preprocessing", which is designed to increase redundancy in x86 code.

If you imagine a program like this:

mov   foo, bar 

cmp   bar, baz

push  foo 

call  write

push  bar

call  write

The two calls are relative to the branch location, so there will be two different encodings of the same instruction. At compress time, we can translate them to absolute addresses. This way, the same instruction appears twice, and can therefore be compressed much more efficiently. When the archive is decompressed, this transformation can be reversed to restore the original.