| 1 | /* infblock.c -- interpret and process block types to last block |
| 2 | * Copyright (C) 1995-1998 Mark Adler |
| 3 | * For conditions of distribution and use, see copyright notice in zlib.h |
| 4 | */ |
| 5 | |
| 6 | #include "zutil.h" |
| 7 | #include "infblock.h" |
| 8 | #include "inftrees.h" |
| 9 | #include "infcodes.h" |
| 10 | #include "infutil.h" |
| 11 | |
| 12 | struct inflate_codes_state {int dummy;}; /* for buggy compilers */ |
| 13 | |
| 14 | /* simplify the use of the inflate_huft type with some defines */ |
| 15 | #define exop word.what.Exop |
| 16 | #define bits word.what.Bits |
| 17 | |
| 18 | /* Table for deflate from PKZIP's appnote.txt. */ |
| 19 | local const uInt border[] = { /* Order of the bit length code lengths */ |
| 20 | 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; |
| 21 | |
| 22 | /* |
| 23 | Notes beyond the 1.93a appnote.txt: |
| 24 | |
| 25 | 1. Distance pointers never point before the beginning of the output |
| 26 | stream. |
| 27 | 2. Distance pointers can point back across blocks, up to 32k away. |
| 28 | 3. There is an implied maximum of 7 bits for the bit length table and |
| 29 | 15 bits for the actual data. |
| 30 | 4. If only one code exists, then it is encoded using one bit. (Zero |
| 31 | would be more efficient, but perhaps a little confusing.) If two |
| 32 | codes exist, they are coded using one bit each (0 and 1). |
| 33 | 5. There is no way of sending zero distance codes--a dummy must be |
| 34 | sent if there are none. (History: a pre 2.0 version of PKZIP would |
| 35 | store blocks with no distance codes, but this was discovered to be |
| 36 | too harsh a criterion.) Valid only for 1.93a. 2.04c does allow |
| 37 | zero distance codes, which is sent as one code of zero bits in |
| 38 | length. |
| 39 | 6. There are up to 286 literal/length codes. Code 256 represents the |
| 40 | end-of-block. Note however that the static length tree defines |
| 41 | 288 codes just to fill out the Huffman codes. Codes 286 and 287 |
| 42 | cannot be used though, since there is no length base or extra bits |
| 43 | defined for them. Similarily, there are up to 30 distance codes. |
| 44 | However, static trees define 32 codes (all 5 bits) to fill out the |
| 45 | Huffman codes, but the last two had better not show up in the data. |
| 46 | 7. Unzip can check dynamic Huffman blocks for complete code sets. |
| 47 | The exception is that a single code would not be complete (see #4). |
| 48 | 8. The five bits following the block type is really the number of |
| 49 | literal codes sent minus 257. |
| 50 | 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits |
| 51 | (1+6+6). Therefore, to output three times the length, you output |
| 52 | three codes (1+1+1), whereas to output four times the same length, |
| 53 | you only need two codes (1+3). Hmm. |
| 54 | 10. In the tree reconstruction algorithm, Code = Code + Increment |
| 55 | only if BitLength(i) is not zero. (Pretty obvious.) |
| 56 | 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) |
| 57 | 12. Note: length code 284 can represent 227-258, but length code 285 |
| 58 | really is 258. The last length deserves its own, short code |
| 59 | since it gets used a lot in very redundant files. The length |
| 60 | 258 is special since 258 - 3 (the min match length) is 255. |
| 61 | 13. The literal/length and distance code bit lengths are read as a |
| 62 | single stream of lengths. It is possible (and advantageous) for |
| 63 | a repeat code (16, 17, or 18) to go across the boundary between |
| 64 | the two sets of lengths. |
| 65 | */ |
| 66 | |
| 67 | |
| 68 | #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */ |
| 69 | void inflate_blocks_reset(inflate_blocks_statef* s, z_streamp z, uLongf* c) |
| 70 | #else |
| 71 | void inflate_blocks_reset(s, z, c) |
| 72 | inflate_blocks_statef *s; |
| 73 | z_streamp z; |
| 74 | uLongf *c; |
| 75 | #endif |
| 76 | { |
| 77 | if (c != Z_NULL) |
| 78 | *c = s->check; |
| 79 | if (s->mode == BTREE || s->mode == DTREE) |
| 80 | ZFREE(z, s->sub.trees.blens); |
| 81 | if (s->mode == CODES) |
| 82 | inflate_codes_free(s->sub.decode.codes, z); |
| 83 | s->mode = TYPE; |
| 84 | s->bitk = 0; |
| 85 | s->bitb = 0; |
| 86 | s->read = s->write = s->window; |
| 87 | if (s->checkfn != Z_NULL) |
| 88 | z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0); |
| 89 | Tracev((stderr, "inflate: blocks reset\n")); |
| 90 | } |
| 91 | |
| 92 | #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */ |
| 93 | inflate_blocks_statef *inflate_blocks_new(z_streamp z, check_func c, uInt w) |
| 94 | #else |
| 95 | inflate_blocks_statef *inflate_blocks_new(z, c, w) |
| 96 | z_streamp z; |
| 97 | check_func c; |
| 98 | uInt w; |
| 99 | #endif |
| 100 | { |
| 101 | inflate_blocks_statef *s; |
| 102 | |
| 103 | if ((s = (inflate_blocks_statef *)ZALLOC |
| 104 | (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) |
| 105 | return s; |
| 106 | if ((s->hufts = |
| 107 | (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL) |
| 108 | { |
| 109 | ZFREE(z, s); |
| 110 | return Z_NULL; |
| 111 | } |
| 112 | if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) |
| 113 | { |
| 114 | ZFREE(z, s->hufts); |
| 115 | ZFREE(z, s); |
| 116 | return Z_NULL; |
| 117 | } |
| 118 | s->end = s->window + w; |
| 119 | s->checkfn = c; |
| 120 | s->mode = TYPE; |
| 121 | Tracev((stderr, "inflate: blocks allocated\n")); |
| 122 | inflate_blocks_reset(s, z, Z_NULL); |
| 123 | return s; |
| 124 | } |
| 125 | |
| 126 | #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */ |
| 127 | int inflate_blocks(inflate_blocks_statef* s, z_streamp z, int r) |
| 128 | #else |
| 129 | int inflate_blocks(s, z, r) |
| 130 | inflate_blocks_statef *s; |
| 131 | z_streamp z; |
| 132 | int r; |
| 133 | #endif |
| 134 | { |
| 135 | uInt t; /* temporary storage */ |
| 136 | uLong b; /* bit buffer */ |
| 137 | uInt k; /* bits in bit buffer */ |
| 138 | Bytef *p; /* input data pointer */ |
| 139 | uInt n; /* bytes available there */ |
| 140 | Bytef *q; /* output window write pointer */ |
| 141 | uInt m; /* bytes to end of window or read pointer */ |
| 142 | |
| 143 | /* copy input/output information to locals (UPDATE macro restores) */ |
| 144 | LOAD |
| 145 | |
| 146 | /* process input based on current state */ |
| 147 | while (1) switch (s->mode) |
| 148 | { |
| 149 | case TYPE: |
| 150 | NEEDBITS(3) |
| 151 | t = (uInt)b & 7; |
| 152 | s->last = t & 1; |
| 153 | switch (t >> 1) |
| 154 | { |
| 155 | case 0: /* stored */ |
| 156 | Tracev((stderr, "inflate: stored block%s\n", |
| 157 | s->last ? " (last)" : "")); |
| 158 | DUMPBITS(3) |
| 159 | t = k & 7; /* go to byte boundary */ |
| 160 | DUMPBITS(t) |
| 161 | s->mode = LENS; /* get length of stored block */ |
| 162 | break; |
| 163 | case 1: /* fixed */ |
| 164 | Tracev((stderr, "inflate: fixed codes block%s\n", |
| 165 | s->last ? " (last)" : "")); |
| 166 | { |
| 167 | uInt bl, bd; |
| 168 | inflate_huft *tl, *td; |
| 169 | |
| 170 | inflate_trees_fixed(&bl, &bd, &tl, &td, z); |
| 171 | s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); |
| 172 | if (s->sub.decode.codes == Z_NULL) |
| 173 | { |
| 174 | r = Z_MEM_ERROR; |
| 175 | LEAVE |
| 176 | } |
| 177 | } |
| 178 | DUMPBITS(3) |
| 179 | s->mode = CODES; |
| 180 | break; |
| 181 | case 2: /* dynamic */ |
| 182 | Tracev((stderr, "inflate: dynamic codes block%s\n", |
| 183 | s->last ? " (last)" : "")); |
| 184 | DUMPBITS(3) |
| 185 | s->mode = TABLE; |
| 186 | break; |
| 187 | case 3: /* illegal */ |
| 188 | DUMPBITS(3) |
| 189 | s->mode = BAD; |
| 190 | z->msg = (char*)"invalid block type"; |
| 191 | r = Z_DATA_ERROR; |
| 192 | LEAVE |
| 193 | } |
| 194 | break; |
| 195 | case LENS: |
| 196 | NEEDBITS(32) |
| 197 | if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) |
| 198 | { |
| 199 | s->mode = BAD; |
| 200 | z->msg = (char*)"invalid stored block lengths"; |
| 201 | r = Z_DATA_ERROR; |
| 202 | LEAVE |
| 203 | } |
| 204 | s->sub.left = (uInt)b & 0xffff; |
| 205 | b = k = 0; /* dump bits */ |
| 206 | Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); |
| 207 | s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); |
| 208 | break; |
| 209 | case STORED: |
| 210 | if (n == 0) |
| 211 | LEAVE |
| 212 | NEEDOUT |
| 213 | t = s->sub.left; |
| 214 | if (t > n) t = n; |
| 215 | if (t > m) t = m; |
| 216 | zmemcpy(q, p, t); |
| 217 | p += t; n -= t; |
| 218 | q += t; m -= t; |
| 219 | if ((s->sub.left -= t) != 0) |
| 220 | break; |
| 221 | Tracev((stderr, "inflate: stored end, %lu total out\n", |
| 222 | z->total_out + (q >= s->read ? q - s->read : |
| 223 | (s->end - s->read) + (q - s->window)))); |
| 224 | s->mode = s->last ? DRY : TYPE; |
| 225 | break; |
| 226 | case TABLE: |
| 227 | NEEDBITS(14) |
| 228 | s->sub.trees.table = t = (uInt)b & 0x3fff; |
| 229 | #ifndef PKZIP_BUG_WORKAROUND |
| 230 | if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) |
| 231 | { |
| 232 | s->mode = BAD; |
| 233 | z->msg = (char*)"too many length or distance symbols"; |
| 234 | r = Z_DATA_ERROR; |
| 235 | LEAVE |
| 236 | } |
| 237 | #endif |
| 238 | t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); |
| 239 | if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) |
| 240 | { |
| 241 | r = Z_MEM_ERROR; |
| 242 | LEAVE |
| 243 | } |
| 244 | DUMPBITS(14) |
| 245 | s->sub.trees.index = 0; |
| 246 | Tracev((stderr, "inflate: table sizes ok\n")); |
| 247 | s->mode = BTREE; |
| 248 | case BTREE: |
| 249 | while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) |
| 250 | { |
| 251 | NEEDBITS(3) |
| 252 | s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; |
| 253 | DUMPBITS(3) |
| 254 | } |
| 255 | while (s->sub.trees.index < 19) |
| 256 | s->sub.trees.blens[border[s->sub.trees.index++]] = 0; |
| 257 | s->sub.trees.bb = 7; |
| 258 | t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, |
| 259 | &s->sub.trees.tb, s->hufts, z); |
| 260 | if (t != Z_OK) |
| 261 | { |
| 262 | ZFREE(z, s->sub.trees.blens); |
| 263 | r = t; |
| 264 | if (r == Z_DATA_ERROR) |
| 265 | s->mode = BAD; |
| 266 | LEAVE |
| 267 | } |
| 268 | s->sub.trees.index = 0; |
| 269 | Tracev((stderr, "inflate: bits tree ok\n")); |
| 270 | s->mode = DTREE; |
| 271 | case DTREE: |
| 272 | while (t = s->sub.trees.table, |
| 273 | s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) |
| 274 | { |
| 275 | inflate_huft *h; |
| 276 | uInt i, j, c; |
| 277 | |
| 278 | t = s->sub.trees.bb; |
| 279 | NEEDBITS(t) |
| 280 | h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); |
| 281 | t = h->bits; |
| 282 | c = h->base; |
| 283 | if (c < 16) |
| 284 | { |
| 285 | DUMPBITS(t) |
| 286 | s->sub.trees.blens[s->sub.trees.index++] = c; |
| 287 | } |
| 288 | else /* c == 16..18 */ |
| 289 | { |
| 290 | i = c == 18 ? 7 : c - 14; |
| 291 | j = c == 18 ? 11 : 3; |
| 292 | NEEDBITS(t + i) |
| 293 | DUMPBITS(t) |
| 294 | j += (uInt)b & inflate_mask[i]; |
| 295 | DUMPBITS(i) |
| 296 | i = s->sub.trees.index; |
| 297 | t = s->sub.trees.table; |
| 298 | if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || |
| 299 | (c == 16 && i < 1)) |
| 300 | { |
| 301 | ZFREE(z, s->sub.trees.blens); |
| 302 | s->mode = BAD; |
| 303 | z->msg = (char*)"invalid bit length repeat"; |
| 304 | r = Z_DATA_ERROR; |
| 305 | LEAVE |
| 306 | } |
| 307 | c = c == 16 ? s->sub.trees.blens[i - 1] : 0; |
| 308 | do { |
| 309 | s->sub.trees.blens[i++] = c; |
| 310 | } while (--j); |
| 311 | s->sub.trees.index = i; |
| 312 | } |
| 313 | } |
| 314 | s->sub.trees.tb = Z_NULL; |
| 315 | { |
| 316 | uInt bl, bd; |
| 317 | inflate_huft *tl, *td; |
| 318 | inflate_codes_statef *c; |
| 319 | |
| 320 | bl = 9; /* must be <= 9 for lookahead assumptions */ |
| 321 | bd = 6; /* must be <= 9 for lookahead assumptions */ |
| 322 | t = s->sub.trees.table; |
| 323 | t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), |
| 324 | s->sub.trees.blens, &bl, &bd, &tl, &td, |
| 325 | s->hufts, z); |
| 326 | ZFREE(z, s->sub.trees.blens); |
| 327 | if (t != Z_OK) |
| 328 | { |
| 329 | if (t == (uInt)Z_DATA_ERROR) |
| 330 | s->mode = BAD; |
| 331 | r = t; |
| 332 | LEAVE |
| 333 | } |
| 334 | Tracev((stderr, "inflate: trees ok\n")); |
| 335 | if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) |
| 336 | { |
| 337 | r = Z_MEM_ERROR; |
| 338 | LEAVE |
| 339 | } |
| 340 | s->sub.decode.codes = c; |
| 341 | } |
| 342 | s->mode = CODES; |
| 343 | case CODES: |
| 344 | UPDATE |
| 345 | if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) |
| 346 | return inflate_flush(s, z, r); |
| 347 | r = Z_OK; |
| 348 | inflate_codes_free(s->sub.decode.codes, z); |
| 349 | LOAD |
| 350 | Tracev((stderr, "inflate: codes end, %lu total out\n", |
| 351 | z->total_out + (q >= s->read ? q - s->read : |
| 352 | (s->end - s->read) + (q - s->window)))); |
| 353 | if (!s->last) |
| 354 | { |
| 355 | s->mode = TYPE; |
| 356 | break; |
| 357 | } |
| 358 | if (k > 7) /* return unused byte, if any */ |
| 359 | { |
| 360 | Assert(k < 16, "inflate_codes grabbed too many bytes") |
| 361 | k -= 8; |
| 362 | n++; |
| 363 | p--; /* can always return one */ |
| 364 | } |
| 365 | s->mode = DRY; |
| 366 | case DRY: |
| 367 | FLUSH |
| 368 | if (s->read != s->write) |
| 369 | LEAVE |
| 370 | s->mode = DONE; |
| 371 | case DONE: |
| 372 | r = Z_STREAM_END; |
| 373 | LEAVE |
| 374 | case BAD: |
| 375 | r = Z_DATA_ERROR; |
| 376 | LEAVE |
| 377 | default: |
| 378 | r = Z_STREAM_ERROR; |
| 379 | LEAVE |
| 380 | } |
| 381 | } |
| 382 | |
| 383 | #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */ |
| 384 | int inflate_blocks_free(inflate_blocks_statef* s, z_streamp z) |
| 385 | #else |
| 386 | int inflate_blocks_free(s, z) |
| 387 | inflate_blocks_statef *s; |
| 388 | z_streamp z; |
| 389 | #endif |
| 390 | { |
| 391 | inflate_blocks_reset(s, z, Z_NULL); |
| 392 | ZFREE(z, s->window); |
| 393 | ZFREE(z, s->hufts); |
| 394 | ZFREE(z, s); |
| 395 | Tracev((stderr, "inflate: blocks freed\n")); |
| 396 | return Z_OK; |
| 397 | } |
| 398 | |
| 399 | #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */ |
| 400 | void inflate_set_dictionary(inflate_blocks_statef* s, const Bytef* d, uInt n) |
| 401 | #else |
| 402 | void inflate_set_dictionary(s, d, n) |
| 403 | inflate_blocks_statef *s; |
| 404 | const Bytef *d; |
| 405 | uInt n; |
| 406 | #endif |
| 407 | { |
| 408 | zmemcpy(s->window, d, n); |
| 409 | s->read = s->write = s->window + n; |
| 410 | } |
| 411 | |
| 412 | /* Returns true if inflate is currently at the end of a block generated |
| 413 | * by Z_SYNC_FLUSH or Z_FULL_FLUSH. |
| 414 | * IN assertion: s != Z_NULL |
| 415 | */ |
| 416 | #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */ |
| 417 | int inflate_blocks_sync_point(inflate_blocks_statef* s) |
| 418 | #else |
| 419 | int inflate_blocks_sync_point(s) |
| 420 | inflate_blocks_statef *s; |
| 421 | #endif |
| 422 | { |
| 423 | return s->mode == LENS; |
| 424 | } |