aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorRichard Purdie <rpurdie@rpsys.net>2006-06-22 17:47:34 -0400
committerLinus Torvalds <torvalds@g5.osdl.org>2006-06-22 18:05:58 -0400
commit4f3865fb57a04db7cca068fed1c15badc064a302 (patch)
tree4c923c72b6ac9b633c87cc73b55a75c7cfd0f044 /lib
parent4f1bcaf094ccc512c23e10104c05a6f8e5b7a9e4 (diff)
[PATCH] zlib_inflate: Upgrade library code to a recent version
Upgrade the zlib_inflate implementation in the kernel from a patched version 1.1.3/4 to a patched 1.2.3. The code in the kernel is about seven years old and I noticed that the external zlib library's inflate performance was significantly faster (~50%) than the code in the kernel on ARM (and faster again on x86_32). For comparison the newer deflate code is 20% slower on ARM and 50% slower on x86_32 but gives an approx 1% compression ratio improvement. I don't consider this to be an improvement for kernel use so have no plans to change the zlib_deflate code. Various changes have been made to the zlib code in the kernel, the most significant being the extra functions/flush option used by ppp_deflate. This update reimplements the features PPP needs to ensure it continues to work. This code has been tested on ARM under both JFFS2 (with zlib compression enabled) and ppp_deflate and on x86_32. JFFS2 sees an approx. 10% real world file read speed improvement. This patch also removes ZLIB_VERSION as it no longer has a correct value. We don't need version checks anyway as the kernel's module handling will take care of that for us. This removal is also more in keeping with the zlib author's wishes (http://www.zlib.net/zlib_faq.html#faq24) and I've added something to the zlib.h header to note its a modified version. Signed-off-by: Richard Purdie <rpurdie@rpsys.net> Acked-by: Joern Engel <joern@wh.fh-wedel.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/zlib_deflate/deflate.c25
-rw-r--r--lib/zlib_deflate/deflate_syms.c3
-rw-r--r--lib/zlib_inflate/Makefile4
-rw-r--r--lib/zlib_inflate/infblock.c365
-rw-r--r--lib/zlib_inflate/infblock.h48
-rw-r--r--lib/zlib_inflate/infcodes.c202
-rw-r--r--lib/zlib_inflate/infcodes.h33
-rw-r--r--lib/zlib_inflate/inffast.c462
-rw-r--r--lib/zlib_inflate/inffast.h12
-rw-r--r--lib/zlib_inflate/inffixed.h94
-rw-r--r--lib/zlib_inflate/inflate.c1086
-rw-r--r--lib/zlib_inflate/inflate.h107
-rw-r--r--lib/zlib_inflate/inflate_syms.c3
-rw-r--r--lib/zlib_inflate/inflate_sync.c152
-rw-r--r--lib/zlib_inflate/inftrees.c683
-rw-r--r--lib/zlib_inflate/inftrees.h99
-rw-r--r--lib/zlib_inflate/infutil.c88
-rw-r--r--lib/zlib_inflate/infutil.h176
18 files changed, 1732 insertions, 1910 deletions
diff --git a/lib/zlib_deflate/deflate.c b/lib/zlib_deflate/deflate.c
index 1653dd9bb01a..c3e4a2baf835 100644
--- a/lib/zlib_deflate/deflate.c
+++ b/lib/zlib_deflate/deflate.c
@@ -164,34 +164,17 @@ static const config configuration_table[10] = {
164 memset((char *)s->head, 0, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 164 memset((char *)s->head, 0, (unsigned)(s->hash_size-1)*sizeof(*s->head));
165 165
166/* ========================================================================= */ 166/* ========================================================================= */
167int zlib_deflateInit_( 167int zlib_deflateInit2(
168 z_streamp strm,
169 int level,
170 const char *version,
171 int stream_size
172)
173{
174 return zlib_deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS,
175 DEF_MEM_LEVEL,
176 Z_DEFAULT_STRATEGY, version, stream_size);
177 /* To do: ignore strm->next_in if we use it as window */
178}
179
180/* ========================================================================= */
181int zlib_deflateInit2_(
182 z_streamp strm, 168 z_streamp strm,
183 int level, 169 int level,
184 int method, 170 int method,
185 int windowBits, 171 int windowBits,
186 int memLevel, 172 int memLevel,
187 int strategy, 173 int strategy
188 const char *version,
189 int stream_size
190) 174)
191{ 175{
192 deflate_state *s; 176 deflate_state *s;
193 int noheader = 0; 177 int noheader = 0;
194 static char* my_version = ZLIB_VERSION;
195 deflate_workspace *mem; 178 deflate_workspace *mem;
196 179
197 ush *overlay; 180 ush *overlay;
@@ -199,10 +182,6 @@ int zlib_deflateInit2_(
199 * output size for (length,distance) codes is <= 24 bits. 182 * output size for (length,distance) codes is <= 24 bits.
200 */ 183 */
201 184
202 if (version == NULL || version[0] != my_version[0] ||
203 stream_size != sizeof(z_stream)) {
204 return Z_VERSION_ERROR;
205 }
206 if (strm == NULL) return Z_STREAM_ERROR; 185 if (strm == NULL) return Z_STREAM_ERROR;
207 186
208 strm->msg = NULL; 187 strm->msg = NULL;
diff --git a/lib/zlib_deflate/deflate_syms.c b/lib/zlib_deflate/deflate_syms.c
index 767b573d1ef6..ccfe25f3920f 100644
--- a/lib/zlib_deflate/deflate_syms.c
+++ b/lib/zlib_deflate/deflate_syms.c
@@ -12,8 +12,7 @@
12 12
13EXPORT_SYMBOL(zlib_deflate_workspacesize); 13EXPORT_SYMBOL(zlib_deflate_workspacesize);
14EXPORT_SYMBOL(zlib_deflate); 14EXPORT_SYMBOL(zlib_deflate);
15EXPORT_SYMBOL(zlib_deflateInit_); 15EXPORT_SYMBOL(zlib_deflateInit2);
16EXPORT_SYMBOL(zlib_deflateInit2_);
17EXPORT_SYMBOL(zlib_deflateEnd); 16EXPORT_SYMBOL(zlib_deflateEnd);
18EXPORT_SYMBOL(zlib_deflateReset); 17EXPORT_SYMBOL(zlib_deflateReset);
19MODULE_LICENSE("GPL"); 18MODULE_LICENSE("GPL");
diff --git a/lib/zlib_inflate/Makefile b/lib/zlib_inflate/Makefile
index 221c139e0df1..bf065482fa67 100644
--- a/lib/zlib_inflate/Makefile
+++ b/lib/zlib_inflate/Makefile
@@ -15,5 +15,5 @@
15 15
16obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate.o 16obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate.o
17 17
18zlib_inflate-objs := infblock.o infcodes.o inffast.o inflate.o \ 18zlib_inflate-objs := inffast.o inflate.o \
19 inflate_sync.o inftrees.o infutil.o inflate_syms.o 19 inftrees.o inflate_syms.o
diff --git a/lib/zlib_inflate/infblock.c b/lib/zlib_inflate/infblock.c
deleted file mode 100644
index c16cdeff51aa..000000000000
--- a/lib/zlib_inflate/infblock.c
+++ /dev/null
@@ -1,365 +0,0 @@
1/* infblock.c -- interpret and process block types to last block
2 * Copyright (C) 1995-1998 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include <linux/zutil.h>
7#include "infblock.h"
8#include "inftrees.h"
9#include "infcodes.h"
10#include "infutil.h"
11
12struct inflate_codes_state;
13
14/* simplify the use of the inflate_huft type with some defines */
15#define exop word.what.Exop
16#define bits word.what.Bits
17
18/* Table for deflate from PKZIP's appnote.txt. */
19static const uInt border[] = { /* Order of the bit length code lengths */
20 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
21
22/*
23 Notes beyond the 1.93a appnote.txt:
24
25 1. Distance pointers never point before the beginning of the output
26 stream.
27 2. Distance pointers can point back across blocks, up to 32k away.
28 3. There is an implied maximum of 7 bits for the bit length table and
29 15 bits for the actual data.
30 4. If only one code exists, then it is encoded using one bit. (Zero
31 would be more efficient, but perhaps a little confusing.) If two
32 codes exist, they are coded using one bit each (0 and 1).
33 5. There is no way of sending zero distance codes--a dummy must be
34 sent if there are none. (History: a pre 2.0 version of PKZIP would
35 store blocks with no distance codes, but this was discovered to be
36 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
37 zero distance codes, which is sent as one code of zero bits in
38 length.
39 6. There are up to 286 literal/length codes. Code 256 represents the
40 end-of-block. Note however that the static length tree defines
41 288 codes just to fill out the Huffman codes. Codes 286 and 287
42 cannot be used though, since there is no length base or extra bits
43 defined for them. Similarily, there are up to 30 distance codes.
44 However, static trees define 32 codes (all 5 bits) to fill out the
45 Huffman codes, but the last two had better not show up in the data.
46 7. Unzip can check dynamic Huffman blocks for complete code sets.
47 The exception is that a single code would not be complete (see #4).
48 8. The five bits following the block type is really the number of
49 literal codes sent minus 257.
50 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
51 (1+6+6). Therefore, to output three times the length, you output
52 three codes (1+1+1), whereas to output four times the same length,
53 you only need two codes (1+3). Hmm.
54 10. In the tree reconstruction algorithm, Code = Code + Increment
55 only if BitLength(i) is not zero. (Pretty obvious.)
56 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
57 12. Note: length code 284 can represent 227-258, but length code 285
58 really is 258. The last length deserves its own, short code
59 since it gets used a lot in very redundant files. The length
60 258 is special since 258 - 3 (the min match length) is 255.
61 13. The literal/length and distance code bit lengths are read as a
62 single stream of lengths. It is possible (and advantageous) for
63 a repeat code (16, 17, or 18) to go across the boundary between
64 the two sets of lengths.
65 */
66
67
68void zlib_inflate_blocks_reset(
69 inflate_blocks_statef *s,
70 z_streamp z,
71 uLong *c
72)
73{
74 if (c != NULL)
75 *c = s->check;
76 if (s->mode == CODES)
77 zlib_inflate_codes_free(s->sub.decode.codes, z);
78 s->mode = TYPE;
79 s->bitk = 0;
80 s->bitb = 0;
81 s->read = s->write = s->window;
82 if (s->checkfn != NULL)
83 z->adler = s->check = (*s->checkfn)(0L, NULL, 0);
84}
85
86inflate_blocks_statef *zlib_inflate_blocks_new(
87 z_streamp z,
88 check_func c,
89 uInt w
90)
91{
92 inflate_blocks_statef *s;
93
94 s = &WS(z)->working_blocks_state;
95 s->hufts = WS(z)->working_hufts;
96 s->window = WS(z)->working_window;
97 s->end = s->window + w;
98 s->checkfn = c;
99 s->mode = TYPE;
100 zlib_inflate_blocks_reset(s, z, NULL);
101 return s;
102}
103
104
105int zlib_inflate_blocks(
106 inflate_blocks_statef *s,
107 z_streamp z,
108 int r
109)
110{
111 uInt t; /* temporary storage */
112 uLong b; /* bit buffer */
113 uInt k; /* bits in bit buffer */
114 Byte *p; /* input data pointer */
115 uInt n; /* bytes available there */
116 Byte *q; /* output window write pointer */
117 uInt m; /* bytes to end of window or read pointer */
118
119 /* copy input/output information to locals (UPDATE macro restores) */
120 LOAD
121
122 /* process input based on current state */
123 while (1) switch (s->mode)
124 {
125 case TYPE:
126 NEEDBITS(3)
127 t = (uInt)b & 7;
128 s->last = t & 1;
129 switch (t >> 1)
130 {
131 case 0: /* stored */
132 DUMPBITS(3)
133 t = k & 7; /* go to byte boundary */
134 DUMPBITS(t)
135 s->mode = LENS; /* get length of stored block */
136 break;
137 case 1: /* fixed */
138 {
139 uInt bl, bd;
140 inflate_huft *tl, *td;
141
142 zlib_inflate_trees_fixed(&bl, &bd, &tl, &td, s->hufts, z);
143 s->sub.decode.codes = zlib_inflate_codes_new(bl, bd, tl, td, z);
144 if (s->sub.decode.codes == NULL)
145 {
146 r = Z_MEM_ERROR;
147 LEAVE
148 }
149 }
150 DUMPBITS(3)
151 s->mode = CODES;
152 break;
153 case 2: /* dynamic */
154 DUMPBITS(3)
155 s->mode = TABLE;
156 break;
157 case 3: /* illegal */
158 DUMPBITS(3)
159 s->mode = B_BAD;
160 z->msg = (char*)"invalid block type";
161 r = Z_DATA_ERROR;
162 LEAVE
163 }
164 break;
165 case LENS:
166 NEEDBITS(32)
167 if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
168 {
169 s->mode = B_BAD;
170 z->msg = (char*)"invalid stored block lengths";
171 r = Z_DATA_ERROR;
172 LEAVE
173 }
174 s->sub.left = (uInt)b & 0xffff;
175 b = k = 0; /* dump bits */
176 s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
177 break;
178 case STORED:
179 if (n == 0)
180 LEAVE
181 NEEDOUT
182 t = s->sub.left;
183 if (t > n) t = n;
184 if (t > m) t = m;
185 memcpy(q, p, t);
186 p += t; n -= t;
187 q += t; m -= t;
188 if ((s->sub.left -= t) != 0)
189 break;
190 s->mode = s->last ? DRY : TYPE;
191 break;
192 case TABLE:
193 NEEDBITS(14)
194 s->sub.trees.table = t = (uInt)b & 0x3fff;
195#ifndef PKZIP_BUG_WORKAROUND
196 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
197 {
198 s->mode = B_BAD;
199 z->msg = (char*)"too many length or distance symbols";
200 r = Z_DATA_ERROR;
201 LEAVE
202 }
203#endif
204 {
205 s->sub.trees.blens = WS(z)->working_blens;
206 }
207 DUMPBITS(14)
208 s->sub.trees.index = 0;
209 s->mode = BTREE;
210 case BTREE:
211 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
212 {
213 NEEDBITS(3)
214 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
215 DUMPBITS(3)
216 }
217 while (s->sub.trees.index < 19)
218 s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
219 s->sub.trees.bb = 7;
220 t = zlib_inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
221 &s->sub.trees.tb, s->hufts, z);
222 if (t != Z_OK)
223 {
224 r = t;
225 if (r == Z_DATA_ERROR)
226 s->mode = B_BAD;
227 LEAVE
228 }
229 s->sub.trees.index = 0;
230 s->mode = DTREE;
231 case DTREE:
232 while (t = s->sub.trees.table,
233 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
234 {
235 inflate_huft *h;
236 uInt i, j, c;
237
238 t = s->sub.trees.bb;
239 NEEDBITS(t)
240 h = s->sub.trees.tb + ((uInt)b & zlib_inflate_mask[t]);
241 t = h->bits;
242 c = h->base;
243 if (c < 16)
244 {
245 DUMPBITS(t)
246 s->sub.trees.blens[s->sub.trees.index++] = c;
247 }
248 else /* c == 16..18 */
249 {
250 i = c == 18 ? 7 : c - 14;
251 j = c == 18 ? 11 : 3;
252 NEEDBITS(t + i)
253 DUMPBITS(t)
254 j += (uInt)b & zlib_inflate_mask[i];
255 DUMPBITS(i)
256 i = s->sub.trees.index;
257 t = s->sub.trees.table;
258 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
259 (c == 16 && i < 1))
260 {
261 s->mode = B_BAD;
262 z->msg = (char*)"invalid bit length repeat";
263 r = Z_DATA_ERROR;
264 LEAVE
265 }
266 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
267 do {
268 s->sub.trees.blens[i++] = c;
269 } while (--j);
270 s->sub.trees.index = i;
271 }
272 }
273 s->sub.trees.tb = NULL;
274 {
275 uInt bl, bd;
276 inflate_huft *tl, *td;
277 inflate_codes_statef *c;
278
279 bl = 9; /* must be <= 9 for lookahead assumptions */
280 bd = 6; /* must be <= 9 for lookahead assumptions */
281 t = s->sub.trees.table;
282 t = zlib_inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
283 s->sub.trees.blens, &bl, &bd, &tl, &td,
284 s->hufts, z);
285 if (t != Z_OK)
286 {
287 if (t == (uInt)Z_DATA_ERROR)
288 s->mode = B_BAD;
289 r = t;
290 LEAVE
291 }
292 if ((c = zlib_inflate_codes_new(bl, bd, tl, td, z)) == NULL)
293 {
294 r = Z_MEM_ERROR;
295 LEAVE
296 }
297 s->sub.decode.codes = c;
298 }
299 s->mode = CODES;
300 case CODES:
301 UPDATE
302 if ((r = zlib_inflate_codes(s, z, r)) != Z_STREAM_END)
303 return zlib_inflate_flush(s, z, r);
304 r = Z_OK;
305 zlib_inflate_codes_free(s->sub.decode.codes, z);
306 LOAD
307 if (!s->last)
308 {
309 s->mode = TYPE;
310 break;
311 }
312 s->mode = DRY;
313 case DRY:
314 FLUSH
315 if (s->read != s->write)
316 LEAVE
317 s->mode = B_DONE;
318 case B_DONE:
319 r = Z_STREAM_END;
320 LEAVE
321 case B_BAD:
322 r = Z_DATA_ERROR;
323 LEAVE
324 default:
325 r = Z_STREAM_ERROR;
326 LEAVE
327 }
328}
329
330
331int zlib_inflate_blocks_free(
332 inflate_blocks_statef *s,
333 z_streamp z
334)
335{
336 zlib_inflate_blocks_reset(s, z, NULL);
337 return Z_OK;
338}
339
340
341#if 0
342void zlib_inflate_set_dictionary(
343 inflate_blocks_statef *s,
344 const Byte *d,
345 uInt n
346)
347{
348 memcpy(s->window, d, n);
349 s->read = s->write = s->window + n;
350}
351#endif /* 0 */
352
353
354/* Returns true if inflate is currently at the end of a block generated
355 * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
356 * IN assertion: s != NULL
357 */
358#if 0
359int zlib_inflate_blocks_sync_point(
360 inflate_blocks_statef *s
361)
362{
363 return s->mode == LENS;
364}
365#endif /* 0 */
diff --git a/lib/zlib_inflate/infblock.h b/lib/zlib_inflate/infblock.h
deleted file mode 100644
index ceee60b5107c..000000000000
--- a/lib/zlib_inflate/infblock.h
+++ /dev/null
@@ -1,48 +0,0 @@
1/* infblock.h -- header to use infblock.c
2 * Copyright (C) 1995-1998 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11#ifndef _INFBLOCK_H
12#define _INFBLOCK_H
13
14struct inflate_blocks_state;
15typedef struct inflate_blocks_state inflate_blocks_statef;
16
17extern inflate_blocks_statef * zlib_inflate_blocks_new (
18 z_streamp z,
19 check_func c, /* check function */
20 uInt w); /* window size */
21
22extern int zlib_inflate_blocks (
23 inflate_blocks_statef *,
24 z_streamp ,
25 int); /* initial return code */
26
27extern void zlib_inflate_blocks_reset (
28 inflate_blocks_statef *,
29 z_streamp ,
30 uLong *); /* check value on output */
31
32extern int zlib_inflate_blocks_free (
33 inflate_blocks_statef *,
34 z_streamp);
35
36#if 0
37extern void zlib_inflate_set_dictionary (
38 inflate_blocks_statef *s,
39 const Byte *d, /* dictionary */
40 uInt n); /* dictionary length */
41#endif /* 0 */
42
43#if 0
44extern int zlib_inflate_blocks_sync_point (
45 inflate_blocks_statef *s);
46#endif /* 0 */
47
48#endif /* _INFBLOCK_H */
diff --git a/lib/zlib_inflate/infcodes.c b/lib/zlib_inflate/infcodes.c
deleted file mode 100644
index 07cd7591cbb7..000000000000
--- a/lib/zlib_inflate/infcodes.c
+++ /dev/null
@@ -1,202 +0,0 @@
1/* infcodes.c -- process literals and length/distance pairs
2 * Copyright (C) 1995-1998 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include <linux/zutil.h>
7#include "inftrees.h"
8#include "infblock.h"
9#include "infcodes.h"
10#include "infutil.h"
11#include "inffast.h"
12
13/* simplify the use of the inflate_huft type with some defines */
14#define exop word.what.Exop
15#define bits word.what.Bits
16
17inflate_codes_statef *zlib_inflate_codes_new(
18 uInt bl,
19 uInt bd,
20 inflate_huft *tl,
21 inflate_huft *td, /* need separate declaration for Borland C++ */
22 z_streamp z
23)
24{
25 inflate_codes_statef *c;
26
27 c = &WS(z)->working_state;
28 {
29 c->mode = START;
30 c->lbits = (Byte)bl;
31 c->dbits = (Byte)bd;
32 c->ltree = tl;
33 c->dtree = td;
34 }
35 return c;
36}
37
38
39int zlib_inflate_codes(
40 inflate_blocks_statef *s,
41 z_streamp z,
42 int r
43)
44{
45 uInt j; /* temporary storage */
46 inflate_huft *t; /* temporary pointer */
47 uInt e; /* extra bits or operation */
48 uLong b; /* bit buffer */
49 uInt k; /* bits in bit buffer */
50 Byte *p; /* input data pointer */
51 uInt n; /* bytes available there */
52 Byte *q; /* output window write pointer */
53 uInt m; /* bytes to end of window or read pointer */
54 Byte *f; /* pointer to copy strings from */
55 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */
56
57 /* copy input/output information to locals (UPDATE macro restores) */
58 LOAD
59
60 /* process input and output based on current state */
61 while (1) switch (c->mode)
62 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
63 case START: /* x: set up for LEN */
64#ifndef SLOW
65 if (m >= 258 && n >= 10)
66 {
67 UPDATE
68 r = zlib_inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
69 LOAD
70 if (r != Z_OK)
71 {
72 c->mode = r == Z_STREAM_END ? WASH : BADCODE;
73 break;
74 }
75 }
76#endif /* !SLOW */
77 c->sub.code.need = c->lbits;
78 c->sub.code.tree = c->ltree;
79 c->mode = LEN;
80 case LEN: /* i: get length/literal/eob next */
81 j = c->sub.code.need;
82 NEEDBITS(j)
83 t = c->sub.code.tree + ((uInt)b & zlib_inflate_mask[j]);
84 DUMPBITS(t->bits)
85 e = (uInt)(t->exop);
86 if (e == 0) /* literal */
87 {
88 c->sub.lit = t->base;
89 c->mode = LIT;
90 break;
91 }
92 if (e & 16) /* length */
93 {
94 c->sub.copy.get = e & 15;
95 c->len = t->base;
96 c->mode = LENEXT;
97 break;
98 }
99 if ((e & 64) == 0) /* next table */
100 {
101 c->sub.code.need = e;
102 c->sub.code.tree = t + t->base;
103 break;
104 }
105 if (e & 32) /* end of block */
106 {
107 c->mode = WASH;
108 break;
109 }
110 c->mode = BADCODE; /* invalid code */
111 z->msg = (char*)"invalid literal/length code";
112 r = Z_DATA_ERROR;
113 LEAVE
114 case LENEXT: /* i: getting length extra (have base) */
115 j = c->sub.copy.get;
116 NEEDBITS(j)
117 c->len += (uInt)b & zlib_inflate_mask[j];
118 DUMPBITS(j)
119 c->sub.code.need = c->dbits;
120 c->sub.code.tree = c->dtree;
121 c->mode = DIST;
122 case DIST: /* i: get distance next */
123 j = c->sub.code.need;
124 NEEDBITS(j)
125 t = c->sub.code.tree + ((uInt)b & zlib_inflate_mask[j]);
126 DUMPBITS(t->bits)
127 e = (uInt)(t->exop);
128 if (e & 16) /* distance */
129 {
130 c->sub.copy.get = e & 15;
131 c->sub.copy.dist = t->base;
132 c->mode = DISTEXT;
133 break;
134 }
135 if ((e & 64) == 0) /* next table */
136 {
137 c->sub.code.need = e;
138 c->sub.code.tree = t + t->base;
139 break;
140 }
141 c->mode = BADCODE; /* invalid code */
142 z->msg = (char*)"invalid distance code";
143 r = Z_DATA_ERROR;
144 LEAVE
145 case DISTEXT: /* i: getting distance extra */
146 j = c->sub.copy.get;
147 NEEDBITS(j)
148 c->sub.copy.dist += (uInt)b & zlib_inflate_mask[j];
149 DUMPBITS(j)
150 c->mode = COPY;
151 case COPY: /* o: copying bytes in window, waiting for space */
152 f = q - c->sub.copy.dist;
153 while (f < s->window) /* modulo window size-"while" instead */
154 f += s->end - s->window; /* of "if" handles invalid distances */
155 while (c->len)
156 {
157 NEEDOUT
158 OUTBYTE(*f++)
159 if (f == s->end)
160 f = s->window;
161 c->len--;
162 }
163 c->mode = START;
164 break;
165 case LIT: /* o: got literal, waiting for output space */
166 NEEDOUT
167 OUTBYTE(c->sub.lit)
168 c->mode = START;
169 break;
170 case WASH: /* o: got eob, possibly more output */
171 if (k > 7) /* return unused byte, if any */
172 {
173 k -= 8;
174 n++;
175 p--; /* can always return one */
176 }
177 FLUSH
178 if (s->read != s->write)
179 LEAVE
180 c->mode = END;
181 case END:
182 r = Z_STREAM_END;
183 LEAVE
184 case BADCODE: /* x: got error */
185 r = Z_DATA_ERROR;
186 LEAVE
187 default:
188 r = Z_STREAM_ERROR;
189 LEAVE
190 }
191#ifdef NEED_DUMMY_RETURN
192 return Z_STREAM_ERROR; /* Some dumb compilers complain without this */
193#endif
194}
195
196
197void zlib_inflate_codes_free(
198 inflate_codes_statef *c,
199 z_streamp z
200)
201{
202}
diff --git a/lib/zlib_inflate/infcodes.h b/lib/zlib_inflate/infcodes.h
deleted file mode 100644
index 5cff417523b0..000000000000
--- a/lib/zlib_inflate/infcodes.h
+++ /dev/null
@@ -1,33 +0,0 @@
1/* infcodes.h -- header to use infcodes.c
2 * Copyright (C) 1995-1998 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11#ifndef _INFCODES_H
12#define _INFCODES_H
13
14#include "infblock.h"
15
16struct inflate_codes_state;
17typedef struct inflate_codes_state inflate_codes_statef;
18
19extern inflate_codes_statef *zlib_inflate_codes_new (
20 uInt, uInt,
21 inflate_huft *, inflate_huft *,
22 z_streamp );
23
24extern int zlib_inflate_codes (
25 inflate_blocks_statef *,
26 z_streamp ,
27 int);
28
29extern void zlib_inflate_codes_free (
30 inflate_codes_statef *,
31 z_streamp );
32
33#endif /* _INFCODES_H */
diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c
index 0bd7623fc85a..02a16eacb72d 100644
--- a/lib/zlib_inflate/inffast.c
+++ b/lib/zlib_inflate/inffast.c
@@ -1,176 +1,312 @@
1/* inffast.c -- process literals and length/distance pairs fast 1/* inffast.c -- fast decoding
2 * Copyright (C) 1995-1998 Mark Adler 2 * Copyright (C) 1995-2004 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6#include <linux/zutil.h> 6#include <linux/zutil.h>
7#include "inftrees.h" 7#include "inftrees.h"
8#include "infblock.h" 8#include "inflate.h"
9#include "infcodes.h"
10#include "infutil.h"
11#include "inffast.h" 9#include "inffast.h"
12 10
13struct inflate_codes_state; 11#ifndef ASMINF
14 12
15/* simplify the use of the inflate_huft type with some defines */ 13/* Allow machine dependent optimization for post-increment or pre-increment.
16#define exop word.what.Exop 14 Based on testing to date,
17#define bits word.what.Bits 15 Pre-increment preferred for:
18 16 - PowerPC G3 (Adler)
19/* macros for bit input with no checking and for returning unused bytes */ 17 - MIPS R5000 (Randers-Pehrson)
20#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} 18 Post-increment preferred for:
21#define UNGRAB {c=z->avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;} 19 - none
22 20 No measurable difference:
23/* Called with number of bytes left to write in window at least 258 21 - Pentium III (Anderson)
24 (the maximum string length) and number of input bytes available 22 - M68060 (Nikl)
25 at least ten. The ten bytes are six bytes for the longest length/ 23 */
26 distance pair plus four bytes for overloading the bit buffer. */ 24#ifdef POSTINC
27 25# define OFF 0
28int zlib_inflate_fast( 26# define PUP(a) *(a)++
29 uInt bl, 27#else
30 uInt bd, 28# define OFF 1
31 inflate_huft *tl, 29# define PUP(a) *++(a)
32 inflate_huft *td, /* need separate declaration for Borland C++ */ 30#endif
33 inflate_blocks_statef *s, 31
34 z_streamp z 32/*
35) 33 Decode literal, length, and distance codes and write out the resulting
34 literal and match bytes until either not enough input or output is
35 available, an end-of-block is encountered, or a data error is encountered.
36 When large enough input and output buffers are supplied to inflate(), for
37 example, a 16K input buffer and a 64K output buffer, more than 95% of the
38 inflate execution time is spent in this routine.
39
40 Entry assumptions:
41
42 state->mode == LEN
43 strm->avail_in >= 6
44 strm->avail_out >= 258
45 start >= strm->avail_out
46 state->bits < 8
47
48 On return, state->mode is one of:
49
50 LEN -- ran out of enough output space or enough available input
51 TYPE -- reached end of block code, inflate() to interpret next block
52 BAD -- error in block data
53
54 Notes:
55
56 - The maximum input bits used by a length/distance pair is 15 bits for the
57 length code, 5 bits for the length extra, 15 bits for the distance code,
58 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
59 Therefore if strm->avail_in >= 6, then there is enough input to avoid
60 checking for available input while decoding.
61
62 - The maximum bytes that a single length/distance pair can output is 258
63 bytes, which is the maximum length that can be coded. inflate_fast()
64 requires strm->avail_out >= 258 for each loop to avoid checking for
65 output space.
66 */
67void inflate_fast(strm, start)
68z_streamp strm;
69unsigned start; /* inflate()'s starting value for strm->avail_out */
36{ 70{
37 inflate_huft *t; /* temporary pointer */ 71 struct inflate_state *state;
38 uInt e; /* extra bits or operation */ 72 unsigned char *in; /* local strm->next_in */
39 uLong b; /* bit buffer */ 73 unsigned char *last; /* while in < last, enough input available */
40 uInt k; /* bits in bit buffer */ 74 unsigned char *out; /* local strm->next_out */
41 Byte *p; /* input data pointer */ 75 unsigned char *beg; /* inflate()'s initial strm->next_out */
42 uInt n; /* bytes available there */ 76 unsigned char *end; /* while out < end, enough space available */
43 Byte *q; /* output window write pointer */ 77#ifdef INFLATE_STRICT
44 uInt m; /* bytes to end of window or read pointer */ 78 unsigned dmax; /* maximum distance from zlib header */
45 uInt ml; /* mask for literal/length tree */ 79#endif
46 uInt md; /* mask for distance tree */ 80 unsigned wsize; /* window size or zero if not using window */
47 uInt c; /* bytes to copy */ 81 unsigned whave; /* valid bytes in the window */
48 uInt d; /* distance back to copy from */ 82 unsigned write; /* window write index */
49 Byte *r; /* copy source pointer */ 83 unsigned char *window; /* allocated sliding window, if wsize != 0 */
50 84 unsigned long hold; /* local strm->hold */
51 /* load input, output, bit values */ 85 unsigned bits; /* local strm->bits */
52 LOAD 86 code const *lcode; /* local strm->lencode */
53 87 code const *dcode; /* local strm->distcode */
54 /* initialize masks */ 88 unsigned lmask; /* mask for first level of length codes */
55 ml = zlib_inflate_mask[bl]; 89 unsigned dmask; /* mask for first level of distance codes */
56 md = zlib_inflate_mask[bd]; 90 code this; /* retrieved table entry */
57 91 unsigned op; /* code bits, operation, extra bits, or */
58 /* do until not enough input or output space for fast loop */ 92 /* window position, window bytes to copy */
59 do { /* assume called with m >= 258 && n >= 10 */ 93 unsigned len; /* match length, unused bytes */
60 /* get literal/length code */ 94 unsigned dist; /* match distance */
61 GRABBITS(20) /* max bits for literal/length code */ 95 unsigned char *from; /* where to copy match from */
62 if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) 96
63 { 97 /* copy state to local variables */
64 DUMPBITS(t->bits) 98 state = (struct inflate_state *)strm->state;
65 *q++ = (Byte)t->base; 99 in = strm->next_in - OFF;
66 m--; 100 last = in + (strm->avail_in - 5);
67 continue; 101 out = strm->next_out - OFF;
68 } 102 beg = out - (start - strm->avail_out);
103 end = out + (strm->avail_out - 257);
104#ifdef INFLATE_STRICT
105 dmax = state->dmax;
106#endif
107 wsize = state->wsize;
108 whave = state->whave;
109 write = state->write;
110 window = state->window;
111 hold = state->hold;
112 bits = state->bits;
113 lcode = state->lencode;
114 dcode = state->distcode;
115 lmask = (1U << state->lenbits) - 1;
116 dmask = (1U << state->distbits) - 1;
117
118 /* decode literals and length/distances until end-of-block or not enough
119 input data or output space */
69 do { 120 do {
70 DUMPBITS(t->bits) 121 if (bits < 15) {
71 if (e & 16) 122 hold += (unsigned long)(PUP(in)) << bits;
72 { 123 bits += 8;
73 /* get extra bits for length */ 124 hold += (unsigned long)(PUP(in)) << bits;
74 e &= 15; 125 bits += 8;
75 c = t->base + ((uInt)b & zlib_inflate_mask[e]); 126 }
76 DUMPBITS(e) 127 this = lcode[hold & lmask];
77 128 dolen:
78 /* decode distance base of block to copy */ 129 op = (unsigned)(this.bits);
79 GRABBITS(15); /* max bits for distance code */ 130 hold >>= op;
80 e = (t = td + ((uInt)b & md))->exop; 131 bits -= op;
81 do { 132 op = (unsigned)(this.op);
82 DUMPBITS(t->bits) 133 if (op == 0) { /* literal */
83 if (e & 16) 134 PUP(out) = (unsigned char)(this.val);
84 { 135 }
85 /* get extra bits to add to distance base */ 136 else if (op & 16) { /* length base */
86 e &= 15; 137 len = (unsigned)(this.val);
87 GRABBITS(e) /* get extra bits (up to 13) */ 138 op &= 15; /* number of extra bits */
88 d = t->base + ((uInt)b & zlib_inflate_mask[e]); 139 if (op) {
89 DUMPBITS(e) 140 if (bits < op) {
90 141 hold += (unsigned long)(PUP(in)) << bits;
91 /* do the copy */ 142 bits += 8;
92 m -= c; 143 }
93 r = q - d; 144 len += (unsigned)hold & ((1U << op) - 1);
94 if (r < s->window) /* wrap if needed */ 145 hold >>= op;
95 { 146 bits -= op;
96 do { 147 }
97 r += s->end - s->window; /* force pointer in window */ 148 if (bits < 15) {
98 } while (r < s->window); /* covers invalid distances */ 149 hold += (unsigned long)(PUP(in)) << bits;
99 e = s->end - r; 150 bits += 8;
100 if (c > e) 151 hold += (unsigned long)(PUP(in)) << bits;
101 { 152 bits += 8;
102 c -= e; /* wrapped copy */ 153 }
103 do { 154 this = dcode[hold & dmask];
104 *q++ = *r++; 155 dodist:
105 } while (--e); 156 op = (unsigned)(this.bits);
106 r = s->window; 157 hold >>= op;
107 do { 158 bits -= op;
108 *q++ = *r++; 159 op = (unsigned)(this.op);
109 } while (--c); 160 if (op & 16) { /* distance base */
110 } 161 dist = (unsigned)(this.val);
111 else /* normal copy */ 162 op &= 15; /* number of extra bits */
112 { 163 if (bits < op) {
113 *q++ = *r++; c--; 164 hold += (unsigned long)(PUP(in)) << bits;
114 *q++ = *r++; c--; 165 bits += 8;
115 do { 166 if (bits < op) {
116 *q++ = *r++; 167 hold += (unsigned long)(PUP(in)) << bits;
117 } while (--c); 168 bits += 8;
118 } 169 }
170 }
171 dist += (unsigned)hold & ((1U << op) - 1);
172#ifdef INFLATE_STRICT
173 if (dist > dmax) {
174 strm->msg = (char *)"invalid distance too far back";
175 state->mode = BAD;
176 break;
177 }
178#endif
179 hold >>= op;
180 bits -= op;
181 op = (unsigned)(out - beg); /* max distance in output */
182 if (dist > op) { /* see if copy from window */
183 op = dist - op; /* distance back in window */
184 if (op > whave) {
185 strm->msg = (char *)"invalid distance too far back";
186 state->mode = BAD;
187 break;
188 }
189 from = window - OFF;
190 if (write == 0) { /* very common case */
191 from += wsize - op;
192 if (op < len) { /* some from window */
193 len -= op;
194 do {
195 PUP(out) = PUP(from);
196 } while (--op);
197 from = out - dist; /* rest from output */
198 }
199 }
200 else if (write < op) { /* wrap around window */
201 from += wsize + write - op;
202 op -= write;
203 if (op < len) { /* some from end of window */
204 len -= op;
205 do {
206 PUP(out) = PUP(from);
207 } while (--op);
208 from = window - OFF;
209 if (write < len) { /* some from start of window */
210 op = write;
211 len -= op;
212 do {
213 PUP(out) = PUP(from);
214 } while (--op);
215 from = out - dist; /* rest from output */
216 }
217 }
218 }
219 else { /* contiguous in window */
220 from += write - op;
221 if (op < len) { /* some from window */
222 len -= op;
223 do {
224 PUP(out) = PUP(from);
225 } while (--op);
226 from = out - dist; /* rest from output */
227 }
228 }
229 while (len > 2) {
230 PUP(out) = PUP(from);
231 PUP(out) = PUP(from);
232 PUP(out) = PUP(from);
233 len -= 3;
234 }
235 if (len) {
236 PUP(out) = PUP(from);
237 if (len > 1)
238 PUP(out) = PUP(from);
239 }
240 }
241 else {
242 from = out - dist; /* copy direct from output */
243 do { /* minimum length is three */
244 PUP(out) = PUP(from);
245 PUP(out) = PUP(from);
246 PUP(out) = PUP(from);
247 len -= 3;
248 } while (len > 2);
249 if (len) {
250 PUP(out) = PUP(from);
251 if (len > 1)
252 PUP(out) = PUP(from);
253 }
254 }
255 }
256 else if ((op & 64) == 0) { /* 2nd level distance code */
257 this = dcode[this.val + (hold & ((1U << op) - 1))];
258 goto dodist;
119 } 259 }
120 else /* normal copy */ 260 else {
121 { 261 strm->msg = (char *)"invalid distance code";
122 *q++ = *r++; c--; 262 state->mode = BAD;
123 *q++ = *r++; c--; 263 break;
124 do {
125 *q++ = *r++;
126 } while (--c);
127 } 264 }
265 }
266 else if ((op & 64) == 0) { /* 2nd level length code */
267 this = lcode[this.val + (hold & ((1U << op) - 1))];
268 goto dolen;
269 }
270 else if (op & 32) { /* end-of-block */
271 state->mode = TYPE;
128 break; 272 break;
129 }
130 else if ((e & 64) == 0)
131 {
132 t += t->base;
133 e = (t += ((uInt)b & zlib_inflate_mask[e]))->exop;
134 }
135 else
136 {
137 z->msg = (char*)"invalid distance code";
138 UNGRAB
139 UPDATE
140 return Z_DATA_ERROR;
141 }
142 } while (1);
143 break;
144 }
145 if ((e & 64) == 0)
146 {
147 t += t->base;
148 if ((e = (t += ((uInt)b & zlib_inflate_mask[e]))->exop) == 0)
149 {
150 DUMPBITS(t->bits)
151 *q++ = (Byte)t->base;
152 m--;
153 break;
154 } 273 }
155 } 274 else {
156 else if (e & 32) 275 strm->msg = (char *)"invalid literal/length code";
157 { 276 state->mode = BAD;
158 UNGRAB 277 break;
159 UPDATE 278 }
160 return Z_STREAM_END; 279 } while (in < last && out < end);
161 } 280
162 else 281 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
163 { 282 len = bits >> 3;
164 z->msg = (char*)"invalid literal/length code"; 283 in -= len;
165 UNGRAB 284 bits -= len << 3;
166 UPDATE 285 hold &= (1U << bits) - 1;
167 return Z_DATA_ERROR; 286
168 } 287 /* update state and return */
169 } while (1); 288 strm->next_in = in + OFF;
170 } while (m >= 258 && n >= 10); 289 strm->next_out = out + OFF;
171 290 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
172 /* not enough input or output--restore pointers and return */ 291 strm->avail_out = (unsigned)(out < end ?
173 UNGRAB 292 257 + (end - out) : 257 - (out - end));
174 UPDATE 293 state->hold = hold;
175 return Z_OK; 294 state->bits = bits;
295 return;
176} 296}
297
298/*
299 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
300 - Using bit fields for code structure
301 - Different op definition to avoid & for extra bits (do & for table bits)
302 - Three separate decoding do-loops for direct, window, and write == 0
303 - Special case for distance > 1 copies to do overlapped load and store copy
304 - Explicit branch predictions (based on measured branch probabilities)
305 - Deferring match copy and interspersed it with decoding subsequent codes
306 - Swapping literal/length else
307 - Swapping window/direct else
308 - Larger unrolled copy loops (three is about right)
309 - Moving len -= 3 statement into middle of loop
310 */
311
312#endif /* !ASMINF */
diff --git a/lib/zlib_inflate/inffast.h b/lib/zlib_inflate/inffast.h
index fc720f0fa7f5..40315d9fddc4 100644
--- a/lib/zlib_inflate/inffast.h
+++ b/lib/zlib_inflate/inffast.h
@@ -1,6 +1,6 @@
1/* inffast.h -- header to use inffast.c 1/* inffast.h -- header to use inffast.c
2 * Copyright (C) 1995-1998 Mark Adler 2 * Copyright (C) 1995-2003 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6/* WARNING: this file should *not* be used by applications. It is 6/* WARNING: this file should *not* be used by applications. It is
@@ -8,10 +8,4 @@
8 subject to change. Applications should only use zlib.h. 8 subject to change. Applications should only use zlib.h.
9 */ 9 */
10 10
11extern int zlib_inflate_fast ( 11void inflate_fast (z_streamp strm, unsigned start);
12 uInt,
13 uInt,
14 inflate_huft *,
15 inflate_huft *,
16 inflate_blocks_statef *,
17 z_streamp );
diff --git a/lib/zlib_inflate/inffixed.h b/lib/zlib_inflate/inffixed.h
new file mode 100644
index 000000000000..75ed4b5978de
--- /dev/null
+++ b/lib/zlib_inflate/inffixed.h
@@ -0,0 +1,94 @@
1 /* inffixed.h -- table for decoding fixed codes
2 * Generated automatically by makefixed().
3 */
4
5 /* WARNING: this file should *not* be used by applications. It
6 is part of the implementation of the compression library and
7 is subject to change. Applications should only use zlib.h.
8 */
9
10 static const code lenfix[512] = {
11 {96,7,0},{0,8,80},{0,8,16},{20,8,115},{18,7,31},{0,8,112},{0,8,48},
12 {0,9,192},{16,7,10},{0,8,96},{0,8,32},{0,9,160},{0,8,0},{0,8,128},
13 {0,8,64},{0,9,224},{16,7,6},{0,8,88},{0,8,24},{0,9,144},{19,7,59},
14 {0,8,120},{0,8,56},{0,9,208},{17,7,17},{0,8,104},{0,8,40},{0,9,176},
15 {0,8,8},{0,8,136},{0,8,72},{0,9,240},{16,7,4},{0,8,84},{0,8,20},
16 {21,8,227},{19,7,43},{0,8,116},{0,8,52},{0,9,200},{17,7,13},{0,8,100},
17 {0,8,36},{0,9,168},{0,8,4},{0,8,132},{0,8,68},{0,9,232},{16,7,8},
18 {0,8,92},{0,8,28},{0,9,152},{20,7,83},{0,8,124},{0,8,60},{0,9,216},
19 {18,7,23},{0,8,108},{0,8,44},{0,9,184},{0,8,12},{0,8,140},{0,8,76},
20 {0,9,248},{16,7,3},{0,8,82},{0,8,18},{21,8,163},{19,7,35},{0,8,114},
21 {0,8,50},{0,9,196},{17,7,11},{0,8,98},{0,8,34},{0,9,164},{0,8,2},
22 {0,8,130},{0,8,66},{0,9,228},{16,7,7},{0,8,90},{0,8,26},{0,9,148},
23 {20,7,67},{0,8,122},{0,8,58},{0,9,212},{18,7,19},{0,8,106},{0,8,42},
24 {0,9,180},{0,8,10},{0,8,138},{0,8,74},{0,9,244},{16,7,5},{0,8,86},
25 {0,8,22},{64,8,0},{19,7,51},{0,8,118},{0,8,54},{0,9,204},{17,7,15},
26 {0,8,102},{0,8,38},{0,9,172},{0,8,6},{0,8,134},{0,8,70},{0,9,236},
27 {16,7,9},{0,8,94},{0,8,30},{0,9,156},{20,7,99},{0,8,126},{0,8,62},
28 {0,9,220},{18,7,27},{0,8,110},{0,8,46},{0,9,188},{0,8,14},{0,8,142},
29 {0,8,78},{0,9,252},{96,7,0},{0,8,81},{0,8,17},{21,8,131},{18,7,31},
30 {0,8,113},{0,8,49},{0,9,194},{16,7,10},{0,8,97},{0,8,33},{0,9,162},
31 {0,8,1},{0,8,129},{0,8,65},{0,9,226},{16,7,6},{0,8,89},{0,8,25},
32 {0,9,146},{19,7,59},{0,8,121},{0,8,57},{0,9,210},{17,7,17},{0,8,105},
33 {0,8,41},{0,9,178},{0,8,9},{0,8,137},{0,8,73},{0,9,242},{16,7,4},
34 {0,8,85},{0,8,21},{16,8,258},{19,7,43},{0,8,117},{0,8,53},{0,9,202},
35 {17,7,13},{0,8,101},{0,8,37},{0,9,170},{0,8,5},{0,8,133},{0,8,69},
36 {0,9,234},{16,7,8},{0,8,93},{0,8,29},{0,9,154},{20,7,83},{0,8,125},
37 {0,8,61},{0,9,218},{18,7,23},{0,8,109},{0,8,45},{0,9,186},{0,8,13},
38 {0,8,141},{0,8,77},{0,9,250},{16,7,3},{0,8,83},{0,8,19},{21,8,195},
39 {19,7,35},{0,8,115},{0,8,51},{0,9,198},{17,7,11},{0,8,99},{0,8,35},
40 {0,9,166},{0,8,3},{0,8,131},{0,8,67},{0,9,230},{16,7,7},{0,8,91},
41 {0,8,27},{0,9,150},{20,7,67},{0,8,123},{0,8,59},{0,9,214},{18,7,19},
42 {0,8,107},{0,8,43},{0,9,182},{0,8,11},{0,8,139},{0,8,75},{0,9,246},
43 {16,7,5},{0,8,87},{0,8,23},{64,8,0},{19,7,51},{0,8,119},{0,8,55},
44 {0,9,206},{17,7,15},{0,8,103},{0,8,39},{0,9,174},{0,8,7},{0,8,135},
45 {0,8,71},{0,9,238},{16,7,9},{0,8,95},{0,8,31},{0,9,158},{20,7,99},
46 {0,8,127},{0,8,63},{0,9,222},{18,7,27},{0,8,111},{0,8,47},{0,9,190},
47 {0,8,15},{0,8,143},{0,8,79},{0,9,254},{96,7,0},{0,8,80},{0,8,16},
48 {20,8,115},{18,7,31},{0,8,112},{0,8,48},{0,9,193},{16,7,10},{0,8,96},
49 {0,8,32},{0,9,161},{0,8,0},{0,8,128},{0,8,64},{0,9,225},{16,7,6},
50 {0,8,88},{0,8,24},{0,9,145},{19,7,59},{0,8,120},{0,8,56},{0,9,209},
51 {17,7,17},{0,8,104},{0,8,40},{0,9,177},{0,8,8},{0,8,136},{0,8,72},
52 {0,9,241},{16,7,4},{0,8,84},{0,8,20},{21,8,227},{19,7,43},{0,8,116},
53 {0,8,52},{0,9,201},{17,7,13},{0,8,100},{0,8,36},{0,9,169},{0,8,4},
54 {0,8,132},{0,8,68},{0,9,233},{16,7,8},{0,8,92},{0,8,28},{0,9,153},
55 {20,7,83},{0,8,124},{0,8,60},{0,9,217},{18,7,23},{0,8,108},{0,8,44},
56 {0,9,185},{0,8,12},{0,8,140},{0,8,76},{0,9,249},{16,7,3},{0,8,82},
57 {0,8,18},{21,8,163},{19,7,35},{0,8,114},{0,8,50},{0,9,197},{17,7,11},
58 {0,8,98},{0,8,34},{0,9,165},{0,8,2},{0,8,130},{0,8,66},{0,9,229},
59 {16,7,7},{0,8,90},{0,8,26},{0,9,149},{20,7,67},{0,8,122},{0,8,58},
60 {0,9,213},{18,7,19},{0,8,106},{0,8,42},{0,9,181},{0,8,10},{0,8,138},
61 {0,8,74},{0,9,245},{16,7,5},{0,8,86},{0,8,22},{64,8,0},{19,7,51},
62 {0,8,118},{0,8,54},{0,9,205},{17,7,15},{0,8,102},{0,8,38},{0,9,173},
63 {0,8,6},{0,8,134},{0,8,70},{0,9,237},{16,7,9},{0,8,94},{0,8,30},
64 {0,9,157},{20,7,99},{0,8,126},{0,8,62},{0,9,221},{18,7,27},{0,8,110},
65 {0,8,46},{0,9,189},{0,8,14},{0,8,142},{0,8,78},{0,9,253},{96,7,0},
66 {0,8,81},{0,8,17},{21,8,131},{18,7,31},{0,8,113},{0,8,49},{0,9,195},
67 {16,7,10},{0,8,97},{0,8,33},{0,9,163},{0,8,1},{0,8,129},{0,8,65},
68 {0,9,227},{16,7,6},{0,8,89},{0,8,25},{0,9,147},{19,7,59},{0,8,121},
69 {0,8,57},{0,9,211},{17,7,17},{0,8,105},{0,8,41},{0,9,179},{0,8,9},
70 {0,8,137},{0,8,73},{0,9,243},{16,7,4},{0,8,85},{0,8,21},{16,8,258},
71 {19,7,43},{0,8,117},{0,8,53},{0,9,203},{17,7,13},{0,8,101},{0,8,37},
72 {0,9,171},{0,8,5},{0,8,133},{0,8,69},{0,9,235},{16,7,8},{0,8,93},
73 {0,8,29},{0,9,155},{20,7,83},{0,8,125},{0,8,61},{0,9,219},{18,7,23},
74 {0,8,109},{0,8,45},{0,9,187},{0,8,13},{0,8,141},{0,8,77},{0,9,251},
75 {16,7,3},{0,8,83},{0,8,19},{21,8,195},{19,7,35},{0,8,115},{0,8,51},
76 {0,9,199},{17,7,11},{0,8,99},{0,8,35},{0,9,167},{0,8,3},{0,8,131},
77 {0,8,67},{0,9,231},{16,7,7},{0,8,91},{0,8,27},{0,9,151},{20,7,67},
78 {0,8,123},{0,8,59},{0,9,215},{18,7,19},{0,8,107},{0,8,43},{0,9,183},
79 {0,8,11},{0,8,139},{0,8,75},{0,9,247},{16,7,5},{0,8,87},{0,8,23},
80 {64,8,0},{19,7,51},{0,8,119},{0,8,55},{0,9,207},{17,7,15},{0,8,103},
81 {0,8,39},{0,9,175},{0,8,7},{0,8,135},{0,8,71},{0,9,239},{16,7,9},
82 {0,8,95},{0,8,31},{0,9,159},{20,7,99},{0,8,127},{0,8,63},{0,9,223},
83 {18,7,27},{0,8,111},{0,8,47},{0,9,191},{0,8,15},{0,8,143},{0,8,79},
84 {0,9,255}
85 };
86
87 static const code distfix[32] = {
88 {16,5,1},{23,5,257},{19,5,17},{27,5,4097},{17,5,5},{25,5,1025},
89 {21,5,65},{29,5,16385},{16,5,3},{24,5,513},{20,5,33},{28,5,8193},
90 {18,5,9},{26,5,2049},{22,5,129},{64,5,0},{16,5,2},{23,5,385},
91 {19,5,25},{27,5,6145},{17,5,7},{25,5,1537},{21,5,97},{29,5,24577},
92 {16,5,4},{24,5,769},{20,5,49},{28,5,12289},{18,5,13},{26,5,3073},
93 {22,5,193},{64,5,0}
94 };
diff --git a/lib/zlib_inflate/inflate.c b/lib/zlib_inflate/inflate.c
index 31b9e9054bf7..7f922dccf1a5 100644
--- a/lib/zlib_inflate/inflate.c
+++ b/lib/zlib_inflate/inflate.c
@@ -1,89 +1,148 @@
1/* inflate.c -- zlib interface to inflate modules 1/* inflate.c -- zlib decompression
2 * Copyright (C) 1995-1998 Mark Adler 2 * Copyright (C) 1995-2005 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 *
5 * Based on zlib 1.2.3 but modified for the Linux Kernel by
6 * Richard Purdie <richard@openedhand.com>
7 *
8 * Changes mainly for static instead of dynamic memory allocation
9 *
4 */ 10 */
5 11
6#include <linux/zutil.h> 12#include <linux/zutil.h>
7#include "infblock.h" 13#include "inftrees.h"
14#include "inflate.h"
15#include "inffast.h"
8#include "infutil.h" 16#include "infutil.h"
9 17
10int zlib_inflate_workspacesize(void) 18int zlib_inflate_workspacesize(void)
11{ 19{
12 return sizeof(struct inflate_workspace); 20 return sizeof(struct inflate_workspace);
13} 21}
14 22
23int zlib_inflateReset(z_streamp strm)
24{
25 struct inflate_state *state;
26
27 if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;
28 state = (struct inflate_state *)strm->state;
29 strm->total_in = strm->total_out = state->total = 0;
30 strm->msg = NULL;
31 strm->adler = 1; /* to support ill-conceived Java test suite */
32 state->mode = HEAD;
33 state->last = 0;
34 state->havedict = 0;
35 state->dmax = 32768U;
36 state->hold = 0;
37 state->bits = 0;
38 state->lencode = state->distcode = state->next = state->codes;
15 39
16int zlib_inflateReset( 40 /* Initialise Window */
17 z_streamp z 41 state->wsize = 1U << state->wbits;
18) 42 state->write = 0;
43 state->whave = 0;
44
45 return Z_OK;
46}
47
48#if 0
49int zlib_inflatePrime(z_streamp strm, int bits, int value)
19{ 50{
20 if (z == NULL || z->state == NULL || z->workspace == NULL) 51 struct inflate_state *state;
21 return Z_STREAM_ERROR; 52
22 z->total_in = z->total_out = 0; 53 if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;
23 z->msg = NULL; 54 state = (struct inflate_state *)strm->state;
24 z->state->mode = z->state->nowrap ? BLOCKS : METHOD; 55 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
25 zlib_inflate_blocks_reset(z->state->blocks, z, NULL); 56 value &= (1L << bits) - 1;
26 return Z_OK; 57 state->hold += value << state->bits;
58 state->bits += bits;
59 return Z_OK;
27} 60}
61#endif
62
63int zlib_inflateInit2(z_streamp strm, int windowBits)
64{
65 struct inflate_state *state;
66
67 if (strm == NULL) return Z_STREAM_ERROR;
68 strm->msg = NULL; /* in case we return an error */
69
70 state = &WS(strm)->inflate_state;
71 strm->state = (struct internal_state *)state;
72
73 if (windowBits < 0) {
74 state->wrap = 0;
75 windowBits = -windowBits;
76 }
77 else {
78 state->wrap = (windowBits >> 4) + 1;
79 }
80 if (windowBits < 8 || windowBits > 15) {
81 return Z_STREAM_ERROR;
82 }
83 state->wbits = (unsigned)windowBits;
84 state->window = &WS(strm)->working_window[0];
28 85
86 return zlib_inflateReset(strm);
87}
29 88
30int zlib_inflateEnd( 89/*
31 z_streamp z 90 Return state with length and distance decoding tables and index sizes set to
32) 91 fixed code decoding. This returns fixed tables from inffixed.h.
92 */
93static void zlib_fixedtables(struct inflate_state *state)
33{ 94{
34 if (z == NULL || z->state == NULL || z->workspace == NULL) 95# include "inffixed.h"
35 return Z_STREAM_ERROR; 96 state->lencode = lenfix;
36 if (z->state->blocks != NULL) 97 state->lenbits = 9;
37 zlib_inflate_blocks_free(z->state->blocks, z); 98 state->distcode = distfix;
38 z->state = NULL; 99 state->distbits = 5;
39 return Z_OK;
40} 100}
41 101
42 102
43int zlib_inflateInit2_( 103/*
44 z_streamp z, 104 Update the window with the last wsize (normally 32K) bytes written before
45 int w, 105 returning. This is only called when a window is already in use, or when
46 const char *version, 106 output has been written during this inflate call, but the end of the deflate
47 int stream_size 107 stream has not been reached yet. It is also called to window dictionary data
48) 108 when a dictionary is loaded.
109
110 Providing output buffers larger than 32K to inflate() should provide a speed
111 advantage, since only the last 32K of output is copied to the sliding window
112 upon return from inflate(), and since all distances after the first 32K of
113 output will fall in the output data, making match copies simpler and faster.
114 The advantage may be dependent on the size of the processor's data caches.
115 */
116static void zlib_updatewindow(z_streamp strm, unsigned out)
49{ 117{
50 if (version == NULL || version[0] != ZLIB_VERSION[0] || 118 struct inflate_state *state;
51 stream_size != sizeof(z_stream) || z->workspace == NULL) 119 unsigned copy, dist;
52 return Z_VERSION_ERROR; 120
53 121 state = (struct inflate_state *)strm->state;
54 /* initialize state */ 122
55 z->msg = NULL; 123 /* copy state->wsize or less output bytes into the circular window */
56 z->state = &WS(z)->internal_state; 124 copy = out - strm->avail_out;
57 z->state->blocks = NULL; 125 if (copy >= state->wsize) {
58 126 memcpy(state->window, strm->next_out - state->wsize, state->wsize);
59 /* handle undocumented nowrap option (no zlib header or check) */ 127 state->write = 0;
60 z->state->nowrap = 0; 128 state->whave = state->wsize;
61 if (w < 0) 129 }
62 { 130 else {
63 w = - w; 131 dist = state->wsize - state->write;
64 z->state->nowrap = 1; 132 if (dist > copy) dist = copy;
65 } 133 memcpy(state->window + state->write, strm->next_out - copy, dist);
66 134 copy -= dist;
67 /* set window size */ 135 if (copy) {
68 if (w < 8 || w > 15) 136 memcpy(state->window, strm->next_out - copy, copy);
69 { 137 state->write = copy;
70 zlib_inflateEnd(z); 138 state->whave = state->wsize;
71 return Z_STREAM_ERROR; 139 }
72 } 140 else {
73 z->state->wbits = (uInt)w; 141 state->write += dist;
74 142 if (state->write == state->wsize) state->write = 0;
75 /* create inflate_blocks state */ 143 if (state->whave < state->wsize) state->whave += dist;
76 if ((z->state->blocks = 144 }
77 zlib_inflate_blocks_new(z, z->state->nowrap ? NULL : zlib_adler32, (uInt)1 << w)) 145 }
78 == NULL)
79 {
80 zlib_inflateEnd(z);
81 return Z_MEM_ERROR;
82 }
83
84 /* reset state */
85 zlib_inflateReset(z);
86 return Z_OK;
87} 146}
88 147
89 148
@@ -91,157 +150,764 @@ int zlib_inflateInit2_(
91 * At the end of a Deflate-compressed PPP packet, we expect to have seen 150 * At the end of a Deflate-compressed PPP packet, we expect to have seen
92 * a `stored' block type value but not the (zero) length bytes. 151 * a `stored' block type value but not the (zero) length bytes.
93 */ 152 */
94static int zlib_inflate_packet_flush(inflate_blocks_statef *s) 153/*
154 Returns true if inflate is currently at the end of a block generated by
155 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
156 implementation to provide an additional safety check. PPP uses
157 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
158 block. When decompressing, PPP checks that at the end of input packet,
159 inflate is waiting for these length bytes.
160 */
161static int zlib_inflateSyncPacket(z_streamp strm)
95{ 162{
96 if (s->mode != LENS) 163 struct inflate_state *state;
97 return Z_DATA_ERROR; 164
98 s->mode = TYPE; 165 if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;
166 state = (struct inflate_state *)strm->state;
167
168 if (state->mode == STORED && state->bits == 0) {
169 state->mode = TYPE;
170 return Z_OK;
171 }
172 return Z_DATA_ERROR;
173}
174
175/* Macros for inflate(): */
176
177/* check function to use adler32() for zlib or crc32() for gzip */
178#define UPDATE(check, buf, len) zlib_adler32(check, buf, len)
179
180/* Load registers with state in inflate() for speed */
181#define LOAD() \
182 do { \
183 put = strm->next_out; \
184 left = strm->avail_out; \
185 next = strm->next_in; \
186 have = strm->avail_in; \
187 hold = state->hold; \
188 bits = state->bits; \
189 } while (0)
190
191/* Restore state from registers in inflate() */
192#define RESTORE() \
193 do { \
194 strm->next_out = put; \
195 strm->avail_out = left; \
196 strm->next_in = next; \
197 strm->avail_in = have; \
198 state->hold = hold; \
199 state->bits = bits; \
200 } while (0)
201
202/* Clear the input bit accumulator */
203#define INITBITS() \
204 do { \
205 hold = 0; \
206 bits = 0; \
207 } while (0)
208
209/* Get a byte of input into the bit accumulator, or return from inflate()
210 if there is no input available. */
211#define PULLBYTE() \
212 do { \
213 if (have == 0) goto inf_leave; \
214 have--; \
215 hold += (unsigned long)(*next++) << bits; \
216 bits += 8; \
217 } while (0)
218
219/* Assure that there are at least n bits in the bit accumulator. If there is
220 not enough available input to do that, then return from inflate(). */
221#define NEEDBITS(n) \
222 do { \
223 while (bits < (unsigned)(n)) \
224 PULLBYTE(); \
225 } while (0)
226
227/* Return the low n bits of the bit accumulator (n < 16) */
228#define BITS(n) \
229 ((unsigned)hold & ((1U << (n)) - 1))
230
231/* Remove n bits from the bit accumulator */
232#define DROPBITS(n) \
233 do { \
234 hold >>= (n); \
235 bits -= (unsigned)(n); \
236 } while (0)
237
238/* Remove zero to seven bits as needed to go to a byte boundary */
239#define BYTEBITS() \
240 do { \
241 hold >>= bits & 7; \
242 bits -= bits & 7; \
243 } while (0)
244
245/* Reverse the bytes in a 32-bit value */
246#define REVERSE(q) \
247 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
248 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
249
250/*
251 inflate() uses a state machine to process as much input data and generate as
252 much output data as possible before returning. The state machine is
253 structured roughly as follows:
254
255 for (;;) switch (state) {
256 ...
257 case STATEn:
258 if (not enough input data or output space to make progress)
259 return;
260 ... make progress ...
261 state = STATEm;
262 break;
263 ...
264 }
265
266 so when inflate() is called again, the same case is attempted again, and
267 if the appropriate resources are provided, the machine proceeds to the
268 next state. The NEEDBITS() macro is usually the way the state evaluates
269 whether it can proceed or should return. NEEDBITS() does the return if
270 the requested bits are not available. The typical use of the BITS macros
271 is:
272
273 NEEDBITS(n);
274 ... do something with BITS(n) ...
275 DROPBITS(n);
276
277 where NEEDBITS(n) either returns from inflate() if there isn't enough
278 input left to load n bits into the accumulator, or it continues. BITS(n)
279 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
280 the low n bits off the accumulator. INITBITS() clears the accumulator
281 and sets the number of available bits to zero. BYTEBITS() discards just
282 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
283 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
284
285 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
286 if there is no input available. The decoding of variable length codes uses
287 PULLBYTE() directly in order to pull just enough bytes to decode the next
288 code, and no more.
289
290 Some states loop until they get enough input, making sure that enough
291 state information is maintained to continue the loop where it left off
292 if NEEDBITS() returns in the loop. For example, want, need, and keep
293 would all have to actually be part of the saved state in case NEEDBITS()
294 returns:
295
296 case STATEw:
297 while (want < need) {
298 NEEDBITS(n);
299 keep[want++] = BITS(n);
300 DROPBITS(n);
301 }
302 state = STATEx;
303 case STATEx:
304
305 As shown above, if the next state is also the next case, then the break
306 is omitted.
307
308 A state may also return if there is not enough output space available to
309 complete that state. Those states are copying stored data, writing a
310 literal byte, and copying a matching string.
311
312 When returning, a "goto inf_leave" is used to update the total counters,
313 update the check value, and determine whether any progress has been made
314 during that inflate() call in order to return the proper return code.
315 Progress is defined as a change in either strm->avail_in or strm->avail_out.
316 When there is a window, goto inf_leave will update the window with the last
317 output written. If a goto inf_leave occurs in the middle of decompression
318 and there is no window currently, goto inf_leave will create one and copy
319 output to the window for the next call of inflate().
320
321 In this implementation, the flush parameter of inflate() only affects the
322 return code (per zlib.h). inflate() always writes as much as possible to
323 strm->next_out, given the space available and the provided input--the effect
324 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
325 the allocation of and copying into a sliding window until necessary, which
326 provides the effect documented in zlib.h for Z_FINISH when the entire input
327 stream available. So the only thing the flush parameter actually does is:
328 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
329 will return Z_BUF_ERROR if it has not reached the end of the stream.
330 */
331
332int zlib_inflate(z_streamp strm, int flush)
333{
334 struct inflate_state *state;
335 unsigned char *next; /* next input */
336 unsigned char *put; /* next output */
337 unsigned have, left; /* available input and output */
338 unsigned long hold; /* bit buffer */
339 unsigned bits; /* bits in bit buffer */
340 unsigned in, out; /* save starting available input and output */
341 unsigned copy; /* number of stored or match bytes to copy */
342 unsigned char *from; /* where to copy match bytes from */
343 code this; /* current decoding table entry */
344 code last; /* parent table entry */
345 unsigned len; /* length to copy for repeats, bits to drop */
346 int ret; /* return code */
347 static const unsigned short order[19] = /* permutation of code lengths */
348 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
349
350 if (strm == NULL || strm->state == NULL || strm->next_out == NULL ||
351 (strm->next_in == NULL && strm->avail_in != 0))
352 return Z_STREAM_ERROR;
353
354 state = (struct inflate_state *)strm->state;
355
356 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
357 LOAD();
358 in = have;
359 out = left;
360 ret = Z_OK;
361 for (;;)
362 switch (state->mode) {
363 case HEAD:
364 if (state->wrap == 0) {
365 state->mode = TYPEDO;
366 break;
367 }
368 NEEDBITS(16);
369 if (
370 ((BITS(8) << 8) + (hold >> 8)) % 31) {
371 strm->msg = (char *)"incorrect header check";
372 state->mode = BAD;
373 break;
374 }
375 if (BITS(4) != Z_DEFLATED) {
376 strm->msg = (char *)"unknown compression method";
377 state->mode = BAD;
378 break;
379 }
380 DROPBITS(4);
381 len = BITS(4) + 8;
382 if (len > state->wbits) {
383 strm->msg = (char *)"invalid window size";
384 state->mode = BAD;
385 break;
386 }
387 state->dmax = 1U << len;
388 strm->adler = state->check = zlib_adler32(0L, NULL, 0);
389 state->mode = hold & 0x200 ? DICTID : TYPE;
390 INITBITS();
391 break;
392 case DICTID:
393 NEEDBITS(32);
394 strm->adler = state->check = REVERSE(hold);
395 INITBITS();
396 state->mode = DICT;
397 case DICT:
398 if (state->havedict == 0) {
399 RESTORE();
400 return Z_NEED_DICT;
401 }
402 strm->adler = state->check = zlib_adler32(0L, NULL, 0);
403 state->mode = TYPE;
404 case TYPE:
405 if (flush == Z_BLOCK) goto inf_leave;
406 case TYPEDO:
407 if (state->last) {
408 BYTEBITS();
409 state->mode = CHECK;
410 break;
411 }
412 NEEDBITS(3);
413 state->last = BITS(1);
414 DROPBITS(1);
415 switch (BITS(2)) {
416 case 0: /* stored block */
417 state->mode = STORED;
418 break;
419 case 1: /* fixed block */
420 zlib_fixedtables(state);
421 state->mode = LEN; /* decode codes */
422 break;
423 case 2: /* dynamic block */
424 state->mode = TABLE;
425 break;
426 case 3:
427 strm->msg = (char *)"invalid block type";
428 state->mode = BAD;
429 }
430 DROPBITS(2);
431 break;
432 case STORED:
433 BYTEBITS(); /* go to byte boundary */
434 NEEDBITS(32);
435 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
436 strm->msg = (char *)"invalid stored block lengths";
437 state->mode = BAD;
438 break;
439 }
440 state->length = (unsigned)hold & 0xffff;
441 INITBITS();
442 state->mode = COPY;
443 case COPY:
444 copy = state->length;
445 if (copy) {
446 if (copy > have) copy = have;
447 if (copy > left) copy = left;
448 if (copy == 0) goto inf_leave;
449 memcpy(put, next, copy);
450 have -= copy;
451 next += copy;
452 left -= copy;
453 put += copy;
454 state->length -= copy;
455 break;
456 }
457 state->mode = TYPE;
458 break;
459 case TABLE:
460 NEEDBITS(14);
461 state->nlen = BITS(5) + 257;
462 DROPBITS(5);
463 state->ndist = BITS(5) + 1;
464 DROPBITS(5);
465 state->ncode = BITS(4) + 4;
466 DROPBITS(4);
467#ifndef PKZIP_BUG_WORKAROUND
468 if (state->nlen > 286 || state->ndist > 30) {
469 strm->msg = (char *)"too many length or distance symbols";
470 state->mode = BAD;
471 break;
472 }
473#endif
474 state->have = 0;
475 state->mode = LENLENS;
476 case LENLENS:
477 while (state->have < state->ncode) {
478 NEEDBITS(3);
479 state->lens[order[state->have++]] = (unsigned short)BITS(3);
480 DROPBITS(3);
481 }
482 while (state->have < 19)
483 state->lens[order[state->have++]] = 0;
484 state->next = state->codes;
485 state->lencode = (code const *)(state->next);
486 state->lenbits = 7;
487 ret = zlib_inflate_table(CODES, state->lens, 19, &(state->next),
488 &(state->lenbits), state->work);
489 if (ret) {
490 strm->msg = (char *)"invalid code lengths set";
491 state->mode = BAD;
492 break;
493 }
494 state->have = 0;
495 state->mode = CODELENS;
496 case CODELENS:
497 while (state->have < state->nlen + state->ndist) {
498 for (;;) {
499 this = state->lencode[BITS(state->lenbits)];
500 if ((unsigned)(this.bits) <= bits) break;
501 PULLBYTE();
502 }
503 if (this.val < 16) {
504 NEEDBITS(this.bits);
505 DROPBITS(this.bits);
506 state->lens[state->have++] = this.val;
507 }
508 else {
509 if (this.val == 16) {
510 NEEDBITS(this.bits + 2);
511 DROPBITS(this.bits);
512 if (state->have == 0) {
513 strm->msg = (char *)"invalid bit length repeat";
514 state->mode = BAD;
515 break;
516 }
517 len = state->lens[state->have - 1];
518 copy = 3 + BITS(2);
519 DROPBITS(2);
520 }
521 else if (this.val == 17) {
522 NEEDBITS(this.bits + 3);
523 DROPBITS(this.bits);
524 len = 0;
525 copy = 3 + BITS(3);
526 DROPBITS(3);
527 }
528 else {
529 NEEDBITS(this.bits + 7);
530 DROPBITS(this.bits);
531 len = 0;
532 copy = 11 + BITS(7);
533 DROPBITS(7);
534 }
535 if (state->have + copy > state->nlen + state->ndist) {
536 strm->msg = (char *)"invalid bit length repeat";
537 state->mode = BAD;
538 break;
539 }
540 while (copy--)
541 state->lens[state->have++] = (unsigned short)len;
542 }
543 }
544
545 /* handle error breaks in while */
546 if (state->mode == BAD) break;
547
548 /* build code tables */
549 state->next = state->codes;
550 state->lencode = (code const *)(state->next);
551 state->lenbits = 9;
552 ret = zlib_inflate_table(LENS, state->lens, state->nlen, &(state->next),
553 &(state->lenbits), state->work);
554 if (ret) {
555 strm->msg = (char *)"invalid literal/lengths set";
556 state->mode = BAD;
557 break;
558 }
559 state->distcode = (code const *)(state->next);
560 state->distbits = 6;
561 ret = zlib_inflate_table(DISTS, state->lens + state->nlen, state->ndist,
562 &(state->next), &(state->distbits), state->work);
563 if (ret) {
564 strm->msg = (char *)"invalid distances set";
565 state->mode = BAD;
566 break;
567 }
568 state->mode = LEN;
569 case LEN:
570 if (have >= 6 && left >= 258) {
571 RESTORE();
572 inflate_fast(strm, out);
573 LOAD();
574 break;
575 }
576 for (;;) {
577 this = state->lencode[BITS(state->lenbits)];
578 if ((unsigned)(this.bits) <= bits) break;
579 PULLBYTE();
580 }
581 if (this.op && (this.op & 0xf0) == 0) {
582 last = this;
583 for (;;) {
584 this = state->lencode[last.val +
585 (BITS(last.bits + last.op) >> last.bits)];
586 if ((unsigned)(last.bits + this.bits) <= bits) break;
587 PULLBYTE();
588 }
589 DROPBITS(last.bits);
590 }
591 DROPBITS(this.bits);
592 state->length = (unsigned)this.val;
593 if ((int)(this.op) == 0) {
594 state->mode = LIT;
595 break;
596 }
597 if (this.op & 32) {
598 state->mode = TYPE;
599 break;
600 }
601 if (this.op & 64) {
602 strm->msg = (char *)"invalid literal/length code";
603 state->mode = BAD;
604 break;
605 }
606 state->extra = (unsigned)(this.op) & 15;
607 state->mode = LENEXT;
608 case LENEXT:
609 if (state->extra) {
610 NEEDBITS(state->extra);
611 state->length += BITS(state->extra);
612 DROPBITS(state->extra);
613 }
614 state->mode = DIST;
615 case DIST:
616 for (;;) {
617 this = state->distcode[BITS(state->distbits)];
618 if ((unsigned)(this.bits) <= bits) break;
619 PULLBYTE();
620 }
621 if ((this.op & 0xf0) == 0) {
622 last = this;
623 for (;;) {
624 this = state->distcode[last.val +
625 (BITS(last.bits + last.op) >> last.bits)];
626 if ((unsigned)(last.bits + this.bits) <= bits) break;
627 PULLBYTE();
628 }
629 DROPBITS(last.bits);
630 }
631 DROPBITS(this.bits);
632 if (this.op & 64) {
633 strm->msg = (char *)"invalid distance code";
634 state->mode = BAD;
635 break;
636 }
637 state->offset = (unsigned)this.val;
638 state->extra = (unsigned)(this.op) & 15;
639 state->mode = DISTEXT;
640 case DISTEXT:
641 if (state->extra) {
642 NEEDBITS(state->extra);
643 state->offset += BITS(state->extra);
644 DROPBITS(state->extra);
645 }
646#ifdef INFLATE_STRICT
647 if (state->offset > state->dmax) {
648 strm->msg = (char *)"invalid distance too far back";
649 state->mode = BAD;
650 break;
651 }
652#endif
653 if (state->offset > state->whave + out - left) {
654 strm->msg = (char *)"invalid distance too far back";
655 state->mode = BAD;
656 break;
657 }
658 state->mode = MATCH;
659 case MATCH:
660 if (left == 0) goto inf_leave;
661 copy = out - left;
662 if (state->offset > copy) { /* copy from window */
663 copy = state->offset - copy;
664 if (copy > state->write) {
665 copy -= state->write;
666 from = state->window + (state->wsize - copy);
667 }
668 else
669 from = state->window + (state->write - copy);
670 if (copy > state->length) copy = state->length;
671 }
672 else { /* copy from output */
673 from = put - state->offset;
674 copy = state->length;
675 }
676 if (copy > left) copy = left;
677 left -= copy;
678 state->length -= copy;
679 do {
680 *put++ = *from++;
681 } while (--copy);
682 if (state->length == 0) state->mode = LEN;
683 break;
684 case LIT:
685 if (left == 0) goto inf_leave;
686 *put++ = (unsigned char)(state->length);
687 left--;
688 state->mode = LEN;
689 break;
690 case CHECK:
691 if (state->wrap) {
692 NEEDBITS(32);
693 out -= left;
694 strm->total_out += out;
695 state->total += out;
696 if (out)
697 strm->adler = state->check =
698 UPDATE(state->check, put - out, out);
699 out = left;
700 if ((
701 REVERSE(hold)) != state->check) {
702 strm->msg = (char *)"incorrect data check";
703 state->mode = BAD;
704 break;
705 }
706 INITBITS();
707 }
708 state->mode = DONE;
709 case DONE:
710 ret = Z_STREAM_END;
711 goto inf_leave;
712 case BAD:
713 ret = Z_DATA_ERROR;
714 goto inf_leave;
715 case MEM:
716 return Z_MEM_ERROR;
717 case SYNC:
718 default:
719 return Z_STREAM_ERROR;
720 }
721
722 /*
723 Return from inflate(), updating the total counts and the check value.
724 If there was no progress during the inflate() call, return a buffer
725 error. Call zlib_updatewindow() to create and/or update the window state.
726 */
727 inf_leave:
728 RESTORE();
729 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
730 zlib_updatewindow(strm, out);
731
732 in -= strm->avail_in;
733 out -= strm->avail_out;
734 strm->total_in += in;
735 strm->total_out += out;
736 state->total += out;
737 if (state->wrap && out)
738 strm->adler = state->check =
739 UPDATE(state->check, strm->next_out - out, out);
740
741 strm->data_type = state->bits + (state->last ? 64 : 0) +
742 (state->mode == TYPE ? 128 : 0);
743 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
744 ret = Z_BUF_ERROR;
745
746 if (flush == Z_PACKET_FLUSH && ret == Z_OK &&
747 (strm->avail_out != 0 || strm->avail_in == 0))
748 return zlib_inflateSyncPacket(strm);
749 return ret;
750}
751
752int zlib_inflateEnd(z_streamp strm)
753{
754 if (strm == NULL || strm->state == NULL)
755 return Z_STREAM_ERROR;
99 return Z_OK; 756 return Z_OK;
100} 757}
101 758
759#if 0
760int zlib_inflateSetDictionary(z_streamp strm, const Byte *dictionary,
761 uInt dictLength)
762{
763 struct inflate_state *state;
764 unsigned long id;
765
766 /* check state */
767 if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;
768 state = (struct inflate_state *)strm->state;
769 if (state->wrap != 0 && state->mode != DICT)
770 return Z_STREAM_ERROR;
771
772 /* check for correct dictionary id */
773 if (state->mode == DICT) {
774 id = zlib_adler32(0L, NULL, 0);
775 id = zlib_adler32(id, dictionary, dictLength);
776 if (id != state->check)
777 return Z_DATA_ERROR;
778 }
779
780 /* copy dictionary to window */
781 zlib_updatewindow(strm, strm->avail_out);
102 782
103int zlib_inflateInit_( 783 if (dictLength > state->wsize) {
104 z_streamp z, 784 memcpy(state->window, dictionary + dictLength - state->wsize,
105 const char *version, 785 state->wsize);
106 int stream_size 786 state->whave = state->wsize;
107) 787 }
788 else {
789 memcpy(state->window + state->wsize - dictLength, dictionary,
790 dictLength);
791 state->whave = dictLength;
792 }
793 state->havedict = 1;
794 return Z_OK;
795}
796#endif
797
798#if 0
799/*
800 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
801 or when out of input. When called, *have is the number of pattern bytes
802 found in order so far, in 0..3. On return *have is updated to the new
803 state. If on return *have equals four, then the pattern was found and the
804 return value is how many bytes were read including the last byte of the
805 pattern. If *have is less than four, then the pattern has not been found
806 yet and the return value is len. In the latter case, zlib_syncsearch() can be
807 called again with more data and the *have state. *have is initialized to
808 zero for the first call.
809 */
810static unsigned zlib_syncsearch(unsigned *have, unsigned char *buf,
811 unsigned len)
108{ 812{
109 return zlib_inflateInit2_(z, DEF_WBITS, version, stream_size); 813 unsigned got;
814 unsigned next;
815
816 got = *have;
817 next = 0;
818 while (next < len && got < 4) {
819 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
820 got++;
821 else if (buf[next])
822 got = 0;
823 else
824 got = 4 - got;
825 next++;
826 }
827 *have = got;
828 return next;
110} 829}
830#endif
111 831
112#undef NEEDBYTE 832#if 0
113#undef NEXTBYTE 833int zlib_inflateSync(z_streamp strm)
114#define NEEDBYTE {if(z->avail_in==0)goto empty;r=trv;} 834{
115#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) 835 unsigned len; /* number of bytes to look at or looked at */
836 unsigned long in, out; /* temporary to save total_in and total_out */
837 unsigned char buf[4]; /* to restore bit buffer to byte string */
838 struct inflate_state *state;
839
840 /* check parameters */
841 if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;
842 state = (struct inflate_state *)strm->state;
843 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
844
845 /* if first time, start search in bit buffer */
846 if (state->mode != SYNC) {
847 state->mode = SYNC;
848 state->hold <<= state->bits & 7;
849 state->bits -= state->bits & 7;
850 len = 0;
851 while (state->bits >= 8) {
852 buf[len++] = (unsigned char)(state->hold);
853 state->hold >>= 8;
854 state->bits -= 8;
855 }
856 state->have = 0;
857 zlib_syncsearch(&(state->have), buf, len);
858 }
859
860 /* search available input */
861 len = zlib_syncsearch(&(state->have), strm->next_in, strm->avail_in);
862 strm->avail_in -= len;
863 strm->next_in += len;
864 strm->total_in += len;
865
866 /* return no joy or set up to restart inflate() on a new block */
867 if (state->have != 4) return Z_DATA_ERROR;
868 in = strm->total_in; out = strm->total_out;
869 zlib_inflateReset(strm);
870 strm->total_in = in; strm->total_out = out;
871 state->mode = TYPE;
872 return Z_OK;
873}
874#endif
116 875
117int zlib_inflate( 876/*
118 z_streamp z, 877 * This subroutine adds the data at next_in/avail_in to the output history
119 int f 878 * without performing any output. The output buffer must be "caught up";
120) 879 * i.e. no pending output but this should always be the case. The state must
880 * be waiting on the start of a block (i.e. mode == TYPE or HEAD). On exit,
881 * the output will also be caught up, and the checksum will have been updated
882 * if need be.
883 */
884int zlib_inflateIncomp(z_stream *z)
121{ 885{
122 int r, trv; 886 struct inflate_state *state = (struct inflate_state *)z->state;
123 uInt b; 887 Byte *saved_no = z->next_out;
124 888 uInt saved_ao = z->avail_out;
125 if (z == NULL || z->state == NULL || z->next_in == NULL) 889
126 return Z_STREAM_ERROR; 890 if (state->mode != TYPE && state->mode != HEAD)
127 trv = f == Z_FINISH ? Z_BUF_ERROR : Z_OK; 891 return Z_DATA_ERROR;
128 r = Z_BUF_ERROR; 892
129 while (1) switch (z->state->mode) 893 /* Setup some variables to allow misuse of updateWindow */
130 { 894 z->avail_out = 0;
131 case METHOD: 895 z->next_out = z->next_in + z->avail_in;
132 NEEDBYTE 896
133 if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED) 897 zlib_updatewindow(z, z->avail_in);
134 { 898
135 z->state->mode = I_BAD; 899 /* Restore saved variables */
136 z->msg = (char*)"unknown compression method"; 900 z->avail_out = saved_ao;
137 z->state->sub.marker = 5; /* can't try inflateSync */ 901 z->next_out = saved_no;
138 break; 902
139 } 903 z->adler = state->check =
140 if ((z->state->sub.method >> 4) + 8 > z->state->wbits) 904 UPDATE(state->check, z->next_in, z->avail_in);
141 { 905
142 z->state->mode = I_BAD; 906 z->total_out += z->avail_in;
143 z->msg = (char*)"invalid window size"; 907 z->total_in += z->avail_in;
144 z->state->sub.marker = 5; /* can't try inflateSync */ 908 z->next_in += z->avail_in;
145 break; 909 state->total += z->avail_in;
146 } 910 z->avail_in = 0;
147 z->state->mode = FLAG; 911
148 case FLAG: 912 return Z_OK;
149 NEEDBYTE
150 b = NEXTBYTE;
151 if (((z->state->sub.method << 8) + b) % 31)
152 {
153 z->state->mode = I_BAD;
154 z->msg = (char*)"incorrect header check";
155 z->state->sub.marker = 5; /* can't try inflateSync */
156 break;
157 }
158 if (!(b & PRESET_DICT))
159 {
160 z->state->mode = BLOCKS;
161 break;
162 }
163 z->state->mode = DICT4;
164 case DICT4:
165 NEEDBYTE
166 z->state->sub.check.need = (uLong)NEXTBYTE << 24;
167 z->state->mode = DICT3;
168 case DICT3:
169 NEEDBYTE
170 z->state->sub.check.need += (uLong)NEXTBYTE << 16;
171 z->state->mode = DICT2;
172 case DICT2:
173 NEEDBYTE
174 z->state->sub.check.need += (uLong)NEXTBYTE << 8;
175 z->state->mode = DICT1;
176 case DICT1:
177 NEEDBYTE
178 z->state->sub.check.need += (uLong)NEXTBYTE;
179 z->adler = z->state->sub.check.need;
180 z->state->mode = DICT0;
181 return Z_NEED_DICT;
182 case DICT0:
183 z->state->mode = I_BAD;
184 z->msg = (char*)"need dictionary";
185 z->state->sub.marker = 0; /* can try inflateSync */
186 return Z_STREAM_ERROR;
187 case BLOCKS:
188 r = zlib_inflate_blocks(z->state->blocks, z, r);
189 if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
190 r = zlib_inflate_packet_flush(z->state->blocks);
191 if (r == Z_DATA_ERROR)
192 {
193 z->state->mode = I_BAD;
194 z->state->sub.marker = 0; /* can try inflateSync */
195 break;
196 }
197 if (r == Z_OK)
198 r = trv;
199 if (r != Z_STREAM_END)
200 return r;
201 r = trv;
202 zlib_inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
203 if (z->state->nowrap)
204 {
205 z->state->mode = I_DONE;
206 break;
207 }
208 z->state->mode = CHECK4;
209 case CHECK4:
210 NEEDBYTE
211 z->state->sub.check.need = (uLong)NEXTBYTE << 24;
212 z->state->mode = CHECK3;
213 case CHECK3:
214 NEEDBYTE
215 z->state->sub.check.need += (uLong)NEXTBYTE << 16;
216 z->state->mode = CHECK2;
217 case CHECK2:
218 NEEDBYTE
219 z->state->sub.check.need += (uLong)NEXTBYTE << 8;
220 z->state->mode = CHECK1;
221 case CHECK1:
222 NEEDBYTE
223 z->state->sub.check.need += (uLong)NEXTBYTE;
224
225 if (z->state->sub.check.was != z->state->sub.check.need)
226 {
227 z->state->mode = I_BAD;
228 z->msg = (char*)"incorrect data check";
229 z->state->sub.marker = 5; /* can't try inflateSync */
230 break;
231 }
232 z->state->mode = I_DONE;
233 case I_DONE:
234 return Z_STREAM_END;
235 case I_BAD:
236 return Z_DATA_ERROR;
237 default:
238 return Z_STREAM_ERROR;
239 }
240 empty:
241 if (f != Z_PACKET_FLUSH)
242 return r;
243 z->state->mode = I_BAD;
244 z->msg = (char *)"need more for packet flush";
245 z->state->sub.marker = 0; /* can try inflateSync */
246 return Z_DATA_ERROR;
247} 913}
diff --git a/lib/zlib_inflate/inflate.h b/lib/zlib_inflate/inflate.h
new file mode 100644
index 000000000000..df8a6c92052d
--- /dev/null
+++ b/lib/zlib_inflate/inflate.h
@@ -0,0 +1,107 @@
1/* inflate.h -- internal inflate state definition
2 * Copyright (C) 1995-2004 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11/* Possible inflate modes between inflate() calls */
12typedef enum {
13 HEAD, /* i: waiting for magic header */
14 FLAGS, /* i: waiting for method and flags (gzip) */
15 TIME, /* i: waiting for modification time (gzip) */
16 OS, /* i: waiting for extra flags and operating system (gzip) */
17 EXLEN, /* i: waiting for extra length (gzip) */
18 EXTRA, /* i: waiting for extra bytes (gzip) */
19 NAME, /* i: waiting for end of file name (gzip) */
20 COMMENT, /* i: waiting for end of comment (gzip) */
21 HCRC, /* i: waiting for header crc (gzip) */
22 DICTID, /* i: waiting for dictionary check value */
23 DICT, /* waiting for inflateSetDictionary() call */
24 TYPE, /* i: waiting for type bits, including last-flag bit */
25 TYPEDO, /* i: same, but skip check to exit inflate on new block */
26 STORED, /* i: waiting for stored size (length and complement) */
27 COPY, /* i/o: waiting for input or output to copy stored block */
28 TABLE, /* i: waiting for dynamic block table lengths */
29 LENLENS, /* i: waiting for code length code lengths */
30 CODELENS, /* i: waiting for length/lit and distance code lengths */
31 LEN, /* i: waiting for length/lit code */
32 LENEXT, /* i: waiting for length extra bits */
33 DIST, /* i: waiting for distance code */
34 DISTEXT, /* i: waiting for distance extra bits */
35 MATCH, /* o: waiting for output space to copy string */
36 LIT, /* o: waiting for output space to write literal */
37 CHECK, /* i: waiting for 32-bit check value */
38 LENGTH, /* i: waiting for 32-bit length (gzip) */
39 DONE, /* finished check, done -- remain here until reset */
40 BAD, /* got a data error -- remain here until reset */
41 MEM, /* got an inflate() memory error -- remain here until reset */
42 SYNC /* looking for synchronization bytes to restart inflate() */
43} inflate_mode;
44
45/*
46 State transitions between above modes -
47
48 (most modes can go to the BAD or MEM mode -- not shown for clarity)
49
50 Process header:
51 HEAD -> (gzip) or (zlib)
52 (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
53 NAME -> COMMENT -> HCRC -> TYPE
54 (zlib) -> DICTID or TYPE
55 DICTID -> DICT -> TYPE
56 Read deflate blocks:
57 TYPE -> STORED or TABLE or LEN or CHECK
58 STORED -> COPY -> TYPE
59 TABLE -> LENLENS -> CODELENS -> LEN
60 Read deflate codes:
61 LEN -> LENEXT or LIT or TYPE
62 LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
63 LIT -> LEN
64 Process trailer:
65 CHECK -> LENGTH -> DONE
66 */
67
68/* state maintained between inflate() calls. Approximately 7K bytes. */
69struct inflate_state {
70 inflate_mode mode; /* current inflate mode */
71 int last; /* true if processing last block */
72 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
73 int havedict; /* true if dictionary provided */
74 int flags; /* gzip header method and flags (0 if zlib) */
75 unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */
76 unsigned long check; /* protected copy of check value */
77 unsigned long total; /* protected copy of output count */
78 /* gz_headerp head; */ /* where to save gzip header information */
79 /* sliding window */
80 unsigned wbits; /* log base 2 of requested window size */
81 unsigned wsize; /* window size or zero if not using window */
82 unsigned whave; /* valid bytes in the window */
83 unsigned write; /* window write index */
84 unsigned char *window; /* allocated sliding window, if needed */
85 /* bit accumulator */
86 unsigned long hold; /* input bit accumulator */
87 unsigned bits; /* number of bits in "in" */
88 /* for string and stored block copying */
89 unsigned length; /* literal or length of data to copy */
90 unsigned offset; /* distance back to copy string from */
91 /* for table and code decoding */
92 unsigned extra; /* extra bits needed */
93 /* fixed and dynamic code tables */
94 code const *lencode; /* starting table for length/literal codes */
95 code const *distcode; /* starting table for distance codes */
96 unsigned lenbits; /* index bits for lencode */
97 unsigned distbits; /* index bits for distcode */
98 /* dynamic table building */
99 unsigned ncode; /* number of code length code lengths */
100 unsigned nlen; /* number of length code lengths */
101 unsigned ndist; /* number of distance code lengths */
102 unsigned have; /* number of code lengths in lens[] */
103 code *next; /* next available space in codes[] */
104 unsigned short lens[320]; /* temporary storage for code lengths */
105 unsigned short work[288]; /* work area for code table building */
106 code codes[ENOUGH]; /* space for code tables */
107};
diff --git a/lib/zlib_inflate/inflate_syms.c b/lib/zlib_inflate/inflate_syms.c
index ef49738f57ec..2061d4f06765 100644
--- a/lib/zlib_inflate/inflate_syms.c
+++ b/lib/zlib_inflate/inflate_syms.c
@@ -12,8 +12,7 @@
12 12
13EXPORT_SYMBOL(zlib_inflate_workspacesize); 13EXPORT_SYMBOL(zlib_inflate_workspacesize);
14EXPORT_SYMBOL(zlib_inflate); 14EXPORT_SYMBOL(zlib_inflate);
15EXPORT_SYMBOL(zlib_inflateInit_); 15EXPORT_SYMBOL(zlib_inflateInit2);
16EXPORT_SYMBOL(zlib_inflateInit2_);
17EXPORT_SYMBOL(zlib_inflateEnd); 16EXPORT_SYMBOL(zlib_inflateEnd);
18EXPORT_SYMBOL(zlib_inflateReset); 17EXPORT_SYMBOL(zlib_inflateReset);
19EXPORT_SYMBOL(zlib_inflateIncomp); 18EXPORT_SYMBOL(zlib_inflateIncomp);
diff --git a/lib/zlib_inflate/inflate_sync.c b/lib/zlib_inflate/inflate_sync.c
deleted file mode 100644
index 61411ff89d61..000000000000
--- a/lib/zlib_inflate/inflate_sync.c
+++ /dev/null
@@ -1,152 +0,0 @@
1/* inflate.c -- zlib interface to inflate modules
2 * Copyright (C) 1995-1998 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include <linux/zutil.h>
7#include "infblock.h"
8#include "infutil.h"
9
10#if 0
11int zlib_inflateSync(
12 z_streamp z
13)
14{
15 uInt n; /* number of bytes to look at */
16 Byte *p; /* pointer to bytes */
17 uInt m; /* number of marker bytes found in a row */
18 uLong r, w; /* temporaries to save total_in and total_out */
19
20 /* set up */
21 if (z == NULL || z->state == NULL)
22 return Z_STREAM_ERROR;
23 if (z->state->mode != I_BAD)
24 {
25 z->state->mode = I_BAD;
26 z->state->sub.marker = 0;
27 }
28 if ((n = z->avail_in) == 0)
29 return Z_BUF_ERROR;
30 p = z->next_in;
31 m = z->state->sub.marker;
32
33 /* search */
34 while (n && m < 4)
35 {
36 static const Byte mark[4] = {0, 0, 0xff, 0xff};
37 if (*p == mark[m])
38 m++;
39 else if (*p)
40 m = 0;
41 else
42 m = 4 - m;
43 p++, n--;
44 }
45
46 /* restore */
47 z->total_in += p - z->next_in;
48 z->next_in = p;
49 z->avail_in = n;
50 z->state->sub.marker = m;
51
52 /* return no joy or set up to restart on a new block */
53 if (m != 4)
54 return Z_DATA_ERROR;
55 r = z->total_in; w = z->total_out;
56 zlib_inflateReset(z);
57 z->total_in = r; z->total_out = w;
58 z->state->mode = BLOCKS;
59 return Z_OK;
60}
61#endif /* 0 */
62
63
64/* Returns true if inflate is currently at the end of a block generated
65 * by Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
66 * implementation to provide an additional safety check. PPP uses Z_SYNC_FLUSH
67 * but removes the length bytes of the resulting empty stored block. When
68 * decompressing, PPP checks that at the end of input packet, inflate is
69 * waiting for these length bytes.
70 */
71#if 0
72int zlib_inflateSyncPoint(
73 z_streamp z
74)
75{
76 if (z == NULL || z->state == NULL || z->state->blocks == NULL)
77 return Z_STREAM_ERROR;
78 return zlib_inflate_blocks_sync_point(z->state->blocks);
79}
80#endif /* 0 */
81
82/*
83 * This subroutine adds the data at next_in/avail_in to the output history
84 * without performing any output. The output buffer must be "caught up";
85 * i.e. no pending output (hence s->read equals s->write), and the state must
86 * be BLOCKS (i.e. we should be willing to see the start of a series of
87 * BLOCKS). On exit, the output will also be caught up, and the checksum
88 * will have been updated if need be.
89 */
90static int zlib_inflate_addhistory(inflate_blocks_statef *s,
91 z_stream *z)
92{
93 uLong b; /* bit buffer */ /* NOT USED HERE */
94 uInt k; /* bits in bit buffer */ /* NOT USED HERE */
95 uInt t; /* temporary storage */
96 Byte *p; /* input data pointer */
97 uInt n; /* bytes available there */
98 Byte *q; /* output window write pointer */
99 uInt m; /* bytes to end of window or read pointer */
100
101 if (s->read != s->write)
102 return Z_STREAM_ERROR;
103 if (s->mode != TYPE)
104 return Z_DATA_ERROR;
105
106 /* we're ready to rock */
107 LOAD
108 /* while there is input ready, copy to output buffer, moving
109 * pointers as needed.
110 */
111 while (n) {
112 t = n; /* how many to do */
113 /* is there room until end of buffer? */
114 if (t > m) t = m;
115 /* update check information */
116 if (s->checkfn != NULL)
117 s->check = (*s->checkfn)(s->check, q, t);
118 memcpy(q, p, t);
119 q += t;
120 p += t;
121 n -= t;
122 z->total_out += t;
123 s->read = q; /* drag read pointer forward */
124/* WWRAP */ /* expand WWRAP macro by hand to handle s->read */
125 if (q == s->end) {
126 s->read = q = s->window;
127 m = WAVAIL;
128 }
129 }
130 UPDATE
131 return Z_OK;
132}
133
134
135/*
136 * This subroutine adds the data at next_in/avail_in to the output history
137 * without performing any output. The output buffer must be "caught up";
138 * i.e. no pending output (hence s->read equals s->write), and the state must
139 * be BLOCKS (i.e. we should be willing to see the start of a series of
140 * BLOCKS). On exit, the output will also be caught up, and the checksum
141 * will have been updated if need be.
142 */
143
144int zlib_inflateIncomp(
145 z_stream *z
146
147)
148{
149 if (z->state->mode != BLOCKS)
150 return Z_DATA_ERROR;
151 return zlib_inflate_addhistory(z->state->blocks, z);
152}
diff --git a/lib/zlib_inflate/inftrees.c b/lib/zlib_inflate/inftrees.c
index 874950ec4858..62343c53bf7e 100644
--- a/lib/zlib_inflate/inftrees.c
+++ b/lib/zlib_inflate/inftrees.c
@@ -1,412 +1,329 @@
1/* inftrees.c -- generate Huffman trees for efficient decoding 1/* inftrees.c -- generate Huffman trees for efficient decoding
2 * Copyright (C) 1995-1998 Mark Adler 2 * Copyright (C) 1995-2005 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6#include <linux/zutil.h> 6#include <linux/zutil.h>
7#include "inftrees.h" 7#include "inftrees.h"
8#include "infutil.h"
9 8
10static const char inflate_copyright[] __attribute_used__ = 9#define MAXBITS 15
11 " inflate 1.1.3 Copyright 1995-1998 Mark Adler "; 10
11const char inflate_copyright[] =
12 " inflate 1.2.3 Copyright 1995-2005 Mark Adler ";
12/* 13/*
13 If you use the zlib library in a product, an acknowledgment is welcome 14 If you use the zlib library in a product, an acknowledgment is welcome
14 in the documentation of your product. If for some reason you cannot 15 in the documentation of your product. If for some reason you cannot
15 include such an acknowledgment, I would appreciate that you keep this 16 include such an acknowledgment, I would appreciate that you keep this
16 copyright string in the executable of your product. 17 copyright string in the executable of your product.
17 */ 18 */
18struct internal_state;
19
20/* simplify the use of the inflate_huft type with some defines */
21#define exop word.what.Exop
22#define bits word.what.Bits
23
24
25static int huft_build (
26 uInt *, /* code lengths in bits */
27 uInt, /* number of codes */
28 uInt, /* number of "simple" codes */
29 const uInt *, /* list of base values for non-simple codes */
30 const uInt *, /* list of extra bits for non-simple codes */
31 inflate_huft **, /* result: starting table */
32 uInt *, /* maximum lookup bits (returns actual) */
33 inflate_huft *, /* space for trees */
34 uInt *, /* hufts used in space */
35 uInt * ); /* space for values */
36
37/* Tables for deflate from PKZIP's appnote.txt. */
38static const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
39 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
40 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
41 /* see note #13 above about 258 */
42static const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
43 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
44 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */
45static const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
46 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
47 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
48 8193, 12289, 16385, 24577};
49static const uInt cpdext[30] = { /* Extra bits for distance codes */
50 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
51 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
52 12, 12, 13, 13};
53 19
54/* 20/*
55 Huffman code decoding is performed using a multi-level table lookup. 21 Build a set of tables to decode the provided canonical Huffman code.
56 The fastest way to decode is to simply build a lookup table whose 22 The code lengths are lens[0..codes-1]. The result starts at *table,
57 size is determined by the longest code. However, the time it takes 23 whose indices are 0..2^bits-1. work is a writable array of at least
58 to build this table can also be a factor if the data being decoded 24 lens shorts, which is used as a work area. type is the type of code
59 is not very long. The most common codes are necessarily the 25 to be generated, CODES, LENS, or DISTS. On return, zero is success,
60 shortest codes, so those codes dominate the decoding time, and hence 26 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
61 the speed. The idea is you can have a shorter table that decodes the 27 on return points to the next available entry's address. bits is the
62 shorter, more probable codes, and then point to subsidiary tables for 28 requested root table index bits, and on return it is the actual root
63 the longer codes. The time it costs to decode the longer codes is 29 table index bits. It will differ if the request is greater than the
64 then traded against the time it takes to make longer tables. 30 longest code or if it is less than the shortest code.
65
66 This results of this trade are in the variables lbits and dbits
67 below. lbits is the number of bits the first level table for literal/
68 length codes can decode in one step, and dbits is the same thing for
69 the distance codes. Subsequent tables are also less than or equal to
70 those sizes. These values may be adjusted either when all of the
71 codes are shorter than that, in which case the longest code length in
72 bits is used, or when the shortest code is *longer* than the requested
73 table size, in which case the length of the shortest code in bits is
74 used.
75
76 There are two different values for the two tables, since they code a
77 different number of possibilities each. The literal/length table
78 codes 286 possible values, or in a flat code, a little over eight
79 bits. The distance table codes 30 possible values, or a little less
80 than five bits, flat. The optimum values for speed end up being
81 about one bit more than those, so lbits is 8+1 and dbits is 5+1.
82 The optimum values may differ though from machine to machine, and
83 possibly even between compilers. Your mileage may vary.
84 */ 31 */
85 32int zlib_inflate_table(type, lens, codes, table, bits, work)
86 33codetype type;
87/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 34unsigned short *lens;
88#define BMAX 15 /* maximum bit length of any code */ 35unsigned codes;
89 36code **table;
90static int huft_build( 37unsigned *bits;
91 uInt *b, /* code lengths in bits (all assumed <= BMAX) */ 38unsigned short *work;
92 uInt n, /* number of codes (assumed <= 288) */
93 uInt s, /* number of simple-valued codes (0..s-1) */
94 const uInt *d, /* list of base values for non-simple codes */
95 const uInt *e, /* list of extra bits for non-simple codes */
96 inflate_huft **t, /* result: starting table */
97 uInt *m, /* maximum lookup bits, returns actual */
98 inflate_huft *hp, /* space for trees */
99 uInt *hn, /* hufts used in space */
100 uInt *v /* working area: values in order of bit length */
101)
102/* Given a list of code lengths and a maximum table size, make a set of
103 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
104 if the given code set is incomplete (the tables are still built in this
105 case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of
106 lengths), or Z_MEM_ERROR if not enough memory. */
107{ 39{
40 unsigned len; /* a code's length in bits */
41 unsigned sym; /* index of code symbols */
42 unsigned min, max; /* minimum and maximum code lengths */
43 unsigned root; /* number of index bits for root table */
44 unsigned curr; /* number of index bits for current table */
45 unsigned drop; /* code bits to drop for sub-table */
46 int left; /* number of prefix codes available */
47 unsigned used; /* code entries in table used */
48 unsigned huff; /* Huffman code */
49 unsigned incr; /* for incrementing code, index */
50 unsigned fill; /* index for replicating entries */
51 unsigned low; /* low bits for current root entry */
52 unsigned mask; /* mask for low root bits */
53 code this; /* table entry for duplication */
54 code *next; /* next available space in table */
55 const unsigned short *base; /* base value table to use */
56 const unsigned short *extra; /* extra bits table to use */
57 int end; /* use base and extra for symbol > end */
58 unsigned short count[MAXBITS+1]; /* number of codes of each length */
59 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
60 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
62 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
63 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
66 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
68 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
69 8193, 12289, 16385, 24577, 0, 0};
70 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
73 28, 28, 29, 29, 64, 64};
74
75 /*
76 Process a set of code lengths to create a canonical Huffman code. The
77 code lengths are lens[0..codes-1]. Each length corresponds to the
78 symbols 0..codes-1. The Huffman code is generated by first sorting the
79 symbols by length from short to long, and retaining the symbol order
80 for codes with equal lengths. Then the code starts with all zero bits
81 for the first code of the shortest length, and the codes are integer
82 increments for the same length, and zeros are appended as the length
83 increases. For the deflate format, these bits are stored backwards
84 from their more natural integer increment ordering, and so when the
85 decoding tables are built in the large loop below, the integer codes
86 are incremented backwards.
87
88 This routine assumes, but does not check, that all of the entries in
89 lens[] are in the range 0..MAXBITS. The caller must assure this.
90 1..MAXBITS is interpreted as that code length. zero means that that
91 symbol does not occur in this code.
92
93 The codes are sorted by computing a count of codes for each length,
94 creating from that a table of starting indices for each length in the
95 sorted table, and then entering the symbols in order in the sorted
96 table. The sorted table is work[], with that space being provided by
97 the caller.
98
99 The length counts are used for other purposes as well, i.e. finding
100 the minimum and maximum length codes, determining if there are any
101 codes at all, checking for a valid set of lengths, and looking ahead
102 at length counts to determine sub-table sizes when building the
103 decoding tables.
104 */
105
106 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
107 for (len = 0; len <= MAXBITS; len++)
108 count[len] = 0;
109 for (sym = 0; sym < codes; sym++)
110 count[lens[sym]]++;
111
112 /* bound code lengths, force root to be within code lengths */
113 root = *bits;
114 for (max = MAXBITS; max >= 1; max--)
115 if (count[max] != 0) break;
116 if (root > max) root = max;
117 if (max == 0) { /* no symbols to code at all */
118 this.op = (unsigned char)64; /* invalid code marker */
119 this.bits = (unsigned char)1;
120 this.val = (unsigned short)0;
121 *(*table)++ = this; /* make a table to force an error */
122 *(*table)++ = this;
123 *bits = 1;
124 return 0; /* no symbols, but wait for decoding to report error */
125 }
126 for (min = 1; min <= MAXBITS; min++)
127 if (count[min] != 0) break;
128 if (root < min) root = min;
129
130 /* check for an over-subscribed or incomplete set of lengths */
131 left = 1;
132 for (len = 1; len <= MAXBITS; len++) {
133 left <<= 1;
134 left -= count[len];
135 if (left < 0) return -1; /* over-subscribed */
136 }
137 if (left > 0 && (type == CODES || max != 1))
138 return -1; /* incomplete set */
139
140 /* generate offsets into symbol table for each length for sorting */
141 offs[1] = 0;
142 for (len = 1; len < MAXBITS; len++)
143 offs[len + 1] = offs[len] + count[len];
144
145 /* sort symbols by length, by symbol order within each length */
146 for (sym = 0; sym < codes; sym++)
147 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
148
149 /*
150 Create and fill in decoding tables. In this loop, the table being
151 filled is at next and has curr index bits. The code being used is huff
152 with length len. That code is converted to an index by dropping drop
153 bits off of the bottom. For codes where len is less than drop + curr,
154 those top drop + curr - len bits are incremented through all values to
155 fill the table with replicated entries.
156
157 root is the number of index bits for the root table. When len exceeds
158 root, sub-tables are created pointed to by the root entry with an index
159 of the low root bits of huff. This is saved in low to check for when a
160 new sub-table should be started. drop is zero when the root table is
161 being filled, and drop is root when sub-tables are being filled.
162
163 When a new sub-table is needed, it is necessary to look ahead in the
164 code lengths to determine what size sub-table is needed. The length
165 counts are used for this, and so count[] is decremented as codes are
166 entered in the tables.
167
168 used keeps track of how many table entries have been allocated from the
169 provided *table space. It is checked when a LENS table is being made
170 against the space in *table, ENOUGH, minus the maximum space needed by
171 the worst case distance code, MAXD. This should never happen, but the
172 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
173 This assumes that when type == LENS, bits == 9.
174
175 sym increments through all symbols, and the loop terminates when
176 all codes of length max, i.e. all codes, have been processed. This
177 routine permits incomplete codes, so another loop after this one fills
178 in the rest of the decoding tables with invalid code markers.
179 */
180
181 /* set up for code type */
182 switch (type) {
183 case CODES:
184 base = extra = work; /* dummy value--not used */
185 end = 19;
186 break;
187 case LENS:
188 base = lbase;
189 base -= 257;
190 extra = lext;
191 extra -= 257;
192 end = 256;
193 break;
194 default: /* DISTS */
195 base = dbase;
196 extra = dext;
197 end = -1;
198 }
108 199
109 uInt a; /* counter for codes of length k */ 200 /* initialize state for loop */
110 uInt c[BMAX+1]; /* bit length count table */ 201 huff = 0; /* starting code */
111 uInt f; /* i repeats in table every f entries */ 202 sym = 0; /* starting code symbol */
112 int g; /* maximum code length */ 203 len = min; /* starting code length */
113 int h; /* table level */ 204 next = *table; /* current table to fill in */
114 register uInt i; /* counter, current code */ 205 curr = root; /* current table index bits */
115 register uInt j; /* counter */ 206 drop = 0; /* current bits to drop from code for index */
116 register int k; /* number of bits in current code */ 207 low = (unsigned)(-1); /* trigger new sub-table when len > root */
117 int l; /* bits per table (returned in m) */ 208 used = 1U << root; /* use root table entries */
118 uInt mask; /* (1 << w) - 1, to avoid cc -O bug on HP */ 209 mask = used - 1; /* mask for comparing low */
119 register uInt *p; /* pointer into c[], b[], or v[] */ 210
120 inflate_huft *q; /* points to current table */ 211 /* check available table space */
121 struct inflate_huft_s r; /* table entry for structure assignment */ 212 if (type == LENS && used >= ENOUGH - MAXD)
122 inflate_huft *u[BMAX]; /* table stack */ 213 return 1;
123 register int w; /* bits before this table == (l * h) */ 214
124 uInt x[BMAX+1]; /* bit offsets, then code stack */ 215 /* process all codes and make table entries */
125 uInt *xp; /* pointer into x */ 216 for (;;) {
126 int y; /* number of dummy codes added */ 217 /* create table entry */
127 uInt z; /* number of entries in current table */ 218 this.bits = (unsigned char)(len - drop);
128 219 if ((int)(work[sym]) < end) {
129 220 this.op = (unsigned char)0;
130 /* Generate counts for each bit length */ 221 this.val = work[sym];
131 p = c;
132#define C0 *p++ = 0;
133#define C2 C0 C0 C0 C0
134#define C4 C2 C2 C2 C2
135 C4 /* clear c[]--assume BMAX+1 is 16 */
136 p = b; i = n;
137 do {
138 c[*p++]++; /* assume all entries <= BMAX */
139 } while (--i);
140 if (c[0] == n) /* null input--all zero length codes */
141 {
142 *t = NULL;
143 *m = 0;
144 return Z_OK;
145 }
146
147
148 /* Find minimum and maximum length, bound *m by those */
149 l = *m;
150 for (j = 1; j <= BMAX; j++)
151 if (c[j])
152 break;
153 k = j; /* minimum code length */
154 if ((uInt)l < j)
155 l = j;
156 for (i = BMAX; i; i--)
157 if (c[i])
158 break;
159 g = i; /* maximum code length */
160 if ((uInt)l > i)
161 l = i;
162 *m = l;
163
164
165 /* Adjust last length count to fill out codes, if needed */
166 for (y = 1 << j; j < i; j++, y <<= 1)
167 if ((y -= c[j]) < 0)
168 return Z_DATA_ERROR;
169 if ((y -= c[i]) < 0)
170 return Z_DATA_ERROR;
171 c[i] += y;
172
173
174 /* Generate starting offsets into the value table for each length */
175 x[1] = j = 0;
176 p = c + 1; xp = x + 2;
177 while (--i) { /* note that i == g from above */
178 *xp++ = (j += *p++);
179 }
180
181
182 /* Make a table of values in order of bit lengths */
183 p = b; i = 0;
184 do {
185 if ((j = *p++) != 0)
186 v[x[j]++] = i;
187 } while (++i < n);
188 n = x[g]; /* set n to length of v */
189
190
191 /* Generate the Huffman codes and for each, make the table entries */
192 x[0] = i = 0; /* first Huffman code is zero */
193 p = v; /* grab values in bit order */
194 h = -1; /* no tables yet--level -1 */
195 w = -l; /* bits decoded == (l * h) */
196 u[0] = NULL; /* just to keep compilers happy */
197 q = NULL; /* ditto */
198 z = 0; /* ditto */
199
200 /* go through the bit lengths (k already is bits in shortest code) */
201 for (; k <= g; k++)
202 {
203 a = c[k];
204 while (a--)
205 {
206 /* here i is the Huffman code of length k bits for value *p */
207 /* make tables up to required level */
208 while (k > w + l)
209 {
210 h++;
211 w += l; /* previous table always l bits */
212
213 /* compute minimum size table less than or equal to l bits */
214 z = g - w;
215 z = z > (uInt)l ? l : z; /* table size upper limit */
216 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
217 { /* too few codes for k-w bit table */
218 f -= a + 1; /* deduct codes from patterns left */
219 xp = c + k;
220 if (j < z)
221 while (++j < z) /* try smaller tables up to z bits */
222 {
223 if ((f <<= 1) <= *++xp)
224 break; /* enough codes to use up j bits */
225 f -= *xp; /* else deduct codes from patterns */
226 }
227 } 222 }
228 z = 1 << j; /* table entries for j-bit table */ 223 else if ((int)(work[sym]) > end) {
229 224 this.op = (unsigned char)(extra[work[sym]]);
230 /* allocate new table */ 225 this.val = base[work[sym]];
231 if (*hn + z > MANY) /* (note: doesn't matter for fixed) */ 226 }
232 return Z_DATA_ERROR; /* overflow of MANY */ 227 else {
233 u[h] = q = hp + *hn; 228 this.op = (unsigned char)(32 + 64); /* end of block */
234 *hn += z; 229 this.val = 0;
235
236 /* connect to last table, if there is one */
237 if (h)
238 {
239 x[h] = i; /* save pattern for backing up */
240 r.bits = (Byte)l; /* bits to dump before this table */
241 r.exop = (Byte)j; /* bits in this table */
242 j = i >> (w - l);
243 r.base = (uInt)(q - u[h-1] - j); /* offset to this table */
244 u[h-1][j] = r; /* connect to last table */
245 } 230 }
246 else
247 *t = q; /* first table is returned result */
248 }
249
250 /* set up table entry in r */
251 r.bits = (Byte)(k - w);
252 if (p >= v + n)
253 r.exop = 128 + 64; /* out of values--invalid code */
254 else if (*p < s)
255 {
256 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
257 r.base = *p++; /* simple code is just the value */
258 }
259 else
260 {
261 r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
262 r.base = d[*p++ - s];
263 }
264
265 /* fill code-like entries with r */
266 f = 1 << (k - w);
267 for (j = i >> w; j < z; j += f)
268 q[j] = r;
269
270 /* backwards increment the k-bit code i */
271 for (j = 1 << (k - 1); i & j; j >>= 1)
272 i ^= j;
273 i ^= j;
274
275 /* backup over finished tables */
276 mask = (1 << w) - 1; /* needed on HP, cc -O bug */
277 while ((i & mask) != x[h])
278 {
279 h--; /* don't need to update q */
280 w -= l;
281 mask = (1 << w) - 1;
282 }
283 }
284 }
285 231
232 /* replicate for those indices with low len bits equal to huff */
233 incr = 1U << (len - drop);
234 fill = 1U << curr;
235 min = fill; /* save offset to next table */
236 do {
237 fill -= incr;
238 next[(huff >> drop) + fill] = this;
239 } while (fill != 0);
240
241 /* backwards increment the len-bit code huff */
242 incr = 1U << (len - 1);
243 while (huff & incr)
244 incr >>= 1;
245 if (incr != 0) {
246 huff &= incr - 1;
247 huff += incr;
248 }
249 else
250 huff = 0;
286 251
287 /* Return Z_BUF_ERROR if we were given an incomplete table */ 252 /* go to next symbol, update count, len */
288 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 253 sym++;
289} 254 if (--(count[len]) == 0) {
255 if (len == max) break;
256 len = lens[work[sym]];
257 }
290 258
259 /* create new sub-table if needed */
260 if (len > root && (huff & mask) != low) {
261 /* if first time, transition to sub-tables */
262 if (drop == 0)
263 drop = root;
264
265 /* increment past last table */
266 next += min; /* here min is 1 << curr */
267
268 /* determine length of next table */
269 curr = len - drop;
270 left = (int)(1 << curr);
271 while (curr + drop < max) {
272 left -= count[curr + drop];
273 if (left <= 0) break;
274 curr++;
275 left <<= 1;
276 }
291 277
292int zlib_inflate_trees_bits( 278 /* check for enough space */
293 uInt *c, /* 19 code lengths */ 279 used += 1U << curr;
294 uInt *bb, /* bits tree desired/actual depth */ 280 if (type == LENS && used >= ENOUGH - MAXD)
295 inflate_huft **tb, /* bits tree result */ 281 return 1;
296 inflate_huft *hp, /* space for trees */
297 z_streamp z /* for messages */
298)
299{
300 int r;
301 uInt hn = 0; /* hufts used in space */
302 uInt *v; /* work area for huft_build */
303
304 v = WS(z)->tree_work_area_1;
305 r = huft_build(c, 19, 19, NULL, NULL, tb, bb, hp, &hn, v);
306 if (r == Z_DATA_ERROR)
307 z->msg = (char*)"oversubscribed dynamic bit lengths tree";
308 else if (r == Z_BUF_ERROR || *bb == 0)
309 {
310 z->msg = (char*)"incomplete dynamic bit lengths tree";
311 r = Z_DATA_ERROR;
312 }
313 return r;
314}
315 282
316int zlib_inflate_trees_dynamic( 283 /* point entry in root table to sub-table */
317 uInt nl, /* number of literal/length codes */ 284 low = huff & mask;
318 uInt nd, /* number of distance codes */ 285 (*table)[low].op = (unsigned char)curr;
319 uInt *c, /* that many (total) code lengths */ 286 (*table)[low].bits = (unsigned char)root;
320 uInt *bl, /* literal desired/actual bit depth */ 287 (*table)[low].val = (unsigned short)(next - *table);
321 uInt *bd, /* distance desired/actual bit depth */ 288 }
322 inflate_huft **tl, /* literal/length tree result */
323 inflate_huft **td, /* distance tree result */
324 inflate_huft *hp, /* space for trees */
325 z_streamp z /* for messages */
326)
327{
328 int r;
329 uInt hn = 0; /* hufts used in space */
330 uInt *v; /* work area for huft_build */
331
332 /* allocate work area */
333 v = WS(z)->tree_work_area_2;
334
335 /* build literal/length tree */
336 r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
337 if (r != Z_OK || *bl == 0)
338 {
339 if (r == Z_DATA_ERROR)
340 z->msg = (char*)"oversubscribed literal/length tree";
341 else if (r != Z_MEM_ERROR)
342 {
343 z->msg = (char*)"incomplete literal/length tree";
344 r = Z_DATA_ERROR;
345 }
346 return r;
347 }
348
349 /* build distance tree */
350 r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
351 if (r != Z_OK || (*bd == 0 && nl > 257))
352 {
353 if (r == Z_DATA_ERROR)
354 z->msg = (char*)"oversubscribed distance tree";
355 else if (r == Z_BUF_ERROR) {
356#ifdef PKZIP_BUG_WORKAROUND
357 r = Z_OK;
358 }
359#else
360 z->msg = (char*)"incomplete distance tree";
361 r = Z_DATA_ERROR;
362 }
363 else if (r != Z_MEM_ERROR)
364 {
365 z->msg = (char*)"empty distance tree with lengths";
366 r = Z_DATA_ERROR;
367 } 289 }
368 return r;
369#endif
370 }
371 290
372 /* done */ 291 /*
373 return Z_OK; 292 Fill in rest of table for incomplete codes. This loop is similar to the
374} 293 loop above in incrementing huff for table indices. It is assumed that
294 len is equal to curr + drop, so there is no loop needed to increment
295 through high index bits. When the current sub-table is filled, the loop
296 drops back to the root table to fill in any remaining entries there.
297 */
298 this.op = (unsigned char)64; /* invalid code marker */
299 this.bits = (unsigned char)(len - drop);
300 this.val = (unsigned short)0;
301 while (huff != 0) {
302 /* when done with sub-table, drop back to root table */
303 if (drop != 0 && (huff & mask) != low) {
304 drop = 0;
305 len = root;
306 next = *table;
307 this.bits = (unsigned char)len;
308 }
375 309
310 /* put invalid code marker in table */
311 next[huff >> drop] = this;
376 312
377int zlib_inflate_trees_fixed( 313 /* backwards increment the len-bit code huff */
378 uInt *bl, /* literal desired/actual bit depth */ 314 incr = 1U << (len - 1);
379 uInt *bd, /* distance desired/actual bit depth */ 315 while (huff & incr)
380 inflate_huft **tl, /* literal/length tree result */ 316 incr >>= 1;
381 inflate_huft **td, /* distance tree result */ 317 if (incr != 0) {
382 inflate_huft *hp, /* space for trees */ 318 huff &= incr - 1;
383 z_streamp z /* for memory allocation */ 319 huff += incr;
384) 320 }
385{ 321 else
386 int i; /* temporary variable */ 322 huff = 0;
387 unsigned l[288]; /* length list for huft_build */ 323 }
388 uInt *v; /* work area for huft_build */ 324
389 325 /* set return parameters */
390 /* set up literal table */ 326 *table += used;
391 for (i = 0; i < 144; i++) 327 *bits = root;
392 l[i] = 8; 328 return 0;
393 for (; i < 256; i++)
394 l[i] = 9;
395 for (; i < 280; i++)
396 l[i] = 7;
397 for (; i < 288; i++) /* make a complete, but wrong code set */
398 l[i] = 8;
399 *bl = 9;
400 v = WS(z)->tree_work_area_1;
401 if ((i = huft_build(l, 288, 257, cplens, cplext, tl, bl, hp, &i, v)) != 0)
402 return i;
403
404 /* set up distance table */
405 for (i = 0; i < 30; i++) /* make an incomplete code set */
406 l[i] = 5;
407 *bd = 5;
408 if ((i = huft_build(l, 30, 0, cpdist, cpdext, td, bd, hp, &i, v)) > 1)
409 return i;
410
411 return Z_OK;
412} 329}
diff --git a/lib/zlib_inflate/inftrees.h b/lib/zlib_inflate/inftrees.h
index e37705adc008..5f5219b1240e 100644
--- a/lib/zlib_inflate/inftrees.h
+++ b/lib/zlib_inflate/inftrees.h
@@ -1,6 +1,6 @@
1/* inftrees.h -- header to use inftrees.c 1/* inftrees.h -- header to use inftrees.c
2 * Copyright (C) 1995-1998 Mark Adler 2 * Copyright (C) 1995-2005 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6/* WARNING: this file should *not* be used by applications. It is 6/* WARNING: this file should *not* be used by applications. It is
@@ -8,57 +8,48 @@
8 subject to change. Applications should only use zlib.h. 8 subject to change. Applications should only use zlib.h.
9 */ 9 */
10 10
11/* Huffman code lookup table entry--this entry is four bytes for machines 11/* Structure for decoding tables. Each entry provides either the
12 that have 16-bit pointers (e.g. PC's in the small or medium model). */ 12 information needed to do the operation requested by the code that
13 13 indexed that table entry, or it provides a pointer to another
14#ifndef _INFTREES_H 14 table that indexes more bits of the code. op indicates whether
15#define _INFTREES_H 15 the entry is a pointer to another table, a literal, a length or
16 16 distance, an end-of-block, or an invalid code. For a table
17typedef struct inflate_huft_s inflate_huft; 17 pointer, the low four bits of op is the number of index bits of
18 18 that table. For a length or distance, the low four bits of op
19struct inflate_huft_s { 19 is the number of extra bits to get after the code. bits is
20 union { 20 the number of bits in this code or part of the code to drop off
21 struct { 21 of the bit buffer. val is the actual byte to output in the case
22 Byte Exop; /* number of extra bits or operation */ 22 of a literal, the base length or distance, or the offset from
23 Byte Bits; /* number of bits in this code or subcode */ 23 the current table to the next table. Each entry is four bytes. */
24 } what; 24typedef struct {
25 uInt pad; /* pad structure to a power of 2 (4 bytes for */ 25 unsigned char op; /* operation, extra bits, table bits */
26 } word; /* 16-bit, 8 bytes for 32-bit int's) */ 26 unsigned char bits; /* bits in this part of the code */
27 uInt base; /* literal, length base, distance base, 27 unsigned short val; /* offset in table or code value */
28 or table offset */ 28} code;
29}; 29
30/* op values as set by inflate_table():
31 00000000 - literal
32 0000tttt - table link, tttt != 0 is the number of table index bits
33 0001eeee - length or distance, eeee is the number of extra bits
34 01100000 - end of block
35 01000000 - invalid code
36 */
30 37
31/* Maximum size of dynamic tree. The maximum found in a long but non- 38/* Maximum size of dynamic tree. The maximum found in a long but non-
32 exhaustive search was 1004 huft structures (850 for length/literals 39 exhaustive search was 1444 code structures (852 for length/literals
33 and 154 for distances, the latter actually the result of an 40 and 592 for distances, the latter actually the result of an
34 exhaustive search). The actual maximum is not known, but the 41 exhaustive search). The true maximum is not known, but the value
35 value below is more than safe. */ 42 below is more than safe. */
36#define MANY 1440 43#define ENOUGH 2048
37 44#define MAXD 592
38extern int zlib_inflate_trees_bits ( 45
39 uInt *, /* 19 code lengths */ 46/* Type of code to build for inftable() */
40 uInt *, /* bits tree desired/actual depth */ 47typedef enum {
41 inflate_huft **, /* bits tree result */ 48 CODES,
42 inflate_huft *, /* space for trees */ 49 LENS,
43 z_streamp); /* for messages */ 50 DISTS
44 51} codetype;
45extern int zlib_inflate_trees_dynamic ( 52
46 uInt, /* number of literal/length codes */ 53extern int zlib_inflate_table (codetype type, unsigned short *lens,
47 uInt, /* number of distance codes */ 54 unsigned codes, code **table,
48 uInt *, /* that many (total) code lengths */ 55 unsigned *bits, unsigned short *work);
49 uInt *, /* literal desired/actual bit depth */
50 uInt *, /* distance desired/actual bit depth */
51 inflate_huft **, /* literal/length tree result */
52 inflate_huft **, /* distance tree result */
53 inflate_huft *, /* space for trees */
54 z_streamp); /* for messages */
55
56extern int zlib_inflate_trees_fixed (
57 uInt *, /* literal desired/actual bit depth */
58 uInt *, /* distance desired/actual bit depth */
59 inflate_huft **, /* literal/length tree result */
60 inflate_huft **, /* distance tree result */
61 inflate_huft *, /* space for trees */
62 z_streamp); /* for memory allocation */
63
64#endif /* _INFTREES_H */
diff --git a/lib/zlib_inflate/infutil.c b/lib/zlib_inflate/infutil.c
deleted file mode 100644
index 00202b3438e1..000000000000
--- a/lib/zlib_inflate/infutil.c
+++ /dev/null
@@ -1,88 +0,0 @@
1/* inflate_util.c -- data and routines common to blocks and codes
2 * Copyright (C) 1995-1998 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include <linux/zutil.h>
7#include "infblock.h"
8#include "inftrees.h"
9#include "infcodes.h"
10#include "infutil.h"
11
12struct inflate_codes_state;
13
14/* And'ing with mask[n] masks the lower n bits */
15uInt zlib_inflate_mask[17] = {
16 0x0000,
17 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
18 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
19};
20
21
22/* copy as much as possible from the sliding window to the output area */
23int zlib_inflate_flush(
24 inflate_blocks_statef *s,
25 z_streamp z,
26 int r
27)
28{
29 uInt n;
30 Byte *p;
31 Byte *q;
32
33 /* local copies of source and destination pointers */
34 p = z->next_out;
35 q = s->read;
36
37 /* compute number of bytes to copy as far as end of window */
38 n = (uInt)((q <= s->write ? s->write : s->end) - q);
39 if (n > z->avail_out) n = z->avail_out;
40 if (n && r == Z_BUF_ERROR) r = Z_OK;
41
42 /* update counters */
43 z->avail_out -= n;
44 z->total_out += n;
45
46 /* update check information */
47 if (s->checkfn != NULL)
48 z->adler = s->check = (*s->checkfn)(s->check, q, n);
49
50 /* copy as far as end of window */
51 memcpy(p, q, n);
52 p += n;
53 q += n;
54
55 /* see if more to copy at beginning of window */
56 if (q == s->end)
57 {
58 /* wrap pointers */
59 q = s->window;
60 if (s->write == s->end)
61 s->write = s->window;
62
63 /* compute bytes to copy */
64 n = (uInt)(s->write - q);
65 if (n > z->avail_out) n = z->avail_out;
66 if (n && r == Z_BUF_ERROR) r = Z_OK;
67
68 /* update counters */
69 z->avail_out -= n;
70 z->total_out += n;
71
72 /* update check information */
73 if (s->checkfn != NULL)
74 z->adler = s->check = (*s->checkfn)(s->check, q, n);
75
76 /* copy */
77 memcpy(p, q, n);
78 p += n;
79 q += n;
80 }
81
82 /* update pointers */
83 z->next_out = p;
84 s->read = q;
85
86 /* done */
87 return r;
88}
diff --git a/lib/zlib_inflate/infutil.h b/lib/zlib_inflate/infutil.h
index a15875fc5f72..eb1a9007bd86 100644
--- a/lib/zlib_inflate/infutil.h
+++ b/lib/zlib_inflate/infutil.h
@@ -11,184 +11,12 @@
11#ifndef _INFUTIL_H 11#ifndef _INFUTIL_H
12#define _INFUTIL_H 12#define _INFUTIL_H
13 13
14#include <linux/zconf.h> 14#include <linux/zlib.h>
15#include "inftrees.h"
16#include "infcodes.h"
17
18typedef enum {
19 TYPE, /* get type bits (3, including end bit) */
20 LENS, /* get lengths for stored */
21 STORED, /* processing stored block */
22 TABLE, /* get table lengths */
23 BTREE, /* get bit lengths tree for a dynamic block */
24 DTREE, /* get length, distance trees for a dynamic block */
25 CODES, /* processing fixed or dynamic block */
26 DRY, /* output remaining window bytes */
27 B_DONE, /* finished last block, done */
28 B_BAD} /* got a data error--stuck here */
29inflate_block_mode;
30
31/* inflate blocks semi-private state */
32struct inflate_blocks_state {
33
34 /* mode */
35 inflate_block_mode mode; /* current inflate_block mode */
36
37 /* mode dependent information */
38 union {
39 uInt left; /* if STORED, bytes left to copy */
40 struct {
41 uInt table; /* table lengths (14 bits) */
42 uInt index; /* index into blens (or border) */
43 uInt *blens; /* bit lengths of codes */
44 uInt bb; /* bit length tree depth */
45 inflate_huft *tb; /* bit length decoding tree */
46 } trees; /* if DTREE, decoding info for trees */
47 struct {
48 inflate_codes_statef
49 *codes;
50 } decode; /* if CODES, current state */
51 } sub; /* submode */
52 uInt last; /* true if this block is the last block */
53
54 /* mode independent information */
55 uInt bitk; /* bits in bit buffer */
56 uLong bitb; /* bit buffer */
57 inflate_huft *hufts; /* single malloc for tree space */
58 Byte *window; /* sliding window */
59 Byte *end; /* one byte after sliding window */
60 Byte *read; /* window read pointer */
61 Byte *write; /* window write pointer */
62 check_func checkfn; /* check function */
63 uLong check; /* check on output */
64
65};
66
67
68/* defines for inflate input/output */
69/* update pointers and return */
70#define UPDBITS {s->bitb=b;s->bitk=k;}
71#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
72#define UPDOUT {s->write=q;}
73#define UPDATE {UPDBITS UPDIN UPDOUT}
74#define LEAVE {UPDATE return zlib_inflate_flush(s,z,r);}
75/* get bytes and bits */
76#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
77#define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
78#define NEXTBYTE (n--,*p++)
79#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
80#define DUMPBITS(j) {b>>=(j);k-=(j);}
81/* output bytes */
82#define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q)
83#define LOADOUT {q=s->write;m=(uInt)WAVAIL;}
84#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}}
85#define FLUSH {UPDOUT r=zlib_inflate_flush(s,z,r); LOADOUT}
86#define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
87#define OUTBYTE(a) {*q++=(Byte)(a);m--;}
88/* load local pointers */
89#define LOAD {LOADIN LOADOUT}
90
91/* masks for lower bits (size given to avoid silly warnings with Visual C++) */
92extern uInt zlib_inflate_mask[17];
93
94/* copy as much as possible from the sliding window to the output area */
95extern int zlib_inflate_flush (
96 inflate_blocks_statef *,
97 z_streamp ,
98 int);
99
100/* inflate private state */
101typedef enum {
102 METHOD, /* waiting for method byte */
103 FLAG, /* waiting for flag byte */
104 DICT4, /* four dictionary check bytes to go */
105 DICT3, /* three dictionary check bytes to go */
106 DICT2, /* two dictionary check bytes to go */
107 DICT1, /* one dictionary check byte to go */
108 DICT0, /* waiting for inflateSetDictionary */
109 BLOCKS, /* decompressing blocks */
110 CHECK4, /* four check bytes to go */
111 CHECK3, /* three check bytes to go */
112 CHECK2, /* two check bytes to go */
113 CHECK1, /* one check byte to go */
114 I_DONE, /* finished check, done */
115 I_BAD} /* got an error--stay here */
116inflate_mode;
117
118struct internal_state {
119
120 /* mode */
121 inflate_mode mode; /* current inflate mode */
122
123 /* mode dependent information */
124 union {
125 uInt method; /* if FLAGS, method byte */
126 struct {
127 uLong was; /* computed check value */
128 uLong need; /* stream check value */
129 } check; /* if CHECK, check values to compare */
130 uInt marker; /* if BAD, inflateSync's marker bytes count */
131 } sub; /* submode */
132
133 /* mode independent information */
134 int nowrap; /* flag for no wrapper */
135 uInt wbits; /* log2(window size) (8..15, defaults to 15) */
136 inflate_blocks_statef
137 *blocks; /* current inflate_blocks state */
138
139};
140
141/* inflate codes private state */
142typedef enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
143 START, /* x: set up for LEN */
144 LEN, /* i: get length/literal/eob next */
145 LENEXT, /* i: getting length extra (have base) */
146 DIST, /* i: get distance next */
147 DISTEXT, /* i: getting distance extra */
148 COPY, /* o: copying bytes in window, waiting for space */
149 LIT, /* o: got literal, waiting for output space */
150 WASH, /* o: got eob, possibly still output waiting */
151 END, /* x: got eob and all data flushed */
152 BADCODE} /* x: got error */
153inflate_codes_mode;
154
155struct inflate_codes_state {
156
157 /* mode */
158 inflate_codes_mode mode; /* current inflate_codes mode */
159
160 /* mode dependent information */
161 uInt len;
162 union {
163 struct {
164 inflate_huft *tree; /* pointer into tree */
165 uInt need; /* bits needed */
166 } code; /* if LEN or DIST, where in tree */
167 uInt lit; /* if LIT, literal */
168 struct {
169 uInt get; /* bits to get for extra */
170 uInt dist; /* distance back to copy from */
171 } copy; /* if EXT or COPY, where and how much */
172 } sub; /* submode */
173
174 /* mode independent information */
175 Byte lbits; /* ltree bits decoded per branch */
176 Byte dbits; /* dtree bits decoder per branch */
177 inflate_huft *ltree; /* literal/length/eob tree */
178 inflate_huft *dtree; /* distance tree */
179
180};
181 15
182/* memory allocation for inflation */ 16/* memory allocation for inflation */
183 17
184struct inflate_workspace { 18struct inflate_workspace {
185 inflate_codes_statef working_state; 19 struct inflate_state inflate_state;
186 struct inflate_blocks_state working_blocks_state;
187 struct internal_state internal_state;
188 unsigned int tree_work_area_1[19];
189 unsigned int tree_work_area_2[288];
190 unsigned working_blens[258 + 0x1f + 0x1f];
191 inflate_huft working_hufts[MANY];
192 unsigned char working_window[1 << MAX_WBITS]; 20 unsigned char working_window[1 << MAX_WBITS];
193}; 21};
194 22
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-18 17:59:17 -0500