Merge pull request #423 from jdgleaver/set-message-ext

[pcsx_rearmed.git] / deps / libchdr / huffman.c

// license:BSD-3-Clause\r
// copyright-holders:Aaron Giles\r
/***************************************************************************\r
\r
    huffman.c\r
\r
    Static Huffman compression and decompression helpers.\r
\r
****************************************************************************\r
\r
    Maximum codelength is officially (alphabetsize - 1). This would be 255 bits\r
    (since we use 1 byte values). However, it is also dependent upon the number\r
    of samples used, as follows:\r
\r
         2 bits -> 3..4 samples\r
         3 bits -> 5..7 samples\r
         4 bits -> 8..12 samples\r
         5 bits -> 13..20 samples\r
         6 bits -> 21..33 samples\r
         7 bits -> 34..54 samples\r
         8 bits -> 55..88 samples\r
         9 bits -> 89..143 samples\r
        10 bits -> 144..232 samples\r
        11 bits -> 233..376 samples\r
        12 bits -> 377..609 samples\r
        13 bits -> 610..986 samples\r
        14 bits -> 987..1596 samples\r
        15 bits -> 1597..2583 samples\r
        16 bits -> 2584..4180 samples   -> note that a 4k data size guarantees codelength <= 16 bits\r
        17 bits -> 4181..6764 samples\r
        18 bits -> 6765..10945 samples\r
        19 bits -> 10946..17710 samples\r
        20 bits -> 17711..28656 samples\r
        21 bits -> 28657..46367 samples\r
        22 bits -> 46368..75024 samples\r
        23 bits -> 75025..121392 samples\r
        24 bits -> 121393..196417 samples\r
        25 bits -> 196418..317810 samples\r
        26 bits -> 317811..514228 samples\r
        27 bits -> 514229..832039 samples\r
        28 bits -> 832040..1346268 samples\r
        29 bits -> 1346269..2178308 samples\r
        30 bits -> 2178309..3524577 samples\r
        31 bits -> 3524578..5702886 samples\r
        32 bits -> 5702887..9227464 samples\r
\r
    Looking at it differently, here is where powers of 2 fall into these buckets:\r
\r
          256 samples -> 11 bits max\r
          512 samples -> 12 bits max\r
           1k samples -> 14 bits max\r
           2k samples -> 15 bits max\r
           4k samples -> 16 bits max\r
           8k samples -> 18 bits max\r
          16k samples -> 19 bits max\r
          32k samples -> 21 bits max\r
          64k samples -> 22 bits max\r
         128k samples -> 24 bits max\r
         256k samples -> 25 bits max\r
         512k samples -> 27 bits max\r
           1M samples -> 28 bits max\r
           2M samples -> 29 bits max\r
           4M samples -> 31 bits max\r
           8M samples -> 32 bits max\r
\r
****************************************************************************\r
\r
    Delta-RLE encoding works as follows:\r
\r
    Starting value is assumed to be 0. All data is encoded as a delta\r
    from the previous value, such that final[i] = final[i - 1] + delta.\r
    Long runs of 0s are RLE-encoded as follows:\r
\r
        0x100 = repeat count of 8\r
        0x101 = repeat count of 9\r
        0x102 = repeat count of 10\r
        0x103 = repeat count of 11\r
        0x104 = repeat count of 12\r
        0x105 = repeat count of 13\r
        0x106 = repeat count of 14\r
        0x107 = repeat count of 15\r
        0x108 = repeat count of 16\r
        0x109 = repeat count of 32\r
        0x10a = repeat count of 64\r
        0x10b = repeat count of 128\r
        0x10c = repeat count of 256\r
        0x10d = repeat count of 512\r
        0x10e = repeat count of 1024\r
        0x10f = repeat count of 2048\r
\r
    Note that repeat counts are reset at the end of a row, so if a 0 run\r
    extends to the end of a row, a large repeat count may be used.\r
\r
    The reason for starting the run counts at 8 is that 0 is expected to\r
    be the most common symbol, and is typically encoded in 1 or 2 bits.\r
\r
***************************************************************************/\r
\r
#include <stdlib.h>\r
#include <assert.h>\r
#include <stdio.h>\r
#include <string.h>\r
\r
#include "huffman.h"\r
\r
#define MAX(x,y) ((x) > (y) ? (x) : (y))\r
\r
//**************************************************************************\r
//  MACROS\r
//**************************************************************************\r
\r
#define MAKE_LOOKUP(code,bits)  (((code) << 5) | ((bits) & 0x1f))\r
\r
\r
//**************************************************************************\r
//  IMPLEMENTATION\r
//**************************************************************************\r
\r
//-------------------------------------------------\r
//  huffman_context_base - create an encoding/\r
//  decoding context\r
//-------------------------------------------------\r
\r
struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits)\r
{\r
   struct huffman_decoder* decoder;\r
\r
	/* limit to 24 bits */\r
	if (maxbits > 24)\r
		return NULL;\r
\r
	decoder = (struct huffman_decoder*)malloc(sizeof(struct huffman_decoder));\r
	decoder->numcodes = numcodes;\r
	decoder->maxbits = maxbits;\r
	decoder->lookup = (lookup_value*)malloc(sizeof(lookup_value) * (1 << maxbits));\r
	decoder->huffnode = (struct node_t*)malloc(sizeof(struct node_t) * numcodes);\r
	decoder->datahisto = NULL;\r
	decoder->prevdata = 0;\r
	decoder->rleremaining = 0;\r
	return decoder;\r
}\r
\r
//-------------------------------------------------\r
//  decode_one - decode a single code from the\r
//  huffman stream\r
//-------------------------------------------------\r
\r
uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
{\r
	/* peek ahead to get maxbits worth of data */\r
	uint32_t bits = bitstream_peek(bitbuf, decoder->maxbits);\r
\r
	/* look it up, then remove the actual number of bits for this code */\r
	lookup_value lookup = decoder->lookup[bits];\r
	bitstream_remove(bitbuf, lookup & 0x1f);\r
\r
	/* return the value */\r
	return lookup >> 5;\r
}\r
\r
//-------------------------------------------------\r
//  import_tree_rle - import an RLE-encoded\r
//  huffman tree from a source data stream\r
//-------------------------------------------------\r
\r
enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
{\r
   enum huffman_error error;\r
	int curnode;\r
	// bits per entry depends on the maxbits\r
	int numbits;\r
	if (decoder->maxbits >= 16)\r
		numbits = 5;\r
	else if (decoder->maxbits >= 8)\r
		numbits = 4;\r
	else\r
		numbits = 3;\r
\r
	// loop until we read all the nodes\r
	for (curnode = 0; curnode < decoder->numcodes; )\r
	{\r
		// a non-one value is just raw\r
		int nodebits = bitstream_read(bitbuf, numbits);\r
		if (nodebits != 1)\r
			decoder->huffnode[curnode++].numbits = nodebits;\r
\r
		// a one value is an escape code\r
		else\r
		{\r
			// a double 1 is just a single 1\r
			nodebits = bitstream_read(bitbuf, numbits);\r
			if (nodebits == 1)\r
				decoder->huffnode[curnode++].numbits = nodebits;\r
\r
			// otherwise, we need one for value for the repeat count\r
			else\r
			{\r
				int repcount = bitstream_read(bitbuf, numbits) + 3;\r
				while (repcount--)\r
					decoder->huffnode[curnode++].numbits = nodebits;\r
			}\r
		}\r
	}\r
\r
	// make sure we ended up with the right number\r
	if (curnode != decoder->numcodes)\r
		return HUFFERR_INVALID_DATA;\r
\r
	// assign canonical codes for all nodes based on their code lengths\r
	error = huffman_assign_canonical_codes(decoder);\r
	if (error != HUFFERR_NONE)\r
		return error;\r
\r
	// build the lookup table\r
	huffman_build_lookup_table(decoder);\r
\r
	// determine final input length and report errors\r
	return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;\r
}\r
\r
\r
//-------------------------------------------------\r
//  import_tree_huffman - import a huffman-encoded\r
//  huffman tree from a source data stream\r
//-------------------------------------------------\r
\r
enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
{\r
   int index;\r
   int start;\r
	int count = 0;\r
	uint8_t rlefullbits = 0;\r
	int last = 0;\r
	int curcode;\r
   enum huffman_error error;\r
   uint32_t temp;\r
	// start by parsing the lengths for the small tree\r
	struct huffman_decoder* smallhuff = create_huffman_decoder(24, 6);\r
\r
	smallhuff->huffnode[0].numbits = bitstream_read(bitbuf, 3);\r
	start = bitstream_read(bitbuf, 3) + 1;\r
\r
	for (index = 1; index < 24; index++)\r
	{\r
		if (index < start || count == 7)\r
			smallhuff->huffnode[index].numbits = 0;\r
		else\r
		{\r
			count = bitstream_read(bitbuf, 3);\r
			smallhuff->huffnode[index].numbits = (count == 7) ? 0 : count;\r
		}\r
	}\r
\r
	// then regenerate the tree\r
	error = huffman_assign_canonical_codes(smallhuff);\r
	if (error != HUFFERR_NONE)\r
		return error;\r
	huffman_build_lookup_table(smallhuff);\r
\r
	// determine the maximum length of an RLE count\r
	temp = decoder->numcodes - 9;\r
	while (temp != 0)\r
		temp >>= 1, rlefullbits++;\r
\r
	// now process the rest of the data\r
	for (curcode = 0; curcode < decoder->numcodes; )\r
	{\r
		int value = huffman_decode_one(smallhuff, bitbuf);\r
		if (value != 0)\r
			decoder->huffnode[curcode++].numbits = last = value - 1;\r
		else\r
		{\r
			int count = bitstream_read(bitbuf, 3) + 2;\r
			if (count == 7+2)\r
				count += bitstream_read(bitbuf, rlefullbits);\r
			for ( ; count != 0 && curcode < decoder->numcodes; count--)\r
				decoder->huffnode[curcode++].numbits = last;\r
		}\r
	}\r
\r
	// make sure we ended up with the right number\r
	if (curcode != decoder->numcodes)\r
		return HUFFERR_INVALID_DATA;\r
\r
	// assign canonical codes for all nodes based on their code lengths\r
	error = huffman_assign_canonical_codes(decoder);\r
	if (error != HUFFERR_NONE)\r
		return error;\r
\r
	// build the lookup table\r
	huffman_build_lookup_table(decoder);\r
\r
	// determine final input length and report errors\r
	return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;\r
}\r
\r
\r
//-------------------------------------------------\r
//  compute_tree_from_histo - common backend for\r
//  computing a tree based on the data histogram\r
//-------------------------------------------------\r
\r
enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder)\r
{\r
   int i;\r
   uint32_t upperweight;\r
	uint32_t lowerweight = 0;\r
	// compute the number of data items in the histogram\r
	uint32_t sdatacount = 0;\r
	for (i = 0; i < decoder->numcodes; i++)\r
		sdatacount += decoder->datahisto[i];\r
\r
	// binary search to achieve the optimum encoding\r
	upperweight = sdatacount * 2;\r
	while (1)\r
	{\r
		// build a tree using the current weight\r
		uint32_t curweight = (upperweight + lowerweight) / 2;\r
		int curmaxbits = huffman_build_tree(decoder, sdatacount, curweight);\r
\r
		// apply binary search here\r
		if (curmaxbits <= decoder->maxbits)\r
		{\r
			lowerweight = curweight;\r
\r
			// early out if it worked with the raw weights, or if we're done searching\r
			if (curweight == sdatacount || (upperweight - lowerweight) <= 1)\r
				break;\r
		}\r
		else\r
			upperweight = curweight;\r
	}\r
\r
	// assign canonical codes for all nodes based on their code lengths\r
	return huffman_assign_canonical_codes(decoder);\r
}\r
\r
\r
\r
//**************************************************************************\r
//  INTERNAL FUNCTIONS\r
//**************************************************************************\r
\r
//-------------------------------------------------\r
//  tree_node_compare - compare two tree nodes\r
//  by weight\r
//-------------------------------------------------\r
\r
static int huffman_tree_node_compare(const void *item1, const void *item2)\r
{\r
	const struct node_t *node1 = *(const struct node_t **)item1;\r
	const struct node_t *node2 = *(const struct node_t **)item2;\r
	if (node2->weight != node1->weight)\r
		return node2->weight - node1->weight;\r
	if (node2->bits - node1->bits == 0)\r
		fprintf(stderr, "identical node sort keys, should not happen!\n");\r
	return (int)node1->bits - (int)node2->bits;\r
}\r
\r
\r
//-------------------------------------------------\r
//  build_tree - build a huffman tree based on the\r
//  data distribution\r
//-------------------------------------------------\r
\r
int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight)\r
{\r
   int curcode;\r
   int nextalloc;\r
	int maxbits = 0;\r
	// make a list of all non-zero nodes\r
	struct node_t** list = (struct node_t**)malloc(sizeof(struct node_t*) * decoder->numcodes * 2);\r
	int listitems = 0;\r
	memset(decoder->huffnode, 0, decoder->numcodes * sizeof(decoder->huffnode[0]));\r
	for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
		if (decoder->datahisto[curcode] != 0)\r
		{\r
			list[listitems++] = &decoder->huffnode[curcode];\r
			decoder->huffnode[curcode].count = decoder->datahisto[curcode];\r
			decoder->huffnode[curcode].bits = curcode;\r
\r
			// scale the weight by the current effective length, ensuring we don't go to 0\r
			decoder->huffnode[curcode].weight = ((uint64_t)decoder->datahisto[curcode]) * ((uint64_t)totalweight) / ((uint64_t)totaldata);\r
			if (decoder->huffnode[curcode].weight == 0)\r
				decoder->huffnode[curcode].weight = 1;\r
		}\r
/*\r
        fprintf(stderr, "Pre-sort:\n");\r
        for (int i = 0; i < listitems; i++) {\r
            fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);\r
        }\r
*/\r
	// sort the list by weight, largest weight first\r
	qsort(&list[0], listitems, sizeof(list[0]), huffman_tree_node_compare);\r
/*\r
        fprintf(stderr, "Post-sort:\n");\r
        for (int i = 0; i < listitems; i++) {\r
            fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);\r
        }\r
        fprintf(stderr, "===================\n");\r
*/\r
	// now build the tree\r
	nextalloc = decoder->numcodes;\r
\r
	while (listitems > 1)\r
	{\r
		int curitem;\r
		// remove lowest two items\r
		struct node_t* node1 = &(*list[--listitems]);\r
		struct node_t* node0 = &(*list[--listitems]);\r
\r
		// create new node\r
		struct node_t* newnode = &decoder->huffnode[nextalloc++];\r
		newnode->parent = NULL;\r
		node0->parent = node1->parent = newnode;\r
		newnode->weight = node0->weight + node1->weight;\r
\r
		// insert into list at appropriate location\r
		for (curitem = 0; curitem < listitems; curitem++)\r
			if (newnode->weight > list[curitem]->weight)\r
			{\r
				memmove(&list[curitem+1], &list[curitem], (listitems - curitem) * sizeof(list[0]));\r
				break;\r
			}\r
		list[curitem] = newnode;\r
		listitems++;\r
	}\r
\r
	// compute the number of bits in each code, and fill in another histogram\r
	for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
	{\r
		struct node_t* node = &decoder->huffnode[curcode];\r
		node->numbits = 0;\r
		node->bits = 0;\r
\r
		// if we have a non-zero weight, compute the number of bits\r
		if (node->weight > 0)\r
		{\r
         struct node_t *curnode;\r
			// determine the number of bits for this node\r
			for (curnode = node; curnode->parent != NULL; curnode = curnode->parent)\r
				node->numbits++;\r
			if (node->numbits == 0)\r
				node->numbits = 1;\r
\r
			// keep track of the max\r
			maxbits = MAX(maxbits, ((int)node->numbits));\r
		}\r
	}\r
	return maxbits;\r
}\r
\r
\r
//-------------------------------------------------\r
//  assign_canonical_codes - assign canonical codes\r
//  to all the nodes based on the number of bits\r
//  in each\r
//-------------------------------------------------\r
\r
enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder)\r
{\r
   int curcode, codelen;\r
	uint32_t curstart = 0;\r
\r
	// build up a histogram of bit lengths\r
	uint32_t bithisto[33] = { 0 };\r
	for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
	{\r
		struct node_t* node = &decoder->huffnode[curcode];\r
		if (node->numbits > decoder->maxbits)\r
			return HUFFERR_INTERNAL_INCONSISTENCY;\r
		if (node->numbits <= 32)\r
			bithisto[node->numbits]++;\r
	}\r
\r
	// for each code length, determine the starting code number\r
	for (codelen = 32; codelen > 0; codelen--)\r
	{\r
		uint32_t nextstart = (curstart + bithisto[codelen]) >> 1;\r
		if (codelen != 1 && nextstart * 2 != (curstart + bithisto[codelen]))\r
			return HUFFERR_INTERNAL_INCONSISTENCY;\r
		bithisto[codelen] = curstart;\r
		curstart = nextstart;\r
	}\r
\r
	// now assign canonical codes\r
	for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
	{\r
		struct node_t* node = &decoder->huffnode[curcode];\r
		if (node->numbits > 0)\r
			node->bits = bithisto[node->numbits]++;\r
	}\r
	return HUFFERR_NONE;\r
}\r
\r
\r
//-------------------------------------------------\r
//  build_lookup_table - build a lookup table for\r
//  fast decoding\r
//-------------------------------------------------\r
\r
void huffman_build_lookup_table(struct huffman_decoder* decoder)\r
{\r
   int curcode;\r
	// iterate over all codes\r
	for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
	{\r
		// process all nodes which have non-zero bits\r
		struct node_t* node = &decoder->huffnode[curcode];\r
		if (node->numbits > 0)\r
		{\r
         int shift;\r
         lookup_value *dest;\r
         lookup_value *destend;\r
\r
			// set up the entry\r
			lookup_value value = MAKE_LOOKUP(curcode, node->numbits);\r
\r
			// fill all matching entries\r
			shift   = decoder->maxbits - node->numbits;\r
			dest    = &decoder->lookup[node->bits << shift];\r
			destend = &decoder->lookup[((node->bits + 1) << shift) - 1];\r
\r
			while (dest <= destend)\r
				*dest++ = value;\r
		}\r
	}\r
}\r