« back to all changes in this revision
Viewing changes to io/gzio.c
- browse files at revision 1.1.2
- compare with another revision
- download diff
- download tarball
- view history from revision 1.1.2
- Committer: Bazaar Package Importer
- Author(s): Otavio Salvador
- Date: 2006-01-05 15:20:40 UTC
- mto: (17.3.1 squeeze) (1.9.1 upstream)
- mto: This revision was merged to the branch mainline in revision 4.
- Revision ID: james.westby@ubuntu.com-20060105152040-b72i5pq1a82z22yi
Tags: upstream-1.92
Import upstream version 1.92
- files added:
- AUTHORS
- boot
- boot/i386
- boot/i386/pc
- commands
- commands/i386
- commands/i386/pc
- commands/ieee1275
- conf
- disk
- disk/i386
- disk/i386/pc
- disk/ieee1275
- font
- fs
- hello
- include
- include/grub
- include/grub/i386
- include/grub/i386/pc
- include/grub/i386/pc/util
- include/grub/ieee1275
- include/grub/powerpc
- include/grub/powerpc/ieee1275
- include/grub/powerpc/ieee1275/util
- include/grub/sparc64
- include/grub/sparc64/ieee1275
- include/grub/util
- io
- kern
- kern/i386
- kern/i386/pc
- kern/ieee1275
- kern/powerpc
- kern/powerpc/ieee1275
- kern/sparc64
- kern/sparc64/ieee1275
- loader
- loader/i386
- loader/i386/pc
- loader/powerpc
- loader/powerpc/ieee1275
- normal
- normal/i386
- normal/powerpc
- partmap
- term
- term/i386
- term/i386/pc
- term/ieee1275
- util
- util/i386
- util/i386/pc
- util/powerpc
- util/powerpc/ieee1275
- video
- video/i386
- video/i386/pc
- files removed:
- src.tar.gz
added
removed
io/gzio.c
1
/* gzio.c - decompression support for gzip */
2
/*
3
* GRUB -- GRand Unified Bootloader
4
* Copyright (C) 1999,2005 Free Software Foundation, Inc.
5
*
6
* This program 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 2 of the License, or
9
* (at your option) any later version.
10
*
11
* This program 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.
15
*
16
* You should have received a copy of the GNU General Public License
17
* along with this program; if not, write to the Free Software
18
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19
*/
20
21
/*
22
* Most of this file was originally the source file "inflate.c", written
23
* by Mark Adler. It has been very heavily modified. In particular, the
24
* original would run through the whole file at once, and this version can
25
* be stopped and restarted on any boundary during the decompression process.
26
*
27
* The license and header comments that file are included here.
28
*/
29
30
/* inflate.c -- Not copyrighted 1992 by Mark Adler
31
version c10p1, 10 January 1993 */
32
33
/* You can do whatever you like with this source file, though I would
34
prefer that if you modify it and redistribute it that you include
35
comments to that effect with your name and the date. Thank you.
36
*/
37
38
#include <grub/err.h>
39
#include <grub/types.h>
40
#include <grub/mm.h>
41
#include <grub/misc.h>
42
#include <grub/fs.h>
43
#include <grub/file.h>
44
#include <grub/gzio.h>
45
46
/*
47
* Window Size
48
*
49
* This must be a power of two, and at least 32K for zip's deflate method
50
*/
51
52
#define WSIZE 0x8000
53
54
55
#define INBUFSIZ 0x2000
56
57
/* The state stored in filesystem-specific data. */
58
struct grub_gzio
59
{
60
/* The underlyding file object. */
61
grub_file_t file;
62
/* The offset at which the data starts in the underlyding file. */
63
grub_ssize_t data_offset;
64
/* The type of current block. */
65
int block_type;
66
/* The length of current block. */
67
int block_len;
68
/* The flag of the last block. */
69
int last_block;
70
/* The flag of codes. */
71
int code_state;
72
/* The length of a copy. */
73
unsigned inflate_n;
74
/* The index of a copy. */
75
unsigned inflate_d;
76
/* The input buffer. */
77
grub_uint8_t inbuf[INBUFSIZ];
78
int inbuf_d;
79
/* The bit buffer. */
80
unsigned long bb;
81
/* The bits in the bit buffer. */
82
unsigned bk;
83
/* Ths sliding window in uncompressed data. */
84
grub_uint8_t slide[WSIZE];
85
/* Current position in the slide. */
86
unsigned wp;
87
/* The literal/length code table. */
88
struct huft *tl;
89
/* The distance code table. */
90
struct huft *td;
91
/* The lookup bits for the literal/length code table. */
92
int bl;
93
/* The lookup bits for the distance code table. */
94
int bd;
95
/* The original offset value. */
96
grub_ssize_t saved_offset;
97
};
98
typedef struct grub_gzio *grub_gzio_t;
99
100
/* Declare the filesystem structure for grub_gzio_open. */
101
static struct grub_fs grub_gzio_fs;
102
103
/* Function prototypes */
104
static void initialize_tables (grub_file_t file);
105
106
/* Eat variable-length header fields. */
107
static int
108
eat_field (grub_file_t file, int len)
109
{
110
char ch = 1;
111
int not_retval = 1;
112
113
do
114
{
115
if (len >= 0)
116
{
117
if (! (len--))
118
break;
119
}
120
else
121
{
122
if (! ch)
123
break;
124
}
125
}
126
while ((not_retval = grub_file_read (file, &ch, 1)) == 1);
127
128
return ! not_retval;
129
}
130
131
132
/* Little-Endian defines for the 2-byte magic numbers for gzip files. */
133
#define GZIP_MAGIC grub_le_to_cpu16 (0x8B1F)
134
#define OLD_GZIP_MAGIC grub_le_to_cpu16 (0x9E1F)
135
136
/* Compression methods (see algorithm.doc) */
137
#define STORED 0
138
#define COMPRESSED 1
139
#define PACKED 2
140
#define LZHED 3
141
/* methods 4 to 7 reserved */
142
#define DEFLATED 8
143
#define MAX_METHODS 9
144
145
/* gzip flag byte */
146
#define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
147
#define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
148
#define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
149
#define ORIG_NAME 0x08 /* bit 3 set: original file name present */
150
#define COMMENT 0x10 /* bit 4 set: file comment present */
151
#define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */
152
#define RESERVED 0xC0 /* bit 6,7: reserved */
153
154
#define UNSUPPORTED_FLAGS (CONTINUATION | ENCRYPTED | RESERVED)
155
156
/* inflate block codes */
157
#define INFLATE_STORED 0
158
#define INFLATE_FIXED 1
159
#define INFLATE_DYNAMIC 2
160
161
typedef unsigned char uch;
162
typedef unsigned short ush;
163
typedef unsigned long ulg;
164
165
static int
166
test_header (grub_file_t file)
167
{
168
unsigned char buf[10] __attribute__ ((aligned));
169
grub_gzio_t gzio = file->data;
170
171
if (grub_file_tell (gzio->file) != 0)
172
grub_file_seek (gzio->file, 0);
173
174
/*
175
* This checks if the file is gzipped. If a problem occurs here
176
* (other than a real error with the disk) then we don't think it
177
* is a compressed file, and simply mark it as such.
178
*/
179
if (grub_file_read (gzio->file, buf, 10) != 10
180
|| ((*((grub_uint16_t *) buf) != GZIP_MAGIC)
181
&& (*((grub_uint16_t *) buf) != OLD_GZIP_MAGIC)))
182
{
183
grub_error (GRUB_ERR_BAD_FILE_TYPE, "no gzip magic found");
184
return 0;
185
}
186
187
/*
188
* This does consistency checking on the header data. If a
189
* problem occurs from here on, then we have corrupt or otherwise
190
* bad data, and the error should be reported to the user.
191
*/
192
if (buf[2] != DEFLATED
193
|| (buf[3] & UNSUPPORTED_FLAGS)
194
|| ((buf[3] & EXTRA_FIELD)
195
&& (grub_file_read (gzio->file, buf, 2) != 2
196
|| eat_field (gzio->file,
197
grub_le_to_cpu16 (*((grub_uint16_t *) buf)))))
198
|| ((buf[3] & ORIG_NAME) && eat_field (gzio->file, -1))
199
|| ((buf[3] & COMMENT) && eat_field (gzio->file, -1)))
200
{
201
grub_error (GRUB_ERR_BAD_GZIP_DATA, "unsupported gzip format");
202
return 0;
203
}
204
205
gzio->data_offset = grub_file_tell (gzio->file);
206
207
grub_file_seek (gzio->file, grub_file_size (gzio->file) - 8);
208
209
if (grub_file_read (gzio->file, buf, 8) != 8)
210
{
211
grub_error (GRUB_ERR_BAD_FILE_TYPE, "unsupported gzip format");
212
return 0;
213
}
214
215
file->size = grub_le_to_cpu32 (*((grub_uint32_t *) (buf + 4)));
216
217
initialize_tables (file);
218
219
return 1;
220
}
221
222
223
/* Huffman code lookup table entry--this entry is four bytes for machines
224
that have 16-bit pointers (e.g. PC's in the small or medium model).
225
Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16
226
means that v is a literal, 16 < e < 32 means that v is a pointer to
227
the next table, which codes e - 16 bits, and lastly e == 99 indicates
228
an unused code. If a code with e == 99 is looked up, this implies an
229
error in the data. */
230
struct huft
231
{
232
uch e; /* number of extra bits or operation */
233
uch b; /* number of bits in this code or subcode */
234
union
235
{
236
ush n; /* literal, length base, or distance base */
237
struct huft *t; /* pointer to next level of table */
238
}
239
v;
240
};
241
242
243
/* The inflate algorithm uses a sliding 32K byte window on the uncompressed
244
stream to find repeated byte strings. This is implemented here as a
245
circular buffer. The index is updated simply by incrementing and then
246
and'ing with 0x7fff (32K-1). */
247
/* It is left to other modules to supply the 32K area. It is assumed
248
to be usable as if it were declared "uch slide[32768];" or as just
249
"uch *slide;" and then malloc'ed in the latter case. The definition
250
must be in unzip.h, included above. */
251
252
253
/* Tables for deflate from PKZIP's appnote.txt. */
254
static unsigned bitorder[] =
255
{ /* Order of the bit length code lengths */
256
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
257
static ush cplens[] =
258
{ /* Copy lengths for literal codes 257..285 */
259
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
260
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
261
/* note: see note #13 above about the 258 in this list. */
262
static ush cplext[] =
263
{ /* Extra bits for literal codes 257..285 */
264
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
265
3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
266
static ush cpdist[] =
267
{ /* Copy offsets for distance codes 0..29 */
268
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
269
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
270
8193, 12289, 16385, 24577};
271
static ush cpdext[] =
272
{ /* Extra bits for distance codes */
273
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
274
7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
275
12, 12, 13, 13};
276
277
278
/*
279
Huffman code decoding is performed using a multi-level table lookup.
280
The fastest way to decode is to simply build a lookup table whose
281
size is determined by the longest code. However, the time it takes
282
to build this table can also be a factor if the data being decoded
283
is not very long. The most common codes are necessarily the
284
shortest codes, so those codes dominate the decoding time, and hence
285
the speed. The idea is you can have a shorter table that decodes the
286
shorter, more probable codes, and then point to subsidiary tables for
287
the longer codes. The time it costs to decode the longer codes is
288
then traded against the time it takes to make longer tables.
289
290
This results of this trade are in the variables lbits and dbits
291
below. lbits is the number of bits the first level table for literal/
292
length codes can decode in one step, and dbits is the same thing for
293
the distance codes. Subsequent tables are also less than or equal to
294
those sizes. These values may be adjusted either when all of the
295
codes are shorter than that, in which case the longest code length in
296
bits is used, or when the shortest code is *longer* than the requested
297
table size, in which case the length of the shortest code in bits is
298
used.
299
300
There are two different values for the two tables, since they code a
301
different number of possibilities each. The literal/length table
302
codes 286 possible values, or in a flat code, a little over eight
303
bits. The distance table codes 30 possible values, or a little less
304
than five bits, flat. The optimum values for speed end up being
305
about one bit more than those, so lbits is 8+1 and dbits is 5+1.
306
The optimum values may differ though from machine to machine, and
307
possibly even between compilers. Your mileage may vary.
308
*/
309
310
311
static int lbits = 9; /* bits in base literal/length lookup table */
312
static int dbits = 6; /* bits in base distance lookup table */
313
314
315
/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
316
#define BMAX 16 /* maximum bit length of any code (16 for explode) */
317
#define N_MAX 288 /* maximum number of codes in any set */
318
319
320
/* Macros for inflate() bit peeking and grabbing.
321
The usage is:
322
323
NEEDBITS(j)
324
x = b & mask_bits[j];
325
DUMPBITS(j)
326
327
where NEEDBITS makes sure that b has at least j bits in it, and
328
DUMPBITS removes the bits from b. The macros use the variable k
329
for the number of bits in b. Normally, b and k are register
330
variables for speed, and are initialized at the beginning of a
331
routine that uses these macros from a global bit buffer and count.
332
333
If we assume that EOB will be the longest code, then we will never
334
ask for bits with NEEDBITS that are beyond the end of the stream.
335
So, NEEDBITS should not read any more bytes than are needed to
336
meet the request. Then no bytes need to be "returned" to the buffer
337
at the end of the last block.
338
339
However, this assumption is not true for fixed blocks--the EOB code
340
is 7 bits, but the other literal/length codes can be 8 or 9 bits.
341
(The EOB code is shorter than other codes because fixed blocks are
342
generally short. So, while a block always has an EOB, many other
343
literal/length codes have a significantly lower probability of
344
showing up at all.) However, by making the first table have a
345
lookup of seven bits, the EOB code will be found in that first
346
lookup, and so will not require that too many bits be pulled from
347
the stream.
348
*/
349
350
static ush mask_bits[] =
351
{
352
0x0000,
353
0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
354
0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
355
};
356
357
#define NEEDBITS(n) do {while(k<(n)){b|=((ulg)get_byte(file))<<k;k+=8;}} while (0)
358
#define DUMPBITS(n) do {b>>=(n);k-=(n);} while (0)
359
360
static int
361
get_byte (grub_file_t file)
362
{
363
grub_gzio_t gzio = file->data;
364
365
if (grub_file_tell (gzio->file) == gzio->data_offset
366
|| gzio->inbuf_d == INBUFSIZ)
367
{
368
gzio->inbuf_d = 0;
369
grub_file_read (gzio->file, gzio->inbuf, INBUFSIZ);
370
}
371
372
return gzio->inbuf[gzio->inbuf_d++];
373
}
374
375
/* more function prototypes */
376
static int huft_build (unsigned *, unsigned, unsigned, ush *, ush *,
377
struct huft **, int *);
378
static int huft_free (struct huft *);
379
static int inflate_codes_in_window (grub_file_t);
380
381
382
/* Given a list of code lengths and a maximum table size, make a set of
383
tables to decode that set of codes. Return zero on success, one if
384
the given code set is incomplete (the tables are still built in this
385
case), two if the input is invalid (all zero length codes or an
386
oversubscribed set of lengths), and three if not enough memory. */
387
388
static int
389
huft_build (unsigned *b, /* code lengths in bits (all assumed <= BMAX) */
390
unsigned n, /* number of codes (assumed <= N_MAX) */
391
unsigned s, /* number of simple-valued codes (0..s-1) */
392
ush * d, /* list of base values for non-simple codes */
393
ush * e, /* list of extra bits for non-simple codes */
394
struct huft **t, /* result: starting table */
395
int *m) /* maximum lookup bits, returns actual */
396
{
397
unsigned a; /* counter for codes of length k */
398
unsigned c[BMAX + 1]; /* bit length count table */
399
unsigned f; /* i repeats in table every f entries */
400
int g; /* maximum code length */
401
int h; /* table level */
402
register unsigned i; /* counter, current code */
403
register unsigned j; /* counter */
404
register int k; /* number of bits in current code */
405
int l; /* bits per table (returned in m) */
406
register unsigned *p; /* pointer into c[], b[], or v[] */
407
register struct huft *q; /* points to current table */
408
struct huft r; /* table entry for structure assignment */
409
struct huft *u[BMAX]; /* table stack */
410
unsigned v[N_MAX]; /* values in order of bit length */
411
register int w; /* bits before this table == (l * h) */
412
unsigned x[BMAX + 1]; /* bit offsets, then code stack */
413
unsigned *xp; /* pointer into x */
414
int y; /* number of dummy codes added */
415
unsigned z; /* number of entries in current table */
416
417
/* Generate counts for each bit length */
418
grub_memset ((char *) c, 0, sizeof (c));
419
p = b;
420
i = n;
421
do
422
{
423
c[*p]++; /* assume all entries <= BMAX */
424
p++; /* Can't combine with above line (Solaris bug) */
425
}
426
while (--i);
427
if (c[0] == n) /* null input--all zero length codes */
428
{
429
*t = (struct huft *) NULL;
430
*m = 0;
431
return 0;
432
}
433
434
/* Find minimum and maximum length, bound *m by those */
435
l = *m;
436
for (j = 1; j <= BMAX; j++)
437
if (c[j])
438
break;
439
k = j; /* minimum code length */
440
if ((unsigned) l < j)
441
l = j;
442
for (i = BMAX; i; i--)
443
if (c[i])
444
break;
445
g = i; /* maximum code length */
446
if ((unsigned) l > i)
447
l = i;
448
*m = l;
449
450
/* Adjust last length count to fill out codes, if needed */
451
for (y = 1 << j; j < i; j++, y <<= 1)
452
if ((y -= c[j]) < 0)
453
return 2; /* bad input: more codes than bits */
454
if ((y -= c[i]) < 0)
455
return 2;
456
c[i] += y;
457
458
/* Generate starting offsets into the value table for each length */
459
x[1] = j = 0;
460
p = c + 1;
461
xp = x + 2;
462
while (--i)
463
{ /* note that i == g from above */
464
*xp++ = (j += *p++);
465
}
466
467
/* Make a table of values in order of bit lengths */
468
p = b;
469
i = 0;
470
do
471
{
472
if ((j = *p++) != 0)
473
v[x[j]++] = i;
474
}
475
while (++i < n);
476
477
/* Generate the Huffman codes and for each, make the table entries */
478
x[0] = i = 0; /* first Huffman code is zero */
479
p = v; /* grab values in bit order */
480
h = -1; /* no tables yet--level -1 */
481
w = -l; /* bits decoded == (l * h) */
482
u[0] = (struct huft *) NULL; /* just to keep compilers happy */
483
q = (struct huft *) NULL; /* ditto */
484
z = 0; /* ditto */
485
486
/* go through the bit lengths (k already is bits in shortest code) */
487
for (; k <= g; k++)
488
{
489
a = c[k];
490
while (a--)
491
{
492
/* here i is the Huffman code of length k bits for value *p */
493
/* make tables up to required level */
494
while (k > w + l)
495
{
496
h++;
497
w += l; /* previous table always l bits */
498
499
/* compute minimum size table less than or equal to l bits */
500
z = (z = (unsigned) (g - w)) > (unsigned) l ? (unsigned) l : z; /* upper limit on table size */
501
if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
502
{ /* too few codes for k-w bit table */
503
f -= a + 1; /* deduct codes from patterns left */
504
xp = c + k;
505
while (++j < z) /* try smaller tables up to z bits */
506
{
507
if ((f <<= 1) <= *++xp)
508
break; /* enough codes to use up j bits */
509
f -= *xp; /* else deduct codes from patterns */
510
}
511
}
512
z = 1 << j; /* table entries for j-bit table */
513
514
/* allocate and link in new table */
515
q = (struct huft *) grub_malloc ((z + 1) * sizeof (struct huft));
516
if (! q)
517
{
518
if (h)
519
huft_free (u[0]);
520
return 3;
521
}
522
523
*t = q + 1; /* link to list for huft_free() */
524
*(t = &(q->v.t)) = (struct huft *) NULL;
525
u[h] = ++q; /* table starts after link */
526
527
/* connect to last table, if there is one */
528
if (h)
529
{
530
x[h] = i; /* save pattern for backing up */
531
r.b = (uch) l; /* bits to dump before this table */
532
r.e = (uch) (16 + j); /* bits in this table */
533
r.v.t = q; /* pointer to this table */
534
j = i >> (w - l); /* (get around Turbo C bug) */
535
u[h - 1][j] = r; /* connect to last table */
536
}
537
}
538
539
/* set up table entry in r */
540
r.b = (uch) (k - w);
541
if (p >= v + n)
542
r.e = 99; /* out of values--invalid code */
543
else if (*p < s)
544
{
545
r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block code */
546
r.v.n = (ush) (*p); /* simple code is just the value */
547
p++; /* one compiler does not like *p++ */
548
}
549
else
550
{
551
r.e = (uch) e[*p - s]; /* non-simple--look up in lists */
552
r.v.n = d[*p++ - s];
553
}
554
555
/* fill code-like entries with r */
556
f = 1 << (k - w);
557
for (j = i >> w; j < z; j += f)
558
q[j] = r;
559
560
/* backwards increment the k-bit code i */
561
for (j = 1 << (k - 1); i & j; j >>= 1)
562
i ^= j;
563
i ^= j;
564
565
/* backup over finished tables */
566
while ((i & ((1 << w) - 1)) != x[h])
567
{
568
h--; /* don't need to update q */
569
w -= l;
570
}
571
}
572
}
573
574
/* Return true (1) if we were given an incomplete table */
575
return y != 0 && g != 1;
576
}
577
578
579
/* Free the malloc'ed tables built by huft_build(), which makes a linked
580
list of the tables it made, with the links in a dummy first entry of
581
each table. */
582
static int
583
huft_free (struct huft *t)
584
{
585
register struct huft *p, *q;
586
587
588
/* Go through linked list, freeing from the malloced (t[-1]) address. */
589
p = t;
590
while (p != (struct huft *) NULL)
591
{
592
q = (--p)->v.t;
593
grub_free ((char *) p);
594
p = q;
595
}
596
return 0;
597
}
598
599
600
/*
601
* inflate (decompress) the codes in a deflated (compressed) block.
602
* Return an error code or zero if it all goes ok.
603
*/
604
605
static int
606
inflate_codes_in_window (grub_file_t file)
607
{
608
register unsigned e; /* table entry flag/number of extra bits */
609
unsigned n, d; /* length and index for copy */
610
unsigned w; /* current window position */
611
struct huft *t; /* pointer to table entry */
612
unsigned ml, md; /* masks for bl and bd bits */
613
register ulg b; /* bit buffer */
614
register unsigned k; /* number of bits in bit buffer */
615
grub_gzio_t gzio = file->data;
616
617
/* make local copies of globals */
618
d = gzio->inflate_d;
619
n = gzio->inflate_n;
620
b = gzio->bb; /* initialize bit buffer */
621
k = gzio->bk;
622
w = gzio->wp; /* initialize window position */
623
624
/* inflate the coded data */
625
ml = mask_bits[gzio->bl]; /* precompute masks for speed */
626
md = mask_bits[gzio->bd];
627
for (;;) /* do until end of block */
628
{
629
if (! gzio->code_state)
630
{
631
NEEDBITS ((unsigned) gzio->bl);
632
if ((e = (t = gzio->tl + ((unsigned) b & ml))->e) > 16)
633
do
634
{
635
if (e == 99)
636
{
637
grub_error (GRUB_ERR_BAD_GZIP_DATA,
638
"an unused code found");
639
return 1;
640
}
641
DUMPBITS (t->b);
642
e -= 16;
643
NEEDBITS (e);
644
}
645
while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
646
DUMPBITS (t->b);
647
648
if (e == 16) /* then it's a literal */
649
{
650
gzio->slide[w++] = (uch) t->v.n;
651
if (w == WSIZE)
652
break;
653
}
654
else
655
/* it's an EOB or a length */
656
{
657
/* exit if end of block */
658
if (e == 15)
659
{
660
gzio->block_len = 0;
661
break;
662
}
663
664
/* get length of block to copy */
665
NEEDBITS (e);
666
n = t->v.n + ((unsigned) b & mask_bits[e]);
667
DUMPBITS (e);
668
669
/* decode distance of block to copy */
670
NEEDBITS ((unsigned) gzio->bd);
671
if ((e = (t = gzio->td + ((unsigned) b & md))->e) > 16)
672
do
673
{
674
if (e == 99)
675
{
676
grub_error (GRUB_ERR_BAD_GZIP_DATA,
677
"an unused code found");
678
return 1;
679
}
680
DUMPBITS (t->b);
681
e -= 16;
682
NEEDBITS (e);
683
}
684
while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e)
685
> 16);
686
DUMPBITS (t->b);
687
NEEDBITS (e);
688
d = w - t->v.n - ((unsigned) b & mask_bits[e]);
689
DUMPBITS (e);
690
gzio->code_state++;
691
}
692
}
693
694
if (gzio->code_state)
695
{
696
/* do the copy */
697
do
698
{
699
n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n
700
: e);
701
702
if (w - d >= e)
703
{
704
grub_memmove (gzio->slide + w, gzio->slide + d, e);
705
w += e;
706
d += e;
707
}
708
else
709
/* purposefully use the overlap for extra copies here!! */
710
{
711
while (e--)
712
gzio->slide[w++] = gzio->slide[d++];
713
}
714
715
if (w == WSIZE)
716
break;
717
}
718
while (n);
719
720
if (! n)
721
gzio->code_state--;
722
723
/* did we break from the loop too soon? */
724
if (w == WSIZE)
725
break;
726
}
727
}
728
729
/* restore the globals from the locals */
730
gzio->inflate_d = d;
731
gzio->inflate_n = n;
732
gzio->wp = w; /* restore global window pointer */
733
gzio->bb = b; /* restore global bit buffer */
734
gzio->bk = k;
735
736
return ! gzio->block_len;
737
}
738
739
740
/* get header for an inflated type 0 (stored) block. */
741
742
static void
743
init_stored_block (grub_file_t file)
744
{
745
register ulg b; /* bit buffer */
746
register unsigned k; /* number of bits in bit buffer */
747
grub_gzio_t gzio = file->data;
748
749
/* make local copies of globals */
750
b = gzio->bb; /* initialize bit buffer */
751
k = gzio->bk;
752
753
/* go to byte boundary */
754
DUMPBITS (k & 7);
755
756
/* get the length and its complement */
757
NEEDBITS (16);
758
gzio->block_len = ((unsigned) b & 0xffff);
759
DUMPBITS (16);
760
NEEDBITS (16);
761
if (gzio->block_len != (int) ((~b) & 0xffff))
762
grub_error (GRUB_ERR_BAD_GZIP_DATA,
763
"the length of a stored block does not match");
764
DUMPBITS (16);
765
766
/* restore global variables */
767
gzio->bb = b;
768
gzio->bk = k;
769
}
770
771
772
/* get header for an inflated type 1 (fixed Huffman codes) block. We should
773
either replace this with a custom decoder, or at least precompute the
774
Huffman tables. */
775
776
static void
777
init_fixed_block (grub_file_t file)
778
{
779
int i; /* temporary variable */
780
unsigned l[288]; /* length list for huft_build */
781
grub_gzio_t gzio = file->data;
782
783
/* set up literal table */
784
for (i = 0; i < 144; i++)
785
l[i] = 8;
786
for (; i < 256; i++)
787
l[i] = 9;
788
for (; i < 280; i++)
789
l[i] = 7;
790
for (; i < 288; i++) /* make a complete, but wrong code set */
791
l[i] = 8;
792
gzio->bl = 7;
793
if (huft_build (l, 288, 257, cplens, cplext, &gzio->tl, &gzio->bl) != 0)
794
{
795
if (grub_errno == GRUB_ERR_NONE)
796
grub_error (GRUB_ERR_BAD_GZIP_DATA,
797
"failed in building a Huffman code table");
798
return;
799
}
800
801
/* set up distance table */
802
for (i = 0; i < 30; i++) /* make an incomplete code set */
803
l[i] = 5;
804
gzio->bd = 5;
805
if (huft_build (l, 30, 0, cpdist, cpdext, &gzio->td, &gzio->bd) > 1)
806
{
807
if (grub_errno == GRUB_ERR_NONE)
808
grub_error (GRUB_ERR_BAD_GZIP_DATA,
809
"failed in building a Huffman code table");
810
huft_free (gzio->tl);
811
gzio->tl = 0;
812
return;
813
}
814
815
/* indicate we're now working on a block */
816
gzio->code_state = 0;
817
gzio->block_len++;
818
}
819
820
821
/* get header for an inflated type 2 (dynamic Huffman codes) block. */
822
823
static void
824
init_dynamic_block (grub_file_t file)
825
{
826
int i; /* temporary variables */
827
unsigned j;
828
unsigned l; /* last length */
829
unsigned m; /* mask for bit lengths table */
830
unsigned n; /* number of lengths to get */
831
unsigned nb; /* number of bit length codes */
832
unsigned nl; /* number of literal/length codes */
833
unsigned nd; /* number of distance codes */
834
unsigned ll[286 + 30]; /* literal/length and distance code lengths */
835
register ulg b; /* bit buffer */
836
register unsigned k; /* number of bits in bit buffer */
837
grub_gzio_t gzio = file->data;
838
839
/* make local bit buffer */
840
b = gzio->bb;
841
k = gzio->bk;
842
843
/* read in table lengths */
844
NEEDBITS (5);
845
nl = 257 + ((unsigned) b & 0x1f); /* number of literal/length codes */
846
DUMPBITS (5);
847
NEEDBITS (5);
848
nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */
849
DUMPBITS (5);
850
NEEDBITS (4);
851
nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */
852
DUMPBITS (4);
853
if (nl > 286 || nd > 30)
854
{
855
grub_error (GRUB_ERR_BAD_GZIP_DATA, "too much data");
856
return;
857
}
858
859
/* read in bit-length-code lengths */
860
for (j = 0; j < nb; j++)
861
{
862
NEEDBITS (3);
863
ll[bitorder[j]] = (unsigned) b & 7;
864
DUMPBITS (3);
865
}
866
for (; j < 19; j++)
867
ll[bitorder[j]] = 0;
868
869
/* build decoding table for trees--single level, 7 bit lookup */
870
gzio->bl = 7;
871
if (huft_build (ll, 19, 19, NULL, NULL, &gzio->tl, &gzio->bl) != 0)
872
{
873
grub_error (GRUB_ERR_BAD_GZIP_DATA,
874
"failed in building a Huffman code table");
875
return;
876
}
877
878
/* read in literal and distance code lengths */
879
n = nl + nd;
880
m = mask_bits[gzio->bl];
881
i = l = 0;
882
while ((unsigned) i < n)
883
{
884
NEEDBITS ((unsigned) gzio->bl);
885
j = (gzio->td = gzio->tl + ((unsigned) b & m))->b;
886
DUMPBITS (j);
887
j = gzio->td->v.n;
888
if (j < 16) /* length of code in bits (0..15) */
889
ll[i++] = l = j; /* save last length in l */
890
else if (j == 16) /* repeat last length 3 to 6 times */
891
{
892
NEEDBITS (2);
893
j = 3 + ((unsigned) b & 3);
894
DUMPBITS (2);
895
if ((unsigned) i + j > n)
896
{
897
grub_error (GRUB_ERR_BAD_GZIP_DATA, "too many codes found");
898
return;
899
}
900
while (j--)
901
ll[i++] = l;
902
}
903
else if (j == 17) /* 3 to 10 zero length codes */
904
{
905
NEEDBITS (3);
906
j = 3 + ((unsigned) b & 7);
907
DUMPBITS (3);
908
if ((unsigned) i + j > n)
909
{
910
grub_error (GRUB_ERR_BAD_GZIP_DATA, "too many codes found");
911
return;
912
}
913
while (j--)
914
ll[i++] = 0;
915
l = 0;
916
}
917
else
918
/* j == 18: 11 to 138 zero length codes */
919
{
920
NEEDBITS (7);
921
j = 11 + ((unsigned) b & 0x7f);
922
DUMPBITS (7);
923
if ((unsigned) i + j > n)
924
{
925
grub_error (GRUB_ERR_BAD_GZIP_DATA, "too many codes found");
926
return;
927
}
928
while (j--)
929
ll[i++] = 0;
930
l = 0;
931
}
932
}
933
934
/* free decoding table for trees */
935
huft_free (gzio->tl);
936
gzio->td = 0;
937
gzio->tl = 0;
938
939
/* restore the global bit buffer */
940
gzio->bb = b;
941
gzio->bk = k;
942
943
/* build the decoding tables for literal/length and distance codes */
944
gzio->bl = lbits;
945
if (huft_build (ll, nl, 257, cplens, cplext, &gzio->tl, &gzio->bl) != 0)
946
{
947
grub_error (GRUB_ERR_BAD_GZIP_DATA,
948
"failed in building a Huffman code table");
949
return;
950
}
951
gzio->bd = dbits;
952
if (huft_build (ll + nl, nd, 0, cpdist, cpdext, &gzio->td, &gzio->bd) != 0)
953
{
954
huft_free (gzio->tl);
955
gzio->tl = 0;
956
grub_error (GRUB_ERR_BAD_GZIP_DATA,
957
"failed in building a Huffman code table");
958
return;
959
}
960
961
/* indicate we're now working on a block */
962
gzio->code_state = 0;
963
gzio->block_len++;
964
}
965
966
967
static void
968
get_new_block (grub_file_t file)
969
{
970
register ulg b; /* bit buffer */
971
register unsigned k; /* number of bits in bit buffer */
972
grub_gzio_t gzio = file->data;
973
974
/* make local bit buffer */
975
b = gzio->bb;
976
k = gzio->bk;
977
978
/* read in last block bit */
979
NEEDBITS (1);
980
gzio->last_block = (int) b & 1;
981
DUMPBITS (1);
982
983
/* read in block type */
984
NEEDBITS (2);
985
gzio->block_type = (unsigned) b & 3;
986
DUMPBITS (2);
987
988
/* restore the global bit buffer */
989
gzio->bb = b;
990
gzio->bk = k;
991
992
switch (gzio->block_type)
993
{
994
case INFLATE_STORED:
995
init_stored_block (file);
996
break;
997
case INFLATE_FIXED:
998
init_fixed_block (file);
999
break;
1000
case INFLATE_DYNAMIC:
1001
init_dynamic_block (file);
1002
break;
1003
default:
1004
break;
1005
}
1006
}
1007
1008
1009
static void
1010
inflate_window (grub_file_t file)
1011
{
1012
grub_gzio_t gzio = file->data;
1013
1014
/* initialize window */
1015
gzio->wp = 0;
1016
1017
/*
1018
* Main decompression loop.
1019
*/
1020
1021
while (gzio->wp < WSIZE && grub_errno == GRUB_ERR_NONE)
1022
{
1023
if (! gzio->block_len)
1024
{
1025
if (gzio->last_block)
1026
break;
1027
1028
get_new_block (file);
1029
}
1030
1031
if (gzio->block_type > INFLATE_DYNAMIC)
1032
grub_error (GRUB_ERR_BAD_GZIP_DATA,
1033
"unknown block type %d", gzio->block_type);
1034
1035
if (grub_errno != GRUB_ERR_NONE)
1036
return;
1037
1038
/*
1039
* Expand stored block here.
1040
*/
1041
if (gzio->block_type == INFLATE_STORED)
1042
{
1043
int w = gzio->wp;
1044
1045
/*
1046
* This is basically a glorified pass-through
1047
*/
1048
1049
while (gzio->block_len && w < WSIZE && grub_errno == GRUB_ERR_NONE)
1050
{
1051
gzio->slide[w++] = get_byte (file);
1052
gzio->block_len--;
1053
}
1054
1055
gzio->wp = w;
1056
1057
continue;
1058
}
1059
1060
/*
1061
* Expand other kind of block.
1062
*/
1063
1064
if (inflate_codes_in_window (file))
1065
{
1066
huft_free (gzio->tl);
1067
huft_free (gzio->td);
1068
gzio->tl = 0;
1069
gzio->td = 0;
1070
}
1071
}
1072
1073
gzio->saved_offset += WSIZE;
1074
1075
/* XXX do CRC calculation here! */
1076
}
1077
1078
1079
static void
1080
initialize_tables (grub_file_t file)
1081
{
1082
grub_gzio_t gzio = file->data;
1083
1084
gzio->saved_offset = 0;
1085
grub_file_seek (gzio->file, gzio->data_offset);
1086
1087
/* Initialize the bit buffer. */
1088
gzio->bk = 0;
1089
gzio->bb = 0;
1090
1091
/* Reset partial decompression code. */
1092
gzio->last_block = 0;
1093
gzio->block_len = 0;
1094
1095
/* Reset memory allocation stuff. */
1096
huft_free (gzio->tl);
1097
huft_free (gzio->td);
1098
}
1099
1100
1101
/* Open a new decompressing object on the top of IO. If TRANSPARENT is true,
1102
even if IO does not contain data compressed by gzip, return a valid file
1103
object. Note that this function won't close IO, even if an error occurs. */
1104
grub_file_t
1105
grub_gzio_open (grub_file_t io, int transparent)
1106
{
1107
grub_file_t file;
1108
grub_gzio_t gzio = 0;
1109
1110
file = (grub_file_t) grub_malloc (sizeof (*file));
1111
if (! file)
1112
return 0;
1113
1114
gzio = grub_malloc (sizeof (*gzio));
1115
if (! gzio)
1116
{
1117
grub_free (file);
1118
return 0;
1119
}
1120
1121
grub_memset (gzio, 0, sizeof (*gzio));
1122
gzio->file = io;
1123
1124
file->device = io->device;
1125
file->offset = 0;
1126
file->data = gzio;
1127
file->read_hook = 0;
1128
file->fs = &grub_gzio_fs;
1129
1130
if (! test_header (file))
1131
{
1132
grub_free (gzio);
1133
grub_free (file);
1134
grub_file_seek (io, 0);
1135
1136
if (grub_errno == GRUB_ERR_BAD_FILE_TYPE && transparent)
1137
{
1138
grub_errno = GRUB_ERR_NONE;
1139
return io;
1140
}
1141
else
1142
return 0;
1143
}
1144
1145
return file;
1146
}
1147
1148
/* This is similar to grub_gzio_open, but takes a file name as an argument. */
1149
grub_file_t
1150
grub_gzfile_open (const char *name, int transparent)
1151
{
1152
grub_file_t io, file;
1153
1154
io = grub_file_open (name);
1155
if (! io)
1156
return 0;
1157
1158
file = grub_gzio_open (io, transparent);
1159
if (! file)
1160
{
1161
grub_file_close (io);
1162
return 0;
1163
}
1164
1165
return file;
1166
}
1167
1168
static grub_ssize_t
1169
grub_gzio_read (grub_file_t file, char *buf, grub_ssize_t len)
1170
{
1171
grub_ssize_t ret = 0;
1172
grub_gzio_t gzio = file->data;
1173
grub_ssize_t offset;
1174
1175
/* Do we reset decompression to the beginning of the file? */
1176
if (gzio->saved_offset > file->offset + WSIZE)
1177
initialize_tables (file);
1178
1179
/*
1180
* This loop operates upon uncompressed data only. The only
1181
* special thing it does is to make sure the decompression
1182
* window is within the range of data it needs.
1183
*/
1184
1185
offset = file->offset;
1186
1187
while (len > 0 && grub_errno == GRUB_ERR_NONE)
1188
{
1189
register grub_ssize_t size;
1190
register char *srcaddr;
1191
1192
while (offset >= gzio->saved_offset)
1193
inflate_window (file);
1194
1195
srcaddr = (char *) ((offset & (WSIZE - 1)) + gzio->slide);
1196
size = gzio->saved_offset - offset;
1197
if (size > len)
1198
size = len;
1199
1200
grub_memmove (buf, srcaddr, size);
1201
1202
buf += size;
1203
len -= size;
1204
ret += size;
1205
offset += size;
1206
}
1207
1208
if (grub_errno != GRUB_ERR_NONE)
1209
ret = -1;
1210
1211
return ret;
1212
}
1213
1214
/* Release everything, including the underlying file object. */
1215
static grub_err_t
1216
grub_gzio_close (grub_file_t file)
1217
{
1218
grub_gzio_t gzio = file->data;
1219
1220
grub_file_close (gzio->file);
1221
huft_free (gzio->tl);
1222
huft_free (gzio->td);
1223
grub_free (gzio);
1224
1225
/* No need to close the same device twice. */
1226
file->device = 0;
1227
1228
return grub_errno;
1229
}
1230
1231
1232
1233
static struct grub_fs grub_gzio_fs =
1234
{
1235
.name = "gzio",
1236
.dir = 0,
1237
.open = 0,
1238
.read = grub_gzio_read,
1239
.close = grub_gzio_close,
1240
.label = 0,
1241
.next = 0
1242
};
Loggerhead is a web-based interface for Breezy
Version: 2.0.1