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;