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