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#include "huffman.h"
4
5#include <base/dbg.h>
6#include <base/mem.h>
7
8#include <algorithm>
9
10const unsigned CHuffman::ms_aFreqTable[HUFFMAN_MAX_SYMBOLS] = {
11 1 << 30, 4545, 2657, 431, 1950, 919, 444, 482, 2244, 617, 838, 542, 715, 1814, 304, 240, 754, 212, 647, 186,
12 283, 131, 146, 166, 543, 164, 167, 136, 179, 859, 363, 113, 157, 154, 204, 108, 137, 180, 202, 176,
13 872, 404, 168, 134, 151, 111, 113, 109, 120, 126, 129, 100, 41, 20, 16, 22, 18, 18, 17, 19,
14 16, 37, 13, 21, 362, 166, 99, 78, 95, 88, 81, 70, 83, 284, 91, 187, 77, 68, 52, 68,
15 59, 66, 61, 638, 71, 157, 50, 46, 69, 43, 11, 24, 13, 19, 10, 12, 12, 20, 14, 9,
16 20, 20, 10, 10, 15, 15, 12, 12, 7, 19, 15, 14, 13, 18, 35, 19, 17, 14, 8, 5,
17 15, 17, 9, 15, 14, 18, 8, 10, 2173, 134, 157, 68, 188, 60, 170, 60, 194, 62, 175, 71,
18 148, 67, 167, 78, 211, 67, 156, 69, 1674, 90, 174, 53, 147, 89, 181, 51, 174, 63, 163, 80,
19 167, 94, 128, 122, 223, 153, 218, 77, 200, 110, 190, 73, 174, 69, 145, 66, 277, 143, 141, 60,
20 136, 53, 180, 57, 142, 57, 158, 61, 166, 112, 152, 92, 26, 22, 21, 28, 20, 26, 30, 21,
21 32, 27, 20, 17, 23, 21, 30, 22, 22, 21, 27, 25, 17, 27, 23, 18, 39, 26, 15, 21,
22 12, 18, 18, 27, 20, 18, 15, 19, 11, 17, 33, 12, 18, 15, 19, 18, 16, 26, 17, 18,
23 9, 10, 25, 22, 22, 17, 20, 16, 6, 16, 15, 20, 14, 18, 24, 335, 1};
24
25class CHuffmanConstructNode
26{
27public:
28 unsigned short m_NodeId;
29 int m_Frequency;
30};
31
32static bool CompareNodesByFrequencyDesc(const CHuffmanConstructNode *pNode1, const CHuffmanConstructNode *pNode2)
33{
34 return pNode2->m_Frequency < pNode1->m_Frequency;
35}
36
37void CHuffman::SetBitsRecursive(CNode *pNode, int Bits, unsigned Depth)
38{
39 if(pNode->m_aLeaves[1] != 0xffff)
40 SetBitsRecursive(pNode: &m_aNodes[pNode->m_aLeaves[1]], Bits: Bits | (1 << Depth), Depth: Depth + 1);
41 if(pNode->m_aLeaves[0] != 0xffff)
42 SetBitsRecursive(pNode: &m_aNodes[pNode->m_aLeaves[0]], Bits, Depth: Depth + 1);
43
44 if(pNode->m_NumBits)
45 {
46 pNode->m_Bits = Bits;
47 pNode->m_NumBits = Depth;
48 }
49}
50
51void CHuffman::ConstructTree(const unsigned *pFrequencies)
52{
53 CHuffmanConstructNode aNodesLeftStorage[HUFFMAN_MAX_SYMBOLS];
54 CHuffmanConstructNode *apNodesLeft[HUFFMAN_MAX_SYMBOLS];
55 int NumNodesLeft = HUFFMAN_MAX_SYMBOLS;
56
57 // add the symbols
58 for(int i = 0; i < HUFFMAN_MAX_SYMBOLS; i++)
59 {
60 m_aNodes[i].m_NumBits = 0xFFFFFFFF;
61 m_aNodes[i].m_Symbol = i;
62 m_aNodes[i].m_aLeaves[0] = 0xffff;
63 m_aNodes[i].m_aLeaves[1] = 0xffff;
64
65 aNodesLeftStorage[i].m_Frequency = pFrequencies[i];
66 aNodesLeftStorage[i].m_NodeId = i;
67 apNodesLeft[i] = &aNodesLeftStorage[i];
68 }
69
70 m_NumNodes = HUFFMAN_MAX_SYMBOLS;
71
72 // construct the table
73 while(NumNodesLeft > 1)
74 {
75 std::stable_sort(first: apNodesLeft, last: apNodesLeft + NumNodesLeft, comp: CompareNodesByFrequencyDesc);
76
77 m_aNodes[m_NumNodes].m_NumBits = 0;
78 m_aNodes[m_NumNodes].m_aLeaves[0] = apNodesLeft[NumNodesLeft - 1]->m_NodeId;
79 m_aNodes[m_NumNodes].m_aLeaves[1] = apNodesLeft[NumNodesLeft - 2]->m_NodeId;
80 apNodesLeft[NumNodesLeft - 2]->m_NodeId = m_NumNodes;
81 apNodesLeft[NumNodesLeft - 2]->m_Frequency = apNodesLeft[NumNodesLeft - 1]->m_Frequency + apNodesLeft[NumNodesLeft - 2]->m_Frequency;
82
83 m_NumNodes++;
84 NumNodesLeft--;
85 }
86
87 // set start node
88 m_pStartNode = &m_aNodes[m_NumNodes - 1];
89
90 // build symbol bits
91 SetBitsRecursive(pNode: m_pStartNode, Bits: 0, Depth: 0);
92}
93
94void CHuffman::Init()
95{
96 // make sure to cleanout every thing
97 mem_zero(block: m_aNodes, size: sizeof(m_aNodes));
98 mem_zero(block: m_apDecodeLut, size: sizeof(m_apDecodeLut));
99 m_pStartNode = nullptr;
100 m_NumNodes = 0;
101
102 // construct the tree
103 ConstructTree(pFrequencies: ms_aFreqTable);
104
105 // build decode LUT
106 for(int i = 0; i < HUFFMAN_LUTSIZE; i++)
107 {
108 unsigned Bits = i;
109 int k;
110 CNode *pNode = m_pStartNode;
111 for(k = 0; k < HUFFMAN_LUTBITS; k++)
112 {
113 pNode = &m_aNodes[pNode->m_aLeaves[Bits & 1]];
114 Bits >>= 1;
115
116 if(pNode->m_NumBits)
117 {
118 m_apDecodeLut[i] = pNode;
119 break;
120 }
121 }
122
123 if(k == HUFFMAN_LUTBITS)
124 m_apDecodeLut[i] = pNode;
125 }
126}
127
128//***************************************************************
129int CHuffman::Compress(const void *pInput, int InputSize, void *pOutput, int OutputSize) const
130{
131 dbg_assert(InputSize >= 0, "Invalid InputSize: %d", InputSize);
132 dbg_assert(OutputSize > 0, "Invalid OutputSize: %d", OutputSize);
133
134 // this macro loads a symbol for a byte into bits and bitcount
135#define HUFFMAN_MACRO_LOADSYMBOL(Sym) \
136 do \
137 { \
138 Bits |= m_aNodes[Sym].m_Bits << Bitcount; \
139 Bitcount += m_aNodes[Sym].m_NumBits; \
140 } while(0)
141
142 // this macro writes the symbol stored in bits and bitcount to the dst pointer
143#define HUFFMAN_MACRO_WRITE() \
144 do \
145 { \
146 while(Bitcount >= 8) \
147 { \
148 if(pDst == pDstEnd) \
149 return -1; \
150 *pDst++ = (unsigned char)(Bits & 0xff); \
151 Bits >>= 8; \
152 Bitcount -= 8; \
153 } \
154 } while(0)
155
156 // setup buffer pointers
157 const unsigned char *pSrc = (const unsigned char *)pInput;
158 const unsigned char *pSrcEnd = pSrc + InputSize;
159 unsigned char *pDst = (unsigned char *)pOutput;
160 unsigned char *pDstEnd = pDst + OutputSize;
161
162 // symbol variables
163 unsigned Bits = 0;
164 unsigned Bitcount = 0;
165
166 // make sure that we have data that we want to compress
167 if(InputSize)
168 {
169 // {A} load the first symbol
170 int Symbol = *pSrc++;
171
172 while(pSrc != pSrcEnd)
173 {
174 // {B} load the symbol
175 HUFFMAN_MACRO_LOADSYMBOL(Symbol);
176
177 // {C} fetch next symbol, this is done here because it will reduce dependency in the code
178 Symbol = *pSrc++;
179
180 // {B} write the symbol loaded at
181 HUFFMAN_MACRO_WRITE();
182 }
183
184 // write the last symbol loaded from {C} or {A} in the case of only 1 byte input buffer
185 HUFFMAN_MACRO_LOADSYMBOL(Symbol);
186 HUFFMAN_MACRO_WRITE();
187 }
188
189 // write EOF symbol
190 HUFFMAN_MACRO_LOADSYMBOL(HUFFMAN_EOF_SYMBOL);
191 HUFFMAN_MACRO_WRITE();
192
193 // write out the last bits if we have any
194 if(Bitcount != 0)
195 {
196 if(pDst == pDstEnd)
197 return -1;
198 *pDst++ = Bits;
199 }
200
201 // return the size of the output
202 return (int)(pDst - (const unsigned char *)pOutput);
203
204 // remove macros
205#undef HUFFMAN_MACRO_LOADSYMBOL
206#undef HUFFMAN_MACRO_WRITE
207}
208
209//***************************************************************
210int CHuffman::Decompress(const void *pInput, int InputSize, void *pOutput, int OutputSize) const
211{
212 dbg_assert(InputSize >= 0, "Invalid InputSize: %d", InputSize);
213 dbg_assert(OutputSize > 0, "Invalid OutputSize: %d", OutputSize);
214
215 // setup buffer pointers
216 const unsigned char *pSrc = (const unsigned char *)pInput;
217 const unsigned char *pSrcEnd = pSrc + InputSize;
218 unsigned char *pDst = (unsigned char *)pOutput;
219 unsigned char *pDstEnd = pDst + OutputSize;
220
221 unsigned Bits = 0;
222 unsigned Bitcount = 0;
223
224 const CNode *pEof = &m_aNodes[HUFFMAN_EOF_SYMBOL];
225
226 while(true)
227 {
228 // {A} try to load a node now, this will reduce dependency at location {D}
229 const CNode *pNode = nullptr;
230 if(Bitcount >= HUFFMAN_LUTBITS)
231 pNode = m_apDecodeLut[Bits & HUFFMAN_LUTMASK];
232
233 // {B} fill with new bits
234 while(Bitcount < 24 && pSrc != pSrcEnd)
235 {
236 Bits |= (*pSrc++) << Bitcount;
237 Bitcount += 8;
238 }
239
240 // {C} load symbol now if we didn't that earlier at location {A}
241 if(!pNode)
242 pNode = m_apDecodeLut[Bits & HUFFMAN_LUTMASK];
243
244 if(!pNode)
245 return -1;
246
247 // {D} check if we hit a symbol already
248 if(pNode->m_NumBits)
249 {
250 // remove the bits for that symbol
251 if(Bitcount < pNode->m_NumBits)
252 {
253 return -1;
254 }
255 Bits >>= pNode->m_NumBits;
256 Bitcount -= pNode->m_NumBits;
257 }
258 else
259 {
260 // remove the bits that the lut checked up for us
261 if(Bitcount < HUFFMAN_LUTBITS)
262 {
263 return -1;
264 }
265 Bits >>= HUFFMAN_LUTBITS;
266 Bitcount -= HUFFMAN_LUTBITS;
267
268 // walk the tree bit by bit
269 while(true)
270 {
271 // traverse tree
272 pNode = &m_aNodes[pNode->m_aLeaves[Bits & 1]];
273
274 // remove bit
275 Bitcount--;
276 Bits >>= 1;
277
278 // check if we hit a symbol
279 if(pNode->m_NumBits)
280 break;
281
282 // no more bits, decoding error
283 if(Bitcount == 0)
284 return -1;
285 }
286 }
287
288 // check for eof
289 if(pNode == pEof)
290 break;
291
292 // output character
293 if(pDst == pDstEnd)
294 return -1;
295 *pDst++ = pNode->m_Symbol;
296 }
297
298 // return the size of the decompressed buffer
299 return (int)(pDst - (const unsigned char *)pOutput);
300}
301