#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include "HuffCompress.h"
#include "Server.h"

DWORD	dwWeight[256];
DWORD	dwCounts[256];
DWORD	dwByte[256];
DWORD	dwCodes[512];
DWORD	dwSymbols[256];
DWORD	dwMapping[256];
DWORD	dwByteTree[765];
WORD	wByteTree[765];
char	dwBitTree[765];
DWORD	dwRootIndex,dwCodeCount,dwStorage;
WORD	wTreeSize;

int		iElements,iTotalElements;

void HuffmanInitArrays()
{
	__asm
	{
		MOV		EDI,OFFSET dwWeight[0]
		MOV		ECX,256
		_InitWeight:
		MOV		DWORD PTR [EDI],0
		ADD		EDI,4
		DEC		ECX
		JNZ		_InitWeight
	}

	__asm
	{
		MOV		EDI,OFFSET dwBitTree[0]
		MOV		EAX,0
		MOV		ECX,255
		_InitBitTree:
		MOV		char PTR [EDI + EAX],2
		ADD		EAX,3
		DEC		ECX
		JNZ		_InitBitTree
	}
}

void HuffmanBuildArrays()
{
	__asm
	{
		MOV		ESI,OFFSET dwWeight[0]
		MOV		EDI,OFFSET dwByte[0]
		MOV		ECX,256
		_BuildByte:
		LODSD
		CMP		EAX,0
		JZ		_SkipByte
		MOV		EAX,256
		SUB		EAX,ECX
		STOSD

		_SkipByte:
		DEC		ECX
		JNZ		_BuildByte

		MOV		ESI,OFFSET dwWeight[0]

		MOV		ECX,256

		MOV		EDI,OFFSET dwCounts[0]

		_BuildCount:
		LODSD

		CMP		EAX,0

		JZ		_SkipCount

		STOSD

		_SkipCount:
		DEC		ECX
		JNZ		_BuildCount

		MOV		ESI,OFFSET dwCounts[0]
		SUB		EDI,ESI
		MOV		ECX,EDI
		SHR		ECX,2

		CMP		ECX,1
		JNE		_Exit

		MOV		EDI,OFFSET dwByte[0]

		MOV		EAX,256
		MOV		[EDI + ECX * 4],EAX

		MOV		EDI,OFFSET dwCounts[0]

		MOV		[EDI + ECX * 4],DWORD PTR 1

		INC		ECX

		_Exit:

		MOV		iElements,ECX
		MOV		iTotalElements,ECX
	}
}

void HuffmanBuildByteTree()
{
	DWORD	dwParentWeight,dwParentDesc;
	int		iStartPos = -3;
	BOOL	fInsert = TRUE;

	dwParentDesc = 1000;

	while (iElements > 1)
	{
		HuffmanQuickSortD(&dwCounts[0],&dwByte[0],0,iElements - 1);
		__asm
		{

			MOV		ESI,OFFSET dwCounts[0]

			MOV		EBX,iElements
			DEC		EBX

			MOV		iElements,EBX

			MOV		EAX,EBX
			DEC		EAX

			MOV		EDX,[ESI + EAX * 4]
			ADD		EDX,[ESI + EBX * 4]

			MOV		dwParentWeight,EDX

			MOV		ECX,iStartPos
			ADD		ECX,3

			MOV		iStartPos,ECX


			MOV		ESI,OFFSET dwByte[0]

			MOV		EDI,OFFSET dwByteTree[0]

			MOV		EDX,dwParentDesc
			MOV		[EDI + ECX * 4],EDX

			MOV		EDX,[ESI + EAX * 4]
			MOV		[EDI + ECX * 4 + 4],EDX
			MOV		EDX,[ESI + EBX * 4]
			MOV		[EDI + ECX * 4 + 8],EDX

			MOV		ESI,OFFSET dwCounts[0]
			MOV		EDX,dwParentWeight

			MOV		[ESI + EAX * 4],EDX

			MOV		ESI,OFFSET dwByte[0]

			MOV		EDX,dwParentDesc

			MOV		[ESI + EAX * 4],EDX

			INC		dwParentDesc
		}
	}

	__asm
	{
		MOV		ECX,iStartPos
		MOV		dwRootIndex,ECX
		ADD		ECX,3
		MOV		wTreeSize,CX
	}
}

void HuffmanQuickSortA(DWORD *pArray1,DWORD *pArray2,int iBegin,int iEnd)
{
	int		iLow,iHigh,iTemp;

	__asm
	{
		MOV		EAX,iBegin
		MOV		EBX,iEnd

		MOV		ESI,pArray1

		MOV		ECX,EAX
		ADD		ECX,EBX
		SHR		ECX,1
		MOV		EDX,[ESI + ECX * 4]

		_DoLoop:

		MOV		ESI,pArray1

		_OrderLow:
		MOV		EDI,EAX
		INC		EAX
		CMP		[ESI + EDI * 4],EDX
		JB		_OrderLow
		MOV		EAX,EDI

		_OrderHigh:
		MOV		EDI,EBX
		DEC		EBX
		CMP		[ESI + EDI * 4],EDX
		JA		_OrderHigh
		MOV		EBX,EDI

		CMP		EAX,EBX
		JG		_NoSwap

		MOV		ECX,[ESI + EAX * 4]
		MOV		EDI,[ESI + EBX * 4]
		MOV		[ESI + EAX * 4],EDI
		MOV		[ESI + EBX * 4],ECX

		MOV		ESI,pArray2
		MOV		ECX,[ESI + EAX * 4]
		MOV		EDI,[ESI + EBX * 4]
		MOV		[ESI + EAX * 4],EDI
		MOV		[ESI + EBX * 4],ECX

		INC		EAX
		DEC		EBX

		_NoSwap:
		MOV		iTemp,EBX
		CMP		EAX,iTemp
		JLE		_DoLoop

		MOV		iLow,EAX
		MOV		iHigh,EBX
	}

	if (iBegin < iHigh)
		HuffmanQuickSortA(pArray1,pArray2,iBegin,iHigh);

	if (iLow < iEnd)
		HuffmanQuickSortA(pArray1,pArray2,iLow,iEnd);
}

void HuffmanQuickSortD(DWORD *pArray1,DWORD *pArray2,int iBegin,int iEnd)
{
	int		iLow,iHigh,iTemp;

	__asm
	{
		MOV		EAX,iBegin
		MOV		EBX,iEnd

		MOV		ESI,pArray1

		MOV		ECX,EAX
		ADD		ECX,EBX
		SHR		ECX,1
		MOV		EDX,[ESI + ECX * 4]

		_DoLoop:

		MOV		ESI,pArray1

		_OrderLow:
		MOV		EDI,EAX
		INC		EAX
		CMP		[ESI + EDI * 4],EDX
		JA		_OrderLow
		MOV		EAX,EDI

		_OrderHigh:
		MOV		EDI,EBX
		DEC		EBX
		CMP		[ESI + EDI * 4],EDX
		JB		_OrderHigh
		MOV		EBX,EDI

		CMP		EAX,EBX
		JG		_NoSwap

		MOV		ECX,[ESI + EAX * 4]
		MOV		EDI,[ESI + EBX * 4]
		MOV		[ESI + EAX * 4],EDI
		MOV		[ESI + EBX * 4],ECX

		MOV		ESI,pArray2
		MOV		ECX,[ESI + EAX * 4]
		MOV		EDI,[ESI + EBX * 4]
		MOV		[ESI + EAX * 4],EDI
		MOV		[ESI + EBX * 4],ECX

		INC		EAX
		DEC		EBX

		_NoSwap:
		MOV		iTemp,EBX
		CMP		EAX,iTemp
		JLE		_DoLoop

		MOV		iLow,EAX
		MOV		iHigh,EBX
	}

	if (iBegin < iHigh)
		HuffmanQuickSortD(pArray1,pArray2,iBegin,iHigh);

	if (iLow < iEnd)
		HuffmanQuickSortD(pArray1,pArray2,iLow,iEnd);
}

void HuffmanBuildCodes()
{
	DWORD	dwCodeBits;
	DWORD	dwLeafNode;

	__asm
	{
		MOV		dwCodeCount,0;

		MOV		ECX,0

		MOV		EDX,dwRootIndex

		MOV		ESI,OFFSET dwBitTree[0]
		MOV		EDI,OFFSET dwByteTree[0]

		MOV		dwCodeBits,0

		_WhileLoop:

		MOV		EAX,0
		MOV		AL,[ESI + EDX]

		DEC		[ESI + EDX]

		CMP		EAX,0
		JE		_FindParent

		ADD		EDX,EAX
		MOV		EBX,[EDI + EDX * 4]
		SUB		EDX,EAX

		ADD		ECX,ECX

		CMP		EAX,2
		JNE		_SkipOr
		OR		ECX,1
		_SkipOr:

		INC		dwCodeBits

		CMP		EBX,256
		JLE		_LeafNode

		_SubIndex:
		SUB		EDX,3
		CMP		EBX,[EDI + EDX * 4]
		JNE		_SubIndex

		JMP		_WhileLoop

		_LeafNode:

		PUSH	EDX

		// Point to the Codes Array
		MOV		EAX,OFFSET dwCodes[0]

		// Set the Bit Count of the Symbol to the Code Array
		MOV		EDX,dwCodeBits
		MOV		[EAX + 1024 + EBX * 4],EDX

		// Set the Symbol to the Code Array
		MOV		[EAX + EBX * 4],ECX

		// Save the Leaf Node
		PUSH	ECX
		MOV		ECX,EBX
		MOV		dwLeafNode,ECX

		// Get the Current Index to the Codes Array
		MOV		EBX,dwCodeCount

		// Point to the Symbol Mapping Array
		MOV		EAX,OFFSET dwMapping[0]

		// Set the Mapping of the Symbol to the Code Array
		MOV		[EAX + EBX * 4],ECX

		// Restore the Leaf Node
		POP		ECX

		// Point to the Code Symbol Array
		MOV		EAX,OFFSET dwSymbols[0]

		// Set the Symbol to the Code Array
		MOV		[EAX + EBX * 4],ECX

		// Increment the Code Count
		INC		EBX
		MOV		dwCodeCount,EBX

		// Restore the Leaf Node
		MOV		EBX,dwLeafNode

		// Restore the Index
		POP		EDX

		// Decrement the Number of Bits in the Code
		DEC		dwCodeBits

		// Decrement the Bits
		SHR		ECX,1

		// Loop Back for Another Node
		JMP		_WhileLoop

		// Find the Parent Index of the Parent
		_FindParent:

		// Get the Current Parent
		MOV		EAX,dwRootIndex
		MOV		EBX,[EDI + EDX * 4]

		// Check the Children of the Parent for a Match
		_AddIndex:

		ADD		EDX,3
		// Check for Completion
		CMP		EDX,EAX
		JG		_Exit
		CMP		EBX,[EDI + (EDX + 4) * 4]
		JE		_SkipAdd
		CMP		EBX,[EDI + (EDX + 8) * 4]
		JNE		_AddIndex

		// Found the Index
		_SkipAdd:

		// Decrement the Number of Bits in the Code
		DEC		dwCodeBits

		// Decrement the Bits
		SHR		ECX,1

		// Go back for Another Node
		JMP		_WhileLoop
		_Exit:
	}
}

// Build the Byte Tree and Codes Table and Return the Tree Size
WORD HuffmanDictionary(BYTE *pInput,DWORD dwCount,DWORD *pByteTree,DWORD *pCodes)
{
	// Byte Tree Storage Requirement
	DWORD	dwStorage;

	// Initialize the Weights Array
	HuffmanInitArrays();

	// Sum the Occurences of the Data to the Weights Array
	__asm
	{
		// Point to the Source Data
		MOV		ESI,pInput

		// Point to the Destination Data
		MOV		EDI,OFFSET dwWeight[0]

		// Set the Loop Count
		MOV		ECX,dwCount
		MOV		EAX,0

		// Increment Each Occurence of the Byte
		_SumOccurences:
		LODSB

		// The Byte is an Index to the Weight Array
		INC		DWORD PTR [EDI + EAX * 4]
		DEC		ECX
		JNZ		_SumOccurences
	}

	// Build the Byte and Count Arrays
	HuffmanBuildArrays();

	// Build the Byte Tree
	HuffmanBuildByteTree();

	// Compute the Byte Tree Storage Requirements
	__asm
	{
		// Multiply the Tree Size by 4, for DWORD Access to the Byte Tree Array
		MOV		EDX,0
		MOV		DX,wTreeSize

		// Compute the Tree Storage Requirements
		SHL		EDX,2
		MOV		dwStorage,EDX
	}

	// Copy the Byte Tree
	memblast(pByteTree,&dwByteTree[0],dwStorage);

	// Build the Code List
	HuffmanBuildCodes();

	// Copy the Codes
	memblast(pCodes,&dwCodes[0],2048);

	// Return the Tree Size
	return wTreeSize;
}

// Compute the Compression Size of the Input Data
DWORD HuffmanCountCompress(BYTE *pInput,DWORD dwCount,WORD iTreeSize,DWORD *pCodes)
{
	// Variables Used for Code Shifting
	BOOL	fOutput = FALSE;

	// Compressed Size with Initial Space for Codes
	DWORD	dwNewCount;

	// Loop Variable
	DWORD	dwLoop;

	// Get the Tree Size and Table Storage Requirement
	__asm
	{
		// Get the Tree Size
		MOV		EAX,0
		MOV		AX,iTreeSize

		// Get the Table Storage
		SHL		EAX,2
		MOV		dwStorage,EAX

		// Add 6 for the DWORD and WORD that Stores the UnCompressed Count and Number of Tree Entries
		ADD		EAX,6

		// Initialize the Base Storage Requirement
		MOV		dwNewCount,EAX