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 | class 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_aLeafs[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 | |
43 | public: |
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 | |