lzw.cpp

用C++语言编译的LZW压缩算法

//:LZW.cpp
#include "LZW.h"
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;

LZW::LZW()
{
	codes = new long[MaxSize];

	for(int i = 0; i < ASCII_SIZE; i++)
		codes[i] = i;

	size = ASCII_SIZE;
	preffix = false;
}//end constructor

LZW::~LZW()
{
	delete []codes;
}//end destructor

void LZW::compact(const string& name)
{
	string outFile = name;
	outFile.append(".zzz");
	ifstream in;
	in.open(name.c_str(), ios::binary);
	ofstream out;
	out.open(outFile.c_str(), ios::binary);

	if(!in)
		throw LZWException("Can't open input file!");

	if(!out)
		throw LZWException("Can't creat file!");

	unsigned char c;
	in >> c;
	long item = c;
	int code = item;

	//Make in ifstream not skip white place
	in >> noskipws;//Very important!
	//Read file and compact it
	while(in >> c)
	{
		item = (item << 8 | c);

		//If this item in the dictionary, continue and change it into code
		if(search(item, code))
			item = code;
		else
		{
			output(code, out);

			//Generate new code
			if(size < MaxSize)
				codes[size++] = item;

			item = c;
			code = c;
		}
	}

	search(item, code);
	output(code, out);

	//Output left
	if(preffix)
	{
		c = static_cast<char>(left << 4);
		out << c;
		preffix = false;
	}
}//end compact

void LZW::deCompact(const string& name)
{
	if(!name.find(".zzz", 0))
		throw LZWException("Not lzw compact file!");

	string outFile(name, 0, name.length()-4);
	outFile.insert(0, "LZW");
	ifstream in;
	in.open(name.c_str(), ios::binary);
	ofstream out;
	out.open(outFile.c_str(), ios::binary);

	unsigned char c;
	in >> c;
	unsigned int code = c;
	preffix = false;

	//Make in ifstream not skip white place
	in >> noskipws;//This manipulator is very important!
	while(in >> c)
	{
		if(preffix)
		{
			code = (code << 8) | c;
			deCode(code, out);

			if(in >> c)
				code = c;
			
			preffix = false;
		}
		else
		{
			code = (code << 4) | (c >> 4);
			deCode(code, out);
			code = c & 0x0F;
			preffix = true;
		}
	}
}//end deCompact

bool LZW::search(long item, int& code)
{
	for(int i = item >> 8; i < size; i++)
	{
		if(codes[i] == item)
		{
			code = i;
			return true;
		}
	}

	return false;
}//end search

void LZW::output(int code, ostream& out)
{
	if(preffix)
	{
		unsigned char c = (left << 4) | (code >> 8);
		out << c;
		c = code & 0x0FF;
		out << c;
		preffix = false;
	}
	else
	{
		left = code & 0x00F;
		unsigned char c = static_cast<char>(code >> 4);
		out << c;
		preffix = true;
	}
}//end output

void LZW::deCode(unsigned int code, ostream& out)
{
	unsigned char c;

	if(code < 0 || code >= size)
		throw LZWException("Out of bounds!");

	if(code < ASCII_SIZE)
	{
		c = static_cast<char>(codes[code]);
		out << c;
	}
	else
	{
		unsigned int pre = codes[code] >> 8;
		deCode(pre, out);
		c = static_cast<char>(codes[code] & 0xFF);
		out << c;
	}
}//end deCode