1 /* inftrees.c -- generate Huffman trees for efficient decoding
2  * Copyright (C) 1995-2024 Mark Adler
12    " inflate 1.3.1 Copyright 1995-2024 Mark Adler ";
22    The code lengths are lens[0..codes-1].  The result starts at *table,
23    whose indices are 0..2^bits-1.  work is a writable array of at least
26    -1 is an invalid code, and +1 means that ENOUGH isn't enough.  table
28    requested root table index bits, and on return it is the actual root
29    table index bits.  It will differ if the request is greater than the
36     unsigned sym;               /* index of code symbols */  in inflate_table()
38     unsigned root;              /* number of index bits for root table */  in inflate_table()
39     unsigned curr;              /* number of index bits for current table */  in inflate_table()
40     unsigned drop;              /* code bits to drop for sub-table */  in inflate_table()
44     unsigned incr;              /* for incrementing code, index */  in inflate_table()
45     unsigned fill;              /* index for replicating entries */  in inflate_table()
72        code lengths are lens[0..codes-1].  Each length corresponds to the  in inflate_table()
73        symbols 0..codes-1.  The Huffman code is generated by first sorting the  in inflate_table()
75        for codes with equal lengths.  Then the code starts with all zero bits  in inflate_table()
96        codes at all, checking for a valid set of lengths, and looking ahead  in inflate_table()
97        at length counts to determine sub-table sizes when building the  in inflate_table()
109     for (max = MAXBITS; max >= 1; max--)  in inflate_table()
112     if (max == 0) {                     /* no symbols to code at all */  in inflate_table()
125     /* check for an over-subscribed or incomplete set of lengths */  in inflate_table()
129         left -= count[len];  in inflate_table()
130         if (left < 0) return -1;        /* over-subscribed */  in inflate_table()
133         return -1;                      /* incomplete set */  in inflate_table()
146        filled is at next and has curr index bits.  The code being used is huff  in inflate_table()
147        with length len.  That code is converted to an index by dropping drop  in inflate_table()
149        those top drop + curr - len bits are incremented through all values to  in inflate_table()
152        root is the number of index bits for the root table.  When len exceeds  in inflate_table()
153        root, sub-tables are created pointed to by the root entry with an index  in inflate_table()
155        new sub-table should be started.  drop is zero when the root table is  in inflate_table()
156        being filled, and drop is root when sub-tables are being filled.  in inflate_table()
158        When a new sub-table is needed, it is necessary to look ahead in the  in inflate_table()
159        code lengths to determine what size sub-table is needed.  The length  in inflate_table()
171        routine permits incomplete codes, so another loop after this one fills  in inflate_table()
178         base = extra = work;    /* dummy value--not used */  in inflate_table()
197     curr = root;                /* current table index bits */  in inflate_table()
198     drop = 0;                   /* current bits to drop from code for index */  in inflate_table()
199     low = (unsigned)(-1);       /* trigger new sub-table when len > root */  in inflate_table()
201     mask = used - 1;            /* mask for comparing low */  in inflate_table()
211         here.bits = (unsigned char)(len - drop);  in inflate_table()
217             here.op = (unsigned char)(extra[work[sym] - match]);  in inflate_table()
218             here.val = base[work[sym] - match];  in inflate_table()
226         incr = 1U << (len - drop);  in inflate_table()
230             fill -= incr;  in inflate_table()
234         /* backwards increment the len-bit code huff */  in inflate_table()
235         incr = 1U << (len - 1);  in inflate_table()
239             huff &= incr - 1;  in inflate_table()
247         if (--(count[len]) == 0) {  in inflate_table()
252         /* create new sub-table if needed */  in inflate_table()
254             /* if first time, transition to sub-tables */  in inflate_table()
262             curr = len - drop;  in inflate_table()
265                 left -= count[curr + drop];  in inflate_table()
277             /* point entry in root table to sub-table */  in inflate_table()
281             (*table)[low].val = (unsigned short)(next - *table);  in inflate_table()
286        at most one remaining entry, since if the code is incomplete, the  in inflate_table()
287        maximum code length that was allowed to get this far is one bit) */  in inflate_table()
290         here.bits = (unsigned char)(len - drop);  in inflate_table()