////////////////////////////////////////////////////////////////////////////
////////                                                            ////////
////////                  利用哈希表完成LZW壓縮與解壓               ////////
////////                                               by 施瑋喆    ////////
////////                                               5060309818   ////////
////////                                               2007--11-5   ////////
////////                                                            ////////
////////////////////////////////////////////////////////////////////////////


#include<iostream.h>
#include<stdio.h> 
#include<stdlib.h> 
#include<malloc.h> 
#include<string.h> 
#include<math.h> 
#include"hash.h"



int mark=0;
int status=0;
int LeftOver;



void Output(unsigned long pcode,FILE* file,int& out)
{
   unsigned char a,b;
   if(mark)                                      //有上次剩余的4位
   {
	   b=pcode & 255;
	   a=(LeftOver << 4) | (pcode >> 8);
	   fprintf(file,"%c",a);
	   fprintf(file,"%c",b);
	   out=out+2;
	   mark=0;
   }
   else                                         //沒有剩余
   {
	   LeftOver=pcode & 15; 
	   a=pcode >> 4;
	   fprintf(file,"%c",a);
	   out++;
	   mark=1;
   }
}



bool Getcode(int& code,FILE* file)
{                                           
	char a,b;
	int c,d;
	a=fgetc(file);
	if(feof(file)) return false; 
	if(status)
	{
		c=a & 255;
		code=(LeftOver << 8) | c;
	}
	else 
	{
		b=fgetc(file);
		c=a & 255;
		d=b & 255;
		code=(c << 4) | (d >> 4);
		LeftOver=d & 15;
	}
	status=1-status;
	return true;
}



void Print(int code,int& n,unsigned char s[4096],element ht[4096],FILE* file)
{
   n=-1;
   while(code>=256)
   {
	   s[++n]=ht[code].suffix;
	   code=ht[code].prefix;
   }
   s[++n]=code;
   for(int i=n;i>=0;i--)
	   fprintf(file,"%c",s[i]);
}



void Compress(char fori[30],char fcom[30])       //LZW壓縮器
{
   FILE* forigin=fopen(fori,"rb");
   FILE* fcompress=fopen(fcom,"wb");

   hashnode* P=new hashnode[D];                    //定義并初始化代碼字典
   hashnode* T;
   for(int i=0;i<D;i++) P[i].link=NULL;
   part e;
   char ch;
   int temp,in=1,out=0;
   int s;
   
   for(i=0;i<256;i++)
   {
	   e.key=i;
	   e.code=i;
	   insert(P,e);
   }
   int used=256;                                 //記錄當前code用到的數

   ch=fgetc(forigin);                            //輸入文件中的第一個字符
   unsigned long pcode=ch; 
   if (!feof(forigin))
   {
	   do{
		   ch=fgetc(forigin);
		   in++;
		   if(feof(forigin)) 
			   break; 
		   s=ch & 255;
		   unsigned long k=(pcode << 8) | s;
		   if(search(P,k,temp))
			   pcode=temp;
		   else
		   {
			   Output(pcode,fcompress,out);
			   if(used>=4096)                              //刷新字典
			   {
				   T=P;
				   delete T;
				   P=new hashnode[D];
				   for(int i=0;i<D;i++) P[i].link=NULL;
				   for(i=0;i<256;i++)
				   {
					   e.key=i;
					   e.code=i;
					   insert(P,e);
				   }
				   used=256;         
			   }
			   e.code=used++;
			   s=ch & 255;
			   e.key=(pcode << 8) | s;
			   insert(P,e);
			   pcode=ch;
		   }
	   }while(1);
	   Output(pcode,fcompress,out);
	   if(mark)
	   {
		   ch=LeftOver << 4;
		   fprintf(fcompress,"%c",ch);
		   out++;
	   }
   }
   fclose(forigin);
   fclose(fcompress);
   cout<<"壓縮成功,壓縮比為："<<out*100/in<<"%\n";
}


void Decompress(char fcom[30],char fori[30])     //LZW解壓器
{
	FILE* fcompress=fopen(fcom,"rb");
	FILE* forigin=fopen(fori,"wb");
	
	int n=0;
	int used = 256;                              // 迄今所使用的代碼
	int pcode,ccode;                             // 前一代碼與當前代碼
	element ht[4096];
	unsigned char s[4096];
	
	if(Getcode(pcode,fcompress))
	{
		s[0]=pcode;  
		fprintf(forigin,"%c",s[0]);
		
		while(Getcode(ccode,fcompress))
		{
			if(ccode<used)                    // ccode已在字典中
			{
				Print(ccode,n,s,ht,forigin);
				if(used>=4096) used=256;
				
				ht[used].prefix=pcode;
				ht[used++].suffix=s[n];
				
			}                                    
			else
			{
				ht[used].prefix=pcode;
				ht[used++].suffix=s[n];
				Print(ccode,n,s,ht,forigin);
			}
			pcode=ccode;
		}
	}
	fclose(fcompress);
	fclose(forigin);
	cout<<"解壓成功\n";
}



int main() 
{ 
    cout<<"//////////////////////////////////////////////////////////////"<<endl;
    cout<<"////                                                      ////"<<endl;
    cout<<"////      利用哈希表完成LZW壓縮與解壓                     ////"<<endl;
    cout<<"////                                   姓名： 施瑋喆      ////"<<endl;
    cout<<"////                                   學號： 5060309818  ////"<<endl;
    cout<<"////                                   班級： F0603031    ////"<<endl;
    cout<<"////                               完成時間： 2007-11-5   ////"<<endl;
    cout<<"////                                                      ////"<<endl;
    cout<<"//////////////////////////////////////////////////////////////"<<endl<<endl;

	char choice,fori[30],fcom[30];

	while(1)
	{
		cout<<"****************************************************************\n";
		cout<<" 1   --   Compress\n";
		cout<<" 2   --   Decompress\n";
		cout<<" 3   --   Quit\n";
		cout<<"****************************************************************\n";
		cout<<" what to do : ";
		cin>>choice;
		switch(choice){
		case '1':
			{
				cout<<"請輸入要壓縮的文件名: "; 
				cin>>fori; 
				cout<<"請輸入壓縮后的保存文件名: "; 
				cin>>fcom; 
				Compress(fori,fcom);
			}
			break;
		case '2':
			{
				cout<<"請輸入要解壓縮的文件名: "; 
				cin>>fcom; 
				cout<<"請輸入解壓縮后的保存文件名: "; 
				cin>>fori; 
				Decompress(fcom,fori);
			}
			break;
		case '3':
			return 0;
		default:
			cout<<"Wrong input!";
		}
	}

	return 0;
}