Lines Matching +full:j +full:- +full:to +full:- +full:k
1 // SPDX-License-Identifier: GPL-2.0
4 /* inflate.c -- Not copyrighted 1992 by Mark Adler
9 * based on gzip-1.0.3
12 * Little mods for all variable to reside either into rodata or bss segments
14 * at run-time only. This allows for the kernel uncompressor to run
20 method searches for as much of the current string of bytes (up to a
21 length of 258) in the previous 32 K bytes. If it doesn't find any
28 of "extra" (sometimes zero) bits to get to add to the base value. At
29 the end of each deflated block is a special end-of-block (EOB) literal/
32 length then get the distance and emit the referred-to bytes from the
37 decides which method to use on a chunk-by-chunk basis. A chunk might
38 typically be 32 K or 64 K. If the chunk is incompressible, then the
46 to be used to decode this block. The representation is itself Huffman
52 codes are customized to the probabilities in the current block, and so
53 can code it much better than the pre-determined fixed codes.
55 The Huffman codes themselves are decoded using a multi-level table
56 lookup, in order to maximize the speed of decoding plus the speed of
67 2. Distance pointers can point back across blocks, up to 32k away.
73 5. There is no way of sending zero distance codes--a dummy must be
75 store blocks with no distance codes, but this was discovered to be
79 6. There are up to 286 literal/length codes. Code 256 represents the
80 end-of-block. Note however that the static length tree defines
81 288 codes just to fill out the Huffman codes. Codes 286 and 287
83 defined for them. Similarly, there are up to 30 distance codes.
84 However, static trees define 32 codes (all 5 bits) to fill out the
91 (1+6+6). Therefore, to output three times the length, you output
92 three codes (1+1+1), whereas to output four times the same length,
96 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
97 12. Note: length code 284 can represent 227-258, but length code 285
100 258 is special since 258 - 3 (the min match length) is 255.
103 a repeat code (16, 17, or 18) to go across the boundary between
132 /* Huffman code lookup table entry--this entry is four bytes for machines
133 that have 16-bit pointers (e.g. PC's in the small or medium model).
135 means that v is a literal, 16 < e < 32 means that v is a pointer to
136 the next table, which codes e - 16 bits, and lastly e == 99 indicates
144 struct huft *t; /* pointer to next level of table */
161 /* The inflate algorithm uses a sliding 32 K byte window on the uncompressed
162 stream to find repeated byte strings. This is implemented here as a
164 ANDing with 0x7fff (32K-1). */
165 /* It is left to other modules to supply the 32 K area. It is assumed
166 to be usable as if it were declared "uch slide[32768];" or as just
197 NEEDBITS(j)
198 x = b & mask_bits[j];
199 DUMPBITS(j)
201 where NEEDBITS makes sure that b has at least j bits in it, and
202 DUMPBITS removes the bits from b. The macros use the variable k
203 for the number of bits in b. Normally, b and k are register
209 So, NEEDBITS should not read any more bytes than are needed to
210 meet the request. Then no bytes need to be "returned" to the buffer
213 However, this assumption is not true for fixed blocks--the EOB code
234 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
235 #define DUMPBITS(n) {b>>=(n);k-=(n);}
268 malloc_count--; in free()
278 Huffman code decoding is performed using a multi-level table lookup.
279 The fastest way to decode is to simply build a lookup table whose
281 to build this table can also be a factor if the data being decoded
285 shorter, more probable codes, and then point to subsidiary tables for
286 the longer codes. The time it costs to decode the longer codes is
287 then traded against the time it takes to make longer tables.
292 the distance codes. Subsequent tables are also less than or equal to
305 The optimum values may differ though from machine to machine, and
314 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
325 unsigned s, /* number of simple-valued codes (0..s-1) */ in huft_build()
326 const ush *d, /* list of base values for non-simple codes */ in huft_build()
327 const ush *e, /* list of extra bits for non-simple codes */ in huft_build()
332 tables to decode that set of codes. Return zero on success, one if in huft_build()
337 unsigned a; /* counter for codes of length k */ in huft_build()
342 register unsigned j; /* counter */ in huft_build() local
343 register int k; /* number of bits in current code */ in huft_build() local
346 register struct huft *q; /* points to current table */ in huft_build()
368 c = stk->c; in huft_build()
369 v = stk->v; in huft_build()
370 x = stk->x; in huft_build()
371 u = stk->u; in huft_build()
374 memzero(stk->c, sizeof(stk->c)); in huft_build()
377 Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), in huft_build()
378 n-i, *p)); in huft_build()
381 } while (--i); in huft_build()
382 if (c[0] == n) /* null input--all zero length codes */ in huft_build()
394 for (j = 1; j <= BMAX; j++) in huft_build()
395 if (c[j]) in huft_build()
397 k = j; /* minimum code length */ in huft_build()
398 if ((unsigned)l < j) in huft_build()
399 l = j; in huft_build()
400 for (i = BMAX; i; i--) in huft_build()
410 /* Adjust last length count to fill out codes, if needed */ in huft_build()
411 for (y = 1 << j; j < i; j++, y <<= 1) in huft_build()
412 if ((y -= c[j]) < 0) { in huft_build()
416 if ((y -= c[i]) < 0) { in huft_build()
425 x[1] = j = 0; in huft_build()
427 while (--i) { /* note that i == g from above */ in huft_build()
428 *xp++ = (j += *p++); in huft_build()
436 if ((j = *p++) != 0) in huft_build()
437 v[x[j]++] = i; in huft_build()
439 n = x[g]; /* set n to length of v */ in huft_build()
446 h = -1; /* no tables yet--level -1 */ in huft_build()
447 w = -l; /* bits decoded == (l * h) */ in huft_build()
448 u[0] = (struct huft *)NULL; /* just to keep compilers happy */ in huft_build()
453 /* go through the bit lengths (k already is bits in shortest code) */ in huft_build()
454 for (; k <= g; k++) in huft_build()
457 a = c[k]; in huft_build()
458 while (a--) in huft_build()
461 /* here i is the Huffman code of length k bits for value *p */ in huft_build()
462 /* make tables up to required level */ in huft_build()
463 while (k > w + l) in huft_build()
469 /* compute minimum size table less than or equal to l bits */ in huft_build()
470 z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */ in huft_build()
471 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ in huft_build()
472 { /* too few codes for k-w bit table */ in huft_build()
474 f -= a + 1; /* deduct codes from patterns left */ in huft_build()
475 xp = c + k; in huft_build()
476 if (j < z) in huft_build()
477 while (++j < z) /* try smaller tables up to z bits */ in huft_build()
480 break; /* enough codes to use up j bits */ in huft_build()
481 f -= *xp; /* else deduct codes from patterns */ in huft_build()
485 z = 1 << j; /* table entries for j-bit table */ in huft_build()
498 *t = q + 1; /* link to list for huft_free() */ in huft_build()
499 *(t = &(q->v.t)) = (struct huft *)NULL; in huft_build()
503 /* connect to last table, if there is one */ in huft_build()
507 r.b = (uch)l; /* bits to dump before this table */ in huft_build()
508 r.e = (uch)(16 + j); /* bits in this table */ in huft_build()
509 r.v.t = q; /* pointer to this table */ in huft_build()
510 j = i >> (w - l); /* (get around Turbo C bug) */ in huft_build()
511 u[h-1][j] = r; /* connect to last table */ in huft_build()
518 r.b = (uch)(k - w); in huft_build()
520 r.e = 99; /* out of values--invalid code */ in huft_build()
523 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ in huft_build()
529 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ in huft_build()
530 r.v.n = d[*p++ - s]; in huft_build()
534 /* fill code-like entries with r */ in huft_build()
535 f = 1 << (k - w); in huft_build()
536 for (j = i >> w; j < z; j += f) in huft_build()
537 q[j] = r; in huft_build()
539 /* backwards increment the k-bit code i */ in huft_build()
540 for (j = 1 << (k - 1); i & j; j >>= 1) in huft_build()
541 i ^= j; in huft_build()
542 i ^= j; in huft_build()
545 while ((i & ((1 << w) - 1)) != x[h]) in huft_build()
547 h--; /* don't need to update q */ in huft_build()
548 w -= l; in huft_build()
568 struct huft *t /* table to free */ in huft_free()
577 /* Go through linked list, freeing from the malloced (t[-1]) address. */ in huft_free()
581 q = (--p)->v.t; in huft_free()
601 struct huft *t; /* pointer to table entry */ in inflate_codes()
604 register unsigned k; /* number of bits in bit buffer */ in inflate_codes() local
609 k = bk; in inflate_codes()
618 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) in inflate_codes()
622 DUMPBITS(t->b) in inflate_codes()
623 e -= 16; in inflate_codes()
625 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); in inflate_codes()
626 DUMPBITS(t->b) in inflate_codes()
629 slide[w++] = (uch)t->v.n; in inflate_codes()
630 Tracevv((stderr, "%c", slide[w-1])); in inflate_codes()
643 /* get length of block to copy */ in inflate_codes()
645 n = t->v.n + ((unsigned)b & mask_bits[e]); in inflate_codes()
648 /* decode distance of block to copy */ in inflate_codes()
650 if ((e = (t = td + ((unsigned)b & md))->e) > 16) in inflate_codes()
654 DUMPBITS(t->b) in inflate_codes()
655 e -= 16; in inflate_codes()
657 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); in inflate_codes()
658 DUMPBITS(t->b) in inflate_codes()
660 d = w - t->v.n - ((unsigned)b & mask_bits[e]); in inflate_codes()
662 Tracevv((stderr,"\\[%d,%d]", w-d, n)); in inflate_codes()
666 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); in inflate_codes()
668 if (w - d >= e) /* (this test assumes unsigned comparison) */ in inflate_codes()
674 else /* do it slow to avoid memcpy() overlap */ in inflate_codes()
678 Tracevv((stderr, "%c", slide[w-1])); in inflate_codes()
679 } while (--e); in inflate_codes()
693 bk = k; in inflate_codes()
710 register unsigned k; /* number of bits in bit buffer */ in inflate_stored() local
716 k = bk; in inflate_stored()
720 /* go to byte boundary */ in inflate_stored()
721 n = k & 7; in inflate_stored()
736 while (n--) in inflate_stored()
752 bk = k; in inflate_stored()
763 * We use `noinline' here to prevent gcc-3.5 from using too much stack space
812 /* decompress until an end-of-block code */ in inflate_fixed()
827 * We use `noinline' here to prevent gcc-3.5 from using too much stack space
833 unsigned j; in inflate_dynamic() local
836 unsigned n; /* number of lengths to get */ in inflate_dynamic()
846 register unsigned k; /* number of bits in bit buffer */ in inflate_dynamic() local
862 k = bk; in inflate_dynamic()
887 /* read in bit-length-code lengths */ in inflate_dynamic()
888 for (j = 0; j < nb; j++) in inflate_dynamic()
891 ll[border[j]] = (unsigned)b & 7; in inflate_dynamic()
894 for (; j < 19; j++) in inflate_dynamic()
895 ll[border[j]] = 0; in inflate_dynamic()
899 /* build decoding table for trees--single level, 7 bit lookup */ in inflate_dynamic()
918 j = (td = tl + ((unsigned)b & m))->b; in inflate_dynamic()
919 DUMPBITS(j) in inflate_dynamic()
920 j = td->v.n; in inflate_dynamic()
921 if (j < 16) /* length of code in bits (0..15) */ in inflate_dynamic()
922 ll[i++] = l = j; /* save last length in l */ in inflate_dynamic()
923 else if (j == 16) /* repeat last length 3 to 6 times */ in inflate_dynamic()
926 j = 3 + ((unsigned)b & 3); in inflate_dynamic()
928 if ((unsigned)i + j > n) { in inflate_dynamic()
932 while (j--) in inflate_dynamic()
935 else if (j == 17) /* 3 to 10 zero length codes */ in inflate_dynamic()
938 j = 3 + ((unsigned)b & 7); in inflate_dynamic()
940 if ((unsigned)i + j > n) { in inflate_dynamic()
944 while (j--) in inflate_dynamic()
948 else /* j == 18: 11 to 138 zero length codes */ in inflate_dynamic()
951 j = 11 + ((unsigned)b & 0x7f); in inflate_dynamic()
953 if ((unsigned)i + j > n) { in inflate_dynamic()
957 while (j--) in inflate_dynamic()
972 bk = k; in inflate_dynamic()
1009 /* decompress until an end-of-block code */
1041 register unsigned k; /* number of bits in bit buffer */ in inflate_block() local
1047 k = bk; in inflate_block()
1064 bk = k; in inflate_block()
1116 bk -= 8; in inflate()
1117 inptr--; in inflate()
1142 * Code to compute the CRC-32 table. Borrowed from
1143 * gzip-1.0.3/makecrc.c.
1152 unsigned long e; /* polynomial exclusive-or pattern */ in makecrc()
1154 int k; /* byte being shifted into crc apparatus */ in makecrc() local
1159 /* Make exclusive-or pattern from polynomial */ in makecrc()
1162 e |= 1L << (31 - p[i]); in makecrc()
1169 for (k = i | 256; k != 1; k >>= 1) in makecrc()
1172 if (k & 1) in makecrc()
1184 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
1210 return -1; in gunzip()
1216 return -1; in gunzip()
1222 return -1; in gunzip()
1226 return -1; in gunzip()
1230 return -1; in gunzip()
1243 while (len--) (void)NEXTBYTE(); in gunzip()
1277 return -1; in gunzip()
1297 return -1; in gunzip()
1301 return -1; in gunzip()
1307 return -1; in gunzip()