/*****************************************************************************/
/* huffman.h                              Copyright (c) Ladislav Zezula 2003 */
/*---------------------------------------------------------------------------*/
/* Description :                                                             */
/*---------------------------------------------------------------------------*/
/*   Date    Ver   Who  Comment                                              */
/* --------  ----  ---  -------                                              */
/* xx.xx.xx  1.00  Lad  The first version of huffman.h                       */
/* 03.05.03  2.00  Lad  Added compression                                    */
/* 08.12.03  2.01  Dan  High-memory handling (> 0x80000000)                  */
/*****************************************************************************/

#ifndef __HUFFMAN_H__
#define __HUFFMAN_H__

//-----------------------------------------------------------------------------
// Defines

#define HUFF_ITEM_COUNT    0x203        // Number of items in the item pool
#define LINK_ITEM_COUNT    0x80         // Maximum number of quick-link items

//-----------------------------------------------------------------------------
// Structures and classes

// Input stream for Huffmann decompression
class TInputStream
{
    public:

    TInputStream(void * pvInBuffer, size_t cbInBuffer);
    bool Get1Bit(unsigned int & BitValue);
    bool Get8Bits(unsigned int & ByteValue);
    bool Peek7Bits(unsigned int & Value);
    void SkipBits(unsigned int BitCount);

    unsigned char * pbInBufferEnd;      // End position in the the input buffer
    unsigned char * pbInBuffer;         // Current position in the the input buffer
    unsigned int BitBuffer;             // Input bit buffer
    unsigned int BitCount;              // Number of bits remaining in 'dwBitBuff'
};


// Output stream for Huffmann compression
class TOutputStream
{
    public:

    TOutputStream(void * pvOutBuffer, size_t cbOutLength);
    void PutBits(unsigned int dwValue, unsigned int nBitCount);
    void Flush();

    unsigned char * pbOutBufferEnd;     // End position in the output buffer
    unsigned char * pbOutBuffer;        // Current position in the output buffer
    unsigned int BitBuffer;             // Bit buffer
    unsigned int BitCount;              // Number of bits in the bit buffer
};

// A virtual tree item that represents the head of the item list
#define LIST_HEAD()  ((THTreeItem *)(&pFirst))

enum TInsertPoint
{
    InsertAfter = 1,
    InsertBefore = 2
};

// Huffmann tree item
struct THTreeItem
{
    THTreeItem()    { pPrev = pNext = NULL; DecompressedValue = 0; Weight = 0; pParent = pChildLo = NULL; }
//  ~THTreeItem()   { RemoveItem(); }

    void         RemoveItem();
//  void         RemoveEntry();

    THTreeItem  * pNext;                // Pointer to lower-weight tree item
    THTreeItem  * pPrev;                // Pointer to higher-weight item
    unsigned int  DecompressedValue;    // 08 - Decompressed byte value (also index in the array)
    unsigned int  Weight;               // 0C - Weight
    THTreeItem  * pParent;              // 10 - Pointer to parent item (NULL if none)
    THTreeItem  * pChildLo;             // 14 - Pointer to the child with lower-weight child ("left child")
};


// Structure used for quick navigating in the huffmann tree.
// Allows skipping up to 7 bits in the compressed stream, thus
// decompressing a bit faster. Sometimes it can even get the decompressed
// byte directly.
struct TQuickLink
{
    unsigned int ValidValue;            // If greater than THuffmannTree::MinValidValue, the entry is valid
    unsigned int ValidBits;             // Number of bits that are valid for this item link
    union
    {
        THTreeItem  * pItem;            // Pointer to the item within the Huffmann tree
        unsigned int DecompressedValue; // Value for direct decompression
    };
};


// Structure for Huffman tree (Size 0x3674 bytes). Because I'm not expert
// for the decompression, I do not know actually if the class is really a Hufmann
// tree. If someone knows the decompression details, please let me know
class THuffmannTree
{
    public:

    THuffmannTree(bool bCompression);
    ~THuffmannTree();

    void  LinkTwoItems(THTreeItem * pItem1, THTreeItem * pItem2);
    void  InsertItem(THTreeItem * item, TInsertPoint InsertPoint, THTreeItem * item2);

    THTreeItem * FindHigherOrEqualItem(THTreeItem * pItem, unsigned int Weight);
    THTreeItem * CreateNewItem(unsigned int DecompressedValue, unsigned int Weight, TInsertPoint InsertPoint);

    unsigned int FixupItemPosByWeight(THTreeItem * pItem, unsigned int MaxWeight);
    bool  BuildTree(unsigned int CompressionType);

    void  IncWeightsAndRebalance(THTreeItem * pItem);
    bool  InsertNewBranchAndRebalance(unsigned int Value1, unsigned int Value2);

    void  EncodeOneByte(TOutputStream * os, THTreeItem * pItem);
    unsigned int DecodeOneByte(TInputStream * is);

    unsigned int Compress(TOutputStream * os, void * pvInBuffer, int cbInBuffer, int nCmpType);
    unsigned int Decompress(void * pvOutBuffer, unsigned int cbOutLength, TInputStream * is);

    THTreeItem   ItemBuffer[HUFF_ITEM_COUNT];   // Buffer for tree items. No memory allocation is needed
    unsigned int ItemsUsed;                     // Number of tree items used from ItemBuffer

    // Head of the linear item list
    THTreeItem * pFirst;                        // Pointer to the highest weight item
    THTreeItem * pLast;                         // Pointer to the lowest weight item

    THTreeItem * ItemsByByte[0x102];            // Array of item pointers, one for each possible byte value
    TQuickLink   QuickLinks[LINK_ITEM_COUNT];   // Array of quick-link items

    unsigned int MinValidValue;                 // A minimum value of TQDecompress::ValidValue to be considered valid
    unsigned int bIsCmp0;                       // 1 if compression type 0
};

#endif // __HUFFMAN_H__