This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| Simple Compression Class Submitted by

A couple of weeks ago I dug into the huge world of data compression, and this is what I've come up with until now. It's a simple compression/decompression class which allows you to (guess! :) compress data. The algorithm I've implemented is a mixture of RLE and Huffman, and is very inferior to most other compressors :(, but, hey, we all have to start somewhere. But it's good enough for the project I'm currently working on. The following files are included: cmpr.cpp (the actual code), cmpr.h (the header), and sample.cpp (a small test program which can compress/decompress files).
Problems:

> - Not suited for very small files, as the header is quite beefy.
> - Data patterns are not compressed enough.
> - It's quite slow.
> - It's using a lot of memory to compress (More than 10 times the data size).
> - Not much error handling.
> - Standard malloc/free is used, you'll probably want to change that to something more useful.

Things that would be cool to add:

> - LZSS compression between the RLE and the Huffman. That would, in some cases, make the compression ratio better. But the compression would also be much slower.
> - A smaller header (compressed?)

This source might be usefull for other people, who are, like me, trying to get the idea of data compression. I've only tried to compile this with VC++6, and the sample is a console app. Rasmus Neckelmann

Currently browsing [cmpr.zip] (6,131 bytes) - [cmpr.cpp] - (16,298 bytes)

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  Simple compression/decompression class
    //
    //  Files: cmpr.cpp, cmpr.h
    //
    //  By Rasmus Neckelmann (mullen@mailme.dk), 27/6-2001
    //

    #include <windows.h>
    #include <string.h>
    #include <malloc.h>

    #include <stdio.h>

    #include "cmpr.h"

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  Constructors, destructors, entry functions
    //

    CCmpr::CCmpr(void) {
    }

    CCmpr::~CCmpr(void) {
    }

    void CCmpr::SetInputData(void *pvData,int nDataSize) {
    	m_nInputSize=nDataSize;
    	m_pvInput=pvData;
    }

    void *CCmpr::GetOutputData(void) {
    	return m_pvOutput;
    }

    int CCmpr::GetOutputSize(void) {
    	return m_nOutputSize;
    }

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //                                  C O M P R E S S I O N
    //
    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  First step of compression (preperation + RLE)
    //

    bool CCmpr::CreateItemList(void) {
    	int nOffset=0;
    	int nRun;
    	int nValue;
    	unsigned char *pcData;
    	int i;

    	// Create list of items + do the initial RLE compression //

    	// Maximum number of items in list is equal to the number of bytes in source buffer... //
    	m_nNumItems=0;
    	m_pnItems=(ITEM *)malloc(sizeof(ITEM)*m_nInputSize);
    	if(!m_pnItems)
    		return FALSE;

    	pcData=(unsigned char *)m_pvInput;

    	// Continue until no bytes is left //
    	while(nOffset<m_nInputSize) {
    		nValue=pcData[nOffset];

    		// Determine run-length (maximum 65535 (not 65536, as we use length 0 for sth else)) //
    		nRun=0;

    		for(i=0;i<65535;i++) {
    			if(pcData[nOffset+i]!=nValue)
    				break;

    			nRun++;
    		}

    		// Create item (first 16 bits are the item length, next 8 bits reserved for later use,
    		// the last 8 bits are the item data) //
    		m_pnItems[m_nNumItems]=nRun | (nValue<<24);
    		m_nNumItems++;

    		// Move read pointer //
    		nOffset+=nRun;
    	}

    	return TRUE;
    }

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  Second step of compression (Huffman)
    //

    bool CCmpr::InitNodePool(void) {
    	int i;

    	// Allocate memory for node pool //
    	m_pNodePool=(hc_nodepool_t *)malloc(sizeof(hc_nodepool_t)*m_nNumItems*2);
    	if(!m_pNodePool)
    		return FALSE;

    	for(i=0;i<m_nNumItems*2;i++) {
    		m_pNodePool[i].bUsed=FALSE;
    		memset(&m_pNodePool[i].node,0,sizeof(hc_node_t));
    	}

    	m_nLastNode=0;

    	return TRUE;
    }

    void CCmpr::FreeNodePool(void) {
    	if(m_pNodePool) {
    		free(m_pNodePool);
    		m_pNodePool=NULL;
    	}
    }

    hc_node_t *CCmpr::AllocateNode(void) {
    	int i,f;

    	// Find first free slot for node //
    	f=-1;
    	for(i=0;i<m_nLastNode;i++) {
    		if(!m_pNodePool[i].bUsed) {
    			f=i;
    			break;
    		}
    	}

    	if(f<0) {
    		f=m_nLastNode;
    		m_nLastNode++;
    	}

    	m_pNodePool[i].bUsed=TRUE;

    	// Return it //
    	return &m_pNodePool[i].node;
    }

    void CCmpr::FreeNode(hc_node_t *pNode) {
    	int i;

    	// Find pNode in pool and remove it //

    	for(i=0;i<m_nLastNode;i++) {
    		if(m_pNodePool[i].bUsed && (&m_pNodePool[i].node)==pNode) {
    			memset(&m_pNodePool[i].node,0,sizeof(hc_node_t));

    			m_pNodePool[i].bUsed=FALSE;
    			if(i==(m_nLastNode-1))
    				m_nLastNode--;

    			break;
    		}
    	}
    }

    hc_node_t *CCmpr::FindLeafByItem(ITEM nItem) {
    	int i;

    	for(i=0;i<m_nLastNode;i++) {
    		if(m_pNodePool[i].bUsed && m_pNodePool[i].node.cType==NODETYPE_LEAF && m_pNodePool[i].node.nItem==nItem)
    			return &m_pNodePool[i].node;
    	}

    	return NULL;
    }

    hc_node_t *CCmpr::FindRootByLeaf(hc_node_t *pLeaf) {
    	hc_node_t *pNode;

    	// Backtrace from leaf to root //
    	pNode=(hc_node_t *)pLeaf->pvParent;

    	while(pNode) {
    		if(pNode->cType==NODETYPE_ROOT)
    			return pNode;

    		pNode=(hc_node_t *)pNode->pvParent;
    	}

    	// Something is SERIOUSLY wrong... all leaves should have a root (this should NOT happen) //
    	return NULL;
    }

    hc_node_t *CCmpr::FindLeastImportantRoot(hc_node_t *pIgnore) {
    	int nLowest=0;
    	hc_node_t *pNode=NULL;
    	int i;

    	// Find the root with the least occurances //
    	for(i=0;i<m_nLastNode;i++) {
    		if(m_pNodePool[i].bUsed && m_pNodePool[i].node.cType==NODETYPE_ROOT && pIgnore!=(&m_pNodePool[i].node)) {
    			if(!nLowest || (m_pNodePool[i].node.nOccurances<nLowest)) {
    				nLowest=m_pNodePool[i].node.nOccurances;
    				pNode=&m_pNodePool[i].node;
    			}
    		}
    	}

    	return pNode;
    }

    int CCmpr::CountRoots(void) {
    	int nRoots=0;
    	int i;

    	for(i=0;i<m_nLastNode;i++) {
    		if(m_pNodePool[i].bUsed && m_pNodePool[i].node.cType==NODETYPE_ROOT) {
    			nRoots++;
    		}
    	}

    	return nRoots;
    }

    int CCmpr::CountLeaves(void) {
    	int nLeaves=0;
    	int i;

    	for(i=0;i<m_nLastNode;i++) {
    		if(m_pNodePool[i].bUsed && m_pNodePool[i].node.cType==NODETYPE_LEAF) {
    			nLeaves++;
    		}
    	}

    	return nLeaves;
    }

    bool CCmpr::AnalyzeItems(void) {
    	hc_node_t *pRoot;
    	hc_node_t *pLeaf;
    	int i;

    	// Classify the items, find out how many of each item-type there are //
    	// Create a root and a leaf for each unique item-type //

    	for(i=0;i<m_nNumItems;i++) {
    		pLeaf=FindLeafByItem(m_pnItems[i]);

    		if(!pLeaf) {
    			// We haven't seen this one before... create root //
    			pRoot=AllocateNode();
    			pRoot->cType=NODETYPE_ROOT;
    			pRoot->nOccurances=1;

    			// Create leaf and attach it to the root we just created //
    			pLeaf=AllocateNode();
    			pLeaf->cType=NODETYPE_LEAF;
    			pLeaf->nItem=m_pnItems[i];
    			pLeaf->pvParent=(void *)pRoot;

    			pRoot->pvChildL=(void *)pLeaf;
    			pRoot->pvChildR=NULL;
    		}
    		else {
    			// Increase the occurance of the unique item //
    			pRoot=FindRootByLeaf(pLeaf);
    			pRoot->nOccurances++;
    		}
    	}

    	return TRUE;
    }

    bool CCmpr::CreateHuffmanTree(void) {
    	int i;
    	int nNumRoots;
    	hc_node_t *pRoot1;
    	hc_node_t *pRoot2;
    	hc_node_t *pNode;
    	hc_node_t *pNode2;

    	// Allocate memory for tree //
    	if(!InitNodePool())
    		return FALSE;

    	// Analyze items //
    	if(!AnalyzeItems())
    		return FALSE;

    	// Now we have some leaves with a LOT of roots... Our job is now to reduce this to only ONE root //
    	nNumRoots=CountRoots();

    	// Continue until only one root is left... //
    	while(nNumRoots>1) {
    		// Find the two least important roots //
    		pRoot1=FindLeastImportantRoot(NULL);
    		pRoot2=FindLeastImportantRoot(pRoot1);

    		// Combine them //
    		if(pRoot1->pvChildR==NULL && pRoot2->pvChildR==NULL) {
    			//  A       B       (A+B)
    			//  |   +   |   =    / \
    			//  X       Y       X   Y
    			pRoot1->pvChildR=pRoot2->pvChildL;
    			((hc_node_t *)pRoot1->pvChildR)->pvParent=(void *)pRoot1;

    			pRoot1->nOccurances+=pRoot2->nOccurances;

    			FreeNode(pRoot2);
    		}
    		else if(pRoot1->pvChildR==NULL && pRoot2->pvChildR!=NULL) {
    			//  A       B        (A+B)
    			//  |   +  / \   =    / \
    			//  X     Y   Z      X   *
    			//                      / \
    			//                     Y   Z
    			pNode=AllocateNode();
    			pNode->cType=NODETYPE_NODE;
    			pNode->pvParent=(void *)pRoot1;
    			pNode->pvChildL=pRoot2->pvChildL;
    			pNode->pvChildR=pRoot2->pvChildR;
    			((hc_node_t *)pNode->pvChildL)->pvParent=(void *)pNode;
    			((hc_node_t *)pNode->pvChildR)->pvParent=(void *)pNode;

    			pRoot1->pvChildR=(void *)pNode;

    			pRoot1->nOccurances+=pRoot2->nOccurances;

    			FreeNode(pRoot2);
    		}
    		else if(pRoot1->pvChildR!=NULL && pRoot2->pvChildR==NULL) {
    			//    A        B        (A+B)
    			//   / \   +   |   =     / \
    			//  X   Y      Z        *   Z
    			//                     / \
    			//                    X   Y
    			pNode=AllocateNode();
    			pNode->cType=NODETYPE_NODE;
    			pNode->pvParent=(void *)pRoot1;
    			pNode->pvChildL=pRoot1->pvChildL;
    			pNode->pvChildR=pRoot1->pvChildR;
    			((hc_node_t *)pNode->pvChildL)->pvParent=(void *)pNode;
    			((hc_node_t *)pNode->pvChildR)->pvParent=(void *)pNode;

    			pRoot1->pvChildL=(void *)pNode;
    			pRoot1->pvChildR=(void *)pRoot2->pvChildL;
    			((hc_node_t *)pRoot1->pvChildR)->pvParent=(void *)pRoot1;

    			pRoot1->nOccurances+=pRoot2->nOccurances;

    			FreeNode(pRoot2);
    		}
    		else if(pRoot1->pvChildR!=NULL && pRoot2->pvChildR!=NULL) {
    			//    A        B            (A+B)
    			//   / \   +  / \    =       / \
    			//  W   X    Y   Z          *   *
    			//                         /\   /\
    			//                        W  X Y  Z
    			pNode=AllocateNode();
    			pNode->cType=NODETYPE_NODE;
    			pNode->pvParent=(void *)pRoot1;
    			pNode->pvChildL=pRoot1->pvChildL;
    			pNode->pvChildR=pRoot1->pvChildR;
    			((hc_node_t *)pNode->pvChildL)->pvParent=(void *)pNode;
    			((hc_node_t *)pNode->pvChildR)->pvParent=(void *)pNode;

    			pNode2=AllocateNode();
    			pNode2->cType=NODETYPE_NODE;
    			pNode2->pvParent=(void *)pRoot1;
    			pNode2->pvChildL=pRoot2->pvChildL;
    			pNode2->pvChildR=pRoot2->pvChildR;
    			((hc_node_t *)pNode2->pvChildL)->pvParent=(void *)pNode2;
    			((hc_node_t *)pNode2->pvChildR)->pvParent=(void *)pNode2;

    			pRoot1->pvChildL=(void *)pNode;
    			pRoot1->pvChildR=(void *)pNode2;

    			pRoot1->nOccurances+=pRoot2->nOccurances;

    			FreeNode(pRoot2);
    		}

    		nNumRoots--;
    	}

    	// The encoding tree is now DONE //

    	return TRUE;
    }

    void CCmpr::EncodeItem(hc_item_t *pItem,hc_node_t *pLeaf) {
    	ITEMCODEWORD nBits;
    	int nLevels;
    	hc_node_t *pNode;
    	hc_node_t *pPrev;
    	int i;

    	// Backtrace to root //
    	pNode=(hc_node_t *)pLeaf->pvParent;
    	pPrev=pLeaf;
    	nLevels=0;
    	nBits=0;

    	while(pNode) {
    		// Where did we come from? //
    		if(pPrev==pNode->pvChildL) {
    			// From the left //
    			// Bit OFF //
    		}
    		else if(pPrev==pNode->pvChildR) {
    			// From the right //
    			// Bit ON //
    			nBits|=(1<<nLevels);
    		}

    		if(pNode->cType==NODETYPE_ROOT) {
    			// We have found the root!! //
    			break;
    		}

    		nLevels++;
    		pPrev=pNode;
    		pNode=(hc_node_t *)pNode->pvParent;
    	}

    	nLevels++;

    	// We have determined the route BACKWARDS -- now reverse it //
    	pItem->nCodeWord=0;

    	for(i=0;i<nLevels;i++) {
    		if(nBits & (1<<i)) {
    			pItem->nCodeWord|=(1<<(nLevels-i-1));
    		}
    	}

    	pItem->cBits=nLevels;
    }

    bool CCmpr::HuffmanEncode(void) {
    	int i,j,k;
    	int nIndex;
    	hc_item_t *pTable;
    	unsigned char *pcCompressedData;
    	unsigned char *pcTmp;
    	int nCompressedSize;
    	int nOffset=0;
    	int nBitOffset=0;
    	int nPtr;
    	unsigned char cByte;
    	unsigned short nWord;

    	// Create encoding tree //
    	if(!CreateHuffmanTree())
    		return FALSE;

    	// Before we can do the encoding, we'll have to set up a quick lookup table for codewords //
    	pTable=(hc_item_t *)malloc(sizeof(hc_item_t)*CountLeaves());
    	if(!pTable)
    		return FALSE;

    	nIndex=0;

    	for(i=0;i<m_nLastNode;i++) {
    		if(m_pNodePool[i].bUsed && m_pNodePool[i].node.cType==NODETYPE_LEAF) {
    			pTable[nIndex].nItem=m_pNodePool[i].node.nItem;

    			// Encode the item //
    			EncodeItem(&pTable[nIndex],&m_pNodePool[i].node);

    			nIndex++;
    		}
    	}

    	// Allocate memory for compressed data //
    	pcCompressedData=(unsigned char *)malloc(m_nInputSize*2);
    	if(!pcCompressedData)
    		return FALSE;

    	memset(pcCompressedData,0,m_nInputSize*2);

    	// With the table up-and-running we can do the actual encoding of data //

    	for(i=0;i<m_nNumItems;i++) {
    		// Find the item's codeword in the table //
    		for(j=0;j<nIndex;j++) {
    			if(pTable[j].nItem==m_pnItems[i]) {
    				// Send it to the bitstream //
    				for(k=0;k<pTable[j].cBits;k++) {
    					if(pTable[j].nCodeWord & (1<<k))
    						pcCompressedData[nOffset] |= (1<<nBitOffset);

    					// Increase the bit offset //
    					nBitOffset++;
    					if(nBitOffset>7) {
    						nBitOffset=0;
    						nOffset++;
    					}
    				}
    			}
    		}
    	}

    	nCompressedSize=nOffset;
    	if(nBitOffset>0) nCompressedSize++;

    	// Now it is time to put the various things together -- the table and the data we just encoded //
    	pcTmp=(unsigned char *)malloc(m_nInputSize*2+4096);
    	if(!pcTmp)
    		return FALSE;

    	nPtr=0;

    	// Make room for header //
    	nPtr+=8;

    	// Write table //
    	memcpy(&pcTmp[nPtr],&nIndex,4);
    	nPtr+=4;

    	for(i=0;i<nIndex;i++) {
    		memcpy(&pcTmp[nPtr],&pTable[i].cBits,1);
    		nPtr++;

    		if(pTable[i].cBits<=8) {
    			cByte=pTable[i].nCodeWord;
    			memcpy(&pcTmp[nPtr],&cByte,1);
    			nPtr++;
    		}
    		else if(pTable[i].cBits<=16) {
    			nWord=pTable[i].nCodeWord;
    			memcpy(&pcTmp[nPtr],&nWord,2);
    			nPtr+=2;
    		}
    		else {
    			memcpy(&pcTmp[nPtr],&pTable[i].nCodeWord,4);
    			nPtr+=4;
    		}

    		memcpy(&pcTmp[nPtr],&pTable[i].nItem,4);
    		nPtr+=4;
    	}

    	// Write compressed data //
    	memcpy(&pcTmp[nPtr],pcCompressedData,nCompressedSize);
    	nPtr+=nCompressedSize;

    	// Write header //
    	memcpy(&pcTmp[0],&m_nInputSize,4);
    	memcpy(&pcTmp[4],&nCompressedSize,4);

    	// FINISHED! //
    	m_pvOutput=(void *)malloc(nPtr);
    	if(!m_pvOutput)
    		return FALSE;

    	memcpy(m_pvOutput,pcTmp,nPtr);
    	m_nOutputSize=nPtr;

    	// Free stuff //
    	free((void *)pTable);
    	free(pcCompressedData);
    	free(pcTmp);
    	FreeNodePool();

    	return TRUE;
    }

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  Data compression
    //

    bool CCmpr::Compress(void) {
    	int i;

    	// Do first step of compression (RLE) //
    	if(!CreateItemList())
    		return FALSE;

    	// Do Second step of compression (Huffman) //
    	if(!HuffmanEncode())
    		return FALSE;

    	// Clean up //
    	free(m_pnItems);

    	return TRUE;
    }

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //                                D E C O M P R E S S I O N
    //

    bool CCmpr::Uncompress(void) {
    	int nRBit,nRByte,nLevel;
    	unsigned char *pcInput;
    	unsigned char *pcOutput;
    	int nReadPtr,nWritePtr;
    	int nItemTypes;
    	int nRawSize,nCompressedSize;
    	hc_item_t *pTable;
    	int i,j;
    	unsigned char cByte;
    	unsigned short nWord;
    	unsigned char *pcStream;
    	ITEMCODEWORD nCodeWord;
    	bool bEqual;
    	int nLen,nMLen;
    	int nOffset;

    	pcInput=(unsigned char *)m_pvInput;

    	// First step of decompression is to get the decoding table //
    	memcpy(&nRawSize,&pcInput[0],4);
    	memcpy(&nCompressedSize,&pcInput[4],4);
    	memcpy(&nItemTypes,&pcInput[8],4);
    	nReadPtr=12;

    	pTable=(hc_item_t *)malloc(sizeof(hc_item_t)*nItemTypes);
    	if(!pTable)
    		return FALSE;

    	for(i=0;i<nItemTypes;i++) {
    		memcpy(&pTable[i].cBits,&pcInput[nReadPtr],1);
    		nReadPtr++;

    		if(pTable[i].cBits<=8) {
    			memcpy(&cByte,&pcInput[nReadPtr],1);
    			nReadPtr++;
    			pTable[i].nCodeWord=cByte;
    		}
    		else if(pTable[i].cBits<=16) {
    			memcpy(&nWord,&pcInput[nReadPtr],2);
    			nReadPtr+=2;
    			pTable[i].nCodeWord=nWord;
    		}
    		else {
    			memcpy(&pTable[i].nCodeWord,&pcInput[nReadPtr],4);
    			nReadPtr+=4;
    		}

    		memcpy(&pTable[i].nItem,&pcInput[nReadPtr],4);
    		nReadPtr+=4;
    	}

    	// Create a pointer to the bitstream //
    	pcStream=&pcInput[nReadPtr];

    	// Start the decoding //
    	pcOutput=(unsigned char *)malloc(nRawSize);
    	if(!pcOutput)
    		return FALSE;

    	m_pvOutput=(void *)pcOutput;

    	nRBit=0;
    	nRByte=0;
    	nWritePtr=0;
    	nLevel=0;
    	nCodeWord=0;

    	// Continue until all data is restored //
    	while(nWritePtr<nRawSize) {
    		// Read a bit from the stream //
    		if(pcStream[nRByte] & (1<<nRBit)) {
    			nCodeWord|=(1<<nLevel);
    		}
    		nLevel++;

    		// Is 'nCodeWord' found in the table? //
    		for(i=0;i<nItemTypes;i++) {
    			// Compare the two codewords //
    			bEqual=TRUE;
    			if(pTable[i].cBits==nLevel) {
    				for(j=0;j<nLevel;j++) {
    					if(nCodeWord & (1<<j)) {
    						if(!(pTable[i].nCodeWord & (1<<j))) {
    							bEqual=FALSE;
    							break;
    						}
    					}
    					else if(!(nCodeWord & (1<<j))) {
    						if(pTable[i].nCodeWord & (1<<j)) {
    							bEqual=FALSE;
    							break;
    						}
    					}
    				}
    			}
    			else {
    				bEqual=FALSE;
    			}

    			if(bEqual) {
    				// We've found it! //
    				nLen=pTable[i].nItem & 0xFFFF;

    				if(nLen>0) {
    					// RLE //
    					cByte=(pTable[i].nItem & 0xFF000000) >> 24;
    					memset(&pcOutput[nWritePtr],cByte,nLen);
    					nWritePtr+=nLen;
    				}

    				// Reset codeword //
    				nLevel=0;
    				nCodeWord=0;
    				break;
    			}
    		}

    		// Move to next bit //
    		nRBit++;
    		if(nRBit>7) {
    			nRBit=0;
    			nRByte++;
    		}
    	}

    	m_nOutputSize=nRawSize;

    	// Clean up //
    	free(pTable);

    	return TRUE;
    }

Currently browsing [cmpr.zip] (6,131 bytes) - [cmpr.h] - (2,098 bytes)

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  Simple compression/decompression class
    //
    //  Files: cmpr.cpp, cmpr.h
    //
    //  By Rasmus Neckelmann (mullen@mailme.dk), 27/6-2001
    //

    #ifndef __CMPR_H__
    #define __CMPR_H__

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  Misc definitions
    //

    typedef unsigned long ITEM;
    typedef unsigned long ITEMCODEWORD;

    #define NODETYPE_NODE   0x00
    #define NODETYPE_ROOT		0x01
    #define NODETYPE_LEAF		0x02

    typedef struct {
    	unsigned char cType;

    	void *pvParent;
    	void *pvChildL,*pvChildR;

    	// Leaves //
    	ITEM nItem;

    	// Roots //
    	int nOccurances;
    } hc_node_t;

    typedef struct {
    	bool bUsed;
    	hc_node_t node;
    } hc_nodepool_t;

    typedef struct {
    	ITEM nItem;

    	unsigned char cBits;
    	ITEMCODEWORD nCodeWord;
    } hc_item_t;

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  Class definition
    //

    class CCmpr {
    	// ***** Member functions ***** //
    	public:
    	CCmpr(void);
    	~CCmpr(void);

    	void SetInputData(void *pvData,int nDataSize);
    	void *GetOutputData(void);
    	int GetOutputSize(void);

    	bool Compress(void);
    	bool Uncompress(void);

    	private:
    	bool CreateItemList(void);
    	bool CreateHuffmanTree(void);
    	bool HuffmanEncode(void);

    	void EncodeItem(hc_item_t *pItem,hc_node_t *pLeaf);
    	bool AnalyzeItems(void);

    	hc_node_t *FindLeafByItem(ITEM nItem);
    	hc_node_t *FindRootByLeaf(hc_node_t *pLeaf);
    	hc_node_t *FindLeastImportantRoot(hc_node_t *pIgnore);

    	int CountRoots(void);
    	int CountLeaves(void);
    	bool InitNodePool(void);
    	void FreeNodePool(void);
    	hc_node_t *AllocateNode(void);
    	void FreeNode(hc_node_t *pNode);

    	// ***** Member variables ***** //
    	public:

    	private:
    	// Data //
    	int m_nInputSize;
    	void *m_pvInput;

    	int m_nOutputSize;
    	void *m_pvOutput;

    	// Temporary buffers and such //
    	int m_nNumItems;
    	ITEM *m_pnItems;

    	int m_nLastNode;
    	hc_nodepool_t *m_pNodePool;
    };

    #endif

Currently browsing [cmpr.zip] (6,131 bytes) - [sample.cpp] - (2,560 bytes)

    ////////////////////////////////////////////////////////////////////////////////////////////////
    //
    //  Sample application using my compression/decompression class
    //
    //  Files: sample.cpp
    //
    //  By Rasmus Neckelmann (mullen@mailme.dk), 27/6-2001
    //

    #include <windows.h>
    #include <stdio.h>
    #include <string.h>
    #include <malloc.h>

    #include "cmpr.h"

    void main(int nNumArguments,char **ppcArguments) {
    	int i;
    	FILE *fp;
    	int nInputDataSize;
    	void *pvInputData;

    	CCmpr *pCmpr;

    	char *pcInputFile=NULL;
    	char *pcOutputFile=NULL;
    	bool bDecompress=FALSE;

    	// Parse command-line arguments //
    	for(i=1;i<nNumArguments;i++) {
    		if(!strcmp(ppcArguments[i],"-d") || !strcmp(ppcArguments[i],"-D")) {
    			bDecompress=TRUE;
    		}
    		else if(!strcmp(ppcArguments[i],"-c") || !strcmp(ppcArguments[i],"-C")) {
    			bDecompress=FALSE;
    		}
    		else {
    			if(pcInputFile==NULL) pcInputFile=ppcArguments[i];
    			else pcOutputFile=ppcArguments[i];
    		}
    	}

    	// Should we display some help text? //
    	if(pcInputFile==NULL || pcOutputFile==NULL) {
    		printf("usage: sample infile outfile [options]\n");
    		printf("options: (* = default)\n");
    		printf("  -d    Decompress\n");
    		printf("* -c    Compress\n");
    		return;
    	}

    	// Create compression/decompression object //
    	pCmpr=new CCmpr;

    	// Read input file //
    	fp=fopen(pcInputFile,"rb");
    	if(!fp) {
    		printf("Could not open input file: %s!\n",pcInputFile);
    		return;
    	}

    	fseek(fp,0,SEEK_END);
    	nInputDataSize=ftell(fp);
    	fseek(fp,0,SEEK_SET);

    	pvInputData=(void *)malloc(nInputDataSize);
    	fread(pvInputData,nInputDataSize,1,fp);
    	fclose(fp);

    	// Set up compressor/decompressor //
    	pCmpr->SetInputData(pvInputData,nInputDataSize);

    	// Compress/decompress //
    	if(bDecompress) {
    		printf("Decompressing data..."); fflush(stdout);
    		if(!pCmpr->Uncompress()) {
    			printf("Something went wrong while decompressing data!\n");
    			return;
    		}
    		printf("OK\n");
    	}
    	else {
    		printf("Compressing data..."); fflush(stdout);
    		if(!pCmpr->Compress()) {
    			printf("Something went wrong while compressing data!\n");
    			return;
    		}
    		printf("OK\n");
    		printf("%d -> %d (%d%c)\n",nInputDataSize,pCmpr->GetOutputSize(),(pCmpr->GetOutputSize()*100)/nInputDataSize,'%');
    	}

    	// Save //
    	fp=fopen(pcOutputFile,"wb");
    	if(!fp) {
    		printf("Could not open output file: %s!\n",pcOutputFile);
    		return;
    	}

    	fwrite(pCmpr->GetOutputData(),pCmpr->GetOutputSize(),1,fp);
    	fclose(fp);

    	// Clean up //
    	free(pCmpr->GetOutputData());
    	delete pCmpr;
    }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.