OSCL-LXR |
|
|
|
|||
0001 // SPDX-License-Identifier: GPL-2.0 0002 #define DEBG(x) 0003 #define DEBG1(x) 0004 /* inflate.c -- Not copyrighted 1992 by Mark Adler 0005 version c10p1, 10 January 1993 */ 0006 0007 /* 0008 * Adapted for booting Linux by Hannu Savolainen 1993 0009 * based on gzip-1.0.3 0010 * 0011 * Nicolas Pitre <nico@fluxnic.net>, 1999/04/14 : 0012 * Little mods for all variable to reside either into rodata or bss segments 0013 * by marking constant variables with 'const' and initializing all the others 0014 * at run-time only. This allows for the kernel uncompressor to run 0015 * directly from Flash or ROM memory on embedded systems. 0016 */ 0017 0018 /* 0019 Inflate deflated (PKZIP's method 8 compressed) data. The compression 0020 method searches for as much of the current string of bytes (up to a 0021 length of 258) in the previous 32 K bytes. If it doesn't find any 0022 matches (of at least length 3), it codes the next byte. Otherwise, it 0023 codes the length of the matched string and its distance backwards from 0024 the current position. There is a single Huffman code that codes both 0025 single bytes (called "literals") and match lengths. A second Huffman 0026 code codes the distance information, which follows a length code. Each 0027 length or distance code actually represents a base value and a number 0028 of "extra" (sometimes zero) bits to get to add to the base value. At 0029 the end of each deflated block is a special end-of-block (EOB) literal/ 0030 length code. The decoding process is basically: get a literal/length 0031 code; if EOB then done; if a literal, emit the decoded byte; if a 0032 length then get the distance and emit the referred-to bytes from the 0033 sliding window of previously emitted data. 0034 0035 There are (currently) three kinds of inflate blocks: stored, fixed, and 0036 dynamic. The compressor deals with some chunk of data at a time, and 0037 decides which method to use on a chunk-by-chunk basis. A chunk might 0038 typically be 32 K or 64 K. If the chunk is incompressible, then the 0039 "stored" method is used. In this case, the bytes are simply stored as 0040 is, eight bits per byte, with none of the above coding. The bytes are 0041 preceded by a count, since there is no longer an EOB code. 0042 0043 If the data is compressible, then either the fixed or dynamic methods 0044 are used. In the dynamic method, the compressed data is preceded by 0045 an encoding of the literal/length and distance Huffman codes that are 0046 to be used to decode this block. The representation is itself Huffman 0047 coded, and so is preceded by a description of that code. These code 0048 descriptions take up a little space, and so for small blocks, there is 0049 a predefined set of codes, called the fixed codes. The fixed method is 0050 used if the block codes up smaller that way (usually for quite small 0051 chunks), otherwise the dynamic method is used. In the latter case, the 0052 codes are customized to the probabilities in the current block, and so 0053 can code it much better than the pre-determined fixed codes. 0054 0055 The Huffman codes themselves are decoded using a multi-level table 0056 lookup, in order to maximize the speed of decoding plus the speed of 0057 building the decoding tables. See the comments below that precede the 0058 lbits and dbits tuning parameters. 0059 */ 0060 0061 0062 /* 0063 Notes beyond the 1.93a appnote.txt: 0064 0065 1. Distance pointers never point before the beginning of the output 0066 stream. 0067 2. Distance pointers can point back across blocks, up to 32k away. 0068 3. There is an implied maximum of 7 bits for the bit length table and 0069 15 bits for the actual data. 0070 4. If only one code exists, then it is encoded using one bit. (Zero 0071 would be more efficient, but perhaps a little confusing.) If two 0072 codes exist, they are coded using one bit each (0 and 1). 0073 5. There is no way of sending zero distance codes--a dummy must be 0074 sent if there are none. (History: a pre 2.0 version of PKZIP would 0075 store blocks with no distance codes, but this was discovered to be 0076 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 0077 zero distance codes, which is sent as one code of zero bits in 0078 length. 0079 6. There are up to 286 literal/length codes. Code 256 represents the 0080 end-of-block. Note however that the static length tree defines 0081 288 codes just to fill out the Huffman codes. Codes 286 and 287 0082 cannot be used though, since there is no length base or extra bits 0083 defined for them. Similarly, there are up to 30 distance codes. 0084 However, static trees define 32 codes (all 5 bits) to fill out the 0085 Huffman codes, but the last two had better not show up in the data. 0086 7. Unzip can check dynamic Huffman blocks for complete code sets. 0087 The exception is that a single code would not be complete (see #4). 0088 8. The five bits following the block type is really the number of 0089 literal codes sent minus 257. 0090 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 0091 (1+6+6). Therefore, to output three times the length, you output 0092 three codes (1+1+1), whereas to output four times the same length, 0093 you only need two codes (1+3). Hmm. 0094 10. In the tree reconstruction algorithm, Code = Code + Increment 0095 only if BitLength(i) is not zero. (Pretty obvious.) 0096 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 0097 12. Note: length code 284 can represent 227-258, but length code 285 0098 really is 258. The last length deserves its own, short code 0099 since it gets used a lot in very redundant files. The length 0100 258 is special since 258 - 3 (the min match length) is 255. 0101 13. The literal/length and distance code bit lengths are read as a 0102 single stream of lengths. It is possible (and advantageous) for 0103 a repeat code (16, 17, or 18) to go across the boundary between 0104 the two sets of lengths. 0105 */ 0106 #include <linux/compiler.h> 0107 #ifdef NO_INFLATE_MALLOC 0108 #include <linux/slab.h> 0109 #endif 0110 0111 #ifdef RCSID 0112 static char rcsid[] = "#Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp #"; 0113 #endif 0114 0115 #ifndef STATIC 0116 0117 #if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H) 0118 # include <sys/types.h> 0119 # include <stdlib.h> 0120 #endif 0121 0122 #include "gzip.h" 0123 #define STATIC 0124 #endif /* !STATIC */ 0125 0126 #ifndef INIT 0127 #define INIT 0128 #endif 0129 0130 #define slide window 0131 0132 /* Huffman code lookup table entry--this entry is four bytes for machines 0133 that have 16-bit pointers (e.g. PC's in the small or medium model). 0134 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 0135 means that v is a literal, 16 < e < 32 means that v is a pointer to 0136 the next table, which codes e - 16 bits, and lastly e == 99 indicates 0137 an unused code. If a code with e == 99 is looked up, this implies an 0138 error in the data. */ 0139 struct huft { 0140 uch e; /* number of extra bits or operation */ 0141 uch b; /* number of bits in this code or subcode */ 0142 union { 0143 ush n; /* literal, length base, or distance base */ 0144 struct huft *t; /* pointer to next level of table */ 0145 } v; 0146 }; 0147 0148 0149 /* Function prototypes */ 0150 STATIC int INIT huft_build OF((unsigned *, unsigned, unsigned, 0151 const ush *, const ush *, struct huft **, int *)); 0152 STATIC int INIT huft_free OF((struct huft *)); 0153 STATIC int INIT inflate_codes OF((struct huft *, struct huft *, int, int)); 0154 STATIC int INIT inflate_stored OF((void)); 0155 STATIC int INIT inflate_fixed OF((void)); 0156 STATIC int INIT inflate_dynamic OF((void)); 0157 STATIC int INIT inflate_block OF((int *)); 0158 STATIC int INIT inflate OF((void)); 0159 0160 0161 /* The inflate algorithm uses a sliding 32 K byte window on the uncompressed 0162 stream to find repeated byte strings. This is implemented here as a 0163 circular buffer. The index is updated simply by incrementing and then 0164 ANDing with 0x7fff (32K-1). */ 0165 /* It is left to other modules to supply the 32 K area. It is assumed 0166 to be usable as if it were declared "uch slide[32768];" or as just 0167 "uch *slide;" and then malloc'ed in the latter case. The definition 0168 must be in unzip.h, included above. */ 0169 /* unsigned wp; current position in slide */ 0170 #define wp outcnt 0171 #define flush_output(w) (wp=(w),flush_window()) 0172 0173 /* Tables for deflate from PKZIP's appnote.txt. */ 0174 static const unsigned border[] = { /* Order of the bit length code lengths */ 0175 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 0176 static const ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 0177 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 0178 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 0179 /* note: see note #13 above about the 258 in this list. */ 0180 static const ush cplext[] = { /* Extra bits for literal codes 257..285 */ 0181 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 0182 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 0183 static const ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 0184 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 0185 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 0186 8193, 12289, 16385, 24577}; 0187 static const ush cpdext[] = { /* Extra bits for distance codes */ 0188 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 0189 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 0190 12, 12, 13, 13}; 0191 0192 0193 0194 /* Macros for inflate() bit peeking and grabbing. 0195 The usage is: 0196 0197 NEEDBITS(j) 0198 x = b & mask_bits[j]; 0199 DUMPBITS(j) 0200 0201 where NEEDBITS makes sure that b has at least j bits in it, and 0202 DUMPBITS removes the bits from b. The macros use the variable k 0203 for the number of bits in b. Normally, b and k are register 0204 variables for speed, and are initialized at the beginning of a 0205 routine that uses these macros from a global bit buffer and count. 0206 0207 If we assume that EOB will be the longest code, then we will never 0208 ask for bits with NEEDBITS that are beyond the end of the stream. 0209 So, NEEDBITS should not read any more bytes than are needed to 0210 meet the request. Then no bytes need to be "returned" to the buffer 0211 at the end of the last block. 0212 0213 However, this assumption is not true for fixed blocks--the EOB code 0214 is 7 bits, but the other literal/length codes can be 8 or 9 bits. 0215 (The EOB code is shorter than other codes because fixed blocks are 0216 generally short. So, while a block always has an EOB, many other 0217 literal/length codes have a significantly lower probability of 0218 showing up at all.) However, by making the first table have a 0219 lookup of seven bits, the EOB code will be found in that first 0220 lookup, and so will not require that too many bits be pulled from 0221 the stream. 0222 */ 0223 0224 STATIC ulg bb; /* bit buffer */ 0225 STATIC unsigned bk; /* bits in bit buffer */ 0226 0227 STATIC const ush mask_bits[] = { 0228 0x0000, 0229 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 0230 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 0231 }; 0232 0233 #define NEXTBYTE() ({ int v = get_byte(); if (v < 0) goto underrun; (uch)v; }) 0234 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}} 0235 #define DUMPBITS(n) {b>>=(n);k-=(n);} 0236 0237 #ifndef NO_INFLATE_MALLOC 0238 /* A trivial malloc implementation, adapted from 0239 * malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994 0240 */ 0241 0242 static unsigned long malloc_ptr; 0243 static int malloc_count; 0244 0245 static void *malloc(int size) 0246 { 0247 void *p; 0248 0249 if (size < 0) 0250 error("Malloc error"); 0251 if (!malloc_ptr) 0252 malloc_ptr = free_mem_ptr; 0253 0254 malloc_ptr = (malloc_ptr + 3) & ~3; /* Align */ 0255 0256 p = (void *)malloc_ptr; 0257 malloc_ptr += size; 0258 0259 if (free_mem_end_ptr && malloc_ptr >= free_mem_end_ptr) 0260 error("Out of memory"); 0261 0262 malloc_count++; 0263 return p; 0264 } 0265 0266 static void free(void *where) 0267 { 0268 malloc_count--; 0269 if (!malloc_count) 0270 malloc_ptr = free_mem_ptr; 0271 } 0272 #else 0273 #define malloc(a) kmalloc(a, GFP_KERNEL) 0274 #define free(a) kfree(a) 0275 #endif 0276 0277 /* 0278 Huffman code decoding is performed using a multi-level table lookup. 0279 The fastest way to decode is to simply build a lookup table whose 0280 size is determined by the longest code. However, the time it takes 0281 to build this table can also be a factor if the data being decoded 0282 is not very long. The most common codes are necessarily the 0283 shortest codes, so those codes dominate the decoding time, and hence 0284 the speed. The idea is you can have a shorter table that decodes the 0285 shorter, more probable codes, and then point to subsidiary tables for 0286 the longer codes. The time it costs to decode the longer codes is 0287 then traded against the time it takes to make longer tables. 0288 0289 This results of this trade are in the variables lbits and dbits 0290 below. lbits is the number of bits the first level table for literal/ 0291 length codes can decode in one step, and dbits is the same thing for 0292 the distance codes. Subsequent tables are also less than or equal to 0293 those sizes. These values may be adjusted either when all of the 0294 codes are shorter than that, in which case the longest code length in 0295 bits is used, or when the shortest code is *longer* than the requested 0296 table size, in which case the length of the shortest code in bits is 0297 used. 0298 0299 There are two different values for the two tables, since they code a 0300 different number of possibilities each. The literal/length table 0301 codes 286 possible values, or in a flat code, a little over eight 0302 bits. The distance table codes 30 possible values, or a little less 0303 than five bits, flat. The optimum values for speed end up being 0304 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 0305 The optimum values may differ though from machine to machine, and 0306 possibly even between compilers. Your mileage may vary. 0307 */ 0308 0309 0310 STATIC const int lbits = 9; /* bits in base literal/length lookup table */ 0311 STATIC const int dbits = 6; /* bits in base distance lookup table */ 0312 0313 0314 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 0315 #define BMAX 16 /* maximum bit length of any code (16 for explode) */ 0316 #define N_MAX 288 /* maximum number of codes in any set */ 0317 0318 0319 STATIC unsigned hufts; /* track memory usage */ 0320 0321 0322 STATIC int INIT huft_build( 0323 unsigned *b, /* code lengths in bits (all assumed <= BMAX) */ 0324 unsigned n, /* number of codes (assumed <= N_MAX) */ 0325 unsigned s, /* number of simple-valued codes (0..s-1) */ 0326 const ush *d, /* list of base values for non-simple codes */ 0327 const ush *e, /* list of extra bits for non-simple codes */ 0328 struct huft **t, /* result: starting table */ 0329 int *m /* maximum lookup bits, returns actual */ 0330 ) 0331 /* Given a list of code lengths and a maximum table size, make a set of 0332 tables to decode that set of codes. Return zero on success, one if 0333 the given code set is incomplete (the tables are still built in this 0334 case), two if the input is invalid (all zero length codes or an 0335 oversubscribed set of lengths), and three if not enough memory. */ 0336 { 0337 unsigned a; /* counter for codes of length k */ 0338 unsigned f; /* i repeats in table every f entries */ 0339 int g; /* maximum code length */ 0340 int h; /* table level */ 0341 register unsigned i; /* counter, current code */ 0342 register unsigned j; /* counter */ 0343 register int k; /* number of bits in current code */ 0344 int l; /* bits per table (returned in m) */ 0345 register unsigned *p; /* pointer into c[], b[], or v[] */ 0346 register struct huft *q; /* points to current table */ 0347 struct huft r; /* table entry for structure assignment */ 0348 register int w; /* bits before this table == (l * h) */ 0349 unsigned *xp; /* pointer into x */ 0350 int y; /* number of dummy codes added */ 0351 unsigned z; /* number of entries in current table */ 0352 struct { 0353 unsigned c[BMAX+1]; /* bit length count table */ 0354 struct huft *u[BMAX]; /* table stack */ 0355 unsigned v[N_MAX]; /* values in order of bit length */ 0356 unsigned x[BMAX+1]; /* bit offsets, then code stack */ 0357 } *stk; 0358 unsigned *c, *v, *x; 0359 struct huft **u; 0360 int ret; 0361 0362 DEBG("huft1 "); 0363 0364 stk = malloc(sizeof(*stk)); 0365 if (stk == NULL) 0366 return 3; /* out of memory */ 0367 0368 c = stk->c; 0369 v = stk->v; 0370 x = stk->x; 0371 u = stk->u; 0372 0373 /* Generate counts for each bit length */ 0374 memzero(stk->c, sizeof(stk->c)); 0375 p = b; i = n; 0376 do { 0377 Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), 0378 n-i, *p)); 0379 c[*p]++; /* assume all entries <= BMAX */ 0380 p++; /* Can't combine with above line (Solaris bug) */ 0381 } while (--i); 0382 if (c[0] == n) /* null input--all zero length codes */ 0383 { 0384 *t = (struct huft *)NULL; 0385 *m = 0; 0386 ret = 2; 0387 goto out; 0388 } 0389 0390 DEBG("huft2 "); 0391 0392 /* Find minimum and maximum length, bound *m by those */ 0393 l = *m; 0394 for (j = 1; j <= BMAX; j++) 0395 if (c[j]) 0396 break; 0397 k = j; /* minimum code length */ 0398 if ((unsigned)l < j) 0399 l = j; 0400 for (i = BMAX; i; i--) 0401 if (c[i]) 0402 break; 0403 g = i; /* maximum code length */ 0404 if ((unsigned)l > i) 0405 l = i; 0406 *m = l; 0407 0408 DEBG("huft3 "); 0409 0410 /* Adjust last length count to fill out codes, if needed */ 0411 for (y = 1 << j; j < i; j++, y <<= 1) 0412 if ((y -= c[j]) < 0) { 0413 ret = 2; /* bad input: more codes than bits */ 0414 goto out; 0415 } 0416 if ((y -= c[i]) < 0) { 0417 ret = 2; 0418 goto out; 0419 } 0420 c[i] += y; 0421 0422 DEBG("huft4 "); 0423 0424 /* Generate starting offsets into the value table for each length */ 0425 x[1] = j = 0; 0426 p = c + 1; xp = x + 2; 0427 while (--i) { /* note that i == g from above */ 0428 *xp++ = (j += *p++); 0429 } 0430 0431 DEBG("huft5 "); 0432 0433 /* Make a table of values in order of bit lengths */ 0434 p = b; i = 0; 0435 do { 0436 if ((j = *p++) != 0) 0437 v[x[j]++] = i; 0438 } while (++i < n); 0439 n = x[g]; /* set n to length of v */ 0440 0441 DEBG("h6 "); 0442 0443 /* Generate the Huffman codes and for each, make the table entries */ 0444 x[0] = i = 0; /* first Huffman code is zero */ 0445 p = v; /* grab values in bit order */ 0446 h = -1; /* no tables yet--level -1 */ 0447 w = -l; /* bits decoded == (l * h) */ 0448 u[0] = (struct huft *)NULL; /* just to keep compilers happy */ 0449 q = (struct huft *)NULL; /* ditto */ 0450 z = 0; /* ditto */ 0451 DEBG("h6a "); 0452 0453 /* go through the bit lengths (k already is bits in shortest code) */ 0454 for (; k <= g; k++) 0455 { 0456 DEBG("h6b "); 0457 a = c[k]; 0458 while (a--) 0459 { 0460 DEBG("h6b1 "); 0461 /* here i is the Huffman code of length k bits for value *p */ 0462 /* make tables up to required level */ 0463 while (k > w + l) 0464 { 0465 DEBG1("1 "); 0466 h++; 0467 w += l; /* previous table always l bits */ 0468 0469 /* compute minimum size table less than or equal to l bits */ 0470 z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */ 0471 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 0472 { /* too few codes for k-w bit table */ 0473 DEBG1("2 "); 0474 f -= a + 1; /* deduct codes from patterns left */ 0475 xp = c + k; 0476 if (j < z) 0477 while (++j < z) /* try smaller tables up to z bits */ 0478 { 0479 if ((f <<= 1) <= *++xp) 0480 break; /* enough codes to use up j bits */ 0481 f -= *xp; /* else deduct codes from patterns */ 0482 } 0483 } 0484 DEBG1("3 "); 0485 z = 1 << j; /* table entries for j-bit table */ 0486 0487 /* allocate and link in new table */ 0488 if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == 0489 (struct huft *)NULL) 0490 { 0491 if (h) 0492 huft_free(u[0]); 0493 ret = 3; /* not enough memory */ 0494 goto out; 0495 } 0496 DEBG1("4 "); 0497 hufts += z + 1; /* track memory usage */ 0498 *t = q + 1; /* link to list for huft_free() */ 0499 *(t = &(q->v.t)) = (struct huft *)NULL; 0500 u[h] = ++q; /* table starts after link */ 0501 0502 DEBG1("5 "); 0503 /* connect to last table, if there is one */ 0504 if (h) 0505 { 0506 x[h] = i; /* save pattern for backing up */ 0507 r.b = (uch)l; /* bits to dump before this table */ 0508 r.e = (uch)(16 + j); /* bits in this table */ 0509 r.v.t = q; /* pointer to this table */ 0510 j = i >> (w - l); /* (get around Turbo C bug) */ 0511 u[h-1][j] = r; /* connect to last table */ 0512 } 0513 DEBG1("6 "); 0514 } 0515 DEBG("h6c "); 0516 0517 /* set up table entry in r */ 0518 r.b = (uch)(k - w); 0519 if (p >= v + n) 0520 r.e = 99; /* out of values--invalid code */ 0521 else if (*p < s) 0522 { 0523 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ 0524 r.v.n = (ush)(*p); /* simple code is just the value */ 0525 p++; /* one compiler does not like *p++ */ 0526 } 0527 else 0528 { 0529 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ 0530 r.v.n = d[*p++ - s]; 0531 } 0532 DEBG("h6d "); 0533 0534 /* fill code-like entries with r */ 0535 f = 1 << (k - w); 0536 for (j = i >> w; j < z; j += f) 0537 q[j] = r; 0538 0539 /* backwards increment the k-bit code i */ 0540 for (j = 1 << (k - 1); i & j; j >>= 1) 0541 i ^= j; 0542 i ^= j; 0543 0544 /* backup over finished tables */ 0545 while ((i & ((1 << w) - 1)) != x[h]) 0546 { 0547 h--; /* don't need to update q */ 0548 w -= l; 0549 } 0550 DEBG("h6e "); 0551 } 0552 DEBG("h6f "); 0553 } 0554 0555 DEBG("huft7 "); 0556 0557 /* Return true (1) if we were given an incomplete table */ 0558 ret = y != 0 && g != 1; 0559 0560 out: 0561 free(stk); 0562 return ret; 0563 } 0564 0565 0566 0567 STATIC int INIT huft_free( 0568 struct huft *t /* table to free */ 0569 ) 0570 /* Free the malloc'ed tables built by huft_build(), which makes a linked 0571 list of the tables it made, with the links in a dummy first entry of 0572 each table. */ 0573 { 0574 register struct huft *p, *q; 0575 0576 0577 /* Go through linked list, freeing from the malloced (t[-1]) address. */ 0578 p = t; 0579 while (p != (struct huft *)NULL) 0580 { 0581 q = (--p)->v.t; 0582 free((char*)p); 0583 p = q; 0584 } 0585 return 0; 0586 } 0587 0588 0589 STATIC int INIT inflate_codes( 0590 struct huft *tl, /* literal/length decoder tables */ 0591 struct huft *td, /* distance decoder tables */ 0592 int bl, /* number of bits decoded by tl[] */ 0593 int bd /* number of bits decoded by td[] */ 0594 ) 0595 /* inflate (decompress) the codes in a deflated (compressed) block. 0596 Return an error code or zero if it all goes ok. */ 0597 { 0598 register unsigned e; /* table entry flag/number of extra bits */ 0599 unsigned n, d; /* length and index for copy */ 0600 unsigned w; /* current window position */ 0601 struct huft *t; /* pointer to table entry */ 0602 unsigned ml, md; /* masks for bl and bd bits */ 0603 register ulg b; /* bit buffer */ 0604 register unsigned k; /* number of bits in bit buffer */ 0605 0606 0607 /* make local copies of globals */ 0608 b = bb; /* initialize bit buffer */ 0609 k = bk; 0610 w = wp; /* initialize window position */ 0611 0612 /* inflate the coded data */ 0613 ml = mask_bits[bl]; /* precompute masks for speed */ 0614 md = mask_bits[bd]; 0615 for (;;) /* do until end of block */ 0616 { 0617 NEEDBITS((unsigned)bl) 0618 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) 0619 do { 0620 if (e == 99) 0621 return 1; 0622 DUMPBITS(t->b) 0623 e -= 16; 0624 NEEDBITS(e) 0625 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); 0626 DUMPBITS(t->b) 0627 if (e == 16) /* then it's a literal */ 0628 { 0629 slide[w++] = (uch)t->v.n; 0630 Tracevv((stderr, "%c", slide[w-1])); 0631 if (w == WSIZE) 0632 { 0633 flush_output(w); 0634 w = 0; 0635 } 0636 } 0637 else /* it's an EOB or a length */ 0638 { 0639 /* exit if end of block */ 0640 if (e == 15) 0641 break; 0642 0643 /* get length of block to copy */ 0644 NEEDBITS(e) 0645 n = t->v.n + ((unsigned)b & mask_bits[e]); 0646 DUMPBITS(e); 0647 0648 /* decode distance of block to copy */ 0649 NEEDBITS((unsigned)bd) 0650 if ((e = (t = td + ((unsigned)b & md))->e) > 16) 0651 do { 0652 if (e == 99) 0653 return 1; 0654 DUMPBITS(t->b) 0655 e -= 16; 0656 NEEDBITS(e) 0657 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); 0658 DUMPBITS(t->b) 0659 NEEDBITS(e) 0660 d = w - t->v.n - ((unsigned)b & mask_bits[e]); 0661 DUMPBITS(e) 0662 Tracevv((stderr,"\\[%d,%d]", w-d, n)); 0663 0664 /* do the copy */ 0665 do { 0666 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); 0667 #if !defined(NOMEMCPY) && !defined(DEBUG) 0668 if (w - d >= e) /* (this test assumes unsigned comparison) */ 0669 { 0670 memcpy(slide + w, slide + d, e); 0671 w += e; 0672 d += e; 0673 } 0674 else /* do it slow to avoid memcpy() overlap */ 0675 #endif /* !NOMEMCPY */ 0676 do { 0677 slide[w++] = slide[d++]; 0678 Tracevv((stderr, "%c", slide[w-1])); 0679 } while (--e); 0680 if (w == WSIZE) 0681 { 0682 flush_output(w); 0683 w = 0; 0684 } 0685 } while (n); 0686 } 0687 } 0688 0689 0690 /* restore the globals from the locals */ 0691 wp = w; /* restore global window pointer */ 0692 bb = b; /* restore global bit buffer */ 0693 bk = k; 0694 0695 /* done */ 0696 return 0; 0697 0698 underrun: 0699 return 4; /* Input underrun */ 0700 } 0701 0702 0703 0704 STATIC int INIT inflate_stored(void) 0705 /* "decompress" an inflated type 0 (stored) block. */ 0706 { 0707 unsigned n; /* number of bytes in block */ 0708 unsigned w; /* current window position */ 0709 register ulg b; /* bit buffer */ 0710 register unsigned k; /* number of bits in bit buffer */ 0711 0712 DEBG("<stor"); 0713 0714 /* make local copies of globals */ 0715 b = bb; /* initialize bit buffer */ 0716 k = bk; 0717 w = wp; /* initialize window position */ 0718 0719 0720 /* go to byte boundary */ 0721 n = k & 7; 0722 DUMPBITS(n); 0723 0724 0725 /* get the length and its complement */ 0726 NEEDBITS(16) 0727 n = ((unsigned)b & 0xffff); 0728 DUMPBITS(16) 0729 NEEDBITS(16) 0730 if (n != (unsigned)((~b) & 0xffff)) 0731 return 1; /* error in compressed data */ 0732 DUMPBITS(16) 0733 0734 0735 /* read and output the compressed data */ 0736 while (n--) 0737 { 0738 NEEDBITS(8) 0739 slide[w++] = (uch)b; 0740 if (w == WSIZE) 0741 { 0742 flush_output(w); 0743 w = 0; 0744 } 0745 DUMPBITS(8) 0746 } 0747 0748 0749 /* restore the globals from the locals */ 0750 wp = w; /* restore global window pointer */ 0751 bb = b; /* restore global bit buffer */ 0752 bk = k; 0753 0754 DEBG(">"); 0755 return 0; 0756 0757 underrun: 0758 return 4; /* Input underrun */ 0759 } 0760 0761 0762 /* 0763 * We use `noinline' here to prevent gcc-3.5 from using too much stack space 0764 */ 0765 STATIC int noinline INIT inflate_fixed(void) 0766 /* decompress an inflated type 1 (fixed Huffman codes) block. We should 0767 either replace this with a custom decoder, or at least precompute the 0768 Huffman tables. */ 0769 { 0770 int i; /* temporary variable */ 0771 struct huft *tl; /* literal/length code table */ 0772 struct huft *td; /* distance code table */ 0773 int bl; /* lookup bits for tl */ 0774 int bd; /* lookup bits for td */ 0775 unsigned *l; /* length list for huft_build */ 0776 0777 DEBG("<fix"); 0778 0779 l = malloc(sizeof(*l) * 288); 0780 if (l == NULL) 0781 return 3; /* out of memory */ 0782 0783 /* set up literal table */ 0784 for (i = 0; i < 144; i++) 0785 l[i] = 8; 0786 for (; i < 256; i++) 0787 l[i] = 9; 0788 for (; i < 280; i++) 0789 l[i] = 7; 0790 for (; i < 288; i++) /* make a complete, but wrong code set */ 0791 l[i] = 8; 0792 bl = 7; 0793 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) { 0794 free(l); 0795 return i; 0796 } 0797 0798 /* set up distance table */ 0799 for (i = 0; i < 30; i++) /* make an incomplete code set */ 0800 l[i] = 5; 0801 bd = 5; 0802 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) 0803 { 0804 huft_free(tl); 0805 free(l); 0806 0807 DEBG(">"); 0808 return i; 0809 } 0810 0811 0812 /* decompress until an end-of-block code */ 0813 if (inflate_codes(tl, td, bl, bd)) { 0814 free(l); 0815 return 1; 0816 } 0817 0818 /* free the decoding tables, return */ 0819 free(l); 0820 huft_free(tl); 0821 huft_free(td); 0822 return 0; 0823 } 0824 0825 0826 /* 0827 * We use `noinline' here to prevent gcc-3.5 from using too much stack space 0828 */ 0829 STATIC int noinline INIT inflate_dynamic(void) 0830 /* decompress an inflated type 2 (dynamic Huffman codes) block. */ 0831 { 0832 int i; /* temporary variables */ 0833 unsigned j; 0834 unsigned l; /* last length */ 0835 unsigned m; /* mask for bit lengths table */ 0836 unsigned n; /* number of lengths to get */ 0837 struct huft *tl; /* literal/length code table */ 0838 struct huft *td; /* distance code table */ 0839 int bl; /* lookup bits for tl */ 0840 int bd; /* lookup bits for td */ 0841 unsigned nb; /* number of bit length codes */ 0842 unsigned nl; /* number of literal/length codes */ 0843 unsigned nd; /* number of distance codes */ 0844 unsigned *ll; /* literal/length and distance code lengths */ 0845 register ulg b; /* bit buffer */ 0846 register unsigned k; /* number of bits in bit buffer */ 0847 int ret; 0848 0849 DEBG("<dyn"); 0850 0851 #ifdef PKZIP_BUG_WORKAROUND 0852 ll = malloc(sizeof(*ll) * (288+32)); /* literal/length and distance code lengths */ 0853 #else 0854 ll = malloc(sizeof(*ll) * (286+30)); /* literal/length and distance code lengths */ 0855 #endif 0856 0857 if (ll == NULL) 0858 return 1; 0859 0860 /* make local bit buffer */ 0861 b = bb; 0862 k = bk; 0863 0864 0865 /* read in table lengths */ 0866 NEEDBITS(5) 0867 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ 0868 DUMPBITS(5) 0869 NEEDBITS(5) 0870 nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ 0871 DUMPBITS(5) 0872 NEEDBITS(4) 0873 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ 0874 DUMPBITS(4) 0875 #ifdef PKZIP_BUG_WORKAROUND 0876 if (nl > 288 || nd > 32) 0877 #else 0878 if (nl > 286 || nd > 30) 0879 #endif 0880 { 0881 ret = 1; /* bad lengths */ 0882 goto out; 0883 } 0884 0885 DEBG("dyn1 "); 0886 0887 /* read in bit-length-code lengths */ 0888 for (j = 0; j < nb; j++) 0889 { 0890 NEEDBITS(3) 0891 ll[border[j]] = (unsigned)b & 7; 0892 DUMPBITS(3) 0893 } 0894 for (; j < 19; j++) 0895 ll[border[j]] = 0; 0896 0897 DEBG("dyn2 "); 0898 0899 /* build decoding table for trees--single level, 7 bit lookup */ 0900 bl = 7; 0901 if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) 0902 { 0903 if (i == 1) 0904 huft_free(tl); 0905 ret = i; /* incomplete code set */ 0906 goto out; 0907 } 0908 0909 DEBG("dyn3 "); 0910 0911 /* read in literal and distance code lengths */ 0912 n = nl + nd; 0913 m = mask_bits[bl]; 0914 i = l = 0; 0915 while ((unsigned)i < n) 0916 { 0917 NEEDBITS((unsigned)bl) 0918 j = (td = tl + ((unsigned)b & m))->b; 0919 DUMPBITS(j) 0920 j = td->v.n; 0921 if (j < 16) /* length of code in bits (0..15) */ 0922 ll[i++] = l = j; /* save last length in l */ 0923 else if (j == 16) /* repeat last length 3 to 6 times */ 0924 { 0925 NEEDBITS(2) 0926 j = 3 + ((unsigned)b & 3); 0927 DUMPBITS(2) 0928 if ((unsigned)i + j > n) { 0929 ret = 1; 0930 goto out; 0931 } 0932 while (j--) 0933 ll[i++] = l; 0934 } 0935 else if (j == 17) /* 3 to 10 zero length codes */ 0936 { 0937 NEEDBITS(3) 0938 j = 3 + ((unsigned)b & 7); 0939 DUMPBITS(3) 0940 if ((unsigned)i + j > n) { 0941 ret = 1; 0942 goto out; 0943 } 0944 while (j--) 0945 ll[i++] = 0; 0946 l = 0; 0947 } 0948 else /* j == 18: 11 to 138 zero length codes */ 0949 { 0950 NEEDBITS(7) 0951 j = 11 + ((unsigned)b & 0x7f); 0952 DUMPBITS(7) 0953 if ((unsigned)i + j > n) { 0954 ret = 1; 0955 goto out; 0956 } 0957 while (j--) 0958 ll[i++] = 0; 0959 l = 0; 0960 } 0961 } 0962 0963 DEBG("dyn4 "); 0964 0965 /* free decoding table for trees */ 0966 huft_free(tl); 0967 0968 DEBG("dyn5 "); 0969 0970 /* restore the global bit buffer */ 0971 bb = b; 0972 bk = k; 0973 0974 DEBG("dyn5a "); 0975 0976 /* build the decoding tables for literal/length and distance codes */ 0977 bl = lbits; 0978 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) 0979 { 0980 DEBG("dyn5b "); 0981 if (i == 1) { 0982 error("incomplete literal tree"); 0983 huft_free(tl); 0984 } 0985 ret = i; /* incomplete code set */ 0986 goto out; 0987 } 0988 DEBG("dyn5c "); 0989 bd = dbits; 0990 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) 0991 { 0992 DEBG("dyn5d "); 0993 if (i == 1) { 0994 error("incomplete distance tree"); 0995 #ifdef PKZIP_BUG_WORKAROUND 0996 i = 0; 0997 } 0998 #else 0999 huft_free(td); 1000 } 1001 huft_free(tl); 1002 ret = i; /* incomplete code set */ 1003 goto out; 1004 #endif 1005 } 1006 1007 DEBG("dyn6 "); 1008 1009 /* decompress until an end-of-block code */ 1010 if (inflate_codes(tl, td, bl, bd)) { 1011 ret = 1; 1012 goto out; 1013 } 1014 1015 DEBG("dyn7 "); 1016 1017 /* free the decoding tables, return */ 1018 huft_free(tl); 1019 huft_free(td); 1020 1021 DEBG(">"); 1022 ret = 0; 1023 out: 1024 free(ll); 1025 return ret; 1026 1027 underrun: 1028 ret = 4; /* Input underrun */ 1029 goto out; 1030 } 1031 1032 1033 1034 STATIC int INIT inflate_block( 1035 int *e /* last block flag */ 1036 ) 1037 /* decompress an inflated block */ 1038 { 1039 unsigned t; /* block type */ 1040 register ulg b; /* bit buffer */ 1041 register unsigned k; /* number of bits in bit buffer */ 1042 1043 DEBG("<blk"); 1044 1045 /* make local bit buffer */ 1046 b = bb; 1047 k = bk; 1048 1049 1050 /* read in last block bit */ 1051 NEEDBITS(1) 1052 *e = (int)b & 1; 1053 DUMPBITS(1) 1054 1055 1056 /* read in block type */ 1057 NEEDBITS(2) 1058 t = (unsigned)b & 3; 1059 DUMPBITS(2) 1060 1061 1062 /* restore the global bit buffer */ 1063 bb = b; 1064 bk = k; 1065 1066 /* inflate that block type */ 1067 if (t == 2) 1068 return inflate_dynamic(); 1069 if (t == 0) 1070 return inflate_stored(); 1071 if (t == 1) 1072 return inflate_fixed(); 1073 1074 DEBG(">"); 1075 1076 /* bad block type */ 1077 return 2; 1078 1079 underrun: 1080 return 4; /* Input underrun */ 1081 } 1082 1083 1084 1085 STATIC int INIT inflate(void) 1086 /* decompress an inflated entry */ 1087 { 1088 int e; /* last block flag */ 1089 int r; /* result code */ 1090 unsigned h; /* maximum struct huft's malloc'ed */ 1091 1092 /* initialize window, bit buffer */ 1093 wp = 0; 1094 bk = 0; 1095 bb = 0; 1096 1097 1098 /* decompress until the last block */ 1099 h = 0; 1100 do { 1101 hufts = 0; 1102 #ifdef ARCH_HAS_DECOMP_WDOG 1103 arch_decomp_wdog(); 1104 #endif 1105 r = inflate_block(&e); 1106 if (r) 1107 return r; 1108 if (hufts > h) 1109 h = hufts; 1110 } while (!e); 1111 1112 /* Undo too much lookahead. The next read will be byte aligned so we 1113 * can discard unused bits in the last meaningful byte. 1114 */ 1115 while (bk >= 8) { 1116 bk -= 8; 1117 inptr--; 1118 } 1119 1120 /* flush out slide */ 1121 flush_output(wp); 1122 1123 1124 /* return success */ 1125 #ifdef DEBUG 1126 fprintf(stderr, "<%u> ", h); 1127 #endif /* DEBUG */ 1128 return 0; 1129 } 1130 1131 /********************************************************************** 1132 * 1133 * The following are support routines for inflate.c 1134 * 1135 **********************************************************************/ 1136 1137 static ulg crc_32_tab[256]; 1138 static ulg crc; /* initialized in makecrc() so it'll reside in bss */ 1139 #define CRC_VALUE (crc ^ 0xffffffffUL) 1140 1141 /* 1142 * Code to compute the CRC-32 table. Borrowed from 1143 * gzip-1.0.3/makecrc.c. 1144 */ 1145 1146 static void INIT 1147 makecrc(void) 1148 { 1149 /* Not copyrighted 1990 Mark Adler */ 1150 1151 unsigned long c; /* crc shift register */ 1152 unsigned long e; /* polynomial exclusive-or pattern */ 1153 int i; /* counter for all possible eight bit values */ 1154 int k; /* byte being shifted into crc apparatus */ 1155 1156 /* terms of polynomial defining this crc (except x^32): */ 1157 static const int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 1158 1159 /* Make exclusive-or pattern from polynomial */ 1160 e = 0; 1161 for (i = 0; i < sizeof(p)/sizeof(int); i++) 1162 e |= 1L << (31 - p[i]); 1163 1164 crc_32_tab[0] = 0; 1165 1166 for (i = 1; i < 256; i++) 1167 { 1168 c = 0; 1169 for (k = i | 256; k != 1; k >>= 1) 1170 { 1171 c = c & 1 ? (c >> 1) ^ e : c >> 1; 1172 if (k & 1) 1173 c ^= e; 1174 } 1175 crc_32_tab[i] = c; 1176 } 1177 1178 /* this is initialized here so this code could reside in ROM */ 1179 crc = (ulg)0xffffffffUL; /* shift register contents */ 1180 } 1181 1182 /* gzip flag byte */ 1183 #define ASCII_FLAG 0x01 /* bit 0 set: file probably ASCII text */ 1184 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */ 1185 #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */ 1186 #define ORIG_NAME 0x08 /* bit 3 set: original file name present */ 1187 #define COMMENT 0x10 /* bit 4 set: file comment present */ 1188 #define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */ 1189 #define RESERVED 0xC0 /* bit 6,7: reserved */ 1190 1191 /* 1192 * Do the uncompression! 1193 */ 1194 static int INIT gunzip(void) 1195 { 1196 uch flags; 1197 unsigned char magic[2]; /* magic header */ 1198 char method; 1199 ulg orig_crc = 0; /* original crc */ 1200 ulg orig_len = 0; /* original uncompressed length */ 1201 int res; 1202 1203 magic[0] = NEXTBYTE(); 1204 magic[1] = NEXTBYTE(); 1205 method = NEXTBYTE(); 1206 1207 if (magic[0] != 037 || 1208 ((magic[1] != 0213) && (magic[1] != 0236))) { 1209 error("bad gzip magic numbers"); 1210 return -1; 1211 } 1212 1213 /* We only support method #8, DEFLATED */ 1214 if (method != 8) { 1215 error("internal error, invalid method"); 1216 return -1; 1217 } 1218 1219 flags = (uch)get_byte(); 1220 if ((flags & ENCRYPTED) != 0) { 1221 error("Input is encrypted"); 1222 return -1; 1223 } 1224 if ((flags & CONTINUATION) != 0) { 1225 error("Multi part input"); 1226 return -1; 1227 } 1228 if ((flags & RESERVED) != 0) { 1229 error("Input has invalid flags"); 1230 return -1; 1231 } 1232 NEXTBYTE(); /* Get timestamp */ 1233 NEXTBYTE(); 1234 NEXTBYTE(); 1235 NEXTBYTE(); 1236 1237 (void)NEXTBYTE(); /* Ignore extra flags for the moment */ 1238 (void)NEXTBYTE(); /* Ignore OS type for the moment */ 1239 1240 if ((flags & EXTRA_FIELD) != 0) { 1241 unsigned len = (unsigned)NEXTBYTE(); 1242 len |= ((unsigned)NEXTBYTE())<<8; 1243 while (len--) (void)NEXTBYTE(); 1244 } 1245 1246 /* Get original file name if it was truncated */ 1247 if ((flags & ORIG_NAME) != 0) { 1248 /* Discard the old name */ 1249 while (NEXTBYTE() != 0) /* null */ ; 1250 } 1251 1252 /* Discard file comment if any */ 1253 if ((flags & COMMENT) != 0) { 1254 while (NEXTBYTE() != 0) /* null */ ; 1255 } 1256 1257 /* Decompress */ 1258 if ((res = inflate())) { 1259 switch (res) { 1260 case 0: 1261 break; 1262 case 1: 1263 error("invalid compressed format (err=1)"); 1264 break; 1265 case 2: 1266 error("invalid compressed format (err=2)"); 1267 break; 1268 case 3: 1269 error("out of memory"); 1270 break; 1271 case 4: 1272 error("out of input data"); 1273 break; 1274 default: 1275 error("invalid compressed format (other)"); 1276 } 1277 return -1; 1278 } 1279 1280 /* Get the crc and original length */ 1281 /* crc32 (see algorithm.doc) 1282 * uncompressed input size modulo 2^32 1283 */ 1284 orig_crc = (ulg) NEXTBYTE(); 1285 orig_crc |= (ulg) NEXTBYTE() << 8; 1286 orig_crc |= (ulg) NEXTBYTE() << 16; 1287 orig_crc |= (ulg) NEXTBYTE() << 24; 1288 1289 orig_len = (ulg) NEXTBYTE(); 1290 orig_len |= (ulg) NEXTBYTE() << 8; 1291 orig_len |= (ulg) NEXTBYTE() << 16; 1292 orig_len |= (ulg) NEXTBYTE() << 24; 1293 1294 /* Validate decompression */ 1295 if (orig_crc != CRC_VALUE) { 1296 error("crc error"); 1297 return -1; 1298 } 1299 if (orig_len != bytes_out) { 1300 error("length error"); 1301 return -1; 1302 } 1303 return 0; 1304 1305 underrun: /* NEXTBYTE() goto's here if needed */ 1306 error("out of input data"); 1307 return -1; 1308 } 1309 1310
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.1.0 LXR engine. The LXR team |
|