Merge pull request #3138 from Robyt3/CHuffman-refactoring

Refactor CHuffman

2 files changed, 40 insertions, 62 deletions

diff --git a/src/engine/shared/huffman.cpp b/src/engine/shared/huffman.cpp
index cce241bbd..4fef3990f 100644
--- a/src/engine/shared/huffman.cpp
+++ b/src/engine/shared/huffman.cpp
@@ -1,10 +1,10 @@
 /* (c) Magnus Auvinen. See licence.txt in the root of the distribution for more information. */
 /* If you are missing that file, acquire a complete release at teeworlds.com.                */
-#include <base/system.h>
 #include "huffman.h"
+#include <algorithm>
+#include <base/system.h>
 
-
-static const unsigned gs_aFreqTable[256 + 1] = {
+const unsigned CHuffman::ms_aFreqTable[HUFFMAN_MAX_SYMBOLS] = {
 	1 << 30,4545,2657,431,1950,919,444,482,2244,617,838,542,715,1814,304,240,754,212,647,186,
 	283,131,146,166,543,164,167,136,179,859,363,113,157,154,204,108,137,180,202,176,
 	872,404,168,134,151,111,113,109,120,126,129,100,41,20,16,22,18,18,17,19,
@@ -22,9 +22,14 @@ static const unsigned gs_aFreqTable[256 + 1] = {
 struct CHuffmanConstructNode
 {
 	unsigned short m_NodeId;
- 	int m_Frequency;
+	int m_Frequency;
 };
 
+bool CompareNodesByFrequencyDesc(const CHuffmanConstructNode *pNode1, const CHuffmanConstructNode *pNode2)
+{
+	return pNode2->m_Frequency < pNode1->m_Frequency;
+}
+
 void CHuffman::Setbits_r(CNode *pNode, int Bits, unsigned Depth)
 {
 	if(pNode->m_aLeafs[1] != 0xffff)
@@ -39,29 +44,6 @@ void CHuffman::Setbits_r(CNode *pNode, int Bits, unsigned Depth)
 	}
 }
 
-// TODO: this should be something faster, but it's enough for now
-static void BubbleSort(CHuffmanConstructNode **ppList, int Size)
-{
-	int Changed = 1;
-	CHuffmanConstructNode *pTemp;
-
-	while(Changed)
-	{
-		Changed = 0;
-		for(int i = 0; i < Size-1; i++)
-		{
-			if(ppList[i]->m_Frequency < ppList[i+1]->m_Frequency)
-			{
-				pTemp = ppList[i];
-				ppList[i] = ppList[i+1];
-				ppList[i+1] = pTemp;
-				Changed = 1;
-			}
-		}
-		Size--;
-	}
-}
-
 void CHuffman::ConstructTree(const unsigned *pFrequencies)
 {
 	CHuffmanConstructNode aNodesLeftStorage[HUFFMAN_MAX_SYMBOLS];
@@ -90,8 +72,7 @@ void CHuffman::ConstructTree(const unsigned *pFrequencies)
 	// construct the table
 	while(NumNodesLeft > 1)
 	{
-		// we can't rely on stdlib's qsort for this, it can generate different results on different implementations
-		BubbleSort(apNodesLeft, NumNodesLeft);
+		std::stable_sort(apNodesLeft, apNodesLeft + NumNodesLeft, CompareNodesByFrequencyDesc);
 
 		m_aNodes[m_NumNodes].m_NumBits = 0;
 		m_aNodes[m_NumNodes].m_aLeafs[0] = apNodesLeft[NumNodesLeft-1]->m_NodeId;
@@ -113,11 +94,12 @@ void CHuffman::ConstructTree(const unsigned *pFrequencies)
 void CHuffman::Init(const unsigned *pFrequencies)
 {
 	// make sure to cleanout every thing
-	mem_zero(this, sizeof(*this));
+	mem_zero(m_aNodes, sizeof(m_aNodes));
+	mem_zero(m_apDecodeLut, sizeof(m_apDecodeLut));
+	m_pStartNode = 0x0;
+	m_NumNodes = 0;
 
 	// construct the tree
-	if(!pFrequencies)
-		pFrequencies = gs_aFreqTable;
 	ConstructTree(pFrequencies);
 
 	// build decode LUT
@@ -148,7 +130,7 @@ void CHuffman::Init(const unsigned *pFrequencies)
 }
 
 //***************************************************************
-int CHuffman::Compress(const void *pInput, int InputSize, void *pOutput, int OutputSize)
+int CHuffman::Compress(const void *pInput, int InputSize, void *pOutput, int OutputSize) const
 {
 	// this macro loads a symbol for a byte into bits and bitcount
 #define HUFFMAN_MACRO_LOADSYMBOL(Sym) \
@@ -215,7 +197,7 @@ int CHuffman::Compress(const void *pInput, int InputSize, void *pOutput, int Out
 }
 
 //***************************************************************
-int CHuffman::Decompress(const void *pInput, int InputSize, void *pOutput, int OutputSize)
+int CHuffman::Decompress(const void *pInput, int InputSize, void *pOutput, int OutputSize) const
 {
 	// setup buffer pointers
 	unsigned char *pDst = (unsigned char *)pOutput;
@@ -226,10 +208,10 @@ int CHuffman::Decompress(const void *pInput, int InputSize, void *pOutput, int O
 	unsigned Bits = 0;
 	unsigned Bitcount = 0;
 
-	CNode *pEof = &m_aNodes[HUFFMAN_EOF_SYMBOL];
-	CNode *pNode = 0;
+	const CNode *pEof = &m_aNodes[HUFFMAN_EOF_SYMBOL];
+	const CNode *pNode = 0;
 
-	while(1)
+	while(true)
 	{
 		// {A} try to load a node now, this will reduce dependency at location {D}
 		pNode = 0;
@@ -264,7 +246,7 @@ int CHuffman::Decompress(const void *pInput, int InputSize, void *pOutput, int O
 			Bitcount -= HUFFMAN_LUTBITS;
 
 			// walk the tree bit by bit
-			while(1)
+			while(true)
 			{
 				// traverse tree
 				pNode = &m_aNodes[pNode->m_aLeafs[Bits&1]];
diff --git a/src/engine/shared/huffman.h b/src/engine/shared/huffman.h
index 96628db9c..985b915ed 100644
--- a/src/engine/shared/huffman.h
+++ b/src/engine/shared/huffman.h
@@ -3,8 +3,6 @@
 #ifndef ENGINE_SHARED_HUFFMAN_H
 #define ENGINE_SHARED_HUFFMAN_H
 
-
-
 class CHuffman
 {
 	enum
@@ -32,6 +30,8 @@ class CHuffman
 		unsigned char m_Symbol;
 	};
 
+	static const unsigned ms_aFreqTable[HUFFMAN_MAX_SYMBOLS];
+
 	CNode m_aNodes[HUFFMAN_MAX_NODES];
 	CNode *m_apDecodeLut[HUFFMAN_LUTSIZE];
 	CNode *m_pStartNode;
@@ -42,50 +42,46 @@ class CHuffman
 
 public:
 	/*
-		Function: huffman_init
+		Function: Init
 			Inits the compressor/decompressor.
 
 		Parameters:
-			huff - Pointer to the state to init
-			frequencies - A pointer to an array of 256 entries of the frequencies of the bytes
+			pFrequencies - A pointer to an array of 256 entries of the frequencies of the bytes
 
 		Remarks:
-			- Does no allocation what so ever.
-			- You don't have to call any cleanup functions when you are done with it
+			- Does no allocation whatsoever.
+			- You don't have to call any cleanup functions when you are done with it.
 	*/
-	void Init(const unsigned *pFrequencies = 0);
+	void Init(const unsigned *pFrequencies = ms_aFreqTable);
 
 	/*
-		Function: huffman_compress
+		Function: Compress
 			Compresses a buffer and outputs a compressed buffer.
 
 		Parameters:
-			huff - Pointer to the huffman state
-			input - Buffer to compress
-			input_size - Size of the buffer to compress
-			output - Buffer to put the compressed data into
-			output_size - Size of the output buffer
+			pInput - Buffer to compress
+			InputSize - Size of the buffer to compress
+			pOutput - Buffer to put the compressed data into
+			OutputSize - Size of the output buffer
 
 		Returns:
 			Returns the size of the compressed data. Negative value on failure.
 	*/
-	int Compress(const void *pInput, int InputSize, void *pOutput, int OutputSize);
+	int Compress(const void *pInput, int InputSize, void *pOutput, int OutputSize) const;
 
 	/*
-		Function: huffman_decompress
+		Function: Decompress
 			Decompresses a buffer
 
 		Parameters:
-			huff - Pointer to the huffman state
-			input - Buffer to decompress
-			input_size - Size of the buffer to decompress
-			output - Buffer to put the uncompressed data into
-			output_size - Size of the output buffer
+			pInput - Buffer to decompress
+			InputSize - Size of the buffer to decompress
+			pOutput - Buffer to put the uncompressed data into
+			OutputSize - Size of the output buffer
 
 		Returns:
 			Returns the size of the uncompressed data. Negative value on failure.
 	*/
-	int Decompress(const void *pInput, int InputSize, void *pOutput, int OutputSize);
-
+	int Decompress(const void *pInput, int InputSize, void *pOutput, int OutputSize) const;
 };
-#endif // __HUFFMAN_HEADER__
+#endif // ENGINE_SHARED_HUFFMAN_H