1 // license:BSD-3-Clause
\r
2 // copyright-holders:Aaron Giles
\r
3 /***************************************************************************
\r
7 Static Huffman compression and decompression helpers.
\r
9 ***************************************************************************/
\r
13 #ifndef __HUFFMAN_H__
\r
14 #define __HUFFMAN_H__
\r
16 #include "bitstream.h"
\r
19 //**************************************************************************
\r
21 //**************************************************************************
\r
26 HUFFERR_TOO_MANY_BITS,
\r
27 HUFFERR_INVALID_DATA,
\r
28 HUFFERR_INPUT_BUFFER_TOO_SMALL,
\r
29 HUFFERR_OUTPUT_BUFFER_TOO_SMALL,
\r
30 HUFFERR_INTERNAL_INCONSISTENCY,
\r
31 HUFFERR_TOO_MANY_CONTEXTS
\r
36 //**************************************************************************
\r
38 //**************************************************************************
\r
40 typedef uint16_t lookup_value;
\r
42 // a node in the huffman tree
\r
45 struct node_t* parent; // pointer to parent node
\r
46 uint32_t count; // number of hits on this node
\r
47 uint32_t weight; // assigned weight of this node
\r
48 uint32_t bits; // bits used to encode the node
\r
49 uint8_t numbits; // number of bits needed for this node
\r
52 // ======================> huffman_context_base
\r
54 // context class for decoding
\r
55 struct huffman_decoder
\r
58 uint32_t numcodes; // number of total codes being processed
\r
59 uint8_t maxbits; // maximum bits per code
\r
60 uint8_t prevdata; // value of the previous data (for delta-RLE encoding)
\r
61 int rleremaining; // number of RLE bytes remaining (for delta-RLE encoding)
\r
62 lookup_value * lookup; // pointer to the lookup table
\r
63 struct node_t * huffnode; // array of nodes
\r
64 uint32_t * datahisto; // histogram of data values
\r
66 // array versions of the info we need
\r
67 //node_t* huffnode_array; //[_NumCodes];
\r
68 //lookup_value* lookup_array; //[1 << _MaxBits];
\r
71 // ======================> huffman_decoder
\r
73 struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits);
\r
75 // single item operations
\r
76 uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf);
\r
78 enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf);
\r
79 enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf);
\r
81 int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight);
\r
82 enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder);
\r
83 enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder);
\r
85 void huffman_build_lookup_table(struct huffman_decoder* decoder);
\r