RLE

General Description

RLE (Run Length Encoding) describes a compression technique which tries to take advantage of long "runs" of a single symbol in the input. Instead of then storing all repetitions, the symbol is just stored once, together with an information on the length of this run. Similary, long runs of symbols without repetitions are stored literally.

The advantage of RLE are obviously an easy an fast compression/decompression technique and good compression ratios on uniform inputs (e. g. images with a single background colour in large areas). However, on more complicated inputs RLE will often produce outputs that are even larger than the input.

How to Recognize an RLE-compressed File

A file processed a "standard implementation" of RLE can best be recognized when an uncompressed output file is known:

• If the output file is quite uniform, look out for larger areas of 0xff with one other byte in between.
• If the output file is very non-uniform, look out for frequent occurrences of 0x00 followed by a byte whose value matches the distance to the next 0x00.

Decompression

When decompressing data, the basic task is to differentiate between literal and compressed data and reproduce the correct number of compressed characters. The pseudo code below shows a possible RLE decompression routine. Please note that the RLE method is quite widespread and has often been altered by developers to best match the type of data they want to compress. Thus, the below example just illustrates the general method of decompression, but has been used quite a few times in this variation:

<syntaxhighlight lang=pascal> while InputPos < InputSize do begin

 RunLength := Input[InputPos++]
 if RunLength = 0 then
 begin
   Count := Input[InputPos++]
   for i := 1 to Count do
     Output[OutPos++] := Input[InPos++]
 end
 else
 begin
   Symbol := Input[InputPos++]
   for i := 1 to RunLength do
     Output[OutPos++] := Symbol
 end

end </syntaxhighlight>

Further Information

More extensive information on this technique can easily be found on the web. Starting points might be this page showing a graphical explanation of the compression method using a more theoretically generalized approach than the sample implementation above. There are hundreds of further pages (too much to list them all here) describing a multitude of RLE variants.

Games

• The Riddle of Master Lu ( *.ss )