Click here to Skip to main content
12,405,543 members (56,457 online)
Click here to Skip to main content

Stats

45.1K views
2.5K downloads
20 bookmarked
Posted

RunLength Compression

, 21 Jan 2005 CPOL
Fast Run-Length coding with variable runs sizes.
// 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


You may also be interested in...

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