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

    huffman.c

    Video compression and decompression helpers.

    Copyright (c) 1996-2007, Nicola Salmoria and the MAME Team.
    Visit http://mamedev.org for licensing and usage restrictions.

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

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

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

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

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

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

#include "huffman.h"



/***************************************************************************
    CONSTANTS
***************************************************************************/

#define MAX_HUFFMAN_NODES		(256 + 256)



/***************************************************************************
    TYPE DEFINITIONS
***************************************************************************/

typedef struct _bit_buffer bit_buffer;
struct _bit_buffer
{
	UINT32			buffer;
	int				bits;
	union
	{
		const UINT8 *read;
		UINT8 *		write;
	} data;
	UINT32			doffset;
	UINT32			dlength;
	int				overflow;
};


typedef struct _huffman_node huffman_node;
struct _huffman_node
{
	huffman_node *	parent;
	UINT32			count;
	UINT32			weight;
	UINT32			bits;
	UINT8			numbits;
};


struct _huffman_context
{
	UINT8			maxbits;
	UINT8			lookupdirty;
	huffman_node 	huffnode[MAX_HUFFMAN_NODES];
	UINT32			lookupmask;
	huffman_lookup_value *lookup;
};



/***************************************************************************
    PROTOTYPES
***************************************************************************/

static void huffman_write_rle_tree_bits(bit_buffer *bitbuf, int value, int repcount, int numbits);
static int CLIB_DECL huffman_tree_node_compare(const void *item1, const void *item2);
static int huffman_build_tree(huffman_context *context, const UINT32 *datahisto, UINT32 totaldata, UINT32 totalweight);
static huffman_error huffman_assign_canonical_codes(huffman_context *context);
static huffman_error huffman_build_lookup_table(huffman_context *context);



/***************************************************************************
    INLINE FUNCTIONS
***************************************************************************/

/*-------------------------------------------------
    bit_buffer_write_init - initialize a bit
    buffer for writing
-------------------------------------------------*/

INLINE void bit_buffer_write_init(bit_buffer *bitbuf, UINT8 *data, UINT32 dlength)
{
	/* fill in the basic data structure */
	bitbuf->buffer = 0;
	bitbuf->bits = 0;
	bitbuf->data.write = data;
	bitbuf->doffset = 0;
	bitbuf->dlength = dlength;
	bitbuf->overflow = FALSE;
}


/*-------------------------------------------------
    bit_buffer_write - write 'numbits' to the
    bit buffer, assuming that 'newbits' is right-
    justified
-------------------------------------------------*/

INLINE void bit_buffer_write(bit_buffer *bitbuf, UINT32 newbits, int numbits)
{
	/* flush the buffer if we're going to overflow it */
	if (bitbuf->bits + numbits > 32)
		while (bitbuf->bits >= 8)
		{
			if (bitbuf->doffset < bitbuf->dlength)
				bitbuf->data.write[bitbuf->doffset] = bitbuf->buffer >> 24;
			else
				bitbuf->overflow = TRUE;
			bitbuf->doffset++;
			bitbuf->buffer <<= 8;
			bitbuf->bits -= 8;
		}

	/* shift the bits to the top */
	newbits <<= 32 - numbits;

	/* now shift it down to account for the number of bits we already have and OR them in */
	bitbuf->buffer |= newbits >> bitbuf->bits;
	bitbuf->bits += numbits;
}


/*-------------------------------------------------
    bit_buffer_flush - flush any bits in the write
    buffer and return the final data offset
-------------------------------------------------*/

INLINE UINT32 bit_buffer_flush(bit_buffer *bitbuf)
{
	while (bitbuf->bits > 0)
	{
		if (bitbuf->doffset < bitbuf->dlength)
			bitbuf->data.write[bitbuf->doffset] = bitbuf->buffer >> 24;
		else
			bitbuf->overflow = TRUE;
		bitbuf->doffset++;
		bitbuf->buffer <<= 8;
		bitbuf->bits -= 8;
	}
	return bitbuf->doffset;
}


/*-------------------------------------------------
    bit_buffer_read_init - initialize a bit
    buffer for reading
-------------------------------------------------*/

INLINE void bit_buffer_read_init(bit_buffer *bitbuf, const UINT8 *data, UINT32 dlength)
{
	/* fill in the basic data structure */
	bitbuf->buffer = 0;
	bitbuf->bits = 0;
	bitbuf->data.read = data;
	bitbuf->doffset = 0;
	bitbuf->dlength = dlength;
	bitbuf->overflow = FALSE;
}


/*-------------------------------------------------
    bit_buffer_read - read 'numbits' bits from
    the buffer, returning the right-justified
-------------------------------------------------*/

INLINE UINT32 bit_buffer_read(bit_buffer *bitbuf, int numbits)
{
	UINT32 result;

	/* fetch data if we need more */
	if (numbits > bitbuf->bits)
	{
		while (bitbuf->bits <= 24)
		{
			if (bitbuf->doffset < bitbuf->dlength)
				bitbuf->buffer |= bitbuf->data.read[bitbuf->doffset] << (24 - bitbuf->bits);
			bitbuf->doffset++;
			bitbuf->bits += 8;
		}
		if (numbits > bitbuf->bits)
			bitbuf->overflow = TRUE;
	}

	/* return the data */
	result = bitbuf->buffer >> (32 - numbits);
	bitbuf->buffer <<= numbits;
	bitbuf->bits -= numbits;
	return result;
}


/*-------------------------------------------------
    bit_buffer_read_offset - return the current
    rounded byte reading offset
-------------------------------------------------*/

INLINE UINT32 bit_buffer_read_offset(bit_buffer *bitbuf)
{
	UINT32 result = bitbuf->doffset;
	int bits = bitbuf->bits;
	while (bits >= 8)
	{
		result--;
		bits -= 8;
	}
	return result;
}



/***************************************************************************
    IMPLEMENTATION
***************************************************************************/

/*-------------------------------------------------
    huffman_create_context - create an encoding/
    decoding context
-------------------------------------------------*/

huffman_error huffman_create_context(huffman_context **context, int maxbits)
{
	/* limit to 24 bits */
	if (maxbits > 24)
		return HUFFERR_TOO_MANY_BITS;

	/* allocate a context */
	*context = malloc(sizeof(**context));
	if (*context == NULL)
		return HUFFERR_OUT_OF_MEMORY;

	/* set the info */
	memset(*context, 0, sizeof(**context));
	(*context)->maxbits = maxbits;
	(*context)->lookupmask = (1 << maxbits) - 1;
	(*context)->lookupdirty = TRUE;

	return HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_free_context - free an encoding/
    decoding context
-------------------------------------------------*/

void huffman_free_context(huffman_context *context)
{
	if (context->lookup != NULL)
		free(context->lookup);
	free(context);
}


/*-------------------------------------------------
    huffman_compute_tree - compute an optimal
    huffman tree for the given source data
-------------------------------------------------*/

huffman_error huffman_compute_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 sstride)
{
	UINT32 lowerweight, upperweight;
	UINT32 datahisto[256];
	int i;

	/* build the data histogram */
	memset(datahisto, 0, sizeof(datahisto));
	for (i = 0; i < slength; i += sstride)
		datahisto[source[i]]++;

	/* binary search to achieve the optimum encoding */
	lowerweight = 0;
	upperweight = slength * 2;
	while (TRUE)
	{
		UINT32 curweight = (upperweight + lowerweight) / 2;
		int curmaxbits;

		/* build a tree using the current weight */
		curmaxbits = huffman_build_tree(context, datahisto, slength, curweight);

		/* apply binary search here */
		if (curmaxbits <= context->maxbits)
		{
			lowerweight = curweight;

			/* early out if it worked with the raw weights, or if we're done searching */
			if (curweight == slength || (upperweight - lowerweight) <= 1)
				break;
		}
		else
			upperweight = curweight;
	}

	/* assign canonical codes for all nodes based on their code lengths */
	return huffman_assign_canonical_codes(context);
}


/*-------------------------------------------------
    huffman_import_tree - import a huffman tree
    from a source data stream
-------------------------------------------------*/

huffman_error huffman_import_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 *actlength)
{
	huffman_error error;
	bit_buffer bitbuf;
	int curnode;
	int numbits;

	/* initialize the input buffer */
	bit_buffer_read_init(&bitbuf, source, slength);

	/* bits per entry depends on the maxbits */
	if (context->maxbits >= 16)
		numbits = 5;
	else if (context->maxbits >= 8)
		numbits = 4;
	else
		numbits = 3;

	/* loop until we read all the nodes */
	for (curnode = 0; curnode < 256; )
	{
		int nodebits = bit_buffer_read(&bitbuf, numbits);

		/* a non-one value is just raw */
		if (nodebits != 1)
			context->huffnode[curnode++].numbits = nodebits;

		/* a one value is an escape code */
		else
		{
			nodebits = bit_buffer_read(&bitbuf, numbits);

			/* a double 1 is just a single 1 */
			if (nodebits == 1)
				context->huffnode[curnode++].numbits = nodebits;

			/* otherwise, we need one for value for the repeat count */
			else
			{
				int repcount = bit_buffer_read(&bitbuf, numbits) + 3;
				while (repcount--)
					context->huffnode[curnode++].numbits = nodebits;
			}
		}
	}

	/* assign canonical codes for all nodes based on their code lengths */
	error = huffman_assign_canonical_codes(context);
	if (error != HUFFERR_NONE)
		return error;

	/* make sure we ended up with the right number */
	if (curnode != 256)
		return HUFFERR_INVALID_DATA;

	*actlength = bit_buffer_read_offset(&bitbuf);
	return bitbuf.overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_export_tree - export a huffman tree
    to a target data stream
-------------------------------------------------*/

huffman_error huffman_export_tree(huffman_context *context, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
{
	bit_buffer bitbuf;
	int repcount;
	int lastval;
	int numbits;
	int i;

	/* initialize the output buffer */
	bit_buffer_write_init(&bitbuf, dest, dlength);

	/* bits per entry depends on the maxbits */
	if (context->maxbits >= 16)
		numbits = 5;
	else if (context->maxbits >= 8)
		numbits = 4;
	else
		numbits = 3;

	/* RLE encode the lengths */
	lastval = ~0;
	repcount = 0;
	for (i = 0; i < 256; i++)
	{
		int newval = context->huffnode[i].numbits;

		/* if we match the previous value, just bump the repcount */
		if (newval == lastval)
			repcount++;

		/* otherwise, we need to flush the previous repeats */
		else
		{
			if (repcount != 0)
				huffman_write_rle_tree_bits(&bitbuf, lastval, repcount, numbits);
			lastval = newval;
			repcount = 1;
		}
	}

	/* flush the last value */
	huffman_write_rle_tree_bits(&bitbuf, lastval, repcount, numbits);
	*actlength = bit_buffer_flush(&bitbuf);
	return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_get_lookup_table - return a pointer to
    the lookup table
-------------------------------------------------*/

huffman_error huffman_get_lookup_table(huffman_context *context, const huffman_lookup_value **table)
{
	if (context->lookupdirty)
	{
		huffman_error error = huffman_build_lookup_table(context);
		if (error != HUFFERR_NONE)
			return error;
	}
	*table = context->lookup;
	return HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_encode_data - encode data using the
    current tree
-------------------------------------------------*/

huffman_error huffman_encode_data(huffman_context *context, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
{
	bit_buffer bitbuf;
	UINT32 soffset;

	/* initialize the output buffer */
	bit_buffer_write_init(&bitbuf, dest, dlength);

	/* loop over source data and encode */
	for (soffset = 0; soffset < slength; soffset++)
	{
		huffman_node *node = &context->huffnode[source[soffset]];
		bit_buffer_write(&bitbuf, node->bits, node->numbits);
	}
	*actlength = bit_buffer_flush(&bitbuf);
	return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_encode_data_interleaved_2 - encode
    alternating data with two contexts
-------------------------------------------------*/

huffman_error huffman_encode_data_interleaved_2(huffman_context *context1, huffman_context *context2, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
{
	bit_buffer bitbuf;
	UINT32 soffset;

	/* initialize the output buffer */
	bit_buffer_write_init(&bitbuf, dest, dlength);

	/* loop over source data and encode */
	for (soffset = 0; soffset < slength; soffset += 2)
	{
		huffman_node *node;

		node = &context1->huffnode[source[soffset + 0]];
		bit_buffer_write(&bitbuf, node->bits, node->numbits);

		node = &context2->huffnode[source[soffset + 1]];
		bit_buffer_write(&bitbuf, node->bits, node->numbits);
	}
	*actlength = bit_buffer_flush(&bitbuf);
	return bitbuf.overflow ? HUFFERR_OUTPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_decode_data - decode data using the
    current tree
-------------------------------------------------*/

huffman_error huffman_decode_data(huffman_context *context, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
{
	int maxbits = context->maxbits;
	int shiftbits = 32 - maxbits;
	const huffman_lookup_value *table;
	int overflow = FALSE;
	huffman_error error;
	UINT32 doffset = 0;
	UINT32 soffset = 0;
	UINT32 bitbuf = 0;
	int sbits = 0;

	/* regenerate the lookup table if necessary */
	error = huffman_get_lookup_table(context, &table);
	if (error != HUFFERR_NONE)
		return error;

	/* decode until we process all of the destination data */
	for (doffset = 0; doffset < dlength; doffset++)
	{
		huffman_lookup_value lookup;

		/* if we don't have enough bits, load up the buffer */
		if (sbits < maxbits)
		{
			while (sbits <= 24)
			{
				if (soffset < slength)
					bitbuf |= source[soffset] << (24 - sbits);
				soffset++;
				sbits += 8;
			}
			if (sbits < maxbits)
				overflow = TRUE;
		}

		/* lookup the data */
		lookup = table[bitbuf >> shiftbits];

		/* store the upper byte */
		dest[doffset] = lookup >> 8;

		/* count the bits */
		lookup &= 0x1f;
		bitbuf <<= lookup;
		sbits -= lookup;
	}

	/* back off soffset while we have whole bytes */
	while (sbits >= 8)
	{
		sbits -= 8;
		soffset--;
	}
	*actlength = soffset;
	return overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_decode_data_interleaved_2 - decode
    interleaved data using two contexts
-------------------------------------------------*/

huffman_error huffman_decode_data_interleaved_2(huffman_context *context1, huffman_context *context2, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dlength, UINT32 *actlength)
{
	int maxbits1 = context1->maxbits, maxbits2 = context2->maxbits;
	const huffman_lookup_value *table1, *table2;
	int shiftbits1 = 32 - maxbits1;
	int shiftbits2 = 32 - maxbits2;
	int overflow = FALSE;
	huffman_error error;
	UINT32 doffset = 0;
	UINT32 soffset = 0;
	UINT32 bitbuf = 0;
	int sbits = 0;

	/* regenerate the lookup table if necessary */
	error = huffman_get_lookup_table(context1, &table1);
	if (error != HUFFERR_NONE)
		return error;
	error = huffman_get_lookup_table(context2, &table2);
	if (error != HUFFERR_NONE)
		return error;

	/* decode until we process all of the destination data */
	for (doffset = 0; doffset < dlength; doffset += 2)
	{
		huffman_lookup_value lookup;

		/* if we don't have enough bits, load up the buffer */
		if (sbits < maxbits1)
		{
			while (sbits <= 24)
			{
				if (soffset < slength)
					bitbuf |= source[soffset] << (24 - sbits);
				soffset++;
				sbits += 8;
			}
			if (sbits < maxbits1)
				overflow = TRUE;
		}

		/* lookup the data */
		lookup = table1[bitbuf >> shiftbits1];

		/* store the upper byte */
		dest[doffset + 0] = lookup >> 8;

		/* count the bits */
		lookup &= 0x1f;
		bitbuf <<= lookup;
		sbits -= lookup;

		/* if we don't have enough bits, load up the buffer */
		if (sbits < maxbits2)
		{
			while (sbits <= 24)
			{
				if (soffset < slength)
					bitbuf |= source[soffset] << (24 - sbits);
				soffset++;
				sbits += 8;
			}
			if (sbits < maxbits2)
				overflow = TRUE;
		}

		/* lookup the data */
		lookup = table2[bitbuf >> shiftbits2];

		/* store the upper byte */
		dest[doffset + 1] = lookup >> 8;

		/* count the bits */
		lookup &= 0x1f;
		bitbuf <<= lookup;
		sbits -= lookup;
	}

	/* back off soffset while we have whole bytes */
	while (sbits >= 8)
	{
		sbits -= 8;
		soffset--;
	}
	*actlength = soffset;
	return overflow ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_write_rle_tree_bits - write an RLE
    encoded set of data to a target stream
-------------------------------------------------*/

static void huffman_write_rle_tree_bits(bit_buffer *bitbuf, int value, int repcount, int numbits)
{
	/* loop until we have output all of the repeats */
	while (repcount > 0)
	{
		/* if we have a 1, write it twice as it is an escape code */
		if (value == 1)
		{
			bit_buffer_write(bitbuf, 1, numbits);
			bit_buffer_write(bitbuf, 1, numbits);
			repcount--;
		}

		/* if we have two or fewer in a row, write them raw */
		else if (repcount <= 2)
		{
			bit_buffer_write(bitbuf, value, numbits);
			repcount--;
		}

		/* otherwise, write a triple using 1 as the escape code */
		else
		{
			int cur_reps = MIN(repcount - 3, (1 << numbits) - 1);
			bit_buffer_write(bitbuf, 1, numbits);
			bit_buffer_write(bitbuf, value, numbits);
			bit_buffer_write(bitbuf, cur_reps, numbits);
			repcount -= cur_reps + 3;
		}
	}
}


/*-------------------------------------------------
    huffman_tree_node_compare - compare two
    tree nodes by weight
-------------------------------------------------*/

static int CLIB_DECL huffman_tree_node_compare(const void *item1, const void *item2)
{
	const huffman_node *node1 = *(const huffman_node **)item1;
	const huffman_node *node2 = *(const huffman_node **)item2;
	return node2->weight - node1->weight;
}


/*-------------------------------------------------
    huffman_build_tree - build a huffman tree
    based on the data distribution
-------------------------------------------------*/

static int huffman_build_tree(huffman_context *context, const UINT32 *datahisto, UINT32 totaldata, UINT32 totalweight)
{
	huffman_node *list[256];
	int listitems;
	int nextalloc;
	int maxbits;
	int i;

	/* make a list of all non-zero nodes */
	listitems = 0;
	memset(context->huffnode, 0, 256 * sizeof(context->huffnode[0]));
	for (i = 0; i < 256; i++)
		if (datahisto[i] != 0)
		{
			list[listitems++] = &context->huffnode[i];
			context->huffnode[i].count = datahisto[i];

			/* scale the weight by the current effective length, ensuring we don't go to 0 */
			context->huffnode[i].weight = (UINT64)datahisto[i] * (UINT64)totalweight / (UINT64)totaldata;
			if (context->huffnode[i].weight == 0)
				context->huffnode[i].weight = 1;
		}

	/* sort the list by weight, largest weight first */
	qsort(list, listitems, sizeof(list[0]), huffman_tree_node_compare);

	/* now build the tree */
	nextalloc = 256;
	while (listitems > 1)
	{
		huffman_node *node0, *node1, *newnode;

		/* remove lowest two items */
		node1 = list[--listitems];
		node0 = list[--listitems];

		/* create new node */
		newnode = &context->huffnode[nextalloc++];
		newnode->parent = NULL;
		node0->parent = node1->parent = newnode;
		newnode->weight = node0->weight + node1->weight;

		/* insert into list at appropriate location */
		for (i = 0; i < listitems; i++)
			if (newnode->weight > list[i]->weight)
			{
				memmove(&list[i+1], &list[i], (listitems - i) * sizeof(list[0]));
				break;
			}
		list[i] = newnode;
		listitems++;
	}

	/* compute the number of bits in each code, and fill in another histogram */
	maxbits = 0;
	for (i = 0; i < 256; i++)
	{
		huffman_node *node = &context->huffnode[i];
		node->numbits = 0;

		/* if we have a non-zero weight, compute the number of bits */
		if (node->weight > 0)
		{
			huffman_node *curnode;

			/* determine the number of bits for this node */
			for (curnode = node; curnode->parent != NULL; curnode = curnode->parent)
				node->numbits++;
			if (node->numbits == 0)
				node->numbits = 1;

			/* keep track of the max */
			maxbits = MAX(maxbits, node->numbits);
		}
	}

	return maxbits;
}


/*-------------------------------------------------
    huffman_assign_canonical_codes - assign
    canonical codes to all the nodes based on the
    number of bits in each
-------------------------------------------------*/

static huffman_error huffman_assign_canonical_codes(huffman_context *context)
{
	UINT32 bithisto[33];
	int curstart;
	int i;

	/* build up a histogram of bit lengths */
	memset(bithisto, 0, sizeof(bithisto));
	for (i = 0; i < 256; i++)
	{
		huffman_node *node = &context->huffnode[i];
		if (node->numbits > context->maxbits)
			return HUFFERR_INTERNAL_INCONSISTENCY;
		if (node->numbits <= 32)
			bithisto[node->numbits]++;
	}

	/* for each code length, determine the starting code number */
	curstart = 0;
	for (i = 32; i > 0; i--)
	{
		UINT32 nextstart = (curstart + bithisto[i]) >> 1;
		if (i != 1 && nextstart * 2 != (curstart + bithisto[i]))
			return HUFFERR_INTERNAL_INCONSISTENCY;
		bithisto[i] = curstart;
		curstart = nextstart;
	}

	/* now assign canonical codes */
	for (i = 0; i < 256; i++)
	{
		huffman_node *node = &context->huffnode[i];
		if (node->numbits > 0)
			node->bits = bithisto[node->numbits]++;
	}

	/* if there was a decoding table, get rid of it now */
	context->lookupdirty = TRUE;
	return HUFFERR_NONE;
}


/*-------------------------------------------------
    huffman_build_lookup_table - build a lookup
    table for fast decoding
-------------------------------------------------*/

static huffman_error huffman_build_lookup_table(huffman_context *context)
{
	int i;

	/* allocate a table if needed */
	if (context->lookup == NULL)
		context->lookup = malloc((UINT32)sizeof(context->lookup[0]) * (UINT32)(1 << context->maxbits));
	if (context->lookup == NULL)
		return HUFFERR_OUT_OF_MEMORY;

	/* now build */
	for (i = 0; i < 256; i++)
	{
		huffman_node *node = &context->huffnode[i];
		if (node->numbits > 0)
		{
			huffman_lookup_value *dest, *destend;

			/* left justify this node's bit values to max bits */
			int shift = context->maxbits - node->numbits;
			UINT32 start = node->bits << shift;
			UINT32 end = ((node->bits + 1) << shift) - 1;
			huffman_lookup_value value;

			/* set up the entry */
			value = (i << 8) | node->numbits;

			/* fill all matching entries */
			dest = &context->lookup[start];
			destend = &context->lookup[end];
			while (dest <= destend)
				*dest++ = value;
		}
	}

	/* no longer dirty */
	context->lookupdirty = FALSE;
	return HUFFERR_NONE;
}
