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.