1 /* $NetBSD: zlib.c,v 1.3 2020/05/04 00:18:34 agc Exp $ */ 2 3 /* inflate.c -- zlib decompression 4 * Copyright (C) 1995-2005 Mark Adler 5 * For conditions of distribution and use, see copyright notice in zlib.h 6 */ 7 8 /* 9 * Change history: 10 * 11 * 1.2.beta0 24 Nov 2002 12 * - First version -- complete rewrite of inflate to simplify code, avoid 13 * creation of window when not needed, minimize use of window when it is 14 * needed, make inffast.c even faster, implement gzip decoding, and to 15 * improve code readability and style over the previous zlib inflate code 16 * 17 * 1.2.beta1 25 Nov 2002 18 * - Use pointers for available input and output checking in inffast.c 19 * - Remove input and output counters in inffast.c 20 * - Change inffast.c entry and loop from avail_in >= 7 to >= 6 21 * - Remove unnecessary second byte pull from length extra in inffast.c 22 * - Unroll direct copy to three copies per loop in inffast.c 23 * 24 * 1.2.beta2 4 Dec 2002 25 * - Change external routine names to reduce potential conflicts 26 * - Correct filename to inffixed.h for fixed tables in inflate.c 27 * - Make hbuf[] unsigned char to match parameter type in inflate.c 28 * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 29 * to avoid negation problem on Alphas (64 bit) in inflate.c 30 * 31 * 1.2.beta3 22 Dec 2002 32 * - Add comments on state->bits assertion in inffast.c 33 * - Add comments on op field in inftrees.h 34 * - Fix bug in reuse of allocated window after inflateReset() 35 * - Remove bit fields--back to byte structure for speed 36 * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 37 * - Change post-increments to pre-increments in netpgpv_inflate_fast(), PPC biased? 38 * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 39 * - Make MATCH copy in inflate() much faster for when netpgpv_inflate_fast() not used 40 * - Use local copies of stream next and avail values, as well as local bit 41 * buffer and bit count in inflate()--for speed when netpgpv_inflate_fast() not used 42 * 43 * 1.2.beta4 1 Jan 2003 44 * - Split ptr - 257 statements in netpgpv_inflate_table() to avoid compiler warnings 45 * - Move a comment on output buffer sizes from inffast.c to inflate.c 46 * - Add comments in inffast.c to introduce the netpgpv_inflate_fast() routine 47 * - Rearrange window copies in netpgpv_inflate_fast() for speed and simplification 48 * - Unroll last copy for window match in netpgpv_inflate_fast() 49 * - Use local copies of window variables in netpgpv_inflate_fast() for speed 50 * - Pull out common write == 0 case for speed in netpgpv_inflate_fast() 51 * - Make op and len in netpgpv_inflate_fast() unsigned for consistency 52 * - Add FAR to lcode and dcode declarations in netpgpv_inflate_fast() 53 * - Simplified bad distance check in netpgpv_inflate_fast() 54 * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 55 * source file infback.c to provide a call-back interface to inflate for 56 * programs like gzip and unzip -- uses window as output buffer to avoid 57 * window copying 58 * 59 * 1.2.beta5 1 Jan 2003 60 * - Improved inflateBack() interface to allow the caller to provide initial 61 * input in strm. 62 * - Fixed stored blocks bug in inflateBack() 63 * 64 * 1.2.beta6 4 Jan 2003 65 * - Added comments in inffast.c on effectiveness of POSTINC 66 * - Typecasting all around to reduce compiler warnings 67 * - Changed loops from while (1) or do {} while (1) to for (;;), again to 68 * make compilers happy 69 * - Changed type of window in inflateBackInit() to unsigned char * 70 * 71 * 1.2.beta7 27 Jan 2003 72 * - Changed many types to unsigned or unsigned short to avoid warnings 73 * - Added inflateCopy() function 74 * 75 * 1.2.0 9 Mar 2003 76 * - Changed inflateBack() interface to provide separate opaque descriptors 77 * for the in() and out() functions 78 * - Changed inflateBack() argument and in_func typedef to swap the length 79 * and buffer address return values for the input function 80 * - Check next_in and next_out for Z_NULL on entry to inflate() 81 * 82 * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 83 */ 84 #include "config.h" 85 86 #include <stdio.h> 87 #include <stdlib.h> 88 #include <string.h> 89 90 #include "zlib.h" 91 92 #ifdef MAKEFIXED 93 # ifndef BUILDFIXED 94 # define BUILDFIXED 95 # endif 96 #endif 97 98 #ifndef local 99 #define local static 100 #endif 101 102 #define ZALLOC(strm, items, size) \ 103 (*((strm)->zalloc))((strm)->opaque, (items), (size)) 104 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) 105 #define Tracev(x) 106 #define Tracevv(x) 107 108 /* Possible inflate modes between inflate() calls */ 109 typedef enum { 110 HEAD, /* i: waiting for magic header */ 111 FLAGS, /* i: waiting for method and flags (gzip) */ 112 TIME, /* i: waiting for modification time (gzip) */ 113 OS, /* i: waiting for extra flags and operating system (gzip) */ 114 EXLEN, /* i: waiting for extra length (gzip) */ 115 EXTRA, /* i: waiting for extra bytes (gzip) */ 116 NAME, /* i: waiting for end of file name (gzip) */ 117 COMMENT, /* i: waiting for end of comment (gzip) */ 118 HCRC, /* i: waiting for header crc (gzip) */ 119 DICTID, /* i: waiting for dictionary check value */ 120 DICT, /* waiting for inflateSetDictionary() call */ 121 TYPE, /* i: waiting for type bits, including last-flag bit */ 122 TYPEDO, /* i: same, but skip check to exit inflate on new block */ 123 STORED, /* i: waiting for stored size (length and complement) */ 124 COPY, /* i/o: waiting for input or output to copy stored block */ 125 TABLE, /* i: waiting for dynamic block table lengths */ 126 LENLENS, /* i: waiting for code length code lengths */ 127 CODELENS, /* i: waiting for length/lit and distance code lengths */ 128 LEN, /* i: waiting for length/lit code */ 129 LENEXT, /* i: waiting for length extra bits */ 130 DIST, /* i: waiting for distance code */ 131 DISTEXT, /* i: waiting for distance extra bits */ 132 MATCH, /* o: waiting for output space to copy string */ 133 LIT, /* o: waiting for output space to write literal */ 134 CHECK, /* i: waiting for 32-bit check value */ 135 LENGTH, /* i: waiting for 32-bit length (gzip) */ 136 DONE, /* finished check, done -- remain here until reset */ 137 BAD, /* got a data error -- remain here until reset */ 138 MEM, /* got an inflate() memory error -- remain here until reset */ 139 SYNC /* looking for synchronization bytes to restart inflate() */ 140 } inflate_mode; 141 142 /* Structure for decoding tables. Each entry provides either the 143 information needed to do the operation requested by the code that 144 indexed that table entry, or it provides a pointer to another 145 table that indexes more bits of the code. op indicates whether 146 the entry is a pointer to another table, a literal, a length or 147 distance, an end-of-block, or an invalid code. For a table 148 pointer, the low four bits of op is the number of index bits of 149 that table. For a length or distance, the low four bits of op 150 is the number of extra bits to get after the code. bits is 151 the number of bits in this code or part of the code to drop off 152 of the bit buffer. val is the actual byte to output in the case 153 of a literal, the base length or distance, or the offset from 154 the current table to the next table. Each entry is four bytes. */ 155 typedef struct { 156 unsigned char op; /* operation, extra bits, table bits */ 157 unsigned char bits; /* bits in this part of the code */ 158 unsigned short val; /* offset in table or code value */ 159 } code; 160 161 #define ENOUGH 2048 162 163 /* Type of code to build for inftable() */ 164 typedef enum { 165 CODES, 166 LENS, 167 DISTS 168 } codetype; 169 170 #ifndef DEF_WBITS 171 # define DEF_WBITS MAX_WBITS 172 #endif 173 174 #define zmemcpy memcpy 175 176 /* 177 State transitions between above modes - 178 179 (most modes can go to the BAD or MEM mode -- not shown for clarity) 180 181 Process header: 182 HEAD -> (gzip) or (zlib) 183 (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME 184 NAME -> COMMENT -> HCRC -> TYPE 185 (zlib) -> DICTID or TYPE 186 DICTID -> DICT -> TYPE 187 Read deflate blocks: 188 TYPE -> STORED or TABLE or LEN or CHECK 189 STORED -> COPY -> TYPE 190 TABLE -> LENLENS -> CODELENS -> LEN 191 Read deflate codes: 192 LEN -> LENEXT or LIT or TYPE 193 LENEXT -> DIST -> DISTEXT -> MATCH -> LEN 194 LIT -> LEN 195 Process trailer: 196 CHECK -> LENGTH -> DONE 197 */ 198 199 /* state maintained between inflate() calls. Approximately 7K bytes. */ 200 struct inflate_state { 201 inflate_mode mode; /* current inflate mode */ 202 int last; /* true if processing last block */ 203 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */ 204 int havedict; /* true if dictionary provided */ 205 int flags; /* gzip header method and flags (0 if zlib) */ 206 unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */ 207 unsigned long check; /* protected copy of check value */ 208 unsigned long total; /* protected copy of output count */ 209 gz_headerp head; /* where to save gzip header information */ 210 /* sliding window */ 211 unsigned wbits; /* log base 2 of requested window size */ 212 unsigned wsize; /* window size or zero if not using window */ 213 unsigned whave; /* valid bytes in the window */ 214 unsigned write; /* window write index */ 215 unsigned char FAR *window; /* allocated sliding window, if needed */ 216 /* bit accumulator */ 217 unsigned long hold; /* input bit accumulator */ 218 unsigned bits; /* number of bits in "in" */ 219 /* for string and stored block copying */ 220 unsigned length; /* literal or length of data to copy */ 221 unsigned offset; /* distance back to copy string from */ 222 /* for table and code decoding */ 223 unsigned extra; /* extra bits needed */ 224 /* fixed and dynamic code tables */ 225 code const FAR *lencode; /* starting table for length/literal codes */ 226 code const FAR *distcode; /* starting table for distance codes */ 227 unsigned lenbits; /* index bits for lencode */ 228 unsigned distbits; /* index bits for distcode */ 229 /* dynamic table building */ 230 unsigned ncode; /* number of code length code lengths */ 231 unsigned nlen; /* number of length code lengths */ 232 unsigned ndist; /* number of distance code lengths */ 233 unsigned have; /* number of code lengths in lens[] */ 234 code FAR *next; /* next available space in codes[] */ 235 unsigned short lens[320]; /* temporary storage for code lengths */ 236 unsigned short work[288]; /* work area for code table building */ 237 code codes[ENOUGH]; /* space for code tables */ 238 }; 239 240 voidpf netpgpv_zcalloc(voidpf /*opaque*/, unsigned /*items*/, unsigned /*size*/); 241 void netpgpv_zcfree (voidpf /*opaque*/, voidpf /*ptr*/); 242 int netpgpv_inflate_table(codetype /*type*/, unsigned short FAR */*lens*/, unsigned /*codes*/, 243 code FAR * FAR */*table*/, unsigned FAR */*bits*/, unsigned short FAR */*work*/); 244 void netpgpv_inflate_fast(z_streamp /*strm*/, unsigned /*start*/); 245 246 voidpf 247 netpgpv_zcalloc (voidpf opaque, unsigned items, unsigned size) 248 { 249 if (opaque) items += size - size; /* make compiler happy */ 250 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) : 251 (voidpf)calloc(items, size); 252 } 253 254 void 255 netpgpv_zcfree (voidpf opaque, voidpf ptr) 256 { 257 free(ptr); 258 if (opaque) return; /* make compiler happy */ 259 } 260 261 /* function prototypes */ 262 local void fixedtables OF((struct inflate_state FAR *state)); 263 local int updatewindow OF((z_streamp strm, unsigned out)); 264 #ifdef BUILDFIXED 265 void makefixed OF((void)); 266 #endif 267 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf, 268 unsigned len)); 269 270 int ZEXPORT inflateReset(z_streamp strm) 271 { 272 struct inflate_state FAR *state; 273 274 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 275 state = (struct inflate_state FAR *)(void *)strm->state; 276 strm->total_in = strm->total_out = state->total = 0; 277 strm->msg = Z_NULL; 278 strm->adler = 1; /* to support ill-conceived Java test suite */ 279 state->mode = HEAD; 280 state->last = 0; 281 state->havedict = 0; 282 state->dmax = 32768U; 283 state->head = Z_NULL; 284 state->wsize = 0; 285 state->whave = 0; 286 state->write = 0; 287 state->hold = 0; 288 state->bits = 0; 289 state->lencode = state->distcode = state->next = state->codes; 290 Tracev((stderr, "inflate: reset\n")); 291 return Z_OK; 292 } 293 294 int ZEXPORT netpgpv_inflatePrime(z_streamp strm, int bits, int value) 295 { 296 struct inflate_state FAR *state; 297 298 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 299 state = (struct inflate_state FAR *)(void *)strm->state; 300 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR; 301 value &= (1L << bits) - 1; 302 state->hold += value << state->bits; 303 state->bits += bits; 304 return Z_OK; 305 } 306 307 int ZEXPORT inflateInit2_(z_streamp strm, int windowBits, const char *version, int stream_size) 308 { 309 struct inflate_state FAR *state; 310 311 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 312 stream_size != (int)(sizeof(z_stream))) 313 return Z_VERSION_ERROR; 314 if (strm == Z_NULL) return Z_STREAM_ERROR; 315 strm->msg = Z_NULL; /* in case we return an error */ 316 if (strm->zalloc == (alloc_func)0) { 317 strm->zalloc = netpgpv_zcalloc; 318 strm->opaque = (voidpf)0; 319 } 320 if (strm->zfree == (free_func)0) strm->zfree = netpgpv_zcfree; 321 state = (struct inflate_state FAR *) 322 ZALLOC(strm, 1, sizeof(struct inflate_state)); 323 if (state == Z_NULL) return Z_MEM_ERROR; 324 Tracev((stderr, "inflate: allocated\n")); 325 strm->state = (struct internal_state FAR *)(void *)state; 326 if (windowBits < 0) { 327 state->wrap = 0; 328 windowBits = -windowBits; 329 } 330 else { 331 state->wrap = (windowBits >> 4) + 1; 332 #ifdef GUNZIP 333 if (windowBits < 48) windowBits &= 15; 334 #endif 335 } 336 if (windowBits < 8 || windowBits > 15) { 337 ZFREE(strm, state); 338 strm->state = Z_NULL; 339 return Z_STREAM_ERROR; 340 } 341 state->wbits = (unsigned)windowBits; 342 state->window = Z_NULL; 343 return inflateReset(strm); 344 } 345 346 int ZEXPORT inflateInit_( z_streamp strm, const char *version, int stream_size) 347 { 348 return inflateInit2_(strm, DEF_WBITS, version, stream_size); 349 } 350 351 /* 352 Return state with length and distance decoding tables and index sizes set to 353 fixed code decoding. Normally this returns fixed tables from inffixed.h. 354 If BUILDFIXED is defined, then instead this routine builds the tables the 355 first time it's called, and returns those tables the first time and 356 thereafter. This reduces the size of the code by about 2K bytes, in 357 exchange for a little execution time. However, BUILDFIXED should not be 358 used for threaded applications, since the rewriting of the tables and virgin 359 may not be thread-safe. 360 */ 361 local void 362 fixedtables(struct inflate_state FAR *state) 363 { 364 /* $NetBSD: zlib.c,v 1.3 2020/05/04 00:18:34 agc Exp $ */ 365 366 /* inffixed.h -- table for decoding fixed codes 367 * Generated automatically by makefixed(). 368 */ 369 370 /* WARNING: this file should *not* be used by applications. It 371 is part of the implementation of the compression library and 372 is subject to change. Applications should only use zlib.h. 373 */ 374 375 static const code lenfix[512] = { 376 {96,7,0},{0,8,80},{0,8,16},{20,8,115},{18,7,31},{0,8,112},{0,8,48}, 377 {0,9,192},{16,7,10},{0,8,96},{0,8,32},{0,9,160},{0,8,0},{0,8,128}, 378 {0,8,64},{0,9,224},{16,7,6},{0,8,88},{0,8,24},{0,9,144},{19,7,59}, 379 {0,8,120},{0,8,56},{0,9,208},{17,7,17},{0,8,104},{0,8,40},{0,9,176}, 380 {0,8,8},{0,8,136},{0,8,72},{0,9,240},{16,7,4},{0,8,84},{0,8,20}, 381 {21,8,227},{19,7,43},{0,8,116},{0,8,52},{0,9,200},{17,7,13},{0,8,100}, 382 {0,8,36},{0,9,168},{0,8,4},{0,8,132},{0,8,68},{0,9,232},{16,7,8}, 383 {0,8,92},{0,8,28},{0,9,152},{20,7,83},{0,8,124},{0,8,60},{0,9,216}, 384 {18,7,23},{0,8,108},{0,8,44},{0,9,184},{0,8,12},{0,8,140},{0,8,76}, 385 {0,9,248},{16,7,3},{0,8,82},{0,8,18},{21,8,163},{19,7,35},{0,8,114}, 386 {0,8,50},{0,9,196},{17,7,11},{0,8,98},{0,8,34},{0,9,164},{0,8,2}, 387 {0,8,130},{0,8,66},{0,9,228},{16,7,7},{0,8,90},{0,8,26},{0,9,148}, 388 {20,7,67},{0,8,122},{0,8,58},{0,9,212},{18,7,19},{0,8,106},{0,8,42}, 389 {0,9,180},{0,8,10},{0,8,138},{0,8,74},{0,9,244},{16,7,5},{0,8,86}, 390 {0,8,22},{64,8,0},{19,7,51},{0,8,118},{0,8,54},{0,9,204},{17,7,15}, 391 {0,8,102},{0,8,38},{0,9,172},{0,8,6},{0,8,134},{0,8,70},{0,9,236}, 392 {16,7,9},{0,8,94},{0,8,30},{0,9,156},{20,7,99},{0,8,126},{0,8,62}, 393 {0,9,220},{18,7,27},{0,8,110},{0,8,46},{0,9,188},{0,8,14},{0,8,142}, 394 {0,8,78},{0,9,252},{96,7,0},{0,8,81},{0,8,17},{21,8,131},{18,7,31}, 395 {0,8,113},{0,8,49},{0,9,194},{16,7,10},{0,8,97},{0,8,33},{0,9,162}, 396 {0,8,1},{0,8,129},{0,8,65},{0,9,226},{16,7,6},{0,8,89},{0,8,25}, 397 {0,9,146},{19,7,59},{0,8,121},{0,8,57},{0,9,210},{17,7,17},{0,8,105}, 398 {0,8,41},{0,9,178},{0,8,9},{0,8,137},{0,8,73},{0,9,242},{16,7,4}, 399 {0,8,85},{0,8,21},{16,8,258},{19,7,43},{0,8,117},{0,8,53},{0,9,202}, 400 {17,7,13},{0,8,101},{0,8,37},{0,9,170},{0,8,5},{0,8,133},{0,8,69}, 401 {0,9,234},{16,7,8},{0,8,93},{0,8,29},{0,9,154},{20,7,83},{0,8,125}, 402 {0,8,61},{0,9,218},{18,7,23},{0,8,109},{0,8,45},{0,9,186},{0,8,13}, 403 {0,8,141},{0,8,77},{0,9,250},{16,7,3},{0,8,83},{0,8,19},{21,8,195}, 404 {19,7,35},{0,8,115},{0,8,51},{0,9,198},{17,7,11},{0,8,99},{0,8,35}, 405 {0,9,166},{0,8,3},{0,8,131},{0,8,67},{0,9,230},{16,7,7},{0,8,91}, 406 {0,8,27},{0,9,150},{20,7,67},{0,8,123},{0,8,59},{0,9,214},{18,7,19}, 407 {0,8,107},{0,8,43},{0,9,182},{0,8,11},{0,8,139},{0,8,75},{0,9,246}, 408 {16,7,5},{0,8,87},{0,8,23},{64,8,0},{19,7,51},{0,8,119},{0,8,55}, 409 {0,9,206},{17,7,15},{0,8,103},{0,8,39},{0,9,174},{0,8,7},{0,8,135}, 410 {0,8,71},{0,9,238},{16,7,9},{0,8,95},{0,8,31},{0,9,158},{20,7,99}, 411 {0,8,127},{0,8,63},{0,9,222},{18,7,27},{0,8,111},{0,8,47},{0,9,190}, 412 {0,8,15},{0,8,143},{0,8,79},{0,9,254},{96,7,0},{0,8,80},{0,8,16}, 413 {20,8,115},{18,7,31},{0,8,112},{0,8,48},{0,9,193},{16,7,10},{0,8,96}, 414 {0,8,32},{0,9,161},{0,8,0},{0,8,128},{0,8,64},{0,9,225},{16,7,6}, 415 {0,8,88},{0,8,24},{0,9,145},{19,7,59},{0,8,120},{0,8,56},{0,9,209}, 416 {17,7,17},{0,8,104},{0,8,40},{0,9,177},{0,8,8},{0,8,136},{0,8,72}, 417 {0,9,241},{16,7,4},{0,8,84},{0,8,20},{21,8,227},{19,7,43},{0,8,116}, 418 {0,8,52},{0,9,201},{17,7,13},{0,8,100},{0,8,36},{0,9,169},{0,8,4}, 419 {0,8,132},{0,8,68},{0,9,233},{16,7,8},{0,8,92},{0,8,28},{0,9,153}, 420 {20,7,83},{0,8,124},{0,8,60},{0,9,217},{18,7,23},{0,8,108},{0,8,44}, 421 {0,9,185},{0,8,12},{0,8,140},{0,8,76},{0,9,249},{16,7,3},{0,8,82}, 422 {0,8,18},{21,8,163},{19,7,35},{0,8,114},{0,8,50},{0,9,197},{17,7,11}, 423 {0,8,98},{0,8,34},{0,9,165},{0,8,2},{0,8,130},{0,8,66},{0,9,229}, 424 {16,7,7},{0,8,90},{0,8,26},{0,9,149},{20,7,67},{0,8,122},{0,8,58}, 425 {0,9,213},{18,7,19},{0,8,106},{0,8,42},{0,9,181},{0,8,10},{0,8,138}, 426 {0,8,74},{0,9,245},{16,7,5},{0,8,86},{0,8,22},{64,8,0},{19,7,51}, 427 {0,8,118},{0,8,54},{0,9,205},{17,7,15},{0,8,102},{0,8,38},{0,9,173}, 428 {0,8,6},{0,8,134},{0,8,70},{0,9,237},{16,7,9},{0,8,94},{0,8,30}, 429 {0,9,157},{20,7,99},{0,8,126},{0,8,62},{0,9,221},{18,7,27},{0,8,110}, 430 {0,8,46},{0,9,189},{0,8,14},{0,8,142},{0,8,78},{0,9,253},{96,7,0}, 431 {0,8,81},{0,8,17},{21,8,131},{18,7,31},{0,8,113},{0,8,49},{0,9,195}, 432 {16,7,10},{0,8,97},{0,8,33},{0,9,163},{0,8,1},{0,8,129},{0,8,65}, 433 {0,9,227},{16,7,6},{0,8,89},{0,8,25},{0,9,147},{19,7,59},{0,8,121}, 434 {0,8,57},{0,9,211},{17,7,17},{0,8,105},{0,8,41},{0,9,179},{0,8,9}, 435 {0,8,137},{0,8,73},{0,9,243},{16,7,4},{0,8,85},{0,8,21},{16,8,258}, 436 {19,7,43},{0,8,117},{0,8,53},{0,9,203},{17,7,13},{0,8,101},{0,8,37}, 437 {0,9,171},{0,8,5},{0,8,133},{0,8,69},{0,9,235},{16,7,8},{0,8,93}, 438 {0,8,29},{0,9,155},{20,7,83},{0,8,125},{0,8,61},{0,9,219},{18,7,23}, 439 {0,8,109},{0,8,45},{0,9,187},{0,8,13},{0,8,141},{0,8,77},{0,9,251}, 440 {16,7,3},{0,8,83},{0,8,19},{21,8,195},{19,7,35},{0,8,115},{0,8,51}, 441 {0,9,199},{17,7,11},{0,8,99},{0,8,35},{0,9,167},{0,8,3},{0,8,131}, 442 {0,8,67},{0,9,231},{16,7,7},{0,8,91},{0,8,27},{0,9,151},{20,7,67}, 443 {0,8,123},{0,8,59},{0,9,215},{18,7,19},{0,8,107},{0,8,43},{0,9,183}, 444 {0,8,11},{0,8,139},{0,8,75},{0,9,247},{16,7,5},{0,8,87},{0,8,23}, 445 {64,8,0},{19,7,51},{0,8,119},{0,8,55},{0,9,207},{17,7,15},{0,8,103}, 446 {0,8,39},{0,9,175},{0,8,7},{0,8,135},{0,8,71},{0,9,239},{16,7,9}, 447 {0,8,95},{0,8,31},{0,9,159},{20,7,99},{0,8,127},{0,8,63},{0,9,223}, 448 {18,7,27},{0,8,111},{0,8,47},{0,9,191},{0,8,15},{0,8,143},{0,8,79}, 449 {0,9,255} 450 }; 451 452 static const code distfix[32] = { 453 {16,5,1},{23,5,257},{19,5,17},{27,5,4097},{17,5,5},{25,5,1025}, 454 {21,5,65},{29,5,16385},{16,5,3},{24,5,513},{20,5,33},{28,5,8193}, 455 {18,5,9},{26,5,2049},{22,5,129},{64,5,0},{16,5,2},{23,5,385}, 456 {19,5,25},{27,5,6145},{17,5,7},{25,5,1537},{21,5,97},{29,5,24577}, 457 {16,5,4},{24,5,769},{20,5,49},{28,5,12289},{18,5,13},{26,5,3073}, 458 {22,5,193},{64,5,0} 459 }; 460 state->lencode = lenfix; 461 state->lenbits = 9; 462 state->distcode = distfix; 463 state->distbits = 5; 464 } 465 466 /* 467 Update the window with the last wsize (normally 32K) bytes written before 468 returning. If window does not exist yet, create it. This is only called 469 when a window is already in use, or when output has been written during this 470 inflate call, but the end of the deflate stream has not been reached yet. 471 It is also called to create a window for dictionary data when a dictionary 472 is loaded. 473 474 Providing output buffers larger than 32K to inflate() should provide a speed 475 advantage, since only the last 32K of output is copied to the sliding window 476 upon return from inflate(), and since all distances after the first 32K of 477 output will fall in the output data, making match copies simpler and faster. 478 The advantage may be dependent on the size of the processor's data caches. 479 */ 480 local int 481 updatewindow(z_streamp strm, unsigned out) 482 { 483 struct inflate_state FAR *state; 484 unsigned copy, dist; 485 486 state = (struct inflate_state FAR *)(void *)strm->state; 487 488 /* if it hasn't been done already, allocate space for the window */ 489 if (state->window == Z_NULL) { 490 state->window = (unsigned char FAR *) 491 ZALLOC(strm, 1U << state->wbits, 492 sizeof(unsigned char)); 493 if (state->window == Z_NULL) return 1; 494 } 495 496 /* if window not in use yet, initialize */ 497 if (state->wsize == 0) { 498 state->wsize = 1U << state->wbits; 499 state->write = 0; 500 state->whave = 0; 501 } 502 503 /* copy state->wsize or less output bytes into the circular window */ 504 copy = out - strm->avail_out; 505 if (copy >= state->wsize) { 506 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize); 507 state->write = 0; 508 state->whave = state->wsize; 509 } 510 else { 511 dist = state->wsize - state->write; 512 if (dist > copy) dist = copy; 513 zmemcpy(state->window + state->write, strm->next_out - copy, dist); 514 copy -= dist; 515 if (copy) { 516 zmemcpy(state->window, strm->next_out - copy, copy); 517 state->write = copy; 518 state->whave = state->wsize; 519 } 520 else { 521 state->write += dist; 522 if (state->write == state->wsize) state->write = 0; 523 if (state->whave < state->wsize) state->whave += dist; 524 } 525 } 526 return 0; 527 } 528 529 #define BASE 65521UL /* largest prime smaller than 65536 */ 530 #define NMAX 5552 531 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 532 533 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} 534 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 535 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 536 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 537 #define DO16(buf) DO8(buf,0); DO8(buf,8); 538 539 /* use NO_DIVIDE if your processor does not do division in hardware */ 540 #ifdef NO_DIVIDE 541 # define MOD(a) \ 542 do { \ 543 if (a >= (BASE << 16)) a -= (BASE << 16); \ 544 if (a >= (BASE << 15)) a -= (BASE << 15); \ 545 if (a >= (BASE << 14)) a -= (BASE << 14); \ 546 if (a >= (BASE << 13)) a -= (BASE << 13); \ 547 if (a >= (BASE << 12)) a -= (BASE << 12); \ 548 if (a >= (BASE << 11)) a -= (BASE << 11); \ 549 if (a >= (BASE << 10)) a -= (BASE << 10); \ 550 if (a >= (BASE << 9)) a -= (BASE << 9); \ 551 if (a >= (BASE << 8)) a -= (BASE << 8); \ 552 if (a >= (BASE << 7)) a -= (BASE << 7); \ 553 if (a >= (BASE << 6)) a -= (BASE << 6); \ 554 if (a >= (BASE << 5)) a -= (BASE << 5); \ 555 if (a >= (BASE << 4)) a -= (BASE << 4); \ 556 if (a >= (BASE << 3)) a -= (BASE << 3); \ 557 if (a >= (BASE << 2)) a -= (BASE << 2); \ 558 if (a >= (BASE << 1)) a -= (BASE << 1); \ 559 if (a >= BASE) a -= BASE; \ 560 } while (0) 561 # define MOD4(a) \ 562 do { \ 563 if (a >= (BASE << 4)) a -= (BASE << 4); \ 564 if (a >= (BASE << 3)) a -= (BASE << 3); \ 565 if (a >= (BASE << 2)) a -= (BASE << 2); \ 566 if (a >= (BASE << 1)) a -= (BASE << 1); \ 567 if (a >= BASE) a -= BASE; \ 568 } while (0) 569 #else 570 # define MOD(a) a %= BASE 571 # define MOD4(a) a %= BASE 572 #endif 573 574 /* ========================================================================= */ 575 uLong ZEXPORT 576 adler32(uLong adler, const Bytef *buf, uInt len) 577 { 578 unsigned long sum2; 579 unsigned n; 580 581 /* split Adler-32 into component sums */ 582 sum2 = (adler >> 16) & 0xffff; 583 adler &= 0xffff; 584 585 /* in case user likes doing a byte at a time, keep it fast */ 586 if (len == 1) { 587 adler += buf[0]; 588 if (adler >= BASE) 589 adler -= BASE; 590 sum2 += adler; 591 if (sum2 >= BASE) 592 sum2 -= BASE; 593 return adler | (sum2 << 16); 594 } 595 596 /* initial Adler-32 value (deferred check for len == 1 speed) */ 597 if (buf == Z_NULL) 598 return 1L; 599 600 /* in case short lengths are provided, keep it somewhat fast */ 601 if (len < 16) { 602 while (len--) { 603 adler += *buf++; 604 sum2 += adler; 605 } 606 if (adler >= BASE) 607 adler -= BASE; 608 MOD4(sum2); /* only added so many BASE's */ 609 return adler | (sum2 << 16); 610 } 611 612 /* do length NMAX blocks -- requires just one modulo operation */ 613 while (len >= NMAX) { 614 len -= NMAX; 615 n = NMAX / 16; /* NMAX is divisible by 16 */ 616 do { 617 DO16(buf); /* 16 sums unrolled */ 618 buf += 16; 619 } while (--n); 620 MOD(adler); 621 MOD(sum2); 622 } 623 624 /* do remaining bytes (less than NMAX, still just one modulo) */ 625 if (len) { /* avoid modulos if none remaining */ 626 while (len >= 16) { 627 len -= 16; 628 DO16(buf); 629 buf += 16; 630 } 631 while (len--) { 632 adler += *buf++; 633 sum2 += adler; 634 } 635 MOD(adler); 636 MOD(sum2); 637 } 638 639 /* return recombined sums */ 640 return adler | (sum2 << 16); 641 } 642 643 /* Macros for inflate(): */ 644 645 /* check function to use adler32() for zlib or crc32() for gzip */ 646 #ifdef GUNZIP 647 # define UPDATE(check, buf, len) \ 648 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len)) 649 #else 650 # define UPDATE(check, buf, len) adler32(check, buf, len) 651 #endif 652 653 /* check macros for header crc */ 654 #ifdef GUNZIP 655 # define CRC2(check, word) \ 656 do { \ 657 hbuf[0] = (unsigned char)(word); \ 658 hbuf[1] = (unsigned char)((word) >> 8); \ 659 check = crc32(check, hbuf, 2); \ 660 } while (0) 661 662 # define CRC4(check, word) \ 663 do { \ 664 hbuf[0] = (unsigned char)(word); \ 665 hbuf[1] = (unsigned char)((word) >> 8); \ 666 hbuf[2] = (unsigned char)((word) >> 16); \ 667 hbuf[3] = (unsigned char)((word) >> 24); \ 668 check = crc32(check, hbuf, 4); \ 669 } while (0) 670 #endif 671 672 /* Load registers with state in inflate() for speed */ 673 #define LOAD() \ 674 do { \ 675 put = strm->next_out; \ 676 left = strm->avail_out; \ 677 next = strm->next_in; \ 678 have = strm->avail_in; \ 679 hold = state->hold; \ 680 bits = state->bits; \ 681 } while (0) 682 683 /* Restore state from registers in inflate() */ 684 #define RESTORE() \ 685 do { \ 686 strm->next_out = put; \ 687 strm->avail_out = left; \ 688 strm->next_in = next; \ 689 strm->avail_in = have; \ 690 state->hold = hold; \ 691 state->bits = bits; \ 692 } while (0) 693 694 /* Clear the input bit accumulator */ 695 #define INITBITS() \ 696 do { \ 697 hold = 0; \ 698 bits = 0; \ 699 } while (0) 700 701 /* Get a byte of input into the bit accumulator, or return from inflate() 702 if there is no input available. */ 703 #define PULLBYTE() \ 704 do { \ 705 if (have == 0) goto inf_leave; \ 706 have--; \ 707 hold += (unsigned long)(*next++) << bits; \ 708 bits += 8; \ 709 } while (0) 710 711 /* Assure that there are at least n bits in the bit accumulator. If there is 712 not enough available input to do that, then return from inflate(). */ 713 #define NEEDBITS(n) \ 714 do { \ 715 while (bits < (unsigned)(n)) \ 716 PULLBYTE(); \ 717 } while (0) 718 719 /* Return the low n bits of the bit accumulator (n < 16) */ 720 #define BITS(n) \ 721 ((unsigned)hold & ((1U << (n)) - 1)) 722 723 /* Remove n bits from the bit accumulator */ 724 #define DROPBITS(n) \ 725 do { \ 726 hold >>= (n); \ 727 bits -= (unsigned)(n); \ 728 } while (0) 729 730 /* Remove zero to seven bits as needed to go to a byte boundary */ 731 #define BYTEBITS() \ 732 do { \ 733 hold >>= bits & 7; \ 734 bits -= bits & 7; \ 735 } while (0) 736 737 /* Reverse the bytes in a 32-bit value */ 738 #define REVERSE(q) \ 739 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \ 740 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24)) 741 742 #define MAXBITS 15 743 #define MAXD 592 744 745 /* 746 If you use the zlib library in a product, an acknowledgment is welcome 747 in the documentation of your product. If for some reason you cannot 748 include such an acknowledgment, I would appreciate that you keep this 749 copyright string in the executable of your product. 750 */ 751 752 /* 753 Build a set of tables to decode the provided canonical Huffman code. 754 The code lengths are lens[0..codes-1]. The result starts at *table, 755 whose indices are 0..2^bits-1. work is a writable array of at least 756 lens shorts, which is used as a work area. type is the type of code 757 to be generated, CODES, LENS, or DISTS. On return, zero is success, 758 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table 759 on return points to the next available entry's address. bits is the 760 requested root table index bits, and on return it is the actual root 761 table index bits. It will differ if the request is greater than the 762 longest code or if it is less than the shortest code. 763 */ 764 int 765 netpgpv_inflate_table(codetype type, unsigned short FAR *lens, unsigned codes, 766 code FAR * FAR *table, unsigned FAR *bits, unsigned short FAR *work) 767 { 768 unsigned len; /* a code's length in bits */ 769 unsigned sym; /* index of code symbols */ 770 unsigned mmin, mmax; /* minimum and maximum code lengths */ 771 unsigned root; /* number of index bits for root table */ 772 unsigned curr; /* number of index bits for current table */ 773 unsigned drop; /* code bits to drop for sub-table */ 774 int left; /* number of prefix codes available */ 775 unsigned used; /* code entries in table used */ 776 unsigned huff; /* Huffman code */ 777 unsigned incr; /* for incrementing code, index */ 778 unsigned fill; /* index for replicating entries */ 779 unsigned low; /* low bits for current root entry */ 780 unsigned mask; /* mask for low root bits */ 781 code this; /* table entry for duplication */ 782 code FAR *next; /* next available space in table */ 783 const unsigned short FAR *base; /* base value table to use */ 784 const unsigned short FAR *extra; /* extra bits table to use */ 785 int end; /* use base and extra for symbol > end */ 786 unsigned short count[MAXBITS+1]; /* number of codes of each length */ 787 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */ 788 static const unsigned short lbase[31] = { /* Length codes 257..285 base */ 789 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 790 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 791 static const unsigned short lext[31] = { /* Length codes 257..285 extra */ 792 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 793 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196}; 794 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */ 795 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 796 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 797 8193, 12289, 16385, 24577, 0, 0}; 798 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */ 799 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 800 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 801 28, 28, 29, 29, 64, 64}; 802 803 /* 804 Process a set of code lengths to create a canonical Huffman code. The 805 code lengths are lens[0..codes-1]. Each length corresponds to the 806 symbols 0..codes-1. The Huffman code is generated by first sorting the 807 symbols by length from short to long, and retaining the symbol order 808 for codes with equal lengths. Then the code starts with all zero bits 809 for the first code of the shortest length, and the codes are integer 810 increments for the same length, and zeros are appended as the length 811 increases. For the deflate format, these bits are stored backwards 812 from their more natural integer increment ordering, and so when the 813 decoding tables are built in the large loop below, the integer codes 814 are incremented backwards. 815 816 This routine assumes, but does not check, that all of the entries in 817 lens[] are in the range 0..MAXBITS. The caller must assure this. 818 1..MAXBITS is interpreted as that code length. zero means that that 819 symbol does not occur in this code. 820 821 The codes are sorted by computing a count of codes for each length, 822 creating from that a table of starting indices for each length in the 823 sorted table, and then entering the symbols in order in the sorted 824 table. The sorted table is work[], with that space being provided by 825 the caller. 826 827 The length counts are used for other purposes as well, i.e. finding 828 the minimum and maximum length codes, determining if there are any 829 codes at all, checking for a valid set of lengths, and looking ahead 830 at length counts to determine sub-table sizes when building the 831 decoding tables. 832 */ 833 834 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */ 835 for (len = 0; len <= MAXBITS; len++) 836 count[len] = 0; 837 for (sym = 0; sym < codes; sym++) 838 count[lens[sym]]++; 839 840 /* bound code lengths, force root to be within code lengths */ 841 root = *bits; 842 for (mmax = MAXBITS; mmax >= 1; mmax--) 843 if (count[mmax] != 0) break; 844 if (root > mmax) root = mmax; 845 if (mmax == 0) { /* no symbols to code at all */ 846 this.op = (unsigned char)64; /* invalid code marker */ 847 this.bits = (unsigned char)1; 848 this.val = (unsigned short)0; 849 *(*table)++ = this; /* make a table to force an error */ 850 *(*table)++ = this; 851 *bits = 1; 852 return 0; /* no symbols, but wait for decoding to report error */ 853 } 854 for (mmin = 1; mmin <= MAXBITS; mmin++) 855 if (count[mmin] != 0) break; 856 if (root < mmin) root = mmin; 857 858 /* check for an over-subscribed or incomplete set of lengths */ 859 left = 1; 860 for (len = 1; len <= MAXBITS; len++) { 861 left <<= 1; 862 left -= count[len]; 863 if (left < 0) return -1; /* over-subscribed */ 864 } 865 if (left > 0 && (type == CODES || mmax != 1)) 866 return -1; /* incomplete set */ 867 868 /* generate offsets into symbol table for each length for sorting */ 869 offs[1] = 0; 870 for (len = 1; len < MAXBITS; len++) 871 offs[len + 1] = offs[len] + count[len]; 872 873 /* sort symbols by length, by symbol order within each length */ 874 for (sym = 0; sym < codes; sym++) 875 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym; 876 877 /* 878 Create and fill in decoding tables. In this loop, the table being 879 filled is at next and has curr index bits. The code being used is huff 880 with length len. That code is converted to an index by dropping drop 881 bits off of the bottom. For codes where len is less than drop + curr, 882 those top drop + curr - len bits are incremented through all values to 883 fill the table with replicated entries. 884 885 root is the number of index bits for the root table. When len exceeds 886 root, sub-tables are created pointed to by the root entry with an index 887 of the low root bits of huff. This is saved in low to check for when a 888 new sub-table should be started. drop is zero when the root table is 889 being filled, and drop is root when sub-tables are being filled. 890 891 When a new sub-table is needed, it is necessary to look ahead in the 892 code lengths to determine what size sub-table is needed. The length 893 counts are used for this, and so count[] is decremented as codes are 894 entered in the tables. 895 896 used keeps track of how many table entries have been allocated from the 897 provided *table space. It is checked when a LENS table is being made 898 against the space in *table, ENOUGH, minus the maximum space needed by 899 the worst case distance code, MAXD. This should never happen, but the 900 sufficiency of ENOUGH has not been proven exhaustively, hence the check. 901 This assumes that when type == LENS, bits == 9. 902 903 sym increments through all symbols, and the loop terminates when 904 all codes of length mmax, i.e. all codes, have been processed. This 905 routine permits incomplete codes, so another loop after this one fills 906 in the rest of the decoding tables with invalid code markers. 907 */ 908 909 /* set up for code type */ 910 switch (type) { 911 case CODES: 912 base = extra = work; /* dummy value--not used */ 913 end = 19; 914 break; 915 case LENS: 916 base = lbase; 917 base -= 257; 918 extra = lext; 919 extra -= 257; 920 end = 256; 921 break; 922 default: /* DISTS */ 923 base = dbase; 924 extra = dext; 925 end = -1; 926 } 927 928 /* initialize state for loop */ 929 huff = 0; /* starting code */ 930 sym = 0; /* starting code symbol */ 931 len = mmin; /* starting code length */ 932 next = *table; /* current table to fill in */ 933 curr = root; /* current table index bits */ 934 drop = 0; /* current bits to drop from code for index */ 935 low = (unsigned)(-1); /* trigger new sub-table when len > root */ 936 used = 1U << root; /* use root table entries */ 937 mask = used - 1; /* mask for comparing low */ 938 939 /* check available table space */ 940 if (type == LENS && used >= ENOUGH - MAXD) 941 return 1; 942 943 /* process all codes and make table entries */ 944 for (;;) { 945 /* create table entry */ 946 this.bits = (unsigned char)(len - drop); 947 if ((int)(work[sym]) < end) { 948 this.op = (unsigned char)0; 949 this.val = work[sym]; 950 } 951 else if ((int)(work[sym]) > end) { 952 this.op = (unsigned char)(extra[work[sym]]); 953 this.val = base[work[sym]]; 954 } 955 else { 956 this.op = (unsigned char)(32 + 64); /* end of block */ 957 this.val = 0; 958 } 959 960 /* replicate for those indices with low len bits equal to huff */ 961 incr = 1U << (len - drop); 962 fill = 1U << curr; 963 mmin = fill; /* save offset to next table */ 964 do { 965 fill -= incr; 966 next[(huff >> drop) + fill] = this; 967 } while (fill != 0); 968 969 /* backwards increment the len-bit code huff */ 970 incr = 1U << (len - 1); 971 while (huff & incr) 972 incr >>= 1; 973 if (incr != 0) { 974 huff &= incr - 1; 975 huff += incr; 976 } 977 else 978 huff = 0; 979 980 /* go to next symbol, update count, len */ 981 sym++; 982 if (--(count[len]) == 0) { 983 if (len == mmax) break; 984 len = lens[work[sym]]; 985 } 986 987 /* create new sub-table if needed */ 988 if (len > root && (huff & mask) != low) { 989 /* if first time, transition to sub-tables */ 990 if (drop == 0) 991 drop = root; 992 993 /* increment past last table */ 994 next += mmin; /* here mmin is 1 << curr */ 995 996 /* determine length of next table */ 997 curr = len - drop; 998 left = (int)(1 << curr); 999 while (curr + drop < mmax) { 1000 left -= count[curr + drop]; 1001 if (left <= 0) break; 1002 curr++; 1003 left <<= 1; 1004 } 1005 1006 /* check for enough space */ 1007 used += 1U << curr; 1008 if (type == LENS && used >= ENOUGH - MAXD) 1009 return 1; 1010 1011 /* point entry in root table to sub-table */ 1012 low = huff & mask; 1013 (*table)[low].op = (unsigned char)curr; 1014 (*table)[low].bits = (unsigned char)root; 1015 (*table)[low].val = (unsigned short)(next - *table); 1016 } 1017 } 1018 1019 /* 1020 Fill in rest of table for incomplete codes. This loop is similar to the 1021 loop above in incrementing huff for table indices. It is assumed that 1022 len is equal to curr + drop, so there is no loop needed to increment 1023 through high index bits. When the current sub-table is filled, the loop 1024 drops back to the root table to fill in any remaining entries there. 1025 */ 1026 this.op = (unsigned char)64; /* invalid code marker */ 1027 this.bits = (unsigned char)(len - drop); 1028 this.val = (unsigned short)0; 1029 while (huff != 0) { 1030 /* when done with sub-table, drop back to root table */ 1031 if (drop != 0 && (huff & mask) != low) { 1032 drop = 0; 1033 len = root; 1034 next = *table; 1035 this.bits = (unsigned char)len; 1036 } 1037 1038 /* put invalid code marker in table */ 1039 next[huff >> drop] = this; 1040 1041 /* backwards increment the len-bit code huff */ 1042 incr = 1U << (len - 1); 1043 while (huff & incr) 1044 incr >>= 1; 1045 if (incr != 0) { 1046 huff &= incr - 1; 1047 huff += incr; 1048 } 1049 else 1050 huff = 0; 1051 } 1052 1053 /* set return parameters */ 1054 *table += used; 1055 *bits = root; 1056 return 0; 1057 } 1058 1059 /* Allow machine dependent optimization for post-increment or pre-increment. 1060 Based on testing to date, 1061 Pre-increment preferred for: 1062 - PowerPC G3 (Adler) 1063 - MIPS R5000 (Randers-Pehrson) 1064 Post-increment preferred for: 1065 - none 1066 No measurable difference: 1067 - Pentium III (Anderson) 1068 - M68060 (Nikl) 1069 */ 1070 #ifdef POSTINC 1071 # define OFF 0 1072 # define PUP(a) *(a)++ 1073 #else 1074 # define OFF 1 1075 # define PUP(a) *++(a) 1076 #endif 1077 1078 /* 1079 Decode literal, length, and distance codes and write out the resulting 1080 literal and match bytes until either not enough input or output is 1081 available, an end-of-block is encountered, or a data error is encountered. 1082 When large enough input and output buffers are supplied to inflate(), for 1083 example, a 16K input buffer and a 64K output buffer, more than 95% of the 1084 inflate execution time is spent in this routine. 1085 1086 Entry assumptions: 1087 1088 state->mode == LEN 1089 strm->avail_in >= 6 1090 strm->avail_out >= 258 1091 start >= strm->avail_out 1092 state->bits < 8 1093 1094 On return, state->mode is one of: 1095 1096 LEN -- ran out of enough output space or enough available input 1097 TYPE -- reached end of block code, inflate() to interpret next block 1098 BAD -- error in block data 1099 1100 Notes: 1101 1102 - The maximum input bits used by a length/distance pair is 15 bits for the 1103 length code, 5 bits for the length extra, 15 bits for the distance code, 1104 and 13 bits for the distance extra. This totals 48 bits, or six bytes. 1105 Therefore if strm->avail_in >= 6, then there is enough input to avoid 1106 checking for available input while decoding. 1107 1108 - The maximum bytes that a single length/distance pair can output is 258 1109 bytes, which is the maximum length that can be coded. netpgpv_inflate_fast() 1110 requires strm->avail_out >= 258 for each loop to avoid checking for 1111 output space. 1112 */ 1113 void 1114 netpgpv_inflate_fast(z_streamp strm, unsigned start) 1115 /* inflate()'s starting value for strm->avail_out */ 1116 { 1117 struct inflate_state FAR *state; 1118 unsigned char FAR *in; /* local strm->next_in */ 1119 unsigned char FAR *last; /* while in < last, enough input available */ 1120 unsigned char FAR *out; /* local strm->next_out */ 1121 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */ 1122 unsigned char FAR *end; /* while out < end, enough space available */ 1123 #ifdef INFLATE_STRICT 1124 unsigned dmax; /* maximum distance from zlib header */ 1125 #endif 1126 unsigned wsize; /* window size or zero if not using window */ 1127 unsigned whave; /* valid bytes in the window */ 1128 unsigned wwrite; /* window write index */ 1129 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */ 1130 unsigned long hold; /* local strm->hold */ 1131 unsigned bits; /* local strm->bits */ 1132 code const FAR *lcode; /* local strm->lencode */ 1133 code const FAR *dcode; /* local strm->distcode */ 1134 unsigned lmask; /* mask for first level of length codes */ 1135 unsigned dmask; /* mask for first level of distance codes */ 1136 code this; /* retrieved table entry */ 1137 unsigned op; /* code bits, operation, extra bits, or */ 1138 /* window position, window bytes to copy */ 1139 unsigned len; /* match length, unused bytes */ 1140 unsigned dist; /* match distance */ 1141 unsigned char FAR *from; /* where to copy match from */ 1142 1143 /* copy state to local variables */ 1144 state = (struct inflate_state FAR *)(void *)strm->state; 1145 in = strm->next_in - OFF; 1146 last = in + (strm->avail_in - 5); 1147 out = strm->next_out - OFF; 1148 beg = out - (start - strm->avail_out); 1149 end = out + (strm->avail_out - 257); 1150 #ifdef INFLATE_STRICT 1151 dmax = state->dmax; 1152 #endif 1153 wsize = state->wsize; 1154 whave = state->whave; 1155 wwrite = state->write; 1156 window = state->window; 1157 hold = state->hold; 1158 bits = state->bits; 1159 lcode = state->lencode; 1160 dcode = state->distcode; 1161 lmask = (1U << state->lenbits) - 1; 1162 dmask = (1U << state->distbits) - 1; 1163 1164 /* decode literals and length/distances until end-of-block or not enough 1165 input data or output space */ 1166 do { 1167 if (bits < 15) { 1168 hold += (unsigned long)(PUP(in)) << bits; 1169 bits += 8; 1170 hold += (unsigned long)(PUP(in)) << bits; 1171 bits += 8; 1172 } 1173 this = lcode[hold & lmask]; 1174 dolen: 1175 op = (unsigned)(this.bits); 1176 hold >>= op; 1177 bits -= op; 1178 op = (unsigned)(this.op); 1179 if (op == 0) { /* literal */ 1180 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 1181 "inflate: literal '%c'\n" : 1182 "inflate: literal 0x%02x\n", this.val)); 1183 PUP(out) = (unsigned char)(this.val); 1184 } 1185 else if (op & 16) { /* length base */ 1186 len = (unsigned)(this.val); 1187 op &= 15; /* number of extra bits */ 1188 if (op) { 1189 if (bits < op) { 1190 hold += (unsigned long)(PUP(in)) << bits; 1191 bits += 8; 1192 } 1193 len += (unsigned)hold & ((1U << op) - 1); 1194 hold >>= op; 1195 bits -= op; 1196 } 1197 Tracevv((stderr, "inflate: length %u\n", len)); 1198 if (bits < 15) { 1199 hold += (unsigned long)(PUP(in)) << bits; 1200 bits += 8; 1201 hold += (unsigned long)(PUP(in)) << bits; 1202 bits += 8; 1203 } 1204 this = dcode[hold & dmask]; 1205 dodist: 1206 op = (unsigned)(this.bits); 1207 hold >>= op; 1208 bits -= op; 1209 op = (unsigned)(this.op); 1210 if (op & 16) { /* distance base */ 1211 dist = (unsigned)(this.val); 1212 op &= 15; /* number of extra bits */ 1213 if (bits < op) { 1214 hold += (unsigned long)(PUP(in)) << bits; 1215 bits += 8; 1216 if (bits < op) { 1217 hold += (unsigned long)(PUP(in)) << bits; 1218 bits += 8; 1219 } 1220 } 1221 dist += (unsigned)hold & ((1U << op) - 1); 1222 #ifdef INFLATE_STRICT 1223 if (dist > dmax) { 1224 strm->msg = (char *)"invalid distance too far back"; 1225 state->mode = BAD; 1226 break; 1227 } 1228 #endif 1229 hold >>= op; 1230 bits -= op; 1231 Tracevv((stderr, "inflate: distance %u\n", dist)); 1232 op = (unsigned)(out - beg); /* max distance in output */ 1233 if (dist > op) { /* see if copy from window */ 1234 op = dist - op; /* distance back in window */ 1235 if (op > whave) { 1236 strm->msg = __UNCONST("invalid distance too far back"); 1237 state->mode = BAD; 1238 break; 1239 } 1240 from = window - OFF; 1241 if (wwrite == 0) { /* very common case */ 1242 from += wsize - op; 1243 if (op < len) { /* some from window */ 1244 len -= op; 1245 do { 1246 PUP(out) = PUP(from); 1247 } while (--op); 1248 from = out - dist; /* rest from output */ 1249 } 1250 } 1251 else if (wwrite < op) { /* wrap around window */ 1252 from += wsize + wwrite - op; 1253 op -= wwrite; 1254 if (op < len) { /* some from end of window */ 1255 len -= op; 1256 do { 1257 PUP(out) = PUP(from); 1258 } while (--op); 1259 from = window - OFF; 1260 if (wwrite < len) { /* some from start of window */ 1261 op = wwrite; 1262 len -= op; 1263 do { 1264 PUP(out) = PUP(from); 1265 } while (--op); 1266 from = out - dist; /* rest from output */ 1267 } 1268 } 1269 } 1270 else { /* contiguous in window */ 1271 from += wwrite - op; 1272 if (op < len) { /* some from window */ 1273 len -= op; 1274 do { 1275 PUP(out) = PUP(from); 1276 } while (--op); 1277 from = out - dist; /* rest from output */ 1278 } 1279 } 1280 while (len > 2) { 1281 PUP(out) = PUP(from); 1282 PUP(out) = PUP(from); 1283 PUP(out) = PUP(from); 1284 len -= 3; 1285 } 1286 if (len) { 1287 PUP(out) = PUP(from); 1288 if (len > 1) 1289 PUP(out) = PUP(from); 1290 } 1291 } 1292 else { 1293 from = out - dist; /* copy direct from output */ 1294 do { /* minimum length is three */ 1295 PUP(out) = PUP(from); 1296 PUP(out) = PUP(from); 1297 PUP(out) = PUP(from); 1298 len -= 3; 1299 } while (len > 2); 1300 if (len) { 1301 PUP(out) = PUP(from); 1302 if (len > 1) 1303 PUP(out) = PUP(from); 1304 } 1305 } 1306 } 1307 else if ((op & 64) == 0) { /* 2nd level distance code */ 1308 this = dcode[this.val + (hold & ((1U << op) - 1))]; 1309 goto dodist; 1310 } 1311 else { 1312 strm->msg = __UNCONST("invalid distance code"); 1313 state->mode = BAD; 1314 break; 1315 } 1316 } 1317 else if ((op & 64) == 0) { /* 2nd level length code */ 1318 this = lcode[this.val + (hold & ((1U << op) - 1))]; 1319 goto dolen; 1320 } 1321 else if (op & 32) { /* end-of-block */ 1322 Tracevv((stderr, "inflate: end of block\n")); 1323 state->mode = TYPE; 1324 break; 1325 } 1326 else { 1327 strm->msg = __UNCONST("invalid literal/length code"); 1328 state->mode = BAD; 1329 break; 1330 } 1331 } while (in < last && out < end); 1332 1333 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */ 1334 len = bits >> 3; 1335 in -= len; 1336 bits -= len << 3; 1337 hold &= (1U << bits) - 1; 1338 1339 /* update state and return */ 1340 strm->next_in = in + OFF; 1341 strm->next_out = out + OFF; 1342 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last)); 1343 strm->avail_out = (unsigned)(out < end ? 1344 257 + (end - out) : 257 - (out - end)); 1345 state->hold = hold; 1346 state->bits = bits; 1347 return; 1348 } 1349 1350 /* 1351 inflate() uses a state machine to process as much input data and generate as 1352 much output data as possible before returning. The state machine is 1353 structured roughly as follows: 1354 1355 for (;;) switch (state) { 1356 ... 1357 case STATEn: 1358 if (not enough input data or output space to make progress) 1359 return; 1360 ... make progress ... 1361 state = STATEm; 1362 break; 1363 ... 1364 } 1365 1366 so when inflate() is called again, the same case is attempted again, and 1367 if the appropriate resources are provided, the machine proceeds to the 1368 next state. The NEEDBITS() macro is usually the way the state evaluates 1369 whether it can proceed or should return. NEEDBITS() does the return if 1370 the requested bits are not available. The typical use of the BITS macros 1371 is: 1372 1373 NEEDBITS(n); 1374 ... do something with BITS(n) ... 1375 DROPBITS(n); 1376 1377 where NEEDBITS(n) either returns from inflate() if there isn't enough 1378 input left to load n bits into the accumulator, or it continues. BITS(n) 1379 gives the low n bits in the accumulator. When done, DROPBITS(n) drops 1380 the low n bits off the accumulator. INITBITS() clears the accumulator 1381 and sets the number of available bits to zero. BYTEBITS() discards just 1382 enough bits to put the accumulator on a byte boundary. After BYTEBITS() 1383 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 1384 1385 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 1386 if there is no input available. The decoding of variable length codes uses 1387 PULLBYTE() directly in order to pull just enough bytes to decode the next 1388 code, and no more. 1389 1390 Some states loop until they get enough input, making sure that enough 1391 state information is maintained to continue the loop where it left off 1392 if NEEDBITS() returns in the loop. For example, want, need, and keep 1393 would all have to actually be part of the saved state in case NEEDBITS() 1394 returns: 1395 1396 case STATEw: 1397 while (want < need) { 1398 NEEDBITS(n); 1399 keep[want++] = BITS(n); 1400 DROPBITS(n); 1401 } 1402 state = STATEx; 1403 case STATEx: 1404 1405 As shown above, if the next state is also the next case, then the break 1406 is omitted. 1407 1408 A state may also return if there is not enough output space available to 1409 complete that state. Those states are copying stored data, writing a 1410 literal byte, and copying a matching string. 1411 1412 When returning, a "goto inf_leave" is used to update the total counters, 1413 update the check value, and determine whether any progress has been made 1414 during that inflate() call in order to return the proper return code. 1415 Progress is defined as a change in either strm->avail_in or strm->avail_out. 1416 When there is a window, goto inf_leave will update the window with the last 1417 output written. If a goto inf_leave occurs in the middle of decompression 1418 and there is no window currently, goto inf_leave will create one and copy 1419 output to the window for the next call of inflate(). 1420 1421 In this implementation, the flush parameter of inflate() only affects the 1422 return code (per zlib.h). inflate() always writes as much as possible to 1423 strm->next_out, given the space available and the provided input--the effect 1424 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 1425 the allocation of and copying into a sliding window until necessary, which 1426 provides the effect documented in zlib.h for Z_FINISH when the entire input 1427 stream available. So the only thing the flush parameter actually does is: 1428 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 1429 will return Z_BUF_ERROR if it has not reached the end of the stream. 1430 */ 1431 1432 int ZEXPORT 1433 inflate(z_streamp strm, int flush) 1434 { 1435 struct inflate_state FAR *state; 1436 unsigned char FAR *next; /* next input */ 1437 unsigned char FAR *put; /* next output */ 1438 unsigned have, left; /* available input and output */ 1439 unsigned long hold; /* bit buffer */ 1440 unsigned bits; /* bits in bit buffer */ 1441 unsigned in, out; /* save starting available input and output */ 1442 unsigned copy; /* number of stored or match bytes to copy */ 1443 unsigned char FAR *from; /* where to copy match bytes from */ 1444 code this; /* current decoding table entry */ 1445 code last; /* parent table entry */ 1446 unsigned len; /* length to copy for repeats, bits to drop */ 1447 int ret; /* return code */ 1448 #ifdef GUNZIP 1449 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */ 1450 #endif 1451 static const unsigned short order[19] = /* permutation of code lengths */ 1452 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 1453 1454 #if defined(__NetBSD__) && defined(_STANDALONE) 1455 /* Some kernels are loaded at address 0x0 so strm->next_out could be NULL */ 1456 if (strm == Z_NULL || strm->state == Z_NULL || 1457 (strm->next_in == Z_NULL && strm->avail_in != 0)) 1458 return Z_STREAM_ERROR; 1459 #else 1460 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 1461 (strm->next_in == Z_NULL && strm->avail_in != 0)) 1462 return Z_STREAM_ERROR; 1463 #endif 1464 1465 state = (struct inflate_state FAR *)(void *)strm->state; 1466 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 1467 LOAD(); 1468 in = have; 1469 out = left; 1470 ret = Z_OK; 1471 for (;;) 1472 switch (state->mode) { 1473 case HEAD: 1474 if (state->wrap == 0) { 1475 state->mode = TYPEDO; 1476 break; 1477 } 1478 NEEDBITS(16); 1479 #ifdef GUNZIP 1480 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */ 1481 state->check = crc32(0L, Z_NULL, 0); 1482 CRC2(state->check, hold); 1483 INITBITS(); 1484 state->mode = FLAGS; 1485 break; 1486 } 1487 state->flags = 0; /* expect zlib header */ 1488 if (state->head != Z_NULL) 1489 state->head->done = -1; 1490 if (!(state->wrap & 1) || /* check if zlib header allowed */ 1491 #else 1492 if ( 1493 #endif 1494 ((BITS(8) << 8) + (hold >> 8)) % 31) { 1495 strm->msg = __UNCONST("incorrect header check"); 1496 state->mode = BAD; 1497 break; 1498 } 1499 if (BITS(4) != Z_DEFLATED) { 1500 strm->msg = __UNCONST("unknown compression method"); 1501 state->mode = BAD; 1502 break; 1503 } 1504 DROPBITS(4); 1505 len = BITS(4) + 8; 1506 if (len > state->wbits) { 1507 strm->msg = __UNCONST("invalid window size"); 1508 state->mode = BAD; 1509 break; 1510 } 1511 state->dmax = 1U << len; 1512 Tracev((stderr, "inflate: zlib header ok\n")); 1513 strm->adler = state->check = adler32(0L, Z_NULL, 0); 1514 state->mode = hold & 0x200 ? DICTID : TYPE; 1515 INITBITS(); 1516 break; 1517 #ifdef GUNZIP 1518 case FLAGS: 1519 NEEDBITS(16); 1520 state->flags = (int)(hold); 1521 if ((state->flags & 0xff) != Z_DEFLATED) { 1522 strm->msg = __UNCONST("unknown compression method"); 1523 state->mode = BAD; 1524 break; 1525 } 1526 if (state->flags & 0xe000) { 1527 strm->msg = __UNCONST("unknown header flags set"); 1528 state->mode = BAD; 1529 break; 1530 } 1531 if (state->head != Z_NULL) 1532 state->head->text = (int)((hold >> 8) & 1); 1533 if (state->flags & 0x0200) CRC2(state->check, hold); 1534 INITBITS(); 1535 state->mode = TIME; 1536 case TIME: 1537 NEEDBITS(32); 1538 if (state->head != Z_NULL) 1539 state->head->time = hold; 1540 if (state->flags & 0x0200) CRC4(state->check, hold); 1541 INITBITS(); 1542 state->mode = OS; 1543 case OS: 1544 NEEDBITS(16); 1545 if (state->head != Z_NULL) { 1546 state->head->xflags = (int)(hold & 0xff); 1547 state->head->os = (int)(hold >> 8); 1548 } 1549 if (state->flags & 0x0200) CRC2(state->check, hold); 1550 INITBITS(); 1551 state->mode = EXLEN; 1552 case EXLEN: 1553 if (state->flags & 0x0400) { 1554 NEEDBITS(16); 1555 state->length = (unsigned)(hold); 1556 if (state->head != Z_NULL) 1557 state->head->extra_len = (unsigned)hold; 1558 if (state->flags & 0x0200) CRC2(state->check, hold); 1559 INITBITS(); 1560 } 1561 else if (state->head != Z_NULL) 1562 state->head->extra = Z_NULL; 1563 state->mode = EXTRA; 1564 case EXTRA: 1565 if (state->flags & 0x0400) { 1566 copy = state->length; 1567 if (copy > have) copy = have; 1568 if (copy) { 1569 if (state->head != Z_NULL && 1570 state->head->extra != Z_NULL) { 1571 len = state->head->extra_len - state->length; 1572 Assert (next != NULL, "next is null"); 1573 zmemcpy(state->head->extra + len, next, 1574 len + copy > state->head->extra_max ? 1575 state->head->extra_max - len : copy); 1576 } 1577 if (state->flags & 0x0200) 1578 state->check = crc32(state->check, next, copy); 1579 have -= copy; 1580 next += copy; 1581 state->length -= copy; 1582 } 1583 if (state->length) goto inf_leave; 1584 } 1585 state->length = 0; 1586 state->mode = NAME; 1587 case NAME: 1588 if (state->flags & 0x0800) { 1589 if (have == 0) goto inf_leave; 1590 copy = 0; 1591 do { 1592 len = (unsigned)(next[copy++]); 1593 if (state->head != Z_NULL && 1594 state->head->name != Z_NULL && 1595 state->length < state->head->name_max) 1596 state->head->name[state->length++] = len; 1597 } while (len && copy < have); 1598 if (state->flags & 0x0200) 1599 state->check = crc32(state->check, next, copy); 1600 have -= copy; 1601 next += copy; 1602 if (len) goto inf_leave; 1603 } 1604 else if (state->head != Z_NULL) 1605 state->head->name = Z_NULL; 1606 state->length = 0; 1607 state->mode = COMMENT; 1608 case COMMENT: 1609 if (state->flags & 0x1000) { 1610 if (have == 0) goto inf_leave; 1611 copy = 0; 1612 do { 1613 len = (unsigned)(next[copy++]); 1614 if (state->head != Z_NULL && 1615 state->head->comment != Z_NULL && 1616 state->length < state->head->comm_max) 1617 state->head->comment[state->length++] = len; 1618 } while (len && copy < have); 1619 if (state->flags & 0x0200) 1620 state->check = crc32(state->check, next, copy); 1621 have -= copy; 1622 next += copy; 1623 if (len) goto inf_leave; 1624 } 1625 else if (state->head != Z_NULL) 1626 state->head->comment = Z_NULL; 1627 state->mode = HCRC; 1628 case HCRC: 1629 if (state->flags & 0x0200) { 1630 NEEDBITS(16); 1631 if (hold != (state->check & 0xffff)) { 1632 strm->msg = __UNCONST("header crc mismatch"); 1633 state->mode = BAD; 1634 break; 1635 } 1636 INITBITS(); 1637 } 1638 if (state->head != Z_NULL) { 1639 state->head->hcrc = (int)((state->flags >> 9) & 1); 1640 state->head->done = 1; 1641 } 1642 strm->adler = state->check = crc32(0L, Z_NULL, 0); 1643 state->mode = TYPE; 1644 break; 1645 #endif 1646 case DICTID: 1647 NEEDBITS(32); 1648 strm->adler = state->check = REVERSE(hold); 1649 INITBITS(); 1650 state->mode = DICT; 1651 case DICT: 1652 if (state->havedict == 0) { 1653 RESTORE(); 1654 return Z_NEED_DICT; 1655 } 1656 strm->adler = state->check = adler32(0L, Z_NULL, 0); 1657 state->mode = TYPE; 1658 case TYPE: 1659 if (flush == Z_BLOCK) goto inf_leave; 1660 case TYPEDO: 1661 if (state->last) { 1662 BYTEBITS(); 1663 state->mode = CHECK; 1664 break; 1665 } 1666 NEEDBITS(3); 1667 state->last = BITS(1); 1668 DROPBITS(1); 1669 switch (BITS(2)) { 1670 case 0: /* stored block */ 1671 Tracev((stderr, "inflate: stored block%s\n", 1672 state->last ? " (last)" : "")); 1673 state->mode = STORED; 1674 break; 1675 case 1: /* fixed block */ 1676 fixedtables(state); 1677 Tracev((stderr, "inflate: fixed codes block%s\n", 1678 state->last ? " (last)" : "")); 1679 state->mode = LEN; /* decode codes */ 1680 break; 1681 case 2: /* dynamic block */ 1682 Tracev((stderr, "inflate: dynamic codes block%s\n", 1683 state->last ? " (last)" : "")); 1684 state->mode = TABLE; 1685 break; 1686 case 3: 1687 strm->msg = __UNCONST("invalid block type"); 1688 state->mode = BAD; 1689 } 1690 DROPBITS(2); 1691 break; 1692 case STORED: 1693 BYTEBITS(); /* go to byte boundary */ 1694 NEEDBITS(32); 1695 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 1696 strm->msg = __UNCONST("invalid stored block lengths"); 1697 state->mode = BAD; 1698 break; 1699 } 1700 state->length = (unsigned)hold & 0xffff; 1701 Tracev((stderr, "inflate: stored length %u\n", 1702 state->length)); 1703 INITBITS(); 1704 state->mode = COPY; 1705 case COPY: 1706 copy = state->length; 1707 if (copy) { 1708 if (copy > have) copy = have; 1709 if (copy > left) copy = left; 1710 if (copy == 0) goto inf_leave; 1711 zmemcpy(put, next, copy); 1712 have -= copy; 1713 next += copy; 1714 left -= copy; 1715 put += copy; 1716 state->length -= copy; 1717 break; 1718 } 1719 Tracev((stderr, "inflate: stored end\n")); 1720 state->mode = TYPE; 1721 break; 1722 case TABLE: 1723 NEEDBITS(14); 1724 state->nlen = BITS(5) + 257; 1725 DROPBITS(5); 1726 state->ndist = BITS(5) + 1; 1727 DROPBITS(5); 1728 state->ncode = BITS(4) + 4; 1729 DROPBITS(4); 1730 #ifndef PKZIP_BUG_WORKAROUND 1731 if (state->nlen > 286 || state->ndist > 30) { 1732 strm->msg = __UNCONST("too many length or distance symbols"); 1733 state->mode = BAD; 1734 break; 1735 } 1736 #endif 1737 Tracev((stderr, "inflate: table sizes ok\n")); 1738 state->have = 0; 1739 state->mode = LENLENS; 1740 case LENLENS: 1741 while (state->have < state->ncode) { 1742 NEEDBITS(3); 1743 state->lens[order[state->have++]] = (unsigned short)BITS(3); 1744 DROPBITS(3); 1745 } 1746 while (state->have < 19) 1747 state->lens[order[state->have++]] = 0; 1748 state->next = state->codes; 1749 state->lencode = (code const FAR *)(state->next); 1750 state->lenbits = 7; 1751 ret = netpgpv_inflate_table(CODES, state->lens, 19, &(state->next), 1752 &(state->lenbits), state->work); 1753 if (ret) { 1754 strm->msg = __UNCONST("invalid code lengths set"); 1755 state->mode = BAD; 1756 break; 1757 } 1758 Tracev((stderr, "inflate: code lengths ok\n")); 1759 state->have = 0; 1760 state->mode = CODELENS; 1761 case CODELENS: 1762 while (state->have < state->nlen + state->ndist) { 1763 for (;;) { 1764 this = state->lencode[BITS(state->lenbits)]; 1765 if ((unsigned)(this.bits) <= bits) break; 1766 PULLBYTE(); 1767 } 1768 if (this.val < 16) { 1769 NEEDBITS(this.bits); 1770 DROPBITS(this.bits); 1771 state->lens[state->have++] = this.val; 1772 } 1773 else { 1774 if (this.val == 16) { 1775 NEEDBITS(this.bits + 2); 1776 DROPBITS(this.bits); 1777 if (state->have == 0) { 1778 strm->msg = __UNCONST("invalid bit length repeat"); 1779 state->mode = BAD; 1780 break; 1781 } 1782 len = state->lens[state->have - 1]; 1783 copy = 3 + BITS(2); 1784 DROPBITS(2); 1785 } 1786 else if (this.val == 17) { 1787 NEEDBITS(this.bits + 3); 1788 DROPBITS(this.bits); 1789 len = 0; 1790 copy = 3 + BITS(3); 1791 DROPBITS(3); 1792 } 1793 else { 1794 NEEDBITS(this.bits + 7); 1795 DROPBITS(this.bits); 1796 len = 0; 1797 copy = 11 + BITS(7); 1798 DROPBITS(7); 1799 } 1800 if (state->have + copy > state->nlen + state->ndist) { 1801 strm->msg = __UNCONST("invalid bit length repeat"); 1802 state->mode = BAD; 1803 break; 1804 } 1805 while (copy--) 1806 state->lens[state->have++] = (unsigned short)len; 1807 } 1808 } 1809 1810 /* handle error breaks in while */ 1811 if (state->mode == BAD) break; 1812 1813 /* build code tables */ 1814 state->next = state->codes; 1815 state->lencode = (code const FAR *)(state->next); 1816 state->lenbits = 9; 1817 ret = netpgpv_inflate_table(LENS, state->lens, state->nlen, &(state->next), 1818 &(state->lenbits), state->work); 1819 if (ret) { 1820 strm->msg = __UNCONST("invalid literal/lengths set"); 1821 state->mode = BAD; 1822 break; 1823 } 1824 state->distcode = (code const FAR *)(state->next); 1825 state->distbits = 6; 1826 ret = netpgpv_inflate_table(DISTS, state->lens + state->nlen, state->ndist, 1827 &(state->next), &(state->distbits), state->work); 1828 if (ret) { 1829 strm->msg = __UNCONST("invalid distances set"); 1830 state->mode = BAD; 1831 break; 1832 } 1833 Tracev((stderr, "inflate: codes ok\n")); 1834 state->mode = LEN; 1835 case LEN: 1836 if (have >= 6 && left >= 258) { 1837 RESTORE(); 1838 netpgpv_inflate_fast(strm, out); 1839 LOAD(); 1840 break; 1841 } 1842 for (;;) { 1843 this = state->lencode[BITS(state->lenbits)]; 1844 if ((unsigned)(this.bits) <= bits) break; 1845 PULLBYTE(); 1846 } 1847 if (this.op && (this.op & 0xf0) == 0) { 1848 last = this; 1849 for (;;) { 1850 this = state->lencode[last.val + 1851 (BITS(last.bits + last.op) >> last.bits)]; 1852 if ((unsigned)(last.bits + this.bits) <= bits) break; 1853 PULLBYTE(); 1854 } 1855 DROPBITS(last.bits); 1856 } 1857 DROPBITS(this.bits); 1858 state->length = (unsigned)this.val; 1859 if ((int)(this.op) == 0) { 1860 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 1861 "inflate: literal '%c'\n" : 1862 "inflate: literal 0x%02x\n", this.val)); 1863 state->mode = LIT; 1864 break; 1865 } 1866 if (this.op & 32) { 1867 Tracevv((stderr, "inflate: end of block\n")); 1868 state->mode = TYPE; 1869 break; 1870 } 1871 if (this.op & 64) { 1872 strm->msg = __UNCONST("invalid literal/length code"); 1873 state->mode = BAD; 1874 break; 1875 } 1876 state->extra = (unsigned)(this.op) & 15; 1877 state->mode = LENEXT; 1878 case LENEXT: 1879 if (state->extra) { 1880 NEEDBITS(state->extra); 1881 state->length += BITS(state->extra); 1882 DROPBITS(state->extra); 1883 } 1884 Tracevv((stderr, "inflate: length %u\n", state->length)); 1885 state->mode = DIST; 1886 case DIST: 1887 for (;;) { 1888 this = state->distcode[BITS(state->distbits)]; 1889 if ((unsigned)(this.bits) <= bits) break; 1890 PULLBYTE(); 1891 } 1892 if ((this.op & 0xf0) == 0) { 1893 last = this; 1894 for (;;) { 1895 this = state->distcode[last.val + 1896 (BITS(last.bits + last.op) >> last.bits)]; 1897 if ((unsigned)(last.bits + this.bits) <= bits) break; 1898 PULLBYTE(); 1899 } 1900 DROPBITS(last.bits); 1901 } 1902 DROPBITS(this.bits); 1903 if (this.op & 64) { 1904 strm->msg = __UNCONST("invalid distance code"); 1905 state->mode = BAD; 1906 break; 1907 } 1908 state->offset = (unsigned)this.val; 1909 state->extra = (unsigned)(this.op) & 15; 1910 state->mode = DISTEXT; 1911 case DISTEXT: 1912 if (state->extra) { 1913 NEEDBITS(state->extra); 1914 state->offset += BITS(state->extra); 1915 DROPBITS(state->extra); 1916 } 1917 #ifdef INFLATE_STRICT 1918 if (state->offset > state->dmax) { 1919 strm->msg = __UNCONST("invalid distance too far back"); 1920 state->mode = BAD; 1921 break; 1922 } 1923 #endif 1924 if (state->offset > state->whave + out - left) { 1925 strm->msg = __UNCONST("invalid distance too far back"); 1926 state->mode = BAD; 1927 break; 1928 } 1929 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 1930 state->mode = MATCH; 1931 case MATCH: 1932 if (left == 0) goto inf_leave; 1933 copy = out - left; 1934 if (state->offset > copy) { /* copy from window */ 1935 copy = state->offset - copy; 1936 if (copy > state->write) { 1937 copy -= state->write; 1938 from = state->window + (state->wsize - copy); 1939 } 1940 else 1941 from = state->window + (state->write - copy); 1942 if (copy > state->length) copy = state->length; 1943 } 1944 else { /* copy from output */ 1945 from = put - state->offset; 1946 copy = state->length; 1947 } 1948 if (copy > left) copy = left; 1949 left -= copy; 1950 state->length -= copy; 1951 do { 1952 *put++ = *from++; 1953 } while (--copy); 1954 if (state->length == 0) state->mode = LEN; 1955 break; 1956 case LIT: 1957 if (left == 0) goto inf_leave; 1958 *put++ = (unsigned char)(state->length); 1959 left--; 1960 state->mode = LEN; 1961 break; 1962 case CHECK: 1963 if (state->wrap) { 1964 NEEDBITS(32); 1965 out -= left; 1966 strm->total_out += out; 1967 state->total += out; 1968 if (out) 1969 strm->adler = state->check = 1970 UPDATE(state->check, put - out, out); 1971 out = left; 1972 if (( 1973 #ifdef GUNZIP 1974 state->flags ? hold : 1975 #endif 1976 REVERSE(hold)) != state->check) { 1977 strm->msg = __UNCONST("incorrect data check"); 1978 state->mode = BAD; 1979 break; 1980 } 1981 INITBITS(); 1982 Tracev((stderr, "inflate: check matches trailer\n")); 1983 } 1984 #ifdef GUNZIP 1985 state->mode = LENGTH; 1986 case LENGTH: 1987 if (state->wrap && state->flags) { 1988 NEEDBITS(32); 1989 if (hold != (state->total & 0xffffffffUL)) { 1990 strm->msg = __UNCONST("incorrect length check"); 1991 state->mode = BAD; 1992 break; 1993 } 1994 INITBITS(); 1995 Tracev((stderr, "inflate: length matches trailer\n")); 1996 } 1997 #endif 1998 state->mode = DONE; 1999 case DONE: 2000 ret = Z_STREAM_END; 2001 goto inf_leave; 2002 case BAD: 2003 ret = Z_DATA_ERROR; 2004 goto inf_leave; 2005 case MEM: 2006 return Z_MEM_ERROR; 2007 case SYNC: 2008 default: 2009 return Z_STREAM_ERROR; 2010 } 2011 2012 /* 2013 Return from inflate(), updating the total counts and the check value. 2014 If there was no progress during the inflate() call, return a buffer 2015 error. Call updatewindow() to create and/or update the window state. 2016 Note: a memory error from inflate() is non-recoverable. 2017 */ 2018 inf_leave: 2019 RESTORE(); 2020 if (state->wsize || (state->mode < CHECK && out != strm->avail_out)) 2021 if (updatewindow(strm, out)) { 2022 state->mode = MEM; 2023 return Z_MEM_ERROR; 2024 } 2025 in -= strm->avail_in; 2026 out -= strm->avail_out; 2027 strm->total_in += in; 2028 strm->total_out += out; 2029 state->total += out; 2030 if (state->wrap && out) 2031 strm->adler = state->check = 2032 UPDATE(state->check, strm->next_out - out, out); 2033 strm->data_type = state->bits + (state->last ? 64 : 0) + 2034 (state->mode == TYPE ? 128 : 0); 2035 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 2036 ret = Z_BUF_ERROR; 2037 return ret; 2038 } 2039 2040 int ZEXPORT 2041 inflateEnd(z_streamp strm) 2042 { 2043 struct inflate_state FAR *state; 2044 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 2045 return Z_STREAM_ERROR; 2046 state = (struct inflate_state FAR *)(void *)strm->state; 2047 if (state->window != Z_NULL) ZFREE(strm, state->window); 2048 ZFREE(strm, strm->state); 2049 strm->state = Z_NULL; 2050 Tracev((stderr, "inflate: end\n")); 2051 return Z_OK; 2052 } 2053 2054 int ZEXPORT 2055 inflateSetDictionary(z_streamp strm, const Bytef *dictionary, uInt dictLength) 2056 { 2057 struct inflate_state FAR *state; 2058 unsigned long id; 2059 2060 /* check state */ 2061 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 2062 state = (struct inflate_state FAR *)(void *)strm->state; 2063 if (state->wrap != 0 && state->mode != DICT) 2064 return Z_STREAM_ERROR; 2065 2066 /* check for correct dictionary id */ 2067 if (state->mode == DICT) { 2068 id = adler32(0L, Z_NULL, 0); 2069 id = adler32(id, dictionary, dictLength); 2070 if (id != state->check) 2071 return Z_DATA_ERROR; 2072 } 2073 2074 /* copy dictionary to window */ 2075 if (updatewindow(strm, strm->avail_out)) { 2076 state->mode = MEM; 2077 return Z_MEM_ERROR; 2078 } 2079 if (dictLength > state->wsize) { 2080 zmemcpy(state->window, dictionary + dictLength - state->wsize, 2081 state->wsize); 2082 state->whave = state->wsize; 2083 } 2084 else { 2085 zmemcpy(state->window + state->wsize - dictLength, dictionary, 2086 dictLength); 2087 state->whave = dictLength; 2088 } 2089 state->havedict = 1; 2090 Tracev((stderr, "inflate: dictionary set\n")); 2091 return Z_OK; 2092 } 2093 2094 int ZEXPORT 2095 netpgpv_inflateGetHeader(z_streamp strm, gz_headerp head) 2096 { 2097 struct inflate_state FAR *state; 2098 2099 /* check state */ 2100 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 2101 state = (struct inflate_state FAR *)(void *)strm->state; 2102 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR; 2103 2104 /* save header structure */ 2105 state->head = head; 2106 head->done = 0; 2107 return Z_OK; 2108 } 2109 2110 /* 2111 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 2112 or when out of input. When called, *have is the number of pattern bytes 2113 found in order so far, in 0..3. On return *have is updated to the new 2114 state. If on return *have equals four, then the pattern was found and the 2115 return value is how many bytes were read including the last byte of the 2116 pattern. If *have is less than four, then the pattern has not been found 2117 yet and the return value is len. In the latter case, syncsearch() can be 2118 called again with more data and the *have state. *have is initialized to 2119 zero for the first call. 2120 */ 2121 local unsigned 2122 syncsearch(unsigned FAR *have, unsigned char FAR *buf, unsigned len) 2123 { 2124 unsigned got; 2125 unsigned next; 2126 2127 got = *have; 2128 next = 0; 2129 while (next < len && got < 4) { 2130 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 2131 got++; 2132 else if (buf[next]) 2133 got = 0; 2134 else 2135 got = 4 - got; 2136 next++; 2137 } 2138 *have = got; 2139 return next; 2140 } 2141 2142 int ZEXPORT 2143 inflateSync(z_streamp strm) 2144 { 2145 unsigned len; /* number of bytes to look at or looked at */ 2146 unsigned long in, out; /* temporary to save total_in and total_out */ 2147 unsigned char buf[4]; /* to restore bit buffer to byte string */ 2148 struct inflate_state FAR *state; 2149 2150 /* check parameters */ 2151 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 2152 state = (struct inflate_state FAR *)(void *)strm->state; 2153 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 2154 2155 /* if first time, start search in bit buffer */ 2156 if (state->mode != SYNC) { 2157 state->mode = SYNC; 2158 state->hold <<= state->bits & 7; 2159 state->bits -= state->bits & 7; 2160 len = 0; 2161 while (state->bits >= 8) { 2162 buf[len++] = (unsigned char)(state->hold); 2163 state->hold >>= 8; 2164 state->bits -= 8; 2165 } 2166 state->have = 0; 2167 syncsearch(&(state->have), buf, len); 2168 } 2169 2170 /* search available input */ 2171 len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 2172 strm->avail_in -= len; 2173 strm->next_in += len; 2174 strm->total_in += len; 2175 2176 /* return no joy or set up to restart inflate() on a new block */ 2177 if (state->have != 4) return Z_DATA_ERROR; 2178 in = strm->total_in; out = strm->total_out; 2179 inflateReset(strm); 2180 strm->total_in = in; strm->total_out = out; 2181 state->mode = TYPE; 2182 return Z_OK; 2183 } 2184 2185 /* 2186 Returns true if inflate is currently at the end of a block generated by 2187 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 2188 implementation to provide an additional safety check. PPP uses 2189 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 2190 block. When decompressing, PPP checks that at the end of input packet, 2191 inflate is waiting for these length bytes. 2192 */ 2193 int ZEXPORT 2194 inflateSyncPoint(z_streamp strm) 2195 { 2196 struct inflate_state FAR *state; 2197 2198 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 2199 state = (struct inflate_state FAR *)(void *)strm->state; 2200 return state->mode == STORED && state->bits == 0; 2201 } 2202 2203 int ZEXPORT 2204 inflateCopy(z_streamp dest, z_streamp source) 2205 { 2206 struct inflate_state FAR *state; 2207 struct inflate_state FAR *copy; 2208 unsigned char FAR *window; 2209 unsigned wsize; 2210 2211 /* check input */ 2212 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 2213 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 2214 return Z_STREAM_ERROR; 2215 state = (struct inflate_state FAR *)(void *)source->state; 2216 2217 /* allocate space */ 2218 copy = (struct inflate_state FAR *) 2219 ZALLOC(source, 1, sizeof(struct inflate_state)); 2220 if (copy == Z_NULL) return Z_MEM_ERROR; 2221 window = Z_NULL; 2222 if (state->window != Z_NULL) { 2223 window = (unsigned char FAR *) 2224 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 2225 if (window == Z_NULL) { 2226 ZFREE(source, copy); 2227 return Z_MEM_ERROR; 2228 } 2229 } 2230 2231 /* copy state */ 2232 zmemcpy(dest, source, sizeof(z_stream)); 2233 zmemcpy(copy, state, sizeof(struct inflate_state)); 2234 if (state->lencode >= state->codes && 2235 state->lencode <= state->codes + ENOUGH - 1) { 2236 copy->lencode = copy->codes + (state->lencode - state->codes); 2237 copy->distcode = copy->codes + (state->distcode - state->codes); 2238 } 2239 copy->next = copy->codes + (state->next - state->codes); 2240 if (window != Z_NULL) { 2241 wsize = 1U << state->wbits; 2242 zmemcpy(window, state->window, wsize); 2243 } 2244 copy->window = window; 2245 dest->state = (struct internal_state FAR *)copy; 2246 return Z_OK; 2247 } 2248