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