src/engine/shared/huffman.h

   1 /* (c) Magnus Auvinen. See licence.txt in the root of the distribution for more information. */
   2 /* If you are missing that file, acquire a complete release at teeworlds.com.                */
   3 #ifndef ENGINE_SHARED_HUFFMAN_H
   4 #define ENGINE_SHARED_HUFFMAN_H
   5
   6
   7
   8 class CHuffman
   9 {
  10         enum
  11         {
  12                 HUFFMAN_EOF_SYMBOL = 256,
  13
  14                 HUFFMAN_MAX_SYMBOLS=HUFFMAN_EOF_SYMBOL+1,
  15                 HUFFMAN_MAX_NODES=HUFFMAN_MAX_SYMBOLS*2-1,
  16
  17                 HUFFMAN_LUTBITS = 10,
  18                 HUFFMAN_LUTSIZE = (1<<HUFFMAN_LUTBITS),
  19                 HUFFMAN_LUTMASK = (HUFFMAN_LUTSIZE-1)
  20         };
  21
  22         struct CNode
  23         {
  24                 // symbol
  25                 unsigned m_Bits;
  26                 unsigned m_NumBits;
  27
  28                 // don't use pointers for this. shorts are smaller so we can fit more data into the cache
  29                 unsigned short m_aLeafs[2];
  30
  31                 // what the symbol represents
  32                 unsigned char m_Symbol;
  33         };
  34
  35         CNode m_aNodes[HUFFMAN_MAX_NODES];
  36         CNode *m_apDecodeLut[HUFFMAN_LUTSIZE];
  37         CNode *m_pStartNode;
  38         int m_NumNodes;
  39
  40         void Setbits_r(CNode *pNode, int Bits, unsigned Depth);
  41         void ConstructTree(const unsigned *pFrequencies);
  42
  43 public:
  44         /*
  45                 Function: huffman_init
  46                         Inits the compressor/decompressor.
  47
  48                 Parameters:
  49                         huff - Pointer to the state to init
  50                         frequencies - A pointer to an array of 256 entries of the frequencies of the bytes
  51
  52                 Remarks:
  53                         - Does no allocation what so ever.
  54                         - You don't have to call any cleanup functions when you are done with it
  55         */
  56         void Init(const unsigned *pFrequencies);
  57
  58         /*
  59                 Function: huffman_compress
  60                         Compresses a buffer and outputs a compressed buffer.
  61
  62                 Parameters:
  63                         huff - Pointer to the huffman state
  64                         input - Buffer to compress
  65                         input_size - Size of the buffer to compress
  66                         output - Buffer to put the compressed data into
  67                         output_size - Size of the output buffer
  68
  69                 Returns:
  70                         Returns the size of the compressed data. Negative value on failure.
  71         */
  72         int Compress(const void *pInput, int InputSize, void *pOutput, int OutputSize);
  73
  74         /*
  75                 Function: huffman_decompress
  76                         Decompresses a buffer
  77
  78                 Parameters:
  79                         huff - Pointer to the huffman state
  80                         input - Buffer to decompress
  81                         input_size - Size of the buffer to decompress
  82                         output - Buffer to put the uncompressed data into
  83                         output_size - Size of the output buffer
  84
  85                 Returns:
  86                         Returns the size of the uncompressed data. Negative value on failure.
  87         */
  88         int Decompress(const void *pInput, int InputSize, void *pOutput, int OutputSize);
  89
  90 };
  91 #endif // __HUFFMAN_HEADER__