Commit | Line | Data |
---|---|---|
3719602c PC |
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 |