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