dos.cpp

Huffman compression by Visual C++2008

#include <iostream.h>
#include <string.h>
#include <fstream.h>
#include <stdlib.h>
#include <conio.h>

#define NUM_CHAR 256
#define NUM_BIT 8
struct treenode {

		unsigned int freq;
		unsigned char ch;
		treenode *left;
		treenode *right;

};
struct PQ {

	int heap_size;
	treenode *A[NUM_CHAR];
};

struct bit_buffer{
	char content[NUM_BIT];
	int post;
};
int parent (int i)
{
	return (i-1) / 2;
}

int left_child(int i)
{
	return i*2 + 1;
}

int right_child(int i)
{
	return i*2 + 2;
}

void create_pq(PQ *p)
{
	 p->heap_size = 0;
}

class Compress {
protected:
	unsigned int freq[NUM_CHAR];
	unsigned char ch;
	int nbits;
	int current_byte;
	
public:
	Compress();
	unsigned int get_frequencies (char *NameFileIn);
	void heapify (PQ *p, int i);
	void insert_pq (PQ *p, treenode *r);
    treenode *extract_min_pq (PQ *p);
	treenode *build_huffman ();
	void traverse (treenode *r,int level,char code_so_far[],char *codes[ ]);
	void bitout(fstream &FileOut, char bit);
    void encode_file(char *NameFileIn, char *NameFileOut, char *codes[ ]);
};


Compress::Compress()
{
	for(int i=0;i<NUM_CHAR;++i)
		freq[i] = 0;
}

unsigned int Compress::get_frequencies(char *NameFileIn)
{
	unsigned int n;
	fstream	FileIn(NameFileIn,ios::in|ios::binary);

	for (n=0;;n++)
	{
		FileIn.get(ch);	
		if (FileIn.eof())
			break;
		
		freq[ch]++;
	}
	FileIn.close();
	return n;
}
void Compress::heapify(PQ *p, int i)
{
		int l, r, smallest;
		treenode *t;
		
		l = left_child (i);
		r = right_child (i);
		if (l < p->heap_size && p->A[l]->freq < p->A[i]->freq)
			smallest = l;
		else
			smallest = i;
		if (r < p->heap_size && p->A[r]->freq < p->A[smallest]->freq)
			smallest = r;
		
		if (smallest != i) 
		{
			t = p->A[i];
			p->A[i] = p->A[smallest];
			p->A[smallest] = t;
			this->heapify (p, smallest);
		}
}
void Compress::insert_pq(PQ *p, treenode *r)
{
	int i;
	
	p->heap_size++;
	i = p->heap_size - 1;
	
	while ((i > 0) && (p->A[parent(i)]->freq > r->freq)) 
	{
		p->A[i] = p->A[parent(i)];
		i = parent (i);
	}
	p->A[i] = r;
}

treenode* Compress::extract_min_pq(PQ *p)
{
	treenode *r;
	if (p->heap_size == 0) 
	{
		cout<<"hang doi rong!\n";
		exit (1);
	}
	r = p->A[0];
	p->A[0] = p->A[p->heap_size-1];
	p->heap_size--;
	this->heapify (p, 0);
	return r;
}

treenode* Compress::build_huffman()
{
	int i, n;
	treenode *x, *y, *z;
	PQ p;
	
	create_pq (&p);
	
	for (i=0; i< NUM_CHAR; i++) 
	{
		x = (treenode*)malloc (sizeof (treenode));
		x->left = NULL;
		x->right = NULL;
		x->freq = freq[i];
		x->ch = (char) i;
		this->insert_pq (&p, x);
	}
	n = p.heap_size-1;
	for (i=0; i< n; i++) 
	{
		z = (treenode*)malloc (sizeof (treenode));
		x = this->extract_min_pq (&p);
		y = this->extract_min_pq (&p);
		z->left = x;
		z->right = y;
		z->freq = x->freq + y->freq;
		this->insert_pq (&p, z);
	}

	return this->extract_min_pq (&p);
}

void Compress::traverse(treenode *r,int level,char code_so_far[],char *codes[ ])
{
	if ((r->left == NULL) && (r->right == NULL)) 
	{
		code_so_far[level] = 0;
		
		codes[r->ch] = strdup (code_so_far);
	} 
	else 
	{
		code_so_far[level] = '0';
		this->traverse (r->left, level+1, code_so_far, codes);
		
		code_so_far[level] = '1';
		this->traverse (r->right, level+1, code_so_far, codes);
	}
}

void Compress::bitout(fstream &FileOut, char bit)
{
	current_byte <<= 1;
	
	
	if (bit == '1')
	current_byte |= 1;
	nbits++;
	
	if (nbits == NUM_BIT)
	{
		FileOut.put ((unsigned char)current_byte);
		nbits = 0;
		current_byte = 0;
	}
}


void Compress::encode_file(char *NameFileIn, char *NameFileOut, char *codes[ ])
{
	int n = 0;
	char *s;
	current_byte =0;
	nbits = 0;
	for(int i=0;i<NUM_CHAR;++i)
		if(freq[i])
		++n;  // So ky tu co trong File
		
		fstream FileIn(NameFileIn,ios::in|ios::binary);
		fstream FileOut(NameFileOut,ios::out|ios::binary);
		FileOut.write((char*)(&n),sizeof(n));
		for(i=0;i<NUM_CHAR;++i)
		if(freq[i])
		{
			FileOut.put(unsigned char(i));
			FileOut.write((char *)(&freq[i]),sizeof(int));
		}
		for(;;)
		{
			FileIn.get(ch);
			if(FileIn.eof())
				break;
			for (s=codes[ch]; *s; s++)
				this->bitout (FileOut, *s);
		}
		n = nbits;
		while(nbits)
			this->bitout(FileOut,'0');
		FileOut.put(char(n));
		FileIn.close();
		FileOut.close();
}
class Decompress : public Compress 
{
private:	
	bit_buffer buff;
public:
	Decompress();
	void convert_bin(unsigned char c);
	void decode_file(char *FileIn, char *FileOut);


};
Decompress::Decompress()
{
	for(int i=0;i<NUM_CHAR;++i)
		freq[i] = 0;
}
void Decompress::convert_bin(unsigned char c)
{	
	int i;
	for(i=0;i<NUM_BIT;++i)
		buff.content[i] = '0';
	buff.content[NUM_BIT]='\0';
	i= NUM_BIT - 1;
	while(i>=0)
	{	
		buff.content[i]=(c%2)+'0';
		c=c/2;
		i--;
	}
	buff.post = 0;
	
}

void Decompress::decode_file(char *NameFileIn, char *NameFileOut)
{
	char *codes[NUM_CHAR];
	char code[NUM_CHAR];
	unsigned char c;  // luu tru byte cuoi cung
	int n;  // So ky tu co trong File truoc khi nen
	fstream FileIn(NameFileIn,ios::in|ios::binary);
	fstream FileOut(NameFileOut,ios::out|ios::binary);
	FileIn.read((char*)(&n),sizeof(n));
	for(int i=1;i<=n;++i)
	{	
		FileIn.get(unsigned char(ch));
		FileIn.read((char*)(&freq[ch]),sizeof(int)); 
	}
	int start = FileIn.tellg();
	FileIn.seekp(-1,ios::end);
	int full_bytes = FileIn.tellg() - start - 1;
	FileIn.get(c);
	FileIn.seekg(-full_bytes-2,ios::end);
	treenode *r = this->build_huffman();
	this->traverse (r, 0, code, codes);
	treenode *t=r;
	FileIn.get(ch);
	this->convert_bin(ch);
	for(i=1;i<=full_bytes;)
	{	
		if(t->left==NULL&&t->right==NULL)
		{	
			FileOut.put(t->ch);
			t = r;
		}
		else
		{
			if(buff.post<NUM_BIT&&buff.content[buff.post]=='0')
				t = t->left;
			if(buff.post<NUM_BIT&&buff.content[buff.post]=='1')
				t = t->right;
			if(buff.post==NUM_BIT)
			{
				FileIn.get(ch);
				this->convert_bin(ch);
				++i;
				buff.post = -1;
			}
			buff.post++;
			
		}
		
	}
	int remain = (int(c)==0)?NUM_BIT:int(c);
	for(;buff.post<=remain;)
	{	
		if(t->left==NULL&&t->right==NULL)
		{
			FileOut.put(t->ch);
			t = r;
		}
		else
		{
			if(buff.post<NUM_BIT&&buff.content[buff.post]=='0')
				t = t->left;
			if(buff.post<NUM_BIT&&buff.content[buff.post]=='1')
				t = t->right;
			buff.post++;
		
		}

	}
	FileIn.close();
	FileOut.close();
	
}
void main()
{	
	Compress C;
	Decompress D;
	char *s = "C:\\Input.txt";
	char *s1 = "C:\\Compress.huf";
	char *codes[NUM_CHAR];
	char code[NUM_CHAR];
	C.get_frequencies(s);
	treenode *r= C.build_huffman();
	C.traverse(r,0,code,codes);
	C.encode_file(s,s1,codes);
	D.decode_file(s1,"C:\\Decompress.txt");
}