#include "stdio.h"
#include "string.h"
#define swap(type, x,y) do{type t;t=x;x=y;y=t;} while(0)
char srcCode[]="TONARI NO KYAKU WA YOKU KAKI KUU KYAKU DA";/*元データ*/
int  pntDT=0; char charDT[257]; int freqDT[257];/*頻度表(番人付き探索を使うので256+1に*/
/*（注意）文字列の長さの最大値は65,536なので文字列の添え字はunsignedにする*/
char Huffman[1024]={0};unsigned int ppHuff=0, bpHuff=0;/*Huffman Code格納領域*/
int searchDT(char DT){/*頻度表検索(番人付き探索)*/
	int i=0; charDT[pntDT]=DT; freqDT[pntDT]=0;
	while(charDT[i]!=DT) i++;
	if(i>=pntDT) pntDT++;/*見つからなかった場合，表の大きさを+1*/
	return i;
}
void freqCount(){/*頻度カウント*/
	for(int i=0;srcCode[i]!=0;i++)freqDT[searchDT(srcCode[i])]++;
}
void sortFreq(){/*頻度降順にソート（バブルソート）*/
	for(int i=0;i<pntDT-1;i++)
		for(int j=pntDT-1;j>i;j--)
			if(freqDT[j-1]<freqDT[j]){
				swap(char, charDT[j-1],charDT[j]);
				swap(int, freqDT[j-1],freqDT[j]);
			}
}
char bitOn(int bp){return 1<<(7-bp);}/*指定ビットOn*/
void bitstr(char str[], char ch){/*ビット列文字列化*/
	char dt=ch;
	for(int i=0;i<8;i++,dt<<=1)
		if(dt & 0x80) str[i]='1'; else str[i]='0';
	str[8]=0;
}
void countHuffman(){/*ハフマン符号のビットカウント*/
	bpHuff++;if(bpHuff>=8){bpHuff=0; ppHuff++;}
}
void setHuffman(){/*ハフマン符号化*/
	unsigned int N=strlen(srcCode);/*文字列の長さ*/
	for(unsigned int i=0; i<N; i++){
		int p=searchDT(srcCode[i]);/*頻度表から文字検索*/
		if(p==0){countHuffman();countHuffman();}/*先頭コードB'00'*/
		else if(p==1){/*2番目B'01'*/
			countHuffman();	Huffman[ppHuff] |=bitOn(bpHuff);/*ビットOn*/
			countHuffman();/*次の位置*/
		}
		else {/*3番目以降B'1'の連続*/
			for(int j=0; j<(p-1);j++){
				Huffman[ppHuff] |= bitOn(bpHuff);/*ビットOn*/
				countHuffman();/*次の位置*/
			}
			if(p<(pntDT-1))countHuffman();/*最小頻度以外は最後がB'0'*/
		}
	}
}
void countBitP(int * i, int *j){/*バイト単位のビットカウント*/
	(*j)++;if((*j)>=8){(*j)=0; (*i)++;}
}
void getHuffman(char str[]){/*ハフマン符号から文字列取得*/
	int i=0,j=0, p=0; unsigned int N=strlen(srcCode);
	for(unsigned int k=0;k<N;k++){
		if(Huffman[i] & bitOn(j)){/*先頭がB'1'のとき，B'1'カウント*/
			p=pntDT-1;countBitP(&i, &j); /*すべてB'1'のとき最小頻度文字*/
			for(int jj=0;jj<pntDT-3;jj++,countBitP(&i, &j))
				if(!(Huffman[i] & bitOn(j))){/*B'0'のとき，連続的なB'1'の終了*/
					p=jj+2;countBitP(&i, &j); break;
				}
		}
		else{/*Code=B'00',B'01'のとき*/
			countBitP(&i, &j);
			if(Huffman[i] & bitOn(j))p=1; else p=0;
			countBitP(&i, &j);/*next bit position*/
		}
		str[k]=charDT[p];
	}
	str[N]=0;
}
int main(){
	printf("\n\n Source String \"%s\"\n", srcCode);
	
	freqCount();/*Frequency Table 生成*/
	printf("\n\n Size of Frequency Table = %d", pntDT);
	printf("\n N0.  (\'C\' : Hex) freq. ");
	printf("\n-------------------------------------");
	for(int i=0;i<pntDT; i++){
		char CC=charDT[i],CD=CC;if(CC<=0x20) CD=' ';
		printf("\n %4d (\'%c\' : %02X )  %4d  ", i,CD,CC,freqDT[i]);
	}
	sortFreq();/*descending sort by Frequency*/
	printf("\n\n Size of Frequency Table = %d(after sort)\n", pntDT);
	printf("\n N0.  (\'C\' : Hex) freq.  Huffman Code");
	printf("\n-------------------------------------");
	for(int i=0;i<pntDT; i++){
		char CC=charDT[i],CD=CC;
		if(CC<=0x20) CD=' ';
		printf("\n %4d (\'%c\' : %02X )  %4d  ", i,CD,CC,freqDT[i]);
		/*Huffman Code Display */
		if     (i==0) printf("00");
		else if(i==1) printf("01");
		else{
			for(int k=1; k<i;k++)printf("1");
			if(i!=(pntDT-1))printf("0");
		}
	}
	char str[256];
	printf("\n\n Huffman Code check\n");
	setHuffman();/*Huffman coding*/
	for(unsigned int i=0;i<=ppHuff;i++){
	  if((i%8)==0)printf("\n");
	  bitstr(str,Huffman[i]); printf(" %s", str);
	}
	getHuffman(str);/* Get String from Huffman Cide*/
	printf("\n\n reverce Huffman Code \"%s\"\n", str);
	unsigned int N=ppHuff;if(bpHuff !=0) N++;
	unsigned int N2=strlen(srcCode);
	printf("\n Huffman Code Length=%d (Source String Length=%d) Coff.=%lf",N,N2, (double)N/N2);
	getchar();
	return 0;
}