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