OpenCores
URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [rc203soc/] [sw/] [uClinux/] [lib/] [inflate.c] - Blame information for rev 1777

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 1634 jcastillo
#define DEBG(x)
2
#define DEBG1(x)
3
/* inflate.c -- Not copyrighted 1992 by Mark Adler
4
   version c10p1, 10 January 1993 */
5
 
6
/*
7
 * Adapted for booting Linux by Hannu Savolainen 1993
8
 * based on gzip-1.0.3
9
 */
10
 
11
/*
12
   Inflate deflated (PKZIP's method 8 compressed) data.  The compression
13
   method searches for as much of the current string of bytes (up to a
14
   length of 258) in the previous 32K bytes.  If it doesn't find any
15
   matches (of at least length 3), it codes the next byte.  Otherwise, it
16
   codes the length of the matched string and its distance backwards from
17
   the current position.  There is a single Huffman code that codes both
18
   single bytes (called "literals") and match lengths.  A second Huffman
19
   code codes the distance information, which follows a length code.  Each
20
   length or distance code actually represents a base value and a number
21
   of "extra" (sometimes zero) bits to get to add to the base value.  At
22
   the end of each deflated block is a special end-of-block (EOB) literal/
23
   length code.  The decoding process is basically: get a literal/length
24
   code; if EOB then done; if a literal, emit the decoded byte; if a
25
   length then get the distance and emit the referred-to bytes from the
26
   sliding window of previously emitted data.
27
 
28
   There are (currently) three kinds of inflate blocks: stored, fixed, and
29
   dynamic.  The compressor deals with some chunk of data at a time, and
30
   decides which method to use on a chunk-by-chunk basis.  A chunk might
31
   typically be 32K or 64K.  If the chunk is uncompressible, then the
32
   "stored" method is used.  In this case, the bytes are simply stored as
33
   is, eight bits per byte, with none of the above coding.  The bytes are
34
   preceded by a count, since there is no longer an EOB code.
35
 
36
   If the data is compressible, then either the fixed or dynamic methods
37
   are used.  In the dynamic method, the compressed data is preceded by
38
   an encoding of the literal/length and distance Huffman codes that are
39
   to be used to decode this block.  The representation is itself Huffman
40
   coded, and so is preceded by a description of that code.  These code
41
   descriptions take up a little space, and so for small blocks, there is
42
   a predefined set of codes, called the fixed codes.  The fixed method is
43
   used if the block codes up smaller that way (usually for quite small
44
   chunks), otherwise the dynamic method is used.  In the latter case, the
45
   codes are customized to the probabilities in the current block, and so
46
   can code it much better than the pre-determined fixed codes.
47
 
48
   The Huffman codes themselves are decoded using a multi-level table
49
   lookup, in order to maximize the speed of decoding plus the speed of
50
   building the decoding tables.  See the comments below that precede the
51
   lbits and dbits tuning parameters.
52
 */
53
 
54
 
55
/*
56
   Notes beyond the 1.93a appnote.txt:
57
 
58
   1. Distance pointers never point before the beginning of the output
59
      stream.
60
   2. Distance pointers can point back across blocks, up to 32k away.
61
   3. There is an implied maximum of 7 bits for the bit length table and
62
      15 bits for the actual data.
63
   4. If only one code exists, then it is encoded using one bit.  (Zero
64
      would be more efficient, but perhaps a little confusing.)  If two
65
      codes exist, they are coded using one bit each (0 and 1).
66
   5. There is no way of sending zero distance codes--a dummy must be
67
      sent if there are none.  (History: a pre 2.0 version of PKZIP would
68
      store blocks with no distance codes, but this was discovered to be
69
      too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
70
      zero distance codes, which is sent as one code of zero bits in
71
      length.
72
   6. There are up to 286 literal/length codes.  Code 256 represents the
73
      end-of-block.  Note however that the static length tree defines
74
      288 codes just to fill out the Huffman codes.  Codes 286 and 287
75
      cannot be used though, since there is no length base or extra bits
76
      defined for them.  Similarly, there are up to 30 distance codes.
77
      However, static trees define 32 codes (all 5 bits) to fill out the
78
      Huffman codes, but the last two had better not show up in the data.
79
   7. Unzip can check dynamic Huffman blocks for complete code sets.
80
      The exception is that a single code would not be complete (see #4).
81
   8. The five bits following the block type is really the number of
82
      literal codes sent minus 257.
83
   9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
84
      (1+6+6).  Therefore, to output three times the length, you output
85
      three codes (1+1+1), whereas to output four times the same length,
86
      you only need two codes (1+3).  Hmm.
87
  10. In the tree reconstruction algorithm, Code = Code + Increment
88
      only if BitLength(i) is not zero.  (Pretty obvious.)
89
  11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
90
  12. Note: length code 284 can represent 227-258, but length code 285
91
      really is 258.  The last length deserves its own, short code
92
      since it gets used a lot in very redundant files.  The length
93
      258 is special since 258 - 3 (the min match length) is 255.
94
  13. The literal/length and distance code bit lengths are read as a
95
      single stream of lengths.  It is possible (and advantageous) for
96
      a repeat code (16, 17, or 18) to go across the boundary between
97
      the two sets of lengths.
98
 */
99
 
100
#ifdef RCSID
101
static char rcsid[] = "#Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp #";
102
#endif
103
 
104
#ifndef STATIC
105
 
106
#if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H)
107
#  include <sys/types.h>
108
#  include <stdlib.h>
109
#endif
110
 
111
#include "gzip.h"
112
#define STATIC
113
#endif /* !STATIC */
114
 
115
#define slide window
116
 
117
/* Huffman code lookup table entry--this entry is four bytes for machines
118
   that have 16-bit pointers (e.g. PC's in the small or medium model).
119
   Valid extra bits are 0..13.  e == 15 is EOB (end of block), e == 16
120
   means that v is a literal, 16 < e < 32 means that v is a pointer to
121
   the next table, which codes e - 16 bits, and lastly e == 99 indicates
122
   an unused code.  If a code with e == 99 is looked up, this implies an
123
   error in the data. */
124
struct huft {
125
  uch e;                /* number of extra bits or operation */
126
  uch b;                /* number of bits in this code or subcode */
127
  union {
128
    ush n;              /* literal, length base, or distance base */
129
    struct huft *t;     /* pointer to next level of table */
130
  } v;
131
};
132
 
133
 
134
/* Function prototypes */
135
STATIC int huft_build OF((unsigned *, unsigned, unsigned, ush *, ush *,
136
                   struct huft **, int *));
137
STATIC int huft_free OF((struct huft *));
138
STATIC int inflate_codes OF((struct huft *, struct huft *, int, int));
139
STATIC int inflate_stored OF((void));
140
STATIC int inflate_fixed OF((void));
141
STATIC int inflate_dynamic OF((void));
142
STATIC int inflate_block OF((int *));
143
STATIC int inflate OF((void));
144
 
145
 
146
/* The inflate algorithm uses a sliding 32K byte window on the uncompressed
147
   stream to find repeated byte strings.  This is implemented here as a
148
   circular buffer.  The index is updated simply by incrementing and then
149
   and'ing with 0x7fff (32K-1). */
150
/* It is left to other modules to supply the 32K area.  It is assumed
151
   to be usable as if it were declared "uch slide[32768];" or as just
152
   "uch *slide;" and then malloc'ed in the latter case.  The definition
153
   must be in unzip.h, included above. */
154
/* unsigned wp;             current position in slide */
155
#define wp outcnt
156
#define flush_output(w) (wp=(w),flush_window())
157
 
158
/* Tables for deflate from PKZIP's appnote.txt. */
159
static unsigned border[] = {    /* Order of the bit length code lengths */
160
        16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
161
static ush cplens[] = {         /* Copy lengths for literal codes 257..285 */
162
        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
163
        35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
164
        /* note: see note #13 above about the 258 in this list. */
165
static ush cplext[] = {         /* Extra bits for literal codes 257..285 */
166
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
167
        3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
168
static ush cpdist[] = {         /* Copy offsets for distance codes 0..29 */
169
        1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
170
        257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
171
        8193, 12289, 16385, 24577};
172
static ush cpdext[] = {         /* Extra bits for distance codes */
173
        0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
174
        7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
175
        12, 12, 13, 13};
176
 
177
 
178
 
179
/* Macros for inflate() bit peeking and grabbing.
180
   The usage is:
181
 
182
        NEEDBITS(j)
183
        x = b & mask_bits[j];
184
        DUMPBITS(j)
185
 
186
   where NEEDBITS makes sure that b has at least j bits in it, and
187
   DUMPBITS removes the bits from b.  The macros use the variable k
188
   for the number of bits in b.  Normally, b and k are register
189
   variables for speed, and are initialized at the beginning of a
190
   routine that uses these macros from a global bit buffer and count.
191
 
192
   If we assume that EOB will be the longest code, then we will never
193
   ask for bits with NEEDBITS that are beyond the end of the stream.
194
   So, NEEDBITS should not read any more bytes than are needed to
195
   meet the request.  Then no bytes need to be "returned" to the buffer
196
   at the end of the last block.
197
 
198
   However, this assumption is not true for fixed blocks--the EOB code
199
   is 7 bits, but the other literal/length codes can be 8 or 9 bits.
200
   (The EOB code is shorter than other codes because fixed blocks are
201
   generally short.  So, while a block always has an EOB, many other
202
   literal/length codes have a significantly lower probability of
203
   showing up at all.)  However, by making the first table have a
204
   lookup of seven bits, the EOB code will be found in that first
205
   lookup, and so will not require that too many bits be pulled from
206
   the stream.
207
 */
208
 
209
STATIC ulg bb;                         /* bit buffer */
210
STATIC unsigned bk;                    /* bits in bit buffer */
211
 
212
STATIC ush mask_bits[] = {
213
    0x0000,
214
    0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
215
    0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
216
};
217
 
218
#define NEXTBYTE()  (uch)get_byte()
219
#define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
220
#define DUMPBITS(n) {b>>=(n);k-=(n);}
221
 
222
 
223
/*
224
   Huffman code decoding is performed using a multi-level table lookup.
225
   The fastest way to decode is to simply build a lookup table whose
226
   size is determined by the longest code.  However, the time it takes
227
   to build this table can also be a factor if the data being decoded
228
   is not very long.  The most common codes are necessarily the
229
   shortest codes, so those codes dominate the decoding time, and hence
230
   the speed.  The idea is you can have a shorter table that decodes the
231
   shorter, more probable codes, and then point to subsidiary tables for
232
   the longer codes.  The time it costs to decode the longer codes is
233
   then traded against the time it takes to make longer tables.
234
 
235
   This results of this trade are in the variables lbits and dbits
236
   below.  lbits is the number of bits the first level table for literal/
237
   length codes can decode in one step, and dbits is the same thing for
238
   the distance codes.  Subsequent tables are also less than or equal to
239
   those sizes.  These values may be adjusted either when all of the
240
   codes are shorter than that, in which case the longest code length in
241
   bits is used, or when the shortest code is *longer* than the requested
242
   table size, in which case the length of the shortest code in bits is
243
   used.
244
 
245
   There are two different values for the two tables, since they code a
246
   different number of possibilities each.  The literal/length table
247
   codes 286 possible values, or in a flat code, a little over eight
248
   bits.  The distance table codes 30 possible values, or a little less
249
   than five bits, flat.  The optimum values for speed end up being
250
   about one bit more than those, so lbits is 8+1 and dbits is 5+1.
251
   The optimum values may differ though from machine to machine, and
252
   possibly even between compilers.  Your mileage may vary.
253
 */
254
 
255
 
256
STATIC int lbits = 9;          /* bits in base literal/length lookup table */
257
STATIC int dbits = 6;          /* bits in base distance lookup table */
258
 
259
 
260
/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
261
#define BMAX 16         /* maximum bit length of any code (16 for explode) */
262
#define N_MAX 288       /* maximum number of codes in any set */
263
 
264
 
265
STATIC unsigned hufts;         /* track memory usage */
266
 
267
 
268
STATIC int huft_build(b, n, s, d, e, t, m)
269
unsigned *b;            /* code lengths in bits (all assumed <= BMAX) */
270
unsigned n;             /* number of codes (assumed <= N_MAX) */
271
unsigned s;             /* number of simple-valued codes (0..s-1) */
272
ush *d;                 /* list of base values for non-simple codes */
273
ush *e;                 /* list of extra bits for non-simple codes */
274
struct huft **t;        /* result: starting table */
275
int *m;                 /* maximum lookup bits, returns actual */
276
/* Given a list of code lengths and a maximum table size, make a set of
277
   tables to decode that set of codes.  Return zero on success, one if
278
   the given code set is incomplete (the tables are still built in this
279
   case), two if the input is invalid (all zero length codes or an
280
   oversubscribed set of lengths), and three if not enough memory. */
281
{
282
  unsigned a;                   /* counter for codes of length k */
283
  unsigned c[BMAX+1];           /* bit length count table */
284
  unsigned f;                   /* i repeats in table every f entries */
285
  int g;                        /* maximum code length */
286
  int h;                        /* table level */
287
  register unsigned i;          /* counter, current code */
288
  register unsigned j;          /* counter */
289
  register int k;               /* number of bits in current code */
290
  int l;                        /* bits per table (returned in m) */
291
  register unsigned *p;         /* pointer into c[], b[], or v[] */
292
  register struct huft *q;      /* points to current table */
293
  struct huft r;                /* table entry for structure assignment */
294
  struct huft *u[BMAX];         /* table stack */
295
  unsigned v[N_MAX];            /* values in order of bit length */
296
  register int w;               /* bits before this table == (l * h) */
297
  unsigned x[BMAX+1];           /* bit offsets, then code stack */
298
  unsigned *xp;                 /* pointer into x */
299
  int y;                        /* number of dummy codes added */
300
  unsigned z;                   /* number of entries in current table */
301
 
302
DEBG("huft1 ");
303
 
304
  /* Generate counts for each bit length */
305
  memzero(c, sizeof(c));
306
  p = b;  i = n;
307
  do {
308
    Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
309
            n-i, *p));
310
    c[*p]++;                    /* assume all entries <= BMAX */
311
    p++;                      /* Can't combine with above line (Solaris bug) */
312
  } while (--i);
313
  if (c[0] == n)                /* null input--all zero length codes */
314
  {
315
    *t = (struct huft *)NULL;
316
    *m = 0;
317
    return 0;
318
  }
319
 
320
DEBG("huft2 ");
321
 
322
  /* Find minimum and maximum length, bound *m by those */
323
  l = *m;
324
  for (j = 1; j <= BMAX; j++)
325
    if (c[j])
326
      break;
327
  k = j;                        /* minimum code length */
328
  if ((unsigned)l < j)
329
    l = j;
330
  for (i = BMAX; i; i--)
331
    if (c[i])
332
      break;
333
  g = i;                        /* maximum code length */
334
  if ((unsigned)l > i)
335
    l = i;
336
  *m = l;
337
 
338
DEBG("huft3 ");
339
 
340
  /* Adjust last length count to fill out codes, if needed */
341
  for (y = 1 << j; j < i; j++, y <<= 1)
342
    if ((y -= c[j]) < 0)
343
      return 2;                 /* bad input: more codes than bits */
344
  if ((y -= c[i]) < 0)
345
    return 2;
346
  c[i] += y;
347
 
348
DEBG("huft4 ");
349
 
350
  /* Generate starting offsets into the value table for each length */
351
  x[1] = j = 0;
352
  p = c + 1;  xp = x + 2;
353
  while (--i) {                 /* note that i == g from above */
354
    *xp++ = (j += *p++);
355
  }
356
 
357
DEBG("huft5 ");
358
 
359
  /* Make a table of values in order of bit lengths */
360
  p = b;  i = 0;
361
  do {
362
    if ((j = *p++) != 0)
363
      v[x[j]++] = i;
364
  } while (++i < n);
365
 
366
DEBG("h6 ");
367
 
368
  /* Generate the Huffman codes and for each, make the table entries */
369
  x[0] = i = 0;                 /* first Huffman code is zero */
370
  p = v;                        /* grab values in bit order */
371
  h = -1;                       /* no tables yet--level -1 */
372
  w = -l;                       /* bits decoded == (l * h) */
373
  u[0] = (struct huft *)NULL;   /* just to keep compilers happy */
374
  q = (struct huft *)NULL;      /* ditto */
375
  z = 0;                        /* ditto */
376
DEBG("h6a ");
377
 
378
  /* go through the bit lengths (k already is bits in shortest code) */
379
  for (; k <= g; k++)
380
  {
381
DEBG("h6b ");
382
    a = c[k];
383
    while (a--)
384
    {
385
DEBG("h6b1 ");
386
      /* here i is the Huffman code of length k bits for value *p */
387
      /* make tables up to required level */
388
      while (k > w + l)
389
      {
390
DEBG1("1 ");
391
        h++;
392
        w += l;                 /* previous table always l bits */
393
 
394
        /* compute minimum size table less than or equal to l bits */
395
        z = (z = g - w) > (unsigned)l ? l : z;  /* upper limit on table size */
396
        if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
397
        {                       /* too few codes for k-w bit table */
398
DEBG1("2 ");
399
          f -= a + 1;           /* deduct codes from patterns left */
400
          xp = c + k;
401
          while (++j < z)       /* try smaller tables up to z bits */
402
          {
403
            if ((f <<= 1) <= *++xp)
404
              break;            /* enough codes to use up j bits */
405
            f -= *xp;           /* else deduct codes from patterns */
406
          }
407
        }
408
DEBG1("3 ");
409
        z = 1 << j;             /* table entries for j-bit table */
410
 
411
        /* allocate and link in new table */
412
        if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) ==
413
            (struct huft *)NULL)
414
        {
415
          if (h)
416
            huft_free(u[0]);
417
          return 3;             /* not enough memory */
418
        }
419
DEBG1("4 ");
420
        hufts += z + 1;         /* track memory usage */
421
        *t = q + 1;             /* link to list for huft_free() */
422
        *(t = &(q->v.t)) = (struct huft *)NULL;
423
        u[h] = ++q;             /* table starts after link */
424
 
425
DEBG1("5 ");
426
        /* connect to last table, if there is one */
427
        if (h)
428
        {
429
          x[h] = i;             /* save pattern for backing up */
430
          r.b = (uch)l;         /* bits to dump before this table */
431
          r.e = (uch)(16 + j);  /* bits in this table */
432
          r.v.t = q;            /* pointer to this table */
433
          j = i >> (w - l);     /* (get around Turbo C bug) */
434
          u[h-1][j] = r;        /* connect to last table */
435
        }
436
DEBG1("6 ");
437
      }
438
DEBG("h6c ");
439
 
440
      /* set up table entry in r */
441
      r.b = (uch)(k - w);
442
      if (p >= v + n)
443
        r.e = 99;               /* out of values--invalid code */
444
      else if (*p < s)
445
      {
446
        r.e = (uch)(*p < 256 ? 16 : 15);    /* 256 is end-of-block code */
447
        r.v.n = (ush)(*p);             /* simple code is just the value */
448
        p++;                           /* one compiler does not like *p++ */
449
      }
450
      else
451
      {
452
        r.e = (uch)e[*p - s];   /* non-simple--look up in lists */
453
        r.v.n = d[*p++ - s];
454
      }
455
DEBG("h6d ");
456
 
457
      /* fill code-like entries with r */
458
      f = 1 << (k - w);
459
      for (j = i >> w; j < z; j += f)
460
        q[j] = r;
461
 
462
      /* backwards increment the k-bit code i */
463
      for (j = 1 << (k - 1); i & j; j >>= 1)
464
        i ^= j;
465
      i ^= j;
466
 
467
      /* backup over finished tables */
468
      while ((i & ((1 << w) - 1)) != x[h])
469
      {
470
        h--;                    /* don't need to update q */
471
        w -= l;
472
      }
473
DEBG("h6e ");
474
    }
475
DEBG("h6f ");
476
  }
477
 
478
DEBG("huft7 ");
479
 
480
  /* Return true (1) if we were given an incomplete table */
481
  return y != 0 && g != 1;
482
}
483
 
484
 
485
 
486
STATIC int huft_free(t)
487
struct huft *t;         /* table to free */
488
/* Free the malloc'ed tables built by huft_build(), which makes a linked
489
   list of the tables it made, with the links in a dummy first entry of
490
   each table. */
491
{
492
  register struct huft *p, *q;
493
 
494
 
495
  /* Go through linked list, freeing from the malloced (t[-1]) address. */
496
  p = t;
497
  while (p != (struct huft *)NULL)
498
  {
499
    q = (--p)->v.t;
500
    free((char*)p);
501
    p = q;
502
  }
503
  return 0;
504
}
505
 
506
 
507
STATIC int inflate_codes(tl, td, bl, bd)
508
struct huft *tl, *td;   /* literal/length and distance decoder tables */
509
int bl, bd;             /* number of bits decoded by tl[] and td[] */
510
/* inflate (decompress) the codes in a deflated (compressed) block.
511
   Return an error code or zero if it all goes ok. */
512
{
513
  register unsigned e;  /* table entry flag/number of extra bits */
514
  unsigned n, d;        /* length and index for copy */
515
  unsigned w;           /* current window position */
516
  struct huft *t;       /* pointer to table entry */
517
  unsigned ml, md;      /* masks for bl and bd bits */
518
  register ulg b;       /* bit buffer */
519
  register unsigned k;  /* number of bits in bit buffer */
520
 
521
 
522
  /* make local copies of globals */
523
  b = bb;                       /* initialize bit buffer */
524
  k = bk;
525
  w = wp;                       /* initialize window position */
526
 
527
  /* inflate the coded data */
528
  ml = mask_bits[bl];           /* precompute masks for speed */
529
  md = mask_bits[bd];
530
  for (;;)                      /* do until end of block */
531
  {
532
    NEEDBITS((unsigned)bl)
533
    if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
534
      do {
535
        if (e == 99)
536
          return 1;
537
        DUMPBITS(t->b)
538
        e -= 16;
539
        NEEDBITS(e)
540
      } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
541
    DUMPBITS(t->b)
542
    if (e == 16)                /* then it's a literal */
543
    {
544
      slide[w++] = (uch)t->v.n;
545
      Tracevv((stderr, "%c", slide[w-1]));
546
      if (w == WSIZE)
547
      {
548
        flush_output(w);
549
        w = 0;
550
      }
551
    }
552
    else                        /* it's an EOB or a length */
553
    {
554
      /* exit if end of block */
555
      if (e == 15)
556
        break;
557
 
558
      /* get length of block to copy */
559
      NEEDBITS(e)
560
      n = t->v.n + ((unsigned)b & mask_bits[e]);
561
      DUMPBITS(e);
562
 
563
      /* decode distance of block to copy */
564
      NEEDBITS((unsigned)bd)
565
      if ((e = (t = td + ((unsigned)b & md))->e) > 16)
566
        do {
567
          if (e == 99)
568
            return 1;
569
          DUMPBITS(t->b)
570
          e -= 16;
571
          NEEDBITS(e)
572
        } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
573
      DUMPBITS(t->b)
574
      NEEDBITS(e)
575
      d = w - t->v.n - ((unsigned)b & mask_bits[e]);
576
      DUMPBITS(e)
577
      Tracevv((stderr,"\\[%d,%d]", w-d, n));
578
 
579
      /* do the copy */
580
      do {
581
        n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
582
#if !defined(NOMEMCPY) && !defined(DEBUG)
583
        if (w - d >= e)         /* (this test assumes unsigned comparison) */
584
        {
585
          memcpy(slide + w, slide + d, e);
586
          w += e;
587
          d += e;
588
        }
589
        else                      /* do it slow to avoid memcpy() overlap */
590
#endif /* !NOMEMCPY */
591
          do {
592
            slide[w++] = slide[d++];
593
            Tracevv((stderr, "%c", slide[w-1]));
594
          } while (--e);
595
        if (w == WSIZE)
596
        {
597
          flush_output(w);
598
          w = 0;
599
        }
600
      } while (n);
601
    }
602
  }
603
 
604
 
605
  /* restore the globals from the locals */
606
  wp = w;                       /* restore global window pointer */
607
  bb = b;                       /* restore global bit buffer */
608
  bk = k;
609
 
610
  /* done */
611
  return 0;
612
}
613
 
614
 
615
 
616
STATIC int inflate_stored()
617
/* "decompress" an inflated type 0 (stored) block. */
618
{
619
  unsigned n;           /* number of bytes in block */
620
  unsigned w;           /* current window position */
621
  register ulg b;       /* bit buffer */
622
  register unsigned k;  /* number of bits in bit buffer */
623
 
624
DEBG("<stor");
625
 
626
  /* make local copies of globals */
627
  b = bb;                       /* initialize bit buffer */
628
  k = bk;
629
  w = wp;                       /* initialize window position */
630
 
631
 
632
  /* go to byte boundary */
633
  n = k & 7;
634
  DUMPBITS(n);
635
 
636
 
637
  /* get the length and its complement */
638
  NEEDBITS(16)
639
  n = ((unsigned)b & 0xffff);
640
  DUMPBITS(16)
641
  NEEDBITS(16)
642
  if (n != (unsigned)((~b) & 0xffff))
643
    return 1;                   /* error in compressed data */
644
  DUMPBITS(16)
645
 
646
 
647
  /* read and output the compressed data */
648
  while (n--)
649
  {
650
    NEEDBITS(8)
651
    slide[w++] = (uch)b;
652
    if (w == WSIZE)
653
    {
654
      flush_output(w);
655
      w = 0;
656
    }
657
    DUMPBITS(8)
658
  }
659
 
660
 
661
  /* restore the globals from the locals */
662
  wp = w;                       /* restore global window pointer */
663
  bb = b;                       /* restore global bit buffer */
664
  bk = k;
665
 
666
  DEBG(">");
667
  return 0;
668
}
669
 
670
 
671
 
672
STATIC int inflate_fixed()
673
/* decompress an inflated type 1 (fixed Huffman codes) block.  We should
674
   either replace this with a custom decoder, or at least precompute the
675
   Huffman tables. */
676
{
677
  int i;                /* temporary variable */
678
  struct huft *tl;      /* literal/length code table */
679
  struct huft *td;      /* distance code table */
680
  int bl;               /* lookup bits for tl */
681
  int bd;               /* lookup bits for td */
682
  unsigned l[288];      /* length list for huft_build */
683
 
684
DEBG("<fix");
685
 
686
  /* set up literal table */
687
  for (i = 0; i < 144; i++)
688
    l[i] = 8;
689
  for (; i < 256; i++)
690
    l[i] = 9;
691
  for (; i < 280; i++)
692
    l[i] = 7;
693
  for (; i < 288; i++)          /* make a complete, but wrong code set */
694
    l[i] = 8;
695
  bl = 7;
696
  if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
697
    return i;
698
 
699
 
700
  /* set up distance table */
701
  for (i = 0; i < 30; i++)      /* make an incomplete code set */
702
    l[i] = 5;
703
  bd = 5;
704
  if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
705
  {
706
    huft_free(tl);
707
 
708
    DEBG(">");
709
    return i;
710
  }
711
 
712
 
713
  /* decompress until an end-of-block code */
714
  if (inflate_codes(tl, td, bl, bd))
715
    return 1;
716
 
717
 
718
  /* free the decoding tables, return */
719
  huft_free(tl);
720
  huft_free(td);
721
  return 0;
722
}
723
 
724
 
725
 
726
STATIC int inflate_dynamic()
727
/* decompress an inflated type 2 (dynamic Huffman codes) block. */
728
{
729
  int i;                /* temporary variables */
730
  unsigned j;
731
  unsigned l;           /* last length */
732
  unsigned m;           /* mask for bit lengths table */
733
  unsigned n;           /* number of lengths to get */
734
  struct huft *tl;      /* literal/length code table */
735
  struct huft *td;      /* distance code table */
736
  int bl;               /* lookup bits for tl */
737
  int bd;               /* lookup bits for td */
738
  unsigned nb;          /* number of bit length codes */
739
  unsigned nl;          /* number of literal/length codes */
740
  unsigned nd;          /* number of distance codes */
741
#ifdef PKZIP_BUG_WORKAROUND
742
  unsigned ll[288+32];  /* literal/length and distance code lengths */
743
#else
744
  unsigned ll[286+30];  /* literal/length and distance code lengths */
745
#endif
746
  register ulg b;       /* bit buffer */
747
  register unsigned k;  /* number of bits in bit buffer */
748
 
749
DEBG("<dyn");
750
 
751
  /* make local bit buffer */
752
  b = bb;
753
  k = bk;
754
 
755
 
756
  /* read in table lengths */
757
  NEEDBITS(5)
758
  nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
759
  DUMPBITS(5)
760
  NEEDBITS(5)
761
  nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
762
  DUMPBITS(5)
763
  NEEDBITS(4)
764
  nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
765
  DUMPBITS(4)
766
#ifdef PKZIP_BUG_WORKAROUND
767
  if (nl > 288 || nd > 32)
768
#else
769
  if (nl > 286 || nd > 30)
770
#endif
771
    return 1;                   /* bad lengths */
772
 
773
DEBG("dyn1 ");
774
 
775
  /* read in bit-length-code lengths */
776
  for (j = 0; j < nb; j++)
777
  {
778
    NEEDBITS(3)
779
    ll[border[j]] = (unsigned)b & 7;
780
    DUMPBITS(3)
781
  }
782
  for (; j < 19; j++)
783
    ll[border[j]] = 0;
784
 
785
DEBG("dyn2 ");
786
 
787
  /* build decoding table for trees--single level, 7 bit lookup */
788
  bl = 7;
789
  if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
790
  {
791
    if (i == 1)
792
      huft_free(tl);
793
    return i;                   /* incomplete code set */
794
  }
795
 
796
DEBG("dyn3 ");
797
 
798
  /* read in literal and distance code lengths */
799
  n = nl + nd;
800
  m = mask_bits[bl];
801
  i = l = 0;
802
  while ((unsigned)i < n)
803
  {
804
    NEEDBITS((unsigned)bl)
805
    j = (td = tl + ((unsigned)b & m))->b;
806
    DUMPBITS(j)
807
    j = td->v.n;
808
    if (j < 16)                 /* length of code in bits (0..15) */
809
      ll[i++] = l = j;          /* save last length in l */
810
    else if (j == 16)           /* repeat last length 3 to 6 times */
811
    {
812
      NEEDBITS(2)
813
      j = 3 + ((unsigned)b & 3);
814
      DUMPBITS(2)
815
      if ((unsigned)i + j > n)
816
        return 1;
817
      while (j--)
818
        ll[i++] = l;
819
    }
820
    else if (j == 17)           /* 3 to 10 zero length codes */
821
    {
822
      NEEDBITS(3)
823
      j = 3 + ((unsigned)b & 7);
824
      DUMPBITS(3)
825
      if ((unsigned)i + j > n)
826
        return 1;
827
      while (j--)
828
        ll[i++] = 0;
829
      l = 0;
830
    }
831
    else                        /* j == 18: 11 to 138 zero length codes */
832
    {
833
      NEEDBITS(7)
834
      j = 11 + ((unsigned)b & 0x7f);
835
      DUMPBITS(7)
836
      if ((unsigned)i + j > n)
837
        return 1;
838
      while (j--)
839
        ll[i++] = 0;
840
      l = 0;
841
    }
842
  }
843
 
844
DEBG("dyn4 ");
845
 
846
  /* free decoding table for trees */
847
  huft_free(tl);
848
 
849
DEBG("dyn5 ");
850
 
851
  /* restore the global bit buffer */
852
  bb = b;
853
  bk = k;
854
 
855
DEBG("dyn5a ");
856
 
857
  /* build the decoding tables for literal/length and distance codes */
858
  bl = lbits;
859
  if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
860
  {
861
DEBG("dyn5b ");
862
    if (i == 1) {
863
      error(" incomplete literal tree\n");
864
      huft_free(tl);
865
    }
866
    return i;                   /* incomplete code set */
867
  }
868
DEBG("dyn5c ");
869
  bd = dbits;
870
  if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
871
  {
872
DEBG("dyn5d ");
873
    if (i == 1) {
874
      error(" incomplete distance tree\n");
875
#ifdef PKZIP_BUG_WORKAROUND
876
      i = 0;
877
    }
878
#else
879
      huft_free(td);
880
    }
881
    huft_free(tl);
882
    return i;                   /* incomplete code set */
883
#endif
884
  }
885
 
886
DEBG("dyn6 ");
887
 
888
  /* decompress until an end-of-block code */
889
  if (inflate_codes(tl, td, bl, bd))
890
    return 1;
891
 
892
DEBG("dyn7 ");
893
 
894
  /* free the decoding tables, return */
895
  huft_free(tl);
896
  huft_free(td);
897
 
898
  DEBG(">");
899
  return 0;
900
}
901
 
902
 
903
 
904
STATIC int inflate_block(e)
905
int *e;                 /* last block flag */
906
/* decompress an inflated block */
907
{
908
  unsigned t;           /* block type */
909
  register ulg b;       /* bit buffer */
910
  register unsigned k;  /* number of bits in bit buffer */
911
 
912
  DEBG("<blk");
913
 
914
  /* make local bit buffer */
915
  b = bb;
916
  k = bk;
917
 
918
 
919
  /* read in last block bit */
920
  NEEDBITS(1)
921
  *e = (int)b & 1;
922
  DUMPBITS(1)
923
 
924
 
925
  /* read in block type */
926
  NEEDBITS(2)
927
  t = (unsigned)b & 3;
928
  DUMPBITS(2)
929
 
930
 
931
  /* restore the global bit buffer */
932
  bb = b;
933
  bk = k;
934
 
935
  /* inflate that block type */
936
  if (t == 2)
937
    return inflate_dynamic();
938
  if (t == 0)
939
    return inflate_stored();
940
  if (t == 1)
941
    return inflate_fixed();
942
 
943
  DEBG(">");
944
 
945
  /* bad block type */
946
  return 2;
947
}
948
 
949
 
950
 
951
STATIC int inflate()
952
/* decompress an inflated entry */
953
{
954
  int e;                /* last block flag */
955
  int r;                /* result code */
956
  unsigned h;           /* maximum struct huft's malloc'ed */
957
  void *ptr;
958
 
959
  /* initialize window, bit buffer */
960
  wp = 0;
961
  bk = 0;
962
  bb = 0;
963
 
964
 
965
  /* decompress until the last block */
966
  h = 0;
967
  do {
968
    hufts = 0;
969
    gzip_mark(&ptr);
970
    if ((r = inflate_block(&e)) != 0) {
971
      gzip_release(&ptr);
972
      return r;
973
    }
974
    gzip_release(&ptr);
975
    if (hufts > h)
976
      h = hufts;
977
  } while (!e);
978
 
979
  /* Undo too much lookahead. The next read will be byte aligned so we
980
   * can discard unused bits in the last meaningful byte.
981
   */
982
  while (bk >= 8) {
983
    bk -= 8;
984
    inptr--;
985
  }
986
 
987
  /* flush out slide */
988
  flush_output(wp);
989
 
990
 
991
  /* return success */
992
#ifdef DEBUG
993
  fprintf(stderr, "<%u> ", h);
994
#endif /* DEBUG */
995
  return 0;
996
}
997
 
998
/**********************************************************************
999
 *
1000
 * The following are support routines for inflate.c
1001
 *
1002
 **********************************************************************/
1003
 
1004
static ulg crc_32_tab[256];
1005
static ulg crc = (ulg)0xffffffffL; /* shift register contents */
1006
#define CRC_VALUE (crc ^ 0xffffffffL)
1007
 
1008
/*
1009
 * Code to compute the CRC-32 table. Borrowed from
1010
 * gzip-1.0.3/makecrc.c.
1011
 */
1012
 
1013
static void
1014
makecrc(void)
1015
{
1016
/* Not copyrighted 1990 Mark Adler      */
1017
 
1018
  unsigned long c;      /* crc shift register */
1019
  unsigned long e;      /* polynomial exclusive-or pattern */
1020
  int i;                /* counter for all possible eight bit values */
1021
  int k;                /* byte being shifted into crc apparatus */
1022
 
1023
  /* terms of polynomial defining this crc (except x^32): */
1024
  static int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
1025
 
1026
  /* Make exclusive-or pattern from polynomial */
1027
  e = 0;
1028
  for (i = 0; i < sizeof(p)/sizeof(int); i++)
1029
    e |= 1L << (31 - p[i]);
1030
 
1031
  crc_32_tab[0] = 0;
1032
 
1033
  for (i = 1; i < 256; i++)
1034
  {
1035
    c = 0;
1036
    for (k = i | 256; k != 1; k >>= 1)
1037
    {
1038
      c = c & 1 ? (c >> 1) ^ e : c >> 1;
1039
      if (k & 1)
1040
        c ^= e;
1041
    }
1042
    crc_32_tab[i] = c;
1043
  }
1044
}
1045
 
1046
/* gzip flag byte */
1047
#define ASCII_FLAG   0x01 /* bit 0 set: file probably ascii text */
1048
#define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
1049
#define EXTRA_FIELD  0x04 /* bit 2 set: extra field present */
1050
#define ORIG_NAME    0x08 /* bit 3 set: original file name present */
1051
#define COMMENT      0x10 /* bit 4 set: file comment present */
1052
#define ENCRYPTED    0x20 /* bit 5 set: file is encrypted */
1053
#define RESERVED     0xC0 /* bit 6,7:   reserved */
1054
 
1055
/*
1056
 * Do the uncompression!
1057
 */
1058
static int gunzip(void)
1059
{
1060
    uch flags;
1061
    unsigned char magic[2]; /* magic header */
1062
    char method;
1063
    ulg orig_crc = 0;       /* original crc */
1064
    ulg orig_len = 0;       /* original uncompressed length */
1065
    int res;
1066
 
1067
    magic[0] = (unsigned char)get_byte();
1068
    magic[1] = (unsigned char)get_byte();
1069
    method = (unsigned char)get_byte();
1070
 
1071
    if (magic[0] != 037 ||
1072
        ((magic[1] != 0213) && (magic[1] != 0236))) {
1073
            error("bad gzip magic numbers");
1074
            return -1;
1075
    }
1076
 
1077
    /* We only support method #8, DEFLATED */
1078
    if (method != 8)  {
1079
            error("internal error, invalid method");
1080
            return -1;
1081
    }
1082
 
1083
    flags  = (uch)get_byte();
1084
    if ((flags & ENCRYPTED) != 0) {
1085
            error("Input is encrypted\n");
1086
            return -1;
1087
    }
1088
    if ((flags & CONTINUATION) != 0) {
1089
            error("Multi part input\n");
1090
            return -1;
1091
    }
1092
    if ((flags & RESERVED) != 0) {
1093
            error("Input has invalid flags\n");
1094
            return -1;
1095
    }
1096
    (ulg)get_byte();    /* Get timestamp */
1097
    ((ulg)get_byte()) << 8;
1098
    ((ulg)get_byte()) << 16;
1099
    ((ulg)get_byte()) << 24;
1100
 
1101
    (void)get_byte();  /* Ignore extra flags for the moment */
1102
    (void)get_byte();  /* Ignore OS type for the moment */
1103
 
1104
    if ((flags & EXTRA_FIELD) != 0) {
1105
            unsigned len = (unsigned)get_byte();
1106
            len |= ((unsigned)get_byte())<<8;
1107
            while (len--) (void)get_byte();
1108
    }
1109
 
1110
    /* Get original file name if it was truncated */
1111
    if ((flags & ORIG_NAME) != 0) {
1112
            /* Discard the old name */
1113
            while (get_byte() != 0) /* null */ ;
1114
    }
1115
 
1116
    /* Discard file comment if any */
1117
    if ((flags & COMMENT) != 0) {
1118
            while (get_byte() != 0) /* null */ ;
1119
    }
1120
 
1121
    /* Decompress */
1122
    if ((res = inflate())) {
1123
            switch (res) {
1124
            case 0:
1125
                    break;
1126
            case 1:
1127
                    error("invalid compressed format (err=1)");
1128
                    break;
1129
            case 2:
1130
                    error("invalid compressed format (err=2)");
1131
                    break;
1132
            case 3:
1133
                    error("out of memory");
1134
                    break;
1135
            default:
1136
                    error("invalid compressed format (other)");
1137
            }
1138
            return -1;
1139
    }
1140
 
1141
    /* Get the crc and original length */
1142
    /* crc32  (see algorithm.doc)
1143
     * uncompressed input size modulo 2^32
1144
     */
1145
    orig_crc = (ulg) get_byte();
1146
    orig_crc |= (ulg) get_byte() << 8;
1147
    orig_crc |= (ulg) get_byte() << 16;
1148
    orig_crc |= (ulg) get_byte() << 24;
1149
 
1150
    orig_len = (ulg) get_byte();
1151
    orig_len |= (ulg) get_byte() << 8;
1152
    orig_len |= (ulg) get_byte() << 16;
1153
    orig_len |= (ulg) get_byte() << 24;
1154
 
1155
    /* Validate decompression */
1156
    if (orig_crc != CRC_VALUE) {
1157
            error("crc error");
1158
            return -1;
1159
    }
1160
    if (orig_len != bytes_out) {
1161
            error("length error");
1162
            return -1;
1163
    }
1164
    return 0;
1165
}
1166
 
1167
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.