[acc25ee] | 1 | /* |
---|
| 2 | * This file is derived from various .h and .c files from the zlib-0.95 |
---|
| 3 | * distribution by Jean-loup Gailly and Mark Adler, with some additions |
---|
| 4 | * by Paul Mackerras to aid in implementing Deflate compression and |
---|
| 5 | * decompression for PPP packets. See zlib.h for conditions of |
---|
| 6 | * distribution and use. |
---|
| 7 | * |
---|
| 8 | * Changes that have been made include: |
---|
| 9 | * - changed functions not used outside this file to "local" |
---|
| 10 | * - added minCompression parameter to deflateInit2 |
---|
| 11 | * - added Z_PACKET_FLUSH (see zlib.h for details) |
---|
| 12 | * - added inflateIncomp |
---|
| 13 | * |
---|
| 14 | * $Id$ |
---|
| 15 | */ |
---|
| 16 | |
---|
| 17 | /*+++++*/ |
---|
| 18 | /* zutil.h -- internal interface and configuration of the compression library |
---|
| 19 | * Copyright (C) 1995 Jean-loup Gailly. |
---|
| 20 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 21 | */ |
---|
| 22 | |
---|
| 23 | /* WARNING: this file should *not* be used by applications. It is |
---|
| 24 | part of the implementation of the compression library and is |
---|
| 25 | subject to change. Applications should only use zlib.h. |
---|
| 26 | */ |
---|
| 27 | |
---|
| 28 | /* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */ |
---|
| 29 | |
---|
| 30 | #define _Z_UTIL_H |
---|
| 31 | |
---|
| 32 | #include "zlib.h" |
---|
| 33 | |
---|
| 34 | #ifndef local |
---|
| 35 | # define local static |
---|
| 36 | #endif |
---|
| 37 | /* compile with -Dlocal if your debugger can't find static symbols */ |
---|
| 38 | |
---|
| 39 | #define FAR |
---|
| 40 | |
---|
| 41 | typedef unsigned char uch; |
---|
| 42 | typedef uch FAR uchf; |
---|
| 43 | typedef unsigned short ush; |
---|
| 44 | typedef ush FAR ushf; |
---|
| 45 | typedef unsigned long ulg; |
---|
| 46 | |
---|
| 47 | extern char *z_errmsg[]; /* indexed by 1-zlib_error */ |
---|
| 48 | |
---|
| 49 | #define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err) |
---|
| 50 | /* To be used only when the state is known to be valid */ |
---|
| 51 | |
---|
| 52 | #ifndef NULL |
---|
| 53 | #define NULL ((void *) 0) |
---|
| 54 | #endif |
---|
| 55 | |
---|
| 56 | /* common constants */ |
---|
| 57 | |
---|
| 58 | #define DEFLATED 8 |
---|
| 59 | |
---|
| 60 | #ifndef DEF_WBITS |
---|
| 61 | # define DEF_WBITS MAX_WBITS |
---|
| 62 | #endif |
---|
| 63 | /* default windowBits for decompression. MAX_WBITS is for compression only */ |
---|
| 64 | |
---|
| 65 | #if MAX_MEM_LEVEL >= 8 |
---|
| 66 | # define DEF_MEM_LEVEL 8 |
---|
| 67 | #else |
---|
| 68 | # define DEF_MEM_LEVEL MAX_MEM_LEVEL |
---|
| 69 | #endif |
---|
| 70 | /* default memLevel */ |
---|
| 71 | |
---|
| 72 | #define STORED_BLOCK 0 |
---|
| 73 | #define STATIC_TREES 1 |
---|
| 74 | #define DYN_TREES 2 |
---|
| 75 | /* The three kinds of block type */ |
---|
| 76 | |
---|
| 77 | #define MIN_MATCH 3 |
---|
| 78 | #define MAX_MATCH 258 |
---|
| 79 | /* The minimum and maximum match lengths */ |
---|
| 80 | |
---|
| 81 | /* functions */ |
---|
| 82 | |
---|
| 83 | #include <string.h> |
---|
| 84 | #define zmemcpy memcpy |
---|
| 85 | #define zmemzero(dest, len) memset(dest, 0, len) |
---|
| 86 | |
---|
| 87 | /* Diagnostic functions */ |
---|
| 88 | #ifdef DEBUG_ZLIB |
---|
| 89 | # include <stdio.h> |
---|
| 90 | # ifndef verbose |
---|
| 91 | # define verbose 0 |
---|
| 92 | # endif |
---|
| 93 | # define Assert(cond, msg) {if(!(cond)) Trace(msg);} |
---|
| 94 | # define Trace(x) printk(x) |
---|
| 95 | # define Tracev(x) {if (verbose) printk x ;} |
---|
| 96 | # define Tracevv(x) {if (verbose>1) printk x ;} |
---|
| 97 | # define Tracec(c,x) {if (verbose && (c)) printk x ;} |
---|
| 98 | # define Tracecv(c,x) {if (verbose>1 && (c)) printk x ;} |
---|
| 99 | #else |
---|
| 100 | # define Assert(cond,msg) |
---|
| 101 | # define Trace(x) |
---|
| 102 | # define Tracev(x) |
---|
| 103 | # define Tracevv(x) |
---|
| 104 | # define Tracec(c,x) |
---|
| 105 | # define Tracecv(c,x) |
---|
| 106 | #endif |
---|
| 107 | |
---|
| 108 | |
---|
| 109 | typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len)); |
---|
| 110 | |
---|
| 111 | /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */ |
---|
| 112 | /* void zcfree OF((voidpf opaque, voidpf ptr)); */ |
---|
| 113 | |
---|
| 114 | #define ZALLOC(strm, items, size) \ |
---|
| 115 | (*((strm)->zalloc))((strm)->opaque, (items), (size)) |
---|
| 116 | #define ZFREE(strm, addr, size) \ |
---|
| 117 | (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size)) |
---|
| 118 | #define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);} |
---|
| 119 | |
---|
| 120 | /* deflate.h -- internal compression state |
---|
| 121 | * Copyright (C) 1995 Jean-loup Gailly |
---|
| 122 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 123 | */ |
---|
| 124 | |
---|
| 125 | /* WARNING: this file should *not* be used by applications. It is |
---|
| 126 | part of the implementation of the compression library and is |
---|
| 127 | subject to change. Applications should only use zlib.h. |
---|
| 128 | */ |
---|
| 129 | |
---|
| 130 | /*+++++*/ |
---|
| 131 | /* infblock.h -- header to use infblock.c |
---|
| 132 | * Copyright (C) 1995 Mark Adler |
---|
| 133 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 134 | */ |
---|
| 135 | |
---|
| 136 | /* WARNING: this file should *not* be used by applications. It is |
---|
| 137 | part of the implementation of the compression library and is |
---|
| 138 | subject to change. Applications should only use zlib.h. |
---|
| 139 | */ |
---|
| 140 | |
---|
| 141 | struct inflate_blocks_state; |
---|
| 142 | typedef struct inflate_blocks_state FAR inflate_blocks_statef; |
---|
| 143 | |
---|
| 144 | local inflate_blocks_statef * inflate_blocks_new OF(( |
---|
| 145 | z_stream *z, |
---|
| 146 | check_func c, /* check function */ |
---|
| 147 | uInt w)); /* window size */ |
---|
| 148 | |
---|
| 149 | local int inflate_blocks OF(( |
---|
| 150 | inflate_blocks_statef *, |
---|
| 151 | z_stream *, |
---|
| 152 | int)); /* initial return code */ |
---|
| 153 | |
---|
| 154 | local void inflate_blocks_reset OF(( |
---|
| 155 | inflate_blocks_statef *, |
---|
| 156 | z_stream *, |
---|
| 157 | uLongf *)); /* check value on output */ |
---|
| 158 | |
---|
| 159 | local int inflate_blocks_free OF(( |
---|
| 160 | inflate_blocks_statef *, |
---|
| 161 | z_stream *, |
---|
| 162 | uLongf *)); /* check value on output */ |
---|
| 163 | |
---|
| 164 | local int inflate_addhistory OF(( |
---|
| 165 | inflate_blocks_statef *, |
---|
| 166 | z_stream *)); |
---|
| 167 | |
---|
| 168 | local int inflate_packet_flush OF(( |
---|
| 169 | inflate_blocks_statef *)); |
---|
| 170 | |
---|
| 171 | /*+++++*/ |
---|
| 172 | /* inftrees.h -- header to use inftrees.c |
---|
| 173 | * Copyright (C) 1995 Mark Adler |
---|
| 174 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 175 | */ |
---|
| 176 | |
---|
| 177 | /* WARNING: this file should *not* be used by applications. It is |
---|
| 178 | part of the implementation of the compression library and is |
---|
| 179 | subject to change. Applications should only use zlib.h. |
---|
| 180 | */ |
---|
| 181 | |
---|
| 182 | /* Huffman code lookup table entry--this entry is four bytes for machines |
---|
| 183 | that have 16-bit pointers (e.g. PC's in the small or medium model). */ |
---|
| 184 | |
---|
| 185 | typedef struct inflate_huft_s FAR inflate_huft; |
---|
| 186 | |
---|
| 187 | struct inflate_huft_s { |
---|
| 188 | union { |
---|
| 189 | struct { |
---|
| 190 | Byte Exop; /* number of extra bits or operation */ |
---|
| 191 | Byte Bits; /* number of bits in this code or subcode */ |
---|
| 192 | } what; |
---|
| 193 | uInt Nalloc; /* number of these allocated here */ |
---|
| 194 | Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ |
---|
| 195 | } word; /* 16-bit, 8 bytes for 32-bit machines) */ |
---|
| 196 | union { |
---|
| 197 | uInt Base; /* literal, length base, or distance base */ |
---|
| 198 | inflate_huft *Next; /* pointer to next level of table */ |
---|
| 199 | } more; |
---|
| 200 | }; |
---|
| 201 | |
---|
| 202 | #ifdef DEBUG_ZLIB |
---|
| 203 | local uInt inflate_hufts; |
---|
| 204 | #endif |
---|
| 205 | |
---|
| 206 | local int inflate_trees_bits OF(( |
---|
| 207 | uIntf *, /* 19 code lengths */ |
---|
| 208 | uIntf *, /* bits tree desired/actual depth */ |
---|
| 209 | inflate_huft * FAR *, /* bits tree result */ |
---|
| 210 | z_stream *)); /* for zalloc, zfree functions */ |
---|
| 211 | |
---|
| 212 | local int inflate_trees_dynamic OF(( |
---|
| 213 | uInt, /* number of literal/length codes */ |
---|
| 214 | uInt, /* number of distance codes */ |
---|
| 215 | uIntf *, /* that many (total) code lengths */ |
---|
| 216 | uIntf *, /* literal desired/actual bit depth */ |
---|
| 217 | uIntf *, /* distance desired/actual bit depth */ |
---|
| 218 | inflate_huft * FAR *, /* literal/length tree result */ |
---|
| 219 | inflate_huft * FAR *, /* distance tree result */ |
---|
| 220 | z_stream *)); /* for zalloc, zfree functions */ |
---|
| 221 | |
---|
| 222 | local int inflate_trees_fixed OF(( |
---|
| 223 | uIntf *, /* literal desired/actual bit depth */ |
---|
| 224 | uIntf *, /* distance desired/actual bit depth */ |
---|
| 225 | inflate_huft * FAR *, /* literal/length tree result */ |
---|
| 226 | inflate_huft * FAR *)); /* distance tree result */ |
---|
| 227 | |
---|
| 228 | local int inflate_trees_free OF(( |
---|
| 229 | inflate_huft *, /* tables to free */ |
---|
| 230 | z_stream *)); /* for zfree function */ |
---|
| 231 | |
---|
| 232 | |
---|
| 233 | /*+++++*/ |
---|
| 234 | /* infcodes.h -- header to use infcodes.c |
---|
| 235 | * Copyright (C) 1995 Mark Adler |
---|
| 236 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 237 | */ |
---|
| 238 | |
---|
| 239 | /* WARNING: this file should *not* be used by applications. It is |
---|
| 240 | part of the implementation of the compression library and is |
---|
| 241 | subject to change. Applications should only use zlib.h. |
---|
| 242 | */ |
---|
| 243 | |
---|
| 244 | struct inflate_codes_state; |
---|
| 245 | typedef struct inflate_codes_state FAR inflate_codes_statef; |
---|
| 246 | |
---|
| 247 | local inflate_codes_statef *inflate_codes_new OF(( |
---|
| 248 | uInt, uInt, |
---|
| 249 | inflate_huft *, inflate_huft *, |
---|
| 250 | z_stream *)); |
---|
| 251 | |
---|
| 252 | local int inflate_codes OF(( |
---|
| 253 | inflate_blocks_statef *, |
---|
| 254 | z_stream *, |
---|
| 255 | int)); |
---|
| 256 | |
---|
| 257 | local void inflate_codes_free OF(( |
---|
| 258 | inflate_codes_statef *, |
---|
| 259 | z_stream *)); |
---|
| 260 | |
---|
| 261 | |
---|
| 262 | /*+++++*/ |
---|
| 263 | /* inflate.c -- zlib interface to inflate modules |
---|
| 264 | * Copyright (C) 1995 Mark Adler |
---|
| 265 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 266 | */ |
---|
| 267 | |
---|
| 268 | /* inflate private state */ |
---|
| 269 | struct internal_state { |
---|
| 270 | |
---|
| 271 | /* mode */ |
---|
| 272 | enum { |
---|
| 273 | METHOD, /* waiting for method byte */ |
---|
| 274 | FLAG, /* waiting for flag byte */ |
---|
| 275 | BLOCKS, /* decompressing blocks */ |
---|
| 276 | CHECK4, /* four check bytes to go */ |
---|
| 277 | CHECK3, /* three check bytes to go */ |
---|
| 278 | CHECK2, /* two check bytes to go */ |
---|
| 279 | CHECK1, /* one check byte to go */ |
---|
| 280 | DONE, /* finished check, done */ |
---|
| 281 | BAD} /* got an error--stay here */ |
---|
| 282 | mode; /* current inflate mode */ |
---|
| 283 | |
---|
| 284 | /* mode dependent information */ |
---|
| 285 | union { |
---|
| 286 | uInt method; /* if FLAGS, method byte */ |
---|
| 287 | struct { |
---|
| 288 | uLong was; /* computed check value */ |
---|
| 289 | uLong need; /* stream check value */ |
---|
| 290 | } check; /* if CHECK, check values to compare */ |
---|
| 291 | uInt marker; /* if BAD, inflateSync's marker bytes count */ |
---|
| 292 | } sub; /* submode */ |
---|
| 293 | |
---|
| 294 | /* mode independent information */ |
---|
| 295 | int nowrap; /* flag for no wrapper */ |
---|
| 296 | uInt wbits; /* log2(window size) (8..15, defaults to 15) */ |
---|
| 297 | inflate_blocks_statef |
---|
| 298 | *blocks; /* current inflate_blocks state */ |
---|
| 299 | |
---|
| 300 | }; |
---|
| 301 | |
---|
| 302 | |
---|
| 303 | int inflateReset(z) |
---|
| 304 | z_stream *z; |
---|
| 305 | { |
---|
| 306 | uLong c; |
---|
| 307 | |
---|
| 308 | if (z == Z_NULL || z->state == Z_NULL) |
---|
| 309 | return Z_STREAM_ERROR; |
---|
| 310 | z->total_in = z->total_out = 0; |
---|
| 311 | z->msg = Z_NULL; |
---|
| 312 | z->state->mode = z->state->nowrap ? BLOCKS : METHOD; |
---|
| 313 | inflate_blocks_reset(z->state->blocks, z, &c); |
---|
| 314 | Trace("inflate: reset\n"); |
---|
| 315 | return Z_OK; |
---|
| 316 | } |
---|
| 317 | |
---|
| 318 | |
---|
| 319 | int inflateEnd(z) |
---|
| 320 | z_stream *z; |
---|
| 321 | { |
---|
| 322 | uLong c; |
---|
| 323 | |
---|
| 324 | if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) |
---|
| 325 | return Z_STREAM_ERROR; |
---|
| 326 | if (z->state->blocks != Z_NULL) |
---|
| 327 | inflate_blocks_free(z->state->blocks, z, &c); |
---|
| 328 | ZFREE(z, z->state, sizeof(struct internal_state)); |
---|
| 329 | z->state = Z_NULL; |
---|
| 330 | Trace("inflate: end\n"); |
---|
| 331 | return Z_OK; |
---|
| 332 | } |
---|
| 333 | |
---|
| 334 | |
---|
| 335 | int inflateInit2(z, w) |
---|
| 336 | z_stream *z; |
---|
| 337 | int w; |
---|
| 338 | { |
---|
| 339 | /* initialize state */ |
---|
| 340 | if (z == Z_NULL) |
---|
| 341 | return Z_STREAM_ERROR; |
---|
| 342 | /* if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */ |
---|
| 343 | /* if (z->zfree == Z_NULL) z->zfree = zcfree; */ |
---|
| 344 | if ((z->state = (struct internal_state FAR *) |
---|
| 345 | ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) |
---|
| 346 | return Z_MEM_ERROR; |
---|
| 347 | z->state->blocks = Z_NULL; |
---|
| 348 | |
---|
| 349 | /* handle undocumented nowrap option (no zlib header or check) */ |
---|
| 350 | z->state->nowrap = 0; |
---|
| 351 | if (w < 0) |
---|
| 352 | { |
---|
| 353 | w = - w; |
---|
| 354 | z->state->nowrap = 1; |
---|
| 355 | } |
---|
| 356 | |
---|
| 357 | /* set window size */ |
---|
| 358 | if (w < 8 || w > 15) |
---|
| 359 | { |
---|
| 360 | inflateEnd(z); |
---|
| 361 | return Z_STREAM_ERROR; |
---|
| 362 | } |
---|
| 363 | z->state->wbits = (uInt)w; |
---|
| 364 | |
---|
| 365 | /* create inflate_blocks state */ |
---|
| 366 | if ((z->state->blocks = |
---|
| 367 | inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w)) |
---|
| 368 | == Z_NULL) |
---|
| 369 | { |
---|
| 370 | inflateEnd(z); |
---|
| 371 | return Z_MEM_ERROR; |
---|
| 372 | } |
---|
| 373 | Trace("inflate: allocated\n"); |
---|
| 374 | |
---|
| 375 | /* reset state */ |
---|
| 376 | inflateReset(z); |
---|
| 377 | return Z_OK; |
---|
| 378 | } |
---|
| 379 | |
---|
| 380 | |
---|
| 381 | int inflateInit(z) |
---|
| 382 | z_stream *z; |
---|
| 383 | { |
---|
| 384 | return inflateInit2(z, DEF_WBITS); |
---|
| 385 | } |
---|
| 386 | |
---|
| 387 | |
---|
| 388 | #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} |
---|
| 389 | #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) |
---|
| 390 | |
---|
| 391 | int inflate(z, f) |
---|
| 392 | z_stream *z; |
---|
| 393 | int f; |
---|
| 394 | { |
---|
| 395 | int r; |
---|
| 396 | uInt b; |
---|
| 397 | |
---|
| 398 | if (z == Z_NULL || z->next_in == Z_NULL) |
---|
| 399 | return Z_STREAM_ERROR; |
---|
| 400 | r = Z_BUF_ERROR; |
---|
| 401 | while (1) switch (z->state->mode) |
---|
| 402 | { |
---|
| 403 | case METHOD: |
---|
| 404 | NEEDBYTE |
---|
| 405 | if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED) |
---|
| 406 | { |
---|
| 407 | z->state->mode = BAD; |
---|
| 408 | z->msg = "unknown compression method"; |
---|
| 409 | z->state->sub.marker = 5; /* can't try inflateSync */ |
---|
| 410 | break; |
---|
| 411 | } |
---|
| 412 | if ((z->state->sub.method >> 4) + 8 > z->state->wbits) |
---|
| 413 | { |
---|
| 414 | z->state->mode = BAD; |
---|
| 415 | z->msg = "invalid window size"; |
---|
| 416 | z->state->sub.marker = 5; /* can't try inflateSync */ |
---|
| 417 | break; |
---|
| 418 | } |
---|
| 419 | z->state->mode = FLAG; |
---|
| 420 | case FLAG: |
---|
| 421 | NEEDBYTE |
---|
| 422 | if ((b = NEXTBYTE) & 0x20) |
---|
| 423 | { |
---|
| 424 | z->state->mode = BAD; |
---|
| 425 | z->msg = "invalid reserved bit"; |
---|
| 426 | z->state->sub.marker = 5; /* can't try inflateSync */ |
---|
| 427 | break; |
---|
| 428 | } |
---|
| 429 | if (((z->state->sub.method << 8) + b) % 31) |
---|
| 430 | { |
---|
| 431 | z->state->mode = BAD; |
---|
| 432 | z->msg = "incorrect header check"; |
---|
| 433 | z->state->sub.marker = 5; /* can't try inflateSync */ |
---|
| 434 | break; |
---|
| 435 | } |
---|
| 436 | Trace("inflate: zlib header ok\n"); |
---|
| 437 | z->state->mode = BLOCKS; |
---|
| 438 | case BLOCKS: |
---|
| 439 | r = inflate_blocks(z->state->blocks, z, r); |
---|
| 440 | if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) |
---|
| 441 | r = inflate_packet_flush(z->state->blocks); |
---|
| 442 | if (r == Z_DATA_ERROR) |
---|
| 443 | { |
---|
| 444 | z->state->mode = BAD; |
---|
| 445 | z->state->sub.marker = 0; /* can try inflateSync */ |
---|
| 446 | break; |
---|
| 447 | } |
---|
| 448 | if (r != Z_STREAM_END) |
---|
| 449 | return r; |
---|
| 450 | r = Z_OK; |
---|
| 451 | inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); |
---|
| 452 | if (z->state->nowrap) |
---|
| 453 | { |
---|
| 454 | z->state->mode = DONE; |
---|
| 455 | break; |
---|
| 456 | } |
---|
| 457 | z->state->mode = CHECK4; |
---|
| 458 | case CHECK4: |
---|
| 459 | NEEDBYTE |
---|
| 460 | z->state->sub.check.need = (uLong)NEXTBYTE << 24; |
---|
| 461 | z->state->mode = CHECK3; |
---|
| 462 | case CHECK3: |
---|
| 463 | NEEDBYTE |
---|
| 464 | z->state->sub.check.need += (uLong)NEXTBYTE << 16; |
---|
| 465 | z->state->mode = CHECK2; |
---|
| 466 | case CHECK2: |
---|
| 467 | NEEDBYTE |
---|
| 468 | z->state->sub.check.need += (uLong)NEXTBYTE << 8; |
---|
| 469 | z->state->mode = CHECK1; |
---|
| 470 | case CHECK1: |
---|
| 471 | NEEDBYTE |
---|
| 472 | z->state->sub.check.need += (uLong)NEXTBYTE; |
---|
| 473 | |
---|
| 474 | if (z->state->sub.check.was != z->state->sub.check.need) |
---|
| 475 | { |
---|
| 476 | z->state->mode = BAD; |
---|
| 477 | z->msg = "incorrect data check"; |
---|
| 478 | z->state->sub.marker = 5; /* can't try inflateSync */ |
---|
| 479 | break; |
---|
| 480 | } |
---|
| 481 | Trace( "inflate: zlib check ok\n"); |
---|
| 482 | z->state->mode = DONE; |
---|
| 483 | case DONE: |
---|
| 484 | return Z_STREAM_END; |
---|
| 485 | case BAD: |
---|
| 486 | return Z_DATA_ERROR; |
---|
| 487 | default: |
---|
| 488 | return Z_STREAM_ERROR; |
---|
| 489 | } |
---|
| 490 | |
---|
| 491 | empty: |
---|
| 492 | if (f != Z_PACKET_FLUSH) |
---|
| 493 | return r; |
---|
| 494 | z->state->mode = BAD; |
---|
| 495 | z->state->sub.marker = 0; /* can try inflateSync */ |
---|
| 496 | return Z_DATA_ERROR; |
---|
| 497 | } |
---|
| 498 | |
---|
| 499 | /* |
---|
| 500 | * This subroutine adds the data at next_in/avail_in to the output history |
---|
| 501 | * without performing any output. The output buffer must be "caught up"; |
---|
| 502 | * i.e. no pending output (hence s->read equals s->write), and the state must |
---|
| 503 | * be BLOCKS (i.e. we should be willing to see the start of a series of |
---|
| 504 | * BLOCKS). On exit, the output will also be caught up, and the checksum |
---|
| 505 | * will have been updated if need be. |
---|
| 506 | */ |
---|
| 507 | |
---|
| 508 | int inflateIncomp(z) |
---|
| 509 | z_stream *z; |
---|
| 510 | { |
---|
| 511 | if (z->state->mode != BLOCKS) |
---|
| 512 | return Z_DATA_ERROR; |
---|
| 513 | return inflate_addhistory(z->state->blocks, z); |
---|
| 514 | } |
---|
| 515 | |
---|
| 516 | |
---|
| 517 | int inflateSync(z) |
---|
| 518 | z_stream *z; |
---|
| 519 | { |
---|
| 520 | uInt n; /* number of bytes to look at */ |
---|
| 521 | Bytef *p; /* pointer to bytes */ |
---|
| 522 | uInt m; /* number of marker bytes found in a row */ |
---|
| 523 | uLong r, w; /* temporaries to save total_in and total_out */ |
---|
| 524 | |
---|
| 525 | /* set up */ |
---|
| 526 | if (z == Z_NULL || z->state == Z_NULL) |
---|
| 527 | return Z_STREAM_ERROR; |
---|
| 528 | if (z->state->mode != BAD) |
---|
| 529 | { |
---|
| 530 | z->state->mode = BAD; |
---|
| 531 | z->state->sub.marker = 0; |
---|
| 532 | } |
---|
| 533 | if ((n = z->avail_in) == 0) |
---|
| 534 | return Z_BUF_ERROR; |
---|
| 535 | p = z->next_in; |
---|
| 536 | m = z->state->sub.marker; |
---|
| 537 | |
---|
| 538 | /* search */ |
---|
| 539 | while (n && m < 4) |
---|
| 540 | { |
---|
| 541 | if (*p == (Byte)(m < 2 ? 0 : 0xff)) |
---|
| 542 | m++; |
---|
| 543 | else if (*p) |
---|
| 544 | m = 0; |
---|
| 545 | else |
---|
| 546 | m = 4 - m; |
---|
| 547 | p++, n--; |
---|
| 548 | } |
---|
| 549 | |
---|
| 550 | /* restore */ |
---|
| 551 | z->total_in += p - z->next_in; |
---|
| 552 | z->next_in = p; |
---|
| 553 | z->avail_in = n; |
---|
| 554 | z->state->sub.marker = m; |
---|
| 555 | |
---|
| 556 | /* return no joy or set up to restart on a new block */ |
---|
| 557 | if (m != 4) |
---|
| 558 | return Z_DATA_ERROR; |
---|
| 559 | r = z->total_in; w = z->total_out; |
---|
| 560 | inflateReset(z); |
---|
| 561 | z->total_in = r; z->total_out = w; |
---|
| 562 | z->state->mode = BLOCKS; |
---|
| 563 | return Z_OK; |
---|
| 564 | } |
---|
| 565 | |
---|
| 566 | #undef NEEDBYTE |
---|
| 567 | #undef NEXTBYTE |
---|
| 568 | |
---|
| 569 | /*+++++*/ |
---|
| 570 | /* infutil.h -- types and macros common to blocks and codes |
---|
| 571 | * Copyright (C) 1995 Mark Adler |
---|
| 572 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 573 | */ |
---|
| 574 | |
---|
| 575 | /* WARNING: this file should *not* be used by applications. It is |
---|
| 576 | part of the implementation of the compression library and is |
---|
| 577 | subject to change. Applications should only use zlib.h. |
---|
| 578 | */ |
---|
| 579 | |
---|
| 580 | /* inflate blocks semi-private state */ |
---|
| 581 | struct inflate_blocks_state { |
---|
| 582 | |
---|
| 583 | /* mode */ |
---|
| 584 | enum { |
---|
| 585 | TYPE, /* get type bits (3, including end bit) */ |
---|
| 586 | LENS, /* get lengths for stored */ |
---|
| 587 | STORED, /* processing stored block */ |
---|
| 588 | TABLE, /* get table lengths */ |
---|
| 589 | BTREE, /* get bit lengths tree for a dynamic block */ |
---|
| 590 | DTREE, /* get length, distance trees for a dynamic block */ |
---|
| 591 | CODES, /* processing fixed or dynamic block */ |
---|
| 592 | DRY, /* output remaining window bytes */ |
---|
| 593 | DONEB, /* finished last block, done */ |
---|
| 594 | BADB} /* got a data error--stuck here */ |
---|
| 595 | mode; /* current inflate_block mode */ |
---|
| 596 | |
---|
| 597 | /* mode dependent information */ |
---|
| 598 | union { |
---|
| 599 | uInt left; /* if STORED, bytes left to copy */ |
---|
| 600 | struct { |
---|
| 601 | uInt table; /* table lengths (14 bits) */ |
---|
| 602 | uInt index; /* index into blens (or border) */ |
---|
| 603 | uIntf *blens; /* bit lengths of codes */ |
---|
| 604 | uInt bb; /* bit length tree depth */ |
---|
| 605 | inflate_huft *tb; /* bit length decoding tree */ |
---|
| 606 | int nblens; /* # elements allocated at blens */ |
---|
| 607 | } trees; /* if DTREE, decoding info for trees */ |
---|
| 608 | struct { |
---|
| 609 | inflate_huft *tl, *td; /* trees to free */ |
---|
| 610 | inflate_codes_statef |
---|
| 611 | *codes; |
---|
| 612 | } decode; /* if CODES, current state */ |
---|
| 613 | } sub; /* submode */ |
---|
| 614 | uInt last; /* true if this block is the last block */ |
---|
| 615 | |
---|
| 616 | /* mode independent information */ |
---|
| 617 | uInt bitk; /* bits in bit buffer */ |
---|
| 618 | uLong bitb; /* bit buffer */ |
---|
| 619 | Bytef *window; /* sliding window */ |
---|
| 620 | Bytef *end; /* one byte after sliding window */ |
---|
| 621 | Bytef *read; /* window read pointer */ |
---|
| 622 | Bytef *write; /* window write pointer */ |
---|
| 623 | check_func checkfn; /* check function */ |
---|
| 624 | uLong check; /* check on output */ |
---|
| 625 | |
---|
| 626 | }; |
---|
| 627 | |
---|
| 628 | |
---|
| 629 | /* defines for inflate input/output */ |
---|
| 630 | /* update pointers and return */ |
---|
| 631 | #define UPDBITS {s->bitb=b;s->bitk=k;} |
---|
| 632 | #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} |
---|
| 633 | #define UPDOUT {s->write=q;} |
---|
| 634 | #define UPDATE {UPDBITS UPDIN UPDOUT} |
---|
| 635 | #define LEAVE {UPDATE return inflate_flush(s,z,r);} |
---|
| 636 | /* get bytes and bits */ |
---|
| 637 | #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} |
---|
| 638 | #define NEEDBYTE {if(n)r=Z_OK;else LEAVE} |
---|
| 639 | #define NEXTBYTE (n--,*p++) |
---|
| 640 | #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} |
---|
| 641 | #define DUMPBITS(j) {b>>=(j);k-=(j);} |
---|
| 642 | /* output bytes */ |
---|
| 643 | #define WAVAIL (q<s->read?s->read-q-1:s->end-q) |
---|
| 644 | #define LOADOUT {q=s->write;m=WAVAIL;} |
---|
| 645 | #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}} |
---|
| 646 | #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} |
---|
| 647 | #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;} |
---|
| 648 | #define OUTBYTE(a) {*q++=(Byte)(a);m--;} |
---|
| 649 | /* load local pointers */ |
---|
| 650 | #define LOAD {LOADIN LOADOUT} |
---|
| 651 | |
---|
| 652 | /* And'ing with mask[n] masks the lower n bits */ |
---|
| 653 | local uInt inflate_mask[] = { |
---|
| 654 | 0x0000, |
---|
| 655 | 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, |
---|
| 656 | 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff |
---|
| 657 | }; |
---|
| 658 | |
---|
| 659 | /* copy as much as possible from the sliding window to the output area */ |
---|
| 660 | local int inflate_flush OF(( |
---|
| 661 | inflate_blocks_statef *, |
---|
| 662 | z_stream *, |
---|
| 663 | int)); |
---|
| 664 | |
---|
| 665 | /*+++++*/ |
---|
| 666 | /* inffast.h -- header to use inffast.c |
---|
| 667 | * Copyright (C) 1995 Mark Adler |
---|
| 668 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 669 | */ |
---|
| 670 | |
---|
| 671 | /* WARNING: this file should *not* be used by applications. It is |
---|
| 672 | part of the implementation of the compression library and is |
---|
| 673 | subject to change. Applications should only use zlib.h. |
---|
| 674 | */ |
---|
| 675 | |
---|
| 676 | local int inflate_fast OF(( |
---|
| 677 | uInt, |
---|
| 678 | uInt, |
---|
| 679 | inflate_huft *, |
---|
| 680 | inflate_huft *, |
---|
| 681 | inflate_blocks_statef *, |
---|
| 682 | z_stream *)); |
---|
| 683 | |
---|
| 684 | |
---|
| 685 | /*+++++*/ |
---|
| 686 | /* infblock.c -- interpret and process block types to last block |
---|
| 687 | * Copyright (C) 1995 Mark Adler |
---|
| 688 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 689 | */ |
---|
| 690 | |
---|
| 691 | /* Table for deflate from PKZIP's appnote.txt. */ |
---|
| 692 | local uInt border[] = { /* Order of the bit length code lengths */ |
---|
| 693 | 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; |
---|
| 694 | |
---|
| 695 | /* |
---|
| 696 | Notes beyond the 1.93a appnote.txt: |
---|
| 697 | |
---|
| 698 | 1. Distance pointers never point before the beginning of the output |
---|
| 699 | stream. |
---|
| 700 | 2. Distance pointers can point back across blocks, up to 32k away. |
---|
| 701 | 3. There is an implied maximum of 7 bits for the bit length table and |
---|
| 702 | 15 bits for the actual data. |
---|
| 703 | 4. If only one code exists, then it is encoded using one bit. (Zero |
---|
| 704 | would be more efficient, but perhaps a little confusing.) If two |
---|
| 705 | codes exist, they are coded using one bit each (0 and 1). |
---|
| 706 | 5. There is no way of sending zero distance codes--a dummy must be |
---|
| 707 | sent if there are none. (History: a pre 2.0 version of PKZIP would |
---|
| 708 | store blocks with no distance codes, but this was discovered to be |
---|
| 709 | too harsh a criterion.) Valid only for 1.93a. 2.04c does allow |
---|
| 710 | zero distance codes, which is sent as one code of zero bits in |
---|
| 711 | length. |
---|
| 712 | 6. There are up to 286 literal/length codes. Code 256 represents the |
---|
| 713 | end-of-block. Note however that the static length tree defines |
---|
| 714 | 288 codes just to fill out the Huffman codes. Codes 286 and 287 |
---|
| 715 | cannot be used though, since there is no length base or extra bits |
---|
| 716 | defined for them. Similarily, there are up to 30 distance codes. |
---|
| 717 | However, static trees define 32 codes (all 5 bits) to fill out the |
---|
| 718 | Huffman codes, but the last two had better not show up in the data. |
---|
| 719 | 7. Unzip can check dynamic Huffman blocks for complete code sets. |
---|
| 720 | The exception is that a single code would not be complete (see #4). |
---|
| 721 | 8. The five bits following the block type is really the number of |
---|
| 722 | literal codes sent minus 257. |
---|
| 723 | 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits |
---|
| 724 | (1+6+6). Therefore, to output three times the length, you output |
---|
| 725 | three codes (1+1+1), whereas to output four times the same length, |
---|
| 726 | you only need two codes (1+3). Hmm. |
---|
| 727 | 10. In the tree reconstruction algorithm, Code = Code + Increment |
---|
| 728 | only if BitLength(i) is not zero. (Pretty obvious.) |
---|
| 729 | 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) |
---|
| 730 | 12. Note: length code 284 can represent 227-258, but length code 285 |
---|
| 731 | really is 258. The last length deserves its own, short code |
---|
| 732 | since it gets used a lot in very redundant files. The length |
---|
| 733 | 258 is special since 258 - 3 (the min match length) is 255. |
---|
| 734 | 13. The literal/length and distance code bit lengths are read as a |
---|
| 735 | single stream of lengths. It is possible (and advantageous) for |
---|
| 736 | a repeat code (16, 17, or 18) to go across the boundary between |
---|
| 737 | the two sets of lengths. |
---|
| 738 | */ |
---|
| 739 | |
---|
| 740 | |
---|
| 741 | local void inflate_blocks_reset(s, z, c) |
---|
| 742 | inflate_blocks_statef *s; |
---|
| 743 | z_stream *z; |
---|
| 744 | uLongf *c; |
---|
| 745 | { |
---|
| 746 | if (s->checkfn != Z_NULL) |
---|
| 747 | *c = s->check; |
---|
| 748 | if (s->mode == BTREE || s->mode == DTREE) |
---|
| 749 | ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt)); |
---|
| 750 | if (s->mode == CODES) |
---|
| 751 | { |
---|
| 752 | inflate_codes_free(s->sub.decode.codes, z); |
---|
| 753 | inflate_trees_free(s->sub.decode.td, z); |
---|
| 754 | inflate_trees_free(s->sub.decode.tl, z); |
---|
| 755 | } |
---|
| 756 | s->mode = TYPE; |
---|
| 757 | s->bitk = 0; |
---|
| 758 | s->bitb = 0; |
---|
| 759 | s->read = s->write = s->window; |
---|
| 760 | if (s->checkfn != Z_NULL) |
---|
| 761 | s->check = (*s->checkfn)(0L, Z_NULL, 0); |
---|
| 762 | Trace("inflate: blocks reset\n"); |
---|
| 763 | } |
---|
| 764 | |
---|
| 765 | |
---|
| 766 | local inflate_blocks_statef *inflate_blocks_new(z, c, w) |
---|
| 767 | z_stream *z; |
---|
| 768 | check_func c; |
---|
| 769 | uInt w; |
---|
| 770 | { |
---|
| 771 | inflate_blocks_statef *s; |
---|
| 772 | |
---|
| 773 | if ((s = (inflate_blocks_statef *)ZALLOC |
---|
| 774 | (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) |
---|
| 775 | return s; |
---|
| 776 | if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) |
---|
| 777 | { |
---|
| 778 | ZFREE(z, s, sizeof(struct inflate_blocks_state)); |
---|
| 779 | return Z_NULL; |
---|
| 780 | } |
---|
| 781 | s->end = s->window + w; |
---|
| 782 | s->checkfn = c; |
---|
| 783 | s->mode = TYPE; |
---|
| 784 | Trace("inflate: blocks allocated\n"); |
---|
| 785 | inflate_blocks_reset(s, z, &s->check); |
---|
| 786 | return s; |
---|
| 787 | } |
---|
| 788 | |
---|
| 789 | |
---|
| 790 | local int inflate_blocks(s, z, r) |
---|
| 791 | inflate_blocks_statef *s; |
---|
| 792 | z_stream *z; |
---|
| 793 | int r; |
---|
| 794 | { |
---|
| 795 | uInt t; /* temporary storage */ |
---|
| 796 | uLong b; /* bit buffer */ |
---|
| 797 | uInt k; /* bits in bit buffer */ |
---|
| 798 | Bytef *p; /* input data pointer */ |
---|
| 799 | uInt n; /* bytes available there */ |
---|
| 800 | Bytef *q; /* output window write pointer */ |
---|
| 801 | uInt m; /* bytes to end of window or read pointer */ |
---|
| 802 | |
---|
| 803 | /* copy input/output information to locals (UPDATE macro restores) */ |
---|
| 804 | LOAD |
---|
| 805 | |
---|
| 806 | /* process input based on current state */ |
---|
| 807 | while (1) switch (s->mode) |
---|
| 808 | { |
---|
| 809 | case TYPE: |
---|
| 810 | NEEDBITS(3) |
---|
| 811 | t = (uInt)b & 7; |
---|
| 812 | s->last = t & 1; |
---|
| 813 | switch (t >> 1) |
---|
| 814 | { |
---|
| 815 | case 0: /* stored */ |
---|
| 816 | Trace(("inflate: stored block%s\n", |
---|
| 817 | s->last ? " (last)" : "")); |
---|
| 818 | DUMPBITS(3) |
---|
| 819 | t = k & 7; /* go to byte boundary */ |
---|
| 820 | DUMPBITS(t) |
---|
| 821 | s->mode = LENS; /* get length of stored block */ |
---|
| 822 | break; |
---|
| 823 | case 1: /* fixed */ |
---|
| 824 | Trace(( "inflate: fixed codes block%s\n", |
---|
| 825 | s->last ? " (last)" : "")); |
---|
| 826 | { |
---|
| 827 | uInt bl, bd; |
---|
| 828 | inflate_huft *tl, *td; |
---|
| 829 | |
---|
| 830 | inflate_trees_fixed(&bl, &bd, &tl, &td); |
---|
| 831 | s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); |
---|
| 832 | if (s->sub.decode.codes == Z_NULL) |
---|
| 833 | { |
---|
| 834 | r = Z_MEM_ERROR; |
---|
| 835 | LEAVE |
---|
| 836 | } |
---|
| 837 | s->sub.decode.tl = Z_NULL; /* don't try to free these */ |
---|
| 838 | s->sub.decode.td = Z_NULL; |
---|
| 839 | } |
---|
| 840 | DUMPBITS(3) |
---|
| 841 | s->mode = CODES; |
---|
| 842 | break; |
---|
| 843 | case 2: /* dynamic */ |
---|
| 844 | Trace(( "inflate: dynamic codes block%s\n", |
---|
| 845 | s->last ? " (last)" : "")); |
---|
| 846 | DUMPBITS(3) |
---|
| 847 | s->mode = TABLE; |
---|
| 848 | break; |
---|
| 849 | case 3: /* illegal */ |
---|
| 850 | DUMPBITS(3) |
---|
| 851 | s->mode = BADB; |
---|
| 852 | z->msg = "invalid block type"; |
---|
| 853 | r = Z_DATA_ERROR; |
---|
| 854 | LEAVE |
---|
| 855 | } |
---|
| 856 | break; |
---|
| 857 | case LENS: |
---|
| 858 | NEEDBITS(32) |
---|
| 859 | if (((~b) >> 16) != (b & 0xffff)) |
---|
| 860 | { |
---|
| 861 | s->mode = BADB; |
---|
| 862 | z->msg = "invalid stored block lengths"; |
---|
| 863 | r = Z_DATA_ERROR; |
---|
| 864 | LEAVE |
---|
| 865 | } |
---|
| 866 | s->sub.left = (uInt)b & 0xffff; |
---|
| 867 | b = k = 0; /* dump bits */ |
---|
| 868 | Tracev(( "inflate: stored length %u\n", s->sub.left)); |
---|
| 869 | s->mode = s->sub.left ? STORED : TYPE; |
---|
| 870 | break; |
---|
| 871 | case STORED: |
---|
| 872 | if (n == 0) |
---|
| 873 | LEAVE |
---|
| 874 | NEEDOUT |
---|
| 875 | t = s->sub.left; |
---|
| 876 | if (t > n) t = n; |
---|
| 877 | if (t > m) t = m; |
---|
| 878 | zmemcpy(q, p, t); |
---|
| 879 | p += t; n -= t; |
---|
| 880 | q += t; m -= t; |
---|
| 881 | if ((s->sub.left -= t) != 0) |
---|
| 882 | break; |
---|
| 883 | Tracev(( "inflate: stored end, %lu total out\n", |
---|
| 884 | z->total_out + (q >= s->read ? q - s->read : |
---|
| 885 | (s->end - s->read) + (q - s->window)))); |
---|
| 886 | s->mode = s->last ? DRY : TYPE; |
---|
| 887 | break; |
---|
| 888 | case TABLE: |
---|
| 889 | NEEDBITS(14) |
---|
| 890 | s->sub.trees.table = t = (uInt)b & 0x3fff; |
---|
| 891 | #ifndef PKZIP_BUG_WORKAROUND |
---|
| 892 | if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) |
---|
| 893 | { |
---|
| 894 | s->mode = BADB; |
---|
| 895 | z->msg = "too many length or distance symbols"; |
---|
| 896 | r = Z_DATA_ERROR; |
---|
| 897 | LEAVE |
---|
| 898 | } |
---|
| 899 | #endif |
---|
| 900 | t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); |
---|
| 901 | if (t < 19) |
---|
| 902 | t = 19; |
---|
| 903 | if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) |
---|
| 904 | { |
---|
| 905 | r = Z_MEM_ERROR; |
---|
| 906 | LEAVE |
---|
| 907 | } |
---|
| 908 | s->sub.trees.nblens = t; |
---|
| 909 | DUMPBITS(14) |
---|
| 910 | s->sub.trees.index = 0; |
---|
| 911 | Tracev(( "inflate: table sizes ok\n")); |
---|
| 912 | s->mode = BTREE; |
---|
| 913 | case BTREE: |
---|
| 914 | while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) |
---|
| 915 | { |
---|
| 916 | NEEDBITS(3) |
---|
| 917 | s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; |
---|
| 918 | DUMPBITS(3) |
---|
| 919 | } |
---|
| 920 | while (s->sub.trees.index < 19) |
---|
| 921 | s->sub.trees.blens[border[s->sub.trees.index++]] = 0; |
---|
| 922 | s->sub.trees.bb = 7; |
---|
| 923 | t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, |
---|
| 924 | &s->sub.trees.tb, z); |
---|
| 925 | if (t != Z_OK) |
---|
| 926 | { |
---|
| 927 | r = t; |
---|
| 928 | if (r == Z_DATA_ERROR) |
---|
| 929 | s->mode = BADB; |
---|
| 930 | LEAVE |
---|
| 931 | } |
---|
| 932 | s->sub.trees.index = 0; |
---|
| 933 | Tracev(( "inflate: bits tree ok\n")); |
---|
| 934 | s->mode = DTREE; |
---|
| 935 | case DTREE: |
---|
| 936 | while (t = s->sub.trees.table, |
---|
| 937 | s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) |
---|
| 938 | { |
---|
| 939 | inflate_huft *h; |
---|
| 940 | uInt i, j, c; |
---|
| 941 | |
---|
| 942 | t = s->sub.trees.bb; |
---|
| 943 | NEEDBITS(t) |
---|
| 944 | h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); |
---|
| 945 | t = h->word.what.Bits; |
---|
| 946 | c = h->more.Base; |
---|
| 947 | if (c < 16) |
---|
| 948 | { |
---|
| 949 | DUMPBITS(t) |
---|
| 950 | s->sub.trees.blens[s->sub.trees.index++] = c; |
---|
| 951 | } |
---|
| 952 | else /* c == 16..18 */ |
---|
| 953 | { |
---|
| 954 | i = c == 18 ? 7 : c - 14; |
---|
| 955 | j = c == 18 ? 11 : 3; |
---|
| 956 | NEEDBITS(t + i) |
---|
| 957 | DUMPBITS(t) |
---|
| 958 | j += (uInt)b & inflate_mask[i]; |
---|
| 959 | DUMPBITS(i) |
---|
| 960 | i = s->sub.trees.index; |
---|
| 961 | t = s->sub.trees.table; |
---|
| 962 | if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || |
---|
| 963 | (c == 16 && i < 1)) |
---|
| 964 | { |
---|
| 965 | s->mode = BADB; |
---|
| 966 | z->msg = "invalid bit length repeat"; |
---|
| 967 | r = Z_DATA_ERROR; |
---|
| 968 | LEAVE |
---|
| 969 | } |
---|
| 970 | c = c == 16 ? s->sub.trees.blens[i - 1] : 0; |
---|
| 971 | do { |
---|
| 972 | s->sub.trees.blens[i++] = c; |
---|
| 973 | } while (--j); |
---|
| 974 | s->sub.trees.index = i; |
---|
| 975 | } |
---|
| 976 | } |
---|
| 977 | inflate_trees_free(s->sub.trees.tb, z); |
---|
| 978 | s->sub.trees.tb = Z_NULL; |
---|
| 979 | { |
---|
| 980 | uInt bl, bd; |
---|
| 981 | inflate_huft *tl, *td; |
---|
| 982 | inflate_codes_statef *c; |
---|
| 983 | |
---|
| 984 | bl = 9; /* must be <= 9 for lookahead assumptions */ |
---|
| 985 | bd = 6; /* must be <= 9 for lookahead assumptions */ |
---|
| 986 | t = s->sub.trees.table; |
---|
| 987 | t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), |
---|
| 988 | s->sub.trees.blens, &bl, &bd, &tl, &td, z); |
---|
| 989 | if (t != Z_OK) |
---|
| 990 | { |
---|
| 991 | if (t == (uInt)Z_DATA_ERROR) |
---|
| 992 | s->mode = BADB; |
---|
| 993 | r = t; |
---|
| 994 | LEAVE |
---|
| 995 | } |
---|
| 996 | Tracev(( "inflate: trees ok\n")); |
---|
| 997 | if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) |
---|
| 998 | { |
---|
| 999 | inflate_trees_free(td, z); |
---|
| 1000 | inflate_trees_free(tl, z); |
---|
| 1001 | r = Z_MEM_ERROR; |
---|
| 1002 | LEAVE |
---|
| 1003 | } |
---|
| 1004 | ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt)); |
---|
| 1005 | s->sub.decode.codes = c; |
---|
| 1006 | s->sub.decode.tl = tl; |
---|
| 1007 | s->sub.decode.td = td; |
---|
| 1008 | } |
---|
| 1009 | s->mode = CODES; |
---|
| 1010 | case CODES: |
---|
| 1011 | UPDATE |
---|
| 1012 | if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) |
---|
| 1013 | return inflate_flush(s, z, r); |
---|
| 1014 | r = Z_OK; |
---|
| 1015 | inflate_codes_free(s->sub.decode.codes, z); |
---|
| 1016 | inflate_trees_free(s->sub.decode.td, z); |
---|
| 1017 | inflate_trees_free(s->sub.decode.tl, z); |
---|
| 1018 | LOAD |
---|
| 1019 | Tracev(( "inflate: codes end, %lu total out\n", |
---|
| 1020 | z->total_out + (q >= s->read ? q - s->read : |
---|
| 1021 | (s->end - s->read) + (q - s->window)))); |
---|
| 1022 | if (!s->last) |
---|
| 1023 | { |
---|
| 1024 | s->mode = TYPE; |
---|
| 1025 | break; |
---|
| 1026 | } |
---|
| 1027 | if (k > 7) /* return unused byte, if any */ |
---|
| 1028 | { |
---|
| 1029 | Assert(k < 16, "inflate_codes grabbed too many bytes") |
---|
| 1030 | k -= 8; |
---|
| 1031 | n++; |
---|
| 1032 | p--; /* can always return one */ |
---|
| 1033 | } |
---|
| 1034 | s->mode = DRY; |
---|
| 1035 | case DRY: |
---|
| 1036 | FLUSH |
---|
| 1037 | if (s->read != s->write) |
---|
| 1038 | LEAVE |
---|
| 1039 | s->mode = DONEB; |
---|
| 1040 | case DONEB: |
---|
| 1041 | r = Z_STREAM_END; |
---|
| 1042 | LEAVE |
---|
| 1043 | case BADB: |
---|
| 1044 | r = Z_DATA_ERROR; |
---|
| 1045 | LEAVE |
---|
| 1046 | default: |
---|
| 1047 | r = Z_STREAM_ERROR; |
---|
| 1048 | LEAVE |
---|
| 1049 | } |
---|
| 1050 | } |
---|
| 1051 | |
---|
| 1052 | |
---|
| 1053 | local int inflate_blocks_free(s, z, c) |
---|
| 1054 | inflate_blocks_statef *s; |
---|
| 1055 | z_stream *z; |
---|
| 1056 | uLongf *c; |
---|
| 1057 | { |
---|
| 1058 | inflate_blocks_reset(s, z, c); |
---|
| 1059 | ZFREE(z, s->window, s->end - s->window); |
---|
| 1060 | ZFREE(z, s, sizeof(struct inflate_blocks_state)); |
---|
| 1061 | Trace(( "inflate: blocks freed\n")); |
---|
| 1062 | return Z_OK; |
---|
| 1063 | } |
---|
| 1064 | |
---|
| 1065 | /* |
---|
| 1066 | * This subroutine adds the data at next_in/avail_in to the output history |
---|
| 1067 | * without performing any output. The output buffer must be "caught up"; |
---|
| 1068 | * i.e. no pending output (hence s->read equals s->write), and the state must |
---|
| 1069 | * be BLOCKS (i.e. we should be willing to see the start of a series of |
---|
| 1070 | * BLOCKS). On exit, the output will also be caught up, and the checksum |
---|
| 1071 | * will have been updated if need be. |
---|
| 1072 | */ |
---|
| 1073 | local int inflate_addhistory(s, z) |
---|
| 1074 | inflate_blocks_statef *s; |
---|
| 1075 | z_stream *z; |
---|
| 1076 | { |
---|
| 1077 | uLong b; /* bit buffer */ /* NOT USED HERE */ |
---|
| 1078 | uInt k; /* bits in bit buffer */ /* NOT USED HERE */ |
---|
| 1079 | uInt t; /* temporary storage */ |
---|
| 1080 | Bytef *p; /* input data pointer */ |
---|
| 1081 | uInt n; /* bytes available there */ |
---|
| 1082 | Bytef *q; /* output window write pointer */ |
---|
| 1083 | uInt m; /* bytes to end of window or read pointer */ |
---|
| 1084 | |
---|
| 1085 | if (s->read != s->write) |
---|
| 1086 | return Z_STREAM_ERROR; |
---|
| 1087 | if (s->mode != TYPE) |
---|
| 1088 | return Z_DATA_ERROR; |
---|
| 1089 | |
---|
| 1090 | /* we're ready to rock */ |
---|
| 1091 | LOAD |
---|
| 1092 | /* while there is input ready, copy to output buffer, moving |
---|
| 1093 | * pointers as needed. |
---|
| 1094 | */ |
---|
| 1095 | while (n) { |
---|
| 1096 | t = n; /* how many to do */ |
---|
| 1097 | /* is there room until end of buffer? */ |
---|
| 1098 | if (t > m) t = m; |
---|
| 1099 | /* update check information */ |
---|
| 1100 | if (s->checkfn != Z_NULL) |
---|
| 1101 | s->check = (*s->checkfn)(s->check, q, t); |
---|
| 1102 | zmemcpy(q, p, t); |
---|
| 1103 | q += t; |
---|
| 1104 | p += t; |
---|
| 1105 | n -= t; |
---|
| 1106 | z->total_out += t; |
---|
| 1107 | s->read = q; /* drag read pointer forward */ |
---|
| 1108 | /* WRAP */ /* expand WRAP macro by hand to handle s->read */ |
---|
| 1109 | if (q == s->end) { |
---|
| 1110 | s->read = q = s->window; |
---|
| 1111 | m = WAVAIL; |
---|
| 1112 | } |
---|
| 1113 | } |
---|
| 1114 | UPDATE |
---|
| 1115 | return Z_OK; |
---|
| 1116 | } |
---|
| 1117 | |
---|
| 1118 | |
---|
| 1119 | /* |
---|
| 1120 | * At the end of a Deflate-compressed PPP packet, we expect to have seen |
---|
| 1121 | * a `stored' block type value but not the (zero) length bytes. |
---|
| 1122 | */ |
---|
| 1123 | local int inflate_packet_flush(s) |
---|
| 1124 | inflate_blocks_statef *s; |
---|
| 1125 | { |
---|
| 1126 | if (s->mode != LENS) |
---|
| 1127 | return Z_DATA_ERROR; |
---|
| 1128 | s->mode = TYPE; |
---|
| 1129 | return Z_OK; |
---|
| 1130 | } |
---|
| 1131 | |
---|
| 1132 | |
---|
| 1133 | /*+++++*/ |
---|
| 1134 | /* inftrees.c -- generate Huffman trees for efficient decoding |
---|
| 1135 | * Copyright (C) 1995 Mark Adler |
---|
| 1136 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 1137 | */ |
---|
| 1138 | |
---|
| 1139 | /* simplify the use of the inflate_huft type with some defines */ |
---|
| 1140 | #define base more.Base |
---|
| 1141 | #define next more.Next |
---|
| 1142 | #define exop word.what.Exop |
---|
| 1143 | #define bits word.what.Bits |
---|
| 1144 | |
---|
| 1145 | |
---|
| 1146 | local int huft_build OF(( |
---|
| 1147 | uIntf *, /* code lengths in bits */ |
---|
| 1148 | uInt, /* number of codes */ |
---|
| 1149 | uInt, /* number of "simple" codes */ |
---|
| 1150 | uIntf *, /* list of base values for non-simple codes */ |
---|
| 1151 | uIntf *, /* list of extra bits for non-simple codes */ |
---|
| 1152 | inflate_huft * FAR*,/* result: starting table */ |
---|
| 1153 | uIntf *, /* maximum lookup bits (returns actual) */ |
---|
| 1154 | z_stream *)); /* for zalloc function */ |
---|
| 1155 | |
---|
| 1156 | local voidpf falloc OF(( |
---|
| 1157 | voidpf, /* opaque pointer (not used) */ |
---|
| 1158 | uInt, /* number of items */ |
---|
| 1159 | uInt)); /* size of item */ |
---|
| 1160 | |
---|
| 1161 | local void ffree OF(( |
---|
| 1162 | voidpf q, /* opaque pointer (not used) */ |
---|
| 1163 | voidpf p, /* what to free (not used) */ |
---|
| 1164 | uInt n)); /* number of bytes (not used) */ |
---|
| 1165 | |
---|
| 1166 | /* Tables for deflate from PKZIP's appnote.txt. */ |
---|
| 1167 | local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */ |
---|
| 1168 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, |
---|
| 1169 | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; |
---|
| 1170 | /* actually lengths - 2; also see note #13 above about 258 */ |
---|
| 1171 | local uInt cplext[] = { /* Extra bits for literal codes 257..285 */ |
---|
| 1172 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, |
---|
| 1173 | 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */ |
---|
| 1174 | local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */ |
---|
| 1175 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, |
---|
| 1176 | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, |
---|
| 1177 | 8193, 12289, 16385, 24577}; |
---|
| 1178 | local uInt cpdext[] = { /* Extra bits for distance codes */ |
---|
| 1179 | 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, |
---|
| 1180 | 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, |
---|
| 1181 | 12, 12, 13, 13}; |
---|
| 1182 | |
---|
| 1183 | /* |
---|
| 1184 | Huffman code decoding is performed using a multi-level table lookup. |
---|
| 1185 | The fastest way to decode is to simply build a lookup table whose |
---|
| 1186 | size is determined by the longest code. However, the time it takes |
---|
| 1187 | to build this table can also be a factor if the data being decoded |
---|
| 1188 | is not very long. The most common codes are necessarily the |
---|
| 1189 | shortest codes, so those codes dominate the decoding time, and hence |
---|
| 1190 | the speed. The idea is you can have a shorter table that decodes the |
---|
| 1191 | shorter, more probable codes, and then point to subsidiary tables for |
---|
| 1192 | the longer codes. The time it costs to decode the longer codes is |
---|
| 1193 | then traded against the time it takes to make longer tables. |
---|
| 1194 | |
---|
| 1195 | This results of this trade are in the variables lbits and dbits |
---|
| 1196 | below. lbits is the number of bits the first level table for literal/ |
---|
| 1197 | length codes can decode in one step, and dbits is the same thing for |
---|
| 1198 | the distance codes. Subsequent tables are also less than or equal to |
---|
| 1199 | those sizes. These values may be adjusted either when all of the |
---|
| 1200 | codes are shorter than that, in which case the longest code length in |
---|
| 1201 | bits is used, or when the shortest code is *longer* than the requested |
---|
| 1202 | table size, in which case the length of the shortest code in bits is |
---|
| 1203 | used. |
---|
| 1204 | |
---|
| 1205 | There are two different values for the two tables, since they code a |
---|
| 1206 | different number of possibilities each. The literal/length table |
---|
| 1207 | codes 286 possible values, or in a flat code, a little over eight |
---|
| 1208 | bits. The distance table codes 30 possible values, or a little less |
---|
| 1209 | than five bits, flat. The optimum values for speed end up being |
---|
| 1210 | about one bit more than those, so lbits is 8+1 and dbits is 5+1. |
---|
| 1211 | The optimum values may differ though from machine to machine, and |
---|
| 1212 | possibly even between compilers. Your mileage may vary. |
---|
| 1213 | */ |
---|
| 1214 | |
---|
| 1215 | |
---|
| 1216 | /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ |
---|
| 1217 | #define BMAX 15 /* maximum bit length of any code */ |
---|
| 1218 | #define N_MAX 288 /* maximum number of codes in any set */ |
---|
| 1219 | |
---|
| 1220 | #ifdef DEBUG_ZLIB |
---|
| 1221 | uInt inflate_hufts; |
---|
| 1222 | #endif |
---|
| 1223 | |
---|
| 1224 | local int huft_build(b, n, s, d, e, t, m, zs) |
---|
| 1225 | uIntf *b; /* code lengths in bits (all assumed <= BMAX) */ |
---|
| 1226 | uInt n; /* number of codes (assumed <= N_MAX) */ |
---|
| 1227 | uInt s; /* number of simple-valued codes (0..s-1) */ |
---|
| 1228 | uIntf *d; /* list of base values for non-simple codes */ |
---|
| 1229 | uIntf *e; /* list of extra bits for non-simple codes */ |
---|
| 1230 | inflate_huft * FAR *t; /* result: starting table */ |
---|
| 1231 | uIntf *m; /* maximum lookup bits, returns actual */ |
---|
| 1232 | z_stream *zs; /* for zalloc function */ |
---|
| 1233 | /* Given a list of code lengths and a maximum table size, make a set of |
---|
| 1234 | tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR |
---|
| 1235 | if the given code set is incomplete (the tables are still built in this |
---|
| 1236 | case), Z_DATA_ERROR if the input is invalid (all zero length codes or an |
---|
| 1237 | over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */ |
---|
| 1238 | { |
---|
| 1239 | |
---|
| 1240 | uInt a; /* counter for codes of length k */ |
---|
| 1241 | uInt c[BMAX+1]; /* bit length count table */ |
---|
| 1242 | uInt f; /* i repeats in table every f entries */ |
---|
| 1243 | int g; /* maximum code length */ |
---|
| 1244 | int h; /* table level */ |
---|
| 1245 | register uInt i; /* counter, current code */ |
---|
| 1246 | register uInt j; /* counter */ |
---|
| 1247 | register int k; /* number of bits in current code */ |
---|
| 1248 | int l; /* bits per table (returned in m) */ |
---|
| 1249 | register uIntf *p; /* pointer into c[], b[], or v[] */ |
---|
| 1250 | inflate_huft *q; /* points to current table */ |
---|
| 1251 | struct inflate_huft_s r; /* table entry for structure assignment */ |
---|
| 1252 | inflate_huft *u[BMAX]; /* table stack */ |
---|
| 1253 | uInt v[N_MAX]; /* values in order of bit length */ |
---|
| 1254 | register int w; /* bits before this table == (l * h) */ |
---|
| 1255 | uInt x[BMAX+1]; /* bit offsets, then code stack */ |
---|
| 1256 | uIntf *xp; /* pointer into x */ |
---|
| 1257 | int y; /* number of dummy codes added */ |
---|
| 1258 | uInt z; /* number of entries in current table */ |
---|
| 1259 | |
---|
| 1260 | |
---|
| 1261 | /* Generate counts for each bit length */ |
---|
| 1262 | p = c; |
---|
| 1263 | #define C0 *p++ = 0; |
---|
| 1264 | #define C2 C0 C0 C0 C0 |
---|
| 1265 | #define C4 C2 C2 C2 C2 |
---|
| 1266 | C4 /* clear c[]--assume BMAX+1 is 16 */ |
---|
| 1267 | p = b; i = n; |
---|
| 1268 | do { |
---|
| 1269 | c[*p++]++; /* assume all entries <= BMAX */ |
---|
| 1270 | } while (--i); |
---|
| 1271 | if (c[0] == n) /* null input--all zero length codes */ |
---|
| 1272 | { |
---|
| 1273 | *t = (inflate_huft *)Z_NULL; |
---|
| 1274 | *m = 0; |
---|
| 1275 | return Z_OK; |
---|
| 1276 | } |
---|
| 1277 | |
---|
| 1278 | |
---|
| 1279 | /* Find minimum and maximum length, bound *m by those */ |
---|
| 1280 | l = *m; |
---|
| 1281 | for (j = 1; j <= BMAX; j++) |
---|
| 1282 | if (c[j]) |
---|
| 1283 | break; |
---|
| 1284 | k = j; /* minimum code length */ |
---|
| 1285 | if ((uInt)l < j) |
---|
| 1286 | l = j; |
---|
| 1287 | for (i = BMAX; i; i--) |
---|
| 1288 | if (c[i]) |
---|
| 1289 | break; |
---|
| 1290 | g = i; /* maximum code length */ |
---|
| 1291 | if ((uInt)l > i) |
---|
| 1292 | l = i; |
---|
| 1293 | *m = l; |
---|
| 1294 | |
---|
| 1295 | |
---|
| 1296 | /* Adjust last length count to fill out codes, if needed */ |
---|
| 1297 | for (y = 1 << j; j < i; j++, y <<= 1) |
---|
| 1298 | if ((y -= c[j]) < 0) |
---|
| 1299 | return Z_DATA_ERROR; |
---|
| 1300 | if ((y -= c[i]) < 0) |
---|
| 1301 | return Z_DATA_ERROR; |
---|
| 1302 | c[i] += y; |
---|
| 1303 | |
---|
| 1304 | |
---|
| 1305 | /* Generate starting offsets into the value table for each length */ |
---|
| 1306 | x[1] = j = 0; |
---|
| 1307 | p = c + 1; xp = x + 2; |
---|
| 1308 | while (--i) { /* note that i == g from above */ |
---|
| 1309 | *xp++ = (j += *p++); |
---|
| 1310 | } |
---|
| 1311 | |
---|
| 1312 | |
---|
| 1313 | /* Make a table of values in order of bit lengths */ |
---|
| 1314 | p = b; i = 0; |
---|
| 1315 | do { |
---|
| 1316 | if ((j = *p++) != 0) |
---|
| 1317 | v[x[j]++] = i; |
---|
| 1318 | } while (++i < n); |
---|
| 1319 | |
---|
| 1320 | |
---|
| 1321 | /* Generate the Huffman codes and for each, make the table entries */ |
---|
| 1322 | x[0] = i = 0; /* first Huffman code is zero */ |
---|
| 1323 | p = v; /* grab values in bit order */ |
---|
| 1324 | h = -1; /* no tables yet--level -1 */ |
---|
| 1325 | w = -l; /* bits decoded == (l * h) */ |
---|
| 1326 | u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ |
---|
| 1327 | q = (inflate_huft *)Z_NULL; /* ditto */ |
---|
| 1328 | z = 0; /* ditto */ |
---|
| 1329 | |
---|
| 1330 | /* go through the bit lengths (k already is bits in shortest code) */ |
---|
| 1331 | for (; k <= g; k++) |
---|
| 1332 | { |
---|
| 1333 | a = c[k]; |
---|
| 1334 | while (a--) |
---|
| 1335 | { |
---|
| 1336 | /* here i is the Huffman code of length k bits for value *p */ |
---|
| 1337 | /* make tables up to required level */ |
---|
| 1338 | while (k > w + l) |
---|
| 1339 | { |
---|
| 1340 | h++; |
---|
| 1341 | w += l; /* previous table always l bits */ |
---|
| 1342 | |
---|
| 1343 | /* compute minimum size table less than or equal to l bits */ |
---|
| 1344 | z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */ |
---|
| 1345 | if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ |
---|
| 1346 | { /* too few codes for k-w bit table */ |
---|
| 1347 | f -= a + 1; /* deduct codes from patterns left */ |
---|
| 1348 | xp = c + k; |
---|
| 1349 | if (j < z) |
---|
| 1350 | while (++j < z) /* try smaller tables up to z bits */ |
---|
| 1351 | { |
---|
| 1352 | if ((f <<= 1) <= *++xp) |
---|
| 1353 | break; /* enough codes to use up j bits */ |
---|
| 1354 | f -= *xp; /* else deduct codes from patterns */ |
---|
| 1355 | } |
---|
| 1356 | } |
---|
| 1357 | z = 1 << j; /* table entries for j-bit table */ |
---|
| 1358 | |
---|
| 1359 | /* allocate and link in new table */ |
---|
| 1360 | if ((q = (inflate_huft *)ZALLOC |
---|
| 1361 | (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) |
---|
| 1362 | { |
---|
| 1363 | if (h) |
---|
| 1364 | inflate_trees_free(u[0], zs); |
---|
| 1365 | return Z_MEM_ERROR; /* not enough memory */ |
---|
| 1366 | } |
---|
| 1367 | q->word.Nalloc = z + 1; |
---|
| 1368 | #ifdef DEBUG_ZLIB |
---|
| 1369 | inflate_hufts += z + 1; |
---|
| 1370 | #endif |
---|
| 1371 | *t = q + 1; /* link to list for huft_free() */ |
---|
| 1372 | *(t = &(q->next)) = Z_NULL; |
---|
| 1373 | u[h] = ++q; /* table starts after link */ |
---|
| 1374 | |
---|
| 1375 | /* connect to last table, if there is one */ |
---|
| 1376 | if (h) |
---|
| 1377 | { |
---|
| 1378 | x[h] = i; /* save pattern for backing up */ |
---|
| 1379 | r.bits = (Byte)l; /* bits to dump before this table */ |
---|
| 1380 | r.exop = (Byte)j; /* bits in this table */ |
---|
| 1381 | r.next = q; /* pointer to this table */ |
---|
| 1382 | j = i >> (w - l); /* (get around Turbo C bug) */ |
---|
| 1383 | u[h-1][j] = r; /* connect to last table */ |
---|
| 1384 | } |
---|
| 1385 | } |
---|
| 1386 | |
---|
| 1387 | /* set up table entry in r */ |
---|
| 1388 | r.bits = (Byte)(k - w); |
---|
| 1389 | if (p >= v + n) |
---|
| 1390 | r.exop = 128 + 64; /* out of values--invalid code */ |
---|
| 1391 | else if (*p < s) |
---|
| 1392 | { |
---|
| 1393 | r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ |
---|
| 1394 | r.base = *p++; /* simple code is just the value */ |
---|
| 1395 | } |
---|
| 1396 | else |
---|
| 1397 | { |
---|
| 1398 | r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */ |
---|
| 1399 | r.base = d[*p++ - s]; |
---|
| 1400 | } |
---|
| 1401 | |
---|
| 1402 | /* fill code-like entries with r */ |
---|
| 1403 | f = 1 << (k - w); |
---|
| 1404 | for (j = i >> w; j < z; j += f) |
---|
| 1405 | q[j] = r; |
---|
| 1406 | |
---|
| 1407 | /* backwards increment the k-bit code i */ |
---|
| 1408 | for (j = 1 << (k - 1); i & j; j >>= 1) |
---|
| 1409 | i ^= j; |
---|
| 1410 | i ^= j; |
---|
| 1411 | |
---|
| 1412 | /* backup over finished tables */ |
---|
| 1413 | while ((i & ((1 << w) - 1)) != x[h]) |
---|
| 1414 | { |
---|
| 1415 | h--; /* don't need to update q */ |
---|
| 1416 | w -= l; |
---|
| 1417 | } |
---|
| 1418 | } |
---|
| 1419 | } |
---|
| 1420 | |
---|
| 1421 | |
---|
| 1422 | /* Return Z_BUF_ERROR if we were given an incomplete table */ |
---|
| 1423 | return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; |
---|
| 1424 | } |
---|
| 1425 | |
---|
| 1426 | |
---|
| 1427 | local int inflate_trees_bits(c, bb, tb, z) |
---|
| 1428 | uIntf *c; /* 19 code lengths */ |
---|
| 1429 | uIntf *bb; /* bits tree desired/actual depth */ |
---|
| 1430 | inflate_huft * FAR *tb; /* bits tree result */ |
---|
| 1431 | z_stream *z; /* for zfree function */ |
---|
| 1432 | { |
---|
| 1433 | int r; |
---|
| 1434 | |
---|
| 1435 | r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); |
---|
| 1436 | if (r == Z_DATA_ERROR) |
---|
| 1437 | z->msg = "oversubscribed dynamic bit lengths tree"; |
---|
| 1438 | else if (r == Z_BUF_ERROR) |
---|
| 1439 | { |
---|
| 1440 | inflate_trees_free(*tb, z); |
---|
| 1441 | z->msg = "incomplete dynamic bit lengths tree"; |
---|
| 1442 | r = Z_DATA_ERROR; |
---|
| 1443 | } |
---|
| 1444 | return r; |
---|
| 1445 | } |
---|
| 1446 | |
---|
| 1447 | |
---|
| 1448 | local int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) |
---|
| 1449 | uInt nl; /* number of literal/length codes */ |
---|
| 1450 | uInt nd; /* number of distance codes */ |
---|
| 1451 | uIntf *c; /* that many (total) code lengths */ |
---|
| 1452 | uIntf *bl; /* literal desired/actual bit depth */ |
---|
| 1453 | uIntf *bd; /* distance desired/actual bit depth */ |
---|
| 1454 | inflate_huft * FAR *tl; /* literal/length tree result */ |
---|
| 1455 | inflate_huft * FAR *td; /* distance tree result */ |
---|
| 1456 | z_stream *z; /* for zfree function */ |
---|
| 1457 | { |
---|
| 1458 | int r; |
---|
| 1459 | |
---|
| 1460 | /* build literal/length tree */ |
---|
| 1461 | if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK) |
---|
| 1462 | { |
---|
| 1463 | if (r == Z_DATA_ERROR) |
---|
| 1464 | z->msg = "oversubscribed literal/length tree"; |
---|
| 1465 | else if (r == Z_BUF_ERROR) |
---|
| 1466 | { |
---|
| 1467 | inflate_trees_free(*tl, z); |
---|
| 1468 | z->msg = "incomplete literal/length tree"; |
---|
| 1469 | r = Z_DATA_ERROR; |
---|
| 1470 | } |
---|
| 1471 | return r; |
---|
| 1472 | } |
---|
| 1473 | |
---|
| 1474 | /* build distance tree */ |
---|
| 1475 | if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK) |
---|
| 1476 | { |
---|
| 1477 | if (r == Z_DATA_ERROR) |
---|
| 1478 | z->msg = "oversubscribed literal/length tree"; |
---|
| 1479 | else if (r == Z_BUF_ERROR) { |
---|
| 1480 | #ifdef PKZIP_BUG_WORKAROUND |
---|
| 1481 | r = Z_OK; |
---|
| 1482 | } |
---|
| 1483 | #else |
---|
| 1484 | inflate_trees_free(*td, z); |
---|
| 1485 | z->msg = "incomplete literal/length tree"; |
---|
| 1486 | r = Z_DATA_ERROR; |
---|
| 1487 | } |
---|
| 1488 | inflate_trees_free(*tl, z); |
---|
| 1489 | return r; |
---|
| 1490 | #endif |
---|
| 1491 | } |
---|
| 1492 | |
---|
| 1493 | /* done */ |
---|
| 1494 | return Z_OK; |
---|
| 1495 | } |
---|
| 1496 | |
---|
| 1497 | |
---|
| 1498 | /* build fixed tables only once--keep them here */ |
---|
| 1499 | local int fixed_lock = 0; |
---|
| 1500 | local int fixed_built = 0; |
---|
| 1501 | #define FIXEDH 530 /* number of hufts used by fixed tables */ |
---|
| 1502 | local uInt fixed_left = FIXEDH; |
---|
| 1503 | local inflate_huft fixed_mem[FIXEDH]; |
---|
| 1504 | local uInt fixed_bl; |
---|
| 1505 | local uInt fixed_bd; |
---|
| 1506 | local inflate_huft *fixed_tl; |
---|
| 1507 | local inflate_huft *fixed_td; |
---|
| 1508 | |
---|
| 1509 | |
---|
| 1510 | local voidpf falloc(q, n, s) |
---|
| 1511 | voidpf q; /* opaque pointer (not used) */ |
---|
| 1512 | uInt n; /* number of items */ |
---|
| 1513 | uInt s; /* size of item */ |
---|
| 1514 | { |
---|
| 1515 | Assert(s == sizeof(inflate_huft) && n <= fixed_left, |
---|
| 1516 | "inflate_trees falloc overflow"); |
---|
| 1517 | if (q) s++; /* to make some compilers happy */ |
---|
| 1518 | fixed_left -= n; |
---|
| 1519 | return (voidpf)(fixed_mem + fixed_left); |
---|
| 1520 | } |
---|
| 1521 | |
---|
| 1522 | |
---|
| 1523 | local void ffree(q, p, n) |
---|
| 1524 | voidpf q; |
---|
| 1525 | voidpf p; |
---|
| 1526 | uInt n; |
---|
| 1527 | { |
---|
| 1528 | Assert(0, "inflate_trees ffree called!"); |
---|
| 1529 | if (q) q = p; /* to make some compilers happy */ |
---|
| 1530 | } |
---|
| 1531 | |
---|
| 1532 | |
---|
| 1533 | local int inflate_trees_fixed(bl, bd, tl, td) |
---|
| 1534 | uIntf *bl; /* literal desired/actual bit depth */ |
---|
| 1535 | uIntf *bd; /* distance desired/actual bit depth */ |
---|
| 1536 | inflate_huft * FAR *tl; /* literal/length tree result */ |
---|
| 1537 | inflate_huft * FAR *td; /* distance tree result */ |
---|
| 1538 | { |
---|
| 1539 | /* build fixed tables if not built already--lock out other instances */ |
---|
| 1540 | while (++fixed_lock > 1) |
---|
| 1541 | fixed_lock--; |
---|
| 1542 | if (!fixed_built) |
---|
| 1543 | { |
---|
| 1544 | int k; /* temporary variable */ |
---|
| 1545 | unsigned c[288]; /* length list for huft_build */ |
---|
| 1546 | z_stream z; /* for falloc function */ |
---|
| 1547 | |
---|
| 1548 | /* set up fake z_stream for memory routines */ |
---|
| 1549 | z.zalloc = falloc; |
---|
| 1550 | z.zfree = ffree; |
---|
| 1551 | z.opaque = Z_NULL; |
---|
| 1552 | |
---|
| 1553 | /* literal table */ |
---|
| 1554 | for (k = 0; k < 144; k++) |
---|
| 1555 | c[k] = 8; |
---|
| 1556 | for (; k < 256; k++) |
---|
| 1557 | c[k] = 9; |
---|
| 1558 | for (; k < 280; k++) |
---|
| 1559 | c[k] = 7; |
---|
| 1560 | for (; k < 288; k++) |
---|
| 1561 | c[k] = 8; |
---|
| 1562 | fixed_bl = 7; |
---|
| 1563 | huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); |
---|
| 1564 | |
---|
| 1565 | /* distance table */ |
---|
| 1566 | for (k = 0; k < 30; k++) |
---|
| 1567 | c[k] = 5; |
---|
| 1568 | fixed_bd = 5; |
---|
| 1569 | huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); |
---|
| 1570 | |
---|
| 1571 | /* done */ |
---|
| 1572 | fixed_built = 1; |
---|
| 1573 | } |
---|
| 1574 | fixed_lock--; |
---|
| 1575 | *bl = fixed_bl; |
---|
| 1576 | *bd = fixed_bd; |
---|
| 1577 | *tl = fixed_tl; |
---|
| 1578 | *td = fixed_td; |
---|
| 1579 | return Z_OK; |
---|
| 1580 | } |
---|
| 1581 | |
---|
| 1582 | |
---|
| 1583 | local int inflate_trees_free(t, z) |
---|
| 1584 | inflate_huft *t; /* table to free */ |
---|
| 1585 | z_stream *z; /* for zfree function */ |
---|
| 1586 | /* Free the malloc'ed tables built by huft_build(), which makes a linked |
---|
| 1587 | list of the tables it made, with the links in a dummy first entry of |
---|
| 1588 | each table. */ |
---|
| 1589 | { |
---|
| 1590 | register inflate_huft *p, *q; |
---|
| 1591 | |
---|
| 1592 | /* Go through linked list, freeing from the malloced (t[-1]) address. */ |
---|
| 1593 | p = t; |
---|
| 1594 | while (p != Z_NULL) |
---|
| 1595 | { |
---|
| 1596 | q = (--p)->next; |
---|
| 1597 | ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft)); |
---|
| 1598 | p = q; |
---|
| 1599 | } |
---|
| 1600 | return Z_OK; |
---|
| 1601 | } |
---|
| 1602 | |
---|
| 1603 | /*+++++*/ |
---|
| 1604 | /* infcodes.c -- process literals and length/distance pairs |
---|
| 1605 | * Copyright (C) 1995 Mark Adler |
---|
| 1606 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 1607 | */ |
---|
| 1608 | |
---|
| 1609 | /* simplify the use of the inflate_huft type with some defines */ |
---|
| 1610 | #define base more.Base |
---|
| 1611 | #define next more.Next |
---|
| 1612 | #define exop word.what.Exop |
---|
| 1613 | #define bits word.what.Bits |
---|
| 1614 | |
---|
| 1615 | /* inflate codes private state */ |
---|
| 1616 | struct inflate_codes_state { |
---|
| 1617 | |
---|
| 1618 | /* mode */ |
---|
| 1619 | enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ |
---|
| 1620 | START, /* x: set up for LEN */ |
---|
| 1621 | LEN, /* i: get length/literal/eob next */ |
---|
| 1622 | LENEXT, /* i: getting length extra (have base) */ |
---|
| 1623 | DIST, /* i: get distance next */ |
---|
| 1624 | DISTEXT, /* i: getting distance extra */ |
---|
| 1625 | COPY, /* o: copying bytes in window, waiting for space */ |
---|
| 1626 | LIT, /* o: got literal, waiting for output space */ |
---|
| 1627 | WASH, /* o: got eob, possibly still output waiting */ |
---|
| 1628 | END, /* x: got eob and all data flushed */ |
---|
| 1629 | BADCODE} /* x: got error */ |
---|
| 1630 | mode; /* current inflate_codes mode */ |
---|
| 1631 | |
---|
| 1632 | /* mode dependent information */ |
---|
| 1633 | uInt len; |
---|
| 1634 | union { |
---|
| 1635 | struct { |
---|
| 1636 | inflate_huft *tree; /* pointer into tree */ |
---|
| 1637 | uInt need; /* bits needed */ |
---|
| 1638 | } code; /* if LEN or DIST, where in tree */ |
---|
| 1639 | uInt lit; /* if LIT, literal */ |
---|
| 1640 | struct { |
---|
| 1641 | uInt get; /* bits to get for extra */ |
---|
| 1642 | uInt dist; /* distance back to copy from */ |
---|
| 1643 | } copy; /* if EXT or COPY, where and how much */ |
---|
| 1644 | } sub; /* submode */ |
---|
| 1645 | |
---|
| 1646 | /* mode independent information */ |
---|
| 1647 | Byte lbits; /* ltree bits decoded per branch */ |
---|
| 1648 | Byte dbits; /* dtree bits decoder per branch */ |
---|
| 1649 | inflate_huft *ltree; /* literal/length/eob tree */ |
---|
| 1650 | inflate_huft *dtree; /* distance tree */ |
---|
| 1651 | |
---|
| 1652 | }; |
---|
| 1653 | |
---|
| 1654 | |
---|
| 1655 | local inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z) |
---|
| 1656 | uInt bl, bd; |
---|
| 1657 | inflate_huft *tl, *td; |
---|
| 1658 | z_stream *z; |
---|
| 1659 | { |
---|
| 1660 | inflate_codes_statef *c; |
---|
| 1661 | |
---|
| 1662 | if ((c = (inflate_codes_statef *) |
---|
| 1663 | ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) |
---|
| 1664 | { |
---|
| 1665 | c->mode = START; |
---|
| 1666 | c->lbits = (Byte)bl; |
---|
| 1667 | c->dbits = (Byte)bd; |
---|
| 1668 | c->ltree = tl; |
---|
| 1669 | c->dtree = td; |
---|
| 1670 | Tracev(( "inflate: codes new\n")); |
---|
| 1671 | } |
---|
| 1672 | return c; |
---|
| 1673 | } |
---|
| 1674 | |
---|
| 1675 | |
---|
| 1676 | local int inflate_codes(s, z, r) |
---|
| 1677 | inflate_blocks_statef *s; |
---|
| 1678 | z_stream *z; |
---|
| 1679 | int r; |
---|
| 1680 | { |
---|
| 1681 | uInt j; /* temporary storage */ |
---|
| 1682 | inflate_huft *t; /* temporary pointer */ |
---|
| 1683 | uInt e; /* extra bits or operation */ |
---|
| 1684 | uLong b; /* bit buffer */ |
---|
| 1685 | uInt k; /* bits in bit buffer */ |
---|
| 1686 | Bytef *p; /* input data pointer */ |
---|
| 1687 | uInt n; /* bytes available there */ |
---|
| 1688 | Bytef *q; /* output window write pointer */ |
---|
| 1689 | uInt m; /* bytes to end of window or read pointer */ |
---|
| 1690 | Bytef *f; /* pointer to copy strings from */ |
---|
| 1691 | inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ |
---|
| 1692 | |
---|
| 1693 | /* copy input/output information to locals (UPDATE macro restores) */ |
---|
| 1694 | LOAD |
---|
| 1695 | |
---|
| 1696 | /* process input and output based on current state */ |
---|
| 1697 | while (1) switch (c->mode) |
---|
| 1698 | { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ |
---|
| 1699 | case START: /* x: set up for LEN */ |
---|
| 1700 | #ifndef SLOW |
---|
| 1701 | if (m >= 258 && n >= 10) |
---|
| 1702 | { |
---|
| 1703 | UPDATE |
---|
| 1704 | r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); |
---|
| 1705 | LOAD |
---|
| 1706 | if (r != Z_OK) |
---|
| 1707 | { |
---|
| 1708 | c->mode = r == Z_STREAM_END ? WASH : BADCODE; |
---|
| 1709 | break; |
---|
| 1710 | } |
---|
| 1711 | } |
---|
| 1712 | #endif /* !SLOW */ |
---|
| 1713 | c->sub.code.need = c->lbits; |
---|
| 1714 | c->sub.code.tree = c->ltree; |
---|
| 1715 | c->mode = LEN; |
---|
| 1716 | case LEN: /* i: get length/literal/eob next */ |
---|
| 1717 | j = c->sub.code.need; |
---|
| 1718 | NEEDBITS(j) |
---|
| 1719 | t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); |
---|
| 1720 | DUMPBITS(t->bits) |
---|
| 1721 | e = (uInt)(t->exop); |
---|
| 1722 | if (e == 0) /* literal */ |
---|
| 1723 | { |
---|
| 1724 | c->sub.lit = t->base; |
---|
| 1725 | Tracevv(( t->base >= 0x20 && t->base < 0x7f ? |
---|
| 1726 | "inflate: literal '%c'\n" : |
---|
| 1727 | "inflate: literal 0x%02x\n", t->base)); |
---|
| 1728 | c->mode = LIT; |
---|
| 1729 | break; |
---|
| 1730 | } |
---|
| 1731 | if (e & 16) /* length */ |
---|
| 1732 | { |
---|
| 1733 | c->sub.copy.get = e & 15; |
---|
| 1734 | c->len = t->base; |
---|
| 1735 | c->mode = LENEXT; |
---|
| 1736 | break; |
---|
| 1737 | } |
---|
| 1738 | if ((e & 64) == 0) /* next table */ |
---|
| 1739 | { |
---|
| 1740 | c->sub.code.need = e; |
---|
| 1741 | c->sub.code.tree = t->next; |
---|
| 1742 | break; |
---|
| 1743 | } |
---|
| 1744 | if (e & 32) /* end of block */ |
---|
| 1745 | { |
---|
| 1746 | Tracevv(( "inflate: end of block\n")); |
---|
| 1747 | c->mode = WASH; |
---|
| 1748 | break; |
---|
| 1749 | } |
---|
| 1750 | c->mode = BADCODE; /* invalid code */ |
---|
| 1751 | z->msg = "invalid literal/length code"; |
---|
| 1752 | r = Z_DATA_ERROR; |
---|
| 1753 | LEAVE |
---|
| 1754 | case LENEXT: /* i: getting length extra (have base) */ |
---|
| 1755 | j = c->sub.copy.get; |
---|
| 1756 | NEEDBITS(j) |
---|
| 1757 | c->len += (uInt)b & inflate_mask[j]; |
---|
| 1758 | DUMPBITS(j) |
---|
| 1759 | c->sub.code.need = c->dbits; |
---|
| 1760 | c->sub.code.tree = c->dtree; |
---|
| 1761 | Tracevv(( "inflate: length %u\n", c->len)); |
---|
| 1762 | c->mode = DIST; |
---|
| 1763 | case DIST: /* i: get distance next */ |
---|
| 1764 | j = c->sub.code.need; |
---|
| 1765 | NEEDBITS(j) |
---|
| 1766 | t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); |
---|
| 1767 | DUMPBITS(t->bits) |
---|
| 1768 | e = (uInt)(t->exop); |
---|
| 1769 | if (e & 16) /* distance */ |
---|
| 1770 | { |
---|
| 1771 | c->sub.copy.get = e & 15; |
---|
| 1772 | c->sub.copy.dist = t->base; |
---|
| 1773 | c->mode = DISTEXT; |
---|
| 1774 | break; |
---|
| 1775 | } |
---|
| 1776 | if ((e & 64) == 0) /* next table */ |
---|
| 1777 | { |
---|
| 1778 | c->sub.code.need = e; |
---|
| 1779 | c->sub.code.tree = t->next; |
---|
| 1780 | break; |
---|
| 1781 | } |
---|
| 1782 | c->mode = BADCODE; /* invalid code */ |
---|
| 1783 | z->msg = "invalid distance code"; |
---|
| 1784 | r = Z_DATA_ERROR; |
---|
| 1785 | LEAVE |
---|
| 1786 | case DISTEXT: /* i: getting distance extra */ |
---|
| 1787 | j = c->sub.copy.get; |
---|
| 1788 | NEEDBITS(j) |
---|
| 1789 | c->sub.copy.dist += (uInt)b & inflate_mask[j]; |
---|
| 1790 | DUMPBITS(j) |
---|
| 1791 | Tracevv(( "inflate: distance %u\n", c->sub.copy.dist)); |
---|
| 1792 | c->mode = COPY; |
---|
| 1793 | case COPY: /* o: copying bytes in window, waiting for space */ |
---|
| 1794 | #ifndef __TURBOC__ /* Turbo C bug for following expression */ |
---|
| 1795 | f = (uInt)(q - s->window) < c->sub.copy.dist ? |
---|
| 1796 | s->end - (c->sub.copy.dist - (q - s->window)) : |
---|
| 1797 | q - c->sub.copy.dist; |
---|
| 1798 | #else |
---|
| 1799 | f = q - c->sub.copy.dist; |
---|
| 1800 | if ((uInt)(q - s->window) < c->sub.copy.dist) |
---|
| 1801 | f = s->end - (c->sub.copy.dist - (q - s->window)); |
---|
| 1802 | #endif |
---|
| 1803 | while (c->len) |
---|
| 1804 | { |
---|
| 1805 | NEEDOUT |
---|
| 1806 | OUTBYTE(*f++) |
---|
| 1807 | if (f == s->end) |
---|
| 1808 | f = s->window; |
---|
| 1809 | c->len--; |
---|
| 1810 | } |
---|
| 1811 | c->mode = START; |
---|
| 1812 | break; |
---|
| 1813 | case LIT: /* o: got literal, waiting for output space */ |
---|
| 1814 | NEEDOUT |
---|
| 1815 | OUTBYTE(c->sub.lit) |
---|
| 1816 | c->mode = START; |
---|
| 1817 | break; |
---|
| 1818 | case WASH: /* o: got eob, possibly more output */ |
---|
| 1819 | FLUSH |
---|
| 1820 | if (s->read != s->write) |
---|
| 1821 | LEAVE |
---|
| 1822 | c->mode = END; |
---|
| 1823 | case END: |
---|
| 1824 | r = Z_STREAM_END; |
---|
| 1825 | LEAVE |
---|
| 1826 | case BADCODE: /* x: got error */ |
---|
| 1827 | r = Z_DATA_ERROR; |
---|
| 1828 | LEAVE |
---|
| 1829 | default: |
---|
| 1830 | r = Z_STREAM_ERROR; |
---|
| 1831 | LEAVE |
---|
| 1832 | } |
---|
| 1833 | } |
---|
| 1834 | |
---|
| 1835 | |
---|
| 1836 | local void inflate_codes_free(c, z) |
---|
| 1837 | inflate_codes_statef *c; |
---|
| 1838 | z_stream *z; |
---|
| 1839 | { |
---|
| 1840 | ZFREE(z, c, sizeof(struct inflate_codes_state)); |
---|
| 1841 | Tracev(( "inflate: codes free\n")); |
---|
| 1842 | } |
---|
| 1843 | |
---|
| 1844 | /*+++++*/ |
---|
| 1845 | /* inflate_util.c -- data and routines common to blocks and codes |
---|
| 1846 | * Copyright (C) 1995 Mark Adler |
---|
| 1847 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 1848 | */ |
---|
| 1849 | |
---|
| 1850 | /* copy as much as possible from the sliding window to the output area */ |
---|
| 1851 | local int inflate_flush(s, z, r) |
---|
| 1852 | inflate_blocks_statef *s; |
---|
| 1853 | z_stream *z; |
---|
| 1854 | int r; |
---|
| 1855 | { |
---|
| 1856 | uInt n; |
---|
| 1857 | Bytef *p, *q; |
---|
| 1858 | |
---|
| 1859 | /* local copies of source and destination pointers */ |
---|
| 1860 | p = z->next_out; |
---|
| 1861 | q = s->read; |
---|
| 1862 | |
---|
| 1863 | /* compute number of bytes to copy as far as end of window */ |
---|
| 1864 | n = (uInt)((q <= s->write ? s->write : s->end) - q); |
---|
| 1865 | if (n > z->avail_out) n = z->avail_out; |
---|
| 1866 | if (n && r == Z_BUF_ERROR) r = Z_OK; |
---|
| 1867 | |
---|
| 1868 | /* update counters */ |
---|
| 1869 | z->avail_out -= n; |
---|
| 1870 | z->total_out += n; |
---|
| 1871 | |
---|
| 1872 | /* update check information */ |
---|
| 1873 | if (s->checkfn != Z_NULL) |
---|
| 1874 | s->check = (*s->checkfn)(s->check, q, n); |
---|
| 1875 | |
---|
| 1876 | /* copy as far as end of window */ |
---|
| 1877 | zmemcpy(p, q, n); |
---|
| 1878 | p += n; |
---|
| 1879 | q += n; |
---|
| 1880 | |
---|
| 1881 | /* see if more to copy at beginning of window */ |
---|
| 1882 | if (q == s->end) |
---|
| 1883 | { |
---|
| 1884 | /* wrap pointers */ |
---|
| 1885 | q = s->window; |
---|
| 1886 | if (s->write == s->end) |
---|
| 1887 | s->write = s->window; |
---|
| 1888 | |
---|
| 1889 | /* compute bytes to copy */ |
---|
| 1890 | n = (uInt)(s->write - q); |
---|
| 1891 | if (n > z->avail_out) n = z->avail_out; |
---|
| 1892 | if (n && r == Z_BUF_ERROR) r = Z_OK; |
---|
| 1893 | |
---|
| 1894 | /* update counters */ |
---|
| 1895 | z->avail_out -= n; |
---|
| 1896 | z->total_out += n; |
---|
| 1897 | |
---|
| 1898 | /* update check information */ |
---|
| 1899 | if (s->checkfn != Z_NULL) |
---|
| 1900 | s->check = (*s->checkfn)(s->check, q, n); |
---|
| 1901 | |
---|
| 1902 | /* copy */ |
---|
| 1903 | zmemcpy(p, q, n); |
---|
| 1904 | p += n; |
---|
| 1905 | q += n; |
---|
| 1906 | } |
---|
| 1907 | |
---|
| 1908 | /* update pointers */ |
---|
| 1909 | z->next_out = p; |
---|
| 1910 | s->read = q; |
---|
| 1911 | |
---|
| 1912 | /* done */ |
---|
| 1913 | return r; |
---|
| 1914 | } |
---|
| 1915 | |
---|
| 1916 | |
---|
| 1917 | /*+++++*/ |
---|
| 1918 | /* inffast.c -- process literals and length/distance pairs fast |
---|
| 1919 | * Copyright (C) 1995 Mark Adler |
---|
| 1920 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 1921 | */ |
---|
| 1922 | |
---|
| 1923 | /* simplify the use of the inflate_huft type with some defines */ |
---|
| 1924 | #define base more.Base |
---|
| 1925 | #define next more.Next |
---|
| 1926 | #define exop word.what.Exop |
---|
| 1927 | #define bits word.what.Bits |
---|
| 1928 | |
---|
| 1929 | /* macros for bit input with no checking and for returning unused bytes */ |
---|
| 1930 | #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} |
---|
| 1931 | #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} |
---|
| 1932 | |
---|
| 1933 | /* Called with number of bytes left to write in window at least 258 |
---|
| 1934 | (the maximum string length) and number of input bytes available |
---|
| 1935 | at least ten. The ten bytes are six bytes for the longest length/ |
---|
| 1936 | distance pair plus four bytes for overloading the bit buffer. */ |
---|
| 1937 | |
---|
| 1938 | local int inflate_fast(bl, bd, tl, td, s, z) |
---|
| 1939 | uInt bl, bd; |
---|
| 1940 | inflate_huft *tl, *td; |
---|
| 1941 | inflate_blocks_statef *s; |
---|
| 1942 | z_stream *z; |
---|
| 1943 | { |
---|
| 1944 | inflate_huft *t; /* temporary pointer */ |
---|
| 1945 | uInt e; /* extra bits or operation */ |
---|
| 1946 | uLong b; /* bit buffer */ |
---|
| 1947 | uInt k; /* bits in bit buffer */ |
---|
| 1948 | Bytef *p; /* input data pointer */ |
---|
| 1949 | uInt n; /* bytes available there */ |
---|
| 1950 | Bytef *q; /* output window write pointer */ |
---|
| 1951 | uInt m; /* bytes to end of window or read pointer */ |
---|
| 1952 | uInt ml; /* mask for literal/length tree */ |
---|
| 1953 | uInt md; /* mask for distance tree */ |
---|
| 1954 | uInt c; /* bytes to copy */ |
---|
| 1955 | uInt d; /* distance back to copy from */ |
---|
| 1956 | Bytef *r; /* copy source pointer */ |
---|
| 1957 | |
---|
| 1958 | /* load input, output, bit values */ |
---|
| 1959 | LOAD |
---|
| 1960 | |
---|
| 1961 | /* initialize masks */ |
---|
| 1962 | ml = inflate_mask[bl]; |
---|
| 1963 | md = inflate_mask[bd]; |
---|
| 1964 | |
---|
| 1965 | /* do until not enough input or output space for fast loop */ |
---|
| 1966 | do { /* assume called with m >= 258 && n >= 10 */ |
---|
| 1967 | /* get literal/length code */ |
---|
| 1968 | GRABBITS(20) /* max bits for literal/length code */ |
---|
| 1969 | if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) |
---|
| 1970 | { |
---|
| 1971 | DUMPBITS(t->bits) |
---|
| 1972 | Tracevv(( t->base >= 0x20 && t->base < 0x7f ? |
---|
| 1973 | "inflate: * literal '%c'\n" : |
---|
| 1974 | "inflate: * literal 0x%02x\n", t->base)); |
---|
| 1975 | *q++ = (Byte)t->base; |
---|
| 1976 | m--; |
---|
| 1977 | continue; |
---|
| 1978 | } |
---|
| 1979 | do { |
---|
| 1980 | DUMPBITS(t->bits) |
---|
| 1981 | if (e & 16) |
---|
| 1982 | { |
---|
| 1983 | /* get extra bits for length */ |
---|
| 1984 | e &= 15; |
---|
| 1985 | c = t->base + ((uInt)b & inflate_mask[e]); |
---|
| 1986 | DUMPBITS(e) |
---|
| 1987 | Tracevv(( "inflate: * length %u\n", c)); |
---|
| 1988 | |
---|
| 1989 | /* decode distance base of block to copy */ |
---|
| 1990 | GRABBITS(15); /* max bits for distance code */ |
---|
| 1991 | e = (t = td + ((uInt)b & md))->exop; |
---|
| 1992 | do { |
---|
| 1993 | DUMPBITS(t->bits) |
---|
| 1994 | if (e & 16) |
---|
| 1995 | { |
---|
| 1996 | /* get extra bits to add to distance base */ |
---|
| 1997 | e &= 15; |
---|
| 1998 | GRABBITS(e) /* get extra bits (up to 13) */ |
---|
| 1999 | d = t->base + ((uInt)b & inflate_mask[e]); |
---|
| 2000 | DUMPBITS(e) |
---|
| 2001 | Tracevv(( "inflate: * distance %u\n", d)); |
---|
| 2002 | |
---|
| 2003 | /* do the copy */ |
---|
| 2004 | m -= c; |
---|
| 2005 | if ((uInt)(q - s->window) >= d) /* offset before dest */ |
---|
| 2006 | { /* just copy */ |
---|
| 2007 | r = q - d; |
---|
| 2008 | *q++ = *r++; c--; /* minimum count is three, */ |
---|
| 2009 | *q++ = *r++; c--; /* so unroll loop a little */ |
---|
| 2010 | } |
---|
| 2011 | else /* else offset after destination */ |
---|
| 2012 | { |
---|
| 2013 | e = d - (q - s->window); /* bytes from offset to end */ |
---|
| 2014 | r = s->end - e; /* pointer to offset */ |
---|
| 2015 | if (c > e) /* if source crosses, */ |
---|
| 2016 | { |
---|
| 2017 | c -= e; /* copy to end of window */ |
---|
| 2018 | do { |
---|
| 2019 | *q++ = *r++; |
---|
| 2020 | } while (--e); |
---|
| 2021 | r = s->window; /* copy rest from start of window */ |
---|
| 2022 | } |
---|
| 2023 | } |
---|
| 2024 | do { /* copy all or what's left */ |
---|
| 2025 | *q++ = *r++; |
---|
| 2026 | } while (--c); |
---|
| 2027 | break; |
---|
| 2028 | } |
---|
| 2029 | else if ((e & 64) == 0) |
---|
| 2030 | e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; |
---|
| 2031 | else |
---|
| 2032 | { |
---|
| 2033 | z->msg = "invalid distance code"; |
---|
| 2034 | UNGRAB |
---|
| 2035 | UPDATE |
---|
| 2036 | return Z_DATA_ERROR; |
---|
| 2037 | } |
---|
| 2038 | } while (1); |
---|
| 2039 | break; |
---|
| 2040 | } |
---|
| 2041 | if ((e & 64) == 0) |
---|
| 2042 | { |
---|
| 2043 | if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) |
---|
| 2044 | { |
---|
| 2045 | DUMPBITS(t->bits) |
---|
| 2046 | Tracevv(( t->base >= 0x20 && t->base < 0x7f ? |
---|
| 2047 | "inflate: * literal '%c'\n" : |
---|
| 2048 | "inflate: * literal 0x%02x\n", t->base)); |
---|
| 2049 | *q++ = (Byte)t->base; |
---|
| 2050 | m--; |
---|
| 2051 | break; |
---|
| 2052 | } |
---|
| 2053 | } |
---|
| 2054 | else if (e & 32) |
---|
| 2055 | { |
---|
| 2056 | Tracevv(( "inflate: * end of block\n")); |
---|
| 2057 | UNGRAB |
---|
| 2058 | UPDATE |
---|
| 2059 | return Z_STREAM_END; |
---|
| 2060 | } |
---|
| 2061 | else |
---|
| 2062 | { |
---|
| 2063 | z->msg = "invalid literal/length code"; |
---|
| 2064 | UNGRAB |
---|
| 2065 | UPDATE |
---|
| 2066 | return Z_DATA_ERROR; |
---|
| 2067 | } |
---|
| 2068 | } while (1); |
---|
| 2069 | } while (m >= 258 && n >= 10); |
---|
| 2070 | |
---|
| 2071 | /* not enough input or output--restore pointers and return */ |
---|
| 2072 | UNGRAB |
---|
| 2073 | UPDATE |
---|
| 2074 | return Z_OK; |
---|
| 2075 | } |
---|
| 2076 | |
---|
| 2077 | |
---|
| 2078 | /*+++++*/ |
---|
| 2079 | /* zutil.c -- target dependent utility functions for the compression library |
---|
| 2080 | * Copyright (C) 1995 Jean-loup Gailly. |
---|
| 2081 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 2082 | */ |
---|
| 2083 | |
---|
| 2084 | /* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */ |
---|
| 2085 | |
---|
| 2086 | char *zlib_version = ZLIB_VERSION; |
---|
| 2087 | |
---|
| 2088 | char *z_errmsg[] = { |
---|
| 2089 | "stream end", /* Z_STREAM_END 1 */ |
---|
| 2090 | "", /* Z_OK 0 */ |
---|
| 2091 | "file error", /* Z_ERRNO (-1) */ |
---|
| 2092 | "stream error", /* Z_STREAM_ERROR (-2) */ |
---|
| 2093 | "data error", /* Z_DATA_ERROR (-3) */ |
---|
| 2094 | "insufficient memory", /* Z_MEM_ERROR (-4) */ |
---|
| 2095 | "buffer error", /* Z_BUF_ERROR (-5) */ |
---|
| 2096 | ""}; |
---|
| 2097 | |
---|
| 2098 | |
---|
| 2099 | /*+++++*/ |
---|
| 2100 | /* adler32.c -- compute the Adler-32 checksum of a data stream |
---|
| 2101 | * Copyright (C) 1995 Mark Adler |
---|
| 2102 | * For conditions of distribution and use, see copyright notice in zlib.h |
---|
| 2103 | */ |
---|
| 2104 | |
---|
| 2105 | /* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */ |
---|
| 2106 | |
---|
| 2107 | #define BASE 65521L /* largest prime smaller than 65536 */ |
---|
| 2108 | #define NMAX 5552 |
---|
| 2109 | /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ |
---|
| 2110 | |
---|
| 2111 | #define DO1(buf) {s1 += *buf++; s2 += s1;} |
---|
| 2112 | #define DO2(buf) DO1(buf); DO1(buf); |
---|
| 2113 | #define DO4(buf) DO2(buf); DO2(buf); |
---|
| 2114 | #define DO8(buf) DO4(buf); DO4(buf); |
---|
| 2115 | #define DO16(buf) DO8(buf); DO8(buf); |
---|
| 2116 | |
---|
| 2117 | /* ========================================================================= */ |
---|
| 2118 | uLong adler32(adler, buf, len) |
---|
| 2119 | uLong adler; |
---|
| 2120 | Bytef *buf; |
---|
| 2121 | uInt len; |
---|
| 2122 | { |
---|
| 2123 | unsigned long s1 = adler & 0xffff; |
---|
| 2124 | unsigned long s2 = (adler >> 16) & 0xffff; |
---|
| 2125 | int k; |
---|
| 2126 | |
---|
| 2127 | if (buf == Z_NULL) return 1L; |
---|
| 2128 | |
---|
| 2129 | while (len > 0) { |
---|
| 2130 | k = len < NMAX ? len : NMAX; |
---|
| 2131 | len -= k; |
---|
| 2132 | while (k >= 16) { |
---|
| 2133 | DO16(buf); |
---|
| 2134 | k -= 16; |
---|
| 2135 | } |
---|
| 2136 | if (k != 0) do { |
---|
| 2137 | DO1(buf); |
---|
| 2138 | } while (--k); |
---|
| 2139 | s1 %= BASE; |
---|
| 2140 | s2 %= BASE; |
---|
| 2141 | } |
---|
| 2142 | return (s2 << 16) | s1; |
---|
| 2143 | } |
---|