lzwcompression.cpp

LZW是一种常用的压缩算法,可以直接下载来对某些数据进行压缩

// LZWCompression.cpp: implementation of the CLZWCompression class.
//
//////////////////////////////////////////////////////////////////////

/*
	Created by: Luria Israel

  This project implements the use of a dynamic LZW compression.
  This code is free for use, and can be inserted into any MFC project.
*/

#include "stdafx.h"
#include "LZWCompression.h"
#include "CSPcompressDlg.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

CLZWCompression::CLZWCompression(CCSPcompressDlg * p)
{
	Init();
	this->parent=p;

	//	The Maximum code for a bit
	m_MaxCode[0]		= 0;
	m_MaxCode[1]		= 0x1;
	m_MaxCode[2]		= 0x3;
	m_MaxCode[3]		= 0x7;
	m_MaxCode[4]		= 0xF;
	m_MaxCode[5]		= 0x1F;
	m_MaxCode[6]		= 0x3F;
	m_MaxCode[7]		= 0x7F;
	m_MaxCode[8]		= 0xFF;
	m_MaxCode[9]		= 0x1FF;
	m_MaxCode[10]		= 0x3FF;
	m_MaxCode[11]		= 0x7FF;
	m_MaxCode[12]		= 0xFFF;
	m_MaxCode[13]		= 0x1FFF;
	m_MaxCode[14]		= 0x3FFF;
	m_MaxCode[15]		= 0x7FFF;
	m_MaxCode[16]		= 0xFFFF;
	m_MaxCode[17]		= 0x1FFF;
	m_MaxCode[18]		= 0x3FFFF;
	m_MaxCode[19]		= 0x7FFFF;
	m_MaxCode[20]		= 0xFFFFF;
	m_MaxCode[21]		= 0x1FFFFF;
	m_MaxCode[22]		= 0x3FFFFF;
	m_MaxCode[23]		= 0x7FFFFF;
	m_MaxCode[24]		= 0xFFFFFF;
	m_MaxCode[25]		= 0x1FFFFFF;
	m_MaxCode[26]		= 0x3FFFFFF;
	m_MaxCode[27]		= 0x7FFFFFF;
	m_MaxCode[28]		= 0xFFFFFFF;
	m_MaxCode[29]		= 0x1FFFFFFF;
	m_MaxCode[30]		= 0x3FFFFFFF;
	m_MaxCode[31]		= 0x7FFFFFFF;

}

void CLZWCompression::Init()
{
//	m_dictionary = NULL;
	m_SavedData = 0;
	m_TotalBits = 0;
	m_MaxBits = 9;
}

CLZWCompression::~CLZWCompression()
{
	ClearDictionary();
}

//	This function was added to send log information to the view

//	Create a new dictionary
void CLZWCompression::CreateDictionary()
{
	m_dictionary = new CDictionary;
}

//	Remove the existing dictionary
void CLZWCompression::ClearDictionary()
{
	if (m_dictionary != NULL)
	{
		delete[] m_dictionary;
		m_dictionary = NULL;
	}
}

BOOL CLZWCompression::Compress(unsigned char **p,CFile &destination)
{
//	parent->bytecount=0;
	long prefix = 0;
	long result = 0;
	BYTE readByte = 0;
//	CString logString;
	DWORD resAdd = 256;
	int n=0,all=0;
//    ofstream out("result.txt", ios::app);
	//	Initialize the neccessry data
	Init();

	//	Get the total file size
//	filetotal = source.GetLength();

	//	Create the dictionary (if not created already)
	if (m_dictionary == NULL)
	{
		CreateDictionary();
	}


//	int v=m_dictionary->GetSize();
	//	Read the first byte from the file
	prefix=p[0][0];

	parent->m_pro.SetRange(0,10);
	parent->m_pro.SetPos(0);
	int t,re;

	//	Go over the rest of the file and read it
  for(int i=0;i<parent->ImageY;i++)
	  for(int j=(i?0:1);j<parent->ImageX;j++)
	{
		t=(((i+1)*parent->ImageX+j+1)*10)/(parent->ImageX*parent->ImageY);
        parent->m_pro.SetPos(t);
		parent->UpdateData(false);
		//	Read the second byte
		readByte=p[i][j];

		//	Check if the prefix and readByte combination exist in the dictionary
		result = m_dictionary->GetEntry(prefix, readByte);
        //若找到返回相应的字符串，若没找到返回－1;
		//	If not exist
		if (result == -1)
		{
			all++;
			if(re<=max&&re>255)
				n++;
			//	Add the new combination
			resAdd = m_dictionary->AddEntry(prefix, readByte);
			//	Calculate the new bit size needed to encode the file
			CalculateBitSize(resAdd);

			//	To show a log in the view
//			logString.Format("Adding combination of %d and %d to dictionary to entry %d.",
//				prefix, readByte, resAdd);
//			Log(logString);

			//	Send the prefix for compression in to the destination file
			CompressData(destination, prefix);

			//	Set the prefix as the readByte
			prefix = readByte;

			//	Initiate the result
			result = -1;
		}
		else
		{
			re=result;
			//	Set the prefix as the result
			prefix = result;
			readByte = 0;
		}
	}
//	  out<<"字典总大小:"<<(int)(255+m_dictionary->GetSize())<<endl;
//	  out<<"匹配个数:"<<n<<endl;
//      out<<"总匹配个数:"<<all<<endl;
	//	Compress the remaining information in the refix into the destination file
	CompressData(destination, prefix);
	//	Close the destination file
	CloseCompressedFile(destination);

	//	Remove the existing dictionary
	ClearDictionary();
	return TRUE;
}

void CLZWCompression::CompressData(CFile &dest, long toSave)
{

	/////将新的二进制串与缓冲区内的二进制串进行接合；；；
	DWORD writeData = 0;

	//	Move the data you want to write few bits to the left
	//	and combine it with the already existing data in the buffer
	m_SavedData |= (DWORD) toSave << (32 - m_MaxBits - m_TotalBits);

	//	Add the new added number of bits to the total bits counter
	m_TotalBits += m_MaxBits;

	//	Check if it's possible to enter the data to the file
	//	(over and equal a byte of data)
	while (m_TotalBits >= 8)
	{
		//	Get the byte we want to write
		writeData = m_SavedData;
		writeData >>= 24;
		dest.Write(&writeData, 1);
		parent->bytecount++;
		//	remove the byte from the buffer
		m_SavedData <<= 8;
		//	Remove the byte from the counter
		m_TotalBits -= 8;
	}
}

BOOL CLZWCompression::Decompress(CFile &source, CFile &destination)
{
	DWORD prefix = 0, data = 0;
	CString logString;
	CByteArray decodeString;
	BYTE writeData = 0, character = 0;
	int counter = 0;

	Init();

	//	Create the dicionary (if not already created)
	if (m_dictionary == NULL)
	{
		CreateDictionary();
	}

	//	Get the first prefix information
	prefix = DecompressData(source);
	//	Save the prefix as the last used character (since we're writing it in the
	//	destination file)
	character = (BYTE)prefix;
	//	Write the prefix in the destination file (the first byte inside
	//	a LZW copressed file is always the first byte of the original file)
	destination.Write(&prefix, 1);

	//	While the recieve data is not the maximum bit data possible
	while ((data = DecompressData(source)) != m_MaxCode[m_MaxBits])
	{
		//	Check if the code exist in the dictionary
		//	if not
		if (!m_dictionary->IsCodeExist(data))
		{
			//	Get the last used character into the decod buffer
			decodeString.Add((BYTE)character);
			//	Decode the existing prefix into a known string of data
			m_dictionary->GetBytesFromCode(&decodeString, prefix);
		}
		else
		{
			//	Decode the data into the decode buffer
			m_dictionary->GetBytesFromCode(&decodeString, data);
			//	Get the last letter inside the data, as the last used letter
			character = decodeString.GetAt(decodeString.GetSize() - 1);
		}

		//	Go over the decode buffer, from the end to the start,
		//	and write the information into the destination file
		counter = decodeString.GetSize();
		while (counter > 0)
		{
			writeData = (BYTE)decodeString.GetAt(--counter);
			destination.Write(&writeData, 1);

			//	To show a log in the view

			//	This commented addition was added as suggested by WREY from www.codeproject.com
//			logString.Format("Adding character code %d with know visualisation of: %s"
//				, writeData, convertASCIIToText(writeData));
//			logString.Format("Adding byte %d to file.", writeData);
//			Log(logString);
		}

		//	Clear the decode buffer
		decodeString.RemoveAll();

		//	Add the new combination into the dictionary
		m_dictionary->AddEntry(prefix, (BYTE)character);
		//	Calculate the new buffer size to read now
		CalculateBitSize(m_dictionary->GetMaxCode()+1);

		//	Set the new prefix to use
		prefix = data;
	}
	return TRUE;
}

DWORD CLZWCompression::DecompressData(CFile &source)
{
	DWORD returnValue;
	BYTE readByte = 0;

	//	If the source file still contains information
	if (source.GetPosition() < source.GetLength())
	{
		//	check if the number of bits in the read buffer is >= 24
		while (m_TotalBits <= 24)
		{
			//	Read one byte
			source.Read(&readByte, 1);

			//	Add the byte to the read buffer
			m_SavedData |= (DWORD) readByte << (24 - m_TotalBits);
			//	Add byte to the bit counter
			m_TotalBits += 8;
		}
	}
	else
	{
		//	If there is no more data, and there are no more bits to read
		//	while the file is over, then return the maximum bit number
		//	to end the decompression process
		if (m_SavedData == 0 && m_TotalBits == 0)
			return m_MaxCode[m_MaxBits];
	}

	//	calculate the return information
	returnValue = m_SavedData >> (32 - m_MaxBits);
	//	Remove the returned information from the buffer
	m_SavedData <<= m_MaxBits;
	//	Remove the return information bit size from the bit counter
	m_TotalBits -= m_MaxBits;

	//	Return the data
	return returnValue;
}

void CLZWCompression::CloseCompressedFile(CFile &source)
{
	//	Insert to the file the maximum number of bit (for signaling the end of the
	//	compression\decompression)
	CompressData(source, m_MaxCode[m_MaxBits]);
	//	Flash the rest of the file with 0
	CompressData(source, 0);
}

void CLZWCompression::CalculateBitSize(DWORD value)
{
	//////计算value的位数
	//	Check the value of the parameter against the Maximum number possible
	//	and then returns the counter

	//	This can also be acheived by right shifting the value until we get 0
	//	and counting the number of times we doing it.

	BYTE counter;

	for (counter = 0; counter < 32; counter++)
	{
		if (value <= m_MaxCode[counter])
			break;
	}
	m_MaxBits = counter;

	//	Since the minimal number of bits we are using is 9 (256 is the begining of the dictionary), 
	//	then the minimal number of bits is check to return a 9 in case a lower value will be
	//	reached in the application
	if (m_MaxBits < 9)
		m_MaxBits = 9;
}

//	Added for using the log from the application


CString CLZWCompression::convertASCIIToText(BYTE ascii)
{
	//	Those are the values I know of.
	//	If you know others then just add then to this function.
	CString rValue;

	switch (ascii)
	{
	case 8:		//	Backspace
		rValue = "Backspace";
		break;
	case 9:		//	TAB
		rValue = "TAB";
		break;
	case 10:	//	Line Feed
		rValue = "Line Feed";
		break;
	case 12:	//	Form Feed
		rValue = "Form Feed";
		break;
	case 13:	//	Enter
		rValue = "Enter";
		break;
	case 32:	//	Space
		rValue = "Space";
		break;
	case 127:	//	Delete
		rValue = "Delete";
		break;
	default:
		rValue = "There is no visual character associated with this code";
		break;
	}

	if ((ascii >= 33) && (ascii <= 126))
		rValue.Format("%c", ascii);

	return rValue;
}