RLE

From XentaxWiki
Jump to: navigation, search

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:

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

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 )