#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include "HuffCompress.h"
#include "Client.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]
		// Use the Pointers to get the Number of Elements
		SUB		EDI,ESI
		MOV		ECX,EDI
		SHR		ECX,2

		// Check for only 1 Element in the Byte Array
		CMP		ECX,1
		JNE		_Exit

		// Point to the Byte Array
		MOV		EDI,OFFSET dwByte[0]

		// Add the Dummy Byte (256 Can't Exist, so it is Fine)
		MOV		EAX,256
		MOV		[EDI + ECX * 4],EAX

		// Point to the Counts Array
		MOV		EDI,OFFSET dwCounts[0]

		// Add the Dummy Count of 1
		MOV		[EDI + ECX * 4],DWORD PTR 1

		// Increment the Number of Elements
		INC		ECX

		// Finished Building the Arrays
		_Exit:

		// Update the Number of Elements
		MOV		iElements,ECX
		MOV		iTotalElements,ECX
	}
}

// Build the Byte Tree
void HuffmanBuildByteTree()
{
	DWORD	dwParentWeight,dwParentDesc;
	int		iStartPos = -3;
	BOOL	fInsert = TRUE;

	// Arbitrary Value of the First Parent Combined Parent Description
	dwParentDesc = 1000;

	// While we don't have a Root Node
	while (iElements > 1)
	{
		// Quick Sort the Array
		HuffmanQuickSortD(&dwCounts[0],&dwByte[0],0,iElements - 1);

		// Build the Huffman Tree
		__asm
		{
			/* Step 1: Create a Parent for the Children with the
			           two lowest Weights and a Descriptor for
					   the Parent from the Children Bytes */

			// Point to the Count Array
			MOV		ESI,OFFSET dwCounts[0]

			// Compute the New End of Array
			MOV		EBX,iElements
			DEC		EBX

			// Update the Number of Elements
			MOV		iElements,EBX

			// Index the two Lowest Weights
			MOV		EAX,EBX
			DEC		EAX

			// Create a Parent from the Two Lowest Weights
			MOV		EDX,[ESI + EAX * 4]
			ADD		EDX,[ESI + EBX * 4]

			// Save the Parent
			MOV		dwParentWeight,EDX

			// Compute the Start Position in the Tree
			MOV		ECX,iStartPos
			ADD		ECX,3

			// Update the Start Position in the Tree
			MOV		iStartPos,ECX

			/* Step 3: Add to the Byte Conversion Tree */

			// Point to the Byte Array
			MOV		ESI,OFFSET dwByte[0]

			// Point to the Byte Table Conversion Tree
			MOV		EDI,OFFSET dwByteTree[0]

			// Move the New Parent Descriptor to the First Spot in Tree
			MOV		EDX,dwParentDesc
			MOV		[EDI + ECX * 4],EDX

			// Move the First Child Byte to the Second Spot in Tree
			MOV		EDX,[ESI + EAX * 4]
			MOV		[EDI + ECX * 4 + 4],EDX
			// Move the Second Child Byte to the Third Spot in Tree
			MOV		EDX,[ESI + EBX * 4]
			MOV		[EDI + ECX * 4 + 8],EDX

			/* Step 4: Update the Counts Array, Removing the Children
			           and Adding the Parent */

			// Point to the Count Array
			MOV		ESI,OFFSET dwCounts[0]

			// Restore the New Weight Value of the Parent
			MOV		EDX,dwParentWeight

			// Insert the Parent to the Counts Array
			MOV		[ESI + EAX * 4],EDX

			// Point to the Byte Array
			MOV		ESI,OFFSET dwByte[0]

			// Restore the New Weight Value of the Parent
			MOV		EDX,dwParentDesc

			// Insert the Combined Parent to the End of the Byte Array
			MOV		[ESI + EAX * 4],EDX

			// Update the Parent Descriptor for the Next New Parent
			INC		dwParentDesc
		}
	}

	// Get the Index to the Root in the Tree
	__asm
	{
		MOV		ECX,iStartPos
		MOV		dwRootIndex,ECX
		ADD		ECX,3
		MOV		wTreeSize,CX
	}
}

// Quick Sort the Array in Ascending Order
void HuffmanQuickSortA(DWORD *pArray1,DWORD *pArray2,int iBegin,int iEnd)
{
	int		iLow,iHigh,iTemp;

	__asm
	{
		// Set the Low and High Elements
		MOV		EAX,iBegin
		MOV		EBX,iEnd

		// Point the Input Array
		MOV		ESI,pArray1

		// Get the List Separator
		MOV		ECX,EAX
		ADD		ECX,EBX
		SHR		ECX,1
		MOV		EDX,[ESI + ECX * 4]

		// The Main Loop
		_DoLoop:

		// Point the Input Array
		MOV		ESI,pArray1

		// Order the Low Elements
		_OrderLow:
		MOV		EDI,EAX
		INC		EAX
		CMP		[ESI + EDI * 4],EDX
		JB		_OrderLow
		MOV		EAX,EDI

		// Order the High Elements
		_OrderHigh:
		MOV		EDI,EBX
		DEC		EBX
		CMP		[ESI + EDI * 4],EDX
		JA		_OrderHigh
		MOV		EBX,EDI

		// Check for Swapping Array[Low] with Array[High]
		CMP		EAX,EBX
		JG		_NoSwap

		// Swap dwCounts[Low] with dwCounts[High]
		MOV		ECX,[ESI + EAX * 4]
		MOV		EDI,[ESI + EBX * 4]
		MOV		[ESI + EAX * 4],EDI
		MOV		[ESI + EBX * 4],ECX

		// Swap the Byte Array
		MOV		ESI,pArray2
		MOV		ECX,[ESI + EAX * 4]
		MOV		EDI,[ESI + EBX * 4]
		MOV		[ESI + EAX * 4],EDI
		MOV		[ESI + EBX * 4],ECX

		// Update the Low and High Indexes
		INC		EAX
		DEC		EBX

		// Test for Looping Back
		_NoSwap:
		MOV		iTemp,EBX
		CMP		EAX,iTemp
		JLE		_DoLoop

		// Update the Low and High Values
		MOV		iLow,EAX
		MOV		iHigh,EBX
	}

	// Check for Sorting Elements between Begin and High (New Lower Range)
	if (iBegin < iHigh)
		HuffmanQuickSortA(pArray1,pArray2,iBegin,iHigh);

	// Check for Sorting Elements between Low and End (New Upper Range)
	if (iLow < iEnd)
		HuffmanQuickSortA(pArray1,pArray2,iLow,iEnd);
}

// Quick Sort the Array in Descending Order
void HuffmanQuickSortD(DWORD *pArray1,DWORD *pArray2,int iBegin,int iEnd)
{
	int		iLow,iHigh,iTemp;

	__asm
	{
		// Set the Low and High Elements
		MOV		EAX,iBegin
		MOV		EBX,iEnd

		// Point the Input Array
		MOV		ESI,pArray1

		// Get the List Separator
		MOV		ECX,EAX
		ADD		ECX,EBX
		SHR		ECX,1
		MOV		EDX,[ESI + ECX * 4]

		// The Main Loop
		_DoLoop:

		// Point the Input Array
		MOV		ESI,pArray1

		// Order the Low Elements
		_OrderLow:
		MOV		EDI,EAX
		INC		EAX
		CMP		[ESI + EDI * 4],EDX
		JA		_OrderLow
		MOV		EAX,EDI

		// Order the High Elements
		_OrderHigh:
		MOV		EDI,EBX
		DEC		EBX
		CMP		[ESI + EDI * 4],EDX
		JB		_OrderHigh
		MOV		EBX,EDI

		// Check for Swapping Array[Low] with Array[High]
		CMP		EAX,EBX
		JG		_NoSwap

		// Swap dwCounts[Low] with dwCounts[High]
		MOV		ECX,[ESI + EAX * 4]
		MOV		EDI,[ESI + EBX * 4]
		MOV		[ESI + EAX * 4],EDI
		MOV		[ESI + EBX * 4],ECX

		// Swap the Byte Array
		MOV		ESI,pArray2
		MOV		ECX,[ESI + EAX * 4]
		MOV		EDI,[ESI + EBX * 4]
		MOV		[ESI + EAX * 4],EDI
		MOV		[ESI + EBX * 4],ECX

		// Update the Low and High Indexes
		INC		EAX
		DEC		EBX

		// Test for Looping Back
		_NoSwap:
		MOV		iTemp,EBX
		CMP		EAX,iTemp
		JLE		_DoLoop

		// Update the Low and High Values
		MOV		iLow,EAX
		MOV		iHigh,EBX
	}

	// Check for Sorting Elements between Begin and High (New Lower Range)
	if (iBegin < iHigh)
		HuffmanQuickSortD(pArray1,pArray2,iBegin,iHigh);

	// Check for Sorting Elements between Low and End (New Upper Range)
	if (iLow < iEnd)
		HuffmanQuickSortD(pArray1,pArray2,iLow,iEnd);
}

// Navigate the Binary Tree
void HuffmanBuildCodes()
{
	DWORD	dwCodeBits;
	DWORD	dwLeafNode;

	__asm
	{
		// Initialize the Count of Codes
		MOV		dwCodeCount,0;

		// Initialize the Bit Code
		MOV		ECX,0

		// Initialize the Index
		MOV		EDX,dwRootIndex

		// Point to the Bit and Byte Tree Arrays
		MOV		ESI,OFFSET dwBitTree[0]
		MOV		EDI,OFFSET dwByteTree[0]

		// Initialize the Number of Bits in the Code
		MOV		dwCodeBits,0

		// While We Still Have Children for the Parent
		_WhileLoop:

		// Get the Number of Children
		MOV		EAX,0
		MOV		AL,[ESI + EDX]

		// Decrement the Parents Number of Children
		DEC		[ESI + EDX]

		// Check for Children
		CMP		EAX,0
		JE		_FindParent

		// Get the Last Child of the Current Parent
		ADD		EDX,EAX
		MOV		EBX,[EDI + EDX * 4]
		SUB		EDX,EAX

		// Increment the Code Bits
		ADD		ECX,ECX

		// For a Move to the Right in the Tree Add a 1 to the Code
		CMP		EAX,2
		JNE		_SkipOr
		OR		ECX,1
		_SkipOr:

		// Increment the Number of Bits in the Code
		INC		dwCodeBits

		// Check for a Leaf Node
		CMP		EBX,256
		JLE		_LeafNode

 		// Get the Parent Index of the Child Node Starting 
		// with the Previous Parent of the Current Parent
		_SubIndex:
		SUB		EDX,3
		CMP		EBX,[EDI + EDX * 4]
		JNE		_SubIndex

		// Loop Back for Another Node
		JMP		_WhileLoop

		// Process a Leaf Node
		_LeafNode:

		// Save the Index
		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