[apple/xnu.git] / libkern / zlib / inflate.h

/*
 * Copyright (c) 2008 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */
/* inflate.h -- internal inflate state definition
 * Copyright (C) 1995-2004 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the compression library and is
   subject to change. Applications should only use zlib.h.
 */

/* define NO_GZIP when compiling if you want to disable gzip header and
   trailer decoding by inflate().  NO_GZIP would be used to avoid linking in
   the crc code when it is not needed.  For shared libraries, gzip decoding
   should be left enabled. */
#ifndef NO_GZIP
#  define GUNZIP
#endif

/* Possible inflate modes between inflate() calls */
typedef enum {
    HEAD,       /* i: waiting for magic header */
    FLAGS,      /* i: waiting for method and flags (gzip) */
    TIME,       /* i: waiting for modification time (gzip) */
    OS,         /* i: waiting for extra flags and operating system (gzip) */
    EXLEN,      /* i: waiting for extra length (gzip) */
    EXTRA,      /* i: waiting for extra bytes (gzip) */
    NAME,       /* i: waiting for end of file name (gzip) */
    COMMENT,    /* i: waiting for end of comment (gzip) */
    HCRC,       /* i: waiting for header crc (gzip) */
    DICTID,     /* i: waiting for dictionary check value */
    DICT,       /* waiting for inflateSetDictionary() call */
        TYPE,       /* i: waiting for type bits, including last-flag bit */
        TYPEDO,     /* i: same, but skip check to exit inflate on new block */
        STORED,     /* i: waiting for stored size (length and complement) */
        COPY,       /* i/o: waiting for input or output to copy stored block */
        TABLE,      /* i: waiting for dynamic block table lengths */
        LENLENS,    /* i: waiting for code length code lengths */
        CODELENS,   /* i: waiting for length/lit and distance code lengths */
            LEN,        /* i: waiting for length/lit code */
            LENEXT,     /* i: waiting for length extra bits */
            DIST,       /* i: waiting for distance code */
            DISTEXT,    /* i: waiting for distance extra bits */
            MATCH,      /* o: waiting for output space to copy string */
            LIT,        /* o: waiting for output space to write literal */
    CHECK,      /* i: waiting for 32-bit check value */
    LENGTH,     /* i: waiting for 32-bit length (gzip) */
    DONE,       /* finished check, done -- remain here until reset */
    BAD,        /* got a data error -- remain here until reset */
    MEM,        /* got an inflate() memory error -- remain here until reset */
    SYNC        /* looking for synchronization bytes to restart inflate() */
} inflate_mode;

/*
    State transitions between above modes -

    (most modes can go to the BAD or MEM mode -- not shown for clarity)

    Process header:
        HEAD -> (gzip) or (zlib)
        (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
        NAME -> COMMENT -> HCRC -> TYPE
        (zlib) -> DICTID or TYPE
        DICTID -> DICT -> TYPE
    Read deflate blocks:
            TYPE -> STORED or TABLE or LEN or CHECK
            STORED -> COPY -> TYPE
            TABLE -> LENLENS -> CODELENS -> LEN
    Read deflate codes:
                LEN -> LENEXT or LIT or TYPE
                LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
                LIT -> LEN
    Process trailer:
        CHECK -> LENGTH -> DONE
 */

/* state maintained between inflate() calls.  Approximately 7K bytes. */
struct inflate_state {
    inflate_mode mode;          /* current inflate mode */
    int last;                   /* true if processing last block */
    int wrap;                   /* bit 0 true for zlib, bit 1 true for gzip */
    int havedict;               /* true if dictionary provided */
    int flags;                  /* gzip header method and flags (0 if zlib) */
    unsigned dmax;              /* zlib header max distance (INFLATE_STRICT) */
    unsigned long check;        /* protected copy of check value */
    unsigned long total;        /* protected copy of output count */
    gz_headerp head;            /* where to save gzip header information */
        /* sliding window */
    unsigned wbits;             /* log base 2 of requested window size */
    unsigned wsize;             /* window size or zero if not using window */
    unsigned whave;             /* valid bytes in the window */
    unsigned write;             /* window write index */
    unsigned char FAR *window;  /* allocated sliding window, if needed */
        /* bit accumulator */
    unsigned long hold;         /* input bit accumulator */
    unsigned bits;              /* number of bits in "in" */
        /* for string and stored block copying */
    unsigned length;            /* literal or length of data to copy */
    unsigned offset;            /* distance back to copy string from */
        /* for table and code decoding */
    unsigned extra;             /* extra bits needed */
        /* fixed and dynamic code tables */
    code const FAR *lencode;    /* starting table for length/literal codes */
    code const FAR *distcode;   /* starting table for distance codes */
    unsigned lenbits;           /* index bits for lencode */
    unsigned distbits;          /* index bits for distcode */
        /* dynamic table building */
    unsigned ncode;             /* number of code length code lengths */
    unsigned nlen;              /* number of length code lengths */
    unsigned ndist;             /* number of distance code lengths */
    unsigned have;              /* number of code lengths in lens[] */
    code FAR *next;             /* next available space in codes[] */
    unsigned short lens[320];   /* temporary storage for code lengths */
    unsigned short work[288];   /* work area for code table building */
    code codes[ENOUGH];         /* space for code tables */
};
Commit	Line	Data
b0d623f7 A	1	/*
	2	* Copyright (c) 2008 Apple Inc. All rights reserved.
	3	*
	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
	25	*
	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
	27	*/
	28	/* inflate.h -- internal inflate state definition
	29	* Copyright (C) 1995-2004 Mark Adler
	30	* For conditions of distribution and use, see copyright notice in zlib.h
	31	*/
	32
	33	/* WARNING: this file should not be used by applications. It is
	34	part of the implementation of the compression library and is
	35	subject to change. Applications should only use zlib.h.
	36	*/
	37
	38	/* define NO_GZIP when compiling if you want to disable gzip header and
	39	trailer decoding by inflate(). NO_GZIP would be used to avoid linking in
	40	the crc code when it is not needed. For shared libraries, gzip decoding
	41	should be left enabled. */
	42	#ifndef NO_GZIP
	43	# define GUNZIP
	44	#endif
	45
	46	/* Possible inflate modes between inflate() calls */
	47	typedef enum {
	48	HEAD, /* i: waiting for magic header */
	49	FLAGS, /* i: waiting for method and flags (gzip) */
	50	TIME, /* i: waiting for modification time (gzip) */
	51	OS, /* i: waiting for extra flags and operating system (gzip) */
	52	EXLEN, /* i: waiting for extra length (gzip) */
	53	EXTRA, /* i: waiting for extra bytes (gzip) */
	54	NAME, /* i: waiting for end of file name (gzip) */
	55	COMMENT, /* i: waiting for end of comment (gzip) */
	56	HCRC, /* i: waiting for header crc (gzip) */
	57	DICTID, /* i: waiting for dictionary check value */
	58	DICT, /* waiting for inflateSetDictionary() call */
	59	TYPE, /* i: waiting for type bits, including last-flag bit */
	60	TYPEDO, /* i: same, but skip check to exit inflate on new block */
	61	STORED, /* i: waiting for stored size (length and complement) */
	62	COPY, /* i/o: waiting for input or output to copy stored block */
	63	TABLE, /* i: waiting for dynamic block table lengths */
	64	LENLENS, /* i: waiting for code length code lengths */
65	CODELENS, /* i: waiting for length/lit and distance code lengths */
66	LEN, /* i: waiting for length/lit code */
67	LENEXT, /* i: waiting for length extra bits */
68	DIST, /* i: waiting for distance code */
69	DISTEXT, /* i: waiting for distance extra bits */
70	MATCH, /* o: waiting for output space to copy string */
71	LIT, /* o: waiting for output space to write literal */
72	CHECK, /* i: waiting for 32-bit check value */
73	LENGTH, /* i: waiting for 32-bit length (gzip) */
74	DONE, /* finished check, done -- remain here until reset */
75	BAD, /* got a data error -- remain here until reset */
76	MEM, /* got an inflate() memory error -- remain here until reset */
77	SYNC /* looking for synchronization bytes to restart inflate() */
78	} inflate_mode;
79
80	/*
81	State transitions between above modes -
82
83	(most modes can go to the BAD or MEM mode -- not shown for clarity)
84
85	Process header:
86	HEAD -> (gzip) or (zlib)
87	(gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
88	NAME -> COMMENT -> HCRC -> TYPE
89	(zlib) -> DICTID or TYPE
90	DICTID -> DICT -> TYPE
91	Read deflate blocks:
92	TYPE -> STORED or TABLE or LEN or CHECK
93	STORED -> COPY -> TYPE
94	TABLE -> LENLENS -> CODELENS -> LEN
95	Read deflate codes:
96	LEN -> LENEXT or LIT or TYPE
97	LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
98	LIT -> LEN
99	Process trailer:
100	CHECK -> LENGTH -> DONE
101	*/
102
103	/* state maintained between inflate() calls. Approximately 7K bytes. */
104	struct inflate_state {
105	inflate_mode mode; /* current inflate mode */
106	int last; /* true if processing last block */
107	int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
108	int havedict; /* true if dictionary provided */
109	int flags; /* gzip header method and flags (0 if zlib) */
110	unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */
111	unsigned long check; /* protected copy of check value */
112	unsigned long total; /* protected copy of output count */
113	gz_headerp head; /* where to save gzip header information */
114	/* sliding window */
115	unsigned wbits; /* log base 2 of requested window size */
116	unsigned wsize; /* window size or zero if not using window */
117	unsigned whave; /* valid bytes in the window */
118	unsigned write; /* window write index */
119	unsigned char FAR window; / allocated sliding window, if needed */
120	/* bit accumulator */
121	unsigned long hold; /* input bit accumulator */
122	unsigned bits; /* number of bits in "in" */
123	/* for string and stored block copying */
124	unsigned length; /* literal or length of data to copy */
125	unsigned offset; /* distance back to copy string from */
126	/* for table and code decoding */
127	unsigned extra; /* extra bits needed */
128	/* fixed and dynamic code tables */
129	code const FAR lencode; / starting table for length/literal codes */
130	code const FAR distcode; / starting table for distance codes */
131	unsigned lenbits; /* index bits for lencode */
132	unsigned distbits; /* index bits for distcode */
133	/* dynamic table building */
134	unsigned ncode; /* number of code length code lengths */
135	unsigned nlen; /* number of length code lengths */
136	unsigned ndist; /* number of distance code lengths */
137	unsigned have; /* number of code lengths in lens[] */
138	code FAR next; / next available space in codes[] */
139	unsigned short lens[320]; /* temporary storage for code lengths */
140	unsigned short work[288]; /* work area for code table building */
141	code codes[ENOUGH]; /* space for code tables */
142	};