~ubuntu-branches/ubuntu/saucy/clamav/saucy-backports

/*
 * This file includes code from libmspack adapted for libclamav by
 * tkojm@clamav.net and draynor@sourcefire.com
 *
 * 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 <stdio.h>
#include <string.h>

#include <openssl/ssl.h>
#include <openssl/err.h>
#include "libclamav/crypto.h"

#include "others.h"
#include "clamav.h"
#include "mspack.h"

#if HAVE_LIMITS_H
# include <limits.h>
#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->file, zip->inbuf, (int)zip->inbuf_size);
  if (nread < 0) {
    if (zip->file->error == CL_BREAK) {
      if (nread == zip->last) {
        cli_dbgmsg("mszip_read_input: Two consecutive CL_BREAKs reached.\n");
        return CL_BREAK;
      }
      // Need short circuit to ensure scanning small files
      cli_dbgmsg("mszip_read_input: First CL_BREAK reached.\n");
      zip->i_ptr = zip->i_end;
      zip->last = nread;
      return CL_SUCCESS;
    }
    else
      return zip->error = CL_EFORMAT;
  }

  zip->last = nread;
  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 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)))) {
      cli_errmsg("mszip_stream: Unable to allocate zip buffer\n");
    return NULL;
  }

  /* allocate input buffer */
  zip->inbuf  = cli_malloc((size_t) input_buffer_size);
  if (!zip->inbuf) {
      cli_errmsg("mszip_stream: Unable to allocate input buffer\n");
    free(zip);
    return NULL;
  }

  /* initialise decompression state */
  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, uint32_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) 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) && ((int) out_bytes >= 0)) 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->file, &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 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->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, uint32_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, warned=0;
  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) 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) && ((int) out_bytes >= 0)) 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;
  cli_dbgmsg("lzx_decompress: end frame = %u\n", end_frame);

  while (lzx->frame < end_frame) {
    cli_dbgmsg("lzx_decompress: current frame = %u\n", lzx->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) {
        /* this is a file format error, but we need to extract what we can and scan that */
        cli_dbgmsg("lzx_decompress: %d bytes remaining at reset interval\n", lzx->block_remaining);
        if (!warned) {
          cli_dbgmsg("Detected an invalid reset interval during decompression.\n");
          warned++;
        }
        if (!lzx->header_read) {
          /* cannot continue if no header at all */
          return lzx->error = CL_EFORMAT;
        }
      } else {
        /* 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->file, &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;
  }

  if (nread == 0) {
    if (qtm->input_end) {
      cli_dbgmsg("qtm_read_input: out of input bytes\n");
      return qtm->error = CL_EREAD;
    }
    else {
      nread = 2;
      qtm->inbuf[0] = qtm->inbuf[1] = 0;
      qtm->input_end = 1;
    }
  }

  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 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) {
      cli_errmsg("qtm_init: Unable to allocate decompression window\n");
    free(qtm);
    return NULL;
  }

  qtm->inbuf  = cli_malloc((size_t) input_buffer_size);
  if (!qtm->inbuf) {
      cli_errmsg("qtm_init: Unable to allocate input buffer\n");
    free(qtm->window);
    free(qtm);
    return NULL;
  }

  /* initialise decompression state */
  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, uint32_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) 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) && ((int) out_bytes >= 0)) 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;
    }
    if (frame_end < window_posn) {
	cli_dbgmsg("qtm_decompress: window position beyond end of frame\n");
	return qtm->error = CL_EFORMAT;
    }

    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);
  }
}