stdafx.cpp

this is hupffman code.you can compress file with this application

// stdafx.cpp : source file that includes just the standard includes
//	0712118.pch will be the pre-compiled header
//	stdafx.obj will contain the pre-compiled type information

#include "stdafx.h"

// TODO: reference any additional headers you need in STDAFX.H
// and not in this file
inline int Huffman::getnextbit()
{
	if (bitslast)
	{
		return 0x1 & (*psour >> (--bitslast));
	}
	else
	{
		psour++;
		bitslast = 8;
		return 0x1 & (*psour >> (--bitslast));
	}
}



//======================================================================
void Huffman::encode(unsigned char *dest, int &csize, unsigned char *sour, int usize)
{
	pheader = (HUFFHDR)dest;     //header
	psour = sour;                //con tro nguon
	pdest = dest;                //con tro dich
	filesize = usize;            //size cua tap tin chua nen
	csize = 0;                   

	SoLuongKyTu = 0;
	bitslast = 8;

	inittree();               
	taocay();                 
	buildtable();           
	for (int i = 0; i < filesize; i++)
		writesymb(*psour++);

	csize = int((pdest - dest) + 1);
	pheader->Size_DaNen = csize;

	pheader =NULL;
	psour = NULL;              //con tro nguon
	pdest = NULL;             //con tro dich
	this->psheader=NULL;								
	this->temptree=NULL;								// cay huff  tam
	htree=NULL;								// huff tree
	hsymbol=NULL;

}

//------------------------------------------------------------------------------
void Huffman::decode(unsigned char *dest, int &usize, unsigned char *sour)
{
	pheader = (HUFFHDR)sour;     
	psour = sour;                
	pdest = dest;                
	usize = 0;                   

	bitslast = 8;

	readtree();               
	taocay();                 
	while (filesize) {
		*pdest++ = readsymb();
		filesize--;
	}

	usize = int(pdest - dest);
	pheader =NULL;
	psour = NULL  ;              //con tro nguon
	pdest = NULL   ;             //con tro dich

}

/*                           HUFF ENCODING                                  */
void Huffman::inittree()
{
	/*               memory init                           */
	memset(tmass1, 0, 256*sizeof(hufftree));	//khoi tao vung nho ban dau voi ki tu 0
	memset(tmass2, 0, 256*sizeof(hufftree));	//khoi tao vung nho ban dau voi ki tu 0
	memset(smass, 0, 256*sizeof(huffsymbol));	//khoi tao vung nho ban dau voi ki tu 0
	int i;

	temptree = (HTREE)tmass1;
	htree = (HTREE)tmass2;
	hsymbol = (SYMB)smass;

	for (i = 0; i < 256; i++) 
		temptree[i].s1 = i;               //khoi tao 256 ki tu cho 'temptrree'
	for ( i = 0; i < filesize; i++) 
		temptree[psour[i]].freq++;   //tim trong so cac ky tu cho temptree, psour[i] la chi so cua ki tu trong 256 ki tu
	for (i = 0; i < 256; i++)			// psour la con tro luu chuoi ki tu
		if (temptree[i].freq) 
			SoLuongKyTu++;        //tong so luong cac loai ki tu

	qsort((void *)temptree, 256, sizeof(hufftree), &compare);      //sap xep temptree	

	/*              khoi tao headers                           */
	memcpy(pheader->huff, "HUFF", 4);
	memcpy(pheader->TenFile,this->TenFile, 255);
	pheader->SoLuongKyTu = SoLuongKyTu;
	pheader->Size_ChuaNen = filesize;
	pheader->Size_DaNen = 0;
	pdest += sizeof(huffheader);	// tang kich thuoc con tro dich

	for ( i = 0; i < SoLuongKyTu; i++) 
	{
		psheader = (SYMBHDR)pdest;
		psheader->symb = temptree[i].s1;
		psheader->freq = temptree[i].freq;

		pdest += 5;   
	}
	*pdest = 0;
}

/*         tao cay huff tu cay tam                */
void Huffman::taocay()
{
	/*        truong hop dac biet SoLuongKyTu = 1   */
	if (SoLuongKyTu == 1) {
		hsymbol[psour[0]].size = 1;
		return;
	}
	/*		tat ca cac truong ho khac			*/
	for (int i = SoLuongKyTu - 2; i >= 0; i--) 
	{
		if (temptree[i].parent) 
		{							                    
			htree[i].pleft = temptree[i].parent;        
			htree[i].pleft->parent = &htree[i];
		} 
		else
			htree[i].s1 = temptree[i].s1;               

		if (temptree[i+1].parent) 
		{
			htree[i].pright = temptree[i+1].parent;     
			htree[i].pright->parent = &htree[i];
		} 
		else
			htree[i].s2 = temptree[i+1].s1;	           

		if (i)
		{
			temptree[i].freq += temptree[i+1].freq;     //[i]+[i+1] la trong so cho node [i] moi
			temptree[i].parent = &htree[i];             //[i] tro thanh 1 node
			temptree[i+1].freq = 0;                     //[i+1] bi loai

			qsort((void *)temptree, (i + 1), sizeof(hufftree), &compare);
		}
	}
}

/*         xay dung mang ma tu htree        */
void Huffman::buildtable()
{
	unsigned char c;
	HTREE parent, child;

	for (int i = SoLuongKyTu - 2; i >= 0; i--)
	{
		if (!htree[i].pleft) 
		{         
			c = htree[i].s1;
			hsymbol[c].size++;

			child = &htree[i];
			parent = child->parent;
			while (parent) 
			{
				if (parent->pleft == child)              //them 0
					hsymbol[c].size++;
				if (parent->pright == child)		     //them 1
					hsymbol[c].symb |= (1 << hsymbol[c].size++);

				child = parent;                    //hoan vi cha con
				parent = child->parent;            
			}
		}
		if (!htree[i].pright) 
		{        
			c = htree[i].s2;
			hsymbol[c].symb |= (1 << hsymbol[c].size++);

			child = &htree[i];
			parent = child->parent;
			while (parent) {
				if (parent->pleft == child)              //them 0
					hsymbol[c].size++;
				if (parent->pright == child)             //them 1
					hsymbol[c].symb |= (1 << hsymbol[c].size++);

				child = parent;                    //hoan vi cha con
				parent = child->parent;            
			}
		}
	}
}

/*         ghi bang ma ra dest    */
void Huffman::writesymb(int c)
{
	for (unsigned int i = 1; i <= hsymbol[c].size; i++) 
	{
		*pdest |= ((0x1 & (hsymbol[c].symb >> (hsymbol[c].size - i))) << (--bitslast));

		if (bitslast == 0)
		{
			*(++pdest) = 0;
			bitslast = 8;
		}
	}
}


/*                           HUFF DECODING	                             */

/*         doc huff header va tim freqs        */
void Huffman::readtree()
{
	/*              khoi tao                    */
	memset(tmass1, 0, 256*sizeof(hufftree));
	memset(tmass2, 0, 256*sizeof(hufftree));

	temptree = (HTREE)tmass1;
	htree = (HTREE)tmass2;

	//filesize = pheader->Size_ChuaNen;
	strcpy(TenFile,pheader->TenFile);
	SoLuongKyTu = pheader->SoLuongKyTu;
	psour += sizeof(huffheader);

	/*       get freqs      */
	for (int i = 0; i < SoLuongKyTu; i++) {
		psheader = (SYMBHDR)psour;
		temptree[i].freq = psheader->freq;
		temptree[i].s1 = psheader->symb;

		psour += 5;    
	}
}

/*         giai ma cac ki tu        */
unsigned char Huffman::readsymb()
{
	HTREE node = &htree[0];

	while (1) 
	{
		if (getnextbit()) 
		{         
			if (node->pright)
				node = node->pright;
			else
				return node->s2;
		} 
		else 
		{              
			if (node->pleft)
				node = node->pleft;
			else
				return node->s1;
		}
	}
}



/*         ham compare cho qsort()              */
int __cdecl  Huffman::compare(const void *a, const void *b)
{
	HTREE t1 = (HTREE)a;
	HTREE t2 = (HTREE)b;

	if (t1->freq == t2->freq) 
		return 0;
	else 
		return ((t1->freq < t2->freq) ? 1 : -1);
}

int get_file_size(FILE *fp)		// ham tim kich thuoc tap tin
{
	fseek(fp, 0, SEEK_END);
	int size = ftell(fp);
	fseek(fp, 0, SEEK_SET);
	return size;
}

//-----dua vao 1 ten file va tra ve 'file.huf'------------------------------------------------------------------------
void CreateFileName (char *oldname)
{
	int i,j,h=0;
	for(i=strlen(oldname)-1;i>=0;i--)
		if(oldname[i]=='.')
		{
			j=i;
			break;
		}
		j++;
		oldname[j++]='h';
		oldname[j++]='u';
		oldname[j++]='f';
		oldname[j]='\0';
}
//------------ket noii tap tin vao duong dan---------------
void CreateFileDirectory (char*file, char* directory)
{
	int size=strlen(directory);
	directory[size]='\\';
	directory[size+1]=NULL;
	strcat(directory,file);

}
//------------------tim ra ten tap tin trong duong dan-----------
void FileNameFromPath(char *Path)
{
	int i,j,h=0;
	j=-1;
	for(i=strlen(Path)-1;i>=0;i--)
		if(Path[i]=='\\')
		{
			j=i;
			break;
		}
		char FileName[255];
		if(j>=0)
		{
			j++;
			for(j;j<(int)strlen(Path);j++)
				FileName[h++]=Path[j];
			FileName[h]='\0';
			strcpy(Path,FileName);
		} 
}
//-------------------------------------Kiem tra thu muc------------------------------
int IsFolder(char *Folder, char Files[20][255])
{
	WIN32_FIND_DATA FindFileData;
	HANDLE hFind = INVALID_HANDLE_VALUE;
	char DirSpec[MAX_PATH]; // directory specification
	int h=0;

	strncpy (DirSpec, Folder, strlen(Folder)+1);
	strncat (DirSpec, "\\*", 3);
	hFind = FindFirstFile(DirSpec, &FindFileData);
	
	if (hFind == INVALID_HANDLE_VALUE)
		return (0);
	else	
		while (1)
			if(FindNextFile(hFind, &FindFileData)!=0)
			{
				if(strcmp(FindFileData.cFileName,"..")!=0)
				{
					strcpy(Files[h],Folder);
					strcat(Files[h],"\\");
					strcat(Files[h],FindFileData.cFileName);
					//strcpy(Files[h],FindFileData.cFileName);
					h++;
					
				}
			}
			else
				break;
		
	return h;
}
//-------------------lay cac ten tap tin tu tham so dong lenh----------------------
int GetFileName(char *Arg, char filename[100][255])
{
	int chiso,length;
	chiso=length=0;
	for(int i=0;i<=strlen(Arg);i++)
	{
		if(Arg[i]!=',')
			filename[chiso][length++]=Arg[i];
		else
		{
			filename[chiso][length]='\0';
			chiso++;
			length=0;
		}
	}
	return (chiso+1);
}
int IsFileDecoding(char *file, char filename[100][255],int soluong_file)
{
	int flag=0;
	for(int i=0;i<soluong_file;i++)
		if(strcmp(file,filename[i])==0)
		{
			flag++;
			break;
		}
	return flag;
}