130bfc1167f9eaa30bf9e55fee05cf41c76226a4
[wimlib] / src / compress_common.c
1 /*
2  * compress_common.c
3  *
4  * Code for compression shared among multiple compression formats.
5  *
6  * Author:  Eric Biggers
7  * Year:    2012 - 2014
8  *
9  * The author dedicates this file to the public domain.
10  * You can do whatever you want with this file.
11  */
12
13 #ifdef HAVE_CONFIG_H
14 #  include "config.h"
15 #endif
16
17 #include "wimlib/assert.h"
18 #include "wimlib/compress_common.h"
19 #include "wimlib/util.h"
20
21 #include <string.h>
22
23 /* Given the binary tree node A[subtree_idx] whose children already
24  * satisfy the maxheap property, swap the node with its greater child
25  * until it is greater than both its children, so that the maxheap
26  * property is satisfied in the subtree rooted at A[subtree_idx].  */
27 static void
28 heapify_subtree(u32 A[], unsigned length, unsigned subtree_idx)
29 {
30         unsigned parent_idx;
31         unsigned child_idx;
32         u32 v;
33
34         v = A[subtree_idx];
35         parent_idx = subtree_idx;
36         while ((child_idx = parent_idx * 2) <= length) {
37                 if (child_idx < length && A[child_idx + 1] > A[child_idx])
38                         child_idx++;
39                 if (v >= A[child_idx])
40                         break;
41                 A[parent_idx] = A[child_idx];
42                 parent_idx = child_idx;
43         }
44         A[parent_idx] = v;
45 }
46
47 /* Rearrange the array 'A' so that it satisfies the maxheap property.
48  * 'A' uses 1-based indices, so the children of A[i] are A[i*2] and A[i*2 + 1].
49  */
50 static void
51 heapify_array(u32 A[], unsigned length)
52 {
53         for (unsigned subtree_idx = length / 2; subtree_idx >= 1; subtree_idx--)
54                 heapify_subtree(A, length, subtree_idx);
55 }
56
57 /* Sort the array 'A', which contains 'length' unsigned 32-bit integers.  */
58 static void
59 heapsort(u32 A[], unsigned length)
60 {
61         A--; /* Use 1-based indices  */
62
63         heapify_array(A, length);
64
65         while (length >= 2) {
66                 swap(A[1], A[length]);
67                 length--;
68                 heapify_subtree(A, length, 1);
69         }
70 }
71
72 #define NUM_SYMBOL_BITS 10
73 #define SYMBOL_MASK ((1 << NUM_SYMBOL_BITS) - 1)
74
75 /*
76  * Sort the symbols primarily by frequency and secondarily by symbol
77  * value.  Discard symbols with zero frequency and fill in an array with
78  * the remaining symbols, along with their frequencies.  The low
79  * NUM_SYMBOL_BITS bits of each array entry will contain the symbol
80  * value, and the remaining bits will contain the frequency.
81  *
82  * @num_syms
83  *      Number of symbols in the alphabet.
84  *      Can't be greater than (1 << NUM_SYMBOL_BITS).
85  *
86  * @freqs[num_syms]
87  *      The frequency of each symbol.
88  *
89  * @lens[num_syms]
90  *      An array that eventually will hold the length of each codeword.
91  *      This function only fills in the codeword lengths for symbols that
92  *      have zero frequency, which are not well defined per se but will
93  *      be set to 0.
94  *
95  * @symout[num_syms]
96  *      The output array, described above.
97  *
98  * Returns the number of entries in 'symout' that were filled.  This is
99  * the number of symbols that have nonzero frequency.
100  */
101 static unsigned
102 sort_symbols(unsigned num_syms, const u32 freqs[restrict],
103              u8 lens[restrict], u32 symout[restrict])
104 {
105         unsigned num_used_syms;
106         unsigned num_counters;
107
108         /* We rely on heapsort, but with an added optimization.  Since
109          * it's common for most symbol frequencies to be low, we first do
110          * a count sort using a limited number of counters.  High
111          * frequencies will be counted in the last counter, and only they
112          * will be sorted with heapsort.
113          *
114          * Note: with more symbols, it is generally beneficial to have more
115          * counters.  About 1 counter per 4 symbols seems fast.
116          *
117          * Note: I also tested radix sort, but even for large symbol
118          * counts (> 255) and frequencies bounded at 16 bits (enabling
119          * radix sort by just two base-256 digits), it didn't seem any
120          * faster than the method implemented here.
121          *
122          * Note: I tested the optimized quicksort implementation from
123          * glibc (with indirection overhead removed), but it was only
124          * marginally faster than the simple heapsort implemented here.
125          *
126          * Tests were done with building the codes for LZX.  Results may
127          * vary for different compression algorithms...!  */
128
129         num_counters = (DIV_ROUND_UP(num_syms, 4) + 3) & ~3;
130
131         unsigned counters[num_counters];
132
133         memset(counters, 0, sizeof(counters));
134
135         /* Count the frequencies.  */
136         for (unsigned sym = 0; sym < num_syms; sym++)
137                 counters[min(freqs[sym], num_counters - 1)]++;
138
139         /* Make the counters cumulative, ignoring the zero-th, which
140          * counted symbols with zero frequency.  As a side effect, this
141          * calculates the number of symbols with nonzero frequency.  */
142         num_used_syms = 0;
143         for (unsigned i = 1; i < num_counters; i++) {
144                 unsigned count = counters[i];
145                 counters[i] = num_used_syms;
146                 num_used_syms += count;
147         }
148
149         /* Sort nonzero-frequency symbols using the counters.  At the
150          * same time, set the codeword lengths of zero-frequency symbols
151          * to 0.  */
152         for (unsigned sym = 0; sym < num_syms; sym++) {
153                 u32 freq = freqs[sym];
154                 if (freq != 0) {
155                         symout[counters[min(freq, num_counters - 1)]++] =
156                                 sym | (freq << NUM_SYMBOL_BITS);
157                 } else {
158                         lens[sym] = 0;
159                 }
160         }
161
162         /* Sort the symbols counted in the last counter.  */
163         heapsort(symout + counters[num_counters - 2],
164                  counters[num_counters - 1] - counters[num_counters - 2]);
165
166         return num_used_syms;
167 }
168
169 /*
170  * Build the Huffman tree.
171  *
172  * This is an optimized implementation that
173  *      (a) takes advantage of the frequencies being already sorted;
174  *      (b) only generates non-leaf nodes, since the non-leaf nodes of a
175  *          Huffman tree are sufficient to generate a canonical code;
176  *      (c) Only stores parent pointers, not child pointers;
177  *      (d) Produces the nodes in the same memory used for input
178  *          frequency information.
179  *
180  * Array 'A', which contains 'sym_count' entries, is used for both input
181  * and output.  For this function, 'sym_count' must be at least 2.
182  *
183  * For input, the array must contain the frequencies of the symbols,
184  * sorted in increasing order.  Specifically, each entry must contain a
185  * frequency left shifted by NUM_SYMBOL_BITS bits.  Any data in the low
186  * NUM_SYMBOL_BITS bits of the entries will be ignored by this function.
187  * Although these bits will, in fact, contain the symbols that correspond
188  * to the frequencies, this function is concerned with frequencies only
189  * and keeps the symbols as-is.
190  *
191  * For output, this function will produce the non-leaf nodes of the
192  * Huffman tree.  These nodes will be stored in the first (sym_count - 1)
193  * entries of the array.  Entry A[sym_count - 2] will represent the root
194  * node.  Each other node will contain the zero-based index of its parent
195  * node in 'A', left shifted by NUM_SYMBOL_BITS bits.  The low
196  * NUM_SYMBOL_BITS bits of each entry in A will be kept as-is.  Again,
197  * note that although these low bits will, in fact, contain a symbol
198  * value, this symbol will have *no relationship* with the Huffman tree
199  * node that happens to occupy the same slot.  This is because this
200  * implementation only generates the non-leaf nodes of the tree.
201  */
202 static void
203 build_tree(u32 A[], unsigned sym_count)
204 {
205         /* Index, in 'A', of next lowest frequency symbol that has not
206          * yet been processed.  */
207         unsigned i = 0;
208
209         /* Index, in 'A', of next lowest frequency parentless non-leaf
210          * node; or, if equal to 'e', then no such node exists yet.  */
211         unsigned b = 0;
212
213         /* Index, in 'A', of next node to allocate as a non-leaf.  */
214         unsigned e = 0;
215
216         do {
217                 unsigned m, n;
218                 u32 freq_shifted;
219
220                 /* Choose the two next lowest frequency entries.  */
221
222                 if (i != sym_count &&
223                     (b == e || (A[i] >> NUM_SYMBOL_BITS) <= (A[b] >> NUM_SYMBOL_BITS)))
224                         m = i++;
225                 else
226                         m = b++;
227
228                 if (i != sym_count &&
229                     (b == e || (A[i] >> NUM_SYMBOL_BITS) <= (A[b] >> NUM_SYMBOL_BITS)))
230                         n = i++;
231                 else
232                         n = b++;
233
234                 /* Allocate a non-leaf node and link the entries to it.
235                  *
236                  * If we link an entry that we're visiting for the first
237                  * time (via index 'i'), then we're actually linking a
238                  * leaf node and it will have no effect, since the leaf
239                  * will be overwritten with a non-leaf when index 'e'
240                  * catches up to it.  But it's not any slower to
241                  * unconditionally set the parent index.
242                  *
243                  * We also compute the frequency of the non-leaf node as
244                  * the sum of its two children's frequencies.  */
245
246                 freq_shifted = (A[m] & ~SYMBOL_MASK) + (A[n] & ~SYMBOL_MASK);
247
248                 A[m] = (A[m] & SYMBOL_MASK) | (e << NUM_SYMBOL_BITS);
249                 A[n] = (A[n] & SYMBOL_MASK) | (e << NUM_SYMBOL_BITS);
250                 A[e] = (A[e] & SYMBOL_MASK) | freq_shifted;
251                 e++;
252         } while (sym_count - e > 1);
253                 /* When just one entry remains, it is a "leaf" that was
254                  * linked to some other node.  We ignore it, since the
255                  * rest of the array contains the non-leaves which we
256                  * need.  (Note that we're assuming the cases with 0 or 1
257                  * symbols were handled separately.) */
258 }
259
260 /*
261  * Given the stripped-down Huffman tree constructed by build_tree(),
262  * determine the number of codewords that should be assigned each
263  * possible length, taking into account the length-limited constraint.
264  *
265  * @A
266  *      The array produced by build_tree(), containing parent index
267  *      information for the non-leaf nodes of the Huffman tree.  Each
268  *      entry in this array is a node; a node's parent always has a
269  *      greater index than that node itself.  This function will
270  *      overwrite the parent index information in this array, so
271  *      essentially it will destroy the tree.  However, the data in the
272  *      low NUM_SYMBOL_BITS of each entry will be preserved.
273  *
274  * @root_idx
275  *      The 0-based index of the root node in 'A', and consequently one
276  *      less than the number of tree node entries in 'A'.  (Or, really 2
277  *      less than the actual length of 'A'.)
278  *
279  * @len_counts
280  *      An array of length ('max_codeword_len' + 1) in which the number of
281  *      codewords having each length <= max_codeword_len will be
282  *      returned.
283  *
284  * @max_codeword_len
285  *      The maximum permissible codeword length.
286  */
287 static void
288 compute_length_counts(u32 A[restrict], unsigned root_idx,
289                       unsigned len_counts[restrict], unsigned max_codeword_len)
290 {
291         /* The key observations are:
292          *
293          * (1) We can traverse the non-leaf nodes of the tree, always
294          * visiting a parent before its children, by simply iterating
295          * through the array in reverse order.  Consequently, we can
296          * compute the depth of each node in one pass, overwriting the
297          * parent indices with depths.
298          *
299          * (2) We can initially assume that in the real Huffman tree,
300          * both children of the root are leaves.  This corresponds to two
301          * codewords of length 1.  Then, whenever we visit a (non-leaf)
302          * node during the traversal, we modify this assumption to
303          * account for the current node *not* being a leaf, but rather
304          * its two children being leaves.  This causes the loss of one
305          * codeword for the current depth and the addition of two
306          * codewords for the current depth plus one.
307          *
308          * (3) We can handle the length-limited constraint fairly easily
309          * by simply using the largest length available when a depth
310          * exceeds max_codeword_len.
311          */
312
313         for (unsigned len = 0; len <= max_codeword_len; len++)
314                 len_counts[len] = 0;
315         len_counts[1] = 2;
316
317         /* Set the root node's depth to 0.  */
318         A[root_idx] &= SYMBOL_MASK;
319
320         for (int node = root_idx - 1; node >= 0; node--) {
321
322                 /* Calculate the depth of this node.  */
323
324                 unsigned parent = A[node] >> NUM_SYMBOL_BITS;
325                 unsigned parent_depth = A[parent] >> NUM_SYMBOL_BITS;
326                 unsigned depth = parent_depth + 1;
327                 unsigned len = depth;
328
329                 /* Set the depth of this node so that it is available
330                  * when its children (if any) are processed.  */
331
332                 A[node] = (A[node] & SYMBOL_MASK) | (depth << NUM_SYMBOL_BITS);
333
334                 /* If needed, decrease the length to meet the
335                  * length-limited constraint.  This is not the optimal
336                  * method for generating length-limited Huffman codes!
337                  * But it should be good enough.  */
338                 if (len >= max_codeword_len) {
339                         len = max_codeword_len;
340                         do {
341                                 len--;
342                         } while (len_counts[len] == 0);
343                 }
344
345                 /* Account for the fact that we have a non-leaf node at
346                  * the current depth.  */
347                 len_counts[len]--;
348                 len_counts[len + 1] += 2;
349         }
350 }
351
352 /*
353  * Generate the codewords for a canonical Huffman code.
354  *
355  * @A
356  *      The output array for codewords.  In addition, initially this
357  *      array must contain the symbols, sorted primarily by frequency and
358  *      secondarily by symbol value, in the low NUM_SYMBOL_BITS bits of
359  *      each entry.
360  *
361  * @len
362  *      Output array for codeword lengths.
363  *
364  * @len_counts
365  *      An array that provides the number of codewords that will have
366  *      each possible length <= max_codeword_len.
367  *
368  * @max_codeword_len
369  *      Maximum length, in bits, of each codeword.
370  *
371  * @num_syms
372  *      Number of symbols in the alphabet, including symbols with zero
373  *      frequency.  This is the length of the 'A' and 'len' arrays.
374  */
375 static void
376 gen_codewords(u32 A[restrict], u8 lens[restrict],
377               const unsigned len_counts[restrict],
378               unsigned max_codeword_len, unsigned num_syms)
379 {
380         u32 next_codewords[max_codeword_len + 1];
381
382         /* Given the number of codewords that will have each length,
383          * assign codeword lengths to symbols.  We do this by assigning
384          * the lengths in decreasing order to the symbols sorted
385          * primarily by increasing frequency and secondarily by
386          * increasing symbol value.  */
387         for (unsigned i = 0, len = max_codeword_len; len >= 1; len--) {
388                 unsigned count = len_counts[len];
389                 while (count--)
390                         lens[A[i++] & SYMBOL_MASK] = len;
391         }
392
393         /* Generate the codewords themselves.  We initialize the
394          * 'next_codewords' array to provide the lexicographically first
395          * codeword of each length, then assign codewords in symbol
396          * order.  This produces a canonical code.  */
397         next_codewords[0] = 0;
398         next_codewords[1] = 0;
399         for (unsigned len = 2; len <= max_codeword_len; len++)
400                 next_codewords[len] =
401                         (next_codewords[len - 1] + len_counts[len - 1]) << 1;
402
403         for (unsigned sym = 0; sym < num_syms; sym++)
404                 A[sym] = next_codewords[lens[sym]]++;
405 }
406
407 /*
408  * ---------------------------------------------------------------------
409  *                      make_canonical_huffman_code()
410  * ---------------------------------------------------------------------
411  *
412  * Given an alphabet and the frequency of each symbol in it, construct a
413  * length-limited canonical Huffman code.
414  *
415  * @num_syms
416  *      The number of symbols in the alphabet.  The symbols are the
417  *      integers in the range [0, num_syms - 1].  This parameter must be
418  *      at least 2 and can't be greater than (1 << NUM_SYMBOL_BITS).
419  *
420  * @max_codeword_len
421  *      The maximum permissible codeword length.
422  *
423  * @freqs
424  *      An array of @num_syms entries, each of which specifies the
425  *      frequency of the corresponding symbol.  It is valid for some,
426  *      none, or all of the frequencies to be 0.
427  *
428  * @lens
429  *      An array of @num_syms entries in which this function will return
430  *      the length, in bits, of the codeword assigned to each symbol.
431  *      Symbols with 0 frequency will not have codewords per se, but
432  *      their entries in this array will be set to 0.  No lengths greater
433  *      than @max_codeword_len will be assigned.
434  *
435  * @codewords
436  *      An array of @num_syms entries in which this function will return
437  *      the codeword for each symbol, right-justified and padded on the
438  *      left with zeroes.  Codewords for symbols with 0 frequency will be
439  *      undefined.
440  *
441  * ---------------------------------------------------------------------
442  *
443  * This function builds a length-limited canonical Huffman code.
444  *
445  * A length-limited Huffman code contains no codewords longer than some
446  * specified length, and has exactly (with some algorithms) or
447  * approximately (with the algorithm used here) the minimum weighted path
448  * length from the root, given this constraint.
449  *
450  * A canonical Huffman code satisfies the properties that a longer
451  * codeword never lexicographically precedes a shorter codeword, and the
452  * lexicographic ordering of codewords of the same length is the same as
453  * the lexicographic ordering of the corresponding symbols.  A canonical
454  * Huffman code, or more generally a canonical prefix code, can be
455  * reconstructed from only a list containing the codeword length of each
456  * symbol.
457  *
458  * The classic algorithm to generate a Huffman code creates a node for
459  * each symbol, then inserts these nodes into a min-heap keyed by symbol
460  * frequency.  Then, repeatedly, the two lowest-frequency nodes are
461  * removed from the min-heap and added as the children of a new node
462  * having frequency equal to the sum of its two children, which is then
463  * inserted into the min-heap.  When only a single node remains in the
464  * min-heap, it is the root of the Huffman tree.  The codeword for each
465  * symbol is determined by the path needed to reach the corresponding
466  * node from the root.  Descending to the left child appends a 0 bit,
467  * whereas descending to the right child appends a 1 bit.
468  *
469  * The classic algorithm is relatively easy to understand, but it is
470  * subject to a number of inefficiencies.  In practice, it is fastest to
471  * first sort the symbols by frequency.  (This itself can be subject to
472  * an optimization based on the fact that most frequencies tend to be
473  * low.)  At the same time, we sort secondarily by symbol value, which
474  * aids the process of generating a canonical code.  Then, during tree
475  * construction, no heap is necessary because both the leaf nodes and the
476  * unparented non-leaf nodes can be easily maintained in sorted order.
477  * Consequently, there can never be more than two possibilities for the
478  * next-lowest-frequency node.
479  *
480  * In addition, because we're generating a canonical code, we actually
481  * don't need the leaf nodes of the tree at all, only the non-leaf nodes.
482  * This is because for canonical code generation we don't need to know
483  * where the symbols are in the tree.  Rather, we only need to know how
484  * many leaf nodes have each depth (codeword length).  And this
485  * information can, in fact, be quickly generated from the tree of
486  * non-leaves only.
487  *
488  * Furthermore, we can build this stripped-down Huffman tree directly in
489  * the array in which the codewords are to be generated, provided that
490  * these array slots are large enough to hold a symbol and frequency
491  * value.
492  *
493  * Still furthermore, we don't even need to maintain explicit child
494  * pointers.  We only need the parent pointers, and even those can be
495  * overwritten in-place with depth information as part of the process of
496  * extracting codeword lengths from the tree.  So in summary, we do NOT
497  * need a big structure like:
498  *
499  *      struct huffman_tree_node {
500  *              unsigned int symbol;
501  *              unsigned int frequency;
502  *              unsigned int depth;
503  *              struct huffman_tree_node *left_child;
504  *              struct huffman_tree_node *right_child;
505  *      };
506  *
507  *
508  *   ... which often gets used in "naive" implementations of Huffman code
509  *   generation.
510  *
511  * Most of these optimizations are based on the implementation in 7-Zip
512  * (source file: C/HuffEnc.c), which has been placed in the public domain
513  * by Igor Pavlov.  But I've rewritten the code with extensive comments,
514  * as it took me a while to figure out what it was doing...!
515  *
516  * ---------------------------------------------------------------------
517  *
518  * NOTE: in general, the same frequencies can be used to generate
519  * different length-limited canonical Huffman codes.  One choice we have
520  * is during tree construction, when we must decide whether to prefer a
521  * leaf or non-leaf when there is a tie in frequency.  Another choice we
522  * have is how to deal with codewords that would exceed @max_codeword_len
523  * bits in length.  Both of these choices affect the resulting codeword
524  * lengths, which otherwise can be mapped uniquely onto the resulting
525  * canonical Huffman code.
526  *
527  * Normally, there is no problem with choosing one valid code over
528  * another, provided that they produce similar compression ratios.
529  * However, the LZMS compression format uses adaptive Huffman coding.  It
530  * requires that both the decompressor and compressor build a canonical
531  * code equivalent to that which can be generated by using the classic
532  * Huffman tree construction algorithm and always processing leaves
533  * before non-leaves when there is a frequency tie.  Therefore, we make
534  * sure to do this.  This method also has the advantage of sometimes
535  * shortening the longest codeword that is generated.
536  *
537  * There also is the issue of how codewords longer than @max_codeword_len
538  * are dealt with.  Fortunately, for LZMS this is irrelevant because
539  * because for the LZMS alphabets no codeword can ever exceed
540  * LZMS_MAX_CODEWORD_LEN (= 15).  Since the LZMS algorithm regularly
541  * halves all frequencies, the frequencies cannot become high enough for
542  * a length 16 codeword to be generated.  Specifically, I think that if
543  * ties are broken in favor of non-leaves (as we do), the lowest total
544  * frequency that would give a length-16 codeword would be the sum of the
545  * frequencies 1 1 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364, which
546  * is 3570.  And in LZMS we can't get a frequency that high based on the
547  * alphabet sizes, rebuild frequencies, and scaling factors.  This
548  * worst-case scenario is based on the following degenerate case (only
549  * the bottom of the tree shown):
550  *
551  *                          ...
552  *                        17
553  *                       /  \
554  *                      10   7
555  *                     / \
556  *                    6   4
557  *                   / \
558  *                  3   3
559  *                 / \
560  *                2   1
561  *               / \
562  *              1   1
563  *
564  * Excluding the first leaves (those with value 1), each leaf value must
565  * be greater than the non-leaf up 1 and down 2 from it; otherwise that
566  * leaf would have taken precedence over that non-leaf and been combined
567  * with the leaf below, thereby decreasing the height compared to that
568  * shown.
569  *
570  * Interesting fact: if we were to instead prioritize non-leaves over
571  * leaves, then the worst case frequencies would be the Fibonacci
572  * sequence, plus an extra frequency of 1.  In this hypothetical
573  * scenario, it would be slightly easier for longer codewords to be
574  * generated.
575  */
576 void
577 make_canonical_huffman_code(unsigned num_syms, unsigned max_codeword_len,
578                             const u32 freqs[restrict],
579                             u8 lens[restrict], u32 codewords[restrict])
580 {
581         u32 *A = codewords;
582         unsigned num_used_syms;
583
584         /* Assumptions  */
585         wimlib_assert2(num_syms >= 2);
586         wimlib_assert2(num_syms <= (1 << NUM_SYMBOL_BITS));
587         wimlib_assert2((1ULL << max_codeword_len) >= num_syms);
588         wimlib_assert2(max_codeword_len <= 32);
589
590         /* We begin by sorting the symbols primarily by frequency and
591          * secondarily by symbol value.  As an optimization, the array
592          * used for this purpose ('A') shares storage with the space in
593          * which we will eventually return the codewords.  */
594
595         num_used_syms = sort_symbols(num_syms, freqs, lens, A);
596
597         /* 'num_used_syms' is the number of symbols with nonzero
598          * frequency.  This may be less than @num_syms.  'num_used_syms'
599          * is also the number of entries in 'A' that are valid.  Each
600          * entry consists of a distinct symbol and a nonzero frequency
601          * packed into a 32-bit integer.  */
602
603         /* Handle special cases where only 0 or 1 symbols were used (had
604          * nonzero frequency).  */
605
606         if (unlikely(num_used_syms == 0)) {
607                 /* Code is empty.  sort_symbols() already set all lengths
608                  * to 0, so there is nothing more to do.  */
609                 return;
610         }
611
612         if (unlikely(num_used_syms == 1)) {
613                 /* Only one symbol was used, so we only need one
614                  * codeword.  But two codewords are needed to form the
615                  * smallest complete Huffman code, which uses codewords 0
616                  * and 1.  Therefore, we choose another symbol to which
617                  * to assign a codeword.  We use 0 (if the used symbol is
618                  * not 0) or 1 (if the used symbol is 0).  In either
619                  * case, the lesser-valued symbol must be assigned
620                  * codeword 0 so that the resulting code is canonical.  */
621
622                 unsigned sym = A[0] & SYMBOL_MASK;
623                 unsigned nonzero_idx = sym ? sym : 1;
624
625                 codewords[0] = 0;
626                 lens[0] = 1;
627                 codewords[nonzero_idx] = 1;
628                 lens[nonzero_idx] = 1;
629                 return;
630         }
631
632         /* Build a stripped-down version of the Huffman tree, sharing the
633          * array 'A' with the symbol values.  Then extract length counts
634          * from the tree and use them to generate the final codewords.  */
635
636         build_tree(A, num_used_syms);
637
638         {
639                 unsigned len_counts[max_codeword_len + 1];
640
641                 compute_length_counts(A, num_used_syms - 2,
642                                       len_counts, max_codeword_len);
643
644                 gen_codewords(A, lens, len_counts, max_codeword_len, num_syms);
645         }
646 }