huffman.cpp

Huffman/RLE archivator

#include "stdafx.h"
#include <fcntl.h>
#include <io.h>
#include "compressing.h"


void CompressHuffman(CString fileName, CString archName)
{
	SymbolInfo symbols[256];
	FILE *in = _wfopen(fileName, L"rb"); 
	FILE *out = _wfopen(archName, L"wb");

	int speciesCount = 0;
	unsigned char temp1;

	// Array of species initialization
	for (int i = 0; i < 256; i++)
	{
		symbols[i].length = 0;
		symbols[i].mask = 0;
		symbols[i].rate = 0;
	}

	//Reading symbols to array
	while (fread(&temp1, 1, 1, in) > 0)
	{
		symbols[temp1].rate++;
	}
	
	// Queue for tree forming
	TQueue myQueue;
	InitQueue(&myQueue, symbols, &speciesCount);

	if (speciesCount!=0)
	{
		// forming tree
		TreeForm(&myQueue);

		TNode *tree;
		if (myQueue.size() == 1)
		{
			tree = myQueue.top();
			myQueue.pop();
		}

		TreeRun(symbols, tree, 0, 0);

		if (tree->real == true)
			symbols[tree->name].length = 1;

		// Writing to file
		WriteRatesToFile(out, symbols, speciesCount);
		WriteBytesToFile(in, out, symbols);

	}
	fclose(in);
	fclose(out);
}

//////////////////////////////////////////////////////////////////////////

void DecompressHuffman(CString archName, CString fileName)
{
	SymbolInfo symbols[256];
	FILE *in = _wfopen(archName, L"rb");
	FILE *out = _wfopen(fileName, L"wb");

	int speciesCount=0;

	for (int i = 0; i < 256; i++)
	{
		symbols[i].length = 0;
		symbols[i].mask = 0;
		symbols[i].rate = 0;
	}

	ReadRatesFromArch(in, symbols);

	TQueue myQueue;

	InitQueue(&myQueue, symbols, &speciesCount);
	
	if (speciesCount != 0)
	{
		// forming tree
		TreeForm(&myQueue);

		TNode *tree;
		if (myQueue.size() == 1)
		{
			tree = myQueue.top();
			myQueue.pop();
		}

		unsigned long long totalBytes = 0;
		for (int i=0; i<256; i++)
		{
			if (symbols[i].rate !=0 )
			{
				totalBytes += symbols[i].rate;
			}
		}

		ReadBytesFromArch(in, out, tree, totalBytes);
	}
	fclose(in);
	fclose(out);
	
}

void InitQueue(TQueue *myQueue, SymbolInfo symbols[256], int *speciesCount)
{
	for (int i = 0; i < 256; i++)
	{
		if (symbols[i].rate != 0)
		{
			TNode *newNode = new TNode;
			InitNode(newNode, i, symbols[i].rate, NULL, NULL, NULL);
			newNode->real = true;
			myQueue->push(newNode);
			(*speciesCount)++;
		}
	}
}

void InitNode(TNode* newNode, unsigned char name, unsigned int rate, 
			  TNode *parent, TNode *left, TNode *right)
{
	newNode->left = left;
	newNode->right = right;
	newNode->parent = parent;
	newNode->name = name;
	newNode->rate = rate;
	newNode->real = false;
}

void TreeForm(TQueue *myQueue)
{
	while (myQueue->size() > 1)
	{
		TNode *node1 = myQueue->top();
		myQueue->pop();
		TNode *node2 = myQueue->top();
		myQueue->pop();
		TNode *newNode = new TNode;
		InitNode(newNode, 0, node1->rate + node2->rate, NULL, node1, node2);
		node1->parent = newNode;
		node2->parent = newNode;
		myQueue->push(newNode);
	}
}

void TreeRun(SymbolInfo symbols[256], TNode *curNode, unsigned long long mask, int length)
{
	if (curNode != NULL)
	{
		if (curNode->real)
		{
			symbols[curNode->name].mask = mask;
			symbols[curNode->name].length = length;
		}
		TreeRun(symbols, curNode->left, mask<<1, length+1);
		TreeRun(symbols, curNode->right, mask<<1 | 1, length+1);
	}
}

void WriteRatesToFile(FILE *file, SymbolInfo symbols[256], int count)
{
	if (count == 0)
		return;
	unsigned char temp1;
	unsigned char temp2 = count-1;
	fwrite(&temp2, 1, 1, file);
	for (int i=0 ; i < 256; i++)
	{
		if (symbols[i].rate != 0)
		{
			temp1 = i;
			fwrite(&temp1, 1, 1, file);
			fwrite(&(symbols[i].rate), 4, 1, file);
		}
	}
}

void WriteBytesToFile(FILE *in, FILE *out, SymbolInfo symbols[256])
{
	fseek(in, 0, SEEK_SET);
	unsigned long long currCode=0;
	int lengthCur = 0;
	unsigned char writtenChar;
	unsigned char temp1;

	while (fread(&temp1, 1, 1, in) > 0)
	{
		currCode = currCode | ((symbols[temp1].mask) << (64 - lengthCur - symbols[temp1].length));

		lengthCur += symbols[temp1].length;
		while (lengthCur >= 8)
		{
			writtenChar = currCode >> 56;
			currCode <<= 8;
			lengthCur -= 8;
			fwrite( &writtenChar, 1, 1, out);
		}
	}
	if (lengthCur > 0)
	{
		writtenChar = currCode >> 56;
		currCode >>= 8;
		fwrite( &writtenChar, 1, 1, out);
	}
}

void ReadRatesFromArch(FILE *file, SymbolInfo symbols[256])
{
	unsigned char temp1;
	unsigned int temp2;
	int count;
	if (fread(&temp1, 1, 1, file) >0)
	{
		count = temp1 + 1;
		for (int i = 0; i < count; i++)
		{
			fread(&temp1, 1, 1, file);
			fread(&temp2, 4, 1, file);
			symbols[temp1].rate = temp2;
		}
	}
}

void ReadBytesFromArch(FILE *in, FILE *out, TNode *tree ,unsigned long long totalBytes)
{
	int flag;
	int counter = 8;
	unsigned char mask;
	unsigned char temp1;
	unsigned long long bytes = 0;

	TNode *curNode = tree;
	do
	{
		flag = fread(&temp1, 1, 1, in);
		mask = (unsigned char) 1 << 7;

		for(int i=0; i<counter; i++)
		{
			if (curNode->real)
			{
				fwrite(&curNode->name, 1, 1, out);
				curNode = tree;
				if (++bytes == totalBytes)
				{	
					flag = -1;
					break;
				}
			}
			if (mask & temp1)
				curNode = curNode->right;
			else if (curNode->left != NULL)
				curNode = curNode->left;
			mask >>= 1;
		}
	} while ( flag > 0);
}