decoder.cpp

在嵌入式FPGA开发环境(ISE7.1)下的Huffman编解码的程序.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>

#define NON_LEAVE 999

typedef struct
{
//	char character;
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;         // the HuffmanTree struct is a little different from the struct in encoder

typedef char **HuffmanCode;

void main()
{
	FILE *codeStream,*codeTable,*decodeStream;
	int i=0,idx;      //idx: index of the idle space in the tree
	unsigned char k=128;  // binary:1000 0000
	unsigned char temp=0;
	char *cd;
	HuffmanTree HT,p;
	HuffmanCode HC;

	codeTable=fopen("codetable.txt","r");
	char length=fgetc(codeTable);
	char *CH=(char *)malloc(sizeof(char)*length);  // characters
	HC=(HuffmanCode)malloc(sizeof(char *)*length); // codes of characters 

//	while(!feof(codeTable))  //  feof() need one more read operation,see the same problem below
	while(i<length)
	{
		char value=fgetc(codeTable);
		char codelen=fgetc(codeTable);
		
		unsigned char code=fgetc(codeTable);  //
		
		CH[i]=value;
		//		code>>=(8-codelen);
		
		cd=(char *)malloc((codelen+1)*sizeof(char));
		cd[codelen]='\0';
		//		for(int l=0;l<codelen;l++)
		//			HC[i][l]='0';
		//		_itoa(code,HC[i],2);
		for(int j=0;j<codelen;j++)
		{
			temp=code&k;
			if(temp==k)
				//				*(HC[i]+j)='1';
				cd[j]='1';
			//				strcat(HC[i],"1");
			else
				//				*(HC[i]+j)='0';
				cd[j]='0';
			//				strcat(HC[i],"0");
			k>>=1;
		}
		
		HC[i]=(char *)malloc((codelen+1)*sizeof(char));
		strcpy(HC[i],cd);
		//		printf("%s  ",HC[i]);
		
		k=128;
		i++;
	}

	if(fclose(codeTable))
      printf("The code table file was not closed\n" );

//	codeStream=fopen("encode_result.txt","r");
//	char temp=fgetc(codeStream);
	HT=(HuffmanTree)malloc((2*length)*sizeof(HTNode));   // initiate the tree before creation 
	for(p=HT,i=0;i<2*length;++i,++p)
	{
		(*p).weight=NON_LEAVE;                    // to distinguish from the ASCII code, use a number that never occur in ASCII code
//		(*p).character=cha[i-1];
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}
	
	for(i=0,idx=2;i<length;i++)
	{
		int t=0,par=1;   //par: index of parent node
		p=HT+1;               
		
		while(HC[i][t]!='\0')
		{
			if((HC[i][t]=='1')&&((*p).rchild==0))  // if '1' and first time,create and go right hand 
			{
				(*p).rchild=idx;
				HT[idx].parent=par;
				p=&HT[idx];
				par=idx;
				idx++;
			}
			else if((HC[i][t]=='1')&&((*p).rchild!=0))   // if '1' but created,just go right hand
			{
				par=(*p).rchild;
				p=&HT[par];
			}
			else if((HC[i][t]=='0')&&((*p).lchild==0))  // if '0' and first time,create and go left hand
			{
				(*p).lchild=idx;
				HT[idx].parent=par;
				p=&HT[idx];
				par=idx;
				idx++;
			}
			else if((HC[i][t]=='0')&&((*p).lchild!=0))   // if '0' but created,just go left hand
			{
				par=(*p).lchild;
				p=&HT[par];
			}
			t++;
		}
		(*p).weight=CH[i];
	}
// print the tree created by the code table(to test)	
/*	printf("no. weight rchild lchild\n");
	for(i=1,p=HT+1;i<2*length;i++,p++)
	{
		printf("%d    ",i);
		printf("%d    ",(*p).weight);
		printf("%d    ",(*p).parent);
		printf("%d    ",(*p).rchild);
		printf("%d \n",(*p).lchild);
	}
// to test the correctness of the tree	
	p=HT+1;
	char ch;
	while(1)
	{
		
		do
		{
			scanf("%c",&ch);
			if(ch=='1')
				p=&HT[(*p).rchild];
			else if(ch=='0')
				p=&HT[(*p).lchild];
		}while(((*p).rchild!=0)||((*p).lchild!=0));
		printf("%c \n",(*p).weight);
		p=HT+1;
	}
*/
	// read from the encode result and decode it
	p=HT+1;
	unsigned char buffer1,buffer2,buffer3;      // buffer4 is not necessary
	codeStream=fopen("encode_result.txt","r");
	decodeStream=fopen("decode_result.txt","wb+");  // save the decode result
	int posidx=1;                              // position index of current bit out of 8
	k=128;                                    // that is '1000 0000' in binary 
	bool EOFLAG=false;                        // flag of EOF

	fread(&buffer1,1,1,codeStream);
	while(!feof(codeStream))
	{
		if(EOFLAG&&(posidx==(buffer3+1)))
			break;
		do {
			if(posidx>8)       // need to read a new byte
			{
				fread(&buffer2,1,1,codeStream);
				fread(&buffer3,1,1,codeStream);  // to test whether EOF
				fread(&buffer3,1,1,codeStream);
				if(feof(codeStream))
					EOFLAG=true;
				fseek(codeStream,-2L,1);
				buffer1=buffer2;
				k=128;
				posidx=1;
			}
			temp=buffer1&k;           // get the current bit
			if(temp==k)               // if current bit is '1',go right hand
			{
				p=&HT[(*p).rchild];
				posidx++;
			}
			else                      // if current bit is '0',go left hand
			{
				p=&HT[(*p).lchild];
				posidx++;
			}
			k=128>>(posidx-1);
		}while(((*p).rchild!=0)||((*p).lchild!=0));  // (rchild==0 && lchild==0) means leave of huffman tree,also means a character has been decoded  
		fwrite(&((*p).weight),1,1,decodeStream);     // then write the character to file
		p=HT+1;                                      // reset the pointer to root of huffman tree
		
	}
	
	if(fclose(codeStream))
		printf("The code file was not closed\n" );
	if(fclose(decodeStream))
		printf("The decode file was not closed\n" );

}