aboutsummaryrefslogtreecommitdiffstats
path: root/lib/zlib_inflate/inflate.c
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/zlib_inflate/inflate.c
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/zlib_inflate/inflate.c')
-rw-r--r--lib/zlib_inflate/inflate.c1086
1 files changed, 876 insertions, 210 deletions
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}