Compression RLE

Tutorial (en anglais) sur la programmation RLE en C par Thor

  This tutorial had been written by Cyril Mottier (orlin61@wanadoo.fr) and may be distributed by any other website for non-commercial use only.

  The author makes no representations or warranties about the suitability of the software and/or the data files, either express or implied. The author shall not be liable for any damages suffered as a result of using or distributing this software and/or data files.

  Obviously, you are free to re-use any part of the sourcecode in your products as long as you give credits including a reference to me : Cyril Mottier :-).

  In this tutorial we'll see :
-What is the basics of RLE compression and decompression.
-How creating a picture RLE_compressed.
-How decompressing a picture compressed with an RLE algorithm.

  Note: This tutorial is based on Ti68k programming so it assumes that you have bases in programming with TIGCC, especially in C using pointers, while-loops, for-loops and arrays. Nevertheless, the ideas are the most important because they can be used in every development platforms.

  To conclude, you need some different softwares to understand each part of this tutorial :

• TIGCC
• Image studio
• a text-editor which contains a function to replace all occurences with another expression. Personnaly I use a free text-editor called ©ConText. This software can be found here.
• an image-editor which can resize and clarify a picture (for exemple ©Paint Shop Pro). This software is not compulsory but it can be very usefull to get beautiful pictures and have better results.

  RLE compression is probably the easier compression algorithm there is. Unfortunately, when a compression algorithm is easy to use it is also not very efficient. RLE compression can be very efficient in some special case like black and white pictures (the goal of this tutorial)  or text files which contain lots of spaces for indenting (like a C source). I'll try to explain you this property in this part.

  Everybody know the mp3 or jpeg compression. These technics extract all useless entities : for exemple mp3 extract all inaudible sounds giving a file sometimes 10 times smaller than the original file. Nevertheless, this mp3-file is 'impoverished' because you can't decompress the mp3-file to re-find the original file. This technic is very usefull when you want to compress some pictures (composed of lots of colors) or sounds. But it's impossible to use this compression way to reduce an executable file or a black and white picture (due to the fact that it's very easy to see the difference between two opposite colors). On our calculators all picture are black and white so we are 'obliged' to use a 'fast' and 'lossless' compression algorithm : the RLE algorithm. RLE means Run Lenght Encoding and it's also called Run Length Coding (RLC). This technic of compression is defined as a 'lossless' compression because the output file can be decompressed with no loss. When you execute a RLE algorithm on a file, you 'cut' all bytes which are repeated. It replaces sequences of the same data values within a file by a count number and a single value. I'll try to explain you this method by compressing the (senseless) word :

  This 'word' is composed of 12 letters (or bytes because a letter is encoded on a single bytes with ASCII). RLE compression consist on changing all repeated bytes with an control character followed by the number of letters and finally the letter compressed. Suppose the control caracter '#', with this method the precedent word becomes :

  This last word is composed of 9 bytes so you win 12-9=3 bytes. I'm okay that you don't find the compression amazing but the compression rate (ratio) is equal to ((12-9)*100)/12 = 25%. Imagine a word made up of 2000 bytes and compressed with a ratio of 25%, the final file is 2000*0.75 = 1500 so you win 500 bytes! As you can see, the ratio can be found with the followed function or routine :

  The RLE compression suffer from many disadvantages : suppose the word and the control caracter '#' :

  The compressed word becomes :

  The compressed word contains 36 letters and the original word is composed of 12 bytes so the routine ratio (12,36) will returns -200%! So the algorithm is useless! To overcome this problem RLE compression is only used if there are sequences of four or more repeating characters because three characters are used to conduct RLE so coding one or two repeating characters would even lead to an increase in file size and it's contrary to our goal!

  Then we use to conduct this compression a control caracter coded on a bytes but if this caracter appears in the file it will 'crash' our routine because it will interpret this caracter as a control caracter and not a 'normal' caracter. So if the control character itself appears in the file then one extra character is coded. For exemple the word :

will become :

  To conclude, the RLE algorithm needs, in special cases, some alternatives to problems which are very easy to overcome. We are going to see in the second part how decompressing a picture compressed with this esay-to-use RLE compression.

  To start, we need a picture which will be compressed : for this tutorial, I have taken a picture representing a little animal : a cat in a famous cartoon. To begin with this problem, you need to learn many tips in preparing the picture:

  Firstly, IStudio can just compress the bitmap picture. So, you need to change a .jpg or .gif picture in .bmp. With Paint Shop Pro, open the picture  and after you may save as a .bmp.

  Secondly, IStudio contains two option which can change the contrast and brightness. What a shame that these options are not very efficient! The solution consist on changing the contrast and brightness by clarifying the picture with Paint Shop Pro.

  Thirdly, you can see the result of a reduction of colors without IStudio. In Paint Shop Pro, open the picture, switch this one in grayscales and reduce the number of colors to 4. With this method you have an idee of the final project and it can be very usefull!

Now it's high time to RLE_compress our picture. To explain easily the process, all steps are stored and showed in the following list :

• Open Istudio ,clik on "File" and then on "Open...".
• Choose your bitmap picture.
• The picture is now opened and you have the destination at the right.
• Be sure to be in "Standart Grayscale (4 colors)" if you are working in grayscales.
• Clik on "File" and "Export".
• Set the Export option to "Text File", and ASM format to "68k (dc.b)"
• Don't forget to tick the cell "RLE Compressed" :-)
• You can now clik on OK and choose the file name.

Our picture in now compressed but the output file contains odd datas for the C-compiler. These datas need to be modified with a text editor. I will use ConText in this tutorial. Open ConText software and then open the Istudio file (normally this file has the extension .asm) by cliking 'File' and 'Open'. The file is now open : Click on 'Edit' and then on 'Replace' to replace '$' by '0x' and ' dc.b ' by ','. Note that the process is sometimes very long (it depends on file size). Finally change the string 'Layer1' by 'unsigned char name_of_picture1[]={' and 'Layer2' by 'unsigned char name_of_picture2[]={'. Don't forget to erase the first virgule and place a '}' at the end of a layer! Datas are now 'clean' and can be used in your programs.

  If you watched attentively output datas of Istudio you can remark these datas contain lots of 0x91. In fact, Istudio use the byte 0x91 as special caracter. With this last information, it's easy to create an algorithm which can decompress RLE_compressed pictures. I've decided to split this part in two routine. The first routine will explain you how decompressing a RLE_compressed picture to a BITMAP structure (after you can use the basic function BitmapPut to display the result). The second routine will particular touch all ExtGraph's users because it shows you how decompressing a RLE_compressed picture to the specific format of the extraph functions : (Gray)SpriteX8_(AND|OR|XOR|MASK|BLIT).

A) Bitmap version routine

  To understand easily our next routine, we need to know the structure of a BITMAP structure. In TIGCC documentation, this structure is defined like that :

typedef struct
{
 unsigned short NumRows, NumCols;
 unsigned char Data[];
}BITMAP;

  With this definition, it's easy to see what sort of datas are compulsory. The process to obtain a BITMAP structure is first to define a new BITMAP structure and then to fill all variables with parameters passed in argument (some paramaters like 'size' need to be calculated first).To fill the field 'Data' we will use a pointer 'dest' which point to the 'Data' field of our new BITMAP structure. Finally, the pointer to our final BITMAP structure is returned. Very simple, isn't it ? Don't be afraid, just watch attentively the following code (again and again if necessary). An exemple is available to show how to display a decompressed picture : see rletobmp.c for more informations.

BITMAP *RLE_Decompress_To_BITMAP (unsigned char *src, unsigned short rows, unsigned short cols)
{
 //---------------------------------------------------------------------------------------
 // Declaration of necessary variables
 //---------------------------------------------------------------------------------------
 unsigned char len, val, *dest;

 //---------------------------------------------------------------------------------------
 // The following instruction calculates the size in bytes of the bitmap.
 // The operation consists on multiplying number of pixels in width with number of
 // pixels in height. The result will give the number of pixel. To conclude,
 // 8 pixels are coded with one bytes so to find the size of the picture
 // the following result is divide by eight.
 //---------------------------------------------------------------------------------------
 unsigned short size = (rows*cols)>>3;

 //---------------------------------------------------------------------------------------
 // Allocates the necessary size. Note that the necessary size is not 'size' but
 // 'size+BITMAP_HDR_SIZE'. BITMAP_HDR_SIZE is equal to four and it defines the size of 
 // the header of the BITMAP structure.
 //---------------------------------------------------------------------------------------
 BITMAP *ptr = malloc (size+BITMAP_HDR_SIZE);

 //---------------------------------------------------------------------------------------
 // Don't forget to check if memory hed been correctly allocated.
 // The function 'malloc' returns 'NULL' if not enough space exists for the new block so
 // RLE_Decompress_To_BITMAP() will also return 'NULL' in this case.
 //---------------------------------------------------------------------------------------
 if (ptr)
 {
 
 //---------------------------------------------------------------------------------------
 // The BITMAP structure is modified with right datas.
 //---------------------------------------------------------------------------------------
  ptr->NumRows = rows;
  ptr->NumCols = cols;
  dest = ptr->Data;
 
 //---------------------------------------------------------------------------------------
 // The algorithm loops while the final size is different from zero.
 // So it will be 'size' iterations.
 //---------------------------------------------------------------------------------------
  while (size)
  {
 
 //---------------------------------------------------------------------------------------
 // If the special (or control) caracter is found, following bytes are compressed.
 // With Istudio the RLE_compressed datas are coded with this technic : first we have the
 // control caracter (0x91) then the repeated value and finally the lenght of this value.
 // Now it's easy to decompress this sequence
 //---------------------------------------------------------------------------------------
   if (*src==0x91)
   {
    src++;
    val = *src++;
    len = *src++;
    while (len)
    {
     *dest++ = val;
     len--;
     size--;
    }
   }
 
 //---------------------------------------------------------------------------------------
 // If no control cracter hed been found, it means the bytes are not compressed.
 // These bytes are just copied from 'src' to 'dest' with no modifications
 //---------------------------------------------------------------------------------------
   else
   {
    *dest++ = *src++;
    size--;
   }
  }
 }
 
 //---------------------------------------------------------------------------------------
 //On success ,the function returns a pointer to the newly decompressed datas,
 //else it return 'NULL'
 //---------------------------------------------------------------------------------------
 return ptr;
}

  Note : The function 'RLE_Decompress_To_BITMAP()' may crash your calculator if the pointer 'scr' and arguments 'rows' and 'cols' are in contradiction. For exemple if you try to decompress a 64x40 picture pointed by 'ptr' with the following routine : RLE_Decompress_To_BITMAP (ptr, 72, 40)!

B) Extgraph version routine

  In Extgraph documentation, (Gray)SpriteX8_(AND|OR|XOR) are defined like that :

  'x' and 'y' are the coordinates of the upper left corner of the sprite. 'h' is the height of the sprite. 'sprite1' and 'sprite2' are some pointers to arrays of unsigned char. 'bytewidth' is the width of the picture in bytes and finally 'dest1' and 'dest2' are some pointers to the video planes (GetPlane(LIGHT_PLANE) for exemple). Note that blackj and white variant functions have the same syntax exept 'sprite2' and 'dest2'.The sprite data has to be organized like this (example for bytewidth == 3): line1/byte1, line1/byte2, line1/byte3, line2/byte1, line2/byte2, line2/byte3 etc. It's now esay to create our decompressing routine because these functions don't need to create a specific structure. We just have to decompress our compressed datas in an allocated block.The following code explain you the decompression technic. Read it attentively! An exemple is available to show how to display a decompressed picture : see rletoext.c for more informations.

unsigned char *RLE_Decompress_To_ExtGraph (unsigned char *src, unsigned short size)
{
 
 //---------------------------------------------------------------------------------------
 // Declaration of necessary variables
 //---------------------------------------------------------------------------------------
 unsigned char len, val, *ptr, *dest;
 
 //---------------------------------------------------------------------------------------
 // Allocates the necessary size.
 //---------------------------------------------------------------------------------------
 ptr = malloc (size);
 
 //---------------------------------------------------------------------------------------
 // Don't forget to check if memory hed been correctly allocated.
 // The function 'malloc' returns 'NULL' if not enough space exists for the new block so
 // 'RLE_Decompress_To_ExtGraph()' will also return 'NULL' in this case.
 //---------------------------------------------------------------------------------------
 if (ptr)
 {
  dest=ptr;

 //---------------------------------------------------------------------------------------
 // The algorithm loops while the final size is different from zero.
 // So it will be 'size' iterations.
 //--------------------------------------------------------------------------------------- 
  while (size)
  {
   if (*src==0x91)
   {
    src++;
    val = *src++;
    len = *src++;
    while (len) 
    {
     *dest++ = val;
     len--;
     size--;
    }
   }

 //---------------------------------------------------------------------------------------
 // If no control cracter hed been found, it means the bytes are not compressed.
 // These bytes are just copied from 'src' to 'dest' with no modifications
 //---------------------------------------------------------------------------------------
   else
   {
    *dest++ = *src++;
    size--;
   }
  }
 }

 //---------------------------------------------------------------------------------------
 //On success ,the function returns a pointer to the newly decompressed datas,
 //else it return 'NULL'
 //---------------------------------------------------------------------------------------
 return ptr;
}

  Note : The function 'RLE_Decompress_To_ExtGraph()' may crash your calculator if the pointer 'scr' and argument 'size' are in contradiction. For exemple if you try to decompress a 64x40 (320 bytes) picture pointed by 'ptr' with the following routine : RLE_Decompress_To_ExtGraph (ptr, 340)!

  It's the end of this tutorial. I hope that you have easily understand each parts of this tutorial! If you have some problems in understanding one part (ore more), or if your program to test this method in not a success and don't run correctly, feel free to mail me. Suggestions, bug reports, and similar are VERY welcome. You can reach me at : orlin61@wanadoo.fr, on this forum of this site : www.tigen.org  and at my adress :

Mottier Cyril
Le haut pré morel
61350 St Mars d'Egrenne
France

test is often compulsory

  Don't hesitate to send me a postcard from your country. I prefer to receive A beautiful and well-written postcard  than an e-mail rapidly and badly written :-).