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