Lib RLE Description of operation

The RLE acronym stands for Run Length Encoding. It is a form of compression/encoding, and is perhaps the simplest and most basic of such schemes available. The general way in which it works is to take a stream of bytes and look for sections in that stream where identical bytes (in our case pixels) repeat in runs. This will typically occur in a visual image where the majority of the image is a background colour, which is then divided up by lines and forms of other colours. When thinking about this, it is clear that the scheme is fairly limited. A horizontal line of a uniform colour, would represent a good candidate for encoding as a run, since the line will cause a sequence of identical bytes in the binary image. On the other hand a vertical line will not compress very well since a trace of it's manifestation appears once on every line, and therefore does not constitute a "run". So then, when a run is found, the length of the run is determined, and the run is then represented in the output by data that indicates the value and length of the run. That, is run length encoding.

The RLE library functions have been divided into two discrete groups. One deals with RLE8 the other RLE4. The two formats are essentially the the same, with the exception that the RLE format attempts to seek runs within nibbles (four bit words), or bytes, depending on the request. The two halves of the library are essentially the same, with the exception that type changes, and minor differences to the logic, allow the two formats to be read accurately. Had the library been written for C++, it is almost certain that the common functionality would have been placed in a base class. Subclasses could then have been written to reflect the slight differences in format. As it is the rest of the library is written as C code, so this code follows that convention. The code could have been written to mirror the notional C++ architecture, but that was deemed unworthwhile.

The implementation of the Microsoft bitmap RLE format, involves some careful consideration. Such considerations are largely to do with the way they define the standard. In our discussion of this scheme we assume the perspective of the RLE8 decompression machine.

The RLE data stream takes the form of a pipe. When we read data from the pipe, we automatically increment a pointer to the data in the pipe, such that subsequent reads extract subsequent data. When writing data to uncompressed output image, we will already have determined the overall size of the image, and allocated memory for it. By default when we write data to the output, it is written to the next pixel location in the image. We assume that the next pixel is to the right of the current one, and at the end of the line, the next pixel is the first on the next line.

As a result of reading the data we view the machine as being in one of three states;

• IDLE
• ESCAPED
• ENCODED

Before reading any data, we assume the IDLE state. In this IDLE state, we read a byte from the pipe, and this byte tells us which of the other states to enter. If the byte is zero, then we enter the ESCAPED state, otherwise we enter the ENCODED state.

In the ESCAPED state the next byte read from the pipe may either be a command or a count. There are three commands;

• 0x00 - End of line - indicates that there is no more data available for the current line and that the next pixel should be placed in the output image at the beginning of the next line.
• 0x01 - End of bitmap - indicates that there is no more data available for the output image and that the next pixel should be considered to be the first in the image.
• 0x02 - Delta - indicates that the next pixel is at a given offset from the current one. Another two bytes are read from the input to determine the x and y sizes of this offset. The offsets are added to the current output pixel position.

If the command code is none of these three then the command code is considered to be a count instead. The count represents the number of bytes to read from the input that should be repeated as pixels on the output. Microsoft refer to this condition as "Absolute Mode". This is a mode where uncompressed data is retrieved from the input pipe.

After either a command or an absolute mode block in the ESCAPED state has been processed the machine returns to the IDLE state.

In the ENCODED state we read a byte from the input, and this is considered to be a count. We read another, and it is considered to be a pixel value. We add this single pixel value to the next output pixel, and repeat as indicated by the count. Microsoft refer to this condition as "Encoded Mode". This is a mode where compressed data is retrieved from the input. Once this action is complete the machine returns to the IDLE state.

The following table encapulates these considerations;

In the best tradition of home car mechanics, compression is the reverse of expansion! There is, however, one notable point, that the table above makes clearer. When compressing bitmaps to RLE, the circumstance may arise that it is necassary to emit one, or two bytes that are not compressed. The single byte case is the clue, because a single byte repeat in encoded mode is the same as the single byte transfer we may wish to make in absolute mode. Sending the one byte in encoded mode is more efficient than sending one byte in absolute mode, were that available. Clearly if it is possible to send one absolute byte in encoded mode, then sending two is also possible.

The final observation, is that two different encoders could produce two different but completely valid RLE data files, from the same source bitmap.

We leave the detail of the encoder for the reader to estabish, the sources are zipped up under the download page on the left. Our encoder is not as smart at optimisation as some. Both the encoder and decoder have been tested, against itself and external readers and writers. Given the simplicity of this standard, compression, even on images which one would not normally expect dramatic benefits, show surprising results.

#include "..\ImgTypes.h"
#include "ImgRle8.h"
#include "..\ImgAlloc.h"

#define ALLOC_CHUNK		1024

#define CMPS_FLAGS_NONE		0x00
#define CMPS_FLAGS_EOF		0x01
#define CMPS_FLAGS_EOL		0x02

#define RLE_CMD_NULL		0	//A: NULL ~ B: NULL
#define RLE_CMD_EOL			1	//A: NULL ~ B: NULL
#define RLE_CMD_EOF			2	//A: NULL ~ B: NULL
#define RLE_CMD_DELTA		3	//A: XOffs ~ B: YOffs
#define RLE_CMD_ABS			4	//A: Ptr ~ B: Cnt (03-FF)
#define RLE_CMD_ENC			5	//A: Char ~ B: Cnt (01-FF)
#define RLE_CMD_TWO			6	//A: Char1 ~ B: Char2

#define RLE_CODE_ESCAPE		0x00
#define RLE_CODE_EOL		0x00
#define RLE_CODE_EOF		0x01
#define RLE_CODE_DELTA		0x02

typedef struct
{
	unsigned long XDim;
	unsigned long YDim;
	unsigned long LineSize;

	unsigned char* pInBuf;
	unsigned long InSize;
	unsigned long InPtr;

	unsigned char* pOutBuf;
	unsigned long OutSize;
	unsigned long OutPtr;

	unsigned long NextLine;
	unsigned long EndOfLine;
	unsigned long EndOfFile;
	unsigned char Flags;
	unsigned char Cmd;
	unsigned long aParam;
	unsigned long bParam;
}CmpsState;

typedef struct
{
	unsigned long XDim;
	unsigned long YDim;
	unsigned long LineSize;

	unsigned char* pInBuf;
	unsigned long InSize;
	unsigned long InPtr;

	unsigned char* pOutBuf;
	unsigned long OutSize;

	unsigned long XPos;
	unsigned long YPos;
	unsigned char Cmd;
	unsigned long aParam;
	unsigned long bParam;
}ExpdState;

void CmpsSeek8(CmpsState& aCS)
{
	unsigned long LocalPtr;

	LocalPtr = aCS.InPtr;

	bool Stop = false;
	unsigned char AbsCount = 0;
	while(!Stop)
	{
		unsigned char DataA = aCS.pInBuf[LocalPtr];
		unsigned char DataB = aCS.pInBuf[LocalPtr+1];

		if(DataA == DataB)
		 Stop = true;
		else
		{
			AbsCount++;
			LocalPtr++;
		}

		if((LocalPtr >= aCS.EndOfLine) || (AbsCount == 0xFF))
		 Stop = true;
	}

	if(AbsCount == 0)
	{
		LocalPtr = aCS.InPtr;

		unsigned char EncCount = 0;
		unsigned char Data = aCS.pInBuf[LocalPtr];
		LocalPtr++;
		EncCount++;

		while((aCS.pInBuf[LocalPtr] == Data) && (LocalPtr < aCS.EndOfLine) && (EncCount < 0xFF))
		{
			LocalPtr++;
			EncCount++;
		}

		aCS.Cmd = RLE_CMD_ENC;
		aCS.aParam = (((unsigned long) Data) & 0x000000FF);
		aCS.bParam = (((unsigned long) EncCount) & 0x000000FF);
		aCS.InPtr = LocalPtr;
	}
	else
	{
		switch(AbsCount)
		{
			case 1:
			{
				aCS.Cmd = RLE_CMD_ENC;
				aCS.aParam = (((unsigned long) aCS.pInBuf[aCS.InPtr]) & 0x000000FF);
				aCS.bParam = 1;
				aCS.InPtr = LocalPtr;
			}
			break;

			case 2:
			{
				aCS.Cmd = RLE_CMD_TWO;
				aCS.aParam = (((unsigned long) aCS.pInBuf[aCS.InPtr]) & 0x000000FF);
				aCS.bParam = (((unsigned long) aCS.pInBuf[aCS.InPtr+1]) & 0x000000FF);
				aCS.InPtr = LocalPtr;
			}
			break;
			
			default:
			{
				aCS.Cmd = RLE_CMD_ABS;
				aCS.aParam = aCS.InPtr;
				aCS.bParam = (((unsigned long) AbsCount) & 0x000000FF);
				aCS.InPtr = LocalPtr;
			}
			break;			
		}
	}
}

bool NextCmpsCmd8(CmpsState& aCS)
{
	bool Action = false;
	aCS.Cmd = RLE_CMD_NULL;

	if(aCS.InPtr < aCS.EndOfFile)
	{
		if((aCS.InPtr < aCS.EndOfLine) || ((aCS.Flags & CMPS_FLAGS_EOL) != 0))
		{
			if((aCS.Flags & CMPS_FLAGS_EOL) != 0)
			{
				aCS.Flags &= ~CMPS_FLAGS_EOL;
				aCS.InPtr = aCS.NextLine;
				aCS.EndOfLine = aCS.NextLine + aCS.XDim;
				aCS.NextLine += aCS.LineSize;
			}

			CmpsSeek8(aCS);

			Action = true;
		}
		else
		if((aCS.Flags & CMPS_FLAGS_EOL) == 0)
		{
			aCS.Flags |= CMPS_FLAGS_EOL;
			aCS.Cmd = RLE_CMD_EOL;
			Action = true;
		}
	}
	else
	if((aCS.Flags & CMPS_FLAGS_EOF) == 0)
	{
		aCS.Flags |= CMPS_FLAGS_EOF;
		aCS.Cmd = RLE_CMD_EOF;
		Action = true;
	}

	return Action;
}

void CmpsWrite8(CmpsState& aCS,unsigned char Data)
{
	if(aCS.OutPtr >= aCS.OutSize)
	{
		aCS.OutSize += ALLOC_CHUNK;
		aCS.pOutBuf = (unsigned char*) img_realloc(aCS.pOutBuf,aCS.OutSize);
	}

	aCS.pOutBuf[aCS.OutPtr] = Data;
	aCS.OutPtr++;
}

void CmpsDump8(CmpsState& aCS)
{
	switch(aCS.Cmd)
	{
		case RLE_CMD_EOL:
		{
			CmpsWrite8(aCS,RLE_CODE_ESCAPE);
			CmpsWrite8(aCS,RLE_CODE_EOL);
		}
		break;

		case RLE_CMD_EOF:
		{
			CmpsWrite8(aCS,RLE_CODE_ESCAPE);
			CmpsWrite8(aCS,RLE_CODE_EOF);
		}
		break;

		case RLE_CMD_DELTA:
		{
			CmpsWrite8(aCS,RLE_CODE_ESCAPE);
			CmpsWrite8(aCS,RLE_CODE_DELTA);
			CmpsWrite8(aCS,(unsigned char)aCS.aParam);
			CmpsWrite8(aCS,(unsigned char)aCS.bParam);
		}
		break;

		case RLE_CMD_ABS:
		{
			CmpsWrite8(aCS,RLE_CODE_ESCAPE);
			CmpsWrite8(aCS,(unsigned char)aCS.bParam);

			unsigned char i,Count;
			Count = (unsigned char) aCS.bParam;
			for(i=0;i<Count;i++)
			 CmpsWrite8(aCS,aCS.pInBuf[aCS.aParam + i]);

			if((Count & 0x01) != 0)
			 CmpsWrite8(aCS,0);
		}
		break;

		case RLE_CMD_ENC:
		{
			CmpsWrite8(aCS,(unsigned char)aCS.bParam);
			CmpsWrite8(aCS,(unsigned char) aCS.aParam);
		}
		break;

		case RLE_CMD_TWO:
		{
			CmpsWrite8(aCS,1);
			CmpsWrite8(aCS,(unsigned char) aCS.aParam);

			CmpsWrite8(aCS,1);
			CmpsWrite8(aCS,(unsigned char) aCS.bParam);
		}
		break;

		default:
		case RLE_CMD_NULL:
		break;
	}
}

bool ExpdRead8(ExpdState& aES,unsigned char& Data)
{
	bool RetVal = false;

	if(aES.InPtr < aES.InSize)
	{
		Data = aES.pInBuf[aES.InPtr];
		aES.InPtr++;
		RetVal = true;
	}
	else
	 Data = 0x00;

	return RetVal;
}

bool NextExpdCmd8(ExpdState& aES)
{
	bool RetVal = false;
	aES.Cmd = RLE_CMD_NULL;

	unsigned char Data;
	if(ExpdRead8(aES,Data))
	{
		if(Data == 0x00)
		{
			if(ExpdRead8(aES,Data))
			{
				switch(Data)
				{
					case 0:
					{
						aES.Cmd = RLE_CMD_EOL;
						aES.aParam = 0;
						aES.bParam = 0;
						RetVal = true;
					}
					break;

					case 1:
					{
						aES.Cmd = RLE_CMD_EOF;
						aES.aParam = 0;
						aES.bParam = 0;
						RetVal = true;
					}
					break;

					case 2:
					{
						aES.Cmd = RLE_CMD_DELTA;

						if(ExpdRead8(aES,Data))
						{
							aES.aParam = (((unsigned long)Data) & 0x000000FF);

							if(ExpdRead8(aES,Data))
							{
								aES.bParam = (((unsigned long)Data) & 0x000000FF);
								RetVal = true;
							}
						}
					}
					break;

					default:
					{
						aES.Cmd = RLE_CMD_ABS;
						aES.aParam = aES.InPtr;
						aES.bParam = (((unsigned long)Data) & 0x000000FF);

						aES.InPtr += Data;
						if((Data & 0x01) != 0)
						 aES.InPtr++;

						RetVal = true;
					}
					break;
				}
			}
		}
		else
		{
			aES.Cmd = RLE_CMD_ENC;
			aES.bParam = (((unsigned long)Data) & 0x000000FF);
			if(ExpdRead8(aES,Data))
			{
				aES.aParam = (((unsigned long)Data) & 0x000000FF);
				RetVal = true;
			}
		}
	}

	return RetVal;
}

void WritePixel8(ExpdState& aES,unsigned char Data)
{
	if((aES.XPos < aES.XDim) && (aES.YPos < aES.YDim))
	{
		unsigned long Ptr = (aES.YPos * aES.LineSize) + aES.XPos;
		aES.pOutBuf[Ptr] = Data;
	}

	aES.XPos++;
}

void ExpdDump8(ExpdState& aES)
{
	switch(aES.Cmd)
	{
		case RLE_CMD_EOL:
		{
			aES.XPos = 0;
			aES.YPos++;
		}
		break;

		case RLE_CMD_EOF:
		{
			aES.XPos = 0;
			aES.YPos = 0;
		}
		break;

		case RLE_CMD_DELTA:
		{
			aES.XPos += aES.aParam;
			aES.YPos += aES.bParam;
		}
		break;

		case RLE_CMD_ABS:
		{
			unsigned long LocalPtr = aES.aParam;
			unsigned char i,Count;

			Count = (unsigned char) aES.bParam;
			for(i=0;i<Count;i++)
			{
				WritePixel8(aES,aES.pInBuf[LocalPtr]);
				LocalPtr++;
			}
		}
		break;

		case RLE_CMD_ENC:
		{
			unsigned char Data = (unsigned char) aES.aParam;
			unsigned char i,Count;

			Count = (unsigned char) aES.bParam;
			for(i=0;i<Count;i++)
			 WritePixel8(aES,Data);
		}
		break;

		default:
		case RLE_CMD_NULL:
		break;
	}
}

void rle_ToRLE8(void*& pBuf,unsigned long& BufSz,ImgRLEInfo& Info)
{
	CmpsState aCS;

	aCS.XDim = Info.XDim;
	aCS.YDim = Info.YDim;
	aCS.LineSize = Info.LineSize;

	aCS.InSize = BufSz;
	aCS.pInBuf = (unsigned char*) pBuf;
	aCS.InPtr = 0;

	aCS.OutSize = ALLOC_CHUNK;
	aCS.pOutBuf = (unsigned char*) img_malloc(aCS.OutSize);
	aCS.OutPtr = 0;

	aCS.NextLine = aCS.LineSize;
	aCS.EndOfLine = aCS.XDim;
	aCS.EndOfFile = (((aCS.YDim - 1) * aCS.LineSize) + aCS.XDim);
	aCS.Flags = CMPS_FLAGS_NONE;

	while(NextCmpsCmd8(aCS))
	 CmpsDump8(aCS);

	if(aCS.OutSize != aCS.OutPtr)
	 aCS.pOutBuf = (unsigned char*) img_realloc(aCS.pOutBuf,aCS.OutPtr);
	 
	img_free(pBuf);
	pBuf = aCS.pOutBuf;
	BufSz = aCS.OutPtr;
}

void rle_FromRLE8(void*& pBuf,unsigned long& BufSz,ImgRLEInfo& Info)
{
	ExpdState aES;

	aES.XDim = Info.XDim;
	aES.YDim = Info.YDim;
	aES.LineSize = Info.XDim;

	char Rem = (char) (aES.LineSize % 4);
	if(Rem != 0)
	 aES.LineSize += (4 - Rem);

	aES.pInBuf = (unsigned char*) pBuf;
	aES.InSize = BufSz;
	aES.InPtr = 0;

	aES.OutSize = aES.YDim * aES.LineSize;
	aES.pOutBuf = (unsigned char*) img_malloc(aES.OutSize);

	aES.XPos = 0;
	aES.YPos = 0;

	while(NextExpdCmd8(aES))
	 ExpdDump8(aES);

	img_free(pBuf);
	pBuf = aES.pOutBuf;
	BufSz = aES.OutSize;
}