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