Subversion Repositories shark

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
107 pj 1
/* infblock.c -- interpret and process block types to last block
2
 * Copyright (C) 1995-2002 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
/* 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
local 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 inflate_blocks_reset(s, z, c)
69
inflate_blocks_statef *s;
70
z_streamp z;
71
uLongf *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
 
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->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
 
120
int inflate_blocks(s, z, r)
121
inflate_blocks_statef *s;
122
z_streamp z;
123
int 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
        r = t;
253
        if (r == Z_DATA_ERROR)
254
        {
255
          ZFREE(z, s->sub.trees.blens);
256
          s->mode = BAD;
257
        }
258
        LEAVE
259
      }
260
      s->sub.trees.index = 0;
261
      Tracev((stderr, "inflate:       bits tree ok\n"));
262
      s->mode = DTREE;
263
    case DTREE:
264
      while (t = s->sub.trees.table,
265
             s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
266
      {
267
        inflate_huft *h;
268
        uInt i, j, c;
269
 
270
        t = s->sub.trees.bb;
271
        NEEDBITS(t)
272
        h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
273
        t = h->bits;
274
        c = h->base;
275
        if (c < 16)
276
        {
277
          DUMPBITS(t)
278
          s->sub.trees.blens[s->sub.trees.index++] = c;
279
        }
280
        else /* c == 16..18 */
281
        {
282
          i = c == 18 ? 7 : c - 14;
283
          j = c == 18 ? 11 : 3;
284
          NEEDBITS(t + i)
285
          DUMPBITS(t)
286
          j += (uInt)b & inflate_mask[i];
287
          DUMPBITS(i)
288
          i = s->sub.trees.index;
289
          t = s->sub.trees.table;
290
          if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
291
              (c == 16 && i < 1))
292
          {
293
            ZFREE(z, s->sub.trees.blens);
294
            s->mode = BAD;
295
            z->msg = (char*)"invalid bit length repeat";
296
            r = Z_DATA_ERROR;
297
            LEAVE
298
          }
299
          c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
300
          do {
301
            s->sub.trees.blens[i++] = c;
302
          } while (--j);
303
          s->sub.trees.index = i;
304
        }
305
      }
306
      s->sub.trees.tb = Z_NULL;
307
      {
308
        uInt bl, bd;
309
        inflate_huft *tl, *td;
310
        inflate_codes_statef *c;
311
 
312
        bl = 9;         /* must be <= 9 for lookahead assumptions */
313
        bd = 6;         /* must be <= 9 for lookahead assumptions */
314
        t = s->sub.trees.table;
315
        t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
316
                                  s->sub.trees.blens, &bl, &bd, &tl, &td,
317
                                  s->hufts, z);
318
        if (t != Z_OK)
319
        {
320
          if (t == (uInt)Z_DATA_ERROR)
321
          {
322
            ZFREE(z, s->sub.trees.blens);
323
            s->mode = BAD;
324
          }
325
          r = t;
326
          LEAVE
327
        }
328
        Tracev((stderr, "inflate:       trees ok\n"));
329
        if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
330
        {
331
          r = Z_MEM_ERROR;
332
          LEAVE
333
        }
334
        s->sub.decode.codes = c;
335
      }
336
      ZFREE(z, s->sub.trees.blens);
337
      s->mode = CODES;
338
    case CODES:
339
      UPDATE
340
      if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
341
        return inflate_flush(s, z, r);
342
      r = Z_OK;
343
      inflate_codes_free(s->sub.decode.codes, z);
344
      LOAD
345
      Tracev((stderr, "inflate:       codes end, %lu total out\n",
346
              z->total_out + (q >= s->read ? q - s->read :
347
              (s->end - s->read) + (q - s->window))));
348
      if (!s->last)
349
      {
350
        s->mode = TYPE;
351
        break;
352
      }
353
      s->mode = DRY;
354
    case DRY:
355
      FLUSH
356
      if (s->read != s->write)
357
        LEAVE
358
      s->mode = DONE;
359
    case DONE:
360
      r = Z_STREAM_END;
361
      LEAVE
362
    case BAD:
363
      r = Z_DATA_ERROR;
364
      LEAVE
365
    default:
366
      r = Z_STREAM_ERROR;
367
      LEAVE
368
  }
369
}
370
 
371
 
372
int inflate_blocks_free(s, z)
373
inflate_blocks_statef *s;
374
z_streamp z;
375
{
376
  inflate_blocks_reset(s, z, Z_NULL);
377
  ZFREE(z, s->window);
378
  ZFREE(z, s->hufts);
379
  ZFREE(z, s);
380
  Tracev((stderr, "inflate:   blocks freed\n"));
381
  return Z_OK;
382
}
383
 
384
 
385
void inflate_set_dictionary(s, d, n)
386
inflate_blocks_statef *s;
387
const Bytef *d;
388
uInt  n;
389
{
390
  zmemcpy(s->window, d, n);
391
  s->read = s->write = s->window + n;
392
}
393
 
394
 
395
/* Returns true if inflate is currently at the end of a block generated
396
 * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
397
 * IN assertion: s != Z_NULL
398
 */
399
int inflate_blocks_sync_point(s)
400
inflate_blocks_statef *s;
401
{
402
  return s->mode == LENS;
403
}