arch/xtensa/boot/lib/zlib.c

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