1 /*
2  * huffman.h: Huffman tree-building routines common to Deflate and LZX.
3  */
4 
5 /*
6  * Take an input array 'freqs' of size 'nsyms' giving each symbol's
7  * frequency. Return an output array 'lengths' of the same size giving
8  * each symbol's code length. Enforce during construction that no code
9  * length is greater than 'limit'.
10  *
11  * The 'freqs' array may be modified, as a side effect of the limit
12  * enforcement.
13  */
14 void build_huffman_tree(int *freqs, unsigned char *lengths,
15                         int nsyms, int limit);
16 
17 /*
18  * Given a sequence of Huffman code lengths, compute the actual code
19  * values. Each one is returned in codes[i] and occupies the bottom
20  * lengths[i] bits of the integer. They are in natural big-endian
21  * format, i.e. the initial bit of the code, governing the choice of
22  * direction at the root node of the notional decode tree, is in the
23  * most significant bit position.
24  *
25  * Returns the maximum code length found. Can also return -1 to
26  * indicate the table was overcommitted (too many or too short codes
27  * to exactly cover the possible space), which is a fatal error (the
28  * output codes will not form a usable Huffman tree), or -2 to
29  * indicate it was undercommitted (too few or too long codes), which
30  * is a non-fatal error (the resulting tree would be usable, just
31  * inefficient).
32  */
33 int compute_huffman_codes(const unsigned char *lengths, int *codes, int nsyms);
34