Click here to Skip to main content
15,886,110 members
Articles / Programming Languages / C

Fast and Simple Huffman Compressor

Rate me:
Please Sign up or sign in to vote.
4.80/5 (16 votes)
2 Apr 2012CPOL5 min read 75.9K   4.8K   38  
Fast and simple huffman compressor
//#ifndef _SIMPLEHUFFMANH_
//#define _SIMPLEHUFFMANH_ 
#include <memory.h>     // memset
#include <stdlib.h>     // qsort
typedef unsigned char BYTE;
class simple_Huffman{
private:
	class node{
	public:
		node *left, *right;
		int count;       // ref. count
		int code;        // code in bits
		int codelength;  // code length
		BYTE chr;        // ASCII char, serves in compression and then in writing of frequencies
		node(void)  {memset(this, 0, sizeof(node));} // constructor, memset is faster than individ.
		~node() {
			if (left) {delete left; left = NULL;}
			if (right) {delete right; right = NULL;}
		}
	};
	node *trees[256];  // Array of trees, here will be only one tree at pos. 0 when finished with merging 
	node *leaves[256]; // array of leaves, each contains ASCII char,
	                   // ref. count, later code and codelength too. It is a reference to original trees
	node *trees_backup[256];
	int STEPS[256];    // as the tree is constructed, this stores exact steps (movings) of the last tree
	int stepscount;
	node nodes[256];

	void MakeTree();
	void MakeTreeD(); // maketree for decompression (no searching)
	int treescount;
	BYTE *allocatedoutput;
	void InitializeLeaves(node *, int, int);              // initialization of leaves with codes and code lengths
	static int comparefreq(const void *A, const void *B); // sorting, we want to sort descending
	void moveTreesRight(node **toTree);
	void moveTreesRight2(node **toTree);
	void tryToPop();
	void moveToTop();
	void performInternalCleanup();
	void initialize();
	int LastError;
public:
	simple_Huffman();
	int Compress(BYTE *input, int inputlength);
	int Decompress(BYTE *input, int inputlength);
	int CompressFile(char *InFile, char *OutFile);
	int DecompressFile(char *InFile, char *OutFile);
	void Finalize(); // call after each stream compress/decompress to deallocate
	BYTE *getOutput(); // call after each stream compress/decompress to obtain output
	int getLastError();
};
//#endif

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)


Written By
Software Developer (Junior) SOMI Systems
Slovakia Slovakia
Got 1st and 2nd degree from computer science in 2011 on university of Matej Bel, city of Banska Bystrica. Currently work for computer-oriented company SOMI Systems in Slovakia.
Working for SOMI Systems a.s., http://somi.sk/

Comments and Discussions