source: rtems/c/src/lib/libbsp/powerpc/shared/bootloader/zlib.c @ df49c60

4.104.114.84.95
Last change on this file since df49c60 was acc25ee, checked in by Joel Sherrill <joel.sherrill@…>, on Dec 2, 1999 at 2:31:19 PM

Merged of mcp750 and mvme2307 BSP by Eric Valette <valette@…>.
As part of this effort, the mpc750 libcpu code is now shared with the
ppc6xx.

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