1168404Spjd/* 2168404Spjd * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 3168404Spjd * Use is subject to license terms. 4168404Spjd */ 5168404Spjd 6168404Spjd/* inflate.c -- zlib decompression 7168404Spjd * Copyright (C) 1995-2005 Mark Adler 8168404Spjd * For conditions of distribution and use, see copyright notice in zlib.h 9168404Spjd */ 10168404Spjd 11168404Spjd#pragma ident "%Z%%M% %I% %E% SMI" 12168404Spjd 13168404Spjd/* 14168404Spjd * Change history: 15168404Spjd * 16168404Spjd * 1.2.beta0 24 Nov 2002 17168404Spjd * - First version -- complete rewrite of inflate to simplify code, avoid 18168404Spjd * creation of window when not needed, minimize use of window when it is 19168404Spjd * needed, make inffast.c even faster, implement gzip decoding, and to 20168404Spjd * improve code readability and style over the previous zlib inflate code 21168404Spjd * 22168404Spjd * 1.2.beta1 25 Nov 2002 23168404Spjd * - Use pointers for available input and output checking in inffast.c 24168404Spjd * - Remove input and output counters in inffast.c 25168404Spjd * - Change inffast.c entry and loop from avail_in >= 7 to >= 6 26168404Spjd * - Remove unnecessary second byte pull from length extra in inffast.c 27168404Spjd * - Unroll direct copy to three copies per loop in inffast.c 28168404Spjd * 29168404Spjd * 1.2.beta2 4 Dec 2002 30168404Spjd * - Change external routine names to reduce potential conflicts 31168404Spjd * - Correct filename to inffixed.h for fixed tables in inflate.c 32168404Spjd * - Make hbuf[] unsigned char to match parameter type in inflate.c 33168404Spjd * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 34168404Spjd * to avoid negation problem on Alphas (64 bit) in inflate.c 35168404Spjd * 36168404Spjd * 1.2.beta3 22 Dec 2002 37168404Spjd * - Add comments on state->bits assertion in inffast.c 38168404Spjd * - Add comments on op field in inftrees.h 39168404Spjd * - Fix bug in reuse of allocated window after inflateReset() 40168404Spjd * - Remove bit fields--back to byte structure for speed 41168404Spjd * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 42168404Spjd * - Change post-increments to pre-increments in inflate_fast(), PPC biased? 43168404Spjd * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 44168404Spjd * - Make MATCH copy in inflate() much faster for when inflate_fast() not used 45168404Spjd * - Use local copies of stream next and avail values, as well as local bit 46168404Spjd * buffer and bit count in inflate()--for speed when inflate_fast() not used 47168404Spjd * 48168404Spjd * 1.2.beta4 1 Jan 2003 49168404Spjd * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings 50168404Spjd * - Move a comment on output buffer sizes from inffast.c to inflate.c 51168404Spjd * - Add comments in inffast.c to introduce the inflate_fast() routine 52168404Spjd * - Rearrange window copies in inflate_fast() for speed and simplification 53168404Spjd * - Unroll last copy for window match in inflate_fast() 54168404Spjd * - Use local copies of window variables in inflate_fast() for speed 55168404Spjd * - Pull out common write == 0 case for speed in inflate_fast() 56168404Spjd * - Make op and len in inflate_fast() unsigned for consistency 57168404Spjd * - Add FAR to lcode and dcode declarations in inflate_fast() 58168404Spjd * - Simplified bad distance check in inflate_fast() 59168404Spjd * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 60168404Spjd * source file infback.c to provide a call-back interface to inflate for 61168404Spjd * programs like gzip and unzip -- uses window as output buffer to avoid 62168404Spjd * window copying 63168404Spjd * 64168404Spjd * 1.2.beta5 1 Jan 2003 65168404Spjd * - Improved inflateBack() interface to allow the caller to provide initial 66168404Spjd * input in strm. 67168404Spjd * - Fixed stored blocks bug in inflateBack() 68168404Spjd * 69168404Spjd * 1.2.beta6 4 Jan 2003 70168404Spjd * - Added comments in inffast.c on effectiveness of POSTINC 71168404Spjd * - Typecasting all around to reduce compiler warnings 72168404Spjd * - Changed loops from while (1) or do {} while (1) to for (;;), again to 73168404Spjd * make compilers happy 74168404Spjd * - Changed type of window in inflateBackInit() to unsigned char * 75168404Spjd * 76168404Spjd * 1.2.beta7 27 Jan 2003 77168404Spjd * - Changed many types to unsigned or unsigned short to avoid warnings 78168404Spjd * - Added inflateCopy() function 79168404Spjd * 80168404Spjd * 1.2.0 9 Mar 2003 81168404Spjd * - Changed inflateBack() interface to provide separate opaque descriptors 82168404Spjd * for the in() and out() functions 83168404Spjd * - Changed inflateBack() argument and in_func typedef to swap the length 84168404Spjd * and buffer address return values for the input function 85168404Spjd * - Check next_in and next_out for Z_NULL on entry to inflate() 86168404Spjd * 87168404Spjd * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 88168404Spjd */ 89168404Spjd 90168404Spjd#include "zutil.h" 91168404Spjd#include "inftrees.h" 92168404Spjd#include "inflate.h" 93168404Spjd#include "inffast.h" 94168404Spjd 95168404Spjd#ifdef MAKEFIXED 96168404Spjd# ifndef BUILDFIXED 97168404Spjd# define BUILDFIXED 98168404Spjd# endif 99168404Spjd#endif 100168404Spjd 101168404Spjd/* function prototypes */ 102168404Spjdlocal void fixedtables OF((struct inflate_state FAR *state)); 103168404Spjdlocal int updatewindow OF((z_streamp strm, unsigned out)); 104168404Spjd#ifdef BUILDFIXED 105168404Spjd void makefixed OF((void)); 106168404Spjd#endif 107168404Spjdlocal unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf, 108168404Spjd unsigned len)); 109168404Spjd 110168404Spjdint ZEXPORT inflateReset(strm) 111168404Spjdz_streamp strm; 112168404Spjd{ 113168404Spjd struct inflate_state FAR *state; 114168404Spjd 115168404Spjd if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 116168404Spjd state = (struct inflate_state FAR *)strm->state; 117168404Spjd strm->total_in = strm->total_out = state->total = 0; 118168404Spjd strm->msg = Z_NULL; 119168404Spjd strm->adler = 1; /* to support ill-conceived Java test suite */ 120168404Spjd state->mode = HEAD; 121168404Spjd state->last = 0; 122168404Spjd state->havedict = 0; 123168404Spjd state->dmax = 32768U; 124168404Spjd state->head = Z_NULL; 125168404Spjd state->wsize = 0; 126168404Spjd state->whave = 0; 127168404Spjd state->write = 0; 128168404Spjd state->hold = 0; 129168404Spjd state->bits = 0; 130168404Spjd state->lencode = state->distcode = state->next = state->codes; 131168404Spjd Tracev((stderr, "inflate: reset\n")); 132168404Spjd return Z_OK; 133168404Spjd} 134168404Spjd 135168404Spjdint ZEXPORT inflatePrime(strm, bits, value) 136168404Spjdz_streamp strm; 137168404Spjdint bits; 138168404Spjdint value; 139168404Spjd{ 140168404Spjd struct inflate_state FAR *state; 141168404Spjd 142168404Spjd if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 143168404Spjd state = (struct inflate_state FAR *)strm->state; 144168404Spjd if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR; 145168404Spjd value &= (1L << bits) - 1; 146168404Spjd state->hold += value << state->bits; 147168404Spjd state->bits += bits; 148168404Spjd return Z_OK; 149168404Spjd} 150168404Spjd 151168404Spjdint ZEXPORT inflateInit2_(strm, windowBits, version, stream_size) 152168404Spjdz_streamp strm; 153168404Spjdint windowBits; 154168404Spjdconst char *version; 155168404Spjdint stream_size; 156168404Spjd{ 157168404Spjd struct inflate_state FAR *state; 158168404Spjd 159168404Spjd if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 160168404Spjd stream_size != (int)(sizeof(z_stream))) 161168404Spjd return Z_VERSION_ERROR; 162168404Spjd if (strm == Z_NULL) return Z_STREAM_ERROR; 163168404Spjd strm->msg = Z_NULL; /* in case we return an error */ 164168404Spjd if (strm->zalloc == (alloc_func)0) { 165168404Spjd strm->zalloc = zcalloc; 166168404Spjd strm->opaque = (voidpf)0; 167168404Spjd } 168168404Spjd if (strm->zfree == (free_func)0) strm->zfree = zcfree; 169168404Spjd state = (struct inflate_state FAR *) 170168404Spjd ZALLOC(strm, 1, sizeof(struct inflate_state)); 171168404Spjd if (state == Z_NULL) return Z_MEM_ERROR; 172168404Spjd Tracev((stderr, "inflate: allocated\n")); 173168404Spjd strm->state = (struct internal_state FAR *)state; 174168404Spjd if (windowBits < 0) { 175168404Spjd state->wrap = 0; 176168404Spjd windowBits = -windowBits; 177168404Spjd } 178168404Spjd else { 179168404Spjd state->wrap = (windowBits >> 4) + 1; 180168404Spjd#ifdef GUNZIP 181168404Spjd if (windowBits < 48) windowBits &= 15; 182168404Spjd#endif 183168404Spjd } 184168404Spjd if (windowBits < 8 || windowBits > 15) { 185168404Spjd ZFREE(strm, state); 186168404Spjd strm->state = Z_NULL; 187168404Spjd return Z_STREAM_ERROR; 188168404Spjd } 189168404Spjd state->wbits = (unsigned)windowBits; 190168404Spjd state->window = Z_NULL; 191168404Spjd return inflateReset(strm); 192168404Spjd} 193168404Spjd 194168404Spjdint ZEXPORT inflateInit_(strm, version, stream_size) 195168404Spjdz_streamp strm; 196168404Spjdconst char *version; 197168404Spjdint stream_size; 198168404Spjd{ 199168404Spjd return inflateInit2_(strm, DEF_WBITS, version, stream_size); 200168404Spjd} 201168404Spjd 202168404Spjd/* 203168404Spjd Return state with length and distance decoding tables and index sizes set to 204168404Spjd fixed code decoding. Normally this returns fixed tables from inffixed.h. 205168404Spjd If BUILDFIXED is defined, then instead this routine builds the tables the 206168404Spjd first time it's called, and returns those tables the first time and 207168404Spjd thereafter. This reduces the size of the code by about 2K bytes, in 208168404Spjd exchange for a little execution time. However, BUILDFIXED should not be 209168404Spjd used for threaded applications, since the rewriting of the tables and virgin 210168404Spjd may not be thread-safe. 211168404Spjd */ 212168404Spjdlocal void fixedtables(state) 213168404Spjdstruct inflate_state FAR *state; 214168404Spjd{ 215168404Spjd#ifdef BUILDFIXED 216168404Spjd static int virgin = 1; 217168404Spjd static code *lenfix, *distfix; 218168404Spjd static code fixed[544]; 219168404Spjd 220168404Spjd /* build fixed huffman tables if first call (may not be thread safe) */ 221168404Spjd if (virgin) { 222168404Spjd unsigned sym, bits; 223168404Spjd static code *next; 224168404Spjd 225168404Spjd /* literal/length table */ 226168404Spjd sym = 0; 227168404Spjd while (sym < 144) state->lens[sym++] = 8; 228168404Spjd while (sym < 256) state->lens[sym++] = 9; 229168404Spjd while (sym < 280) state->lens[sym++] = 7; 230168404Spjd while (sym < 288) state->lens[sym++] = 8; 231168404Spjd next = fixed; 232168404Spjd lenfix = next; 233168404Spjd bits = 9; 234168404Spjd inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); 235168404Spjd 236168404Spjd /* distance table */ 237168404Spjd sym = 0; 238168404Spjd while (sym < 32) state->lens[sym++] = 5; 239168404Spjd distfix = next; 240168404Spjd bits = 5; 241168404Spjd inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); 242168404Spjd 243168404Spjd /* do this just once */ 244168404Spjd virgin = 0; 245168404Spjd } 246168404Spjd#else /* !BUILDFIXED */ 247168404Spjd# include "inffixed.h" 248168404Spjd#endif /* BUILDFIXED */ 249168404Spjd state->lencode = lenfix; 250168404Spjd state->lenbits = 9; 251168404Spjd state->distcode = distfix; 252168404Spjd state->distbits = 5; 253168404Spjd} 254168404Spjd 255168404Spjd#ifdef MAKEFIXED 256168404Spjd#include <stdio.h> 257168404Spjd 258168404Spjd/* 259168404Spjd Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also 260168404Spjd defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 261168404Spjd those tables to stdout, which would be piped to inffixed.h. A small program 262168404Spjd can simply call makefixed to do this: 263168404Spjd 264168404Spjd void makefixed(void); 265168404Spjd 266168404Spjd int main(void) 267168404Spjd { 268168404Spjd makefixed(); 269168404Spjd return 0; 270168404Spjd } 271168404Spjd 272168404Spjd Then that can be linked with zlib built with MAKEFIXED defined and run: 273168404Spjd 274168404Spjd a.out > inffixed.h 275168404Spjd */ 276168404Spjdvoid makefixed() 277168404Spjd{ 278168404Spjd unsigned low, size; 279168404Spjd struct inflate_state state; 280168404Spjd 281168404Spjd fixedtables(&state); 282168404Spjd puts(" /* inffixed.h -- table for decoding fixed codes"); 283168404Spjd puts(" * Generated automatically by makefixed()."); 284168404Spjd puts(" */"); 285168404Spjd puts(""); 286168404Spjd puts(" /* WARNING: this file should *not* be used by applications."); 287168404Spjd puts(" It is part of the implementation of this library and is"); 288168404Spjd puts(" subject to change. Applications should only use zlib.h."); 289168404Spjd puts(" */"); 290168404Spjd puts(""); 291168404Spjd size = 1U << 9; 292168404Spjd printf(" static const code lenfix[%u] = {", size); 293168404Spjd low = 0; 294168404Spjd for (;;) { 295168404Spjd if ((low % 7) == 0) printf("\n "); 296168404Spjd printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits, 297168404Spjd state.lencode[low].val); 298168404Spjd if (++low == size) break; 299168404Spjd putchar(','); 300168404Spjd } 301168404Spjd puts("\n };"); 302168404Spjd size = 1U << 5; 303168404Spjd printf("\n static const code distfix[%u] = {", size); 304168404Spjd low = 0; 305168404Spjd for (;;) { 306168404Spjd if ((low % 6) == 0) printf("\n "); 307168404Spjd printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits, 308168404Spjd state.distcode[low].val); 309168404Spjd if (++low == size) break; 310168404Spjd putchar(','); 311168404Spjd } 312168404Spjd puts("\n };"); 313168404Spjd} 314168404Spjd#endif /* MAKEFIXED */ 315168404Spjd 316168404Spjd/* 317168404Spjd Update the window with the last wsize (normally 32K) bytes written before 318168404Spjd returning. If window does not exist yet, create it. This is only called 319168404Spjd when a window is already in use, or when output has been written during this 320168404Spjd inflate call, but the end of the deflate stream has not been reached yet. 321168404Spjd It is also called to create a window for dictionary data when a dictionary 322168404Spjd is loaded. 323168404Spjd 324168404Spjd Providing output buffers larger than 32K to inflate() should provide a speed 325168404Spjd advantage, since only the last 32K of output is copied to the sliding window 326168404Spjd upon return from inflate(), and since all distances after the first 32K of 327168404Spjd output will fall in the output data, making match copies simpler and faster. 328168404Spjd The advantage may be dependent on the size of the processor's data caches. 329168404Spjd */ 330168404Spjdlocal int updatewindow(strm, out) 331168404Spjdz_streamp strm; 332168404Spjdunsigned out; 333168404Spjd{ 334168404Spjd struct inflate_state FAR *state; 335168404Spjd unsigned copy, dist; 336168404Spjd 337168404Spjd state = (struct inflate_state FAR *)strm->state; 338168404Spjd 339168404Spjd /* if it hasn't been done already, allocate space for the window */ 340168404Spjd if (state->window == Z_NULL) { 341168404Spjd state->window = (unsigned char FAR *) 342168404Spjd ZALLOC(strm, 1U << state->wbits, 343168404Spjd sizeof(unsigned char)); 344168404Spjd if (state->window == Z_NULL) return 1; 345168404Spjd } 346168404Spjd 347168404Spjd /* if window not in use yet, initialize */ 348168404Spjd if (state->wsize == 0) { 349168404Spjd state->wsize = 1U << state->wbits; 350168404Spjd state->write = 0; 351168404Spjd state->whave = 0; 352168404Spjd } 353168404Spjd 354168404Spjd /* copy state->wsize or less output bytes into the circular window */ 355168404Spjd copy = out - strm->avail_out; 356168404Spjd if (copy >= state->wsize) { 357168404Spjd zmemcpy(state->window, strm->next_out - state->wsize, state->wsize); 358168404Spjd state->write = 0; 359168404Spjd state->whave = state->wsize; 360168404Spjd } 361168404Spjd else { 362168404Spjd dist = state->wsize - state->write; 363168404Spjd if (dist > copy) dist = copy; 364168404Spjd zmemcpy(state->window + state->write, strm->next_out - copy, dist); 365168404Spjd copy -= dist; 366168404Spjd if (copy) { 367168404Spjd zmemcpy(state->window, strm->next_out - copy, copy); 368168404Spjd state->write = copy; 369168404Spjd state->whave = state->wsize; 370168404Spjd } 371168404Spjd else { 372168404Spjd state->write += dist; 373168404Spjd if (state->write == state->wsize) state->write = 0; 374168404Spjd if (state->whave < state->wsize) state->whave += dist; 375168404Spjd } 376168404Spjd } 377168404Spjd return 0; 378168404Spjd} 379168404Spjd 380168404Spjd/* Macros for inflate(): */ 381168404Spjd 382168404Spjd/* check function to use adler32() for zlib or crc32() for gzip */ 383168404Spjd#ifdef GUNZIP 384168404Spjd# define UPDATE(check, buf, len) \ 385168404Spjd (state->flags ? crc32(check, buf, len) : adler32(check, buf, len)) 386168404Spjd#else 387168404Spjd# define UPDATE(check, buf, len) adler32(check, buf, len) 388168404Spjd#endif 389168404Spjd 390168404Spjd/* check macros for header crc */ 391168404Spjd#ifdef GUNZIP 392168404Spjd# define CRC2(check, word) \ 393168404Spjd do { \ 394168404Spjd hbuf[0] = (unsigned char)(word); \ 395168404Spjd hbuf[1] = (unsigned char)((word) >> 8); \ 396168404Spjd check = crc32(check, hbuf, 2); \ 397168404Spjd } while (0) 398168404Spjd 399168404Spjd# define CRC4(check, word) \ 400168404Spjd do { \ 401168404Spjd hbuf[0] = (unsigned char)(word); \ 402168404Spjd hbuf[1] = (unsigned char)((word) >> 8); \ 403168404Spjd hbuf[2] = (unsigned char)((word) >> 16); \ 404168404Spjd hbuf[3] = (unsigned char)((word) >> 24); \ 405168404Spjd check = crc32(check, hbuf, 4); \ 406168404Spjd } while (0) 407168404Spjd#endif 408168404Spjd 409168404Spjd/* Load registers with state in inflate() for speed */ 410168404Spjd#define LOAD() \ 411168404Spjd do { \ 412168404Spjd put = strm->next_out; \ 413168404Spjd left = strm->avail_out; \ 414168404Spjd next = strm->next_in; \ 415168404Spjd have = strm->avail_in; \ 416168404Spjd hold = state->hold; \ 417168404Spjd bits = state->bits; \ 418168404Spjd } while (0) 419168404Spjd 420168404Spjd/* Restore state from registers in inflate() */ 421168404Spjd#define RESTORE() \ 422168404Spjd do { \ 423168404Spjd strm->next_out = put; \ 424168404Spjd strm->avail_out = left; \ 425168404Spjd strm->next_in = next; \ 426168404Spjd strm->avail_in = have; \ 427168404Spjd state->hold = hold; \ 428168404Spjd state->bits = bits; \ 429168404Spjd } while (0) 430168404Spjd 431168404Spjd/* Clear the input bit accumulator */ 432168404Spjd#define INITBITS() \ 433168404Spjd do { \ 434168404Spjd hold = 0; \ 435168404Spjd bits = 0; \ 436168404Spjd } while (0) 437168404Spjd 438168404Spjd/* Get a byte of input into the bit accumulator, or return from inflate() 439168404Spjd if there is no input available. */ 440168404Spjd#define PULLBYTE() \ 441168404Spjd do { \ 442168404Spjd if (have == 0) goto inf_leave; \ 443168404Spjd have--; \ 444168404Spjd hold += (unsigned long)(*next++) << bits; \ 445168404Spjd bits += 8; \ 446168404Spjd } while (0) 447168404Spjd 448168404Spjd/* Assure that there are at least n bits in the bit accumulator. If there is 449168404Spjd not enough available input to do that, then return from inflate(). */ 450168404Spjd#define NEEDBITS(n) \ 451168404Spjd do { \ 452168404Spjd while (bits < (unsigned)(n)) \ 453168404Spjd PULLBYTE(); \ 454168404Spjd } while (0) 455168404Spjd 456168404Spjd/* Return the low n bits of the bit accumulator (n < 16) */ 457168404Spjd#define BITS(n) \ 458168404Spjd ((unsigned)hold & ((1U << (n)) - 1)) 459168404Spjd 460168404Spjd/* Remove n bits from the bit accumulator */ 461168404Spjd#define DROPBITS(n) \ 462168404Spjd do { \ 463168404Spjd hold >>= (n); \ 464168404Spjd bits -= (unsigned)(n); \ 465168404Spjd } while (0) 466168404Spjd 467168404Spjd/* Remove zero to seven bits as needed to go to a byte boundary */ 468168404Spjd#define BYTEBITS() \ 469168404Spjd do { \ 470168404Spjd hold >>= bits & 7; \ 471168404Spjd bits -= bits & 7; \ 472168404Spjd } while (0) 473168404Spjd 474168404Spjd/* Reverse the bytes in a 32-bit value */ 475168404Spjd#define REVERSE(q) \ 476168404Spjd ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \ 477168404Spjd (((q) & 0xff00) << 8) + (((q) & 0xff) << 24)) 478168404Spjd 479168404Spjd/* 480168404Spjd inflate() uses a state machine to process as much input data and generate as 481168404Spjd much output data as possible before returning. The state machine is 482168404Spjd structured roughly as follows: 483168404Spjd 484168404Spjd for (;;) switch (state) { 485168404Spjd ... 486168404Spjd case STATEn: 487168404Spjd if (not enough input data or output space to make progress) 488168404Spjd return; 489168404Spjd ... make progress ... 490168404Spjd state = STATEm; 491168404Spjd break; 492168404Spjd ... 493168404Spjd } 494168404Spjd 495168404Spjd so when inflate() is called again, the same case is attempted again, and 496168404Spjd if the appropriate resources are provided, the machine proceeds to the 497168404Spjd next state. The NEEDBITS() macro is usually the way the state evaluates 498168404Spjd whether it can proceed or should return. NEEDBITS() does the return if 499168404Spjd the requested bits are not available. The typical use of the BITS macros 500168404Spjd is: 501168404Spjd 502168404Spjd NEEDBITS(n); 503168404Spjd ... do something with BITS(n) ... 504168404Spjd DROPBITS(n); 505168404Spjd 506168404Spjd where NEEDBITS(n) either returns from inflate() if there isn't enough 507168404Spjd input left to load n bits into the accumulator, or it continues. BITS(n) 508168404Spjd gives the low n bits in the accumulator. When done, DROPBITS(n) drops 509168404Spjd the low n bits off the accumulator. INITBITS() clears the accumulator 510168404Spjd and sets the number of available bits to zero. BYTEBITS() discards just 511168404Spjd enough bits to put the accumulator on a byte boundary. After BYTEBITS() 512168404Spjd and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 513168404Spjd 514168404Spjd NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 515168404Spjd if there is no input available. The decoding of variable length codes uses 516168404Spjd PULLBYTE() directly in order to pull just enough bytes to decode the next 517168404Spjd code, and no more. 518168404Spjd 519168404Spjd Some states loop until they get enough input, making sure that enough 520168404Spjd state information is maintained to continue the loop where it left off 521168404Spjd if NEEDBITS() returns in the loop. For example, want, need, and keep 522168404Spjd would all have to actually be part of the saved state in case NEEDBITS() 523168404Spjd returns: 524168404Spjd 525168404Spjd case STATEw: 526168404Spjd while (want < need) { 527168404Spjd NEEDBITS(n); 528168404Spjd keep[want++] = BITS(n); 529168404Spjd DROPBITS(n); 530168404Spjd } 531168404Spjd state = STATEx; 532168404Spjd case STATEx: 533168404Spjd 534168404Spjd As shown above, if the next state is also the next case, then the break 535168404Spjd is omitted. 536168404Spjd 537168404Spjd A state may also return if there is not enough output space available to 538168404Spjd complete that state. Those states are copying stored data, writing a 539168404Spjd literal byte, and copying a matching string. 540168404Spjd 541168404Spjd When returning, a "goto inf_leave" is used to update the total counters, 542168404Spjd update the check value, and determine whether any progress has been made 543168404Spjd during that inflate() call in order to return the proper return code. 544168404Spjd Progress is defined as a change in either strm->avail_in or strm->avail_out. 545168404Spjd When there is a window, goto inf_leave will update the window with the last 546168404Spjd output written. If a goto inf_leave occurs in the middle of decompression 547168404Spjd and there is no window currently, goto inf_leave will create one and copy 548168404Spjd output to the window for the next call of inflate(). 549168404Spjd 550168404Spjd In this implementation, the flush parameter of inflate() only affects the 551168404Spjd return code (per zlib.h). inflate() always writes as much as possible to 552168404Spjd strm->next_out, given the space available and the provided input--the effect 553168404Spjd documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 554168404Spjd the allocation of and copying into a sliding window until necessary, which 555168404Spjd provides the effect documented in zlib.h for Z_FINISH when the entire input 556168404Spjd stream available. So the only thing the flush parameter actually does is: 557168404Spjd when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 558168404Spjd will return Z_BUF_ERROR if it has not reached the end of the stream. 559168404Spjd */ 560168404Spjd 561168404Spjdint ZEXPORT inflate(strm, flush) 562168404Spjdz_streamp strm; 563168404Spjdint flush; 564168404Spjd{ 565168404Spjd struct inflate_state FAR *state; 566168404Spjd unsigned char FAR *next; /* next input */ 567168404Spjd unsigned char FAR *put; /* next output */ 568168404Spjd unsigned have, left; /* available input and output */ 569168404Spjd unsigned long hold; /* bit buffer */ 570168404Spjd unsigned bits; /* bits in bit buffer */ 571168404Spjd unsigned in, out; /* save starting available input and output */ 572168404Spjd unsigned copy; /* number of stored or match bytes to copy */ 573168404Spjd unsigned char FAR *from; /* where to copy match bytes from */ 574168404Spjd code this; /* current decoding table entry */ 575168404Spjd code last; /* parent table entry */ 576168404Spjd unsigned len; /* length to copy for repeats, bits to drop */ 577168404Spjd int ret; /* return code */ 578168404Spjd#ifdef GUNZIP 579168404Spjd unsigned char hbuf[4]; /* buffer for gzip header crc calculation */ 580168404Spjd#endif 581168404Spjd static const unsigned short order[19] = /* permutation of code lengths */ 582168404Spjd {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 583168404Spjd 584168404Spjd if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 585168404Spjd (strm->next_in == Z_NULL && strm->avail_in != 0)) 586168404Spjd return Z_STREAM_ERROR; 587168404Spjd 588168404Spjd state = (struct inflate_state FAR *)strm->state; 589168404Spjd if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 590168404Spjd LOAD(); 591168404Spjd in = have; 592168404Spjd out = left; 593168404Spjd ret = Z_OK; 594168404Spjd for (;;) 595168404Spjd switch (state->mode) { 596168404Spjd case HEAD: 597168404Spjd if (state->wrap == 0) { 598168404Spjd state->mode = TYPEDO; 599168404Spjd break; 600168404Spjd } 601168404Spjd NEEDBITS(16); 602168404Spjd#ifdef GUNZIP 603168404Spjd if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */ 604168404Spjd state->check = crc32(0L, Z_NULL, 0); 605168404Spjd CRC2(state->check, hold); 606168404Spjd INITBITS(); 607168404Spjd state->mode = FLAGS; 608168404Spjd break; 609168404Spjd } 610168404Spjd state->flags = 0; /* expect zlib header */ 611168404Spjd if (state->head != Z_NULL) 612168404Spjd state->head->done = -1; 613168404Spjd if (!(state->wrap & 1) || /* check if zlib header allowed */ 614168404Spjd#else 615168404Spjd if ( 616168404Spjd#endif 617168404Spjd ((BITS(8) << 8) + (hold >> 8)) % 31) { 618168404Spjd strm->msg = (char *)"incorrect header check"; 619168404Spjd state->mode = BAD; 620168404Spjd break; 621168404Spjd } 622168404Spjd if (BITS(4) != Z_DEFLATED) { 623168404Spjd strm->msg = (char *)"unknown compression method"; 624168404Spjd state->mode = BAD; 625168404Spjd break; 626168404Spjd } 627168404Spjd DROPBITS(4); 628168404Spjd len = BITS(4) + 8; 629168404Spjd if (len > state->wbits) { 630168404Spjd strm->msg = (char *)"invalid window size"; 631168404Spjd state->mode = BAD; 632168404Spjd break; 633168404Spjd } 634168404Spjd state->dmax = 1U << len; 635168404Spjd Tracev((stderr, "inflate: zlib header ok\n")); 636168404Spjd strm->adler = state->check = adler32(0L, Z_NULL, 0); 637168404Spjd state->mode = hold & 0x200 ? DICTID : TYPE; 638168404Spjd INITBITS(); 639168404Spjd break; 640168404Spjd#ifdef GUNZIP 641168404Spjd case FLAGS: 642168404Spjd NEEDBITS(16); 643168404Spjd state->flags = (int)(hold); 644168404Spjd if ((state->flags & 0xff) != Z_DEFLATED) { 645168404Spjd strm->msg = (char *)"unknown compression method"; 646168404Spjd state->mode = BAD; 647168404Spjd break; 648168404Spjd } 649168404Spjd if (state->flags & 0xe000) { 650168404Spjd strm->msg = (char *)"unknown header flags set"; 651168404Spjd state->mode = BAD; 652168404Spjd break; 653168404Spjd } 654168404Spjd if (state->head != Z_NULL) 655168404Spjd state->head->text = (int)((hold >> 8) & 1); 656168404Spjd if (state->flags & 0x0200) CRC2(state->check, hold); 657168404Spjd INITBITS(); 658168404Spjd state->mode = TIME; 659168404Spjd /*FALLTHRU*/ 660168404Spjd case TIME: 661168404Spjd NEEDBITS(32); 662168404Spjd if (state->head != Z_NULL) 663168404Spjd state->head->time = hold; 664168404Spjd if (state->flags & 0x0200) CRC4(state->check, hold); 665168404Spjd INITBITS(); 666168404Spjd state->mode = OS; 667168404Spjd /*FALLTHRU*/ 668168404Spjd case OS: 669168404Spjd NEEDBITS(16); 670168404Spjd if (state->head != Z_NULL) { 671168404Spjd state->head->xflags = (int)(hold & 0xff); 672168404Spjd state->head->os = (int)(hold >> 8); 673168404Spjd } 674168404Spjd if (state->flags & 0x0200) CRC2(state->check, hold); 675168404Spjd INITBITS(); 676168404Spjd state->mode = EXLEN; 677168404Spjd /*FALLTHRU*/ 678168404Spjd case EXLEN: 679168404Spjd if (state->flags & 0x0400) { 680168404Spjd NEEDBITS(16); 681168404Spjd state->length = (unsigned)(hold); 682168404Spjd if (state->head != Z_NULL) 683168404Spjd state->head->extra_len = (unsigned)hold; 684168404Spjd if (state->flags & 0x0200) CRC2(state->check, hold); 685168404Spjd INITBITS(); 686168404Spjd } 687168404Spjd else if (state->head != Z_NULL) 688168404Spjd state->head->extra = Z_NULL; 689168404Spjd state->mode = EXTRA; 690168404Spjd /*FALLTHRU*/ 691168404Spjd case EXTRA: 692168404Spjd if (state->flags & 0x0400) { 693168404Spjd copy = state->length; 694168404Spjd if (copy > have) copy = have; 695168404Spjd if (copy) { 696168404Spjd if (state->head != Z_NULL && 697168404Spjd state->head->extra != Z_NULL) { 698168404Spjd len = state->head->extra_len - state->length; 699168404Spjd zmemcpy(state->head->extra + len, next, 700168404Spjd len + copy > state->head->extra_max ? 701168404Spjd state->head->extra_max - len : copy); 702168404Spjd } 703168404Spjd if (state->flags & 0x0200) 704168404Spjd state->check = crc32(state->check, next, copy); 705168404Spjd have -= copy; 706168404Spjd next += copy; 707168404Spjd state->length -= copy; 708168404Spjd } 709168404Spjd if (state->length) goto inf_leave; 710168404Spjd } 711168404Spjd state->length = 0; 712168404Spjd state->mode = NAME; 713168404Spjd /*FALLTHRU*/ 714168404Spjd case NAME: 715168404Spjd if (state->flags & 0x0800) { 716168404Spjd if (have == 0) goto inf_leave; 717168404Spjd copy = 0; 718168404Spjd do { 719168404Spjd len = (unsigned)(next[copy++]); 720168404Spjd if (state->head != Z_NULL && 721168404Spjd state->head->name != Z_NULL && 722168404Spjd state->length < state->head->name_max) 723168404Spjd state->head->name[state->length++] = len; 724168404Spjd } while (len && copy < have); 725168404Spjd if (state->flags & 0x0200) 726168404Spjd state->check = crc32(state->check, next, copy); 727168404Spjd have -= copy; 728168404Spjd next += copy; 729168404Spjd if (len) goto inf_leave; 730168404Spjd } 731168404Spjd else if (state->head != Z_NULL) 732168404Spjd state->head->name = Z_NULL; 733168404Spjd state->length = 0; 734168404Spjd state->mode = COMMENT; 735168404Spjd /*FALLTHRU*/ 736168404Spjd case COMMENT: 737168404Spjd if (state->flags & 0x1000) { 738168404Spjd if (have == 0) goto inf_leave; 739168404Spjd copy = 0; 740168404Spjd do { 741168404Spjd len = (unsigned)(next[copy++]); 742168404Spjd if (state->head != Z_NULL && 743168404Spjd state->head->comment != Z_NULL && 744168404Spjd state->length < state->head->comm_max) 745168404Spjd state->head->comment[state->length++] = len; 746168404Spjd } while (len && copy < have); 747168404Spjd if (state->flags & 0x0200) 748168404Spjd state->check = crc32(state->check, next, copy); 749168404Spjd have -= copy; 750168404Spjd next += copy; 751168404Spjd if (len) goto inf_leave; 752168404Spjd } 753168404Spjd else if (state->head != Z_NULL) 754168404Spjd state->head->comment = Z_NULL; 755168404Spjd state->mode = HCRC; 756168404Spjd /*FALLTHRU*/ 757168404Spjd case HCRC: 758168404Spjd if (state->flags & 0x0200) { 759168404Spjd NEEDBITS(16); 760168404Spjd if (hold != (state->check & 0xffff)) { 761168404Spjd strm->msg = (char *)"header crc mismatch"; 762168404Spjd state->mode = BAD; 763168404Spjd break; 764168404Spjd } 765168404Spjd INITBITS(); 766168404Spjd } 767168404Spjd if (state->head != Z_NULL) { 768168404Spjd state->head->hcrc = (int)((state->flags >> 9) & 1); 769168404Spjd state->head->done = 1; 770168404Spjd } 771168404Spjd strm->adler = state->check = crc32(0L, Z_NULL, 0); 772168404Spjd state->mode = TYPE; 773168404Spjd break; 774168404Spjd#endif 775168404Spjd case DICTID: 776168404Spjd NEEDBITS(32); 777168404Spjd strm->adler = state->check = REVERSE(hold); 778168404Spjd INITBITS(); 779168404Spjd state->mode = DICT; 780168404Spjd /*FALLTHRU*/ 781168404Spjd case DICT: 782168404Spjd if (state->havedict == 0) { 783168404Spjd RESTORE(); 784168404Spjd return Z_NEED_DICT; 785168404Spjd } 786168404Spjd strm->adler = state->check = adler32(0L, Z_NULL, 0); 787168404Spjd state->mode = TYPE; 788168404Spjd /*FALLTHRU*/ 789168404Spjd case TYPE: 790168404Spjd if (flush == Z_BLOCK) goto inf_leave; 791168404Spjd /*FALLTHRU*/ 792168404Spjd case TYPEDO: 793168404Spjd if (state->last) { 794168404Spjd BYTEBITS(); 795168404Spjd state->mode = CHECK; 796168404Spjd break; 797168404Spjd } 798168404Spjd NEEDBITS(3); 799168404Spjd state->last = BITS(1); 800168404Spjd DROPBITS(1); 801168404Spjd switch (BITS(2)) { 802168404Spjd case 0: /* stored block */ 803168404Spjd Tracev((stderr, "inflate: stored block%s\n", 804168404Spjd state->last ? " (last)" : "")); 805168404Spjd state->mode = STORED; 806168404Spjd break; 807168404Spjd case 1: /* fixed block */ 808168404Spjd fixedtables(state); 809168404Spjd Tracev((stderr, "inflate: fixed codes block%s\n", 810168404Spjd state->last ? " (last)" : "")); 811168404Spjd state->mode = LEN; /* decode codes */ 812168404Spjd break; 813168404Spjd case 2: /* dynamic block */ 814168404Spjd Tracev((stderr, "inflate: dynamic codes block%s\n", 815168404Spjd state->last ? " (last)" : "")); 816168404Spjd state->mode = TABLE; 817168404Spjd break; 818168404Spjd case 3: 819168404Spjd strm->msg = (char *)"invalid block type"; 820168404Spjd state->mode = BAD; 821168404Spjd } 822168404Spjd DROPBITS(2); 823168404Spjd break; 824168404Spjd case STORED: 825168404Spjd BYTEBITS(); /* go to byte boundary */ 826168404Spjd NEEDBITS(32); 827168404Spjd if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 828168404Spjd strm->msg = (char *)"invalid stored block lengths"; 829168404Spjd state->mode = BAD; 830168404Spjd break; 831168404Spjd } 832168404Spjd state->length = (unsigned)hold & 0xffff; 833168404Spjd Tracev((stderr, "inflate: stored length %u\n", 834168404Spjd state->length)); 835168404Spjd INITBITS(); 836168404Spjd state->mode = COPY; 837168404Spjd /*FALLTHRU*/ 838168404Spjd case COPY: 839168404Spjd copy = state->length; 840168404Spjd if (copy) { 841168404Spjd if (copy > have) copy = have; 842168404Spjd if (copy > left) copy = left; 843168404Spjd if (copy == 0) goto inf_leave; 844168404Spjd zmemcpy(put, next, copy); 845168404Spjd have -= copy; 846168404Spjd next += copy; 847168404Spjd left -= copy; 848168404Spjd put += copy; 849168404Spjd state->length -= copy; 850168404Spjd break; 851168404Spjd } 852168404Spjd Tracev((stderr, "inflate: stored end\n")); 853168404Spjd state->mode = TYPE; 854168404Spjd break; 855168404Spjd case TABLE: 856168404Spjd NEEDBITS(14); 857168404Spjd state->nlen = BITS(5) + 257; 858168404Spjd DROPBITS(5); 859168404Spjd state->ndist = BITS(5) + 1; 860168404Spjd DROPBITS(5); 861168404Spjd state->ncode = BITS(4) + 4; 862168404Spjd DROPBITS(4); 863168404Spjd#ifndef PKZIP_BUG_WORKAROUND 864168404Spjd if (state->nlen > 286 || state->ndist > 30) { 865168404Spjd strm->msg = (char *)"too many length or distance symbols"; 866168404Spjd state->mode = BAD; 867168404Spjd break; 868168404Spjd } 869168404Spjd#endif 870168404Spjd Tracev((stderr, "inflate: table sizes ok\n")); 871168404Spjd state->have = 0; 872168404Spjd state->mode = LENLENS; 873168404Spjd /*FALLTHRU*/ 874168404Spjd case LENLENS: 875168404Spjd while (state->have < state->ncode) { 876168404Spjd NEEDBITS(3); 877168404Spjd state->lens[order[state->have++]] = (unsigned short)BITS(3); 878168404Spjd DROPBITS(3); 879168404Spjd } 880168404Spjd while (state->have < 19) 881168404Spjd state->lens[order[state->have++]] = 0; 882168404Spjd state->next = state->codes; 883168404Spjd state->lencode = (code const FAR *)(state->next); 884168404Spjd state->lenbits = 7; 885168404Spjd ret = inflate_table(CODES, state->lens, 19, &(state->next), 886168404Spjd &(state->lenbits), state->work); 887168404Spjd if (ret) { 888168404Spjd strm->msg = (char *)"invalid code lengths set"; 889168404Spjd state->mode = BAD; 890168404Spjd break; 891168404Spjd } 892168404Spjd Tracev((stderr, "inflate: code lengths ok\n")); 893168404Spjd state->have = 0; 894168404Spjd state->mode = CODELENS; 895168404Spjd /*FALLTHRU*/ 896168404Spjd case CODELENS: 897168404Spjd while (state->have < state->nlen + state->ndist) { 898168404Spjd for (;;) { 899168404Spjd this = state->lencode[BITS(state->lenbits)]; 900168404Spjd if ((unsigned)(this.bits) <= bits) break; 901168404Spjd PULLBYTE(); 902168404Spjd } 903168404Spjd if (this.val < 16) { 904168404Spjd NEEDBITS(this.bits); 905168404Spjd DROPBITS(this.bits); 906168404Spjd state->lens[state->have++] = this.val; 907168404Spjd } 908168404Spjd else { 909168404Spjd if (this.val == 16) { 910168404Spjd NEEDBITS(this.bits + 2); 911168404Spjd DROPBITS(this.bits); 912168404Spjd if (state->have == 0) { 913168404Spjd strm->msg = (char *)"invalid bit length repeat"; 914168404Spjd state->mode = BAD; 915168404Spjd break; 916168404Spjd } 917168404Spjd len = state->lens[state->have - 1]; 918168404Spjd copy = 3 + BITS(2); 919168404Spjd DROPBITS(2); 920168404Spjd } 921168404Spjd else if (this.val == 17) { 922168404Spjd NEEDBITS(this.bits + 3); 923168404Spjd DROPBITS(this.bits); 924168404Spjd len = 0; 925168404Spjd copy = 3 + BITS(3); 926168404Spjd DROPBITS(3); 927168404Spjd } 928168404Spjd else { 929168404Spjd NEEDBITS(this.bits + 7); 930168404Spjd DROPBITS(this.bits); 931168404Spjd len = 0; 932168404Spjd copy = 11 + BITS(7); 933168404Spjd DROPBITS(7); 934168404Spjd } 935168404Spjd if (state->have + copy > state->nlen + state->ndist) { 936168404Spjd strm->msg = (char *)"invalid bit length repeat"; 937168404Spjd state->mode = BAD; 938168404Spjd break; 939168404Spjd } 940168404Spjd while (copy--) 941168404Spjd state->lens[state->have++] = (unsigned short)len; 942168404Spjd } 943168404Spjd } 944168404Spjd 945168404Spjd /* handle error breaks in while */ 946168404Spjd if (state->mode == BAD) break; 947168404Spjd 948168404Spjd /* build code tables */ 949168404Spjd state->next = state->codes; 950168404Spjd state->lencode = (code const FAR *)(state->next); 951168404Spjd state->lenbits = 9; 952168404Spjd ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 953168404Spjd &(state->lenbits), state->work); 954168404Spjd if (ret) { 955168404Spjd strm->msg = (char *)"invalid literal/lengths set"; 956168404Spjd state->mode = BAD; 957168404Spjd break; 958168404Spjd } 959168404Spjd state->distcode = (code const FAR *)(state->next); 960168404Spjd state->distbits = 6; 961168404Spjd ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 962168404Spjd &(state->next), &(state->distbits), state->work); 963168404Spjd if (ret) { 964168404Spjd strm->msg = (char *)"invalid distances set"; 965168404Spjd state->mode = BAD; 966168404Spjd break; 967168404Spjd } 968168404Spjd Tracev((stderr, "inflate: codes ok\n")); 969168404Spjd state->mode = LEN; 970168404Spjd /*FALLTHRU*/ 971168404Spjd case LEN: 972168404Spjd if (have >= 6 && left >= 258) { 973168404Spjd RESTORE(); 974168404Spjd inflate_fast(strm, out); 975168404Spjd LOAD(); 976168404Spjd break; 977168404Spjd } 978168404Spjd for (;;) { 979168404Spjd this = state->lencode[BITS(state->lenbits)]; 980168404Spjd if ((unsigned)(this.bits) <= bits) break; 981168404Spjd PULLBYTE(); 982168404Spjd } 983168404Spjd if (this.op && (this.op & 0xf0) == 0) { 984168404Spjd last = this; 985168404Spjd for (;;) { 986168404Spjd this = state->lencode[last.val + 987168404Spjd (BITS(last.bits + last.op) >> last.bits)]; 988168404Spjd if ((unsigned)(last.bits + this.bits) <= bits) break; 989168404Spjd PULLBYTE(); 990168404Spjd } 991168404Spjd DROPBITS(last.bits); 992168404Spjd } 993168404Spjd DROPBITS(this.bits); 994168404Spjd state->length = (unsigned)this.val; 995168404Spjd if ((int)(this.op) == 0) { 996168404Spjd Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 997168404Spjd "inflate: literal '%c'\n" : 998168404Spjd "inflate: literal 0x%02x\n", this.val)); 999168404Spjd state->mode = LIT; 1000168404Spjd break; 1001168404Spjd } 1002168404Spjd if (this.op & 32) { 1003168404Spjd Tracevv((stderr, "inflate: end of block\n")); 1004168404Spjd state->mode = TYPE; 1005168404Spjd break; 1006168404Spjd } 1007168404Spjd if (this.op & 64) { 1008168404Spjd strm->msg = (char *)"invalid literal/length code"; 1009168404Spjd state->mode = BAD; 1010168404Spjd break; 1011168404Spjd } 1012168404Spjd state->extra = (unsigned)(this.op) & 15; 1013168404Spjd state->mode = LENEXT; 1014168404Spjd /*FALLTHRU*/ 1015168404Spjd case LENEXT: 1016168404Spjd if (state->extra) { 1017168404Spjd NEEDBITS(state->extra); 1018168404Spjd state->length += BITS(state->extra); 1019168404Spjd DROPBITS(state->extra); 1020168404Spjd } 1021168404Spjd Tracevv((stderr, "inflate: length %u\n", state->length)); 1022168404Spjd state->mode = DIST; 1023168404Spjd /*FALLTHRU*/ 1024168404Spjd case DIST: 1025168404Spjd for (;;) { 1026168404Spjd this = state->distcode[BITS(state->distbits)]; 1027168404Spjd if ((unsigned)(this.bits) <= bits) break; 1028168404Spjd PULLBYTE(); 1029168404Spjd } 1030168404Spjd if ((this.op & 0xf0) == 0) { 1031168404Spjd last = this; 1032168404Spjd for (;;) { 1033168404Spjd this = state->distcode[last.val + 1034168404Spjd (BITS(last.bits + last.op) >> last.bits)]; 1035168404Spjd if ((unsigned)(last.bits + this.bits) <= bits) break; 1036168404Spjd PULLBYTE(); 1037168404Spjd } 1038168404Spjd DROPBITS(last.bits); 1039168404Spjd } 1040168404Spjd DROPBITS(this.bits); 1041168404Spjd if (this.op & 64) { 1042168404Spjd strm->msg = (char *)"invalid distance code"; 1043168404Spjd state->mode = BAD; 1044168404Spjd break; 1045168404Spjd } 1046168404Spjd state->offset = (unsigned)this.val; 1047168404Spjd state->extra = (unsigned)(this.op) & 15; 1048168404Spjd state->mode = DISTEXT; 1049168404Spjd /*FALLTHRU*/ 1050168404Spjd case DISTEXT: 1051168404Spjd if (state->extra) { 1052168404Spjd NEEDBITS(state->extra); 1053168404Spjd state->offset += BITS(state->extra); 1054168404Spjd DROPBITS(state->extra); 1055168404Spjd } 1056168404Spjd#ifdef INFLATE_STRICT 1057168404Spjd if (state->offset > state->dmax) { 1058168404Spjd strm->msg = (char *)"invalid distance too far back"; 1059168404Spjd state->mode = BAD; 1060168404Spjd break; 1061168404Spjd } 1062168404Spjd#endif 1063168404Spjd if (state->offset > state->whave + out - left) { 1064168404Spjd strm->msg = (char *)"invalid distance too far back"; 1065168404Spjd state->mode = BAD; 1066168404Spjd break; 1067168404Spjd } 1068168404Spjd Tracevv((stderr, "inflate: distance %u\n", state->offset)); 1069168404Spjd state->mode = MATCH; 1070168404Spjd /*FALLTHRU*/ 1071168404Spjd case MATCH: 1072168404Spjd if (left == 0) goto inf_leave; 1073168404Spjd copy = out - left; 1074168404Spjd if (state->offset > copy) { /* copy from window */ 1075168404Spjd copy = state->offset - copy; 1076168404Spjd if (copy > state->write) { 1077168404Spjd copy -= state->write; 1078168404Spjd from = state->window + (state->wsize - copy); 1079168404Spjd } 1080168404Spjd else 1081168404Spjd from = state->window + (state->write - copy); 1082168404Spjd if (copy > state->length) copy = state->length; 1083168404Spjd } 1084168404Spjd else { /* copy from output */ 1085168404Spjd from = put - state->offset; 1086168404Spjd copy = state->length; 1087168404Spjd } 1088168404Spjd if (copy > left) copy = left; 1089168404Spjd left -= copy; 1090168404Spjd state->length -= copy; 1091168404Spjd do { 1092168404Spjd *put++ = *from++; 1093168404Spjd } while (--copy); 1094168404Spjd if (state->length == 0) state->mode = LEN; 1095168404Spjd break; 1096168404Spjd case LIT: 1097168404Spjd if (left == 0) goto inf_leave; 1098168404Spjd *put++ = (unsigned char)(state->length); 1099168404Spjd left--; 1100168404Spjd state->mode = LEN; 1101168404Spjd break; 1102168404Spjd case CHECK: 1103168404Spjd if (state->wrap) { 1104168404Spjd NEEDBITS(32); 1105168404Spjd out -= left; 1106168404Spjd strm->total_out += out; 1107168404Spjd state->total += out; 1108168404Spjd if (out) 1109168404Spjd strm->adler = state->check = 1110168404Spjd UPDATE(state->check, put - out, out); 1111168404Spjd out = left; 1112168404Spjd if (( 1113168404Spjd#ifdef GUNZIP 1114168404Spjd state->flags ? hold : 1115168404Spjd#endif 1116168404Spjd REVERSE(hold)) != state->check) { 1117168404Spjd strm->msg = (char *)"incorrect data check"; 1118168404Spjd state->mode = BAD; 1119168404Spjd break; 1120168404Spjd } 1121168404Spjd INITBITS(); 1122168404Spjd Tracev((stderr, "inflate: check matches trailer\n")); 1123168404Spjd } 1124168404Spjd#ifdef GUNZIP 1125168404Spjd state->mode = LENGTH; 1126168404Spjd /*FALLTHRU*/ 1127168404Spjd case LENGTH: 1128168404Spjd if (state->wrap && state->flags) { 1129168404Spjd NEEDBITS(32); 1130168404Spjd if (hold != (state->total & 0xffffffffUL)) { 1131168404Spjd strm->msg = (char *)"incorrect length check"; 1132168404Spjd state->mode = BAD; 1133168404Spjd break; 1134168404Spjd } 1135168404Spjd INITBITS(); 1136168404Spjd Tracev((stderr, "inflate: length matches trailer\n")); 1137168404Spjd } 1138168404Spjd#endif 1139168404Spjd state->mode = DONE; 1140168404Spjd /*FALLTHRU*/ 1141168404Spjd case DONE: 1142168404Spjd ret = Z_STREAM_END; 1143168404Spjd goto inf_leave; 1144168404Spjd case BAD: 1145168404Spjd ret = Z_DATA_ERROR; 1146168404Spjd goto inf_leave; 1147168404Spjd case MEM: 1148168404Spjd return Z_MEM_ERROR; 1149168404Spjd case SYNC: 1150168404Spjd default: 1151168404Spjd return Z_STREAM_ERROR; 1152168404Spjd } 1153168404Spjd 1154168404Spjd /* 1155168404Spjd Return from inflate(), updating the total counts and the check value. 1156168404Spjd If there was no progress during the inflate() call, return a buffer 1157168404Spjd error. Call updatewindow() to create and/or update the window state. 1158168404Spjd Note: a memory error from inflate() is non-recoverable. 1159168404Spjd */ 1160168404Spjd inf_leave: 1161168404Spjd RESTORE(); 1162168404Spjd if (state->wsize || (state->mode < CHECK && out != strm->avail_out)) 1163168404Spjd if (updatewindow(strm, out)) { 1164168404Spjd state->mode = MEM; 1165168404Spjd return Z_MEM_ERROR; 1166168404Spjd } 1167168404Spjd in -= strm->avail_in; 1168168404Spjd out -= strm->avail_out; 1169168404Spjd strm->total_in += in; 1170168404Spjd strm->total_out += out; 1171168404Spjd state->total += out; 1172168404Spjd if (state->wrap && out) 1173168404Spjd strm->adler = state->check = 1174168404Spjd UPDATE(state->check, strm->next_out - out, out); 1175168404Spjd strm->data_type = state->bits + (state->last ? 64 : 0) + 1176168404Spjd (state->mode == TYPE ? 128 : 0); 1177168404Spjd if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1178168404Spjd ret = Z_BUF_ERROR; 1179168404Spjd return ret; 1180168404Spjd} 1181168404Spjd 1182168404Spjdint ZEXPORT inflateEnd(strm) 1183168404Spjdz_streamp strm; 1184168404Spjd{ 1185168404Spjd struct inflate_state FAR *state; 1186168404Spjd if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1187168404Spjd return Z_STREAM_ERROR; 1188168404Spjd state = (struct inflate_state FAR *)strm->state; 1189168404Spjd if (state->window != Z_NULL) ZFREE(strm, state->window); 1190168404Spjd ZFREE(strm, strm->state); 1191168404Spjd strm->state = Z_NULL; 1192168404Spjd Tracev((stderr, "inflate: end\n")); 1193168404Spjd return Z_OK; 1194168404Spjd} 1195168404Spjd 1196168404Spjdint ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1197168404Spjdz_streamp strm; 1198168404Spjdconst Bytef *dictionary; 1199168404SpjduInt dictLength; 1200168404Spjd{ 1201168404Spjd struct inflate_state FAR *state; 1202168404Spjd unsigned long id; 1203168404Spjd 1204168404Spjd /* check state */ 1205168404Spjd if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1206168404Spjd state = (struct inflate_state FAR *)strm->state; 1207168404Spjd if (state->wrap != 0 && state->mode != DICT) 1208168404Spjd return Z_STREAM_ERROR; 1209168404Spjd 1210168404Spjd /* check for correct dictionary id */ 1211168404Spjd if (state->mode == DICT) { 1212168404Spjd id = adler32(0L, Z_NULL, 0); 1213168404Spjd id = adler32(id, dictionary, dictLength); 1214168404Spjd if (id != state->check) 1215168404Spjd return Z_DATA_ERROR; 1216168404Spjd } 1217168404Spjd 1218168404Spjd /* copy dictionary to window */ 1219168404Spjd if (updatewindow(strm, strm->avail_out)) { 1220168404Spjd state->mode = MEM; 1221168404Spjd return Z_MEM_ERROR; 1222168404Spjd } 1223168404Spjd if (dictLength > state->wsize) { 1224168404Spjd zmemcpy(state->window, dictionary + dictLength - state->wsize, 1225168404Spjd state->wsize); 1226168404Spjd state->whave = state->wsize; 1227168404Spjd } 1228168404Spjd else { 1229168404Spjd zmemcpy(state->window + state->wsize - dictLength, dictionary, 1230168404Spjd dictLength); 1231168404Spjd state->whave = dictLength; 1232168404Spjd } 1233168404Spjd state->havedict = 1; 1234168404Spjd Tracev((stderr, "inflate: dictionary set\n")); 1235168404Spjd return Z_OK; 1236168404Spjd} 1237168404Spjd 1238168404Spjdint ZEXPORT inflateGetHeader(strm, head) 1239168404Spjdz_streamp strm; 1240168404Spjdgz_headerp head; 1241168404Spjd{ 1242168404Spjd struct inflate_state FAR *state; 1243168404Spjd 1244168404Spjd /* check state */ 1245168404Spjd if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1246168404Spjd state = (struct inflate_state FAR *)strm->state; 1247168404Spjd if ((state->wrap & 2) == 0) return Z_STREAM_ERROR; 1248168404Spjd 1249168404Spjd /* save header structure */ 1250168404Spjd state->head = head; 1251168404Spjd head->done = 0; 1252168404Spjd return Z_OK; 1253168404Spjd} 1254168404Spjd 1255168404Spjd/* 1256168404Spjd Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1257168404Spjd or when out of input. When called, *have is the number of pattern bytes 1258168404Spjd found in order so far, in 0..3. On return *have is updated to the new 1259168404Spjd state. If on return *have equals four, then the pattern was found and the 1260168404Spjd return value is how many bytes were read including the last byte of the 1261168404Spjd pattern. If *have is less than four, then the pattern has not been found 1262168404Spjd yet and the return value is len. In the latter case, syncsearch() can be 1263168404Spjd called again with more data and the *have state. *have is initialized to 1264168404Spjd zero for the first call. 1265168404Spjd */ 1266168404Spjdlocal unsigned syncsearch(have, buf, len) 1267168404Spjdunsigned FAR *have; 1268168404Spjdunsigned char FAR *buf; 1269168404Spjdunsigned len; 1270168404Spjd{ 1271168404Spjd unsigned got; 1272168404Spjd unsigned next; 1273168404Spjd 1274168404Spjd got = *have; 1275168404Spjd next = 0; 1276168404Spjd while (next < len && got < 4) { 1277168404Spjd if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1278168404Spjd got++; 1279168404Spjd else if (buf[next]) 1280168404Spjd got = 0; 1281168404Spjd else 1282168404Spjd got = 4 - got; 1283168404Spjd next++; 1284168404Spjd } 1285168404Spjd *have = got; 1286168404Spjd return next; 1287168404Spjd} 1288168404Spjd 1289168404Spjdint ZEXPORT inflateSync(strm) 1290168404Spjdz_streamp strm; 1291168404Spjd{ 1292168404Spjd unsigned len; /* number of bytes to look at or looked at */ 1293168404Spjd unsigned long in, out; /* temporary to save total_in and total_out */ 1294168404Spjd unsigned char buf[4]; /* to restore bit buffer to byte string */ 1295168404Spjd struct inflate_state FAR *state; 1296168404Spjd 1297168404Spjd /* check parameters */ 1298168404Spjd if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1299168404Spjd state = (struct inflate_state FAR *)strm->state; 1300168404Spjd if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 1301168404Spjd 1302168404Spjd /* if first time, start search in bit buffer */ 1303168404Spjd if (state->mode != SYNC) { 1304168404Spjd state->mode = SYNC; 1305168404Spjd state->hold <<= state->bits & 7; 1306168404Spjd state->bits -= state->bits & 7; 1307168404Spjd len = 0; 1308168404Spjd while (state->bits >= 8) { 1309168404Spjd buf[len++] = (unsigned char)(state->hold); 1310168404Spjd state->hold >>= 8; 1311168404Spjd state->bits -= 8; 1312168404Spjd } 1313168404Spjd state->have = 0; 1314168404Spjd (void) syncsearch(&(state->have), buf, len); 1315168404Spjd } 1316168404Spjd 1317168404Spjd /* search available input */ 1318168404Spjd len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1319168404Spjd strm->avail_in -= len; 1320168404Spjd strm->next_in += len; 1321168404Spjd strm->total_in += len; 1322168404Spjd 1323168404Spjd /* return no joy or set up to restart inflate() on a new block */ 1324168404Spjd if (state->have != 4) return Z_DATA_ERROR; 1325168404Spjd in = strm->total_in; out = strm->total_out; 1326168404Spjd (void) inflateReset(strm); 1327168404Spjd strm->total_in = in; strm->total_out = out; 1328168404Spjd state->mode = TYPE; 1329168404Spjd return Z_OK; 1330168404Spjd} 1331168404Spjd 1332168404Spjd/* 1333168404Spjd Returns true if inflate is currently at the end of a block generated by 1334168404Spjd Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1335168404Spjd implementation to provide an additional safety check. PPP uses 1336168404Spjd Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1337168404Spjd block. When decompressing, PPP checks that at the end of input packet, 1338168404Spjd inflate is waiting for these length bytes. 1339168404Spjd */ 1340168404Spjdint ZEXPORT inflateSyncPoint(strm) 1341168404Spjdz_streamp strm; 1342168404Spjd{ 1343168404Spjd struct inflate_state FAR *state; 1344168404Spjd 1345168404Spjd if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1346168404Spjd state = (struct inflate_state FAR *)strm->state; 1347168404Spjd return state->mode == STORED && state->bits == 0; 1348168404Spjd} 1349168404Spjd 1350168404Spjdint ZEXPORT inflateCopy(dest, source) 1351168404Spjdz_streamp dest; 1352168404Spjdz_streamp source; 1353168404Spjd{ 1354168404Spjd struct inflate_state FAR *state; 1355168404Spjd struct inflate_state FAR *copy; 1356168404Spjd unsigned char FAR *window; 1357168404Spjd unsigned wsize; 1358168404Spjd 1359168404Spjd /* check input */ 1360168404Spjd if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1361168404Spjd source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1362168404Spjd return Z_STREAM_ERROR; 1363168404Spjd state = (struct inflate_state FAR *)source->state; 1364168404Spjd 1365168404Spjd /* allocate space */ 1366168404Spjd copy = (struct inflate_state FAR *) 1367168404Spjd ZALLOC(source, 1, sizeof(struct inflate_state)); 1368168404Spjd if (copy == Z_NULL) return Z_MEM_ERROR; 1369168404Spjd window = Z_NULL; 1370168404Spjd if (state->window != Z_NULL) { 1371168404Spjd window = (unsigned char FAR *) 1372168404Spjd ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1373168404Spjd if (window == Z_NULL) { 1374168404Spjd ZFREE(source, copy); 1375168404Spjd return Z_MEM_ERROR; 1376168404Spjd } 1377168404Spjd } 1378168404Spjd 1379168404Spjd /* copy state */ 1380168404Spjd zmemcpy(dest, source, sizeof(z_stream)); 1381168404Spjd zmemcpy(copy, state, sizeof(struct inflate_state)); 1382168404Spjd if (state->lencode >= state->codes && 1383168404Spjd state->lencode <= state->codes + ENOUGH - 1) { 1384168404Spjd copy->lencode = copy->codes + (state->lencode - state->codes); 1385168404Spjd copy->distcode = copy->codes + (state->distcode - state->codes); 1386168404Spjd } 1387168404Spjd copy->next = copy->codes + (state->next - state->codes); 1388168404Spjd if (window != Z_NULL) { 1389168404Spjd wsize = 1U << state->wbits; 1390168404Spjd zmemcpy(window, state->window, wsize); 1391168404Spjd } 1392168404Spjd copy->window = window; 1393168404Spjd dest->state = (struct internal_state FAR *)copy; 1394168404Spjd return Z_OK; 1395168404Spjd} 1396