1131380Stjr/* inflate.c -- zlib decompression 2237410Sdelphij * Copyright (C) 1995-2012 Mark Adler 3131380Stjr * For conditions of distribution and use, see copyright notice in zlib.h 417651Speter */ 517651Speter 6131380Stjr/* 7131380Stjr * Change history: 8131380Stjr * 9131380Stjr * 1.2.beta0 24 Nov 2002 10131380Stjr * - First version -- complete rewrite of inflate to simplify code, avoid 11131380Stjr * creation of window when not needed, minimize use of window when it is 12131380Stjr * needed, make inffast.c even faster, implement gzip decoding, and to 13131380Stjr * improve code readability and style over the previous zlib inflate code 14131380Stjr * 15131380Stjr * 1.2.beta1 25 Nov 2002 16131380Stjr * - Use pointers for available input and output checking in inffast.c 17131380Stjr * - Remove input and output counters in inffast.c 18131380Stjr * - Change inffast.c entry and loop from avail_in >= 7 to >= 6 19131380Stjr * - Remove unnecessary second byte pull from length extra in inffast.c 20131380Stjr * - Unroll direct copy to three copies per loop in inffast.c 21131380Stjr * 22131380Stjr * 1.2.beta2 4 Dec 2002 23131380Stjr * - Change external routine names to reduce potential conflicts 24131380Stjr * - Correct filename to inffixed.h for fixed tables in inflate.c 25131380Stjr * - Make hbuf[] unsigned char to match parameter type in inflate.c 26131380Stjr * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 27131380Stjr * to avoid negation problem on Alphas (64 bit) in inflate.c 28131380Stjr * 29131380Stjr * 1.2.beta3 22 Dec 2002 30131380Stjr * - Add comments on state->bits assertion in inffast.c 31131380Stjr * - Add comments on op field in inftrees.h 32131380Stjr * - Fix bug in reuse of allocated window after inflateReset() 33131380Stjr * - Remove bit fields--back to byte structure for speed 34131380Stjr * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 35131380Stjr * - Change post-increments to pre-increments in inflate_fast(), PPC biased? 36131380Stjr * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 37131380Stjr * - Make MATCH copy in inflate() much faster for when inflate_fast() not used 38131380Stjr * - Use local copies of stream next and avail values, as well as local bit 39131380Stjr * buffer and bit count in inflate()--for speed when inflate_fast() not used 40131380Stjr * 41131380Stjr * 1.2.beta4 1 Jan 2003 42131380Stjr * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings 43131380Stjr * - Move a comment on output buffer sizes from inffast.c to inflate.c 44131380Stjr * - Add comments in inffast.c to introduce the inflate_fast() routine 45131380Stjr * - Rearrange window copies in inflate_fast() for speed and simplification 46131380Stjr * - Unroll last copy for window match in inflate_fast() 47131380Stjr * - Use local copies of window variables in inflate_fast() for speed 48205471Sdelphij * - Pull out common wnext == 0 case for speed in inflate_fast() 49131380Stjr * - Make op and len in inflate_fast() unsigned for consistency 50131380Stjr * - Add FAR to lcode and dcode declarations in inflate_fast() 51131380Stjr * - Simplified bad distance check in inflate_fast() 52131380Stjr * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 53131380Stjr * source file infback.c to provide a call-back interface to inflate for 54131380Stjr * programs like gzip and unzip -- uses window as output buffer to avoid 55131380Stjr * window copying 56131380Stjr * 57131380Stjr * 1.2.beta5 1 Jan 2003 58131380Stjr * - Improved inflateBack() interface to allow the caller to provide initial 59131380Stjr * input in strm. 60131380Stjr * - Fixed stored blocks bug in inflateBack() 61131380Stjr * 62131380Stjr * 1.2.beta6 4 Jan 2003 63131380Stjr * - Added comments in inffast.c on effectiveness of POSTINC 64131380Stjr * - Typecasting all around to reduce compiler warnings 65131380Stjr * - Changed loops from while (1) or do {} while (1) to for (;;), again to 66131380Stjr * make compilers happy 67131380Stjr * - Changed type of window in inflateBackInit() to unsigned char * 68131380Stjr * 69131380Stjr * 1.2.beta7 27 Jan 2003 70131380Stjr * - Changed many types to unsigned or unsigned short to avoid warnings 71131380Stjr * - Added inflateCopy() function 72131380Stjr * 73131380Stjr * 1.2.0 9 Mar 2003 74131380Stjr * - Changed inflateBack() interface to provide separate opaque descriptors 75131380Stjr * for the in() and out() functions 76131380Stjr * - Changed inflateBack() argument and in_func typedef to swap the length 77131380Stjr * and buffer address return values for the input function 78131380Stjr * - Check next_in and next_out for Z_NULL on entry to inflate() 79131380Stjr * 80131380Stjr * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 81131380Stjr */ 82131380Stjr 8317651Speter#include "zutil.h" 84131380Stjr#include "inftrees.h" 85131380Stjr#include "inflate.h" 86131380Stjr#include "inffast.h" 8717651Speter 88131380Stjr#ifdef MAKEFIXED 89131380Stjr# ifndef BUILDFIXED 90131380Stjr# define BUILDFIXED 91131380Stjr# endif 92131380Stjr#endif 9317651Speter 94131380Stjr/* function prototypes */ 95131380Stjrlocal void fixedtables OF((struct inflate_state FAR *state)); 96250261Sdelphijlocal int updatewindow OF((z_streamp strm, const unsigned char FAR *end, 97250261Sdelphij unsigned copy)); 98131380Stjr#ifdef BUILDFIXED 99131380Stjr void makefixed OF((void)); 100131380Stjr#endif 101250261Sdelphijlocal unsigned syncsearch OF((unsigned FAR *have, const unsigned char FAR *buf, 102131380Stjr unsigned len)); 10317651Speter 104237410Sdelphijint ZEXPORT inflateResetKeep(strm) 105131380Stjrz_streamp strm; 106131380Stjr{ 107131380Stjr struct inflate_state FAR *state; 10833904Ssteve 109131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 110131380Stjr state = (struct inflate_state FAR *)strm->state; 111131380Stjr strm->total_in = strm->total_out = state->total = 0; 112131380Stjr strm->msg = Z_NULL; 113237410Sdelphij if (state->wrap) /* to support ill-conceived Java test suite */ 114237410Sdelphij strm->adler = state->wrap & 1; 115131380Stjr state->mode = HEAD; 116131380Stjr state->last = 0; 117131380Stjr state->havedict = 0; 118157046Sdes state->dmax = 32768U; 119157046Sdes state->head = Z_NULL; 120131380Stjr state->hold = 0; 121131380Stjr state->bits = 0; 122131380Stjr state->lencode = state->distcode = state->next = state->codes; 123205471Sdelphij state->sane = 1; 124205471Sdelphij state->back = -1; 125131380Stjr Tracev((stderr, "inflate: reset\n")); 126131380Stjr return Z_OK; 127131380Stjr} 12833904Ssteve 129237410Sdelphijint ZEXPORT inflateReset(strm) 130237410Sdelphijz_streamp strm; 131237410Sdelphij{ 132237410Sdelphij struct inflate_state FAR *state; 133237410Sdelphij 134237410Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 135237410Sdelphij state = (struct inflate_state FAR *)strm->state; 136237410Sdelphij state->wsize = 0; 137237410Sdelphij state->whave = 0; 138237410Sdelphij state->wnext = 0; 139237410Sdelphij return inflateResetKeep(strm); 140237410Sdelphij} 141237410Sdelphij 142205471Sdelphijint ZEXPORT inflateReset2(strm, windowBits) 143157046Sdesz_streamp strm; 144205471Sdelphijint windowBits; 145157046Sdes{ 146205471Sdelphij int wrap; 147157046Sdes struct inflate_state FAR *state; 148157046Sdes 149205471Sdelphij /* get the state */ 150157046Sdes if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 151157046Sdes state = (struct inflate_state FAR *)strm->state; 152205471Sdelphij 153205471Sdelphij /* extract wrap request from windowBits parameter */ 154205471Sdelphij if (windowBits < 0) { 155205471Sdelphij wrap = 0; 156205471Sdelphij windowBits = -windowBits; 157205471Sdelphij } 158205471Sdelphij else { 159205471Sdelphij wrap = (windowBits >> 4) + 1; 160205471Sdelphij#ifdef GUNZIP 161205471Sdelphij if (windowBits < 48) 162205471Sdelphij windowBits &= 15; 163205471Sdelphij#endif 164205471Sdelphij } 165205471Sdelphij 166205471Sdelphij /* set number of window bits, free window if different */ 167205471Sdelphij if (windowBits && (windowBits < 8 || windowBits > 15)) 168205471Sdelphij return Z_STREAM_ERROR; 169205471Sdelphij if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) { 170205471Sdelphij ZFREE(strm, state->window); 171205471Sdelphij state->window = Z_NULL; 172205471Sdelphij } 173205471Sdelphij 174205471Sdelphij /* update state and reset the rest of it */ 175205471Sdelphij state->wrap = wrap; 176205471Sdelphij state->wbits = (unsigned)windowBits; 177205471Sdelphij return inflateReset(strm); 178157046Sdes} 179157046Sdes 180131380Stjrint ZEXPORT inflateInit2_(strm, windowBits, version, stream_size) 181131380Stjrz_streamp strm; 182131380Stjrint windowBits; 183131380Stjrconst char *version; 184131380Stjrint stream_size; 185131380Stjr{ 186205471Sdelphij int ret; 187131380Stjr struct inflate_state FAR *state; 18817651Speter 189131380Stjr if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 190131380Stjr stream_size != (int)(sizeof(z_stream))) 191131380Stjr return Z_VERSION_ERROR; 192131380Stjr if (strm == Z_NULL) return Z_STREAM_ERROR; 193131380Stjr strm->msg = Z_NULL; /* in case we return an error */ 194131380Stjr if (strm->zalloc == (alloc_func)0) { 195237410Sdelphij#ifdef Z_SOLO 196237410Sdelphij return Z_STREAM_ERROR; 197237410Sdelphij#else 198131380Stjr strm->zalloc = zcalloc; 199131380Stjr strm->opaque = (voidpf)0; 200237410Sdelphij#endif 201131380Stjr } 202237410Sdelphij if (strm->zfree == (free_func)0) 203237410Sdelphij#ifdef Z_SOLO 204237410Sdelphij return Z_STREAM_ERROR; 205237410Sdelphij#else 206237410Sdelphij strm->zfree = zcfree; 207237410Sdelphij#endif 208131380Stjr state = (struct inflate_state FAR *) 209131380Stjr ZALLOC(strm, 1, sizeof(struct inflate_state)); 210131380Stjr if (state == Z_NULL) return Z_MEM_ERROR; 211131380Stjr Tracev((stderr, "inflate: allocated\n")); 212157046Sdes strm->state = (struct internal_state FAR *)state; 213205471Sdelphij state->window = Z_NULL; 214205471Sdelphij ret = inflateReset2(strm, windowBits); 215205471Sdelphij if (ret != Z_OK) { 216131380Stjr ZFREE(strm, state); 217131380Stjr strm->state = Z_NULL; 218131380Stjr } 219205471Sdelphij return ret; 220131380Stjr} 22117651Speter 222131380Stjrint ZEXPORT inflateInit_(strm, version, stream_size) 223131380Stjrz_streamp strm; 224131380Stjrconst char *version; 225131380Stjrint stream_size; 22617651Speter{ 227131380Stjr return inflateInit2_(strm, DEF_WBITS, version, stream_size); 22817651Speter} 22917651Speter 230205471Sdelphijint ZEXPORT inflatePrime(strm, bits, value) 231205471Sdelphijz_streamp strm; 232205471Sdelphijint bits; 233205471Sdelphijint value; 234205471Sdelphij{ 235205471Sdelphij struct inflate_state FAR *state; 236205471Sdelphij 237205471Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 238205471Sdelphij state = (struct inflate_state FAR *)strm->state; 239205471Sdelphij if (bits < 0) { 240205471Sdelphij state->hold = 0; 241205471Sdelphij state->bits = 0; 242205471Sdelphij return Z_OK; 243205471Sdelphij } 244205471Sdelphij if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR; 245205471Sdelphij value &= (1L << bits) - 1; 246205471Sdelphij state->hold += value << state->bits; 247205471Sdelphij state->bits += bits; 248205471Sdelphij return Z_OK; 249205471Sdelphij} 250205471Sdelphij 251131380Stjr/* 252131380Stjr Return state with length and distance decoding tables and index sizes set to 253131380Stjr fixed code decoding. Normally this returns fixed tables from inffixed.h. 254131380Stjr If BUILDFIXED is defined, then instead this routine builds the tables the 255131380Stjr first time it's called, and returns those tables the first time and 256131380Stjr thereafter. This reduces the size of the code by about 2K bytes, in 257131380Stjr exchange for a little execution time. However, BUILDFIXED should not be 258131380Stjr used for threaded applications, since the rewriting of the tables and virgin 259131380Stjr may not be thread-safe. 260131380Stjr */ 261131380Stjrlocal void fixedtables(state) 262131380Stjrstruct inflate_state FAR *state; 263131380Stjr{ 264131380Stjr#ifdef BUILDFIXED 265131380Stjr static int virgin = 1; 266131380Stjr static code *lenfix, *distfix; 267131380Stjr static code fixed[544]; 26817651Speter 269131380Stjr /* build fixed huffman tables if first call (may not be thread safe) */ 270131380Stjr if (virgin) { 271131380Stjr unsigned sym, bits; 272131380Stjr static code *next; 273131380Stjr 274131380Stjr /* literal/length table */ 275131380Stjr sym = 0; 276131380Stjr while (sym < 144) state->lens[sym++] = 8; 277131380Stjr while (sym < 256) state->lens[sym++] = 9; 278131380Stjr while (sym < 280) state->lens[sym++] = 7; 279131380Stjr while (sym < 288) state->lens[sym++] = 8; 280131380Stjr next = fixed; 281131380Stjr lenfix = next; 282131380Stjr bits = 9; 283131380Stjr inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); 284131380Stjr 285131380Stjr /* distance table */ 286131380Stjr sym = 0; 287131380Stjr while (sym < 32) state->lens[sym++] = 5; 288131380Stjr distfix = next; 289131380Stjr bits = 5; 290131380Stjr inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); 291131380Stjr 292131380Stjr /* do this just once */ 293131380Stjr virgin = 0; 294131380Stjr } 295131380Stjr#else /* !BUILDFIXED */ 296131380Stjr# include "inffixed.h" 297131380Stjr#endif /* BUILDFIXED */ 298131380Stjr state->lencode = lenfix; 299131380Stjr state->lenbits = 9; 300131380Stjr state->distcode = distfix; 301131380Stjr state->distbits = 5; 30217651Speter} 30317651Speter 304131380Stjr#ifdef MAKEFIXED 305131380Stjr#include <stdio.h> 30617651Speter 307131380Stjr/* 308131380Stjr Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also 309131380Stjr defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 310131380Stjr those tables to stdout, which would be piped to inffixed.h. A small program 311131380Stjr can simply call makefixed to do this: 31217651Speter 313131380Stjr void makefixed(void); 31417651Speter 315131380Stjr int main(void) 316131380Stjr { 317131380Stjr makefixed(); 318131380Stjr return 0; 319131380Stjr } 32017651Speter 321131380Stjr Then that can be linked with zlib built with MAKEFIXED defined and run: 32217651Speter 323131380Stjr a.out > inffixed.h 324131380Stjr */ 325131380Stjrvoid makefixed() 326131380Stjr{ 327131380Stjr unsigned low, size; 328131380Stjr struct inflate_state state; 32917651Speter 330131380Stjr fixedtables(&state); 331131380Stjr puts(" /* inffixed.h -- table for decoding fixed codes"); 332131380Stjr puts(" * Generated automatically by makefixed()."); 333131380Stjr puts(" */"); 334131380Stjr puts(""); 335131380Stjr puts(" /* WARNING: this file should *not* be used by applications."); 336131380Stjr puts(" It is part of the implementation of this library and is"); 337131380Stjr puts(" subject to change. Applications should only use zlib.h."); 338131380Stjr puts(" */"); 339131380Stjr puts(""); 340131380Stjr size = 1U << 9; 341131380Stjr printf(" static const code lenfix[%u] = {", size); 342131380Stjr low = 0; 343131380Stjr for (;;) { 344131380Stjr if ((low % 7) == 0) printf("\n "); 345237410Sdelphij printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op, 346237410Sdelphij state.lencode[low].bits, state.lencode[low].val); 347131380Stjr if (++low == size) break; 348131380Stjr putchar(','); 349131380Stjr } 350131380Stjr puts("\n };"); 351131380Stjr size = 1U << 5; 352131380Stjr printf("\n static const code distfix[%u] = {", size); 353131380Stjr low = 0; 354131380Stjr for (;;) { 355131380Stjr if ((low % 6) == 0) printf("\n "); 356131380Stjr printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits, 357131380Stjr state.distcode[low].val); 358131380Stjr if (++low == size) break; 359131380Stjr putchar(','); 360131380Stjr } 361131380Stjr puts("\n };"); 36217651Speter} 363131380Stjr#endif /* MAKEFIXED */ 36417651Speter 365131380Stjr/* 366131380Stjr Update the window with the last wsize (normally 32K) bytes written before 367131380Stjr returning. If window does not exist yet, create it. This is only called 368131380Stjr when a window is already in use, or when output has been written during this 369131380Stjr inflate call, but the end of the deflate stream has not been reached yet. 370131380Stjr It is also called to create a window for dictionary data when a dictionary 371131380Stjr is loaded. 37217651Speter 373131380Stjr Providing output buffers larger than 32K to inflate() should provide a speed 374131380Stjr advantage, since only the last 32K of output is copied to the sliding window 375131380Stjr upon return from inflate(), and since all distances after the first 32K of 376131380Stjr output will fall in the output data, making match copies simpler and faster. 377131380Stjr The advantage may be dependent on the size of the processor's data caches. 378131380Stjr */ 379250261Sdelphijlocal int updatewindow(strm, end, copy) 380131380Stjrz_streamp strm; 381250261Sdelphijconst Bytef *end; 382250261Sdelphijunsigned copy; 38317651Speter{ 384131380Stjr struct inflate_state FAR *state; 385250261Sdelphij unsigned dist; 386131380Stjr 387131380Stjr state = (struct inflate_state FAR *)strm->state; 388131380Stjr 389131380Stjr /* if it hasn't been done already, allocate space for the window */ 390131380Stjr if (state->window == Z_NULL) { 391131380Stjr state->window = (unsigned char FAR *) 392131380Stjr ZALLOC(strm, 1U << state->wbits, 393131380Stjr sizeof(unsigned char)); 394131380Stjr if (state->window == Z_NULL) return 1; 395131380Stjr } 396131380Stjr 397131380Stjr /* if window not in use yet, initialize */ 398131380Stjr if (state->wsize == 0) { 399131380Stjr state->wsize = 1U << state->wbits; 400205471Sdelphij state->wnext = 0; 401131380Stjr state->whave = 0; 402131380Stjr } 403131380Stjr 404131380Stjr /* copy state->wsize or less output bytes into the circular window */ 405131380Stjr if (copy >= state->wsize) { 406250261Sdelphij zmemcpy(state->window, end - state->wsize, state->wsize); 407205471Sdelphij state->wnext = 0; 408131380Stjr state->whave = state->wsize; 409131380Stjr } 410131380Stjr else { 411205471Sdelphij dist = state->wsize - state->wnext; 412131380Stjr if (dist > copy) dist = copy; 413250261Sdelphij zmemcpy(state->window + state->wnext, end - copy, dist); 414131380Stjr copy -= dist; 415131380Stjr if (copy) { 416250261Sdelphij zmemcpy(state->window, end - copy, copy); 417205471Sdelphij state->wnext = copy; 418131380Stjr state->whave = state->wsize; 419131380Stjr } 420131380Stjr else { 421205471Sdelphij state->wnext += dist; 422205471Sdelphij if (state->wnext == state->wsize) state->wnext = 0; 423131380Stjr if (state->whave < state->wsize) state->whave += dist; 424131380Stjr } 425131380Stjr } 426131380Stjr return 0; 42717651Speter} 42817651Speter 429131380Stjr/* Macros for inflate(): */ 43017651Speter 431131380Stjr/* check function to use adler32() for zlib or crc32() for gzip */ 432131380Stjr#ifdef GUNZIP 433131380Stjr# define UPDATE(check, buf, len) \ 434131380Stjr (state->flags ? crc32(check, buf, len) : adler32(check, buf, len)) 435131380Stjr#else 436131380Stjr# define UPDATE(check, buf, len) adler32(check, buf, len) 437131380Stjr#endif 43817651Speter 439131380Stjr/* check macros for header crc */ 440131380Stjr#ifdef GUNZIP 441131380Stjr# define CRC2(check, word) \ 442131380Stjr do { \ 443131380Stjr hbuf[0] = (unsigned char)(word); \ 444131380Stjr hbuf[1] = (unsigned char)((word) >> 8); \ 445131380Stjr check = crc32(check, hbuf, 2); \ 446131380Stjr } while (0) 44717651Speter 448131380Stjr# define CRC4(check, word) \ 449131380Stjr do { \ 450131380Stjr hbuf[0] = (unsigned char)(word); \ 451131380Stjr hbuf[1] = (unsigned char)((word) >> 8); \ 452131380Stjr hbuf[2] = (unsigned char)((word) >> 16); \ 453131380Stjr hbuf[3] = (unsigned char)((word) >> 24); \ 454131380Stjr check = crc32(check, hbuf, 4); \ 455131380Stjr } while (0) 456131380Stjr#endif 457131380Stjr 458131380Stjr/* Load registers with state in inflate() for speed */ 459131380Stjr#define LOAD() \ 460131380Stjr do { \ 461131380Stjr put = strm->next_out; \ 462131380Stjr left = strm->avail_out; \ 463131380Stjr next = strm->next_in; \ 464131380Stjr have = strm->avail_in; \ 465131380Stjr hold = state->hold; \ 466131380Stjr bits = state->bits; \ 467131380Stjr } while (0) 468131380Stjr 469131380Stjr/* Restore state from registers in inflate() */ 470131380Stjr#define RESTORE() \ 471131380Stjr do { \ 472131380Stjr strm->next_out = put; \ 473131380Stjr strm->avail_out = left; \ 474131380Stjr strm->next_in = next; \ 475131380Stjr strm->avail_in = have; \ 476131380Stjr state->hold = hold; \ 477131380Stjr state->bits = bits; \ 478131380Stjr } while (0) 479131380Stjr 480131380Stjr/* Clear the input bit accumulator */ 481131380Stjr#define INITBITS() \ 482131380Stjr do { \ 483131380Stjr hold = 0; \ 484131380Stjr bits = 0; \ 485131380Stjr } while (0) 486131380Stjr 487131380Stjr/* Get a byte of input into the bit accumulator, or return from inflate() 488131380Stjr if there is no input available. */ 489131380Stjr#define PULLBYTE() \ 490131380Stjr do { \ 491131380Stjr if (have == 0) goto inf_leave; \ 492131380Stjr have--; \ 493131380Stjr hold += (unsigned long)(*next++) << bits; \ 494131380Stjr bits += 8; \ 495131380Stjr } while (0) 496131380Stjr 497131380Stjr/* Assure that there are at least n bits in the bit accumulator. If there is 498131380Stjr not enough available input to do that, then return from inflate(). */ 499131380Stjr#define NEEDBITS(n) \ 500131380Stjr do { \ 501131380Stjr while (bits < (unsigned)(n)) \ 502131380Stjr PULLBYTE(); \ 503131380Stjr } while (0) 504131380Stjr 505131380Stjr/* Return the low n bits of the bit accumulator (n < 16) */ 506131380Stjr#define BITS(n) \ 507131380Stjr ((unsigned)hold & ((1U << (n)) - 1)) 508131380Stjr 509131380Stjr/* Remove n bits from the bit accumulator */ 510131380Stjr#define DROPBITS(n) \ 511131380Stjr do { \ 512131380Stjr hold >>= (n); \ 513131380Stjr bits -= (unsigned)(n); \ 514131380Stjr } while (0) 515131380Stjr 516131380Stjr/* Remove zero to seven bits as needed to go to a byte boundary */ 517131380Stjr#define BYTEBITS() \ 518131380Stjr do { \ 519131380Stjr hold >>= bits & 7; \ 520131380Stjr bits -= bits & 7; \ 521131380Stjr } while (0) 522131380Stjr 523131380Stjr/* 524131380Stjr inflate() uses a state machine to process as much input data and generate as 525131380Stjr much output data as possible before returning. The state machine is 526131380Stjr structured roughly as follows: 527131380Stjr 528131380Stjr for (;;) switch (state) { 529131380Stjr ... 530131380Stjr case STATEn: 531131380Stjr if (not enough input data or output space to make progress) 532131380Stjr return; 533131380Stjr ... make progress ... 534131380Stjr state = STATEm; 53517651Speter break; 536131380Stjr ... 537131380Stjr } 53817651Speter 539131380Stjr so when inflate() is called again, the same case is attempted again, and 540131380Stjr if the appropriate resources are provided, the machine proceeds to the 541131380Stjr next state. The NEEDBITS() macro is usually the way the state evaluates 542131380Stjr whether it can proceed or should return. NEEDBITS() does the return if 543131380Stjr the requested bits are not available. The typical use of the BITS macros 544131380Stjr is: 545131380Stjr 546131380Stjr NEEDBITS(n); 547131380Stjr ... do something with BITS(n) ... 548131380Stjr DROPBITS(n); 549131380Stjr 550131380Stjr where NEEDBITS(n) either returns from inflate() if there isn't enough 551131380Stjr input left to load n bits into the accumulator, or it continues. BITS(n) 552131380Stjr gives the low n bits in the accumulator. When done, DROPBITS(n) drops 553131380Stjr the low n bits off the accumulator. INITBITS() clears the accumulator 554131380Stjr and sets the number of available bits to zero. BYTEBITS() discards just 555131380Stjr enough bits to put the accumulator on a byte boundary. After BYTEBITS() 556131380Stjr and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 557131380Stjr 558131380Stjr NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 559131380Stjr if there is no input available. The decoding of variable length codes uses 560131380Stjr PULLBYTE() directly in order to pull just enough bytes to decode the next 561131380Stjr code, and no more. 562131380Stjr 563131380Stjr Some states loop until they get enough input, making sure that enough 564131380Stjr state information is maintained to continue the loop where it left off 565131380Stjr if NEEDBITS() returns in the loop. For example, want, need, and keep 566131380Stjr would all have to actually be part of the saved state in case NEEDBITS() 567131380Stjr returns: 568131380Stjr 569131380Stjr case STATEw: 570131380Stjr while (want < need) { 571131380Stjr NEEDBITS(n); 572131380Stjr keep[want++] = BITS(n); 573131380Stjr DROPBITS(n); 574131380Stjr } 575131380Stjr state = STATEx; 576131380Stjr case STATEx: 577131380Stjr 578131380Stjr As shown above, if the next state is also the next case, then the break 579131380Stjr is omitted. 580131380Stjr 581131380Stjr A state may also return if there is not enough output space available to 582131380Stjr complete that state. Those states are copying stored data, writing a 583131380Stjr literal byte, and copying a matching string. 584131380Stjr 585131380Stjr When returning, a "goto inf_leave" is used to update the total counters, 586131380Stjr update the check value, and determine whether any progress has been made 587131380Stjr during that inflate() call in order to return the proper return code. 588131380Stjr Progress is defined as a change in either strm->avail_in or strm->avail_out. 589131380Stjr When there is a window, goto inf_leave will update the window with the last 590131380Stjr output written. If a goto inf_leave occurs in the middle of decompression 591131380Stjr and there is no window currently, goto inf_leave will create one and copy 592131380Stjr output to the window for the next call of inflate(). 593131380Stjr 594131380Stjr In this implementation, the flush parameter of inflate() only affects the 595131380Stjr return code (per zlib.h). inflate() always writes as much as possible to 596131380Stjr strm->next_out, given the space available and the provided input--the effect 597131380Stjr documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 598131380Stjr the allocation of and copying into a sliding window until necessary, which 599131380Stjr provides the effect documented in zlib.h for Z_FINISH when the entire input 600131380Stjr stream available. So the only thing the flush parameter actually does is: 601131380Stjr when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 602131380Stjr will return Z_BUF_ERROR if it has not reached the end of the stream. 603131380Stjr */ 604131380Stjr 605131380Stjrint ZEXPORT inflate(strm, flush) 606131380Stjrz_streamp strm; 607131380Stjrint flush; 608131380Stjr{ 609131380Stjr struct inflate_state FAR *state; 610250261Sdelphij z_const unsigned char FAR *next; /* next input */ 611131380Stjr unsigned char FAR *put; /* next output */ 612131380Stjr unsigned have, left; /* available input and output */ 613131380Stjr unsigned long hold; /* bit buffer */ 614131380Stjr unsigned bits; /* bits in bit buffer */ 615131380Stjr unsigned in, out; /* save starting available input and output */ 616131380Stjr unsigned copy; /* number of stored or match bytes to copy */ 617131380Stjr unsigned char FAR *from; /* where to copy match bytes from */ 618205471Sdelphij code here; /* current decoding table entry */ 619131380Stjr code last; /* parent table entry */ 620131380Stjr unsigned len; /* length to copy for repeats, bits to drop */ 621131380Stjr int ret; /* return code */ 622131380Stjr#ifdef GUNZIP 623131380Stjr unsigned char hbuf[4]; /* buffer for gzip header crc calculation */ 62433904Ssteve#endif 625131380Stjr static const unsigned short order[19] = /* permutation of code lengths */ 626131380Stjr {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 627131380Stjr 628131380Stjr if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 629131380Stjr (strm->next_in == Z_NULL && strm->avail_in != 0)) 630131380Stjr return Z_STREAM_ERROR; 631131380Stjr 632131380Stjr state = (struct inflate_state FAR *)strm->state; 633131380Stjr if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 634131380Stjr LOAD(); 635131380Stjr in = have; 636131380Stjr out = left; 637131380Stjr ret = Z_OK; 638131380Stjr for (;;) 639131380Stjr switch (state->mode) { 640131380Stjr case HEAD: 641131380Stjr if (state->wrap == 0) { 642131380Stjr state->mode = TYPEDO; 643131380Stjr break; 644131380Stjr } 645131380Stjr NEEDBITS(16); 646131380Stjr#ifdef GUNZIP 647131380Stjr if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */ 648131380Stjr state->check = crc32(0L, Z_NULL, 0); 649131380Stjr CRC2(state->check, hold); 650131380Stjr INITBITS(); 651131380Stjr state->mode = FLAGS; 652131380Stjr break; 653131380Stjr } 654131380Stjr state->flags = 0; /* expect zlib header */ 655157046Sdes if (state->head != Z_NULL) 656157046Sdes state->head->done = -1; 657131380Stjr if (!(state->wrap & 1) || /* check if zlib header allowed */ 658131380Stjr#else 659131380Stjr if ( 660131380Stjr#endif 661131380Stjr ((BITS(8) << 8) + (hold >> 8)) % 31) { 662131380Stjr strm->msg = (char *)"incorrect header check"; 663131380Stjr state->mode = BAD; 664131380Stjr break; 665131380Stjr } 666131380Stjr if (BITS(4) != Z_DEFLATED) { 667131380Stjr strm->msg = (char *)"unknown compression method"; 668131380Stjr state->mode = BAD; 669131380Stjr break; 670131380Stjr } 671131380Stjr DROPBITS(4); 672157046Sdes len = BITS(4) + 8; 673205471Sdelphij if (state->wbits == 0) 674205471Sdelphij state->wbits = len; 675205471Sdelphij else if (len > state->wbits) { 676131380Stjr strm->msg = (char *)"invalid window size"; 677131380Stjr state->mode = BAD; 678131380Stjr break; 679131380Stjr } 680157046Sdes state->dmax = 1U << len; 681131380Stjr Tracev((stderr, "inflate: zlib header ok\n")); 682131380Stjr strm->adler = state->check = adler32(0L, Z_NULL, 0); 683131380Stjr state->mode = hold & 0x200 ? DICTID : TYPE; 684131380Stjr INITBITS(); 685131380Stjr break; 686131380Stjr#ifdef GUNZIP 687131380Stjr case FLAGS: 688131380Stjr NEEDBITS(16); 689131380Stjr state->flags = (int)(hold); 690131380Stjr if ((state->flags & 0xff) != Z_DEFLATED) { 691131380Stjr strm->msg = (char *)"unknown compression method"; 692131380Stjr state->mode = BAD; 693131380Stjr break; 694131380Stjr } 695131380Stjr if (state->flags & 0xe000) { 696131380Stjr strm->msg = (char *)"unknown header flags set"; 697131380Stjr state->mode = BAD; 698131380Stjr break; 699131380Stjr } 700157046Sdes if (state->head != Z_NULL) 701157046Sdes state->head->text = (int)((hold >> 8) & 1); 702131380Stjr if (state->flags & 0x0200) CRC2(state->check, hold); 703131380Stjr INITBITS(); 704131380Stjr state->mode = TIME; 705131380Stjr case TIME: 706131380Stjr NEEDBITS(32); 707157046Sdes if (state->head != Z_NULL) 708157046Sdes state->head->time = hold; 709131380Stjr if (state->flags & 0x0200) CRC4(state->check, hold); 710131380Stjr INITBITS(); 711131380Stjr state->mode = OS; 712131380Stjr case OS: 713131380Stjr NEEDBITS(16); 714157046Sdes if (state->head != Z_NULL) { 715157046Sdes state->head->xflags = (int)(hold & 0xff); 716157046Sdes state->head->os = (int)(hold >> 8); 717157046Sdes } 718131380Stjr if (state->flags & 0x0200) CRC2(state->check, hold); 719131380Stjr INITBITS(); 720131380Stjr state->mode = EXLEN; 721131380Stjr case EXLEN: 722131380Stjr if (state->flags & 0x0400) { 723131380Stjr NEEDBITS(16); 724131380Stjr state->length = (unsigned)(hold); 725157046Sdes if (state->head != Z_NULL) 726157046Sdes state->head->extra_len = (unsigned)hold; 727131380Stjr if (state->flags & 0x0200) CRC2(state->check, hold); 728131380Stjr INITBITS(); 729131380Stjr } 730157046Sdes else if (state->head != Z_NULL) 731157046Sdes state->head->extra = Z_NULL; 732131380Stjr state->mode = EXTRA; 733131380Stjr case EXTRA: 734131380Stjr if (state->flags & 0x0400) { 735131380Stjr copy = state->length; 736131380Stjr if (copy > have) copy = have; 737131380Stjr if (copy) { 738157046Sdes if (state->head != Z_NULL && 739157046Sdes state->head->extra != Z_NULL) { 740157046Sdes len = state->head->extra_len - state->length; 741157046Sdes zmemcpy(state->head->extra + len, next, 742157046Sdes len + copy > state->head->extra_max ? 743157046Sdes state->head->extra_max - len : copy); 744157046Sdes } 745131380Stjr if (state->flags & 0x0200) 746131380Stjr state->check = crc32(state->check, next, copy); 747131380Stjr have -= copy; 748131380Stjr next += copy; 749131380Stjr state->length -= copy; 750131380Stjr } 751131380Stjr if (state->length) goto inf_leave; 752131380Stjr } 753157046Sdes state->length = 0; 754131380Stjr state->mode = NAME; 755131380Stjr case NAME: 756131380Stjr if (state->flags & 0x0800) { 757131380Stjr if (have == 0) goto inf_leave; 758131380Stjr copy = 0; 759131380Stjr do { 760131380Stjr len = (unsigned)(next[copy++]); 761157046Sdes if (state->head != Z_NULL && 762157046Sdes state->head->name != Z_NULL && 763157046Sdes state->length < state->head->name_max) 764157046Sdes state->head->name[state->length++] = len; 765131380Stjr } while (len && copy < have); 766157046Sdes if (state->flags & 0x0200) 767131380Stjr state->check = crc32(state->check, next, copy); 768131380Stjr have -= copy; 769131380Stjr next += copy; 770131380Stjr if (len) goto inf_leave; 771131380Stjr } 772157046Sdes else if (state->head != Z_NULL) 773157046Sdes state->head->name = Z_NULL; 774157046Sdes state->length = 0; 775131380Stjr state->mode = COMMENT; 776131380Stjr case COMMENT: 777131380Stjr if (state->flags & 0x1000) { 778131380Stjr if (have == 0) goto inf_leave; 779131380Stjr copy = 0; 780131380Stjr do { 781131380Stjr len = (unsigned)(next[copy++]); 782157046Sdes if (state->head != Z_NULL && 783157046Sdes state->head->comment != Z_NULL && 784157046Sdes state->length < state->head->comm_max) 785157046Sdes state->head->comment[state->length++] = len; 786131380Stjr } while (len && copy < have); 787157046Sdes if (state->flags & 0x0200) 788131380Stjr state->check = crc32(state->check, next, copy); 789131380Stjr have -= copy; 790131380Stjr next += copy; 791131380Stjr if (len) goto inf_leave; 792131380Stjr } 793157046Sdes else if (state->head != Z_NULL) 794157046Sdes state->head->comment = Z_NULL; 795131380Stjr state->mode = HCRC; 796131380Stjr case HCRC: 797131380Stjr if (state->flags & 0x0200) { 798131380Stjr NEEDBITS(16); 799131380Stjr if (hold != (state->check & 0xffff)) { 800131380Stjr strm->msg = (char *)"header crc mismatch"; 801131380Stjr state->mode = BAD; 802131380Stjr break; 803131380Stjr } 804131380Stjr INITBITS(); 805131380Stjr } 806157046Sdes if (state->head != Z_NULL) { 807157046Sdes state->head->hcrc = (int)((state->flags >> 9) & 1); 808157046Sdes state->head->done = 1; 809157046Sdes } 810131380Stjr strm->adler = state->check = crc32(0L, Z_NULL, 0); 811131380Stjr state->mode = TYPE; 812131380Stjr break; 813131380Stjr#endif 814131380Stjr case DICTID: 815131380Stjr NEEDBITS(32); 816237410Sdelphij strm->adler = state->check = ZSWAP32(hold); 817131380Stjr INITBITS(); 818131380Stjr state->mode = DICT; 819131380Stjr case DICT: 820131380Stjr if (state->havedict == 0) { 821131380Stjr RESTORE(); 822131380Stjr return Z_NEED_DICT; 823131380Stjr } 824131380Stjr strm->adler = state->check = adler32(0L, Z_NULL, 0); 825131380Stjr state->mode = TYPE; 826131380Stjr case TYPE: 827205471Sdelphij if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave; 828131380Stjr case TYPEDO: 829131380Stjr if (state->last) { 830131380Stjr BYTEBITS(); 831131380Stjr state->mode = CHECK; 832131380Stjr break; 833131380Stjr } 834131380Stjr NEEDBITS(3); 835131380Stjr state->last = BITS(1); 836131380Stjr DROPBITS(1); 837131380Stjr switch (BITS(2)) { 838131380Stjr case 0: /* stored block */ 839131380Stjr Tracev((stderr, "inflate: stored block%s\n", 840131380Stjr state->last ? " (last)" : "")); 841131380Stjr state->mode = STORED; 842131380Stjr break; 843131380Stjr case 1: /* fixed block */ 844131380Stjr fixedtables(state); 845131380Stjr Tracev((stderr, "inflate: fixed codes block%s\n", 846131380Stjr state->last ? " (last)" : "")); 847205471Sdelphij state->mode = LEN_; /* decode codes */ 848205471Sdelphij if (flush == Z_TREES) { 849205471Sdelphij DROPBITS(2); 850205471Sdelphij goto inf_leave; 851205471Sdelphij } 852131380Stjr break; 853131380Stjr case 2: /* dynamic block */ 854131380Stjr Tracev((stderr, "inflate: dynamic codes block%s\n", 855131380Stjr state->last ? " (last)" : "")); 856131380Stjr state->mode = TABLE; 857131380Stjr break; 858131380Stjr case 3: 859131380Stjr strm->msg = (char *)"invalid block type"; 860131380Stjr state->mode = BAD; 861131380Stjr } 862131380Stjr DROPBITS(2); 863131380Stjr break; 864131380Stjr case STORED: 865131380Stjr BYTEBITS(); /* go to byte boundary */ 866131380Stjr NEEDBITS(32); 867131380Stjr if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 868131380Stjr strm->msg = (char *)"invalid stored block lengths"; 869131380Stjr state->mode = BAD; 870131380Stjr break; 871131380Stjr } 872131380Stjr state->length = (unsigned)hold & 0xffff; 873131380Stjr Tracev((stderr, "inflate: stored length %u\n", 874131380Stjr state->length)); 875131380Stjr INITBITS(); 876205471Sdelphij state->mode = COPY_; 877205471Sdelphij if (flush == Z_TREES) goto inf_leave; 878205471Sdelphij case COPY_: 879131380Stjr state->mode = COPY; 880131380Stjr case COPY: 881131380Stjr copy = state->length; 882131380Stjr if (copy) { 883131380Stjr if (copy > have) copy = have; 884131380Stjr if (copy > left) copy = left; 885131380Stjr if (copy == 0) goto inf_leave; 886131380Stjr zmemcpy(put, next, copy); 887131380Stjr have -= copy; 888131380Stjr next += copy; 889131380Stjr left -= copy; 890131380Stjr put += copy; 891131380Stjr state->length -= copy; 892131380Stjr break; 893131380Stjr } 894131380Stjr Tracev((stderr, "inflate: stored end\n")); 895131380Stjr state->mode = TYPE; 896131380Stjr break; 897131380Stjr case TABLE: 898131380Stjr NEEDBITS(14); 899131380Stjr state->nlen = BITS(5) + 257; 900131380Stjr DROPBITS(5); 901131380Stjr state->ndist = BITS(5) + 1; 902131380Stjr DROPBITS(5); 903131380Stjr state->ncode = BITS(4) + 4; 904131380Stjr DROPBITS(4); 905131380Stjr#ifndef PKZIP_BUG_WORKAROUND 906131380Stjr if (state->nlen > 286 || state->ndist > 30) { 907131380Stjr strm->msg = (char *)"too many length or distance symbols"; 908131380Stjr state->mode = BAD; 909131380Stjr break; 910131380Stjr } 911131380Stjr#endif 912131380Stjr Tracev((stderr, "inflate: table sizes ok\n")); 913131380Stjr state->have = 0; 914131380Stjr state->mode = LENLENS; 915131380Stjr case LENLENS: 916131380Stjr while (state->have < state->ncode) { 917131380Stjr NEEDBITS(3); 918131380Stjr state->lens[order[state->have++]] = (unsigned short)BITS(3); 919131380Stjr DROPBITS(3); 920131380Stjr } 921131380Stjr while (state->have < 19) 922131380Stjr state->lens[order[state->have++]] = 0; 923131380Stjr state->next = state->codes; 924250261Sdelphij state->lencode = (const code FAR *)(state->next); 925131380Stjr state->lenbits = 7; 926131380Stjr ret = inflate_table(CODES, state->lens, 19, &(state->next), 927131380Stjr &(state->lenbits), state->work); 928131380Stjr if (ret) { 929131380Stjr strm->msg = (char *)"invalid code lengths set"; 930131380Stjr state->mode = BAD; 931131380Stjr break; 932131380Stjr } 933131380Stjr Tracev((stderr, "inflate: code lengths ok\n")); 934131380Stjr state->have = 0; 935131380Stjr state->mode = CODELENS; 936131380Stjr case CODELENS: 937131380Stjr while (state->have < state->nlen + state->ndist) { 938131380Stjr for (;;) { 939205471Sdelphij here = state->lencode[BITS(state->lenbits)]; 940205471Sdelphij if ((unsigned)(here.bits) <= bits) break; 941131380Stjr PULLBYTE(); 942131380Stjr } 943205471Sdelphij if (here.val < 16) { 944205471Sdelphij DROPBITS(here.bits); 945205471Sdelphij state->lens[state->have++] = here.val; 946131380Stjr } 947131380Stjr else { 948205471Sdelphij if (here.val == 16) { 949205471Sdelphij NEEDBITS(here.bits + 2); 950205471Sdelphij DROPBITS(here.bits); 951131380Stjr if (state->have == 0) { 952131380Stjr strm->msg = (char *)"invalid bit length repeat"; 953131380Stjr state->mode = BAD; 954131380Stjr break; 955131380Stjr } 956131380Stjr len = state->lens[state->have - 1]; 957131380Stjr copy = 3 + BITS(2); 958131380Stjr DROPBITS(2); 959131380Stjr } 960205471Sdelphij else if (here.val == 17) { 961205471Sdelphij NEEDBITS(here.bits + 3); 962205471Sdelphij DROPBITS(here.bits); 963131380Stjr len = 0; 964131380Stjr copy = 3 + BITS(3); 965131380Stjr DROPBITS(3); 966131380Stjr } 967131380Stjr else { 968205471Sdelphij NEEDBITS(here.bits + 7); 969205471Sdelphij DROPBITS(here.bits); 970131380Stjr len = 0; 971131380Stjr copy = 11 + BITS(7); 972131380Stjr DROPBITS(7); 973131380Stjr } 974131380Stjr if (state->have + copy > state->nlen + state->ndist) { 975131380Stjr strm->msg = (char *)"invalid bit length repeat"; 976131380Stjr state->mode = BAD; 977131380Stjr break; 978131380Stjr } 979131380Stjr while (copy--) 980131380Stjr state->lens[state->have++] = (unsigned short)len; 981131380Stjr } 982131380Stjr } 983131380Stjr 984146081Skientzle /* handle error breaks in while */ 985146081Skientzle if (state->mode == BAD) break; 986134354Snectar 987205471Sdelphij /* check for end-of-block code (better have one) */ 988205471Sdelphij if (state->lens[256] == 0) { 989205471Sdelphij strm->msg = (char *)"invalid code -- missing end-of-block"; 990205471Sdelphij state->mode = BAD; 991205471Sdelphij break; 992205471Sdelphij } 993205471Sdelphij 994205471Sdelphij /* build code tables -- note: do not change the lenbits or distbits 995205471Sdelphij values here (9 and 6) without reading the comments in inftrees.h 996205471Sdelphij concerning the ENOUGH constants, which depend on those values */ 997131380Stjr state->next = state->codes; 998250261Sdelphij state->lencode = (const code FAR *)(state->next); 999131380Stjr state->lenbits = 9; 1000131380Stjr ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 1001131380Stjr &(state->lenbits), state->work); 1002131380Stjr if (ret) { 1003131380Stjr strm->msg = (char *)"invalid literal/lengths set"; 1004131380Stjr state->mode = BAD; 1005131380Stjr break; 1006131380Stjr } 1007250261Sdelphij state->distcode = (const code FAR *)(state->next); 1008131380Stjr state->distbits = 6; 1009131380Stjr ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 1010131380Stjr &(state->next), &(state->distbits), state->work); 1011131380Stjr if (ret) { 1012131380Stjr strm->msg = (char *)"invalid distances set"; 1013131380Stjr state->mode = BAD; 1014131380Stjr break; 1015131380Stjr } 1016131380Stjr Tracev((stderr, "inflate: codes ok\n")); 1017205471Sdelphij state->mode = LEN_; 1018205471Sdelphij if (flush == Z_TREES) goto inf_leave; 1019205471Sdelphij case LEN_: 1020131380Stjr state->mode = LEN; 1021131380Stjr case LEN: 1022131380Stjr if (have >= 6 && left >= 258) { 1023131380Stjr RESTORE(); 1024131380Stjr inflate_fast(strm, out); 1025131380Stjr LOAD(); 1026205471Sdelphij if (state->mode == TYPE) 1027205471Sdelphij state->back = -1; 1028131380Stjr break; 1029131380Stjr } 1030205471Sdelphij state->back = 0; 1031131380Stjr for (;;) { 1032205471Sdelphij here = state->lencode[BITS(state->lenbits)]; 1033205471Sdelphij if ((unsigned)(here.bits) <= bits) break; 1034131380Stjr PULLBYTE(); 1035131380Stjr } 1036205471Sdelphij if (here.op && (here.op & 0xf0) == 0) { 1037205471Sdelphij last = here; 1038131380Stjr for (;;) { 1039205471Sdelphij here = state->lencode[last.val + 1040131380Stjr (BITS(last.bits + last.op) >> last.bits)]; 1041205471Sdelphij if ((unsigned)(last.bits + here.bits) <= bits) break; 1042131380Stjr PULLBYTE(); 1043131380Stjr } 1044131380Stjr DROPBITS(last.bits); 1045205471Sdelphij state->back += last.bits; 1046131380Stjr } 1047205471Sdelphij DROPBITS(here.bits); 1048205471Sdelphij state->back += here.bits; 1049205471Sdelphij state->length = (unsigned)here.val; 1050205471Sdelphij if ((int)(here.op) == 0) { 1051205471Sdelphij Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? 1052131380Stjr "inflate: literal '%c'\n" : 1053205471Sdelphij "inflate: literal 0x%02x\n", here.val)); 1054131380Stjr state->mode = LIT; 1055131380Stjr break; 1056131380Stjr } 1057205471Sdelphij if (here.op & 32) { 1058131380Stjr Tracevv((stderr, "inflate: end of block\n")); 1059205471Sdelphij state->back = -1; 1060131380Stjr state->mode = TYPE; 1061131380Stjr break; 1062131380Stjr } 1063205471Sdelphij if (here.op & 64) { 1064131380Stjr strm->msg = (char *)"invalid literal/length code"; 1065131380Stjr state->mode = BAD; 1066131380Stjr break; 1067131380Stjr } 1068205471Sdelphij state->extra = (unsigned)(here.op) & 15; 1069131380Stjr state->mode = LENEXT; 1070131380Stjr case LENEXT: 1071131380Stjr if (state->extra) { 1072131380Stjr NEEDBITS(state->extra); 1073131380Stjr state->length += BITS(state->extra); 1074131380Stjr DROPBITS(state->extra); 1075205471Sdelphij state->back += state->extra; 1076131380Stjr } 1077131380Stjr Tracevv((stderr, "inflate: length %u\n", state->length)); 1078205471Sdelphij state->was = state->length; 1079131380Stjr state->mode = DIST; 1080131380Stjr case DIST: 1081131380Stjr for (;;) { 1082205471Sdelphij here = state->distcode[BITS(state->distbits)]; 1083205471Sdelphij if ((unsigned)(here.bits) <= bits) break; 1084131380Stjr PULLBYTE(); 1085131380Stjr } 1086205471Sdelphij if ((here.op & 0xf0) == 0) { 1087205471Sdelphij last = here; 1088131380Stjr for (;;) { 1089205471Sdelphij here = state->distcode[last.val + 1090131380Stjr (BITS(last.bits + last.op) >> last.bits)]; 1091205471Sdelphij if ((unsigned)(last.bits + here.bits) <= bits) break; 1092131380Stjr PULLBYTE(); 1093131380Stjr } 1094131380Stjr DROPBITS(last.bits); 1095205471Sdelphij state->back += last.bits; 1096131380Stjr } 1097205471Sdelphij DROPBITS(here.bits); 1098205471Sdelphij state->back += here.bits; 1099205471Sdelphij if (here.op & 64) { 1100131380Stjr strm->msg = (char *)"invalid distance code"; 1101131380Stjr state->mode = BAD; 1102131380Stjr break; 1103131380Stjr } 1104205471Sdelphij state->offset = (unsigned)here.val; 1105205471Sdelphij state->extra = (unsigned)(here.op) & 15; 1106131380Stjr state->mode = DISTEXT; 1107131380Stjr case DISTEXT: 1108131380Stjr if (state->extra) { 1109131380Stjr NEEDBITS(state->extra); 1110131380Stjr state->offset += BITS(state->extra); 1111131380Stjr DROPBITS(state->extra); 1112205471Sdelphij state->back += state->extra; 1113131380Stjr } 1114157046Sdes#ifdef INFLATE_STRICT 1115157046Sdes if (state->offset > state->dmax) { 1116157046Sdes strm->msg = (char *)"invalid distance too far back"; 1117157046Sdes state->mode = BAD; 1118157046Sdes break; 1119157046Sdes } 1120157046Sdes#endif 1121131380Stjr Tracevv((stderr, "inflate: distance %u\n", state->offset)); 1122131380Stjr state->mode = MATCH; 1123131380Stjr case MATCH: 1124131380Stjr if (left == 0) goto inf_leave; 1125131380Stjr copy = out - left; 1126131380Stjr if (state->offset > copy) { /* copy from window */ 1127131380Stjr copy = state->offset - copy; 1128205471Sdelphij if (copy > state->whave) { 1129205471Sdelphij if (state->sane) { 1130205471Sdelphij strm->msg = (char *)"invalid distance too far back"; 1131205471Sdelphij state->mode = BAD; 1132205471Sdelphij break; 1133205471Sdelphij } 1134205471Sdelphij#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 1135205471Sdelphij Trace((stderr, "inflate.c too far\n")); 1136205471Sdelphij copy -= state->whave; 1137205471Sdelphij if (copy > state->length) copy = state->length; 1138205471Sdelphij if (copy > left) copy = left; 1139205471Sdelphij left -= copy; 1140205471Sdelphij state->length -= copy; 1141205471Sdelphij do { 1142205471Sdelphij *put++ = 0; 1143205471Sdelphij } while (--copy); 1144205471Sdelphij if (state->length == 0) state->mode = LEN; 1145205471Sdelphij break; 1146205471Sdelphij#endif 1147205471Sdelphij } 1148205471Sdelphij if (copy > state->wnext) { 1149205471Sdelphij copy -= state->wnext; 1150131380Stjr from = state->window + (state->wsize - copy); 1151131380Stjr } 1152131380Stjr else 1153205471Sdelphij from = state->window + (state->wnext - copy); 1154131380Stjr if (copy > state->length) copy = state->length; 1155131380Stjr } 1156131380Stjr else { /* copy from output */ 1157131380Stjr from = put - state->offset; 1158131380Stjr copy = state->length; 1159131380Stjr } 1160131380Stjr if (copy > left) copy = left; 1161131380Stjr left -= copy; 1162131380Stjr state->length -= copy; 1163131380Stjr do { 1164131380Stjr *put++ = *from++; 1165131380Stjr } while (--copy); 1166131380Stjr if (state->length == 0) state->mode = LEN; 1167131380Stjr break; 1168131380Stjr case LIT: 1169131380Stjr if (left == 0) goto inf_leave; 1170131380Stjr *put++ = (unsigned char)(state->length); 1171131380Stjr left--; 1172131380Stjr state->mode = LEN; 1173131380Stjr break; 1174131380Stjr case CHECK: 1175131380Stjr if (state->wrap) { 1176131380Stjr NEEDBITS(32); 1177131380Stjr out -= left; 1178131380Stjr strm->total_out += out; 1179131380Stjr state->total += out; 1180131380Stjr if (out) 1181131380Stjr strm->adler = state->check = 1182131380Stjr UPDATE(state->check, put - out, out); 1183131380Stjr out = left; 1184131380Stjr if (( 1185131380Stjr#ifdef GUNZIP 1186131380Stjr state->flags ? hold : 1187131380Stjr#endif 1188237410Sdelphij ZSWAP32(hold)) != state->check) { 1189131380Stjr strm->msg = (char *)"incorrect data check"; 1190131380Stjr state->mode = BAD; 1191131380Stjr break; 1192131380Stjr } 1193131380Stjr INITBITS(); 1194131380Stjr Tracev((stderr, "inflate: check matches trailer\n")); 1195131380Stjr } 1196131380Stjr#ifdef GUNZIP 1197131380Stjr state->mode = LENGTH; 1198131380Stjr case LENGTH: 1199131380Stjr if (state->wrap && state->flags) { 1200131380Stjr NEEDBITS(32); 1201131380Stjr if (hold != (state->total & 0xffffffffUL)) { 1202131380Stjr strm->msg = (char *)"incorrect length check"; 1203131380Stjr state->mode = BAD; 1204131380Stjr break; 1205131380Stjr } 1206131380Stjr INITBITS(); 1207131380Stjr Tracev((stderr, "inflate: length matches trailer\n")); 1208131380Stjr } 1209131380Stjr#endif 1210131380Stjr state->mode = DONE; 1211131380Stjr case DONE: 1212131380Stjr ret = Z_STREAM_END; 1213131380Stjr goto inf_leave; 1214131380Stjr case BAD: 1215131380Stjr ret = Z_DATA_ERROR; 1216131380Stjr goto inf_leave; 1217131380Stjr case MEM: 1218131380Stjr return Z_MEM_ERROR; 1219131380Stjr case SYNC: 1220131380Stjr default: 1221131380Stjr return Z_STREAM_ERROR; 1222131380Stjr } 1223131380Stjr 1224131380Stjr /* 1225131380Stjr Return from inflate(), updating the total counts and the check value. 1226131380Stjr If there was no progress during the inflate() call, return a buffer 1227131380Stjr error. Call updatewindow() to create and/or update the window state. 1228131380Stjr Note: a memory error from inflate() is non-recoverable. 1229131380Stjr */ 1230131380Stjr inf_leave: 1231131380Stjr RESTORE(); 1232237410Sdelphij if (state->wsize || (out != strm->avail_out && state->mode < BAD && 1233237410Sdelphij (state->mode < CHECK || flush != Z_FINISH))) 1234250261Sdelphij if (updatewindow(strm, strm->next_out, out - strm->avail_out)) { 1235131380Stjr state->mode = MEM; 1236131380Stjr return Z_MEM_ERROR; 1237131380Stjr } 1238131380Stjr in -= strm->avail_in; 1239131380Stjr out -= strm->avail_out; 1240131380Stjr strm->total_in += in; 1241131380Stjr strm->total_out += out; 1242131380Stjr state->total += out; 1243131380Stjr if (state->wrap && out) 1244131380Stjr strm->adler = state->check = 1245131380Stjr UPDATE(state->check, strm->next_out - out, out); 1246131380Stjr strm->data_type = state->bits + (state->last ? 64 : 0) + 1247205471Sdelphij (state->mode == TYPE ? 128 : 0) + 1248205471Sdelphij (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0); 1249131380Stjr if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1250131380Stjr ret = Z_BUF_ERROR; 1251131380Stjr return ret; 125217651Speter} 125317651Speter 1254131380Stjrint ZEXPORT inflateEnd(strm) 1255131380Stjrz_streamp strm; 1256131380Stjr{ 1257131380Stjr struct inflate_state FAR *state; 1258131380Stjr if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1259131380Stjr return Z_STREAM_ERROR; 1260131380Stjr state = (struct inflate_state FAR *)strm->state; 1261131380Stjr if (state->window != Z_NULL) ZFREE(strm, state->window); 1262131380Stjr ZFREE(strm, strm->state); 1263131380Stjr strm->state = Z_NULL; 1264131380Stjr Tracev((stderr, "inflate: end\n")); 1265131380Stjr return Z_OK; 1266131380Stjr} 126717651Speter 1268250261Sdelphijint ZEXPORT inflateGetDictionary(strm, dictionary, dictLength) 1269250261Sdelphijz_streamp strm; 1270250261SdelphijBytef *dictionary; 1271250261SdelphijuInt *dictLength; 1272250261Sdelphij{ 1273250261Sdelphij struct inflate_state FAR *state; 1274250261Sdelphij 1275250261Sdelphij /* check state */ 1276250261Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1277250261Sdelphij state = (struct inflate_state FAR *)strm->state; 1278250261Sdelphij 1279250261Sdelphij /* copy dictionary */ 1280250261Sdelphij if (state->whave && dictionary != Z_NULL) { 1281250261Sdelphij zmemcpy(dictionary, state->window + state->wnext, 1282250261Sdelphij state->whave - state->wnext); 1283250261Sdelphij zmemcpy(dictionary + state->whave - state->wnext, 1284250261Sdelphij state->window, state->wnext); 1285250261Sdelphij } 1286250261Sdelphij if (dictLength != Z_NULL) 1287250261Sdelphij *dictLength = state->whave; 1288250261Sdelphij return Z_OK; 1289250261Sdelphij} 1290250261Sdelphij 1291131380Stjrint ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1292131380Stjrz_streamp strm; 129317651Speterconst Bytef *dictionary; 1294131380StjruInt dictLength; 129517651Speter{ 1296131380Stjr struct inflate_state FAR *state; 1297237410Sdelphij unsigned long dictid; 1298237410Sdelphij int ret; 129917651Speter 1300131380Stjr /* check state */ 1301131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1302131380Stjr state = (struct inflate_state FAR *)strm->state; 1303157046Sdes if (state->wrap != 0 && state->mode != DICT) 1304157046Sdes return Z_STREAM_ERROR; 130517651Speter 1306237410Sdelphij /* check for correct dictionary identifier */ 1307157046Sdes if (state->mode == DICT) { 1308237410Sdelphij dictid = adler32(0L, Z_NULL, 0); 1309237410Sdelphij dictid = adler32(dictid, dictionary, dictLength); 1310237410Sdelphij if (dictid != state->check) 1311157046Sdes return Z_DATA_ERROR; 1312157046Sdes } 131317651Speter 1314237410Sdelphij /* copy dictionary to window using updatewindow(), which will amend the 1315237410Sdelphij existing dictionary if appropriate */ 1316250261Sdelphij ret = updatewindow(strm, dictionary + dictLength, dictLength); 1317237410Sdelphij if (ret) { 1318131380Stjr state->mode = MEM; 1319131380Stjr return Z_MEM_ERROR; 1320131380Stjr } 1321131380Stjr state->havedict = 1; 1322131380Stjr Tracev((stderr, "inflate: dictionary set\n")); 1323131380Stjr return Z_OK; 132417651Speter} 132517651Speter 1326157046Sdesint ZEXPORT inflateGetHeader(strm, head) 1327157046Sdesz_streamp strm; 1328157046Sdesgz_headerp head; 1329157046Sdes{ 1330157046Sdes struct inflate_state FAR *state; 1331157046Sdes 1332157046Sdes /* check state */ 1333157046Sdes if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1334157046Sdes state = (struct inflate_state FAR *)strm->state; 1335157046Sdes if ((state->wrap & 2) == 0) return Z_STREAM_ERROR; 1336157046Sdes 1337157046Sdes /* save header structure */ 1338157046Sdes state->head = head; 1339157046Sdes head->done = 0; 1340157046Sdes return Z_OK; 1341157046Sdes} 1342157046Sdes 1343131380Stjr/* 1344131380Stjr Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1345131380Stjr or when out of input. When called, *have is the number of pattern bytes 1346131380Stjr found in order so far, in 0..3. On return *have is updated to the new 1347131380Stjr state. If on return *have equals four, then the pattern was found and the 1348131380Stjr return value is how many bytes were read including the last byte of the 1349131380Stjr pattern. If *have is less than four, then the pattern has not been found 1350131380Stjr yet and the return value is len. In the latter case, syncsearch() can be 1351131380Stjr called again with more data and the *have state. *have is initialized to 1352131380Stjr zero for the first call. 1353131380Stjr */ 1354131380Stjrlocal unsigned syncsearch(have, buf, len) 1355131380Stjrunsigned FAR *have; 1356250261Sdelphijconst unsigned char FAR *buf; 1357131380Stjrunsigned len; 1358131380Stjr{ 1359131380Stjr unsigned got; 1360131380Stjr unsigned next; 136117651Speter 1362131380Stjr got = *have; 1363131380Stjr next = 0; 1364131380Stjr while (next < len && got < 4) { 1365131380Stjr if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1366131380Stjr got++; 1367131380Stjr else if (buf[next]) 1368131380Stjr got = 0; 1369131380Stjr else 1370131380Stjr got = 4 - got; 1371131380Stjr next++; 1372131380Stjr } 1373131380Stjr *have = got; 1374131380Stjr return next; 1375131380Stjr} 1376131380Stjr 1377131380Stjrint ZEXPORT inflateSync(strm) 1378131380Stjrz_streamp strm; 137917651Speter{ 1380131380Stjr unsigned len; /* number of bytes to look at or looked at */ 1381131380Stjr unsigned long in, out; /* temporary to save total_in and total_out */ 1382131380Stjr unsigned char buf[4]; /* to restore bit buffer to byte string */ 1383131380Stjr struct inflate_state FAR *state; 138417651Speter 1385131380Stjr /* check parameters */ 1386131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1387131380Stjr state = (struct inflate_state FAR *)strm->state; 1388131380Stjr if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 138917651Speter 1390131380Stjr /* if first time, start search in bit buffer */ 1391131380Stjr if (state->mode != SYNC) { 1392131380Stjr state->mode = SYNC; 1393131380Stjr state->hold <<= state->bits & 7; 1394131380Stjr state->bits -= state->bits & 7; 1395131380Stjr len = 0; 1396131380Stjr while (state->bits >= 8) { 1397131380Stjr buf[len++] = (unsigned char)(state->hold); 1398131380Stjr state->hold >>= 8; 1399131380Stjr state->bits -= 8; 1400131380Stjr } 1401131380Stjr state->have = 0; 1402131380Stjr syncsearch(&(state->have), buf, len); 1403131380Stjr } 140417651Speter 1405131380Stjr /* search available input */ 1406131380Stjr len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1407131380Stjr strm->avail_in -= len; 1408131380Stjr strm->next_in += len; 1409131380Stjr strm->total_in += len; 141017651Speter 1411131380Stjr /* return no joy or set up to restart inflate() on a new block */ 1412131380Stjr if (state->have != 4) return Z_DATA_ERROR; 1413131380Stjr in = strm->total_in; out = strm->total_out; 1414131380Stjr inflateReset(strm); 1415131380Stjr strm->total_in = in; strm->total_out = out; 1416131380Stjr state->mode = TYPE; 1417131380Stjr return Z_OK; 141817651Speter} 141933904Ssteve 1420131380Stjr/* 1421131380Stjr Returns true if inflate is currently at the end of a block generated by 1422131380Stjr Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1423131380Stjr implementation to provide an additional safety check. PPP uses 1424131380Stjr Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1425131380Stjr block. When decompressing, PPP checks that at the end of input packet, 1426131380Stjr inflate is waiting for these length bytes. 142733904Ssteve */ 1428131380Stjrint ZEXPORT inflateSyncPoint(strm) 1429131380Stjrz_streamp strm; 143033904Ssteve{ 1431131380Stjr struct inflate_state FAR *state; 1432131380Stjr 1433131380Stjr if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1434131380Stjr state = (struct inflate_state FAR *)strm->state; 1435131380Stjr return state->mode == STORED && state->bits == 0; 143633904Ssteve} 1437131380Stjr 1438131380Stjrint ZEXPORT inflateCopy(dest, source) 1439131380Stjrz_streamp dest; 1440131380Stjrz_streamp source; 1441131380Stjr{ 1442131380Stjr struct inflate_state FAR *state; 1443131380Stjr struct inflate_state FAR *copy; 1444131380Stjr unsigned char FAR *window; 1445157046Sdes unsigned wsize; 1446131380Stjr 1447131380Stjr /* check input */ 1448131380Stjr if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1449131380Stjr source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1450131380Stjr return Z_STREAM_ERROR; 1451131380Stjr state = (struct inflate_state FAR *)source->state; 1452131380Stjr 1453131380Stjr /* allocate space */ 1454131380Stjr copy = (struct inflate_state FAR *) 1455131380Stjr ZALLOC(source, 1, sizeof(struct inflate_state)); 1456131380Stjr if (copy == Z_NULL) return Z_MEM_ERROR; 1457131380Stjr window = Z_NULL; 1458131380Stjr if (state->window != Z_NULL) { 1459131380Stjr window = (unsigned char FAR *) 1460131380Stjr ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1461131380Stjr if (window == Z_NULL) { 1462131380Stjr ZFREE(source, copy); 1463131380Stjr return Z_MEM_ERROR; 1464131380Stjr } 1465131380Stjr } 1466131380Stjr 1467131380Stjr /* copy state */ 1468237410Sdelphij zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 1469237410Sdelphij zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state)); 1470157046Sdes if (state->lencode >= state->codes && 1471157046Sdes state->lencode <= state->codes + ENOUGH - 1) { 1472157046Sdes copy->lencode = copy->codes + (state->lencode - state->codes); 1473157046Sdes copy->distcode = copy->codes + (state->distcode - state->codes); 1474157046Sdes } 1475131380Stjr copy->next = copy->codes + (state->next - state->codes); 1476157046Sdes if (window != Z_NULL) { 1477157046Sdes wsize = 1U << state->wbits; 1478157046Sdes zmemcpy(window, state->window, wsize); 1479157046Sdes } 1480131380Stjr copy->window = window; 1481157046Sdes dest->state = (struct internal_state FAR *)copy; 1482131380Stjr return Z_OK; 1483131380Stjr} 1484205471Sdelphij 1485205471Sdelphijint ZEXPORT inflateUndermine(strm, subvert) 1486205471Sdelphijz_streamp strm; 1487205471Sdelphijint subvert; 1488205471Sdelphij{ 1489205471Sdelphij struct inflate_state FAR *state; 1490205471Sdelphij 1491205471Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1492205471Sdelphij state = (struct inflate_state FAR *)strm->state; 1493205471Sdelphij state->sane = !subvert; 1494205471Sdelphij#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 1495205471Sdelphij return Z_OK; 1496205471Sdelphij#else 1497205471Sdelphij state->sane = 1; 1498205471Sdelphij return Z_DATA_ERROR; 1499205471Sdelphij#endif 1500205471Sdelphij} 1501205471Sdelphij 1502205471Sdelphijlong ZEXPORT inflateMark(strm) 1503205471Sdelphijz_streamp strm; 1504205471Sdelphij{ 1505205471Sdelphij struct inflate_state FAR *state; 1506205471Sdelphij 1507205471Sdelphij if (strm == Z_NULL || strm->state == Z_NULL) return -1L << 16; 1508205471Sdelphij state = (struct inflate_state FAR *)strm->state; 1509205471Sdelphij return ((long)(state->back) << 16) + 1510205471Sdelphij (state->mode == COPY ? state->length : 1511205471Sdelphij (state->mode == MATCH ? state->was - state->length : 0)); 1512205471Sdelphij} 1513