Artifact 2f831281d83bb9952216060ef1d2547a91e9bd93:
0000: 2f 2a 20 69 6e 66 74 72 65 65 73 2e 68 20 2d 2d /* inftrees.h --
0010: 20 68 65 61 64 65 72 20 74 6f 20 75 73 65 20 69 header to use i
0020: 6e 66 74 72 65 65 73 2e 63 0a 20 2a 20 43 6f 70 nftrees.c. * Cop
0030: 79 72 69 67 68 74 20 28 43 29 20 31 39 39 35 2d yright (C) 1995-
0040: 31 39 39 38 20 4d 61 72 6b 20 41 64 6c 65 72 0a 1998 Mark Adler.
0050: 20 2a 20 46 6f 72 20 63 6f 6e 64 69 74 69 6f 6e * For condition
0060: 73 20 6f 66 20 64 69 73 74 72 69 62 75 74 69 6f s of distributio
0070: 6e 20 61 6e 64 20 75 73 65 2c 20 73 65 65 20 63 n and use, see c
0080: 6f 70 79 72 69 67 68 74 20 6e 6f 74 69 63 65 20 opyright notice
0090: 69 6e 20 7a 6c 69 62 2e 68 20 0a 20 2a 2f 0a 0a in zlib.h . */..
00a0: 2f 2a 20 57 41 52 4e 49 4e 47 3a 20 74 68 69 73 /* WARNING: this
00b0: 20 66 69 6c 65 20 73 68 6f 75 6c 64 20 2a 6e 6f file should *no
00c0: 74 2a 20 62 65 20 75 73 65 64 20 62 79 20 61 70 t* be used by ap
00d0: 70 6c 69 63 61 74 69 6f 6e 73 2e 20 49 74 20 69 plications. It i
00e0: 73 0a 20 20 20 70 61 72 74 20 6f 66 20 74 68 65 s. part of the
00f0: 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 implementation
0100: 6f 66 20 74 68 65 20 63 6f 6d 70 72 65 73 73 69 of the compressi
0110: 6f 6e 20 6c 69 62 72 61 72 79 20 61 6e 64 20 69 on library and i
0120: 73 0a 20 20 20 73 75 62 6a 65 63 74 20 74 6f 20 s. subject to
0130: 63 68 61 6e 67 65 2e 20 41 70 70 6c 69 63 61 74 change. Applicat
0140: 69 6f 6e 73 20 73 68 6f 75 6c 64 20 6f 6e 6c 79 ions should only
0150: 20 75 73 65 20 7a 6c 69 62 2e 68 2e 0a 20 2a 2f use zlib.h.. */
0160: 0a 0a 2f 2a 20 48 75 66 66 6d 61 6e 20 63 6f 64 ../* Huffman cod
0170: 65 20 6c 6f 6f 6b 75 70 20 74 61 62 6c 65 20 65 e lookup table e
0180: 6e 74 72 79 2d 2d 74 68 69 73 20 65 6e 74 72 79 ntry--this entry
0190: 20 69 73 20 66 6f 75 72 20 62 79 74 65 73 20 66 is four bytes f
01a0: 6f 72 20 6d 61 63 68 69 6e 65 73 0a 20 20 20 74 or machines. t
01b0: 68 61 74 20 68 61 76 65 20 31 36 2d 62 69 74 20 hat have 16-bit
01c0: 70 6f 69 6e 74 65 72 73 20 28 65 2e 67 2e 20 50 pointers (e.g. P
01d0: 43 27 73 20 69 6e 20 74 68 65 20 73 6d 61 6c 6c C's in the small
01e0: 20 6f 72 20 6d 65 64 69 75 6d 20 6d 6f 64 65 6c or medium model
01f0: 29 2e 20 2a 2f 0a 0a 74 79 70 65 64 65 66 20 73 ). */..typedef s
0200: 74 72 75 63 74 20 69 6e 66 6c 61 74 65 5f 68 75 truct inflate_hu
0210: 66 74 5f 73 20 46 41 52 20 69 6e 66 6c 61 74 65 ft_s FAR inflate
0220: 5f 68 75 66 74 3b 0a 0a 73 74 72 75 63 74 20 69 _huft;..struct i
0230: 6e 66 6c 61 74 65 5f 68 75 66 74 5f 73 20 7b 0a nflate_huft_s {.
0240: 20 20 75 6e 69 6f 6e 20 7b 0a 20 20 20 20 73 74 union {. st
0250: 72 75 63 74 20 7b 0a 20 20 20 20 20 20 42 79 74 ruct {. Byt
0260: 65 20 45 78 6f 70 3b 20 20 20 20 20 20 20 20 2f e Exop; /
0270: 2a 20 6e 75 6d 62 65 72 20 6f 66 20 65 78 74 72 * number of extr
0280: 61 20 62 69 74 73 20 6f 72 20 6f 70 65 72 61 74 a bits or operat
0290: 69 6f 6e 20 2a 2f 0a 20 20 20 20 20 20 42 79 74 ion */. Byt
02a0: 65 20 42 69 74 73 3b 20 20 20 20 20 20 20 20 2f e Bits; /
02b0: 2a 20 6e 75 6d 62 65 72 20 6f 66 20 62 69 74 73 * number of bits
02c0: 20 69 6e 20 74 68 69 73 20 63 6f 64 65 20 6f 72 in this code or
02d0: 20 73 75 62 63 6f 64 65 20 2a 2f 0a 20 20 20 20 subcode */.
02e0: 7d 20 77 68 61 74 3b 0a 20 20 20 20 75 49 6e 74 } what;. uInt
02f0: 20 70 61 64 3b 20 20 20 20 20 20 20 20 20 20 20 pad;
0300: 2f 2a 20 70 61 64 20 73 74 72 75 63 74 75 72 65 /* pad structure
0310: 20 74 6f 20 61 20 70 6f 77 65 72 20 6f 66 20 32 to a power of 2
0320: 20 28 34 20 62 79 74 65 73 20 66 6f 72 20 2a 2f (4 bytes for */
0330: 0a 20 20 7d 20 77 6f 72 64 3b 20 20 20 20 20 20 . } word;
0340: 20 20 20 20 20 20 20 20 20 2f 2a 20 20 31 36 2d /* 16-
0350: 62 69 74 2c 20 38 20 62 79 74 65 73 20 66 6f 72 bit, 8 bytes for
0360: 20 33 32 2d 62 69 74 20 69 6e 74 27 73 29 20 2a 32-bit int's) *
0370: 2f 0a 20 20 75 49 6e 74 20 62 61 73 65 3b 20 20 /. uInt base;
0380: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6c 69 74 /* lit
0390: 65 72 61 6c 2c 20 6c 65 6e 67 74 68 20 62 61 73 eral, length bas
03a0: 65 2c 20 64 69 73 74 61 6e 63 65 20 62 61 73 65 e, distance base
03b0: 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ,.
03c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 6f 72 20 or
03d0: 74 61 62 6c 65 20 6f 66 66 73 65 74 20 2a 2f 0a table offset */.
03e0: 7d 3b 0a 0a 2f 2a 20 4d 61 78 69 6d 75 6d 20 73 };../* Maximum s
03f0: 69 7a 65 20 6f 66 20 64 79 6e 61 6d 69 63 20 74 ize of dynamic t
0400: 72 65 65 2e 20 20 54 68 65 20 6d 61 78 69 6d 75 ree. The maximu
0410: 6d 20 66 6f 75 6e 64 20 69 6e 20 61 20 6c 6f 6e m found in a lon
0420: 67 20 62 75 74 20 6e 6f 6e 2d 0a 20 20 20 65 78 g but non-. ex
0430: 68 61 75 73 74 69 76 65 20 73 65 61 72 63 68 20 haustive search
0440: 77 61 73 20 31 30 30 34 20 68 75 66 74 20 73 74 was 1004 huft st
0450: 72 75 63 74 75 72 65 73 20 28 38 35 30 20 66 6f ructures (850 fo
0460: 72 20 6c 65 6e 67 74 68 2f 6c 69 74 65 72 61 6c r length/literal
0470: 73 0a 20 20 20 61 6e 64 20 31 35 34 20 66 6f 72 s. and 154 for
0480: 20 64 69 73 74 61 6e 63 65 73 2c 20 74 68 65 20 distances, the
0490: 6c 61 74 74 65 72 20 61 63 74 75 61 6c 6c 79 20 latter actually
04a0: 74 68 65 20 72 65 73 75 6c 74 20 6f 66 20 61 6e the result of an
04b0: 0a 20 20 20 65 78 68 61 75 73 74 69 76 65 20 73 . exhaustive s
04c0: 65 61 72 63 68 29 2e 20 20 54 68 65 20 61 63 74 earch). The act
04d0: 75 61 6c 20 6d 61 78 69 6d 75 6d 20 69 73 20 6e ual maximum is n
04e0: 6f 74 20 6b 6e 6f 77 6e 2c 20 62 75 74 20 74 68 ot known, but th
04f0: 65 0a 20 20 20 76 61 6c 75 65 20 62 65 6c 6f 77 e. value below
0500: 20 69 73 20 6d 6f 72 65 20 74 68 61 6e 20 73 61 is more than sa
0510: 66 65 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 4d fe. */.#define M
0520: 41 4e 59 20 31 34 34 30 0a 0a 65 78 74 65 72 6e ANY 1440..extern
0530: 20 69 6e 74 20 69 6e 66 6c 61 74 65 5f 74 72 65 int inflate_tre
0540: 65 73 5f 62 69 74 73 20 4f 46 28 28 0a 20 20 20 es_bits OF((.
0550: 20 75 49 6e 74 66 20 2a 2c 20 20 20 20 20 20 20 uIntf *,
0560: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
0570: 31 39 20 63 6f 64 65 20 6c 65 6e 67 74 68 73 20 19 code lengths
0580: 2a 2f 0a 20 20 20 20 75 49 6e 74 66 20 2a 2c 20 */. uIntf *,
0590: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
05a0: 20 20 20 2f 2a 20 62 69 74 73 20 74 72 65 65 20 /* bits tree
05b0: 64 65 73 69 72 65 64 2f 61 63 74 75 61 6c 20 64 desired/actual d
05c0: 65 70 74 68 20 2a 2f 0a 20 20 20 20 69 6e 66 6c epth */. infl
05d0: 61 74 65 5f 68 75 66 74 20 2a 20 46 41 52 20 2a ate_huft * FAR *
05e0: 2c 20 20 20 20 20 20 20 2f 2a 20 62 69 74 73 20 , /* bits
05f0: 74 72 65 65 20 72 65 73 75 6c 74 20 2a 2f 0a 20 tree result */.
0600: 20 20 20 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 inflate_huft
0610: 2a 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 2f *, /
0620: 2a 20 73 70 61 63 65 20 66 6f 72 20 74 72 65 65 * space for tree
0630: 73 20 2a 2f 0a 20 20 20 20 7a 5f 73 74 72 65 61 s */. z_strea
0640: 6d 70 29 29 3b 20 20 20 20 20 20 20 20 20 20 20 mp));
0650: 20 20 20 20 20 2f 2a 20 66 6f 72 20 6d 65 73 73 /* for mess
0660: 61 67 65 73 20 2a 2f 0a 0a 65 78 74 65 72 6e 20 ages */..extern
0670: 69 6e 74 20 69 6e 66 6c 61 74 65 5f 74 72 65 65 int inflate_tree
0680: 73 5f 64 79 6e 61 6d 69 63 20 4f 46 28 28 0a 20 s_dynamic OF((.
0690: 20 20 20 75 49 6e 74 2c 20 20 20 20 20 20 20 20 uInt,
06a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
06b0: 2a 20 6e 75 6d 62 65 72 20 6f 66 20 6c 69 74 65 * number of lite
06c0: 72 61 6c 2f 6c 65 6e 67 74 68 20 63 6f 64 65 73 ral/length codes
06d0: 20 2a 2f 0a 20 20 20 20 75 49 6e 74 2c 20 20 20 */. uInt,
06e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
06f0: 20 20 20 20 2f 2a 20 6e 75 6d 62 65 72 20 6f 66 /* number of
0700: 20 64 69 73 74 61 6e 63 65 20 63 6f 64 65 73 20 distance codes
0710: 2a 2f 0a 20 20 20 20 75 49 6e 74 66 20 2a 2c 20 */. uIntf *,
0720: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0730: 20 20 20 2f 2a 20 74 68 61 74 20 6d 61 6e 79 20 /* that many
0740: 28 74 6f 74 61 6c 29 20 63 6f 64 65 20 6c 65 6e (total) code len
0750: 67 74 68 73 20 2a 2f 0a 20 20 20 20 75 49 6e 74 gths */. uInt
0760: 66 20 2a 2c 20 20 20 20 20 20 20 20 20 20 20 20 f *,
0770: 20 20 20 20 20 20 20 20 2f 2a 20 6c 69 74 65 72 /* liter
0780: 61 6c 20 64 65 73 69 72 65 64 2f 61 63 74 75 61 al desired/actua
0790: 6c 20 62 69 74 20 64 65 70 74 68 20 2a 2f 0a 20 l bit depth */.
07a0: 20 20 20 75 49 6e 74 66 20 2a 2c 20 20 20 20 20 uIntf *,
07b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
07c0: 2a 20 64 69 73 74 61 6e 63 65 20 64 65 73 69 72 * distance desir
07d0: 65 64 2f 61 63 74 75 61 6c 20 62 69 74 20 64 65 ed/actual bit de
07e0: 70 74 68 20 2a 2f 0a 20 20 20 20 69 6e 66 6c 61 pth */. infla
07f0: 74 65 5f 68 75 66 74 20 2a 20 46 41 52 20 2a 2c te_huft * FAR *,
0800: 20 20 20 20 20 20 20 2f 2a 20 6c 69 74 65 72 61 /* litera
0810: 6c 2f 6c 65 6e 67 74 68 20 74 72 65 65 20 72 65 l/length tree re
0820: 73 75 6c 74 20 2a 2f 0a 20 20 20 20 69 6e 66 6c sult */. infl
0830: 61 74 65 5f 68 75 66 74 20 2a 20 46 41 52 20 2a ate_huft * FAR *
0840: 2c 20 20 20 20 20 20 20 2f 2a 20 64 69 73 74 61 , /* dista
0850: 6e 63 65 20 74 72 65 65 20 72 65 73 75 6c 74 20 nce tree result
0860: 2a 2f 0a 20 20 20 20 69 6e 66 6c 61 74 65 5f 68 */. inflate_h
0870: 75 66 74 20 2a 2c 20 20 20 20 20 20 20 20 20 20 uft *,
0880: 20 20 20 2f 2a 20 73 70 61 63 65 20 66 6f 72 20 /* space for
0890: 74 72 65 65 73 20 2a 2f 0a 20 20 20 20 7a 5f 73 trees */. z_s
08a0: 74 72 65 61 6d 70 29 29 3b 20 20 20 20 20 20 20 treamp));
08b0: 20 20 20 20 20 20 20 20 20 2f 2a 20 66 6f 72 20 /* for
08c0: 6d 65 73 73 61 67 65 73 20 2a 2f 0a 0a 65 78 74 messages */..ext
08d0: 65 72 6e 20 69 6e 74 20 69 6e 66 6c 61 74 65 5f ern int inflate_
08e0: 74 72 65 65 73 5f 66 69 78 65 64 20 4f 46 28 28 trees_fixed OF((
08f0: 0a 20 20 20 20 75 49 6e 74 66 20 2a 2c 20 20 20 . uIntf *,
0900: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0910: 20 2f 2a 20 6c 69 74 65 72 61 6c 20 64 65 73 69 /* literal desi
0920: 72 65 64 2f 61 63 74 75 61 6c 20 62 69 74 20 64 red/actual bit d
0930: 65 70 74 68 20 2a 2f 0a 20 20 20 20 75 49 6e 74 epth */. uInt
0940: 66 20 2a 2c 20 20 20 20 20 20 20 20 20 20 20 20 f *,
0950: 20 20 20 20 20 20 20 20 2f 2a 20 64 69 73 74 61 /* dista
0960: 6e 63 65 20 64 65 73 69 72 65 64 2f 61 63 74 75 nce desired/actu
0970: 61 6c 20 62 69 74 20 64 65 70 74 68 20 2a 2f 0a al bit depth */.
0980: 20 20 20 20 69 6e 66 6c 61 74 65 5f 68 75 66 74 inflate_huft
0990: 20 2a 20 46 41 52 20 2a 2c 20 20 20 20 20 20 20 * FAR *,
09a0: 2f 2a 20 6c 69 74 65 72 61 6c 2f 6c 65 6e 67 74 /* literal/lengt
09b0: 68 20 74 72 65 65 20 72 65 73 75 6c 74 20 2a 2f h tree result */
09c0: 0a 20 20 20 20 69 6e 66 6c 61 74 65 5f 68 75 66 . inflate_huf
09d0: 74 20 2a 20 46 41 52 20 2a 2c 20 20 20 20 20 20 t * FAR *,
09e0: 20 2f 2a 20 64 69 73 74 61 6e 63 65 20 74 72 65 /* distance tre
09f0: 65 20 72 65 73 75 6c 74 20 2a 2f 0a 20 20 20 20 e result */.
0a00: 7a 5f 73 74 72 65 61 6d 70 29 29 3b 20 20 20 20 z_streamp));
0a10: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 66 /* f
0a20: 6f 72 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 or memory alloca
0a30: 74 69 6f 6e 20 2a 2f 0a tion */.