-// license:BSD-3-Clause\r
-// copyright-holders:Aaron Giles\r
-/***************************************************************************\r
-\r
- huffman.c\r
-\r
- Static Huffman compression and decompression helpers.\r
-\r
-****************************************************************************\r
-\r
- Maximum codelength is officially (alphabetsize - 1). This would be 255 bits\r
- (since we use 1 byte values). However, it is also dependent upon the number\r
- of samples used, as follows:\r
-\r
- 2 bits -> 3..4 samples\r
- 3 bits -> 5..7 samples\r
- 4 bits -> 8..12 samples\r
- 5 bits -> 13..20 samples\r
- 6 bits -> 21..33 samples\r
- 7 bits -> 34..54 samples\r
- 8 bits -> 55..88 samples\r
- 9 bits -> 89..143 samples\r
- 10 bits -> 144..232 samples\r
- 11 bits -> 233..376 samples\r
- 12 bits -> 377..609 samples\r
- 13 bits -> 610..986 samples\r
- 14 bits -> 987..1596 samples\r
- 15 bits -> 1597..2583 samples\r
- 16 bits -> 2584..4180 samples -> note that a 4k data size guarantees codelength <= 16 bits\r
- 17 bits -> 4181..6764 samples\r
- 18 bits -> 6765..10945 samples\r
- 19 bits -> 10946..17710 samples\r
- 20 bits -> 17711..28656 samples\r
- 21 bits -> 28657..46367 samples\r
- 22 bits -> 46368..75024 samples\r
- 23 bits -> 75025..121392 samples\r
- 24 bits -> 121393..196417 samples\r
- 25 bits -> 196418..317810 samples\r
- 26 bits -> 317811..514228 samples\r
- 27 bits -> 514229..832039 samples\r
- 28 bits -> 832040..1346268 samples\r
- 29 bits -> 1346269..2178308 samples\r
- 30 bits -> 2178309..3524577 samples\r
- 31 bits -> 3524578..5702886 samples\r
- 32 bits -> 5702887..9227464 samples\r
-\r
- Looking at it differently, here is where powers of 2 fall into these buckets:\r
-\r
- 256 samples -> 11 bits max\r
- 512 samples -> 12 bits max\r
- 1k samples -> 14 bits max\r
- 2k samples -> 15 bits max\r
- 4k samples -> 16 bits max\r
- 8k samples -> 18 bits max\r
- 16k samples -> 19 bits max\r
- 32k samples -> 21 bits max\r
- 64k samples -> 22 bits max\r
- 128k samples -> 24 bits max\r
- 256k samples -> 25 bits max\r
- 512k samples -> 27 bits max\r
- 1M samples -> 28 bits max\r
- 2M samples -> 29 bits max\r
- 4M samples -> 31 bits max\r
- 8M samples -> 32 bits max\r
-\r
-****************************************************************************\r
-\r
- Delta-RLE encoding works as follows:\r
-\r
- Starting value is assumed to be 0. All data is encoded as a delta\r
- from the previous value, such that final[i] = final[i - 1] + delta.\r
- Long runs of 0s are RLE-encoded as follows:\r
-\r
- 0x100 = repeat count of 8\r
- 0x101 = repeat count of 9\r
- 0x102 = repeat count of 10\r
- 0x103 = repeat count of 11\r
- 0x104 = repeat count of 12\r
- 0x105 = repeat count of 13\r
- 0x106 = repeat count of 14\r
- 0x107 = repeat count of 15\r
- 0x108 = repeat count of 16\r
- 0x109 = repeat count of 32\r
- 0x10a = repeat count of 64\r
- 0x10b = repeat count of 128\r
- 0x10c = repeat count of 256\r
- 0x10d = repeat count of 512\r
- 0x10e = repeat count of 1024\r
- 0x10f = repeat count of 2048\r
-\r
- Note that repeat counts are reset at the end of a row, so if a 0 run\r
- extends to the end of a row, a large repeat count may be used.\r
-\r
- The reason for starting the run counts at 8 is that 0 is expected to\r
- be the most common symbol, and is typically encoded in 1 or 2 bits.\r
-\r
-***************************************************************************/\r
-\r
-#include <stdlib.h>\r
-#include <assert.h>\r
-#include <stdio.h>\r
-#include <string.h>\r
-\r
-#include "huffman.h"\r
-\r
-#define MAX(x,y) ((x) > (y) ? (x) : (y))\r
-\r
-//**************************************************************************\r
-// MACROS\r
-//**************************************************************************\r
-\r
-#define MAKE_LOOKUP(code,bits) (((code) << 5) | ((bits) & 0x1f))\r
-\r
-\r
-//**************************************************************************\r
-// IMPLEMENTATION\r
-//**************************************************************************\r
-\r
-//-------------------------------------------------\r
-// huffman_context_base - create an encoding/\r
-// decoding context\r
-//-------------------------------------------------\r
-\r
-struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits)\r
-{\r
- struct huffman_decoder* decoder;\r
-\r
- /* limit to 24 bits */\r
- if (maxbits > 24)\r
- return NULL;\r
-\r
- decoder = (struct huffman_decoder*)malloc(sizeof(struct huffman_decoder));\r
- decoder->numcodes = numcodes;\r
- decoder->maxbits = maxbits;\r
- decoder->lookup = (lookup_value*)malloc(sizeof(lookup_value) * (1 << maxbits));\r
- decoder->huffnode = (struct node_t*)malloc(sizeof(struct node_t) * numcodes);\r
- decoder->datahisto = NULL;\r
- decoder->prevdata = 0;\r
- decoder->rleremaining = 0;\r
- return decoder;\r
-}\r
-\r
-//-------------------------------------------------\r
-// decode_one - decode a single code from the\r
-// huffman stream\r
-//-------------------------------------------------\r
-\r
-uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
-{\r
- /* peek ahead to get maxbits worth of data */\r
- uint32_t bits = bitstream_peek(bitbuf, decoder->maxbits);\r
-\r
- /* look it up, then remove the actual number of bits for this code */\r
- lookup_value lookup = decoder->lookup[bits];\r
- bitstream_remove(bitbuf, lookup & 0x1f);\r
-\r
- /* return the value */\r
- return lookup >> 5;\r
-}\r
-\r
-//-------------------------------------------------\r
-// import_tree_rle - import an RLE-encoded\r
-// huffman tree from a source data stream\r
-//-------------------------------------------------\r
-\r
-enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
-{\r
- enum huffman_error error;\r
- int curnode;\r
- // bits per entry depends on the maxbits\r
- int numbits;\r
- if (decoder->maxbits >= 16)\r
- numbits = 5;\r
- else if (decoder->maxbits >= 8)\r
- numbits = 4;\r
- else\r
- numbits = 3;\r
-\r
- // loop until we read all the nodes\r
- for (curnode = 0; curnode < decoder->numcodes; )\r
- {\r
- // a non-one value is just raw\r
- int nodebits = bitstream_read(bitbuf, numbits);\r
- if (nodebits != 1)\r
- decoder->huffnode[curnode++].numbits = nodebits;\r
-\r
- // a one value is an escape code\r
- else\r
- {\r
- // a double 1 is just a single 1\r
- nodebits = bitstream_read(bitbuf, numbits);\r
- if (nodebits == 1)\r
- decoder->huffnode[curnode++].numbits = nodebits;\r
-\r
- // otherwise, we need one for value for the repeat count\r
- else\r
- {\r
- int repcount = bitstream_read(bitbuf, numbits) + 3;\r
- while (repcount--)\r
- decoder->huffnode[curnode++].numbits = nodebits;\r
- }\r
- }\r
- }\r
-\r
- // make sure we ended up with the right number\r
- if (curnode != decoder->numcodes)\r
- return HUFFERR_INVALID_DATA;\r
-\r
- // assign canonical codes for all nodes based on their code lengths\r
- error = huffman_assign_canonical_codes(decoder);\r
- if (error != HUFFERR_NONE)\r
- return error;\r
-\r
- // build the lookup table\r
- huffman_build_lookup_table(decoder);\r
-\r
- // determine final input length and report errors\r
- return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;\r
-}\r
-\r
-\r
-//-------------------------------------------------\r
-// import_tree_huffman - import a huffman-encoded\r
-// huffman tree from a source data stream\r
-//-------------------------------------------------\r
-\r
-enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
-{\r
- int index;\r
- int start;\r
- int count = 0;\r
- uint8_t rlefullbits = 0;\r
- int last = 0;\r
- int curcode;\r
- enum huffman_error error;\r
- uint32_t temp;\r
- // start by parsing the lengths for the small tree\r
- struct huffman_decoder* smallhuff = create_huffman_decoder(24, 6);\r
-\r
- smallhuff->huffnode[0].numbits = bitstream_read(bitbuf, 3);\r
- start = bitstream_read(bitbuf, 3) + 1;\r
-\r
- for (index = 1; index < 24; index++)\r
- {\r
- if (index < start || count == 7)\r
- smallhuff->huffnode[index].numbits = 0;\r
- else\r
- {\r
- count = bitstream_read(bitbuf, 3);\r
- smallhuff->huffnode[index].numbits = (count == 7) ? 0 : count;\r
- }\r
- }\r
-\r
- // then regenerate the tree\r
- error = huffman_assign_canonical_codes(smallhuff);\r
- if (error != HUFFERR_NONE)\r
- return error;\r
- huffman_build_lookup_table(smallhuff);\r
-\r
- // determine the maximum length of an RLE count\r
- temp = decoder->numcodes - 9;\r
- while (temp != 0)\r
- temp >>= 1, rlefullbits++;\r
-\r
- // now process the rest of the data\r
- for (curcode = 0; curcode < decoder->numcodes; )\r
- {\r
- int value = huffman_decode_one(smallhuff, bitbuf);\r
- if (value != 0)\r
- decoder->huffnode[curcode++].numbits = last = value - 1;\r
- else\r
- {\r
- int count = bitstream_read(bitbuf, 3) + 2;\r
- if (count == 7+2)\r
- count += bitstream_read(bitbuf, rlefullbits);\r
- for ( ; count != 0 && curcode < decoder->numcodes; count--)\r
- decoder->huffnode[curcode++].numbits = last;\r
- }\r
- }\r
-\r
- // make sure we ended up with the right number\r
- if (curcode != decoder->numcodes)\r
- return HUFFERR_INVALID_DATA;\r
-\r
- // assign canonical codes for all nodes based on their code lengths\r
- error = huffman_assign_canonical_codes(decoder);\r
- if (error != HUFFERR_NONE)\r
- return error;\r
-\r
- // build the lookup table\r
- huffman_build_lookup_table(decoder);\r
-\r
- // determine final input length and report errors\r
- return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;\r
-}\r
-\r
-\r
-//-------------------------------------------------\r
-// compute_tree_from_histo - common backend for\r
-// computing a tree based on the data histogram\r
-//-------------------------------------------------\r
-\r
-enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder)\r
-{\r
- int i;\r
- uint32_t upperweight;\r
- uint32_t lowerweight = 0;\r
- // compute the number of data items in the histogram\r
- uint32_t sdatacount = 0;\r
- for (i = 0; i < decoder->numcodes; i++)\r
- sdatacount += decoder->datahisto[i];\r
-\r
- // binary search to achieve the optimum encoding\r
- upperweight = sdatacount * 2;\r
- while (1)\r
- {\r
- // build a tree using the current weight\r
- uint32_t curweight = (upperweight + lowerweight) / 2;\r
- int curmaxbits = huffman_build_tree(decoder, sdatacount, curweight);\r
-\r
- // apply binary search here\r
- if (curmaxbits <= decoder->maxbits)\r
- {\r
- lowerweight = curweight;\r
-\r
- // early out if it worked with the raw weights, or if we're done searching\r
- if (curweight == sdatacount || (upperweight - lowerweight) <= 1)\r
- break;\r
- }\r
- else\r
- upperweight = curweight;\r
- }\r
-\r
- // assign canonical codes for all nodes based on their code lengths\r
- return huffman_assign_canonical_codes(decoder);\r
-}\r
-\r
-\r
-\r
-//**************************************************************************\r
-// INTERNAL FUNCTIONS\r
-//**************************************************************************\r
-\r
-//-------------------------------------------------\r
-// tree_node_compare - compare two tree nodes\r
-// by weight\r
-//-------------------------------------------------\r
-\r
-static int huffman_tree_node_compare(const void *item1, const void *item2)\r
-{\r
- const struct node_t *node1 = *(const struct node_t **)item1;\r
- const struct node_t *node2 = *(const struct node_t **)item2;\r
- if (node2->weight != node1->weight)\r
- return node2->weight - node1->weight;\r
- if (node2->bits - node1->bits == 0)\r
- fprintf(stderr, "identical node sort keys, should not happen!\n");\r
- return (int)node1->bits - (int)node2->bits;\r
-}\r
-\r
-\r
-//-------------------------------------------------\r
-// build_tree - build a huffman tree based on the\r
-// data distribution\r
-//-------------------------------------------------\r
-\r
-int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight)\r
-{\r
- int curcode;\r
- int nextalloc;\r
- int maxbits = 0;\r
- // make a list of all non-zero nodes\r
- struct node_t** list = (struct node_t**)malloc(sizeof(struct node_t*) * decoder->numcodes * 2);\r
- int listitems = 0;\r
- memset(decoder->huffnode, 0, decoder->numcodes * sizeof(decoder->huffnode[0]));\r
- for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
- if (decoder->datahisto[curcode] != 0)\r
- {\r
- list[listitems++] = &decoder->huffnode[curcode];\r
- decoder->huffnode[curcode].count = decoder->datahisto[curcode];\r
- decoder->huffnode[curcode].bits = curcode;\r
-\r
- // scale the weight by the current effective length, ensuring we don't go to 0\r
- decoder->huffnode[curcode].weight = ((uint64_t)decoder->datahisto[curcode]) * ((uint64_t)totalweight) / ((uint64_t)totaldata);\r
- if (decoder->huffnode[curcode].weight == 0)\r
- decoder->huffnode[curcode].weight = 1;\r
- }\r
-/*\r
- fprintf(stderr, "Pre-sort:\n");\r
- for (int i = 0; i < listitems; i++) {\r
- fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);\r
- }\r
-*/\r
- // sort the list by weight, largest weight first\r
- qsort(&list[0], listitems, sizeof(list[0]), huffman_tree_node_compare);\r
-/*\r
- fprintf(stderr, "Post-sort:\n");\r
- for (int i = 0; i < listitems; i++) {\r
- fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);\r
- }\r
- fprintf(stderr, "===================\n");\r
-*/\r
- // now build the tree\r
- nextalloc = decoder->numcodes;\r
-\r
- while (listitems > 1)\r
- {\r
- int curitem;\r
- // remove lowest two items\r
- struct node_t* node1 = &(*list[--listitems]);\r
- struct node_t* node0 = &(*list[--listitems]);\r
-\r
- // create new node\r
- struct node_t* newnode = &decoder->huffnode[nextalloc++];\r
- newnode->parent = NULL;\r
- node0->parent = node1->parent = newnode;\r
- newnode->weight = node0->weight + node1->weight;\r
-\r
- // insert into list at appropriate location\r
- for (curitem = 0; curitem < listitems; curitem++)\r
- if (newnode->weight > list[curitem]->weight)\r
- {\r
- memmove(&list[curitem+1], &list[curitem], (listitems - curitem) * sizeof(list[0]));\r
- break;\r
- }\r
- list[curitem] = newnode;\r
- listitems++;\r
- }\r
-\r
- // compute the number of bits in each code, and fill in another histogram\r
- for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
- {\r
- struct node_t* node = &decoder->huffnode[curcode];\r
- node->numbits = 0;\r
- node->bits = 0;\r
-\r
- // if we have a non-zero weight, compute the number of bits\r
- if (node->weight > 0)\r
- {\r
- struct node_t *curnode;\r
- // determine the number of bits for this node\r
- for (curnode = node; curnode->parent != NULL; curnode = curnode->parent)\r
- node->numbits++;\r
- if (node->numbits == 0)\r
- node->numbits = 1;\r
-\r
- // keep track of the max\r
- maxbits = MAX(maxbits, ((int)node->numbits));\r
- }\r
- }\r
- return maxbits;\r
-}\r
-\r
-\r
-//-------------------------------------------------\r
-// assign_canonical_codes - assign canonical codes\r
-// to all the nodes based on the number of bits\r
-// in each\r
-//-------------------------------------------------\r
-\r
-enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder)\r
-{\r
- int curcode, codelen;\r
- uint32_t curstart = 0;\r
-\r
- // build up a histogram of bit lengths\r
- uint32_t bithisto[33] = { 0 };\r
- for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
- {\r
- struct node_t* node = &decoder->huffnode[curcode];\r
- if (node->numbits > decoder->maxbits)\r
- return HUFFERR_INTERNAL_INCONSISTENCY;\r
- if (node->numbits <= 32)\r
- bithisto[node->numbits]++;\r
- }\r
-\r
- // for each code length, determine the starting code number\r
- for (codelen = 32; codelen > 0; codelen--)\r
- {\r
- uint32_t nextstart = (curstart + bithisto[codelen]) >> 1;\r
- if (codelen != 1 && nextstart * 2 != (curstart + bithisto[codelen]))\r
- return HUFFERR_INTERNAL_INCONSISTENCY;\r
- bithisto[codelen] = curstart;\r
- curstart = nextstart;\r
- }\r
-\r
- // now assign canonical codes\r
- for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
- {\r
- struct node_t* node = &decoder->huffnode[curcode];\r
- if (node->numbits > 0)\r
- node->bits = bithisto[node->numbits]++;\r
- }\r
- return HUFFERR_NONE;\r
-}\r
-\r
-\r
-//-------------------------------------------------\r
-// build_lookup_table - build a lookup table for\r
-// fast decoding\r
-//-------------------------------------------------\r
-\r
-void huffman_build_lookup_table(struct huffman_decoder* decoder)\r
-{\r
- int curcode;\r
- // iterate over all codes\r
- for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
- {\r
- // process all nodes which have non-zero bits\r
- struct node_t* node = &decoder->huffnode[curcode];\r
- if (node->numbits > 0)\r
- {\r
- int shift;\r
- lookup_value *dest;\r
- lookup_value *destend;\r
-\r
- // set up the entry\r
- lookup_value value = MAKE_LOOKUP(curcode, node->numbits);\r
-\r
- // fill all matching entries\r
- shift = decoder->maxbits - node->numbits;\r
- dest = &decoder->lookup[node->bits << shift];\r
- destend = &decoder->lookup[((node->bits + 1) << shift) - 1];\r
-\r
- while (dest <= destend)\r
- *dest++ = value;\r
- }\r
- }\r
-}\r
+/* license:BSD-3-Clause
+ * copyright-holders:Aaron Giles
+****************************************************************************
+
+ huffman.c
+
+ Static Huffman compression and decompression helpers.
+
+****************************************************************************
+
+ Maximum codelength is officially (alphabetsize - 1). This would be 255 bits
+ (since we use 1 byte values). However, it is also dependent upon the number
+ of samples used, as follows:
+
+ 2 bits -> 3..4 samples
+ 3 bits -> 5..7 samples
+ 4 bits -> 8..12 samples
+ 5 bits -> 13..20 samples
+ 6 bits -> 21..33 samples
+ 7 bits -> 34..54 samples
+ 8 bits -> 55..88 samples
+ 9 bits -> 89..143 samples
+ 10 bits -> 144..232 samples
+ 11 bits -> 233..376 samples
+ 12 bits -> 377..609 samples
+ 13 bits -> 610..986 samples
+ 14 bits -> 987..1596 samples
+ 15 bits -> 1597..2583 samples
+ 16 bits -> 2584..4180 samples -> note that a 4k data size guarantees codelength <= 16 bits
+ 17 bits -> 4181..6764 samples
+ 18 bits -> 6765..10945 samples
+ 19 bits -> 10946..17710 samples
+ 20 bits -> 17711..28656 samples
+ 21 bits -> 28657..46367 samples
+ 22 bits -> 46368..75024 samples
+ 23 bits -> 75025..121392 samples
+ 24 bits -> 121393..196417 samples
+ 25 bits -> 196418..317810 samples
+ 26 bits -> 317811..514228 samples
+ 27 bits -> 514229..832039 samples
+ 28 bits -> 832040..1346268 samples
+ 29 bits -> 1346269..2178308 samples
+ 30 bits -> 2178309..3524577 samples
+ 31 bits -> 3524578..5702886 samples
+ 32 bits -> 5702887..9227464 samples
+
+ Looking at it differently, here is where powers of 2 fall into these buckets:
+
+ 256 samples -> 11 bits max
+ 512 samples -> 12 bits max
+ 1k samples -> 14 bits max
+ 2k samples -> 15 bits max
+ 4k samples -> 16 bits max
+ 8k samples -> 18 bits max
+ 16k samples -> 19 bits max
+ 32k samples -> 21 bits max
+ 64k samples -> 22 bits max
+ 128k samples -> 24 bits max
+ 256k samples -> 25 bits max
+ 512k samples -> 27 bits max
+ 1M samples -> 28 bits max
+ 2M samples -> 29 bits max
+ 4M samples -> 31 bits max
+ 8M samples -> 32 bits max
+
+****************************************************************************
+
+ Delta-RLE encoding works as follows:
+
+ Starting value is assumed to be 0. All data is encoded as a delta
+ from the previous value, such that final[i] = final[i - 1] + delta.
+ Long runs of 0s are RLE-encoded as follows:
+
+ 0x100 = repeat count of 8
+ 0x101 = repeat count of 9
+ 0x102 = repeat count of 10
+ 0x103 = repeat count of 11
+ 0x104 = repeat count of 12
+ 0x105 = repeat count of 13
+ 0x106 = repeat count of 14
+ 0x107 = repeat count of 15
+ 0x108 = repeat count of 16
+ 0x109 = repeat count of 32
+ 0x10a = repeat count of 64
+ 0x10b = repeat count of 128
+ 0x10c = repeat count of 256
+ 0x10d = repeat count of 512
+ 0x10e = repeat count of 1024
+ 0x10f = repeat count of 2048
+
+ Note that repeat counts are reset at the end of a row, so if a 0 run
+ extends to the end of a row, a large repeat count may be used.
+
+ The reason for starting the run counts at 8 is that 0 is expected to
+ be the most common symbol, and is typically encoded in 1 or 2 bits.
+
+***************************************************************************/
+
+#include <stdlib.h>
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "huffman.h"
+
+#define MAX(x,y) ((x) > (y) ? (x) : (y))
+
+/***************************************************************************
+ * MACROS
+ ***************************************************************************
+ */
+
+#define MAKE_LOOKUP(code,bits) (((code) << 5) | ((bits) & 0x1f))
+
+/***************************************************************************
+ * IMPLEMENTATION
+ ***************************************************************************
+ */
+
+/*-------------------------------------------------
+ * huffman_context_base - create an encoding/
+ * decoding context
+ *-------------------------------------------------
+ */
+
+struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits)
+{
+ struct huffman_decoder* decoder = NULL;
+
+ /* limit to 24 bits */
+ if (maxbits > 24)
+ return NULL;
+
+ decoder = (struct huffman_decoder*)malloc(sizeof(struct huffman_decoder));
+ decoder->numcodes = numcodes;
+ decoder->maxbits = maxbits;
+ decoder->lookup = (lookup_value*)malloc(sizeof(lookup_value) * (1 << maxbits));
+ decoder->huffnode = (struct node_t*)malloc(sizeof(struct node_t) * numcodes);
+ decoder->datahisto = NULL;
+ decoder->prevdata = 0;
+ decoder->rleremaining = 0;
+ return decoder;
+}
+
+/*-------------------------------------------------
+ * decode_one - decode a single code from the
+ * huffman stream
+ *-------------------------------------------------
+ */
+
+uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf)
+{
+ /* peek ahead to get maxbits worth of data */
+ uint32_t bits = bitstream_peek(bitbuf, decoder->maxbits);
+
+ /* look it up, then remove the actual number of bits for this code */
+ lookup_value lookup = decoder->lookup[bits];
+ bitstream_remove(bitbuf, lookup & 0x1f);
+
+ /* return the value */
+ return lookup >> 5;
+}
+
+/*-------------------------------------------------
+ * import_tree_rle - import an RLE-encoded
+ * huffman tree from a source data stream
+ *-------------------------------------------------
+ */
+
+enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf)
+{
+ int numbits, curnode;
+ enum huffman_error error;
+
+ /* bits per entry depends on the maxbits */
+ if (decoder->maxbits >= 16)
+ numbits = 5;
+ else if (decoder->maxbits >= 8)
+ numbits = 4;
+ else
+ numbits = 3;
+
+ /* loop until we read all the nodes */
+ for (curnode = 0; curnode < decoder->numcodes; )
+ {
+ /* a non-one value is just raw */
+ int nodebits = bitstream_read(bitbuf, numbits);
+ if (nodebits != 1)
+ decoder->huffnode[curnode++].numbits = nodebits;
+
+ /* a one value is an escape code */
+ else
+ {
+ /* a double 1 is just a single 1 */
+ nodebits = bitstream_read(bitbuf, numbits);
+ if (nodebits == 1)
+ decoder->huffnode[curnode++].numbits = nodebits;
+
+ /* otherwise, we need one for value for the repeat count */
+ else
+ {
+ int repcount = bitstream_read(bitbuf, numbits) + 3;
+ while (repcount--)
+ decoder->huffnode[curnode++].numbits = nodebits;
+ }
+ }
+ }
+
+ /* make sure we ended up with the right number */
+ if (curnode != decoder->numcodes)
+ return HUFFERR_INVALID_DATA;
+
+ /* assign canonical codes for all nodes based on their code lengths */
+ error = huffman_assign_canonical_codes(decoder);
+ if (error != HUFFERR_NONE)
+ return error;
+
+ /* build the lookup table */
+ huffman_build_lookup_table(decoder);
+
+ /* determine final input length and report errors */
+ return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ * import_tree_huffman - import a huffman-encoded
+ * huffman tree from a source data stream
+ *-------------------------------------------------
+ */
+
+enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf)
+{
+ int start;
+ int last = 0;
+ int count = 0;
+ int index;
+ int curcode;
+ uint8_t rlefullbits = 0;
+ uint32_t temp;
+ enum huffman_error error;
+ /* start by parsing the lengths for the small tree */
+ struct huffman_decoder* smallhuff = create_huffman_decoder(24, 6);
+ smallhuff->huffnode[0].numbits = bitstream_read(bitbuf, 3);
+ start = bitstream_read(bitbuf, 3) + 1;
+ for (index = 1; index < 24; index++)
+ {
+ if (index < start || count == 7)
+ smallhuff->huffnode[index].numbits = 0;
+ else
+ {
+ count = bitstream_read(bitbuf, 3);
+ smallhuff->huffnode[index].numbits = (count == 7) ? 0 : count;
+ }
+ }
+
+ /* then regenerate the tree */
+ error = huffman_assign_canonical_codes(smallhuff);
+ if (error != HUFFERR_NONE)
+ return error;
+ huffman_build_lookup_table(smallhuff);
+
+ /* determine the maximum length of an RLE count */
+ temp = decoder->numcodes - 9;
+ while (temp != 0)
+ temp >>= 1, rlefullbits++;
+
+ /* now process the rest of the data */
+ for (curcode = 0; curcode < decoder->numcodes; )
+ {
+ int value = huffman_decode_one(smallhuff, bitbuf);
+ if (value != 0)
+ decoder->huffnode[curcode++].numbits = last = value - 1;
+ else
+ {
+ int count = bitstream_read(bitbuf, 3) + 2;
+ if (count == 7+2)
+ count += bitstream_read(bitbuf, rlefullbits);
+ for ( ; count != 0 && curcode < decoder->numcodes; count--)
+ decoder->huffnode[curcode++].numbits = last;
+ }
+ }
+
+ /* make sure we ended up with the right number */
+ if (curcode != decoder->numcodes)
+ return HUFFERR_INVALID_DATA;
+
+ /* assign canonical codes for all nodes based on their code lengths */
+ error = huffman_assign_canonical_codes(decoder);
+ if (error != HUFFERR_NONE)
+ return error;
+
+ /* build the lookup table */
+ huffman_build_lookup_table(decoder);
+
+ /* determine final input length and report errors */
+ return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
+}
+
+/*-------------------------------------------------
+ * compute_tree_from_histo - common backend for
+ * computing a tree based on the data histogram
+ *-------------------------------------------------
+ */
+
+enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder)
+{
+ int i;
+ uint32_t lowerweight;
+ uint32_t upperweight;
+ /* compute the number of data items in the histogram */
+ uint32_t sdatacount = 0;
+ for (i = 0; i < decoder->numcodes; i++)
+ sdatacount += decoder->datahisto[i];
+
+ /* binary search to achieve the optimum encoding */
+ lowerweight = 0;
+ upperweight = sdatacount * 2;
+ while (1)
+ {
+ /* build a tree using the current weight */
+ uint32_t curweight = (upperweight + lowerweight) / 2;
+ int curmaxbits = huffman_build_tree(decoder, sdatacount, curweight);
+
+ /* apply binary search here */
+ if (curmaxbits <= decoder->maxbits)
+ {
+ lowerweight = curweight;
+
+ /* early out if it worked with the raw weights, or if we're done searching */
+ if (curweight == sdatacount || (upperweight - lowerweight) <= 1)
+ break;
+ }
+ else
+ upperweight = curweight;
+ }
+
+ /* assign canonical codes for all nodes based on their code lengths */
+ return huffman_assign_canonical_codes(decoder);
+}
+
+/***************************************************************************
+ * INTERNAL FUNCTIONS
+ ***************************************************************************
+ */
+
+/*-------------------------------------------------
+ * tree_node_compare - compare two tree nodes
+ * by weight
+ *-------------------------------------------------
+ */
+
+static int huffman_tree_node_compare(const void *item1, const void *item2)
+{
+ const struct node_t *node1 = *(const struct node_t **)item1;
+ const struct node_t *node2 = *(const struct node_t **)item2;
+ if (node2->weight != node1->weight)
+ return node2->weight - node1->weight;
+ if (node2->bits - node1->bits == 0)
+ fprintf(stderr, "identical node sort keys, should not happen!\n");
+ return (int)node1->bits - (int)node2->bits;
+}
+
+/*-------------------------------------------------
+ * build_tree - build a huffman tree based on the
+ * data distribution
+ *-------------------------------------------------
+ */
+
+int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight)
+{
+ int curcode;
+ int nextalloc;
+ int listitems = 0;
+ int maxbits = 0;
+ /* make a list of all non-zero nodes */
+ struct node_t** list = (struct node_t**)malloc(sizeof(struct node_t*) * decoder->numcodes * 2);
+ memset(decoder->huffnode, 0, decoder->numcodes * sizeof(decoder->huffnode[0]));
+ for (curcode = 0; curcode < decoder->numcodes; curcode++)
+ if (decoder->datahisto[curcode] != 0)
+ {
+ list[listitems++] = &decoder->huffnode[curcode];
+ decoder->huffnode[curcode].count = decoder->datahisto[curcode];
+ decoder->huffnode[curcode].bits = curcode;
+
+ /* scale the weight by the current effective length, ensuring we don't go to 0 */
+ decoder->huffnode[curcode].weight = ((uint64_t)decoder->datahisto[curcode]) * ((uint64_t)totalweight) / ((uint64_t)totaldata);
+ if (decoder->huffnode[curcode].weight == 0)
+ decoder->huffnode[curcode].weight = 1;
+ }
+
+#if 0
+ fprintf(stderr, "Pre-sort:\n");
+ for (int i = 0; i < listitems; i++) {
+ fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);
+ }
+#endif
+
+ /* sort the list by weight, largest weight first */
+ qsort(&list[0], listitems, sizeof(list[0]), huffman_tree_node_compare);
+
+#if 0
+ fprintf(stderr, "Post-sort:\n");
+ for (int i = 0; i < listitems; i++) {
+ fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);
+ }
+ fprintf(stderr, "===================\n");
+#endif
+
+ /* now build the tree */
+ nextalloc = decoder->numcodes;
+ while (listitems > 1)
+ {
+ /* remove lowest two items */
+ struct node_t* node1 = &(*list[--listitems]);
+ struct node_t* node0 = &(*list[--listitems]);
+
+ /* create new node */
+ struct node_t* newnode = &decoder->huffnode[nextalloc++];
+ newnode->parent = NULL;
+ node0->parent = node1->parent = newnode;
+ newnode->weight = node0->weight + node1->weight;
+
+ /* insert into list at appropriate location */
+ int curitem;
+ for (curitem = 0; curitem < listitems; curitem++)
+ if (newnode->weight > list[curitem]->weight)
+ {
+ memmove(&list[curitem+1], &list[curitem], (listitems - curitem) * sizeof(list[0]));
+ break;
+ }
+ list[curitem] = newnode;
+ listitems++;
+ }
+
+ /* compute the number of bits in each code, and fill in another histogram */
+ for (curcode = 0; curcode < decoder->numcodes; curcode++)
+ {
+ struct node_t* node = &decoder->huffnode[curcode];
+ node->numbits = 0;
+ node->bits = 0;
+
+ /* if we have a non-zero weight, compute the number of bits */
+ if (node->weight > 0)
+ {
+ /* determine the number of bits for this node */
+ for (struct node_t *curnode = node; curnode->parent != NULL; curnode = curnode->parent)
+ node->numbits++;
+ if (node->numbits == 0)
+ node->numbits = 1;
+
+ /* keep track of the max */
+ maxbits = MAX(maxbits, ((int)node->numbits));
+ }
+ }
+ return maxbits;
+}
+
+/*-------------------------------------------------
+ * assign_canonical_codes - assign canonical codes
+ * to all the nodes based on the number of bits
+ * in each
+ *-------------------------------------------------
+ */
+
+enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder)
+{
+ int curcode, codelen;
+ uint32_t curstart = 0;
+ /* build up a histogram of bit lengths */
+ uint32_t bithisto[33] = { 0 };
+ for (curcode = 0; curcode < decoder->numcodes; curcode++)
+ {
+ struct node_t* node = &decoder->huffnode[curcode];
+ if (node->numbits > decoder->maxbits)
+ return HUFFERR_INTERNAL_INCONSISTENCY;
+ if (node->numbits <= 32)
+ bithisto[node->numbits]++;
+ }
+
+ /* for each code length, determine the starting code number */
+ for (codelen = 32; codelen > 0; codelen--)
+ {
+ uint32_t nextstart = (curstart + bithisto[codelen]) >> 1;
+ if (codelen != 1 && nextstart * 2 != (curstart + bithisto[codelen]))
+ return HUFFERR_INTERNAL_INCONSISTENCY;
+ bithisto[codelen] = curstart;
+ curstart = nextstart;
+ }
+
+ /* now assign canonical codes */
+ for (curcode = 0; curcode < decoder->numcodes; curcode++)
+ {
+ struct node_t* node = &decoder->huffnode[curcode];
+ if (node->numbits > 0)
+ node->bits = bithisto[node->numbits]++;
+ }
+ return HUFFERR_NONE;
+}
+
+/*-------------------------------------------------
+ * build_lookup_table - build a lookup table for
+ * fast decoding
+ *-------------------------------------------------
+ */
+
+void huffman_build_lookup_table(struct huffman_decoder* decoder)
+{
+ int curcode;
+ /* iterate over all codes */
+ for (curcode = 0; curcode < decoder->numcodes; curcode++)
+ {
+ /* process all nodes which have non-zero bits */
+ struct node_t* node = &decoder->huffnode[curcode];
+ if (node->numbits > 0)
+ {
+ /* set up the entry */
+ lookup_value value = MAKE_LOOKUP(curcode, node->numbits);
+
+ /* fill all matching entries */
+ int shift = decoder->maxbits - node->numbits;
+ lookup_value *dest = &decoder->lookup[node->bits << shift];
+ lookup_value *destend = &decoder->lookup[((node->bits + 1) << shift) - 1];
+ while (dest <= destend)
+ *dest++ = value;
+ }
+ }
+}
notaz.gp2x.de / pcsx_rearmed.git / blobdiff