inflate.c revision 237248
1131377Stjr/* inflate.c -- zlib decompression 2237248Sdelphij * Copyright (C) 1995-2012 Mark Adler 3131377Stjr * For conditions of distribution and use, see copyright notice in zlib.h 417651Speter */ 517651Speter 6131377Stjr/* 7131377Stjr * Change history: 8131377Stjr * 9131377Stjr * 1.2.beta0 24 Nov 2002 10131377Stjr * - First version -- complete rewrite of inflate to simplify code, avoid 11131377Stjr * creation of window when not needed, minimize use of window when it is 12131377Stjr * needed, make inffast.c even faster, implement gzip decoding, and to 13131377Stjr * improve code readability and style over the previous zlib inflate code 14131377Stjr * 15131377Stjr * 1.2.beta1 25 Nov 2002 16131377Stjr * - Use pointers for available input and output checking in inffast.c 17131377Stjr * - Remove input and output counters in inffast.c 18131377Stjr * - Change inffast.c entry and loop from avail_in >= 7 to >= 6 19131377Stjr * - Remove unnecessary second byte pull from length extra in inffast.c 20131377Stjr * - Unroll direct copy to three copies per loop in inffast.c 21131377Stjr * 22131377Stjr * 1.2.beta2 4 Dec 2002 23131377Stjr * - Change external routine names to reduce potential conflicts 24131377Stjr * - Correct filename to inffixed.h for fixed tables in inflate.c 25131377Stjr * - Make hbuf[] unsigned char to match parameter type in inflate.c 26131377Stjr * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 27131377Stjr * to avoid negation problem on Alphas (64 bit) in inflate.c 28131377Stjr * 29131377Stjr * 1.2.beta3 22 Dec 2002 30131377Stjr * - Add comments on state->bits assertion in inffast.c 31131377Stjr * - Add comments on op field in inftrees.h 32131377Stjr * - Fix bug in reuse of allocated window after inflateReset() 33131377Stjr * - Remove bit fields--back to byte structure for speed 34131377Stjr * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 35131377Stjr * - Change post-increments to pre-increments in inflate_fast(), PPC biased? 36131377Stjr * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 37131377Stjr * - Make MATCH copy in inflate() much faster for when inflate_fast() not used 38131377Stjr * - Use local copies of stream next and avail values, as well as local bit 39131377Stjr * buffer and bit count in inflate()--for speed when inflate_fast() not used 40131377Stjr * 41131377Stjr * 1.2.beta4 1 Jan 2003 42131377Stjr * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings 43131377Stjr * - Move a comment on output buffer sizes from inffast.c to inflate.c 44131377Stjr * - Add comments in inffast.c to introduce the inflate_fast() routine 45131377Stjr * - Rearrange window copies in inflate_fast() for speed and simplification 46131377Stjr * - Unroll last copy for window match in inflate_fast() 47131377Stjr * - Use local copies of window variables in inflate_fast() for speed 48205194Sdelphij * - Pull out common wnext == 0 case for speed in inflate_fast() 49131377Stjr * - Make op and len in inflate_fast() unsigned for consistency 50131377Stjr * - Add FAR to lcode and dcode declarations in inflate_fast() 51131377Stjr * - Simplified bad distance check in inflate_fast() 52131377Stjr * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 53131377Stjr * source file infback.c to provide a call-back interface to inflate for 54131377Stjr * programs like gzip and unzip -- uses window as output buffer to avoid 55131377Stjr * window copying 56131377Stjr * 57131377Stjr * 1.2.beta5 1 Jan 2003 58131377Stjr * - Improved inflateBack() interface to allow the caller to provide initial 59131377Stjr * input in strm. 60131377Stjr * - Fixed stored blocks bug in inflateBack() 61131377Stjr * 62131377Stjr * 1.2.beta6 4 Jan 2003 63131377Stjr * - Added comments in inffast.c on effectiveness of POSTINC 64131377Stjr * - Typecasting all around to reduce compiler warnings 65131377Stjr * - Changed loops from while (1) or do {} while (1) to for (;;), again to 66131377Stjr * make compilers happy 67131377Stjr * - Changed type of window in inflateBackInit() to unsigned char * 68131377Stjr * 69131377Stjr * 1.2.beta7 27 Jan 2003 70131377Stjr * - Changed many types to unsigned or unsigned short to avoid warnings 71131377Stjr * - Added inflateCopy() function 72131377Stjr * 73131377Stjr * 1.2.0 9 Mar 2003 74131377Stjr * - Changed inflateBack() interface to provide separate opaque descriptors 75131377Stjr * for the in() and out() functions 76131377Stjr * - Changed inflateBack() argument and in_func typedef to swap the length 77131377Stjr * and buffer address return values for the input function 78131377Stjr * - Check next_in and next_out for Z_NULL on entry to inflate() 79131377Stjr * 80131377Stjr * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 81131377Stjr */ 82131377Stjr 8317651Speter#include "zutil.h" 84131377Stjr#include "inftrees.h" 85131377Stjr#include "inflate.h" 86131377Stjr#include "inffast.h" 8717651Speter 88131377Stjr#ifdef MAKEFIXED 89131377Stjr# ifndef BUILDFIXED 90131377Stjr# define BUILDFIXED 91131377Stjr# endif 92131377Stjr#endif 9317651Speter 94131377Stjr/* function prototypes */ 95131377Stjrlocal void fixedtables OF((struct inflate_state FAR *state)); 96131377Stjrlocal int updatewindow OF((z_streamp strm, unsigned out)); 97131377Stjr#ifdef BUILDFIXED 98131377Stjr void makefixed OF((void)); 99131377Stjr#endif 100131377Stjrlocal unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf, 101131377Stjr unsigned len)); 10217651Speter 103230837Sdelphijint ZEXPORT inflateResetKeep(strm) 104131377Stjrz_streamp strm; 105131377Stjr{ 106131377Stjr struct inflate_state FAR *state; 10733904Ssteve 108131377Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 109131377Stjr state = (struct inflate_state FAR *)strm->state; 110131377Stjr strm->total_in = strm->total_out = state->total = 0; 111131377Stjr strm->msg = Z_NULL; 112230837Sdelphij if (state->wrap) /* to support ill-conceived Java test suite */ 113230837Sdelphij strm->adler = state->wrap & 1; 114131377Stjr state->mode = HEAD; 115131377Stjr state->last = 0; 116131377Stjr state->havedict = 0; 117157043Sdes state->dmax = 32768U; 118157043Sdes state->head = Z_NULL; 119131377Stjr state->hold = 0; 120131377Stjr state->bits = 0; 121131377Stjr state->lencode = state->distcode = state->next = state->codes; 122205194Sdelphij state->sane = 1; 123205194Sdelphij state->back = -1; 124131377Stjr Tracev((stderr, "inflate: reset\n")); 125131377Stjr return Z_OK; 126131377Stjr} 12733904Ssteve 128230837Sdelphijint ZEXPORT inflateReset(strm) 129230837Sdelphijz_streamp strm; 130230837Sdelphij{ 131230837Sdelphij struct inflate_state FAR *state; 132230837Sdelphij 133230837Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 134230837Sdelphij state = (struct inflate_state FAR *)strm->state; 135230837Sdelphij state->wsize = 0; 136230837Sdelphij state->whave = 0; 137230837Sdelphij state->wnext = 0; 138230837Sdelphij return inflateResetKeep(strm); 139230837Sdelphij} 140230837Sdelphij 141205194Sdelphijint ZEXPORT inflateReset2(strm, windowBits) 142157043Sdesz_streamp strm; 143205194Sdelphijint windowBits; 144157043Sdes{ 145205194Sdelphij int wrap; 146157043Sdes struct inflate_state FAR *state; 147157043Sdes 148205194Sdelphij /* get the state */ 149157043Sdes if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 150157043Sdes state = (struct inflate_state FAR *)strm->state; 151205194Sdelphij 152205194Sdelphij /* extract wrap request from windowBits parameter */ 153205194Sdelphij if (windowBits < 0) { 154205194Sdelphij wrap = 0; 155205194Sdelphij windowBits = -windowBits; 156205194Sdelphij } 157205194Sdelphij else { 158205194Sdelphij wrap = (windowBits >> 4) + 1; 159205194Sdelphij#ifdef GUNZIP 160205194Sdelphij if (windowBits < 48) 161205194Sdelphij windowBits &= 15; 162205194Sdelphij#endif 163205194Sdelphij } 164205194Sdelphij 165205194Sdelphij /* set number of window bits, free window if different */ 166205194Sdelphij if (windowBits && (windowBits < 8 || windowBits > 15)) 167205194Sdelphij return Z_STREAM_ERROR; 168205194Sdelphij if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) { 169205194Sdelphij ZFREE(strm, state->window); 170205194Sdelphij state->window = Z_NULL; 171205194Sdelphij } 172205194Sdelphij 173205194Sdelphij /* update state and reset the rest of it */ 174205194Sdelphij state->wrap = wrap; 175205194Sdelphij state->wbits = (unsigned)windowBits; 176205194Sdelphij return inflateReset(strm); 177157043Sdes} 178157043Sdes 179131377Stjrint ZEXPORT inflateInit2_(strm, windowBits, version, stream_size) 180131377Stjrz_streamp strm; 181131377Stjrint windowBits; 182131377Stjrconst char *version; 183131377Stjrint stream_size; 184131377Stjr{ 185205194Sdelphij int ret; 186131377Stjr struct inflate_state FAR *state; 18717651Speter 188131377Stjr if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 189131377Stjr stream_size != (int)(sizeof(z_stream))) 190131377Stjr return Z_VERSION_ERROR; 191131377Stjr if (strm == Z_NULL) return Z_STREAM_ERROR; 192131377Stjr strm->msg = Z_NULL; /* in case we return an error */ 193131377Stjr if (strm->zalloc == (alloc_func)0) { 194230837Sdelphij#ifdef Z_SOLO 195230837Sdelphij return Z_STREAM_ERROR; 196230837Sdelphij#else 197131377Stjr strm->zalloc = zcalloc; 198131377Stjr strm->opaque = (voidpf)0; 199230837Sdelphij#endif 200131377Stjr } 201230837Sdelphij if (strm->zfree == (free_func)0) 202230837Sdelphij#ifdef Z_SOLO 203230837Sdelphij return Z_STREAM_ERROR; 204230837Sdelphij#else 205230837Sdelphij strm->zfree = zcfree; 206230837Sdelphij#endif 207131377Stjr state = (struct inflate_state FAR *) 208131377Stjr ZALLOC(strm, 1, sizeof(struct inflate_state)); 209131377Stjr if (state == Z_NULL) return Z_MEM_ERROR; 210131377Stjr Tracev((stderr, "inflate: allocated\n")); 211157043Sdes strm->state = (struct internal_state FAR *)state; 212205194Sdelphij state->window = Z_NULL; 213205194Sdelphij ret = inflateReset2(strm, windowBits); 214205194Sdelphij if (ret != Z_OK) { 215131377Stjr ZFREE(strm, state); 216131377Stjr strm->state = Z_NULL; 217131377Stjr } 218205194Sdelphij return ret; 219131377Stjr} 22017651Speter 221131377Stjrint ZEXPORT inflateInit_(strm, version, stream_size) 222131377Stjrz_streamp strm; 223131377Stjrconst char *version; 224131377Stjrint stream_size; 22517651Speter{ 226131377Stjr return inflateInit2_(strm, DEF_WBITS, version, stream_size); 22717651Speter} 22817651Speter 229205194Sdelphijint ZEXPORT inflatePrime(strm, bits, value) 230205194Sdelphijz_streamp strm; 231205194Sdelphijint bits; 232205194Sdelphijint value; 233205194Sdelphij{ 234205194Sdelphij struct inflate_state FAR *state; 235205194Sdelphij 236205194Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 237205194Sdelphij state = (struct inflate_state FAR *)strm->state; 238205194Sdelphij if (bits < 0) { 239205194Sdelphij state->hold = 0; 240205194Sdelphij state->bits = 0; 241205194Sdelphij return Z_OK; 242205194Sdelphij } 243205194Sdelphij if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR; 244205194Sdelphij value &= (1L << bits) - 1; 245205194Sdelphij state->hold += value << state->bits; 246205194Sdelphij state->bits += bits; 247205194Sdelphij return Z_OK; 248205194Sdelphij} 249205194Sdelphij 250131377Stjr/* 251131377Stjr Return state with length and distance decoding tables and index sizes set to 252131377Stjr fixed code decoding. Normally this returns fixed tables from inffixed.h. 253131377Stjr If BUILDFIXED is defined, then instead this routine builds the tables the 254131377Stjr first time it's called, and returns those tables the first time and 255131377Stjr thereafter. This reduces the size of the code by about 2K bytes, in 256131377Stjr exchange for a little execution time. However, BUILDFIXED should not be 257131377Stjr used for threaded applications, since the rewriting of the tables and virgin 258131377Stjr may not be thread-safe. 259131377Stjr */ 260131377Stjrlocal void fixedtables(state) 261131377Stjrstruct inflate_state FAR *state; 262131377Stjr{ 263131377Stjr#ifdef BUILDFIXED 264131377Stjr static int virgin = 1; 265131377Stjr static code *lenfix, *distfix; 266131377Stjr static code fixed[544]; 26717651Speter 268131377Stjr /* build fixed huffman tables if first call (may not be thread safe) */ 269131377Stjr if (virgin) { 270131377Stjr unsigned sym, bits; 271131377Stjr static code *next; 272131377Stjr 273131377Stjr /* literal/length table */ 274131377Stjr sym = 0; 275131377Stjr while (sym < 144) state->lens[sym++] = 8; 276131377Stjr while (sym < 256) state->lens[sym++] = 9; 277131377Stjr while (sym < 280) state->lens[sym++] = 7; 278131377Stjr while (sym < 288) state->lens[sym++] = 8; 279131377Stjr next = fixed; 280131377Stjr lenfix = next; 281131377Stjr bits = 9; 282131377Stjr inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); 283131377Stjr 284131377Stjr /* distance table */ 285131377Stjr sym = 0; 286131377Stjr while (sym < 32) state->lens[sym++] = 5; 287131377Stjr distfix = next; 288131377Stjr bits = 5; 289131377Stjr inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); 290131377Stjr 291131377Stjr /* do this just once */ 292131377Stjr virgin = 0; 293131377Stjr } 294131377Stjr#else /* !BUILDFIXED */ 295131377Stjr# include "inffixed.h" 296131377Stjr#endif /* BUILDFIXED */ 297131377Stjr state->lencode = lenfix; 298131377Stjr state->lenbits = 9; 299131377Stjr state->distcode = distfix; 300131377Stjr state->distbits = 5; 30117651Speter} 30217651Speter 303131377Stjr#ifdef MAKEFIXED 304131377Stjr#include <stdio.h> 30517651Speter 306131377Stjr/* 307131377Stjr Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also 308131377Stjr defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 309131377Stjr those tables to stdout, which would be piped to inffixed.h. A small program 310131377Stjr can simply call makefixed to do this: 31117651Speter 312131377Stjr void makefixed(void); 31317651Speter 314131377Stjr int main(void) 315131377Stjr { 316131377Stjr makefixed(); 317131377Stjr return 0; 318131377Stjr } 31917651Speter 320131377Stjr Then that can be linked with zlib built with MAKEFIXED defined and run: 32117651Speter 322131377Stjr a.out > inffixed.h 323131377Stjr */ 324131377Stjrvoid makefixed() 325131377Stjr{ 326131377Stjr unsigned low, size; 327131377Stjr struct inflate_state state; 32817651Speter 329131377Stjr fixedtables(&state); 330131377Stjr puts(" /* inffixed.h -- table for decoding fixed codes"); 331131377Stjr puts(" * Generated automatically by makefixed()."); 332131377Stjr puts(" */"); 333131377Stjr puts(""); 334131377Stjr puts(" /* WARNING: this file should *not* be used by applications."); 335131377Stjr puts(" It is part of the implementation of this library and is"); 336131377Stjr puts(" subject to change. Applications should only use zlib.h."); 337131377Stjr puts(" */"); 338131377Stjr puts(""); 339131377Stjr size = 1U << 9; 340131377Stjr printf(" static const code lenfix[%u] = {", size); 341131377Stjr low = 0; 342131377Stjr for (;;) { 343131377Stjr if ((low % 7) == 0) printf("\n "); 344230837Sdelphij printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op, 345230837Sdelphij state.lencode[low].bits, state.lencode[low].val); 346131377Stjr if (++low == size) break; 347131377Stjr putchar(','); 348131377Stjr } 349131377Stjr puts("\n };"); 350131377Stjr size = 1U << 5; 351131377Stjr printf("\n static const code distfix[%u] = {", size); 352131377Stjr low = 0; 353131377Stjr for (;;) { 354131377Stjr if ((low % 6) == 0) printf("\n "); 355131377Stjr printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits, 356131377Stjr state.distcode[low].val); 357131377Stjr if (++low == size) break; 358131377Stjr putchar(','); 359131377Stjr } 360131377Stjr puts("\n };"); 36117651Speter} 362131377Stjr#endif /* MAKEFIXED */ 36317651Speter 364131377Stjr/* 365131377Stjr Update the window with the last wsize (normally 32K) bytes written before 366131377Stjr returning. If window does not exist yet, create it. This is only called 367131377Stjr when a window is already in use, or when output has been written during this 368131377Stjr inflate call, but the end of the deflate stream has not been reached yet. 369131377Stjr It is also called to create a window for dictionary data when a dictionary 370131377Stjr is loaded. 37117651Speter 372131377Stjr Providing output buffers larger than 32K to inflate() should provide a speed 373131377Stjr advantage, since only the last 32K of output is copied to the sliding window 374131377Stjr upon return from inflate(), and since all distances after the first 32K of 375131377Stjr output will fall in the output data, making match copies simpler and faster. 376131377Stjr The advantage may be dependent on the size of the processor's data caches. 377131377Stjr */ 378131377Stjrlocal int updatewindow(strm, out) 379131377Stjrz_streamp strm; 380131377Stjrunsigned out; 38117651Speter{ 382131377Stjr struct inflate_state FAR *state; 383131377Stjr unsigned copy, dist; 384131377Stjr 385131377Stjr state = (struct inflate_state FAR *)strm->state; 386131377Stjr 387131377Stjr /* if it hasn't been done already, allocate space for the window */ 388131377Stjr if (state->window == Z_NULL) { 389131377Stjr state->window = (unsigned char FAR *) 390131377Stjr ZALLOC(strm, 1U << state->wbits, 391131377Stjr sizeof(unsigned char)); 392131377Stjr if (state->window == Z_NULL) return 1; 393131377Stjr } 394131377Stjr 395131377Stjr /* if window not in use yet, initialize */ 396131377Stjr if (state->wsize == 0) { 397131377Stjr state->wsize = 1U << state->wbits; 398205194Sdelphij state->wnext = 0; 399131377Stjr state->whave = 0; 400131377Stjr } 401131377Stjr 402131377Stjr /* copy state->wsize or less output bytes into the circular window */ 403131377Stjr copy = out - strm->avail_out; 404131377Stjr if (copy >= state->wsize) { 405131377Stjr zmemcpy(state->window, strm->next_out - state->wsize, state->wsize); 406205194Sdelphij state->wnext = 0; 407131377Stjr state->whave = state->wsize; 408131377Stjr } 409131377Stjr else { 410205194Sdelphij dist = state->wsize - state->wnext; 411131377Stjr if (dist > copy) dist = copy; 412205194Sdelphij zmemcpy(state->window + state->wnext, strm->next_out - copy, dist); 413131377Stjr copy -= dist; 414131377Stjr if (copy) { 415131377Stjr zmemcpy(state->window, strm->next_out - copy, copy); 416205194Sdelphij state->wnext = copy; 417131377Stjr state->whave = state->wsize; 418131377Stjr } 419131377Stjr else { 420205194Sdelphij state->wnext += dist; 421205194Sdelphij if (state->wnext == state->wsize) state->wnext = 0; 422131377Stjr if (state->whave < state->wsize) state->whave += dist; 423131377Stjr } 424131377Stjr } 425131377Stjr return 0; 42617651Speter} 42717651Speter 428131377Stjr/* Macros for inflate(): */ 42917651Speter 430131377Stjr/* check function to use adler32() for zlib or crc32() for gzip */ 431131377Stjr#ifdef GUNZIP 432131377Stjr# define UPDATE(check, buf, len) \ 433131377Stjr (state->flags ? crc32(check, buf, len) : adler32(check, buf, len)) 434131377Stjr#else 435131377Stjr# define UPDATE(check, buf, len) adler32(check, buf, len) 436131377Stjr#endif 43717651Speter 438131377Stjr/* check macros for header crc */ 439131377Stjr#ifdef GUNZIP 440131377Stjr# define CRC2(check, word) \ 441131377Stjr do { \ 442131377Stjr hbuf[0] = (unsigned char)(word); \ 443131377Stjr hbuf[1] = (unsigned char)((word) >> 8); \ 444131377Stjr check = crc32(check, hbuf, 2); \ 445131377Stjr } while (0) 44617651Speter 447131377Stjr# define CRC4(check, word) \ 448131377Stjr do { \ 449131377Stjr hbuf[0] = (unsigned char)(word); \ 450131377Stjr hbuf[1] = (unsigned char)((word) >> 8); \ 451131377Stjr hbuf[2] = (unsigned char)((word) >> 16); \ 452131377Stjr hbuf[3] = (unsigned char)((word) >> 24); \ 453131377Stjr check = crc32(check, hbuf, 4); \ 454131377Stjr } while (0) 455131377Stjr#endif 456131377Stjr 457131377Stjr/* Load registers with state in inflate() for speed */ 458131377Stjr#define LOAD() \ 459131377Stjr do { \ 460131377Stjr put = strm->next_out; \ 461131377Stjr left = strm->avail_out; \ 462131377Stjr next = strm->next_in; \ 463131377Stjr have = strm->avail_in; \ 464131377Stjr hold = state->hold; \ 465131377Stjr bits = state->bits; \ 466131377Stjr } while (0) 467131377Stjr 468131377Stjr/* Restore state from registers in inflate() */ 469131377Stjr#define RESTORE() \ 470131377Stjr do { \ 471131377Stjr strm->next_out = put; \ 472131377Stjr strm->avail_out = left; \ 473131377Stjr strm->next_in = next; \ 474131377Stjr strm->avail_in = have; \ 475131377Stjr state->hold = hold; \ 476131377Stjr state->bits = bits; \ 477131377Stjr } while (0) 478131377Stjr 479131377Stjr/* Clear the input bit accumulator */ 480131377Stjr#define INITBITS() \ 481131377Stjr do { \ 482131377Stjr hold = 0; \ 483131377Stjr bits = 0; \ 484131377Stjr } while (0) 485131377Stjr 486131377Stjr/* Get a byte of input into the bit accumulator, or return from inflate() 487131377Stjr if there is no input available. */ 488131377Stjr#define PULLBYTE() \ 489131377Stjr do { \ 490131377Stjr if (have == 0) goto inf_leave; \ 491131377Stjr have--; \ 492131377Stjr hold += (unsigned long)(*next++) << bits; \ 493131377Stjr bits += 8; \ 494131377Stjr } while (0) 495131377Stjr 496131377Stjr/* Assure that there are at least n bits in the bit accumulator. If there is 497131377Stjr not enough available input to do that, then return from inflate(). */ 498131377Stjr#define NEEDBITS(n) \ 499131377Stjr do { \ 500131377Stjr while (bits < (unsigned)(n)) \ 501131377Stjr PULLBYTE(); \ 502131377Stjr } while (0) 503131377Stjr 504131377Stjr/* Return the low n bits of the bit accumulator (n < 16) */ 505131377Stjr#define BITS(n) \ 506131377Stjr ((unsigned)hold & ((1U << (n)) - 1)) 507131377Stjr 508131377Stjr/* Remove n bits from the bit accumulator */ 509131377Stjr#define DROPBITS(n) \ 510131377Stjr do { \ 511131377Stjr hold >>= (n); \ 512131377Stjr bits -= (unsigned)(n); \ 513131377Stjr } while (0) 514131377Stjr 515131377Stjr/* Remove zero to seven bits as needed to go to a byte boundary */ 516131377Stjr#define BYTEBITS() \ 517131377Stjr do { \ 518131377Stjr hold >>= bits & 7; \ 519131377Stjr bits -= bits & 7; \ 520131377Stjr } while (0) 521131377Stjr 522131377Stjr/* 523131377Stjr inflate() uses a state machine to process as much input data and generate as 524131377Stjr much output data as possible before returning. The state machine is 525131377Stjr structured roughly as follows: 526131377Stjr 527131377Stjr for (;;) switch (state) { 528131377Stjr ... 529131377Stjr case STATEn: 530131377Stjr if (not enough input data or output space to make progress) 531131377Stjr return; 532131377Stjr ... make progress ... 533131377Stjr state = STATEm; 53417651Speter break; 535131377Stjr ... 536131377Stjr } 53717651Speter 538131377Stjr so when inflate() is called again, the same case is attempted again, and 539131377Stjr if the appropriate resources are provided, the machine proceeds to the 540131377Stjr next state. The NEEDBITS() macro is usually the way the state evaluates 541131377Stjr whether it can proceed or should return. NEEDBITS() does the return if 542131377Stjr the requested bits are not available. The typical use of the BITS macros 543131377Stjr is: 544131377Stjr 545131377Stjr NEEDBITS(n); 546131377Stjr ... do something with BITS(n) ... 547131377Stjr DROPBITS(n); 548131377Stjr 549131377Stjr where NEEDBITS(n) either returns from inflate() if there isn't enough 550131377Stjr input left to load n bits into the accumulator, or it continues. BITS(n) 551131377Stjr gives the low n bits in the accumulator. When done, DROPBITS(n) drops 552131377Stjr the low n bits off the accumulator. INITBITS() clears the accumulator 553131377Stjr and sets the number of available bits to zero. BYTEBITS() discards just 554131377Stjr enough bits to put the accumulator on a byte boundary. After BYTEBITS() 555131377Stjr and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 556131377Stjr 557131377Stjr NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 558131377Stjr if there is no input available. The decoding of variable length codes uses 559131377Stjr PULLBYTE() directly in order to pull just enough bytes to decode the next 560131377Stjr code, and no more. 561131377Stjr 562131377Stjr Some states loop until they get enough input, making sure that enough 563131377Stjr state information is maintained to continue the loop where it left off 564131377Stjr if NEEDBITS() returns in the loop. For example, want, need, and keep 565131377Stjr would all have to actually be part of the saved state in case NEEDBITS() 566131377Stjr returns: 567131377Stjr 568131377Stjr case STATEw: 569131377Stjr while (want < need) { 570131377Stjr NEEDBITS(n); 571131377Stjr keep[want++] = BITS(n); 572131377Stjr DROPBITS(n); 573131377Stjr } 574131377Stjr state = STATEx; 575131377Stjr case STATEx: 576131377Stjr 577131377Stjr As shown above, if the next state is also the next case, then the break 578131377Stjr is omitted. 579131377Stjr 580131377Stjr A state may also return if there is not enough output space available to 581131377Stjr complete that state. Those states are copying stored data, writing a 582131377Stjr literal byte, and copying a matching string. 583131377Stjr 584131377Stjr When returning, a "goto inf_leave" is used to update the total counters, 585131377Stjr update the check value, and determine whether any progress has been made 586131377Stjr during that inflate() call in order to return the proper return code. 587131377Stjr Progress is defined as a change in either strm->avail_in or strm->avail_out. 588131377Stjr When there is a window, goto inf_leave will update the window with the last 589131377Stjr output written. If a goto inf_leave occurs in the middle of decompression 590131377Stjr and there is no window currently, goto inf_leave will create one and copy 591131377Stjr output to the window for the next call of inflate(). 592131377Stjr 593131377Stjr In this implementation, the flush parameter of inflate() only affects the 594131377Stjr return code (per zlib.h). inflate() always writes as much as possible to 595131377Stjr strm->next_out, given the space available and the provided input--the effect 596131377Stjr documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 597131377Stjr the allocation of and copying into a sliding window until necessary, which 598131377Stjr provides the effect documented in zlib.h for Z_FINISH when the entire input 599131377Stjr stream available. So the only thing the flush parameter actually does is: 600131377Stjr when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 601131377Stjr will return Z_BUF_ERROR if it has not reached the end of the stream. 602131377Stjr */ 603131377Stjr 604131377Stjrint ZEXPORT inflate(strm, flush) 605131377Stjrz_streamp strm; 606131377Stjrint flush; 607131377Stjr{ 608131377Stjr struct inflate_state FAR *state; 609131377Stjr unsigned char FAR *next; /* next input */ 610131377Stjr unsigned char FAR *put; /* next output */ 611131377Stjr unsigned have, left; /* available input and output */ 612131377Stjr unsigned long hold; /* bit buffer */ 613131377Stjr unsigned bits; /* bits in bit buffer */ 614131377Stjr unsigned in, out; /* save starting available input and output */ 615131377Stjr unsigned copy; /* number of stored or match bytes to copy */ 616131377Stjr unsigned char FAR *from; /* where to copy match bytes from */ 617205194Sdelphij code here; /* current decoding table entry */ 618131377Stjr code last; /* parent table entry */ 619131377Stjr unsigned len; /* length to copy for repeats, bits to drop */ 620131377Stjr int ret; /* return code */ 621131377Stjr#ifdef GUNZIP 622131377Stjr unsigned char hbuf[4]; /* buffer for gzip header crc calculation */ 62333904Ssteve#endif 624131377Stjr static const unsigned short order[19] = /* permutation of code lengths */ 625131377Stjr {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 626131377Stjr 627131377Stjr if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 628131377Stjr (strm->next_in == Z_NULL && strm->avail_in != 0)) 629131377Stjr return Z_STREAM_ERROR; 630131377Stjr 631131377Stjr state = (struct inflate_state FAR *)strm->state; 632131377Stjr if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 633131377Stjr LOAD(); 634131377Stjr in = have; 635131377Stjr out = left; 636131377Stjr ret = Z_OK; 637131377Stjr for (;;) 638131377Stjr switch (state->mode) { 639131377Stjr case HEAD: 640131377Stjr if (state->wrap == 0) { 641131377Stjr state->mode = TYPEDO; 642131377Stjr break; 643131377Stjr } 644131377Stjr NEEDBITS(16); 645131377Stjr#ifdef GUNZIP 646131377Stjr if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */ 647131377Stjr state->check = crc32(0L, Z_NULL, 0); 648131377Stjr CRC2(state->check, hold); 649131377Stjr INITBITS(); 650131377Stjr state->mode = FLAGS; 651131377Stjr break; 652131377Stjr } 653131377Stjr state->flags = 0; /* expect zlib header */ 654157043Sdes if (state->head != Z_NULL) 655157043Sdes state->head->done = -1; 656131377Stjr if (!(state->wrap & 1) || /* check if zlib header allowed */ 657131377Stjr#else 658131377Stjr if ( 659131377Stjr#endif 660131377Stjr ((BITS(8) << 8) + (hold >> 8)) % 31) { 661131377Stjr strm->msg = (char *)"incorrect header check"; 662131377Stjr state->mode = BAD; 663131377Stjr break; 664131377Stjr } 665131377Stjr if (BITS(4) != Z_DEFLATED) { 666131377Stjr strm->msg = (char *)"unknown compression method"; 667131377Stjr state->mode = BAD; 668131377Stjr break; 669131377Stjr } 670131377Stjr DROPBITS(4); 671157043Sdes len = BITS(4) + 8; 672205194Sdelphij if (state->wbits == 0) 673205194Sdelphij state->wbits = len; 674205194Sdelphij else if (len > state->wbits) { 675131377Stjr strm->msg = (char *)"invalid window size"; 676131377Stjr state->mode = BAD; 677131377Stjr break; 678131377Stjr } 679157043Sdes state->dmax = 1U << len; 680131377Stjr Tracev((stderr, "inflate: zlib header ok\n")); 681131377Stjr strm->adler = state->check = adler32(0L, Z_NULL, 0); 682131377Stjr state->mode = hold & 0x200 ? DICTID : TYPE; 683131377Stjr INITBITS(); 684131377Stjr break; 685131377Stjr#ifdef GUNZIP 686131377Stjr case FLAGS: 687131377Stjr NEEDBITS(16); 688131377Stjr state->flags = (int)(hold); 689131377Stjr if ((state->flags & 0xff) != Z_DEFLATED) { 690131377Stjr strm->msg = (char *)"unknown compression method"; 691131377Stjr state->mode = BAD; 692131377Stjr break; 693131377Stjr } 694131377Stjr if (state->flags & 0xe000) { 695131377Stjr strm->msg = (char *)"unknown header flags set"; 696131377Stjr state->mode = BAD; 697131377Stjr break; 698131377Stjr } 699157043Sdes if (state->head != Z_NULL) 700157043Sdes state->head->text = (int)((hold >> 8) & 1); 701131377Stjr if (state->flags & 0x0200) CRC2(state->check, hold); 702131377Stjr INITBITS(); 703131377Stjr state->mode = TIME; 704131377Stjr case TIME: 705131377Stjr NEEDBITS(32); 706157043Sdes if (state->head != Z_NULL) 707157043Sdes state->head->time = hold; 708131377Stjr if (state->flags & 0x0200) CRC4(state->check, hold); 709131377Stjr INITBITS(); 710131377Stjr state->mode = OS; 711131377Stjr case OS: 712131377Stjr NEEDBITS(16); 713157043Sdes if (state->head != Z_NULL) { 714157043Sdes state->head->xflags = (int)(hold & 0xff); 715157043Sdes state->head->os = (int)(hold >> 8); 716157043Sdes } 717131377Stjr if (state->flags & 0x0200) CRC2(state->check, hold); 718131377Stjr INITBITS(); 719131377Stjr state->mode = EXLEN; 720131377Stjr case EXLEN: 721131377Stjr if (state->flags & 0x0400) { 722131377Stjr NEEDBITS(16); 723131377Stjr state->length = (unsigned)(hold); 724157043Sdes if (state->head != Z_NULL) 725157043Sdes state->head->extra_len = (unsigned)hold; 726131377Stjr if (state->flags & 0x0200) CRC2(state->check, hold); 727131377Stjr INITBITS(); 728131377Stjr } 729157043Sdes else if (state->head != Z_NULL) 730157043Sdes state->head->extra = Z_NULL; 731131377Stjr state->mode = EXTRA; 732131377Stjr case EXTRA: 733131377Stjr if (state->flags & 0x0400) { 734131377Stjr copy = state->length; 735131377Stjr if (copy > have) copy = have; 736131377Stjr if (copy) { 737157043Sdes if (state->head != Z_NULL && 738157043Sdes state->head->extra != Z_NULL) { 739157043Sdes len = state->head->extra_len - state->length; 740157043Sdes zmemcpy(state->head->extra + len, next, 741157043Sdes len + copy > state->head->extra_max ? 742157043Sdes state->head->extra_max - len : copy); 743157043Sdes } 744131377Stjr if (state->flags & 0x0200) 745131377Stjr state->check = crc32(state->check, next, copy); 746131377Stjr have -= copy; 747131377Stjr next += copy; 748131377Stjr state->length -= copy; 749131377Stjr } 750131377Stjr if (state->length) goto inf_leave; 751131377Stjr } 752157043Sdes state->length = 0; 753131377Stjr state->mode = NAME; 754131377Stjr case NAME: 755131377Stjr if (state->flags & 0x0800) { 756131377Stjr if (have == 0) goto inf_leave; 757131377Stjr copy = 0; 758131377Stjr do { 759131377Stjr len = (unsigned)(next[copy++]); 760157043Sdes if (state->head != Z_NULL && 761157043Sdes state->head->name != Z_NULL && 762157043Sdes state->length < state->head->name_max) 763157043Sdes state->head->name[state->length++] = len; 764131377Stjr } while (len && copy < have); 765157043Sdes if (state->flags & 0x0200) 766131377Stjr state->check = crc32(state->check, next, copy); 767131377Stjr have -= copy; 768131377Stjr next += copy; 769131377Stjr if (len) goto inf_leave; 770131377Stjr } 771157043Sdes else if (state->head != Z_NULL) 772157043Sdes state->head->name = Z_NULL; 773157043Sdes state->length = 0; 774131377Stjr state->mode = COMMENT; 775131377Stjr case COMMENT: 776131377Stjr if (state->flags & 0x1000) { 777131377Stjr if (have == 0) goto inf_leave; 778131377Stjr copy = 0; 779131377Stjr do { 780131377Stjr len = (unsigned)(next[copy++]); 781157043Sdes if (state->head != Z_NULL && 782157043Sdes state->head->comment != Z_NULL && 783157043Sdes state->length < state->head->comm_max) 784157043Sdes state->head->comment[state->length++] = len; 785131377Stjr } while (len && copy < have); 786157043Sdes if (state->flags & 0x0200) 787131377Stjr state->check = crc32(state->check, next, copy); 788131377Stjr have -= copy; 789131377Stjr next += copy; 790131377Stjr if (len) goto inf_leave; 791131377Stjr } 792157043Sdes else if (state->head != Z_NULL) 793157043Sdes state->head->comment = Z_NULL; 794131377Stjr state->mode = HCRC; 795131377Stjr case HCRC: 796131377Stjr if (state->flags & 0x0200) { 797131377Stjr NEEDBITS(16); 798131377Stjr if (hold != (state->check & 0xffff)) { 799131377Stjr strm->msg = (char *)"header crc mismatch"; 800131377Stjr state->mode = BAD; 801131377Stjr break; 802131377Stjr } 803131377Stjr INITBITS(); 804131377Stjr } 805157043Sdes if (state->head != Z_NULL) { 806157043Sdes state->head->hcrc = (int)((state->flags >> 9) & 1); 807157043Sdes state->head->done = 1; 808157043Sdes } 809131377Stjr strm->adler = state->check = crc32(0L, Z_NULL, 0); 810131377Stjr state->mode = TYPE; 811131377Stjr break; 812131377Stjr#endif 813131377Stjr case DICTID: 814131377Stjr NEEDBITS(32); 815237248Sdelphij strm->adler = state->check = ZSWAP32(hold); 816131377Stjr INITBITS(); 817131377Stjr state->mode = DICT; 818131377Stjr case DICT: 819131377Stjr if (state->havedict == 0) { 820131377Stjr RESTORE(); 821131377Stjr return Z_NEED_DICT; 822131377Stjr } 823131377Stjr strm->adler = state->check = adler32(0L, Z_NULL, 0); 824131377Stjr state->mode = TYPE; 825131377Stjr case TYPE: 826205194Sdelphij if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave; 827131377Stjr case TYPEDO: 828131377Stjr if (state->last) { 829131377Stjr BYTEBITS(); 830131377Stjr state->mode = CHECK; 831131377Stjr break; 832131377Stjr } 833131377Stjr NEEDBITS(3); 834131377Stjr state->last = BITS(1); 835131377Stjr DROPBITS(1); 836131377Stjr switch (BITS(2)) { 837131377Stjr case 0: /* stored block */ 838131377Stjr Tracev((stderr, "inflate: stored block%s\n", 839131377Stjr state->last ? " (last)" : "")); 840131377Stjr state->mode = STORED; 841131377Stjr break; 842131377Stjr case 1: /* fixed block */ 843131377Stjr fixedtables(state); 844131377Stjr Tracev((stderr, "inflate: fixed codes block%s\n", 845131377Stjr state->last ? " (last)" : "")); 846205194Sdelphij state->mode = LEN_; /* decode codes */ 847205194Sdelphij if (flush == Z_TREES) { 848205194Sdelphij DROPBITS(2); 849205194Sdelphij goto inf_leave; 850205194Sdelphij } 851131377Stjr break; 852131377Stjr case 2: /* dynamic block */ 853131377Stjr Tracev((stderr, "inflate: dynamic codes block%s\n", 854131377Stjr state->last ? " (last)" : "")); 855131377Stjr state->mode = TABLE; 856131377Stjr break; 857131377Stjr case 3: 858131377Stjr strm->msg = (char *)"invalid block type"; 859131377Stjr state->mode = BAD; 860131377Stjr } 861131377Stjr DROPBITS(2); 862131377Stjr break; 863131377Stjr case STORED: 864131377Stjr BYTEBITS(); /* go to byte boundary */ 865131377Stjr NEEDBITS(32); 866131377Stjr if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 867131377Stjr strm->msg = (char *)"invalid stored block lengths"; 868131377Stjr state->mode = BAD; 869131377Stjr break; 870131377Stjr } 871131377Stjr state->length = (unsigned)hold & 0xffff; 872131377Stjr Tracev((stderr, "inflate: stored length %u\n", 873131377Stjr state->length)); 874131377Stjr INITBITS(); 875205194Sdelphij state->mode = COPY_; 876205194Sdelphij if (flush == Z_TREES) goto inf_leave; 877205194Sdelphij case COPY_: 878131377Stjr state->mode = COPY; 879131377Stjr case COPY: 880131377Stjr copy = state->length; 881131377Stjr if (copy) { 882131377Stjr if (copy > have) copy = have; 883131377Stjr if (copy > left) copy = left; 884131377Stjr if (copy == 0) goto inf_leave; 885131377Stjr zmemcpy(put, next, copy); 886131377Stjr have -= copy; 887131377Stjr next += copy; 888131377Stjr left -= copy; 889131377Stjr put += copy; 890131377Stjr state->length -= copy; 891131377Stjr break; 892131377Stjr } 893131377Stjr Tracev((stderr, "inflate: stored end\n")); 894131377Stjr state->mode = TYPE; 895131377Stjr break; 896131377Stjr case TABLE: 897131377Stjr NEEDBITS(14); 898131377Stjr state->nlen = BITS(5) + 257; 899131377Stjr DROPBITS(5); 900131377Stjr state->ndist = BITS(5) + 1; 901131377Stjr DROPBITS(5); 902131377Stjr state->ncode = BITS(4) + 4; 903131377Stjr DROPBITS(4); 904131377Stjr#ifndef PKZIP_BUG_WORKAROUND 905131377Stjr if (state->nlen > 286 || state->ndist > 30) { 906131377Stjr strm->msg = (char *)"too many length or distance symbols"; 907131377Stjr state->mode = BAD; 908131377Stjr break; 909131377Stjr } 910131377Stjr#endif 911131377Stjr Tracev((stderr, "inflate: table sizes ok\n")); 912131377Stjr state->have = 0; 913131377Stjr state->mode = LENLENS; 914131377Stjr case LENLENS: 915131377Stjr while (state->have < state->ncode) { 916131377Stjr NEEDBITS(3); 917131377Stjr state->lens[order[state->have++]] = (unsigned short)BITS(3); 918131377Stjr DROPBITS(3); 919131377Stjr } 920131377Stjr while (state->have < 19) 921131377Stjr state->lens[order[state->have++]] = 0; 922131377Stjr state->next = state->codes; 923131377Stjr state->lencode = (code const FAR *)(state->next); 924131377Stjr state->lenbits = 7; 925131377Stjr ret = inflate_table(CODES, state->lens, 19, &(state->next), 926131377Stjr &(state->lenbits), state->work); 927131377Stjr if (ret) { 928131377Stjr strm->msg = (char *)"invalid code lengths set"; 929131377Stjr state->mode = BAD; 930131377Stjr break; 931131377Stjr } 932131377Stjr Tracev((stderr, "inflate: code lengths ok\n")); 933131377Stjr state->have = 0; 934131377Stjr state->mode = CODELENS; 935131377Stjr case CODELENS: 936131377Stjr while (state->have < state->nlen + state->ndist) { 937131377Stjr for (;;) { 938205194Sdelphij here = state->lencode[BITS(state->lenbits)]; 939205194Sdelphij if ((unsigned)(here.bits) <= bits) break; 940131377Stjr PULLBYTE(); 941131377Stjr } 942205194Sdelphij if (here.val < 16) { 943205194Sdelphij DROPBITS(here.bits); 944205194Sdelphij state->lens[state->have++] = here.val; 945131377Stjr } 946131377Stjr else { 947205194Sdelphij if (here.val == 16) { 948205194Sdelphij NEEDBITS(here.bits + 2); 949205194Sdelphij DROPBITS(here.bits); 950131377Stjr if (state->have == 0) { 951131377Stjr strm->msg = (char *)"invalid bit length repeat"; 952131377Stjr state->mode = BAD; 953131377Stjr break; 954131377Stjr } 955131377Stjr len = state->lens[state->have - 1]; 956131377Stjr copy = 3 + BITS(2); 957131377Stjr DROPBITS(2); 958131377Stjr } 959205194Sdelphij else if (here.val == 17) { 960205194Sdelphij NEEDBITS(here.bits + 3); 961205194Sdelphij DROPBITS(here.bits); 962131377Stjr len = 0; 963131377Stjr copy = 3 + BITS(3); 964131377Stjr DROPBITS(3); 965131377Stjr } 966131377Stjr else { 967205194Sdelphij NEEDBITS(here.bits + 7); 968205194Sdelphij DROPBITS(here.bits); 969131377Stjr len = 0; 970131377Stjr copy = 11 + BITS(7); 971131377Stjr DROPBITS(7); 972131377Stjr } 973131377Stjr if (state->have + copy > state->nlen + state->ndist) { 974131377Stjr strm->msg = (char *)"invalid bit length repeat"; 975131377Stjr state->mode = BAD; 976131377Stjr break; 977131377Stjr } 978131377Stjr while (copy--) 979131377Stjr state->lens[state->have++] = (unsigned short)len; 980131377Stjr } 981131377Stjr } 982131377Stjr 983145474Skientzle /* handle error breaks in while */ 984145474Skientzle if (state->mode == BAD) break; 985145474Skientzle 986205194Sdelphij /* check for end-of-block code (better have one) */ 987205194Sdelphij if (state->lens[256] == 0) { 988205194Sdelphij strm->msg = (char *)"invalid code -- missing end-of-block"; 989205194Sdelphij state->mode = BAD; 990205194Sdelphij break; 991205194Sdelphij } 992205194Sdelphij 993205194Sdelphij /* build code tables -- note: do not change the lenbits or distbits 994205194Sdelphij values here (9 and 6) without reading the comments in inftrees.h 995205194Sdelphij concerning the ENOUGH constants, which depend on those values */ 996131377Stjr state->next = state->codes; 997131377Stjr state->lencode = (code const FAR *)(state->next); 998131377Stjr state->lenbits = 9; 999131377Stjr ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 1000131377Stjr &(state->lenbits), state->work); 1001131377Stjr if (ret) { 1002131377Stjr strm->msg = (char *)"invalid literal/lengths set"; 1003131377Stjr state->mode = BAD; 1004131377Stjr break; 1005131377Stjr } 1006131377Stjr state->distcode = (code const FAR *)(state->next); 1007131377Stjr state->distbits = 6; 1008131377Stjr ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 1009131377Stjr &(state->next), &(state->distbits), state->work); 1010131377Stjr if (ret) { 1011131377Stjr strm->msg = (char *)"invalid distances set"; 1012131377Stjr state->mode = BAD; 1013131377Stjr break; 1014131377Stjr } 1015131377Stjr Tracev((stderr, "inflate: codes ok\n")); 1016205194Sdelphij state->mode = LEN_; 1017205194Sdelphij if (flush == Z_TREES) goto inf_leave; 1018205194Sdelphij case LEN_: 1019131377Stjr state->mode = LEN; 1020131377Stjr case LEN: 1021131377Stjr if (have >= 6 && left >= 258) { 1022131377Stjr RESTORE(); 1023131377Stjr inflate_fast(strm, out); 1024131377Stjr LOAD(); 1025205194Sdelphij if (state->mode == TYPE) 1026205194Sdelphij state->back = -1; 1027131377Stjr break; 1028131377Stjr } 1029205194Sdelphij state->back = 0; 1030131377Stjr for (;;) { 1031205194Sdelphij here = state->lencode[BITS(state->lenbits)]; 1032205194Sdelphij if ((unsigned)(here.bits) <= bits) break; 1033131377Stjr PULLBYTE(); 1034131377Stjr } 1035205194Sdelphij if (here.op && (here.op & 0xf0) == 0) { 1036205194Sdelphij last = here; 1037131377Stjr for (;;) { 1038205194Sdelphij here = state->lencode[last.val + 1039131377Stjr (BITS(last.bits + last.op) >> last.bits)]; 1040205194Sdelphij if ((unsigned)(last.bits + here.bits) <= bits) break; 1041131377Stjr PULLBYTE(); 1042131377Stjr } 1043131377Stjr DROPBITS(last.bits); 1044205194Sdelphij state->back += last.bits; 1045131377Stjr } 1046205194Sdelphij DROPBITS(here.bits); 1047205194Sdelphij state->back += here.bits; 1048205194Sdelphij state->length = (unsigned)here.val; 1049205194Sdelphij if ((int)(here.op) == 0) { 1050205194Sdelphij Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? 1051131377Stjr "inflate: literal '%c'\n" : 1052205194Sdelphij "inflate: literal 0x%02x\n", here.val)); 1053131377Stjr state->mode = LIT; 1054131377Stjr break; 1055131377Stjr } 1056205194Sdelphij if (here.op & 32) { 1057131377Stjr Tracevv((stderr, "inflate: end of block\n")); 1058205194Sdelphij state->back = -1; 1059131377Stjr state->mode = TYPE; 1060131377Stjr break; 1061131377Stjr } 1062205194Sdelphij if (here.op & 64) { 1063131377Stjr strm->msg = (char *)"invalid literal/length code"; 1064131377Stjr state->mode = BAD; 1065131377Stjr break; 1066131377Stjr } 1067205194Sdelphij state->extra = (unsigned)(here.op) & 15; 1068131377Stjr state->mode = LENEXT; 1069131377Stjr case LENEXT: 1070131377Stjr if (state->extra) { 1071131377Stjr NEEDBITS(state->extra); 1072131377Stjr state->length += BITS(state->extra); 1073131377Stjr DROPBITS(state->extra); 1074205194Sdelphij state->back += state->extra; 1075131377Stjr } 1076131377Stjr Tracevv((stderr, "inflate: length %u\n", state->length)); 1077205194Sdelphij state->was = state->length; 1078131377Stjr state->mode = DIST; 1079131377Stjr case DIST: 1080131377Stjr for (;;) { 1081205194Sdelphij here = state->distcode[BITS(state->distbits)]; 1082205194Sdelphij if ((unsigned)(here.bits) <= bits) break; 1083131377Stjr PULLBYTE(); 1084131377Stjr } 1085205194Sdelphij if ((here.op & 0xf0) == 0) { 1086205194Sdelphij last = here; 1087131377Stjr for (;;) { 1088205194Sdelphij here = state->distcode[last.val + 1089131377Stjr (BITS(last.bits + last.op) >> last.bits)]; 1090205194Sdelphij if ((unsigned)(last.bits + here.bits) <= bits) break; 1091131377Stjr PULLBYTE(); 1092131377Stjr } 1093131377Stjr DROPBITS(last.bits); 1094205194Sdelphij state->back += last.bits; 1095131377Stjr } 1096205194Sdelphij DROPBITS(here.bits); 1097205194Sdelphij state->back += here.bits; 1098205194Sdelphij if (here.op & 64) { 1099131377Stjr strm->msg = (char *)"invalid distance code"; 1100131377Stjr state->mode = BAD; 1101131377Stjr break; 1102131377Stjr } 1103205194Sdelphij state->offset = (unsigned)here.val; 1104205194Sdelphij state->extra = (unsigned)(here.op) & 15; 1105131377Stjr state->mode = DISTEXT; 1106131377Stjr case DISTEXT: 1107131377Stjr if (state->extra) { 1108131377Stjr NEEDBITS(state->extra); 1109131377Stjr state->offset += BITS(state->extra); 1110131377Stjr DROPBITS(state->extra); 1111205194Sdelphij state->back += state->extra; 1112131377Stjr } 1113157043Sdes#ifdef INFLATE_STRICT 1114157043Sdes if (state->offset > state->dmax) { 1115157043Sdes strm->msg = (char *)"invalid distance too far back"; 1116157043Sdes state->mode = BAD; 1117157043Sdes break; 1118157043Sdes } 1119157043Sdes#endif 1120131377Stjr Tracevv((stderr, "inflate: distance %u\n", state->offset)); 1121131377Stjr state->mode = MATCH; 1122131377Stjr case MATCH: 1123131377Stjr if (left == 0) goto inf_leave; 1124131377Stjr copy = out - left; 1125131377Stjr if (state->offset > copy) { /* copy from window */ 1126131377Stjr copy = state->offset - copy; 1127205194Sdelphij if (copy > state->whave) { 1128205194Sdelphij if (state->sane) { 1129205194Sdelphij strm->msg = (char *)"invalid distance too far back"; 1130205194Sdelphij state->mode = BAD; 1131205194Sdelphij break; 1132205194Sdelphij } 1133205194Sdelphij#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 1134205194Sdelphij Trace((stderr, "inflate.c too far\n")); 1135205194Sdelphij copy -= state->whave; 1136205194Sdelphij if (copy > state->length) copy = state->length; 1137205194Sdelphij if (copy > left) copy = left; 1138205194Sdelphij left -= copy; 1139205194Sdelphij state->length -= copy; 1140205194Sdelphij do { 1141205194Sdelphij *put++ = 0; 1142205194Sdelphij } while (--copy); 1143205194Sdelphij if (state->length == 0) state->mode = LEN; 1144205194Sdelphij break; 1145205194Sdelphij#endif 1146205194Sdelphij } 1147205194Sdelphij if (copy > state->wnext) { 1148205194Sdelphij copy -= state->wnext; 1149131377Stjr from = state->window + (state->wsize - copy); 1150131377Stjr } 1151131377Stjr else 1152205194Sdelphij from = state->window + (state->wnext - copy); 1153131377Stjr if (copy > state->length) copy = state->length; 1154131377Stjr } 1155131377Stjr else { /* copy from output */ 1156131377Stjr from = put - state->offset; 1157131377Stjr copy = state->length; 1158131377Stjr } 1159131377Stjr if (copy > left) copy = left; 1160131377Stjr left -= copy; 1161131377Stjr state->length -= copy; 1162131377Stjr do { 1163131377Stjr *put++ = *from++; 1164131377Stjr } while (--copy); 1165131377Stjr if (state->length == 0) state->mode = LEN; 1166131377Stjr break; 1167131377Stjr case LIT: 1168131377Stjr if (left == 0) goto inf_leave; 1169131377Stjr *put++ = (unsigned char)(state->length); 1170131377Stjr left--; 1171131377Stjr state->mode = LEN; 1172131377Stjr break; 1173131377Stjr case CHECK: 1174131377Stjr if (state->wrap) { 1175131377Stjr NEEDBITS(32); 1176131377Stjr out -= left; 1177131377Stjr strm->total_out += out; 1178131377Stjr state->total += out; 1179131377Stjr if (out) 1180131377Stjr strm->adler = state->check = 1181131377Stjr UPDATE(state->check, put - out, out); 1182131377Stjr out = left; 1183131377Stjr if (( 1184131377Stjr#ifdef GUNZIP 1185131377Stjr state->flags ? hold : 1186131377Stjr#endif 1187237248Sdelphij ZSWAP32(hold)) != state->check) { 1188131377Stjr strm->msg = (char *)"incorrect data check"; 1189131377Stjr state->mode = BAD; 1190131377Stjr break; 1191131377Stjr } 1192131377Stjr INITBITS(); 1193131377Stjr Tracev((stderr, "inflate: check matches trailer\n")); 1194131377Stjr } 1195131377Stjr#ifdef GUNZIP 1196131377Stjr state->mode = LENGTH; 1197131377Stjr case LENGTH: 1198131377Stjr if (state->wrap && state->flags) { 1199131377Stjr NEEDBITS(32); 1200131377Stjr if (hold != (state->total & 0xffffffffUL)) { 1201131377Stjr strm->msg = (char *)"incorrect length check"; 1202131377Stjr state->mode = BAD; 1203131377Stjr break; 1204131377Stjr } 1205131377Stjr INITBITS(); 1206131377Stjr Tracev((stderr, "inflate: length matches trailer\n")); 1207131377Stjr } 1208131377Stjr#endif 1209131377Stjr state->mode = DONE; 1210131377Stjr case DONE: 1211131377Stjr ret = Z_STREAM_END; 1212131377Stjr goto inf_leave; 1213131377Stjr case BAD: 1214131377Stjr ret = Z_DATA_ERROR; 1215131377Stjr goto inf_leave; 1216131377Stjr case MEM: 1217131377Stjr return Z_MEM_ERROR; 1218131377Stjr case SYNC: 1219131377Stjr default: 1220131377Stjr return Z_STREAM_ERROR; 1221131377Stjr } 1222131377Stjr 1223131377Stjr /* 1224131377Stjr Return from inflate(), updating the total counts and the check value. 1225131377Stjr If there was no progress during the inflate() call, return a buffer 1226131377Stjr error. Call updatewindow() to create and/or update the window state. 1227131377Stjr Note: a memory error from inflate() is non-recoverable. 1228131377Stjr */ 1229131377Stjr inf_leave: 1230131377Stjr RESTORE(); 1231230837Sdelphij if (state->wsize || (out != strm->avail_out && state->mode < BAD && 1232230837Sdelphij (state->mode < CHECK || flush != Z_FINISH))) 1233131377Stjr if (updatewindow(strm, out)) { 1234131377Stjr state->mode = MEM; 1235131377Stjr return Z_MEM_ERROR; 1236131377Stjr } 1237131377Stjr in -= strm->avail_in; 1238131377Stjr out -= strm->avail_out; 1239131377Stjr strm->total_in += in; 1240131377Stjr strm->total_out += out; 1241131377Stjr state->total += out; 1242131377Stjr if (state->wrap && out) 1243131377Stjr strm->adler = state->check = 1244131377Stjr UPDATE(state->check, strm->next_out - out, out); 1245131377Stjr strm->data_type = state->bits + (state->last ? 64 : 0) + 1246205194Sdelphij (state->mode == TYPE ? 128 : 0) + 1247205194Sdelphij (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0); 1248131377Stjr if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1249131377Stjr ret = Z_BUF_ERROR; 1250131377Stjr return ret; 125117651Speter} 125217651Speter 1253131377Stjrint ZEXPORT inflateEnd(strm) 1254131377Stjrz_streamp strm; 1255131377Stjr{ 1256131377Stjr struct inflate_state FAR *state; 1257131377Stjr if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1258131377Stjr return Z_STREAM_ERROR; 1259131377Stjr state = (struct inflate_state FAR *)strm->state; 1260131377Stjr if (state->window != Z_NULL) ZFREE(strm, state->window); 1261131377Stjr ZFREE(strm, strm->state); 1262131377Stjr strm->state = Z_NULL; 1263131377Stjr Tracev((stderr, "inflate: end\n")); 1264131377Stjr return Z_OK; 1265131377Stjr} 126617651Speter 1267131377Stjrint ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1268131377Stjrz_streamp strm; 126917651Speterconst Bytef *dictionary; 1270131377StjruInt dictLength; 127117651Speter{ 1272131377Stjr struct inflate_state FAR *state; 1273237248Sdelphij unsigned long dictid; 1274230837Sdelphij unsigned char *next; 1275230837Sdelphij unsigned avail; 1276230837Sdelphij int ret; 127717651Speter 1278131377Stjr /* check state */ 1279131377Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1280131377Stjr state = (struct inflate_state FAR *)strm->state; 1281157043Sdes if (state->wrap != 0 && state->mode != DICT) 1282157043Sdes return Z_STREAM_ERROR; 128317651Speter 1284237248Sdelphij /* check for correct dictionary identifier */ 1285157043Sdes if (state->mode == DICT) { 1286237248Sdelphij dictid = adler32(0L, Z_NULL, 0); 1287237248Sdelphij dictid = adler32(dictid, dictionary, dictLength); 1288237248Sdelphij if (dictid != state->check) 1289157043Sdes return Z_DATA_ERROR; 1290157043Sdes } 129117651Speter 1292230837Sdelphij /* copy dictionary to window using updatewindow(), which will amend the 1293230837Sdelphij existing dictionary if appropriate */ 1294230837Sdelphij next = strm->next_out; 1295230837Sdelphij avail = strm->avail_out; 1296230837Sdelphij strm->next_out = (Bytef *)dictionary + dictLength; 1297230837Sdelphij strm->avail_out = 0; 1298230837Sdelphij ret = updatewindow(strm, dictLength); 1299230837Sdelphij strm->avail_out = avail; 1300230837Sdelphij strm->next_out = next; 1301230837Sdelphij if (ret) { 1302131377Stjr state->mode = MEM; 1303131377Stjr return Z_MEM_ERROR; 1304131377Stjr } 1305131377Stjr state->havedict = 1; 1306131377Stjr Tracev((stderr, "inflate: dictionary set\n")); 1307131377Stjr return Z_OK; 130817651Speter} 130917651Speter 1310157043Sdesint ZEXPORT inflateGetHeader(strm, head) 1311157043Sdesz_streamp strm; 1312157043Sdesgz_headerp head; 1313157043Sdes{ 1314157043Sdes struct inflate_state FAR *state; 1315157043Sdes 1316157043Sdes /* check state */ 1317157043Sdes if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1318157043Sdes state = (struct inflate_state FAR *)strm->state; 1319157043Sdes if ((state->wrap & 2) == 0) return Z_STREAM_ERROR; 1320157043Sdes 1321157043Sdes /* save header structure */ 1322157043Sdes state->head = head; 1323157043Sdes head->done = 0; 1324157043Sdes return Z_OK; 1325157043Sdes} 1326157043Sdes 1327131377Stjr/* 1328131377Stjr Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1329131377Stjr or when out of input. When called, *have is the number of pattern bytes 1330131377Stjr found in order so far, in 0..3. On return *have is updated to the new 1331131377Stjr state. If on return *have equals four, then the pattern was found and the 1332131377Stjr return value is how many bytes were read including the last byte of the 1333131377Stjr pattern. If *have is less than four, then the pattern has not been found 1334131377Stjr yet and the return value is len. In the latter case, syncsearch() can be 1335131377Stjr called again with more data and the *have state. *have is initialized to 1336131377Stjr zero for the first call. 1337131377Stjr */ 1338131377Stjrlocal unsigned syncsearch(have, buf, len) 1339131377Stjrunsigned FAR *have; 1340131377Stjrunsigned char FAR *buf; 1341131377Stjrunsigned len; 1342131377Stjr{ 1343131377Stjr unsigned got; 1344131377Stjr unsigned next; 134517651Speter 1346131377Stjr got = *have; 1347131377Stjr next = 0; 1348131377Stjr while (next < len && got < 4) { 1349131377Stjr if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1350131377Stjr got++; 1351131377Stjr else if (buf[next]) 1352131377Stjr got = 0; 1353131377Stjr else 1354131377Stjr got = 4 - got; 1355131377Stjr next++; 1356131377Stjr } 1357131377Stjr *have = got; 1358131377Stjr return next; 1359131377Stjr} 1360131377Stjr 1361131377Stjrint ZEXPORT inflateSync(strm) 1362131377Stjrz_streamp strm; 136317651Speter{ 1364131377Stjr unsigned len; /* number of bytes to look at or looked at */ 1365131377Stjr unsigned long in, out; /* temporary to save total_in and total_out */ 1366131377Stjr unsigned char buf[4]; /* to restore bit buffer to byte string */ 1367131377Stjr struct inflate_state FAR *state; 136817651Speter 1369131377Stjr /* check parameters */ 1370131377Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1371131377Stjr state = (struct inflate_state FAR *)strm->state; 1372131377Stjr if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 137317651Speter 1374131377Stjr /* if first time, start search in bit buffer */ 1375131377Stjr if (state->mode != SYNC) { 1376131377Stjr state->mode = SYNC; 1377131377Stjr state->hold <<= state->bits & 7; 1378131377Stjr state->bits -= state->bits & 7; 1379131377Stjr len = 0; 1380131377Stjr while (state->bits >= 8) { 1381131377Stjr buf[len++] = (unsigned char)(state->hold); 1382131377Stjr state->hold >>= 8; 1383131377Stjr state->bits -= 8; 1384131377Stjr } 1385131377Stjr state->have = 0; 1386131377Stjr syncsearch(&(state->have), buf, len); 1387131377Stjr } 138817651Speter 1389131377Stjr /* search available input */ 1390131377Stjr len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1391131377Stjr strm->avail_in -= len; 1392131377Stjr strm->next_in += len; 1393131377Stjr strm->total_in += len; 139417651Speter 1395131377Stjr /* return no joy or set up to restart inflate() on a new block */ 1396131377Stjr if (state->have != 4) return Z_DATA_ERROR; 1397131377Stjr in = strm->total_in; out = strm->total_out; 1398131377Stjr inflateReset(strm); 1399131377Stjr strm->total_in = in; strm->total_out = out; 1400131377Stjr state->mode = TYPE; 1401131377Stjr return Z_OK; 140217651Speter} 140333904Ssteve 1404131377Stjr/* 1405131377Stjr Returns true if inflate is currently at the end of a block generated by 1406131377Stjr Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1407131377Stjr implementation to provide an additional safety check. PPP uses 1408131377Stjr Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1409131377Stjr block. When decompressing, PPP checks that at the end of input packet, 1410131377Stjr inflate is waiting for these length bytes. 141133904Ssteve */ 1412131377Stjrint ZEXPORT inflateSyncPoint(strm) 1413131377Stjrz_streamp strm; 141433904Ssteve{ 1415131377Stjr struct inflate_state FAR *state; 1416131377Stjr 1417131377Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1418131377Stjr state = (struct inflate_state FAR *)strm->state; 1419131377Stjr return state->mode == STORED && state->bits == 0; 142033904Ssteve} 1421131377Stjr 1422131377Stjrint ZEXPORT inflateCopy(dest, source) 1423131377Stjrz_streamp dest; 1424131377Stjrz_streamp source; 1425131377Stjr{ 1426131377Stjr struct inflate_state FAR *state; 1427131377Stjr struct inflate_state FAR *copy; 1428131377Stjr unsigned char FAR *window; 1429157043Sdes unsigned wsize; 1430131377Stjr 1431131377Stjr /* check input */ 1432131377Stjr if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1433131377Stjr source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1434131377Stjr return Z_STREAM_ERROR; 1435131377Stjr state = (struct inflate_state FAR *)source->state; 1436131377Stjr 1437131377Stjr /* allocate space */ 1438131377Stjr copy = (struct inflate_state FAR *) 1439131377Stjr ZALLOC(source, 1, sizeof(struct inflate_state)); 1440131377Stjr if (copy == Z_NULL) return Z_MEM_ERROR; 1441131377Stjr window = Z_NULL; 1442131377Stjr if (state->window != Z_NULL) { 1443131377Stjr window = (unsigned char FAR *) 1444131377Stjr ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1445131377Stjr if (window == Z_NULL) { 1446131377Stjr ZFREE(source, copy); 1447131377Stjr return Z_MEM_ERROR; 1448131377Stjr } 1449131377Stjr } 1450131377Stjr 1451131377Stjr /* copy state */ 1452230837Sdelphij zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 1453230837Sdelphij zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state)); 1454157043Sdes if (state->lencode >= state->codes && 1455157043Sdes state->lencode <= state->codes + ENOUGH - 1) { 1456157043Sdes copy->lencode = copy->codes + (state->lencode - state->codes); 1457157043Sdes copy->distcode = copy->codes + (state->distcode - state->codes); 1458157043Sdes } 1459131377Stjr copy->next = copy->codes + (state->next - state->codes); 1460157043Sdes if (window != Z_NULL) { 1461157043Sdes wsize = 1U << state->wbits; 1462157043Sdes zmemcpy(window, state->window, wsize); 1463157043Sdes } 1464131377Stjr copy->window = window; 1465157043Sdes dest->state = (struct internal_state FAR *)copy; 1466131377Stjr return Z_OK; 1467131377Stjr} 1468205194Sdelphij 1469205194Sdelphijint ZEXPORT inflateUndermine(strm, subvert) 1470205194Sdelphijz_streamp strm; 1471205194Sdelphijint subvert; 1472205194Sdelphij{ 1473205194Sdelphij struct inflate_state FAR *state; 1474205194Sdelphij 1475205194Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1476205194Sdelphij state = (struct inflate_state FAR *)strm->state; 1477205194Sdelphij state->sane = !subvert; 1478205194Sdelphij#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 1479205194Sdelphij return Z_OK; 1480205194Sdelphij#else 1481205194Sdelphij state->sane = 1; 1482205194Sdelphij return Z_DATA_ERROR; 1483205194Sdelphij#endif 1484205194Sdelphij} 1485205194Sdelphij 1486205194Sdelphijlong ZEXPORT inflateMark(strm) 1487205194Sdelphijz_streamp strm; 1488205194Sdelphij{ 1489205194Sdelphij struct inflate_state FAR *state; 1490205194Sdelphij 1491205194Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return -1L << 16; 1492205194Sdelphij state = (struct inflate_state FAR *)strm->state; 1493205194Sdelphij return ((long)(state->back) << 16) + 1494205194Sdelphij (state->mode == COPY ? state->length : 1495205194Sdelphij (state->mode == MATCH ? state->was - state->length : 0)); 1496205194Sdelphij} 1497