diff options
Diffstat (limited to 'src/lib/util/huffman.c')
-rw-r--r-- | src/lib/util/huffman.c | 934 |
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; +} |