1 /* inftrees.c -- generate Huffman trees for ef 1
2 * Copyright (C) 1995-2005 Mark Adler
3 * For conditions of distribution and use, see
4 */
5
6 #include <linux/zutil.h>
7 #include "inftrees.h"
8
9 #define MAXBITS 15
10
11 /*
12 Build a set of tables to decode the provide
13 The code lengths are lens[0..codes-1]. The
14 whose indices are 0..2^bits-1. work is a w
15 lens shorts, which is used as a work area.
16 to be generated, CODES, LENS, or DISTS. On
17 -1 is an invalid code, and +1 means that EN
18 on return points to the next available entr
19 requested root table index bits, and on ret
20 table index bits. It will differ if the re
21 longest code or if it is less than the shor
22 */
23 int zlib_inflate_table(codetype type, unsigned
24 code **table, unsigned
25 {
26 unsigned len; /* a code's le
27 unsigned sym; /* index of co
28 unsigned min, max; /* minimum and
29 unsigned root; /* number of i
30 unsigned curr; /* number of i
31 unsigned drop; /* code bits t
32 int left; /* number of p
33 unsigned used; /* code entrie
34 unsigned huff; /* Huffman cod
35 unsigned incr; /* for increme
36 unsigned fill; /* index for r
37 unsigned low; /* low bits fo
38 unsigned mask; /* mask for lo
39 code this; /* table entry
40 code *next; /* next available
41 const unsigned short *base; /* base va
42 const unsigned short *extra; /* extra b
43 int end; /* use base an
44 unsigned short count[MAXBITS+1]; /* num
45 unsigned short offs[MAXBITS+1]; /* off
46 static const unsigned short lbase[31] = {
47 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 1
48 35, 43, 51, 59, 67, 83, 99, 115, 131,
49 static const unsigned short lext[31] = { /
50 16, 16, 16, 16, 16, 16, 16, 16, 17, 17
51 19, 19, 19, 19, 20, 20, 20, 20, 21, 21
52 static const unsigned short dbase[32] = {
53 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 4
54 257, 385, 513, 769, 1025, 1537, 2049,
55 8193, 12289, 16385, 24577, 0, 0};
56 static const unsigned short dext[32] = { /
57 16, 16, 16, 16, 17, 17, 18, 18, 19, 19
58 23, 23, 24, 24, 25, 25, 26, 26, 27, 27
59 28, 28, 29, 29, 64, 64};
60
61 /*
62 Process a set of code lengths to create
63 code lengths are lens[0..codes-1]. Eac
64 symbols 0..codes-1. The Huffman code i
65 symbols by length from short to long, a
66 for codes with equal lengths. Then the
67 for the first code of the shortest leng
68 increments for the same length, and zer
69 increases. For the deflate format, the
70 from their more natural integer increme
71 decoding tables are built in the large
72 are incremented backwards.
73
74 This routine assumes, but does not chec
75 lens[] are in the range 0..MAXBITS. Th
76 1..MAXBITS is interpreted as that code
77 symbol does not occur in this code.
78
79 The codes are sorted by computing a cou
80 creating from that a table of starting
81 sorted table, and then entering the sym
82 table. The sorted table is work[], wit
83 the caller.
84
85 The length counts are used for other pu
86 the minimum and maximum length codes, d
87 codes at all, checking for a valid set
88 at length counts to determine sub-table
89 decoding tables.
90 */
91
92 /* accumulate lengths for codes (assumes l
93 for (len = 0; len <= MAXBITS; len++)
94 count[len] = 0;
95 for (sym = 0; sym < codes; sym++)
96 count[lens[sym]]++;
97
98 /* bound code lengths, force root to be wi
99 root = *bits;
100 for (max = MAXBITS; max >= 1; max--)
101 if (count[max] != 0) break;
102 if (root > max) root = max;
103 if (max == 0) { /* no
104 this.op = (unsigned char)64; /* inv
105 this.bits = (unsigned char)1;
106 this.val = (unsigned short)0;
107 *(*table)++ = this; /* mak
108 *(*table)++ = this;
109 *bits = 1;
110 return 0; /* no symbols, but wait
111 }
112 for (min = 1; min < MAXBITS; min++)
113 if (count[min] != 0) break;
114 if (root < min) root = min;
115
116 /* check for an over-subscribed or incompl
117 left = 1;
118 for (len = 1; len <= MAXBITS; len++) {
119 left <<= 1;
120 left -= count[len];
121 if (left < 0) return -1; /* ove
122 }
123 if (left > 0 && (type == CODES || max != 1
124 return -1; /* inc
125
126 /* generate offsets into symbol table for
127 offs[1] = 0;
128 for (len = 1; len < MAXBITS; len++)
129 offs[len + 1] = offs[len] + count[len]
130
131 /* sort symbols by length, by symbol order
132 for (sym = 0; sym < codes; sym++)
133 if (lens[sym] != 0) work[offs[lens[sym
134
135 /*
136 Create and fill in decoding tables. In
137 filled is at next and has curr index bi
138 with length len. That code is converte
139 bits off of the bottom. For codes wher
140 those top drop + curr - len bits are in
141 fill the table with replicated entries.
142
143 root is the number of index bits for th
144 root, sub-tables are created pointed to
145 of the low root bits of huff. This is
146 new sub-table should be started. drop
147 being filled, and drop is root when sub
148
149 When a new sub-table is needed, it is n
150 code lengths to determine what size sub
151 counts are used for this, and so count[
152 entered in the tables.
153
154 used keeps track of how many table entr
155 provided *table space. It is checked w
156 against the space in *table, ENOUGH, mi
157 the worst case distance code, MAXD. Th
158 sufficiency of ENOUGH has not been prov
159 This assumes that when type == LENS, bi
160
161 sym increments through all symbols, and
162 all codes of length max, i.e. all codes
163 routine permits incomplete codes, so an
164 in the rest of the decoding tables with
165 */
166
167 /* set up for code type */
168 switch (type) {
169 case CODES:
170 base = extra = work; /* dummy value
171 end = 19;
172 break;
173 case LENS:
174 base = lbase;
175 base -= 257;
176 extra = lext;
177 extra -= 257;
178 end = 256;
179 break;
180 default: /* DISTS */
181 base = dbase;
182 extra = dext;
183 end = -1;
184 }
185
186 /* initialize state for loop */
187 huff = 0; /* starting co
188 sym = 0; /* starting co
189 len = min; /* starting co
190 next = *table; /* current tab
191 curr = root; /* current tab
192 drop = 0; /* current bit
193 low = (unsigned)(-1); /* trigger new
194 used = 1U << root; /* use root ta
195 mask = used - 1; /* mask for co
196
197 /* check available table space */
198 if (type == LENS && used >= ENOUGH - MAXD)
199 return 1;
200
201 /* process all codes and make table entrie
202 for (;;) {
203 /* create table entry */
204 this.bits = (unsigned char)(len - drop
205 if ((int)(work[sym]) < end) {
206 this.op = (unsigned char)0;
207 this.val = work[sym];
208 }
209 else if ((int)(work[sym]) > end) {
210 this.op = (unsigned char)(extra[wo
211 this.val = base[work[sym]];
212 }
213 else {
214 this.op = (unsigned char)(32 + 64)
215 this.val = 0;
216 }
217
218 /* replicate for those indices with lo
219 incr = 1U << (len - drop);
220 fill = 1U << curr;
221 min = fill; /* save of
222 do {
223 fill -= incr;
224 next[(huff >> drop) + fill] = this
225 } while (fill != 0);
226
227 /* backwards increment the len-bit cod
228 incr = 1U << (len - 1);
229 while (huff & incr)
230 incr >>= 1;
231 if (incr != 0) {
232 huff &= incr - 1;
233 huff += incr;
234 }
235 else
236 huff = 0;
237
238 /* go to next symbol, update count, le
239 sym++;
240 if (--(count[len]) == 0) {
241 if (len == max) break;
242 len = lens[work[sym]];
243 }
244
245 /* create new sub-table if needed */
246 if (len > root && (huff & mask) != low
247 /* if first time, transition to su
248 if (drop == 0)
249 drop = root;
250
251 /* increment past last table */
252 next += min; /* here mi
253
254 /* determine length of next table
255 curr = len - drop;
256 left = (int)(1 << curr);
257 while (curr + drop < max) {
258 left -= count[curr + drop];
259 if (left <= 0) break;
260 curr++;
261 left <<= 1;
262 }
263
264 /* check for enough space */
265 used += 1U << curr;
266 if (type == LENS && used >= ENOUGH
267 return 1;
268
269 /* point entry in root table to su
270 low = huff & mask;
271 (*table)[low].op = (unsigned char)
272 (*table)[low].bits = (unsigned cha
273 (*table)[low].val = (unsigned shor
274 }
275 }
276
277 /*
278 Fill in rest of table for incomplete co
279 loop above in incrementing huff for tab
280 len is equal to curr + drop, so there i
281 through high index bits. When the curr
282 drops back to the root table to fill in
283 */
284 this.op = (unsigned char)64;
285 this.bits = (unsigned char)(len - drop);
286 this.val = (unsigned short)0;
287 while (huff != 0) {
288 /* when done with sub-table, drop back
289 if (drop != 0 && (huff & mask) != low)
290 drop = 0;
291 len = root;
292 next = *table;
293 this.bits = (unsigned char)len;
294 }
295
296 /* put invalid code marker in table */
297 next[huff >> drop] = this;
298
299 /* backwards increment the len-bit cod
300 incr = 1U << (len - 1);
301 while (huff & incr)
302 incr >>= 1;
303 if (incr != 0) {
304 huff &= incr - 1;
305 huff += incr;
306 }
307 else
308 huff = 0;
309 }
310
311 /* set return parameters */
312 *table += used;
313 *bits = root;
314 return 0;
315 }
316
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.