/*************************************************************************** huffman.c Video compression and decompression helpers. Copyright 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; }