From 715a3bef377aeee898c427be99b1acf440b4a5e5 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Wed, 10 May 2017 07:10:14 +0100 Subject: Factor LZ77 and Huffman routines out of deflate.c. The general routines for analysing a buffer into an LZ77ish stream of literals and matches, and for constructing a Huffman tree in canonical format, now live in their own source files so that they can be reused for other similar compression formats. Deflate-specific details like the exact file encoding are left in deflate.c. --- huffman.h | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 huffman.h (limited to 'huffman.h') diff --git a/huffman.h b/huffman.h new file mode 100644 index 0000000..91faa8e --- /dev/null +++ b/huffman.h @@ -0,0 +1,33 @@ +/* + * huffman.h: Huffman tree-building routines common to Deflate and LZX. + */ + +/* + * Take an input array 'freqs' of size 'nsyms' giving each symbol's + * frequency. Return an output array 'lengths' of the same size giving + * each symbol's code length. Enforce during construction that no code + * length is greater than 'limit'. + * + * The 'freqs' array may be modified, as a side effect of the limit + * enforcement. + */ +void build_huffman_tree(int *freqs, unsigned char *lengths, + int nsyms, int limit); + +/* + * Given a sequence of Huffman code lengths, compute the actual code + * values. Each one is returned in codes[i] and occupies the bottom + * lengths[i] bits of the integer. They are in natural big-endian + * format, i.e. the initial bit of the code, governing the choice of + * direction at the root node of the notional decode tree, is in the + * most significant bit position. + * + * Returns the maximum code length found. Can also return -1 to + * indicate the table was overcommitted (too many or too short codes + * to exactly cover the possible space), which is a fatal error (the + * output codes will not form a usable Huffman tree), or -2 to + * indicate it was undercommitted (too few or too long codes), which + * is a non-fatal error (the resulting tree would be usable, just + * inefficient). + */ +int compute_huffman_codes(const unsigned char *lengths, int *codes, int nsyms); -- cgit v1.1