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
40     unsigned drop;              /* code bits to drop for sub-table */  in inflate_table()
49     code FAR *next;             /* next available space in table */  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()
91        table.  The sorted table is work[], with that space being provided by  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()
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()
149        those top drop + curr - len bits are incremented through all values to  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()
164        provided *table space.  It is checked for LENS and DIST tables against  in inflate_table()
178         base = extra = work;    /* dummy value--not used */  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()
203     /* check available table space */  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()
271             /* check for enough space */  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()
290         here.bits = (unsigned char)(len - drop);  in inflate_table()