| 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 |