huffcompress.c

Visual C++网络通信编程实用案例精逊配套源码 光盘中存放的是书中涉及的所有实例的源代码和经过编译后的应用程序。所有程序均经过测试

#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