17eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* inftrees.h -- header to use inftrees.c 27eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * Copyright (C) 1995-2005, 2010 Mark Adler 37eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * For conditions of distribution and use, see copyright notice in zlib.h 47eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 57eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 67eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* WARNING: this file should *not* be used by applications. It is 77eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel part of the implementation of the compression library and is 87eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel subject to change. Applications should only use zlib.h. 97eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* Structure for decoding tables. Each entry provides either the 127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel information needed to do the operation requested by the code that 137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel indexed that table entry, or it provides a pointer to another 147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel table that indexes more bits of the code. op indicates whether 157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel the entry is a pointer to another table, a literal, a length or 167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel distance, an end-of-block, or an invalid code. For a table 177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel pointer, the low four bits of op is the number of index bits of 187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel that table. For a length or distance, the low four bits of op 197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel is the number of extra bits to get after the code. bits is 207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel the number of bits in this code or part of the code to drop off 217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel of the bit buffer. val is the actual byte to output in the case 227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel of a literal, the base length or distance, or the offset from 237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel the current table to the next table. Each entry is four bytes. */ 247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieltypedef struct { 257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel unsigned char op; /* operation, extra bits, table bits */ 267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel unsigned char bits; /* bits in this part of the code */ 277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel unsigned short val; /* offset in table or code value */ 287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} code; 297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* op values as set by inflate_table(): 317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 00000000 - literal 327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0000tttt - table link, tttt != 0 is the number of table index bits 337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0001eeee - length or distance, eeee is the number of extra bits 347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 01100000 - end of block 357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 01000000 - invalid code 367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* Maximum size of the dynamic table. The maximum number of code structures is 397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1444, which is the sum of 852 for literal/length codes and 592 for distance 407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel codes. These values were found by exhaustive searches using the program 417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel examples/enough.c found in the zlib distribtution. The arguments to that 427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel program are the number of symbols, the initial root table size, and the 437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel maximum bit length of a code. "enough 286 9 15" for literal/length codes 447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel returns returns 852, and "enough 30 6 15" for distance codes returns 592. 457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel The initial root table size (9 or 6) is found in the fifth argument of the 467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel inflate_table() calls in inflate.c and infback.c. If the root table size is 477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel changed, then these maximum sizes would be need to be recalculated and 487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel updated. */ 497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#define ENOUGH_LENS 852 507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#define ENOUGH_DISTS 592 517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#define ENOUGH (ENOUGH_LENS+ENOUGH_DISTS) 527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* Type of code to build for inflate_table() */ 547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieltypedef enum { 557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel CODES, 567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel LENS, 577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel DISTS 587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} codetype; 597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielint ZLIB_INTERNAL inflate_table OF((codetype type, unsigned short FAR *lens, 617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel unsigned codes, code FAR * FAR *table, 627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel unsigned FAR *bits, unsigned short FAR *work)); 63