RLEW compression

From ModdingWiki
Jump to: navigation, search

RLEW compression is a modified form of RLE Compression in which words, not bytes, are the basic units of compression. Because of this, RLEW compression tends to be much more standardized than RLE, but less often used.

This form of compression is preferred for files that themselves have words, not bytes as the basic form of compression, such as the Commander Keen 1-3 Level format, since we can expect the repetition of the same two byte sequence many times, something that is poorly compressed by RLE. Large files, especially those with long repetitive stretches are also compressed very well, and RLEW is easy both to write and to read.

Unlike RLE compression, which has a number of differing means of compressing bytes, the format for RLEW is almost universally the same. A flag, almost always $FEFE is followed by two words, the number of times to repeat the next word, and the word to be repeated. Any non-flag words are copied as is.

Thus unlike RLE, which is usually limited to repeat counts of 128, RLEW repeat counts are almost unlimited. It is also usually very easy to 'minimally compress' data in this manner by simply copying everything except values of $FEFE which must become $FEFE $0001 $FEFE to avoid being mistaken for flags.

Data is usually read from the start of a file to the end, but many implementations have the size of the decompressed data at the file start as either a check or a means of stopping decompression/

A simple algorithm for decompressing this format is as follows;

1.) If implemented, get the first dword in the file, [Final Length]
2.) If [Length of data so far] < [Final Length] then:
 3.) Get a word
 2.) Is this word $FEFE?
     -> If yes;
        Get the next two words (Word1 and Word2)
        Copy Word2 [Word1] times
        Move forward three words and got to 2.)
     -> If no;
        Copy the word
        Move forward a word and go to 2.)

RLEB compression

This is almost exactly the same as RLEW compression. The only difference is that it operates on bytes instead of words. The flag value for this compression is $FE in most cases.

Notes

Dangerous Dave 2, Shadow Knights, Commander Keen 1-3, and Slordax use it to compress their levels and sometimes graphics.