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