1
/* gzio.c - decompression support for gzip */
3
* GRUB -- GRand Unified Bootloader
4
* Copyright (C) 1999,2005,2006,2007,2009 Free Software Foundation, Inc.
6
* GRUB is free software: you can redistribute it and/or modify
7
* it under the terms of the GNU General Public License as published by
8
* the Free Software Foundation, either version 3 of the License, or
9
* (at your option) any later version.
11
* GRUB is distributed in the hope that it will be useful,
12
* but WITHOUT ANY WARRANTY; without even the implied warranty of
13
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
* GNU General Public License for more details.
16
* You should have received a copy of the GNU General Public License
17
* along with GRUB. If not, see <http://www.gnu.org/licenses/>.
21
* Most of this file was originally the source file "inflate.c", written
22
* by Mark Adler. It has been very heavily modified. In particular, the
23
* original would run through the whole file at once, and this version can
24
* be stopped and restarted on any boundary during the decompression process.
26
* The license and header comments that file are included here.
29
/* inflate.c -- Not copyrighted 1992 by Mark Adler
30
version c10p1, 10 January 1993 */
32
/* You can do whatever you like with this source file, though I would
33
prefer that if you modify it and redistribute it that you include
34
comments to that effect with your name and the date. Thank you.
38
#include <grub/types.h>
40
#include <grub/misc.h>
42
#include <grub/file.h>
43
#include <grub/gzio.h>
48
* This must be a power of two, and at least 32K for zip's deflate method
54
#define INBUFSIZ 0x2000
56
/* The state stored in filesystem-specific data. */
59
/* The underlying file object. */
61
/* The offset at which the data starts in the underlying file. */
62
grub_off_t data_offset;
63
/* The type of current block. */
65
/* The length of current block. */
67
/* The flag of the last block. */
69
/* The flag of codes. */
71
/* The length of a copy. */
73
/* The index of a copy. */
75
/* The input buffer. */
76
grub_uint8_t inbuf[INBUFSIZ];
80
/* The bits in the bit buffer. */
82
/* The sliding window in uncompressed data. */
83
grub_uint8_t slide[WSIZE];
84
/* Current position in the slide. */
86
/* The literal/length code table. */
88
/* The distance code table. */
90
/* The lookup bits for the literal/length code table. */
92
/* The lookup bits for the distance code table. */
94
/* The original offset value. */
95
grub_off_t saved_offset;
97
typedef struct grub_gzio *grub_gzio_t;
99
/* Declare the filesystem structure for grub_gzio_open. */
100
static struct grub_fs grub_gzio_fs;
102
/* Function prototypes */
103
static void initialize_tables (grub_file_t file);
105
/* Eat variable-length header fields. */
107
eat_field (grub_file_t file, int len)
125
while ((not_retval = grub_file_read (file, &ch, 1)) == 1);
131
/* Little-Endian defines for the 2-byte magic numbers for gzip files. */
132
#define GZIP_MAGIC grub_le_to_cpu16 (0x8B1F)
133
#define OLD_GZIP_MAGIC grub_le_to_cpu16 (0x9E1F)
135
/* Compression methods (see algorithm.doc) */
140
/* methods 4 to 7 reserved */
142
#define MAX_METHODS 9
145
#define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
146
#define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
147
#define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
148
#define ORIG_NAME 0x08 /* bit 3 set: original file name present */
149
#define COMMENT 0x10 /* bit 4 set: file comment present */
150
#define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */
151
#define RESERVED 0xC0 /* bit 6,7: reserved */
153
#define UNSUPPORTED_FLAGS (CONTINUATION | ENCRYPTED | RESERVED)
155
/* inflate block codes */
156
#define INFLATE_STORED 0
157
#define INFLATE_FIXED 1
158
#define INFLATE_DYNAMIC 2
160
typedef unsigned char uch;
161
typedef unsigned short ush;
162
typedef unsigned long ulg;
165
test_header (grub_file_t file)
171
grub_uint32_t timestamp;
172
grub_uint8_t extra_flags;
173
grub_uint8_t os_type;
175
grub_uint16_t extra_len;
176
grub_uint32_t orig_len;
177
grub_gzio_t gzio = file->data;
179
if (grub_file_tell (gzio->file) != 0)
180
grub_file_seek (gzio->file, 0);
183
* This checks if the file is gzipped. If a problem occurs here
184
* (other than a real error with the disk) then we don't think it
185
* is a compressed file, and simply mark it as such.
187
if (grub_file_read (gzio->file, &hdr, 10) != 10
188
|| ((hdr.magic != GZIP_MAGIC)
189
&& (hdr.magic != OLD_GZIP_MAGIC)))
191
grub_error (GRUB_ERR_BAD_FILE_TYPE, "no gzip magic found");
196
* This does consistency checking on the header data. If a
197
* problem occurs from here on, then we have corrupt or otherwise
198
* bad data, and the error should be reported to the user.
200
if (hdr.method != DEFLATED
201
|| (hdr.flags & UNSUPPORTED_FLAGS)
202
|| ((hdr.flags & EXTRA_FIELD)
203
&& (grub_file_read (gzio->file, &extra_len, 2) != 2
204
|| eat_field (gzio->file,
205
grub_le_to_cpu16 (extra_len))))
206
|| ((hdr.flags & ORIG_NAME) && eat_field (gzio->file, -1))
207
|| ((hdr.flags & COMMENT) && eat_field (gzio->file, -1)))
209
grub_error (GRUB_ERR_BAD_GZIP_DATA, "unsupported gzip format");
213
gzio->data_offset = grub_file_tell (gzio->file);
215
grub_file_seek (gzio->file, grub_file_size (gzio->file) - 4);
217
if (grub_file_read (gzio->file, &orig_len, 4) != 4)
219
grub_error (GRUB_ERR_BAD_FILE_TYPE, "unsupported gzip format");
223
/* FIXME: this does not handle files whose original size is over 4GB.
224
But how can we know the real original size? */
225
file->size = grub_le_to_cpu32 (orig_len);
227
initialize_tables (file);
233
/* Huffman code lookup table entry--this entry is four bytes for machines
234
that have 16-bit pointers (e.g. PC's in the small or medium model).
235
Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16
236
means that v is a literal, 16 < e < 32 means that v is a pointer to
237
the next table, which codes e - 16 bits, and lastly e == 99 indicates
238
an unused code. If a code with e == 99 is looked up, this implies an
239
error in the data. */
242
uch e; /* number of extra bits or operation */
243
uch b; /* number of bits in this code or subcode */
246
ush n; /* literal, length base, or distance base */
247
struct huft *t; /* pointer to next level of table */
253
/* The inflate algorithm uses a sliding 32K byte window on the uncompressed
254
stream to find repeated byte strings. This is implemented here as a
255
circular buffer. The index is updated simply by incrementing and then
256
and'ing with 0x7fff (32K-1). */
257
/* It is left to other modules to supply the 32K area. It is assumed
258
to be usable as if it were declared "uch slide[32768];" or as just
259
"uch *slide;" and then malloc'ed in the latter case. The definition
260
must be in unzip.h, included above. */
263
/* Tables for deflate from PKZIP's appnote.txt. */
264
static unsigned bitorder[] =
265
{ /* Order of the bit length code lengths */
266
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
267
static ush cplens[] =
268
{ /* Copy lengths for literal codes 257..285 */
269
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
270
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
271
/* note: see note #13 above about the 258 in this list. */
272
static ush cplext[] =
273
{ /* Extra bits for literal codes 257..285 */
274
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
275
3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
276
static ush cpdist[] =
277
{ /* Copy offsets for distance codes 0..29 */
278
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
279
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
280
8193, 12289, 16385, 24577};
281
static ush cpdext[] =
282
{ /* Extra bits for distance codes */
283
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
284
7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
289
Huffman code decoding is performed using a multi-level table lookup.
290
The fastest way to decode is to simply build a lookup table whose
291
size is determined by the longest code. However, the time it takes
292
to build this table can also be a factor if the data being decoded
293
is not very long. The most common codes are necessarily the
294
shortest codes, so those codes dominate the decoding time, and hence
295
the speed. The idea is you can have a shorter table that decodes the
296
shorter, more probable codes, and then point to subsidiary tables for
297
the longer codes. The time it costs to decode the longer codes is
298
then traded against the time it takes to make longer tables.
300
This results of this trade are in the variables lbits and dbits
301
below. lbits is the number of bits the first level table for literal/
302
length codes can decode in one step, and dbits is the same thing for
303
the distance codes. Subsequent tables are also less than or equal to
304
those sizes. These values may be adjusted either when all of the
305
codes are shorter than that, in which case the longest code length in
306
bits is used, or when the shortest code is *longer* than the requested
307
table size, in which case the length of the shortest code in bits is
310
There are two different values for the two tables, since they code a
311
different number of possibilities each. The literal/length table
312
codes 286 possible values, or in a flat code, a little over eight
313
bits. The distance table codes 30 possible values, or a little less
314
than five bits, flat. The optimum values for speed end up being
315
about one bit more than those, so lbits is 8+1 and dbits is 5+1.
316
The optimum values may differ though from machine to machine, and
317
possibly even between compilers. Your mileage may vary.
321
static int lbits = 9; /* bits in base literal/length lookup table */
322
static int dbits = 6; /* bits in base distance lookup table */
325
/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
326
#define BMAX 16 /* maximum bit length of any code (16 for explode) */
327
#define N_MAX 288 /* maximum number of codes in any set */
330
/* Macros for inflate() bit peeking and grabbing.
334
x = b & mask_bits[j];
337
where NEEDBITS makes sure that b has at least j bits in it, and
338
DUMPBITS removes the bits from b. The macros use the variable k
339
for the number of bits in b. Normally, b and k are register
340
variables for speed, and are initialized at the beginning of a
341
routine that uses these macros from a global bit buffer and count.
343
If we assume that EOB will be the longest code, then we will never
344
ask for bits with NEEDBITS that are beyond the end of the stream.
345
So, NEEDBITS should not read any more bytes than are needed to
346
meet the request. Then no bytes need to be "returned" to the buffer
347
at the end of the last block.
349
However, this assumption is not true for fixed blocks--the EOB code
350
is 7 bits, but the other literal/length codes can be 8 or 9 bits.
351
(The EOB code is shorter than other codes because fixed blocks are
352
generally short. So, while a block always has an EOB, many other
353
literal/length codes have a significantly lower probability of
354
showing up at all.) However, by making the first table have a
355
lookup of seven bits, the EOB code will be found in that first
356
lookup, and so will not require that too many bits be pulled from
360
static ush mask_bits[] =
363
0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
364
0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
367
#define NEEDBITS(n) do {while(k<(n)){b|=((ulg)get_byte(file))<<k;k+=8;}} while (0)
368
#define DUMPBITS(n) do {b>>=(n);k-=(n);} while (0)
371
get_byte (grub_file_t file)
373
grub_gzio_t gzio = file->data;
375
if (grub_file_tell (gzio->file) == (grub_off_t) gzio->data_offset
376
|| gzio->inbuf_d == INBUFSIZ)
379
grub_file_read (gzio->file, gzio->inbuf, INBUFSIZ);
382
return gzio->inbuf[gzio->inbuf_d++];
385
/* more function prototypes */
386
static int huft_build (unsigned *, unsigned, unsigned, ush *, ush *,
387
struct huft **, int *);
388
static int huft_free (struct huft *);
389
static int inflate_codes_in_window (grub_file_t);
392
/* Given a list of code lengths and a maximum table size, make a set of
393
tables to decode that set of codes. Return zero on success, one if
394
the given code set is incomplete (the tables are still built in this
395
case), two if the input is invalid (all zero length codes or an
396
oversubscribed set of lengths), and three if not enough memory. */
399
huft_build (unsigned *b, /* code lengths in bits (all assumed <= BMAX) */
400
unsigned n, /* number of codes (assumed <= N_MAX) */
401
unsigned s, /* number of simple-valued codes (0..s-1) */
402
ush * d, /* list of base values for non-simple codes */
403
ush * e, /* list of extra bits for non-simple codes */
404
struct huft **t, /* result: starting table */
405
int *m) /* maximum lookup bits, returns actual */
407
unsigned a; /* counter for codes of length k */
408
unsigned c[BMAX + 1]; /* bit length count table */
409
unsigned f; /* i repeats in table every f entries */
410
int g; /* maximum code length */
411
int h; /* table level */
412
register unsigned i; /* counter, current code */
413
register unsigned j; /* counter */
414
register int k; /* number of bits in current code */
415
int l; /* bits per table (returned in m) */
416
register unsigned *p; /* pointer into c[], b[], or v[] */
417
register struct huft *q; /* points to current table */
418
struct huft r; /* table entry for structure assignment */
419
struct huft *u[BMAX]; /* table stack */
420
unsigned v[N_MAX]; /* values in order of bit length */
421
register int w; /* bits before this table == (l * h) */
422
unsigned x[BMAX + 1]; /* bit offsets, then code stack */
423
unsigned *xp; /* pointer into x */
424
int y; /* number of dummy codes added */
425
unsigned z; /* number of entries in current table */
427
/* Generate counts for each bit length */
428
grub_memset ((char *) c, 0, sizeof (c));
433
c[*p]++; /* assume all entries <= BMAX */
434
p++; /* Can't combine with above line (Solaris bug) */
437
if (c[0] == n) /* null input--all zero length codes */
439
*t = (struct huft *) NULL;
444
/* Find minimum and maximum length, bound *m by those */
446
for (j = 1; j <= BMAX; j++)
449
k = j; /* minimum code length */
450
if ((unsigned) l < j)
452
for (i = BMAX; i; i--)
455
g = i; /* maximum code length */
456
if ((unsigned) l > i)
460
/* Adjust last length count to fill out codes, if needed */
461
for (y = 1 << j; j < i; j++, y <<= 1)
463
return 2; /* bad input: more codes than bits */
468
/* Generate starting offsets into the value table for each length */
473
{ /* note that i == g from above */
477
/* Make a table of values in order of bit lengths */
487
/* Generate the Huffman codes and for each, make the table entries */
488
x[0] = i = 0; /* first Huffman code is zero */
489
p = v; /* grab values in bit order */
490
h = -1; /* no tables yet--level -1 */
491
w = -l; /* bits decoded == (l * h) */
492
u[0] = (struct huft *) NULL; /* just to keep compilers happy */
493
q = (struct huft *) NULL; /* ditto */
496
/* go through the bit lengths (k already is bits in shortest code) */
502
/* here i is the Huffman code of length k bits for value *p */
503
/* make tables up to required level */
507
w += l; /* previous table always l bits */
509
/* compute minimum size table less than or equal to l bits */
510
z = (z = (unsigned) (g - w)) > (unsigned) l ? (unsigned) l : z; /* upper limit on table size */
511
if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
512
{ /* too few codes for k-w bit table */
513
f -= a + 1; /* deduct codes from patterns left */
515
while (++j < z) /* try smaller tables up to z bits */
517
if ((f <<= 1) <= *++xp)
518
break; /* enough codes to use up j bits */
519
f -= *xp; /* else deduct codes from patterns */
522
z = 1 << j; /* table entries for j-bit table */
524
/* allocate and link in new table */
525
q = (struct huft *) grub_malloc ((z + 1) * sizeof (struct huft));
533
*t = q + 1; /* link to list for huft_free() */
534
*(t = &(q->v.t)) = (struct huft *) NULL;
535
u[h] = ++q; /* table starts after link */
537
/* connect to last table, if there is one */
540
x[h] = i; /* save pattern for backing up */
541
r.b = (uch) l; /* bits to dump before this table */
542
r.e = (uch) (16 + j); /* bits in this table */
543
r.v.t = q; /* pointer to this table */
544
j = i >> (w - l); /* (get around Turbo C bug) */
545
u[h - 1][j] = r; /* connect to last table */
549
/* set up table entry in r */
552
r.e = 99; /* out of values--invalid code */
555
r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block code */
556
r.v.n = (ush) (*p); /* simple code is just the value */
557
p++; /* one compiler does not like *p++ */
561
r.e = (uch) e[*p - s]; /* non-simple--look up in lists */
565
/* fill code-like entries with r */
567
for (j = i >> w; j < z; j += f)
570
/* backwards increment the k-bit code i */
571
for (j = 1 << (k - 1); i & j; j >>= 1)
575
/* backup over finished tables */
576
while ((i & ((1 << w) - 1)) != x[h])
578
h--; /* don't need to update q */
584
/* Return true (1) if we were given an incomplete table */
585
return y != 0 && g != 1;
589
/* Free the malloc'ed tables built by huft_build(), which makes a linked
590
list of the tables it made, with the links in a dummy first entry of
593
huft_free (struct huft *t)
595
register struct huft *p, *q;
598
/* Go through linked list, freeing from the malloced (t[-1]) address. */
600
while (p != (struct huft *) NULL)
603
grub_free ((char *) p);
611
* inflate (decompress) the codes in a deflated (compressed) block.
612
* Return an error code or zero if it all goes ok.
616
inflate_codes_in_window (grub_file_t file)
618
register unsigned e; /* table entry flag/number of extra bits */
619
unsigned n, d; /* length and index for copy */
620
unsigned w; /* current window position */
621
struct huft *t; /* pointer to table entry */
622
unsigned ml, md; /* masks for bl and bd bits */
623
register ulg b; /* bit buffer */
624
register unsigned k; /* number of bits in bit buffer */
625
grub_gzio_t gzio = file->data;
627
/* make local copies of globals */
630
b = gzio->bb; /* initialize bit buffer */
632
w = gzio->wp; /* initialize window position */
634
/* inflate the coded data */
635
ml = mask_bits[gzio->bl]; /* precompute masks for speed */
636
md = mask_bits[gzio->bd];
637
for (;;) /* do until end of block */
639
if (! gzio->code_state)
641
NEEDBITS ((unsigned) gzio->bl);
642
if ((e = (t = gzio->tl + ((unsigned) b & ml))->e) > 16)
647
grub_error (GRUB_ERR_BAD_GZIP_DATA,
648
"an unused code found");
655
while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
658
if (e == 16) /* then it's a literal */
660
gzio->slide[w++] = (uch) t->v.n;
665
/* it's an EOB or a length */
667
/* exit if end of block */
674
/* get length of block to copy */
676
n = t->v.n + ((unsigned) b & mask_bits[e]);
679
/* decode distance of block to copy */
680
NEEDBITS ((unsigned) gzio->bd);
681
if ((e = (t = gzio->td + ((unsigned) b & md))->e) > 16)
686
grub_error (GRUB_ERR_BAD_GZIP_DATA,
687
"an unused code found");
694
while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e)
698
d = w - t->v.n - ((unsigned) b & mask_bits[e]);
704
if (gzio->code_state)
709
n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n
714
grub_memmove (gzio->slide + w, gzio->slide + d, e);
719
/* purposefully use the overlap for extra copies here!! */
722
gzio->slide[w++] = gzio->slide[d++];
733
/* did we break from the loop too soon? */
739
/* restore the globals from the locals */
742
gzio->wp = w; /* restore global window pointer */
743
gzio->bb = b; /* restore global bit buffer */
746
return ! gzio->block_len;
750
/* get header for an inflated type 0 (stored) block. */
753
init_stored_block (grub_file_t file)
755
register ulg b; /* bit buffer */
756
register unsigned k; /* number of bits in bit buffer */
757
grub_gzio_t gzio = file->data;
759
/* make local copies of globals */
760
b = gzio->bb; /* initialize bit buffer */
763
/* go to byte boundary */
766
/* get the length and its complement */
768
gzio->block_len = ((unsigned) b & 0xffff);
771
if (gzio->block_len != (int) ((~b) & 0xffff))
772
grub_error (GRUB_ERR_BAD_GZIP_DATA,
773
"the length of a stored block does not match");
776
/* restore global variables */
782
/* get header for an inflated type 1 (fixed Huffman codes) block. We should
783
either replace this with a custom decoder, or at least precompute the
787
init_fixed_block (grub_file_t file)
789
int i; /* temporary variable */
790
unsigned l[288]; /* length list for huft_build */
791
grub_gzio_t gzio = file->data;
793
/* set up literal table */
794
for (i = 0; i < 144; i++)
800
for (; i < 288; i++) /* make a complete, but wrong code set */
803
if (huft_build (l, 288, 257, cplens, cplext, &gzio->tl, &gzio->bl) != 0)
805
if (grub_errno == GRUB_ERR_NONE)
806
grub_error (GRUB_ERR_BAD_GZIP_DATA,
807
"failed in building a Huffman code table");
811
/* set up distance table */
812
for (i = 0; i < 30; i++) /* make an incomplete code set */
815
if (huft_build (l, 30, 0, cpdist, cpdext, &gzio->td, &gzio->bd) > 1)
817
if (grub_errno == GRUB_ERR_NONE)
818
grub_error (GRUB_ERR_BAD_GZIP_DATA,
819
"failed in building a Huffman code table");
820
huft_free (gzio->tl);
825
/* indicate we're now working on a block */
826
gzio->code_state = 0;
831
/* get header for an inflated type 2 (dynamic Huffman codes) block. */
834
init_dynamic_block (grub_file_t file)
836
int i; /* temporary variables */
838
unsigned l; /* last length */
839
unsigned m; /* mask for bit lengths table */
840
unsigned n; /* number of lengths to get */
841
unsigned nb; /* number of bit length codes */
842
unsigned nl; /* number of literal/length codes */
843
unsigned nd; /* number of distance codes */
844
unsigned ll[286 + 30]; /* literal/length and distance code lengths */
845
register ulg b; /* bit buffer */
846
register unsigned k; /* number of bits in bit buffer */
847
grub_gzio_t gzio = file->data;
849
/* make local bit buffer */
853
/* read in table lengths */
855
nl = 257 + ((unsigned) b & 0x1f); /* number of literal/length codes */
858
nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */
861
nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */
863
if (nl > 286 || nd > 30)
865
grub_error (GRUB_ERR_BAD_GZIP_DATA, "too much data");
869
/* read in bit-length-code lengths */
870
for (j = 0; j < nb; j++)
873
ll[bitorder[j]] = (unsigned) b & 7;
879
/* build decoding table for trees--single level, 7 bit lookup */
881
if (huft_build (ll, 19, 19, NULL, NULL, &gzio->tl, &gzio->bl) != 0)
883
grub_error (GRUB_ERR_BAD_GZIP_DATA,
884
"failed in building a Huffman code table");
888
/* read in literal and distance code lengths */
890
m = mask_bits[gzio->bl];
892
while ((unsigned) i < n)
894
NEEDBITS ((unsigned) gzio->bl);
895
j = (gzio->td = gzio->tl + ((unsigned) b & m))->b;
898
if (j < 16) /* length of code in bits (0..15) */
899
ll[i++] = l = j; /* save last length in l */
900
else if (j == 16) /* repeat last length 3 to 6 times */
903
j = 3 + ((unsigned) b & 3);
905
if ((unsigned) i + j > n)
907
grub_error (GRUB_ERR_BAD_GZIP_DATA, "too many codes found");
913
else if (j == 17) /* 3 to 10 zero length codes */
916
j = 3 + ((unsigned) b & 7);
918
if ((unsigned) i + j > n)
920
grub_error (GRUB_ERR_BAD_GZIP_DATA, "too many codes found");
928
/* j == 18: 11 to 138 zero length codes */
931
j = 11 + ((unsigned) b & 0x7f);
933
if ((unsigned) i + j > n)
935
grub_error (GRUB_ERR_BAD_GZIP_DATA, "too many codes found");
944
/* free decoding table for trees */
945
huft_free (gzio->tl);
949
/* restore the global bit buffer */
953
/* build the decoding tables for literal/length and distance codes */
955
if (huft_build (ll, nl, 257, cplens, cplext, &gzio->tl, &gzio->bl) != 0)
957
grub_error (GRUB_ERR_BAD_GZIP_DATA,
958
"failed in building a Huffman code table");
962
if (huft_build (ll + nl, nd, 0, cpdist, cpdext, &gzio->td, &gzio->bd) != 0)
964
huft_free (gzio->tl);
966
grub_error (GRUB_ERR_BAD_GZIP_DATA,
967
"failed in building a Huffman code table");
971
/* indicate we're now working on a block */
972
gzio->code_state = 0;
978
get_new_block (grub_file_t file)
980
register ulg b; /* bit buffer */
981
register unsigned k; /* number of bits in bit buffer */
982
grub_gzio_t gzio = file->data;
984
/* make local bit buffer */
988
/* read in last block bit */
990
gzio->last_block = (int) b & 1;
993
/* read in block type */
995
gzio->block_type = (unsigned) b & 3;
998
/* restore the global bit buffer */
1002
switch (gzio->block_type)
1004
case INFLATE_STORED:
1005
init_stored_block (file);
1008
init_fixed_block (file);
1010
case INFLATE_DYNAMIC:
1011
init_dynamic_block (file);
1020
inflate_window (grub_file_t file)
1022
grub_gzio_t gzio = file->data;
1024
/* initialize window */
1028
* Main decompression loop.
1031
while (gzio->wp < WSIZE && grub_errno == GRUB_ERR_NONE)
1033
if (! gzio->block_len)
1035
if (gzio->last_block)
1038
get_new_block (file);
1041
if (gzio->block_type > INFLATE_DYNAMIC)
1042
grub_error (GRUB_ERR_BAD_GZIP_DATA,
1043
"unknown block type %d", gzio->block_type);
1045
if (grub_errno != GRUB_ERR_NONE)
1049
* Expand stored block here.
1051
if (gzio->block_type == INFLATE_STORED)
1056
* This is basically a glorified pass-through
1059
while (gzio->block_len && w < WSIZE && grub_errno == GRUB_ERR_NONE)
1061
gzio->slide[w++] = get_byte (file);
1071
* Expand other kind of block.
1074
if (inflate_codes_in_window (file))
1076
huft_free (gzio->tl);
1077
huft_free (gzio->td);
1083
gzio->saved_offset += WSIZE;
1085
/* XXX do CRC calculation here! */
1090
initialize_tables (grub_file_t file)
1092
grub_gzio_t gzio = file->data;
1094
gzio->saved_offset = 0;
1095
grub_file_seek (gzio->file, gzio->data_offset);
1097
/* Initialize the bit buffer. */
1101
/* Reset partial decompression code. */
1102
gzio->last_block = 0;
1103
gzio->block_len = 0;
1105
/* Reset memory allocation stuff. */
1106
huft_free (gzio->tl);
1107
huft_free (gzio->td);
1111
/* Open a new decompressing object on the top of IO. If TRANSPARENT is true,
1112
even if IO does not contain data compressed by gzip, return a valid file
1113
object. Note that this function won't close IO, even if an error occurs. */
1115
grub_gzio_open (grub_file_t io, int transparent)
1118
grub_gzio_t gzio = 0;
1120
file = (grub_file_t) grub_malloc (sizeof (*file));
1124
gzio = grub_zalloc (sizeof (*gzio));
1133
file->device = io->device;
1136
file->read_hook = 0;
1137
file->fs = &grub_gzio_fs;
1139
if (! test_header (file))
1143
grub_file_seek (io, 0);
1145
if (grub_errno == GRUB_ERR_BAD_FILE_TYPE && transparent)
1147
grub_errno = GRUB_ERR_NONE;
1157
/* This is similar to grub_gzio_open, but takes a file name as an argument. */
1159
grub_gzfile_open (const char *name, int transparent)
1161
grub_file_t io, file;
1163
io = grub_file_open (name);
1167
file = grub_gzio_open (io, transparent);
1170
grub_file_close (io);
1178
grub_gzio_read (grub_file_t file, char *buf, grub_size_t len)
1180
grub_ssize_t ret = 0;
1181
grub_gzio_t gzio = file->data;
1184
/* Do we reset decompression to the beginning of the file? */
1185
if (gzio->saved_offset > file->offset + WSIZE)
1186
initialize_tables (file);
1189
* This loop operates upon uncompressed data only. The only
1190
* special thing it does is to make sure the decompression
1191
* window is within the range of data it needs.
1194
offset = file->offset;
1196
while (len > 0 && grub_errno == GRUB_ERR_NONE)
1198
register grub_size_t size;
1199
register char *srcaddr;
1201
while (offset >= gzio->saved_offset)
1202
inflate_window (file);
1204
srcaddr = (char *) ((offset & (WSIZE - 1)) + gzio->slide);
1205
size = gzio->saved_offset - offset;
1209
grub_memmove (buf, srcaddr, size);
1217
if (grub_errno != GRUB_ERR_NONE)
1223
/* Release everything, including the underlying file object. */
1225
grub_gzio_close (grub_file_t file)
1227
grub_gzio_t gzio = file->data;
1229
grub_file_close (gzio->file);
1230
huft_free (gzio->tl);
1231
huft_free (gzio->td);
1234
/* No need to close the same device twice. */
1242
static struct grub_fs grub_gzio_fs =
1247
.read = grub_gzio_read,
1248
.close = grub_gzio_close,
added
removed
io/gzio.c
