| 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 <libchdr/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 | void delete_huffman_decoder(struct huffman_decoder* decoder); |
| 77 | |
| 78 | /* single item operations */ |
| 79 | uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf); |
| 80 | |
| 81 | enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf); |
| 82 | enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf); |
| 83 | |
| 84 | int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight); |
| 85 | enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder); |
| 86 | enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder); |
| 87 | |
| 88 | void huffman_build_lookup_table(struct huffman_decoder* decoder); |
| 89 | |
| 90 | #endif |