#include <gmp.h>
#include <cmath>
#include <ctime>
#include <string>
#include <fstream>
#include <iomanip>
#include <iostream>
using namespace std;

#define Tc 1		// 1 2 3
#define Td 30		// 30 20 10
#define ColorNum 256
#define ColorDepth 3
#define max_size 1024
#define SecLength 1000000

char SecretFileName[25] = "aaa";

unsigned int ClusterNum;
unsigned int TotalEmbeddedBits;
unsigned int im_height, im_width;
unsigned int PaletteNum, indexsize, DuPosiLen;

double 		luminance[ColorNum];
double 		sortstack[ColorNum];
double		ColorDifference[ColorNum][ColorNum];
unsigned int	SecMap[5]={0,1,0,1,0};
unsigned int  	EmCode[SecLength];						//用來存放Secret data的bits
unsigned int	ColorClSi[ColorNum];
unsigned int  	ClusterSize[ColorNum];					//用來記錄每一個cluster的大小(size)
unsigned int	ExtractData[SecLength];
unsigned int	DuPosition[max_size*max_size];
unsigned int  	IndexImage[max_size*max_size];					//Image的block指標
unsigned int 	Palette[ColorNum][ColorDepth];
unsigned int  	ClusterIndex[ColorNum][ColorNum];		//紀錄每個Cluster中有哪些codebook中codeword的指標
unsigned char 	InImage[max_size][max_size][ColorDepth];
unsigned char 	OutImage[max_size][max_size][ColorDepth];

double RMSE();
double PSNR(double);
int main(int, char* []);
int Product_Palette();
void decode();
void contrast();
void Embedding();
void SortPalette();
void PaletteIndex();
void Du_Method(mpz_t);
void ReadBMP(char []);							//讀出影像檔
void ProductCluster();
void WriteBMP(char []);							//寫入影像檔
void ReadSigningCode();					//讀檔:Secret Data
void PaletteChange(int);
void ExtrPaletteIndex();
void InputErrorPrintf();
void ReadCluster(char []);
void ComputeDiffOfColors();
void Quicksort(const int ,const int);

//====================================================================================
void Du_Method(mpz_t ComDat)
{		
	int pi, pb, ptr, i, j, k, l;
	int record[indexsize][2];		
	unsigned long int  numexProd;	
	
	mpz_t CMDT, exProd, reamt;	
	mpz_init(CMDT);
	mpz_init(exProd);
	mpz_init(reamt);
	mpz_set(CMDT, ComDat);	

	mpz_set_ui(exProd,(unsigned long int)0);
	numexProd = 0;
	
	//計算要用幾個indeics作排列組合	
	while(mpz_cmp(CMDT,exProd)>0){		
		//**看IndexImage[i][j]屬於那一個cluster			
		for(i=0;i<ClusterNum;i++){
			for(j=0;j<ClusterSize[i];j++){				
				if(IndexImage[DuPosition[numexProd]] == ClusterIndex[i][j]){
					pi = i;	//哪一群
					pb = j;	//那一群中的第幾個					
				}
			}
		}
		record[numexProd][0]=pi;
		record[numexProd][1]=pb;		
				
		if(ClusterSize[pi]==1){
			mpz_mul_ui(exProd,exProd,(unsigned long int)1);	
			cout<<"Du_method error!"<<endl;
			exit(1);
		}
		else{
			if(mpz_cmp_ui(exProd,(unsigned long int)0) == 0)
				mpz_set_ui(exProd,(unsigned long int)(ClusterSize[pi]));
			else							
				mpz_mul_ui(exProd,exProd,(unsigned long int)(ClusterSize[pi]));	
		}
				
		numexProd++;
		if(numexProd>DuPosiLen){
			cout<<"Du::Out of indexsize."<<endl;
			exit(1);
		}		
	}//end of while(ComDat>exProd)
			
	bool ISZERO = true;
	for(i=numexProd-1;i>=0;i--){		//反過來做:D
		if(ClusterSize[pi]!=1){				
			mpz_mod_ui(reamt, CMDT, (unsigned long int)ClusterSize[record[i][0]]);
			ptr = mpz_get_ui(reamt);				
			mpz_cdiv_q_ui(CMDT, CMDT, (unsigned long int)ClusterSize[record[i][0]]);			
				
			if(ISZERO)	//表示陣列編號順序為1,2,...(ClusterSize[i]-1)-1,0;  其中(ClusterSize[i]-1)為去掉breakpoint後的size
			{								
				if(ptr==0)		//當餘數為0時,其index為cluster的最後一個非breakpoint的codeword						
					IndexImage[DuPosition[i]]=ClusterIndex[record[i][0]][ClusterSize[record[i][0]]-1];					
				else{		//ptr!=0
					ISZERO = false;						
					IndexImage[DuPosition[i]] = ClusterIndex[record[i][0]][ptr-1];					
				}				
			}
			else		//表示陣列編號順序為0,1,...(ClusterSize[i]-1)-1;									
				IndexImage[DuPosition[i]] = ClusterIndex[record[i][0]][ptr];					
		}
	}
}
//====================================================================================

//====================================================================================
void Embedding()
{
	cout<<"Embedding Program"<<endl;
	
	int i, j, k, l, p, pi, pj, ccc;
	int DistinctColor, DuLen, NowSec, numNeighbor;
	int numEmbeddedOneBit, numDuPosition, numEmbeddable, numNonEmbeddable, numNotEmbeddedOneBit;
	int neighbor[4];		
	double MinDiff, MaxD, sum, CandMaxD;
	mpz_t Prod, SDec;
	
	mpz_init(SDec);
	mpz_init(Prod);
	mpz_set_ui(SDec, (unsigned long int)1);
	DuPosiLen = 0;
	
	numDuPosition = 0;
	numEmbeddable = 0;
	numNonEmbeddable = 0;
	numEmbeddedOneBit = 0;
	numNotEmbeddedOneBit = 0;
	
	TotalEmbeddedBits = 0;
	
	for(i=0; i<im_height; i++){
		for(j=0; j<im_width; j++){
			
			numNeighbor = 0;
			MaxD = 0;
			cout<<"("<<i<<","<<j<<")"<<" ";
						
			//計算Maximum color difference between (i,j) and (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1)
			if((i-1)>0 && (j-1)>0){			//For (i-1, j-1)				
				if(ColorDifference[ IndexImage[i*im_width+j] ][ IndexImage[(i-1)*im_width+(j-1)] ]>MaxD)
					MaxD = ColorDifference[ IndexImage[i*im_width+j] ][ IndexImage[(i-1)*im_width+(j-1)] ];
				sortstack[numNeighbor] = IndexImage[(i-1)*im_width + (j-1)];	
				numNeighbor++;		
			}
			if((i-1)>0){					//For (i-1, j)
				if(ColorDifference[ IndexImage[i*im_width+j] ][ IndexImage[(i-1)*im_width+j] ]>MaxD)
					MaxD = ColorDifference[ IndexImage[i*im_width+j] ][ IndexImage[(i-1)*im_width+j] ];
				sortstack[numNeighbor] = IndexImage[(i-1)*im_width + j];
				numNeighbor++;
			}
			if((i-1)>0 && (j+1)<im_width){	//For (i-1, j+1)
				if(ColorDifference[ IndexImage[i*im_width+j] ][ IndexImage[(i-1)*im_width+(j+1)] ]>MaxD)
					MaxD = ColorDifference[ IndexImage[i*im_width+j] ][ IndexImage[(i-1)*im_width+(j+1)] ];
				sortstack[numNeighbor] = IndexImage[(i-1)*im_width+(j+1)];	
				numNeighbor++;			
			}
			if((j-1)>0){					//For (i, j-1)
				if(ColorDifference[ IndexImage[i*im_width+j] ][ IndexImage[i*im_width+(j-1)] ]>MaxD)
					MaxD = ColorDifference[ IndexImage[i*im_width+j] ][ IndexImage[i*im_width+(j-1)] ];
				sortstack[numNeighbor] = IndexImage[i*im_width+(j-1)];
				numNeighbor++;
			}
						
			if(numNeighbor!=0){
				Quicksort(0,(numNeighbor-1));
				DistinctColor = 1;
				for(k=1; k<numNeighbor; k++){
					if(sortstack[k]!=sortstack[k-1])
						DistinctColor++;
				}
			}
			else		
				DistinctColor = 0;
					
			//cout<<" "<<DistinctColor<<"/"<<numNeighbor<<" "<<MaxD<<" ";
			
			if(DistinctColor>=Tc && MaxD<=Td){			
								
				numEmbeddable++;
				
				if(ColorClSi[IndexImage[i*im_width+j]]==1){
					if(numNeighbor!=4){
						for(k=numNeighbor; k<4; k++)
							sortstack[k] = 0;						
						Quicksort(0, 3);									
					}
					if(IndexImage[i*im_width+j]>=sortstack[3])
						NowSec = SecMap[0];
					else if(sortstack[3]>IndexImage[i*im_width+j] && IndexImage[i*im_width+j]>=sortstack[2])
						NowSec = SecMap[1];
					else if(sortstack[2]>IndexImage[i*im_width+j] && IndexImage[i*im_width+j]>=sortstack[1])
						NowSec = SecMap[2];
					else if(sortstack[1]>IndexImage[i*im_width+j] && IndexImage[i*im_width+j]>=sortstack[0])
						NowSec = SecMap[3];
					else
						NowSec = SecMap[4];
					//cout<<IndexImage[i*im_width+j]<<"/"<<NowSec<<" ";
					if( NowSec != EmCode[TotalEmbeddedBits%SecLength]){  //not okay 只要算與EmCode相同的
						MinDiff = 999999;
						for(k=0; k<PaletteNum; k++){
							if(ColorClSi[k]==1){	//只考慮ClusterSize為1的
								
								if(k>=sortstack[3])
									l = SecMap[0];
								else if(sortstack[3]>k && k>=sortstack[2])
									l = SecMap[1];
								else if(sortstack[2]>k && k>=sortstack[1])
									l = SecMap[2];
								else if(sortstack[1]>k && k>=sortstack[0])
									l = SecMap[3];
								else
									l = SecMap[4];
								
								if(l == EmCode[TotalEmbeddedBits%SecLength]){
									//計算Maximum color difference between (i,j) and (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1)
									CandMaxD = 0;
									if((i-1)>0 && (j-1)>0){		//For (i-1, j-1)
										if(ColorDifference[ k ][ IndexImage[(i-1)*im_width+(j-1)] ]>CandMaxD)
											CandMaxD = ColorDifference[ k ][ IndexImage[(i-1)*im_width+(j-1)] ];						
									}
									if((i-1)>0){					//For (i-1, j)
										if(ColorDifference[ k ][ IndexImage[(i-1)*im_width+j] ]>CandMaxD)
											CandMaxD = ColorDifference[ k ][ IndexImage[(i-1)*im_width+j] ];									
									}
									if((i-1)>0 && (j+1)<im_width){	//For (i-1, j+1)
										if(ColorDifference[ k ][ IndexImage[(i-1)*im_width+(j+1)] ]>CandMaxD)
											CandMaxD = ColorDifference[ k ][ IndexImage[(i-1)*im_width+(j+1)] ];												
									}
									if((j-1)>0){					//For (i, j-1)
										if(ColorDifference[ k ][ IndexImage[i*im_width+(j-1)] ]>CandMaxD)
											CandMaxD = ColorDifference[ k ][ IndexImage[i*im_width+(j-1)] ];								
									}
									if(CandMaxD<MinDiff){
										MinDiff = CandMaxD;
										p = k;
									}
								}
								
							}
						}
						if(MinDiff<=Td){							
							cout<<"Embedding 1 bits! changed"<<TotalEmbeddedBits<<endl;
							IndexImage[i*im_width+j] = p;
							numEmbeddedOneBit++;
							TotalEmbeddedBits++;
						}
						else{
							numNotEmbeddedOneBit++;
							cout<<"Not Embedding Data! Since replace color isn't satisfied!"<<endl;
						}
					}
					else{						
						cout<<"Embedding 1 bits!  nonchanged"<<TotalEmbeddedBits<<endl;
						numEmbeddedOneBit++;
						TotalEmbeddedBits++;
					}																
				}
				else{
					//要檢驗看Cluster中的所有color是否都符合embeddable的條件
					for(k=0; k<ClusterNum; k++){						
						for(l=0; l<ClusterSize[k]; l++){
							if(IndexImage[i*im_width+j] == ClusterIndex[k][l]){
								pi = k;
								pj = l;								
							}
						}
					}
					CandMaxD = 0;
					for(k=0; k<ColorClSi[IndexImage[i*im_width+j]]; k++){						
						if((i-1)>0 && (j-1)>0){		//For (i-1, j-1)
							if(ColorDifference[ ClusterIndex[pi][k] ][ IndexImage[(i-1)*im_width+(j-1)] ]>CandMaxD)
								CandMaxD = ColorDifference[ ClusterIndex[pi][k] ][ IndexImage[(i-1)*im_width+(j-1)] ];						
						}
						if((i-1)>0){					//For (i-1, j)
							if(ColorDifference[ ClusterIndex[pi][k] ][ IndexImage[(i-1)*im_width+j] ]>CandMaxD)
								CandMaxD = ColorDifference[ ClusterIndex[pi][k] ][ IndexImage[(i-1)*im_width+j] ];									
						}
						if((i-1)>0 && (j+1)<im_width){	//For (i-1, j+1)
							if(ColorDifference[ ClusterIndex[pi][k] ][ IndexImage[(i-1)*im_width+(j+1)] ]>CandMaxD)
								CandMaxD = ColorDifference[ ClusterIndex[pi][k] ][ IndexImage[(i-1)*im_width+(j+1)] ];												
						}
						if((j-1)>0){					//For (i, j-1)
							if(ColorDifference[ ClusterIndex[pi][k] ][ IndexImage[i*im_width+(j-1)] ]>CandMaxD)
								CandMaxD = ColorDifference[ ClusterIndex[pi][k] ][ IndexImage[i*im_width+(j-1)] ];								
						}						
					}
					if(CandMaxD>=Td){
						cout<<"Not Embedding Data in Du Position! Since had a replace color isn't embeddable!"<<endl;
					}
					else{
						cout<<"Using Du's method!"<<endl;					
						mpz_mul_ui(SDec, SDec, (unsigned long int)ColorClSi[IndexImage[i*im_width+j]]);					
						DuPosition[DuPosiLen] = i*im_width+j;
						numDuPosition++;
						DuPosiLen++;
					}													
				}
			}
			else{
				numNonEmbeddable++;
				cout<<"Not Embedding Data!"<<endl;
			}					
		}	
	}
	cout<<SDec<<endl;
	DuLen = 0;
	mpz_set_ui(Prod, (unsigned long)1);	
	while(mpz_cmp(SDec, Prod)>0)
	{			
		mpz_ui_pow_ui(Prod, (unsigned long int)2, (unsigned long int)DuLen);
		DuLen++;
	}
	DuLen = DuLen-2;	
	
	//算出要藏入的Secret data(10)
	mpz_set_ui(SDec, (unsigned long)0);
	for(i=0; i<DuLen; i++){
		if(EmCode[(TotalEmbeddedBits+i)%SecLength]==0)
			mpz_mul_ui(SDec, SDec, (unsigned long)2);	//SDec = SDec*2;		
		else{
			mpz_mul_ui(SDec, SDec, (unsigned long)2);	//SDec = SDec*2;
			mpz_add_ui(SDec, SDec, (unsigned long)1);	//SDec = SDec+1;
		}
	}	
	cout<<"SDec : "<<SDec<<endl;	
	
	Du_Method(SDec);
	
	cout<<"indexsize: "<<indexsize<<endl;
	cout<<"numNonEmbeddable: "<<numNonEmbeddable<<endl;
	cout<<"numEmbeddable: "<<numEmbeddable<<endl;
	cout<<"numEmbeddedOneBit: "<<numEmbeddedOneBit<<" :: numNotEmbeddedOneBit: "<<numNotEmbeddedOneBit<<" :: numDuPosition: "<<numDuPosition<<" ("<<numDuPosition+numEmbeddedOneBit+numNotEmbeddedOneBit<<")"<<endl;
	
	cout<<"TotalEmbeddedBits:"<<TotalEmbeddedBits+DuLen<<endl;
	
	//用Du來藏資訊
	
	
}
//====================================================================================

//====================================================================================
void contrast()
{
}
//====================================================================================

//====================================================================================
void decode()
{
	
}
//====================================================================================

//====================================================================================
void Quicksort(const int left,const int right)
{
	int i, j;
	double pivot,temp;
	
	if(left<right)
	{
		i=left;
		j=right+1;
		pivot=sortstack[left];
		do{
    		do{
				i++;			
			}while(sortstack[i]<pivot);
			do{
				j--;
			}while(sortstack[j]>pivot);
			if(i<j)
			{
				temp=sortstack[i];
				sortstack[i]=sortstack[j];
				sortstack[j]=temp;
			}
		}while(i<j);
    	temp=sortstack[left];		
		sortstack[left]=sortstack[j];
		sortstack[j]=temp;		
	    
		Quicksort(left,j-1);
    	Quicksort(j+1,right);
	}
}
//====================================================================================

//====================================================================================
void PaletteChange(int p)			//using for SortPalette()
{
	int i;
	int ColorTemp[ColorDepth];
	
	for(i; i<ColorDepth; i++)
		ColorTemp[i]=Palette[p][i];
	for(i; i<ColorDepth; i++)
		Palette[p][i]=Palette[p][p+1];
	for(i; i<ColorDepth; i++)
		Palette[p+1][i]=ColorTemp[i];
}
//====================================================================================

//====================================================================================
void SortPalette()
{
	cout<<"SortPalette"<<endl;
	int i, j, k, l;
	int appear = 0;
	int Reco[ColorNum];
	int Temp[ColorNum][ColorDepth];
	
	for(i=0; i<PaletteNum; i++){
		for(j=0; j<ColorDepth; j++){
			Temp[i][0] = Palette[i][0];
		    Temp[i][1] = Palette[i][1];
		    Temp[i][2] = Palette[i][2];
		}
	}
	
	for(i=0; i<PaletteNum; i++){
		luminance[i] = 0.3*Palette[i][0]+0.59*Palette[i][1]+0.11*Palette[i][2];
		sortstack[i] = 0.3*Palette[i][0]+0.59*Palette[i][1]+0.11*Palette[i][2];		
	}
	
	Quicksort(0, (PaletteNum-1));
	
	l = 0;
	for(i=0; i<=PaletteNum; i++){	
		for(j=0; j<PaletteNum; j++){			
			if(sortstack[(PaletteNum-1)-i]==luminance[j]){
				appear = 0;
				for(k=0; k<l; k++){
					if(Reco[k]==j)
						appear = 1;
				}
				if(appear==0){
					for(k=0; k<ColorDepth; k++)
						Palette[i][k] = Temp[j][k];
					Reco[l] = j;
					l++;
					break;
				}
			}
		}		
	}
	
	for(i=0; i<PaletteNum; i++)
		luminance[i] = sortstack[(PaletteNum-1)-i];
	
	for(i=0; i<(PaletteNum-1); i++){		
		if(luminance[i]==luminance[i+1]){
			if(Palette[i][0]<Palette[i+1][0]){
				PaletteChange(i);
			}
			else if(Palette[i][0]==Palette[i+1][0]){
				if(Palette[i][1]<Palette[i+1][1]){
					PaletteChange(i);
				}
				else if(Palette[i][1]==Palette[i+1][1]){
					if(Palette[i][2]<Palette[i+1][2])
						PaletteChange(i);
				}
			}
		}
	}		
}
//====================================================================================

//====================================================================================
void PaletteIndex()							//將影像轉成Palette Index
{
	int i, j, k;		
	int CountOfIndex;	
	
	CountOfIndex=0;
	
	for(i=0; i<im_height; i++){
		for(j=0; j<im_width; j++){
			for(k=0;k<PaletteNum;k++){
				if((InImage[i][j][0]==Palette[k][0]) && (InImage[i][j][1]==Palette[k][1]) && (InImage[i][j][2]==Palette[k][2])){					
					IndexImage[CountOfIndex]=k;
					CountOfIndex++;
				}
			}
		}
	}	
	if(CountOfIndex != indexsize){
		cout<<"Error!!Size isn't same!! - VQIndex\n";
		exit(1);
	}	
}
//====================================================================================

//====================================================================================
void ComputeDiffOfColors()
{
	cout<<"ComputeDiffOfColors"<<endl;
	int i, j, k;
	double sum;
		
	//建立Palette中每個Color間的Difference
	for(i=0; i<PaletteNum; i++){
		for(j=0; j<PaletteNum; j++){
			sum = 0.0;
			for(k=0; k<ColorDepth; k++)
				sum += (Palette[i][k]-Palette[j][k])*(Palette[i][k]-Palette[j][k]);
			ColorDifference[i][j]=sqrt(sum);
		}
	}
}
//====================================================================================

//====================================================================================
void ExtrPaletteIndex()
{
	int i,j,k,l;
	//針對 OutImage
	k = 0;
	for(i=0; i<im_height; i++){
		for(j=0; j<im_width; j++){			
			for(l=0; l<ColorDepth; l++){				
				OutImage[i][j][l] = Palette[IndexImage[k]][l];				
			}
			k++;
		}
	}	
}
//====================================================================================

//====================================================================================
int Product_Palette()
{
	int i, j, k, pn, reseen;
	pn = 0;
	for(i=0;i<im_height;i++){
		for(j=0;j<im_width;j++){
			reseen = 0;
			for(k=0; k<pn; k++){							
				if((Palette[k][0]==InImage[i][j][0]) && (Palette[k][1]==InImage[i][j][1]) && (Palette[k][2]==InImage[i][j][2]))
					reseen = 1;
		    }
		    if(reseen == 0){
		    	Palette[pn][0] = InImage[i][j][0];
		    	Palette[pn][1] = InImage[i][j][1];
		    	Palette[pn][2] = InImage[i][j][2];
		    	pn++;
		    }		    
		}
	}		
	
	return pn;
}
//====================================================================================

//====================================================================================
void ProductCluster()			//讀進Cluster(分群結果)--這裡使用 C 的讀檔方法
{
	cout<<"ProductCluster"<<endl;
	int i,j,k,p,ppp, pi, pj;
	int DCP, timecl, appear, tempclustersize;
	int tempci[ColorNum];
	int IndexCount[ColorNum];
	double Tv = 15;
	double MinDiff, MaxDiff;				
	
	//Init.
	for(i=0;i<PaletteNum;i++){
		IndexCount[i] = 0;
		sortstack[i] = 0;
		ClusterSize[i] = 1;
		ClusterIndex[i][0] = i;
	}
	tempclustersize = PaletteNum;
	
	DCP = PaletteNum-ClusterNum;		
	
	//計算Index出現次數
	for(i=0;i<im_height;i++){
		for(j=0;j<im_width;j++){
			IndexCount[IndexImage[i*im_width+j]]++;
			sortstack[IndexImage[i*im_width+j]]++;
		}
	}
	
	//for(i=0;i<PaletteNum; i++)
	//	cout<<IndexCount[i]<<" ";
	//cout<<endl;
	
	Quicksort(0, (PaletteNum-1));
	
	timecl = 0;
	ppp = 0;
	while(tempclustersize>ClusterNum && timecl<PaletteNum){
		
		cout<<tempclustersize<<"::"<<ClusterNum<<"  "<<timecl<<endl;
		
		//依據大小(由大到小)找出出現最多次的Index
		for(i=0; i<tempclustersize; i++){
			for(j=0;j<ClusterSize[i];j++){
				appear = 0;
				for(k=0; k<timecl; k++){
					if(ClusterIndex[i][j]==tempci[k]){
						appear = 1;
						break;
					}
				}
				if(appear == 0){		//尚未放入tempci[]中
					if(sortstack[(PaletteNum-1)-ppp] == IndexCount[ClusterIndex[i][j]]){
						tempci[timecl]=ClusterIndex[i][j];
						pi = i;
						pj = j;
						timecl ++ ;
						break;
					}
				}
			}
		}
		
		//找不在本身Cluster中的最相近的color放入cluster當中
		MinDiff = 999999;
		for(i=0; i<tempclustersize; i++){
			if(i!=pi){
				MaxDiff = 0;
				for(k=0; k<ClusterSize[pi]; k++){
					for(j=0;j<ClusterSize[i];j++){						
						if(ColorDifference[ClusterIndex[pi][k]][ClusterIndex[i][j]]>MaxDiff)
							MaxDiff = ColorDifference[ClusterIndex[pi][k]][ClusterIndex[i][j]];
					}
				}
				if(MaxDiff<MinDiff){
					MinDiff = MaxDiff;
					p=i;
				}
			}
		}
		
		if(MinDiff<=Tv){		//合併 pi和p 這兩個Cluster
			for(i=0; i<ClusterSize[p]; i++){
				ClusterIndex[pi][ClusterSize[pi]] = ClusterIndex[p][i];
				ClusterSize[pi]++;
			}
			for(i=p; i<(tempclustersize-1); i++){
				ClusterSize[i] = ClusterSize[i+1];
				for(j=0; j<ClusterSize[i+1]; j++){
					ClusterIndex[i][j]=ClusterIndex[i+1][j];
				}
			}
			
			tempclustersize--;			
		}
		ppp++;						
	}
	
	//==Show Information
	cout<<"Number of Cluster is "<<ClusterNum<<endl;
	cout<<"Every Cluster Size is:"<<endl;
	for(i=0;i<ClusterNum;i++)
		cout<<ClusterSize[i]<<" ";	
	cout<<endl;
	
	for(i=0;i<ClusterNum;i++){
		for(j=0;j<ClusterSize[i];j++){
			cout<<ClusterIndex[i][j]<<" ";
		}
		cout<<" ; ";
	}
	cout<<endl;
	
}
//====================================================================================

//====================================================================================
void ReadCluster(char rCF[25])			//讀進Cluster(分群結果)--這裡使用 C 的讀檔方法
{
	FILE *rCC;
	int i,j,k;	
	int tempci[ColorNum];
	
	if ((rCC=fopen(rCF,"rb"))==NULL){
		printf("Unable to open Cluster File.\n");
    	exit(1);
	}	
	fread(&ClusterNum,sizeof(unsigned int),1,rCC);
	fread(ClusterSize,sizeof(unsigned int),ClusterNum,rCC);
	fread(tempci,sizeof(unsigned int),PaletteNum,rCC);
   
	fclose(rCC);	
		
	k=0;
	for(i=0;i<ClusterNum;i++){
		for(j=0;j<ClusterSize[i];j++){
			ClusterIndex[i][j]=tempci[k];
			k++;
		}
	}
	
	//==Show Information
	cout<<"Number of Cluster is "<<ClusterNum<<endl;
	cout<<"Every Cluster Size is:"<<endl;
	for(i=0;i<ClusterNum;i++)
		cout<<ClusterSize[i]<<" ";   	   	
   	cout<<endl;
   	/*
   	for(i=0;i<ClusterNum;i++){
		for(j=0;j<ClusterSize[i];j++)
			cout<<setw(3)<<ClusterIndex[i][j];
		cout<<endl;
	}
	cout<<endl;
	*/
}
//====================================================================================

//====================================================================================
void ReadSigningCode(char incb[25])		//讀Secret Data File
{
	char ch;		
	ifstream infile(incb,ios::binary);
	for(int i=0;i<SecLength;i++)
	{
		infile.get(ch);
		if (infile.eof())
			break;	
		else{
			if(ch=='1')	EmCode[i]=1;				
			else if(ch=='0') EmCode[i]=0;
		}
	}
	
	infile.close();
}
//====================================================================================

//====================================================================================
void ReadBMP(char inputname[25])	//讀影像檔(.Raw)
{
	int i, j, k;
	char ch;		
	ifstream infile(inputname,ios::binary);
	for(i=0;i<im_height;i++){
		for(j=0;j<im_width;j++){
			for(k=0; k<ColorDepth; k++){
				infile.get(ch);				
				if (infile.eof())
					break;	
				else
					InImage[i][j][k] = ch;	
			}
		}
	}
	infile.close();	
}
//====================================================================================

//====================================================================================
void WriteBMP(char outputname[40])	//寫影像檔(.Raw)
{	
	int i, j, k;
	ofstream outfile(outputname,ios::binary);
    for(i=0;i<im_height;i++){
		for(j=0;j<im_width;j++){		
			for(k=0; k<ColorDepth; k++)
		    	outfile<<(unsigned char)OutImage[i][j][k];		
		}
	}
	outfile.close();		
}
//====================================================================================

//====================================================================================
double RMSE()							//計算Mean Square Error
{
	double _mse = 0;	
	for(int i=0;i<im_height;i++){
		for(int j=0;j<im_width;j++){
			for(int k=0;k<ColorDepth;k++)
				_mse += (InImage[i][j][k]-OutImage[i][j][k])*(InImage[i][j][k]-OutImage[i][j][k]);
		}
	}	
	_mse = sqrt(_mse/(im_height*im_width));		
	return _mse;
}
//====================================================================================

//====================================================================================
double PSNR(double _pm)					//計算PSNR
{	
	double _psnr;		
	_psnr = 10*log10(255*255/_pm);	
	return _psnr;
}
//====================================================================================

//====================================================================================
void InputErrorPrintf()
{
	//		  0		  1			2		  3		  4	      5       6			//
	cout<<"$HCDHPI [OPTION1] [OPTION2] [Item1] [Item2] [Item3] [Item4]"<<endl;
	cout<<" D <Decoder Option>"<<endl;
	cout<<"	C <Using Clostest pair method>"<<endl;
	cout<<"		$HCDHPI D C [Stego-Image File] [Image Height] [Image Width] [Clustering File]"<<endl;
	cout<<"	G <Using GA Glustering method>"<<endl;
	cout<<"		$HCDHPI D G [Stego-Image File] [Image Height] [Image Width] [Clustering File]"<<endl;	
	cout<<endl;
	cout<<" H <Data Hiding Option>"<<endl;
	cout<<"	C <Using Clostest pair method>"<<endl;
	cout<<"		$HCDHPI D C [Stego-Image File] [Image Height] [Image Width] [Clustering File]"<<endl;
	cout<<"	G <Using GA Glustering method>"<<endl;
	cout<<"		$HCDHPI D G [Stego-Image File] [Image Height] [Image Width] [Clustering File]"<<endl;
	exit(1);
}
//====================================================================================

//====================================================================================
int main(int argc, char* argv[])
{
	int i, j, k;
	double ms, ps;
	char OutImageName[40]="Cover_";		
	
	if(argc!=7 || (argv[1][0]!='D' && argv[1][0]!='H') || (argv[2][0]!='C' && argv[2][0]!='G'))
		InputErrorPrintf();	
	
	//先將高和寬讀入::因為讀圖檔需要"高"和"寬"
	im_height = 0;	
	for(i=0;i<strlen(argv[4]);i++){
		if( 48<=argv[4][i] && argv[4][i]<=57)
			im_height = im_height*10 + argv[4][i]-48;
	}		
	im_width = 0;	
	for(i=0;i<strlen(argv[5]);i++){
		if( 48<=argv[5][i] && argv[5][i]<=57)
			im_width = im_width*10 + argv[5][i]-48;
	}
	if(im_height>max_size || im_width>max_size){
		cout<<"超過Image Size!!"<<endl;
		exit(1);
	}
	indexsize = im_height*im_width;
	
	//==讀檔==		
	ReadBMP(argv[3]);					//讀入cover image
	PaletteNum = Product_Palette();		//將cover image的調色盤產生出來,得到調色盤的顏色總數
	//========
	
	//==調色盤分群資訊==
	SortPalette();						//將調色盤中所有的顏色做大小的排序
	PaletteIndex();						//將每個Pixel用Index來表示
	ComputeDiffOfColors();				//建立Palette中每個的Color間的Difference
	if(argv[2][0]=='C'){
		ClusterNum = 0;
		for(i=0;i<strlen(argv[6]);i++){
			if( 48<=argv[6][i] && argv[6][i]<=57)
				ClusterNum = ClusterNum*10 + argv[6][i]-48;
		}
		if(ClusterNum>PaletteNum){
			cout<<"Cluster Size超過Palette Size!!"<<endl;
			cout<<"The number of the palette is "<<PaletteNum<<endl;
			exit(1);
		}
		ProductCluster();			
	}
	else if(argv[2][0]=='G')
		ReadCluster(argv[6]);		
	
	//針對每一個color index紀錄它所屬的cluster的size
	for(i=0; i<ClusterNum; i++){
		for(j=0; j<ClusterSize[i]; j++){
			ColorClSi[ClusterIndex[i][j]]=ClusterSize[i];
		}
	}
	//for(i=0;i<PaletteNum;i++)
	//	cout<<ColorClSi[i]<<" ";	
	//cout<<endl;
	//==========	


	ReadSigningCode(SecretFileName);
	
	if(argv[1][0]=='D'){
		decode();
		contrast();
	}
	else if(argv[1][0]=='H'){		
		
		Embedding();
	
		ExtrPaletteIndex();
		ms = RMSE();	//==計算MSE==	
		cout<<"MSE = "<<ms;	
		if( ms != 0){
			ps = PSNR(ms);  //==計算PSNR==
			cout<<"	PSNR = "<<ps;
		}
		strcat(OutImageName, argv[3]);	
		WriteBMP(OutImageName);
	}
	
	
	
	return 0;
}
//====================================================================================

