/* * This file includes code from libmspack adapted for libclamav by * tkojm@clamav.net * * Copyright (C) 2003-2004 Stuart Caie * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License version 2.1 as published by the Free Software Foundation. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 * USA */ #if HAVE_CONFIG_H #include "clamav-config.h" #endif #include #include #include "others.h" #include "clamav.h" #include "mspack.h" #if HAVE_LIMITS_H # include #endif #ifndef CHAR_BIT # define CHAR_BIT (8) #endif /*************************************************************************** * MS-ZIP decompression implementation *************************************************************************** * The LZX method was created by Jonathan Forbes and Tomi Poutanen, adapted * by Microsoft Corporation. * * The deflate method was created by Phil Katz. MSZIP is equivalent to the * deflate method. * */ /* match lengths for literal codes 257.. 285 */ static const unsigned short mszip_lit_lengths[29] = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 }; /* match offsets for distance codes 0 .. 29 */ static const unsigned short mszip_dist_offsets[30] = { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 }; /* extra bits required for literal codes 257.. 285 */ static const unsigned char mszip_lit_extrabits[29] = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 }; /* extra bits required for distance codes 0 .. 29 */ static const unsigned char mszip_dist_extrabits[30] = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 }; /* the order of the bit length Huffman code lengths */ static const unsigned char mszip_bitlen_order[19] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; /* ANDing with mszip_bit_mask[n] masks the lower n bits */ static const unsigned short mszip_bit_mask_tab[17] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff }; #define MSZIP_STORE_BITS do { \ zip->i_ptr = i_ptr; \ zip->i_end = i_end; \ zip->bit_buffer = bit_buffer; \ zip->bits_left = bits_left; \ } while (0) #define MSZIP_RESTORE_BITS do { \ i_ptr = zip->i_ptr; \ i_end = zip->i_end; \ bit_buffer = zip->bit_buffer; \ bits_left = zip->bits_left; \ } while (0) #define MSZIP_ENSURE_BITS(nbits) do { \ while (bits_left < (nbits)) { \ if (i_ptr >= i_end) { \ if (mszip_read_input(zip)) return zip->error; \ i_ptr = zip->i_ptr; \ i_end = zip->i_end; \ if(i_ptr == i_end) break; \ } \ bit_buffer |= *i_ptr++ << bits_left; bits_left += 8; \ } \ } while (0) #define MSZIP_PEEK_BITS(nbits) (bit_buffer & ((1<<(nbits))-1)) #define MSZIP_PEEK_BITS_T(nbits) (bit_buffer & mszip_bit_mask_tab[(nbits)]) #define MSZIP_REMOVE_BITS(nbits) ((bit_buffer >>= (nbits)), (bits_left -= (nbits))) #define MSZIP_READ_BITS(val, nbits) do { \ MSZIP_ENSURE_BITS(nbits); (val) = MSZIP_PEEK_BITS(nbits); MSZIP_REMOVE_BITS(nbits); \ } while (0) #define MSZIP_READ_BITS_T(val, nbits) do { \ MSZIP_ENSURE_BITS(nbits); (val) = MSZIP_PEEK_BITS_T(nbits); MSZIP_REMOVE_BITS(nbits); \ } while (0) static int mszip_read_input(struct mszip_stream *zip) { int nread = zip->read_cb ? zip->read_cb(zip->file, zip->inbuf, (int)zip->inbuf_size) : cli_readn(zip->fd, zip->inbuf, (int)zip->inbuf_size); if (nread < 0) { if (zip->file->error == CL_BREAK) return zip->error = CL_BREAK; else return zip->error = CL_EFORMAT; } zip->i_ptr = &zip->inbuf[0]; zip->i_end = &zip->inbuf[nread]; return CL_SUCCESS; } /* inflate() error codes */ #define INF_ERR_BLOCKTYPE (-1) /* unknown block type */ #define INF_ERR_COMPLEMENT (-2) /* block size complement mismatch */ #define INF_ERR_FLUSH (-3) /* error from flush_window() callback */ #define INF_ERR_BITBUF (-4) /* too many bits in bit buffer */ #define INF_ERR_SYMLENS (-5) /* too many symbols in blocktype 2 header */ #define INF_ERR_BITLENTBL (-6) /* failed to build bitlens huffman table */ #define INF_ERR_LITERALTBL (-7) /* failed to build literals huffman table */ #define INF_ERR_DISTANCETBL (-8) /* failed to build distance huffman table */ #define INF_ERR_BITOVERRUN (-9) /* bitlen RLE code goes over table size */ #define INF_ERR_BADBITLEN (-10) /* invalid bit-length code */ #define INF_ERR_LITCODE (-11) /* out-of-range literal code */ #define INF_ERR_DISTCODE (-12) /* out-of-range distance code */ #define INF_ERR_DISTANCE (-13) /* somehow, distance is beyond 32k */ #define INF_ERR_HUFFSYM (-14) /* out of bits decoding huffman symbol */ /* mszip_make_decode_table(nsyms, nbits, length[], table[]) * * This function was coded by David Tritscher. It builds a fast huffman * decoding table out of just a canonical huffman code lengths table. * * NOTE: this is NOT identical to the mszip_make_decode_table() in lzxd.c. This * one reverses the quick-lookup bit pattern. Bits are read MSB to LSB in LZX, * but LSB to MSB in MSZIP. * * nsyms = total number of symbols in this huffman tree. * nbits = any symbols with a code length of nbits or less can be decoded * in one lookup of the table. * length = A table to get code lengths from [0 to nsyms-1] * table = The table to fill up with decoded symbols and pointers. * * Returns 0 for OK or 1 for error */ static int mszip_make_decode_table(unsigned int nsyms, unsigned int nbits, unsigned char *length, unsigned short *table) { register unsigned int leaf, reverse, fill; register unsigned short sym, next_sym; register unsigned char bit_num; unsigned int pos = 0; /* the current position in the decode table */ unsigned int table_mask = 1 << nbits; unsigned int mszip_bit_mask = table_mask >> 1; /* don't do 0 length codes */ /* fill entries for codes short enough for a direct mapping */ for (bit_num = 1; bit_num <= nbits; bit_num++) { for (sym = 0; sym < nsyms; sym++) { if (length[sym] != bit_num) continue; /* reverse the significant bits */ fill = length[sym]; reverse = pos >> (nbits - fill); leaf = 0; do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill); if((pos += mszip_bit_mask) > table_mask) return 1; /* table overrun */ /* fill all possible lookups of this symbol with the symbol itself */ fill = mszip_bit_mask; next_sym = 1 << bit_num; do { table[leaf] = sym; leaf += next_sym; } while (--fill); } mszip_bit_mask >>= 1; } /* exit with success if table is now complete */ if (pos == table_mask) return 0; /* mark all remaining table entries as unused */ for (sym = pos; sym < table_mask; sym++) { reverse = sym; leaf = 0; fill = nbits; do { leaf <<= 1; leaf |= reverse & 1; reverse >>= 1; } while (--fill); table[leaf] = 0xFFFF; } /* where should the longer codes be allocated from? */ next_sym = ((table_mask >> 1) < nsyms) ? nsyms : (table_mask >> 1); /* give ourselves room for codes to grow by up to 16 more bits. * codes now start at bit nbits+16 and end at (nbits+16-codelength) */ pos <<= 16; table_mask <<= 16; mszip_bit_mask = 1 << 15; for (bit_num = nbits+1; bit_num <= MSZIP_MAX_HUFFBITS; bit_num++) { for (sym = 0; sym < nsyms; sym++) { if (length[sym] != bit_num) continue; /* leaf = the first nbits of the code, reversed */ reverse = pos >> 16; leaf = 0; fill = nbits; do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill); for (fill = 0; fill < (bit_num - nbits); fill++) { /* if this path hasn't been taken yet, 'allocate' two entries */ if (table[leaf] == 0xFFFF) { table[(next_sym << 1) ] = 0xFFFF; table[(next_sym << 1) + 1 ] = 0xFFFF; table[leaf] = next_sym++; } /* follow the path and select either left or right for next bit */ leaf = (table[leaf] << 1) | ((pos >> (15 - fill)) & 1); } table[leaf] = sym; if ((pos += mszip_bit_mask) > table_mask) return 1; /* table overflow */ } mszip_bit_mask >>= 1; } /* full table? */ return (pos != table_mask) ? 1 : 0; } /* MSZIP_READ_HUFFSYM(tablename, var) decodes one huffman symbol from the * bitstream using the stated table and puts it in var. */ #define MSZIP_READ_HUFFSYM(tbl, var) do { \ /* huffman symbols can be up to 16 bits long */ \ MSZIP_ENSURE_BITS(MSZIP_MAX_HUFFBITS); \ /* immediate table lookup of [tablebits] bits of the code */ \ sym = zip->tbl##_table[MSZIP_PEEK_BITS(MSZIP_##tbl##_TABLEBITS)]; \ /* is the symbol is longer than [tablebits] bits? (i=node index) */ \ if (sym >= MSZIP_##tbl##_MAXSYMBOLS) { \ /* decode remaining bits by tree traversal */ \ i = MSZIP_##tbl##_TABLEBITS - 1; \ do { \ /* check next bit. error if we run out of bits before decode */ \ if (i++ > MSZIP_MAX_HUFFBITS) { \ cli_dbgmsg("zip_inflate: out of bits in huffman decode\n"); \ return INF_ERR_HUFFSYM; \ } \ sym = (sym << 1) | ((bit_buffer >> i) & 1); \ if(sym >= MSZIP_##tbl##_TABLESIZE) { \ cli_dbgmsg("zip_inflate: index out of table\n"); \ return INF_ERR_HUFFSYM; \ } \ /* double node index and add 0 (left branch) or 1 (right) */ \ sym = zip->tbl##_table[sym]; \ /* while we are still in node indicies, not decoded symbols */ \ } while (sym >= MSZIP_##tbl##_MAXSYMBOLS); \ } \ /* result */ \ (var) = sym; \ /* look up the code length of that symbol and discard those bits */ \ i = zip->tbl##_len[sym]; \ MSZIP_REMOVE_BITS(i); \ } while (0) static int mszip_read_lens(struct mszip_stream *zip) { /* for the bit buffer and huffman decoding */ register unsigned int bit_buffer; register int bits_left; unsigned char *i_ptr, *i_end; /* bitlen Huffman codes -- immediate lookup, 7 bit max code length */ unsigned short bl_table[(1 << 7)]; unsigned char bl_len[19]; unsigned char lens[MSZIP_LITERAL_MAXSYMBOLS + MSZIP_DISTANCE_MAXSYMBOLS]; unsigned int lit_codes, dist_codes, code, last_code=0, bitlen_codes, i, run; MSZIP_RESTORE_BITS; /* read the number of codes */ MSZIP_READ_BITS(lit_codes, 5); lit_codes += 257; MSZIP_READ_BITS(dist_codes, 5); dist_codes += 1; MSZIP_READ_BITS(bitlen_codes, 4); bitlen_codes += 4; if (lit_codes > MSZIP_LITERAL_MAXSYMBOLS) return INF_ERR_SYMLENS; if (dist_codes > MSZIP_DISTANCE_MAXSYMBOLS) return INF_ERR_SYMLENS; /* read in the bit lengths in their unusual order */ for (i = 0; i < bitlen_codes; i++) MSZIP_READ_BITS(bl_len[mszip_bitlen_order[i]], 3); while (i < 19) bl_len[mszip_bitlen_order[i++]] = 0; /* create decoding table with an immediate lookup */ if (mszip_make_decode_table(19, 7, &bl_len[0], &bl_table[0])) { return INF_ERR_BITLENTBL; } /* read literal / distance code lengths */ for (i = 0; i < (lit_codes + dist_codes); i++) { /* single-level huffman lookup */ MSZIP_ENSURE_BITS(7); code = bl_table[MSZIP_PEEK_BITS(7)]; MSZIP_REMOVE_BITS(bl_len[code]); if (code < 16) lens[i] = last_code = code; else { switch (code) { case 16: MSZIP_READ_BITS(run, 2); run += 3; code = last_code; break; case 17: MSZIP_READ_BITS(run, 3); run += 3; code = 0; break; case 18: MSZIP_READ_BITS(run, 7); run += 11; code = 0; break; default: cli_dbgmsg("zip_read_lens: bad code!: %u\n", code); return INF_ERR_BADBITLEN; } if ((i + run) > (lit_codes + dist_codes)) return INF_ERR_BITOVERRUN; while (run--) lens[i++] = code; i--; } } /* copy LITERAL code lengths and clear any remaining */ i = lit_codes; memcpy(&zip->LITERAL_len[0], &lens[0], i); while (i < MSZIP_LITERAL_MAXSYMBOLS) zip->LITERAL_len[i++] = 0; i = dist_codes; memcpy(&zip->DISTANCE_len[0], &lens[lit_codes], i); while (i < MSZIP_DISTANCE_MAXSYMBOLS) zip->DISTANCE_len[i++] = 0; MSZIP_STORE_BITS; return 0; } static int mspack_write(int fd, const void *buff, unsigned int count, struct cab_file *file) { int ret; if(file->max_size) { if(file->written_size >= file->max_size) return CL_BREAK; if(file->written_size + count > file->max_size) count = file->max_size - file->written_size; } if((ret = cli_writen(fd, buff, count)) > 0) file->written_size += ret; return (ret == -1) ? CL_EWRITE : CL_SUCCESS; } /* a clean implementation of RFC 1951 / inflate */ static int mszip_inflate(struct mszip_stream *zip) { unsigned int last_block, block_type, distance, length, this_run, i; /* for the bit buffer and huffman decoding */ register unsigned int bit_buffer; register int bits_left; register unsigned short sym; unsigned char *i_ptr, *i_end; MSZIP_RESTORE_BITS; do { /* read in last block bit */ MSZIP_READ_BITS(last_block, 1); /* read in block type */ MSZIP_READ_BITS(block_type, 2); if (block_type == 0) { /* uncompressed block */ unsigned char lens_buf[4]; /* go to byte boundary */ i = bits_left & 7; MSZIP_REMOVE_BITS(i); /* read 4 bytes of data, emptying the bit-buffer if necessary */ for (i = 0; (bits_left >= 8); i++) { if (i == 4) return INF_ERR_BITBUF; lens_buf[i] = MSZIP_PEEK_BITS(8); MSZIP_REMOVE_BITS(8); } if (bits_left != 0) return INF_ERR_BITBUF; while (i < 4) { if (i_ptr >= i_end) { if (mszip_read_input(zip)) return zip->error; i_ptr = zip->i_ptr; i_end = zip->i_end; if(i_ptr == i_end) break; } lens_buf[i++] = *i_ptr++; } if (i < 4) return INF_ERR_BITBUF; /* get the length and its complement */ length = lens_buf[0] | (lens_buf[1] << 8); i = lens_buf[2] | (lens_buf[3] << 8); if (length != (~i & 0xFFFF)) return INF_ERR_COMPLEMENT; /* read and copy the uncompressed data into the window */ while (length > 0) { if (i_ptr >= i_end) { if (mszip_read_input(zip)) return zip->error; i_ptr = zip->i_ptr; i_end = zip->i_end; if(i_ptr == i_end) break; } this_run = length; if (this_run > (unsigned int)(i_end - i_ptr)) this_run = i_end - i_ptr; if (this_run > (MSZIP_FRAME_SIZE - zip->window_posn)) this_run = MSZIP_FRAME_SIZE - zip->window_posn; memcpy(&zip->window[zip->window_posn], i_ptr, this_run); zip->window_posn += this_run; i_ptr += this_run; length -= this_run; if (zip->window_posn == MSZIP_FRAME_SIZE) { if (zip->flush_window(zip, MSZIP_FRAME_SIZE)) return INF_ERR_FLUSH; zip->window_posn = 0; } } } else if ((block_type == 1) || (block_type == 2)) { /* Huffman-compressed LZ77 block */ unsigned int window_posn, match_posn, code; if (block_type == 1) { /* block with fixed Huffman codes */ i = 0; while (i < 144) zip->LITERAL_len[i++] = 8; while (i < 256) zip->LITERAL_len[i++] = 9; while (i < 280) zip->LITERAL_len[i++] = 7; while (i < 288) zip->LITERAL_len[i++] = 8; for (i = 0; i < 32; i++) zip->DISTANCE_len[i] = 5; } else { /* block with dynamic Huffman codes */ MSZIP_STORE_BITS; if ((i = mszip_read_lens(zip))) return i; MSZIP_RESTORE_BITS; } /* now huffman lengths are read for either kind of block, * create huffman decoding tables */ if (mszip_make_decode_table(MSZIP_LITERAL_MAXSYMBOLS, MSZIP_LITERAL_TABLEBITS, &zip->LITERAL_len[0], &zip->LITERAL_table[0])) { return INF_ERR_LITERALTBL; } if (mszip_make_decode_table(MSZIP_DISTANCE_MAXSYMBOLS,MSZIP_DISTANCE_TABLEBITS, &zip->DISTANCE_len[0], &zip->DISTANCE_table[0])) { return INF_ERR_DISTANCETBL; } /* decode forever until end of block code */ window_posn = zip->window_posn; while (1) { MSZIP_READ_HUFFSYM(LITERAL, code); if (code < 256) { zip->window[window_posn++] = (unsigned char) code; if (window_posn == MSZIP_FRAME_SIZE) { if (zip->flush_window(zip, MSZIP_FRAME_SIZE)) return INF_ERR_FLUSH; window_posn = 0; } } else if (code == 256) { /* END OF BLOCK CODE: loop break point */ break; } else { code -= 257; if (code > 29) return INF_ERR_LITCODE; MSZIP_READ_BITS_T(length, mszip_lit_extrabits[code]); length += mszip_lit_lengths[code]; MSZIP_READ_HUFFSYM(DISTANCE, code); if (code > 30) return INF_ERR_DISTCODE; MSZIP_READ_BITS_T(distance, mszip_dist_extrabits[code]); distance += mszip_dist_offsets[code]; /* match position is window position minus distance. If distance * is more than window position numerically, it must 'wrap * around' the frame size. */ match_posn = ((distance > window_posn) ? MSZIP_FRAME_SIZE : 0) + window_posn - distance; /* copy match */ if (length < 12) { /* short match, use slower loop but no loop setup code */ while (length--) { zip->window[window_posn++] = zip->window[match_posn++]; match_posn &= MSZIP_FRAME_SIZE - 1; if (window_posn == MSZIP_FRAME_SIZE) { if (zip->flush_window(zip, MSZIP_FRAME_SIZE)) return INF_ERR_FLUSH; window_posn = 0; } } } else { /* longer match, use faster loop but with setup expense */ unsigned char *runsrc, *rundest; do { this_run = length; if ((match_posn + this_run) > MSZIP_FRAME_SIZE) this_run = MSZIP_FRAME_SIZE - match_posn; if ((window_posn + this_run) > MSZIP_FRAME_SIZE) this_run = MSZIP_FRAME_SIZE - window_posn; rundest = &zip->window[window_posn]; window_posn += this_run; runsrc = &zip->window[match_posn]; match_posn += this_run; length -= this_run; while (this_run--) *rundest++ = *runsrc++; /* flush if necessary */ if (window_posn == MSZIP_FRAME_SIZE) { if (zip->flush_window(zip, MSZIP_FRAME_SIZE)) return INF_ERR_FLUSH; window_posn = 0; } if (match_posn == MSZIP_FRAME_SIZE) match_posn = 0; } while (length > 0); } } /* else (code >= 257) */ } /* while (forever) -- break point at 'code == 256' */ zip->window_posn = window_posn; } else { /* block_type == 3 -- bad block type */ return INF_ERR_BLOCKTYPE; } } while (!last_block); /* flush the remaining data */ if (zip->window_posn) { if (zip->flush_window(zip, zip->window_posn)) return INF_ERR_FLUSH; } MSZIP_STORE_BITS; /* return success */ return 0; } /* inflate() calls this whenever the window should be flushed. As * MSZIP only expands to the size of the window, the implementation used * simply keeps track of the amount of data flushed, and if more than 32k * is flushed, an error is raised. */ static int mszip_flush_window(struct mszip_stream *zip, unsigned int data_flushed) { zip->bytes_output += data_flushed; if (zip->bytes_output > MSZIP_FRAME_SIZE) { cli_dbgmsg("mszip_flush_window: overflow: %u bytes flushed, total is now %u\n", data_flushed, zip->bytes_output); return 1; } return 0; } struct mszip_stream *mszip_init(int fd, int ofd, int input_buffer_size, int repair_mode, struct cab_file *file, int (*read_cb)(struct cab_file *, unsigned char *, int)) { struct mszip_stream *zip; input_buffer_size = (input_buffer_size + 1) & -2; if (!input_buffer_size) return NULL; /* allocate decompression state */ if (!(zip = cli_calloc(1, sizeof(struct mszip_stream)))) { return NULL; } /* allocate input buffer */ zip->inbuf = cli_malloc((size_t) input_buffer_size); if (!zip->inbuf) { free(zip); return NULL; } /* initialise decompression state */ zip->fd = fd; zip->ofd = ofd; zip->wflag = 1; zip->inbuf_size = input_buffer_size; zip->error = CL_SUCCESS; zip->repair_mode = repair_mode; zip->flush_window = &mszip_flush_window; zip->input_end = 0; zip->i_ptr = zip->i_end = &zip->inbuf[0]; zip->o_ptr = zip->o_end = NULL; zip->bit_buffer = 0; zip->bits_left = 0; zip->file = file; zip->read_cb = read_cb; return zip; } int mszip_decompress(struct mszip_stream *zip, off_t out_bytes) { /* for the bit buffer */ register unsigned int bit_buffer; register int bits_left; unsigned char *i_ptr, *i_end; int i, ret, state, error; /* easy answers */ if (!zip || (out_bytes < 0)) return CL_ENULLARG; if (zip->error) return zip->error; /* flush out any stored-up bytes before we begin */ i = zip->o_end - zip->o_ptr; if ((off_t) i > out_bytes) i = (int) out_bytes; if (i) { if (zip->wflag && (ret = mspack_write(zip->ofd, zip->o_ptr, i, zip->file)) != CL_SUCCESS) { return zip->error = ret; } zip->o_ptr += i; out_bytes -= i; } if (out_bytes == 0) return CL_SUCCESS; while (out_bytes > 0) { /* unpack another block */ MSZIP_RESTORE_BITS; /* skip to next read 'CK' header */ i = bits_left & 7; MSZIP_REMOVE_BITS(i); /* align to bytestream */ state = 0; do { MSZIP_READ_BITS(i, 8); if (i == 'C') state = 1; else if ((state == 1) && (i == 'K')) state = 2; else state = 0; } while (state != 2); /* inflate a block, repair and realign if necessary */ zip->window_posn = 0; zip->bytes_output = 0; MSZIP_STORE_BITS; if ((error = mszip_inflate(zip))) { cli_dbgmsg("mszip_decompress: inflate error %d\n", error); if (zip->repair_mode) { cli_dbgmsg("mszip_decompress: MSZIP error, %u bytes of data lost\n", MSZIP_FRAME_SIZE - zip->bytes_output); for (i = zip->bytes_output; i < MSZIP_FRAME_SIZE; i++) { zip->window[i] = '\0'; } zip->bytes_output = MSZIP_FRAME_SIZE; } else { return zip->error = (error > 0) ? error : CL_EFORMAT; } } zip->o_ptr = &zip->window[0]; zip->o_end = &zip->o_ptr[zip->bytes_output]; /* write a frame */ i = (out_bytes < (off_t)zip->bytes_output) ? (int)out_bytes : zip->bytes_output; if (zip->wflag && (ret = mspack_write(zip->ofd, zip->o_ptr, i, zip->file)) != CL_SUCCESS) { return zip->error = ret; } /* mspack errors (i.e. read errors) are fatal and can't be recovered */ if ((error > 0) && zip->repair_mode) return error; zip->o_ptr += i; out_bytes -= i; } if (out_bytes) cli_dbgmsg("mszip_decompress: bytes left to output\n"); return CL_SUCCESS; } void mszip_free(struct mszip_stream *zip) { if (zip) { free(zip->inbuf); free(zip); } } /*************************************************************************** * LZX decompression implementation *************************************************************************** * The LZX method was created by Jonathan Forbes and Tomi Poutanen, adapted * by Microsoft Corporation. * */ /* LZX decompressor input macros * * LZX_STORE_BITS stores bitstream state in lzx_stream structure * LZX_RESTORE_BITS restores bitstream state from lzx_stream structure * LZX_READ_BITS(var,n) takes N bits from the buffer and puts them in var * LZX_ENSURE_BITS(n) ensures there are at least N bits in the bit buffer. * LZX_PEEK_BITS(n) extracts without removing N bits from the bit buffer * LZX_REMOVE_BITS(n) removes N bits from the bit buffer * */ #define LZX_BITBUF_WIDTH (sizeof(bit_buffer) * CHAR_BIT) #define LZX_STORE_BITS do { \ lzx->i_ptr = i_ptr; \ lzx->i_end = i_end; \ lzx->bit_buffer = bit_buffer; \ lzx->bits_left = bits_left; \ } while (0) #define LZX_RESTORE_BITS do { \ i_ptr = lzx->i_ptr; \ i_end = lzx->i_end; \ bit_buffer = lzx->bit_buffer; \ bits_left = lzx->bits_left; \ } while (0) #define LZX_ENSURE_BITS(nbits) \ while (bits_left < (nbits)) { \ if (i_ptr + 1 >= i_end) { \ if (lzx_read_input(lzx)) return lzx->error; \ i_ptr = lzx->i_ptr; \ i_end = lzx->i_end; \ } \ bit_buffer |= ((i_ptr[1] << 8) | i_ptr[0]) \ << (LZX_BITBUF_WIDTH - 16 - bits_left); \ bits_left += 16; \ i_ptr += 2; \ } #define LZX_PEEK_BITS(nbits) (bit_buffer >> (LZX_BITBUF_WIDTH - (nbits))) #define LZX_REMOVE_BITS(nbits) ((bit_buffer <<= (nbits)), (bits_left -= (nbits))) #define LZX_READ_BITS(val, nbits) do { \ LZX_ENSURE_BITS(nbits); \ (val) = LZX_PEEK_BITS(nbits); \ LZX_REMOVE_BITS(nbits); \ } while (0) static int lzx_read_input(struct lzx_stream *lzx) { int bread = lzx->read_cb ? lzx->read_cb(lzx->file, &lzx->inbuf[0], (int)lzx->inbuf_size) : cli_readn(lzx->fd, &lzx->inbuf[0], (int)lzx->inbuf_size); if (bread < 0) { if (lzx->file->error == CL_BREAK) return lzx->error = CL_BREAK; else return lzx->error = CL_EFORMAT; } /* huff decode's ENSURE_BYTES(16) might overrun the input stream, even * if those bits aren't used, so fake 2 more bytes */ if (bread == 0) { if (lzx->input_end) { cli_dbgmsg("lzx_read_input: out of input bytes\n"); return lzx->error = CL_EREAD; } else { bread = 2; lzx->inbuf[0] = lzx->inbuf[1] = 0; lzx->input_end = 1; } } lzx->i_ptr = &lzx->inbuf[0]; lzx->i_end = &lzx->inbuf[bread]; return CL_SUCCESS; } /* Huffman decoding macros */ /* LZX_READ_HUFFSYM(tablename, var) decodes one huffman symbol from the * bitstream using the stated table and puts it in var. */ #define LZX_READ_HUFFSYM(tbl, var) do { \ /* huffman symbols can be up to 16 bits long */ \ LZX_ENSURE_BITS(16); \ /* immediate table lookup of [tablebits] bits of the code */ \ sym = lzx->tbl##_table[LZX_PEEK_BITS(LZX_##tbl##_TABLEBITS)]; \ /* is the symbol is longer than [tablebits] bits? (i=node index) */ \ if (sym >= LZX_##tbl##_MAXSYMBOLS) { \ /* decode remaining bits by tree traversal */ \ i = 1 << (LZX_BITBUF_WIDTH - LZX_##tbl##_TABLEBITS); \ do { \ /* one less bit. error if we run out of bits before decode */ \ i >>= 1; \ if (i == 0) { \ cli_dbgmsg("lzx: out of bits in huffman decode\n"); \ return lzx->error = CL_EFORMAT; \ } \ /* double node index and add 0 (left branch) or 1 (right) */ \ sym <<= 1; sym |= (bit_buffer & i) ? 1 : 0; \ /* hop to next node index / decoded symbol */ \ if(sym >= (1 << LZX_##tbl##_TABLEBITS) + (LZX_##tbl##_MAXSYMBOLS * 2)) { \ cli_dbgmsg("lzx: index out of table\n"); \ return lzx->error = CL_EFORMAT; \ } \ sym = lzx->tbl##_table[sym]; \ /* while we are still in node indicies, not decoded symbols */ \ } while (sym >= LZX_##tbl##_MAXSYMBOLS); \ } \ /* result */ \ (var) = sym; \ /* look up the code length of that symbol and discard those bits */ \ i = lzx->tbl##_len[sym]; \ LZX_REMOVE_BITS(i); \ } while (0) /* LZX_BUILD_TABLE(tbl) builds a huffman lookup table from code lengths */ #define LZX_BUILD_TABLE(tbl) \ if (lzx_make_decode_table(LZX_##tbl##_MAXSYMBOLS, LZX_##tbl##_TABLEBITS, \ &lzx->tbl##_len[0], &lzx->tbl##_table[0])) \ { \ cli_dbgmsg("lzx: failed to build %s table\n", #tbl); \ return lzx->error = CL_EFORMAT; \ } /* lzx_make_decode_table(nsyms, nbits, length[], table[]) * * This function was coded by David Tritscher. It builds a fast huffman * decoding table from a canonical huffman code lengths table. * * nsyms = total number of symbols in this huffman tree. * nbits = any symbols with a code length of nbits or less can be decoded * in one lookup of the table. * length = A table to get code lengths from [0 to syms-1] * table = The table to fill up with decoded symbols and pointers. * * Returns 0 for OK or 1 for error */ static int lzx_make_decode_table(unsigned int nsyms, unsigned int nbits, unsigned char *length, unsigned short *table) { register unsigned short sym; register unsigned int leaf, fill; register unsigned char bit_num; unsigned int pos = 0; /* the current position in the decode table */ unsigned int table_mask = 1 << nbits; unsigned int bit_mask = table_mask >> 1; /* don't do 0 length codes */ unsigned int next_symbol = bit_mask; /* base of allocation for long codes */ /* fill entries for codes short enough for a direct mapping */ for (bit_num = 1; bit_num <= nbits; bit_num++) { for (sym = 0; sym < nsyms; sym++) { if (length[sym] != bit_num) continue; leaf = pos; if((pos += bit_mask) > table_mask) return 1; /* table overrun */ /* fill all possible lookups of this symbol with the symbol itself */ for (fill = bit_mask; fill-- > 0;) table[leaf++] = sym; } bit_mask >>= 1; } /* full table already? */ if (pos == table_mask) return 0; /* clear the remainder of the table */ for (sym = pos; sym < table_mask; sym++) table[sym] = 0xFFFF; /* allow codes to be up to nbits+16 long, instead of nbits */ pos <<= 16; table_mask <<= 16; bit_mask = 1 << 15; for (bit_num = nbits+1; bit_num <= 16; bit_num++) { for (sym = 0; sym < nsyms; sym++) { if (length[sym] != bit_num) continue; leaf = pos >> 16; for (fill = 0; fill < bit_num - nbits; fill++) { /* if this path hasn't been taken yet, 'allocate' two entries */ if (table[leaf] == 0xFFFF) { table[(next_symbol << 1)] = 0xFFFF; table[(next_symbol << 1) + 1] = 0xFFFF; table[leaf] = next_symbol++; } /* follow the path and select either left or right for next bit */ leaf = table[leaf] << 1; if ((pos >> (15-fill)) & 1) leaf++; } table[leaf] = sym; if ((pos += bit_mask) > table_mask) return 1; /* table overflow */ } bit_mask >>= 1; } /* full table? */ if (pos == table_mask) return 0; /* either erroneous table, or all elements are 0 - let's find out. */ for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1; return 0; } /* LZX_READ_LENGTHS(tablename, first, last) reads in code lengths for symbols * first to last in the given table. The code lengths are stored in their * own special LZX way. */ #define LZX_READ_LENGTHS(tbl, first, last) do { \ LZX_STORE_BITS; \ if (lzx_read_lens(lzx, &lzx->tbl##_len[0], (first), \ (unsigned int)(last))) return lzx->error; \ LZX_RESTORE_BITS; \ } while (0) static int lzx_read_lens(struct lzx_stream *lzx, unsigned char *lens, unsigned int first, unsigned int last) { /* bit buffer and huffman symbol decode variables */ register unsigned int bit_buffer; register int bits_left, i; register unsigned short sym; unsigned char *i_ptr, *i_end; unsigned int x, y; int z; LZX_RESTORE_BITS; /* read lengths for pretree (20 symbols, lengths stored in fixed 4 bits) */ for (x = 0; x < 20; x++) { LZX_READ_BITS(y, 4); lzx->PRETREE_len[x] = y; } LZX_BUILD_TABLE(PRETREE); for (x = first; x < last; ) { LZX_READ_HUFFSYM(PRETREE, z); if (z == 17) { /* code = 17, run of ([read 4 bits]+4) zeros */ LZX_READ_BITS(y, 4); y += 4; while (y--) lens[x++] = 0; } else if (z == 18) { /* code = 18, run of ([read 5 bits]+20) zeros */ LZX_READ_BITS(y, 5); y += 20; while (y--) lens[x++] = 0; } else if (z == 19) { /* code = 19, run of ([read 1 bit]+4) [read huffman symbol] */ LZX_READ_BITS(y, 1); y += 4; LZX_READ_HUFFSYM(PRETREE, z); z = lens[x] - z; if (z < 0) z += 17; while (y--) lens[x++] = z; } else { /* code = 0 to 16, delta current length entry */ z = lens[x] - z; if (z < 0) z += 17; lens[x++] = z; } } LZX_STORE_BITS; return CL_SUCCESS; } static void lzx_reset_state(struct lzx_stream *lzx) { int i; lzx->R0 = 1; lzx->R1 = 1; lzx->R2 = 1; lzx->header_read = 0; lzx->block_remaining = 0; lzx->block_type = LZX_BLOCKTYPE_INVALID; /* initialise tables to 0 (because deltas will be applied to them) */ for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) lzx->MAINTREE_len[i] = 0; for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) lzx->LENGTH_len[i] = 0; } /*-------- main LZX code --------*/ struct lzx_stream *lzx_init(int fd, int ofd, int window_bits, int reset_interval, int input_buffer_size, off_t output_length, struct cab_file *file, int (*read_cb)(struct cab_file *, unsigned char *, int)) { unsigned int window_size = 1 << window_bits; struct lzx_stream *lzx; int i, j; /* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */ if (window_bits < 15 || window_bits > 21) return NULL; input_buffer_size = (input_buffer_size + 1) & -2; if (!input_buffer_size) return NULL; /* allocate decompression state */ if (!(lzx = cli_calloc(1, sizeof(struct lzx_stream)))) { return NULL; } for (i = 0, j = 0; i < 51; i += 2) { lzx->extra_bits[i] = j; /* 0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7... */ if(i < 50) lzx->extra_bits[i+1] = j; if ((i != 0) && (j < 17)) j++; /* 0,0,1,2,3,4...15,16,17,17,17,17... */ } for (i = 0, j = 0; i < 51; i++) { lzx->position_base[i] = j; /* 0,1,2,3,4,6,8,12,16,24,32,... */ j += 1 << lzx->extra_bits[i]; /* 1,1,1,1,2,2,4,4,8,8,16,16,32,32,... */ } /* allocate decompression window and input buffer */ lzx->window = cli_calloc(1, (size_t) window_size); if(!lzx->window) { free(lzx); return NULL; } lzx->inbuf = cli_calloc(1, (size_t) input_buffer_size); if (!lzx->inbuf) { free(lzx->window); free(lzx); return NULL; } /* initialise decompression state */ lzx->fd = fd; lzx->ofd = ofd; lzx->wflag = 1; lzx->offset = 0; lzx->length = output_length; lzx->file = file; lzx->read_cb = read_cb; lzx->inbuf_size = input_buffer_size; lzx->window_size = 1 << window_bits; lzx->window_posn = 0; lzx->frame_posn = 0; lzx->frame = 0; lzx->reset_interval = reset_interval; lzx->intel_filesize = 0; lzx->intel_curpos = 0; /* window bits: 15 16 17 18 19 20 21 * position slots: 30 32 34 36 38 42 50 */ lzx->posn_slots = ((window_bits == 21) ? 50 : ((window_bits == 20) ? 42 : (window_bits << 1))); lzx->intel_started = 0; lzx->input_end = 0; lzx->error = CL_SUCCESS; lzx->i_ptr = lzx->i_end = &lzx->inbuf[0]; lzx->o_ptr = lzx->o_end = &lzx->e8_buf[0]; lzx->bit_buffer = lzx->bits_left = 0; lzx_reset_state(lzx); return lzx; } void lzx_set_output_length(struct lzx_stream *lzx, off_t out_bytes) { if (lzx) lzx->length = out_bytes; } int lzx_decompress(struct lzx_stream *lzx, off_t out_bytes) { /* bitstream reading and huffman variables */ register unsigned int bit_buffer; register int bits_left, i=0; register unsigned short sym; unsigned char *i_ptr, *i_end; int match_length, length_footer, extra, verbatim_bits, bytes_todo; int this_run, main_element, aligned_bits, j, ret; unsigned char *window, *runsrc, *rundest, buf[12]; unsigned int frame_size=0, end_frame, match_offset, window_posn; unsigned int R0, R1, R2; /* easy answers */ if (!lzx || (out_bytes < 0)) return CL_ENULLARG; if (lzx->error) return lzx->error; /* flush out any stored-up bytes before we begin */ i = lzx->o_end - lzx->o_ptr; if ((off_t) i > out_bytes) i = (int) out_bytes; if (i) { if (lzx->wflag && (ret = mspack_write(lzx->ofd, lzx->o_ptr, i, lzx->file)) != CL_SUCCESS) { return lzx->error = ret; } lzx->o_ptr += i; lzx->offset += i; out_bytes -= i; } if (out_bytes == 0) return CL_SUCCESS; /* restore local state */ LZX_RESTORE_BITS; window = lzx->window; window_posn = lzx->window_posn; R0 = lzx->R0; R1 = lzx->R1; R2 = lzx->R2; end_frame = (unsigned int)((lzx->offset + out_bytes) / LZX_FRAME_SIZE) + 1; while (lzx->frame < end_frame) { /* have we reached the reset interval? (if there is one?) */ if (lzx->reset_interval && ((lzx->frame % lzx->reset_interval) == 0)) { if (lzx->block_remaining) { cli_dbgmsg("lzx_decompress: %d bytes remaining at reset interval\n", lzx->block_remaining); return lzx->error = CL_EFORMAT; } /* re-read the intel header and reset the huffman lengths */ lzx_reset_state(lzx); } /* read header if necessary */ if (!lzx->header_read) { /* read 1 bit. if bit=0, intel filesize = 0. * if bit=1, read intel filesize (32 bits) */ j = 0; LZX_READ_BITS(i, 1); if (i) { LZX_READ_BITS(i, 16); LZX_READ_BITS(j, 16); } lzx->intel_filesize = (i << 16) | j; lzx->header_read = 1; } /* calculate size of frame: all frames are 32k except the final frame * which is 32kb or less. this can only be calculated when lzx->length * has been filled in. */ frame_size = LZX_FRAME_SIZE; if (lzx->length && (lzx->length - lzx->offset) < (off_t)frame_size) { frame_size = lzx->length - lzx->offset; } /* decode until one more frame is available */ bytes_todo = lzx->frame_posn + frame_size - window_posn; while (bytes_todo > 0) { /* initialise new block, if one is needed */ if (lzx->block_remaining == 0) { /* realign if previous block was an odd-sized UNCOMPRESSED block */ if ((lzx->block_type == LZX_BLOCKTYPE_UNCOMPRESSED) && (lzx->block_length & 1)) { if (i_ptr == i_end) { if (lzx_read_input(lzx)) return lzx->error; i_ptr = lzx->i_ptr; i_end = lzx->i_end; } i_ptr++; } /* read block type (3 bits) and block length (24 bits) */ LZX_READ_BITS(lzx->block_type, 3); LZX_READ_BITS(i, 16); LZX_READ_BITS(j, 8); lzx->block_remaining = lzx->block_length = (i << 8) | j; /* read individual block headers */ switch (lzx->block_type) { case LZX_BLOCKTYPE_ALIGNED: /* read lengths of and build aligned huffman decoding tree */ for (i = 0; i < 8; i++) { LZX_READ_BITS(j, 3); lzx->ALIGNED_len[i] = j; } LZX_BUILD_TABLE(ALIGNED); /* no break -- rest of aligned header is same as verbatim */ case LZX_BLOCKTYPE_VERBATIM: /* read lengths of and build main huffman decoding tree */ LZX_READ_LENGTHS(MAINTREE, 0, 256); LZX_READ_LENGTHS(MAINTREE, 256, LZX_NUM_CHARS + (lzx->posn_slots << 3)); LZX_BUILD_TABLE(MAINTREE); /* if the literal 0xE8 is anywhere in the block... */ if (lzx->MAINTREE_len[0xE8] != 0) lzx->intel_started = 1; /* read lengths of and build lengths huffman decoding tree */ LZX_READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS); LZX_BUILD_TABLE(LENGTH); break; case LZX_BLOCKTYPE_UNCOMPRESSED: /* because we can't assume otherwise */ lzx->intel_started = 1; /* read 1-16 (not 0-15) bits to align to bytes */ LZX_ENSURE_BITS(16); if (bits_left > 16) i_ptr -= 2; bits_left = 0; bit_buffer = 0; /* read 12 bytes of stored R0 / R1 / R2 values */ for (rundest = &buf[0], i = 0; i < 12; i++) { if (i_ptr == i_end) { if (lzx_read_input(lzx)) return lzx->error; i_ptr = lzx->i_ptr; i_end = lzx->i_end; } *rundest++ = *i_ptr++; } R0 = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24); R1 = buf[4] | (buf[5] << 8) | (buf[6] << 16) | (buf[7] << 24); R2 = buf[8] | (buf[9] << 8) | (buf[10] << 16) | (buf[11] << 24); break; default: cli_dbgmsg("lzx_decompress: bad block type (0x%x)\n", lzx->block_type); return lzx->error = CL_EFORMAT; } } /* decode more of the block: * run = min(what's available, what's needed) */ this_run = lzx->block_remaining; if (this_run > bytes_todo) this_run = bytes_todo; /* assume we decode exactly this_run bytes, for now */ bytes_todo -= this_run; lzx->block_remaining -= this_run; /* decode at least this_run bytes */ switch (lzx->block_type) { case LZX_BLOCKTYPE_VERBATIM: while (this_run > 0) { LZX_READ_HUFFSYM(MAINTREE, main_element); if (main_element < LZX_NUM_CHARS) { /* literal: 0 to LZX_NUM_CHARS-1 */ window[window_posn++] = main_element; this_run--; } else { /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */ main_element -= LZX_NUM_CHARS; /* get match length */ match_length = main_element & LZX_NUM_PRIMARY_LENGTHS; if (match_length == LZX_NUM_PRIMARY_LENGTHS) { LZX_READ_HUFFSYM(LENGTH, length_footer); match_length += length_footer; } match_length += LZX_MIN_MATCH; /* get match offset */ switch ((match_offset = (main_element >> 3))) { case 0: match_offset = R0; break; case 1: match_offset = R1; R1=R0; R0 = match_offset; break; case 2: match_offset = R2; R2=R0; R0 = match_offset; break; case 3: match_offset = 1; R2=R1; R1=R0; R0 = match_offset; break; default: extra = lzx->extra_bits[match_offset]; LZX_READ_BITS(verbatim_bits, extra); match_offset = lzx->position_base[match_offset] - 2 + verbatim_bits; R2 = R1; R1 = R0; R0 = match_offset; } if ((window_posn + match_length) > lzx->window_size) { cli_dbgmsg("lzx_decompress: match ran over window wrap\n"); return lzx->error = CL_EFORMAT; } /* copy match */ rundest = &window[window_posn]; i = match_length; /* does match offset wrap the window? */ if (match_offset > window_posn) { /* j = length from match offset to end of window */ j = match_offset - window_posn; if (j > (int) lzx->window_size) { cli_dbgmsg("lzx_decompress: match offset beyond window boundaries\n"); return lzx->error = CL_EFORMAT; } runsrc = &window[lzx->window_size - j]; if (j < i) { /* if match goes over the window edge, do two copy runs */ i -= j; while (j-- > 0) *rundest++ = *runsrc++; runsrc = window; } while (i-- > 0) *rundest++ = *runsrc++; } else { runsrc = rundest - match_offset; if(i > (int) (lzx->window_size - window_posn)) i = lzx->window_size - window_posn; while (i-- > 0) *rundest++ = *runsrc++; } this_run -= match_length; window_posn += match_length; } } /* while (this_run > 0) */ break; case LZX_BLOCKTYPE_ALIGNED: while (this_run > 0) { LZX_READ_HUFFSYM(MAINTREE, main_element); if (main_element < LZX_NUM_CHARS) { /* literal: 0 to LZX_NUM_CHARS-1 */ window[window_posn++] = main_element; this_run--; } else { /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */ main_element -= LZX_NUM_CHARS; /* get match length */ match_length = main_element & LZX_NUM_PRIMARY_LENGTHS; if (match_length == LZX_NUM_PRIMARY_LENGTHS) { LZX_READ_HUFFSYM(LENGTH, length_footer); match_length += length_footer; } match_length += LZX_MIN_MATCH; /* get match offset */ switch ((match_offset = (main_element >> 3))) { case 0: match_offset = R0; break; case 1: match_offset = R1; R1 = R0; R0 = match_offset; break; case 2: match_offset = R2; R2 = R0; R0 = match_offset; break; default: extra = lzx->extra_bits[match_offset]; match_offset = lzx->position_base[match_offset] - 2; if (extra > 3) { /* verbatim and aligned bits */ extra -= 3; LZX_READ_BITS(verbatim_bits, extra); match_offset += (verbatim_bits << 3); LZX_READ_HUFFSYM(ALIGNED, aligned_bits); match_offset += aligned_bits; } else if (extra == 3) { /* aligned bits only */ LZX_READ_HUFFSYM(ALIGNED, aligned_bits); match_offset += aligned_bits; } else if (extra > 0) { /* extra==1, extra==2 */ /* verbatim bits only */ LZX_READ_BITS(verbatim_bits, extra); match_offset += verbatim_bits; } else /* extra == 0 */ { /* ??? not defined in LZX specification! */ match_offset = 1; } /* update repeated offset LRU queue */ R2 = R1; R1 = R0; R0 = match_offset; } if ((window_posn + match_length) > lzx->window_size) { cli_dbgmsg("lzx_decompress: match ran over window wrap\n"); return lzx->error = CL_EFORMAT; } /* copy match */ rundest = &window[window_posn]; i = match_length; /* does match offset wrap the window? */ if (match_offset > window_posn) { /* j = length from match offset to end of window */ j = match_offset - window_posn; if (j > (int) lzx->window_size) { cli_dbgmsg("lzx_decompress: match offset beyond window boundaries\n"); return lzx->error = CL_EFORMAT; } runsrc = &window[lzx->window_size - j]; if (j < i) { /* if match goes over the window edge, do two copy runs */ i -= j; while (j-- > 0) *rundest++ = *runsrc++; runsrc = window; } while (i-- > 0) *rundest++ = *runsrc++; } else { runsrc = rundest - match_offset; while (i-- > 0) *rundest++ = *runsrc++; } this_run -= match_length; window_posn += match_length; } } /* while (this_run > 0) */ break; case LZX_BLOCKTYPE_UNCOMPRESSED: /* as this_run is limited not to wrap a frame, this also means it * won't wrap the window (as the window is a multiple of 32k) */ rundest = &window[window_posn]; window_posn += this_run; while (this_run > 0) { if ((i = i_end - i_ptr)) { if (i > this_run) i = this_run; memcpy(rundest, i_ptr, (size_t) i); rundest += i; i_ptr += i; this_run -= i; } else { if (lzx_read_input(lzx)) return lzx->error; i_ptr = lzx->i_ptr; i_end = lzx->i_end; } } break; default: return lzx->error = CL_EFORMAT; /* might as well */ } /* did the final match overrun our desired this_run length? */ if (this_run < 0) { if ((unsigned int)(-this_run) > lzx->block_remaining) { cli_dbgmsg("lzx_decompress: overrun went past end of block by %d (%d remaining)\n", -this_run, lzx->block_remaining); return lzx->error = CL_EFORMAT; } lzx->block_remaining -= -this_run; } } /* while (bytes_todo > 0) */ /* streams don't extend over frame boundaries */ if ((window_posn - lzx->frame_posn) != frame_size) { cli_dbgmsg("lzx_decompress: decode beyond output frame limits! %d != %d\n", window_posn - lzx->frame_posn, frame_size); return lzx->error = CL_EFORMAT; } /* re-align input bitstream */ if (bits_left > 0) LZX_ENSURE_BITS(16); if (bits_left & 15) LZX_REMOVE_BITS(bits_left & 15); /* check that we've used all of the previous frame first */ if (lzx->o_ptr != lzx->o_end) { cli_dbgmsg("lzx_decompress: %ld avail bytes, new %d frame\n", lzx->o_end-lzx->o_ptr, frame_size); return lzx->error = CL_EFORMAT; } /* does this intel block _really_ need decoding? */ if (lzx->intel_started && lzx->intel_filesize && (lzx->frame <= 32768) && (frame_size > 10)) { unsigned char *data = &lzx->e8_buf[0]; unsigned char *dataend = &lzx->e8_buf[frame_size - 10]; signed int curpos = lzx->intel_curpos; signed int filesize = lzx->intel_filesize; signed int abs_off, rel_off; /* copy e8 block to the e8 buffer and tweak if needed */ lzx->o_ptr = data; memcpy(data, &lzx->window[lzx->frame_posn], frame_size); while (data < dataend) { if (*data++ != 0xE8) { curpos++; continue; } abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24); if ((abs_off >= -curpos) && (abs_off < filesize)) { rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize; data[0] = (unsigned char) rel_off; data[1] = (unsigned char) (rel_off >> 8); data[2] = (unsigned char) (rel_off >> 16); data[3] = (unsigned char) (rel_off >> 24); } data += 4; curpos += 5; } lzx->intel_curpos += frame_size; } else { lzx->o_ptr = &lzx->window[lzx->frame_posn]; if (lzx->intel_filesize) lzx->intel_curpos += frame_size; } lzx->o_end = &lzx->o_ptr[frame_size]; /* write a frame */ i = (out_bytes < (off_t)frame_size) ? (unsigned int)out_bytes : frame_size; if (lzx->wflag && (ret = mspack_write(lzx->ofd, lzx->o_ptr, i, lzx->file)) != CL_SUCCESS) { return lzx->error = ret; } lzx->o_ptr += i; lzx->offset += i; out_bytes -= i; /* advance frame start position */ lzx->frame_posn += frame_size; lzx->frame++; /* wrap window / frame position pointers */ if (window_posn == lzx->window_size) window_posn = 0; if (lzx->frame_posn == lzx->window_size) lzx->frame_posn = 0; } /* while (lzx->frame < end_frame) */ if (out_bytes) cli_dbgmsg("lzx_decompress: bytes left to output\n"); /* store local state */ LZX_STORE_BITS; lzx->window_posn = window_posn; lzx->R0 = R0; lzx->R1 = R1; lzx->R2 = R2; return CL_SUCCESS; } void lzx_free(struct lzx_stream *lzx) { if (lzx) { free(lzx->inbuf); free(lzx->window); free(lzx); } } /*************************************************************************** * Quantum decompression implementation *************************************************************************** * The Quantum method was created by David Stafford, adapted by Microsoft * Corporation. * * This decompressor is based on an implementation by Matthew Russotto, used * with permission. * * This decompressor was researched and implemented by Matthew Russotto. It * has since been tidied up by Stuart Caie. More information can be found at * http://www.speakeasy.org/~russotto/quantumcomp.html */ /* Quantum decompressor bitstream reading macros * * QTM_STORE_BITS stores bitstream state in qtm_stream structure * QTM_RESTORE_BITS restores bitstream state from qtm_stream structure * QTM_READ_BITS(var,n) takes N bits from the buffer and puts them in var * QTM_FILL_BUFFER if there is room for another 16 bits, reads another * 16 bits from the input stream. * QTM_PEEK_BITS(n) extracts without removing N bits from the bit buffer * QTM_REMOVE_BITS(n) removes N bits from the bit buffer * * These bit access routines work by using the area beyond the MSB and the * LSB as a free source of zeroes. This avoids having to mask any bits. * So we have to know the bit width of the bitbuffer variable. */ #define QTM_BITBUF_WIDTH (sizeof(unsigned int) * CHAR_BIT) #define QTM_STORE_BITS do { \ qtm->i_ptr = i_ptr; \ qtm->i_end = i_end; \ qtm->bit_buffer = bit_buffer; \ qtm->bits_left = bits_left; \ } while (0) #define QTM_RESTORE_BITS do { \ i_ptr = qtm->i_ptr; \ i_end = qtm->i_end; \ bit_buffer = qtm->bit_buffer; \ bits_left = qtm->bits_left; \ } while (0) /* adds 16 bits to bit buffer, if there's space for the new bits */ #define QTM_FILL_BUFFER do { \ if (bits_left <= (QTM_BITBUF_WIDTH - 16)) { \ if (i_ptr >= i_end) { \ if (qtm_read_input(qtm)) return qtm->error; \ i_ptr = qtm->i_ptr; \ i_end = qtm->i_end; \ } \ bit_buffer |= ((i_ptr[0] << 8) | i_ptr[1]) \ << (QTM_BITBUF_WIDTH - 16 - bits_left); \ bits_left += 16; \ i_ptr += 2; \ } \ } while (0) #define QTM_PEEK_BITS(n) (bit_buffer >> (QTM_BITBUF_WIDTH - (n))) #define QTM_REMOVE_BITS(n) ((bit_buffer <<= (n)), (bits_left -= (n))) #define QTM_READ_BITS(val, bits) do { \ (val) = 0; \ for (bits_needed = (bits); bits_needed > 0; bits_needed -= bit_run) { \ QTM_FILL_BUFFER; \ bit_run = (bits_left < bits_needed) ? bits_left : bits_needed; \ (val) = ((val) << bit_run) | QTM_PEEK_BITS(bit_run); \ QTM_REMOVE_BITS(bit_run); \ } \ } while (0) static int qtm_read_input(struct qtm_stream *qtm) { int nread = qtm->read_cb ? qtm->read_cb(qtm->file, &qtm->inbuf[0], (int)qtm->inbuf_size) : cli_readn(qtm->fd, &qtm->inbuf[0], (int)qtm->inbuf_size); if (nread < 0) { if (qtm->file->error == CL_BREAK) return qtm->error = CL_BREAK; else return qtm->error = CL_EFORMAT; } qtm->i_ptr = &qtm->inbuf[0]; qtm->i_end = &qtm->inbuf[nread]; return CL_SUCCESS; } /* Arithmetic decoder: * * QTM_GET_SYMBOL(model, var) fetches the next symbol from the stated model * and puts it in var. * * If necessary, qtm_update_model() is called. */ #define QTM_GET_SYMBOL(model, var) do { \ range = ((H - L) & 0xFFFF) + 1; \ symf = ((((C - L + 1) * model.syms[0].cumfreq)-1) / range) & 0xFFFF; \ \ for (i = 1; i < model.entries; i++) { \ if (model.syms[i].cumfreq <= symf) break; \ } \ (var) = model.syms[i-1].sym; \ \ range = (H - L) + 1; \ symf = model.syms[0].cumfreq; \ H = L + ((model.syms[i-1].cumfreq * range) / symf) - 1; \ L = L + ((model.syms[i].cumfreq * range) / symf); \ \ do { model.syms[--i].cumfreq += 8; } while (i > 0); \ if (model.syms[0].cumfreq > 3800) qtm_update_model(&model); \ \ while (1) { \ if ((L & 0x8000) != (H & 0x8000)) { \ if ((L & 0x4000) && !(H & 0x4000)) { \ /* underflow case */ \ C ^= 0x4000; L &= 0x3FFF; H |= 0x4000; \ } \ else break; \ } \ L <<= 1; H = (H << 1) | 1; \ QTM_FILL_BUFFER; \ C = (C << 1) | QTM_PEEK_BITS(1); \ QTM_REMOVE_BITS(1); \ } \ } while (0) static void qtm_update_model(struct qtm_model *model) { struct qtm_modelsym tmp; int i, j; if (--model->shiftsleft) { for (i = model->entries - 1; i >= 0; i--) { /* -1, not -2; the 0 entry saves this */ model->syms[i].cumfreq >>= 1; if (model->syms[i].cumfreq <= model->syms[i+1].cumfreq) { model->syms[i].cumfreq = model->syms[i+1].cumfreq + 1; } } } else { model->shiftsleft = 50; for (i = 0; i < model->entries; i++) { /* no -1, want to include the 0 entry */ /* this converts cumfreqs into frequencies, then shifts right */ model->syms[i].cumfreq -= model->syms[i+1].cumfreq; model->syms[i].cumfreq++; /* avoid losing things entirely */ model->syms[i].cumfreq >>= 1; } /* now sort by frequencies, decreasing order -- this must be an * inplace selection sort, or a sort with the same (in)stability * characteristics */ for (i = 0; i < model->entries - 1; i++) { for (j = i + 1; j < model->entries; j++) { if (model->syms[i].cumfreq < model->syms[j].cumfreq) { tmp = model->syms[i]; model->syms[i] = model->syms[j]; model->syms[j] = tmp; } } } /* then convert frequencies back to cumfreq */ for (i = model->entries - 1; i >= 0; i--) { model->syms[i].cumfreq += model->syms[i+1].cumfreq; } } } /* Initialises a model to decode symbols from [start] to [start]+[len]-1 */ static void qtm_init_model(struct qtm_model *model, struct qtm_modelsym *syms, int start, int len) { int i; model->shiftsleft = 4; model->entries = len; model->syms = syms; for (i = 0; i <= len; i++) { syms[i].sym = start + i; /* actual symbol */ syms[i].cumfreq = len - i; /* current frequency of that symbol */ } } /*-------- main Quantum code --------*/ struct qtm_stream *qtm_init(int fd, int ofd, int window_bits, int input_buffer_size, struct cab_file *file, int (*read_cb)(struct cab_file *, unsigned char *, int)) { unsigned int window_size = 1 << window_bits; struct qtm_stream *qtm; unsigned offset; int i; /* Quantum supports window sizes of 2^10 (1Kb) through 2^21 (2Mb) */ /* tk: temporary fix: only process 32KB+ window sizes */ if (window_bits < 15 || window_bits > 21) return NULL; input_buffer_size = (input_buffer_size + 1) & -2; if (input_buffer_size < 2) return NULL; /* allocate decompression state */ if (!(qtm = cli_calloc(1, sizeof(struct qtm_stream)))) { return NULL; } for (i = 0, offset = 0; i < 42; i++) { qtm->position_base[i] = offset; qtm->extra_bits[i] = ((i < 2) ? 0 : (i - 2)) >> 1; offset += 1 << qtm->extra_bits[i]; } for (i = 0, offset = 0; i < 26; i++) { qtm->length_base[i] = offset; qtm->length_extra[i] = (i < 2 ? 0 : i - 2) >> 2; offset += 1 << qtm->length_extra[i]; } qtm->length_base[26] = 254; qtm->length_extra[26] = 0; /* allocate decompression window and input buffer */ qtm->window = cli_malloc((size_t) window_size); if (!qtm->window) { free(qtm); return NULL; } qtm->inbuf = cli_malloc((size_t) input_buffer_size); if (!qtm->inbuf) { free(qtm->window); free(qtm); return NULL; } /* initialise decompression state */ qtm->fd = fd; qtm->ofd = ofd; qtm->wflag = 1; qtm->inbuf_size = input_buffer_size; qtm->window_size = window_size; qtm->window_posn = 0; qtm->frame_start = 0; qtm->header_read = 0; qtm->error = CL_SUCCESS; qtm->i_ptr = qtm->i_end = &qtm->inbuf[0]; qtm->o_ptr = qtm->o_end = &qtm->window[0]; qtm->bits_left = 0; qtm->bit_buffer = 0; /* initialise arithmetic coding models * - model 4 depends on window size, ranges from 20 to 24 * - model 5 depends on window size, ranges from 20 to 36 * - model 6pos depends on window size, ranges from 20 to 42 */ i = window_bits * 2; qtm_init_model(&qtm->model0, &qtm->m0sym[0], 0, 64); qtm_init_model(&qtm->model1, &qtm->m1sym[0], 64, 64); qtm_init_model(&qtm->model2, &qtm->m2sym[0], 128, 64); qtm_init_model(&qtm->model3, &qtm->m3sym[0], 192, 64); qtm_init_model(&qtm->model4, &qtm->m4sym[0], 0, (i > 24) ? 24 : i); qtm_init_model(&qtm->model5, &qtm->m5sym[0], 0, (i > 36) ? 36 : i); qtm_init_model(&qtm->model6, &qtm->m6sym[0], 0, i); qtm_init_model(&qtm->model6len, &qtm->m6lsym[0], 0, 27); qtm_init_model(&qtm->model7, &qtm->m7sym[0], 0, 7); qtm->file = file; qtm->read_cb = read_cb; /* all ok */ return qtm; } int qtm_decompress(struct qtm_stream *qtm, off_t out_bytes) { unsigned int frame_start, frame_end, window_posn, match_offset, range; unsigned char *window, *i_ptr, *i_end, *runsrc, *rundest; int i, j, selector, extra, sym, match_length, ret; unsigned short H, L, C, symf; register unsigned int bit_buffer; register unsigned char bits_left; unsigned char bits_needed, bit_run; /* easy answers */ if (!qtm || (out_bytes < 0)) return CL_ENULLARG; if (qtm->error) return qtm->error; /* flush out any stored-up bytes before we begin */ i = qtm->o_end - qtm->o_ptr; if ((off_t) i > out_bytes) i = (int) out_bytes; if (i) { if (qtm->wflag && (ret = mspack_write(qtm->ofd, qtm->o_ptr, i, qtm->file)) != CL_SUCCESS) { return qtm->error = ret; } qtm->o_ptr += i; out_bytes -= i; } if (out_bytes == 0) return CL_SUCCESS; /* restore local state */ QTM_RESTORE_BITS; window = qtm->window; window_posn = qtm->window_posn; frame_start = qtm->frame_start; H = qtm->H; L = qtm->L; C = qtm->C; /* while we do not have enough decoded bytes in reserve: */ while ((qtm->o_end - qtm->o_ptr) < out_bytes) { /* read header if necessary. Initialises H, L and C */ if (!qtm->header_read) { H = 0xFFFF; L = 0; QTM_READ_BITS(C, 16); qtm->header_read = 1; } /* decode more, at most up to to frame boundary */ frame_end = window_posn + (out_bytes - (qtm->o_end - qtm->o_ptr)); if ((frame_start + QTM_FRAME_SIZE) < frame_end) { frame_end = frame_start + QTM_FRAME_SIZE; } while (window_posn < frame_end) { QTM_GET_SYMBOL(qtm->model7, selector); if (selector < 4) { struct qtm_model *mdl = (selector == 0) ? &qtm->model0 : ((selector == 1) ? &qtm->model1 : ((selector == 2) ? &qtm->model2 : &qtm->model3)); QTM_GET_SYMBOL((*mdl), sym); window[window_posn++] = sym; } else { switch (selector) { case 4: /* selector 4 = fixed length match (3 bytes) */ QTM_GET_SYMBOL(qtm->model4, sym); QTM_READ_BITS(extra, qtm->extra_bits[sym]); match_offset = qtm->position_base[sym] + extra + 1; match_length = 3; break; case 5: /* selector 5 = fixed length match (4 bytes) */ QTM_GET_SYMBOL(qtm->model5, sym); QTM_READ_BITS(extra, qtm->extra_bits[sym]); match_offset = qtm->position_base[sym] + extra + 1; match_length = 4; break; case 6: /* selector 6 = variable length match */ QTM_GET_SYMBOL(qtm->model6len, sym); QTM_READ_BITS(extra, qtm->length_extra[sym]); match_length = qtm->length_base[sym] + extra + 5; QTM_GET_SYMBOL(qtm->model6, sym); QTM_READ_BITS(extra, qtm->extra_bits[sym]); match_offset = qtm->position_base[sym] + extra + 1; break; default: /* should be impossible, model7 can only return 0-6 */ return qtm->error = CL_EFORMAT; } if (window_posn + match_length > qtm->window_size) { cli_dbgmsg("qtm_decompress: match ran over window wrap\n"); return qtm->error = CL_EFORMAT; } rundest = &window[window_posn]; i = match_length; /* does match offset wrap the window? */ if (match_offset > window_posn) { /* j = length from match offset to end of window */ j = match_offset - window_posn; if (j > (int) qtm->window_size) { cli_dbgmsg("qtm_decompress: match offset beyond window boundaries\n"); return qtm->error = CL_EFORMAT; } runsrc = &window[qtm->window_size - j]; if (j < i) { /* if match goes over the window edge, do two copy runs */ i -= j; while (j-- > 0) *rundest++ = *runsrc++; runsrc = window; } while (i-- > 0) *rundest++ = *runsrc++; } else { runsrc = rundest - match_offset; if(i > (int) (qtm->window_size - window_posn)) i = qtm->window_size - window_posn; while (i-- > 0) *rundest++ = *runsrc++; } window_posn += match_length; } } /* while (window_posn < frame_end) */ qtm->o_end = &window[window_posn]; /* another frame completed? */ if ((window_posn - frame_start) >= QTM_FRAME_SIZE) { if ((window_posn - frame_start) != QTM_FRAME_SIZE) { cli_dbgmsg("qtm_decompress: overshot frame alignment\n"); return qtm->error = CL_EFORMAT; } /* re-align input */ if (bits_left & 7) QTM_REMOVE_BITS(bits_left & 7); do { QTM_READ_BITS(i, 8); } while (i != 0xFF); qtm->header_read = 0; /* window wrap? */ if (window_posn == qtm->window_size) { /* flush all currently stored data */ i = (qtm->o_end - qtm->o_ptr); if(i <= 0) break; if (qtm->wflag && (ret = mspack_write(qtm->ofd, qtm->o_ptr, i, qtm->file)) != CL_SUCCESS) { return qtm->error = ret; } out_bytes -= i; qtm->o_ptr = &window[0]; qtm->o_end = &window[0]; window_posn = 0; } frame_start = window_posn; } } /* while (more bytes needed) */ if (out_bytes > 0) { i = (int) out_bytes; if (qtm->wflag && (ret = mspack_write(qtm->ofd, qtm->o_ptr, i, qtm->file)) != CL_SUCCESS) { return qtm->error = ret; } qtm->o_ptr += i; } /* store local state */ QTM_STORE_BITS; qtm->window_posn = window_posn; qtm->frame_start = frame_start; qtm->H = H; qtm->L = L; qtm->C = C; return CL_SUCCESS; } void qtm_free(struct qtm_stream *qtm) { if (qtm) { free(qtm->window); free(qtm->inbuf); free(qtm); } }