source: rtems/bsps/powerpc/motorola_powerpc/bootloader/zlib.c @ eb36d11

5
Last change on this file since eb36d11 was 03e1d837, checked in by Sebastian Huber <sebastian.huber@…>, on 04/24/18 at 05:06:36

bsps/powerpc: Move bootloader to bsps

This bootloader is only used by the motorola_powerpc BSP.

This patch is a part of the BSP source reorganization.

Update #3285.

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