/***************************************************************************

    huffman.c

    Video compression and decompression helpers.

    Copyright Nicola Salmoria and the MAME Team.
    Visit http://mamedev.org for licensing and usage restrictions.

****************************************************************************

    Maximum codelength is officially (alphabetsize - 1). This would be 255 bits
    (since we use 1 byte values). However, it is also dependent upon the number
    of samples used, as follows:

         2 bits -> 3..4 samples
         3 bits -> 5..7 samples
         4 bits -> 8..12 samples
         5 bits -> 13..20 samples
         6 bits -> 21..33 samples
         7 bits -> 34..54 samples
         8 bits -> 55..88 samples
         9 bits -> 89..143 samples
        10 bits -> 144..232 samples
        11 bits -> 233..376 samples
        12 bits -> 377..609 samples
        13 bits -> 610..986 samples
        14 bits -> 987..1596 samples
        15 bits -> 1597..2583 samples
        16 bits -> 2584..4180 samples   -> note that a 4k data size guarantees codelength <= 16 bits
        17 bits -> 4181..6764 samples
        18 bits -> 6765..10945 samples
        19 bits -> 10946..17710 samples
        20 bits -> 17711..28656 samples
        21 bits -> 28657..46367 samples
        22 bits -> 46368..75024 samples
        23 bits -> 75025..121392 samples
        24 bits -> 121393..196417 samples
        25 bits -> 196418..317810 samples
        26 bits -> 317811..514228 samples
        27 bits -> 514229..832039 samples
        28 bits -> 832040..1346268 samples
        29 bits -> 1346269..2178308 samples
        30 bits -> 2178309..3524577 samples
        31 bits -> 3524578..5702886 samples
        32 bits -> 5702887..9227464 samples

    Looking at it differently, here is where powers of 2 fall into these buckets:

          256 samples -> 11 bits max
          512 samples -> 12 bits max
           1k samples -> 14 bits max
           2k samples -> 15 bits max
           4k samples -> 16 bits max
           8k samples -> 18 bits max
          16k samples -> 19 bits max
          32k samples -> 21 bits max
          64k samples -> 22 bits max
         128k samples -> 24 bits max
         256k samples -> 25 bits max
         512k samples -> 27 bits max
           1M samples -> 28 bits max
           2M samples -> 29 bits max
           4M samples -> 31 bits max
           8M samples -> 32 bits max

****************************************************************************

    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 "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;
}
