Subversion Repositories spk

/*****************************************************************************

  LiteralHuffTree

  ---------------

  Class for generating/emitting Huffman trees on a byte base.

  Could be used for adaptive and non-adaptive Huffman tree models.

  by yoda

  WWW:      y0da.cjb.net

  E-mail:   LordPE@gmx.net

  You are allowed to use this class in your own projects if you keep this

  trademark.

*****************************************************************************/

#pragma once

#include <windows.h>

#include "ByteReader.h"

//

// constants

//

#define HT_LEFT  0

#define HT_RIGHT 1

//

// structures

//

typedef struct _LHT_ITEM

{

	WORD                     id;                           // a unique value

	BOOL                     bLinked;                      // already linked in the tree ?

	DWORD                    dwDadId;                      // 0 == root item

	DWORD                    dwLeftId;

	DWORD                    dwRightId;  

	DWORD                    dwcOccurr;

//	float                    probability;                  // how often the character appears in the input block

	DWORD                    dwSequence;                   // bit signature for the character

	BYTE                     bySequLen;                    // length of the bit signature

} LHT_ITEM, *PLHT_ITEM;

//

// LiteralHuffTree class

//

class LiteralHuffTree

{

public:

	LiteralHuffTree(void);

	~LiteralHuffTree(void);

	DWORD      m_dwOccurr[256];

	BOOL       Generate( PBYTE buff, DWORD cb );

	BOOL       GenerateWithOccurrences();

	BOOL       GenerateAdaptiveModel();

	DWORD      QueryLiteralByBitSequence( PByteReader reader );

	PLHT_ITEM  operator[]( UINT index ) { return &m_tree[index]; };

private:

	LHT_ITEM   m_tree[(256 * 2) - 1];

	UINT       m_ucTreeItems;

	void       GetByteOccurrences( PBYTE pby, DWORD cb );

	void       BuildInternalTree();

	void       LinkTreeElements();

	bool       GenerateBitSequences();

	DWORD      GetBitCountForOccurrence();

};

typedef LiteralHuffTree *PLiteralHuffTree;