diff options
Diffstat (limited to 'src/lib/util/huffman.c')
-rw-r--r-- | src/lib/util/huffman.c | 1841 |
1 files changed, 454 insertions, 1387 deletions
diff --git a/src/lib/util/huffman.c b/src/lib/util/huffman.c index 3b9c4ea52b8..b672a7a0d89 100644 --- a/src/lib/util/huffman.c +++ b/src/lib/util/huffman.c @@ -2,7 +2,7 @@ huffman.c - Video compression and decompression helpers. + Static Huffman compression and decompression helpers. **************************************************************************** @@ -127,1569 +127,636 @@ #include <stdlib.h> +#include "coretmpl.h" #include "huffman.h" -/*************************************************************************** - CONSTANTS -***************************************************************************/ - -#define HUFFMAN_CODES 256 -#define HUFFMAN_DELTARLE_CODES (HUFFMAN_CODES + 16) - -#define MAX_HUFFMAN_CODES (HUFFMAN_DELTARLE_CODES) -#define MAX_HUFFMAN_NODES (MAX_HUFFMAN_CODES + MAX_HUFFMAN_CODES) +//************************************************************************** +// MACROS +//************************************************************************** +#define MAKE_LOOKUP(code,bits) (((code) << 5) | ((bits) & 0x1f)) -/*************************************************************************** - MACROS -***************************************************************************/ -#define MAKE_LOOKUP(code,bits) (((code) << 6) | ((bits) & 0x1f)) -#define LOOKUP_CODE(val) ((val) >> 6) -#define LOOKUP_BITS(val) ((val) & 0x1f) +//************************************************************************** +// IMPLEMENTATION +//************************************************************************** +//------------------------------------------------- +// huffman_context_base - create an encoding/ +// decoding context +//------------------------------------------------- - -/*************************************************************************** - TYPE DEFINITIONS -***************************************************************************/ - -typedef struct _bit_buffer bit_buffer; -struct _bit_buffer +huffman_context_base::huffman_context_base(int numcodes, int maxbits, lookup_value *lookup, UINT32 *histo, node_t *nodes) + : m_numcodes(numcodes), + m_maxbits(maxbits), + m_prevdata(0), + m_rleremaining(0), + m_lookup(lookup), + m_datahisto(histo), + m_huffnode(nodes) { - UINT32 buffer; /* current bit accumulator */ - int bits; /* number of bits in the accumulator */ - union - { - const UINT8 * read; /* read pointer */ - UINT8 * write; /* write pointer */ - } data; - UINT32 doffset; /* byte offset within the data */ - UINT32 dlength; /* length of the data */ - int overflow; /* flag: true if we read/wrote past the end */ -}; - - -typedef struct _huffman_node huffman_node; -struct _huffman_node -{ - huffman_node * parent; /* pointer to parent node */ - UINT32 count; /* number of hits on this node */ - UINT32 weight; /* assigned weight of this node */ - UINT32 bits; /* bits used to encode the node */ - UINT8 numbits; /* number of bits needed for this node */ -}; - - -struct _huffman_context -{ - UINT8 maxbits; /* maximum bits per code */ - UINT8 lookupdirty; /* TRUE if the lookup table is dirty */ - UINT8 prevdata; /* value of the previous data (for delta-RLE encoding) */ - UINT32 datahisto[MAX_HUFFMAN_CODES]; /* histogram of data values */ - int rleremaining; /* number of RLE bytes remaining (for delta-RLE encoding) */ - huffman_node huffnode[MAX_HUFFMAN_NODES]; /* array of nodes */ - huffman_lookup_value * lookup; /* pointer to the lookup table */ -}; - - - -/*************************************************************************** - PROTOTYPES -***************************************************************************/ - -static huffman_error huffman_deltarle_decode_data_interleaved_0102(huffman_context **contexts, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength); - -static huffman_error import_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 *actlength, UINT32 numcodes); -static huffman_error export_tree(huffman_context *context, UINT8 *dest, UINT32 dlength, UINT32 *actlength, UINT32 numcodes); -static void write_rle_tree_bits(bit_buffer *bitbuf, int value, int repcount, int numbits); -static int CLIB_DECL tree_node_compare(const void *item1, const void *item2); -static huffman_error compute_optimal_tree(huffman_context *context, const UINT32 *datahisto, UINT32 numcodes); -static int huffman_build_tree(huffman_context *context, const UINT32 *datahisto, UINT32 totaldata, UINT32 totalweight, UINT32 numcodes); -static huffman_error assign_canonical_codes(huffman_context *context, UINT32 numcodes); -static huffman_error build_lookup_table(huffman_context *context, UINT32 numcodes); - - - -/*************************************************************************** - 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 them 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_peek - peek ahead and return - 'numbits' bits from the buffer, returning - them right-justified --------------------------------------------------*/ - -INLINE UINT32 bit_buffer_peek(bit_buffer *bitbuf, int numbits) -{ - /* 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 */ - return bitbuf->buffer >> (32 - numbits); -} - - -/*------------------------------------------------- - bit_buffer_remove - remove 'numbits' bits - from the bit buffer; this presupposes that - at least 'numbits' are present --------------------------------------------------*/ - -INLINE void bit_buffer_remove(bit_buffer *bitbuf, int numbits) -{ - bitbuf->buffer <<= numbits; - bitbuf->bits -= numbits; -} - - -/*------------------------------------------------- - 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; -} - - -/*------------------------------------------------- - code_to_rlecount - number of RLE repetitions - encoded in a given byte --------------------------------------------------*/ - -INLINE int code_to_rlecount(int code) -{ - if (code == 0x00) - return 1; - if (code <= 0x107) - return 8 + (code - 0x100); - return 16 << (code - 0x108); -} - - -/*------------------------------------------------- - rlecount_to_byte - return a byte encoding - the maximum RLE count less than or equal to - the provided amount --------------------------------------------------*/ - -INLINE int rlecount_to_code(int rlecount) -{ - if (rlecount >= 2048) - return 0x10f; - if (rlecount >= 1024) - return 0x10e; - if (rlecount >= 512) - return 0x10d; - if (rlecount >= 256) - return 0x10c; - if (rlecount >= 128) - return 0x10b; - if (rlecount >= 64) - return 0x10a; - if (rlecount >= 32) - return 0x109; - if (rlecount >= 16) - return 0x108; - if (rlecount >= 8) - return 0x100 + (rlecount - 8); - return 0x00; -} - - - -/*************************************************************************** - IMPLEMENTATION -***************************************************************************/ - -/*------------------------------------------------- - huffman_create_context - create an encoding/ - decoding context --------------------------------------------------*/ - -huffman_error huffman_create_context(huffman_context **context, int maxbits) -{ - /* limit to 24 bits */ + // limit to 24 bits if (maxbits > 24) - return HUFFERR_TOO_MANY_BITS; - - /* allocate a context */ - *context = (huffman_context *)malloc(sizeof(**context)); - if (*context == NULL) - return HUFFERR_OUT_OF_MEMORY; - - /* set the info */ - memset(*context, 0, sizeof(**context)); - (*context)->maxbits = maxbits; - (*context)->lookupdirty = TRUE; - - return HUFFERR_NONE; + throw HUFFERR_TOO_MANY_BITS; } -/*------------------------------------------------- - huffman_free_context - free an encoding/ - decoding context --------------------------------------------------*/ +//------------------------------------------------- +// import_tree_rle - import an RLE-encoded +// huffman tree from a source data stream +//------------------------------------------------- -void huffman_free_context(huffman_context *context) +huffman_error huffman_context_base::import_tree_rle(bitstream_in &bitbuf) { - if (context->lookup != NULL) - free(context->lookup); - free(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) -{ - return import_tree(context, source, slength, actlength, HUFFMAN_CODES); -} - - -/*------------------------------------------------- - 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) -{ - return export_tree(context, dest, dlength, actlength, HUFFMAN_CODES); -} - - -/*------------------------------------------------- - huffman_deltarle_import_tree - import a - huffman tree from a source data stream for - delta-RLE encoded data --------------------------------------------------*/ - -huffman_error huffman_deltarle_import_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 *actlength) -{ - return import_tree(context, source, slength, actlength, HUFFMAN_DELTARLE_CODES); -} - - -/*------------------------------------------------- - huffman__deltarle_export_tree - export a - huffman tree to a target data stream for - delta-RLE encoded data --------------------------------------------------*/ - -huffman_error huffman_deltarle_export_tree(huffman_context *context, UINT8 *dest, UINT32 dlength, UINT32 *actlength) -{ - return export_tree(context, dest, dlength, actlength, HUFFMAN_DELTARLE_CODES); -} - - -/*------------------------------------------------- - 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 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor) -{ - return huffman_compute_tree_interleaved(1, &context, source, swidth, sheight, sstride, sxor); -} - -huffman_error huffman_compute_tree_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor) -{ - UINT32 sx, sy, ctxnum; - huffman_error error; - - /* initialize all nodes */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) - { - huffman_context *context = contexts[ctxnum]; - memset(context->datahisto, 0, sizeof(context->datahisto)); - } - - /* iterate over "height" */ - for (sy = 0; sy < sheight; sy++) - { - /* iterate over "width" */ - for (sx = 0; sx < swidth; ) - { - /* iterate over contexts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++, sx++) - { - huffman_context *context = contexts[ctxnum]; - context->datahisto[source[sx ^ sxor]]++; - } - } - - /* advance to the next row */ - source += sstride; - } - - /* compute optimal trees for each */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) - { - huffman_context *context = contexts[ctxnum]; - error = compute_optimal_tree(context, context->datahisto, HUFFMAN_CODES); - if (error != HUFFERR_NONE) - return error; - } - return HUFFERR_NONE; -} - - -/*------------------------------------------------- - huffman_deltarle_compute_tree - compute an - optimal huffman tree for the given source - data, with pre-encoding as delta-RLE --------------------------------------------------*/ - -huffman_error huffman_deltarle_compute_tree(huffman_context *context, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor) -{ - return huffman_deltarle_compute_tree_interleaved(1, &context, source, swidth, sheight, sstride, sxor); -} - -huffman_error huffman_deltarle_compute_tree_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor) -{ - UINT32 sx, sy, ctxnum; - huffman_error error; + // bits per entry depends on the maxbits + int numbits; + if (m_maxbits >= 16) + numbits = 5; + else if (m_maxbits >= 8) + numbits = 4; + else + numbits = 3; - /* initialize all nodes */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) + // loop until we read all the nodes + int curnode; + for (curnode = 0; curnode < m_numcodes; ) { - huffman_context *context = contexts[ctxnum]; - memset(context->datahisto, 0, sizeof(context->datahisto)); - context->prevdata = 0; - } + // a non-one value is just raw + int nodebits = bitbuf.read(numbits); + if (nodebits != 1) + m_huffnode[curnode++].m_numbits = nodebits; - /* iterate over "height" */ - for (sy = 0; sy < sheight; sy++) - { - /* reset RLE counts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) + // a one value is an escape code + else { - huffman_context *context = contexts[ctxnum]; - context->rleremaining = 0; - } + // a double 1 is just a single 1 + nodebits = bitbuf.read(numbits); + if (nodebits == 1) + m_huffnode[curnode++].m_numbits = nodebits; - /* iterate over "width" */ - for (sx = 0; sx < swidth; ) - { - /* iterate over contexts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++, sx++) + // otherwise, we need one for value for the repeat count + else { - huffman_context *context = contexts[ctxnum]; - UINT8 newdata, delta; - - /* if still counting RLE, do nothing */ - if (context->rleremaining != 0) - { - context->rleremaining--; - continue; - } - - /* fetch new data and compute the delta */ - newdata = source[sx ^ sxor]; - delta = newdata - context->prevdata; - context->prevdata = newdata; - - /* 0 deltas scan forward for a count */ - if (delta == 0) - { - int zerocount = 1; - int rlecode; - UINT32 scan; - - /* count the number of consecutive values */ - for (scan = sx + 1; scan < swidth; scan++) - if (contexts[scan % numcontexts] == context) - { - if (newdata == source[scan ^ sxor]) - zerocount++; - else - break; - } - - /* if we hit the end of row, maximize the count */ - if (scan >= swidth && zerocount >= 8) - zerocount = 100000; - - /* encode the maximal count we can */ - rlecode = rlecount_to_code(zerocount); - context->datahisto[rlecode]++; - - /* set up the remaining count */ - context->rleremaining = code_to_rlecount(rlecode) - 1; - } - else - { - /* encode the actual delta */ - context->datahisto[delta]++; - } + int repcount = bitbuf.read(numbits) + 3; + while (repcount--) + m_huffnode[curnode++].m_numbits = nodebits; } } - - /* advance to the next row */ - source += sstride; } - /* compute optimal trees for each */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) - { - huffman_context *context = contexts[ctxnum]; - error = compute_optimal_tree(context, context->datahisto, HUFFMAN_DELTARLE_CODES); - if (error != HUFFERR_NONE) - return error; - } - return HUFFERR_NONE; -} - - -/*------------------------------------------------- - huffman_encode_data - encode data using the - given tree --------------------------------------------------*/ - -huffman_error huffman_encode_data(huffman_context *context, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor, UINT8 *dest, UINT32 dlength, UINT32 *actlength) -{ - return huffman_encode_data_interleaved(1, &context, source, swidth, sheight, sstride, sxor, dest, dlength, actlength); -} - -huffman_error huffman_encode_data_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor, UINT8 *dest, UINT32 dlength, UINT32 *actlength) -{ - UINT32 sx, sy, ctxnum; - bit_buffer bitbuf; - - /* initialize the output buffer */ - bit_buffer_write_init(&bitbuf, dest, dlength); - - /* iterate over "height" */ - for (sy = 0; sy < sheight; sy++) - { - /* iterate over "width" */ - for (sx = 0; sx < swidth; ) - { - /* iterate over contexts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++, sx++) - { - huffman_context *context = contexts[ctxnum]; - huffman_node *node = &context->huffnode[source[sx ^ sxor]]; - bit_buffer_write(&bitbuf, node->bits, node->numbits); - } - } + // make sure we ended up with the right number + if (curnode != m_numcodes) + return HUFFERR_INVALID_DATA; - /* advance to the next row */ - source += sstride; - } + // assign canonical codes for all nodes based on their code lengths + huffman_error error = assign_canonical_codes(); + if (error != HUFFERR_NONE) + return error; + + // build the lookup table + build_lookup_table(); - /* flush and return a status */ - *actlength = bit_buffer_flush(&bitbuf); - return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; + // determine final input length and report errors + return bitbuf.overflow() ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; } -/*------------------------------------------------- - huffman_deltarle_encode_data - encode data - using the given tree with delta-RLE - pre-encoding --------------------------------------------------*/ +//------------------------------------------------- +// export_tree_rle - export a huffman tree to an +// RLE target data stream +//------------------------------------------------- -huffman_error huffman_deltarle_encode_data(huffman_context *context, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor, UINT8 *dest, UINT32 dlength, UINT32 *actlength) +huffman_error huffman_context_base::export_tree_rle(bitstream_out &bitbuf) { - return huffman_deltarle_encode_data_interleaved(1, &context, source, swidth, sheight, sstride, sxor, dest, dlength, actlength); -} - -huffman_error huffman_deltarle_encode_data_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor, UINT8 *dest, UINT32 dlength, UINT32 *actlength) -{ - UINT32 sx, sy, ctxnum; - bit_buffer bitbuf; - - /* initialize the output buffer */ - bit_buffer_write_init(&bitbuf, dest, dlength); - - /* initialize the contexts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) - { - huffman_context *context = contexts[ctxnum]; - context->prevdata = 0; - } - - /* iterate over "height" */ - for (sy = 0; sy < sheight; sy++) - { - /* reset RLE counts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) - { - huffman_context *context = contexts[ctxnum]; - context->rleremaining = 0; - } - - /* iterate over "width" */ - for (sx = 0; sx < swidth; ) - { - /* iterate over contexts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++, sx++) - { - huffman_context *context = contexts[ctxnum]; - UINT8 newdata, delta; - huffman_node *node; - - /* if still counting RLE, do nothing */ - if (context->rleremaining != 0) - { - context->rleremaining--; - continue; - } - - /* fetch new data and compute the delta */ - newdata = source[sx ^ sxor]; - delta = newdata - context->prevdata; - context->prevdata = newdata; - - /* 0 deltas scan forward for a count */ - if (delta == 0) - { - int zerocount = 1; - int rlecode; - UINT32 scan; - - /* count the number of consecutive values */ - for (scan = sx + 1; scan < swidth; scan++) - if (contexts[scan % numcontexts] == context) - { - if (newdata == source[scan ^ sxor]) - zerocount++; - else - break; - } - - /* if we hit the end of row, maximize the count */ - if (scan >= swidth && zerocount >= 8) - zerocount = 100000; - - /* encode the maximal count we can */ - rlecode = rlecount_to_code(zerocount); - node = &context->huffnode[rlecode]; - bit_buffer_write(&bitbuf, node->bits, node->numbits); - - /* set up the remaining count */ - context->rleremaining = code_to_rlecount(rlecode) - 1; - } - else - { - /* encode the actual delta */ - node = &context->huffnode[delta]; - bit_buffer_write(&bitbuf, node->bits, node->numbits); - } - } - } - - /* advance to the next row */ - source += sstride; - } - - /* flush and return a status */ - *actlength = bit_buffer_flush(&bitbuf); - return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; -} - - -/*------------------------------------------------- - huffman_decode_data - decode data using the - given tree --------------------------------------------------*/ + // bits per entry depends on the maxbits + int numbits; + if (m_maxbits >= 16) + numbits = 5; + else if (m_maxbits >= 8) + numbits = 4; + else + numbits = 3; -huffman_error huffman_decode_data(huffman_context *context, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength) -{ - const huffman_lookup_value *table; - int maxbits = context->maxbits; - huffman_error error; - bit_buffer bitbuf; - UINT32 dx, dy; - - /* regenerate the lookup table if necessary */ - if (context->lookupdirty) + // RLE encode the lengths + int lastval = ~0; + int repcount = 0; + for (int curcode = 0; curcode < m_numcodes; curcode++) { - error = build_lookup_table(context, HUFFMAN_CODES); - if (error != HUFFERR_NONE) - return error; - } - table = context->lookup; - - /* initialize our bit buffer */ - bit_buffer_read_init(&bitbuf, source, slength); + // if we match the previous value, just bump the repcount + int newval = m_huffnode[curcode].m_numbits; + if (newval == lastval) + repcount++; - /* iterate over "height" */ - for (dy = 0; dy < dheight; dy++) - { - /* iterate over "width" */ - for (dx = 0; dx < dwidth; dx++) + // otherwise, we need to flush the previous repeats + else { - huffman_lookup_value lookup; - UINT32 bits; - - /* peek ahead to get maxbits worth of data */ - bits = bit_buffer_peek(&bitbuf, maxbits); - - /* look it up, then remove the actual number of bits for this code */ - lookup = table[bits]; - bit_buffer_remove(&bitbuf, LOOKUP_BITS(lookup)); - - /* store the upper byte */ - dest[dx ^ dxor] = LOOKUP_CODE(lookup); + if (repcount != 0) + write_rle_tree_bits(bitbuf, lastval, repcount, numbits); + lastval = newval; + repcount = 1; } - - /* advance to the next row */ - dest += dstride; } - /* determine the actual length and indicate overflow */ - *actlength = bit_buffer_read_offset(&bitbuf); - return bitbuf.overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; + // flush the last value + write_rle_tree_bits(bitbuf, lastval, repcount, numbits); + return bitbuf.overflow() ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; } -/*------------------------------------------------- - huffman_decode_data_interleaved - decode - interleaved data using multiple contexts --------------------------------------------------*/ +//------------------------------------------------- +// import_tree_huffman - import a huffman-encoded +// huffman tree from a source data stream +//------------------------------------------------- -huffman_error huffman_decode_data_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength) +huffman_error huffman_context_base::import_tree_huffman(bitstream_in &bitbuf) { - UINT32 dx, dy, ctxnum; - huffman_error error; - bit_buffer bitbuf; - - /* regenerate the lookup tables if necessary */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) + // start by parsing the lengths for the small tree + huffman_decoder<24, 6> smallhuff; + smallhuff.m_huffnode[0].m_numbits = bitbuf.read(3); + int start = bitbuf.read(3) + 1; + int count = 0; + for (int index = 1; index < 24; index++) { - huffman_context *context = contexts[ctxnum]; - if (context->lookupdirty) + if (index < start || count == 7) + smallhuff.m_huffnode[index].m_numbits = 0; + else { - error = build_lookup_table(context, HUFFMAN_CODES); - if (error != HUFFERR_NONE) - return error; + count = bitbuf.read(3); + smallhuff.m_huffnode[index].m_numbits = (count == 7) ? 0 : count; } } - - /* initialize our bit buffer */ - bit_buffer_read_init(&bitbuf, source, slength); - - /* iterate over "height" */ - for (dy = 0; dy < dheight; dy++) - { - /* iterate over "width" */ - for (dx = 0; dx < dwidth; ) + + // then regenerate the tree + huffman_error error = smallhuff.assign_canonical_codes(); + if (error != HUFFERR_NONE) + return error; + smallhuff.build_lookup_table(); + + // determine the maximum length of an RLE count + UINT32 temp = m_numcodes - 9; + UINT8 rlefullbits = 0; + while (temp != 0) + temp >>= 1, rlefullbits++; + + // now process the rest of the data + int last = 0; + int curcode; + for (curcode = 0; curcode < m_numcodes; ) + { + int value = smallhuff.decode_one(bitbuf); + if (value != 0) + m_huffnode[curcode++].m_numbits = last = value - 1; + else { - /* iterate over contexts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++, dx++) - { - huffman_context *context = contexts[ctxnum]; - huffman_lookup_value lookup; - UINT32 bits; - - /* peek ahead to get maxbits worth of data */ - bits = bit_buffer_peek(&bitbuf, context->maxbits); - - /* look it up, then remove the actual number of bits for this code */ - lookup = context->lookup[bits]; - bit_buffer_remove(&bitbuf, LOOKUP_BITS(lookup)); - - /* store the upper byte */ - dest[dx ^ dxor] = LOOKUP_CODE(lookup); - } + int count = bitbuf.read(3) + 2; + if (count == 7+2) + count += bitbuf.read(rlefullbits); + for ( ; count != 0 && curcode < m_numcodes; count--) + m_huffnode[curcode++].m_numbits = last; } - - /* advance to the next row */ - dest += dstride; - } - - /* determine the actual length and indicate overflow */ - *actlength = bit_buffer_read_offset(&bitbuf); - return bitbuf.overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; -} - - -/*------------------------------------------------- - huffman_deltarle_decode_data - decode data - using the given tree with delta-RLE - post-decoding --------------------------------------------------*/ - -huffman_error huffman_deltarle_decode_data(huffman_context *context, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength) -{ - const huffman_lookup_value *table; - int maxbits = context->maxbits; - UINT32 rleremaining = 0; - huffman_error error; - UINT8 prevdata = 0; - bit_buffer bitbuf; - UINT32 dx, dy; - - /* regenerate the lookup table if necessary */ - if (context->lookupdirty) - { - error = build_lookup_table(context, HUFFMAN_DELTARLE_CODES); - if (error != HUFFERR_NONE) - return error; } - table = context->lookup; - - /* initialize our bit buffer */ - bit_buffer_read_init(&bitbuf, source, slength); - - /* iterate over "height" */ - for (dy = 0; dy < dheight; dy++) - { - /* reset RLE counts */ - rleremaining = 0; - - /* iterate over "width" */ - for (dx = 0; dx < dwidth; dx++) - { - huffman_lookup_value lookup; - UINT32 bits; - int data; - /* if we have RLE remaining, just store that */ - if (rleremaining != 0) - { - rleremaining--; - dest[dx ^ dxor] = prevdata; - continue; - } - - /* peek ahead to get maxbits worth of data */ - bits = bit_buffer_peek(&bitbuf, maxbits); - - /* look it up, then remove the actual number of bits for this code */ - lookup = table[bits]; - bit_buffer_remove(&bitbuf, LOOKUP_BITS(lookup)); - - /* compute the data and handle RLE decoding */ - data = LOOKUP_CODE(lookup); - - /* if not an RLE special, just add to the previous; otherwise, start counting RLE */ - if (data < 0x100) - prevdata += (UINT8)data; - else - rleremaining = code_to_rlecount(data) - 1; + // make sure we ended up with the right number + if (curcode != m_numcodes) + return HUFFERR_INVALID_DATA; - /* store the updated data value */ - dest[dx ^ dxor] = prevdata; - } + // assign canonical codes for all nodes based on their code lengths + error = assign_canonical_codes(); + if (error != HUFFERR_NONE) + return error; - /* advance to the next row */ - dest += dstride; - } + // build the lookup table + build_lookup_table(); - /* determine the actual length and indicate overflow */ - *actlength = bit_buffer_read_offset(&bitbuf); - return bitbuf.overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; + // determine final input length and report errors + return bitbuf.overflow() ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; } -/*------------------------------------------------- - huffman_deltarle_decode_data_interleaved - - decode data using multiple contexts and - delta-RLE post-decoding --------------------------------------------------*/ +//------------------------------------------------- +// export_tree_huffman - export a huffman tree to +// a huffman target data stream +//------------------------------------------------- -huffman_error huffman_deltarle_decode_data_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength) +huffman_error huffman_context_base::export_tree_huffman(bitstream_out &bitbuf) { - UINT32 dx, dy, ctxnum; - huffman_error error; - bit_buffer bitbuf; - - /* fast case the A/V Y/Cb/Y/Cr case */ - if (numcontexts == 4 && contexts[0] == contexts[2] && contexts[0] != contexts[1] && contexts[1] != contexts[3] && - contexts[0]->maxbits == contexts[1]->maxbits && contexts[0]->maxbits == contexts[3]->maxbits) - return huffman_deltarle_decode_data_interleaved_0102(contexts, source, slength, dest, dwidth, dheight, dstride, dxor, actlength); + // first RLE compress the lengths of all the nodes + dynamic_array<UINT8> rle_data(m_numcodes); + UINT8 *dest = rle_data; + dynamic_array<UINT16> rle_lengths(m_numcodes/3); + UINT16 *lengths = rle_lengths; + int last = ~0; + int repcount = 0; + + // use a small huffman context to create a tree (ignoring RLE lengths) + huffman_encoder<24, 6> smallhuff; - /* regenerate the lookup tables if necessary */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) + // RLE-compress the lengths + for (int curcode = 0; curcode < m_numcodes; curcode++) { - huffman_context *context = contexts[ctxnum]; - if (context->lookupdirty) + // if this is the end of a repeat, flush any accumulation + int newval = m_huffnode[curcode].m_numbits; + if (newval != last && repcount > 0) { - error = build_lookup_table(context, HUFFMAN_DELTARLE_CODES); - if (error != HUFFERR_NONE) - return error; + if (repcount == 1) + smallhuff.histo_one(*dest++ = last + 1); + else + smallhuff.histo_one(*dest++ = 0), *lengths++ = repcount - 2; } - context->prevdata = 0; - } - - /* initialize our bit buffer */ - bit_buffer_read_init(&bitbuf, source, slength); - - /* iterate over "height" */ - for (dy = 0; dy < dheight; dy++) - { - /* reset RLE counts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++) - { - huffman_context *context = contexts[ctxnum]; - context->rleremaining = 0; - } - - /* iterate over "width" */ - for (dx = 0; dx < dwidth; ) + + // if same as last, just track repeats + if (newval == last) + repcount++; + + // otherwise, write it and start a new run + else { - /* iterate over contexts */ - for (ctxnum = 0; ctxnum < numcontexts; ctxnum++, dx++) - { - huffman_context *context = contexts[ctxnum]; - huffman_lookup_value lookup; - UINT32 bits; - int data; - - /* if we have RLE remaining, just store that */ - if (context->rleremaining != 0) - { - context->rleremaining--; - dest[dx ^ dxor] = context->prevdata; - continue; - } - - /* peek ahead to get maxbits worth of data */ - bits = bit_buffer_peek(&bitbuf, context->maxbits); - - /* look it up, then remove the actual number of bits for this code */ - lookup = context->lookup[bits]; - bit_buffer_remove(&bitbuf, LOOKUP_BITS(lookup)); - - /* compute the data and handle RLE decoding */ - data = LOOKUP_CODE(lookup); - - /* if not an RLE special, just add to the previous; otherwise, start counting RLE */ - if (data < 0x100) - context->prevdata += (UINT8)data; - else - context->rleremaining = code_to_rlecount(data) - 1; - - /* store the updated data value */ - dest[dx ^ dxor] = context->prevdata; - } + smallhuff.histo_one(*dest++ = newval + 1); + last = newval; + repcount = 0; } - - /* advance to the next row */ - dest += dstride; } - /* determine the actual length and indicate overflow */ - *actlength = bit_buffer_read_offset(&bitbuf); - return bitbuf.overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; -} - - -/*------------------------------------------------- - huffman_deltarle_decode_data_interleaved_0102 - - decode data using 3 unique contexts in - 0/1/0/2 order (used for Y/Cb/Y/Cr encoding) --------------------------------------------------*/ - -static huffman_error huffman_deltarle_decode_data_interleaved_0102(huffman_context **contexts, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength) -{ - const huffman_lookup_value *table02, *table1, *table3; - int rleremaining02, rleremaining1, rleremaining3; - UINT8 prevdata02 = 0, prevdata1 = 0, prevdata3 = 0; - int maxbits = contexts[0]->maxbits; - huffman_error error; - bit_buffer bitbuf; - UINT32 dx, dy; - - /* regenerate the lookup tables if necessary */ - if (contexts[0]->lookupdirty) - { - error = build_lookup_table(contexts[0], HUFFMAN_DELTARLE_CODES); - if (error != HUFFERR_NONE) - return error; - } - if (contexts[1]->lookupdirty) + // flush any final RLE counts + if (repcount > 0) { - error = build_lookup_table(contexts[1], HUFFMAN_DELTARLE_CODES); - if (error != HUFFERR_NONE) - return error; + if (repcount == 1) + smallhuff.histo_one(*dest++ = last + 1); + else + smallhuff.histo_one(*dest++ = 0), *lengths++ = repcount - 2; } - if (contexts[3]->lookupdirty) - { - error = build_lookup_table(contexts[3], HUFFMAN_DELTARLE_CODES); - if (error != HUFFERR_NONE) - return error; - } - - /* cache the tables locally */ - table02 = contexts[0]->lookup; - table1 = contexts[1]->lookup; - table3 = contexts[3]->lookup; - /* initialize our bit buffer */ - bit_buffer_read_init(&bitbuf, source, slength); + // compute an optimal tree + smallhuff.compute_tree_from_histo(); - /* iterate over "height" */ - for (dy = 0; dy < dheight; dy++) - { - /* reset RLE counts */ - rleremaining02 = rleremaining1 = rleremaining3 = 0; - - /* iterate over "width" */ - for (dx = 0; dx < dwidth; dx += 4) + // determine the first and last non-zero nodes + int first_non_zero = 31, last_non_zero = 0; + for (int index = 1; index < smallhuff.m_numcodes; index++) + if (smallhuff.m_huffnode[index].m_numbits != 0) { - huffman_lookup_value lookup; - UINT32 bits; - int data; - - /* ----- offset 0 ----- */ - - /* if we have RLE remaining, just store that */ - if (rleremaining02 != 0) - rleremaining02--; - else - { - /* peek ahead to get maxbits worth of data */ - bits = bit_buffer_peek(&bitbuf, maxbits); - - /* look it up, then remove the actual number of bits for this code */ - lookup = table02[bits]; - bit_buffer_remove(&bitbuf, LOOKUP_BITS(lookup)); - - /* compute the data and handle RLE decoding */ - data = LOOKUP_CODE(lookup); - - /* if not an RLE special, just add to the previous; otherwise, start counting RLE */ - if (data < 0x100) - prevdata02 += (UINT8)data; - else - rleremaining02 = code_to_rlecount(data) - 1; - } - - /* store the updated data value */ - dest[(dx + 0) ^ dxor] = prevdata02; - - /* ----- offset 1 ----- */ - - /* if we have RLE remaining, just store that */ - if (rleremaining1 != 0) - rleremaining1--; - else - { - /* peek ahead to get maxbits worth of data */ - bits = bit_buffer_peek(&bitbuf, maxbits); - - /* look it up, then remove the actual number of bits for this code */ - lookup = table1[bits]; - bit_buffer_remove(&bitbuf, LOOKUP_BITS(lookup)); - - /* compute the data and handle RLE decoding */ - data = LOOKUP_CODE(lookup); - - /* if not an RLE special, just add to the previous; otherwise, start counting RLE */ - if (data < 0x100) - prevdata1 += (UINT8)data; - else - rleremaining1 = code_to_rlecount(data) - 1; - } - - /* store the updated data value */ - dest[(dx + 1) ^ dxor] = prevdata1; - - /* ----- offset 2 (same as 0) ----- */ - - /* if we have RLE remaining, just store that */ - if (rleremaining02 != 0) - rleremaining02--; - else - { - /* peek ahead to get maxbits worth of data */ - bits = bit_buffer_peek(&bitbuf, maxbits); - - /* look it up, then remove the actual number of bits for this code */ - lookup = table02[bits]; - bit_buffer_remove(&bitbuf, LOOKUP_BITS(lookup)); - - /* compute the data and handle RLE decoding */ - data = LOOKUP_CODE(lookup); - - /* if not an RLE special, just add to the previous; otherwise, start counting RLE */ - if (data < 0x100) - prevdata02 += (UINT8)data; - else - rleremaining02 = code_to_rlecount(data) - 1; - } - - /* store the updated data value */ - dest[(dx + 2) ^ dxor] = prevdata02; - - /* ----- offset 3 ----- */ + if (first_non_zero == 31) + first_non_zero = index; + last_non_zero = index; + } - /* if we have RLE remaining, just store that */ - if (rleremaining3 != 0) - rleremaining3--; + // clamp first non-zero to be 8 at a maximum + first_non_zero = MIN(first_non_zero, 8); + + // output the lengths of the each small tree node, starting with the RLE + // token (0), followed by the first_non_zero value, followed by the data + // terminated by a 7 + bitbuf.write(smallhuff.m_huffnode[0].m_numbits, 3); + bitbuf.write(first_non_zero - 1, 3); + for (int index = first_non_zero; index <= last_non_zero; index++) + bitbuf.write(smallhuff.m_huffnode[index].m_numbits, 3); + bitbuf.write(7, 3); + + // determine the maximum length of an RLE count + UINT32 temp = m_numcodes - 9; + UINT8 rlefullbits = 0; + while (temp != 0) + temp >>= 1, rlefullbits++; + + // now encode the RLE data + lengths = rle_lengths; + for (UINT8 *src = rle_data; src < dest; src++) + { + // encode the data + UINT8 data = *src; + smallhuff.encode_one(bitbuf, data); + + // if this is an RLE token, encode the length following + if (data == 0) + { + int count = *lengths++; + if (count < 7) + bitbuf.write(count, 3); else - { - /* peek ahead to get maxbits worth of data */ - bits = bit_buffer_peek(&bitbuf, maxbits); - - /* look it up, then remove the actual number of bits for this code */ - lookup = table3[bits]; - bit_buffer_remove(&bitbuf, LOOKUP_BITS(lookup)); - - /* compute the data and handle RLE decoding */ - data = LOOKUP_CODE(lookup); - - /* if not an RLE special, just add to the previous; otherwise, start counting RLE */ - if (data < 0x100) - prevdata3 += (UINT8)data; - else - rleremaining3 = code_to_rlecount(data) - 1; - } - - /* store the updated data value */ - dest[(dx + 3) ^ dxor] = prevdata3; + bitbuf.write(7, 3), bitbuf.write(count - 7, rlefullbits); } - - /* advance to the next row */ - dest += dstride; } - - /* determine the actual length and indicate overflow */ - *actlength = bit_buffer_read_offset(&bitbuf); - return bitbuf.overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; + + // flush the final buffer + return bitbuf.overflow() ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; } +//------------------------------------------------- +// compute_tree_from_histo - common backend for +// computing a tree based on the data histogram +//------------------------------------------------- -/*************************************************************************** - INTERNAL FUNCTIONS -***************************************************************************/ - -/*------------------------------------------------- - import_tree - import a huffman tree from a - source data stream --------------------------------------------------*/ - -static huffman_error import_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 *actlength, UINT32 numcodes) +huffman_error huffman_context_base::compute_tree_from_histo() { - 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; + // compute the number of data items in the histogram + UINT32 sdatacount = 0; + for (int i = 0; i < m_numcodes; i++) + sdatacount += m_datahisto[i]; - /* loop until we read all the nodes */ - for (curnode = 0; curnode < numcodes; ) + // binary search to achieve the optimum encoding + UINT32 lowerweight = 0; + UINT32 upperweight = sdatacount * 2; + while (1) { - int nodebits = bit_buffer_read(&bitbuf, numbits); - - /* a non-one value is just raw */ - if (nodebits != 1) - context->huffnode[curnode++].numbits = nodebits; + // build a tree using the current weight + UINT32 curweight = (upperweight + lowerweight) / 2; + int curmaxbits = build_tree(sdatacount, curweight); - /* a one value is an escape code */ - else + // apply binary search here + if (curmaxbits <= m_maxbits) { - nodebits = bit_buffer_read(&bitbuf, numbits); - - /* a double 1 is just a single 1 */ - if (nodebits == 1) - context->huffnode[curnode++].numbits = nodebits; + lowerweight = curweight; - /* 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; - } + // 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 */ - error = assign_canonical_codes(context, numcodes); - if (error != HUFFERR_NONE) - return error; - - /* make sure we ended up with the right number */ - if (curnode != numcodes) - return HUFFERR_INVALID_DATA; - - *actlength = bit_buffer_read_offset(&bitbuf); - return bitbuf.overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; + // assign canonical codes for all nodes based on their code lengths + return assign_canonical_codes(); } -/*------------------------------------------------- - export_tree - export a huffman tree to a - target data stream --------------------------------------------------*/ - -static huffman_error export_tree(huffman_context *context, UINT8 *dest, UINT32 dlength, UINT32 *actlength, UINT32 numcodes) -{ - 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 < numcodes; 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) - write_rle_tree_bits(&bitbuf, lastval, repcount, numbits); - lastval = newval; - repcount = 1; - } - } - - /* flush the last value */ - write_rle_tree_bits(&bitbuf, lastval, repcount, numbits); - *actlength = bit_buffer_flush(&bitbuf); - return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; -} +//************************************************************************** +// INTERNAL FUNCTIONS +//************************************************************************** -/*------------------------------------------------- - write_rle_tree_bits - write an RLE encoded - set of data to a target stream --------------------------------------------------*/ +//------------------------------------------------- +// write_rle_tree_bits - write an RLE encoded +// set of data to a target stream +//------------------------------------------------- -static void write_rle_tree_bits(bit_buffer *bitbuf, int value, int repcount, int numbits) +void huffman_context_base::write_rle_tree_bits(bitstream_out &bitbuf, int value, int repcount, int numbits) { - /* loop until we have output all of the repeats */ + // 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 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); + bitbuf.write(1, numbits); + bitbuf.write(1, numbits); repcount--; } - /* if we have two or fewer in a row, write them raw */ + // if we have two or fewer in a row, write them raw else if (repcount <= 2) { - bit_buffer_write(bitbuf, value, numbits); + bitbuf.write(value, numbits); repcount--; } - /* otherwise, write a triple using 1 as the escape code */ + // 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); + bitbuf.write(1, numbits); + bitbuf.write(value, numbits); + bitbuf.write(cur_reps, numbits); repcount -= cur_reps + 3; } } } -/*------------------------------------------------- - tree_node_compare - compare two tree nodes - by weight --------------------------------------------------*/ - -static int CLIB_DECL 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; -} - - -/*------------------------------------------------- - compute_optimal_tree - common backend for - computing a tree based on the data histogram --------------------------------------------------*/ +//------------------------------------------------- +// tree_node_compare - compare two tree nodes +// by weight +//------------------------------------------------- -static huffman_error compute_optimal_tree(huffman_context *context, const UINT32 *datahisto, UINT32 numcodes) +int CLIB_DECL huffman_context_base::tree_node_compare(const void *item1, const void *item2) { - UINT32 lowerweight, upperweight; - UINT32 sdatacount; - int i; - - /* compute the number of data items in the histogram */ - sdatacount = 0; - for (i = 0; i < numcodes; i++) - sdatacount += datahisto[i]; - - /* binary search to achieve the optimum encoding */ - lowerweight = 0; - upperweight = sdatacount * 2; - while (TRUE) - { - UINT32 curweight = (upperweight + lowerweight) / 2; - int curmaxbits; - - /* build a tree using the current weight */ - curmaxbits = huffman_build_tree(context, datahisto, sdatacount, curweight, numcodes); - - /* 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 == sdatacount || (upperweight - lowerweight) <= 1) - break; - } - else - upperweight = curweight; - } - - /* assign canonical codes for all nodes based on their code lengths */ - return assign_canonical_codes(context, numcodes); + const node_t *node1 = *(const node_t **)item1; + const node_t *node2 = *(const node_t **)item2; + return node2->m_weight - node1->m_weight; } -/*------------------------------------------------- - huffman_build_tree - build a huffman tree - based on the data distribution --------------------------------------------------*/ +//------------------------------------------------- +// 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, UINT32 numcodes) +int huffman_context_base::build_tree(UINT32 totaldata, UINT32 totalweight) { - huffman_node *list[MAX_HUFFMAN_CODES]; - int listitems; - int nextalloc; - int maxbits; - int i; - - /* make a list of all non-zero nodes */ - listitems = 0; - memset(context->huffnode, 0, numcodes * sizeof(context->huffnode[0])); - for (i = 0; i < numcodes; i++) - if (datahisto[i] != 0) + // make a list of all non-zero nodes + dynamic_array<node_t *> list(m_numcodes * 2); + int listitems = 0; + memset(m_huffnode, 0, m_numcodes * sizeof(m_huffnode[0])); + for (int curcode = 0; curcode < m_numcodes; curcode++) + if (m_datahisto[curcode] != 0) { - list[listitems++] = &context->huffnode[i]; - context->huffnode[i].count = datahisto[i]; + list[listitems++] = &m_huffnode[curcode]; + m_huffnode[curcode].m_count = m_datahisto[curcode]; - /* 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; + // scale the weight by the current effective length, ensuring we don't go to 0 + m_huffnode[curcode].m_weight = UINT64(m_datahisto[curcode]) * UINT64(totalweight) / UINT64(totaldata); + if (m_huffnode[curcode].m_weight == 0) + m_huffnode[curcode].m_weight = 1; } - /* sort the list by weight, largest weight first */ + // sort the list by weight, largest weight first qsort(list, listitems, sizeof(list[0]), tree_node_compare); - /* now build the tree */ - nextalloc = MAX_HUFFMAN_CODES; + // now build the tree + int nextalloc = m_numcodes; while (listitems > 1) { - huffman_node *node0, *node1, *newnode; - - /* remove lowest two items */ - node1 = list[--listitems]; - node0 = list[--listitems]; + // remove lowest two items + node_t &node1 = *list[--listitems]; + node_t &node0 = *list[--listitems]; - /* create new node */ - newnode = &context->huffnode[nextalloc++]; - newnode->parent = NULL; - node0->parent = node1->parent = newnode; - newnode->weight = node0->weight + node1->weight; + // create new node + node_t &newnode = m_huffnode[nextalloc++]; + newnode.m_parent = NULL; + node0.m_parent = node1.m_parent = &newnode; + newnode.m_weight = node0.m_weight + node1.m_weight; - /* insert into list at appropriate location */ - for (i = 0; i < listitems; i++) - if (newnode->weight > list[i]->weight) + // insert into list at appropriate location + int curitem; + for (curitem = 0; curitem < listitems; curitem++) + if (newnode.m_weight > list[curitem]->m_weight) { - memmove(&list[i+1], &list[i], (listitems - i) * sizeof(list[0])); + memmove(&list[curitem+1], &list[curitem], (listitems - curitem) * sizeof(list[0])); break; } - list[i] = newnode; + list[curitem] = &newnode; listitems++; } - /* compute the number of bits in each code, and fill in another histogram */ - maxbits = 0; - for (i = 0; i < numcodes; i++) + // compute the number of bits in each code, and fill in another histogram + int maxbits = 0; + for (int curcode = 0; curcode < m_numcodes; curcode++) { - huffman_node *node = &context->huffnode[i]; - node->numbits = 0; + node_t &node = m_huffnode[curcode]; + node.m_numbits = 0; - /* if we have a non-zero weight, compute the number of bits */ - if (node->weight > 0) + // if we have a non-zero weight, compute the number of bits + if (node.m_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); + // determine the number of bits for this node + for (node_t *curnode = &node; curnode->m_parent != NULL; curnode = curnode->m_parent) + node.m_numbits++; + if (node.m_numbits == 0) + node.m_numbits = 1; + + // keep track of the max + maxbits = MAX(maxbits, node.m_numbits); } } - return maxbits; } -/*------------------------------------------------- - assign_canonical_codes - assign - canonical codes to all the nodes based on the - number of bits in each --------------------------------------------------*/ +//------------------------------------------------- +// assign_canonical_codes - assign canonical codes +// to all the nodes based on the number of bits +// in each +//------------------------------------------------- -static huffman_error assign_canonical_codes(huffman_context *context, UINT32 numcodes) +huffman_error huffman_context_base::assign_canonical_codes() { - UINT32 bithisto[33]; - int curstart; - int i; - - /* build up a histogram of bit lengths */ - memset(bithisto, 0, sizeof(bithisto)); - for (i = 0; i < numcodes; i++) + // build up a histogram of bit lengths + UINT32 bithisto[33] = { 0 }; + for (int curcode = 0; curcode < m_numcodes; curcode++) { - huffman_node *node = &context->huffnode[i]; - if (node->numbits > context->maxbits) + node_t &node = m_huffnode[curcode]; + if (node.m_numbits > m_maxbits) return HUFFERR_INTERNAL_INCONSISTENCY; - if (node->numbits <= 32) - bithisto[node->numbits]++; + if (node.m_numbits <= 32) + bithisto[node.m_numbits]++; } - /* for each code length, determine the starting code number */ - curstart = 0; - for (i = 32; i > 0; i--) + // for each code length, determine the starting code number + UINT32 curstart = 0; + for (int codelen = 32; codelen > 0; codelen--) { - UINT32 nextstart = (curstart + bithisto[i]) >> 1; - if (i != 1 && nextstart * 2 != (curstart + bithisto[i])) + UINT32 nextstart = (curstart + bithisto[codelen]) >> 1; + if (codelen != 1 && nextstart * 2 != (curstart + bithisto[codelen])) return HUFFERR_INTERNAL_INCONSISTENCY; - bithisto[i] = curstart; + bithisto[codelen] = curstart; curstart = nextstart; } - /* now assign canonical codes */ - for (i = 0; i < numcodes; i++) + // now assign canonical codes + for (int curcode = 0; curcode < m_numcodes; curcode++) { - huffman_node *node = &context->huffnode[i]; - if (node->numbits > 0) - node->bits = bithisto[node->numbits]++; + node_t &node = m_huffnode[curcode]; + if (node.m_numbits > 0) + node.m_bits = bithisto[node.m_numbits]++; } - - /* if there was a decoding table, get rid of it now */ - context->lookupdirty = TRUE; return HUFFERR_NONE; } -/*------------------------------------------------- - build_lookup_table - build a lookup - table for fast decoding --------------------------------------------------*/ +//------------------------------------------------- +// build_lookup_table - build a lookup table for +// fast decoding +//------------------------------------------------- -static huffman_error build_lookup_table(huffman_context *context, UINT32 numcodes) +void huffman_context_base::build_lookup_table() { - int i; - - /* allocate a table if needed */ - if (context->lookup == NULL) - context->lookup = (huffman_lookup_value *)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 < numcodes; i++) + // iterate over all codes + for (int curcode = 0; curcode < m_numcodes; curcode++) { - huffman_node *node = &context->huffnode[i]; - if (node->numbits > 0) + // process all nodes which have non-zero bits + node_t &node = m_huffnode[curcode]; + if (node.m_numbits > 0) { - huffman_lookup_value *dest, *destend; + // set up the entry + lookup_value value = MAKE_LOOKUP(curcode, node.m_numbits); - /* 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 << 6) | node->numbits; - - /* fill all matching entries */ - dest = &context->lookup[start]; - destend = &context->lookup[end]; + // fill all matching entries + int shift = m_maxbits - node.m_numbits; + lookup_value *dest = &m_lookup[node.m_bits << shift]; + lookup_value *destend = &m_lookup[((node.m_bits + 1) << shift) - 1]; while (dest <= destend) *dest++ = value; } } +} - /* no longer dirty */ - context->lookupdirty = FALSE; - return HUFFERR_NONE; + + +//************************************************************************** +// 8-BIT ENCODER +//************************************************************************** + +//------------------------------------------------- +// huffman_8bit_encoder - constructor +//------------------------------------------------- + +huffman_8bit_encoder::huffman_8bit_encoder() +{ +} + + +//------------------------------------------------- +// encode - encode a full buffer +//------------------------------------------------- + +huffman_error huffman_8bit_encoder::encode(const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 &complength) +{ + // first compute the histogram + histo_reset(); + for (UINT32 cur = 0; cur < slength; cur++) + histo_one(source[cur]); + + // then compute the tree + huffman_error err = compute_tree_from_histo(); + if (err != HUFFERR_NONE) + return err; + + // export the tree + bitstream_out bitbuf(dest, dlength); + err = export_tree_huffman(bitbuf); + if (err != HUFFERR_NONE) + return err; + + // then encode the data + for (UINT32 cur = 0; cur < slength; cur++) + encode_one(bitbuf, source[cur]); + complength = bitbuf.flush(); + return bitbuf.overflow() ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; +} + + + +//************************************************************************** +// 8-BIT DECODER +//************************************************************************** + +//------------------------------------------------- +// huffman_8bit_decoder - constructor +//------------------------------------------------- + +huffman_8bit_decoder::huffman_8bit_decoder() +{ +} + + +//------------------------------------------------- +// decode - decode a full buffer +//------------------------------------------------- + +huffman_error huffman_8bit_decoder::decode(const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength) +{ + // first import the tree + bitstream_in bitbuf(source, slength); + huffman_error err = import_tree_huffman(bitbuf); + if (err != HUFFERR_NONE) + return err; + + // then decode the data + for (UINT32 cur = 0; cur < dlength; cur++) + dest[cur] = decode_one(bitbuf); + bitbuf.flush(); + return bitbuf.overflow() ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE; } |