19e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* inftrees.h -- header to use inftrees.c 2381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * Copyright (C) 1995-2005, 2010 Mark Adler 39e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 49e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 59e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 69e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* WARNING: this file should *not* be used by applications. It is 79e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project part of the implementation of the compression library and is 89e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project subject to change. Applications should only use zlib.h. 99e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Structure for decoding tables. Each entry provides either the 129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project information needed to do the operation requested by the code that 139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project indexed that table entry, or it provides a pointer to another 149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project table that indexes more bits of the code. op indicates whether 159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the entry is a pointer to another table, a literal, a length or 169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project distance, an end-of-block, or an invalid code. For a table 179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project pointer, the low four bits of op is the number of index bits of 189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project that table. For a length or distance, the low four bits of op 199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project is the number of extra bits to get after the code. bits is 209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the number of bits in this code or part of the code to drop off 219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project of the bit buffer. val is the actual byte to output in the case 229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project of a literal, the base length or distance, or the offset from 239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the current table to the next table. Each entry is four bytes. */ 249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef struct { 259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char op; /* operation, extra bits, table bits */ 269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char bits; /* bits in this part of the code */ 279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned short val; /* offset in table or code value */ 289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} code; 299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* op values as set by inflate_table(): 319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 00000000 - literal 329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 0000tttt - table link, tttt != 0 is the number of table index bits 339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 0001eeee - length or distance, eeee is the number of extra bits 349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 01100000 - end of block 359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 01000000 - invalid code 369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 38381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes/* Maximum size of the dynamic table. The maximum number of code structures is 39381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes 1444, which is the sum of 852 for literal/length codes and 592 for distance 40381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes codes. These values were found by exhaustive searches using the program 41381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes examples/enough.c found in the zlib distribtution. The arguments to that 42381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes program are the number of symbols, the initial root table size, and the 43381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes maximum bit length of a code. "enough 286 9 15" for literal/length codes 44381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes returns returns 852, and "enough 30 6 15" for distance codes returns 592. 45381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes The initial root table size (9 or 6) is found in the fifth argument of the 46381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes inflate_table() calls in inflate.c and infback.c. If the root table size is 47381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes changed, then these maximum sizes would be need to be recalculated and 48381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes updated. */ 49381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#define ENOUGH_LENS 852 50381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#define ENOUGH_DISTS 592 51381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#define ENOUGH (ENOUGH_LENS+ENOUGH_DISTS) 529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 53381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes/* Type of code to build for inflate_table() */ 549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef enum { 559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project CODES, 569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project LENS, 579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project DISTS 589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} codetype; 599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 60381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesint ZLIB_INTERNAL inflate_table OF((codetype type, unsigned short FAR *lens, 619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned codes, code FAR * FAR *table, 629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned FAR *bits, unsigned short FAR *work)); 63