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