1 /* 2 * Copyright 2003 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 #pragma ident "%Z%%M% %I% %E% SMI" 7 8 /* 9 * inftrees.c -- generate Huffman trees for efficient decoding 10 * Copyright (C) 1995-1998 Mark Adler 11 * For conditions of distribution and use, see copyright notice in zlib.h 12 */ 13 14 #include "zutil.h" 15 #include "inftrees.h" 16 17 local const uInt fixed_bl = 9; 18 local const uInt fixed_bd = 5; 19 local const inflate_huft fixed_tl[] = { 20 {{{96,7}},256}, {{{0,8}},80}, {{{0,8}},16}, {{{84,8}},115}, 21 {{{82,7}},31}, {{{0,8}},112}, {{{0,8}},48}, {{{0,9}},192}, 22 {{{80,7}},10}, {{{0,8}},96}, {{{0,8}},32}, {{{0,9}},160}, 23 {{{0,8}},0}, {{{0,8}},128}, {{{0,8}},64}, {{{0,9}},224}, 24 {{{80,7}},6}, {{{0,8}},88}, {{{0,8}},24}, {{{0,9}},144}, 25 {{{83,7}},59}, {{{0,8}},120}, {{{0,8}},56}, {{{0,9}},208}, 26 {{{81,7}},17}, {{{0,8}},104}, {{{0,8}},40}, {{{0,9}},176}, 27 {{{0,8}},8}, {{{0,8}},136}, {{{0,8}},72}, {{{0,9}},240}, 28 {{{80,7}},4}, {{{0,8}},84}, {{{0,8}},20}, {{{85,8}},227}, 29 {{{83,7}},43}, {{{0,8}},116}, {{{0,8}},52}, {{{0,9}},200}, 30 {{{81,7}},13}, {{{0,8}},100}, {{{0,8}},36}, {{{0,9}},168}, 31 {{{0,8}},4}, {{{0,8}},132}, {{{0,8}},68}, {{{0,9}},232}, 32 {{{80,7}},8}, {{{0,8}},92}, {{{0,8}},28}, {{{0,9}},152}, 33 {{{84,7}},83}, {{{0,8}},124}, {{{0,8}},60}, {{{0,9}},216}, 34 {{{82,7}},23}, {{{0,8}},108}, {{{0,8}},44}, {{{0,9}},184}, 35 {{{0,8}},12}, {{{0,8}},140}, {{{0,8}},76}, {{{0,9}},248}, 36 {{{80,7}},3}, {{{0,8}},82}, {{{0,8}},18}, {{{85,8}},163}, 37 {{{83,7}},35}, {{{0,8}},114}, {{{0,8}},50}, {{{0,9}},196}, 38 {{{81,7}},11}, {{{0,8}},98}, {{{0,8}},34}, {{{0,9}},164}, 39 {{{0,8}},2}, {{{0,8}},130}, {{{0,8}},66}, {{{0,9}},228}, 40 {{{80,7}},7}, {{{0,8}},90}, {{{0,8}},26}, {{{0,9}},148}, 41 {{{84,7}},67}, {{{0,8}},122}, {{{0,8}},58}, {{{0,9}},212}, 42 {{{82,7}},19}, {{{0,8}},106}, {{{0,8}},42}, {{{0,9}},180}, 43 {{{0,8}},10}, {{{0,8}},138}, {{{0,8}},74}, {{{0,9}},244}, 44 {{{80,7}},5}, {{{0,8}},86}, {{{0,8}},22}, {{{192,8}},0}, 45 {{{83,7}},51}, {{{0,8}},118}, {{{0,8}},54}, {{{0,9}},204}, 46 {{{81,7}},15}, {{{0,8}},102}, {{{0,8}},38}, {{{0,9}},172}, 47 {{{0,8}},6}, {{{0,8}},134}, {{{0,8}},70}, {{{0,9}},236}, 48 {{{80,7}},9}, {{{0,8}},94}, {{{0,8}},30}, {{{0,9}},156}, 49 {{{84,7}},99}, {{{0,8}},126}, {{{0,8}},62}, {{{0,9}},220}, 50 {{{82,7}},27}, {{{0,8}},110}, {{{0,8}},46}, {{{0,9}},188}, 51 {{{0,8}},14}, {{{0,8}},142}, {{{0,8}},78}, {{{0,9}},252}, 52 {{{96,7}},256}, {{{0,8}},81}, {{{0,8}},17}, {{{85,8}},131}, 53 {{{82,7}},31}, {{{0,8}},113}, {{{0,8}},49}, {{{0,9}},194}, 54 {{{80,7}},10}, {{{0,8}},97}, {{{0,8}},33}, {{{0,9}},162}, 55 {{{0,8}},1}, {{{0,8}},129}, {{{0,8}},65}, {{{0,9}},226}, 56 {{{80,7}},6}, {{{0,8}},89}, {{{0,8}},25}, {{{0,9}},146}, 57 {{{83,7}},59}, {{{0,8}},121}, {{{0,8}},57}, {{{0,9}},210}, 58 {{{81,7}},17}, {{{0,8}},105}, {{{0,8}},41}, {{{0,9}},178}, 59 {{{0,8}},9}, {{{0,8}},137}, {{{0,8}},73}, {{{0,9}},242}, 60 {{{80,7}},4}, {{{0,8}},85}, {{{0,8}},21}, {{{80,8}},258}, 61 {{{83,7}},43}, {{{0,8}},117}, {{{0,8}},53}, {{{0,9}},202}, 62 {{{81,7}},13}, {{{0,8}},101}, {{{0,8}},37}, {{{0,9}},170}, 63 {{{0,8}},5}, {{{0,8}},133}, {{{0,8}},69}, {{{0,9}},234}, 64 {{{80,7}},8}, {{{0,8}},93}, {{{0,8}},29}, {{{0,9}},154}, 65 {{{84,7}},83}, {{{0,8}},125}, {{{0,8}},61}, {{{0,9}},218}, 66 {{{82,7}},23}, {{{0,8}},109}, {{{0,8}},45}, {{{0,9}},186}, 67 {{{0,8}},13}, {{{0,8}},141}, {{{0,8}},77}, {{{0,9}},250}, 68 {{{80,7}},3}, {{{0,8}},83}, {{{0,8}},19}, {{{85,8}},195}, 69 {{{83,7}},35}, {{{0,8}},115}, {{{0,8}},51}, {{{0,9}},198}, 70 {{{81,7}},11}, {{{0,8}},99}, {{{0,8}},35}, {{{0,9}},166}, 71 {{{0,8}},3}, {{{0,8}},131}, {{{0,8}},67}, {{{0,9}},230}, 72 {{{80,7}},7}, {{{0,8}},91}, {{{0,8}},27}, {{{0,9}},150}, 73 {{{84,7}},67}, {{{0,8}},123}, {{{0,8}},59}, {{{0,9}},214}, 74 {{{82,7}},19}, {{{0,8}},107}, {{{0,8}},43}, {{{0,9}},182}, 75 {{{0,8}},11}, {{{0,8}},139}, {{{0,8}},75}, {{{0,9}},246}, 76 {{{80,7}},5}, {{{0,8}},87}, {{{0,8}},23}, {{{192,8}},0}, 77 {{{83,7}},51}, {{{0,8}},119}, {{{0,8}},55}, {{{0,9}},206}, 78 {{{81,7}},15}, {{{0,8}},103}, {{{0,8}},39}, {{{0,9}},174}, 79 {{{0,8}},7}, {{{0,8}},135}, {{{0,8}},71}, {{{0,9}},238}, 80 {{{80,7}},9}, {{{0,8}},95}, {{{0,8}},31}, {{{0,9}},158}, 81 {{{84,7}},99}, {{{0,8}},127}, {{{0,8}},63}, {{{0,9}},222}, 82 {{{82,7}},27}, {{{0,8}},111}, {{{0,8}},47}, {{{0,9}},190}, 83 {{{0,8}},15}, {{{0,8}},143}, {{{0,8}},79}, {{{0,9}},254}, 84 {{{96,7}},256}, {{{0,8}},80}, {{{0,8}},16}, {{{84,8}},115}, 85 {{{82,7}},31}, {{{0,8}},112}, {{{0,8}},48}, {{{0,9}},193}, 86 {{{80,7}},10}, {{{0,8}},96}, {{{0,8}},32}, {{{0,9}},161}, 87 {{{0,8}},0}, {{{0,8}},128}, {{{0,8}},64}, {{{0,9}},225}, 88 {{{80,7}},6}, {{{0,8}},88}, {{{0,8}},24}, {{{0,9}},145}, 89 {{{83,7}},59}, {{{0,8}},120}, {{{0,8}},56}, {{{0,9}},209}, 90 {{{81,7}},17}, {{{0,8}},104}, {{{0,8}},40}, {{{0,9}},177}, 91 {{{0,8}},8}, {{{0,8}},136}, {{{0,8}},72}, {{{0,9}},241}, 92 {{{80,7}},4}, {{{0,8}},84}, {{{0,8}},20}, {{{85,8}},227}, 93 {{{83,7}},43}, {{{0,8}},116}, {{{0,8}},52}, {{{0,9}},201}, 94 {{{81,7}},13}, {{{0,8}},100}, {{{0,8}},36}, {{{0,9}},169}, 95 {{{0,8}},4}, {{{0,8}},132}, {{{0,8}},68}, {{{0,9}},233}, 96 {{{80,7}},8}, {{{0,8}},92}, {{{0,8}},28}, {{{0,9}},153}, 97 {{{84,7}},83}, {{{0,8}},124}, {{{0,8}},60}, {{{0,9}},217}, 98 {{{82,7}},23}, {{{0,8}},108}, {{{0,8}},44}, {{{0,9}},185}, 99 {{{0,8}},12}, {{{0,8}},140}, {{{0,8}},76}, {{{0,9}},249}, 100 {{{80,7}},3}, {{{0,8}},82}, {{{0,8}},18}, {{{85,8}},163}, 101 {{{83,7}},35}, {{{0,8}},114}, {{{0,8}},50}, {{{0,9}},197}, 102 {{{81,7}},11}, {{{0,8}},98}, {{{0,8}},34}, {{{0,9}},165}, 103 {{{0,8}},2}, {{{0,8}},130}, {{{0,8}},66}, {{{0,9}},229}, 104 {{{80,7}},7}, {{{0,8}},90}, {{{0,8}},26}, {{{0,9}},149}, 105 {{{84,7}},67}, {{{0,8}},122}, {{{0,8}},58}, {{{0,9}},213}, 106 {{{82,7}},19}, {{{0,8}},106}, {{{0,8}},42}, {{{0,9}},181}, 107 {{{0,8}},10}, {{{0,8}},138}, {{{0,8}},74}, {{{0,9}},245}, 108 {{{80,7}},5}, {{{0,8}},86}, {{{0,8}},22}, {{{192,8}},0}, 109 {{{83,7}},51}, {{{0,8}},118}, {{{0,8}},54}, {{{0,9}},205}, 110 {{{81,7}},15}, {{{0,8}},102}, {{{0,8}},38}, {{{0,9}},173}, 111 {{{0,8}},6}, {{{0,8}},134}, {{{0,8}},70}, {{{0,9}},237}, 112 {{{80,7}},9}, {{{0,8}},94}, {{{0,8}},30}, {{{0,9}},157}, 113 {{{84,7}},99}, {{{0,8}},126}, {{{0,8}},62}, {{{0,9}},221}, 114 {{{82,7}},27}, {{{0,8}},110}, {{{0,8}},46}, {{{0,9}},189}, 115 {{{0,8}},14}, {{{0,8}},142}, {{{0,8}},78}, {{{0,9}},253}, 116 {{{96,7}},256}, {{{0,8}},81}, {{{0,8}},17}, {{{85,8}},131}, 117 {{{82,7}},31}, {{{0,8}},113}, {{{0,8}},49}, {{{0,9}},195}, 118 {{{80,7}},10}, {{{0,8}},97}, {{{0,8}},33}, {{{0,9}},163}, 119 {{{0,8}},1}, {{{0,8}},129}, {{{0,8}},65}, {{{0,9}},227}, 120 {{{80,7}},6}, {{{0,8}},89}, {{{0,8}},25}, {{{0,9}},147}, 121 {{{83,7}},59}, {{{0,8}},121}, {{{0,8}},57}, {{{0,9}},211}, 122 {{{81,7}},17}, {{{0,8}},105}, {{{0,8}},41}, {{{0,9}},179}, 123 {{{0,8}},9}, {{{0,8}},137}, {{{0,8}},73}, {{{0,9}},243}, 124 {{{80,7}},4}, {{{0,8}},85}, {{{0,8}},21}, {{{80,8}},258}, 125 {{{83,7}},43}, {{{0,8}},117}, {{{0,8}},53}, {{{0,9}},203}, 126 {{{81,7}},13}, {{{0,8}},101}, {{{0,8}},37}, {{{0,9}},171}, 127 {{{0,8}},5}, {{{0,8}},133}, {{{0,8}},69}, {{{0,9}},235}, 128 {{{80,7}},8}, {{{0,8}},93}, {{{0,8}},29}, {{{0,9}},155}, 129 {{{84,7}},83}, {{{0,8}},125}, {{{0,8}},61}, {{{0,9}},219}, 130 {{{82,7}},23}, {{{0,8}},109}, {{{0,8}},45}, {{{0,9}},187}, 131 {{{0,8}},13}, {{{0,8}},141}, {{{0,8}},77}, {{{0,9}},251}, 132 {{{80,7}},3}, {{{0,8}},83}, {{{0,8}},19}, {{{85,8}},195}, 133 {{{83,7}},35}, {{{0,8}},115}, {{{0,8}},51}, {{{0,9}},199}, 134 {{{81,7}},11}, {{{0,8}},99}, {{{0,8}},35}, {{{0,9}},167}, 135 {{{0,8}},3}, {{{0,8}},131}, {{{0,8}},67}, {{{0,9}},231}, 136 {{{80,7}},7}, {{{0,8}},91}, {{{0,8}},27}, {{{0,9}},151}, 137 {{{84,7}},67}, {{{0,8}},123}, {{{0,8}},59}, {{{0,9}},215}, 138 {{{82,7}},19}, {{{0,8}},107}, {{{0,8}},43}, {{{0,9}},183}, 139 {{{0,8}},11}, {{{0,8}},139}, {{{0,8}},75}, {{{0,9}},247}, 140 {{{80,7}},5}, {{{0,8}},87}, {{{0,8}},23}, {{{192,8}},0}, 141 {{{83,7}},51}, {{{0,8}},119}, {{{0,8}},55}, {{{0,9}},207}, 142 {{{81,7}},15}, {{{0,8}},103}, {{{0,8}},39}, {{{0,9}},175}, 143 {{{0,8}},7}, {{{0,8}},135}, {{{0,8}},71}, {{{0,9}},239}, 144 {{{80,7}},9}, {{{0,8}},95}, {{{0,8}},31}, {{{0,9}},159}, 145 {{{84,7}},99}, {{{0,8}},127}, {{{0,8}},63}, {{{0,9}},223}, 146 {{{82,7}},27}, {{{0,8}},111}, {{{0,8}},47}, {{{0,9}},191}, 147 {{{0,8}},15}, {{{0,8}},143}, {{{0,8}},79}, {{{0,9}},255} 148 }; 149 150 local const inflate_huft fixed_td[] = { 151 {{{80,5}},1}, {{{87,5}},257}, {{{83,5}},17}, {{{91,5}},4097}, 152 {{{81,5}},5}, {{{89,5}},1025}, {{{85,5}},65}, {{{93,5}},16385}, 153 {{{80,5}},3}, {{{88,5}},513}, {{{84,5}},33}, {{{92,5}},8193}, 154 {{{82,5}},9}, {{{90,5}},2049}, {{{86,5}},129}, {{{192,5}},24577}, 155 {{{80,5}},2}, {{{87,5}},385}, {{{83,5}},25}, {{{91,5}},6145}, 156 {{{81,5}},7}, {{{89,5}},1537}, {{{85,5}},97}, {{{93,5}},24577}, 157 {{{80,5}},4}, {{{88,5}},769}, {{{84,5}},49}, {{{92,5}},12289}, 158 {{{82,5}},13}, {{{90,5}},3073}, {{{86,5}},193}, {{{192,5}},24577} 159 }; 160 161 /* simplify the use of the inflate_huft type with some defines */ 162 #define exop word.what.Exop 163 #define bits word.what.Bits 164 165 166 local int huft_build OF(( 167 uIntf *, /* code lengths in bits */ 168 uInt, /* number of codes */ 169 uInt, /* number of "simple" codes */ 170 const uIntf *, /* list of base values for non-simple codes */ 171 const uIntf *, /* list of extra bits for non-simple codes */ 172 inflate_huft * FAR*,/* result: starting table */ 173 uIntf *, /* maximum lookup bits (returns actual) */ 174 inflate_huft *, /* space for trees */ 175 uInt *, /* hufts used in space */ 176 uIntf * )); /* space for values */ 177 178 /* Tables for deflate from PKZIP's appnote.txt. */ 179 local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ 180 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 181 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 182 /* see note #13 above about 258 */ 183 local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ 184 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 185 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ 186 local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ 187 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 188 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 189 8193, 12289, 16385, 24577}; 190 local const uInt cpdext[30] = { /* Extra bits for distance codes */ 191 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 192 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 193 12, 12, 13, 13}; 194 195 /* 196 Huffman code decoding is performed using a multi-level table lookup. 197 The fastest way to decode is to simply build a lookup table whose 198 size is determined by the longest code. However, the time it takes 199 to build this table can also be a factor if the data being decoded 200 is not very long. The most common codes are necessarily the 201 shortest codes, so those codes dominate the decoding time, and hence 202 the speed. The idea is you can have a shorter table that decodes the 203 shorter, more probable codes, and then point to subsidiary tables for 204 the longer codes. The time it costs to decode the longer codes is 205 then traded against the time it takes to make longer tables. 206 207 This results of this trade are in the variables lbits and dbits 208 below. lbits is the number of bits the first level table for literal/ 209 length codes can decode in one step, and dbits is the same thing for 210 the distance codes. Subsequent tables are also less than or equal to 211 those sizes. These values may be adjusted either when all of the 212 codes are shorter than that, in which case the longest code length in 213 bits is used, or when the shortest code is *longer* than the requested 214 table size, in which case the length of the shortest code in bits is 215 used. 216 217 There are two different values for the two tables, since they code a 218 different number of possibilities each. The literal/length table 219 codes 286 possible values, or in a flat code, a little over eight 220 bits. The distance table codes 30 possible values, or a little less 221 than five bits, flat. The optimum values for speed end up being 222 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 223 The optimum values may differ though from machine to machine, and 224 possibly even between compilers. Your mileage may vary. 225 */ 226 227 228 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 229 #define BMAX 15 /* maximum bit length of any code */ 230 231 local int huft_build(b, n, s, d, e, t, m, hp, hn, v) 232 uIntf *b; /* code lengths in bits (all assumed <= BMAX) */ 233 uInt n; /* number of codes (assumed <= 288) */ 234 uInt s; /* number of simple-valued codes (0..s-1) */ 235 const uIntf *d; /* list of base values for non-simple codes */ 236 const uIntf *e; /* list of extra bits for non-simple codes */ 237 inflate_huft * FAR *t; /* result: starting table */ 238 uIntf *m; /* maximum lookup bits, returns actual */ 239 inflate_huft *hp; /* space for trees */ 240 uInt *hn; /* hufts used in space */ 241 uIntf *v; /* working area: values in order of bit length */ 242 /* Given a list of code lengths and a maximum table size, make a set of 243 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR 244 if the given code set is incomplete (the tables are still built in this 245 case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of 246 lengths), or Z_MEM_ERROR if not enough memory. */ 247 { 248 249 uInt a; /* counter for codes of length k */ 250 uInt c[BMAX+1]; /* bit length count table */ 251 uInt f; /* i repeats in table every f entries */ 252 int g; /* maximum code length */ 253 int h; /* table level */ 254 register uInt i; /* counter, current code */ 255 register uInt j; /* counter */ 256 register int k; /* number of bits in current code */ 257 int l; /* bits per table (returned in m) */ 258 uInt mask; /* (1 << w) - 1, to avoid cc -O bug on HP */ 259 register uIntf *p; /* pointer into c[], b[], or v[] */ 260 inflate_huft *q; /* points to current table */ 261 struct inflate_huft_s r; /* table entry for structure assignment */ 262 inflate_huft *u[BMAX]; /* table stack */ 263 register int w; /* bits before this table == (l * h) */ 264 uInt x[BMAX+1]; /* bit offsets, then code stack */ 265 uIntf *xp; /* pointer into x */ 266 int y; /* number of dummy codes added */ 267 uInt z; /* number of entries in current table */ 268 269 270 /* Generate counts for each bit length */ 271 p = c; 272 #define C0 *p++ = 0; 273 #define C2 C0 C0 C0 C0 274 #define C4 C2 C2 C2 C2 275 C4 /* clear c[]--assume BMAX+1 is 16 */ 276 p = b; i = n; 277 do { 278 c[*p++]++; /* assume all entries <= BMAX */ 279 } while (--i); 280 if (c[0] == n) /* null input--all zero length codes */ 281 { 282 *t = (inflate_huft *)Z_NULL; 283 *m = 0; 284 return Z_OK; 285 } 286 287 288 /* Find minimum and maximum length, bound *m by those */ 289 l = *m; 290 for (j = 1; j <= BMAX; j++) 291 if (c[j]) 292 break; 293 k = j; /* minimum code length */ 294 if ((uInt)l < j) 295 l = j; 296 for (i = BMAX; i; i--) 297 if (c[i]) 298 break; 299 g = i; /* maximum code length */ 300 if ((uInt)l > i) 301 l = i; 302 *m = l; 303 304 305 /* Adjust last length count to fill out codes, if needed */ 306 for (y = 1 << j; j < i; j++, y <<= 1) 307 if ((y -= c[j]) < 0) 308 return Z_DATA_ERROR; 309 if ((y -= c[i]) < 0) 310 return Z_DATA_ERROR; 311 c[i] += y; 312 313 314 /* Generate starting offsets into the value table for each length */ 315 x[1] = j = 0; 316 p = c + 1; xp = x + 2; 317 while (--i) { /* note that i == g from above */ 318 *xp++ = (j += *p++); 319 } 320 321 322 /* Make a table of values in order of bit lengths */ 323 p = b; i = 0; 324 do { 325 if ((j = *p++) != 0) 326 v[x[j]++] = i; 327 } while (++i < n); 328 n = x[g]; /* set n to length of v */ 329 330 331 /* Generate the Huffman codes and for each, make the table entries */ 332 x[0] = i = 0; /* first Huffman code is zero */ 333 p = v; /* grab values in bit order */ 334 h = -1; /* no tables yet--level -1 */ 335 w = -l; /* bits decoded == (l * h) */ 336 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ 337 q = (inflate_huft *)Z_NULL; /* ditto */ 338 z = 0; /* ditto */ 339 340 /* go through the bit lengths (k already is bits in shortest code) */ 341 for (; k <= g; k++) 342 { 343 a = c[k]; 344 while (a--) 345 { 346 /* here i is the Huffman code of length k bits for value *p */ 347 /* make tables up to required level */ 348 while (k > w + l) 349 { 350 h++; 351 w += l; /* previous table always l bits */ 352 353 /* compute minimum size table less than or equal to l bits */ 354 z = g - w; 355 z = z > (uInt)l ? l : z; /* table size upper limit */ 356 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 357 { /* too few codes for k-w bit table */ 358 f -= a + 1; /* deduct codes from patterns left */ 359 xp = c + k; 360 if (j < z) 361 while (++j < z) /* try smaller tables up to z bits */ 362 { 363 if ((f <<= 1) <= *++xp) 364 break; /* enough codes to use up j bits */ 365 f -= *xp; /* else deduct codes from patterns */ 366 } 367 } 368 z = 1 << j; /* table entries for j-bit table */ 369 370 /* allocate new table */ 371 if (*hn + z > MANY) /* (note: doesn't matter for fixed) */ 372 return Z_MEM_ERROR; /* not enough memory */ 373 u[h] = q = hp + *hn; 374 *hn += z; 375 376 /* connect to last table, if there is one */ 377 if (h) 378 { 379 x[h] = i; /* save pattern for backing up */ 380 r.bits = (Byte)l; /* bits to dump before this table */ 381 r.exop = (Byte)j; /* bits in this table */ 382 j = i >> (w - l); 383 r.base = (uInt)(q - u[h-1] - j); /* offset to this table */ 384 u[h-1][j] = r; /* connect to last table */ 385 } 386 else 387 *t = q; /* first table is returned result */ 388 } 389 390 /* set up table entry in r */ 391 r.bits = (Byte)(k - w); 392 if (p >= v + n) 393 r.exop = 128 + 64; /* out of values--invalid code */ 394 else if (*p < s) 395 { 396 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ 397 r.base = *p++; /* simple code is just the value */ 398 } 399 else 400 { 401 r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */ 402 r.base = d[*p++ - s]; 403 } 404 405 /* fill code-like entries with r */ 406 f = 1 << (k - w); 407 for (j = i >> w; j < z; j += f) 408 q[j] = r; 409 410 /* backwards increment the k-bit code i */ 411 for (j = 1 << (k - 1); i & j; j >>= 1) 412 i ^= j; 413 i ^= j; 414 415 /* backup over finished tables */ 416 mask = (1 << w) - 1; /* needed on HP, cc -O bug */ 417 while ((i & mask) != x[h]) 418 { 419 h--; /* don't need to update q */ 420 w -= l; 421 mask = (1 << w) - 1; 422 } 423 } 424 } 425 426 427 /* Return Z_BUF_ERROR if we were given an incomplete table */ 428 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 429 } 430 431 432 int inflate_trees_bits(c, bb, tb, hp, z) 433 uIntf *c; /* 19 code lengths */ 434 uIntf *bb; /* bits tree desired/actual depth */ 435 inflate_huft * FAR *tb; /* bits tree result */ 436 inflate_huft *hp; /* space for trees */ 437 z_streamp z; /* for messages */ 438 { 439 int r; 440 uInt hn = 0; /* hufts used in space */ 441 uIntf *v; /* work area for huft_build */ 442 443 if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL) 444 return Z_MEM_ERROR; 445 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, 446 tb, bb, hp, &hn, v); 447 if (r == Z_DATA_ERROR) 448 z->msg = (char*)"oversubscribed dynamic bit lengths tree"; 449 else if (r == Z_BUF_ERROR || *bb == 0) 450 { 451 z->msg = (char*)"incomplete dynamic bit lengths tree"; 452 r = Z_DATA_ERROR; 453 } 454 ZFREE(z, v); 455 return r; 456 } 457 458 459 int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z) 460 uInt nl; /* number of literal/length codes */ 461 uInt nd; /* number of distance codes */ 462 uIntf *c; /* that many (total) code lengths */ 463 uIntf *bl; /* literal desired/actual bit depth */ 464 uIntf *bd; /* distance desired/actual bit depth */ 465 inflate_huft * FAR *tl; /* literal/length tree result */ 466 inflate_huft * FAR *td; /* distance tree result */ 467 inflate_huft *hp; /* space for trees */ 468 z_streamp z; /* for messages */ 469 { 470 int r; 471 uInt hn = 0; /* hufts used in space */ 472 uIntf *v; /* work area for huft_build */ 473 474 /* allocate work area */ 475 if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL) 476 return Z_MEM_ERROR; 477 478 /* build literal/length tree */ 479 r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v); 480 if (r != Z_OK || *bl == 0) 481 { 482 if (r == Z_DATA_ERROR) 483 z->msg = (char*)"oversubscribed literal/length tree"; 484 else if (r != Z_MEM_ERROR) 485 { 486 z->msg = (char*)"incomplete literal/length tree"; 487 r = Z_DATA_ERROR; 488 } 489 ZFREE(z, v); 490 return r; 491 } 492 493 /* build distance tree */ 494 r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v); 495 if (r != Z_OK || (*bd == 0 && nl > 257)) 496 { 497 if (r == Z_DATA_ERROR) 498 z->msg = (char*)"oversubscribed distance tree"; 499 else if (r == Z_BUF_ERROR) { 500 z->msg = (char*)"incomplete distance tree"; 501 r = Z_DATA_ERROR; 502 } 503 else if (r != Z_MEM_ERROR) 504 { 505 z->msg = (char*)"empty distance tree with lengths"; 506 r = Z_DATA_ERROR; 507 } 508 ZFREE(z, v); 509 return r; 510 } 511 512 /* done */ 513 ZFREE(z, v); 514 return Z_OK; 515 } 516 517 /*ARGSUSED*/ 518 int inflate_trees_fixed(bl, bd, tl, td, z) 519 uIntf *bl; /* literal desired/actual bit depth */ 520 uIntf *bd; /* distance desired/actual bit depth */ 521 inflate_huft * FAR *tl; /* literal/length tree result */ 522 inflate_huft * FAR *td; /* distance tree result */ 523 z_streamp z; /* for memory allocation */ 524 { 525 *bl = fixed_bl; 526 *bd = fixed_bd; 527 *tl = (inflate_huft *)fixed_tl; 528 *td = (inflate_huft *)fixed_td; 529 return Z_OK; 530 } 531