霍夫曼编码源码.txt

霍夫曼编码 是一种无失真编码 讲的很详细

// Adaptive Huffman encoding

#include <stdio.h>
#include <stdlib.h>
#include "Huff.h"

// global flags:
//  output in binary? or "0" "1"?
int binary = 1;
//  if "01", break after each unit?  or every 4 bits?
int hexoutput = 0;
//  decode input?  or encode it?
int decode = 0;

FILE *fin = stdin;
FILE *fout = stdout;

// swaps two nodes within the tree
// when we have added/incrimented a node and a swap is necessary
void SwapNodes(PHuff h, NodeIndex n1, NodeIndex n2)
{
	HuffNode Temp;

	// first swap kids
	if(h->nodes[n1].c0 != NONE)
		h->nodes[ h->nodes[n1].c0].parent = n2;
	if(h->nodes[n1].c1 != NONE)
		h->nodes[ h->nodes[n1].c1].parent = n2;
	if(h->nodes[n2].c0 != NONE)
		h->nodes[ h->nodes[n2].c0].parent = n1;
	if(h->nodes[n2].c1 != NONE)
		h->nodes[ h->nodes[n2].c1].parent = n1;

	// store the pertinent first node vals in temp
	Temp.c0		= h->nodes[n1].c0;
	Temp.c1		= h->nodes[n1].c1;
	Temp.weight	= h->nodes[n1].weight;
	Temp.value	= h->nodes[n1].value;

	// assign 2 to 1
	h->nodes[n1].c0		= h->nodes[n2].c0;
	h->nodes[n1].c1		= h->nodes[n2].c1;
	h->nodes[n1].weight	= h->nodes[n2].weight;
	h->nodes[n1].value	= h->nodes[n2].value;

	//assign temp to 2
	h->nodes[n2].c0		= Temp.c0;
	h->nodes[n2].c1		= Temp.c1;
	h->nodes[n2].weight	= Temp.weight;
	h->nodes[n2].value	= Temp.value;


	// update location of the symbols so we keep track fo them
	// if they are actual chars, UNKNOWN, or EOF
	if(h->nodes[n1].value != NONE)
	{
		h->symbols[ h->nodes[n1].value ] = n1;
	}

	if(h->nodes[n2].value != NONE)
	{
		h->symbols[ h->nodes[n2].value ] = n2;
	}
}

// print out the bits along the path from s to the root
// in the correct order
void PrintCode(NodeIndex ni, PHuff h)
{
	if(ni == h->root)
		return;
	else
	{
		// call recursively before printing so they come out
		// in the correct order
		PrintCode(h->nodes[ni].parent, h);

		// now print this bit
		if(h->nodes[ni].isLeftChild)
			fprintf(fout, "%d", 0);
		else
			fprintf(fout, "%d", 1);

		return;
	}
}


// looks for swaps that need to be made after
// nodes are added and makes necessary changes
// assumes the node it is being passed still needs
// to be incrimented 
void MakeTreeOK(NodeIndex ni, PHuff h)
{
	// if we've reached the root, we just have to incriment the weight
	if(ni == h->root)
		h->nodes[ h->root ].weight++;

	// still traversing tree
	else
	{
		// find the highest node with same val and swap
		 int LastSame = ni;
		 for(int scan = ni + 1; scan < h->root; scan++)
		 {
			 if(h->nodes[scan].weight == h->nodes[ni].weight)
				 LastSame = scan;
		 }

	 	 // incriment the weight of the node now. 
		 h->nodes[ni].weight++;

		 // if this caused a change swap the nodes and keep updating
		 if(LastSame != ni && LastSame != h->nodes[ni].parent)
		 {
			 SwapNodes(h, LastSame, ni);
			 MakeTreeOK(h->nodes[LastSame].parent, h);

		 // no node to swap with
		 }else
		 {
			 MakeTreeOK(h->nodes[ni].parent, h);
		 }
	}

	return;
}

// adds the UNKOWN node and the EOF node
// so we can start receiving/sending real data
void SeedTree(PHuff h)
{
	// initialize the array.  To begin it will have the root
	// node, the UKNOWN node, and the ENDOFFILE node

	// initialize the symbol array
	for(int i = 0; i < NUMSYMBOLS; i++)
		h->symbols[i] = NONE;

	// add the root node.
	h->nodes[MAXNODE].weight	= 1;
	h->nodes[MAXNODE].self		= MAXNODE;
	h->nodes[MAXNODE].c0		= MAXNODE - 2; // NYT aka UNKNOWN
	h->nodes[MAXNODE].c1		= MAXNODE - 1; // EOF
	h->nodes[MAXNODE].parent	= NONE;
	h->nodes[MAXNODE].value		= NONE;

	// add the UNKNOWN node to the end of the array
	h->nodes[MAXNODE - 2].weight		= 0;
	h->nodes[MAXNODE - 2].self			= MAXNODE - 2;
	h->nodes[MAXNODE - 2].value			= UNKNOWN;
	h->nodes[MAXNODE - 2].isLeftChild	= 1;
	h->nodes[MAXNODE - 2].parent		= MAXNODE;
	h->nodes[MAXNODE - 2].c0			= NONE;
	h->nodes[MAXNODE - 2].c1			= NONE;

	// update the symbols array so we know where it is
	h->symbols[UNKNOWN] = MAXNODE - 2;

	// add the ENDOFFILE node
	h->nodes[MAXNODE - 1].weight		= 1;
	h->nodes[MAXNODE - 1].self			= MAXNODE - 1;
	h->nodes[MAXNODE - 1].value			= ENDOFFILE;
	h->nodes[MAXNODE - 1].isLeftChild	= 0;
	h->nodes[MAXNODE - 1].parent		= MAXNODE;
	h->nodes[MAXNODE - 1].c0			= NONE;
	h->nodes[MAXNODE - 1].c1			= NONE;

	// update the symbols array so we know where it is
	h->symbols[ENDOFFILE] = MAXNODE - 1;

	// general bookkeeping for the huff
	h->nextFree = MAXNODE - 3;
	h->root		= MAXNODE;
}

// Creates new nodes and addes them to the tree
// Tree must still be updated after the node is added
int AddNode(Symbol s, PHuff h)
{

		// figure out the next open nodes, then update nextFree
		int NewNode = h->nextFree;
		int NextUnknown = h->nextFree - 1;
		h->nextFree -= 2;

		// get the NodeIndex of UNKNOWN before moving it
		int LastUnknown = h->symbols[UNKNOWN];

		// move UNKNOWN, update its members, and update symbol[]
		// so we can find it later
		h->nodes[NextUnknown] = h->nodes[ h->symbols[UNKNOWN] ];
		h->nodes[NextUnknown].parent = h->symbols[UNKNOWN];
		h->nodes[NextUnknown].self = NextUnknown;

		h->symbols[UNKNOWN] = NextUnknown;

		// Create the parent node
		h->nodes[LastUnknown].c0 = NextUnknown;
		h->nodes[LastUnknown].c1 = NewNode;
		h->nodes[LastUnknown].weight = 0;	// must be incrimented when the tree is fixed
		h->nodes[LastUnknown].value = NONE;

		// Create the new node
		h->nodes[NewNode].parent		= LastUnknown;
		h->nodes[NewNode].self			= NewNode;
		h->nodes[NewNode].weight		= 1;
		h->nodes[NewNode].isLeftChild	= 0;
		h->nodes[NewNode].value			= s;
		h->nodes[NewNode].c0			= NONE;
		h->nodes[NewNode].c1			= NONE;


		// add it to the symbols array
		h->symbols[s] = NewNode;

		// return the last node we found (may be the same node)
		return LastUnknown;

}

// Encode entire input sequence.
void EncodeInput(PHuff h)
{
	// create the tree and add UNKNOWN and ENDOFFILE nodes
	SeedTree(h);

	// now we've set up the tree, start reading in the data and:
	Symbol s;
	while(s != ENDOFFILE)
	{
		// get the symbol to encode
		s = ReadSymbol();

		// update the tree
		if(h->symbols[s] == NONE)
		{

			// first send UNKNOWN and the bit series
			PrintCode(h->symbols[UNKNOWN], h);
			fprintf(fout, " ");
			WriteRawSymbol(s);			
	
			// add the node
			int LastUnknown = AddNode(s, h);
			
			// fix the tree if necessary
			MakeTreeOK(LastUnknown, h); 
		}
		// if it was found incriment the symbol and update tree
		else
		{
			// write the symbol
			PrintCode(h->symbols[s], h);
			fprintf(fout, " ");

			// fix the tree if the new node broke it
			MakeTreeOK(h->symbols[s] , h );
		}
	}

	// print out padding (simulate actual byte)
	fprintf(fout, "00000000");
}

// decode input from intermediate file
void DecodeInput(PHuff h)
{
	// get the tree ready for input
	SeedTree(h);

	// start converting back to data from "binary"
	Symbol s = NONE;
	while(s != ENDOFFILE)
	{
		// get the next symbol
		s = ReadEncSymbol(h);

		// if we see unknown the next one will be
		// a raw 8 bit char and must be converted
		if(s == UNKNOWN)
			s = ReadRawSymbol();

		// write the sybmol out
		WriteSymbol(s);

		// update the tree
		if(h->symbols[s] == NONE)
		{
			//add the node
			int LastUnknown = AddNode(s, h);

			// fix the tree if necessary
			MakeTreeOK(LastUnknown, h); 
		}else
			MakeTreeOK(h->symbols[s], h);
	}
}

// begin main
void main(int argc, char **argv)
{
	// general setup stuff
	int i;

	// read the program flags
	// A flag of -b means output bits as "0" or "1" characters
	//   (useful for debugging)
	// A flag of -d means to decode the input instead of encoding it
	for (i=1; i<argc; i++) {
		if (argv[i][0] == '-') {
			switch(argv[i][1]) {
			case 'b': binary = 0; break;
			case 'd': decode = 1; break;
			case 'h': hexoutput = 1; break;
			}
		}
	}

    // always encode to file 'tstenc' and decode from there
    // always read input files from 'tstin'
    // always write decoded output to 'tstout'
    if (decode) {
        fin = fopen("tstenc.txt", "rb");
        fout = fopen("tstout.txt", "wb");
    } else {
        fin = fopen("tstin", "rb");
        fout = fopen("tstenc.txt", "wb");
	}

	Huff huff;
	PHuff h = &huff;

	// keep track of the root node
	huff.root = MAXNODE;

	if (!decode) {
		EncodeInput(h);
	} else {
		DecodeInput(h);
	}

}



// Used when encoding: reads next symbol from input
Symbol ReadSymbol()
{
	int c;
	c = getc(fin);
	if (c == EOF)
		return ENDOFFILE;
	else return c;
}

// Used when decoding: reads next bit from input
// since bits are 1s and 0s this functions assumes all it 
// will see are 1s 0s and spaces.  
Bit ReadBit()
{

	// removes spaces
	Bit c;
	do{
		c = getc(fin);
	}while( c == ' ');


	// return hex numbers based on the ASCII representations we read
	if(c == '1')
		return 0x01;
	else
		return 0x00;
}

// Used when decoding: read multiple bits until pattern matches some symbol
Symbol ReadEncSymbol(PHuff h)
{
	// this function should make multiple calls to ReadBit()
	// until it figures out which symbol the encoded bits represent
	// (by using the huffman tree)

	// begin looking at the root
	NodeIndex Position = h->root;

	// keep traversing the tree until we find the correct bit
	while(h->nodes[Position].value == NONE)
	{
		Bit Next = ReadBit();

		// if the next bit is a 1 go right, else go left
		if(Next)
		{
			Position = h->nodes[Position].c1;
		}else
		{
			Position = h->nodes[Position].c0;
		}
	}

	// now that we've found the correct symbol return it
	return h->nodes[Position].value;
	
}

// Used when decoding: read raw 8-bit symbol
Symbol ReadRawSymbol()
{
	Symbol s = 0;
	// build the symbol one bit at a time
	for (int i=0; i<8; i++)
		// shift data left by one bit, and stuff new bit at right
		s = s<<1 | ReadBit();

	return s;
}

// Used when decoding: write a symbol to output
// Ignores special symbols > 255
void WriteSymbol(Symbol s)
{
	if (s < NUMCHARS) {
		fprintf(fout, "%c", (unsigned char)s);
	}
}

// Used when encoding: write a bit to output
// Writes "0" or "1" characters if binary==0.
//
// If binary==1, accumulates bits into a holding char, and
// outputs the char once it has 8 bits.
void WriteBit(Bit bitout)
{
	// your implementation here
	// if (binary==0) then just write "0" or "1" to output
	if(!binary)
		fprintf(fout, "%d", bitout);
	// to write a char to output, use fprintf as in WriteSymbol above
	else
	{
		// not used 
	}


}

// Used when encoding: write a raw 8-bit symbol
void WriteRawSymbol(Symbol s)
{
	// write individual bits, from left to right
	for (int i=7; i>=0; i--)

		// shift the bit we're interested in to the rightmost position,
		// then mask out all other bits
		WriteBit(s>>i & 0x1);

	// if we're outputting bits as "0" and "1", add a space after
	// all the bits have been printed
	if (!binary && !hexoutput) fprintf(fout, " ");
}