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>
44 #include <grub/deflate.h>
45 #include <grub/i18n.h>
46 #include <grub/crypto.h>
48 GRUB_MOD_LICENSE ("GPLv3+");
53 * This must be a power of two, and at least 32K for zip's deflate method
59 #define INBUFSIZ 0x2000
61 /* The state stored in filesystem-specific data. */
64 /* The underlying file object. */
66 /* If input is in memory following fields are used instead of file. */
67 grub_size_t mem_input_size, mem_input_off;
68 grub_uint8_t *mem_input;
69 /* The offset at which the data starts in the underlying file. */
70 grub_off_t data_offset;
71 /* The type of current block. */
73 /* The length of current block. */
75 /* The flag of the last block. */
77 /* The flag of codes. */
79 /* The length of a copy. */
81 /* The index of a copy. */
83 /* The input buffer. */
84 grub_uint8_t inbuf[INBUFSIZ];
88 /* The bits in the bit buffer. */
90 /* The sliding window in uncompressed data. */
91 grub_uint8_t slide[WSIZE];
92 /* Current position in the slide. */
94 /* The literal/length code table. */
96 /* The distance code table. */
98 /* The checksum algorithm */
99 const gcry_md_spec_t *hdesc;
100 /* The wanted checksum */
101 grub_uint32_t orig_checksum;
102 /* The uncompressed length */
103 grub_size_t orig_len;
104 /* Context for checksum calculation */
105 grub_uint8_t *hcontext;
106 /* The lookup bits for the literal/length code table. */
108 /* The lookup bits for the distance code table. */
110 /* The original offset value. */
111 grub_off_t saved_offset;
113 typedef struct grub_gzio *grub_gzio_t;
115 /* Declare the filesystem structure for grub_gzio_open. */
116 static struct grub_fs grub_gzio_fs;
118 /* Function prototypes */
119 static void initialize_tables (grub_gzio_t);
121 /* Eat variable-length header fields. */
123 eat_field (grub_file_t file, int len)
141 while ((not_retval = grub_file_read (file, &ch, 1)) == 1);
147 /* Little-Endian defines for the 2-byte magic numbers for gzip files. */
148 #define GZIP_MAGIC grub_le_to_cpu16 (0x8B1F)
149 #define OLD_GZIP_MAGIC grub_le_to_cpu16 (0x9E1F)
151 /* Compression methods (see algorithm.doc) */
152 #define GRUB_GZ_STORED 0
153 #define GRUB_GZ_COMPRESSED 1
154 #define GRUB_GZ_PACKED 2
155 #define GRUB_GZ_LZHED 3
156 /* methods 4 to 7 reserved */
157 #define GRUB_GZ_DEFLATED 8
158 #define GRUB_GZ_MAX_METHODS 9
161 #define GRUB_GZ_ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
162 #define GRUB_GZ_CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
163 #define GRUB_GZ_EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
164 #define GRUB_GZ_ORIG_NAME 0x08 /* bit 3 set: original file name present */
165 #define GRUB_GZ_COMMENT 0x10 /* bit 4 set: file comment present */
166 #define GRUB_GZ_ENCRYPTED 0x20 /* bit 5 set: file is encrypted */
167 #define GRUB_GZ_RESERVED 0xC0 /* bit 6,7: reserved */
169 #define GRUB_GZ_UNSUPPORTED_FLAGS (GRUB_GZ_CONTINUATION | GRUB_GZ_ENCRYPTED | GRUB_GZ_RESERVED)
171 /* inflate block codes */
172 #define INFLATE_STORED 0
173 #define INFLATE_FIXED 1
174 #define INFLATE_DYNAMIC 2
176 typedef unsigned char uch;
177 typedef unsigned short ush;
178 typedef unsigned long ulg;
181 test_gzip_header (grub_file_t file)
187 grub_uint32_t timestamp;
188 grub_uint8_t extra_flags;
189 grub_uint8_t os_type;
191 grub_uint16_t extra_len;
193 grub_gzio_t gzio = file->data;
195 if (grub_file_tell (gzio->file) != 0)
196 grub_file_seek (gzio->file, 0);
199 * This checks if the file is gzipped. If a problem occurs here
200 * (other than a real error with the disk) then we don't think it
201 * is a compressed file, and simply mark it as such.
203 if (grub_file_read (gzio->file, &hdr, 10) != 10
204 || ((hdr.magic != GZIP_MAGIC)
205 && (hdr.magic != OLD_GZIP_MAGIC)))
209 * This does consistency checking on the header data. If a
210 * problem occurs from here on, then we have corrupt or otherwise
211 * bad data, and the error should be reported to the user.
213 if (hdr.method != GRUB_GZ_DEFLATED
214 || (hdr.flags & GRUB_GZ_UNSUPPORTED_FLAGS)
215 || ((hdr.flags & GRUB_GZ_EXTRA_FIELD)
216 && (grub_file_read (gzio->file, &extra_len, 2) != 2
217 || eat_field (gzio->file,
218 grub_le_to_cpu16 (extra_len))))
219 || ((hdr.flags & GRUB_GZ_ORIG_NAME) && eat_field (gzio->file, -1))
220 || ((hdr.flags & GRUB_GZ_COMMENT) && eat_field (gzio->file, -1)))
223 gzio->data_offset = grub_file_tell (gzio->file);
225 /* FIXME: don't do this on not easily seekable files. */
227 grub_file_seek (gzio->file, grub_file_size (gzio->file) - 8);
228 if (grub_file_read (gzio->file, &crc32, 4) != 4)
230 gzio->orig_checksum = grub_le_to_cpu32 (crc32);
231 if (grub_file_read (gzio->file, &gzio->orig_len, 4) != 4)
233 /* FIXME: this does not handle files whose original size is over 4GB.
234 But how can we know the real original size? */
235 file->size = grub_le_to_cpu32 (gzio->orig_len);
238 initialize_tables (gzio);
244 /* Huffman code lookup table entry--this entry is four bytes for machines
245 that have 16-bit pointers (e.g. PC's in the small or medium model).
246 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16
247 means that v is a literal, 16 < e < 32 means that v is a pointer to
248 the next table, which codes e - 16 bits, and lastly e == 99 indicates
249 an unused code. If a code with e == 99 is looked up, this implies an
250 error in the data. */
253 uch e; /* number of extra bits or operation */
254 uch b; /* number of bits in this code or subcode */
257 ush n; /* literal, length base, or distance base */
258 struct huft *t; /* pointer to next level of table */
264 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed
265 stream to find repeated byte strings. This is implemented here as a
266 circular buffer. The index is updated simply by incrementing and then
267 and'ing with 0x7fff (32K-1). */
268 /* It is left to other modules to supply the 32K area. It is assumed
269 to be usable as if it were declared "uch slide[32768];" or as just
270 "uch *slide;" and then malloc'ed in the latter case. The definition
271 must be in unzip.h, included above. */
274 /* Tables for deflate from PKZIP's appnote.txt. */
275 static unsigned bitorder[] =
276 { /* Order of the bit length code lengths */
277 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
278 static ush cplens[] =
279 { /* Copy lengths for literal codes 257..285 */
280 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
281 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
282 /* note: see note #13 above about the 258 in this list. */
283 static ush cplext[] =
284 { /* Extra bits for literal codes 257..285 */
285 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
286 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
287 static ush cpdist[] =
288 { /* Copy offsets for distance codes 0..29 */
289 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
290 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
291 8193, 12289, 16385, 24577};
292 static ush cpdext[] =
293 { /* Extra bits for distance codes */
294 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
295 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
300 Huffman code decoding is performed using a multi-level table lookup.
301 The fastest way to decode is to simply build a lookup table whose
302 size is determined by the longest code. However, the time it takes
303 to build this table can also be a factor if the data being decoded
304 is not very long. The most common codes are necessarily the
305 shortest codes, so those codes dominate the decoding time, and hence
306 the speed. The idea is you can have a shorter table that decodes the
307 shorter, more probable codes, and then point to subsidiary tables for
308 the longer codes. The time it costs to decode the longer codes is
309 then traded against the time it takes to make longer tables.
311 This results of this trade are in the variables lbits and dbits
312 below. lbits is the number of bits the first level table for literal/
313 length codes can decode in one step, and dbits is the same thing for
314 the distance codes. Subsequent tables are also less than or equal to
315 those sizes. These values may be adjusted either when all of the
316 codes are shorter than that, in which case the longest code length in
317 bits is used, or when the shortest code is *longer* than the requested
318 table size, in which case the length of the shortest code in bits is
321 There are two different values for the two tables, since they code a
322 different number of possibilities each. The literal/length table
323 codes 286 possible values, or in a flat code, a little over eight
324 bits. The distance table codes 30 possible values, or a little less
325 than five bits, flat. The optimum values for speed end up being
326 about one bit more than those, so lbits is 8+1 and dbits is 5+1.
327 The optimum values may differ though from machine to machine, and
328 possibly even between compilers. Your mileage may vary.
332 static int lbits = 9; /* bits in base literal/length lookup table */
333 static int dbits = 6; /* bits in base distance lookup table */
336 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
337 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
338 #define N_MAX 288 /* maximum number of codes in any set */
341 /* Macros for inflate() bit peeking and grabbing.
345 x = b & mask_bits[j];
348 where NEEDBITS makes sure that b has at least j bits in it, and
349 DUMPBITS removes the bits from b. The macros use the variable k
350 for the number of bits in b. Normally, b and k are register
351 variables for speed, and are initialized at the beginning of a
352 routine that uses these macros from a global bit buffer and count.
354 If we assume that EOB will be the longest code, then we will never
355 ask for bits with NEEDBITS that are beyond the end of the stream.
356 So, NEEDBITS should not read any more bytes than are needed to
357 meet the request. Then no bytes need to be "returned" to the buffer
358 at the end of the last block.
360 However, this assumption is not true for fixed blocks--the EOB code
361 is 7 bits, but the other literal/length codes can be 8 or 9 bits.
362 (The EOB code is shorter than other codes because fixed blocks are
363 generally short. So, while a block always has an EOB, many other
364 literal/length codes have a significantly lower probability of
365 showing up at all.) However, by making the first table have a
366 lookup of seven bits, the EOB code will be found in that first
367 lookup, and so will not require that too many bits be pulled from
371 static ush mask_bits[] =
374 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
375 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
378 #define NEEDBITS(n) do {while(k<(n)){b|=((ulg)get_byte(gzio))<<k;k+=8;}} while (0)
379 #define DUMPBITS(n) do {b>>=(n);k-=(n);} while (0)
382 get_byte (grub_gzio_t gzio)
386 if (gzio->mem_input_off < gzio->mem_input_size)
387 return gzio->mem_input[gzio->mem_input_off++];
391 if (gzio->file && (grub_file_tell (gzio->file)
392 == (grub_off_t) gzio->data_offset
393 || gzio->inbuf_d == INBUFSIZ))
396 grub_file_read (gzio->file, gzio->inbuf, INBUFSIZ);
399 return gzio->inbuf[gzio->inbuf_d++];
403 gzio_seek (grub_gzio_t gzio, grub_off_t off)
407 if (off > gzio->mem_input_size)
408 grub_error (GRUB_ERR_OUT_OF_RANGE,
409 N_("attempt to seek outside of the file"));
411 gzio->mem_input_off = off;
414 grub_file_seek (gzio->file, off);
417 /* more function prototypes */
418 static int huft_build (unsigned *, unsigned, unsigned, ush *, ush *,
419 struct huft **, int *);
420 static int huft_free (struct huft *);
421 static int inflate_codes_in_window (grub_gzio_t);
424 /* Given a list of code lengths and a maximum table size, make a set of
425 tables to decode that set of codes. Return zero on success, one if
426 the given code set is incomplete (the tables are still built in this
427 case), two if the input is invalid (all zero length codes or an
428 oversubscribed set of lengths), and three if not enough memory. */
431 huft_build (unsigned *b, /* code lengths in bits (all assumed <= BMAX) */
432 unsigned n, /* number of codes (assumed <= N_MAX) */
433 unsigned s, /* number of simple-valued codes (0..s-1) */
434 ush * d, /* list of base values for non-simple codes */
435 ush * e, /* list of extra bits for non-simple codes */
436 struct huft **t, /* result: starting table */
437 int *m) /* maximum lookup bits, returns actual */
439 unsigned a; /* counter for codes of length k */
440 unsigned c[BMAX + 1]; /* bit length count table */
441 unsigned f; /* i repeats in table every f entries */
442 int g; /* maximum code length */
443 int h; /* table level */
444 register unsigned i; /* counter, current code */
445 register unsigned j; /* counter */
446 register int k; /* number of bits in current code */
447 int l; /* bits per table (returned in m) */
448 register unsigned *p; /* pointer into c[], b[], or v[] */
449 register struct huft *q; /* points to current table */
450 struct huft r; /* table entry for structure assignment */
451 struct huft *u[BMAX]; /* table stack */
452 unsigned v[N_MAX]; /* values in order of bit length */
453 register int w; /* bits before this table == (l * h) */
454 unsigned x[BMAX + 1]; /* bit offsets, then code stack */
455 unsigned *xp; /* pointer into x */
456 int y; /* number of dummy codes added */
457 unsigned z; /* number of entries in current table */
459 /* Generate counts for each bit length */
460 grub_memset ((char *) c, 0, sizeof (c));
465 c[*p]++; /* assume all entries <= BMAX */
466 p++; /* Can't combine with above line (Solaris bug) */
469 if (c[0] == n) /* null input--all zero length codes */
471 *t = (struct huft *) NULL;
476 /* Find minimum and maximum length, bound *m by those */
478 for (j = 1; j <= BMAX; j++)
481 k = j; /* minimum code length */
482 if ((unsigned) l < j)
484 for (i = BMAX; i; i--)
487 g = i; /* maximum code length */
488 if ((unsigned) l > i)
492 /* Adjust last length count to fill out codes, if needed */
493 for (y = 1 << j; j < i; j++, y <<= 1)
495 return 2; /* bad input: more codes than bits */
500 /* Generate starting offsets into the value table for each length */
505 { /* note that i == g from above */
509 /* Make a table of values in order of bit lengths */
519 /* Generate the Huffman codes and for each, make the table entries */
520 x[0] = i = 0; /* first Huffman code is zero */
521 p = v; /* grab values in bit order */
522 h = -1; /* no tables yet--level -1 */
523 w = -l; /* bits decoded == (l * h) */
524 u[0] = (struct huft *) NULL; /* just to keep compilers happy */
525 q = (struct huft *) NULL; /* ditto */
528 /* go through the bit lengths (k already is bits in shortest code) */
534 /* here i is the Huffman code of length k bits for value *p */
535 /* make tables up to required level */
539 w += l; /* previous table always l bits */
541 /* compute minimum size table less than or equal to l bits */
542 z = (z = (unsigned) (g - w)) > (unsigned) l ? (unsigned) l : z; /* upper limit on table size */
543 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
544 { /* too few codes for k-w bit table */
545 f -= a + 1; /* deduct codes from patterns left */
547 while (++j < z) /* try smaller tables up to z bits */
549 if ((f <<= 1) <= *++xp)
550 break; /* enough codes to use up j bits */
551 f -= *xp; /* else deduct codes from patterns */
554 z = 1 << j; /* table entries for j-bit table */
556 /* allocate and link in new table */
557 q = (struct huft *) grub_zalloc ((z + 1) * sizeof (struct huft));
565 *t = q + 1; /* link to list for huft_free() */
566 *(t = &(q->v.t)) = (struct huft *) NULL;
567 u[h] = ++q; /* table starts after link */
569 /* connect to last table, if there is one */
572 x[h] = i; /* save pattern for backing up */
573 r.b = (uch) l; /* bits to dump before this table */
574 r.e = (uch) (16 + j); /* bits in this table */
575 r.v.t = q; /* pointer to this table */
576 j = i >> (w - l); /* (get around Turbo C bug) */
577 u[h - 1][j] = r; /* connect to last table */
581 /* set up table entry in r */
584 r.e = 99; /* out of values--invalid code */
587 r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block code */
588 r.v.n = (ush) (*p); /* simple code is just the value */
589 p++; /* one compiler does not like *p++ */
593 r.e = (uch) e[*p - s]; /* non-simple--look up in lists */
597 /* fill code-like entries with r */
599 for (j = i >> w; j < z; j += f)
602 /* backwards increment the k-bit code i */
603 for (j = 1 << (k - 1); i & j; j >>= 1)
607 /* backup over finished tables */
608 while ((i & ((1 << w) - 1)) != x[h])
610 h--; /* don't need to update q */
616 /* Return true (1) if we were given an incomplete table */
617 return y != 0 && g != 1;
621 /* Free the malloc'ed tables built by huft_build(), which makes a linked
622 list of the tables it made, with the links in a dummy first entry of
625 huft_free (struct huft *t)
627 register struct huft *p, *q;
630 /* Go through linked list, freeing from the malloced (t[-1]) address. */
632 while (p != (struct huft *) NULL)
635 grub_free ((char *) p);
643 * inflate (decompress) the codes in a deflated (compressed) block.
644 * Return an error code or zero if it all goes ok.
648 inflate_codes_in_window (grub_gzio_t gzio)
650 register unsigned e; /* table entry flag/number of extra bits */
651 unsigned n, d; /* length and index for copy */
652 unsigned w; /* current window position */
653 struct huft *t; /* pointer to table entry */
654 unsigned ml, md; /* masks for bl and bd bits */
655 register ulg b; /* bit buffer */
656 register unsigned k; /* number of bits in bit buffer */
658 /* make local copies of globals */
661 b = gzio->bb; /* initialize bit buffer */
663 w = gzio->wp; /* initialize window position */
665 /* inflate the coded data */
666 ml = mask_bits[gzio->bl]; /* precompute masks for speed */
667 md = mask_bits[gzio->bd];
668 for (;;) /* do until end of block */
670 if (! gzio->code_state)
672 NEEDBITS ((unsigned) gzio->bl);
673 if ((e = (t = gzio->tl + ((unsigned) b & ml))->e) > 16)
678 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
679 "an unused code found");
686 while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
689 if (e == 16) /* then it's a literal */
691 gzio->slide[w++] = (uch) t->v.n;
696 /* it's an EOB or a length */
698 /* exit if end of block */
705 /* get length of block to copy */
707 n = t->v.n + ((unsigned) b & mask_bits[e]);
710 /* decode distance of block to copy */
711 NEEDBITS ((unsigned) gzio->bd);
712 if ((e = (t = gzio->td + ((unsigned) b & md))->e) > 16)
717 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
718 "an unused code found");
725 while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e)
729 d = w - t->v.n - ((unsigned) b & mask_bits[e]);
735 if (gzio->code_state)
740 n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n
745 grub_memmove (gzio->slide + w, gzio->slide + d, e);
750 /* purposefully use the overlap for extra copies here!! */
753 gzio->slide[w++] = gzio->slide[d++];
764 /* did we break from the loop too soon? */
770 /* restore the globals from the locals */
773 gzio->wp = w; /* restore global window pointer */
774 gzio->bb = b; /* restore global bit buffer */
777 return ! gzio->block_len;
781 /* get header for an inflated type 0 (stored) block. */
784 init_stored_block (grub_gzio_t gzio)
786 register ulg b; /* bit buffer */
787 register unsigned k; /* number of bits in bit buffer */
789 /* make local copies of globals */
790 b = gzio->bb; /* initialize bit buffer */
793 /* go to byte boundary */
796 /* get the length and its complement */
798 gzio->block_len = ((unsigned) b & 0xffff);
801 if (gzio->block_len != (int) ((~b) & 0xffff))
802 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
803 "the length of a stored block does not match");
806 /* restore global variables */
812 /* get header for an inflated type 1 (fixed Huffman codes) block. We should
813 either replace this with a custom decoder, or at least precompute the
817 init_fixed_block (grub_gzio_t gzio)
819 int i; /* temporary variable */
820 unsigned l[288]; /* length list for huft_build */
822 /* set up literal table */
823 for (i = 0; i < 144; i++)
829 for (; i < 288; i++) /* make a complete, but wrong code set */
832 if (huft_build (l, 288, 257, cplens, cplext, &gzio->tl, &gzio->bl) != 0)
834 if (grub_errno == GRUB_ERR_NONE)
835 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
836 "failed in building a Huffman code table");
840 /* set up distance table */
841 for (i = 0; i < 30; i++) /* make an incomplete code set */
844 if (huft_build (l, 30, 0, cpdist, cpdext, &gzio->td, &gzio->bd) > 1)
846 if (grub_errno == GRUB_ERR_NONE)
847 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
848 "failed in building a Huffman code table");
849 huft_free (gzio->tl);
854 /* indicate we're now working on a block */
855 gzio->code_state = 0;
860 /* get header for an inflated type 2 (dynamic Huffman codes) block. */
863 init_dynamic_block (grub_gzio_t gzio)
865 int i; /* temporary variables */
867 unsigned l; /* last length */
868 unsigned m; /* mask for bit lengths table */
869 unsigned n; /* number of lengths to get */
870 unsigned nb; /* number of bit length codes */
871 unsigned nl; /* number of literal/length codes */
872 unsigned nd; /* number of distance codes */
873 unsigned ll[286 + 30]; /* literal/length and distance code lengths */
874 register ulg b; /* bit buffer */
875 register unsigned k; /* number of bits in bit buffer */
877 /* make local bit buffer */
881 /* read in table lengths */
883 nl = 257 + ((unsigned) b & 0x1f); /* number of literal/length codes */
886 nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */
889 nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */
891 if (nl > 286 || nd > 30)
893 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "too much data");
897 /* read in bit-length-code lengths */
898 for (j = 0; j < nb; j++)
901 ll[bitorder[j]] = (unsigned) b & 7;
907 /* build decoding table for trees--single level, 7 bit lookup */
909 if (huft_build (ll, 19, 19, NULL, NULL, &gzio->tl, &gzio->bl) != 0)
911 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
912 "failed in building a Huffman code table");
916 /* read in literal and distance code lengths */
918 m = mask_bits[gzio->bl];
920 while ((unsigned) i < n)
922 NEEDBITS ((unsigned) gzio->bl);
923 j = (gzio->td = gzio->tl + ((unsigned) b & m))->b;
926 if (j < 16) /* length of code in bits (0..15) */
927 ll[i++] = l = j; /* save last length in l */
928 else if (j == 16) /* repeat last length 3 to 6 times */
931 j = 3 + ((unsigned) b & 3);
933 if ((unsigned) i + j > n)
935 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "too many codes found");
941 else if (j == 17) /* 3 to 10 zero length codes */
944 j = 3 + ((unsigned) b & 7);
946 if ((unsigned) i + j > n)
948 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "too many codes found");
956 /* j == 18: 11 to 138 zero length codes */
959 j = 11 + ((unsigned) b & 0x7f);
961 if ((unsigned) i + j > n)
963 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "too many codes found");
972 /* free decoding table for trees */
973 huft_free (gzio->tl);
977 /* restore the global bit buffer */
981 /* build the decoding tables for literal/length and distance codes */
983 if (huft_build (ll, nl, 257, cplens, cplext, &gzio->tl, &gzio->bl) != 0)
985 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
986 "failed in building a Huffman code table");
990 if (huft_build (ll + nl, nd, 0, cpdist, cpdext, &gzio->td, &gzio->bd) != 0)
992 huft_free (gzio->tl);
994 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
995 "failed in building a Huffman code table");
999 /* indicate we're now working on a block */
1000 gzio->code_state = 0;
1006 get_new_block (grub_gzio_t gzio)
1008 register ulg b; /* bit buffer */
1009 register unsigned k; /* number of bits in bit buffer */
1011 /* make local bit buffer */
1015 /* read in last block bit */
1017 gzio->last_block = (int) b & 1;
1020 /* read in block type */
1022 gzio->block_type = (unsigned) b & 3;
1025 /* restore the global bit buffer */
1029 switch (gzio->block_type)
1031 case INFLATE_STORED:
1032 init_stored_block (gzio);
1035 init_fixed_block (gzio);
1037 case INFLATE_DYNAMIC:
1038 init_dynamic_block (gzio);
1047 inflate_window (grub_gzio_t gzio)
1049 /* initialize window */
1053 * Main decompression loop.
1056 while (gzio->wp < WSIZE && grub_errno == GRUB_ERR_NONE)
1058 if (! gzio->block_len)
1060 if (gzio->last_block)
1063 get_new_block (gzio);
1066 if (gzio->block_type > INFLATE_DYNAMIC)
1067 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
1068 "unknown block type %d", gzio->block_type);
1070 if (grub_errno != GRUB_ERR_NONE)
1074 * Expand stored block here.
1076 if (gzio->block_type == INFLATE_STORED)
1081 * This is basically a glorified pass-through
1084 while (gzio->block_len && w < WSIZE && grub_errno == GRUB_ERR_NONE)
1086 gzio->slide[w++] = get_byte (gzio);
1096 * Expand other kind of block.
1099 if (inflate_codes_in_window (gzio))
1101 huft_free (gzio->tl);
1102 huft_free (gzio->td);
1108 gzio->saved_offset += gzio->wp;
1112 gzio->hdesc->write (gzio->hcontext, gzio->slide, gzio->wp);
1114 if (gzio->saved_offset == gzio->orig_len)
1118 gzio->hdesc->final (gzio->hcontext);
1119 csum = *(grub_uint32_t *)gzio->hdesc->read (gzio->hcontext);
1120 csum = grub_be_to_cpu32 (csum);
1121 if (csum != gzio->orig_checksum)
1122 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
1123 "checksum mismatch %08x/%08x",
1124 gzio->orig_checksum, csum);
1131 initialize_tables (grub_gzio_t gzio)
1133 gzio->saved_offset = 0;
1134 gzio_seek (gzio, gzio->data_offset);
1136 /* Initialize the bit buffer. */
1140 /* Reset partial decompression code. */
1141 gzio->last_block = 0;
1142 gzio->block_len = 0;
1144 /* Reset memory allocation stuff. */
1145 huft_free (gzio->tl);
1146 huft_free (gzio->td);
1151 gzio->hdesc->init(gzio->hcontext);
1155 /* Open a new decompressing object on the top of IO. If TRANSPARENT is true,
1156 even if IO does not contain data compressed by gzip, return a valid file
1157 object. Note that this function won't close IO, even if an error occurs. */
1159 grub_gzio_open (grub_file_t io, const char *name __attribute__ ((unused)))
1162 grub_gzio_t gzio = 0;
1164 file = (grub_file_t) grub_zalloc (sizeof (*file));
1168 gzio = grub_zalloc (sizeof (*gzio));
1177 gzio->hdesc = GRUB_MD_CRC32;
1178 gzio->hcontext = grub_malloc(gzio->hdesc->contextsize);
1180 file->device = io->device;
1182 file->fs = &grub_gzio_fs;
1183 file->not_easily_seekable = 1;
1185 if (! test_gzip_header (file))
1187 grub_errno = GRUB_ERR_NONE;
1188 grub_free (gzio->hcontext);
1191 grub_file_seek (io, 0);
1200 mod_31 (grub_uint16_t v)
1202 /* At most 2 iterations for any number that
1204 In any case faster than real division. */
1206 v = (v & 0x1f) + (v >> 5);
1213 test_zlib_header (grub_gzio_t gzio)
1215 grub_uint8_t cmf, flg;
1217 cmf = get_byte (gzio);
1218 flg = get_byte (gzio);
1220 /* Check that compression method is DEFLATE. */
1221 if ((cmf & 0xf) != GRUB_GZ_DEFLATED)
1223 /* TRANSLATORS: It's about given file having some strange format, not
1224 complete lack of gzip support. */
1225 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, N_("unsupported gzip format"));
1229 /* Usually it would be: (cmf * 256 + flg) % 31 != 0. */
1230 /* But 256 == 8 (31). */
1231 /* By multiplying by 4 and using 32 == 1 (31). We get our formula. */
1232 if (mod_31 (cmf + flg * 4) != 0)
1234 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, N_("unsupported gzip format"));
1238 /* Dictionary isn't supported. */
1241 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, N_("unsupported gzip format"));
1245 gzio->data_offset = 2;
1246 initialize_tables (gzio);
1252 grub_gzio_read_real (grub_gzio_t gzio, grub_off_t offset,
1253 char *buf, grub_size_t len)
1255 grub_ssize_t ret = 0;
1257 /* Do we reset decompression to the beginning of the file? */
1258 if (gzio->saved_offset > offset + WSIZE)
1259 initialize_tables (gzio);
1262 * This loop operates upon uncompressed data only. The only
1263 * special thing it does is to make sure the decompression
1264 * window is within the range of data it needs.
1267 while (len > 0 && grub_errno == GRUB_ERR_NONE)
1269 register grub_size_t size;
1270 register char *srcaddr;
1272 while (offset >= gzio->saved_offset)
1274 inflate_window (gzio);
1282 srcaddr = (char *) ((offset & (WSIZE - 1)) + gzio->slide);
1283 size = gzio->saved_offset - offset;
1287 grub_memmove (buf, srcaddr, size);
1296 if (grub_errno != GRUB_ERR_NONE)
1303 grub_gzio_read (grub_file_t file, char *buf, grub_size_t len)
1306 ret = grub_gzio_read_real (file->data, file->offset, buf, len);
1308 if (!grub_errno && ret != (grub_ssize_t) len)
1310 grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "premature end of compressed");
1316 /* Release everything, including the underlying file object. */
1318 grub_gzio_close (grub_file_t file)
1320 grub_gzio_t gzio = file->data;
1322 grub_file_close (gzio->file);
1323 huft_free (gzio->tl);
1324 huft_free (gzio->td);
1325 grub_free (gzio->hcontext);
1328 /* No need to close the same device twice. */
1336 grub_zlib_decompress (char *inbuf, grub_size_t insize, grub_off_t off,
1337 char *outbuf, grub_size_t outsize)
1339 grub_gzio_t gzio = 0;
1342 gzio = grub_zalloc (sizeof (*gzio));
1345 gzio->mem_input = (grub_uint8_t *) inbuf;
1346 gzio->mem_input_size = insize;
1347 gzio->mem_input_off = 0;
1349 if (!test_zlib_header (gzio))
1355 ret = grub_gzio_read_real (gzio, off, outbuf, outsize);
1358 /* FIXME: Check Adler. */
1363 grub_deflate_decompress (char *inbuf, grub_size_t insize, grub_off_t off,
1364 char *outbuf, grub_size_t outsize)
1366 grub_gzio_t gzio = 0;
1369 gzio = grub_zalloc (sizeof (*gzio));
1372 gzio->mem_input = (grub_uint8_t *) inbuf;
1373 gzio->mem_input_size = insize;
1374 gzio->mem_input_off = 0;
1376 initialize_tables (gzio);
1378 ret = grub_gzio_read_real (gzio, off, outbuf, outsize);
1386 static struct grub_fs grub_gzio_fs =
1391 .read = grub_gzio_read,
1392 .close = grub_gzio_close,
1399 grub_file_filter_register (GRUB_FILE_FILTER_GZIO, grub_gzio_open);
1404 grub_file_filter_unregister (GRUB_FILE_FILTER_GZIO);