← Back to branch summary

~etc-pgh-launchpad/wildpockets/trunk

« back to all changes in this revision

Viewing changes to freetype2/src/gzip/infblock.c

  • Committer: etc-pgh-launchpad at cmu
  • Date: 2010-11-30 20:56:30 UTC
  • Revision ID: etc-pgh-launchpad@lists.andrew.cmu.edu-20101130205630-0blbkcz28ovjl8wj
Committing the Wild Pockets code base to Launchpad.

Show diffs side-by-side

added added

removed removed

Lines of Context:
freetype2/src/gzip/infblock.c
 
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
 
 
13
/* simplify the use of the inflate_huft type with some defines */
 
14
#define exop word.what.Exop
 
15
#define bits word.what.Bits
 
16
 
 
17
/* Table for deflate from PKZIP's appnote.txt. */
 
18
local const uInt border[] = { /* Order of the bit length code lengths */
 
19
        16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
 
20
 
 
21
/*
 
22
   Notes beyond the 1.93a appnote.txt:
 
23
 
 
24
   1. Distance pointers never point before the beginning of the output
 
25
      stream.
 
26
   2. Distance pointers can point back across blocks, up to 32k away.
 
27
   3. There is an implied maximum of 7 bits for the bit length table and
 
28
      15 bits for the actual data.
 
29
   4. If only one code exists, then it is encoded using one bit.  (Zero
 
30
      would be more efficient, but perhaps a little confusing.)  If two
 
31
      codes exist, they are coded using one bit each (0 and 1).
 
32
   5. There is no way of sending zero distance codes--a dummy must be
 
33
      sent if there are none.  (History: a pre 2.0 version of PKZIP would
 
34
      store blocks with no distance codes, but this was discovered to be
 
35
      too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
 
36
      zero distance codes, which is sent as one code of zero bits in
 
37
      length.
 
38
   6. There are up to 286 literal/length codes.  Code 256 represents the
 
39
      end-of-block.  Note however that the static length tree defines
 
40
      288 codes just to fill out the Huffman codes.  Codes 286 and 287
 
41
      cannot be used though, since there is no length base or extra bits
 
42
      defined for them.  Similarily, there are up to 30 distance codes.
 
43
      However, static trees define 32 codes (all 5 bits) to fill out the
 
44
      Huffman codes, but the last two had better not show up in the data.
 
45
   7. Unzip can check dynamic Huffman blocks for complete code sets.
 
46
      The exception is that a single code would not be complete (see #4).
 
47
   8. The five bits following the block type is really the number of
 
48
      literal codes sent minus 257.
 
49
   9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
 
50
      (1+6+6).  Therefore, to output three times the length, you output
 
51
      three codes (1+1+1), whereas to output four times the same length,
 
52
      you only need two codes (1+3).  Hmm.
 
53
  10. In the tree reconstruction algorithm, Code = Code + Increment
 
54
      only if BitLength(i) is not zero.  (Pretty obvious.)
 
55
  11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
 
56
  12. Note: length code 284 can represent 227-258, but length code 285
 
57
      really is 258.  The last length deserves its own, short code
 
58
      since it gets used a lot in very redundant files.  The length
 
59
      258 is special since 258 - 3 (the min match length) is 255.
 
60
  13. The literal/length and distance code bit lengths are read as a
 
61
      single stream of lengths.  It is possible (and advantageous) for
 
62
      a repeat code (16, 17, or 18) to go across the boundary between
 
63
      the two sets of lengths.
 
64
 */
 
65
 
 
66
 
 
67
local void inflate_blocks_reset( /* s, z, c) */
 
68
inflate_blocks_statef *s,
 
69
z_streamp z,
 
70
uLongf *c )
 
71
{
 
72
  if (c != Z_NULL)
 
73
    *c = s->check;
 
74
  if (s->mode == BTREE || s->mode == DTREE)
 
75
    ZFREE(z, s->sub.trees.blens);
 
76
  if (s->mode == CODES)
 
77
    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 != Z_NULL)
 
83
    z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0);
 
84
  Tracev((stderr, "inflate:   blocks reset\n"));
 
85
}
 
86
 
 
87
 
 
88
local inflate_blocks_statef *inflate_blocks_new( /* z, c, w) */
 
89
z_streamp z,
 
90
check_func c,
 
91
uInt w )
 
92
{
 
93
  inflate_blocks_statef *s;
 
94
 
 
95
  if ((s = (inflate_blocks_statef *)ZALLOC
 
96
       (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
 
97
    return s;
 
98
  if ((s->hufts =
 
99
       (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
 
100
  {
 
101
    ZFREE(z, s);
 
102
    return Z_NULL;
 
103
  }
 
104
  if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
 
105
  {
 
106
    ZFREE(z, s->hufts);
 
107
    ZFREE(z, s);
 
108
    return Z_NULL;
 
109
  }
 
110
  s->end = s->window + w;
 
111
  s->checkfn = c;
 
112
  s->mode = TYPE;
 
113
  Tracev((stderr, "inflate:   blocks allocated\n"));
 
114
  inflate_blocks_reset(s, z, Z_NULL);
 
115
  return s;
 
116
}
 
117
 
 
118
 
 
119
local int inflate_blocks( /* s, z, r) */
 
120
inflate_blocks_statef *s,
 
121
z_streamp z,
 
122
int r )
 
123
{
 
124
  uInt t;               /* temporary storage */
 
125
  uLong b;              /* bit buffer */
 
126
  uInt k;               /* bits in bit buffer */
 
127
  Bytef *p;             /* input data pointer */
 
128
  uInt n;               /* bytes available there */
 
129
  Bytef *q;             /* output window write pointer */
 
130
  uInt m;               /* bytes to end of window or read pointer */
 
131
 
 
132
  /* copy input/output information to locals (UPDATE macro restores) */
 
133
  LOAD
 
134
 
 
135
  /* process input based on current state */
 
136
  while (1) switch (s->mode)
 
137
  {
 
138
    case TYPE:
 
139
      NEEDBITS(3)
 
140
      t = (uInt)b & 7;
 
141
      s->last = t & 1;
 
142
      switch (t >> 1)
 
143
      {
 
144
        case 0:                         /* stored */
 
145
          Tracev((stderr, "inflate:     stored block%s\n",
 
146
                 s->last ? " (last)" : ""));
 
147
          DUMPBITS(3)
 
148
          t = k & 7;                    /* go to byte boundary */
 
149
          DUMPBITS(t)
 
150
          s->mode = LENS;               /* get length of stored block */
 
151
          break;
 
152
        case 1:                         /* fixed */
 
153
          Tracev((stderr, "inflate:     fixed codes block%s\n",
 
154
                 s->last ? " (last)" : ""));
 
155
          {
 
156
            uInt bl, bd;
 
157
            inflate_huft *tl, *td;
 
158
 
 
159
            inflate_trees_fixed(&bl, &bd, (const inflate_huft**)&tl,
 
160
                                          (const inflate_huft**)&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
#ifdef NEED_DUMMY_RETURN
 
370
  return 0;
 
371
#endif
 
372
}
 
373
 
 
374
 
 
375
local int inflate_blocks_free( /* s, z) */
 
376
inflate_blocks_statef *s,
 
377
z_streamp z )
 
378
{
 
379
  inflate_blocks_reset(s, z, Z_NULL);
 
380
  ZFREE(z, s->window);
 
381
  ZFREE(z, s->hufts);
 
382
  ZFREE(z, s);
 
383
  Tracev((stderr, "inflate:   blocks freed\n"));
 
384
  return Z_OK;
 
385
}
 
386
 
 
387