summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/util/huffman.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/util/huffman.c')
-rw-r--r--src/lib/util/huffman.c934
1 files changed, 934 insertions, 0 deletions
diff --git a/src/lib/util/huffman.c b/src/lib/util/huffman.c
new file mode 100644
index 00000000000..0465f5d94d3
--- /dev/null
+++ b/src/lib/util/huffman.c
@@ -0,0 +1,934 @@
+/***************************************************************************
+
+ huffman.c
+
+ Video compression and decompression helpers.
+
+ Copyright (c) 1996-2007, Nicola Salmoria and the MAME Team.
+ Visit http://mamedev.org for licensing and usage restrictions.
+
+****************************************************************************
+
+ 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
+
+***************************************************************************/
+
+#include "huffman.h"
+
+
+
+/***************************************************************************
+ CONSTANTS
+***************************************************************************/
+
+#define MAX_HUFFMAN_NODES (256 + 256)
+
+
+
+/***************************************************************************
+ TYPE DEFINITIONS
+***************************************************************************/
+
+typedef struct _bit_buffer bit_buffer;
+struct _bit_buffer
+{
+ UINT32 buffer;
+ int bits;
+ union
+ {
+ const UINT8 *read;
+ UINT8 * write;
+ } data;
+ UINT32 doffset;
+ UINT32 dlength;
+ int overflow;
+};
+
+
+typedef struct _huffman_node huffman_node;
+struct _huffman_node
+{
+ huffman_node * parent;
+ UINT32 count;
+ UINT32 weight;
+ UINT32 bits;
+ UINT8 numbits;
+};
+
+
+struct _huffman_context
+{
+ UINT8 maxbits;
+ UINT8 lookupdirty;
+ huffman_node huffnode[MAX_HUFFMAN_NODES];
+ UINT32 lookupmask;
+ huffman_lookup_value *lookup;
+};
+
+
+
+/***************************************************************************
+ PROTOTYPES
+***************************************************************************/
+
+static void huffman_write_rle_tree_bits(bit_buffer *bitbuf, int value, int repcount, int numbits);
+static int CLIB_DECL huffman_tree_node_compare(const void *item1, const void *item2);
+static int huffman_build_tree(huffman_context *context, const UINT32 *datahisto, UINT32 totaldata, UINT32 totalweight);
+static huffman_error huffman_assign_canonical_codes(huffman_context *context);
+static huffman_error huffman_build_lookup_table(huffman_context *context);
+
+
+
+/***************************************************************************
+ INLINE FUNCTIONS
+***************************************************************************/
+
+/*-------------------------------------------------
+ bit_buffer_write_init - initialize a bit
+ buffer for writing
+-------------------------------------------------*/
+
+INLINE void bit_buffer_write_init(bit_buffer *bitbuf, UINT8 *data, UINT32 dlength)
+{
+ /* fill in the basic data structure */
+ bitbuf->buffer = 0;
+ bitbuf->bits = 0;
+ bitbuf->data.write = data;
+ bitbuf->doffset = 0;
+ bitbuf->dlength = dlength;
+ bitbuf->overflow = FALSE;
+}
+
+
+/*-------------------------------------------------
+ bit_buffer_write - write 'numbits' to the
+ bit buffer, assuming that 'newbits' is right-
+ justified
+-------------------------------------------------*/
+
+INLINE void bit_buffer_write(bit_buffer *bitbuf, UINT32 newbits, int numbits)
+{
+ /* flush the buffer if we're going to overflow it */
+ if (bitbuf->bits + numbits > 32)
+ while (bitbuf->bits >= 8)
+ {
+ if (bitbuf->doffset < bitbuf->dlength)
+ bitbuf->data.write[bitbuf->doffset] = bitbuf->buffer >> 24;
+ else
+ bitbuf->overflow = TRUE;
+ bitbuf->doffset++;
+ bitbuf->buffer <<= 8;
+ bitbuf->bits -= 8;
+ }
+
+ /* shift the bits to the top */
+ newbits <<= 32 - numbits;
+
+ /* now shift it down to account for the number of bits we already have and OR them in */
+ bitbuf->buffer |= newbits >> bitbuf->bits;
+ bitbuf->bits += numbits;
+}
+
+
+/*-------------------------------------------------
+ bit_buffer_flush - flush any bits in the write
+ buffer and return the final data offset
+-------------------------------------------------*/
+
+INLINE UINT32 bit_buffer_flush(bit_buffer *bitbuf)
+{
+ while (bitbuf->bits > 0)
+ {
+ if (bitbuf->doffset < bitbuf->dlength)
+ bitbuf->data.write[bitbuf->doffset] = bitbuf->buffer >> 24;
+ else
+ bitbuf->overflow = TRUE;
+ bitbuf->doffset++;
+ bitbuf->buffer <<= 8;
+ bitbuf->bits -= 8;
+ }
+ return bitbuf->doffset;
+}
+
+
+/*-------------------------------------------------
+ bit_buffer_read_init - initialize a bit
+ buffer for reading
+-------------------------------------------------*/
+
+INLINE void bit_buffer_read_init(bit_buffer *bitbuf, const UINT8 *data, UINT32 dlength)
+{
+ /* fill in the basic data structure */
+ bitbuf->buffer = 0;
+ bitbuf->bits = 0;
+ bitbuf->data.read = data;
+ bitbuf->doffset = 0;
+ bitbuf->dlength = dlength;
+ bitbuf->overflow = FALSE;
+}
+
+
+/*-------------------------------------------------
+ bit_buffer_read - read 'numbits' bits from
+ the buffer, returning the right-justified
+-------------------------------------------------*/
+
+INLINE UINT32 bit_buffer_read(bit_buffer *bitbuf, int numbits)
+{
+ UINT32 result;
+
+ /* fetch data if we need more */
+ if (numbits > bitbuf->bits)
+ {
+ while (bitbuf->bits <= 24)
+ {
+ if (bitbuf->doffset < bitbuf->dlength)
+ bitbuf->buffer |= bitbuf->data.read[bitbuf->doffset] << (24 - bitbuf->bits);
+ bitbuf->doffset++;
+ bitbuf->bits += 8;
+ }
+ if (numbits > bitbuf->bits)
+ bitbuf->overflow = TRUE;
+ }
+
+ /* return the data */
+ result = bitbuf->buffer >> (32 - numbits);
+ bitbuf->buffer <<= numbits;
+ bitbuf->bits -= numbits;
+ return result;
+}
+
+
+/*-------------------------------------------------
+ bit_buffer_read_offset - return the current
+ rounded byte reading offset
+-------------------------------------------------*/
+
+INLINE UINT32 bit_buffer_read_offset(bit_buffer *bitbuf)
+{
+ UINT32 result = bitbuf->doffset;
+ int bits = bitbuf->bits;
+ while (bits >= 8)
+ {
+ result--;
+ bits -= 8;
+ }
+ return result;
+}
+
+
+
+/***************************************************************************
+ IMPLEMENTATION
+***************************************************************************/
+
+/*-------------------------------------------------
+ huffman_create_context - create an encoding/
+ decoding context
+-------------------------------------------------*/
+
+huffman_error huffman_create_context(huffman_context **context, int maxbits)
+{
+ /* limit to 24 bits */
+ if (maxbits > 24)
+ return HUFFERR_TOO_MANY_BITS;
+
+ /* allocate a context */
+ *context = malloc(sizeof(**context));
+ if (*context == NULL)
+ return HUFFERR_OUT_OF_MEMORY;
+
+ /* set the info */
+ memset(*context, 0, sizeof(**context));
+ (*context)->maxbits = maxbits;
+ (*context)->lookupmask = (1 << maxbits) - 1;
+ (*context)->lookupdirty = TRUE;
+
+ return HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_free_context - free an encoding/
+ decoding context
+-------------------------------------------------*/
+
+void huffman_free_context(huffman_context *context)
+{
+ if (context->lookup != NULL)
+ free(context->lookup);
+ free(context);
+}
+
+
+/*-------------------------------------------------
+ huffman_compute_tree - compute an optimal
+ huffman tree for the given source data
+-------------------------------------------------*/
+
+huffman_error huffman_compute_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 sstride)
+{
+ UINT32 lowerweight, upperweight;
+ UINT32 datahisto[256];
+ int i;
+
+ /* build the data histogram */
+ memset(datahisto, 0, sizeof(datahisto));
+ for (i = 0; i < slength; i += sstride)
+ datahisto[source[i]]++;
+
+ /* binary search to achieve the optimum encoding */
+ lowerweight = 0;
+ upperweight = slength * 2;
+ while (TRUE)
+ {
+ UINT32 curweight = (upperweight + lowerweight) / 2;
+ int curmaxbits;
+
+ /* build a tree using the current weight */
+ curmaxbits = huffman_build_tree(context, datahisto, slength, curweight);
+
+ /* apply binary search here */
+ if (curmaxbits <= context->maxbits)
+ {
+ lowerweight = curweight;
+
+ /* early out if it worked with the raw weights, or if we're done searching */
+ if (curweight == slength || (upperweight - lowerweight) <= 1)
+ break;
+ }
+ else
+ upperweight = curweight;
+ }
+
+ /* assign canonical codes for all nodes based on their code lengths */
+ return huffman_assign_canonical_codes(context);
+}
+
+
+/*-------------------------------------------------
+ huffman_import_tree - import a huffman tree
+ from a source data stream
+-------------------------------------------------*/
+
+huffman_error huffman_import_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 *actlength)
+{
+ huffman_error error;
+ bit_buffer bitbuf;
+ int curnode;
+ int numbits;
+
+ /* initialize the input buffer */
+ bit_buffer_read_init(&bitbuf, source, slength);
+
+ /* bits per entry depends on the maxbits */
+ if (context->maxbits >= 16)
+ numbits = 5;
+ else if (context->maxbits >= 8)
+ numbits = 4;
+ else
+ numbits = 3;
+
+ /* loop until we read all the nodes */
+ for (curnode = 0; curnode < 256; )
+ {
+ int nodebits = bit_buffer_read(&bitbuf, numbits);
+
+ /* a non-one value is just raw */
+ if (nodebits != 1)
+ context->huffnode[curnode++].numbits = nodebits;
+
+ /* a one value is an escape code */
+ else
+ {
+ nodebits = bit_buffer_read(&bitbuf, numbits);
+
+ /* a double 1 is just a single 1 */
+ if (nodebits == 1)
+ context->huffnode[curnode++].numbits = nodebits;
+
+ /* otherwise, we need one for value for the repeat count */
+ else
+ {
+ int repcount = bit_buffer_read(&bitbuf, numbits) + 3;
+ while (repcount--)
+ context->huffnode[curnode++].numbits = nodebits;
+ }
+ }
+ }
+
+ /* assign canonical codes for all nodes based on their code lengths */
+ error = huffman_assign_canonical_codes(context);
+ if (error != HUFFERR_NONE)
+ return error;
+
+ /* make sure we ended up with the right number */
+ if (curnode != 256)
+ return HUFFERR_INVALID_DATA;
+
+ *actlength = bit_buffer_read_offset(&bitbuf);
+ return bitbuf.overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_export_tree - export a huffman tree
+ to a target data stream
+-------------------------------------------------*/
+
+huffman_error huffman_export_tree(huffman_context *context, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
+{
+ bit_buffer bitbuf;
+ int repcount;
+ int lastval;
+ int numbits;
+ int i;
+
+ /* initialize the output buffer */
+ bit_buffer_write_init(&bitbuf, dest, dlength);
+
+ /* bits per entry depends on the maxbits */
+ if (context->maxbits >= 16)
+ numbits = 5;
+ else if (context->maxbits >= 8)
+ numbits = 4;
+ else
+ numbits = 3;
+
+ /* RLE encode the lengths */
+ lastval = ~0;
+ repcount = 0;
+ for (i = 0; i < 256; i++)
+ {
+ int newval = context->huffnode[i].numbits;
+
+ /* if we match the previous value, just bump the repcount */
+ if (newval == lastval)
+ repcount++;
+
+ /* otherwise, we need to flush the previous repeats */
+ else
+ {
+ if (repcount != 0)
+ huffman_write_rle_tree_bits(&bitbuf, lastval, repcount, numbits);
+ lastval = newval;
+ repcount = 1;
+ }
+ }
+
+ /* flush the last value */
+ huffman_write_rle_tree_bits(&bitbuf, lastval, repcount, numbits);
+ *actlength = bit_buffer_flush(&bitbuf);
+ return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_get_lookup_table - return a pointer to
+ the lookup table
+-------------------------------------------------*/
+
+huffman_error huffman_get_lookup_table(huffman_context *context, const huffman_lookup_value **table)
+{
+ if (context->lookupdirty)
+ {
+ huffman_error error = huffman_build_lookup_table(context);
+ if (error != HUFFERR_NONE)
+ return error;
+ }
+ *table = context->lookup;
+ return HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_encode_data - encode data using the
+ current tree
+-------------------------------------------------*/
+
+huffman_error huffman_encode_data(huffman_context *context, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
+{
+ bit_buffer bitbuf;
+ UINT32 soffset;
+
+ /* initialize the output buffer */
+ bit_buffer_write_init(&bitbuf, dest, dlength);
+
+ /* loop over source data and encode */
+ for (soffset = 0; soffset < slength; soffset++)
+ {
+ huffman_node *node = &context->huffnode[source[soffset]];
+ bit_buffer_write(&bitbuf, node->bits, node->numbits);
+ }
+ *actlength = bit_buffer_flush(&bitbuf);
+ return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_encode_data_interleaved_2 - encode
+ alternating data with two contexts
+-------------------------------------------------*/
+
+huffman_error huffman_encode_data_interleaved_2(huffman_context *context1, huffman_context *context2, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
+{
+ bit_buffer bitbuf;
+ UINT32 soffset;
+
+ /* initialize the output buffer */
+ bit_buffer_write_init(&bitbuf, dest, dlength);
+
+ /* loop over source data and encode */
+ for (soffset = 0; soffset < slength; soffset += 2)
+ {
+ huffman_node *node;
+
+ node = &context1->huffnode[source[soffset + 0]];
+ bit_buffer_write(&bitbuf, node->bits, node->numbits);
+
+ node = &context2->huffnode[source[soffset + 1]];
+ bit_buffer_write(&bitbuf, node->bits, node->numbits);
+ }
+ *actlength = bit_buffer_flush(&bitbuf);
+ return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_decode_data - decode data using the
+ current tree
+-------------------------------------------------*/
+
+huffman_error huffman_decode_data(huffman_context *context, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
+{
+ int maxbits = context->maxbits;
+ int shiftbits = 32 - maxbits;
+ const huffman_lookup_value *table;
+ int overflow = FALSE;
+ huffman_error error;
+ UINT32 doffset = 0;
+ UINT32 soffset = 0;
+ UINT32 bitbuf = 0;
+ int sbits = 0;
+
+ /* regenerate the lookup table if necessary */
+ error = huffman_get_lookup_table(context, &table);
+ if (error != HUFFERR_NONE)
+ return error;
+
+ /* decode until we process all of the destination data */
+ for (doffset = 0; doffset < dlength; doffset++)
+ {
+ huffman_lookup_value lookup;
+
+ /* if we don't have enough bits, load up the buffer */
+ if (sbits < maxbits)
+ {
+ while (sbits <= 24)
+ {
+ if (soffset < slength)
+ bitbuf |= source[soffset] << (24 - sbits);
+ soffset++;
+ sbits += 8;
+ }
+ if (sbits < maxbits)
+ overflow = TRUE;
+ }
+
+ /* lookup the data */
+ lookup = table[bitbuf >> shiftbits];
+
+ /* store the upper byte */
+ dest[doffset] = lookup >> 8;
+
+ /* count the bits */
+ lookup &= 0x1f;
+ bitbuf <<= lookup;
+ sbits -= lookup;
+ }
+
+ /* back off soffset while we have whole bytes */
+ while (sbits >= 8)
+ {
+ sbits -= 8;
+ soffset--;
+ }
+ *actlength = soffset;
+ return overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_decode_data_interleaved_2 - decode
+ interleaved data using two contexts
+-------------------------------------------------*/
+
+huffman_error huffman_decode_data_interleaved_2(huffman_context *context1, huffman_context *context2, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
+{
+ int maxbits1 = context1->maxbits, maxbits2 = context2->maxbits;
+ const huffman_lookup_value *table1, *table2;
+ int shiftbits1 = 32 - maxbits1;
+ int shiftbits2 = 32 - maxbits2;
+ int overflow = FALSE;
+ huffman_error error;
+ UINT32 doffset = 0;
+ UINT32 soffset = 0;
+ UINT32 bitbuf = 0;
+ int sbits = 0;
+
+ /* regenerate the lookup table if necessary */
+ error = huffman_get_lookup_table(context1, &table1);
+ if (error != HUFFERR_NONE)
+ return error;
+ error = huffman_get_lookup_table(context2, &table2);
+ if (error != HUFFERR_NONE)
+ return error;
+
+ /* decode until we process all of the destination data */
+ for (doffset = 0; doffset < dlength; doffset += 2)
+ {
+ huffman_lookup_value lookup;
+
+ /* if we don't have enough bits, load up the buffer */
+ if (sbits < maxbits1)
+ {
+ while (sbits <= 24)
+ {
+ if (soffset < slength)
+ bitbuf |= source[soffset] << (24 - sbits);
+ soffset++;
+ sbits += 8;
+ }
+ if (sbits < maxbits1)
+ overflow = TRUE;
+ }
+
+ /* lookup the data */
+ lookup = table1[bitbuf >> shiftbits1];
+
+ /* store the upper byte */
+ dest[doffset + 0] = lookup >> 8;
+
+ /* count the bits */
+ lookup &= 0x1f;
+ bitbuf <<= lookup;
+ sbits -= lookup;
+
+ /* if we don't have enough bits, load up the buffer */
+ if (sbits < maxbits2)
+ {
+ while (sbits <= 24)
+ {
+ if (soffset < slength)
+ bitbuf |= source[soffset] << (24 - sbits);
+ soffset++;
+ sbits += 8;
+ }
+ if (sbits < maxbits2)
+ overflow = TRUE;
+ }
+
+ /* lookup the data */
+ lookup = table2[bitbuf >> shiftbits2];
+
+ /* store the upper byte */
+ dest[doffset + 1] = lookup >> 8;
+
+ /* count the bits */
+ lookup &= 0x1f;
+ bitbuf <<= lookup;
+ sbits -= lookup;
+ }
+
+ /* back off soffset while we have whole bytes */
+ while (sbits >= 8)
+ {
+ sbits -= 8;
+ soffset--;
+ }
+ *actlength = soffset;
+ return overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_write_rle_tree_bits - write an RLE
+ encoded set of data to a target stream
+-------------------------------------------------*/
+
+static void huffman_write_rle_tree_bits(bit_buffer *bitbuf, int value, int repcount, int numbits)
+{
+ /* loop until we have output all of the repeats */
+ while (repcount > 0)
+ {
+ /* if we have a 1, write it twice as it is an escape code */
+ if (value == 1)
+ {
+ bit_buffer_write(bitbuf, 1, numbits);
+ bit_buffer_write(bitbuf, 1, numbits);
+ repcount--;
+ }
+
+ /* if we have two or fewer in a row, write them raw */
+ else if (repcount <= 2)
+ {
+ bit_buffer_write(bitbuf, value, numbits);
+ repcount--;
+ }
+
+ /* otherwise, write a triple using 1 as the escape code */
+ else
+ {
+ int cur_reps = MIN(repcount - 3, (1 << numbits) - 1);
+ bit_buffer_write(bitbuf, 1, numbits);
+ bit_buffer_write(bitbuf, value, numbits);
+ bit_buffer_write(bitbuf, cur_reps, numbits);
+ repcount -= cur_reps + 3;
+ }
+ }
+}
+
+
+/*-------------------------------------------------
+ huffman_tree_node_compare - compare two
+ tree nodes by weight
+-------------------------------------------------*/
+
+static int CLIB_DECL huffman_tree_node_compare(const void *item1, const void *item2)
+{
+ const huffman_node *node1 = *(const huffman_node **)item1;
+ const huffman_node *node2 = *(const huffman_node **)item2;
+ return node2->weight - node1->weight;
+}
+
+
+/*-------------------------------------------------
+ huffman_build_tree - build a huffman tree
+ based on the data distribution
+-------------------------------------------------*/
+
+static int huffman_build_tree(huffman_context *context, const UINT32 *datahisto, UINT32 totaldata, UINT32 totalweight)
+{
+ huffman_node *list[256];
+ int listitems;
+ int nextalloc;
+ int maxbits;
+ int i;
+
+ /* make a list of all non-zero nodes */
+ listitems = 0;
+ memset(context->huffnode, 0, 256 * sizeof(context->huffnode[0]));
+ for (i = 0; i < 256; i++)
+ if (datahisto[i] != 0)
+ {
+ list[listitems++] = &context->huffnode[i];
+ context->huffnode[i].count = datahisto[i];
+
+ /* scale the weight by the current effective length, ensuring we don't go to 0 */
+ context->huffnode[i].weight = (UINT64)datahisto[i] * (UINT64)totalweight / (UINT64)totaldata;
+ if (context->huffnode[i].weight == 0)
+ context->huffnode[i].weight = 1;
+ }
+
+ /* sort the list by weight, largest weight first */
+ qsort(list, listitems, sizeof(list[0]), huffman_tree_node_compare);
+
+ /* now build the tree */
+ nextalloc = 256;
+ while (listitems > 1)
+ {
+ huffman_node *node0, *node1, *newnode;
+
+ /* remove lowest two items */
+ node1 = list[--listitems];
+ node0 = list[--listitems];
+
+ /* create new node */
+ newnode = &context->huffnode[nextalloc++];
+ newnode->parent = NULL;
+ node0->parent = node1->parent = newnode;
+ newnode->weight = node0->weight + node1->weight;
+
+ /* insert into list at appropriate location */
+ for (i = 0; i < listitems; i++)
+ if (newnode->weight > list[i]->weight)
+ {
+ memmove(&list[i+1], &list[i], (listitems - i) * sizeof(list[0]));
+ break;
+ }
+ list[i] = newnode;
+ listitems++;
+ }
+
+ /* compute the number of bits in each code, and fill in another histogram */
+ maxbits = 0;
+ for (i = 0; i < 256; i++)
+ {
+ huffman_node *node = &context->huffnode[i];
+ node->numbits = 0;
+
+ /* if we have a non-zero weight, compute the number of bits */
+ if (node->weight > 0)
+ {
+ huffman_node *curnode;
+
+ /* determine the number of bits for this node */
+ for (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, node->numbits);
+ }
+ }
+
+ return maxbits;
+}
+
+
+/*-------------------------------------------------
+ huffman_assign_canonical_codes - assign
+ canonical codes to all the nodes based on the
+ number of bits in each
+-------------------------------------------------*/
+
+static huffman_error huffman_assign_canonical_codes(huffman_context *context)
+{
+ UINT32 bithisto[33];
+ int curstart;
+ int i;
+
+ /* build up a histogram of bit lengths */
+ memset(bithisto, 0, sizeof(bithisto));
+ for (i = 0; i < 256; i++)
+ {
+ huffman_node *node = &context->huffnode[i];
+ if (node->numbits > context->maxbits)
+ return HUFFERR_INTERNAL_INCONSISTENCY;
+ if (node->numbits <= 32)
+ bithisto[node->numbits]++;
+ }
+
+ /* for each code length, determine the starting code number */
+ curstart = 0;
+ for (i = 32; i > 0; i--)
+ {
+ UINT32 nextstart = (curstart + bithisto[i]) >> 1;
+ if (i != 1 && nextstart * 2 != (curstart + bithisto[i]))
+ return HUFFERR_INTERNAL_INCONSISTENCY;
+ bithisto[i] = curstart;
+ curstart = nextstart;
+ }
+
+ /* now assign canonical codes */
+ for (i = 0; i < 256; i++)
+ {
+ huffman_node *node = &context->huffnode[i];
+ if (node->numbits > 0)
+ node->bits = bithisto[node->numbits]++;
+ }
+
+ /* if there was a decoding table, get rid of it now */
+ context->lookupdirty = TRUE;
+ return HUFFERR_NONE;
+}
+
+
+/*-------------------------------------------------
+ huffman_build_lookup_table - build a lookup
+ table for fast decoding
+-------------------------------------------------*/
+
+static huffman_error huffman_build_lookup_table(huffman_context *context)
+{
+ int i;
+
+ /* allocate a table if needed */
+ if (context->lookup == NULL)
+ context->lookup = malloc((UINT32)sizeof(context->lookup[0]) * (UINT32)(1 << context->maxbits));
+ if (context->lookup == NULL)
+ return HUFFERR_OUT_OF_MEMORY;
+
+ /* now build */
+ for (i = 0; i < 256; i++)
+ {
+ huffman_node *node = &context->huffnode[i];
+ if (node->numbits > 0)
+ {
+ huffman_lookup_value *dest, *destend;
+
+ /* left justify this node's bit values to max bits */
+ int shift = context->maxbits - node->numbits;
+ UINT32 start = node->bits << shift;
+ UINT32 end = ((node->bits + 1) << shift) - 1;
+ huffman_lookup_value value;
+
+ /* set up the entry */
+ value = (i << 8) | node->numbits;
+
+ /* fill all matching entries */
+ dest = &context->lookup[start];
+ destend = &context->lookup[end];
+ while (dest <= destend)
+ *dest++ = value;
+ }
+ }
+
+ /* no longer dirty */
+ context->lookupdirty = FALSE;
+ return HUFFERR_NONE;
+}