Run-Length Encoding

I hadn’t quite gotten over the horrible cold this weekend, and have had to spend most of my time looking after children. So today’s post will be a short one. I’m looking at a very basic data compression technique frequently used in many older micro-computers of the 80’s to store level information and graphics for games.

The technique is called Run-length encoding (often called RLE), it takes advantage of repetition in data to reduce the storage requirement. It used to be a common compression technique for encoding graphics, but can be used effectively to encode level data or anything that has repeating data in it. The GIF image format is a well known example that uses the technique.

The encoding algorithm is very simple, you simply encode runs of data (repeated identical data) as the number of repetitions and a copy of the data. So if you had data that looked like this aaaaabbbbcaaa it could be encoded as a5b4c1a3. The trouble with this scheme is the worst case scenario (different data every byte) can actually increase the file size significantly, in some cases resulting in a larger file than uncompressed. You can avoid this scenario by encoding the start of a run as repeated characters with single characters representing themselves. This results in the previous data being encoded as aa5bb4caa3 which goes to show that even that technique has its downside.

I wrote up a quick implementation in pascal as an example and used it to compress some data files from my DOS platform game, Bob’s Fury. The first two data files I tried were the graphics data files which you can see compressed quite well, this is because there are many long runs of the same colour pixels. The third data file takes it to the extreme, it is a level data file that is pretty much one big long run of empty spaces, it compresses to an impressively small size. The fourth data file is normal level data (albeit a much larger level), it is much like the graphics data in that there are many runs, but it has some data at the end which does not compress well resulting in a worse ratio. The last file in the table is actually an ASCII map file detailing the contents of the executable for the game, it is useful in determining where errors are in the code, but this clearly shows that ASCII data is unsuitable for this compression technique, it resulted in a much larger file!

What follows is the pascal code I wrote for this quick test. It needs the buffer unit I wrote for buffered reading and writing files. You can also download the source file from here.

{ Run Length Encoder/Decoder for reading and writing files
  to make some very basic file compression.
  A Danson 2014 }

unit RLE;

interface

uses buffer; {we are going to use the buffered reader/writer to save on disk access routines.}

type
   RLDecoder = object
       r : reader;
       count: byte;
       data : char;
       constructor open_file(infile:string);
       function readChar:char;
       function readln:string;
       function eof:boolean;
       destructor close;
   end;
   RLEncoder=object
       w : writer;
       count : byte;
       data : char;
       constructor open_file(infile : string);
       procedure writeChar(o : char);
       procedure writeln(o : string);
       procedure flush; {will only flush underlying buffer!}
       destructor close;
   end;
       
implementation

constructor RLDecoder.open_file(infile :  string);
begin
   r.open(infile);
   count:= ord(r.readChar);
   data := r.readChar;
end;
       
function RLDecoder.readChar:char;
begin
   if (count>0) then
   begin
      dec(count);
      readChar := data;
   end
   else
   begin
      count := ord(r.readChar);
      data := r.readChar;
      dec(count);
      readChar := data;
   end;
end; { RLDecoder }

function RLDecoder.readLn:string;
var
   result : string;
   i	  : char;
begin
   i := Self.readChar;
   result := '';
   while  ( (i<>chr(13)) and (i<>chr(10)) ) do
   begin
      result := result + i;
      i := Self.readChar;
   end;
   readLn := result;
end; { RLDecoder }

function RLDecoder.eof:boolean;
begin
   eof:=false;
   if ((count = 0) and (r.eof)) then eof:=true;
end; { RLDecoder }

destructor RLDecoder.close;
begin
   r.close;
end; 

constructor RLEncoder.open_file(infile: string);
begin
   w.open(infile);
   count := 0;
   data := chr(0);
end;

procedure RLEncoder.writeChar(o	: char);
begin
   if (o = data) then
   begin {input the same as last time}
      inc(count);
      if (count = 255) then
      begin
	 w.writeChar(chr(count));
	 w.writeChar(data);
	 count := 0;
      end;
   end
   else
   begin {different!}
      if (count>0) then
      begin
	 w.writeChar(chr(count));
	 w.writeChar(data);
      end;
      data := o;
      count := 1;
   end;
end;

procedure RLEncoder.writeLn(o : string);
var
   i : word;
begin
   for i:=1 to length(o) do
      writeChar(o[i]);
   writeChar(chr(13));
   writeChar(chr(10));
end;

procedure RLEncoder.flush;
begin
   w.flush;
end; { RLEncoder }

destructor RLEncoder.close;
begin
   if (count>0) then
   begin
      w.writeChar(chr(count));
      w.writeChar(data);
   end;
   w.flush;
   w.close;
end;

end.

sparcie