Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
inftrees.c
Go to the documentation of this file.
1 /* inftrees.c -- generate Huffman trees for efficient decoding
2  * Copyright (C) 1995-2005 Mark Adler
3  * For conditions of distribution and use, see copyright notice in zlib.h
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 provided canonical Huffman code.
13  The code lengths are lens[0..codes-1]. The result starts at *table,
14  whose indices are 0..2^bits-1. work is a writable array of at least
15  lens shorts, which is used as a work area. type is the type of code
16  to be generated, CODES, LENS, or DISTS. On return, zero is success,
17  -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
18  on return points to the next available entry's address. bits is the
19  requested root table index bits, and on return it is the actual root
20  table index bits. It will differ if the request is greater than the
21  longest code or if it is less than the shortest code.
22  */
23 int zlib_inflate_table(codetype type, unsigned short *lens, unsigned codes,
24  code **table, unsigned *bits, unsigned short *work)
25 {
26  unsigned len; /* a code's length in bits */
27  unsigned sym; /* index of code symbols */
28  unsigned min, max; /* minimum and maximum code lengths */
29  unsigned root; /* number of index bits for root table */
30  unsigned curr; /* number of index bits for current table */
31  unsigned drop; /* code bits to drop for sub-table */
32  int left; /* number of prefix codes available */
33  unsigned used; /* code entries in table used */
34  unsigned huff; /* Huffman code */
35  unsigned incr; /* for incrementing code, index */
36  unsigned fill; /* index for replicating entries */
37  unsigned low; /* low bits for current root entry */
38  unsigned mask; /* mask for low root bits */
39  code this; /* table entry for duplication */
40  code *next; /* next available space in table */
41  const unsigned short *base; /* base value table to use */
42  const unsigned short *extra; /* extra bits table to use */
43  int end; /* use base and extra for symbol > end */
44  unsigned short count[MAXBITS+1]; /* number of codes of each length */
45  unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
46  static const unsigned short lbase[31] = { /* Length codes 257..285 base */
47  3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
48  35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
49  static const unsigned short lext[31] = { /* Length codes 257..285 extra */
50  16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
51  19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
52  static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
53  1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
54  257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
55  8193, 12289, 16385, 24577, 0, 0};
56  static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
57  16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
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 a canonical Huffman code. The
63  code lengths are lens[0..codes-1]. Each length corresponds to the
64  symbols 0..codes-1. The Huffman code is generated by first sorting the
65  symbols by length from short to long, and retaining the symbol order
66  for codes with equal lengths. Then the code starts with all zero bits
67  for the first code of the shortest length, and the codes are integer
68  increments for the same length, and zeros are appended as the length
69  increases. For the deflate format, these bits are stored backwards
70  from their more natural integer increment ordering, and so when the
71  decoding tables are built in the large loop below, the integer codes
72  are incremented backwards.
73 
74  This routine assumes, but does not check, that all of the entries in
75  lens[] are in the range 0..MAXBITS. The caller must assure this.
76  1..MAXBITS is interpreted as that code length. zero means that that
77  symbol does not occur in this code.
78 
79  The codes are sorted by computing a count of codes for each length,
80  creating from that a table of starting indices for each length in the
81  sorted table, and then entering the symbols in order in the sorted
82  table. The sorted table is work[], with that space being provided by
83  the caller.
84 
85  The length counts are used for other purposes as well, i.e. finding
86  the minimum and maximum length codes, determining if there are any
87  codes at all, checking for a valid set of lengths, and looking ahead
88  at length counts to determine sub-table sizes when building the
89  decoding tables.
90  */
91 
92  /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
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 within code lengths */
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 symbols to code at all */
104  this.op = (unsigned char)64; /* invalid code marker */
105  this.bits = (unsigned char)1;
106  this.val = (unsigned short)0;
107  *(*table)++ = this; /* make a table to force an error */
108  *(*table)++ = this;
109  *bits = 1;
110  return 0; /* no symbols, but wait for decoding to report error */
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 incomplete set of lengths */
117  left = 1;
118  for (len = 1; len <= MAXBITS; len++) {
119  left <<= 1;
120  left -= count[len];
121  if (left < 0) return -1; /* over-subscribed */
122  }
123  if (left > 0 && (type == CODES || max != 1))
124  return -1; /* incomplete set */
125 
126  /* generate offsets into symbol table for each length for sorting */
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 within each length */
132  for (sym = 0; sym < codes; sym++)
133  if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
134 
135  /*
136  Create and fill in decoding tables. In this loop, the table being
137  filled is at next and has curr index bits. The code being used is huff
138  with length len. That code is converted to an index by dropping drop
139  bits off of the bottom. For codes where len is less than drop + curr,
140  those top drop + curr - len bits are incremented through all values to
141  fill the table with replicated entries.
142 
143  root is the number of index bits for the root table. When len exceeds
144  root, sub-tables are created pointed to by the root entry with an index
145  of the low root bits of huff. This is saved in low to check for when a
146  new sub-table should be started. drop is zero when the root table is
147  being filled, and drop is root when sub-tables are being filled.
148 
149  When a new sub-table is needed, it is necessary to look ahead in the
150  code lengths to determine what size sub-table is needed. The length
151  counts are used for this, and so count[] is decremented as codes are
152  entered in the tables.
153 
154  used keeps track of how many table entries have been allocated from the
155  provided *table space. It is checked when a LENS table is being made
156  against the space in *table, ENOUGH, minus the maximum space needed by
157  the worst case distance code, MAXD. This should never happen, but the
158  sufficiency of ENOUGH has not been proven exhaustively, hence the check.
159  This assumes that when type == LENS, bits == 9.
160 
161  sym increments through all symbols, and the loop terminates when
162  all codes of length max, i.e. all codes, have been processed. This
163  routine permits incomplete codes, so another loop after this one fills
164  in the rest of the decoding tables with invalid code markers.
165  */
166 
167  /* set up for code type */
168  switch (type) {
169  case CODES:
170  base = extra = work; /* dummy value--not used */
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 code */
188  sym = 0; /* starting code symbol */
189  len = min; /* starting code length */
190  next = *table; /* current table to fill in */
191  curr = root; /* current table index bits */
192  drop = 0; /* current bits to drop from code for index */
193  low = (unsigned)(-1); /* trigger new sub-table when len > root */
194  used = 1U << root; /* use root table entries */
195  mask = used - 1; /* mask for comparing low */
196 
197  /* check available table space */
198  if (type == LENS && used >= ENOUGH - MAXD)
199  return 1;
200 
201  /* process all codes and make table entries */
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[work[sym]]);
211  this.val = base[work[sym]];
212  }
213  else {
214  this.op = (unsigned char)(32 + 64); /* end of block */
215  this.val = 0;
216  }
217 
218  /* replicate for those indices with low len bits equal to huff */
219  incr = 1U << (len - drop);
220  fill = 1U << curr;
221  min = fill; /* save offset to next table */
222  do {
223  fill -= incr;
224  next[(huff >> drop) + fill] = this;
225  } while (fill != 0);
226 
227  /* backwards increment the len-bit code huff */
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, len */
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 sub-tables */
248  if (drop == 0)
249  drop = root;
250 
251  /* increment past last table */
252  next += min; /* here min is 1 << curr */
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 - MAXD)
267  return 1;
268 
269  /* point entry in root table to sub-table */
270  low = huff & mask;
271  (*table)[low].op = (unsigned char)curr;
272  (*table)[low].bits = (unsigned char)root;
273  (*table)[low].val = (unsigned short)(next - *table);
274  }
275  }
276 
277  /*
278  Fill in rest of table for incomplete codes. This loop is similar to the
279  loop above in incrementing huff for table indices. It is assumed that
280  len is equal to curr + drop, so there is no loop needed to increment
281  through high index bits. When the current sub-table is filled, the loop
282  drops back to the root table to fill in any remaining entries there.
283  */
284  this.op = (unsigned char)64; /* invalid code marker */
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 to root table */
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 code huff */
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 }