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