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