1 /* license:BSD-3-Clause
2 * copyright-holders:Aaron Giles
3 ***************************************************************************
7 Static Huffman compression and decompression helpers.
9 ***************************************************************************/
16 #include "bitstream.h"
18 /***************************************************************************
20 ***************************************************************************
26 HUFFERR_TOO_MANY_BITS,
28 HUFFERR_INPUT_BUFFER_TOO_SMALL,
29 HUFFERR_OUTPUT_BUFFER_TOO_SMALL,
30 HUFFERR_INTERNAL_INCONSISTENCY,
31 HUFFERR_TOO_MANY_CONTEXTS
34 /***************************************************************************
36 ***************************************************************************
39 typedef uint16_t lookup_value;
41 /* a node in the huffman tree */
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 */
51 /* ======================> huffman_context_base */
53 /* context class for decoding */
54 struct huffman_decoder
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 */
65 /* array versions of the info we need */
67 node_t* huffnode_array; /* [_NumCodes]; */
68 lookup_value* lookup_array; /* [1 << _MaxBits]; */
72 /* ======================> huffman_decoder */
74 struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits);
75 void delete_huffman_decoder(struct huffman_decoder* decoder);
77 /* single item operations */
78 uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf);
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);
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);
87 void huffman_build_lookup_table(struct huffman_decoder* decoder);