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