contrib/extractor/libmpq/huffman.h

   1 /*
   2  *  huffman.h -- structures used for huffman compression.
   3  *
   4  *  Copyright (C) 2003 Maik Broemme <mbroemme@plusserver.de>
   5  *
   6  *  This source was adepted from the C++ version of huffman.h included
   7  *  in stormlib. The C++ version belongs to the following authors,
   8  *
   9  *  Ladislav Zezula <ladik.zezula.net>
  10  *  ShadowFlare <BlakFlare@hotmail.com>
  11  *
  12  *  This program is free software; you can redistribute it and/or modify
  13  *  it under the terms of the GNU General Public License as published by
  14  *  the Free Software Foundation; either version 2 of the License, or
  15  *  (at your option) any later version.
  16  *
  17  *  This program is distributed in the hope that it will be useful,
  18  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  *  GNU General Public License for more details.
  21  *
  22  *  You should have received a copy of the GNU General Public License
  23  *  along with this program; if not, write to the Free Software
  24  *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25  */
  26
  27 #ifndef _HUFFMAN_H
  28 #define _HUFFMAN_H
  29
  30 #define PTR_NOT(ptr)    (struct huffman_tree_item *)(~(unsigned long)(ptr))
  31 #define PTR_PTR(ptr)    ((struct huffman_tree_item *)(ptr))
  32 #define PTR_INT(ptr)    (long)(ptr)
  33
  34 #define INSERT_ITEM     1
  35 #define SWITCH_ITEMS    2                               /* Switch the item1 and item2 */
  36
  37 /*
  38  *  Input stream for Huffmann decompression
  39  */
  40 struct huffman_input_stream {
  41         unsigned char *in_buf;                          /* 00 - Input data */
  42         unsigned long bit_buf;                          /* 04 - Input bit buffer */
  43         unsigned int bits;                              /* 08 - Number of bits remaining in 'byte' */
  44 };
  45
  46 /*
  47  *  Huffmann tree item.
  48  */
  49 struct huffman_tree_item {
  50         struct huffman_tree_item *next;                 /* 00 - Pointer to next huffman_tree_item */
  51         struct huffman_tree_item *prev;                 /* 04 - Pointer to prev huffman_tree_item (< 0 if none) */
  52         unsigned long dcmp_byte;                        /* 08 - Index of this item in item pointer array, decompressed byte value */
  53         unsigned long byte_value;                       /* 0C - Some byte value */
  54         struct huffman_tree_item *parent;               /* 10 - Pointer to parent huffman_tree_item (NULL if none) */
  55         struct huffman_tree_item *child;                /* 14 - Pointer to child huffman_tree_item */
  56 };
  57
  58 /*
  59  *  Structure used for quick decompress. The 'bits' contains
  60  *  number of bits and dcmp_byte contains result decompressed byte
  61  *  value. After each walk through Huffman tree are filled all entries
  62  *  which are multiplies of number of bits loaded from input stream.
  63  *  These entries contain number of bits and result value. At the next
  64  *  7 bits is tested this structure first. If corresponding entry found,
  65  *  decompression routine will not walk through Huffman tree and
  66  *  directly stores output byte to output stream.
  67  */
  68 struct huffman_decompress {
  69         unsigned long offs00;                           /* 00 - 1 if resolved */
  70         unsigned long bits;                             /* 04 - Bit count */
  71         union {
  72                 unsigned long dcmp_byte;                /* 08 - Byte value for decompress (if bitCount <= 7) */
  73                 struct huffman_tree_item *p_item;       /* 08 - THTreeItem (if number of bits is greater than 7 */
  74         };
  75 };
  76
  77 /*
  78  *  Structure for Huffman tree.
  79  */
  80 struct huffman_tree {
  81         unsigned long cmp0;                             /* 0000 - 1 if compression type 0 */
  82         unsigned long offs0004;                         /* 0004 - Some flag */
  83
  84         struct huffman_tree_item items0008[0x203];      /* 0008 - huffman tree items */
  85
  86         /* Sometimes used as huffman tree item */
  87         struct huffman_tree_item *item3050;             /* 3050 - Always NULL (?) */
  88         struct huffman_tree_item *item3054;             /* 3054 - Pointer to huffman_tree_item */
  89         struct huffman_tree_item *item3058;             /* 3058 - Pointer to huffman_tree_item (< 0 if invalid) */
  90
  91         /* Sometimes used as huffman tree item */
  92         struct huffman_tree_item *item305C;             /* 305C - Usually NULL */
  93         struct huffman_tree_item *first;                /* 3060 - Pointer to top (first) Huffman tree item */
  94         struct huffman_tree_item *last;                 /* 3064 - Pointer to bottom (last) Huffman tree item (< 0 if invalid) */
  95         unsigned long items;                            /* 3068 - Number of used huffman tree items */
  96
  97         struct huffman_tree_item *items306C[0x102];     /* 306C - huffman_tree_item pointer array */
  98         struct huffman_decompress qd3474[0x80];         /* 3474 - Array for quick decompression */
  99
 100         //unsigned char table1502A630[];                        /* Some table to make struct size flexible */
 101 };
 102
 103 int libmpq_huff_init_tree(struct huffman_tree *ht, struct huffman_tree_item *hi, unsigned int cmp);
 104 int libmpq_huff_do_decompress(struct huffman_tree *ht, struct huffman_input_stream *is, unsigned char *out_buf, unsigned int out_length);
 105 #endif                  /* _HUFFMAN_H */