ce188d4d |
1 | // license:BSD-3-Clause\r |
2 | // copyright-holders:Aaron Giles\r |
3 | /***************************************************************************\r |
4 | \r |
5 | huffman.h\r |
6 | \r |
7 | Static Huffman compression and decompression helpers.\r |
8 | \r |
9 | ***************************************************************************/\r |
10 | \r |
11 | #pragma once\r |
12 | \r |
13 | #ifndef __HUFFMAN_H__\r |
14 | #define __HUFFMAN_H__\r |
15 | \r |
16 | #include "bitstream.h"\r |
17 | \r |
18 | \r |
19 | //**************************************************************************\r |
20 | // CONSTANTS\r |
21 | //**************************************************************************\r |
22 | \r |
23 | enum huffman_error\r |
24 | {\r |
25 | HUFFERR_NONE = 0,\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 |
32 | };\r |
33 | \r |
34 | \r |
35 | \r |
36 | //**************************************************************************\r |
37 | // TYPE DEFINITIONS\r |
38 | //**************************************************************************\r |
39 | \r |
40 | typedef uint16_t lookup_value;\r |
41 | \r |
42 | // a node in the huffman tree\r |
43 | struct node_t\r |
44 | {\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 |
50 | };\r |
51 | \r |
52 | // ======================> huffman_context_base\r |
53 | \r |
54 | // context class for decoding\r |
55 | struct huffman_decoder\r |
56 | {\r |
57 | // internal state\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 |
65 | \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 |
69 | };\r |
70 | \r |
71 | // ======================> huffman_decoder\r |
72 | \r |
73 | struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits);\r |
74 | \r |
75 | // single item operations\r |
76 | uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf);\r |
77 | \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 |
80 | \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 |
84 | \r |
85 | void huffman_build_lookup_table(struct huffman_decoder* decoder);\r |
86 | \r |
87 | #endif\r |