freenrv2[b,d,e] & upx for code snippets
=======================================
1. lz encoding
Lempel-Ziv encoding replaces repeated strings with (offset,length) codes.
If we cant find duplicated string, we encode character itself.
Both string and character in the packed stream are prefixed with one bit
of data, indicating what kind of code is it.
As such, we lose one bit when we encode character,
but we achieve some compression when we replace duplicated string
with (offset,length) code.
Depending on algorithm modification,
offset and/or length can be limited or not,
and can be encoded using fixed and/or variable-length codes.
The most interesting part of this class of algorithms is that if we will
simply encode longest found strings (v1), we will not
achieve the best compression ratio.
Here is an example (spaces are used just for readability):
Lets assume that (offset,length) code uses 1 bit for prefix,
8 bits for offset and 4 bits for length,
so it all uses 1+8+4=13 bits,
and encoded character uses 1+8=9 bits of data.
data length in bits
------------------------------------------- --------------
unpacked: abc bcdefgh abcdefgh 18*8 = 144
packed (v1) abc (1,2#bc#) defgh (0,3#abc#) (5,5#defgh#) 8*9+3*13 = 111
packed (v2) abc (1,2#bc#) defgh a (3,7#bcdefgh#) 9*9+2*13 = 107
As you can see, scanning for longest repeated strings
is not the best packing strategy.
2. nrv2[b,d,e] algorithms (used by the UPX, binary distribution)
Both algorithms differs by the format of the (offset,length)
encoding.
While encoding offset/length, numbers are divided into two parts:
1st part is encoded as a fixed length code, 2nd part is encoded
as a variable-length code.
Also, if current offset matchs previous offset, it is encoded using
just two bits.
3. freenrv2b algorithm (see nrv2b.zip && nrv2bde.zip)
This is nrv2b-compatible algorithm, difference is only in the compression
method.
We try to achieve "ideal" compression ratio, not taking into account
compression time.
Note, that such an ideality is limited by the algorithm and
(offset,length)-encoding specifics, and other algorithms
can achieve better ratio, for sure.
Using kind of optimized brute force, we try all the possible
variants. (see v1,v2 in the example above)
4. upx for code snippets (see snupx.zip)
Given some code snippet (32-bit x86 code without any headers),
we try nrv2b,d,e methods and choose the best one.
Then we produce the following code ("p" (packed) option):
call X
<packed data>
X:
pop esi
sub esp, ALIGN4(unpacked_data_size)
mov edi, esp
<nrv2[b,d,e] decompressor code>
jmp esp
As such, we generate compressed, self-extracting code snippet.
When "x" (xored) or "px" (packed+xored) options are specified,
we also add "unxor" layer, which hides zero/cr/lf/slash characters.
5. upx for code snippets/special edition (see snupxs.zip)
This is the the same tool as previous one,
except that only "p" option is supported,
and instead of nrv2[b,d,e] algorithms we try
their modifications (some of these modifications are equal to
nrv2b,d,e algorithms), i.e. we generate (offset,length)-codes format
and corresponding decompressor code on-the-fly.
This is even more slow, but improves compression ratio, sometimes 10%+
6. what for?
The only idea was to compress some code snippets, such as shellcodes,
engines, etc.
Since in such a cases data length is only some kilobytes,
compression time is not important, even when it grows as N*N,
while making shellcode some bytes smaller always looks nice.
