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