inflate.c revision 250224
1100966Siwasaki/* inflate.c -- zlib decompression 2100966Siwasaki * Copyright (C) 1995-2012 Mark Adler 3100966Siwasaki * For conditions of distribution and use, see copyright notice in zlib.h 4100966Siwasaki */ 5100966Siwasaki 6100966Siwasaki/* 7100966Siwasaki * Change history: 8217365Sjkim * 9245582Sjkim * 1.2.beta0 24 Nov 2002 10100966Siwasaki * - First version -- complete rewrite of inflate to simplify code, avoid 11100966Siwasaki * creation of window when not needed, minimize use of window when it is 12217365Sjkim * needed, make inffast.c even faster, implement gzip decoding, and to 13217365Sjkim * improve code readability and style over the previous zlib inflate code 14217365Sjkim * 15217365Sjkim * 1.2.beta1 25 Nov 2002 16217365Sjkim * - Use pointers for available input and output checking in inffast.c 17217365Sjkim * - Remove input and output counters in inffast.c 18217365Sjkim * - Change inffast.c entry and loop from avail_in >= 7 to >= 6 19217365Sjkim * - Remove unnecessary second byte pull from length extra in inffast.c 20217365Sjkim * - Unroll direct copy to three copies per loop in inffast.c 21217365Sjkim * 22217365Sjkim * 1.2.beta2 4 Dec 2002 23217365Sjkim * - Change external routine names to reduce potential conflicts 24217365Sjkim * - Correct filename to inffixed.h for fixed tables in inflate.c 25217365Sjkim * - Make hbuf[] unsigned char to match parameter type in inflate.c 26100966Siwasaki * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 27217365Sjkim * to avoid negation problem on Alphas (64 bit) in inflate.c 28217365Sjkim * 29217365Sjkim * 1.2.beta3 22 Dec 2002 30100966Siwasaki * - Add comments on state->bits assertion in inffast.c 31217365Sjkim * - Add comments on op field in inftrees.h 32217365Sjkim * - Fix bug in reuse of allocated window after inflateReset() 33217365Sjkim * - Remove bit fields--back to byte structure for speed 34217365Sjkim * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 35217365Sjkim * - Change post-increments to pre-increments in inflate_fast(), PPC biased? 36217365Sjkim * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 37217365Sjkim * - Make MATCH copy in inflate() much faster for when inflate_fast() not used 38217365Sjkim * - Use local copies of stream next and avail values, as well as local bit 39217365Sjkim * buffer and bit count in inflate()--for speed when inflate_fast() not used 40217365Sjkim * 41217365Sjkim * 1.2.beta4 1 Jan 2003 42217365Sjkim * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings 43217365Sjkim * - Move a comment on output buffer sizes from inffast.c to inflate.c 44100966Siwasaki * - Add comments in inffast.c to introduce the inflate_fast() routine 45100966Siwasaki * - Rearrange window copies in inflate_fast() for speed and simplification 46100966Siwasaki * - Unroll last copy for window match in inflate_fast() 47100966Siwasaki * - Use local copies of window variables in inflate_fast() for speed 48193341Sjkim * - Pull out common wnext == 0 case for speed in inflate_fast() 49193341Sjkim * - Make op and len in inflate_fast() unsigned for consistency 50193341Sjkim * - Add FAR to lcode and dcode declarations in inflate_fast() 51193341Sjkim * - Simplified bad distance check in inflate_fast() 52100966Siwasaki * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 53100966Siwasaki * source file infback.c to provide a call-back interface to inflate for 54100966Siwasaki * programs like gzip and unzip -- uses window as output buffer to avoid 55100966Siwasaki * window copying 56100966Siwasaki * 57193267Sjkim * 1.2.beta5 1 Jan 2003 58100966Siwasaki * - Improved inflateBack() interface to allow the caller to provide initial 59193267Sjkim * input in strm. 60193267Sjkim * - Fixed stored blocks bug in inflateBack() 61193267Sjkim * 62193267Sjkim * 1.2.beta6 4 Jan 2003 63193267Sjkim * - Added comments in inffast.c on effectiveness of POSTINC 64100966Siwasaki * - Typecasting all around to reduce compiler warnings 65100966Siwasaki * - Changed loops from while (1) or do {} while (1) to for (;;), again to 66100966Siwasaki * make compilers happy 67100966Siwasaki * - Changed type of window in inflateBackInit() to unsigned char * 68100966Siwasaki * 69151937Sjkim * 1.2.beta7 27 Jan 2003 70151937Sjkim * - Changed many types to unsigned or unsigned short to avoid warnings 71241973Sjkim * - Added inflateCopy() function 72100966Siwasaki * 73151937Sjkim * 1.2.0 9 Mar 2003 74241973Sjkim * - Changed inflateBack() interface to provide separate opaque descriptors 75100966Siwasaki * for the in() and out() functions 76100966Siwasaki * - Changed inflateBack() argument and in_func typedef to swap the length 77100966Siwasaki * and buffer address return values for the input function 78100966Siwasaki * - Check next_in and next_out for Z_NULL on entry to inflate() 79100966Siwasaki * 80241973Sjkim * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 81100966Siwasaki */ 82100966Siwasaki 83100966Siwasaki#include "zutil.h" 84100966Siwasaki#include "inftrees.h" 85100966Siwasaki#include "inflate.h" 86100966Siwasaki#include "inffast.h" 87100966Siwasaki 88100966Siwasaki#ifdef MAKEFIXED 89100966Siwasaki# ifndef BUILDFIXED 90100966Siwasaki# define BUILDFIXED 91100966Siwasaki# endif 92100966Siwasaki#endif 93100966Siwasaki 94100966Siwasaki/* function prototypes */ 95100966Siwasakilocal void fixedtables OF((struct inflate_state FAR *state)); 96100966Siwasakilocal int updatewindow OF((z_streamp strm, const unsigned char FAR *end, 97167802Sjkim unsigned copy)); 98100966Siwasaki#ifdef BUILDFIXED 99100966Siwasaki void makefixed OF((void)); 100100966Siwasaki#endif 101100966Siwasakilocal unsigned syncsearch OF((unsigned FAR *have, const unsigned char FAR *buf, 102100966Siwasaki unsigned len)); 103100966Siwasaki 104100966Siwasakiint ZEXPORT inflateResetKeep(strm) 105100966Siwasakiz_streamp strm; 106100966Siwasaki{ 107100966Siwasaki struct inflate_state FAR *state; 108100966Siwasaki 109100966Siwasaki if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 110100966Siwasaki state = (struct inflate_state FAR *)strm->state; 111100966Siwasaki strm->total_in = strm->total_out = state->total = 0; 112100966Siwasaki strm->msg = Z_NULL; 113100966Siwasaki if (state->wrap) /* to support ill-conceived Java test suite */ 114100966Siwasaki strm->adler = state->wrap & 1; 115100966Siwasaki state->mode = HEAD; 116100966Siwasaki state->last = 0; 117100966Siwasaki state->havedict = 0; 118100966Siwasaki state->dmax = 32768U; 119100966Siwasaki state->head = Z_NULL; 120100966Siwasaki state->hold = 0; 121100966Siwasaki state->bits = 0; 122100966Siwasaki state->lencode = state->distcode = state->next = state->codes; 123100966Siwasaki state->sane = 1; 124100966Siwasaki state->back = -1; 125100966Siwasaki Tracev((stderr, "inflate: reset\n")); 126100966Siwasaki return Z_OK; 127100966Siwasaki} 128100966Siwasaki 129100966Siwasakiint ZEXPORT inflateReset(strm) 130100966Siwasakiz_streamp strm; 131167802Sjkim{ 132100966Siwasaki struct inflate_state FAR *state; 133100966Siwasaki 134100966Siwasaki if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 135100966Siwasaki state = (struct inflate_state FAR *)strm->state; 136100966Siwasaki state->wsize = 0; 137100966Siwasaki state->whave = 0; 138100966Siwasaki state->wnext = 0; 139100966Siwasaki return inflateResetKeep(strm); 140100966Siwasaki} 141100966Siwasaki 142100966Siwasakiint ZEXPORT inflateReset2(strm, windowBits) 143100966Siwasakiz_streamp strm; 144167802Sjkimint windowBits; 145167802Sjkim{ 146100966Siwasaki int wrap; 147100966Siwasaki struct inflate_state FAR *state; 148100966Siwasaki 149100966Siwasaki /* get the state */ 150100966Siwasaki if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 151100966Siwasaki state = (struct inflate_state FAR *)strm->state; 152100966Siwasaki 153100966Siwasaki /* extract wrap request from windowBits parameter */ 154100966Siwasaki if (windowBits < 0) { 155100966Siwasaki wrap = 0; 156100966Siwasaki windowBits = -windowBits; 157100966Siwasaki } 158100966Siwasaki else { 159100966Siwasaki wrap = (windowBits >> 4) + 1; 160100966Siwasaki#ifdef GUNZIP 161167802Sjkim if (windowBits < 48) 162100966Siwasaki windowBits &= 15; 163167802Sjkim#endif 164100966Siwasaki } 165100966Siwasaki 166100966Siwasaki /* set number of window bits, free window if different */ 167100966Siwasaki if (windowBits && (windowBits < 8 || windowBits > 15)) 168100966Siwasaki return Z_STREAM_ERROR; 169128212Snjl if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) { 170128212Snjl ZFREE(strm, state->window); 171241973Sjkim state->window = Z_NULL; 172100966Siwasaki } 173128212Snjl 174241973Sjkim /* update state and reset the rest of it */ 175100966Siwasaki state->wrap = wrap; 176100966Siwasaki state->wbits = (unsigned)windowBits; 177100966Siwasaki return inflateReset(strm); 178100966Siwasaki} 179241973Sjkim 180100966Siwasakiint ZEXPORT inflateInit2_(strm, windowBits, version, stream_size) 181100966Siwasakiz_streamp strm; 182100966Siwasakiint windowBits; 183100966Siwasakiconst char *version; 184100966Siwasakiint stream_size; 185100966Siwasaki{ 186100966Siwasaki int ret; 187100966Siwasaki struct inflate_state FAR *state; 188100966Siwasaki 189100966Siwasaki if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 190100966Siwasaki stream_size != (int)(sizeof(z_stream))) 191100966Siwasaki return Z_VERSION_ERROR; 192167802Sjkim if (strm == Z_NULL) return Z_STREAM_ERROR; 193100966Siwasaki strm->msg = Z_NULL; /* in case we return an error */ 194100966Siwasaki if (strm->zalloc == (alloc_func)0) { 195100966Siwasaki#ifdef Z_SOLO 196100966Siwasaki return Z_STREAM_ERROR; 197167802Sjkim#else 198100966Siwasaki strm->zalloc = zcalloc; 199100966Siwasaki strm->opaque = (voidpf)0; 200167802Sjkim#endif 201129684Snjl } 202167802Sjkim if (strm->zfree == (free_func)0) 203167802Sjkim#ifdef Z_SOLO 204167802Sjkim return Z_STREAM_ERROR; 205167802Sjkim#else 206167802Sjkim strm->zfree = zcfree; 207167802Sjkim#endif 208167802Sjkim state = (struct inflate_state FAR *) 209167802Sjkim ZALLOC(strm, 1, sizeof(struct inflate_state)); 210200553Sjkim if (state == Z_NULL) return Z_MEM_ERROR; 211167802Sjkim Tracev((stderr, "inflate: allocated\n")); 212167802Sjkim strm->state = (struct internal_state FAR *)state; 213167802Sjkim state->window = Z_NULL; 214167802Sjkim ret = inflateReset2(strm, windowBits); 215167802Sjkim if (ret != Z_OK) { 216167802Sjkim ZFREE(strm, state); 217100966Siwasaki strm->state = Z_NULL; 218249663Sjkim } 219249663Sjkim return ret; 220249663Sjkim} 221249663Sjkim 222249663Sjkimint ZEXPORT inflateInit_(strm, version, stream_size) 223249663Sjkimz_streamp strm; 224100966Siwasakiconst char *version; 225249663Sjkimint stream_size; 226249663Sjkim{ 227249663Sjkim return inflateInit2_(strm, DEF_WBITS, version, stream_size); 228249663Sjkim} 229249663Sjkim 230249663Sjkimint ZEXPORT inflatePrime(strm, bits, value) 231249663Sjkimz_streamp strm; 232249663Sjkimint bits; 233249663Sjkimint value; 234249663Sjkim{ 235249663Sjkim struct inflate_state FAR *state; 236249663Sjkim 237249663Sjkim if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 238249663Sjkim state = (struct inflate_state FAR *)strm->state; 239249663Sjkim if (bits < 0) { 240249663Sjkim state->hold = 0; 241249663Sjkim state->bits = 0; 242249663Sjkim return Z_OK; 243249663Sjkim } 244249663Sjkim if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR; 245249663Sjkim value &= (1L << bits) - 1; 246249663Sjkim state->hold += value << state->bits; 247249663Sjkim state->bits += bits; 248249663Sjkim return Z_OK; 249249663Sjkim} 250249663Sjkim 251249663Sjkim/* 252249663Sjkim Return state with length and distance decoding tables and index sizes set to 253249663Sjkim fixed code decoding. Normally this returns fixed tables from inffixed.h. 254249663Sjkim If BUILDFIXED is defined, then instead this routine builds the tables the 255249663Sjkim first time it's called, and returns those tables the first time and 256249663Sjkim thereafter. This reduces the size of the code by about 2K bytes, in 257249663Sjkim exchange for a little execution time. However, BUILDFIXED should not be 258249663Sjkim used for threaded applications, since the rewriting of the tables and virgin 259249663Sjkim may not be thread-safe. 260100966Siwasaki */ 261100966Siwasakilocal void fixedtables(state) 262249663Sjkimstruct inflate_state FAR *state; 263249663Sjkim{ 264249663Sjkim#ifdef BUILDFIXED 265249663Sjkim static int virgin = 1; 266249663Sjkim static code *lenfix, *distfix; 267249663Sjkim static code fixed[544]; 268249663Sjkim 269249663Sjkim /* build fixed huffman tables if first call (may not be thread safe) */ 270249663Sjkim if (virgin) { 271249663Sjkim unsigned sym, bits; 272249663Sjkim static code *next; 273249663Sjkim 274249663Sjkim /* literal/length table */ 275100966Siwasaki sym = 0; 276100966Siwasaki while (sym < 144) state->lens[sym++] = 8; 277100966Siwasaki while (sym < 256) state->lens[sym++] = 9; 278100966Siwasaki while (sym < 280) state->lens[sym++] = 7; 279167802Sjkim while (sym < 288) state->lens[sym++] = 8; 280249663Sjkim next = fixed; 281167802Sjkim lenfix = next; 282100966Siwasaki bits = 9; 283167802Sjkim inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); 284167802Sjkim 285100966Siwasaki /* distance table */ 286100966Siwasaki sym = 0; 287167802Sjkim while (sym < 32) state->lens[sym++] = 5; 288167802Sjkim distfix = next; 289249663Sjkim bits = 5; 290100966Siwasaki inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); 291167802Sjkim 292249663Sjkim /* do this just once */ 293100966Siwasaki virgin = 0; 294100966Siwasaki } 295167802Sjkim#else /* !BUILDFIXED */ 296100966Siwasaki# include "inffixed.h" 297100966Siwasaki#endif /* BUILDFIXED */ 298249663Sjkim state->lencode = lenfix; 299249663Sjkim state->lenbits = 9; 300100966Siwasaki state->distcode = distfix; 301100966Siwasaki state->distbits = 5; 302249663Sjkim} 303249663Sjkim 304249663Sjkim#ifdef MAKEFIXED 305100966Siwasaki#include <stdio.h> 306249663Sjkim 307249663Sjkim/* 308100966Siwasaki Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also 309249663Sjkim defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 310249663Sjkim those tables to stdout, which would be piped to inffixed.h. A small program 311100966Siwasaki can simply call makefixed to do this: 312249663Sjkim 313167802Sjkim void makefixed(void); 314249663Sjkim 315249663Sjkim int main(void) 316249663Sjkim { 317249663Sjkim makefixed(); 318249663Sjkim return 0; 319249663Sjkim } 320249663Sjkim 321249663Sjkim Then that can be linked with zlib built with MAKEFIXED defined and run: 322249663Sjkim 323249663Sjkim a.out > inffixed.h 324249663Sjkim */ 325249663Sjkimvoid makefixed() 326249663Sjkim{ 327249663Sjkim unsigned low, size; 328249663Sjkim struct inflate_state state; 329249663Sjkim 330249663Sjkim fixedtables(&state); 331249663Sjkim puts(" /* inffixed.h -- table for decoding fixed codes"); 332249663Sjkim puts(" * Generated automatically by makefixed()."); 333249663Sjkim puts(" */"); 334249663Sjkim puts(""); 335249663Sjkim puts(" /* WARNING: this file should *not* be used by applications."); 336249663Sjkim puts(" It is part of the implementation of this library and is"); 337249663Sjkim puts(" subject to change. Applications should only use zlib.h."); 338249663Sjkim puts(" */"); 339100966Siwasaki puts(""); 340249663Sjkim size = 1U << 9; 341249663Sjkim printf(" static const code lenfix[%u] = {", size); 342100966Siwasaki low = 0; 343249663Sjkim for (;;) { 344100966Siwasaki if ((low % 7) == 0) printf("\n "); 345249663Sjkim printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op, 346249663Sjkim state.lencode[low].bits, state.lencode[low].val); 347249663Sjkim if (++low == size) break; 348249663Sjkim putchar(','); 349249663Sjkim } 350249663Sjkim puts("\n };"); 351249663Sjkim size = 1U << 5; 352249663Sjkim printf("\n static const code distfix[%u] = {", size); 353249663Sjkim low = 0; 354249663Sjkim for (;;) { 355249663Sjkim if ((low % 6) == 0) printf("\n "); 356249663Sjkim printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits, 357249663Sjkim state.distcode[low].val); 358249663Sjkim if (++low == size) break; 359249663Sjkim putchar(','); 360249663Sjkim } 361249663Sjkim puts("\n };"); 362249663Sjkim} 363249663Sjkim#endif /* MAKEFIXED */ 364249663Sjkim 365249663Sjkim/* 366249663Sjkim Update the window with the last wsize (normally 32K) bytes written before 367249663Sjkim returning. If window does not exist yet, create it. This is only called 368249663Sjkim when a window is already in use, or when output has been written during this 369249663Sjkim inflate call, but the end of the deflate stream has not been reached yet. 370100966Siwasaki It is also called to create a window for dictionary data when a dictionary 371249663Sjkim is loaded. 372249663Sjkim 373249663Sjkim Providing output buffers larger than 32K to inflate() should provide a speed 374249663Sjkim advantage, since only the last 32K of output is copied to the sliding window 375249663Sjkim upon return from inflate(), and since all distances after the first 32K of 376249663Sjkim output will fall in the output data, making match copies simpler and faster. 377249663Sjkim The advantage may be dependent on the size of the processor's data caches. 378100966Siwasaki */ 379249663Sjkimlocal int updatewindow(strm, end, copy) 380249663Sjkimz_streamp strm; 381249663Sjkimconst Bytef *end; 382100966Siwasakiunsigned copy; 383249663Sjkim{ 384100966Siwasaki struct inflate_state FAR *state; 385167802Sjkim unsigned dist; 386249663Sjkim 387100966Siwasaki state = (struct inflate_state FAR *)strm->state; 388249663Sjkim 389249663Sjkim /* if it hasn't been done already, allocate space for the window */ 390249663Sjkim if (state->window == Z_NULL) { 391249663Sjkim state->window = (unsigned char FAR *) 392249663Sjkim ZALLOC(strm, 1U << state->wbits, 393100966Siwasaki sizeof(unsigned char)); 394100966Siwasaki if (state->window == Z_NULL) return 1; 395100966Siwasaki } 396100966Siwasaki 397100966Siwasaki /* if window not in use yet, initialize */ 398100966Siwasaki if (state->wsize == 0) { 399167802Sjkim state->wsize = 1U << state->wbits; 400100966Siwasaki state->wnext = 0; 401100966Siwasaki state->whave = 0; 402100966Siwasaki } 403100966Siwasaki 404100966Siwasaki /* copy state->wsize or less output bytes into the circular window */ 405167802Sjkim if (copy >= state->wsize) { 406167802Sjkim zmemcpy(state->window, end - state->wsize, state->wsize); 407100966Siwasaki state->wnext = 0; 408100966Siwasaki state->whave = state->wsize; 409100966Siwasaki } 410100966Siwasaki else { 411100966Siwasaki dist = state->wsize - state->wnext; 412100966Siwasaki if (dist > copy) dist = copy; 413100966Siwasaki zmemcpy(state->window + state->wnext, end - copy, dist); 414100966Siwasaki copy -= dist; 415100966Siwasaki if (copy) { 416100966Siwasaki zmemcpy(state->window, end - copy, copy); 417167802Sjkim state->wnext = copy; 418100966Siwasaki state->whave = state->wsize; 419100966Siwasaki } 420100966Siwasaki else { 421100966Siwasaki state->wnext += dist; 422100966Siwasaki if (state->wnext == state->wsize) state->wnext = 0; 423193267Sjkim if (state->whave < state->wsize) state->whave += dist; 424193267Sjkim } 425193267Sjkim } 426193267Sjkim return 0; 427167802Sjkim} 428167802Sjkim 429167802Sjkim/* Macros for inflate(): */ 430167802Sjkim 431100966Siwasaki/* check function to use adler32() for zlib or crc32() for gzip */ 432100966Siwasaki#ifdef GUNZIP 433100966Siwasaki# define UPDATE(check, buf, len) \ 434100966Siwasaki (state->flags ? crc32(check, buf, len) : adler32(check, buf, len)) 435151937Sjkim#else 436167802Sjkim# define UPDATE(check, buf, len) adler32(check, buf, len) 437100966Siwasaki#endif 438100966Siwasaki 439100966Siwasaki/* check macros for header crc */ 440167802Sjkim#ifdef GUNZIP 441167802Sjkim# define CRC2(check, word) \ 442100966Siwasaki do { \ 443100966Siwasaki hbuf[0] = (unsigned char)(word); \ 444100966Siwasaki hbuf[1] = (unsigned char)((word) >> 8); \ 445129684Snjl check = crc32(check, hbuf, 2); \ 446129684Snjl } while (0) 447100966Siwasaki 448100966Siwasaki# define CRC4(check, word) \ 449100966Siwasaki do { \ 450167802Sjkim hbuf[0] = (unsigned char)(word); \ 451167802Sjkim hbuf[1] = (unsigned char)((word) >> 8); \ 452167802Sjkim hbuf[2] = (unsigned char)((word) >> 16); \ 453167802Sjkim hbuf[3] = (unsigned char)((word) >> 24); \ 454100966Siwasaki check = crc32(check, hbuf, 4); \ 455100966Siwasaki } while (0) 456100966Siwasaki#endif 457100966Siwasaki 458100966Siwasaki/* Load registers with state in inflate() for speed */ 459100966Siwasaki#define LOAD() \ 460167802Sjkim do { \ 461100966Siwasaki put = strm->next_out; \ 462129684Snjl left = strm->avail_out; \ 463167802Sjkim next = strm->next_in; \ 464167802Sjkim have = strm->avail_in; \ 465100966Siwasaki hold = state->hold; \ 466167802Sjkim bits = state->bits; \ 467167802Sjkim } while (0) 468167802Sjkim 469167802Sjkim/* Restore state from registers in inflate() */ 470167802Sjkim#define RESTORE() \ 471167802Sjkim do { \ 472100966Siwasaki strm->next_out = put; \ 473100966Siwasaki strm->avail_out = left; \ 474167802Sjkim strm->next_in = next; \ 475167802Sjkim strm->avail_in = have; \ 476167802Sjkim state->hold = hold; \ 477167802Sjkim state->bits = bits; \ 478167802Sjkim } while (0) 479167802Sjkim 480100966Siwasaki/* Clear the input bit accumulator */ 481100966Siwasaki#define INITBITS() \ 482100966Siwasaki do { \ 483167802Sjkim hold = 0; \ 484100966Siwasaki bits = 0; \ 485100966Siwasaki } while (0) 486167802Sjkim 487100966Siwasaki/* Get a byte of input into the bit accumulator, or return from inflate() 488100966Siwasaki if there is no input available. */ 489100966Siwasaki#define PULLBYTE() \ 490167802Sjkim do { \ 491100966Siwasaki if (have == 0) goto inf_leave; \ 492167802Sjkim have--; \ 493100966Siwasaki hold += (unsigned long)(*next++) << bits; \ 494100966Siwasaki bits += 8; \ 495193267Sjkim } while (0) 496193267Sjkim 497193267Sjkim/* Assure that there are at least n bits in the bit accumulator. If there is 498193267Sjkim not enough available input to do that, then return from inflate(). */ 499193267Sjkim#define NEEDBITS(n) \ 500193267Sjkim do { \ 501193267Sjkim while (bits < (unsigned)(n)) \ 502193267Sjkim PULLBYTE(); \ 503193267Sjkim } while (0) 504193267Sjkim 505193267Sjkim/* Return the low n bits of the bit accumulator (n < 16) */ 506193267Sjkim#define BITS(n) \ 507193267Sjkim ((unsigned)hold & ((1U << (n)) - 1)) 508193267Sjkim 509193267Sjkim/* Remove n bits from the bit accumulator */ 510193267Sjkim#define DROPBITS(n) \ 511193267Sjkim do { \ 512193267Sjkim hold >>= (n); \ 513193267Sjkim bits -= (unsigned)(n); \ 514193267Sjkim } while (0) 515193267Sjkim 516193267Sjkim/* Remove zero to seven bits as needed to go to a byte boundary */ 517193267Sjkim#define BYTEBITS() \ 518193267Sjkim do { \ 519193267Sjkim hold >>= bits & 7; \ 520193267Sjkim bits -= bits & 7; \ 521193267Sjkim } while (0) 522193267Sjkim 523193267Sjkim/* 524193267Sjkim inflate() uses a state machine to process as much input data and generate as 525193267Sjkim much output data as possible before returning. The state machine is 526193267Sjkim structured roughly as follows: 527193267Sjkim 528193267Sjkim for (;;) switch (state) { 529193267Sjkim ... 530193267Sjkim case STATEn: 531193267Sjkim if (not enough input data or output space to make progress) 532193267Sjkim return; 533193267Sjkim ... make progress ... 534193267Sjkim state = STATEm; 535193267Sjkim break; 536193267Sjkim ... 537193267Sjkim } 538193267Sjkim 539193267Sjkim so when inflate() is called again, the same case is attempted again, and 540193267Sjkim if the appropriate resources are provided, the machine proceeds to the 541193267Sjkim next state. The NEEDBITS() macro is usually the way the state evaluates 542193267Sjkim whether it can proceed or should return. NEEDBITS() does the return if 543193267Sjkim the requested bits are not available. The typical use of the BITS macros 544193267Sjkim is: 545193267Sjkim 546193267Sjkim NEEDBITS(n); 547193267Sjkim ... do something with BITS(n) ... 548193267Sjkim DROPBITS(n); 549193267Sjkim 550193267Sjkim where NEEDBITS(n) either returns from inflate() if there isn't enough 551193267Sjkim input left to load n bits into the accumulator, or it continues. BITS(n) 552193267Sjkim gives the low n bits in the accumulator. When done, DROPBITS(n) drops 553250838Sjkim the low n bits off the accumulator. INITBITS() clears the accumulator 554193267Sjkim and sets the number of available bits to zero. BYTEBITS() discards just 555193267Sjkim enough bits to put the accumulator on a byte boundary. After BYTEBITS() 556193267Sjkim and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 557193267Sjkim 558193267Sjkim NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 559193267Sjkim if there is no input available. The decoding of variable length codes uses 560193267Sjkim PULLBYTE() directly in order to pull just enough bytes to decode the next 561193267Sjkim code, and no more. 562193267Sjkim 563193267Sjkim Some states loop until they get enough input, making sure that enough 564193267Sjkim state information is maintained to continue the loop where it left off 565193267Sjkim if NEEDBITS() returns in the loop. For example, want, need, and keep 566193267Sjkim would all have to actually be part of the saved state in case NEEDBITS() 567193267Sjkim returns: 568193267Sjkim 569193267Sjkim case STATEw: 570193267Sjkim while (want < need) { 571193267Sjkim NEEDBITS(n); 572100966Siwasaki keep[want++] = BITS(n); 573100966Siwasaki DROPBITS(n); 574100966Siwasaki } 575100966Siwasaki state = STATEx; 576100966Siwasaki case STATEx: 577253690Sjkim 578199337Sjkim As shown above, if the next state is also the next case, then the break 579253690Sjkim is omitted. 580199337Sjkim 581199337Sjkim A state may also return if there is not enough output space available to 582100966Siwasaki complete that state. Those states are copying stored data, writing a 583100966Siwasaki literal byte, and copying a matching string. 584100966Siwasaki 585100966Siwasaki When returning, a "goto inf_leave" is used to update the total counters, 586100966Siwasaki update the check value, and determine whether any progress has been made 587100966Siwasaki during that inflate() call in order to return the proper return code. 588100966Siwasaki Progress is defined as a change in either strm->avail_in or strm->avail_out. 589100966Siwasaki When there is a window, goto inf_leave will update the window with the last 590199337Sjkim output written. If a goto inf_leave occurs in the middle of decompression 591199337Sjkim and there is no window currently, goto inf_leave will create one and copy 592100966Siwasaki output to the window for the next call of inflate(). 593100966Siwasaki 594100966Siwasaki In this implementation, the flush parameter of inflate() only affects the 595100966Siwasaki return code (per zlib.h). inflate() always writes as much as possible to 596100966Siwasaki strm->next_out, given the space available and the provided input--the effect 597199337Sjkim documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 598199337Sjkim the allocation of and copying into a sliding window until necessary, which 599199337Sjkim provides the effect documented in zlib.h for Z_FINISH when the entire input 600100966Siwasaki stream available. So the only thing the flush parameter actually does is: 601100966Siwasaki when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 602100966Siwasaki will return Z_BUF_ERROR if it has not reached the end of the stream. 603100966Siwasaki */ 604100966Siwasaki 605100966Siwasakiint ZEXPORT inflate(strm, flush) 606100966Siwasakiz_streamp strm; 607100966Siwasakiint flush; 608253690Sjkim{ 609253690Sjkim struct inflate_state FAR *state; 610100966Siwasaki z_const unsigned char FAR *next; /* next input */ 611100966Siwasaki unsigned char FAR *put; /* next output */ 612100966Siwasaki unsigned have, left; /* available input and output */ 613100966Siwasaki unsigned long hold; /* bit buffer */ 614100966Siwasaki unsigned bits; /* bits in bit buffer */ 615100966Siwasaki unsigned in, out; /* save starting available input and output */ 616167802Sjkim unsigned copy; /* number of stored or match bytes to copy */ 617100966Siwasaki unsigned char FAR *from; /* where to copy match bytes from */ 618100966Siwasaki code here; /* current decoding table entry */ 619100966Siwasaki code last; /* parent table entry */ 620100966Siwasaki unsigned len; /* length to copy for repeats, bits to drop */ 621167802Sjkim int ret; /* return code */ 622167802Sjkim#ifdef GUNZIP 623253690Sjkim unsigned char hbuf[4]; /* buffer for gzip header crc calculation */ 624100966Siwasaki#endif 625100966Siwasaki static const unsigned short order[19] = /* permutation of code lengths */ 626100966Siwasaki {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 627100966Siwasaki 628100966Siwasaki if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 629193267Sjkim (strm->next_in == Z_NULL && strm->avail_in != 0)) 630193267Sjkim return Z_STREAM_ERROR; 631193267Sjkim 632193267Sjkim state = (struct inflate_state FAR *)strm->state; 633193267Sjkim if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 634193267Sjkim LOAD(); 635193267Sjkim in = have; 636193267Sjkim out = left; 637193267Sjkim ret = Z_OK; 638100966Siwasaki for (;;) 639193267Sjkim switch (state->mode) { 640193267Sjkim case HEAD: 641193267Sjkim if (state->wrap == 0) { 642241973Sjkim state->mode = TYPEDO; 643193267Sjkim break; 644193267Sjkim } 645193267Sjkim NEEDBITS(16); 646193267Sjkim#ifdef GUNZIP 647193267Sjkim if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */ 648193267Sjkim state->check = crc32(0L, Z_NULL, 0); 649193267Sjkim CRC2(state->check, hold); 650193267Sjkim INITBITS(); 651100966Siwasaki state->mode = FLAGS; 652100966Siwasaki break; 653100966Siwasaki } 654193267Sjkim state->flags = 0; /* expect zlib header */ 655100966Siwasaki if (state->head != Z_NULL) 656100966Siwasaki state->head->done = -1; 657254745Sjkim if (!(state->wrap & 1) || /* check if zlib header allowed */ 658254745Sjkim#else 659254745Sjkim if ( 660254745Sjkim#endif 661254745Sjkim ((BITS(8) << 8) + (hold >> 8)) % 31) { 662254745Sjkim strm->msg = (char *)"incorrect header check"; 663254745Sjkim state->mode = BAD; 664254745Sjkim break; 665151937Sjkim } 666253690Sjkim if (BITS(4) != Z_DEFLATED) { 667253690Sjkim strm->msg = (char *)"unknown compression method"; 668100966Siwasaki state->mode = BAD; 669254745Sjkim break; 670100966Siwasaki } 671193267Sjkim DROPBITS(4); 672193267Sjkim len = BITS(4) + 8; 673193267Sjkim if (state->wbits == 0) 674100966Siwasaki state->wbits = len; 675100966Siwasaki else if (len > state->wbits) { 676100966Siwasaki strm->msg = (char *)"invalid window size"; 677167802Sjkim state->mode = BAD; 678100966Siwasaki break; 679167802Sjkim } 680100966Siwasaki state->dmax = 1U << len; 681100966Siwasaki Tracev((stderr, "inflate: zlib header ok\n")); 682100966Siwasaki strm->adler = state->check = adler32(0L, Z_NULL, 0); 683100966Siwasaki state->mode = hold & 0x200 ? DICTID : TYPE; 684100966Siwasaki INITBITS(); 685100966Siwasaki break; 686100966Siwasaki#ifdef GUNZIP 687100966Siwasaki case FLAGS: 688100966Siwasaki NEEDBITS(16); 689100966Siwasaki state->flags = (int)(hold); 690100966Siwasaki if ((state->flags & 0xff) != Z_DEFLATED) { 691100966Siwasaki strm->msg = (char *)"unknown compression method"; 692100966Siwasaki state->mode = BAD; 693100966Siwasaki break; 694100966Siwasaki } 695100966Siwasaki if (state->flags & 0xe000) { 696100966Siwasaki strm->msg = (char *)"unknown header flags set"; 697100966Siwasaki state->mode = BAD; 698100966Siwasaki break; 699100966Siwasaki } 700100966Siwasaki if (state->head != Z_NULL) 701117521Snjl state->head->text = (int)((hold >> 8) & 1); 702100966Siwasaki if (state->flags & 0x0200) CRC2(state->check, hold); 703100966Siwasaki INITBITS(); 704100966Siwasaki state->mode = TIME; 705241973Sjkim case TIME: 706241973Sjkim NEEDBITS(32); 707193267Sjkim if (state->head != Z_NULL) 708193267Sjkim state->head->time = hold; 709197104Sjkim if (state->flags & 0x0200) CRC4(state->check, hold); 710100966Siwasaki INITBITS(); 711100966Siwasaki state->mode = OS; 712100966Siwasaki case OS: 713100966Siwasaki NEEDBITS(16); 714100966Siwasaki if (state->head != Z_NULL) { 715100966Siwasaki state->head->xflags = (int)(hold & 0xff); 716100966Siwasaki state->head->os = (int)(hold >> 8); 717100966Siwasaki } 718200553Sjkim if (state->flags & 0x0200) CRC2(state->check, hold); 719100966Siwasaki INITBITS(); 720100966Siwasaki state->mode = EXLEN; 721100966Siwasaki case EXLEN: 722100966Siwasaki if (state->flags & 0x0400) { 723100966Siwasaki NEEDBITS(16); 724100966Siwasaki state->length = (unsigned)(hold); 725100966Siwasaki if (state->head != Z_NULL) 726100966Siwasaki state->head->extra_len = (unsigned)hold; 727100966Siwasaki if (state->flags & 0x0200) CRC2(state->check, hold); 728100966Siwasaki INITBITS(); 729100966Siwasaki } 730202771Sjkim else if (state->head != Z_NULL) 731202771Sjkim state->head->extra = Z_NULL; 732202771Sjkim state->mode = EXTRA; 733202771Sjkim case EXTRA: 734202771Sjkim if (state->flags & 0x0400) { 735202771Sjkim copy = state->length; 736202771Sjkim if (copy > have) copy = have; 737202771Sjkim if (copy) { 738202771Sjkim if (state->head != Z_NULL && 739202771Sjkim state->head->extra != Z_NULL) { 740202771Sjkim len = state->head->extra_len - state->length; 741202771Sjkim zmemcpy(state->head->extra + len, next, 742202771Sjkim len + copy > state->head->extra_max ? 743202771Sjkim state->head->extra_max - len : copy); 744100966Siwasaki } 745100966Siwasaki if (state->flags & 0x0200) 746100966Siwasaki state->check = crc32(state->check, next, copy); 747100966Siwasaki have -= copy; 748100966Siwasaki next += copy; 749100966Siwasaki state->length -= copy; 750100966Siwasaki } 751100966Siwasaki if (state->length) goto inf_leave; 752100966Siwasaki } 753100966Siwasaki state->length = 0; 754100966Siwasaki state->mode = NAME; 755100966Siwasaki case NAME: 756197104Sjkim if (state->flags & 0x0800) { 757197104Sjkim if (have == 0) goto inf_leave; 758197104Sjkim copy = 0; 759197104Sjkim do { 760100966Siwasaki len = (unsigned)(next[copy++]); 761193267Sjkim if (state->head != Z_NULL && 762193267Sjkim state->head->name != Z_NULL && 763193267Sjkim state->length < state->head->name_max) 764193267Sjkim state->head->name[state->length++] = len; 765100966Siwasaki } while (len && copy < have); 766100966Siwasaki if (state->flags & 0x0200) 767100966Siwasaki state->check = crc32(state->check, next, copy); 768100966Siwasaki have -= copy; 769100966Siwasaki next += copy; 770100966Siwasaki if (len) goto inf_leave; 771100966Siwasaki } 772100966Siwasaki else if (state->head != Z_NULL) 773100966Siwasaki state->head->name = Z_NULL; 774100966Siwasaki state->length = 0; 775117521Snjl state->mode = COMMENT; 776100966Siwasaki case COMMENT: 777193267Sjkim if (state->flags & 0x1000) { 778117521Snjl if (have == 0) goto inf_leave; 779100966Siwasaki copy = 0; 780197104Sjkim do { 781117521Snjl len = (unsigned)(next[copy++]); 782193267Sjkim if (state->head != Z_NULL && 783193267Sjkim state->head->comment != Z_NULL && 784193267Sjkim state->length < state->head->comm_max) 785193267Sjkim state->head->comment[state->length++] = len; 786117521Snjl } while (len && copy < have); 787100966Siwasaki if (state->flags & 0x0200) 788193267Sjkim state->check = crc32(state->check, next, copy); 789167802Sjkim have -= copy; 790193267Sjkim next += copy; 791193267Sjkim if (len) goto inf_leave; 792193267Sjkim } 793193267Sjkim else if (state->head != Z_NULL) 794100966Siwasaki state->head->comment = Z_NULL; 795100966Siwasaki state->mode = HCRC; 796100966Siwasaki case HCRC: 797202771Sjkim if (state->flags & 0x0200) { 798202771Sjkim NEEDBITS(16); 799202771Sjkim if (hold != (state->check & 0xffff)) { 800202771Sjkim strm->msg = (char *)"header crc mismatch"; 801202771Sjkim state->mode = BAD; 802202771Sjkim break; 803202771Sjkim } 804202771Sjkim INITBITS(); 805202771Sjkim } 806202771Sjkim if (state->head != Z_NULL) { 807202771Sjkim state->head->hcrc = (int)((state->flags >> 9) & 1); 808202771Sjkim state->head->done = 1; 809202771Sjkim } 810202771Sjkim strm->adler = state->check = crc32(0L, Z_NULL, 0); 811202771Sjkim state->mode = TYPE; 812202771Sjkim break; 813202771Sjkim#endif 814202771Sjkim case DICTID: 815202771Sjkim NEEDBITS(32); 816193267Sjkim strm->adler = state->check = ZSWAP32(hold); 817193267Sjkim INITBITS(); 818151937Sjkim state->mode = DICT; 819151937Sjkim case DICT: 820100966Siwasaki if (state->havedict == 0) { 821100966Siwasaki RESTORE(); 822100966Siwasaki return Z_NEED_DICT; 823100966Siwasaki } 824100966Siwasaki strm->adler = state->check = adler32(0L, Z_NULL, 0); 825100966Siwasaki state->mode = TYPE; 826100966Siwasaki case TYPE: 827100966Siwasaki if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave; 828100966Siwasaki case TYPEDO: 829100966Siwasaki if (state->last) { 830100966Siwasaki BYTEBITS(); 831100966Siwasaki state->mode = CHECK; 832100966Siwasaki break; 833100966Siwasaki } 834100966Siwasaki NEEDBITS(3); 835100966Siwasaki state->last = BITS(1); 836100966Siwasaki DROPBITS(1); 837100966Siwasaki switch (BITS(2)) { 838100966Siwasaki case 0: /* stored block */ 839117521Snjl Tracev((stderr, "inflate: stored block%s\n", 840241973Sjkim state->last ? " (last)" : "")); 841100966Siwasaki state->mode = STORED; 842100966Siwasaki break; 843100966Siwasaki case 1: /* fixed block */ 844100966Siwasaki fixedtables(state); 845193267Sjkim Tracev((stderr, "inflate: fixed codes block%s\n", 846100966Siwasaki state->last ? " (last)" : "")); 847100966Siwasaki state->mode = LEN_; /* decode codes */ 848100966Siwasaki if (flush == Z_TREES) { 849100966Siwasaki DROPBITS(2); 850100966Siwasaki goto inf_leave; 851114237Snjl } 852100966Siwasaki break; 853100966Siwasaki case 2: /* dynamic block */ 854100966Siwasaki Tracev((stderr, "inflate: dynamic codes block%s\n", 855100966Siwasaki state->last ? " (last)" : "")); 856100966Siwasaki state->mode = TABLE; 857100966Siwasaki break; 858100966Siwasaki case 3: 859100966Siwasaki strm->msg = (char *)"invalid block type"; 860167802Sjkim state->mode = BAD; 861100966Siwasaki } 862100966Siwasaki DROPBITS(2); 863100966Siwasaki break; 864100966Siwasaki case STORED: 865100966Siwasaki BYTEBITS(); /* go to byte boundary */ 866100966Siwasaki NEEDBITS(32); 867100966Siwasaki if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 868100966Siwasaki strm->msg = (char *)"invalid stored block lengths"; 869100966Siwasaki state->mode = BAD; 870100966Siwasaki break; 871100966Siwasaki } 872100966Siwasaki state->length = (unsigned)hold & 0xffff; 873100966Siwasaki Tracev((stderr, "inflate: stored length %u\n", 874167802Sjkim state->length)); 875100966Siwasaki INITBITS(); 876100966Siwasaki state->mode = COPY_; 877100966Siwasaki if (flush == Z_TREES) goto inf_leave; 878100966Siwasaki case COPY_: 879100966Siwasaki state->mode = COPY; 880100966Siwasaki case COPY: 881100966Siwasaki copy = state->length; 882100966Siwasaki if (copy) { 883100966Siwasaki if (copy > have) copy = have; 884100966Siwasaki if (copy > left) copy = left; 885100966Siwasaki if (copy == 0) goto inf_leave; 886100966Siwasaki zmemcpy(put, next, copy); 887100966Siwasaki have -= copy; 888100966Siwasaki next += copy; 889100966Siwasaki left -= copy; 890167802Sjkim put += copy; 891167802Sjkim state->length -= copy; 892199337Sjkim break; 893100966Siwasaki } 894100966Siwasaki Tracev((stderr, "inflate: stored end\n")); 895100966Siwasaki state->mode = TYPE; 896100966Siwasaki break; 897100966Siwasaki case TABLE: 898167802Sjkim NEEDBITS(14); 899100966Siwasaki state->nlen = BITS(5) + 257; 900167802Sjkim DROPBITS(5); 901100966Siwasaki state->ndist = BITS(5) + 1; 902100966Siwasaki DROPBITS(5); 903100966Siwasaki state->ncode = BITS(4) + 4; 904100966Siwasaki DROPBITS(4); 905114237Snjl#ifndef PKZIP_BUG_WORKAROUND 906107325Siwasaki if (state->nlen > 286 || state->ndist > 30) { 907107325Siwasaki strm->msg = (char *)"too many length or distance symbols"; 908100966Siwasaki state->mode = BAD; 909100966Siwasaki break; 910100966Siwasaki } 911107325Siwasaki#endif 912100966Siwasaki Tracev((stderr, "inflate: table sizes ok\n")); 913100966Siwasaki state->have = 0; 914100966Siwasaki state->mode = LENLENS; 915100966Siwasaki case LENLENS: 916100966Siwasaki while (state->have < state->ncode) { 917100966Siwasaki NEEDBITS(3); 918100966Siwasaki state->lens[order[state->have++]] = (unsigned short)BITS(3); 919100966Siwasaki DROPBITS(3); 920100966Siwasaki } 921100966Siwasaki while (state->have < 19) 922100966Siwasaki state->lens[order[state->have++]] = 0; 923100966Siwasaki state->next = state->codes; 924100966Siwasaki state->lencode = (const code FAR *)(state->next); 925100966Siwasaki state->lenbits = 7; 926100966Siwasaki ret = inflate_table(CODES, state->lens, 19, &(state->next), 927100966Siwasaki &(state->lenbits), state->work); 928100966Siwasaki if (ret) { 929100966Siwasaki strm->msg = (char *)"invalid code lengths set"; 930100966Siwasaki state->mode = BAD; 931100966Siwasaki break; 932100966Siwasaki } 933100966Siwasaki Tracev((stderr, "inflate: code lengths ok\n")); 934100966Siwasaki state->have = 0; 935100966Siwasaki state->mode = CODELENS; 936100966Siwasaki case CODELENS: 937100966Siwasaki while (state->have < state->nlen + state->ndist) { 938100966Siwasaki for (;;) { 939100966Siwasaki here = state->lencode[BITS(state->lenbits)]; 940100966Siwasaki if ((unsigned)(here.bits) <= bits) break; 941100966Siwasaki PULLBYTE(); 942200553Sjkim } 943100966Siwasaki if (here.val < 16) { 944100966Siwasaki DROPBITS(here.bits); 945100966Siwasaki state->lens[state->have++] = here.val; 946100966Siwasaki } 947100966Siwasaki else { 948100966Siwasaki if (here.val == 16) { 949100966Siwasaki NEEDBITS(here.bits + 2); 950100966Siwasaki DROPBITS(here.bits); 951100966Siwasaki if (state->have == 0) { 952100966Siwasaki strm->msg = (char *)"invalid bit length repeat"; 953100966Siwasaki state->mode = BAD; 954100966Siwasaki break; 955100966Siwasaki } 956167802Sjkim len = state->lens[state->have - 1]; 957100966Siwasaki copy = 3 + BITS(2); 958167802Sjkim DROPBITS(2); 959100966Siwasaki } 960100966Siwasaki else if (here.val == 17) { 961100966Siwasaki NEEDBITS(here.bits + 3); 962100966Siwasaki DROPBITS(here.bits); 963107325Siwasaki len = 0; 964107325Siwasaki copy = 3 + BITS(3); 965100966Siwasaki DROPBITS(3); 966100966Siwasaki } 967100966Siwasaki else { 968107325Siwasaki NEEDBITS(here.bits + 7); 969100966Siwasaki DROPBITS(here.bits); 970100966Siwasaki len = 0; 971100966Siwasaki copy = 11 + BITS(7); 972100966Siwasaki DROPBITS(7); 973100966Siwasaki } 974100966Siwasaki if (state->have + copy > state->nlen + state->ndist) { 975100966Siwasaki strm->msg = (char *)"invalid bit length repeat"; 976100966Siwasaki state->mode = BAD; 977100966Siwasaki break; 978100966Siwasaki } 979100966Siwasaki while (copy--) 980100966Siwasaki state->lens[state->have++] = (unsigned short)len; 981100966Siwasaki } 982100966Siwasaki } 983100966Siwasaki 984100966Siwasaki /* handle error breaks in while */ 985100966Siwasaki if (state->mode == BAD) break; 986100966Siwasaki 987100966Siwasaki /* check for end-of-block code (better have one) */ 988100966Siwasaki if (state->lens[256] == 0) { 989100966Siwasaki strm->msg = (char *)"invalid code -- missing end-of-block"; 990100966Siwasaki state->mode = BAD; 991100966Siwasaki break; 992100966Siwasaki } 993100966Siwasaki 994100966Siwasaki /* build code tables -- note: do not change the lenbits or distbits 995100966Siwasaki values here (9 and 6) without reading the comments in inftrees.h 996100966Siwasaki concerning the ENOUGH constants, which depend on those values */ 997200553Sjkim state->next = state->codes; 998100966Siwasaki state->lencode = (const code FAR *)(state->next); 999100966Siwasaki state->lenbits = 9; 1000100966Siwasaki ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 1001100966Siwasaki &(state->lenbits), state->work); 1002100966Siwasaki if (ret) { 1003100966Siwasaki strm->msg = (char *)"invalid literal/lengths set"; 1004100966Siwasaki state->mode = BAD; 1005100966Siwasaki break; 1006100966Siwasaki } 1007100966Siwasaki state->distcode = (const code FAR *)(state->next); 1008100966Siwasaki state->distbits = 6; 1009100966Siwasaki ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 1010100966Siwasaki &(state->next), &(state->distbits), state->work); 1011167802Sjkim if (ret) { 1012100966Siwasaki strm->msg = (char *)"invalid distances set"; 1013167802Sjkim state->mode = BAD; 1014100966Siwasaki break; 1015100966Siwasaki } 1016100966Siwasaki Tracev((stderr, "inflate: codes ok\n")); 1017100966Siwasaki state->mode = LEN_; 1018107325Siwasaki if (flush == Z_TREES) goto inf_leave; 1019107325Siwasaki case LEN_: 1020107325Siwasaki state->mode = LEN; 1021100966Siwasaki case LEN: 1022100966Siwasaki if (have >= 6 && left >= 258) { 1023100966Siwasaki RESTORE(); 1024107325Siwasaki inflate_fast(strm, out); 1025100966Siwasaki LOAD(); 1026100966Siwasaki if (state->mode == TYPE) 1027100966Siwasaki state->back = -1; 1028100966Siwasaki break; 1029100966Siwasaki } 1030100966Siwasaki state->back = 0; 1031100966Siwasaki for (;;) { 1032100966Siwasaki here = state->lencode[BITS(state->lenbits)]; 1033100966Siwasaki if ((unsigned)(here.bits) <= bits) break; 1034100966Siwasaki PULLBYTE(); 1035100966Siwasaki } 1036100966Siwasaki if (here.op && (here.op & 0xf0) == 0) { 1037100966Siwasaki last = here; 1038100966Siwasaki for (;;) { 1039100966Siwasaki here = state->lencode[last.val + 1040100966Siwasaki (BITS(last.bits + last.op) >> last.bits)]; 1041100966Siwasaki if ((unsigned)(last.bits + here.bits) <= bits) break; 1042100966Siwasaki PULLBYTE(); 1043100966Siwasaki } 1044100966Siwasaki DROPBITS(last.bits); 1045100966Siwasaki state->back += last.bits; 1046100966Siwasaki } 1047100966Siwasaki DROPBITS(here.bits); 1048100966Siwasaki state->back += here.bits; 1049100966Siwasaki state->length = (unsigned)here.val; 1050100966Siwasaki if ((int)(here.op) == 0) { 1051100966Siwasaki Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? 1052100966Siwasaki "inflate: literal '%c'\n" : 1053100966Siwasaki "inflate: literal 0x%02x\n", here.val)); 1054100966Siwasaki state->mode = LIT; 1055200553Sjkim break; 1056100966Siwasaki } 1057100966Siwasaki if (here.op & 32) { 1058100966Siwasaki Tracevv((stderr, "inflate: end of block\n")); 1059100966Siwasaki state->back = -1; 1060100966Siwasaki state->mode = TYPE; 1061100966Siwasaki break; 1062100966Siwasaki } 1063100966Siwasaki if (here.op & 64) { 1064100966Siwasaki strm->msg = (char *)"invalid literal/length code"; 1065100966Siwasaki state->mode = BAD; 1066100966Siwasaki break; 1067100966Siwasaki } 1068100966Siwasaki state->extra = (unsigned)(here.op) & 15; 1069167802Sjkim state->mode = LENEXT; 1070 case LENEXT: 1071 if (state->extra) { 1072 NEEDBITS(state->extra); 1073 state->length += BITS(state->extra); 1074 DROPBITS(state->extra); 1075 state->back += state->extra; 1076 } 1077 Tracevv((stderr, "inflate: length %u\n", state->length)); 1078 state->was = state->length; 1079 state->mode = DIST; 1080 case DIST: 1081 for (;;) { 1082 here = state->distcode[BITS(state->distbits)]; 1083 if ((unsigned)(here.bits) <= bits) break; 1084 PULLBYTE(); 1085 } 1086 if ((here.op & 0xf0) == 0) { 1087 last = here; 1088 for (;;) { 1089 here = state->distcode[last.val + 1090 (BITS(last.bits + last.op) >> last.bits)]; 1091 if ((unsigned)(last.bits + here.bits) <= bits) break; 1092 PULLBYTE(); 1093 } 1094 DROPBITS(last.bits); 1095 state->back += last.bits; 1096 } 1097 DROPBITS(here.bits); 1098 state->back += here.bits; 1099 if (here.op & 64) { 1100 strm->msg = (char *)"invalid distance code"; 1101 state->mode = BAD; 1102 break; 1103 } 1104 state->offset = (unsigned)here.val; 1105 state->extra = (unsigned)(here.op) & 15; 1106 state->mode = DISTEXT; 1107 case DISTEXT: 1108 if (state->extra) { 1109 NEEDBITS(state->extra); 1110 state->offset += BITS(state->extra); 1111 DROPBITS(state->extra); 1112 state->back += state->extra; 1113 } 1114#ifdef INFLATE_STRICT 1115 if (state->offset > state->dmax) { 1116 strm->msg = (char *)"invalid distance too far back"; 1117 state->mode = BAD; 1118 break; 1119 } 1120#endif 1121 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 1122 state->mode = MATCH; 1123 case MATCH: 1124 if (left == 0) goto inf_leave; 1125 copy = out - left; 1126 if (state->offset > copy) { /* copy from window */ 1127 copy = state->offset - copy; 1128 if (copy > state->whave) { 1129 if (state->sane) { 1130 strm->msg = (char *)"invalid distance too far back"; 1131 state->mode = BAD; 1132 break; 1133 } 1134#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 1135 Trace((stderr, "inflate.c too far\n")); 1136 copy -= state->whave; 1137 if (copy > state->length) copy = state->length; 1138 if (copy > left) copy = left; 1139 left -= copy; 1140 state->length -= copy; 1141 do { 1142 *put++ = 0; 1143 } while (--copy); 1144 if (state->length == 0) state->mode = LEN; 1145 break; 1146#endif 1147 } 1148 if (copy > state->wnext) { 1149 copy -= state->wnext; 1150 from = state->window + (state->wsize - copy); 1151 } 1152 else 1153 from = state->window + (state->wnext - copy); 1154 if (copy > state->length) copy = state->length; 1155 } 1156 else { /* copy from output */ 1157 from = put - state->offset; 1158 copy = state->length; 1159 } 1160 if (copy > left) copy = left; 1161 left -= copy; 1162 state->length -= copy; 1163 do { 1164 *put++ = *from++; 1165 } while (--copy); 1166 if (state->length == 0) state->mode = LEN; 1167 break; 1168 case LIT: 1169 if (left == 0) goto inf_leave; 1170 *put++ = (unsigned char)(state->length); 1171 left--; 1172 state->mode = LEN; 1173 break; 1174 case CHECK: 1175 if (state->wrap) { 1176 NEEDBITS(32); 1177 out -= left; 1178 strm->total_out += out; 1179 state->total += out; 1180 if (out) 1181 strm->adler = state->check = 1182 UPDATE(state->check, put - out, out); 1183 out = left; 1184 if (( 1185#ifdef GUNZIP 1186 state->flags ? hold : 1187#endif 1188 ZSWAP32(hold)) != state->check) { 1189 strm->msg = (char *)"incorrect data check"; 1190 state->mode = BAD; 1191 break; 1192 } 1193 INITBITS(); 1194 Tracev((stderr, "inflate: check matches trailer\n")); 1195 } 1196#ifdef GUNZIP 1197 state->mode = LENGTH; 1198 case LENGTH: 1199 if (state->wrap && state->flags) { 1200 NEEDBITS(32); 1201 if (hold != (state->total & 0xffffffffUL)) { 1202 strm->msg = (char *)"incorrect length check"; 1203 state->mode = BAD; 1204 break; 1205 } 1206 INITBITS(); 1207 Tracev((stderr, "inflate: length matches trailer\n")); 1208 } 1209#endif 1210 state->mode = DONE; 1211 case DONE: 1212 ret = Z_STREAM_END; 1213 goto inf_leave; 1214 case BAD: 1215 ret = Z_DATA_ERROR; 1216 goto inf_leave; 1217 case MEM: 1218 return Z_MEM_ERROR; 1219 case SYNC: 1220 default: 1221 return Z_STREAM_ERROR; 1222 } 1223 1224 /* 1225 Return from inflate(), updating the total counts and the check value. 1226 If there was no progress during the inflate() call, return a buffer 1227 error. Call updatewindow() to create and/or update the window state. 1228 Note: a memory error from inflate() is non-recoverable. 1229 */ 1230 inf_leave: 1231 RESTORE(); 1232 if (state->wsize || (out != strm->avail_out && state->mode < BAD && 1233 (state->mode < CHECK || flush != Z_FINISH))) 1234 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) { 1235 state->mode = MEM; 1236 return Z_MEM_ERROR; 1237 } 1238 in -= strm->avail_in; 1239 out -= strm->avail_out; 1240 strm->total_in += in; 1241 strm->total_out += out; 1242 state->total += out; 1243 if (state->wrap && out) 1244 strm->adler = state->check = 1245 UPDATE(state->check, strm->next_out - out, out); 1246 strm->data_type = state->bits + (state->last ? 64 : 0) + 1247 (state->mode == TYPE ? 128 : 0) + 1248 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0); 1249 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1250 ret = Z_BUF_ERROR; 1251 return ret; 1252} 1253 1254int ZEXPORT inflateEnd(strm) 1255z_streamp strm; 1256{ 1257 struct inflate_state FAR *state; 1258 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1259 return Z_STREAM_ERROR; 1260 state = (struct inflate_state FAR *)strm->state; 1261 if (state->window != Z_NULL) ZFREE(strm, state->window); 1262 ZFREE(strm, strm->state); 1263 strm->state = Z_NULL; 1264 Tracev((stderr, "inflate: end\n")); 1265 return Z_OK; 1266} 1267 1268int ZEXPORT inflateGetDictionary(strm, dictionary, dictLength) 1269z_streamp strm; 1270Bytef *dictionary; 1271uInt *dictLength; 1272{ 1273 struct inflate_state FAR *state; 1274 1275 /* check state */ 1276 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1277 state = (struct inflate_state FAR *)strm->state; 1278 1279 /* copy dictionary */ 1280 if (state->whave && dictionary != Z_NULL) { 1281 zmemcpy(dictionary, state->window + state->wnext, 1282 state->whave - state->wnext); 1283 zmemcpy(dictionary + state->whave - state->wnext, 1284 state->window, state->wnext); 1285 } 1286 if (dictLength != Z_NULL) 1287 *dictLength = state->whave; 1288 return Z_OK; 1289} 1290 1291int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1292z_streamp strm; 1293const Bytef *dictionary; 1294uInt dictLength; 1295{ 1296 struct inflate_state FAR *state; 1297 unsigned long dictid; 1298 int ret; 1299 1300 /* check state */ 1301 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1302 state = (struct inflate_state FAR *)strm->state; 1303 if (state->wrap != 0 && state->mode != DICT) 1304 return Z_STREAM_ERROR; 1305 1306 /* check for correct dictionary identifier */ 1307 if (state->mode == DICT) { 1308 dictid = adler32(0L, Z_NULL, 0); 1309 dictid = adler32(dictid, dictionary, dictLength); 1310 if (dictid != state->check) 1311 return Z_DATA_ERROR; 1312 } 1313 1314 /* copy dictionary to window using updatewindow(), which will amend the 1315 existing dictionary if appropriate */ 1316 ret = updatewindow(strm, dictionary + dictLength, dictLength); 1317 if (ret) { 1318 state->mode = MEM; 1319 return Z_MEM_ERROR; 1320 } 1321 state->havedict = 1; 1322 Tracev((stderr, "inflate: dictionary set\n")); 1323 return Z_OK; 1324} 1325 1326int ZEXPORT inflateGetHeader(strm, head) 1327z_streamp strm; 1328gz_headerp head; 1329{ 1330 struct inflate_state FAR *state; 1331 1332 /* check state */ 1333 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1334 state = (struct inflate_state FAR *)strm->state; 1335 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR; 1336 1337 /* save header structure */ 1338 state->head = head; 1339 head->done = 0; 1340 return Z_OK; 1341} 1342 1343/* 1344 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1345 or when out of input. When called, *have is the number of pattern bytes 1346 found in order so far, in 0..3. On return *have is updated to the new 1347 state. If on return *have equals four, then the pattern was found and the 1348 return value is how many bytes were read including the last byte of the 1349 pattern. If *have is less than four, then the pattern has not been found 1350 yet and the return value is len. In the latter case, syncsearch() can be 1351 called again with more data and the *have state. *have is initialized to 1352 zero for the first call. 1353 */ 1354local unsigned syncsearch(have, buf, len) 1355unsigned FAR *have; 1356const unsigned char FAR *buf; 1357unsigned len; 1358{ 1359 unsigned got; 1360 unsigned next; 1361 1362 got = *have; 1363 next = 0; 1364 while (next < len && got < 4) { 1365 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1366 got++; 1367 else if (buf[next]) 1368 got = 0; 1369 else 1370 got = 4 - got; 1371 next++; 1372 } 1373 *have = got; 1374 return next; 1375} 1376 1377int ZEXPORT inflateSync(strm) 1378z_streamp strm; 1379{ 1380 unsigned len; /* number of bytes to look at or looked at */ 1381 unsigned long in, out; /* temporary to save total_in and total_out */ 1382 unsigned char buf[4]; /* to restore bit buffer to byte string */ 1383 struct inflate_state FAR *state; 1384 1385 /* check parameters */ 1386 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1387 state = (struct inflate_state FAR *)strm->state; 1388 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 1389 1390 /* if first time, start search in bit buffer */ 1391 if (state->mode != SYNC) { 1392 state->mode = SYNC; 1393 state->hold <<= state->bits & 7; 1394 state->bits -= state->bits & 7; 1395 len = 0; 1396 while (state->bits >= 8) { 1397 buf[len++] = (unsigned char)(state->hold); 1398 state->hold >>= 8; 1399 state->bits -= 8; 1400 } 1401 state->have = 0; 1402 syncsearch(&(state->have), buf, len); 1403 } 1404 1405 /* search available input */ 1406 len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1407 strm->avail_in -= len; 1408 strm->next_in += len; 1409 strm->total_in += len; 1410 1411 /* return no joy or set up to restart inflate() on a new block */ 1412 if (state->have != 4) return Z_DATA_ERROR; 1413 in = strm->total_in; out = strm->total_out; 1414 inflateReset(strm); 1415 strm->total_in = in; strm->total_out = out; 1416 state->mode = TYPE; 1417 return Z_OK; 1418} 1419 1420/* 1421 Returns true if inflate is currently at the end of a block generated by 1422 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1423 implementation to provide an additional safety check. PPP uses 1424 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1425 block. When decompressing, PPP checks that at the end of input packet, 1426 inflate is waiting for these length bytes. 1427 */ 1428int ZEXPORT inflateSyncPoint(strm) 1429z_streamp strm; 1430{ 1431 struct inflate_state FAR *state; 1432 1433 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1434 state = (struct inflate_state FAR *)strm->state; 1435 return state->mode == STORED && state->bits == 0; 1436} 1437 1438int ZEXPORT inflateCopy(dest, source) 1439z_streamp dest; 1440z_streamp source; 1441{ 1442 struct inflate_state FAR *state; 1443 struct inflate_state FAR *copy; 1444 unsigned char FAR *window; 1445 unsigned wsize; 1446 1447 /* check input */ 1448 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1449 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1450 return Z_STREAM_ERROR; 1451 state = (struct inflate_state FAR *)source->state; 1452 1453 /* allocate space */ 1454 copy = (struct inflate_state FAR *) 1455 ZALLOC(source, 1, sizeof(struct inflate_state)); 1456 if (copy == Z_NULL) return Z_MEM_ERROR; 1457 window = Z_NULL; 1458 if (state->window != Z_NULL) { 1459 window = (unsigned char FAR *) 1460 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1461 if (window == Z_NULL) { 1462 ZFREE(source, copy); 1463 return Z_MEM_ERROR; 1464 } 1465 } 1466 1467 /* copy state */ 1468 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 1469 zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state)); 1470 if (state->lencode >= state->codes && 1471 state->lencode <= state->codes + ENOUGH - 1) { 1472 copy->lencode = copy->codes + (state->lencode - state->codes); 1473 copy->distcode = copy->codes + (state->distcode - state->codes); 1474 } 1475 copy->next = copy->codes + (state->next - state->codes); 1476 if (window != Z_NULL) { 1477 wsize = 1U << state->wbits; 1478 zmemcpy(window, state->window, wsize); 1479 } 1480 copy->window = window; 1481 dest->state = (struct internal_state FAR *)copy; 1482 return Z_OK; 1483} 1484 1485int ZEXPORT inflateUndermine(strm, subvert) 1486z_streamp strm; 1487int subvert; 1488{ 1489 struct inflate_state FAR *state; 1490 1491 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1492 state = (struct inflate_state FAR *)strm->state; 1493 state->sane = !subvert; 1494#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 1495 return Z_OK; 1496#else 1497 state->sane = 1; 1498 return Z_DATA_ERROR; 1499#endif 1500} 1501 1502long ZEXPORT inflateMark(strm) 1503z_streamp strm; 1504{ 1505 struct inflate_state FAR *state; 1506 1507 if (strm == Z_NULL || strm->state == Z_NULL) return -1L << 16; 1508 state = (struct inflate_state FAR *)strm->state; 1509 return ((long)(state->back) << 16) + 1510 (state->mode == COPY ? state->length : 1511 (state->mode == MATCH ? state->was - state->length : 0)); 1512} 1513