pppdump/zlib.c

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