1 // license:BSD-3-Clause
\r
2 // copyright-holders:Aaron Giles
\r
3 /***************************************************************************
\r
7 Static Huffman compression and decompression helpers.
\r
9 ****************************************************************************
\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
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
47 Looking at it differently, here is where powers of 2 fall into these buckets:
\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
66 ****************************************************************************
\r
68 Delta-RLE encoding works as follows:
\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
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
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
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
97 ***************************************************************************/
\r
100 #include <assert.h>
\r
102 #include <string.h>
\r
104 #include "huffman.h"
\r
106 #define MAX(x,y) ((x) > (y) ? (x) : (y))
\r
108 //**************************************************************************
\r
110 //**************************************************************************
\r
112 #define MAKE_LOOKUP(code,bits) (((code) << 5) | ((bits) & 0x1f))
\r
115 //**************************************************************************
\r
117 //**************************************************************************
\r
119 //-------------------------------------------------
\r
120 // huffman_context_base - create an encoding/
\r
121 // decoding context
\r
122 //-------------------------------------------------
\r
124 struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits)
\r
126 struct huffman_decoder* decoder;
\r
128 /* limit to 24 bits */
\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
143 //-------------------------------------------------
\r
144 // decode_one - decode a single code from the
\r
146 //-------------------------------------------------
\r
148 uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf)
\r
150 /* peek ahead to get maxbits worth of data */
\r
151 uint32_t bits = bitstream_peek(bitbuf, decoder->maxbits);
\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
157 /* return the value */
\r
158 return lookup >> 5;
\r
161 //-------------------------------------------------
\r
162 // import_tree_rle - import an RLE-encoded
\r
163 // huffman tree from a source data stream
\r
164 //-------------------------------------------------
\r
166 enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf)
\r
168 enum huffman_error error;
\r
170 // bits per entry depends on the maxbits
\r
172 if (decoder->maxbits >= 16)
\r
174 else if (decoder->maxbits >= 8)
\r
179 // loop until we read all the nodes
\r
180 for (curnode = 0; curnode < decoder->numcodes; )
\r
182 // a non-one value is just raw
\r
183 int nodebits = bitstream_read(bitbuf, numbits);
\r
185 decoder->huffnode[curnode++].numbits = nodebits;
\r
187 // a one value is an escape code
\r
190 // a double 1 is just a single 1
\r
191 nodebits = bitstream_read(bitbuf, numbits);
\r
193 decoder->huffnode[curnode++].numbits = nodebits;
\r
195 // otherwise, we need one for value for the repeat count
\r
198 int repcount = bitstream_read(bitbuf, numbits) + 3;
\r
200 decoder->huffnode[curnode++].numbits = nodebits;
\r
205 // make sure we ended up with the right number
\r
206 if (curnode != decoder->numcodes)
\r
207 return HUFFERR_INVALID_DATA;
\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
214 // build the lookup table
\r
215 huffman_build_lookup_table(decoder);
\r
217 // determine final input length and report errors
\r
218 return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
\r
222 //-------------------------------------------------
\r
223 // import_tree_huffman - import a huffman-encoded
\r
224 // huffman tree from a source data stream
\r
225 //-------------------------------------------------
\r
227 enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf)
\r
232 uint8_t rlefullbits = 0;
\r
235 enum huffman_error error;
\r
237 // start by parsing the lengths for the small tree
\r
238 struct huffman_decoder* smallhuff = create_huffman_decoder(24, 6);
\r
240 smallhuff->huffnode[0].numbits = bitstream_read(bitbuf, 3);
\r
241 start = bitstream_read(bitbuf, 3) + 1;
\r
243 for (index = 1; index < 24; index++)
\r
245 if (index < start || count == 7)
\r
246 smallhuff->huffnode[index].numbits = 0;
\r
249 count = bitstream_read(bitbuf, 3);
\r
250 smallhuff->huffnode[index].numbits = (count == 7) ? 0 : count;
\r
254 // then regenerate the tree
\r
255 error = huffman_assign_canonical_codes(smallhuff);
\r
256 if (error != HUFFERR_NONE)
\r
258 huffman_build_lookup_table(smallhuff);
\r
260 // determine the maximum length of an RLE count
\r
261 temp = decoder->numcodes - 9;
\r
263 temp >>= 1, rlefullbits++;
\r
265 // now process the rest of the data
\r
266 for (curcode = 0; curcode < decoder->numcodes; )
\r
268 int value = huffman_decode_one(smallhuff, bitbuf);
\r
270 decoder->huffnode[curcode++].numbits = last = value - 1;
\r
273 int count = bitstream_read(bitbuf, 3) + 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
281 // make sure we ended up with the right number
\r
282 if (curcode != decoder->numcodes)
\r
283 return HUFFERR_INVALID_DATA;
\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
290 // build the lookup table
\r
291 huffman_build_lookup_table(decoder);
\r
293 // determine final input length and report errors
\r
294 return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
\r
298 //-------------------------------------------------
\r
299 // compute_tree_from_histo - common backend for
\r
300 // computing a tree based on the data histogram
\r
301 //-------------------------------------------------
\r
303 enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder)
\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
313 // binary search to achieve the optimum encoding
\r
314 upperweight = sdatacount * 2;
\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
321 // apply binary search here
\r
322 if (curmaxbits <= decoder->maxbits)
\r
324 lowerweight = curweight;
\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
331 upperweight = curweight;
\r
334 // assign canonical codes for all nodes based on their code lengths
\r
335 return huffman_assign_canonical_codes(decoder);
\r
340 //**************************************************************************
\r
341 // INTERNAL FUNCTIONS
\r
342 //**************************************************************************
\r
344 //-------------------------------------------------
\r
345 // tree_node_compare - compare two tree nodes
\r
347 //-------------------------------------------------
\r
349 static int huffman_tree_node_compare(const void *item1, const void *item2)
\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
361 //-------------------------------------------------
\r
362 // build_tree - build a huffman tree based on the
\r
363 // data distribution
\r
364 //-------------------------------------------------
\r
366 int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight)
\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
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
378 list[listitems++] = &decoder->huffnode[curcode];
\r
379 decoder->huffnode[curcode].count = decoder->datahisto[curcode];
\r
380 decoder->huffnode[curcode].bits = curcode;
\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
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
393 // sort the list by weight, largest weight first
\r
394 qsort(&list[0], listitems, sizeof(list[0]), huffman_tree_node_compare);
\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
400 fprintf(stderr, "===================\n");
\r
402 // now build the tree
\r
403 nextalloc = decoder->numcodes;
\r
405 while (listitems > 1)
\r
408 // remove lowest two items
\r
409 struct node_t* node1 = &(*list[--listitems]);
\r
410 struct node_t* node0 = &(*list[--listitems]);
\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
418 // insert into list at appropriate location
\r
419 for (curitem = 0; curitem < listitems; curitem++)
\r
420 if (newnode->weight > list[curitem]->weight)
\r
422 memmove(&list[curitem+1], &list[curitem], (listitems - curitem) * sizeof(list[0]));
\r
425 list[curitem] = newnode;
\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
432 struct node_t* node = &decoder->huffnode[curcode];
\r
436 // if we have a non-zero weight, compute the number of bits
\r
437 if (node->weight > 0)
\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
443 if (node->numbits == 0)
\r
446 // keep track of the max
\r
447 maxbits = MAX(maxbits, ((int)node->numbits));
\r
454 //-------------------------------------------------
\r
455 // assign_canonical_codes - assign canonical codes
\r
456 // to all the nodes based on the number of bits
\r
458 //-------------------------------------------------
\r
460 enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder)
\r
462 int curcode, codelen;
\r
463 uint32_t curstart = 0;
\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
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
476 // for each code length, determine the starting code number
\r
477 for (codelen = 32; codelen > 0; codelen--)
\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
486 // now assign canonical codes
\r
487 for (curcode = 0; curcode < decoder->numcodes; curcode++)
\r
489 struct node_t* node = &decoder->huffnode[curcode];
\r
490 if (node->numbits > 0)
\r
491 node->bits = bithisto[node->numbits]++;
\r
493 return HUFFERR_NONE;
\r
497 //-------------------------------------------------
\r
498 // build_lookup_table - build a lookup table for
\r
500 //-------------------------------------------------
\r
502 void huffman_build_lookup_table(struct huffman_decoder* decoder)
\r
505 // iterate over all codes
\r
506 for (curcode = 0; curcode < decoder->numcodes; curcode++)
\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
513 lookup_value *dest;
\r
514 lookup_value *destend;
\r
516 // set up the entry
\r
517 lookup_value value = MAKE_LOOKUP(curcode, node->numbits);
\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
524 while (dest <= destend)
\r