summaryrefslogtreecommitdiffstatshomepage
path: root/trunk/src/lib/util/huffman.c
diff options
context:
space:
mode:
Diffstat (limited to 'trunk/src/lib/util/huffman.c')
-rw-r--r--trunk/src/lib/util/huffman.c1695
1 files changed, 1695 insertions, 0 deletions
diff --git a/trunk/src/lib/util/huffman.c b/trunk/src/lib/util/huffman.c
new file mode 100644
index 00000000000..3b9c4ea52b8
--- /dev/null
+++ b/trunk/src/lib/util/huffman.c
@@ -0,0 +1,1695 @@
+/***************************************************************************
+
+ huffman.c
+
+ Video compression and decompression helpers.
+
+****************************************************************************
+
+ Copyright Aaron Giles
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are
+ met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in
+ the documentation and/or other materials provided with the
+ distribution.
+ * Neither the name 'MAME' nor the names of its contributors may be
+ used to endorse or promote products derived from this software
+ without specific prior written permission.
+
+ THIS SOFTWARE IS PROVIDED BY AARON GILES ''AS IS'' AND ANY EXPRESS OR
+ IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL AARON GILES BE LIABLE FOR ANY DIRECT,
+ INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+ IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ POSSIBILITY OF SUCH DAMAGE.
+
+****************************************************************************
+
+ Maximum codelength is officially (alphabetsize - 1). This would be 255 bits
+ (since we use 1 byte values). However, it is also dependent upon the number
+ of samples used, as follows:
+
+ 2 bits -> 3..4 samples
+ 3 bits -> 5..7 samples
+ 4 bits -> 8..12 samples
+ 5 bits -> 13..20 samples
+ 6 bits -> 21..33 samples
+ 7 bits -> 34..54 samples
+ 8 bits -> 55..88 samples
+ 9 bits -> 89..143 samples
+ 10 bits -> 144..232 samples
+ 11 bits -> 233..376 samples
+ 12 bits -> 377..609 samples
+ 13 bits -> 610..986 samples
+ 14 bits -> 987..1596 samples
+ 15 bits -> 1597..2583 samples
+ 16 bits -> 2584..4180 samples -> note that a 4k data size guarantees codelength <= 16 bits
+ 17 bits -> 4181..6764 samples
+ 18 bits -> 6765..10945 samples
+ 19 bits -> 10946..17710 samples
+ 20 bits -> 17711..28656 samples
+ 21 bits -> 28657..46367 samples
+ 22 bits -> 46368..75024 samples
+ 23 bits -> 75025..121392 samples
+ 24 bits -> 121393..196417 samples
+ 25 bits -> 196418..317810 samples
+ 26 bits -> 317811..514228 samples
+ 27 bits -> 514229..832039 samples
+ 28 bits -> 832040..1346268 samples
+ 29 bits -> 1346269..2178308 samples
+ 30 bits -> 2178309..3524577 samples
+ 31 bits -> 3524578..5702886 samples
+ 32 bits -> 5702887..9227464 samples
+
+ Looking at it differently, here is where powers of 2 fall into these buckets:
+
+ 256 samples -> 11 bits max
+ 512 samples -> 12 bits max
+ 1k samples -> 14 bits max
+ 2k samples -> 15 bits max
+ 4k samples -> 16 bits max
+ 8k samples -> 18 bits max
+ 16k samples -> 19 bits max
+ 32k samples -> 21 bits max
+ 64k samples -> 22 bits max
+ 128k samples -> 24 bits max
+ 256k samples -> 25 bits max
+ 512k samples -> 27 bits max
+ 1M samples -> 28 bits max
+ 2M samples -> 29 bits max
+ 4M samples -> 31 bits max
+ 8M samples -> 32 bits max
+
+****************************************************************************
+
+ Delta-RLE encoding works as follows:
+
+ Starting value is assumed to be 0. All data is encoded as a delta
+ from the previous value, such that final[i] = final[i - 1] + delta.
+ Long runs of 0s are RLE-encoded as follows:
+
+ 0x100 = repeat count of 8
+ 0x101 = repeat count of 9
+ 0x102 = repeat count of 10
+ 0x103 = repeat count of 11
+ 0x104 = repeat count of 12
+ 0x105 = repeat count of 13
+ 0x106 = repeat count of 14
+ 0x107 = repeat count of 15
+ 0x108 = repeat count of 16
+ 0x109 = repeat count of 32
+ 0x10a = repeat count of 64
+ 0x10b = repeat count of 128
+ 0x10c = repeat count of 256
+ 0x10d = repeat count of 512
+ 0x10e = repeat count of 1024
+ 0x10f = repeat count of 2048
+
+ Note that repeat counts are reset at the end of a row, so if a 0 run
+ extends to the end of a row, a large repeat count may be used.
+
+ The reason for starting the run counts at 8 is that 0 is expected to
+ be the most common symbol, and is typically encoded in 1 or 2 bits.
+
+***************************************************************************/
+
+#include <stdlib.h>
+
+#include "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) << 6) | ((bits) & 0x1f))
+#define LOOKUP_CODE(val) ((val) >> 6)
+#define LOOKUP_BITS(val) ((val) & 0x1f)
+
+
+
+/***************************************************************************
+ TYPE DEFINITIONS
+***************************************************************************/
+
+typedef struct _bit_buffer bit_buffer;
+struct _bit_buffer
+{
+ 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 */
+ 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;
+}
+
+
+/*-------------------------------------------------
+ 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_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;
+
+ /* initialize all nodes */
+ for (ctxnum = 0; ctxnum < numcontexts; ctxnum++)
+ {
+ huffman_context *context = contexts[ctxnum];
+ memset(context->datahisto, 0, sizeof(context->datahisto));
+ 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;
+
+ /* 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]++;
+ }
+ }
+ }
+
+ /* 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);
+ }
+ }
+
+ /* 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_deltarle_encode_data - encode data
+ using the given tree with delta-RLE
+ pre-encoding
+-------------------------------------------------*/
+
+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)
+{
+ 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
+-------------------------------------------------*/
+
+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)
+ {
+ 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);
+
+ /* iterate over "height" */
+ for (dy = 0; dy < dheight; dy++)
+ {
+ /* iterate over "width" */
+ for (dx = 0; dx < dwidth; dx++)
+ {
+ 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);
+ }
+
+ /* 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_decode_data_interleaved - decode
+ interleaved data using multiple contexts
+-------------------------------------------------*/
+
+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)
+{
+ UINT32 dx, dy, ctxnum;
+ huffman_error error;
+ bit_buffer bitbuf;
+
+ /* regenerate the lookup tables if necessary */
+ for (ctxnum = 0; ctxnum < numcontexts; ctxnum++)
+ {
+ huffman_context *context = contexts[ctxnum];
+ if (context->lookupdirty)
+ {
+ error = build_lookup_table(context, HUFFMAN_CODES);
+ if (error != HUFFERR_NONE)
+ return error;
+ }
+ }
+
+ /* 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; )
+ {
+ /* 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);
+ }
+ }
+
+ /* 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;
+
+ /* store the updated data value */
+ dest[dx ^ dxor] = prevdata;
+ }
+
+ /* 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 -
+ decode data using multiple contexts and
+ delta-RLE post-decoding
+-------------------------------------------------*/
+
+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)
+{
+ 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);
+
+ /* regenerate the lookup tables if necessary */
+ for (ctxnum = 0; ctxnum < numcontexts; ctxnum++)
+ {
+ huffman_context *context = contexts[ctxnum];
+ if (context->lookupdirty)
+ {
+ error = build_lookup_table(context, HUFFMAN_DELTARLE_CODES);
+ if (error != HUFFERR_NONE)
+ return error;
+ }
+ 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; )
+ {
+ /* 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;
+ }
+ }
+
+ /* 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)
+ {
+ error = build_lookup_table(contexts[1], HUFFMAN_DELTARLE_CODES);
+ if (error != HUFFERR_NONE)
+ return error;
+ }
+ 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);
+
+ /* 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)
+ {
+ 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 we have RLE remaining, just store that */
+ if (rleremaining3 != 0)
+ rleremaining3--;
+ 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;
+ }
+
+ /* 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;
+}
+
+
+
+/***************************************************************************
+ 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 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 < numcodes; )
+ {
+ 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 = 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;
+}
+
+
+/*-------------------------------------------------
+ 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;
+}
+
+
+/*-------------------------------------------------
+ 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)
+{
+ /* 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;
+ }
+ }
+}
+
+
+/*-------------------------------------------------
+ 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
+-------------------------------------------------*/
+
+static huffman_error compute_optimal_tree(huffman_context *context, const UINT32 *datahisto, UINT32 numcodes)
+{
+ 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);
+}
+
+
+/*-------------------------------------------------
+ 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, UINT32 numcodes)
+{
+ 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)
+ {
+ 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]), tree_node_compare);
+
+ /* now build the tree */
+ nextalloc = MAX_HUFFMAN_CODES;
+ 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 < numcodes; 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;
+}
+
+
+/*-------------------------------------------------
+ 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)
+{
+ 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++)
+ {
+ 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 < numcodes; 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;
+}
+
+
+/*-------------------------------------------------
+ build_lookup_table - build a lookup
+ table for fast decoding
+-------------------------------------------------*/
+
+static huffman_error build_lookup_table(huffman_context *context, UINT32 numcodes)
+{
+ 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++)
+ {
+ 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 << 6) | 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;
+}