18b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* inflate.h -- internal inflate state definition 217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner * Copyright (C) 1995-2009 Mark Adler 38b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 48b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 58b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 68b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* WARNING: this file should *not* be used by applications. It is 78b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project part of the implementation of the compression library and is 88b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project subject to change. Applications should only use zlib.h. 98b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* define NO_GZIP when compiling if you want to disable gzip header and 128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project trailer decoding by inflate(). NO_GZIP would be used to avoid linking in 138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project the crc code when it is not needed. For shared libraries, gzip decoding 148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project should be left enabled. */ 158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifndef NO_GZIP 168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define GUNZIP 178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif 188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* Possible inflate modes between inflate() calls */ 208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projecttypedef enum { 218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project HEAD, /* i: waiting for magic header */ 228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project FLAGS, /* i: waiting for method and flags (gzip) */ 238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project TIME, /* i: waiting for modification time (gzip) */ 248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project OS, /* i: waiting for extra flags and operating system (gzip) */ 258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project EXLEN, /* i: waiting for extra length (gzip) */ 268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project EXTRA, /* i: waiting for extra bytes (gzip) */ 278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project NAME, /* i: waiting for end of file name (gzip) */ 288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project COMMENT, /* i: waiting for end of comment (gzip) */ 298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project HCRC, /* i: waiting for header crc (gzip) */ 308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DICTID, /* i: waiting for dictionary check value */ 318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DICT, /* waiting for inflateSetDictionary() call */ 328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project TYPE, /* i: waiting for type bits, including last-flag bit */ 338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project TYPEDO, /* i: same, but skip check to exit inflate on new block */ 348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project STORED, /* i: waiting for stored size (length and complement) */ 3517b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner COPY_, /* i/o: same as COPY below, but only first time in */ 368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project COPY, /* i/o: waiting for input or output to copy stored block */ 378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project TABLE, /* i: waiting for dynamic block table lengths */ 388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project LENLENS, /* i: waiting for code length code lengths */ 398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project CODELENS, /* i: waiting for length/lit and distance code lengths */ 4017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner LEN_, /* i: same as LEN below, but only first time in */ 4117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner LEN, /* i: waiting for length/lit/eob code */ 428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project LENEXT, /* i: waiting for length extra bits */ 438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DIST, /* i: waiting for distance code */ 448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DISTEXT, /* i: waiting for distance extra bits */ 458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project MATCH, /* o: waiting for output space to copy string */ 468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project LIT, /* o: waiting for output space to write literal */ 478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project CHECK, /* i: waiting for 32-bit check value */ 488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project LENGTH, /* i: waiting for 32-bit length (gzip) */ 498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DONE, /* finished check, done -- remain here until reset */ 508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project BAD, /* got a data error -- remain here until reset */ 518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project MEM, /* got an inflate() memory error -- remain here until reset */ 528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project SYNC /* looking for synchronization bytes to restart inflate() */ 538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} inflate_mode; 548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* 568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project State transitions between above modes - 578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 5817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner (most modes can go to BAD or MEM on error -- not shown for clarity) 598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Process header: 6117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner HEAD -> (gzip) or (zlib) or (raw) 6217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME -> COMMENT -> 6317b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner HCRC -> TYPE 648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project (zlib) -> DICTID or TYPE 658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DICTID -> DICT -> TYPE 6617b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner (raw) -> TYPEDO 678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Read deflate blocks: 6817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner TYPE -> TYPEDO -> STORED or TABLE or LEN_ or CHECK 6917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner STORED -> COPY_ -> COPY -> TYPE 7017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner TABLE -> LENLENS -> CODELENS -> LEN_ 7117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner LEN_ -> LEN 7217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner Read deflate codes in fixed or dynamic block: 738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project LEN -> LENEXT or LIT or TYPE 748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project LENEXT -> DIST -> DISTEXT -> MATCH -> LEN 758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project LIT -> LEN 768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Process trailer: 778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project CHECK -> LENGTH -> DONE 788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 8017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner/* state maintained between inflate() calls. Approximately 10K bytes. */ 818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectstruct inflate_state { 828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project inflate_mode mode; /* current inflate mode */ 838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int last; /* true if processing last block */ 848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int wrap; /* bit 0 true for zlib, bit 1 true for gzip */ 858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int havedict; /* true if dictionary provided */ 868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int flags; /* gzip header method and flags (0 if zlib) */ 878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */ 888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long check; /* protected copy of check value */ 898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long total; /* protected copy of output count */ 908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project gz_headerp head; /* where to save gzip header information */ 918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* sliding window */ 928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned wbits; /* log base 2 of requested window size */ 938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned wsize; /* window size or zero if not using window */ 948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned whave; /* valid bytes in the window */ 9517b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner unsigned wnext; /* window write index */ 968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned char FAR *window; /* allocated sliding window, if needed */ 978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* bit accumulator */ 988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long hold; /* input bit accumulator */ 998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned bits; /* number of bits in "in" */ 1008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* for string and stored block copying */ 1018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned length; /* literal or length of data to copy */ 1028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned offset; /* distance back to copy string from */ 1038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* for table and code decoding */ 1048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned extra; /* extra bits needed */ 1058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* fixed and dynamic code tables */ 1068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code const FAR *lencode; /* starting table for length/literal codes */ 1078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code const FAR *distcode; /* starting table for distance codes */ 1088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned lenbits; /* index bits for lencode */ 1098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned distbits; /* index bits for distcode */ 1108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* dynamic table building */ 1118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned ncode; /* number of code length code lengths */ 1128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned nlen; /* number of length code lengths */ 1138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned ndist; /* number of distance code lengths */ 1148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned have; /* number of code lengths in lens[] */ 1158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code FAR *next; /* next available space in codes[] */ 1168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned short lens[320]; /* temporary storage for code lengths */ 1178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned short work[288]; /* work area for code table building */ 1188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code codes[ENOUGH]; /* space for code tables */ 11917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner int sane; /* if false, allow invalid distance too far */ 12017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner int back; /* bits back of last unprocessed length/lit */ 12117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner unsigned was; /* initial length of match */ 1228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project}; 123