0000: 2f 2a 20 69 6e 66 74 72 65 65 73 2e 63 20 2d 2d /* inftrees.c --
0010: 20 67 65 6e 65 72 61 74 65 20 48 75 66 66 6d 61 generate Huffma
0020: 6e 20 74 72 65 65 73 20 66 6f 72 20 65 66 66 69 n trees for effi
0030: 63 69 65 6e 74 20 64 65 63 6f 64 69 6e 67 0a 20 cient decoding.
0040: 2a 20 43 6f 70 79 72 69 67 68 74 20 28 43 29 20 * Copyright (C)
0050: 31 39 39 35 2d 31 39 39 38 20 4d 61 72 6b 20 41 1995-1998 Mark A
0060: 64 6c 65 72 0a 20 2a 20 46 6f 72 20 63 6f 6e 64 dler. * For cond
0070: 69 74 69 6f 6e 73 20 6f 66 20 64 69 73 74 72 69 itions of distri
0080: 62 75 74 69 6f 6e 20 61 6e 64 20 75 73 65 2c 20 bution and use,
0090: 73 65 65 20 63 6f 70 79 72 69 67 68 74 20 6e 6f see copyright no
00a0: 74 69 63 65 20 69 6e 20 7a 6c 69 62 2e 68 20 0a tice in zlib.h .
00b0: 20 2a 2f 0a 0a 23 69 6e 63 6c 75 64 65 20 22 7a */..#include "z
00c0: 75 74 69 6c 2e 68 22 0a 23 69 6e 63 6c 75 64 65 util.h".#include
00d0: 20 22 69 6e 66 74 72 65 65 73 2e 68 22 0a 0a 23 "inftrees.h"..#
00e0: 69 66 20 21 64 65 66 69 6e 65 64 28 42 55 49 4c if !defined(BUIL
00f0: 44 46 49 58 45 44 29 20 26 26 20 21 64 65 66 69 DFIXED) && !defi
0100: 6e 65 64 28 53 54 44 43 29 0a 23 20 20 64 65 66 ned(STDC).# def
0110: 69 6e 65 20 42 55 49 4c 44 46 49 58 45 44 20 20 ine BUILDFIXED
0120: 20 2f 2a 20 6e 6f 6e 20 41 4e 53 49 20 63 6f 6d /* non ANSI com
0130: 70 69 6c 65 72 73 20 6d 61 79 20 6e 6f 74 20 61 pilers may not a
0140: 63 63 65 70 74 20 69 6e 66 66 69 78 65 64 2e 68 ccept inffixed.h
0150: 20 2a 2f 0a 23 65 6e 64 69 66 0a 0a 63 6f 6e 73 */.#endif..cons
0160: 74 20 63 68 61 72 20 69 6e 66 6c 61 74 65 5f 63 t char inflate_c
0170: 6f 70 79 72 69 67 68 74 5b 5d 20 3d 0a 20 20 20 opyright[] =.
0180: 22 20 69 6e 66 6c 61 74 65 20 31 2e 31 2e 33 20 " inflate 1.1.3
0190: 43 6f 70 79 72 69 67 68 74 20 31 39 39 35 2d 31 Copyright 1995-1
01a0: 39 39 38 20 4d 61 72 6b 20 41 64 6c 65 72 20 22 998 Mark Adler "
01b0: 3b 0a 2f 2a 0a 20 20 49 66 20 79 6f 75 20 75 73 ;./*. If you us
01c0: 65 20 74 68 65 20 7a 6c 69 62 20 6c 69 62 72 61 e the zlib libra
01d0: 72 79 20 69 6e 20 61 20 70 72 6f 64 75 63 74 2c ry in a product,
01e0: 20 61 6e 20 61 63 6b 6e 6f 77 6c 65 64 67 6d 65 an acknowledgme
01f0: 6e 74 20 69 73 20 77 65 6c 63 6f 6d 65 0a 20 20 nt is welcome.
0200: 69 6e 20 74 68 65 20 64 6f 63 75 6d 65 6e 74 61 in the documenta
0210: 74 69 6f 6e 20 6f 66 20 79 6f 75 72 20 70 72 6f tion of your pro
0220: 64 75 63 74 2e 20 49 66 20 66 6f 72 20 73 6f 6d duct. If for som
0230: 65 20 72 65 61 73 6f 6e 20 79 6f 75 20 63 61 6e e reason you can
0240: 6e 6f 74 0a 20 20 69 6e 63 6c 75 64 65 20 73 75 not. include su
0250: 63 68 20 61 6e 20 61 63 6b 6e 6f 77 6c 65 64 67 ch an acknowledg
0260: 6d 65 6e 74 2c 20 49 20 77 6f 75 6c 64 20 61 70 ment, I would ap
0270: 70 72 65 63 69 61 74 65 20 74 68 61 74 20 79 6f preciate that yo
0280: 75 20 6b 65 65 70 20 74 68 69 73 0a 20 20 63 6f u keep this. co
0290: 70 79 72 69 67 68 74 20 73 74 72 69 6e 67 20 69 pyright string i
02a0: 6e 20 74 68 65 20 65 78 65 63 75 74 61 62 6c 65 n the executable
02b0: 20 6f 66 20 79 6f 75 72 20 70 72 6f 64 75 63 74 of your product
02c0: 2e 0a 20 2a 2f 0a 73 74 72 75 63 74 20 69 6e 74 .. */.struct int
02d0: 65 72 6e 61 6c 5f 73 74 61 74 65 20 20 7b 69 6e ernal_state {in
02e0: 74 20 64 75 6d 6d 79 3b 7d 3b 20 2f 2a 20 66 6f t dummy;}; /* fo
02f0: 72 20 62 75 67 67 79 20 63 6f 6d 70 69 6c 65 72 r buggy compiler
0300: 73 20 2a 2f 0a 0a 2f 2a 20 73 69 6d 70 6c 69 66 s */../* simplif
0310: 79 20 74 68 65 20 75 73 65 20 6f 66 20 74 68 65 y the use of the
0320: 20 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 74 79 inflate_huft ty
0330: 70 65 20 77 69 74 68 20 73 6f 6d 65 20 64 65 66 pe with some def
0340: 69 6e 65 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 ines */.#define
0350: 65 78 6f 70 20 77 6f 72 64 2e 77 68 61 74 2e 45 exop word.what.E
0360: 78 6f 70 0a 23 64 65 66 69 6e 65 20 62 69 74 73 xop.#define bits
0370: 20 77 6f 72 64 2e 77 68 61 74 2e 42 69 74 73 0a word.what.Bits.
0380: 0a 0a 6c 6f 63 61 6c 20 69 6e 74 20 68 75 66 74 ..local int huft
0390: 5f 62 75 69 6c 64 20 4f 46 28 28 0a 20 20 20 20 _build OF((.
03a0: 75 49 6e 74 66 20 2a 2c 20 20 20 20 20 20 20 20 uIntf *,
03b0: 20 20 20 20 2f 2a 20 63 6f 64 65 20 6c 65 6e 67 /* code leng
03c0: 74 68 73 20 69 6e 20 62 69 74 73 20 2a 2f 0a 20 ths in bits */.
03d0: 20 20 20 75 49 6e 74 2c 20 20 20 20 20 20 20 20 uInt,
03e0: 20 20 20 20 20 20 20 2f 2a 20 6e 75 6d 62 65 72 /* number
03f0: 20 6f 66 20 63 6f 64 65 73 20 2a 2f 0a 20 20 20 of codes */.
0400: 20 75 49 6e 74 2c 20 20 20 20 20 20 20 20 20 20 uInt,
0410: 20 20 20 20 20 2f 2a 20 6e 75 6d 62 65 72 20 6f /* number o
0420: 66 20 22 73 69 6d 70 6c 65 22 20 63 6f 64 65 73 f "simple" codes
0430: 20 2a 2f 0a 20 20 20 20 63 6f 6e 73 74 20 75 49 */. const uI
0440: 6e 74 66 20 2a 2c 20 20 20 20 20 20 2f 2a 20 6c ntf *, /* l
0450: 69 73 74 20 6f 66 20 62 61 73 65 20 76 61 6c 75 ist of base valu
0460: 65 73 20 66 6f 72 20 6e 6f 6e 2d 73 69 6d 70 6c es for non-simpl
0470: 65 20 63 6f 64 65 73 20 2a 2f 0a 20 20 20 20 63 e codes */. c
0480: 6f 6e 73 74 20 75 49 6e 74 66 20 2a 2c 20 20 20 onst uIntf *,
0490: 20 20 20 2f 2a 20 6c 69 73 74 20 6f 66 20 65 78 /* list of ex
04a0: 74 72 61 20 62 69 74 73 20 66 6f 72 20 6e 6f 6e tra bits for non
04b0: 2d 73 69 6d 70 6c 65 20 63 6f 64 65 73 20 2a 2f -simple codes */
04c0: 0a 20 20 20 20 69 6e 66 6c 61 74 65 5f 68 75 66 . inflate_huf
04d0: 74 20 2a 20 46 41 52 2a 2c 2f 2a 20 72 65 73 75 t * FAR*,/* resu
04e0: 6c 74 3a 20 73 74 61 72 74 69 6e 67 20 74 61 62 lt: starting tab
04f0: 6c 65 20 2a 2f 0a 20 20 20 20 75 49 6e 74 66 20 le */. uIntf
0500: 2a 2c 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a *, /*
0510: 20 6d 61 78 69 6d 75 6d 20 6c 6f 6f 6b 75 70 20 maximum lookup
0520: 62 69 74 73 20 28 72 65 74 75 72 6e 73 20 61 63 bits (returns ac
0530: 74 75 61 6c 29 20 2a 2f 0a 20 20 20 20 69 6e 66 tual) */. inf
0540: 6c 61 74 65 5f 68 75 66 74 20 2a 2c 20 20 20 20 late_huft *,
0550: 20 2f 2a 20 73 70 61 63 65 20 66 6f 72 20 74 72 /* space for tr
0560: 65 65 73 20 2a 2f 0a 20 20 20 20 75 49 6e 74 20 ees */. uInt
0570: 2a 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 2f *, /
0580: 2a 20 68 75 66 74 73 20 75 73 65 64 20 69 6e 20 * hufts used in
0590: 73 70 61 63 65 20 2a 2f 0a 20 20 20 20 75 49 6e space */. uIn
05a0: 74 66 20 2a 20 29 29 3b 20 20 20 20 20 20 20 20 tf * ));
05b0: 20 2f 2a 20 73 70 61 63 65 20 66 6f 72 20 76 61 /* space for va
05c0: 6c 75 65 73 20 2a 2f 0a 0a 2f 2a 20 54 61 62 6c lues */../* Tabl
05d0: 65 73 20 66 6f 72 20 64 65 66 6c 61 74 65 20 66 es for deflate f
05e0: 72 6f 6d 20 50 4b 5a 49 50 27 73 20 61 70 70 6e rom PKZIP's appn
05f0: 6f 74 65 2e 74 78 74 2e 20 2a 2f 0a 6c 6f 63 61 ote.txt. */.loca
0600: 6c 20 63 6f 6e 73 74 20 75 49 6e 74 20 63 70 6c l const uInt cpl
0610: 65 6e 73 5b 33 31 5d 20 3d 20 7b 20 2f 2a 20 43 ens[31] = { /* C
0620: 6f 70 79 20 6c 65 6e 67 74 68 73 20 66 6f 72 20 opy lengths for
0630: 6c 69 74 65 72 61 6c 20 63 6f 64 65 73 20 32 35 literal codes 25
0640: 37 2e 2e 32 38 35 20 2a 2f 0a 20 20 20 20 20 20 7..285 */.
0650: 20 20 33 2c 20 34 2c 20 35 2c 20 36 2c 20 37 2c 3, 4, 5, 6, 7,
0660: 20 38 2c 20 39 2c 20 31 30 2c 20 31 31 2c 20 31 8, 9, 10, 11, 1
0670: 33 2c 20 31 35 2c 20 31 37 2c 20 31 39 2c 20 32 3, 15, 17, 19, 2
0680: 33 2c 20 32 37 2c 20 33 31 2c 0a 20 20 20 20 20 3, 27, 31,.
0690: 20 20 20 33 35 2c 20 34 33 2c 20 35 31 2c 20 35 35, 43, 51, 5
06a0: 39 2c 20 36 37 2c 20 38 33 2c 20 39 39 2c 20 31 9, 67, 83, 99, 1
06b0: 31 35 2c 20 31 33 31 2c 20 31 36 33 2c 20 31 39 15, 131, 163, 19
06c0: 35 2c 20 32 32 37 2c 20 32 35 38 2c 20 30 2c 20 5, 227, 258, 0,
06d0: 30 7d 3b 0a 20 20 20 20 20 20 20 20 2f 2a 20 73 0};. /* s
06e0: 65 65 20 6e 6f 74 65 20 23 31 33 20 61 62 6f 76 ee note #13 abov
06f0: 65 20 61 62 6f 75 74 20 32 35 38 20 2a 2f 0a 6c e about 258 */.l
0700: 6f 63 61 6c 20 63 6f 6e 73 74 20 75 49 6e 74 20 ocal const uInt
0710: 63 70 6c 65 78 74 5b 33 31 5d 20 3d 20 7b 20 2f cplext[31] = { /
0720: 2a 20 45 78 74 72 61 20 62 69 74 73 20 66 6f 72 * Extra bits for
0730: 20 6c 69 74 65 72 61 6c 20 63 6f 64 65 73 20 32 literal codes 2
0740: 35 37 2e 2e 32 38 35 20 2a 2f 0a 20 20 20 20 20 57..285 */.
0750: 20 20 20 30 2c 20 30 2c 20 30 2c 20 30 2c 20 30 0, 0, 0, 0, 0
0760: 2c 20 30 2c 20 30 2c 20 30 2c 20 31 2c 20 31 2c , 0, 0, 0, 1, 1,
0770: 20 31 2c 20 31 2c 20 32 2c 20 32 2c 20 32 2c 20 1, 1, 2, 2, 2,
0780: 32 2c 0a 20 20 20 20 20 20 20 20 33 2c 20 33 2c 2,. 3, 3,
0790: 20 33 2c 20 33 2c 20 34 2c 20 34 2c 20 34 2c 20 3, 3, 4, 4, 4,
07a0: 34 2c 20 35 2c 20 35 2c 20 35 2c 20 35 2c 20 30 4, 5, 5, 5, 5, 0
07b0: 2c 20 31 31 32 2c 20 31 31 32 7d 3b 20 2f 2a 20 , 112, 112}; /*
07c0: 31 31 32 3d 3d 69 6e 76 61 6c 69 64 20 2a 2f 0a 112==invalid */.
07d0: 6c 6f 63 61 6c 20 63 6f 6e 73 74 20 75 49 6e 74 local const uInt
07e0: 20 63 70 64 69 73 74 5b 33 30 5d 20 3d 20 7b 20 cpdist[30] = {
07f0: 2f 2a 20 43 6f 70 79 20 6f 66 66 73 65 74 73 20 /* Copy offsets
0800: 66 6f 72 20 64 69 73 74 61 6e 63 65 20 63 6f 64 for distance cod
0810: 65 73 20 30 2e 2e 32 39 20 2a 2f 0a 20 20 20 20 es 0..29 */.
0820: 20 20 20 20 31 2c 20 32 2c 20 33 2c 20 34 2c 20 1, 2, 3, 4,
0830: 35 2c 20 37 2c 20 39 2c 20 31 33 2c 20 31 37 2c 5, 7, 9, 13, 17,
0840: 20 32 35 2c 20 33 33 2c 20 34 39 2c 20 36 35 2c 25, 33, 49, 65,
0850: 20 39 37 2c 20 31 32 39 2c 20 31 39 33 2c 0a 20 97, 129, 193,.
0860: 20 20 20 20 20 20 20 32 35 37 2c 20 33 38 35 2c 257, 385,
0870: 20 35 31 33 2c 20 37 36 39 2c 20 31 30 32 35 2c 513, 769, 1025,
0880: 20 31 35 33 37 2c 20 32 30 34 39 2c 20 33 30 37 1537, 2049, 307
0890: 33 2c 20 34 30 39 37 2c 20 36 31 34 35 2c 0a 20 3, 4097, 6145,.
08a0: 20 20 20 20 20 20 20 38 31 39 33 2c 20 31 32 32 8193, 122
08b0: 38 39 2c 20 31 36 33 38 35 2c 20 32 34 35 37 37 89, 16385, 24577
08c0: 7d 3b 0a 6c 6f 63 61 6c 20 63 6f 6e 73 74 20 75 };.local const u
08d0: 49 6e 74 20 63 70 64 65 78 74 5b 33 30 5d 20 3d Int cpdext[30] =
08e0: 20 7b 20 2f 2a 20 45 78 74 72 61 20 62 69 74 73 { /* Extra bits
08f0: 20 66 6f 72 20 64 69 73 74 61 6e 63 65 20 63 6f for distance co
0900: 64 65 73 20 2a 2f 0a 20 20 20 20 20 20 20 20 30 des */. 0
0910: 2c 20 30 2c 20 30 2c 20 30 2c 20 31 2c 20 31 2c , 0, 0, 0, 1, 1,
0920: 20 32 2c 20 32 2c 20 33 2c 20 33 2c 20 34 2c 20 2, 2, 3, 3, 4,
0930: 34 2c 20 35 2c 20 35 2c 20 36 2c 20 36 2c 0a 20 4, 5, 5, 6, 6,.
0940: 20 20 20 20 20 20 20 37 2c 20 37 2c 20 38 2c 20 7, 7, 8,
0950: 38 2c 20 39 2c 20 39 2c 20 31 30 2c 20 31 30 2c 8, 9, 9, 10, 10,
0960: 20 31 31 2c 20 31 31 2c 0a 20 20 20 20 20 20 20 11, 11,.
0970: 20 31 32 2c 20 31 32 2c 20 31 33 2c 20 31 33 7d 12, 12, 13, 13}
0980: 3b 0a 0a 2f 2a 0a 20 20 20 48 75 66 66 6d 61 6e ;../*. Huffman
0990: 20 63 6f 64 65 20 64 65 63 6f 64 69 6e 67 20 69 code decoding i
09a0: 73 20 70 65 72 66 6f 72 6d 65 64 20 75 73 69 6e s performed usin
09b0: 67 20 61 20 6d 75 6c 74 69 2d 6c 65 76 65 6c 20 g a multi-level
09c0: 74 61 62 6c 65 20 6c 6f 6f 6b 75 70 2e 0a 20 20 table lookup..
09d0: 20 54 68 65 20 66 61 73 74 65 73 74 20 77 61 79 The fastest way
09e0: 20 74 6f 20 64 65 63 6f 64 65 20 69 73 20 74 6f to decode is to
09f0: 20 73 69 6d 70 6c 79 20 62 75 69 6c 64 20 61 20 simply build a
0a00: 6c 6f 6f 6b 75 70 20 74 61 62 6c 65 20 77 68 6f lookup table who
0a10: 73 65 0a 20 20 20 73 69 7a 65 20 69 73 20 64 65 se. size is de
0a20: 74 65 72 6d 69 6e 65 64 20 62 79 20 74 68 65 20 termined by the
0a30: 6c 6f 6e 67 65 73 74 20 63 6f 64 65 2e 20 20 48 longest code. H
0a40: 6f 77 65 76 65 72 2c 20 74 68 65 20 74 69 6d 65 owever, the time
0a50: 20 69 74 20 74 61 6b 65 73 0a 20 20 20 74 6f 20 it takes. to
0a60: 62 75 69 6c 64 20 74 68 69 73 20 74 61 62 6c 65 build this table
0a70: 20 63 61 6e 20 61 6c 73 6f 20 62 65 20 61 20 66 can also be a f
0a80: 61 63 74 6f 72 20 69 66 20 74 68 65 20 64 61 74 actor if the dat
0a90: 61 20 62 65 69 6e 67 20 64 65 63 6f 64 65 64 0a a being decoded.
0aa0: 20 20 20 69 73 20 6e 6f 74 20 76 65 72 79 20 6c is not very l
0ab0: 6f 6e 67 2e 20 20 54 68 65 20 6d 6f 73 74 20 63 ong. The most c
0ac0: 6f 6d 6d 6f 6e 20 63 6f 64 65 73 20 61 72 65 20 ommon codes are
0ad0: 6e 65 63 65 73 73 61 72 69 6c 79 20 74 68 65 0a necessarily the.
0ae0: 20 20 20 73 68 6f 72 74 65 73 74 20 63 6f 64 65 shortest code
0af0: 73 2c 20 73 6f 20 74 68 6f 73 65 20 63 6f 64 65 s, so those code
0b00: 73 20 64 6f 6d 69 6e 61 74 65 20 74 68 65 20 64 s dominate the d
0b10: 65 63 6f 64 69 6e 67 20 74 69 6d 65 2c 20 61 6e ecoding time, an
0b20: 64 20 68 65 6e 63 65 0a 20 20 20 74 68 65 20 73 d hence. the s
0b30: 70 65 65 64 2e 20 20 54 68 65 20 69 64 65 61 20 peed. The idea
0b40: 69 73 20 79 6f 75 20 63 61 6e 20 68 61 76 65 20 is you can have
0b50: 61 20 73 68 6f 72 74 65 72 20 74 61 62 6c 65 20 a shorter table
0b60: 74 68 61 74 20 64 65 63 6f 64 65 73 20 74 68 65 that decodes the
0b70: 0a 20 20 20 73 68 6f 72 74 65 72 2c 20 6d 6f 72 . shorter, mor
0b80: 65 20 70 72 6f 62 61 62 6c 65 20 63 6f 64 65 73 e probable codes
0b90: 2c 20 61 6e 64 20 74 68 65 6e 20 70 6f 69 6e 74 , and then point
0ba0: 20 74 6f 20 73 75 62 73 69 64 69 61 72 79 20 74 to subsidiary t
0bb0: 61 62 6c 65 73 20 66 6f 72 0a 20 20 20 74 68 65 ables for. the
0bc0: 20 6c 6f 6e 67 65 72 20 63 6f 64 65 73 2e 20 20 longer codes.
0bd0: 54 68 65 20 74 69 6d 65 20 69 74 20 63 6f 73 74 The time it cost
0be0: 73 20 74 6f 20 64 65 63 6f 64 65 20 74 68 65 20 s to decode the
0bf0: 6c 6f 6e 67 65 72 20 63 6f 64 65 73 20 69 73 0a longer codes is.
0c00: 20 20 20 74 68 65 6e 20 74 72 61 64 65 64 20 61 then traded a
0c10: 67 61 69 6e 73 74 20 74 68 65 20 74 69 6d 65 20 gainst the time
0c20: 69 74 20 74 61 6b 65 73 20 74 6f 20 6d 61 6b 65 it takes to make
0c30: 20 6c 6f 6e 67 65 72 20 74 61 62 6c 65 73 2e 0a longer tables..
0c40: 0a 20 20 20 54 68 69 73 20 72 65 73 75 6c 74 73 . This results
0c50: 20 6f 66 20 74 68 69 73 20 74 72 61 64 65 20 61 of this trade a
0c60: 72 65 20 69 6e 20 74 68 65 20 76 61 72 69 61 62 re in the variab
0c70: 6c 65 73 20 6c 62 69 74 73 20 61 6e 64 20 64 62 les lbits and db
0c80: 69 74 73 0a 20 20 20 62 65 6c 6f 77 2e 20 20 6c its. below. l
0c90: 62 69 74 73 20 69 73 20 74 68 65 20 6e 75 6d 62 bits is the numb
0ca0: 65 72 20 6f 66 20 62 69 74 73 20 74 68 65 20 66 er of bits the f
0cb0: 69 72 73 74 20 6c 65 76 65 6c 20 74 61 62 6c 65 irst level table
0cc0: 20 66 6f 72 20 6c 69 74 65 72 61 6c 2f 0a 20 20 for literal/.
0cd0: 20 6c 65 6e 67 74 68 20 63 6f 64 65 73 20 63 61 length codes ca
0ce0: 6e 20 64 65 63 6f 64 65 20 69 6e 20 6f 6e 65 20 n decode in one
0cf0: 73 74 65 70 2c 20 61 6e 64 20 64 62 69 74 73 20 step, and dbits
0d00: 69 73 20 74 68 65 20 73 61 6d 65 20 74 68 69 6e is the same thin
0d10: 67 20 66 6f 72 0a 20 20 20 74 68 65 20 64 69 73 g for. the dis
0d20: 74 61 6e 63 65 20 63 6f 64 65 73 2e 20 20 53 75 tance codes. Su
0d30: 62 73 65 71 75 65 6e 74 20 74 61 62 6c 65 73 20 bsequent tables
0d40: 61 72 65 20 61 6c 73 6f 20 6c 65 73 73 20 74 68 are also less th
0d50: 61 6e 20 6f 72 20 65 71 75 61 6c 20 74 6f 0a 20 an or equal to.
0d60: 20 20 74 68 6f 73 65 20 73 69 7a 65 73 2e 20 20 those sizes.
0d70: 54 68 65 73 65 20 76 61 6c 75 65 73 20 6d 61 79 These values may
0d80: 20 62 65 20 61 64 6a 75 73 74 65 64 20 65 69 74 be adjusted eit
0d90: 68 65 72 20 77 68 65 6e 20 61 6c 6c 20 6f 66 20 her when all of
0da0: 74 68 65 0a 20 20 20 63 6f 64 65 73 20 61 72 65 the. codes are
0db0: 20 73 68 6f 72 74 65 72 20 74 68 61 6e 20 74 68 shorter than th
0dc0: 61 74 2c 20 69 6e 20 77 68 69 63 68 20 63 61 73 at, in which cas
0dd0: 65 20 74 68 65 20 6c 6f 6e 67 65 73 74 20 63 6f e the longest co
0de0: 64 65 20 6c 65 6e 67 74 68 20 69 6e 0a 20 20 20 de length in.
0df0: 62 69 74 73 20 69 73 20 75 73 65 64 2c 20 6f 72 bits is used, or
0e00: 20 77 68 65 6e 20 74 68 65 20 73 68 6f 72 74 65 when the shorte
0e10: 73 74 20 63 6f 64 65 20 69 73 20 2a 6c 6f 6e 67 st code is *long
0e20: 65 72 2a 20 74 68 61 6e 20 74 68 65 20 72 65 71 er* than the req
0e30: 75 65 73 74 65 64 0a 20 20 20 74 61 62 6c 65 20 uested. table
0e40: 73 69 7a 65 2c 20 69 6e 20 77 68 69 63 68 20 63 size, in which c
0e50: 61 73 65 20 74 68 65 20 6c 65 6e 67 74 68 20 6f ase the length o
0e60: 66 20 74 68 65 20 73 68 6f 72 74 65 73 74 20 63 f the shortest c
0e70: 6f 64 65 20 69 6e 20 62 69 74 73 20 69 73 0a 20 ode in bits is.
0e80: 20 20 75 73 65 64 2e 0a 0a 20 20 20 54 68 65 72 used... Ther
0e90: 65 20 61 72 65 20 74 77 6f 20 64 69 66 66 65 72 e are two differ
0ea0: 65 6e 74 20 76 61 6c 75 65 73 20 66 6f 72 20 74 ent values for t
0eb0: 68 65 20 74 77 6f 20 74 61 62 6c 65 73 2c 20 73 he two tables, s
0ec0: 69 6e 63 65 20 74 68 65 79 20 63 6f 64 65 20 61 ince they code a
0ed0: 0a 20 20 20 64 69 66 66 65 72 65 6e 74 20 6e 75 . different nu
0ee0: 6d 62 65 72 20 6f 66 20 70 6f 73 73 69 62 69 6c mber of possibil
0ef0: 69 74 69 65 73 20 65 61 63 68 2e 20 20 54 68 65 ities each. The
0f00: 20 6c 69 74 65 72 61 6c 2f 6c 65 6e 67 74 68 20 literal/length
0f10: 74 61 62 6c 65 0a 20 20 20 63 6f 64 65 73 20 32 table. codes 2
0f20: 38 36 20 70 6f 73 73 69 62 6c 65 20 76 61 6c 75 86 possible valu
0f30: 65 73 2c 20 6f 72 20 69 6e 20 61 20 66 6c 61 74 es, or in a flat
0f40: 20 63 6f 64 65 2c 20 61 20 6c 69 74 74 6c 65 20 code, a little
0f50: 6f 76 65 72 20 65 69 67 68 74 0a 20 20 20 62 69 over eight. bi
0f60: 74 73 2e 20 20 54 68 65 20 64 69 73 74 61 6e 63 ts. The distanc
0f70: 65 20 74 61 62 6c 65 20 63 6f 64 65 73 20 33 30 e table codes 30
0f80: 20 70 6f 73 73 69 62 6c 65 20 76 61 6c 75 65 73 possible values
0f90: 2c 20 6f 72 20 61 20 6c 69 74 74 6c 65 20 6c 65 , or a little le
0fa0: 73 73 0a 20 20 20 74 68 61 6e 20 66 69 76 65 20 ss. than five
0fb0: 62 69 74 73 2c 20 66 6c 61 74 2e 20 20 54 68 65 bits, flat. The
0fc0: 20 6f 70 74 69 6d 75 6d 20 76 61 6c 75 65 73 20 optimum values
0fd0: 66 6f 72 20 73 70 65 65 64 20 65 6e 64 20 75 70 for speed end up
0fe0: 20 62 65 69 6e 67 0a 20 20 20 61 62 6f 75 74 20 being. about
0ff0: 6f 6e 65 20 62 69 74 20 6d 6f 72 65 20 74 68 61 one bit more tha
1000: 6e 20 74 68 6f 73 65 2c 20 73 6f 20 6c 62 69 74 n those, so lbit
1010: 73 20 69 73 20 38 2b 31 20 61 6e 64 20 64 62 69 s is 8+1 and dbi
1020: 74 73 20 69 73 20 35 2b 31 2e 0a 20 20 20 54 68 ts is 5+1.. Th
1030: 65 20 6f 70 74 69 6d 75 6d 20 76 61 6c 75 65 73 e optimum values
1040: 20 6d 61 79 20 64 69 66 66 65 72 20 74 68 6f 75 may differ thou
1050: 67 68 20 66 72 6f 6d 20 6d 61 63 68 69 6e 65 20 gh from machine
1060: 74 6f 20 6d 61 63 68 69 6e 65 2c 20 61 6e 64 0a to machine, and.
1070: 20 20 20 70 6f 73 73 69 62 6c 79 20 65 76 65 6e possibly even
1080: 20 62 65 74 77 65 65 6e 20 63 6f 6d 70 69 6c 65 between compile
1090: 72 73 2e 20 20 59 6f 75 72 20 6d 69 6c 65 61 67 rs. Your mileag
10a0: 65 20 6d 61 79 20 76 61 72 79 2e 0a 20 2a 2f 0a e may vary.. */.
10b0: 0a 0a 2f 2a 20 49 66 20 42 4d 41 58 20 6e 65 65 ../* If BMAX nee
10c0: 64 73 20 74 6f 20 62 65 20 6c 61 72 67 65 72 20 ds to be larger
10d0: 74 68 61 6e 20 31 36 2c 20 74 68 65 6e 20 68 20 than 16, then h
10e0: 61 6e 64 20 78 5b 5d 20 73 68 6f 75 6c 64 20 62 and x[] should b
10f0: 65 20 75 4c 6f 6e 67 2e 20 2a 2f 0a 23 64 65 66 e uLong. */.#def
1100: 69 6e 65 20 42 4d 41 58 20 31 35 20 20 20 20 20 ine BMAX 15
1110: 20 20 20 20 2f 2a 20 6d 61 78 69 6d 75 6d 20 62 /* maximum b
1120: 69 74 20 6c 65 6e 67 74 68 20 6f 66 20 61 6e 79 it length of any
1130: 20 63 6f 64 65 20 2a 2f 0a 0a 6c 6f 63 61 6c 20 code */..local
1140: 69 6e 74 20 68 75 66 74 5f 62 75 69 6c 64 28 62 int huft_build(b
1150: 2c 20 6e 2c 20 73 2c 20 64 2c 20 65 2c 20 74 2c , n, s, d, e, t,
1160: 20 6d 2c 20 68 70 2c 20 68 6e 2c 20 76 29 0a 75 m, hp, hn, v).u
1170: 49 6e 74 66 20 2a 62 3b 20 20 20 20 20 20 20 20 Intf *b;
1180: 20 20 20 20 20 20 20 2f 2a 20 63 6f 64 65 20 6c /* code l
1190: 65 6e 67 74 68 73 20 69 6e 20 62 69 74 73 20 28 engths in bits (
11a0: 61 6c 6c 20 61 73 73 75 6d 65 64 20 3c 3d 20 42 all assumed <= B
11b0: 4d 41 58 29 20 2a 2f 0a 75 49 6e 74 20 6e 3b 20 MAX) */.uInt n;
11c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
11d0: 2f 2a 20 6e 75 6d 62 65 72 20 6f 66 20 63 6f 64 /* number of cod
11e0: 65 73 20 28 61 73 73 75 6d 65 64 20 3c 3d 20 32 es (assumed <= 2
11f0: 38 38 29 20 2a 2f 0a 75 49 6e 74 20 73 3b 20 20 88) */.uInt s;
1200: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
1210: 2a 20 6e 75 6d 62 65 72 20 6f 66 20 73 69 6d 70 * number of simp
1220: 6c 65 2d 76 61 6c 75 65 64 20 63 6f 64 65 73 20 le-valued codes
1230: 28 30 2e 2e 73 2d 31 29 20 2a 2f 0a 63 6f 6e 73 (0..s-1) */.cons
1240: 74 20 75 49 6e 74 66 20 2a 64 3b 20 20 20 20 20 t uIntf *d;
1250: 20 20 20 20 2f 2a 20 6c 69 73 74 20 6f 66 20 62 /* list of b
1260: 61 73 65 20 76 61 6c 75 65 73 20 66 6f 72 20 6e ase values for n
1270: 6f 6e 2d 73 69 6d 70 6c 65 20 63 6f 64 65 73 20 on-simple codes
1280: 2a 2f 0a 63 6f 6e 73 74 20 75 49 6e 74 66 20 2a */.const uIntf *
1290: 65 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 6c 69 e; /* li
12a0: 73 74 20 6f 66 20 65 78 74 72 61 20 62 69 74 73 st of extra bits
12b0: 20 66 6f 72 20 6e 6f 6e 2d 73 69 6d 70 6c 65 20 for non-simple
12c0: 63 6f 64 65 73 20 2a 2f 0a 69 6e 66 6c 61 74 65 codes */.inflate
12d0: 5f 68 75 66 74 20 2a 20 46 41 52 20 2a 74 3b 20 _huft * FAR *t;
12e0: 20 2f 2a 20 72 65 73 75 6c 74 3a 20 73 74 61 72 /* result: star
12f0: 74 69 6e 67 20 74 61 62 6c 65 20 2a 2f 0a 75 49 ting table */.uI
1300: 6e 74 66 20 2a 6d 3b 20 20 20 20 20 20 20 20 20 ntf *m;
1310: 20 20 20 20 20 20 2f 2a 20 6d 61 78 69 6d 75 6d /* maximum
1320: 20 6c 6f 6f 6b 75 70 20 62 69 74 73 2c 20 72 65 lookup bits, re
1330: 74 75 72 6e 73 20 61 63 74 75 61 6c 20 2a 2f 0a turns actual */.
1340: 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 2a 68 70 inflate_huft *hp
1350: 3b 20 20 20 20 20 20 20 2f 2a 20 73 70 61 63 65 ; /* space
1360: 20 66 6f 72 20 74 72 65 65 73 20 2a 2f 0a 75 49 for trees */.uI
1370: 6e 74 20 2a 68 6e 3b 20 20 20 20 20 20 20 20 20 nt *hn;
1380: 20 20 20 20 20 20 2f 2a 20 68 75 66 74 73 20 75 /* hufts u
1390: 73 65 64 20 69 6e 20 73 70 61 63 65 20 2a 2f 0a sed in space */.
13a0: 75 49 6e 74 66 20 2a 76 3b 20 20 20 20 20 20 20 uIntf *v;
13b0: 20 20 20 20 20 20 20 20 2f 2a 20 77 6f 72 6b 69 /* worki
13c0: 6e 67 20 61 72 65 61 3a 20 76 61 6c 75 65 73 20 ng area: values
13d0: 69 6e 20 6f 72 64 65 72 20 6f 66 20 62 69 74 20 in order of bit
13e0: 6c 65 6e 67 74 68 20 2a 2f 0a 2f 2a 20 47 69 76 length */./* Giv
13f0: 65 6e 20 61 20 6c 69 73 74 20 6f 66 20 63 6f 64 en a list of cod
1400: 65 20 6c 65 6e 67 74 68 73 20 61 6e 64 20 61 20 e lengths and a
1410: 6d 61 78 69 6d 75 6d 20 74 61 62 6c 65 20 73 69 maximum table si
1420: 7a 65 2c 20 6d 61 6b 65 20 61 20 73 65 74 20 6f ze, make a set o
1430: 66 0a 20 20 20 74 61 62 6c 65 73 20 74 6f 20 64 f. tables to d
1440: 65 63 6f 64 65 20 74 68 61 74 20 73 65 74 20 6f ecode that set o
1450: 66 20 63 6f 64 65 73 2e 20 20 52 65 74 75 72 6e f codes. Return
1460: 20 5a 5f 4f 4b 20 6f 6e 20 73 75 63 63 65 73 73 Z_OK on success
1470: 2c 20 5a 5f 42 55 46 5f 45 52 52 4f 52 0a 20 20 , Z_BUF_ERROR.
1480: 20 69 66 20 74 68 65 20 67 69 76 65 6e 20 63 6f if the given co
1490: 64 65 20 73 65 74 20 69 73 20 69 6e 63 6f 6d 70 de set is incomp
14a0: 6c 65 74 65 20 28 74 68 65 20 74 61 62 6c 65 73 lete (the tables
14b0: 20 61 72 65 20 73 74 69 6c 6c 20 62 75 69 6c 74 are still built
14c0: 20 69 6e 20 74 68 69 73 0a 20 20 20 63 61 73 65 in this. case
14d0: 29 2c 20 5a 5f 44 41 54 41 5f 45 52 52 4f 52 20 ), Z_DATA_ERROR
14e0: 69 66 20 74 68 65 20 69 6e 70 75 74 20 69 73 20 if the input is
14f0: 69 6e 76 61 6c 69 64 20 28 61 6e 20 6f 76 65 72 invalid (an over
1500: 2d 73 75 62 73 63 72 69 62 65 64 20 73 65 74 20 -subscribed set
1510: 6f 66 0a 20 20 20 6c 65 6e 67 74 68 73 29 2c 20 of. lengths),
1520: 6f 72 20 5a 5f 4d 45 4d 5f 45 52 52 4f 52 20 69 or Z_MEM_ERROR i
1530: 66 20 6e 6f 74 20 65 6e 6f 75 67 68 20 6d 65 6d f not enough mem
1540: 6f 72 79 2e 20 2a 2f 0a 7b 0a 0a 20 20 75 49 6e ory. */.{.. uIn
1550: 74 20 61 3b 20 20 20 20 20 20 20 20 20 20 20 20 t a;
1560: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 63 6f /* co
1570: 75 6e 74 65 72 20 66 6f 72 20 63 6f 64 65 73 20 unter for codes
1580: 6f 66 20 6c 65 6e 67 74 68 20 6b 20 2a 2f 0a 20 of length k */.
1590: 20 75 49 6e 74 20 63 5b 42 4d 41 58 2b 31 5d 3b uInt c[BMAX+1];
15a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
15b0: 2a 20 62 69 74 20 6c 65 6e 67 74 68 20 63 6f 75 * bit length cou
15c0: 6e 74 20 74 61 62 6c 65 20 2a 2f 0a 20 20 75 49 nt table */. uI
15d0: 6e 74 20 66 3b 20 20 20 20 20 20 20 20 20 20 20 nt f;
15e0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 69 /* i
15f0: 20 72 65 70 65 61 74 73 20 69 6e 20 74 61 62 6c repeats in tabl
1600: 65 20 65 76 65 72 79 20 66 20 65 6e 74 72 69 65 e every f entrie
1610: 73 20 2a 2f 0a 20 20 69 6e 74 20 67 3b 20 20 20 s */. int g;
1620: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1630: 20 20 20 20 20 2f 2a 20 6d 61 78 69 6d 75 6d 20 /* maximum
1640: 63 6f 64 65 20 6c 65 6e 67 74 68 20 2a 2f 0a 20 code length */.
1650: 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20 20 20 int h;
1660: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
1670: 2a 20 74 61 62 6c 65 20 6c 65 76 65 6c 20 2a 2f * table level */
1680: 0a 20 20 72 65 67 69 73 74 65 72 20 75 49 6e 74 . register uInt
1690: 20 69 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 i;
16a0: 20 2f 2a 20 63 6f 75 6e 74 65 72 2c 20 63 75 72 /* counter, cur
16b0: 72 65 6e 74 20 63 6f 64 65 20 2a 2f 0a 20 20 72 rent code */. r
16c0: 65 67 69 73 74 65 72 20 75 49 6e 74 20 6a 3b 20 egister uInt j;
16d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
16e0: 63 6f 75 6e 74 65 72 20 2a 2f 0a 20 20 72 65 67 counter */. reg
16f0: 69 73 74 65 72 20 69 6e 74 20 6b 3b 20 20 20 20 ister int k;
1700: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6e 75 /* nu
1710: 6d 62 65 72 20 6f 66 20 62 69 74 73 20 69 6e 20 mber of bits in
1720: 63 75 72 72 65 6e 74 20 63 6f 64 65 20 2a 2f 0a current code */.
1730: 20 20 69 6e 74 20 6c 3b 20 20 20 20 20 20 20 20 int l;
1740: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1750: 2f 2a 20 62 69 74 73 20 70 65 72 20 74 61 62 6c /* bits per tabl
1760: 65 20 28 72 65 74 75 72 6e 65 64 20 69 6e 20 6d e (returned in m
1770: 29 20 2a 2f 0a 20 20 75 49 6e 74 20 6d 61 73 6b ) */. uInt mask
1780: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;
1790: 20 20 20 20 20 2f 2a 20 28 31 20 3c 3c 20 77 29 /* (1 << w)
17a0: 20 2d 20 31 2c 20 74 6f 20 61 76 6f 69 64 20 63 - 1, to avoid c
17b0: 63 20 2d 4f 20 62 75 67 20 6f 6e 20 48 50 20 2a c -O bug on HP *
17c0: 2f 0a 20 20 72 65 67 69 73 74 65 72 20 75 49 6e /. register uIn
17d0: 74 66 20 2a 70 3b 20 20 20 20 20 20 20 20 20 20 tf *p;
17e0: 20 20 2f 2a 20 70 6f 69 6e 74 65 72 20 69 6e 74 /* pointer int
17f0: 6f 20 63 5b 5d 2c 20 62 5b 5d 2c 20 6f 72 20 76 o c[], b[], or v
1800: 5b 5d 20 2a 2f 0a 20 20 69 6e 66 6c 61 74 65 5f [] */. inflate_
1810: 68 75 66 74 20 2a 71 3b 20 20 20 20 20 20 20 20 huft *q;
1820: 20 20 20 20 20 20 2f 2a 20 70 6f 69 6e 74 73 20 /* points
1830: 74 6f 20 63 75 72 72 65 6e 74 20 74 61 62 6c 65 to current table
1840: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 69 6e 66 */. struct inf
1850: 6c 61 74 65 5f 68 75 66 74 5f 73 20 72 3b 20 20 late_huft_s r;
1860: 20 20 20 20 2f 2a 20 74 61 62 6c 65 20 65 6e 74 /* table ent
1870: 72 79 20 66 6f 72 20 73 74 72 75 63 74 75 72 65 ry for structure
1880: 20 61 73 73 69 67 6e 6d 65 6e 74 20 2a 2f 0a 20 assignment */.
1890: 20 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 2a 75 inflate_huft *u
18a0: 5b 42 4d 41 58 5d 3b 20 20 20 20 20 20 20 20 2f [BMAX]; /
18b0: 2a 20 74 61 62 6c 65 20 73 74 61 63 6b 20 2a 2f * table stack */
18c0: 0a 20 20 72 65 67 69 73 74 65 72 20 69 6e 74 20 . register int
18d0: 77 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 w;
18e0: 20 2f 2a 20 62 69 74 73 20 62 65 66 6f 72 65 20 /* bits before
18f0: 74 68 69 73 20 74 61 62 6c 65 20 3d 3d 20 28 6c this table == (l
1900: 20 2a 20 68 29 20 2a 2f 0a 20 20 75 49 6e 74 20 * h) */. uInt
1910: 78 5b 42 4d 41 58 2b 31 5d 3b 20 20 20 20 20 20 x[BMAX+1];
1920: 20 20 20 20 20 20 20 20 20 2f 2a 20 62 69 74 20 /* bit
1930: 6f 66 66 73 65 74 73 2c 20 74 68 65 6e 20 63 6f offsets, then co
1940: 64 65 20 73 74 61 63 6b 20 2a 2f 0a 20 20 75 49 de stack */. uI
1950: 6e 74 66 20 2a 78 70 3b 20 20 20 20 20 20 20 20 ntf *xp;
1960: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 70 /* p
1970: 6f 69 6e 74 65 72 20 69 6e 74 6f 20 78 20 2a 2f ointer into x */
1980: 0a 20 20 69 6e 74 20 79 3b 20 20 20 20 20 20 20 . int y;
1990: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
19a0: 20 2f 2a 20 6e 75 6d 62 65 72 20 6f 66 20 64 75 /* number of du
19b0: 6d 6d 79 20 63 6f 64 65 73 20 61 64 64 65 64 20 mmy codes added
19c0: 2a 2f 0a 20 20 75 49 6e 74 20 7a 3b 20 20 20 20 */. uInt z;
19d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
19e0: 20 20 20 2f 2a 20 6e 75 6d 62 65 72 20 6f 66 20 /* number of
19f0: 65 6e 74 72 69 65 73 20 69 6e 20 63 75 72 72 65 entries in curre
1a00: 6e 74 20 74 61 62 6c 65 20 2a 2f 0a 0a 0a 20 20 nt table */...
1a10: 2f 2a 20 47 65 6e 65 72 61 74 65 20 63 6f 75 6e /* Generate coun
1a20: 74 73 20 66 6f 72 20 65 61 63 68 20 62 69 74 20 ts for each bit
1a30: 6c 65 6e 67 74 68 20 2a 2f 0a 20 20 70 20 3d 20 length */. p =
1a40: 63 3b 0a 23 64 65 66 69 6e 65 20 43 30 20 2a 70 c;.#define C0 *p
1a50: 2b 2b 20 3d 20 30 3b 0a 23 64 65 66 69 6e 65 20 ++ = 0;.#define
1a60: 43 32 20 43 30 20 43 30 20 43 30 20 43 30 0a 23 C2 C0 C0 C0 C0.#
1a70: 64 65 66 69 6e 65 20 43 34 20 43 32 20 43 32 20 define C4 C2 C2
1a80: 43 32 20 43 32 0a 20 20 43 34 20 20 20 20 20 20 C2 C2. C4
1a90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1aa0: 20 20 20 20 20 20 2f 2a 20 63 6c 65 61 72 20 63 /* clear c
1ab0: 5b 5d 2d 2d 61 73 73 75 6d 65 20 42 4d 41 58 2b []--assume BMAX+
1ac0: 31 20 69 73 20 31 36 20 2a 2f 0a 20 20 70 20 3d 1 is 16 */. p =
1ad0: 20 62 3b 20 20 69 20 3d 20 6e 3b 0a 20 20 64 6f b; i = n;. do
1ae0: 20 7b 0a 20 20 20 20 63 5b 2a 70 2b 2b 5d 2b 2b {. c[*p++]++
1af0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;
1b00: 20 20 20 2f 2a 20 61 73 73 75 6d 65 20 61 6c 6c /* assume all
1b10: 20 65 6e 74 72 69 65 73 20 3c 3d 20 42 4d 41 58 entries <= BMAX
1b20: 20 2a 2f 0a 20 20 7d 20 77 68 69 6c 65 20 28 2d */. } while (-
1b30: 2d 69 29 3b 0a 20 20 69 66 20 28 63 5b 30 5d 20 -i);. if (c[0]
1b40: 3d 3d 20 6e 29 20 20 20 20 20 20 20 20 20 20 20 == n)
1b50: 20 20 20 20 20 2f 2a 20 6e 75 6c 6c 20 69 6e 70 /* null inp
1b60: 75 74 2d 2d 61 6c 6c 20 7a 65 72 6f 20 6c 65 6e ut--all zero len
1b70: 67 74 68 20 63 6f 64 65 73 20 2a 2f 0a 20 20 7b gth codes */. {
1b80: 0a 20 20 20 20 2a 74 20 3d 20 28 69 6e 66 6c 61 . *t = (infla
1b90: 74 65 5f 68 75 66 74 20 2a 29 5a 5f 4e 55 4c 4c te_huft *)Z_NULL
1ba0: 3b 0a 20 20 20 20 2a 6d 20 3d 20 30 3b 0a 20 20 ;. *m = 0;.
1bb0: 20 20 72 65 74 75 72 6e 20 5a 5f 4f 4b 3b 0a 20 return Z_OK;.
1bc0: 20 7d 0a 0a 0a 20 20 2f 2a 20 46 69 6e 64 20 6d }... /* Find m
1bd0: 69 6e 69 6d 75 6d 20 61 6e 64 20 6d 61 78 69 6d inimum and maxim
1be0: 75 6d 20 6c 65 6e 67 74 68 2c 20 62 6f 75 6e 64 um length, bound
1bf0: 20 2a 6d 20 62 79 20 74 68 6f 73 65 20 2a 2f 0a *m by those */.
1c00: 20 20 6c 20 3d 20 2a 6d 3b 0a 20 20 66 6f 72 20 l = *m;. for
1c10: 28 6a 20 3d 20 31 3b 20 6a 20 3c 3d 20 42 4d 41 (j = 1; j <= BMA
1c20: 58 3b 20 6a 2b 2b 29 0a 20 20 20 20 69 66 20 28 X; j++). if (
1c30: 63 5b 6a 5d 29 0a 20 20 20 20 20 20 62 72 65 61 c[j]). brea
1c40: 6b 3b 0a 20 20 6b 20 3d 20 6a 3b 20 20 20 20 20 k;. k = j;
1c50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1c60: 20 20 20 2f 2a 20 6d 69 6e 69 6d 75 6d 20 63 6f /* minimum co
1c70: 64 65 20 6c 65 6e 67 74 68 20 2a 2f 0a 20 20 69 de length */. i
1c80: 66 20 28 28 75 49 6e 74 29 6c 20 3c 20 6a 29 0a f ((uInt)l < j).
1c90: 20 20 20 20 6c 20 3d 20 6a 3b 0a 20 20 66 6f 72 l = j;. for
1ca0: 20 28 69 20 3d 20 42 4d 41 58 3b 20 69 3b 20 69 (i = BMAX; i; i
1cb0: 2d 2d 29 0a 20 20 20 20 69 66 20 28 63 5b 69 5d --). if (c[i]
1cc0: 29 0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 ). break;.
1cd0: 20 67 20 3d 20 69 3b 20 20 20 20 20 20 20 20 20 g = i;
1ce0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
1cf0: 2a 20 6d 61 78 69 6d 75 6d 20 63 6f 64 65 20 6c * maximum code l
1d00: 65 6e 67 74 68 20 2a 2f 0a 20 20 69 66 20 28 28 ength */. if ((
1d10: 75 49 6e 74 29 6c 20 3e 20 69 29 0a 20 20 20 20 uInt)l > i).
1d20: 6c 20 3d 20 69 3b 0a 20 20 2a 6d 20 3d 20 6c 3b l = i;. *m = l;
1d30: 0a 0a 0a 20 20 2f 2a 20 41 64 6a 75 73 74 20 6c ... /* Adjust l
1d40: 61 73 74 20 6c 65 6e 67 74 68 20 63 6f 75 6e 74 ast length count
1d50: 20 74 6f 20 66 69 6c 6c 20 6f 75 74 20 63 6f 64 to fill out cod
1d60: 65 73 2c 20 69 66 20 6e 65 65 64 65 64 20 2a 2f es, if needed */
1d70: 0a 20 20 66 6f 72 20 28 79 20 3d 20 31 20 3c 3c . for (y = 1 <<
1d80: 20 6a 3b 20 6a 20 3c 20 69 3b 20 6a 2b 2b 2c 20 j; j < i; j++,
1d90: 79 20 3c 3c 3d 20 31 29 0a 20 20 20 20 69 66 20 y <<= 1). if
1da0: 28 28 79 20 2d 3d 20 63 5b 6a 5d 29 20 3c 20 30 ((y -= c[j]) < 0
1db0: 29 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 5a ). return Z
1dc0: 5f 44 41 54 41 5f 45 52 52 4f 52 3b 0a 20 20 69 _DATA_ERROR;. i
1dd0: 66 20 28 28 79 20 2d 3d 20 63 5b 69 5d 29 20 3c f ((y -= c[i]) <
1de0: 20 30 29 0a 20 20 20 20 72 65 74 75 72 6e 20 5a 0). return Z
1df0: 5f 44 41 54 41 5f 45 52 52 4f 52 3b 0a 20 20 63 _DATA_ERROR;. c
1e00: 5b 69 5d 20 2b 3d 20 79 3b 0a 0a 0a 20 20 2f 2a [i] += y;... /*
1e10: 20 47 65 6e 65 72 61 74 65 20 73 74 61 72 74 69 Generate starti
1e20: 6e 67 20 6f 66 66 73 65 74 73 20 69 6e 74 6f 20 ng offsets into
1e30: 74 68 65 20 76 61 6c 75 65 20 74 61 62 6c 65 20 the value table
1e40: 66 6f 72 20 65 61 63 68 20 6c 65 6e 67 74 68 20 for each length
1e50: 2a 2f 0a 20 20 78 5b 31 5d 20 3d 20 6a 20 3d 20 */. x[1] = j =
1e60: 30 3b 0a 20 20 70 20 3d 20 63 20 2b 20 31 3b 20 0;. p = c + 1;
1e70: 20 78 70 20 3d 20 78 20 2b 20 32 3b 0a 20 20 77 xp = x + 2;. w
1e80: 68 69 6c 65 20 28 2d 2d 69 29 20 7b 20 20 20 20 hile (--i) {
1e90: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
1ea0: 6e 6f 74 65 20 74 68 61 74 20 69 20 3d 3d 20 67 note that i == g
1eb0: 20 66 72 6f 6d 20 61 62 6f 76 65 20 2a 2f 0a 20 from above */.
1ec0: 20 20 20 2a 78 70 2b 2b 20 3d 20 28 6a 20 2b 3d *xp++ = (j +=
1ed0: 20 2a 70 2b 2b 29 3b 0a 20 20 7d 0a 0a 0a 20 20 *p++);. }...
1ee0: 2f 2a 20 4d 61 6b 65 20 61 20 74 61 62 6c 65 20 /* Make a table
1ef0: 6f 66 20 76 61 6c 75 65 73 20 69 6e 20 6f 72 64 of values in ord
1f00: 65 72 20 6f 66 20 62 69 74 20 6c 65 6e 67 74 68 er of bit length
1f10: 73 20 2a 2f 0a 20 20 70 20 3d 20 62 3b 20 20 69 s */. p = b; i
1f20: 20 3d 20 30 3b 0a 20 20 64 6f 20 7b 0a 20 20 20 = 0;. do {.
1f30: 20 69 66 20 28 28 6a 20 3d 20 2a 70 2b 2b 29 20 if ((j = *p++)
1f40: 21 3d 20 30 29 0a 20 20 20 20 20 20 76 5b 78 5b != 0). v[x[
1f50: 6a 5d 2b 2b 5d 20 3d 20 69 3b 0a 20 20 7d 20 77 j]++] = i;. } w
1f60: 68 69 6c 65 20 28 2b 2b 69 20 3c 20 6e 29 3b 0a hile (++i < n);.
1f70: 20 20 6e 20 3d 20 78 5b 67 5d 3b 20 20 20 20 20 n = x[g];
1f80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1f90: 2f 2a 20 73 65 74 20 6e 20 74 6f 20 6c 65 6e 67 /* set n to leng
1fa0: 74 68 20 6f 66 20 76 20 2a 2f 0a 0a 0a 20 20 2f th of v */... /
1fb0: 2a 20 47 65 6e 65 72 61 74 65 20 74 68 65 20 48 * Generate the H
1fc0: 75 66 66 6d 61 6e 20 63 6f 64 65 73 20 61 6e 64 uffman codes and
1fd0: 20 66 6f 72 20 65 61 63 68 2c 20 6d 61 6b 65 20 for each, make
1fe0: 74 68 65 20 74 61 62 6c 65 20 65 6e 74 72 69 65 the table entrie
1ff0: 73 20 2a 2f 0a 20 20 78 5b 30 5d 20 3d 20 69 20 s */. x[0] = i
2000: 3d 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 20 = 0;
2010: 20 20 20 20 20 2f 2a 20 66 69 72 73 74 20 48 75 /* first Hu
2020: 66 66 6d 61 6e 20 63 6f 64 65 20 69 73 20 7a 65 ffman code is ze
2030: 72 6f 20 2a 2f 0a 20 20 70 20 3d 20 76 3b 20 20 ro */. p = v;
2040: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2050: 20 20 20 20 20 20 2f 2a 20 67 72 61 62 20 76 61 /* grab va
2060: 6c 75 65 73 20 69 6e 20 62 69 74 20 6f 72 64 65 lues in bit orde
2070: 72 20 2a 2f 0a 20 20 68 20 3d 20 2d 31 3b 20 20 r */. h = -1;
2080: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2090: 20 20 20 20 20 2f 2a 20 6e 6f 20 74 61 62 6c 65 /* no table
20a0: 73 20 79 65 74 2d 2d 6c 65 76 65 6c 20 2d 31 20 s yet--level -1
20b0: 2a 2f 0a 20 20 77 20 3d 20 2d 6c 3b 20 20 20 20 */. w = -l;
20c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
20d0: 20 20 20 2f 2a 20 62 69 74 73 20 64 65 63 6f 64 /* bits decod
20e0: 65 64 20 3d 3d 20 28 6c 20 2a 20 68 29 20 2a 2f ed == (l * h) */
20f0: 0a 20 20 75 5b 30 5d 20 3d 20 28 69 6e 66 6c 61 . u[0] = (infla
2100: 74 65 5f 68 75 66 74 20 2a 29 5a 5f 4e 55 4c 4c te_huft *)Z_NULL
2110: 3b 20 20 20 20 20 20 20 20 2f 2a 20 6a 75 73 74 ; /* just
2120: 20 74 6f 20 6b 65 65 70 20 63 6f 6d 70 69 6c 65 to keep compile
2130: 72 73 20 68 61 70 70 79 20 2a 2f 0a 20 20 71 20 rs happy */. q
2140: 3d 20 28 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 = (inflate_huft
2150: 2a 29 5a 5f 4e 55 4c 4c 3b 20 20 20 2f 2a 20 64 *)Z_NULL; /* d
2160: 69 74 74 6f 20 2a 2f 0a 20 20 7a 20 3d 20 30 3b itto */. z = 0;
2170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2180: 20 20 20 20 20 20 20 20 2f 2a 20 64 69 74 74 6f /* ditto
2190: 20 2a 2f 0a 0a 20 20 2f 2a 20 67 6f 20 74 68 72 */.. /* go thr
21a0: 6f 75 67 68 20 74 68 65 20 62 69 74 20 6c 65 6e ough the bit len
21b0: 67 74 68 73 20 28 6b 20 61 6c 72 65 61 64 79 20 gths (k already
21c0: 69 73 20 62 69 74 73 20 69 6e 20 73 68 6f 72 74 is bits in short
21d0: 65 73 74 20 63 6f 64 65 29 20 2a 2f 0a 20 20 66 est code) */. f
21e0: 6f 72 20 28 3b 20 6b 20 3c 3d 20 67 3b 20 6b 2b or (; k <= g; k+
21f0: 2b 29 0a 20 20 7b 0a 20 20 20 20 61 20 3d 20 63 +). {. a = c
2200: 5b 6b 5d 3b 0a 20 20 20 20 77 68 69 6c 65 20 28 [k];. while (
2210: 61 2d 2d 29 0a 20 20 20 20 7b 0a 20 20 20 20 20 a--). {.
2220: 20 2f 2a 20 68 65 72 65 20 69 20 69 73 20 74 68 /* here i is th
2230: 65 20 48 75 66 66 6d 61 6e 20 63 6f 64 65 20 6f e Huffman code o
2240: 66 20 6c 65 6e 67 74 68 20 6b 20 62 69 74 73 20 f length k bits
2250: 66 6f 72 20 76 61 6c 75 65 20 2a 70 20 2a 2f 0a for value *p */.
2260: 20 20 20 20 20 20 2f 2a 20 6d 61 6b 65 20 74 61 /* make ta
2270: 62 6c 65 73 20 75 70 20 74 6f 20 72 65 71 75 69 bles up to requi
2280: 72 65 64 20 6c 65 76 65 6c 20 2a 2f 0a 20 20 20 red level */.
2290: 20 20 20 77 68 69 6c 65 20 28 6b 20 3e 20 77 20 while (k > w
22a0: 2b 20 6c 29 0a 20 20 20 20 20 20 7b 0a 20 20 20 + l). {.
22b0: 20 20 20 20 20 68 2b 2b 3b 0a 20 20 20 20 20 20 h++;.
22c0: 20 20 77 20 2b 3d 20 6c 3b 20 20 20 20 20 20 20 w += l;
22d0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 70 72 65 /* pre
22e0: 76 69 6f 75 73 20 74 61 62 6c 65 20 61 6c 77 61 vious table alwa
22f0: 79 73 20 6c 20 62 69 74 73 20 2a 2f 0a 0a 20 20 ys l bits */..
2300: 20 20 20 20 20 20 2f 2a 20 63 6f 6d 70 75 74 65 /* compute
2310: 20 6d 69 6e 69 6d 75 6d 20 73 69 7a 65 20 74 61 minimum size ta
2320: 62 6c 65 20 6c 65 73 73 20 74 68 61 6e 20 6f 72 ble less than or
2330: 20 65 71 75 61 6c 20 74 6f 20 6c 20 62 69 74 73 equal to l bits
2340: 20 2a 2f 0a 20 20 20 20 20 20 20 20 7a 20 3d 20 */. z =
2350: 67 20 2d 20 77 3b 0a 20 20 20 20 20 20 20 20 7a g - w;. z
2360: 20 3d 20 7a 20 3e 20 28 75 49 6e 74 29 6c 20 3f = z > (uInt)l ?
2370: 20 6c 20 3a 20 7a 3b 20 20 20 20 20 20 20 20 2f l : z; /
2380: 2a 20 74 61 62 6c 65 20 73 69 7a 65 20 75 70 70 * table size upp
2390: 65 72 20 6c 69 6d 69 74 20 2a 2f 0a 20 20 20 20 er limit */.
23a0: 20 20 20 20 69 66 20 28 28 66 20 3d 20 31 20 3c if ((f = 1 <
23b0: 3c 20 28 6a 20 3d 20 6b 20 2d 20 77 29 29 20 3e < (j = k - w)) >
23c0: 20 61 20 2b 20 31 29 20 20 20 20 20 2f 2a 20 74 a + 1) /* t
23d0: 72 79 20 61 20 6b 2d 77 20 62 69 74 20 74 61 62 ry a k-w bit tab
23e0: 6c 65 20 2a 2f 0a 20 20 20 20 20 20 20 20 7b 20 le */. {
23f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2400: 20 20 20 20 20 20 2f 2a 20 74 6f 6f 20 66 65 77 /* too few
2410: 20 63 6f 64 65 73 20 66 6f 72 20 6b 2d 77 20 62 codes for k-w b
2420: 69 74 20 74 61 62 6c 65 20 2a 2f 0a 20 20 20 20 it table */.
2430: 20 20 20 20 20 20 66 20 2d 3d 20 61 20 2b 20 31 f -= a + 1
2440: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 64 ; /* d
2450: 65 64 75 63 74 20 63 6f 64 65 73 20 66 72 6f 6d educt codes from
2460: 20 70 61 74 74 65 72 6e 73 20 6c 65 66 74 20 2a patterns left *
2470: 2f 0a 20 20 20 20 20 20 20 20 20 20 78 70 20 3d /. xp =
2480: 20 63 20 2b 20 6b 3b 0a 20 20 20 20 20 20 20 20 c + k;.
2490: 20 20 69 66 20 28 6a 20 3c 20 7a 29 0a 20 20 20 if (j < z).
24a0: 20 20 20 20 20 20 20 20 20 77 68 69 6c 65 20 28 while (
24b0: 2b 2b 6a 20 3c 20 7a 29 20 20 20 20 20 2f 2a 20 ++j < z) /*
24c0: 74 72 79 20 73 6d 61 6c 6c 65 72 20 74 61 62 6c try smaller tabl
24d0: 65 73 20 75 70 20 74 6f 20 7a 20 62 69 74 73 20 es up to z bits
24e0: 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 7b */. {
24f0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 . i
2500: 66 20 28 28 66 20 3c 3c 3d 20 31 29 20 3c 3d 20 f ((f <<= 1) <=
2510: 2a 2b 2b 78 70 29 0a 20 20 20 20 20 20 20 20 20 *++xp).
2520: 20 20 20 20 20 20 20 62 72 65 61 6b 3b 20 20 20 break;
2530: 20 20 20 20 20 20 20 2f 2a 20 65 6e 6f 75 67 68 /* enough
2540: 20 63 6f 64 65 73 20 74 6f 20 75 73 65 20 75 70 codes to use up
2550: 20 6a 20 62 69 74 73 20 2a 2f 0a 20 20 20 20 20 j bits */.
2560: 20 20 20 20 20 20 20 20 20 66 20 2d 3d 20 2a 78 f -= *x
2570: 70 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 65 6c p; /* el
2580: 73 65 20 64 65 64 75 63 74 20 63 6f 64 65 73 20 se deduct codes
2590: 66 72 6f 6d 20 70 61 74 74 65 72 6e 73 20 2a 2f from patterns */
25a0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 . }.
25b0: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 }.
25c0: 20 7a 20 3d 20 31 20 3c 3c 20 6a 3b 20 20 20 20 z = 1 << j;
25d0: 20 20 20 20 20 20 20 20 20 2f 2a 20 74 61 62 6c /* tabl
25e0: 65 20 65 6e 74 72 69 65 73 20 66 6f 72 20 6a 2d e entries for j-
25f0: 62 69 74 20 74 61 62 6c 65 20 2a 2f 0a 0a 20 20 bit table */..
2600: 20 20 20 20 20 20 2f 2a 20 61 6c 6c 6f 63 61 74 /* allocat
2610: 65 20 6e 65 77 20 74 61 62 6c 65 20 2a 2f 0a 20 e new table */.
2620: 20 20 20 20 20 20 20 69 66 20 28 2a 68 6e 20 2b if (*hn +
2630: 20 7a 20 3e 20 4d 41 4e 59 29 20 20 20 20 20 2f z > MANY) /
2640: 2a 20 28 6e 6f 74 65 3a 20 64 6f 65 73 6e 27 74 * (note: doesn't
2650: 20 6d 61 74 74 65 72 20 66 6f 72 20 66 69 78 65 matter for fixe
2660: 64 29 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 d) */.
2670: 72 65 74 75 72 6e 20 5a 5f 4d 45 4d 5f 45 52 52 return Z_MEM_ERR
2680: 4f 52 3b 20 20 20 2f 2a 20 6e 6f 74 20 65 6e 6f OR; /* not eno
2690: 75 67 68 20 6d 65 6d 6f 72 79 20 2a 2f 0a 20 20 ugh memory */.
26a0: 20 20 20 20 20 20 75 5b 68 5d 20 3d 20 71 20 3d u[h] = q =
26b0: 20 68 70 20 2b 20 2a 68 6e 3b 0a 20 20 20 20 20 hp + *hn;.
26c0: 20 20 20 2a 68 6e 20 2b 3d 20 7a 3b 0a 0a 20 20 *hn += z;..
26d0: 20 20 20 20 20 20 2f 2a 20 63 6f 6e 6e 65 63 74 /* connect
26e0: 20 74 6f 20 6c 61 73 74 20 74 61 62 6c 65 2c 20 to last table,
26f0: 69 66 20 74 68 65 72 65 20 69 73 20 6f 6e 65 20 if there is one
2700: 2a 2f 0a 20 20 20 20 20 20 20 20 69 66 20 28 68 */. if (h
2710: 29 0a 20 20 20 20 20 20 20 20 7b 0a 20 20 20 20 ). {.
2720: 20 20 20 20 20 20 78 5b 68 5d 20 3d 20 69 3b 20 x[h] = i;
2730: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 73 /* s
2740: 61 76 65 20 70 61 74 74 65 72 6e 20 66 6f 72 20 ave pattern for
2750: 62 61 63 6b 69 6e 67 20 75 70 20 2a 2f 0a 20 20 backing up */.
2760: 20 20 20 20 20 20 20 20 72 2e 62 69 74 73 20 3d r.bits =
2770: 20 28 42 79 74 65 29 6c 3b 20 20 20 20 20 2f 2a (Byte)l; /*
2780: 20 62 69 74 73 20 74 6f 20 64 75 6d 70 20 62 65 bits to dump be
2790: 66 6f 72 65 20 74 68 69 73 20 74 61 62 6c 65 20 fore this table
27a0: 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 72 2e 65 */. r.e
27b0: 78 6f 70 20 3d 20 28 42 79 74 65 29 6a 3b 20 20 xop = (Byte)j;
27c0: 20 20 20 2f 2a 20 62 69 74 73 20 69 6e 20 74 68 /* bits in th
27d0: 69 73 20 74 61 62 6c 65 20 2a 2f 0a 20 20 20 20 is table */.
27e0: 20 20 20 20 20 20 6a 20 3d 20 69 20 3e 3e 20 28 j = i >> (
27f0: 77 20 2d 20 6c 29 3b 0a 20 20 20 20 20 20 20 20 w - l);.
2800: 20 20 72 2e 62 61 73 65 20 3d 20 28 75 49 6e 74 r.base = (uInt
2810: 29 28 71 20 2d 20 75 5b 68 2d 31 5d 20 2d 20 6a )(q - u[h-1] - j
2820: 29 3b 20 20 20 2f 2a 20 6f 66 66 73 65 74 20 74 ); /* offset t
2830: 6f 20 74 68 69 73 20 74 61 62 6c 65 20 2a 2f 0a o this table */.
2840: 20 20 20 20 20 20 20 20 20 20 75 5b 68 2d 31 5d u[h-1]
2850: 5b 6a 5d 20 3d 20 72 3b 20 20 20 20 20 20 20 20 [j] = r;
2860: 2f 2a 20 63 6f 6e 6e 65 63 74 20 74 6f 20 6c 61 /* connect to la
2870: 73 74 20 74 61 62 6c 65 20 2a 2f 0a 20 20 20 20 st table */.
2880: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 65 6c }. el
2890: 73 65 0a 20 20 20 20 20 20 20 20 20 20 2a 74 20 se. *t
28a0: 3d 20 71 3b 20 20 20 20 20 20 20 20 20 20 20 20 = q;
28b0: 20 20 20 2f 2a 20 66 69 72 73 74 20 74 61 62 6c /* first tabl
28c0: 65 20 69 73 20 72 65 74 75 72 6e 65 64 20 72 65 e is returned re
28d0: 73 75 6c 74 20 2a 2f 0a 20 20 20 20 20 20 7d 0a sult */. }.
28e0: 0a 20 20 20 20 20 20 2f 2a 20 73 65 74 20 75 70 . /* set up
28f0: 20 74 61 62 6c 65 20 65 6e 74 72 79 20 69 6e 20 table entry in
2900: 72 20 2a 2f 0a 20 20 20 20 20 20 72 2e 62 69 74 r */. r.bit
2910: 73 20 3d 20 28 42 79 74 65 29 28 6b 20 2d 20 77 s = (Byte)(k - w
2920: 29 3b 0a 20 20 20 20 20 20 69 66 20 28 70 20 3e );. if (p >
2930: 3d 20 76 20 2b 20 6e 29 0a 20 20 20 20 20 20 20 = v + n).
2940: 20 72 2e 65 78 6f 70 20 3d 20 31 32 38 20 2b 20 r.exop = 128 +
2950: 36 34 3b 20 20 20 20 20 20 2f 2a 20 6f 75 74 20 64; /* out
2960: 6f 66 20 76 61 6c 75 65 73 2d 2d 69 6e 76 61 6c of values--inval
2970: 69 64 20 63 6f 64 65 20 2a 2f 0a 20 20 20 20 20 id code */.
2980: 20 65 6c 73 65 20 69 66 20 28 2a 70 20 3c 20 73 else if (*p < s
2990: 29 0a 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 ). {.
29a0: 20 20 72 2e 65 78 6f 70 20 3d 20 28 42 79 74 65 r.exop = (Byte
29b0: 29 28 2a 70 20 3c 20 32 35 36 20 3f 20 30 20 3a )(*p < 256 ? 0 :
29c0: 20 33 32 20 2b 20 36 34 29 3b 20 20 20 20 20 2f 32 + 64); /
29d0: 2a 20 32 35 36 20 69 73 20 65 6e 64 2d 6f 66 2d * 256 is end-of-
29e0: 62 6c 6f 63 6b 20 2a 2f 0a 20 20 20 20 20 20 20 block */.
29f0: 20 72 2e 62 61 73 65 20 3d 20 2a 70 2b 2b 3b 20 r.base = *p++;
2a00: 20 20 20 20 20 20 20 20 20 2f 2a 20 73 69 6d 70 /* simp
2a10: 6c 65 20 63 6f 64 65 20 69 73 20 6a 75 73 74 20 le code is just
2a20: 74 68 65 20 76 61 6c 75 65 20 2a 2f 0a 20 20 20 the value */.
2a30: 20 20 20 7d 0a 20 20 20 20 20 20 65 6c 73 65 0a }. else.
2a40: 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 {.
2a50: 72 2e 65 78 6f 70 20 3d 20 28 42 79 74 65 29 28 r.exop = (Byte)(
2a60: 65 5b 2a 70 20 2d 20 73 5d 20 2b 20 31 36 20 2b e[*p - s] + 16 +
2a70: 20 36 34 29 3b 2f 2a 20 6e 6f 6e 2d 73 69 6d 70 64);/* non-simp
2a80: 6c 65 2d 2d 6c 6f 6f 6b 20 75 70 20 69 6e 20 6c le--look up in l
2a90: 69 73 74 73 20 2a 2f 0a 20 20 20 20 20 20 20 20 ists */.
2aa0: 72 2e 62 61 73 65 20 3d 20 64 5b 2a 70 2b 2b 20 r.base = d[*p++
2ab0: 2d 20 73 5d 3b 0a 20 20 20 20 20 20 7d 0a 0a 20 - s];. }..
2ac0: 20 20 20 20 20 2f 2a 20 66 69 6c 6c 20 63 6f 64 /* fill cod
2ad0: 65 2d 6c 69 6b 65 20 65 6e 74 72 69 65 73 20 77 e-like entries w
2ae0: 69 74 68 20 72 20 2a 2f 0a 20 20 20 20 20 20 66 ith r */. f
2af0: 20 3d 20 31 20 3c 3c 20 28 6b 20 2d 20 77 29 3b = 1 << (k - w);
2b00: 0a 20 20 20 20 20 20 66 6f 72 20 28 6a 20 3d 20 . for (j =
2b10: 69 20 3e 3e 20 77 3b 20 6a 20 3c 20 7a 3b 20 6a i >> w; j < z; j
2b20: 20 2b 3d 20 66 29 0a 20 20 20 20 20 20 20 20 71 += f). q
2b30: 5b 6a 5d 20 3d 20 72 3b 0a 0a 20 20 20 20 20 20 [j] = r;..
2b40: 2f 2a 20 62 61 63 6b 77 61 72 64 73 20 69 6e 63 /* backwards inc
2b50: 72 65 6d 65 6e 74 20 74 68 65 20 6b 2d 62 69 74 rement the k-bit
2b60: 20 63 6f 64 65 20 69 20 2a 2f 0a 20 20 20 20 20 code i */.
2b70: 20 66 6f 72 20 28 6a 20 3d 20 31 20 3c 3c 20 28 for (j = 1 << (
2b80: 6b 20 2d 20 31 29 3b 20 69 20 26 20 6a 3b 20 6a k - 1); i & j; j
2b90: 20 3e 3e 3d 20 31 29 0a 20 20 20 20 20 20 20 20 >>= 1).
2ba0: 69 20 5e 3d 20 6a 3b 0a 20 20 20 20 20 20 69 20 i ^= j;. i
2bb0: 5e 3d 20 6a 3b 0a 0a 20 20 20 20 20 20 2f 2a 20 ^= j;.. /*
2bc0: 62 61 63 6b 75 70 20 6f 76 65 72 20 66 69 6e 69 backup over fini
2bd0: 73 68 65 64 20 74 61 62 6c 65 73 20 2a 2f 0a 20 shed tables */.
2be0: 20 20 20 20 20 6d 61 73 6b 20 3d 20 28 31 20 3c mask = (1 <
2bf0: 3c 20 77 29 20 2d 20 31 3b 20 20 20 20 20 20 2f < w) - 1; /
2c00: 2a 20 6e 65 65 64 65 64 20 6f 6e 20 48 50 2c 20 * needed on HP,
2c10: 63 63 20 2d 4f 20 62 75 67 20 2a 2f 0a 20 20 20 cc -O bug */.
2c20: 20 20 20 77 68 69 6c 65 20 28 28 69 20 26 20 6d while ((i & m
2c30: 61 73 6b 29 20 21 3d 20 78 5b 68 5d 29 0a 20 20 ask) != x[h]).
2c40: 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 68 2d {. h-
2c50: 2d 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 -;
2c60: 20 20 20 20 20 20 2f 2a 20 64 6f 6e 27 74 20 6e /* don't n
2c70: 65 65 64 20 74 6f 20 75 70 64 61 74 65 20 71 20 eed to update q
2c80: 2a 2f 0a 20 20 20 20 20 20 20 20 77 20 2d 3d 20 */. w -=
2c90: 6c 3b 0a 20 20 20 20 20 20 20 20 6d 61 73 6b 20 l;. mask
2ca0: 3d 20 28 31 20 3c 3c 20 77 29 20 2d 20 31 3b 0a = (1 << w) - 1;.
2cb0: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 }. }.
2cc0: 7d 0a 0a 0a 20 20 2f 2a 20 52 65 74 75 72 6e 20 }... /* Return
2cd0: 5a 5f 42 55 46 5f 45 52 52 4f 52 20 69 66 20 77 Z_BUF_ERROR if w
2ce0: 65 20 77 65 72 65 20 67 69 76 65 6e 20 61 6e 20 e were given an
2cf0: 69 6e 63 6f 6d 70 6c 65 74 65 20 74 61 62 6c 65 incomplete table
2d00: 20 2a 2f 0a 20 20 72 65 74 75 72 6e 20 79 20 21 */. return y !
2d10: 3d 20 30 20 26 26 20 67 20 21 3d 20 31 20 3f 20 = 0 && g != 1 ?
2d20: 5a 5f 42 55 46 5f 45 52 52 4f 52 20 3a 20 5a 5f Z_BUF_ERROR : Z_
2d30: 4f 4b 3b 0a 7d 0a 0a 0a 69 6e 74 20 69 6e 66 6c OK;.}...int infl
2d40: 61 74 65 5f 74 72 65 65 73 5f 62 69 74 73 28 63 ate_trees_bits(c
2d50: 2c 20 62 62 2c 20 74 62 2c 20 68 70 2c 20 7a 29 , bb, tb, hp, z)
2d60: 0a 75 49 6e 74 66 20 2a 63 3b 20 20 20 20 20 20 .uIntf *c;
2d70: 20 20 20 20 20 20 20 20 20 2f 2a 20 31 39 20 63 /* 19 c
2d80: 6f 64 65 20 6c 65 6e 67 74 68 73 20 2a 2f 0a 75 ode lengths */.u
2d90: 49 6e 74 66 20 2a 62 62 3b 20 20 20 20 20 20 20 Intf *bb;
2da0: 20 20 20 20 20 20 20 2f 2a 20 62 69 74 73 20 74 /* bits t
2db0: 72 65 65 20 64 65 73 69 72 65 64 2f 61 63 74 75 ree desired/actu
2dc0: 61 6c 20 64 65 70 74 68 20 2a 2f 0a 69 6e 66 6c al depth */.infl
2dd0: 61 74 65 5f 68 75 66 74 20 2a 20 46 41 52 20 2a ate_huft * FAR *
2de0: 74 62 3b 20 2f 2a 20 62 69 74 73 20 74 72 65 65 tb; /* bits tree
2df0: 20 72 65 73 75 6c 74 20 2a 2f 0a 69 6e 66 6c 61 result */.infla
2e00: 74 65 5f 68 75 66 74 20 2a 68 70 3b 20 20 20 20 te_huft *hp;
2e10: 20 20 20 2f 2a 20 73 70 61 63 65 20 66 6f 72 20 /* space for
2e20: 74 72 65 65 73 20 2a 2f 0a 7a 5f 73 74 72 65 61 trees */.z_strea
2e30: 6d 70 20 7a 3b 20 20 20 20 20 20 20 20 20 20 20 mp z;
2e40: 20 2f 2a 20 66 6f 72 20 6d 65 73 73 61 67 65 73 /* for messages
2e50: 20 2a 2f 0a 7b 0a 20 20 69 6e 74 20 72 3b 0a 20 */.{. int r;.
2e60: 20 75 49 6e 74 20 68 6e 20 3d 20 30 3b 20 20 20 uInt hn = 0;
2e70: 20 20 20 20 20 20 20 2f 2a 20 68 75 66 74 73 20 /* hufts
2e80: 75 73 65 64 20 69 6e 20 73 70 61 63 65 20 2a 2f used in space */
2e90: 0a 20 20 75 49 6e 74 66 20 2a 76 3b 20 20 20 20 . uIntf *v;
2ea0: 20 20 20 20 20 20 20 20 20 2f 2a 20 77 6f 72 6b /* work
2eb0: 20 61 72 65 61 20 66 6f 72 20 68 75 66 74 5f 62 area for huft_b
2ec0: 75 69 6c 64 20 2a 2f 0a 0a 20 20 69 66 20 28 28 uild */.. if ((
2ed0: 76 20 3d 20 28 75 49 6e 74 66 2a 29 5a 41 4c 4c v = (uIntf*)ZALL
2ee0: 4f 43 28 7a 2c 20 31 39 2c 20 73 69 7a 65 6f 66 OC(z, 19, sizeof
2ef0: 28 75 49 6e 74 29 29 29 20 3d 3d 20 5a 5f 4e 55 (uInt))) == Z_NU
2f00: 4c 4c 29 0a 20 20 20 20 72 65 74 75 72 6e 20 5a LL). return Z
2f10: 5f 4d 45 4d 5f 45 52 52 4f 52 3b 0a 20 20 72 20 _MEM_ERROR;. r
2f20: 3d 20 68 75 66 74 5f 62 75 69 6c 64 28 63 2c 20 = huft_build(c,
2f30: 31 39 2c 20 31 39 2c 20 28 75 49 6e 74 66 2a 29 19, 19, (uIntf*)
2f40: 5a 5f 4e 55 4c 4c 2c 20 28 75 49 6e 74 66 2a 29 Z_NULL, (uIntf*)
2f50: 5a 5f 4e 55 4c 4c 2c 0a 20 20 20 20 20 20 20 20 Z_NULL,.
2f60: 20 20 20 20 20 20 20 20 20 74 62 2c 20 62 62 2c tb, bb,
2f70: 20 68 70 2c 20 26 68 6e 2c 20 76 29 3b 0a 20 20 hp, &hn, v);.
2f80: 69 66 20 28 72 20 3d 3d 20 5a 5f 44 41 54 41 5f if (r == Z_DATA_
2f90: 45 52 52 4f 52 29 0a 20 20 20 20 7a 2d 3e 6d 73 ERROR). z->ms
2fa0: 67 20 3d 20 28 63 68 61 72 2a 29 22 6f 76 65 72 g = (char*)"over
2fb0: 73 75 62 73 63 72 69 62 65 64 20 64 79 6e 61 6d subscribed dynam
2fc0: 69 63 20 62 69 74 20 6c 65 6e 67 74 68 73 20 74 ic bit lengths t
2fd0: 72 65 65 22 3b 0a 20 20 65 6c 73 65 20 69 66 20 ree";. else if
2fe0: 28 72 20 3d 3d 20 5a 5f 42 55 46 5f 45 52 52 4f (r == Z_BUF_ERRO
2ff0: 52 20 7c 7c 20 2a 62 62 20 3d 3d 20 30 29 0a 20 R || *bb == 0).
3000: 20 7b 0a 20 20 20 20 7a 2d 3e 6d 73 67 20 3d 20 {. z->msg =
3010: 28 63 68 61 72 2a 29 22 69 6e 63 6f 6d 70 6c 65 (char*)"incomple
3020: 74 65 20 64 79 6e 61 6d 69 63 20 62 69 74 20 6c te dynamic bit l
3030: 65 6e 67 74 68 73 20 74 72 65 65 22 3b 0a 20 20 engths tree";.
3040: 20 20 72 20 3d 20 5a 5f 44 41 54 41 5f 45 52 52 r = Z_DATA_ERR
3050: 4f 52 3b 0a 20 20 7d 0a 20 20 5a 46 52 45 45 28 OR;. }. ZFREE(
3060: 7a 2c 20 76 29 3b 0a 20 20 72 65 74 75 72 6e 20 z, v);. return
3070: 72 3b 0a 7d 0a 0a 0a 69 6e 74 20 69 6e 66 6c 61 r;.}...int infla
3080: 74 65 5f 74 72 65 65 73 5f 64 79 6e 61 6d 69 63 te_trees_dynamic
3090: 28 6e 6c 2c 20 6e 64 2c 20 63 2c 20 62 6c 2c 20 (nl, nd, c, bl,
30a0: 62 64 2c 20 74 6c 2c 20 74 64 2c 20 68 70 2c 20 bd, tl, td, hp,
30b0: 7a 29 0a 75 49 6e 74 20 6e 6c 3b 20 20 20 20 20 z).uInt nl;
30c0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6e 75 /* nu
30d0: 6d 62 65 72 20 6f 66 20 6c 69 74 65 72 61 6c 2f mber of literal/
30e0: 6c 65 6e 67 74 68 20 63 6f 64 65 73 20 2a 2f 0a length codes */.
30f0: 75 49 6e 74 20 6e 64 3b 20 20 20 20 20 20 20 20 uInt nd;
3100: 20 20 20 20 20 20 20 20 2f 2a 20 6e 75 6d 62 65 /* numbe
3110: 72 20 6f 66 20 64 69 73 74 61 6e 63 65 20 63 6f r of distance co
3120: 64 65 73 20 2a 2f 0a 75 49 6e 74 66 20 2a 63 3b des */.uIntf *c;
3130: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
3140: 2a 20 74 68 61 74 20 6d 61 6e 79 20 28 74 6f 74 * that many (tot
3150: 61 6c 29 20 63 6f 64 65 20 6c 65 6e 67 74 68 73 al) code lengths
3160: 20 2a 2f 0a 75 49 6e 74 66 20 2a 62 6c 3b 20 20 */.uIntf *bl;
3170: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6c /* l
3180: 69 74 65 72 61 6c 20 64 65 73 69 72 65 64 2f 61 iteral desired/a
3190: 63 74 75 61 6c 20 62 69 74 20 64 65 70 74 68 20 ctual bit depth
31a0: 2a 2f 0a 75 49 6e 74 66 20 2a 62 64 3b 20 20 20 */.uIntf *bd;
31b0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 64 69 /* di
31c0: 73 74 61 6e 63 65 20 64 65 73 69 72 65 64 2f 61 stance desired/a
31d0: 63 74 75 61 6c 20 62 69 74 20 64 65 70 74 68 20 ctual bit depth
31e0: 2a 2f 0a 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 */.inflate_huft
31f0: 2a 20 46 41 52 20 2a 74 6c 3b 20 2f 2a 20 6c 69 * FAR *tl; /* li
3200: 74 65 72 61 6c 2f 6c 65 6e 67 74 68 20 74 72 65 teral/length tre
3210: 65 20 72 65 73 75 6c 74 20 2a 2f 0a 69 6e 66 6c e result */.infl
3220: 61 74 65 5f 68 75 66 74 20 2a 20 46 41 52 20 2a ate_huft * FAR *
3230: 74 64 3b 20 2f 2a 20 64 69 73 74 61 6e 63 65 20 td; /* distance
3240: 74 72 65 65 20 72 65 73 75 6c 74 20 2a 2f 0a 69 tree result */.i
3250: 6e 66 6c 61 74 65 5f 68 75 66 74 20 2a 68 70 3b nflate_huft *hp;
3260: 20 20 20 20 20 20 20 2f 2a 20 73 70 61 63 65 20 /* space
3270: 66 6f 72 20 74 72 65 65 73 20 2a 2f 0a 7a 5f 73 for trees */.z_s
3280: 74 72 65 61 6d 70 20 7a 3b 20 20 20 20 20 20 20 treamp z;
3290: 20 20 20 20 20 2f 2a 20 66 6f 72 20 6d 65 73 73 /* for mess
32a0: 61 67 65 73 20 2a 2f 0a 7b 0a 20 20 69 6e 74 20 ages */.{. int
32b0: 72 3b 0a 20 20 75 49 6e 74 20 68 6e 20 3d 20 30 r;. uInt hn = 0
32c0: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 68 75 ; /* hu
32d0: 66 74 73 20 75 73 65 64 20 69 6e 20 73 70 61 63 fts used in spac
32e0: 65 20 2a 2f 0a 20 20 75 49 6e 74 66 20 2a 76 3b e */. uIntf *v;
32f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
3300: 77 6f 72 6b 20 61 72 65 61 20 66 6f 72 20 68 75 work area for hu
3310: 66 74 5f 62 75 69 6c 64 20 2a 2f 0a 0a 20 20 2f ft_build */.. /
3320: 2a 20 61 6c 6c 6f 63 61 74 65 20 77 6f 72 6b 20 * allocate work
3330: 61 72 65 61 20 2a 2f 0a 20 20 69 66 20 28 28 76 area */. if ((v
3340: 20 3d 20 28 75 49 6e 74 66 2a 29 5a 41 4c 4c 4f = (uIntf*)ZALLO
3350: 43 28 7a 2c 20 32 38 38 2c 20 73 69 7a 65 6f 66 C(z, 288, sizeof
3360: 28 75 49 6e 74 29 29 29 20 3d 3d 20 5a 5f 4e 55 (uInt))) == Z_NU
3370: 4c 4c 29 0a 20 20 20 20 72 65 74 75 72 6e 20 5a LL). return Z
3380: 5f 4d 45 4d 5f 45 52 52 4f 52 3b 0a 0a 20 20 2f _MEM_ERROR;.. /
3390: 2a 20 62 75 69 6c 64 20 6c 69 74 65 72 61 6c 2f * build literal/
33a0: 6c 65 6e 67 74 68 20 74 72 65 65 20 2a 2f 0a 20 length tree */.
33b0: 20 72 20 3d 20 68 75 66 74 5f 62 75 69 6c 64 28 r = huft_build(
33c0: 63 2c 20 6e 6c 2c 20 32 35 37 2c 20 63 70 6c 65 c, nl, 257, cple
33d0: 6e 73 2c 20 63 70 6c 65 78 74 2c 20 74 6c 2c 20 ns, cplext, tl,
33e0: 62 6c 2c 20 68 70 2c 20 26 68 6e 2c 20 76 29 3b bl, hp, &hn, v);
33f0: 0a 20 20 69 66 20 28 72 20 21 3d 20 5a 5f 4f 4b . if (r != Z_OK
3400: 20 7c 7c 20 2a 62 6c 20 3d 3d 20 30 29 0a 20 20 || *bl == 0).
3410: 7b 0a 20 20 20 20 69 66 20 28 72 20 3d 3d 20 5a {. if (r == Z
3420: 5f 44 41 54 41 5f 45 52 52 4f 52 29 0a 20 20 20 _DATA_ERROR).
3430: 20 20 20 7a 2d 3e 6d 73 67 20 3d 20 28 63 68 61 z->msg = (cha
3440: 72 2a 29 22 6f 76 65 72 73 75 62 73 63 72 69 62 r*)"oversubscrib
3450: 65 64 20 6c 69 74 65 72 61 6c 2f 6c 65 6e 67 74 ed literal/lengt
3460: 68 20 74 72 65 65 22 3b 0a 20 20 20 20 65 6c 73 h tree";. els
3470: 65 20 69 66 20 28 72 20 21 3d 20 5a 5f 4d 45 4d e if (r != Z_MEM
3480: 5f 45 52 52 4f 52 29 0a 20 20 20 20 7b 0a 20 20 _ERROR). {.
3490: 20 20 20 20 7a 2d 3e 6d 73 67 20 3d 20 28 63 68 z->msg = (ch
34a0: 61 72 2a 29 22 69 6e 63 6f 6d 70 6c 65 74 65 20 ar*)"incomplete
34b0: 6c 69 74 65 72 61 6c 2f 6c 65 6e 67 74 68 20 74 literal/length t
34c0: 72 65 65 22 3b 0a 20 20 20 20 20 20 72 20 3d 20 ree";. r =
34d0: 5a 5f 44 41 54 41 5f 45 52 52 4f 52 3b 0a 20 20 Z_DATA_ERROR;.
34e0: 20 20 7d 0a 20 20 20 20 5a 46 52 45 45 28 7a 2c }. ZFREE(z,
34f0: 20 76 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 v);. return
3500: 72 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 62 75 69 r;. }.. /* bui
3510: 6c 64 20 64 69 73 74 61 6e 63 65 20 74 72 65 65 ld distance tree
3520: 20 2a 2f 0a 20 20 72 20 3d 20 68 75 66 74 5f 62 */. r = huft_b
3530: 75 69 6c 64 28 63 20 2b 20 6e 6c 2c 20 6e 64 2c uild(c + nl, nd,
3540: 20 30 2c 20 63 70 64 69 73 74 2c 20 63 70 64 65 0, cpdist, cpde
3550: 78 74 2c 20 74 64 2c 20 62 64 2c 20 68 70 2c 20 xt, td, bd, hp,
3560: 26 68 6e 2c 20 76 29 3b 0a 20 20 69 66 20 28 72 &hn, v);. if (r
3570: 20 21 3d 20 5a 5f 4f 4b 20 7c 7c 20 28 2a 62 64 != Z_OK || (*bd
3580: 20 3d 3d 20 30 20 26 26 20 6e 6c 20 3e 20 32 35 == 0 && nl > 25
3590: 37 29 29 0a 20 20 7b 0a 20 20 20 20 69 66 20 28 7)). {. if (
35a0: 72 20 3d 3d 20 5a 5f 44 41 54 41 5f 45 52 52 4f r == Z_DATA_ERRO
35b0: 52 29 0a 20 20 20 20 20 20 7a 2d 3e 6d 73 67 20 R). z->msg
35c0: 3d 20 28 63 68 61 72 2a 29 22 6f 76 65 72 73 75 = (char*)"oversu
35d0: 62 73 63 72 69 62 65 64 20 64 69 73 74 61 6e 63 bscribed distanc
35e0: 65 20 74 72 65 65 22 3b 0a 20 20 20 20 65 6c 73 e tree";. els
35f0: 65 20 69 66 20 28 72 20 3d 3d 20 5a 5f 42 55 46 e if (r == Z_BUF
3600: 5f 45 52 52 4f 52 29 20 7b 0a 23 69 66 64 65 66 _ERROR) {.#ifdef
3610: 20 50 4b 5a 49 50 5f 42 55 47 5f 57 4f 52 4b 41 PKZIP_BUG_WORKA
3620: 52 4f 55 4e 44 0a 20 20 20 20 20 20 72 20 3d 20 ROUND. r =
3630: 5a 5f 4f 4b 3b 0a 20 20 20 20 7d 0a 23 65 6c 73 Z_OK;. }.#els
3640: 65 0a 20 20 20 20 20 20 7a 2d 3e 6d 73 67 20 3d e. z->msg =
3650: 20 28 63 68 61 72 2a 29 22 69 6e 63 6f 6d 70 6c (char*)"incompl
3660: 65 74 65 20 64 69 73 74 61 6e 63 65 20 74 72 65 ete distance tre
3670: 65 22 3b 0a 20 20 20 20 20 20 72 20 3d 20 5a 5f e";. r = Z_
3680: 44 41 54 41 5f 45 52 52 4f 52 3b 0a 20 20 20 20 DATA_ERROR;.
3690: 7d 0a 20 20 20 20 65 6c 73 65 20 69 66 20 28 72 }. else if (r
36a0: 20 21 3d 20 5a 5f 4d 45 4d 5f 45 52 52 4f 52 29 != Z_MEM_ERROR)
36b0: 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 7a 2d 3e . {. z->
36c0: 6d 73 67 20 3d 20 28 63 68 61 72 2a 29 22 65 6d msg = (char*)"em
36d0: 70 74 79 20 64 69 73 74 61 6e 63 65 20 74 72 65 pty distance tre
36e0: 65 20 77 69 74 68 20 6c 65 6e 67 74 68 73 22 3b e with lengths";
36f0: 0a 20 20 20 20 20 20 72 20 3d 20 5a 5f 44 41 54 . r = Z_DAT
3700: 41 5f 45 52 52 4f 52 3b 0a 20 20 20 20 7d 0a 20 A_ERROR;. }.
3710: 20 20 20 5a 46 52 45 45 28 7a 2c 20 76 29 3b 0a ZFREE(z, v);.
3720: 20 20 20 20 72 65 74 75 72 6e 20 72 3b 0a 23 65 return r;.#e
3730: 6e 64 69 66 0a 20 20 7d 0a 0a 20 20 2f 2a 20 64 ndif. }.. /* d
3740: 6f 6e 65 20 2a 2f 0a 20 20 5a 46 52 45 45 28 7a one */. ZFREE(z
3750: 2c 20 76 29 3b 0a 20 20 72 65 74 75 72 6e 20 5a , v);. return Z
3760: 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a 20 62 75 69 6c _OK;.}.../* buil
3770: 64 20 66 69 78 65 64 20 74 61 62 6c 65 73 20 6f d fixed tables o
3780: 6e 6c 79 20 6f 6e 63 65 2d 2d 6b 65 65 70 20 74 nly once--keep t
3790: 68 65 6d 20 68 65 72 65 20 2a 2f 0a 23 69 66 64 hem here */.#ifd
37a0: 65 66 20 42 55 49 4c 44 46 49 58 45 44 0a 6c 6f ef BUILDFIXED.lo
37b0: 63 61 6c 20 69 6e 74 20 66 69 78 65 64 5f 62 75 cal int fixed_bu
37c0: 69 6c 74 20 3d 20 30 3b 0a 23 64 65 66 69 6e 65 ilt = 0;.#define
37d0: 20 46 49 58 45 44 48 20 35 34 34 20 20 20 20 20 FIXEDH 544
37e0: 20 2f 2a 20 6e 75 6d 62 65 72 20 6f 66 20 68 75 /* number of hu
37f0: 66 74 73 20 75 73 65 64 20 62 79 20 66 69 78 65 fts used by fixe
3800: 64 20 74 61 62 6c 65 73 20 2a 2f 0a 6c 6f 63 61 d tables */.loca
3810: 6c 20 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 66 l inflate_huft f
3820: 69 78 65 64 5f 6d 65 6d 5b 46 49 58 45 44 48 5d ixed_mem[FIXEDH]
3830: 3b 0a 6c 6f 63 61 6c 20 75 49 6e 74 20 66 69 78 ;.local uInt fix
3840: 65 64 5f 62 6c 3b 0a 6c 6f 63 61 6c 20 75 49 6e ed_bl;.local uIn
3850: 74 20 66 69 78 65 64 5f 62 64 3b 0a 6c 6f 63 61 t fixed_bd;.loca
3860: 6c 20 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 2a l inflate_huft *
3870: 66 69 78 65 64 5f 74 6c 3b 0a 6c 6f 63 61 6c 20 fixed_tl;.local
3880: 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 2a 66 69 inflate_huft *fi
3890: 78 65 64 5f 74 64 3b 0a 23 65 6c 73 65 0a 23 69 xed_td;.#else.#i
38a0: 6e 63 6c 75 64 65 20 22 69 6e 66 66 69 78 65 64 nclude "inffixed
38b0: 2e 68 22 0a 23 65 6e 64 69 66 0a 0a 0a 69 6e 74 .h".#endif...int
38c0: 20 69 6e 66 6c 61 74 65 5f 74 72 65 65 73 5f 66 inflate_trees_f
38d0: 69 78 65 64 28 62 6c 2c 20 62 64 2c 20 74 6c 2c ixed(bl, bd, tl,
38e0: 20 74 64 2c 20 7a 29 0a 75 49 6e 74 66 20 2a 62 td, z).uIntf *b
38f0: 6c 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 l;
3900: 20 2f 2a 20 6c 69 74 65 72 61 6c 20 64 65 73 69 /* literal desi
3910: 72 65 64 2f 61 63 74 75 61 6c 20 62 69 74 20 64 red/actual bit d
3920: 65 70 74 68 20 2a 2f 0a 75 49 6e 74 66 20 2a 62 epth */.uIntf *b
3930: 64 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 d;
3940: 20 2f 2a 20 64 69 73 74 61 6e 63 65 20 64 65 73 /* distance des
3950: 69 72 65 64 2f 61 63 74 75 61 6c 20 62 69 74 20 ired/actual bit
3960: 64 65 70 74 68 20 2a 2f 0a 69 6e 66 6c 61 74 65 depth */.inflate
3970: 5f 68 75 66 74 20 2a 20 46 41 52 20 2a 74 6c 3b _huft * FAR *tl;
3980: 20 20 2f 2a 20 6c 69 74 65 72 61 6c 2f 6c 65 6e /* literal/len
3990: 67 74 68 20 74 72 65 65 20 72 65 73 75 6c 74 20 gth tree result
39a0: 2a 2f 0a 69 6e 66 6c 61 74 65 5f 68 75 66 74 20 */.inflate_huft
39b0: 2a 20 46 41 52 20 2a 74 64 3b 20 20 2f 2a 20 64 * FAR *td; /* d
39c0: 69 73 74 61 6e 63 65 20 74 72 65 65 20 72 65 73 istance tree res
39d0: 75 6c 74 20 2a 2f 0a 7a 5f 73 74 72 65 61 6d 70 ult */.z_streamp
39e0: 20 7a 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 z;
39f0: 2f 2a 20 66 6f 72 20 6d 65 6d 6f 72 79 20 61 6c /* for memory al
3a00: 6c 6f 63 61 74 69 6f 6e 20 2a 2f 0a 7b 0a 23 69 location */.{.#i
3a10: 66 64 65 66 20 42 55 49 4c 44 46 49 58 45 44 0a fdef BUILDFIXED.
3a20: 20 20 2f 2a 20 62 75 69 6c 64 20 66 69 78 65 64 /* build fixed
3a30: 20 74 61 62 6c 65 73 20 69 66 20 6e 6f 74 20 61 tables if not a
3a40: 6c 72 65 61 64 79 20 2a 2f 0a 20 20 69 66 20 28 lready */. if (
3a50: 21 66 69 78 65 64 5f 62 75 69 6c 74 29 0a 20 20 !fixed_built).
3a60: 7b 0a 20 20 20 20 69 6e 74 20 6b 3b 20 20 20 20 {. int k;
3a70: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 74 65 6d /* tem
3a80: 70 6f 72 61 72 79 20 76 61 72 69 61 62 6c 65 20 porary variable
3a90: 2a 2f 0a 20 20 20 20 75 49 6e 74 20 66 20 3d 20 */. uInt f =
3aa0: 30 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 6e 75 0; /* nu
3ab0: 6d 62 65 72 20 6f 66 20 68 75 66 74 73 20 75 73 mber of hufts us
3ac0: 65 64 20 69 6e 20 66 69 78 65 64 5f 6d 65 6d 20 ed in fixed_mem
3ad0: 2a 2f 0a 20 20 20 20 75 49 6e 74 66 20 2a 63 3b */. uIntf *c;
3ae0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6c 65 /* le
3af0: 6e 67 74 68 20 6c 69 73 74 20 66 6f 72 20 68 75 ngth list for hu
3b00: 66 74 5f 62 75 69 6c 64 20 2a 2f 0a 20 20 20 20 ft_build */.
3b10: 75 49 6e 74 66 20 2a 76 3b 20 20 20 20 20 20 20 uIntf *v;
3b20: 20 20 20 20 2f 2a 20 77 6f 72 6b 20 61 72 65 61 /* work area
3b30: 20 66 6f 72 20 68 75 66 74 5f 62 75 69 6c 64 20 for huft_build
3b40: 2a 2f 0a 0a 20 20 20 20 2f 2a 20 61 6c 6c 6f 63 */.. /* alloc
3b50: 61 74 65 20 6d 65 6d 6f 72 79 20 2a 2f 0a 20 20 ate memory */.
3b60: 20 20 69 66 20 28 28 63 20 3d 20 28 75 49 6e 74 if ((c = (uInt
3b70: 66 2a 29 5a 41 4c 4c 4f 43 28 7a 2c 20 32 38 38 f*)ZALLOC(z, 288
3b80: 2c 20 73 69 7a 65 6f 66 28 75 49 6e 74 29 29 29 , sizeof(uInt)))
3b90: 20 3d 3d 20 5a 5f 4e 55 4c 4c 29 0a 20 20 20 20 == Z_NULL).
3ba0: 20 20 72 65 74 75 72 6e 20 5a 5f 4d 45 4d 5f 45 return Z_MEM_E
3bb0: 52 52 4f 52 3b 0a 20 20 20 20 69 66 20 28 28 76 RROR;. if ((v
3bc0: 20 3d 20 28 75 49 6e 74 66 2a 29 5a 41 4c 4c 4f = (uIntf*)ZALLO
3bd0: 43 28 7a 2c 20 32 38 38 2c 20 73 69 7a 65 6f 66 C(z, 288, sizeof
3be0: 28 75 49 6e 74 29 29 29 20 3d 3d 20 5a 5f 4e 55 (uInt))) == Z_NU
3bf0: 4c 4c 29 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 LL). {.
3c00: 5a 46 52 45 45 28 7a 2c 20 63 29 3b 0a 20 20 20 ZFREE(z, c);.
3c10: 20 20 20 72 65 74 75 72 6e 20 5a 5f 4d 45 4d 5f return Z_MEM_
3c20: 45 52 52 4f 52 3b 0a 20 20 20 20 7d 0a 0a 20 20 ERROR;. }..
3c30: 20 20 2f 2a 20 6c 69 74 65 72 61 6c 20 74 61 62 /* literal tab
3c40: 6c 65 20 2a 2f 0a 20 20 20 20 66 6f 72 20 28 6b le */. for (k
3c50: 20 3d 20 30 3b 20 6b 20 3c 20 31 34 34 3b 20 6b = 0; k < 144; k
3c60: 2b 2b 29 0a 20 20 20 20 20 20 63 5b 6b 5d 20 3d ++). c[k] =
3c70: 20 38 3b 0a 20 20 20 20 66 6f 72 20 28 3b 20 6b 8;. for (; k
3c80: 20 3c 20 32 35 36 3b 20 6b 2b 2b 29 0a 20 20 20 < 256; k++).
3c90: 20 20 20 63 5b 6b 5d 20 3d 20 39 3b 0a 20 20 20 c[k] = 9;.
3ca0: 20 66 6f 72 20 28 3b 20 6b 20 3c 20 32 38 30 3b for (; k < 280;
3cb0: 20 6b 2b 2b 29 0a 20 20 20 20 20 20 63 5b 6b 5d k++). c[k]
3cc0: 20 3d 20 37 3b 0a 20 20 20 20 66 6f 72 20 28 3b = 7;. for (;
3cd0: 20 6b 20 3c 20 32 38 38 3b 20 6b 2b 2b 29 0a 20 k < 288; k++).
3ce0: 20 20 20 20 20 63 5b 6b 5d 20 3d 20 38 3b 0a 20 c[k] = 8;.
3cf0: 20 20 20 66 69 78 65 64 5f 62 6c 20 3d 20 39 3b fixed_bl = 9;
3d00: 0a 20 20 20 20 68 75 66 74 5f 62 75 69 6c 64 28 . huft_build(
3d10: 63 2c 20 32 38 38 2c 20 32 35 37 2c 20 63 70 6c c, 288, 257, cpl
3d20: 65 6e 73 2c 20 63 70 6c 65 78 74 2c 20 26 66 69 ens, cplext, &fi
3d30: 78 65 64 5f 74 6c 2c 20 26 66 69 78 65 64 5f 62 xed_tl, &fixed_b
3d40: 6c 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 l,.
3d50: 20 20 66 69 78 65 64 5f 6d 65 6d 2c 20 26 66 2c fixed_mem, &f,
3d60: 20 76 29 3b 0a 0a 20 20 20 20 2f 2a 20 64 69 73 v);.. /* dis
3d70: 74 61 6e 63 65 20 74 61 62 6c 65 20 2a 2f 0a 20 tance table */.
3d80: 20 20 20 66 6f 72 20 28 6b 20 3d 20 30 3b 20 6b for (k = 0; k
3d90: 20 3c 20 33 30 3b 20 6b 2b 2b 29 0a 20 20 20 20 < 30; k++).
3da0: 20 20 63 5b 6b 5d 20 3d 20 35 3b 0a 20 20 20 20 c[k] = 5;.
3db0: 66 69 78 65 64 5f 62 64 20 3d 20 35 3b 0a 20 20 fixed_bd = 5;.
3dc0: 20 20 68 75 66 74 5f 62 75 69 6c 64 28 63 2c 20 huft_build(c,
3dd0: 33 30 2c 20 30 2c 20 63 70 64 69 73 74 2c 20 63 30, 0, cpdist, c
3de0: 70 64 65 78 74 2c 20 26 66 69 78 65 64 5f 74 64 pdext, &fixed_td
3df0: 2c 20 26 66 69 78 65 64 5f 62 64 2c 0a 20 20 20 , &fixed_bd,.
3e00: 20 20 20 20 20 20 20 20 20 20 20 20 66 69 78 65 fixe
3e10: 64 5f 6d 65 6d 2c 20 26 66 2c 20 76 29 3b 0a 0a d_mem, &f, v);..
3e20: 20 20 20 20 2f 2a 20 64 6f 6e 65 20 2a 2f 0a 20 /* done */.
3e30: 20 20 20 5a 46 52 45 45 28 7a 2c 20 76 29 3b 0a ZFREE(z, v);.
3e40: 20 20 20 20 5a 46 52 45 45 28 7a 2c 20 63 29 3b ZFREE(z, c);
3e50: 0a 20 20 20 20 66 69 78 65 64 5f 62 75 69 6c 74 . fixed_built
3e60: 20 3d 20 31 3b 0a 20 20 7d 0a 23 65 6e 64 69 66 = 1;. }.#endif
3e70: 0a 20 20 2a 62 6c 20 3d 20 66 69 78 65 64 5f 62 . *bl = fixed_b
3e80: 6c 3b 0a 20 20 2a 62 64 20 3d 20 66 69 78 65 64 l;. *bd = fixed
3e90: 5f 62 64 3b 0a 20 20 2a 74 6c 20 3d 20 66 69 78 _bd;. *tl = fix
3ea0: 65 64 5f 74 6c 3b 0a 20 20 2a 74 64 20 3d 20 66 ed_tl;. *td = f
3eb0: 69 78 65 64 5f 74 64 3b 0a 20 20 72 65 74 75 72 ixed_td;. retur
3ec0: 6e 20 5a 5f 4f 4b 3b 0a 7d 0a n Z_OK;.}.