#include <stdlib.h>
#include "huffman.h"
int huffmanencoder(hcode *h,unsigned char *dstbuf,unsigned char *srcbuf,int len){
	dstbuf[0]=dstbuf[1]=0;
	int pos=0,shift=0,i;
	unsigned char c;
	for (i=0;i<len;i++){
		c=srcbuf[i];
		dstbuf[pos]|=h->codeword[c] >>shift;
		dstbuf[pos+1]|=h->codeword[c]<<(8-shift);
		shift+=h->shift[c];
		if (shift>=8){
			shift-=8;
			pos++;
			dstbuf[pos+1]=0;
		}
		if (h->codeword[c]==255){
			dstbuf[pos]|=c >>shift;
			dstbuf[pos+1]|=c<<(8-shift);
			pos++;
			dstbuf[pos+1]=0;
		}
	}
	if (shift==0) pos--;
	return pos+1;
}

int huffmandecoder(hcode *h,unsigned char *dstbuf,unsigned char *srcbuf,int len){
	int pos=0,shift=0;
	int i;
	unsigned char c;
	for (i=0;i<len;i++){
		c=(srcbuf[pos]<<shift) | (srcbuf[pos+1]>>(8-shift));
		dstbuf[i]=h->decode[c];
		shift+=h->decodeshift[c];
		if (shift>=8){
			shift-=8;
			pos++;
		}
		if (__builtin_expect( c==255,0))
		{
			dstbuf[i]=(srcbuf[pos]<<shift) | (srcbuf[pos+1]>>(8-shift));
			pos++;
		}
	}
	dstbuf[len]=0;
	if (shift==0) pos--;
	return pos+1;

}


typedef struct htree{
struct htree *left,*right;
unsigned char c;
} huffmantree;
struct distr {
	huffmantree *h;
	int dist;
};

huffmantree * maketree(int *dist){
	struct distr dists[256];
	int i,j;
	int first,second;
	for (i=0;i<256;i++){
		dists[i].dist=dist[i];
		dists[i].h=calloc(1,sizeof(huffmantree));
		dists[i].h->c=i;
	}
	for (i=256;i>1;i--){
		first=(dists[0].dist<dists[1].dist)?0:1;
		second=(dists[0].dist<dists[1].dist)?1:0;
		for (j=2;j<i;j++) {
			if (dists[j].dist<dists[first].dist){
				second=first;
				first=j;
			} else if (dists[j].dist<dists[second].dist) {
				second=j;
			}
		}
		struct distr fd=dists[first],sd=dists[second];
		if (first==i-1){
			dists[second]=dists[i-2];
		}else if(first==i-2){
			dists[second]=dists[i-1];
		}else if(second==i-1){
			dists[first]=dists[i-2];
		}else if(second==i-2){
			dists[first]=dists[i-1];
		}else{
			dists[first]=dists[i-2];
			dists[second]=dists[i-1];
		}
		dists[i-2].dist=fd.dist+sd.dist;
		dists[i-2].h=calloc(1,sizeof(huffmantree));
		dists[i-2].h->left=fd.h;
		dists[i-2].h->right=sd.h;
	}
	return dists[0].h;
}

void sizes(huffmantree *t, hcode *h,int size){
	if (!t->left){
		h->shift[t->c]=size;
	} else {
		sizes(t->left,h,size+1);
		sizes(t->right,h,size+1);
	}
}
hcode * makehuffmancode(int *dist){
	hcode *h=calloc(1,sizeof(hcode));
	/*create huffman code*/
	huffmantree *tree=maketree(dist);
	sizes(tree,h , 0);  /*and transform to canonic huffman code*/
	unsigned char code=0;
	int i,j,k;
	int lastcode;
	for (i=1;i<=8;i++){
		for (j=0;j<256;j++){
			if (h->shift[j]==i){
				h->codeword[j]=(code++)<<(8-i);
			}
		}
		lastcode=code;
		code*=2;
	}
	for (j=0;j<256;j++){/*we fill codes we didnt use because codewords were >8bits. Which dont fit get 255 as escape code which means to interpret next 8 bits as character.*/
		if (h->shift[j]==9){
			h->shift[j]=8;
			h->codeword[j]=lastcode;
			if (lastcode<255) lastcode++;
		}
	}
	for (j=0;j<256;j++){
		if (h->shift[j]>9){
			h->shift[j]=8;
			h->codeword[j]=lastcode;
			if (lastcode<255) lastcode++;
		}
	}
	/*now we create decoder*/
	for(j=0;j<256;j++){
		for (k=0;k< 1<<(8-h->shift[j]);k++){
			int var=h->codeword[j] |k;
			h->decode[var]=j;
			h->decodeshift[var]=h->shift[j];
		}
	}
return h;
}