RLE Compression

From ModdingWiki
Jump to: navigation, search

RLE compression, short for Run Length Encoding, is a form of compression used by many games and applications. It is based upon using 'flags' to indicate a number of identical bytes and is named for these which indicate the 'length of run' of a series of bytes.


Basic principle

A lot of data will consist, if not of large empty spaces, then of repeating sequences. For example, a picture of clouds will ahve a lot of blue sky in it. Encoded uncompressed this wastes a lot of space, it would be easier to be able to code something like 'The next 126 bytes are blue sky' This is what RLE compression does.

In RLE, there is some sort of 'flag value' or values that indicate that the following data is compressed or repeated in some manner. As an example, consider the string $00 $01 $00 $00 $00 $00 $00 $02, 8 bytes long. If we were to use the value $FF as a flag, with the next byte being the repeat length and the byte after that the repeat byte, it becomes $FF $01 $00 $FF $01 $01 $FF $05 $00 $FF $01 $02, 12 bytes. This may not look very compressed, and indeed it is the simplest and least effective means of compressing. However, even this can cause great compression, since strings of hundreds of null bytes are not unknown.


Variations

There are many compression schemes, many more efficient than the basic scheme. For example we might take the above method and remove the flags, saying simply 'The first byte is a length, the second the value and so on' then we get $01 $00 $01 $01 $05 $00 $01 $02, 8 bytes again. We might use another flag for stretches of different bytes, to avoid wasting space saying '1 of this, 1 of that'; both these methods are used in Keen 1-3 RLE compression

RLEW compression is a form of RLE compression using words instead of bytes as the basic unit of compression. It is usually used to compress files made up of words (Usually levels.) Here the usual practice is to assume nothing is repeated until a special flag is read.

How these and other additions are implemented constitute the main differences between different RLE schemes, with most games using a subtly different system.


Known RLE variants: