adahuff.cpp

自适应huffman编码

	i = idx;
	while(j >= 0) {
		if (this->t[t[i].parent].rchild == i)
			code[byte_idx] |= mask[bit_idx];  
		else
			code[byte_idx] &= (~mask[bit_idx]); 

		i = this->t[i].parent;
		j--;
		byte_idx = j/8;
		bit_idx = j%8;
	}

	return true;
}

bool AdaHuffTree::add_new_node(char * value, int value_len)
{
	// add new node to adaptive huffman tree
//	assert(this->used + 2 <= this->size);
	if (this->used + 2 > this->size)
		printf("Warning： this->used+2 > this->size!!\n");

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

	this->t[used - 1].lchild = used + 1;
	this->t[used - 1].rchild = used;
	this->t[used - 1].value[0] = 0;      // internal node, no meaning for value
	this->t[used - 1].value_len = 8;
	this->t[used - 1].weight = 1;  

	// increase the weights of all the ancestors nodes of t[used - 1];
//	int par = t[used-1].parent;
//	while (par >= 0) {
//		t[par].weight++;
//		par = t[par].parent;
//	};

	this->t[used].lchild = -1;
	this->t[used].rchild = -1;
	memcpy(this->t[used].value, value, (value_len-1)/8 +1);  // new node for new character
	this->t[used].value_len = value_len;
	this->t[used].parent = used - 1;
	this->t[used].weight = 1;
	// modify code for new character in ct (code table)
	char code[4];   // hard coding
	int  code_len;
	code[0] = code[1] = code[2] = code[3] = 0;
	this->get_code_from_tree(used, code, sizeof(code) * 8,code_len);
	int  ct_idx = this->value2ct_idx(value);
	this->ct[ct_idx].code_len = code_len;
	this->ct[ct_idx].idx = used;
#ifdef MY_DEBUG
	printf("%d\n", ct_idx);   // for debug
#endif
	memcpy(this->ct[ct_idx].un.code, code, sizeof(code));
	
	this->used++;

	this->t[used].lchild = -1;
	this->t[used].rchild = -1;
	this->t[used].value[0] = -1;  // NYT node
	this->t[used].value_len = 8;
	this->t[used].parent = used - 2;
	this->t[used].weight = 0;
	// modify code for NYT in ct (code table)
	code[0] = code[1] = code[2] = code[3] = 0;
	this->get_code_from_tree(used, code, sizeof(code) * 8,code_len);
	ct_idx = 256;    //  hard_coding, NT_REVISITED
	this->ct[ct_idx].code_len = code_len;
	this->ct[ct_idx].idx = used;
#ifdef MY_DEBUG
	printf("%d\n", ct_idx);   // for debug
#endif
	memcpy(this->ct[ct_idx].un.code, code, sizeof(code));
	this->nyt_idx = this->used;
	
	this->used++;

	this->PrintLog("\nbefore adjust in add_new_node");
	this->adjust(this->t[used - 3].parent);  // adjust the grandfather node of new node.

	return true;
}

// Adjust adaptive huffman tree when the weight of a node will be increased by 1. 
// Input:  int idx,  the index to the node. The node should not be NYT
// Return: true,  success
//         false, failure
bool AdaHuffTree::adjust(int idx)
{
	assert(idx != this->nyt_idx);
//	if (idx == this->nyt_idx)  // needn't to adjust NYT node
//		return true;
	this->PrintLog("start of adjust");  // for debug
	while (idx >= 0) {  // while t[idx] isn't root node.
		// 寻找adaptive huffman tree 中的相应节点
		int weight = (this->t[idx].weight);
		int new_idx = idx - 1;

		while (new_idx >= 0 && weight == this->t[new_idx].weight)
			new_idx--;

		new_idx++;

#ifdef MY_DEBUG
		printf("new_idx: %d\n", new_idx); // for debug
#endif
		if (new_idx >= 0 && new_idx != idx) {
			if (this->t[idx].parent == new_idx) { 
				; // this->t[new_idx].weight++;
			} else {// exchange two nodes
#ifdef MY_DEBUG
				printf("exchange %d & %d\n", idx, new_idx);  // for debug
#endif
				char temp_value[4];   // hard coding, NT_REVISISTED
				memcpy(temp_value, this->t[idx].value, sizeof(temp_value));
				int  temp_value_len = this->t[idx].value_len;
				int  temp_lchild    = this->t[idx].lchild;
				int  temp_rchild    = this->t[idx].rchild;
//				int  temp_parent = this->t[idx].parent;
				
//				int new_parent = this->t[new_idx].parent;
//				if (this->t[new_parent].lchild == new_idx)
//					this->t[new_parent].lchild = idx;
//				else
//					this->t[new_parent].rchild = idx;
				memcpy(this->t[idx].value, this->t[new_idx].value, sizeof(temp_value));
				this->t[idx].value_len = this->t[new_idx].value_len;
				int l = this->t[idx].lchild = this->t[new_idx].lchild;
				int r = this->t[idx].rchild = this->t[new_idx].rchild;
				if (l > 0)
				    this->t[l].parent = idx;
				if (r > 0)
				    this->t[r].parent = idx;
//				this->t[idx].parent = this->t[new_idx].parent;

//				if (this->t[temp_parent].lchild == idx)
//					this->t[temp_parent].lchild = new_idx;
//				else
//					this->t[temp_parent].rchild = new_idx;
				memcpy(this->t[new_idx].value, temp_value, sizeof(temp_value));
				this->t[new_idx].value_len = temp_value_len;
				this->t[new_idx].lchild = temp_lchild;
				this->t[new_idx].rchild = temp_rchild;
				if (temp_lchild > 0)
				    this->t[temp_lchild].parent = new_idx;
				if (temp_rchild > 0)
                    this->t[temp_rchild].parent = new_idx;

				// rewrite new codes of offspring leaf nodes of node idx.
				rewrite_codes(idx);
				rewrite_codes(new_idx);

				idx = new_idx; 
		        this->PrintLog("after exchange");  // for debug

			} // end of else
		}  // end of if


		this->t[idx].weight++; 
		idx = this->t[idx].parent;

	} // end of while

	return true;
}

bool AdaHuffTree::rewrite_codes(int idx)
{
	if(idx == -1)
		return true;

	int l = this->t[idx].lchild;
	int r = this->t[idx].rchild;
	if( l == -1 && r == -1) {
		char code[4];
		code[0] = code[1] = code[2] = code[3] = 0;
		int max_len = 8*sizeof(code);
		int code_len = 0, value_len = 0;
		char value[4];
		value[0] = value[1] = value[2] = value[3] = 0;
		this->get_code_from_tree(idx, code, max_len, code_len);

		int ct_idx;
		if (idx != this->nyt_idx) {
		    this->idx2value(idx, value, value_len);
		    ct_idx = this->value2ct_idx(value);
		} else {
			ct_idx = 256;  // hardcoding, NT_REVISITED
		}
		memcpy(this->ct[ct_idx].un.code, code, sizeof(code));
		this->ct[ct_idx].code_len = code_len;
		this->ct[ct_idx].idx = idx;
		return(true);
	} else {
		int flagl = rewrite_codes(l);
		int flagr = rewrite_codes(r);
		return (flagl && flagr);
	}
}

void AdaHuffTree::PrintLog(char * prompt)
{
//#ifdef MY_DEBUG
 	if (this->debug_mode) {
		printf("%s\n", prompt);
		printf("idx p   lc  rc  val  len  w\n");
		for (int i = 0; i < this->used; i++)
			printf("%3d %3d %3d %3d %3d %3d %3d\n", i, t[i].parent, t[i].lchild, t[i].rchild, t[i].value[0], t[i].value_len, t[i].weight);
	}
//#endif

   /* printf("\n");
	printf("idx len code\n");
	printf("%3d %3d %3d \n", ct['a'].idx, ct['a'].code_len, ct['a'].un.code[0]);
	printf("%3d %3d %3d \n", ct['b'].idx, ct['b'].code_len, ct['b'].un.code[0]);
	printf("%3d %3d %3d \n", ct['d'].idx, ct['d'].code_len, ct['d'].un.code[0]);
	printf("%3d %3d %3d \n", ct['s'].idx, ct['s'].code_len, ct['s'].un.code[0]);
	printf("%3d %3d %3d \n", ct[256].idx, ct[256].code_len, ct[256].un.code[0]);
	printf("\n");
	*/
	// for debug, end

}

CompressionHeader::CompressionHeader(void)
{
}

CompressionHeader::~CompressionHeader(void)
{
}

void CompressionHeader::Init(fstream * p_fs)
{
	this->fs = p_fs;
}

bool CompressionHeader::ReadHeader(void)
{
	union u {
		unsigned long   l;
	    char   str[4];   // NT_REVISISTED
	} un;

	this->fs->read(un.str, 4);

	if (this->fs->eof()) {
		this->length = 0;
		return false;
	} else {
		this->length = un.l;
	    return true;
	}
}

bool CompressionHeader::WriteHeader(void)
{
	this->fs->seekp(0);
	union u {
		unsigned long   l;
	    char   str[4];   // NT_REVISISTED
	} un;

	un.l = this->length;

	this->fs->write(un.str, 4);
	return true;
}

AdaHuffCoder::AdaHuffCoder(void)
{
}

AdaHuffCoder::~AdaHuffCoder(void)
{
}

void AdaHuffCoder::Init(BitIO * bit_in, BitIO * bit_out)
{ 
	Coder::Init(bit_in, bit_out);
	memset(this->in_bits,0, sizeof(in_bits));
	this->in_bits_len = 0;
	memset(this->out_bits,0, sizeof(out_bits));
	this->out_bits_len = 0;
	this->ada_huff_tree.Init(257 *2 -1);  // hard coding. 
}

bool AdaHuffCoder::GenNextCode()
{
	memset(this->out_bits, 0 ,sizeof(this->out_bits));
	this->out_bits_len = 0;
	if (!ada_huff_tree.AdjustByNextValue(this->bit_reader, this->out_bits, this->out_bits_len))
		return false;

	bit_writer->Write(this->out_bits, this->out_bits_len);

	return true;
}

int AdaHuffCoder::Run(void)
{
	bool flag = true;
	
	do {
		flag = GenNextCode();
	} while(flag);

	this->bit_writer->FlushEnd();

	return 0;
}

void AdaHuffCoder::SetDebugMode(int mode)
{
	this->ada_huff_tree.SetDebugMode(mode);
}


AdaHuffDecoder::AdaHuffDecoder(void)
{
}

AdaHuffDecoder::~AdaHuffDecoder(void)
{
}

bool AdaHuffDecoder::GenNextCode()
{
	memset(this->out_bits, 0, sizeof(this->out_bits));
	this->out_bits_len = 0;
	if (!ada_huff_tree.AdjustByNextCode(this->bit_reader, this->out_bits, this->out_bits_len))
		return false;

	bit_writer->Write(this->out_bits, this->out_bits_len);

	return true;
}

int AdaHuffDecoder::Run()
{
	bool flag = true;

	do {
		flag = GenNextCode();
	} while(flag);

	this->bit_writer->FlushEnd();

	return 0;
}

void AdaHuffDecoder::Init(BitIO * bit_in, BitIO * bit_out)
{
	Coder::Init(bit_in, bit_out);
	this->ada_huff_tree.Init(257 *2 -1);  // hard coding. 
}

void AdaHuffDecoder::SetDebugMode(int mode)
{
	this->ada_huff_tree.SetDebugMode(mode);
}