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