ce188d4d |
1 | // license:BSD-3-Clause\r |
2 | // copyright-holders:Aaron Giles\r |
3 | /***************************************************************************\r |
4 | \r |
5 | huffman.c\r |
6 | \r |
7 | Static Huffman compression and decompression helpers.\r |
8 | \r |
9 | ****************************************************************************\r |
10 | \r |
11 | Maximum codelength is officially (alphabetsize - 1). This would be 255 bits\r |
12 | (since we use 1 byte values). However, it is also dependent upon the number\r |
13 | of samples used, as follows:\r |
14 | \r |
15 | 2 bits -> 3..4 samples\r |
16 | 3 bits -> 5..7 samples\r |
17 | 4 bits -> 8..12 samples\r |
18 | 5 bits -> 13..20 samples\r |
19 | 6 bits -> 21..33 samples\r |
20 | 7 bits -> 34..54 samples\r |
21 | 8 bits -> 55..88 samples\r |
22 | 9 bits -> 89..143 samples\r |
23 | 10 bits -> 144..232 samples\r |
24 | 11 bits -> 233..376 samples\r |
25 | 12 bits -> 377..609 samples\r |
26 | 13 bits -> 610..986 samples\r |
27 | 14 bits -> 987..1596 samples\r |
28 | 15 bits -> 1597..2583 samples\r |
29 | 16 bits -> 2584..4180 samples -> note that a 4k data size guarantees codelength <= 16 bits\r |
30 | 17 bits -> 4181..6764 samples\r |
31 | 18 bits -> 6765..10945 samples\r |
32 | 19 bits -> 10946..17710 samples\r |
33 | 20 bits -> 17711..28656 samples\r |
34 | 21 bits -> 28657..46367 samples\r |
35 | 22 bits -> 46368..75024 samples\r |
36 | 23 bits -> 75025..121392 samples\r |
37 | 24 bits -> 121393..196417 samples\r |
38 | 25 bits -> 196418..317810 samples\r |
39 | 26 bits -> 317811..514228 samples\r |
40 | 27 bits -> 514229..832039 samples\r |
41 | 28 bits -> 832040..1346268 samples\r |
42 | 29 bits -> 1346269..2178308 samples\r |
43 | 30 bits -> 2178309..3524577 samples\r |
44 | 31 bits -> 3524578..5702886 samples\r |
45 | 32 bits -> 5702887..9227464 samples\r |
46 | \r |
47 | Looking at it differently, here is where powers of 2 fall into these buckets:\r |
48 | \r |
49 | 256 samples -> 11 bits max\r |
50 | 512 samples -> 12 bits max\r |
51 | 1k samples -> 14 bits max\r |
52 | 2k samples -> 15 bits max\r |
53 | 4k samples -> 16 bits max\r |
54 | 8k samples -> 18 bits max\r |
55 | 16k samples -> 19 bits max\r |
56 | 32k samples -> 21 bits max\r |
57 | 64k samples -> 22 bits max\r |
58 | 128k samples -> 24 bits max\r |
59 | 256k samples -> 25 bits max\r |
60 | 512k samples -> 27 bits max\r |
61 | 1M samples -> 28 bits max\r |
62 | 2M samples -> 29 bits max\r |
63 | 4M samples -> 31 bits max\r |
64 | 8M samples -> 32 bits max\r |
65 | \r |
66 | ****************************************************************************\r |
67 | \r |
68 | Delta-RLE encoding works as follows:\r |
69 | \r |
70 | Starting value is assumed to be 0. All data is encoded as a delta\r |
71 | from the previous value, such that final[i] = final[i - 1] + delta.\r |
72 | Long runs of 0s are RLE-encoded as follows:\r |
73 | \r |
74 | 0x100 = repeat count of 8\r |
75 | 0x101 = repeat count of 9\r |
76 | 0x102 = repeat count of 10\r |
77 | 0x103 = repeat count of 11\r |
78 | 0x104 = repeat count of 12\r |
79 | 0x105 = repeat count of 13\r |
80 | 0x106 = repeat count of 14\r |
81 | 0x107 = repeat count of 15\r |
82 | 0x108 = repeat count of 16\r |
83 | 0x109 = repeat count of 32\r |
84 | 0x10a = repeat count of 64\r |
85 | 0x10b = repeat count of 128\r |
86 | 0x10c = repeat count of 256\r |
87 | 0x10d = repeat count of 512\r |
88 | 0x10e = repeat count of 1024\r |
89 | 0x10f = repeat count of 2048\r |
90 | \r |
91 | Note that repeat counts are reset at the end of a row, so if a 0 run\r |
92 | extends to the end of a row, a large repeat count may be used.\r |
93 | \r |
94 | The reason for starting the run counts at 8 is that 0 is expected to\r |
95 | be the most common symbol, and is typically encoded in 1 or 2 bits.\r |
96 | \r |
97 | ***************************************************************************/\r |
98 | \r |
99 | #include <stdlib.h>\r |
100 | #include <assert.h>\r |
101 | #include <stdio.h>\r |
102 | #include <string.h>\r |
103 | \r |
104 | #include "huffman.h"\r |
105 | \r |
106 | #define MAX(x,y) ((x) > (y) ? (x) : (y))\r |
107 | \r |
108 | //**************************************************************************\r |
109 | // MACROS\r |
110 | //**************************************************************************\r |
111 | \r |
112 | #define MAKE_LOOKUP(code,bits) (((code) << 5) | ((bits) & 0x1f))\r |
113 | \r |
114 | \r |
115 | //**************************************************************************\r |
116 | // IMPLEMENTATION\r |
117 | //**************************************************************************\r |
118 | \r |
119 | //-------------------------------------------------\r |
120 | // huffman_context_base - create an encoding/\r |
121 | // decoding context\r |
122 | //-------------------------------------------------\r |
123 | \r |
124 | struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits)\r |
125 | {\r |
126 | struct huffman_decoder* decoder;\r |
127 | \r |
128 | /* limit to 24 bits */\r |
129 | if (maxbits > 24)\r |
130 | return NULL;\r |
131 | \r |
132 | decoder = (struct huffman_decoder*)malloc(sizeof(struct huffman_decoder));\r |
133 | decoder->numcodes = numcodes;\r |
134 | decoder->maxbits = maxbits;\r |
135 | decoder->lookup = (lookup_value*)malloc(sizeof(lookup_value) * (1 << maxbits));\r |
136 | decoder->huffnode = (struct node_t*)malloc(sizeof(struct node_t) * numcodes);\r |
137 | decoder->datahisto = NULL;\r |
138 | decoder->prevdata = 0;\r |
139 | decoder->rleremaining = 0;\r |
140 | return decoder;\r |
141 | }\r |
142 | \r |
143 | //-------------------------------------------------\r |
144 | // decode_one - decode a single code from the\r |
145 | // huffman stream\r |
146 | //-------------------------------------------------\r |
147 | \r |
148 | uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r |
149 | {\r |
150 | /* peek ahead to get maxbits worth of data */\r |
151 | uint32_t bits = bitstream_peek(bitbuf, decoder->maxbits);\r |
152 | \r |
153 | /* look it up, then remove the actual number of bits for this code */\r |
154 | lookup_value lookup = decoder->lookup[bits];\r |
155 | bitstream_remove(bitbuf, lookup & 0x1f);\r |
156 | \r |
157 | /* return the value */\r |
158 | return lookup >> 5;\r |
159 | }\r |
160 | \r |
161 | //-------------------------------------------------\r |
162 | // import_tree_rle - import an RLE-encoded\r |
163 | // huffman tree from a source data stream\r |
164 | //-------------------------------------------------\r |
165 | \r |
166 | enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r |
167 | {\r |
168 | enum huffman_error error;\r |
169 | int curnode;\r |
170 | // bits per entry depends on the maxbits\r |
171 | int numbits;\r |
172 | if (decoder->maxbits >= 16)\r |
173 | numbits = 5;\r |
174 | else if (decoder->maxbits >= 8)\r |
175 | numbits = 4;\r |
176 | else\r |
177 | numbits = 3;\r |
178 | \r |
179 | // loop until we read all the nodes\r |
180 | for (curnode = 0; curnode < decoder->numcodes; )\r |
181 | {\r |
182 | // a non-one value is just raw\r |
183 | int nodebits = bitstream_read(bitbuf, numbits);\r |
184 | if (nodebits != 1)\r |
185 | decoder->huffnode[curnode++].numbits = nodebits;\r |
186 | \r |
187 | // a one value is an escape code\r |
188 | else\r |
189 | {\r |
190 | // a double 1 is just a single 1\r |
191 | nodebits = bitstream_read(bitbuf, numbits);\r |
192 | if (nodebits == 1)\r |
193 | decoder->huffnode[curnode++].numbits = nodebits;\r |
194 | \r |
195 | // otherwise, we need one for value for the repeat count\r |
196 | else\r |
197 | {\r |
198 | int repcount = bitstream_read(bitbuf, numbits) + 3;\r |
199 | while (repcount--)\r |
200 | decoder->huffnode[curnode++].numbits = nodebits;\r |
201 | }\r |
202 | }\r |
203 | }\r |
204 | \r |
205 | // make sure we ended up with the right number\r |
206 | if (curnode != decoder->numcodes)\r |
207 | return HUFFERR_INVALID_DATA;\r |
208 | \r |
209 | // assign canonical codes for all nodes based on their code lengths\r |
210 | error = huffman_assign_canonical_codes(decoder);\r |
211 | if (error != HUFFERR_NONE)\r |
212 | return error;\r |
213 | \r |
214 | // build the lookup table\r |
215 | huffman_build_lookup_table(decoder);\r |
216 | \r |
217 | // determine final input length and report errors\r |
218 | return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;\r |
219 | }\r |
220 | \r |
221 | \r |
222 | //-------------------------------------------------\r |
223 | // import_tree_huffman - import a huffman-encoded\r |
224 | // huffman tree from a source data stream\r |
225 | //-------------------------------------------------\r |
226 | \r |
227 | enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r |
228 | {\r |
229 | int index;\r |
230 | int start;\r |
231 | int count = 0;\r |
232 | uint8_t rlefullbits = 0;\r |
233 | int last = 0;\r |
234 | int curcode;\r |
235 | enum huffman_error error;\r |
236 | uint32_t temp;\r |
237 | // start by parsing the lengths for the small tree\r |
238 | struct huffman_decoder* smallhuff = create_huffman_decoder(24, 6);\r |
239 | \r |
240 | smallhuff->huffnode[0].numbits = bitstream_read(bitbuf, 3);\r |
241 | start = bitstream_read(bitbuf, 3) + 1;\r |
242 | \r |
243 | for (index = 1; index < 24; index++)\r |
244 | {\r |
245 | if (index < start || count == 7)\r |
246 | smallhuff->huffnode[index].numbits = 0;\r |
247 | else\r |
248 | {\r |
249 | count = bitstream_read(bitbuf, 3);\r |
250 | smallhuff->huffnode[index].numbits = (count == 7) ? 0 : count;\r |
251 | }\r |
252 | }\r |
253 | \r |
254 | // then regenerate the tree\r |
255 | error = huffman_assign_canonical_codes(smallhuff);\r |
256 | if (error != HUFFERR_NONE)\r |
257 | return error;\r |
258 | huffman_build_lookup_table(smallhuff);\r |
259 | \r |
260 | // determine the maximum length of an RLE count\r |
261 | temp = decoder->numcodes - 9;\r |
262 | while (temp != 0)\r |
263 | temp >>= 1, rlefullbits++;\r |
264 | \r |
265 | // now process the rest of the data\r |
266 | for (curcode = 0; curcode < decoder->numcodes; )\r |
267 | {\r |
268 | int value = huffman_decode_one(smallhuff, bitbuf);\r |
269 | if (value != 0)\r |
270 | decoder->huffnode[curcode++].numbits = last = value - 1;\r |
271 | else\r |
272 | {\r |
273 | int count = bitstream_read(bitbuf, 3) + 2;\r |
274 | if (count == 7+2)\r |
275 | count += bitstream_read(bitbuf, rlefullbits);\r |
276 | for ( ; count != 0 && curcode < decoder->numcodes; count--)\r |
277 | decoder->huffnode[curcode++].numbits = last;\r |
278 | }\r |
279 | }\r |
280 | \r |
281 | // make sure we ended up with the right number\r |
282 | if (curcode != decoder->numcodes)\r |
283 | return HUFFERR_INVALID_DATA;\r |
284 | \r |
285 | // assign canonical codes for all nodes based on their code lengths\r |
286 | error = huffman_assign_canonical_codes(decoder);\r |
287 | if (error != HUFFERR_NONE)\r |
288 | return error;\r |
289 | \r |
290 | // build the lookup table\r |
291 | huffman_build_lookup_table(decoder);\r |
292 | \r |
293 | // determine final input length and report errors\r |
294 | return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;\r |
295 | }\r |
296 | \r |
297 | \r |
298 | //-------------------------------------------------\r |
299 | // compute_tree_from_histo - common backend for\r |
300 | // computing a tree based on the data histogram\r |
301 | //-------------------------------------------------\r |
302 | \r |
303 | enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder)\r |
304 | {\r |
305 | int i;\r |
306 | uint32_t upperweight;\r |
307 | uint32_t lowerweight = 0;\r |
308 | // compute the number of data items in the histogram\r |
309 | uint32_t sdatacount = 0;\r |
310 | for (i = 0; i < decoder->numcodes; i++)\r |
311 | sdatacount += decoder->datahisto[i];\r |
312 | \r |
313 | // binary search to achieve the optimum encoding\r |
314 | upperweight = sdatacount * 2;\r |
315 | while (1)\r |
316 | {\r |
317 | // build a tree using the current weight\r |
318 | uint32_t curweight = (upperweight + lowerweight) / 2;\r |
319 | int curmaxbits = huffman_build_tree(decoder, sdatacount, curweight);\r |
320 | \r |
321 | // apply binary search here\r |
322 | if (curmaxbits <= decoder->maxbits)\r |
323 | {\r |
324 | lowerweight = curweight;\r |
325 | \r |
326 | // early out if it worked with the raw weights, or if we're done searching\r |
327 | if (curweight == sdatacount || (upperweight - lowerweight) <= 1)\r |
328 | break;\r |
329 | }\r |
330 | else\r |
331 | upperweight = curweight;\r |
332 | }\r |
333 | \r |
334 | // assign canonical codes for all nodes based on their code lengths\r |
335 | return huffman_assign_canonical_codes(decoder);\r |
336 | }\r |
337 | \r |
338 | \r |
339 | \r |
340 | //**************************************************************************\r |
341 | // INTERNAL FUNCTIONS\r |
342 | //**************************************************************************\r |
343 | \r |
344 | //-------------------------------------------------\r |
345 | // tree_node_compare - compare two tree nodes\r |
346 | // by weight\r |
347 | //-------------------------------------------------\r |
348 | \r |
349 | static int huffman_tree_node_compare(const void *item1, const void *item2)\r |
350 | {\r |
351 | const struct node_t *node1 = *(const struct node_t **)item1;\r |
352 | const struct node_t *node2 = *(const struct node_t **)item2;\r |
353 | if (node2->weight != node1->weight)\r |
354 | return node2->weight - node1->weight;\r |
355 | if (node2->bits - node1->bits == 0)\r |
356 | fprintf(stderr, "identical node sort keys, should not happen!\n");\r |
357 | return (int)node1->bits - (int)node2->bits;\r |
358 | }\r |
359 | \r |
360 | \r |
361 | //-------------------------------------------------\r |
362 | // build_tree - build a huffman tree based on the\r |
363 | // data distribution\r |
364 | //-------------------------------------------------\r |
365 | \r |
366 | int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight)\r |
367 | {\r |
368 | int curcode;\r |
369 | int nextalloc;\r |
370 | int maxbits = 0;\r |
371 | // make a list of all non-zero nodes\r |
372 | struct node_t** list = (struct node_t**)malloc(sizeof(struct node_t*) * decoder->numcodes * 2);\r |
373 | int listitems = 0;\r |
374 | memset(decoder->huffnode, 0, decoder->numcodes * sizeof(decoder->huffnode[0]));\r |
375 | for (curcode = 0; curcode < decoder->numcodes; curcode++)\r |
376 | if (decoder->datahisto[curcode] != 0)\r |
377 | {\r |
378 | list[listitems++] = &decoder->huffnode[curcode];\r |
379 | decoder->huffnode[curcode].count = decoder->datahisto[curcode];\r |
380 | decoder->huffnode[curcode].bits = curcode;\r |
381 | \r |
382 | // scale the weight by the current effective length, ensuring we don't go to 0\r |
383 | decoder->huffnode[curcode].weight = ((uint64_t)decoder->datahisto[curcode]) * ((uint64_t)totalweight) / ((uint64_t)totaldata);\r |
384 | if (decoder->huffnode[curcode].weight == 0)\r |
385 | decoder->huffnode[curcode].weight = 1;\r |
386 | }\r |
387 | /*\r |
388 | fprintf(stderr, "Pre-sort:\n");\r |
389 | for (int i = 0; i < listitems; i++) {\r |
390 | fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);\r |
391 | }\r |
392 | */\r |
393 | // sort the list by weight, largest weight first\r |
394 | qsort(&list[0], listitems, sizeof(list[0]), huffman_tree_node_compare);\r |
395 | /*\r |
396 | fprintf(stderr, "Post-sort:\n");\r |
397 | for (int i = 0; i < listitems; i++) {\r |
398 | fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);\r |
399 | }\r |
400 | fprintf(stderr, "===================\n");\r |
401 | */\r |
402 | // now build the tree\r |
403 | nextalloc = decoder->numcodes;\r |
404 | \r |
405 | while (listitems > 1)\r |
406 | {\r |
407 | int curitem;\r |
408 | // remove lowest two items\r |
409 | struct node_t* node1 = &(*list[--listitems]);\r |
410 | struct node_t* node0 = &(*list[--listitems]);\r |
411 | \r |
412 | // create new node\r |
413 | struct node_t* newnode = &decoder->huffnode[nextalloc++];\r |
414 | newnode->parent = NULL;\r |
415 | node0->parent = node1->parent = newnode;\r |
416 | newnode->weight = node0->weight + node1->weight;\r |
417 | \r |
418 | // insert into list at appropriate location\r |
419 | for (curitem = 0; curitem < listitems; curitem++)\r |
420 | if (newnode->weight > list[curitem]->weight)\r |
421 | {\r |
422 | memmove(&list[curitem+1], &list[curitem], (listitems - curitem) * sizeof(list[0]));\r |
423 | break;\r |
424 | }\r |
425 | list[curitem] = newnode;\r |
426 | listitems++;\r |
427 | }\r |
428 | \r |
429 | // compute the number of bits in each code, and fill in another histogram\r |
430 | for (curcode = 0; curcode < decoder->numcodes; curcode++)\r |
431 | {\r |
432 | struct node_t* node = &decoder->huffnode[curcode];\r |
433 | node->numbits = 0;\r |
434 | node->bits = 0;\r |
435 | \r |
436 | // if we have a non-zero weight, compute the number of bits\r |
437 | if (node->weight > 0)\r |
438 | {\r |
439 | struct node_t *curnode;\r |
440 | // determine the number of bits for this node\r |
441 | for (curnode = node; curnode->parent != NULL; curnode = curnode->parent)\r |
442 | node->numbits++;\r |
443 | if (node->numbits == 0)\r |
444 | node->numbits = 1;\r |
445 | \r |
446 | // keep track of the max\r |
447 | maxbits = MAX(maxbits, ((int)node->numbits));\r |
448 | }\r |
449 | }\r |
450 | return maxbits;\r |
451 | }\r |
452 | \r |
453 | \r |
454 | //-------------------------------------------------\r |
455 | // assign_canonical_codes - assign canonical codes\r |
456 | // to all the nodes based on the number of bits\r |
457 | // in each\r |
458 | //-------------------------------------------------\r |
459 | \r |
460 | enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder)\r |
461 | {\r |
462 | int curcode, codelen;\r |
463 | uint32_t curstart = 0;\r |
464 | \r |
465 | // build up a histogram of bit lengths\r |
466 | uint32_t bithisto[33] = { 0 };\r |
467 | for (curcode = 0; curcode < decoder->numcodes; curcode++)\r |
468 | {\r |
469 | struct node_t* node = &decoder->huffnode[curcode];\r |
470 | if (node->numbits > decoder->maxbits)\r |
471 | return HUFFERR_INTERNAL_INCONSISTENCY;\r |
472 | if (node->numbits <= 32)\r |
473 | bithisto[node->numbits]++;\r |
474 | }\r |
475 | \r |
476 | // for each code length, determine the starting code number\r |
477 | for (codelen = 32; codelen > 0; codelen--)\r |
478 | {\r |
479 | uint32_t nextstart = (curstart + bithisto[codelen]) >> 1;\r |
480 | if (codelen != 1 && nextstart * 2 != (curstart + bithisto[codelen]))\r |
481 | return HUFFERR_INTERNAL_INCONSISTENCY;\r |
482 | bithisto[codelen] = curstart;\r |
483 | curstart = nextstart;\r |
484 | }\r |
485 | \r |
486 | // now assign canonical codes\r |
487 | for (curcode = 0; curcode < decoder->numcodes; curcode++)\r |
488 | {\r |
489 | struct node_t* node = &decoder->huffnode[curcode];\r |
490 | if (node->numbits > 0)\r |
491 | node->bits = bithisto[node->numbits]++;\r |
492 | }\r |
493 | return HUFFERR_NONE;\r |
494 | }\r |
495 | \r |
496 | \r |
497 | //-------------------------------------------------\r |
498 | // build_lookup_table - build a lookup table for\r |
499 | // fast decoding\r |
500 | //-------------------------------------------------\r |
501 | \r |
502 | void huffman_build_lookup_table(struct huffman_decoder* decoder)\r |
503 | {\r |
504 | int curcode;\r |
505 | // iterate over all codes\r |
506 | for (curcode = 0; curcode < decoder->numcodes; curcode++)\r |
507 | {\r |
508 | // process all nodes which have non-zero bits\r |
509 | struct node_t* node = &decoder->huffnode[curcode];\r |
510 | if (node->numbits > 0)\r |
511 | {\r |
512 | int shift;\r |
513 | lookup_value *dest;\r |
514 | lookup_value *destend;\r |
515 | \r |
516 | // set up the entry\r |
517 | lookup_value value = MAKE_LOOKUP(curcode, node->numbits);\r |
518 | \r |
519 | // fill all matching entries\r |
520 | shift = decoder->maxbits - node->numbits;\r |
521 | dest = &decoder->lookup[node->bits << shift];\r |
522 | destend = &decoder->lookup[((node->bits + 1) << shift) - 1];\r |
523 | \r |
524 | while (dest <= destend)\r |
525 | *dest++ = value;\r |
526 | }\r |
527 | }\r |
528 | }\r |