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 "zutil.h"
7#include "infblock.h"
8#include "inftrees.h"
9#include "infcodes.h"
10#include "infutil.h"
11
12struct inflate_codes_state {int dummy;}; /* for buggy compilers */
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. */
19local 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
68void inflate_blocks_reset(s, z, c)
69inflate_blocks_statef *s;
70z_streamp z;
71uLongf *c;
72{
73  if (c != Z_NULL)
74    *c = s->check;
75  if (s->mode == BTREE || s->mode == DTREE)
76    ZFREE(z, s->sub.trees.blens);
77  if (s->mode == CODES)
78    inflate_codes_free(s->sub.decode.codes, z);
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, (const Bytef *)Z_NULL, 0);
85  Tracev((stderr, "inflate:   blocks reset\n"));
86}
87
88
89inflate_blocks_statef *inflate_blocks_new(z, c, w)
90z_streamp z;
91check_func c;
92uInt 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->hufts =
100       (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
101  {
102    ZFREE(z, s);
103    return Z_NULL;
104  }
105  if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
106  {
107    ZFREE(z, s->hufts);
108    ZFREE(z, s);
109    return Z_NULL;
110  }
111  s->end = s->window + w;
112  s->checkfn = c;
113  s->mode = TYPE;
114  Tracev((stderr, "inflate:   blocks allocated\n"));
115  inflate_blocks_reset(s, z, Z_NULL);
116  return s;
117}
118
119
120int inflate_blocks(s, z, r)
121inflate_blocks_statef *s;
122z_streamp z;
123int r;
124{
125  uInt t;               /* temporary storage */
126  uLong b;              /* bit buffer */
127  uInt k;               /* bits in bit buffer */
128  Bytef *p;             /* input data pointer */
129  uInt n;               /* bytes available there */
130  Bytef *q;             /* output window write pointer */
131  uInt m;               /* bytes to end of window or read pointer */
132
133  /* copy input/output information to locals (UPDATE macro restores) */
134  LOAD
135
136  /* process input based on current state */
137  while (1) switch (s->mode)
138  {
139    case TYPE:
140      NEEDBITS(3)
141      t = (uInt)b & 7;
142      s->last = t & 1;
143      switch (t >> 1)
144      {
145        case 0:                         /* stored */
146          Tracev((stderr, "inflate:     stored block%s\n",
147                 s->last ? " (last)" : ""));
148          DUMPBITS(3)
149          t = k & 7;                    /* go to byte boundary */
150          DUMPBITS(t)
151          s->mode = LENS;               /* get length of stored block */
152          break;
153        case 1:                         /* fixed */
154          Tracev((stderr, "inflate:     fixed codes block%s\n",
155                 s->last ? " (last)" : ""));
156          {
157            uInt bl, bd;
158            inflate_huft *tl, *td;
159
160            inflate_trees_fixed(&bl, &bd, &tl, &td, z);
161            s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
162            if (s->sub.decode.codes == Z_NULL)
163            {
164              r = Z_MEM_ERROR;
165              LEAVE
166            }
167          }
168          DUMPBITS(3)
169          s->mode = CODES;
170          break;
171        case 2:                         /* dynamic */
172          Tracev((stderr, "inflate:     dynamic codes block%s\n",
173                 s->last ? " (last)" : ""));
174          DUMPBITS(3)
175          s->mode = TABLE;
176          break;
177        case 3:                         /* illegal */
178          DUMPBITS(3)
179          s->mode = BAD;
180          z->msg = (char*)"invalid block type";
181          r = Z_DATA_ERROR;
182          LEAVE
183      }
184      break;
185    case LENS:
186      NEEDBITS(32)
187      if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
188      {
189        s->mode = BAD;
190        z->msg = (char*)"invalid stored block lengths";
191        r = Z_DATA_ERROR;
192        LEAVE
193      }
194      s->sub.left = (uInt)b & 0xffff;
195      b = k = 0;                      /* dump bits */
196      Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
197      s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
198      break;
199    case STORED:
200      if (n == 0)
201        LEAVE
202      NEEDOUT
203      t = s->sub.left;
204      if (t > n) t = n;
205      if (t > m) t = m;
206      zmemcpy(q, p, t);
207      p += t;  n -= t;
208      q += t;  m -= t;
209      if ((s->sub.left -= t) != 0)
210        break;
211      Tracev((stderr, "inflate:       stored end, %lu total out\n",
212              z->total_out + (q >= s->read ? q - s->read :
213              (s->end - s->read) + (q - s->window))));
214      s->mode = s->last ? DRY : TYPE;
215      break;
216    case TABLE:
217      NEEDBITS(14)
218      s->sub.trees.table = t = (uInt)b & 0x3fff;
219#ifndef PKZIP_BUG_WORKAROUND
220      if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
221      {
222        s->mode = BAD;
223        z->msg = (char*)"too many length or distance symbols";
224        r = Z_DATA_ERROR;
225        LEAVE
226      }
227#endif
228      t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
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, s->hufts, z);
250      if (t != Z_OK)
251      {
252        ZFREE(z, s->sub.trees.blens);
253        r = t;
254        if (r == Z_DATA_ERROR)
255          s->mode = BAD;
256        LEAVE
257      }
258      s->sub.trees.index = 0;
259      Tracev((stderr, "inflate:       bits tree ok\n"));
260      s->mode = DTREE;
261    case DTREE:
262      while (t = s->sub.trees.table,
263             s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
264      {
265        inflate_huft *h;
266        uInt i, j, c;
267
268        t = s->sub.trees.bb;
269        NEEDBITS(t)
270        h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
271        t = h->bits;
272        c = h->base;
273        if (c < 16)
274        {
275          DUMPBITS(t)
276          s->sub.trees.blens[s->sub.trees.index++] = c;
277        }
278        else /* c == 16..18 */
279        {
280          i = c == 18 ? 7 : c - 14;
281          j = c == 18 ? 11 : 3;
282          NEEDBITS(t + i)
283          DUMPBITS(t)
284          j += (uInt)b & inflate_mask[i];
285          DUMPBITS(i)
286          i = s->sub.trees.index;
287          t = s->sub.trees.table;
288          if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
289              (c == 16 && i < 1))
290          {
291            ZFREE(z, s->sub.trees.blens);
292            s->mode = BAD;
293            z->msg = (char*)"invalid bit length repeat";
294            r = Z_DATA_ERROR;
295            LEAVE
296          }
297          c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
298          do {
299            s->sub.trees.blens[i++] = c;
300          } while (--j);
301          s->sub.trees.index = i;
302        }
303      }
304      s->sub.trees.tb = Z_NULL;
305      {
306        uInt bl, bd;
307        inflate_huft *tl, *td;
308        inflate_codes_statef *c;
309
310        bl = 9;         /* must be <= 9 for lookahead assumptions */
311        bd = 6;         /* must be <= 9 for lookahead assumptions */
312        t = s->sub.trees.table;
313        t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
314                                  s->sub.trees.blens, &bl, &bd, &tl, &td,
315                                  s->hufts, z);
316        ZFREE(z, s->sub.trees.blens);
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\n"));
325        if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
326        {
327          r = Z_MEM_ERROR;
328          LEAVE
329        }
330        s->sub.decode.codes = c;
331      }
332      s->mode = CODES;
333    case CODES:
334      UPDATE
335      if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
336        return inflate_flush(s, z, r);
337      r = Z_OK;
338      inflate_codes_free(s->sub.decode.codes, z);
339      LOAD
340      Tracev((stderr, "inflate:       codes end, %lu total out\n",
341              z->total_out + (q >= s->read ? q - s->read :
342              (s->end - s->read) + (q - s->window))));
343      if (!s->last)
344      {
345        s->mode = TYPE;
346        break;
347      }
348      s->mode = DRY;
349    case DRY:
350      FLUSH
351      if (s->read != s->write)
352        LEAVE
353      s->mode = DONE;
354    case DONE:
355      r = Z_STREAM_END;
356      LEAVE
357    case BAD:
358      r = Z_DATA_ERROR;
359      LEAVE
360    default:
361      r = Z_STREAM_ERROR;
362      LEAVE
363  }
364}
365
366
367int inflate_blocks_free(s, z)
368inflate_blocks_statef *s;
369z_streamp z;
370{
371  inflate_blocks_reset(s, z, Z_NULL);
372  ZFREE(z, s->window);
373  ZFREE(z, s->hufts);
374  ZFREE(z, s);
375  Tracev((stderr, "inflate:   blocks freed\n"));
376  return Z_OK;
377}
378
379
380void inflate_set_dictionary(s, d, n)
381inflate_blocks_statef *s;
382const Bytef *d;
383uInt  n;
384{
385  zmemcpy(s->window, d, n);
386  s->read = s->write = s->window + n;
387}
388
389
390/* Returns true if inflate is currently at the end of a block generated
391 * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
392 * IN assertion: s != Z_NULL
393 */
394int inflate_blocks_sync_point(s)
395inflate_blocks_statef *s;
396{
397  return s->mode == LENS;
398}
399