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