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 /*************************************************************************** 20 * CONSTANTS 21 *************************************************************************** 22 */ 23 24 enum huffman_error 25 { 26 HUFFERR_NONE = 0, 27 HUFFERR_TOO_MANY_BITS, 28 HUFFERR_INVALID_DATA, 29 HUFFERR_INPUT_BUFFER_TOO_SMALL, 30 HUFFERR_OUTPUT_BUFFER_TOO_SMALL, 31 HUFFERR_INTERNAL_INCONSISTENCY, 32 HUFFERR_TOO_MANY_CONTEXTS 33 }; 34 35 /*************************************************************************** 36 * TYPE DEFINITIONS 37 *************************************************************************** 38 */ 39 40 typedef uint16_t lookup_value; 41 42 /* a node in the huffman tree */ 43 struct node_t 44 { 45 struct node_t* parent; /* pointer to parent node */ 46 uint32_t count; /* number of hits on this node */ 47 uint32_t weight; /* assigned weight of this node */ 48 uint32_t bits; /* bits used to encode the node */ 49 uint8_t numbits; /* number of bits needed for this node */ 50 }; 51 52 /* ======================> huffman_context_base */ 53 54 /* context class for decoding */ 55 struct huffman_decoder 56 { 57 /* internal state */ 58 uint32_t numcodes; /* number of total codes being processed */ 59 uint8_t maxbits; /* maximum bits per code */ 60 uint8_t prevdata; /* value of the previous data (for delta-RLE encoding) */ 61 int rleremaining; /* number of RLE bytes remaining (for delta-RLE encoding) */ 62 lookup_value * lookup; /* pointer to the lookup table */ 63 struct node_t * huffnode; /* array of nodes */ 64 uint32_t * datahisto; /* histogram of data values */ 65 66 /* array versions of the info we need */ 67 #if 0 68 node_t* huffnode_array; /* [_NumCodes]; */ 69 lookup_value* lookup_array; /* [1 << _MaxBits]; */ 70 #endif 71 }; 72 73 /* ======================> huffman_decoder */ 74 75 struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits); 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