1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* inftrees.h -- header to use inftrees.c 2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Copyright (C) 1995-2005, 2010 Mark Adler 3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * For conditions of distribution and use, see copyright notice in zlib.h 4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* WARNING: this file should *not* be used by applications. It is 7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov part of the implementation of the compression library and is 8ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov subject to change. Applications should only use zlib.h. 9ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Structure for decoding tables. Each entry provides either the 12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov information needed to do the operation requested by the code that 13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov indexed that table entry, or it provides a pointer to another 14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov table that indexes more bits of the code. op indicates whether 15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov the entry is a pointer to another table, a literal, a length or 16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov distance, an end-of-block, or an invalid code. For a table 17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pointer, the low four bits of op is the number of index bits of 18ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov that table. For a length or distance, the low four bits of op 19ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov is the number of extra bits to get after the code. bits is 20ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov the number of bits in this code or part of the code to drop off 21ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov of the bit buffer. val is the actual byte to output in the case 22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov of a literal, the base length or distance, or the offset from 23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov the current table to the next table. Each entry is four bytes. */ 24ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtypedef struct { 25ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned char op; /* operation, extra bits, table bits */ 26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned char bits; /* bits in this part of the code */ 27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned short val; /* offset in table or code value */ 28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} code; 29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* op values as set by inflate_table(): 31ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 00000000 - literal 32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 0000tttt - table link, tttt != 0 is the number of table index bits 33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 0001eeee - length or distance, eeee is the number of extra bits 34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 01100000 - end of block 35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 01000000 - invalid code 36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Maximum size of the dynamic table. The maximum number of code structures is 39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1444, which is the sum of 852 for literal/length codes and 592 for distance 40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov codes. These values were found by exhaustive searches using the program 41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov examples/enough.c found in the zlib distribtution. The arguments to that 42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov program are the number of symbols, the initial root table size, and the 43ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov maximum bit length of a code. "enough 286 9 15" for literal/length codes 44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov returns returns 852, and "enough 30 6 15" for distance codes returns 592. 45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov The initial root table size (9 or 6) is found in the fifth argument of the 46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov inflate_table() calls in inflate.c and infback.c. If the root table size is 47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov changed, then these maximum sizes would be need to be recalculated and 48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov updated. */ 49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define ENOUGH_LENS 852 50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define ENOUGH_DISTS 592 51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define ENOUGH (ENOUGH_LENS+ENOUGH_DISTS) 52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Type of code to build for inflate_table() */ 54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtypedef enum { 55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov CODES, 56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov LENS, 57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DISTS 58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} codetype; 59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovint ZLIB_INTERNAL inflate_table OF((codetype type, unsigned short FAR *lens, 61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned codes, code FAR * FAR *table, 62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned FAR *bits, unsigned short FAR *work)); 63