adahuff.cpp

自适应huffman编码

#include "StdAfx.h"
#include ".\adahuff.h"

 #undef MY_DEBUG
//#define MY_DEBUG

AdaHuffTree::AdaHuffTree(void)
{
	this->size = 0;
	this->used = 0;
}

AdaHuffTree::~AdaHuffTree(void)
{
	if (this->t)
		delete this->t;

	if (this->ct)
		delete this->ct;
}

void AdaHuffTree::Init(int tsize)
{
	this->t = new AHTreeNode[tsize];   // allocate space for nodes at first
	this->ct = new CodeTbNode[257];    // 257, hard coding, NT_REVISITED, shw, 2005.09.28, PKU
	this->size = tsize;  
	this->used = 1;     // 1 node is reserved for NYT 
	this->nyt_idx = 0;  // initially, the tree contains only one node, NYT.
	
	for (int i = 0; i < this->size; i++)
	{
		this->t[i].parent = -1;   // no parent.
		this->t[i].lchild = -1;   // no left child.
		this->t[i].rchild = -1;   // no right child.
		this->t[i].weight = 0;
		this->t[i].value[0] = 0;
		this->t[i].value_len = 0;
	}

	for (int i = 0; i < 256; i++)  // 256, hard coding, NT_REVISITED, shw
	{
		this->ct[i].un.code[0] = (char)i;
		this->ct[i].un.code[1] = (char)0;
		this->ct[i].un.code[2] = (char)0;
		this->ct[i].un.code[3] = (char)0;
		this->ct[i].code_len = 8;
		this->ct[i].idx = -1;
	}

	//  NYT code , hard coding, NT_REVISITED
	this->ct[256].un.l = 0;
	this->ct[256].code_len = 0; 
	this->ct[256].idx = 0;
}

void AdaHuffTree::SetDebugMode(int mode)
{
	this->debug_mode = mode;
}
// Read next value from bits to value
// now, the function is just simplely read 8 bits each time. 
// The function is write for extensibility
// 
// Input:  BitIO bits,
//         int   max_len, 
// Output: char *value, 
//         int  &value_len
//         int  &idx; the index for the value in the tree.  
// Return: true,  success
//         false, failure
inline bool AdaHuffTree::next_value(BitIO * bits, char * value, int max_len, int & value_len, int & idx)
{
	if (max_len < 8)
		return false;

	if (bits->ReadAByte(value[0]) == false)
		return false;

	value_len = 8;

	return ( value2idx(value, value_len, idx) );
}

// Read next code from BitIO bits to code. 
// Input:  BitIO bits
//         int   max_len ,  the maxium number of bits that code can contain.
// Output: char  * code. 
//         int   & code_len, 
//         int   & idx, the index for the code in the tree.  
// Return: true, success
//         false, failure
bool AdaHuffTree::next_code(BitIO * bits, char * code, int max_len, int & code_len, int & idx)
{
	if (this->used == 1)  { // only NYT in the tree
		idx = this->nyt_idx;
		this->get_nyt_code(code, code_len);
		return true;
	}

	int node_idx = 0;  // 0 is idx of root
	int i;
	for (i=0; i < max_len; i++) { 
		// switch (bits->ReadABit(code, i))
		switch (bits->ReadABit())   // It's not necessary to read data to variable 'code'. 
		{
		case 1:  // right sub-tree
			node_idx = this->t[node_idx].rchild;
			break;
		case 0:          // left sub-tree
			node_idx = this->t[node_idx].lchild;
			break;
		case -1:
		default:
			return false;
		} 

		if (this->t[node_idx].rchild == -1 && this->t[node_idx].lchild == -1)  { // no child 
			break;
		}
	}

	idx = node_idx;

	code_len = i+1;

/*	// set the last bit of code to zero
	int byte_idx = i / 8;
	int bit_idx  = i % 8;

	unsigned char mask[8] =   // 8, hard coding, shw
	{
		(char) 1,
		(char) 2,
		(char) 4,
		(char) 8,
		(char) 16,
		(char) 32,
		(char) 64,
		(char) 128
	};

	code[byte_idx] |= (~mask[bit_idx]); 
*/
	return true;
}

// Read next FIXED code from BitIO bits to code. 
// Input:  BitIO bits
// Output: char  * code. 
//         int   & code_len, 
//         int   & idx, the index for the code in the tree.  
// Return: true, success
//         false, failure
inline bool AdaHuffTree::next_fixed_code(BitIO * bits, char * code, int & code_len)
{
	if (bits->ReadAByte(code[0]) == false) { // NT_REVISITED, suppose that fixed code have fixed lenth of 8 bits.
		code_len = 0;
		return false;
	}

	code_len = 8;
	return true;
}

inline bool AdaHuffTree::idx2value(int idx, char * value, int & value_len)
{
	// take NYT as an ordinary node, NT_REVISITED, may occur error
	// assert(idx != this->nyt_idx);   // for debug
	value_len = this->t[idx].value_len;
	memcpy(value, this->t[idx].value, (value_len-1)/8+1 );
	return true;
}

inline bool AdaHuffTree::fixed_value(char * code, int code_len, char * value, int & value_len)
{
	// for the time being, the function just simplely suppose that code be equal to value. NT_REVISITED
	// no fixed code for NYT
	memcpy(value, code, (code_len-1)/8 +1 );
	value_len = code_len; 
	return true;
}

bool AdaHuffTree::idx2code(int idx, char * code, int & code_len)
{

	if (idx == this->nyt_idx) {
		this->get_nyt_code(code, code_len);
	} else {
	    char value[4];
	    int value_len;
    	idx2value(idx, value, value_len);
	    int ct_idx = value2ct_idx(value);
    	code_len = this->ct[ct_idx].code_len;   
	    memcpy(code, this->ct[ct_idx].un.code, (code_len-1)/8 +1); 
	}

	return true;
}

// 
inline bool AdaHuffTree::fixed_code(char * value, int value_len, char * code, int & code_len)
{   // now, the function is similar to idx2code.
	code_len = this->ct[value2ct_idx(value)].code_len;   
	memcpy(code, this->ct[value2ct_idx(value)].un.code, (code_len-1)/8 +1); 
	return true;
}

inline bool AdaHuffTree::get_nyt_code(char * nyt, int & nyt_len)
{
	nyt_len = this->ct[256].code_len;   // NT_REVISITED
	memcpy(nyt, this->ct[256].un.code, (nyt_len-1)/8 + 1);
	return true;
}

bool AdaHuffTree::AdjustByNextCode(BitIO * bits, char * value, int & value_len)
{
	int  idx = 0;
	char code[16];  // hard coding. 
	int  code_len = 0;
	memset(code, 0, sizeof(code));

	if (this->next_code(bits, code, sizeof(code)*8, code_len, idx) == false) 
		return false;

	if (idx != this->nyt_idx) {   // if found
		this->idx2value(idx, value, value_len);
		this->adjust(idx);
	} else {      // if not found    NT_REVISITED
		if (this->next_fixed_code(bits, code, code_len) == false)
			return false;
		this->fixed_value(code, code_len, value, value_len);
		this->add_new_node(value, value_len);
	}

//	CompareWithOriginal(value);  // for debug
	this->PrintLog("End of AdjustByNextCode");   // for debug

//	this->CheckValid();

	return true;
}

void AdaHuffTree::CompareWithOriginal(char * value)  // for debug
{
	static flag=0;
	static fstream fs_in;	
	static long count = 1;

	if (!flag) {
    	fs_in.open("e:\\tmp\\05.mpga", ios_base::in | ios_base::binary);    // becomes "r" (open existing file for reading)
		flag = 1;
	}

	count++;
	char c;
	fs_in.get(c);
	assert(value[0]==c);
}

// Read next value from bits, and then adjust the tree by the value. Generate the code for the value.
// Input:  BitIO bits,
// Output: char  * code, 
//         int   & code_len, 
// Return: true,  procedure succeeds and doesn't ends. 
//         false, procedure completes or error occurs. 
bool AdaHuffTree::AdjustByNextValue(BitIO * bits, char * code, int & code_len)
{
	int  idx = 0;

	char value[4];
	int  value_len = 0;
	memset(value,0,sizeof(value));

	if (this->next_value(bits, value, 8*sizeof(value), value_len, idx) == false) { // read next value from bits
		return false;
	}

#ifdef MY_DEBUG
	printf("input: %c\n", value[0]);  // for debug
#endif

	if (idx != -1) {   // if found
		this->idx2code(idx,code, code_len); 
		this->adjust(idx);
	} else {          // if not found
		char nyt[16]; 
		int  nyt_len;
	    this->get_nyt_code(nyt, nyt_len);   // save old nyt
		this->fixed_code(value, value_len, code, code_len);
		BitOp::AddPrefix(code, code_len, nyt, nyt_len);
		this->add_new_node(value, value_len);
	}

	this->PrintLog("\nEnd of AdjustByNextValue");

	return true;
}

// Check the validility of the Huffman tree.
bool AdaHuffTree::CheckValid()
{
	int debug_flag = 0;

	if (!debug_flag)
		return true;

	int l, r, ct_idx;
	for (int i = 0; i < this->size; i++) {
		l = t[i].lchild;
		r = t[i].rchild;
		if (i > 0 && t[i].parent == -1)
			break;

		if (l != -1 && r != -1) {
			assert(t[l].parent == i && t[r].parent == i);
		} else {
			if (i != this->nyt_idx) {
				ct_idx = this->value2ct_idx(t[i].value);
			} else {
				ct_idx = 256;
			}
			assert(ct[ct_idx].idx == i);
		}
		
	}

	return true;
}


//  Input:   int  idx; 
//           int  max_len; length by bits 
//  Output:  char * code;   the generated code
//           int  & code_len;   the lenth of the generated code (by bits)
//  Note: The space of o_buf should be allocate by invoker
//        the output is just for testing, not present by bits now!!
bool AdaHuffTree::get_code_from_tree(int idx, char * code, int max_len, int &code_len)
{
	// In this function, take NYT as an ordinary node.

	unsigned char mask[8] =   // 8, hard coding, shw
	{
		(unsigned char) 1,
		(unsigned char) 2,
		(unsigned char) 4,
		(unsigned char) 8,
		(unsigned char) 16,
		(unsigned char) 32,
		(unsigned char) 64,
		(unsigned char) 128
	};

	if (idx < 0 || idx > this->size -1)
		return false;

	code_len = 0;
	int i = idx;
assert(i!=-1);	
	while (i != 0) {
		assert(i!=-1);
	    code_len++;	
		i = this->t[i].parent;
	}
	
	if (code_len > max_len)
		return false;

	int j = code_len - 1;
	int byte_idx = j / 8;
	int bit_idx = j % 8;