#include <windows.h>

#define DEBUG

#ifdef DEBUG
#include <stdio.h>
#endif

typedef struct _bunpunode {
	int data;
	int kosuu;
	struct _bunpunode* prev;
	struct _bunpunode* next[2];
}bunpunode;

typedef struct {
	int size;
	char data[256];
}henkan;

int countbytes(unsigned int*,HANDLE);
bunpunode* dohenkan(henkan*,unsigned int*);
void freehenkan(bunpunode*);
unsigned int writekosuu(unsigned int*,HANDLE);
unsigned int doassyuku(henkan*,HANDLE,HANDLE);
unsigned int writeassyuku(HANDLE,henkan*,char*,int*);
int readkosuu(unsigned int*,HANDLE);
unsigned int dokaitou(HANDLE,HANDLE,bunpunode*);
unsigned int writekaitou(int*,unsigned char,HANDLE,bunpunode*,bunpunode**);
void* mycalloc(unsigned int);
void myfree(void*);

/*データを圧縮する*/
unsigned int assyuku(HANDLE in,HANDLE out) {
	unsigned int kosuu[256]={0};
	henkan henkanlist[257];
	bunpunode* nodefirst;
	unsigned int wrotedata=0;
	/*それぞれのデータがいくつあるか数える*/
	if(countbytes(kosuu,in))return 0xFFFFFFFF;
	/*変換表を作成する*/
	nodefirst=dohenkan(henkanlist,kosuu);
	/*個数一覧を出力する*/
	wrotedata+=writekosuu(kosuu,out);
	/*圧縮をかける*/
	wrotedata+=doassyuku(henkanlist,in,out);
	/*変換表を解放する*/
	freehenkan(nodefirst);
	/*書き込んだバイト数を返す*/
	return wrotedata;
}

/*データを解凍する*/
unsigned int kaitou(HANDLE in,HANDLE out) {
	unsigned int kosuu[256]={0};
	henkan henkanlist[257];
	bunpunode* nodefirst;
	unsigned int wrotedata=0;
	/*データの個数を読み込む*/
	if(readkosuu(kosuu,in))return 0xFFFFFFFF;
	/*変換表を作成する*/
	nodefirst=dohenkan(henkanlist,kosuu);
	/*解凍をする*/
	wrotedata=dokaitou(in,out,nodefirst);
	/*変換表を解放する*/
	freehenkan(nodefirst);
	/*書き込んだバイト数を返す*/
	return wrotedata;
}

/*それぞれのデータがいくつあるか数える*/
int countbytes(unsigned int* kosuu,HANDLE fp) {
	unsigned int i;
	unsigned int size;
	unsigned char c;
	unsigned int read;
	size=GetFileSize(fp,NULL);
	if(size==0xFFFFFFFF)return 1;
	SetFilePointer(fp,FILE_BEGIN,NULL,0);
	for(i=0;i<size;i++) {
		ReadFile(fp,&c,1,(DWORD*)&read,NULL);
		kosuu[c]++;
	}
	return 0;
}

#ifdef DEBUG
/*デバッグ用に変換ツリーを表示する*/
void printbunpunode(bunpunode* root,int kaisou,FILE* out) {
	int i;
	for(i=0;i<kaisou;i++)fprintf(out," ");
	fprintf(out,"address=%p\n",root);
	for(i=0;i<kaisou;i++)fprintf(out," ");
	fprintf(out,"data=%d\n",root->data);
	for(i=0;i<kaisou;i++)fprintf(out," ");
	fprintf(out,"kosuu=%d\n",root->kosuu);
	for(i=0;i<kaisou;i++)fprintf(out," ");
	fprintf(out,"prev=%p\n",root->prev);
	for(i=0;i<kaisou;i++)fprintf(out," ");
	fprintf(out,"next[0]=%p\n",root->next[0]);
	for(i=0;i<kaisou;i++)fprintf(out," ");
	fprintf(out,"next[1]=%p\n",root->next[1]);
	if(root->next[0]!=NULL) {
		for(i=0;i<kaisou;i++)fprintf(out," ");
		fprintf(out,"next[0]\n");
		printbunpunode(root->next[0],kaisou+1,out);
	}
	if(root->next[1]!=NULL) {
		for(i=0;i<kaisou;i++)fprintf(out," ");
		fprintf(out,"next[1]\n");
		printbunpunode(root->next[1],kaisou+1,out);
	}
}
#endif

/*変換表を作成する*/
bunpunode* dohenkan(henkan* henkanlist,unsigned int* kosuu) {
	bunpunode* sublist[257];
	bunpunode* forhenkanlist[257];
	bunpunode* temp;
	int i,j;
	int max;
#ifdef DEBUG
	FILE* log;
#endif
	/*終了コード*/
	sublist[0]=mycalloc(sizeof(bunpunode));
	sublist[0]->data=-1;
	sublist[0]->kosuu=1;
	/*それぞれのデータの数*/
	for(i=0;i<256;i++) {
		sublist[i+1]=mycalloc(sizeof(bunpunode));
		sublist[i+1]->data=i;
		sublist[i+1]->kosuu=kosuu[i];
	}
	/*リストをコピーする*/
	for(i=0;i<257;i++)forhenkanlist[i]=sublist[i];
#ifdef DEBUG
	log=fopen("log.txt","w");
	if(log==NULL)log=stdout;
	fprintf(log,"ソート前\n"); 
	for(i=0;i<257;i++) {
		fprintf(log,"sublist[%d]=%p\n",i,sublist[i]);
		fprintf(log,"sublist[%d]->data=%d\n",i,sublist[i]->data);
		fprintf(log,"sublist[%d]->kosuu=%d\n",i,sublist[i]->kosuu);
	}
#endif
	/*挿入ソート(降順)*/
	for(i=1;i<257;i++) {
		temp=sublist[i];
		for(j=i-1;j>=0;j--) {
			if(sublist[j]->kosuu>=temp->kosuu)break;
			sublist[j+1]=sublist[j];
		}
		sublist[j+1]=temp;
	}
#ifdef DEBUG
	fprintf(log,"ソート後\n"); 
	for(i=0;i<257;i++) {
		fprintf(log,"sublist[%d]=%p\n",i,sublist[i]);
		fprintf(log,"sublist[%d]->data=%d\n",i,sublist[i]->data);
		fprintf(log,"sublist[%d]->kosuu=%d\n",i,sublist[i]->kosuu);
	}
#endif
	/*多い要素から順につなげる*/
	for(i=256;i>0;i--) {
		temp=mycalloc(sizeof(bunpunode));
		temp->data=-2;
		temp->kosuu=sublist[i-1]->kosuu+sublist[i]->kosuu;
		temp->next[0]=sublist[i-1];
		temp->next[1]=sublist[i];
		sublist[i-1]->prev=temp;
		sublist[i]->prev=temp;
		for(j=i-2;j>=0;j--) {
			if(sublist[j]->kosuu>=temp->kosuu)break;
			sublist[j+1]=sublist[j];
		}
		sublist[j+1]=temp;
	}
#ifdef DEBUG
	fprintf(log,"変換ツリー\n");
	printbunpunode(sublist[0],0,log);
#endif
	/*変換表を作成する*/
	for(i=0;i<257;i++) {
		temp=forhenkanlist[i];
		for(henkanlist[i].size=0;temp->prev!=NULL;henkanlist[i].size++) {
			if(temp==temp->prev->next[0])
				henkanlist[i].data[henkanlist[i].size]=0;
			else if(temp==temp->prev->next[1])
				henkanlist[i].data[henkanlist[i].size]=1;
			temp=temp->prev;
		}
	}
#ifdef DEBUG
	fclose(log);
#endif
	/*最初の要素を返す*/
	return sublist[0];
}

/*変換リストを解放する*/
void freehenkan(bunpunode* ptr) {
	if(ptr->next[0]!=NULL)freehenkan(ptr->next[0]);
	if(ptr->next[1]!=NULL)freehenkan(ptr->next[1]);
	myfree(ptr);
}

/*出現回数の情報を書き込む*/
unsigned int writekosuu(unsigned int* kosuu,HANDLE out) {
	unsigned int allwrote=0,wrote;
	int i;
	unsigned int data;
	unsigned char towrite;
	for(i=0;i<256;i++) {
		data=kosuu[i];
		do {
			towrite=data & 0x7F;
			if((data=data>>7)>0)towrite|=0x80;
			WriteFile(out,&towrite,sizeof(char),(DWORD*)&wrote,NULL);
			allwrote+=wrote;
		} while(data>0);
	}
	return allwrote;
}

/*圧縮をかける*/
unsigned int doassyuku(henkan* henkanlist,HANDLE in,HANDLE out) {
	unsigned int i;
	unsigned int size;
	unsigned char c;
	unsigned int read;
	unsigned int allwrote=0,wrote;
	char buf[8];
	int bufsize=0;
	size=GetFileSize(in,NULL);
	if(size==0xFFFFFFFF)return 1;
	SetFilePointer(in,FILE_BEGIN,NULL,0);
	for(i=0;i<size;i++) {
		ReadFile(in,&c,1,(DWORD*)&read,NULL);
		allwrote+=writeassyuku(out,&henkanlist[(int)c+1],buf,&bufsize);
	}
	/*終了コード*/
	allwrote+=writeassyuku(out,&henkanlist[0],buf,&bufsize);
	/*バッファの残りを書き込む*/
	if(bufsize>0) {
		c=0;
		for(i=0;i<bufsize;i++) {
			c|=buf[i]<<i;
		}
		WriteFile(out,&c,sizeof(char),(DWORD*)&wrote,NULL);
		allwrote+=wrote;
	}
	return allwrote;
}

/*圧縮データを書き込む*/
unsigned int writeassyuku(HANDLE out,henkan* hk,char* buf,int* bufsize) {
	int i,j;
	unsigned char c;
	unsigned int allwrote=0,wrote;
	for(i=hk->size-1;i>=0;i--) {
		buf[*bufsize]=hk->data[i];
		(*bufsize)++;
		if(*bufsize>=8) {
			c=0;
			for(j=0;j<8;j++) {
				c|=buf[j]<<j;
			}
			WriteFile(out,&c,sizeof(char),(DWORD*)&wrote,NULL);
			allwrote+=wrote;
			*bufsize=0;
		}
	}
	return allwrote;
}

/*データの個数を読み込む*/
int readkosuu(unsigned int* kosuu,HANDLE in) {
	unsigned int read;
	int i,j;
	unsigned char c;
	for(i=0;i<256;i++)kosuu[i]=0;
	for(i=0;i<256;i++) {
		j=0;
		do {
			ReadFile(in,&c,sizeof(char),(DWORD*)&read,NULL);
			if(read!=sizeof(char))return 1;
			kosuu[i]|=(c & 0x7F)<<j;
			j+=7;
		} while(c & 0x80);
	}
	return 0;
}

/*解凍をする*/
unsigned int dokaitou(HANDLE in,HANDLE out,bunpunode* root) {
	unsigned int wroteall=0;
	unsigned int wrote,read;
	unsigned char c;
	bunpunode* now=root;
	int end=0;
	while(end==0) {
		ReadFile(in,&c,sizeof(char),(DWORD*)&read,NULL);
		if(read!=sizeof(char))return 0xFFFFFFFF;
		wrote=writekaitou(&end,c,out,root,&now);
		wroteall+=wrote;
	}
	return wroteall;
}

/*解凍データを書き込む*/
unsigned int writekaitou(int* end,unsigned char c,HANDLE out,
		bunpunode* root,bunpunode** now) {
	int i;
	int ima;
	unsigned char writec;
	unsigned int wroteall=0,wrote;
	for(i=0;i<8;i++) {
		ima=(c & (1<<i))>>i;
		*now=(*now)->next[ima];
		if((*now)->data==-1) {
			*end=1;
			break;
		} else if((*now)->data>=0) {
			writec=(*now)->data;
			WriteFile(out,&writec,sizeof(char),(DWORD*)&wrote,NULL);
			wroteall+=wrote;
			*now=root;
		}
	}
	return wroteall;
}

/*メモリ確保*/
void* mycalloc(unsigned int size) {
	return HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,size);
}

/*メモリ解放*/
void myfree(void* ptr) {
	HeapFree(GetProcessHeap(),0,ptr);
}