[pcsx_rearmed.git] / deps / libchdr / include / libchdr / huffman.h

/* license:BSD-3-Clause
 * copyright-holders:Aaron Giles
 ***************************************************************************

    huffman.h

    Static Huffman compression and decompression helpers.

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

#pragma once

#ifndef __HUFFMAN_H__
#define __HUFFMAN_H__

#include <libchdr/bitstream.h>


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

enum huffman_error
{
	HUFFERR_NONE = 0,
	HUFFERR_TOO_MANY_BITS,
	HUFFERR_INVALID_DATA,
	HUFFERR_INPUT_BUFFER_TOO_SMALL,
	HUFFERR_OUTPUT_BUFFER_TOO_SMALL,
	HUFFERR_INTERNAL_INCONSISTENCY,
	HUFFERR_TOO_MANY_CONTEXTS
};

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

typedef uint16_t lookup_value;

/* a node in the huffman tree */
struct node_t
{
	struct node_t*		parent;		/* pointer to parent node */
	uint32_t			count;		/* number of hits on this node */
	uint32_t			weight;		/* assigned weight of this node */
	uint32_t			bits;		/* bits used to encode the node */
	uint8_t				numbits;	/* number of bits needed for this node */
};

/* ======================> huffman_context_base */

/* context class for decoding */
struct huffman_decoder
{
	/* internal state */
	uint32_t			numcodes;             /* number of total codes being processed */
	uint8_t				maxbits;           /* maximum bits per code */
	uint8_t 			prevdata;             /* value of the previous data (for delta-RLE encoding) */
	int             	rleremaining;         /* number of RLE bytes remaining (for delta-RLE encoding) */
	lookup_value *  	lookup;               /* pointer to the lookup table */
	struct node_t *     huffnode;             /* array of nodes */
	uint32_t *      	datahisto;            /* histogram of data values */

	/* array versions of the info we need */
#if 0
	node_t*			huffnode_array; /* [_NumCodes]; */
	lookup_value*	lookup_array; /* [1 << _MaxBits]; */
#endif
};

/* ======================> huffman_decoder */

struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits);
void delete_huffman_decoder(struct huffman_decoder* decoder);

/* single item operations */
uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf);

enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf);
enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf);

int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight);
enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder);
enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder);

void huffman_build_lookup_table(struct huffman_decoder* decoder);

#endif
Commit	Line	Data
9c659ffe	1	/* license:BSD-3-Clause
	2	* copyright-holders:Aaron Giles
	3	***************************************************************************
	4
	5	huffman.h
	6
	7	Static Huffman compression and decompression helpers.
	8
	9	***************************************************************************/
	10
	11	#pragma once
	12
	13	#ifndef __HUFFMAN_H__
	14	#define __HUFFMAN_H__
	15
2ff0b512	16	#include <libchdr/bitstream.h>
9c659ffe	17
	18
	19	/***************************************************************************
	20	* CONSTANTS
	21	***************************************************************************
	22	*/
	23
	24	enum huffman_error
	25	{
	26	HUFFERR_NONE = 0,
	27	HUFFERR_TOO_MANY_BITS,
	28	HUFFERR_INVALID_DATA,
	29	HUFFERR_INPUT_BUFFER_TOO_SMALL,
	30	HUFFERR_OUTPUT_BUFFER_TOO_SMALL,
	31	HUFFERR_INTERNAL_INCONSISTENCY,
	32	HUFFERR_TOO_MANY_CONTEXTS
	33	};
	34
	35	/***************************************************************************
	36	* TYPE DEFINITIONS
	37	***************************************************************************
	38	*/
	39
	40	typedef uint16_t lookup_value;
	41
	42	/* a node in the huffman tree */
	43	struct node_t
	44	{
	45	struct node_t* parent; /* pointer to parent node */
	46	uint32_t count; /* number of hits on this node */
	47	uint32_t weight; /* assigned weight of this node */
	48	uint32_t bits; /* bits used to encode the node */
	49	uint8_t numbits; /* number of bits needed for this node */
	50	};
	51
	52	/* ======================> huffman_context_base */
	53
	54	/* context class for decoding */
	55	struct huffman_decoder
	56	{
	57	/* internal state */
	58	uint32_t numcodes; /* number of total codes being processed */
	59	uint8_t maxbits; /* maximum bits per code */
	60	uint8_t prevdata; /* value of the previous data (for delta-RLE encoding) */
	61	int rleremaining; /* number of RLE bytes remaining (for delta-RLE encoding) */
	62	lookup_value * lookup; /* pointer to the lookup table */
	63	struct node_t * huffnode; /* array of nodes */
	64	uint32_t * datahisto; /* histogram of data values */
	65
	66	/* array versions of the info we need */
	67	#if 0
	68	node_t* huffnode_array; /* [_NumCodes]; */
	69	lookup_value* lookup_array; /* [1 << _MaxBits]; */
	70	#endif
	71	};
	72
	73	/* ======================> huffman_decoder */
	74
	75	struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits);
2ff0b512	76	void delete_huffman_decoder(struct huffman_decoder* decoder);
9c659ffe	77
	78	/* single item operations */
	79	uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf);
	80
	81	enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf);
	82	enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf);
	83
	84	int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight);
	85	enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder);
	86	enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder);
	87
	88	void huffman_build_lookup_table(struct huffman_decoder* decoder);
	89
	90	#endif