adahuff.h

自适应huffman编码

//  shw, 2005.09.28, 

#ifndef _AdaHuff_H_
#define _AdaHuff_H_

#include "stdafx.h"

#include "DataCompression.h"

typedef struct _AHTreeNode_ {
    char    value[4];  // now, it's just for a byte, NT_REVISITED, shw
	int     value_len; // by bits
	int     weight;
	int     parent; 
	int     lchild;
	int     rchild;
} AHTreeNode; 

typedef struct _CodeTbNode_
{
	int   idx;         // the index of the code in adaptive huffman tree.
	union u {
		unsigned long   l;
	    char   code[4]; // NT_REVISISTED
	} un;

    char   code_len;   // length of code by bits
} CodeTbNode;


class AdaHuffTree 
{
public:
	AdaHuffTree(void);
	~AdaHuffTree(void);
	void Init(int tsize);
	bool AdjustByNextValue(BitIO * bits, char * code, int & code_len);
	bool AdjustByNextCode(BitIO * bits, char * value, int & value_len);
//	bool GetValue(char * code, int code_len, char * value, int & value_len);
//	bool GetCode(char * value, int code_len, char * code, int & code_len);
	void SetDebugMode(int mode);
	bool CheckValid();

private: 
    AHTreeNode  * t;
	CodeTbNode  * ct;
//	CodeTbNode    nyt;
	int nyt_idx;
//	char nyt_code[4]; 
//	int nyt_code_len;
	int size;   //  num of tree nodes.
	int used;   //  num of used tree nodes.
	int debug_mode;

	bool next_code(BitIO * bits, char * code, int max_len, int & code_len, int & idx);
	bool next_fixed_code(BitIO * bits, char * code, int & code_len);
	bool next_value(BitIO * bits, char * value, int max_len, int & value_len, int & idx);
    bool idx2value(int idx, char * value, int & value_len);
	inline bool value2idx(char * value, int value_len, int & idx) {idx = this->ct[(unsigned char)value[0]].idx; return true; }; // only for 8 byte value now.
	inline int value2ct_idx(char * value) { return *((unsigned char*)value); };  // NT_REVISITED
    bool fixed_value(char * code, int code_len, char * value, int & value_len);
    bool idx2code(int idx, char * code, int & code_len);
    bool fixed_code(char * value, int value_len, char * code, int & code_len);
	bool get_nyt_code(char * nyt, int & nyt_len);

	bool add_new_node(char * value, int value_len);

    bool get_code_from_tree(int idx, char * code, int max_len, int &code_len);
    bool adjust(int idx);
	bool rewrite_codes(int idx);
	void PrintLog(char * prompt);  // for debug
	void CompareWithOriginal(char * value);  // for debug
};

class CompressionHeader
{
public:
	CompressionHeader(void);
	~CompressionHeader(void);
	void Init(fstream * p_fs);
	bool ReadHeader(void);
	bool WriteHeader(void);
	unsigned long length;      // the length of data by bits
protected:
	fstream * fs;
};

class AdaHuffCoder :
	public Coder
{
public:
	AdaHuffCoder(void);
	~AdaHuffCoder(void);
	void Init(BitIO * bit_in, BitIO * bit_out);
	int  Run(void);
	bool GenNextCode();
	void SetDebugMode(int mode);
protected:
	AdaHuffTree  ada_huff_tree;
private:
	char in_bits[64];
	int  in_bits_len;
	char out_bits[64];
	int  out_bits_len;
};

class AdaHuffDecoder :
	public Coder
{
public:
	AdaHuffDecoder(void);
	~AdaHuffDecoder(void);
	void Init(BitIO * bit_in, BitIO * bit_out);
	bool GenNextCode();
	int  Run();
	void SetDebugMode(int mode);
protected:
	AdaHuffTree  ada_huff_tree;
private:
	char in_bits[64];
	int in_bits_len;
	char out_bits[64];
	int out_bits_len;
};

#endif