inflate.c revision 145474
1106813Ssimokawa/* inflate.c -- zlib decompression 2113584Ssimokawa * Copyright (C) 1995-2003 Mark Adler 3106813Ssimokawa * For conditions of distribution and use, see copyright notice in zlib.h 4106813Ssimokawa */ 5106813Ssimokawa 6106813Ssimokawa/* 7106813Ssimokawa * Change history: 8106813Ssimokawa * 9106813Ssimokawa * 1.2.beta0 24 Nov 2002 10106813Ssimokawa * - First version -- complete rewrite of inflate to simplify code, avoid 11106813Ssimokawa * creation of window when not needed, minimize use of window when it is 12106813Ssimokawa * needed, make inffast.c even faster, implement gzip decoding, and to 13106813Ssimokawa * improve code readability and style over the previous zlib inflate code 14106813Ssimokawa * 15106813Ssimokawa * 1.2.beta1 25 Nov 2002 16106813Ssimokawa * - Use pointers for available input and output checking in inffast.c 17106813Ssimokawa * - Remove input and output counters in inffast.c 18106813Ssimokawa * - Change inffast.c entry and loop from avail_in >= 7 to >= 6 19106813Ssimokawa * - Remove unnecessary second byte pull from length extra in inffast.c 20106813Ssimokawa * - Unroll direct copy to three copies per loop in inffast.c 21106813Ssimokawa * 22106813Ssimokawa * 1.2.beta2 4 Dec 2002 23106813Ssimokawa * - Change external routine names to reduce potential conflicts 24106813Ssimokawa * - Correct filename to inffixed.h for fixed tables in inflate.c 25106813Ssimokawa * - Make hbuf[] unsigned char to match parameter type in inflate.c 26106813Ssimokawa * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 27106813Ssimokawa * to avoid negation problem on Alphas (64 bit) in inflate.c 28106813Ssimokawa * 29106813Ssimokawa * 1.2.beta3 22 Dec 2002 30106813Ssimokawa * - Add comments on state->bits assertion in inffast.c 31106813Ssimokawa * - Add comments on op field in inftrees.h 32106813Ssimokawa * - Fix bug in reuse of allocated window after inflateReset() 33106813Ssimokawa * - Remove bit fields--back to byte structure for speed 34106813Ssimokawa * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 35106813Ssimokawa * - Change post-increments to pre-increments in inflate_fast(), PPC biased? 36106813Ssimokawa * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 37106813Ssimokawa * - Make MATCH copy in inflate() much faster for when inflate_fast() not used 38106813Ssimokawa * - Use local copies of stream next and avail values, as well as local bit 39106813Ssimokawa * buffer and bit count in inflate()--for speed when inflate_fast() not used 40106813Ssimokawa * 41106813Ssimokawa * 1.2.beta4 1 Jan 2003 42120660Ssimokawa * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings 43120660Ssimokawa * - Move a comment on output buffer sizes from inffast.c to inflate.c 44120660Ssimokawa * - Add comments in inffast.c to introduce the inflate_fast() routine 45120660Ssimokawa * - Rearrange window copies in inflate_fast() for speed and simplification 46120660Ssimokawa * - Unroll last copy for window match in inflate_fast() 47106813Ssimokawa * - Use local copies of window variables in inflate_fast() for speed 48106813Ssimokawa * - Pull out common write == 0 case for speed in inflate_fast() 49106813Ssimokawa * - Make op and len in inflate_fast() unsigned for consistency 50106813Ssimokawa * - Add FAR to lcode and dcode declarations in inflate_fast() 51106813Ssimokawa * - Simplified bad distance check in inflate_fast() 52106813Ssimokawa * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 53106813Ssimokawa * source file infback.c to provide a call-back interface to inflate for 54118455Ssimokawa * programs like gzip and unzip -- uses window as output buffer to avoid 55113584Ssimokawa * window copying 56106813Ssimokawa * 57106813Ssimokawa * 1.2.beta5 1 Jan 2003 58106813Ssimokawa * - Improved inflateBack() interface to allow the caller to provide initial 59106813Ssimokawa * input in strm. 60106813Ssimokawa * - Fixed stored blocks bug in inflateBack() 61113584Ssimokawa * 62106813Ssimokawa * 1.2.beta6 4 Jan 2003 63109282Ssimokawa * - Added comments in inffast.c on effectiveness of POSTINC 64106813Ssimokawa * - Typecasting all around to reduce compiler warnings 65106813Ssimokawa * - Changed loops from while (1) or do {} while (1) to for (;;), again to 66106813Ssimokawa * make compilers happy 67106813Ssimokawa * - Changed type of window in inflateBackInit() to unsigned char * 68106813Ssimokawa * 69106813Ssimokawa * 1.2.beta7 27 Jan 2003 70106813Ssimokawa * - Changed many types to unsigned or unsigned short to avoid warnings 71106813Ssimokawa * - Added inflateCopy() function 72106813Ssimokawa * 73106813Ssimokawa * 1.2.0 9 Mar 2003 74106813Ssimokawa * - Changed inflateBack() interface to provide separate opaque descriptors 75120660Ssimokawa * for the in() and out() functions 76106813Ssimokawa * - Changed inflateBack() argument and in_func typedef to swap the length 77106813Ssimokawa * and buffer address return values for the input function 78106813Ssimokawa * - Check next_in and next_out for Z_NULL on entry to inflate() 79111942Ssimokawa * 80111815Sphk * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 81111815Sphk */ 82111815Sphk 83111815Sphk#include "zutil.h" 84111815Sphk#include "inftrees.h" 85111815Sphk#include "inflate.h" 86111815Sphk#include "inffast.h" 87120660Ssimokawa 88111815Sphk#ifdef MAKEFIXED 89111815Sphk# ifndef BUILDFIXED 90111815Sphk# define BUILDFIXED 91111942Ssimokawa# endif 92111942Ssimokawa#endif 93120660Ssimokawa 94118455Ssimokawa/* function prototypes */ 95111942Ssimokawalocal void fixedtables OF((struct inflate_state FAR *state)); 96106813Ssimokawalocal int updatewindow OF((z_streamp strm, unsigned out)); 97106813Ssimokawa#ifdef BUILDFIXED 98118293Ssimokawa void makefixed OF((void)); 99118293Ssimokawa#endif 100118293Ssimokawalocal unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf, 101118293Ssimokawa unsigned len)); 102118293Ssimokawa 103118293Ssimokawaint ZEXPORT inflateReset(strm) 104106813Ssimokawaz_streamp strm; 105118293Ssimokawa{ 106118293Ssimokawa struct inflate_state FAR *state; 107118293Ssimokawa 108118293Ssimokawa if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 109118293Ssimokawa state = (struct inflate_state FAR *)strm->state; 110118293Ssimokawa strm->total_in = strm->total_out = state->total = 0; 111118293Ssimokawa strm->msg = Z_NULL; 112118293Ssimokawa strm->adler = 1; /* to support ill-conceived Java test suite */ 113118293Ssimokawa state->mode = HEAD; 114118293Ssimokawa state->last = 0; 115118293Ssimokawa state->havedict = 0; 116118293Ssimokawa state->wsize = 0; 117118293Ssimokawa state->whave = 0; 118118293Ssimokawa state->hold = 0; 119118293Ssimokawa state->bits = 0; 120118293Ssimokawa state->lencode = state->distcode = state->next = state->codes; 121118293Ssimokawa Tracev((stderr, "inflate: reset\n")); 122118293Ssimokawa return Z_OK; 123118293Ssimokawa} 124118293Ssimokawa 125118293Ssimokawaint ZEXPORT inflateInit2_(strm, windowBits, version, stream_size) 126118293Ssimokawaz_streamp strm; 127118293Ssimokawaint windowBits; 128118293Ssimokawaconst char *version; 129118293Ssimokawaint stream_size; 130118293Ssimokawa{ 131118293Ssimokawa struct inflate_state FAR *state; 132118293Ssimokawa 133118293Ssimokawa if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 134118293Ssimokawa stream_size != (int)(sizeof(z_stream))) 135118293Ssimokawa return Z_VERSION_ERROR; 136118293Ssimokawa if (strm == Z_NULL) return Z_STREAM_ERROR; 137118293Ssimokawa strm->msg = Z_NULL; /* in case we return an error */ 138118293Ssimokawa if (strm->zalloc == (alloc_func)0) { 139118293Ssimokawa strm->zalloc = zcalloc; 140118293Ssimokawa strm->opaque = (voidpf)0; 141118293Ssimokawa } 142118293Ssimokawa if (strm->zfree == (free_func)0) strm->zfree = zcfree; 143118293Ssimokawa state = (struct inflate_state FAR *) 144118293Ssimokawa ZALLOC(strm, 1, sizeof(struct inflate_state)); 145118293Ssimokawa if (state == Z_NULL) return Z_MEM_ERROR; 146118293Ssimokawa Tracev((stderr, "inflate: allocated\n")); 147118293Ssimokawa strm->state = (voidpf)state; 148118293Ssimokawa if (windowBits < 0) { 149118293Ssimokawa state->wrap = 0; 150118293Ssimokawa windowBits = -windowBits; 151118293Ssimokawa } 152118293Ssimokawa else { 153118293Ssimokawa state->wrap = (windowBits >> 4) + 1; 154118293Ssimokawa#ifdef GUNZIP 155118293Ssimokawa if (windowBits < 48) windowBits &= 15; 156118293Ssimokawa#endif 157118293Ssimokawa } 158118293Ssimokawa if (windowBits < 8 || windowBits > 15) { 159118293Ssimokawa ZFREE(strm, state); 160118293Ssimokawa strm->state = Z_NULL; 161118293Ssimokawa return Z_STREAM_ERROR; 162118293Ssimokawa } 163118293Ssimokawa state->wbits = (unsigned)windowBits; 164118293Ssimokawa state->window = Z_NULL; 165118293Ssimokawa return inflateReset(strm); 166118293Ssimokawa} 167118293Ssimokawa 168118293Ssimokawaint ZEXPORT inflateInit_(strm, version, stream_size) 169106813Ssimokawaz_streamp strm; 170106813Ssimokawaconst char *version; 171106813Ssimokawaint stream_size; 172106813Ssimokawa{ 173118293Ssimokawa return inflateInit2_(strm, DEF_WBITS, version, stream_size); 174118293Ssimokawa} 175118293Ssimokawa 176106813Ssimokawa/* 177106813Ssimokawa Return state with length and distance decoding tables and index sizes set to 178106813Ssimokawa fixed code decoding. Normally this returns fixed tables from inffixed.h. 179118293Ssimokawa If BUILDFIXED is defined, then instead this routine builds the tables the 180118455Ssimokawa first time it's called, and returns those tables the first time and 181118455Ssimokawa thereafter. This reduces the size of the code by about 2K bytes, in 182118455Ssimokawa exchange for a little execution time. However, BUILDFIXED should not be 183118455Ssimokawa used for threaded applications, since the rewriting of the tables and virgin 184118293Ssimokawa may not be thread-safe. 185118293Ssimokawa */ 186118293Ssimokawalocal void fixedtables(state) 187118455Ssimokawastruct inflate_state FAR *state; 188118455Ssimokawa{ 189118293Ssimokawa#ifdef BUILDFIXED 190118293Ssimokawa static int virgin = 1; 191118293Ssimokawa static code *lenfix, *distfix; 192106813Ssimokawa static code fixed[544]; 193106813Ssimokawa 194106813Ssimokawa /* build fixed huffman tables if first call (may not be thread safe) */ 195106813Ssimokawa if (virgin) { 196106813Ssimokawa unsigned sym, bits; 197106813Ssimokawa static code *next; 198106813Ssimokawa 199118293Ssimokawa /* literal/length table */ 200118293Ssimokawa sym = 0; 201106813Ssimokawa while (sym < 144) state->lens[sym++] = 8; 202106813Ssimokawa while (sym < 256) state->lens[sym++] = 9; 203106813Ssimokawa while (sym < 280) state->lens[sym++] = 7; 204106813Ssimokawa while (sym < 288) state->lens[sym++] = 8; 205106813Ssimokawa next = fixed; 206106813Ssimokawa lenfix = next; 207106813Ssimokawa bits = 9; 208106813Ssimokawa inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); 209106813Ssimokawa 210118293Ssimokawa /* distance table */ 211118293Ssimokawa sym = 0; 212118293Ssimokawa while (sym < 32) state->lens[sym++] = 5; 213118293Ssimokawa distfix = next; 214118293Ssimokawa bits = 5; 215118293Ssimokawa inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); 216118293Ssimokawa 217118293Ssimokawa /* do this just once */ 218118293Ssimokawa virgin = 0; 219118293Ssimokawa } 220118293Ssimokawa#else /* !BUILDFIXED */ 221118293Ssimokawa# include "inffixed.h" 222118293Ssimokawa#endif /* BUILDFIXED */ 223118293Ssimokawa state->lencode = lenfix; 224118293Ssimokawa state->lenbits = 9; 225118293Ssimokawa state->distcode = distfix; 226118293Ssimokawa state->distbits = 5; 227118293Ssimokawa} 228118293Ssimokawa 229118293Ssimokawa#ifdef MAKEFIXED 230118293Ssimokawa#include <stdio.h> 231118293Ssimokawa 232118293Ssimokawa/* 233118293Ssimokawa Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also 234118293Ssimokawa defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 235118293Ssimokawa those tables to stdout, which would be piped to inffixed.h. A small program 236118293Ssimokawa can simply call makefixed to do this: 237118293Ssimokawa 238118293Ssimokawa void makefixed(void); 239118293Ssimokawa 240118293Ssimokawa int main(void) 241118293Ssimokawa { 242118293Ssimokawa makefixed(); 243118293Ssimokawa return 0; 244106813Ssimokawa } 245118293Ssimokawa 246118293Ssimokawa Then that can be linked with zlib built with MAKEFIXED defined and run: 247106813Ssimokawa 248118293Ssimokawa a.out > inffixed.h 249118293Ssimokawa */ 250118293Ssimokawavoid makefixed() 251118293Ssimokawa{ 252118293Ssimokawa unsigned low, size; 253118293Ssimokawa struct inflate_state state; 254118293Ssimokawa 255118293Ssimokawa fixedtables(&state); 256118293Ssimokawa puts(" /* inffixed.h -- table for decoding fixed codes"); 257118293Ssimokawa puts(" * Generated automatically by makefixed()."); 258118293Ssimokawa puts(" */"); 259106813Ssimokawa puts(""); 260118293Ssimokawa puts(" /* WARNING: this file should *not* be used by applications."); 261118293Ssimokawa puts(" It is part of the implementation of this library and is"); 262106813Ssimokawa puts(" subject to change. Applications should only use zlib.h."); 263106813Ssimokawa puts(" */"); 264106813Ssimokawa puts(""); 265106813Ssimokawa size = 1U << 9; 266106813Ssimokawa printf(" static const code lenfix[%u] = {", size); 267106813Ssimokawa low = 0; 268106813Ssimokawa for (;;) { 269106813Ssimokawa if ((low % 7) == 0) printf("\n "); 270106813Ssimokawa printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits, 271106813Ssimokawa state.lencode[low].val); 272106813Ssimokawa if (++low == size) break; 273106813Ssimokawa putchar(','); 274106813Ssimokawa } 275106813Ssimokawa puts("\n };"); 276106813Ssimokawa size = 1U << 5; 277106813Ssimokawa printf("\n static const code distfix[%u] = {", size); 278106813Ssimokawa low = 0; 279106813Ssimokawa for (;;) { 280120660Ssimokawa if ((low % 6) == 0) printf("\n "); 281106813Ssimokawa printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits, 282106813Ssimokawa state.distcode[low].val); 283106813Ssimokawa if (++low == size) break; 284118293Ssimokawa putchar(','); 285118293Ssimokawa } 286118293Ssimokawa puts("\n };"); 287106813Ssimokawa} 288106813Ssimokawa#endif /* MAKEFIXED */ 289106813Ssimokawa 290113584Ssimokawa/* 291109988Ssimokawa Update the window with the last wsize (normally 32K) bytes written before 292106813Ssimokawa returning. If window does not exist yet, create it. This is only called 293109988Ssimokawa when a window is already in use, or when output has been written during this 294106813Ssimokawa inflate call, but the end of the deflate stream has not been reached yet. 295106813Ssimokawa It is also called to create a window for dictionary data when a dictionary 296106813Ssimokawa is loaded. 297106813Ssimokawa 298106813Ssimokawa Providing output buffers larger than 32K to inflate() should provide a speed 299106813Ssimokawa advantage, since only the last 32K of output is copied to the sliding window 300109988Ssimokawa upon return from inflate(), and since all distances after the first 32K of 301109988Ssimokawa output will fall in the output data, making match copies simpler and faster. 302109988Ssimokawa The advantage may be dependent on the size of the processor's data caches. 303106813Ssimokawa */ 304106813Ssimokawalocal int updatewindow(strm, out) 305111748Sdesz_streamp strm; 306109988Ssimokawaunsigned out; 307109988Ssimokawa{ 308109988Ssimokawa struct inflate_state FAR *state; 309109988Ssimokawa unsigned copy, dist; 310106813Ssimokawa 311109988Ssimokawa state = (struct inflate_state FAR *)strm->state; 312109988Ssimokawa 313120660Ssimokawa /* if it hasn't been done already, allocate space for the window */ 314113584Ssimokawa if (state->window == Z_NULL) { 315106813Ssimokawa state->window = (unsigned char FAR *) 316106813Ssimokawa ZALLOC(strm, 1U << state->wbits, 317106813Ssimokawa sizeof(unsigned char)); 318106813Ssimokawa if (state->window == Z_NULL) return 1; 319120660Ssimokawa } 320120660Ssimokawa 321106813Ssimokawa /* if window not in use yet, initialize */ 322120660Ssimokawa if (state->wsize == 0) { 323120660Ssimokawa state->wsize = 1U << state->wbits; 324113584Ssimokawa state->write = 0; 325120660Ssimokawa state->whave = 0; 326106813Ssimokawa } 327109988Ssimokawa 328109988Ssimokawa /* copy state->wsize or less output bytes into the circular window */ 329113584Ssimokawa copy = out - strm->avail_out; 330113584Ssimokawa if (copy >= state->wsize) { 331106813Ssimokawa zmemcpy(state->window, strm->next_out - state->wsize, state->wsize); 332106813Ssimokawa state->write = 0; 333113584Ssimokawa state->whave = state->wsize; 334106813Ssimokawa } 335106813Ssimokawa else { 336106813Ssimokawa dist = state->wsize - state->write; 337109988Ssimokawa if (dist > copy) dist = copy; 338113584Ssimokawa zmemcpy(state->window + state->write, strm->next_out - copy, dist); 339106813Ssimokawa copy -= dist; 340106813Ssimokawa if (copy) { 341106813Ssimokawa zmemcpy(state->window, strm->next_out - copy, copy); 342106813Ssimokawa state->write = copy; 343106813Ssimokawa state->whave = state->wsize; 344118293Ssimokawa } 345106813Ssimokawa else { 346106813Ssimokawa state->write += dist; 347109988Ssimokawa if (state->write == state->wsize) state->write = 0; 348109988Ssimokawa if (state->whave < state->wsize) state->whave += dist; 349109988Ssimokawa } 350109988Ssimokawa } 351106813Ssimokawa return 0; 352106813Ssimokawa} 353106813Ssimokawa 354106813Ssimokawa/* Macros for inflate(): */ 355106813Ssimokawa 356106813Ssimokawa/* check function to use adler32() for zlib or crc32() for gzip */ 357106813Ssimokawa#ifdef GUNZIP 358106813Ssimokawa# define UPDATE(check, buf, len) \ 359106813Ssimokawa (state->flags ? crc32(check, buf, len) : adler32(check, buf, len)) 360106813Ssimokawa#else 361106813Ssimokawa# define UPDATE(check, buf, len) adler32(check, buf, len) 362106813Ssimokawa#endif 363106813Ssimokawa 364106813Ssimokawa/* check macros for header crc */ 365106813Ssimokawa#ifdef GUNZIP 366106813Ssimokawa# define CRC2(check, word) \ 367120660Ssimokawa do { \ 368106813Ssimokawa hbuf[0] = (unsigned char)(word); \ 369106813Ssimokawa hbuf[1] = (unsigned char)((word) >> 8); \ 370106813Ssimokawa check = crc32(check, hbuf, 2); \ 371118293Ssimokawa } while (0) 372118293Ssimokawa 373118293Ssimokawa# define CRC4(check, word) \ 374106813Ssimokawa do { \ 375113802Ssimokawa hbuf[0] = (unsigned char)(word); \ 376113802Ssimokawa hbuf[1] = (unsigned char)((word) >> 8); \ 377113802Ssimokawa hbuf[2] = (unsigned char)((word) >> 16); \ 378106813Ssimokawa hbuf[3] = (unsigned char)((word) >> 24); \ 379113802Ssimokawa check = crc32(check, hbuf, 4); \ 380106813Ssimokawa } while (0) 381113802Ssimokawa#endif 382113802Ssimokawa 383113802Ssimokawa/* Load registers with state in inflate() for speed */ 384118293Ssimokawa#define LOAD() \ 385113802Ssimokawa do { \ 386113802Ssimokawa put = strm->next_out; \ 387113802Ssimokawa left = strm->avail_out; \ 388113802Ssimokawa next = strm->next_in; \ 389113802Ssimokawa have = strm->avail_in; \ 390109988Ssimokawa hold = state->hold; \ 391113802Ssimokawa bits = state->bits; \ 392113802Ssimokawa } while (0) 393106813Ssimokawa 394106813Ssimokawa/* Restore state from registers in inflate() */ 395106813Ssimokawa#define RESTORE() \ 396113802Ssimokawa do { \ 397113802Ssimokawa strm->next_out = put; \ 398113802Ssimokawa strm->avail_out = left; \ 399113802Ssimokawa strm->next_in = next; \ 400113802Ssimokawa strm->avail_in = have; \ 401113802Ssimokawa state->hold = hold; \ 402113802Ssimokawa state->bits = bits; \ 403113802Ssimokawa } while (0) 404113802Ssimokawa 405113802Ssimokawa/* Clear the input bit accumulator */ 406113802Ssimokawa#define INITBITS() \ 407118293Ssimokawa do { \ 408113802Ssimokawa hold = 0; \ 409113802Ssimokawa bits = 0; \ 410113802Ssimokawa } while (0) 411113802Ssimokawa 412113802Ssimokawa/* Get a byte of input into the bit accumulator, or return from inflate() 413113802Ssimokawa if there is no input available. */ 414106813Ssimokawa#define PULLBYTE() \ 415106813Ssimokawa do { \ 416106813Ssimokawa if (have == 0) goto inf_leave; \ 417106813Ssimokawa have--; \ 418106813Ssimokawa hold += (unsigned long)(*next++) << bits; \ 419106813Ssimokawa bits += 8; \ 420106813Ssimokawa } while (0) 421106813Ssimokawa 422118293Ssimokawa/* Assure that there are at least n bits in the bit accumulator. If there is 423118293Ssimokawa not enough available input to do that, then return from inflate(). */ 424106813Ssimokawa#define NEEDBITS(n) \ 425113584Ssimokawa do { \ 426106813Ssimokawa while (bits < (unsigned)(n)) \ 427106813Ssimokawa PULLBYTE(); \ 428106813Ssimokawa } while (0) 429106813Ssimokawa 430106813Ssimokawa/* Return the low n bits of the bit accumulator (n < 16) */ 431109814Ssimokawa#define BITS(n) \ 432117473Ssimokawa ((unsigned)hold & ((1U << (n)) - 1)) 433106813Ssimokawa 434106813Ssimokawa/* Remove n bits from the bit accumulator */ 435106813Ssimokawa#define DROPBITS(n) \ 436106813Ssimokawa do { \ 437106813Ssimokawa hold >>= (n); \ 438106813Ssimokawa bits -= (unsigned)(n); \ 439106813Ssimokawa } while (0) 440106813Ssimokawa 441106813Ssimokawa/* Remove zero to seven bits as needed to go to a byte boundary */ 442106813Ssimokawa#define BYTEBITS() \ 443106813Ssimokawa do { \ 444106813Ssimokawa hold >>= bits & 7; \ 445106813Ssimokawa bits -= bits & 7; \ 446106813Ssimokawa } while (0) 447118293Ssimokawa 448118293Ssimokawa/* Reverse the bytes in a 32-bit value */ 449118293Ssimokawa#define REVERSE(q) \ 450118293Ssimokawa ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \ 451118293Ssimokawa (((q) & 0xff00) << 8) + (((q) & 0xff) << 24)) 452118293Ssimokawa 453106813Ssimokawa/* 454106813Ssimokawa inflate() uses a state machine to process as much input data and generate as 455118293Ssimokawa much output data as possible before returning. The state machine is 456118293Ssimokawa structured roughly as follows: 457118293Ssimokawa 458118293Ssimokawa for (;;) switch (state) { 459118293Ssimokawa ... 460118293Ssimokawa case STATEn: 461118293Ssimokawa if (not enough input data or output space to make progress) 462118293Ssimokawa return; 463118293Ssimokawa ... make progress ... 464118293Ssimokawa state = STATEm; 465118293Ssimokawa break; 466118293Ssimokawa ... 467118293Ssimokawa } 468118293Ssimokawa 469118293Ssimokawa so when inflate() is called again, the same case is attempted again, and 470118293Ssimokawa if the appropriate resources are provided, the machine proceeds to the 471118293Ssimokawa next state. The NEEDBITS() macro is usually the way the state evaluates 472118293Ssimokawa whether it can proceed or should return. NEEDBITS() does the return if 473118293Ssimokawa the requested bits are not available. The typical use of the BITS macros 474106813Ssimokawa is: 475106813Ssimokawa 476118293Ssimokawa NEEDBITS(n); 477118293Ssimokawa ... do something with BITS(n) ... 478118293Ssimokawa DROPBITS(n); 479118293Ssimokawa 480118293Ssimokawa where NEEDBITS(n) either returns from inflate() if there isn't enough 481106813Ssimokawa input left to load n bits into the accumulator, or it continues. BITS(n) 482106813Ssimokawa gives the low n bits in the accumulator. When done, DROPBITS(n) drops 483118293Ssimokawa the low n bits off the accumulator. INITBITS() clears the accumulator 484118293Ssimokawa and sets the number of available bits to zero. BYTEBITS() discards just 485118293Ssimokawa enough bits to put the accumulator on a byte boundary. After BYTEBITS() 486118293Ssimokawa and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 487118293Ssimokawa 488118293Ssimokawa NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 489118293Ssimokawa if there is no input available. The decoding of variable length codes uses 490118293Ssimokawa PULLBYTE() directly in order to pull just enough bytes to decode the next 491118293Ssimokawa code, and no more. 492118293Ssimokawa 493118293Ssimokawa Some states loop until they get enough input, making sure that enough 494118293Ssimokawa state information is maintained to continue the loop where it left off 495118293Ssimokawa if NEEDBITS() returns in the loop. For example, want, need, and keep 496118293Ssimokawa would all have to actually be part of the saved state in case NEEDBITS() 497118293Ssimokawa returns: 498118293Ssimokawa 499118293Ssimokawa case STATEw: 500118293Ssimokawa while (want < need) { 501118293Ssimokawa NEEDBITS(n); 502118293Ssimokawa keep[want++] = BITS(n); 503106813Ssimokawa DROPBITS(n); 504106813Ssimokawa } 505118293Ssimokawa state = STATEx; 506118293Ssimokawa case STATEx: 507118293Ssimokawa 508118293Ssimokawa As shown above, if the next state is also the next case, then the break 509118293Ssimokawa is omitted. 510106813Ssimokawa 511106813Ssimokawa A state may also return if there is not enough output space available to 512118293Ssimokawa complete that state. Those states are copying stored data, writing a 513106813Ssimokawa literal byte, and copying a matching string. 514106813Ssimokawa 515118293Ssimokawa When returning, a "goto inf_leave" is used to update the total counters, 516118293Ssimokawa update the check value, and determine whether any progress has been made 517118293Ssimokawa during that inflate() call in order to return the proper return code. 518118293Ssimokawa Progress is defined as a change in either strm->avail_in or strm->avail_out. 519118293Ssimokawa When there is a window, goto inf_leave will update the window with the last 520118293Ssimokawa output written. If a goto inf_leave occurs in the middle of decompression 521118293Ssimokawa and there is no window currently, goto inf_leave will create one and copy 522118293Ssimokawa output to the window for the next call of inflate(). 523118293Ssimokawa 524118293Ssimokawa In this implementation, the flush parameter of inflate() only affects the 525118293Ssimokawa return code (per zlib.h). inflate() always writes as much as possible to 526118293Ssimokawa strm->next_out, given the space available and the provided input--the effect 527106813Ssimokawa documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 528106813Ssimokawa the allocation of and copying into a sliding window until necessary, which 529120660Ssimokawa provides the effect documented in zlib.h for Z_FINISH when the entire input 530120660Ssimokawa stream available. So the only thing the flush parameter actually does is: 531121466Ssimokawa when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 532120660Ssimokawa will return Z_BUF_ERROR if it has not reached the end of the stream. 533106813Ssimokawa */ 534121466Ssimokawa 535121466Ssimokawaint ZEXPORT inflate(strm, flush) 536121466Ssimokawaz_streamp strm; 537121466Ssimokawaint flush; 538121466Ssimokawa{ 539121466Ssimokawa struct inflate_state FAR *state; 540121466Ssimokawa unsigned char FAR *next; /* next input */ 541121466Ssimokawa unsigned char FAR *put; /* next output */ 542121466Ssimokawa unsigned have, left; /* available input and output */ 543106813Ssimokawa unsigned long hold; /* bit buffer */ 544106813Ssimokawa unsigned bits; /* bits in bit buffer */ 545106813Ssimokawa unsigned in, out; /* save starting available input and output */ 546106813Ssimokawa unsigned copy; /* number of stored or match bytes to copy */ 547110072Ssimokawa unsigned char FAR *from; /* where to copy match bytes from */ 548110582Ssimokawa code this; /* current decoding table entry */ 549106813Ssimokawa code last; /* parent table entry */ 550108782Ssimokawa unsigned len; /* length to copy for repeats, bits to drop */ 551108782Ssimokawa int ret; /* return code */ 552106813Ssimokawa#ifdef GUNZIP 553121466Ssimokawa unsigned char hbuf[4]; /* buffer for gzip header crc calculation */ 554106813Ssimokawa#endif 555120660Ssimokawa static const unsigned short order[19] = /* permutation of code lengths */ 556106813Ssimokawa {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 557106813Ssimokawa 558106813Ssimokawa if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 559106813Ssimokawa (strm->next_in == Z_NULL && strm->avail_in != 0)) 560106813Ssimokawa return Z_STREAM_ERROR; 561106813Ssimokawa 562106813Ssimokawa state = (struct inflate_state FAR *)strm->state; 563106813Ssimokawa if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 564121466Ssimokawa LOAD(); 565120660Ssimokawa in = have; 566121466Ssimokawa out = left; 567120660Ssimokawa ret = Z_OK; 568121466Ssimokawa for (;;) 569121466Ssimokawa switch (state->mode) { 570106813Ssimokawa case HEAD: 571121466Ssimokawa if (state->wrap == 0) { 572121466Ssimokawa state->mode = TYPEDO; 573121466Ssimokawa break; 574121466Ssimokawa } 575121466Ssimokawa NEEDBITS(16); 576121466Ssimokawa#ifdef GUNZIP 577121466Ssimokawa if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */ 578121466Ssimokawa state->check = crc32(0L, Z_NULL, 0); 579106813Ssimokawa CRC2(state->check, hold); 580121466Ssimokawa INITBITS(); 581121466Ssimokawa state->mode = FLAGS; 582121466Ssimokawa break; 583121466Ssimokawa } 584121466Ssimokawa state->flags = 0; /* expect zlib header */ 585121466Ssimokawa if (!(state->wrap & 1) || /* check if zlib header allowed */ 586121466Ssimokawa#else 587121466Ssimokawa if ( 588121466Ssimokawa#endif 589121466Ssimokawa ((BITS(8) << 8) + (hold >> 8)) % 31) { 590121466Ssimokawa strm->msg = (char *)"incorrect header check"; 591121466Ssimokawa state->mode = BAD; 592121466Ssimokawa break; 593120660Ssimokawa } 594106813Ssimokawa if (BITS(4) != Z_DEFLATED) { 595120660Ssimokawa strm->msg = (char *)"unknown compression method"; 596106813Ssimokawa state->mode = BAD; 597106813Ssimokawa break; 598106813Ssimokawa } 599106813Ssimokawa DROPBITS(4); 600106813Ssimokawa if (BITS(4) + 8 > state->wbits) { 601106813Ssimokawa strm->msg = (char *)"invalid window size"; 602106813Ssimokawa state->mode = BAD; 603106813Ssimokawa break; 604106813Ssimokawa } 605106813Ssimokawa Tracev((stderr, "inflate: zlib header ok\n")); 606106813Ssimokawa strm->adler = state->check = adler32(0L, Z_NULL, 0); 607118293Ssimokawa state->mode = hold & 0x200 ? DICTID : TYPE; 608110195Ssimokawa INITBITS(); 609106813Ssimokawa break; 610106813Ssimokawa#ifdef GUNZIP 611106813Ssimokawa case FLAGS: 612106813Ssimokawa NEEDBITS(16); 613106813Ssimokawa state->flags = (int)(hold); 614106813Ssimokawa if ((state->flags & 0xff) != Z_DEFLATED) { 615106813Ssimokawa strm->msg = (char *)"unknown compression method"; 616106813Ssimokawa state->mode = BAD; 617106813Ssimokawa break; 618106813Ssimokawa } 619110195Ssimokawa if (state->flags & 0xe000) { 620106813Ssimokawa strm->msg = (char *)"unknown header flags set"; 621106813Ssimokawa state->mode = BAD; 622106813Ssimokawa break; 623106813Ssimokawa } 624120660Ssimokawa if (state->flags & 0x0200) CRC2(state->check, hold); 625120660Ssimokawa INITBITS(); 626120660Ssimokawa state->mode = TIME; 627118293Ssimokawa case TIME: 628118293Ssimokawa NEEDBITS(32); 629113584Ssimokawa if (state->flags & 0x0200) CRC4(state->check, hold); 630106813Ssimokawa INITBITS(); 631120660Ssimokawa state->mode = OS; 632110269Ssimokawa case OS: 633106813Ssimokawa NEEDBITS(16); 634106813Ssimokawa if (state->flags & 0x0200) CRC2(state->check, hold); 635106813Ssimokawa INITBITS(); 636106813Ssimokawa state->mode = EXLEN; 637106813Ssimokawa case EXLEN: 638106813Ssimokawa if (state->flags & 0x0400) { 639113584Ssimokawa NEEDBITS(16); 640113584Ssimokawa state->length = (unsigned)(hold); 641113584Ssimokawa if (state->flags & 0x0200) CRC2(state->check, hold); 642113584Ssimokawa INITBITS(); 643113584Ssimokawa } 644106813Ssimokawa state->mode = EXTRA; 645106813Ssimokawa case EXTRA: 646106813Ssimokawa if (state->flags & 0x0400) { 647109814Ssimokawa copy = state->length; 648109814Ssimokawa if (copy > have) copy = have; 649109814Ssimokawa if (copy) { 650109814Ssimokawa if (state->flags & 0x0200) 651109814Ssimokawa state->check = crc32(state->check, next, copy); 652109814Ssimokawa have -= copy; 653109814Ssimokawa next += copy; 654110193Ssimokawa state->length -= copy; 655109814Ssimokawa } 656109814Ssimokawa if (state->length) goto inf_leave; 657109814Ssimokawa } 658109814Ssimokawa state->mode = NAME; 659109814Ssimokawa case NAME: 660109814Ssimokawa if (state->flags & 0x0800) { 661109814Ssimokawa if (have == 0) goto inf_leave; 662106813Ssimokawa copy = 0; 663106813Ssimokawa do { 664106813Ssimokawa len = (unsigned)(next[copy++]); 665106813Ssimokawa } while (len && copy < have); 666109814Ssimokawa if (state->flags & 0x02000) 667106813Ssimokawa state->check = crc32(state->check, next, copy); 668106813Ssimokawa have -= copy; 669106813Ssimokawa next += copy; 670106813Ssimokawa if (len) goto inf_leave; 671106813Ssimokawa } 672106813Ssimokawa state->mode = COMMENT; 673110193Ssimokawa case COMMENT: 674110193Ssimokawa if (state->flags & 0x1000) { 675106813Ssimokawa if (have == 0) goto inf_leave; 676106813Ssimokawa copy = 0; 677117473Ssimokawa do { 678117473Ssimokawa len = (unsigned)(next[copy++]); 679117473Ssimokawa } while (len && copy < have); 680117473Ssimokawa if (state->flags & 0x02000) 681117473Ssimokawa state->check = crc32(state->check, next, copy); 682117473Ssimokawa have -= copy; 683117473Ssimokawa next += copy; 684117473Ssimokawa if (len) goto inf_leave; 685117473Ssimokawa } 686117473Ssimokawa state->mode = HCRC; 687117473Ssimokawa case HCRC: 688117473Ssimokawa if (state->flags & 0x0200) { 689117473Ssimokawa NEEDBITS(16); 690117473Ssimokawa if (hold != (state->check & 0xffff)) { 691117473Ssimokawa strm->msg = (char *)"header crc mismatch"; 692117473Ssimokawa state->mode = BAD; 693117473Ssimokawa break; 694106813Ssimokawa } 695106813Ssimokawa INITBITS(); 696106813Ssimokawa } 697106813Ssimokawa strm->adler = state->check = crc32(0L, Z_NULL, 0); 698106813Ssimokawa state->mode = TYPE; 699117473Ssimokawa break; 700117473Ssimokawa#endif 701117473Ssimokawa case DICTID: 702117473Ssimokawa NEEDBITS(32); 703106813Ssimokawa strm->adler = state->check = REVERSE(hold); 704106813Ssimokawa INITBITS(); 705106813Ssimokawa state->mode = DICT; 706106813Ssimokawa case DICT: 707106813Ssimokawa if (state->havedict == 0) { 708106813Ssimokawa RESTORE(); 709106813Ssimokawa return Z_NEED_DICT; 710106813Ssimokawa } 711106813Ssimokawa strm->adler = state->check = adler32(0L, Z_NULL, 0); 712106813Ssimokawa state->mode = TYPE; 713118293Ssimokawa case TYPE: 714118293Ssimokawa if (flush == Z_BLOCK) goto inf_leave; 715106813Ssimokawa case TYPEDO: 716106813Ssimokawa if (state->last) { 717106813Ssimokawa BYTEBITS(); 718106813Ssimokawa state->mode = CHECK; 719106813Ssimokawa break; 720106813Ssimokawa } 721106813Ssimokawa NEEDBITS(3); 722106813Ssimokawa state->last = BITS(1); 723118293Ssimokawa DROPBITS(1); 724106813Ssimokawa switch (BITS(2)) { 725106813Ssimokawa case 0: /* stored block */ 726106813Ssimokawa Tracev((stderr, "inflate: stored block%s\n", 727118293Ssimokawa state->last ? " (last)" : "")); 728106813Ssimokawa state->mode = STORED; 729106813Ssimokawa break; 730118293Ssimokawa case 1: /* fixed block */ 731106813Ssimokawa fixedtables(state); 732106813Ssimokawa Tracev((stderr, "inflate: fixed codes block%s\n", 733106813Ssimokawa state->last ? " (last)" : "")); 734106813Ssimokawa state->mode = LEN; /* decode codes */ 735106813Ssimokawa break; 736106813Ssimokawa case 2: /* dynamic block */ 737106813Ssimokawa Tracev((stderr, "inflate: dynamic codes block%s\n", 738106813Ssimokawa state->last ? " (last)" : "")); 739106813Ssimokawa state->mode = TABLE; 740106813Ssimokawa break; 741106813Ssimokawa case 3: 742113584Ssimokawa strm->msg = (char *)"invalid block type"; 743111615Ssimokawa state->mode = BAD; 744111615Ssimokawa } 745113584Ssimokawa DROPBITS(2); 746111615Ssimokawa break; 747106813Ssimokawa case STORED: 748118455Ssimokawa BYTEBITS(); /* go to byte boundary */ 749106813Ssimokawa NEEDBITS(32); 750106813Ssimokawa if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 751106813Ssimokawa strm->msg = (char *)"invalid stored block lengths"; 752113584Ssimokawa state->mode = BAD; 753111615Ssimokawa break; 754111615Ssimokawa } 755111462Smux state->length = (unsigned)hold & 0xffff; 756111615Ssimokawa Tracev((stderr, "inflate: stored length %u\n", 757106813Ssimokawa state->length)); 758118455Ssimokawa INITBITS(); 759106813Ssimokawa state->mode = COPY; 760106813Ssimokawa case COPY: 761106813Ssimokawa copy = state->length; 762118455Ssimokawa if (copy) { 763120660Ssimokawa if (copy > have) copy = have; 764120660Ssimokawa if (copy > left) copy = left; 765120660Ssimokawa if (copy == 0) goto inf_leave; 766120660Ssimokawa zmemcpy(put, next, copy); 767120660Ssimokawa have -= copy; 768120660Ssimokawa next += copy; 769120660Ssimokawa left -= copy; 770120660Ssimokawa put += copy; 771120660Ssimokawa state->length -= copy; 772120660Ssimokawa break; 773120660Ssimokawa } 774120660Ssimokawa Tracev((stderr, "inflate: stored end\n")); 775120660Ssimokawa state->mode = TYPE; 776120660Ssimokawa break; 777120660Ssimokawa case TABLE: 778120660Ssimokawa NEEDBITS(14); 779120660Ssimokawa state->nlen = BITS(5) + 257; 780118455Ssimokawa DROPBITS(5); 781118455Ssimokawa state->ndist = BITS(5) + 1; 782118455Ssimokawa DROPBITS(5); 783118455Ssimokawa state->ncode = BITS(4) + 4; 784118455Ssimokawa DROPBITS(4); 785118455Ssimokawa#ifndef PKZIP_BUG_WORKAROUND 786118455Ssimokawa if (state->nlen > 286 || state->ndist > 30) { 787118455Ssimokawa strm->msg = (char *)"too many length or distance symbols"; 788118455Ssimokawa state->mode = BAD; 789118455Ssimokawa break; 790118455Ssimokawa } 791118455Ssimokawa#endif 792118455Ssimokawa Tracev((stderr, "inflate: table sizes ok\n")); 793118455Ssimokawa state->have = 0; 794118455Ssimokawa state->mode = LENLENS; 795118455Ssimokawa case LENLENS: 796118455Ssimokawa while (state->have < state->ncode) { 797118455Ssimokawa NEEDBITS(3); 798118455Ssimokawa state->lens[order[state->have++]] = (unsigned short)BITS(3); 799118455Ssimokawa DROPBITS(3); 800118455Ssimokawa } 801118455Ssimokawa while (state->have < 19) 802118455Ssimokawa state->lens[order[state->have++]] = 0; 803118455Ssimokawa state->next = state->codes; 804118455Ssimokawa state->lencode = (code const FAR *)(state->next); 805118455Ssimokawa state->lenbits = 7; 806118455Ssimokawa ret = inflate_table(CODES, state->lens, 19, &(state->next), 807118455Ssimokawa &(state->lenbits), state->work); 808118455Ssimokawa if (ret) { 809118455Ssimokawa strm->msg = (char *)"invalid code lengths set"; 810118455Ssimokawa state->mode = BAD; 811118455Ssimokawa break; 812118455Ssimokawa } 813118455Ssimokawa Tracev((stderr, "inflate: code lengths ok\n")); 814118455Ssimokawa state->have = 0; 815118455Ssimokawa state->mode = CODELENS; 816118455Ssimokawa case CODELENS: 817118455Ssimokawa while (state->have < state->nlen + state->ndist) { 818118455Ssimokawa for (;;) { 819118455Ssimokawa this = state->lencode[BITS(state->lenbits)]; 820118455Ssimokawa if ((unsigned)(this.bits) <= bits) break; 821118455Ssimokawa PULLBYTE(); 822118455Ssimokawa } 823118455Ssimokawa if (this.val < 16) { 824118455Ssimokawa NEEDBITS(this.bits); 825118455Ssimokawa DROPBITS(this.bits); 826118455Ssimokawa state->lens[state->have++] = this.val; 827118455Ssimokawa } 828118455Ssimokawa else { 829118455Ssimokawa if (this.val == 16) { 830118455Ssimokawa NEEDBITS(this.bits + 2); 831118455Ssimokawa DROPBITS(this.bits); 832118455Ssimokawa if (state->have == 0) { 833118455Ssimokawa strm->msg = (char *)"invalid bit length repeat"; 834118455Ssimokawa state->mode = BAD; 835120624Ssimokawa break; 836118455Ssimokawa } 837118455Ssimokawa len = state->lens[state->have - 1]; 838118455Ssimokawa copy = 3 + BITS(2); 839118455Ssimokawa DROPBITS(2); 840118455Ssimokawa } 841118455Ssimokawa else if (this.val == 17) { 842118455Ssimokawa NEEDBITS(this.bits + 3); 843118455Ssimokawa DROPBITS(this.bits); 844118455Ssimokawa len = 0; 845118455Ssimokawa copy = 3 + BITS(3); 846118455Ssimokawa DROPBITS(3); 847118455Ssimokawa } 848118455Ssimokawa else { 849118455Ssimokawa NEEDBITS(this.bits + 7); 850118455Ssimokawa DROPBITS(this.bits); 851118455Ssimokawa len = 0; 852118455Ssimokawa copy = 11 + BITS(7); 853118455Ssimokawa DROPBITS(7); 854118455Ssimokawa } 855118455Ssimokawa if (state->have + copy > state->nlen + state->ndist) { 856118455Ssimokawa strm->msg = (char *)"invalid bit length repeat"; 857118455Ssimokawa state->mode = BAD; 858118455Ssimokawa break; 859118455Ssimokawa } 860118455Ssimokawa while (copy--) 861118455Ssimokawa state->lens[state->have++] = (unsigned short)len; 862118455Ssimokawa } 863 } 864 865 /* handle error breaks in while */ 866 if (state->mode == BAD) break; 867 868 /* build code tables */ 869 state->next = state->codes; 870 state->lencode = (code const FAR *)(state->next); 871 state->lenbits = 9; 872 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 873 &(state->lenbits), state->work); 874 if (ret) { 875 strm->msg = (char *)"invalid literal/lengths set"; 876 state->mode = BAD; 877 break; 878 } 879 state->distcode = (code const FAR *)(state->next); 880 state->distbits = 6; 881 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 882 &(state->next), &(state->distbits), state->work); 883 if (ret) { 884 strm->msg = (char *)"invalid distances set"; 885 state->mode = BAD; 886 break; 887 } 888 Tracev((stderr, "inflate: codes ok\n")); 889 state->mode = LEN; 890 case LEN: 891 if (have >= 6 && left >= 258) { 892 RESTORE(); 893 inflate_fast(strm, out); 894 LOAD(); 895 break; 896 } 897 for (;;) { 898 this = state->lencode[BITS(state->lenbits)]; 899 if ((unsigned)(this.bits) <= bits) break; 900 PULLBYTE(); 901 } 902 if (this.op && (this.op & 0xf0) == 0) { 903 last = this; 904 for (;;) { 905 this = state->lencode[last.val + 906 (BITS(last.bits + last.op) >> last.bits)]; 907 if ((unsigned)(last.bits + this.bits) <= bits) break; 908 PULLBYTE(); 909 } 910 DROPBITS(last.bits); 911 } 912 DROPBITS(this.bits); 913 state->length = (unsigned)this.val; 914 if ((int)(this.op) == 0) { 915 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 916 "inflate: literal '%c'\n" : 917 "inflate: literal 0x%02x\n", this.val)); 918 state->mode = LIT; 919 break; 920 } 921 if (this.op & 32) { 922 Tracevv((stderr, "inflate: end of block\n")); 923 state->mode = TYPE; 924 break; 925 } 926 if (this.op & 64) { 927 strm->msg = (char *)"invalid literal/length code"; 928 state->mode = BAD; 929 break; 930 } 931 state->extra = (unsigned)(this.op) & 15; 932 state->mode = LENEXT; 933 case LENEXT: 934 if (state->extra) { 935 NEEDBITS(state->extra); 936 state->length += BITS(state->extra); 937 DROPBITS(state->extra); 938 } 939 Tracevv((stderr, "inflate: length %u\n", state->length)); 940 state->mode = DIST; 941 case DIST: 942 for (;;) { 943 this = state->distcode[BITS(state->distbits)]; 944 if ((unsigned)(this.bits) <= bits) break; 945 PULLBYTE(); 946 } 947 if ((this.op & 0xf0) == 0) { 948 last = this; 949 for (;;) { 950 this = state->distcode[last.val + 951 (BITS(last.bits + last.op) >> last.bits)]; 952 if ((unsigned)(last.bits + this.bits) <= bits) break; 953 PULLBYTE(); 954 } 955 DROPBITS(last.bits); 956 } 957 DROPBITS(this.bits); 958 if (this.op & 64) { 959 strm->msg = (char *)"invalid distance code"; 960 state->mode = BAD; 961 break; 962 } 963 state->offset = (unsigned)this.val; 964 state->extra = (unsigned)(this.op) & 15; 965 state->mode = DISTEXT; 966 case DISTEXT: 967 if (state->extra) { 968 NEEDBITS(state->extra); 969 state->offset += BITS(state->extra); 970 DROPBITS(state->extra); 971 } 972 if (state->offset > state->whave + out - left) { 973 strm->msg = (char *)"invalid distance too far back"; 974 state->mode = BAD; 975 break; 976 } 977 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 978 state->mode = MATCH; 979 case MATCH: 980 if (left == 0) goto inf_leave; 981 copy = out - left; 982 if (state->offset > copy) { /* copy from window */ 983 copy = state->offset - copy; 984 if (copy > state->write) { 985 copy -= state->write; 986 from = state->window + (state->wsize - copy); 987 } 988 else 989 from = state->window + (state->write - copy); 990 if (copy > state->length) copy = state->length; 991 } 992 else { /* copy from output */ 993 from = put - state->offset; 994 copy = state->length; 995 } 996 if (copy > left) copy = left; 997 left -= copy; 998 state->length -= copy; 999 do { 1000 *put++ = *from++; 1001 } while (--copy); 1002 if (state->length == 0) state->mode = LEN; 1003 break; 1004 case LIT: 1005 if (left == 0) goto inf_leave; 1006 *put++ = (unsigned char)(state->length); 1007 left--; 1008 state->mode = LEN; 1009 break; 1010 case CHECK: 1011 if (state->wrap) { 1012 NEEDBITS(32); 1013 out -= left; 1014 strm->total_out += out; 1015 state->total += out; 1016 if (out) 1017 strm->adler = state->check = 1018 UPDATE(state->check, put - out, out); 1019 out = left; 1020 if (( 1021#ifdef GUNZIP 1022 state->flags ? hold : 1023#endif 1024 REVERSE(hold)) != state->check) { 1025 strm->msg = (char *)"incorrect data check"; 1026 state->mode = BAD; 1027 break; 1028 } 1029 INITBITS(); 1030 Tracev((stderr, "inflate: check matches trailer\n")); 1031 } 1032#ifdef GUNZIP 1033 state->mode = LENGTH; 1034 case LENGTH: 1035 if (state->wrap && state->flags) { 1036 NEEDBITS(32); 1037 if (hold != (state->total & 0xffffffffUL)) { 1038 strm->msg = (char *)"incorrect length check"; 1039 state->mode = BAD; 1040 break; 1041 } 1042 INITBITS(); 1043 Tracev((stderr, "inflate: length matches trailer\n")); 1044 } 1045#endif 1046 state->mode = DONE; 1047 case DONE: 1048 ret = Z_STREAM_END; 1049 goto inf_leave; 1050 case BAD: 1051 ret = Z_DATA_ERROR; 1052 goto inf_leave; 1053 case MEM: 1054 return Z_MEM_ERROR; 1055 case SYNC: 1056 default: 1057 return Z_STREAM_ERROR; 1058 } 1059 1060 /* 1061 Return from inflate(), updating the total counts and the check value. 1062 If there was no progress during the inflate() call, return a buffer 1063 error. Call updatewindow() to create and/or update the window state. 1064 Note: a memory error from inflate() is non-recoverable. 1065 */ 1066 inf_leave: 1067 RESTORE(); 1068 if (state->wsize || (state->mode < CHECK && out != strm->avail_out)) 1069 if (updatewindow(strm, out)) { 1070 state->mode = MEM; 1071 return Z_MEM_ERROR; 1072 } 1073 in -= strm->avail_in; 1074 out -= strm->avail_out; 1075 strm->total_in += in; 1076 strm->total_out += out; 1077 state->total += out; 1078 if (state->wrap && out) 1079 strm->adler = state->check = 1080 UPDATE(state->check, strm->next_out - out, out); 1081 strm->data_type = state->bits + (state->last ? 64 : 0) + 1082 (state->mode == TYPE ? 128 : 0); 1083 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1084 ret = Z_BUF_ERROR; 1085 return ret; 1086} 1087 1088int ZEXPORT inflateEnd(strm) 1089z_streamp strm; 1090{ 1091 struct inflate_state FAR *state; 1092 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1093 return Z_STREAM_ERROR; 1094 state = (struct inflate_state FAR *)strm->state; 1095 if (state->window != Z_NULL) ZFREE(strm, state->window); 1096 ZFREE(strm, strm->state); 1097 strm->state = Z_NULL; 1098 Tracev((stderr, "inflate: end\n")); 1099 return Z_OK; 1100} 1101 1102int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1103z_streamp strm; 1104const Bytef *dictionary; 1105uInt dictLength; 1106{ 1107 struct inflate_state FAR *state; 1108 unsigned long id; 1109 1110 /* check state */ 1111 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1112 state = (struct inflate_state FAR *)strm->state; 1113 if (state->mode != DICT) return Z_STREAM_ERROR; 1114 1115 /* check for correct dictionary id */ 1116 id = adler32(0L, Z_NULL, 0); 1117 id = adler32(id, dictionary, dictLength); 1118 if (id != state->check) return Z_DATA_ERROR; 1119 1120 /* copy dictionary to window */ 1121 if (updatewindow(strm, strm->avail_out)) { 1122 state->mode = MEM; 1123 return Z_MEM_ERROR; 1124 } 1125 if (dictLength > state->wsize) { 1126 zmemcpy(state->window, dictionary + dictLength - state->wsize, 1127 state->wsize); 1128 state->whave = state->wsize; 1129 } 1130 else { 1131 zmemcpy(state->window + state->wsize - dictLength, dictionary, 1132 dictLength); 1133 state->whave = dictLength; 1134 } 1135 state->havedict = 1; 1136 Tracev((stderr, "inflate: dictionary set\n")); 1137 return Z_OK; 1138} 1139 1140/* 1141 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1142 or when out of input. When called, *have is the number of pattern bytes 1143 found in order so far, in 0..3. On return *have is updated to the new 1144 state. If on return *have equals four, then the pattern was found and the 1145 return value is how many bytes were read including the last byte of the 1146 pattern. If *have is less than four, then the pattern has not been found 1147 yet and the return value is len. In the latter case, syncsearch() can be 1148 called again with more data and the *have state. *have is initialized to 1149 zero for the first call. 1150 */ 1151local unsigned syncsearch(have, buf, len) 1152unsigned FAR *have; 1153unsigned char FAR *buf; 1154unsigned len; 1155{ 1156 unsigned got; 1157 unsigned next; 1158 1159 got = *have; 1160 next = 0; 1161 while (next < len && got < 4) { 1162 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1163 got++; 1164 else if (buf[next]) 1165 got = 0; 1166 else 1167 got = 4 - got; 1168 next++; 1169 } 1170 *have = got; 1171 return next; 1172} 1173 1174int ZEXPORT inflateSync(strm) 1175z_streamp strm; 1176{ 1177 unsigned len; /* number of bytes to look at or looked at */ 1178 unsigned long in, out; /* temporary to save total_in and total_out */ 1179 unsigned char buf[4]; /* to restore bit buffer to byte string */ 1180 struct inflate_state FAR *state; 1181 1182 /* check parameters */ 1183 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1184 state = (struct inflate_state FAR *)strm->state; 1185 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 1186 1187 /* if first time, start search in bit buffer */ 1188 if (state->mode != SYNC) { 1189 state->mode = SYNC; 1190 state->hold <<= state->bits & 7; 1191 state->bits -= state->bits & 7; 1192 len = 0; 1193 while (state->bits >= 8) { 1194 buf[len++] = (unsigned char)(state->hold); 1195 state->hold >>= 8; 1196 state->bits -= 8; 1197 } 1198 state->have = 0; 1199 syncsearch(&(state->have), buf, len); 1200 } 1201 1202 /* search available input */ 1203 len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1204 strm->avail_in -= len; 1205 strm->next_in += len; 1206 strm->total_in += len; 1207 1208 /* return no joy or set up to restart inflate() on a new block */ 1209 if (state->have != 4) return Z_DATA_ERROR; 1210 in = strm->total_in; out = strm->total_out; 1211 inflateReset(strm); 1212 strm->total_in = in; strm->total_out = out; 1213 state->mode = TYPE; 1214 return Z_OK; 1215} 1216 1217/* 1218 Returns true if inflate is currently at the end of a block generated by 1219 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1220 implementation to provide an additional safety check. PPP uses 1221 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1222 block. When decompressing, PPP checks that at the end of input packet, 1223 inflate is waiting for these length bytes. 1224 */ 1225int ZEXPORT inflateSyncPoint(strm) 1226z_streamp strm; 1227{ 1228 struct inflate_state FAR *state; 1229 1230 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1231 state = (struct inflate_state FAR *)strm->state; 1232 return state->mode == STORED && state->bits == 0; 1233} 1234 1235int ZEXPORT inflateCopy(dest, source) 1236z_streamp dest; 1237z_streamp source; 1238{ 1239 struct inflate_state FAR *state; 1240 struct inflate_state FAR *copy; 1241 unsigned char FAR *window; 1242 1243 /* check input */ 1244 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1245 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1246 return Z_STREAM_ERROR; 1247 state = (struct inflate_state FAR *)source->state; 1248 1249 /* allocate space */ 1250 copy = (struct inflate_state FAR *) 1251 ZALLOC(source, 1, sizeof(struct inflate_state)); 1252 if (copy == Z_NULL) return Z_MEM_ERROR; 1253 window = Z_NULL; 1254 if (state->window != Z_NULL) { 1255 window = (unsigned char FAR *) 1256 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1257 if (window == Z_NULL) { 1258 ZFREE(source, copy); 1259 return Z_MEM_ERROR; 1260 } 1261 } 1262 1263 /* copy state */ 1264 *dest = *source; 1265 *copy = *state; 1266 copy->lencode = copy->codes + (state->lencode - state->codes); 1267 copy->distcode = copy->codes + (state->distcode - state->codes); 1268 copy->next = copy->codes + (state->next - state->codes); 1269 if (window != Z_NULL) 1270 zmemcpy(window, state->window, 1U << state->wbits); 1271 copy->window = window; 1272 dest->state = (voidpf)copy; 1273 return Z_OK; 1274} 1275