Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

RunLength Compression

, 21 Jan 2005 CPOL
Fast Run-Length coding with variable runs sizes.
runlength_demo.zip
CompressDemo.exe
runlength_src.zip
CompressDemo.clw
CompressDemo.dsp
CompressDemo.dsw
res
Compress.ico
// RunLength.cpp: implementation of the LZW class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "RunLength.h"

#define GetDWORD(buf,bit,mask) ((*(DWORD*)(((BYTE*)buf)+((bit)>>3)))>>((bit)&7)&(mask))
#define GetWORD(buf,bit,mask) ((*(WORD*)(((BYTE*)buf)+((bit)>>3)))>>((bit)&7)&(mask))

int GetBitCount(int n)
{
	int nBitCount = 0;
	while(n)
		n >>= 1, nBitCount++;
	return nBitCount;
}

int BinarySearch(void* pValue, int nVlaueSize, void* pArray, int nCount)
{
	int nIndex, nResult, nStart = 0, nEnd = nCount-1;
	while(nStart <= nEnd)
	{
		nIndex = (nEnd+nStart)/2;
		if((nResult = memcmp((BYTE*)pArray+nIndex*nVlaueSize, pValue, nVlaueSize)) == 0)
			return nIndex;
		if(nResult > 0)
			nEnd = nIndex-1;
		else
			nStart = nIndex+1;
	}
	return -1;
}

bool CompressRunLength(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen, int nBitsPerSample, void* nRuns, int nRunCount, int nRunSize)
{
	pDes = (BYTE*)malloc(nSrcLen*2);
	memset(pDes, 0, nSrcLen*2);

	nDesLen = sizeof(DWORD);
	*(DWORD*)pDes = nSrcLen;							// save source length
	*(pDes+nDesLen++) = nBitsPerSample;					// save bits per sample
	*(pDes+nDesLen++) = nRunCount;						// save runs count
	*(pDes+nDesLen++) = nRunSize;						// save run bytes
	memcpy(pDes+nDesLen, nRuns, nRunCount*nRunSize);	// save runs
	nDesLen += nRunCount*nRunSize;
	nDesLen <<= 3; // bytes to bits
	if(nRunCount == 0)
		nRunCount = 256, nRunSize = 1, nRuns = NULL;

	int nBitsPerTypeIndex = GetBitCount(nRunCount-1);
	int nMaxRunLength = (1 << nBitsPerSample)-1, nRunLength, nRunIndex, nByte = 0;
	// loop in the source buffer
	while(nByte < nSrcLen)
		if((nRuns && (nRunIndex = BinarySearch(pSrc+nByte, nRunSize, nRuns, nRunCount)) != -1 &&
			memcmp(pSrc+nByte+nRunSize, (BYTE*)nRuns+nRunIndex*nRunSize, nRunSize) == 0) ||
			(!nRuns && (nRunIndex = *(pSrc+nByte)) == *(pSrc+nByte+1)))
		{	// set bit to 1 to indicate type found
			*(pDes+(nDesLen>>3)) |= 1 << (nDesLen&7);
			*(DWORD*)(pDes+(++nDesLen>>3)) |= nRunIndex << (nDesLen&7);
			nDesLen += nBitsPerTypeIndex;
			// skip the two repeated runs
			nByte += nRunSize*2;
			// get run length - 2 (without the two repeated runs)
			nRunLength = 0;
			while(nRunLength < nMaxRunLength && nByte < nSrcLen && 
				((nRuns && memcmp(pSrc+nByte, (BYTE*)nRuns+nRunIndex*nRunSize, nRunSize) == 0) || (!nRuns && (BYTE)nRunIndex == *(pSrc+nByte))))
				nRunLength++, nByte += nRunSize;
			// save run length and increment destination length by bits per sample
			*(DWORD*)(pDes+(nDesLen>>3)) |= nRunLength << (nDesLen&7);
			nDesLen += nBitsPerSample;
		}
		else	// copy one byte
			*(WORD*)(pDes+(++nDesLen>>3)) |= *(pSrc+nByte++) << (nDesLen&7), nDesLen += 8;
	nDesLen = (nDesLen+7)/8;	// bits to bytes
	pDes = (BYTE*)realloc(pDes, nDesLen);

	return true;
}

bool DecompressRunLength(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen)
{
	if(nSrcLen == 0)
		return true;
	
	// allocate destination buffer
	nDesLen = *(DWORD*)pSrc;
	pDes = (BYTE*)malloc(nDesLen);
	memset(pDes, 0, nDesLen);
	
	// copy compression information
	int nSrcIndex = sizeof(DWORD);
	int nBitsPerSample = *(pSrc+nSrcIndex++);
	int nRunCount = *(pSrc+nSrcIndex++);
	int nRunSize = *(pSrc+nSrcIndex++);
	void* nRuns = pSrc+nSrcIndex;
	nSrcIndex += nRunSize*nRunCount;
	nSrcIndex <<= 3; // bytes to bits
	if(nRunCount == 0)
		nRunCount = 256, nRunSize = 1, nRuns = NULL;
	
	int nBitsPerTypeIndex = GetBitCount(nRunCount-1);
	int nMaxTypeIndex = (1 << nBitsPerTypeIndex)-1;
	int nMaxRunLength = (1 << nBitsPerSample)-1;
	int nDesIndex = 0, nRunLength, nRunIndex, nRun, nByte;

	nSrcLen <<= 3; // bytes to bits
	while(nSrcIndex < nSrcLen-8)
		if((*(pSrc+(nSrcIndex>>3)) >> (nSrcIndex++&7)) & 1)
		{
			nRunIndex = GetDWORD(pSrc, nSrcIndex, nMaxTypeIndex), nSrcIndex += nBitsPerTypeIndex;
			nRunLength = GetDWORD(pSrc, nSrcIndex, nMaxRunLength)+2, nSrcIndex += nBitsPerSample;
			for(nRun = 0; nRun < nRunLength; nRun++)
				for(nByte = 0; nByte < nRunSize; nByte++, nDesIndex += 8)
					*(WORD*)(pDes+(nDesIndex>>3)) |= nRuns ? GetWORD(nRuns+nRunSize*nRunIndex, nByte<<3, 0xff) : (BYTE)nRunIndex;
		}
		else	// copy one byte
			*(WORD*)(pDes+(nDesIndex>>3)) |=  GetWORD(pSrc, nSrcIndex, 0xff), nDesIndex += 8, nSrcIndex += 8;

	return true;
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author


| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.1411023.1 | Last Updated 21 Jan 2005
Article Copyright 2005 by Hatem Mostafa
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid