huffman.h

   1 /*****************************************************************************/
   2 /* huffman.h                              Copyright (c) Ladislav Zezula 2003 */
   3 /*---------------------------------------------------------------------------*/
   4 /* Description :                                                             */
   5 /*---------------------------------------------------------------------------*/
   6 /*   Date    Ver   Who  Comment                                              */
   7 /* --------  ----  ---  -------                                              */
   8 /* xx.xx.xx  1.00  Lad  The first version of huffman.h                       */
   9 /* 03.05.03  2.00  Lad  Added compression                                    */
  10 /*****************************************************************************/
  11
  12 #ifndef __HUFFMAN_H__
  13 #define __HUFFMAN_H__
  14
  15 //-----------------------------------------------------------------------------
  16 // Defines
  17
  18 #define INSERT_ITEM    1
  19 #define SWITCH_ITEMS   2                    // Switch the item1 and item2
  20
  21 #define PTR_NOT(ptr)  (THTreeItem *)(~(unsigned long)(ptr))
  22 #define PTR_PTR(ptr)  ((THTreeItem *)(ptr))
  23 #define PTR_INT(ptr)  (long)(ptr)
  24
  25 #ifndef NULL
  26 #define NULL 0
  27 #endif
  28
  29 //-----------------------------------------------------------------------------
  30 // Structures and classes
  31
  32 // Input stream for Huffmann decompression
  33 class TInputStream
  34 {
  35     public:
  36
  37     unsigned long GetBit();
  38     unsigned long Get7Bits();
  39     unsigned long Get8Bits();
  40
  41     unsigned char * pbInBuffer;         // 00 - Input data
  42     unsigned long   dwBitBuff;          // 04 - Input bit buffer
  43     unsigned int    nBits;              // 08 - Number of bits remaining in 'dwValue'
  44 };
  45
  46 // Output stream for Huffmann compression
  47 class TOutputStream
  48 {
  49     public:
  50
  51     void PutBits(unsigned long dwBuff, unsigned int nPutBits);
  52
  53     unsigned char * pbOutBuffer;        // 00 : Output buffer
  54     unsigned long   dwOutSize;          // 04 : Size of output buffer
  55     unsigned char * pbOutPos;           // 08 : Current output position
  56     unsigned long   dwBitBuff;          // 0C : Bit buffer
  57     unsigned long   nBits;              // 10 : Number of bits in the bit buffer
  58 };
  59
  60 // Huffmann tree item (?)
  61 struct THTreeItem
  62 {
  63     public:
  64
  65     THTreeItem * Call1501DB70(THTreeItem * pLast);
  66     THTreeItem * GetPrevItem(long value);
  67     void         ClearItemLinks();
  68     void         RemoveItem();
  69
  70     THTreeItem  * next;                 // 00 - Pointer to next THTreeItem
  71     THTreeItem  * prev;                 // 04 - Pointer to prev THTreeItem (< 0 if none)
  72     unsigned long dcmpByte;             // 08 - Index of this item in item pointer array, decompressed byte value
  73     unsigned long byteValue;            // 0C - Some byte value
  74     THTreeItem  * parent;               // 10 - Pointer to parent THTreeItem (NULL if none)
  75     THTreeItem  * child;                // 14 - Pointer to child  THTreeItem
  76 };
  77
  78 // Structure used for quick decompress. The 'bitCount' contains number of bits
  79 // and byte value contains result decompressed byte value.
  80 // After each walk through Huffman tree are filled all entries which are
  81 // multiplies of number of bits loaded from input stream. These entries
  82 // contain number of bits and result value. At the next 7 bits is tested this
  83 // structure first. If corresponding entry found, decompression routine will
  84 // not walk through Huffman tree and directly stores output byte to output stream.
  85 struct TQDecompress
  86 {
  87     unsigned long offs00;               // 00 - 1 if resolved
  88     unsigned long nBits;                // 04 - Bit count
  89     union
  90     {
  91         unsigned long dcmpByte;         // 08 - Byte value for decompress (if bitCount <= 7)
  92         THTreeItem  * pItem;            // 08 - THTreeItem (if number of bits is greater than 7
  93     };
  94 };
  95
  96 // Structure for Huffman tree (Size 0x3674 bytes). Because I'm not expert
  97 // for the decompression, I do not know actually if the class is really a Hufmann
  98 // tree. If someone knows the decompression details, please let me know
  99 class THuffmannTree
 100 {
 101     public:
 102
 103     void  BuildTree(unsigned int nCmpType);
 104 //  void  ModifyTree(unsigned long dwIndex);
 105 //  void  Call15007010(Bit32 dwInLength, THTreeItem * item);
 106     THTreeItem * Call1500E740(unsigned int nValue);
 107     void         Call1500E820(THTreeItem * pItem);
 108     unsigned int DoCompression(TOutputStream * os, unsigned char * pbInBuffer, int nInLength, int nCmpType);
 109     unsigned int DoDecompression(unsigned char * pbOutBuffer, unsigned int dwOutLength, TInputStream * is);
 110
 111     unsigned long bIsCmp0;              // 0000 - 1 if compression type 0
 112     unsigned long offs0004;             // 0004 - Some flag
 113     THTreeItem    items0008[0x203];     // 0008 - HTree items
 114
 115     //- Sometimes used as HTree item -----------
 116     THTreeItem  * pItem3050;            // 3050 - Always NULL (?)
 117     THTreeItem  * pItem3054;            // 3054 - Pointer to Huffman tree item
 118     THTreeItem  * pItem3058;            // 3058 - Pointer to Huffman tree item (< 0 if invalid)
 119
 120     //- Sometimes used as HTree item -----------
 121     THTreeItem  * pItem305C;            // 305C - Usually NULL
 122     THTreeItem  * pFirst;               // 3060 - Pointer to top (first) Huffman tree item
 123     THTreeItem  * pLast;                // 3064 - Pointer to bottom (last) Huffman tree item (< 0 if invalid)
 124     unsigned long nItems;               // 3068 - Number of used HTree items
 125
 126     //-------------------------------------------
 127     THTreeItem * items306C[0x102];      // 306C - THTreeItem pointer array
 128     TQDecompress qd3474[0x80];          // 3474 - Array for quick decompression
 129
 130     static unsigned char Table1502A630[];// Some table
 131 };
 132
 133 #endif // __HUFFMAN_H__