15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* inftrees.h -- header to use inftrees.c 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright (C) 1995-2005, 2010 Mark Adler 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * For conditions of distribution and use, see copyright notice in zlib.h 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* WARNING: this file should *not* be used by applications. It is 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) part of the implementation of the compression library and is 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) subject to change. Applications should only use zlib.h. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Structure for decoding tables. Each entry provides either the 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) information needed to do the operation requested by the code that 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) indexed that table entry, or it provides a pointer to another 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) table that indexes more bits of the code. op indicates whether 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) the entry is a pointer to another table, a literal, a length or 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) distance, an end-of-block, or an invalid code. For a table 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pointer, the low four bits of op is the number of index bits of 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) that table. For a length or distance, the low four bits of op 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) is the number of extra bits to get after the code. bits is 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) the number of bits in this code or part of the code to drop off 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) of the bit buffer. val is the actual byte to output in the case 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) of a literal, the base length or distance, or the offset from 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) the current table to the next table. Each entry is four bytes. */ 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct { 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned char op; /* operation, extra bits, table bits */ 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned char bits; /* bits in this part of the code */ 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned short val; /* offset in table or code value */ 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} code; 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* op values as set by inflate_table(): 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 00000000 - literal 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0000tttt - table link, tttt != 0 is the number of table index bits 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0001eeee - length or distance, eeee is the number of extra bits 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 01100000 - end of block 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 01000000 - invalid code 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Maximum size of the dynamic table. The maximum number of code structures is 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1444, which is the sum of 852 for literal/length codes and 592 for distance 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) codes. These values were found by exhaustive searches using the program 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) examples/enough.c found in the zlib distribtution. The arguments to that 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) program are the number of symbols, the initial root table size, and the 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) maximum bit length of a code. "enough 286 9 15" for literal/length codes 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) returns returns 852, and "enough 30 6 15" for distance codes returns 592. 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) The initial root table size (9 or 6) is found in the fifth argument of the 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inflate_table() calls in inflate.c and infback.c. If the root table size is 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) changed, then these maximum sizes would be need to be recalculated and 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) updated. */ 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define ENOUGH_LENS 852 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define ENOUGH_DISTS 592 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define ENOUGH (ENOUGH_LENS+ENOUGH_DISTS) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Type of code to build for inflate_table() */ 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef enum { 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CODES, 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LENS, 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISTS 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} codetype; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int ZLIB_INTERNAL inflate_table OF((codetype type, unsigned short FAR *lens, 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned codes, code FAR * FAR *table, 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned FAR *bits, unsigned short FAR *work)); 63