[PATCH] lib/zlib*: cleanups
[linux-2.6.git] / lib / zlib_inflate / infblock.c
1 /* infblock.c -- interpret and process block types to last block
2  * Copyright (C) 1995-1998 Mark Adler
3  * For conditions of distribution and use, see copyright notice in zlib.h 
4  */
5
6 #include <linux/zutil.h>
7 #include "infblock.h"
8 #include "inftrees.h"
9 #include "infcodes.h"
10 #include "infutil.h"
11
12 struct inflate_codes_state;
13
14 /* simplify the use of the inflate_huft type with some defines */
15 #define exop word.what.Exop
16 #define bits word.what.Bits
17
18 /* Table for deflate from PKZIP's appnote.txt. */
19 static const uInt border[] = { /* Order of the bit length code lengths */
20         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
21
22 /*
23    Notes beyond the 1.93a appnote.txt:
24
25    1. Distance pointers never point before the beginning of the output
26       stream.
27    2. Distance pointers can point back across blocks, up to 32k away.
28    3. There is an implied maximum of 7 bits for the bit length table and
29       15 bits for the actual data.
30    4. If only one code exists, then it is encoded using one bit.  (Zero
31       would be more efficient, but perhaps a little confusing.)  If two
32       codes exist, they are coded using one bit each (0 and 1).
33    5. There is no way of sending zero distance codes--a dummy must be
34       sent if there are none.  (History: a pre 2.0 version of PKZIP would
35       store blocks with no distance codes, but this was discovered to be
36       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
37       zero distance codes, which is sent as one code of zero bits in
38       length.
39    6. There are up to 286 literal/length codes.  Code 256 represents the
40       end-of-block.  Note however that the static length tree defines
41       288 codes just to fill out the Huffman codes.  Codes 286 and 287
42       cannot be used though, since there is no length base or extra bits
43       defined for them.  Similarily, there are up to 30 distance codes.
44       However, static trees define 32 codes (all 5 bits) to fill out the
45       Huffman codes, but the last two had better not show up in the data.
46    7. Unzip can check dynamic Huffman blocks for complete code sets.
47       The exception is that a single code would not be complete (see #4).
48    8. The five bits following the block type is really the number of
49       literal codes sent minus 257.
50    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
51       (1+6+6).  Therefore, to output three times the length, you output
52       three codes (1+1+1), whereas to output four times the same length,
53       you only need two codes (1+3).  Hmm.
54   10. In the tree reconstruction algorithm, Code = Code + Increment
55       only if BitLength(i) is not zero.  (Pretty obvious.)
56   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
57   12. Note: length code 284 can represent 227-258, but length code 285
58       really is 258.  The last length deserves its own, short code
59       since it gets used a lot in very redundant files.  The length
60       258 is special since 258 - 3 (the min match length) is 255.
61   13. The literal/length and distance code bit lengths are read as a
62       single stream of lengths.  It is possible (and advantageous) for
63       a repeat code (16, 17, or 18) to go across the boundary between
64       the two sets of lengths.
65  */
66
67
68 void zlib_inflate_blocks_reset(
69         inflate_blocks_statef *s,
70         z_streamp z,
71         uLong *c
72 )
73 {
74   if (c != NULL)
75     *c = s->check;
76   if (s->mode == CODES)
77     zlib_inflate_codes_free(s->sub.decode.codes, z);
78   s->mode = TYPE;
79   s->bitk = 0;
80   s->bitb = 0;
81   s->read = s->write = s->window;
82   if (s->checkfn != NULL)
83     z->adler = s->check = (*s->checkfn)(0L, NULL, 0);
84 }
85
86 inflate_blocks_statef *zlib_inflate_blocks_new(
87         z_streamp z,
88         check_func c,
89         uInt w
90 )
91 {
92   inflate_blocks_statef *s;
93
94   s = &WS(z)->working_blocks_state;
95   s->hufts = WS(z)->working_hufts;
96   s->window = WS(z)->working_window;
97   s->end = s->window + w;
98   s->checkfn = c;
99   s->mode = TYPE;
100   zlib_inflate_blocks_reset(s, z, NULL);
101   return s;
102 }
103
104
105 int zlib_inflate_blocks(
106         inflate_blocks_statef *s,
107         z_streamp z,
108         int r
109 )
110 {
111   uInt t;               /* temporary storage */
112   uLong b;              /* bit buffer */
113   uInt k;               /* bits in bit buffer */
114   Byte *p;              /* input data pointer */
115   uInt n;               /* bytes available there */
116   Byte *q;              /* output window write pointer */
117   uInt m;               /* bytes to end of window or read pointer */
118
119   /* copy input/output information to locals (UPDATE macro restores) */
120   LOAD
121
122   /* process input based on current state */
123   while (1) switch (s->mode)
124   {
125     case TYPE:
126       NEEDBITS(3)
127       t = (uInt)b & 7;
128       s->last = t & 1;
129       switch (t >> 1)
130       {
131         case 0:                         /* stored */
132           DUMPBITS(3)
133           t = k & 7;                    /* go to byte boundary */
134           DUMPBITS(t)
135           s->mode = LENS;               /* get length of stored block */
136           break;
137         case 1:                         /* fixed */
138           {
139             uInt bl, bd;
140             inflate_huft *tl, *td;
141
142             zlib_inflate_trees_fixed(&bl, &bd, &tl, &td, s->hufts, z);
143             s->sub.decode.codes = zlib_inflate_codes_new(bl, bd, tl, td, z);
144             if (s->sub.decode.codes == NULL)
145             {
146               r = Z_MEM_ERROR;
147               LEAVE
148             }
149           }
150           DUMPBITS(3)
151           s->mode = CODES;
152           break;
153         case 2:                         /* dynamic */
154           DUMPBITS(3)
155           s->mode = TABLE;
156           break;
157         case 3:                         /* illegal */
158           DUMPBITS(3)
159           s->mode = B_BAD;
160           z->msg = (char*)"invalid block type";
161           r = Z_DATA_ERROR;
162           LEAVE
163       }
164       break;
165     case LENS:
166       NEEDBITS(32)
167       if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
168       {
169         s->mode = B_BAD;
170         z->msg = (char*)"invalid stored block lengths";
171         r = Z_DATA_ERROR;
172         LEAVE
173       }
174       s->sub.left = (uInt)b & 0xffff;
175       b = k = 0;                      /* dump bits */
176       s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
177       break;
178     case STORED:
179       if (n == 0)
180         LEAVE
181       NEEDOUT
182       t = s->sub.left;
183       if (t > n) t = n;
184       if (t > m) t = m;
185       memcpy(q, p, t);
186       p += t;  n -= t;
187       q += t;  m -= t;
188       if ((s->sub.left -= t) != 0)
189         break;
190       s->mode = s->last ? DRY : TYPE;
191       break;
192     case TABLE:
193       NEEDBITS(14)
194       s->sub.trees.table = t = (uInt)b & 0x3fff;
195 #ifndef PKZIP_BUG_WORKAROUND
196       if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
197       {
198         s->mode = B_BAD;
199         z->msg = (char*)"too many length or distance symbols";
200         r = Z_DATA_ERROR;
201         LEAVE
202       }
203 #endif
204       {
205         s->sub.trees.blens = WS(z)->working_blens;
206       }
207       DUMPBITS(14)
208       s->sub.trees.index = 0;
209       s->mode = BTREE;
210     case BTREE:
211       while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
212       {
213         NEEDBITS(3)
214         s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
215         DUMPBITS(3)
216       }
217       while (s->sub.trees.index < 19)
218         s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
219       s->sub.trees.bb = 7;
220       t = zlib_inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
221                                   &s->sub.trees.tb, s->hufts, z);
222       if (t != Z_OK)
223       {
224         r = t;
225         if (r == Z_DATA_ERROR)
226           s->mode = B_BAD;
227         LEAVE
228       }
229       s->sub.trees.index = 0;
230       s->mode = DTREE;
231     case DTREE:
232       while (t = s->sub.trees.table,
233              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
234       {
235         inflate_huft *h;
236         uInt i, j, c;
237
238         t = s->sub.trees.bb;
239         NEEDBITS(t)
240         h = s->sub.trees.tb + ((uInt)b & zlib_inflate_mask[t]);
241         t = h->bits;
242         c = h->base;
243         if (c < 16)
244         {
245           DUMPBITS(t)
246           s->sub.trees.blens[s->sub.trees.index++] = c;
247         }
248         else /* c == 16..18 */
249         {
250           i = c == 18 ? 7 : c - 14;
251           j = c == 18 ? 11 : 3;
252           NEEDBITS(t + i)
253           DUMPBITS(t)
254           j += (uInt)b & zlib_inflate_mask[i];
255           DUMPBITS(i)
256           i = s->sub.trees.index;
257           t = s->sub.trees.table;
258           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
259               (c == 16 && i < 1))
260           {
261             s->mode = B_BAD;
262             z->msg = (char*)"invalid bit length repeat";
263             r = Z_DATA_ERROR;
264             LEAVE
265           }
266           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
267           do {
268             s->sub.trees.blens[i++] = c;
269           } while (--j);
270           s->sub.trees.index = i;
271         }
272       }
273       s->sub.trees.tb = NULL;
274       {
275         uInt bl, bd;
276         inflate_huft *tl, *td;
277         inflate_codes_statef *c;
278
279         bl = 9;         /* must be <= 9 for lookahead assumptions */
280         bd = 6;         /* must be <= 9 for lookahead assumptions */
281         t = s->sub.trees.table;
282         t = zlib_inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
283                                        s->sub.trees.blens, &bl, &bd, &tl, &td,
284                                        s->hufts, z);
285         if (t != Z_OK)
286         {
287           if (t == (uInt)Z_DATA_ERROR)
288             s->mode = B_BAD;
289           r = t;
290           LEAVE
291         }
292         if ((c = zlib_inflate_codes_new(bl, bd, tl, td, z)) == NULL)
293         {
294           r = Z_MEM_ERROR;
295           LEAVE
296         }
297         s->sub.decode.codes = c;
298       }
299       s->mode = CODES;
300     case CODES:
301       UPDATE
302       if ((r = zlib_inflate_codes(s, z, r)) != Z_STREAM_END)
303         return zlib_inflate_flush(s, z, r);
304       r = Z_OK;
305       zlib_inflate_codes_free(s->sub.decode.codes, z);
306       LOAD
307       if (!s->last)
308       {
309         s->mode = TYPE;
310         break;
311       }
312       s->mode = DRY;
313     case DRY:
314       FLUSH
315       if (s->read != s->write)
316         LEAVE
317       s->mode = B_DONE;
318     case B_DONE:
319       r = Z_STREAM_END;
320       LEAVE
321     case B_BAD:
322       r = Z_DATA_ERROR;
323       LEAVE
324     default:
325       r = Z_STREAM_ERROR;
326       LEAVE
327   }
328 }
329
330
331 int zlib_inflate_blocks_free(
332         inflate_blocks_statef *s,
333         z_streamp z
334 )
335 {
336   zlib_inflate_blocks_reset(s, z, NULL);
337   return Z_OK;
338 }
339
340
341 #if 0
342 void zlib_inflate_set_dictionary(
343         inflate_blocks_statef *s,
344         const Byte *d,
345         uInt  n
346 )
347 {
348   memcpy(s->window, d, n);
349   s->read = s->write = s->window + n;
350 }
351 #endif  /*  0  */
352
353
354 /* Returns true if inflate is currently at the end of a block generated
355  * by Z_SYNC_FLUSH or Z_FULL_FLUSH. 
356  * IN assertion: s != NULL
357  */
358 #if 0
359 int zlib_inflate_blocks_sync_point(
360         inflate_blocks_statef *s
361 )
362 {
363   return s->mode == LENS;
364 }
365 #endif  /*  0  */