huffman.cpp

可以选择各种压缩方式对读入的图像进行压缩和解压

#include "stdafx.h"
#include "huffman.h"

using namespace std;

class huffmanEncode
{
public:
	huffmanEncode::huffmanEncode(codeListStruct *list, cltype n) //for AC
	{
		AC=1;
		codeListStruct *p=list; 
		codeListHead=list;
		//readFile(f);
		this->num = n;
		weights = new unsigned long[n];
		weights_sorted = new unsigned long[n];
		for(int i = 0; i < this->num; i++) {
			weights[i] = weights_sorted[i] = p->times;
			p=p->next;
		}
		//while (p){
		//	weights[i] = weights_sorted[i] = p->times;
		//	i++;
		//	p=p->next;
		//}
		qsort(weights_sorted, num, sizeof(weights_sorted[0]), weight_compare);
	}
	huffmanEncode::huffmanEncode(dcCodeList *dclist, cltype n) //for DC
	{
		AC=0;
		dcCodeList *tempP=dclist;
		dchead=tempP;

		this->num = n;
		weights = new unsigned long[n];
		weights_sorted = new unsigned long[n];

		for(int i = 0; i < this->num; i++) {
			weights[i] = weights_sorted[i] = tempP->count;
			tempP=tempP->next;
		}
		qsort(weights_sorted, num, sizeof(weights_sorted[0]), weight_compare);
	}
	virtual ~huffmanEncode()
	{
		delete[] weights;
		delete[] weights_sorted;
	}

	void run(huffman_base* p_huffman, bool dump)
	{
		unsigned long totalsum=0;
		unsigned long totalcodelength=0;
		try
		{
			//clock_t t1, t2;
			if (p_huffman->if_need_sorted())
			{				
				//t1 = clock();
				p_huffman->generate_codes(num, weights_sorted);
				//t2 = clock();
			}
			else
			{
				//t1 = clock();
				p_huffman->generate_codes(num, weights);
				//t2 = clock();
			}
			
			//cout << endl << typeid(*p_huffman).name() << " Cost " 
			//	 << double(t2 - t1) / CLOCKS_PER_SEC << "seconds!" << endl;

			if (!p_huffman->verify())
			{
				cout << endl << typeid(*p_huffman).name() 
					<< " 生成的Huffman树不正确，算法可能存在缺陷" << endl;
				return;
			}

			if (dump)
			{
				//cout << "Char\tTimes\tLength\tCode" << endl;
				vector<int> code_lens = p_huffman->get_all_code_lens();
				vector<string> codes = p_huffman->get_all_code_strs();
				codeListStruct *listp=codeListHead;
				dcCodeList *tempList=dchead;
				for(int i = 0; i < (int)codes.size(); i++)
				{
					////cout << FT[i+1].cap << "\t"; //notice this line!!!!
					/*if (p_huffman->if_need_sorted())
						cout << weights_sorted[i];
					else
						cout << weights[i];*/

					//cout  << "\t" << code_lens[i] << "\t" << codes[i] << endl; //for test use only, compare the result with list
					
					char * tempchar = new char[codes[i].length()+1];
					codes[i].copy(tempchar, codes[i].length());
					tempchar[codes[i].length()]='\0';
					//strcpy_s(tempchar, codes[i].c_str());
					
					if (AC) {
						listp->code=tempchar;
						listp=listp->next;
					}
					else {
						tempList->code=tempchar;
						tempList=tempList->next;
					}


					//totalsum+=FT[i+1].sum;
					//totalcodelength+=code_lens[i]*FT[i+1].sum;
				}
				//cout<<endl<<"Average code length: "<<double(totalcodelength)/totalsum<<endl;
				//cout << endl << "Time cost: " 
				// << double(t2 - t1) / CLOCKS_PER_SEC << " seconds!" << endl;
			}
		}
		catch(exception* e)
		{
			cout << endl << typeid(*p_huffman).name() << " 执行时错误: " << e->what() << endl;
			delete e;
		}
	}
private:
	int num;
	int AC;
	unsigned long* weights;
	unsigned long* weights_sorted;
	codeListStruct* codeListHead;
	dcCodeList* dchead;
	
	static int weight_compare(const void* a, const void* b)
	{
		if (*((unsigned long*)a) > *((unsigned long*)b))
			return 1;
		else if (*((unsigned long*)a) < *((unsigned long*)b))
			return -1;
		else
			return 0;
	}
};





void enCodeAC(codeListStruct *c, cltype n)
{	
	//FILE *stream;
	////fopen_s(&stream,"r");

	bool dump=true;
	huffmanEncode t(c,n);
	huffman_a ha; 	
	t.run(&ha, dump); 
}

void enCodeDC(dcCodeList *c, cltype n){
	bool dump=true;
	huffmanEncode t(c,n);
	huffman_a ha;
	t.run(&ha,dump);
}