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
6class CHuffman
7{
8 enum
9 {
10 HUFFMAN_EOF_SYMBOL = 256,
11
12 HUFFMAN_MAX_SYMBOLS = HUFFMAN_EOF_SYMBOL + 1,
13 HUFFMAN_MAX_NODES = HUFFMAN_MAX_SYMBOLS * 2 - 1,
14
15 HUFFMAN_LUTBITS = 10,
16 HUFFMAN_LUTSIZE = (1 << HUFFMAN_LUTBITS),
17 HUFFMAN_LUTMASK = (HUFFMAN_LUTSIZE - 1)
18 };
19
20 struct CNode
21 {
22 // symbol
23 unsigned m_Bits;
24 unsigned m_NumBits;
25
26 // don't use pointers for this. shorts are smaller so we can fit more data into the cache
27 unsigned short m_aLeaves[2];
28
29 // what the symbol represents
30 unsigned char m_Symbol;
31 };
32
33 static const unsigned ms_aFreqTable[HUFFMAN_MAX_SYMBOLS];
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
43public:
44 /*
45 Function: Init
46 Inits the compressor/decompressor.
47
48 Parameters:
49 pFrequencies - A pointer to an array of 256 entries of the frequencies of the bytes
50
51 Remarks:
52 - Does no allocation whatsoever.
53 - You don't have to call any cleanup functions when you are done with it.
54 */
55 void Init(const unsigned *pFrequencies = ms_aFreqTable);
56
57 /*
58 Function: Compress
59 Compresses a buffer and outputs a compressed buffer.
60
61 Parameters:
62 pInput - Buffer to compress
63 InputSize - Size of the buffer to compress
64 pOutput - Buffer to put the compressed data into
65 OutputSize - Size of the output buffer
66
67 Returns:
68 Returns the size of the compressed data. Negative value on failure.
69 */
70 int Compress(const void *pInput, int InputSize, void *pOutput, int OutputSize) const;
71
72 /*
73 Function: Decompress
74 Decompresses a buffer
75
76 Parameters:
77 pInput - Buffer to decompress
78 InputSize - Size of the buffer to decompress
79 pOutput - Buffer to put the uncompressed data into
80 OutputSize - Size of the output buffer
81
82 Returns:
83 Returns the size of the uncompressed data. Negative value on failure.
84 */
85 int Decompress(const void *pInput, int InputSize, void *pOutput, int OutputSize) const;
86};
87#endif // ENGINE_SHARED_HUFFMAN_H
88