First Version 14.3.1997
Last Updated 4.5.1997
Pasi Ojala, albert@cs.tut.fi

An Optimizing Executable Data Compression Program

Short: A Hybrid LZ77 and RLE, uses an Elias Gamma Code for lengths, Gamma
Code and linear for LZ77 offset, and ranked RLE bytes indexed by the same
Gamma Code. Uses no 'extra' memory in decompression.
---------------------------------------------------------------------------

Features/Requirements/Restrictions

   * Handles Commodore C64 executables of upto 64933 bytes (located at
     $0258-$fffd)
        o Attaches decompressor code so that the resulting file is runnable
          on the C64 like the original program.
        o Does in-place decompressing (single memory buffer)
        o Uses as little memory as possible during decompression
          (preferably no run-time data structures)
        o Has a short and relatively fast decompression routine (for C64)
        o Does not mess up the kernel or basic interpreter variables nor
          the return address on the stack.
   * Reasonable compression time (less than 20 minutes on a 25 MHz 68030)
   * Reasonable memory usage during compression (~1 MB for maximum-sized
     file)
   * Should offer better compression and/or faster decompression than any
     packer/cruncher program available for C64.
   * Selects the best parameters for the compression of each file
     automatically, but allows users to override them.

The current compressor version is available: pucrunch.c (Makefile for gcc).
Windows NT/95 Text mode executable: pucrunch_NT.exe.
AmigaDOS executable: pucrunch_Amiga.
MS-DOS executable: pucrunch_DOS.exe (needs DOS4GW.EXE).
Linux ELF 32-bit LSB executable: pucrunch_linux386 (Intel 80386, version 1,
stripped, dynamically linked libm.so.5/libc.so.5)
---------------------------------------------------------------------------

Algorithm Description

The compression algorithm outputs five (main) classes of data:

  1. uncompressed bytes
  2. LZ77 (offset, length) pairs (1 < offset <= 32000, 1 < length <= 128)
  3. Short RLE (byte, length) pairs (1 < length <= 64)
  4. Long RLE (byte, length) pairs (0 < length <= 32000)
  5. EOF symbol

Uncompressed Bytes

Uncompressed bytes are the bytes that could not be represented by shorter
codes, unlike a part of previously seen data (LZ77), or a part of a longer
sequence of the same byte (RLE). The selection between compressed data and
uncompressed data can be made in a straightforward way by using a prefix
bit. If the bit is 0, the following data is uncompressed, if the bit is 1,
the data is compressed. However, this presents the problem that
uncompressable data will be expanded from the original 8 bits to 9 bits per
byte, i.e. by 12.5 %.

Some data compression systems use a value that represents the number of
uncompressed bytes to follow, but this is really analogous to a prefix
bit(s), because 1-byte uncompressed data is very common.

For now, let's assume that 3/4 of the symbols outputted are uncompressed
bytes. In this case it seems viable to allocate the shorter codes for
uncompressed bytes. We should use 2 bits to determine whether the data is
compressed or uncompressed. Three of the combinations indicate an
uncompressed byte, and one indicates compressed data. But how to do that,
because we already weren't happy with adding bits to the uncompressed bytes
?

Postulating an even distribution on the uncompressed bytes we have another
option. We use two bits (let them be the two most-significant bits) from
the uncompressed bytes themselves to indicate compressed data. We have an
escape code, which is compared to the bits, and if it matches, compressed
data follows. If the bits do not match, the rest of the uncompressed byte
follows. The escape code is not static. Whenever those two bits in an
uncompressed byte would match the escape code, an escape sequence is
outputted. This escape sequence has the offending data and a new escape
code. The length of this escape sequence is 2 (escape bits used) + 3
(selects escape mode) + 2 (new escape bits) + 6 (rest of the byte), i.e.
expands the uncompressed byte by 5 bits.

Thus, uncompressed bytes expand in average 25% of the time by 5 bits. The
average length of uncompressed bytes is 25% * 13 + 75% * 8 = 9.25.
Interestingly, this is longer than using one bit to tag uncompressed bytes.
However, there is one thing we haven't considered: the escape sequence has
the possibility to change the escape code. Using this feature to its
optimum (escape optimization), the average 25% 'hit rate' becomes the
maximum 'hit rate'. Also, because the distribution of the (values of the)
uncompressed bytes is not flat (and there is locality, from which we can
benefit), the actual hit rate is always much smaller than that. Empirical
studies on the test files (see the compression tests) show that for 2-bit
escape codes the actual realized hit rate is only 1.8-6.4%, while the
theoretical maximum is the mentioned 25%.

Previously we assumed the distribution of 75% of uncompressed bytes and 25%
of compressed data (note that this simply refers to the number of times
these classes are output, not to the number of bytes processed). This
provided the reason to select 2 escape bits. For other distributions
(differently compressable files, not necessarily better or worse) some
other number of escape bits may be more suitable. The following table
summarizes the 'hit rates' on the test files for different number of escape
bits.

 1-bit2-bit 3-bit   4-bit   File
 50.0%25.0%   12.5%   6.25% Maximum
 25.3% 2.5% 0.3002% 0.0903% ivanova.bin
 26.5% 2.4% 0.7800% 0.0631% sheridan.bin
 20.7% 1.8% 0.1954% 0.0409% delenn.bin
 26.5% 6.4% 2.4909% 0.7118% bs.bin
 9.06 8.32  8.15    8.050   bits/byte for bs.bin

As can be seen from the table, the realized hit rates are dramatically
smaller than the theoretical maximum values. A thought might occur that we
should always select 4-bit (or longer) escapes, because it presents the
minimum overhead to uncompressed bytes. Unfortunately this isn't the case,
because it also increases the code length of the compressed data.

Also, the case with 1-bit escape code validates the original suggestion:
use a prefix bit. A simple prefix bit would produce better results
(although only slightly, 9 bits vs. 9.06 bits, making 106 bytes for
bs.bin). On the other hand, 1-bit escape code is not selected for bs.bin,
because 2-bit escape gives better overall results.

Note: for 7-bit ASCII text files, where the top bit is always 0, the hit
rate is 0% for even 1-bit escapes. Thus, uncompressed bytes do not expand
at all.

Compressed Data

Using the previously described escape-bit system the compressor outputs the
following types of codes:

    z..zx.....x                                        normal (zz != ee)
    e..e  value(LEN)    value(POSHI+1)  8b(POSLO)      LZ77
    e..e  0 (2)         0 (2-256)       8b(POSLO)      LZ77
    e..e  100 (3)       111111 111111                  END of FILE (LEN=3)

    e..e01 0  n..ne.....e                              escape + new escape
    e..e01 1  value(LEN)      bytecode                 Short RLE 2..64
    e..e01 1  111111 8b(LENLO) value(LENHI+1) bytecode Long RLE

If the top bits of an uncompressed byte do not match the escape code, the
first alternative is used, the byte is output as-is. If the bits match, the
escape sequence is output, with the new escape code.

The most frequent compressed data is LZ77. The length of the match is
output in Elias Gamma code, 0 meaning the length of 2, 100 length of 3, 101
length of 4 etc. If the length is 2, the next bit defines whether this is
LZ77 or RLE/Escape. If the bit is 0, an 8-bit value follows, which gives
the LZ77 offset value (the length is 2). If the bit is 1, the next bit
decides between escape and RLE.

The end of file condition is encoded to the LZ77 position and the long RLE
is encoded into the short RLE length. Read further, and you get a better
idea about why this kind of encoding is selected.

When I studied the distribution of the length values (LZ77 and short RLE
lengths), I noticed that the smaller the value, the more occurrances. The
following table shows the length values used for bs.bin.

         LZLEN   S-RLE
  2       1975     477
  3-4     1480     330
  5-8      492     166
  9-16     125      57
  17-32     31      33
  33-64      8      15

It almost immediately occurred to me that the optimal way to encode the
length values (decremented by one) is:

  0000000    not possible
  0000001    0              1         -6 bits
  000001x    10     x       2-3       -4 bits
  00001xx    110    xx      4-7       -2 bits
  0001xxx    1110   xxx     8-15      +0 bits
  001xxxx    11110  xxxx    16-31     +2 bits
  01xxxxx    111110 xxxxx   32-63     +4 bits
  1xxxxxx    111111 xxxxxx  64-127    +5 bits

The last column shows the difference to a 7-bit linear (non-)encoding.
Using this encoding for the length distribution presented reduces
considerably the bits used compared to a 'linear' representation. Later I
found out that this encoding in fact is Elias Gamma Code, only the
assignment of 0- and 1-bits in the prefix is reversed, and the length is
limited (1-bit gain for each value from 64 to 127).

However, the distribution of the LZ77 offset (LZPOS) values is not at all
similar. Admittedly, the distribution isn't exactly flat, but it also isn't
as radical as for the length values either. I decided to encode the lower 8
bits (selectable between 8 and 12 bits in the newer version) of the value
as-is (i.e. linear) and the upper bits with my version of the Elias Gamma
Code. Because the upper bits need the value 0, and the code can't represent
it, the upper part of the LZ77 offset is incremented by one before encoding
(unlike the length values that are decremented by one). Also, one of the
most significant part codes is reserved for an end of file (EOF) symbol.
This restricts the offset value to slightly less than 32 kilobytes, but the
loss is compression is negligible.

It is also the case, that 2-byte LZ77 matches only gain 4 bits (2-bit
escapes) for each offset from 1 to 256, and 2 bits for each offset from 257
to 768. In the first case 9 bits are used to represent the offset, in the
latter case 11 bits are used. The first case (offset 1..256) is much more
frequent than the second case, because it saves more bits, and also because
the symbol source statistics usually guarantee 2-byte matches in recent
history (much better chance than for 3-byte matches, for example).

So, if we restrict the offset for a 2-byte LZ77 match to 8 bits (1..256),
we don't lose so much compression at all, but instead we can shorten the
code by one bit. Or, as I have done, we can use the bit to select whether
this code really is LZ77 or something else. If you compare this coding to
the older one, you can see that the codes for Escape sequence, RLE and End
of File are still the same length than before, but the code for LZ77 has
been shortened by one bit. Because LZ77 is more frequently used than any of
the other codes, this presents a saving that more than compensates the loss
of 2-byte LZ77 matches with offsets 257..768.

The Long RLE selection is encoded into the Short RLE code. Short RLE only
uses values 2..64, six 1-bits (in the Elias Gamma Code) switches the
decoder to Long RLE mode. Additional compression for RLE is gained using a
table (and Elias Gamma Code) for the 31 top-ranking RLE bytes. The RLE
bytes are ranked by the number of times they are used, and top 31 are put
into a table, which is indexed by an Elias Gamma Code. Other RLE bytes get
a prefix "111111". (Note: in this version RLE codes 32..64 are not used.)

Selecting Compression 'Modes'

How does the data compressor decide whether to output a byte uncompressed,
using RLE, or using LZ77 ? This is determined by a sort of a graph-search
algorithm, which finds the shortest possible route from the start of the
file to the end of the file. Well, actually the algorithm is optimized so,
that it proceeds from the end of the file to the beginning, but the result
is the same anyway: the path that minimizes the bits outputted is found and
remembered. I won't go into the details of the algorithm here, you can
either come up with your own version or look at the source code.

Then why does this optimization give better compression results ? It works
because you are not forced to take every compression opportunity, but
select the best ones. You may want to emit a byte uncompressed even if
there is a 2-byte LZ77 match, because in the next position in the file you
may have a longer match. Well, things are more complicated than that, but
just take my word for it that there is a difference. :-)

To be able to find the minimal path, the algorithm needs the length of the
RLE (the number of the identical bytes following) and the maximum LZ77
length/offset (an identical string appearing earlier in the file) for each
location in the file. This is the most time-consuming part of the
compression. I have used several methods to make the search faster.

RLE Search

The RLE search is straightforward and fast: loop from the current position
(P) until a different byte is found or the end of the file is reached. It
can also be optimized to initialize all locations that belonged to the RLE,
because by definition there are only one-valued bytes in each one.

    unsigned char *a = indata + P, val = *a++;
    int top = inlen - P;
    int rlelen = 1;

    /* Loop for the whole RLE */
    while(rlelen<top && *a++ == val)
        rlelen++;

    for(i=0;i<rlelen-1;i++)
        rle[P+i] = rlelen-i;

LZ77 Maximal String Search

With LZ77 we can't use the same technique as for RLE (i.e. using the
currently found matches to mark subsequent positions to speed up the
search). For LZ77 we need to find the longest possible, and nearest
possible, string that matches the bytes starting from the current location.
A straightforward way to perform this operation is to start comparing the
strings starting from P-1 and P, remembering the length of the matching
part and then doing the same at P-2 and P, P-3 and P, .. P-j and P (j is
the search length, which is min(P-1, 32000)). The longest match and its
location (offset from the current position) are then remembered and
initialized. If we find a match longer or equal than the maximum length we
can actually use, we can stop the search there. (The code used to represent
the values may have an upper limit, this code has the maximum at 128.)

This is a very slow way to do the search though. Theoretically it could
take somewhere about (32000^2)*n compares to process a file of the length n
(a mathematically inclined person would probably give a better estimate).
However, using the RLE to our advantage permits us to rule out the
worst-case projection, which happens when all bytes are the same value. We
only search LZ77 matches if the current file position has shorter RLE
sequence than 128, which is the maximum LZ77 copy length.

The first thing I did to improve the speed is to remember the position
where each byte has last been seen. A simple 256-entry table handles that.
Using this table, the search can directly start from the first potential
match, and we don't need to search for it byte-by-byte anymore.

That didn't give much of an improvement, but then I increased the table to
256*256 entries, making it possible to locate the latest occurrance of any
byte pair instead. Because the shortest possible string that would offer
any compression (for the used encoding of LZ77) is two bytes long, this
byte-pair history is very suitable indeed. Also, the first (shortest
possible, i.e. 2-byte) match is found directly from the byte-pair history.
This gave a moderate 30% decrease in compression time for one of my test
files (from 28 minutes to 17 minutes on a 25 MHz 68030).

The second idea was to quickly discard the strings that had no chance of
being longer matches than the one already found. A one-byte hash value is
calculated from each three-byte groups. The values are calculated once and
put into a table, so we only need two memory fetches to know if two 3-byte
groups are different (if the hash values are different, at least one of the
bytes differ, but if the hash values are the same, we have to compare the
original bytes). The hash values of the strategic positions of the strings
to compare are then .. compared. This strategic position is the location
two bytes earlier than the longest match so far. If the hash values differ,
there is no chance that the match is longer than the current one. It may be
not even be as long, because one of the two earlier bytes may be different.
If the hash values are the same, the brute-force byte-by-byte compare has
to be done. However, the hash value check already discards a huge number of
candidates and more than generously pays back its own memory references.
Using the hash values the compression time shortens by 50%, from 17 minutes
to 8 minutes.

I also reworded some code to help my compiler generate better code, but --
as expected -- only got 20% shorter compression time, 6 minutes.

Okay, the byte-pair table tells us where the latest occurrance of any byte
pair is located. Still, for the latest occurrance before that one we have
to do a brute-force search. The next improvement was to use the byte-pair
table to generate a linked list of the byte pairs with the same value. In
fact, this linked list can be represented as a table, using the same
indexing as the file positions. I.e. to locate the previous occurrance of a
2-byte string starting at location P, look at backSkip[P].

    /* Update the two-byte history & backSkip */
    if(P+1<inlen)
    {
        int index = (indata[P]<<8) | indata[P+1];

        backSkip[P] = lastPair[index];
        lastPair[index] = P+1;
    }

Actually the values in the table are one bigger than the real table
indices. This is because the values are of type unsigned short, and I
wanted zero to mean "not occurred".

This table makes the search of the next (previous) location to consider
much faster. The compression time was reduced from 6 minutes to 1 minute 10
seconds. Quite an improvement from the original 28 minutes!

There is also another trick that takes advantage of the already determined
RLE lengths. If the RLE lengths for the positions to compare don't match,
we can directly skip to the previous potential match. Note that the RLE
bytes (the data bytes) are the same, and need not be compared, because the
first byte (two bytes) are always equal on both positions (our backSkip
table guarantees that). The RLE length value can also be used to skip the
start of the strings when comparing them.

Note that a compression method similar to RLE can be realized using just
LZ77. You just emit the byte to copy, and output a LZ77 code with offset 1
and the original RLE length minus 1. You can thus consider RLE as a special
case, which offers tighter encoding of the necessary information. Also, as
LZ77 limits the 'copy size' to 128 bytes, a RLE version providing lengths
upto 32 kilobytes is a big improvement, even if the code for it is long.

4-Pass Compressor

In fact, pucrunch is a four-pass compressor.

  1. Find RLE and LZ77 data, pre-calculate RLE ranks/pre-select RLE byte
     table
  2. Select the best 'path' (i.e. which RLE and LZ77 codes to use)
  3. Optimize the escaping
  4. Re-calculate RLE ranks and re-select the RLE byte table and output the
     file.

---------------------------------------------------------------------------

Compression Tests

The following data compression tests are made on my four test files:
bs.bin is a demo part, about 50% code and 50% graphics data
delenn.bin is a BFLI picture with a viewer, a lot of dithering
sheridan.bin is a BFLI picture with a viewer, dithering, black areas
ivanova.bin is a BFLI picture with a viewer, dithering, larger black areas
The C64 decompression code. I also have a byte-based (instead of bit-based)
version which trades off some compression for decompression speed.

More test files are welcomed!

 bs.bin          41537
 Packer          Size  Left  Comment
 ByteBonker 1.5  27326 65.8% Mode 4
 Cruelcrunch 2.2 27136 65.3% Mode 1
 The AB Cruncher 27020 65.1%
 Pu-Crunch       26490 63.8% 2-bit escape
 delenn.bin      47105
 The AB Cruncher   N/A   N/A Crashes
 ByteBonker 1.5  21029 44.6% Mode 3
 Cruelcrunch 2.2 20672 43.9% Mode 1
 Pu-Crunch       19817 42.1% 1-bit escape, @2
 sheridan.bin    47105
 ByteBonker 1.5  13661 29.0% Mode 3
 Cruelcrunch 2.2 13595 28.9% Mode H
 The AB Cruncher 13534 28.7%
 Pu-Crunch       12572 26.7% 2-bit escape, @2
 ivanova.bin     47105
 ByteBonker 1.5  11016 23.4% Mode 1
 Cruelcrunch 2.2 10883 23.1% Mode H
 The AB Cruncher 10743 22.8%
 Pu-Crunch        9878 21.0% 2-bit escape, @2
 LhA              9543 20.3% Decompressor not included
 gzip -9          9474 20.1% Decompressor not included

Calgary Corpus Suite

I also modified the compressor to allow bigger files than 63 kB to get some
reference results using the Calgary Corpus test suite.

The compression time for "pic" can be easily reduced, but it reduces the
compression gain somewhat.

The decompression code is included, although it is not valid for files over
63k (uncompressed size). About 34 bytes are decompression parameters, the
rest (299 bytes) is 6510 machine language.

The results surprised me, because the compression algorithm IS developed
for a very special case. It only has a fixed code for LZ77/RLE lengths, not
even a static one (fixed != static != adaptive)! Also, it does not use
arithmetic code to compress the bytes that are not part of LZ77 (and RLE)
matches. Because most of the big files are ASCII text, this severely
handicaps my compressor. Also, decompression is relatively fast, and uses
no extra memory.

I'm getting relatively near LhA, and shorter than LhA for 5 files (300-byte
decompressor included!), and relatively near or shorter than LhA in other
cases if the decompressor is removed.

 SunOS isosotka 5.4 Generic_101945-36 sun4m sparc
 Total bytes output 1145019 (decompressors
 included)                                             LhA    Zip  GZip -9
 Total compression (real)time 13:14
 Estimated decompression on a C64 (1MHz 6510) 6:47
 File           In      Out  Ratio   Gained    Time     Out    Out     Out
 bib        111261    37428  33.6%    66.4%    0:08   40740  35041   34900
 book1      768771   341144  44.4%    55.6%    1:04  339074 313352  312281
 book2      610856   222551  36.4%    63.6%    0:45  228442 206663  206158
 geo        102400    73831  72.1%    27.9%    0:12   68574  68471   68414
 news       377109   152670  40.5%    59.5%    0:19  155084 144817  144400
 obj1        21504    10719  49.9%    50.1%    0:01   10310  10300   10320
 obj2       246814    84395  34.2%    65.8%    0:17   84981  81608   81087
 paper1      53161    19921  34.2%    65.8%    0:02   19676  18552   18543
 paper2      82199    32133  39.1%    60.9%    0:04   32096  29728   29667
 paper3      46526    19541  42.0%    58.0%    0:02   18949  18072   18074
 paper4      13286     6176  46.5%    53.5%    0:01    5558   5511    5534
 paper5      11954     5550  46.4%    53.6%    0:01    4990   4970    4995
 paper6      38105    14358  37.7%    62.3%    0:02   13814  13207   13213
 pic        513216    60161  11.7%    88.3%   10:23   52221  56420   52381
 progc       39611    14369  36.3%    63.7%    0:01   13941  13251   13261
 progl       71646    17415  24.3%    75.4%    0:06   16914  16249   16164
 progp       49379    12125  24.6%    75.4%    0:04   11507  11222   11186
 trans       93695    20532  21.9%    78.1%    0:07   22578  18961   18862
---------------------------------------------------------------------------

Revisions and Ideas

5.3.1997
     Tried reverse LZ, i.e. mirrored history buffer. Gained some bytes, but
     its not really worth it, i.e. the compress time increases hugely and
     the decompressor gets bigger.

6.3.1997
     Tried to have a code to use the last LZ copy position (offset added to
     the lastly used LZ copy position). On bs.run I gained 57 bytes, but in
     fact the net gain was only 2 bytes (decompressor becomes ~25 bytes
     longer, and the lengthening of the long rle codes takes away the rest
     30).

10.3.1997
     Discovered that my representation of integers 1-63 is in fact an Elias
     Gamma Code. Tried Fibonacci code instead, but it was much worse (~500
     bytes on bs.run, ~300 bytes on delenn.run) without even counting the
     expansion of the decompression code.

12.3.1997
     'huffman' coded RLE byte -> ~70 bytes gain for bs.run. The RLE bytes
     used are ranked, and top 15 are put into a table, which is indexed by
     a Elias Gamma Code. Other RLE bytes get a prefix "1111".

15.3.1997
     The number of escape bits used is again selectable. Using only one
     escape bit for delenn.run gains ~150 bytes. If #-option is not
     selected, automatically selects the number of escape bits (is a bit
     slow).

16.3.1997
     Changed some arrays to short. 17 x inlen + 64kB memory used.
     opt_escape() only needs two 16-element arrays now and is slightly
     faster.

31.3.1997
     Tried to use BASIC ROM as a codebook, but the results were not so
     good. For mostly-graphics files there are no long matches -> no net
     gain, for mostly-code files the file itself gives a better codebook..
     Not to mention that using the BASIC ROM as a codebook is not 100%
     compatible.

1.4.1997
     Tried maxlen 128, but it only gained 17 bytes on ivanova.run, and lost
     ~15 byte on bs.run. This also increased the LZPOS maximum value from
     ~16k to ~32k, but it also had little effect.

2.4.1997
     Changed to coding so that LZ77 has the priority. 2-byte LZ matches are
     coded in a special way without big loss in efficiency, and codes also
     RLE/Escape.

5.4.1997
     Tried 'histogram normalization' on LZLEN, but it really did not gain
     much of anything, not even counting the mapping table from index to
     value that is needed.

11.4.1997
     8..14 bit LZPOS base part. 'Automatic' selection. Some more bytes are
     gained if the proper selection is done before the LZ/RLELEN
     optimization. However, it can't really be done automatically before
     that, because it is a recursive process and the original LZ/RLE
     lengths are lost in the first optimization..

22.4.1997
     Found a way to speed up the 'almost pathological' cases by using the
     RLE table to skip the matching beginnings.

2.5.1997
     Switched to maximum length of 128 to get better results on the Calgary
     Corpus test suite.

---------------------------------------------------------------------------
To the homepage of albert@cs.tut.fi
