huffman.cpp

本工程编写了一个对任意文件进行 Huffman 编码的类.

// Huffman.cpp: implementation of the CHuffman class.
//
//////////////////////////////////////////////////////////////////////

#include "Huffman.h"
#include "BTree.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CHuffman::CHuffman()
{
	Initialize();
}

CHuffman::~CHuffman()
{

}

void CHuffman::Initialize()
{
	int i;
	for (i = 0; i < 256; i ++)
	{
		m_char[i] = 0;
		m_szCodeTable[i][0] = 0;
	}
	m_szFileName[0] = 0;
}

BOOL CHuffman::LoadFile(LPCTSTR lpszFileName)
{
	FILE *pFile = fopen(lpszFileName, "rb");
	if (NULL == pFile)
		return FALSE;

	strcpy(m_szFileName, lpszFileName);

	Process(pFile);
	fclose(pFile);

	int i, nNum = 0;
	int j = 0;
	BYTE szChar[256] = {0};
	LONG data[256] = {0};
	for (i = 0; i < 256; i ++)
	{
		if (m_char[i])
		{
			szChar[j] = i;
			data[j] = m_char[i];
			j ++;
			nNum ++;
		}
	}

	CBTree btree;
	btree.MakeBTree(szChar, data, nNum);
	btree.GetHuffmanCode(m_szCodeTable);

	return TRUE;
}

void CHuffman::Process(FILE *pFile)
{
	BYTE c;
	while (1)
	{
		fread(&c, 1, 1, pFile);
		if (feof(pFile))
			break;

		if (c < 0)
			c *= -1;
		m_char[c] ++;
	}
}

void CHuffman::SaveFile(LPCTSTR lpszFileName)
{
	// 1. 存储 Huffman 表
	FILE *pFile = fopen(lpszFileName, "wb");
	if (NULL == pFile)
		return;

	UINT i;
	BYTE nLen, cChar;
	for (i = 0; i < 256; i ++)
	{
		if (m_szCodeTable[i][0])
		{
			cChar = i;
			nLen = strlen(m_szCodeTable[i]);
			fwrite(&cChar, 1, 1, pFile);
			fwrite(&nLen, 1, 1, pFile);
			fwrite(m_szCodeTable[i], nLen, 1, pFile);
		}
	}

	// 2. 扫描待编码的文件, 实现编码
	FILE *pFile2 = fopen(m_szFileName, "rb");

	BYTE cRead;
	ULONG lCode = 0;		// 用于存放编码并写入
	BYTE nUsedBit = 0;		// 对 lCode 已使用了的位数
	while (1)
	{
		fread(&cRead, 1, 1, pFile2);
		if (feof(pFile2))
			break;

		WriteBitCode(cRead, lCode, nUsedBit, pFile);
	}
	if (nUsedBit)
		fwrite(&lCode, 4, 1, pFile);
	fwrite(&nUsedBit, 1, 1, pFile);

	fclose(pFile2);
	fclose(pFile);
}

void CHuffman::WriteBitCode(BYTE c, ULONG &lCode, BYTE &nUsedBit, FILE *pFile)
{
	ULONG uTemp = 0;
	int i, nLen;
	nLen = strlen(m_szCodeTable[c]);
	for (i = 0; i < nLen; i ++)
	{
		uTemp = uTemp << 1;
		if (m_szCodeTable[c][i] == '1')
			uTemp = uTemp | 1;

		if (i != 0 && i % 31 == 0)
		{
			fwrite(&uTemp, 4, 1, pFile);
			uTemp = 0;
		}
	}
	if (i % 32 != 0)
	{
		// 还有余位
		BYTE nRemain = i % 32;
		if (nUsedBit + nRemain >= 32)
		{
			// 再写 4 个字节
			lCode = lCode << (32 - nUsedBit);
			ULONG t1 = uTemp << (32 - nRemain);
			t1 = t1 >> nUsedBit;
			lCode = lCode | t1;
			fwrite(&lCode, 4, 1, pFile);
			lCode = uTemp << (32 - nRemain);
			lCode = lCode << (32 - nUsedBit);
			lCode = lCode >> (64 - nRemain - nUsedBit);
			nUsedBit = 32 - (64 - nRemain - nUsedBit);
			return;
		}
		else
		{
			lCode = lCode << (32 - nUsedBit);
			uTemp = uTemp << (32 - nUsedBit - nRemain);
			lCode = lCode | uTemp;
			nUsedBit = nUsedBit + nRemain;
			return;
		}
	}
}