libkern/zlib/inflate.h

   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 };