path: root/parts/documentation/protocols/chm/decompress.cpp

/*  Most of this file is taken from:
    cabextract 0.5 - a program to extract Microsoft Cabinet files
    (C) 2000-2001 Stuart Caie <kyzer@4u.net>

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    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
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public License
    along with this library; see the file COPYING.LIB.  If not, write to
    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
    Boston, MA 02110-1301, USA.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "decompress.h"

int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table);
int lzx_read_lens(UBYTE *lens, ULONG first, ULONG last, lzx_bits *lb);


/*--------------------------------------------------------------------------*/
/* our archiver information / state */

/* LZX stuff */

/* some constants defined by the LZX specification */
#define LZX_MIN_MATCH                (2)
#define LZX_MAX_MATCH                (257)
#define LZX_NUM_CHARS                (256)
#define LZX_BLOCKTYPE_INVALID        (0)   /* also blocktypes 4-7 invalid */
#define LZX_BLOCKTYPE_VERBATIM       (1)
#define LZX_BLOCKTYPE_ALIGNED        (2)
#define LZX_BLOCKTYPE_UNCOMPRESSED   (3)
#define LZX_PRETREE_NUM_ELEMENTS     (20)
#define LZX_ALIGNED_NUM_ELEMENTS     (8)   /* aligned offset tree #elements */
#define LZX_NUM_PRIMARY_LENGTHS      (7)   /* this one missing from spec! */
#define LZX_NUM_SECONDARY_LENGTHS    (249) /* length tree #elements */

/* LZX huffman defines: tweak tablebits as desired */
#define LZX_PRETREE_MAXSYMBOLS  (LZX_PRETREE_NUM_ELEMENTS)
#define LZX_PRETREE_TABLEBITS   (6)
#define LZX_MAINTREE_MAXSYMBOLS (LZX_NUM_CHARS + 50*8)
#define LZX_MAINTREE_TABLEBITS  (12)
#define LZX_LENGTH_MAXSYMBOLS   (LZX_NUM_SECONDARY_LENGTHS+1)
#define LZX_LENGTH_TABLEBITS    (12)
#define LZX_ALIGNED_MAXSYMBOLS  (LZX_ALIGNED_NUM_ELEMENTS)
#define LZX_ALIGNED_TABLEBITS   (7)

#define LZX_LENTABLE_SAFETY (64) /* we allow length table decoding overruns */

#define LZX_DECLARE_TABLE(tbl) \
  UWORD tbl##_table[(1<<LZX_##tbl##_TABLEBITS) + (LZX_##tbl##_MAXSYMBOLS<<1)];\
  UBYTE tbl##_len  [LZX_##tbl##_MAXSYMBOLS + LZX_LENTABLE_SAFETY]

struct LZXstate
{
	UBYTE *window;		   /* the actual decoding window              */
	ULONG window_size;	   /* window size (32Kb through 2Mb)          */
	ULONG actual_size;	   /* window size when it was first allocated */
	ULONG window_posn;	   /* current offset within the window        */
	ULONG R0, R1, R2;	   /* for the LRU offset system               */
	UWORD main_elements;   /* number of main tree elements            */
	int   header_read;	   /* have we started decoding at all yet?    */
	UWORD block_type;	   /* type of this block                      */
	ULONG block_length;	   /* uncompressed length of this block       */
	ULONG block_remaining; /* uncompressed bytes still left to decode */
	ULONG frames_read;	   /* the number of CFDATA blocks processed   */
	LONG  intel_filesize;  /* magic header value used for transform   */
	LONG  intel_curpos;	   /* current offset in transform space       */
	int   intel_started;   /* have we seen any translatable data yet? */

	LZX_DECLARE_TABLE(PRETREE);
	LZX_DECLARE_TABLE(MAINTREE);
	LZX_DECLARE_TABLE(LENGTH);
	LZX_DECLARE_TABLE(ALIGNED);
};


/* generic stuff */
#define CAB(x) (decomp_state.x)
#define LZX(x) (decomp_state.lzx.x)
#define DECR_OK           (0)
#define DECR_DATAFORMAT   (1)
#define DECR_ILLEGALDATA  (2)
#define DECR_NOMEMORY     (3)
#define DECR_CHECKSUM     (4)
#define DECR_INPUT        (5)
#define DECR_OUTPUT       (6)

struct
{
    struct LZXstate lzx;
} decomp_state;


/* LZX decruncher */

/* Microsoft's LZX document and their implementation of the
 * com.ms.util.cab Java package do not concur.
 *
 * In the LZX document, there is a table showing the correlation between
 * window size and the number of position slots. It states that the 1MB
 * window = 40 slots and the 2MB window = 42 slots. In the implementation,
 * 1MB = 42 slots, 2MB = 50 slots. The actual calculation is 'find the
 * first slot whose position base is equal to or more than the required
 * window size'. This would explain why other tables in the document refer
 * to 50 slots rather than 42.
 *
 * The constant NUM_PRIMARY_LENGTHS used in the decompression pseudocode
 * is not defined in the specification.
 *
 * The LZX document does not state the uncompressed block has an
 * uncompressed length field. Where does this length field come from, so
 * we can know how large the block is? The implementation has it as the 24
 * bits following after the 3 blocktype bits, before the tqalignment
 * padding.
 *
 * The LZX document states that aligned offset blocks have their aligned
 * offset huffman tree AFTER the main and length trees. The implementation
 * suggests that the aligned offset tree is BEFORE the main and length
 * trees.
 *
 * The LZX document decoding algorithm states that, in an aligned offset
 * block, if an extra_bits value is 1, 2 or 3, then that number of bits
 * should be read and the result added to the match offset. This is
 * correct for 1 and 2, but not 3, where just a huffman symbol (using the
 * aligned tree) should be read.
 *
 * Regarding the E8 preprocessing, the LZX document states 'No translation
 * may be performed on the last 6 bytes of the input block'. This is
 * correct.  However, the pseudocode provided checks for the *E8 leader*
 * up to the last 6 bytes. If the leader appears between -10 and -7 bytes
 * from the end, this would cause the next four bytes to be modified, at
 * least one of which would be in the last 6 bytes, which is not allowed
 * according to the spec.
 *
 * The specification states that the huffman trees must always contain at
 * least one element. However, many CAB files contain blocks where the
 * length tree is completely empty (because there are no matches), and
 * this is expected to succeed.
 */


/* LZX uses what it calls 'position slots' to represent match offsets.
 * What this means is that a small 'position slot' number and a small
 * offset from that slot are encoded instead of one large offset for
 * every match.
 * - position_base is an index to the position slot bases
 * - extra_bits states how many bits of offset-from-base data is needed.
 */
static ULONG position_base[51];
static UBYTE extra_bits[51];


int LZXinit(int window) {
	ULONG wndsize = 1 << window;
	int i, j, posn_slots;

	/* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */
	/* if a previously allocated window is big enough, keep it     */
	if (window < 15 || window > 21)	return DECR_DATAFORMAT;
	if (LZX(actual_size) < wndsize)
	{
		if (LZX(window)) free(LZX(window));
		LZX(window) = NULL;
	}
	if (!LZX(window))
	{
		if (!(LZX(window) = (UBYTE*)malloc(wndsize))) return DECR_NOMEMORY;
		LZX(actual_size) = wndsize;
	}
	LZX(window_size) = wndsize;

	/* initialise static tables */
	for (i=0, j=0; i <= 49; i += 2)
	{
		extra_bits[i] = extra_bits[i+1] = j; /* 0,0,0,0,1,1,2,2,3,3... */
		if ((i != 0) && (j < 17)) j++; /* 0,0,1,2,3,4...15,16,17,17,17,17... */
	}
	for (i=0, j=0; i <= 50; i++)
	{
		position_base[i] = j; /* 0,1,2,3,4,6,8,12,16,24,32,... */
		j += 1 << extra_bits[i]; /* 1,1,1,1,2,2,4,4,8,8,16,16,32,32,... */
	}

	/* calculate required position slots */
	if (window == 20) posn_slots = 42;
	else if (window == 21) posn_slots = 50;
	else posn_slots	= window << 1;

	/*posn_slots=i=0; while (i < wndsize) i += 1 << extra_bits[posn_slots++]; */


	LZX(R0)  =  LZX(R1)  = LZX(R2) = 1;
	LZX(main_elements)   = LZX_NUM_CHARS + (posn_slots << 3);
	LZX(header_read)     = 0;
	LZX(frames_read)     = 0;
	LZX(block_remaining) = 0;
	LZX(block_type)      = LZX_BLOCKTYPE_INVALID;
	LZX(intel_curpos)    = 0;
	LZX(intel_started)   = 0;
	LZX(window_posn)     = 0;

	/* 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;

	return DECR_OK;
}


/* Bitstream reading macros:
 *
 * INIT_BITSTREAM    should be used first to set up the system
 * READ_BITS(var,n)  takes N bits from the buffer and puts them in var
 *
 * ENSURE_BITS(n)    ensures there are at least N bits in the bit buffer
 * PEEK_BITS(n)      extracts (without removing) N bits from the bit buffer
 * 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 tqmask any bits.
 * So we have to know the bit width of the bitbuffer variable. This is
 * sizeof(ULONG) * 8, also defined as ULONG_BITS
 */

/* number of bits in ULONG. Note: This must be at multiple of 16, and at
 * least 32 for the bitbuffer code to work (ie, it must be able to ensure
 * up to 17 bits - that's adding 16 bits when there's one bit left, or
 * adding 32 bits when there are no bits left. The code should work fine
 * for machines where ULONG >= 32 bits.
 */
#define ULONG_BITS (sizeof(ULONG)<<3)

#define INIT_BITSTREAM do { bitsleft = 0; bitbuf = 0; } while (0)

#define ENSURE_BITS(n)							\
  while (bitsleft < (n)) {						\
    bitbuf |= ((inpos[1]<<8)|inpos[0]) << (ULONG_BITS-16 - bitsleft);	\
    bitsleft += 16; inpos+=2;						\
  }

#define PEEK_BITS(n)   (bitbuf >> (ULONG_BITS - (n)))
#define REMOVE_BITS(n) ((bitbuf <<= (n)), (bitsleft -= (n)))

#define READ_BITS(v,n) do {						\
  ENSURE_BITS(n);							\
  (v) = PEEK_BITS(n);							\
  REMOVE_BITS(n);							\
} while (0)


/* Huffman macros */

#define TABLEBITS(tbl)   (LZX_##tbl##_TABLEBITS)
#define MAXSYMBOLS(tbl)  (LZX_##tbl##_MAXSYMBOLS)
#define SYMTABLE(tbl)    (LZX(tbl##_table))
#define LENTABLE(tbl)    (LZX(tbl##_len))

/* BUILD_TABLE(tablename) builds a huffman lookup table from code lengths.
 * In reality, it just calls make_decode_table() with the appropriate
 * values - they're all fixed by some #defines anyway, so there's no point
 * writing each call out in full by hand.
 */
#define BUILD_TABLE(tbl)						\
  if (make_decode_table(						\
    MAXSYMBOLS(tbl), TABLEBITS(tbl), LENTABLE(tbl), SYMTABLE(tbl)	\
  )) { return DECR_ILLEGALDATA; }


/* READ_HUFFSYM(tablename, var) decodes one huffman symbol from the
 * bitstream using the stated table and puts it in var.
 */
#define READ_HUFFSYM(tbl,var) do {					\
  ENSURE_BITS(16);							\
  hufftbl = SYMTABLE(tbl);						\
  if ((i = hufftbl[PEEK_BITS(TABLEBITS(tbl))]) >= MAXSYMBOLS(tbl)) {	\
    j = 1 << (ULONG_BITS - TABLEBITS(tbl));				\
    do {								\
      j >>= 1; i <<= 1; i |= (bitbuf & j) ? 1 : 0;			\
      if (!j) { return DECR_ILLEGALDATA; }	                        \
    } while ((i = hufftbl[i]) >= MAXSYMBOLS(tbl));			\
  }									\
  j = LENTABLE(tbl)[(var) = i];						\
  REMOVE_BITS(j);							\
} while (0)


/* 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 READ_LENGTHS(tbl,first,last) do { \
  lb.bb = bitbuf; lb.bl = bitsleft; lb.ip = inpos; \
  if (lzx_read_lens(LENTABLE(tbl),(first),(last),&lb)) { \
    return DECR_ILLEGALDATA; \
  } \
  bitbuf = lb.bb; bitsleft = lb.bl; inpos = lb.ip; \
} while (0)


/* 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.
 *
 * 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
 */

int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table) {
	register UWORD sym;
	register ULONG leaf;
	register UBYTE bit_num = 1;
	ULONG fill;
	ULONG pos         = 0; /* the current position in the decode table */
	ULONG table_tqmask  = 1 << nbits;
	ULONG bit_tqmask    = table_tqmask >> 1; /* don't do 0 length codes */
	ULONG next_symbol = bit_tqmask; /* base of allocation for long codes */

	/* fill entries for codes short enough for a direct mapping */
	while (bit_num <= nbits)
	{
		for (sym = 0; sym < nsyms; sym++)
		{
			if (length[sym] == bit_num)
			{
				leaf = pos;

				if ((pos += bit_tqmask) > table_tqmask)	return 1; /* table overrun */

				/* fill all possible lookups of this symbol with the symbol itself */
				fill = bit_tqmask;
				while (fill-- > 0) table[leaf++] = sym;
			}
		}
		bit_tqmask >>= 1;
		bit_num++;
	}

	/* if there are any codes longer than nbits */
	if (pos != table_tqmask)
	{
		/* clear the remainder of the table */
		for (sym = pos; sym < table_tqmask; sym++) table[sym] = 0;

		/* give ourselves room for codes to grow by up to 16 more bits */
		pos <<= 16;
		table_tqmask <<= 16;
		bit_tqmask = 1 << 15;

		while (bit_num <= 16)
		{
			for (sym = 0; sym < nsyms; sym++)
			{
				if (length[sym] == bit_num)
				{
					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] == 0)
						{
							table[(next_symbol << 1)] = 0;
							table[(next_symbol << 1) + 1] = 0;
							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_tqmask) > table_tqmask)	return 1; /* table overflow */
				}
			}
			bit_tqmask >>= 1;
			bit_num++;
		}
	}

	/* full table? */
	if (pos == table_tqmask) 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;
}

int lzx_read_lens(UBYTE *lens, ULONG first, ULONG last, lzx_bits *lb) {
	ULONG i,j, x,y;
	int z;

	register ULONG bitbuf = lb->bb;
	register int bitsleft = lb->bl;
	UBYTE *inpos = lb->ip;
	UWORD *hufftbl;

	for (x = 0; x < 20; x++)
	{
		READ_BITS(y, 4);
		LENTABLE(PRETREE)[x] = y;
	}
	BUILD_TABLE(PRETREE);

	for (x = first; x < last;)
	{
		READ_HUFFSYM(PRETREE, z);
		if (z == 17)
		{
			READ_BITS(y, 4); y += 4;
			while (y--)	lens[x++] = 0;
		}
		else if (z == 18)
		{
			READ_BITS(y, 5); y += 20;
			while (y--)	lens[x++] = 0;
		}
		else if (z == 19)
		{
			READ_BITS(y, 1); y += 4;
			READ_HUFFSYM(PRETREE, z);
			z = lens[x] - z; if (z < 0)	z += 17;
			while (y--)	lens[x++] = z;
		}
		else
		{
			z = lens[x] - z; if (z < 0)	z += 17;
			lens[x++] = z;
		}
	}

	lb->bb = bitbuf;
	lb->bl = bitsleft;
	lb->ip = inpos;
	return 0;
}

int LZXdecompress(UBYTE* inpos, int inlen, UBYTE* outpos, int outlen) {
	UBYTE *endinp = inpos + inlen;
	UBYTE *window = LZX(window);
	UBYTE *runsrc, *rundest;
	UWORD *hufftbl;	/* used in READ_HUFFSYM macro as chosen decoding table */

	ULONG window_posn = LZX(window_posn);
	ULONG window_size = LZX(window_size);
	ULONG R0 = LZX(R0);
	ULONG R1 = LZX(R1);
	ULONG R2 = LZX(R2);

	register ULONG bitbuf;
	register int bitsleft;
	ULONG match_offset, i,j,k; /* ijk used in READ_HUFFSYM macro */
	lzx_bits lb;	/* used in READ_LENGTHS macro */

	int togo = outlen, this_run, main_element, aligned_bits;
	int match_length, length_footer, extra, verbatim_bits;

	INIT_BITSTREAM;

	/* read header if necessary */
	if (!LZX(header_read))
	{
		i = j = 0;
		READ_BITS(k, 1); if (k)
		{
			READ_BITS(i,16); READ_BITS(j,16);
		}
		LZX(intel_filesize) = (i << 16) | j; /* or 0 if not encoded */
		LZX(header_read) = 1;
	}

	/* main decoding loop */
	while (togo > 0)
	{
		/* last block finished, new block expected */
		if (LZX(block_remaining) == 0)
		{
			if (LZX(block_type) == LZX_BLOCKTYPE_UNCOMPRESSED)
			{
				if (LZX(block_length) & 1) inpos++;	/* realign bitstream to word */
				INIT_BITSTREAM;
			}

			READ_BITS(LZX(block_type), 3);
			READ_BITS(i, 16);
			READ_BITS(j, 8);
			LZX(block_remaining) = LZX(block_length) = (i << 8) | j;

			switch (LZX(block_type))
			{
				case LZX_BLOCKTYPE_ALIGNED:
					for (i = 0; i < 8; i++)
					{
						READ_BITS(j, 3); LENTABLE(ALIGNED)[i] = j;
					}
					BUILD_TABLE(ALIGNED);
					/* rest of aligned header is same as verbatim */

				case LZX_BLOCKTYPE_VERBATIM:
					READ_LENGTHS(MAINTREE, 0, 256);
					READ_LENGTHS(MAINTREE, 256, LZX(main_elements));
					BUILD_TABLE(MAINTREE);
					if (LENTABLE(MAINTREE)[0xE8] != 0) LZX(intel_started) = 1;

					READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS);
					BUILD_TABLE(LENGTH);
					break;

				case LZX_BLOCKTYPE_UNCOMPRESSED:
					LZX(intel_started) = 1;	/* because we can't assume otherwise */
					ENSURE_BITS(16); /* get up to 16 pad bits into the buffer */
					if (bitsleft > 16) inpos -= 2; /* and align the bitstream! */
					R0 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
					R1 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
					R2 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
					break;

				default:
					return DECR_ILLEGALDATA;
			}
		}

		/* buffer exhaustion check */
		if (inpos > endinp)
		{
			/* it's possible to have a file where the next run is less than
			 * 16 bits in size. In this case, the READ_HUFFSYM() macro used
			 * in building the tables will exhaust the buffer, so we should
			 * allow for this, but not allow those accidentally read bits to
			 * be used (so we check that there are at least 16 bits
			 * remaining - in this boundary case they aren't really part of
			 * the compressed data)
			 */
			if (inpos > (endinp+2) || bitsleft < 16) return DECR_ILLEGALDATA;
		}

		while ((this_run = LZX(block_remaining)) > 0 && togo > 0)
		{
			if (this_run > togo) this_run = togo;
			togo -= this_run;
			LZX(block_remaining) -= this_run;

			/* apply 2^x-1 tqmask */
			window_posn &= window_size - 1;
			/* runs can't straddle the window wraparound */
			if ((window_posn + this_run) > window_size)
				return DECR_DATAFORMAT;

			switch (LZX(block_type))
			{
				
				case LZX_BLOCKTYPE_VERBATIM:
					while (this_run > 0)
					{
						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;

							match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
							if (match_length == LZX_NUM_PRIMARY_LENGTHS)
							{
								READ_HUFFSYM(LENGTH, length_footer);
								match_length += length_footer;
							}
							match_length += LZX_MIN_MATCH;

							match_offset = main_element >> 3;

							if (match_offset > 2)
							{
								/* not repeated offset */
								if (match_offset != 3)
								{
									extra = extra_bits[match_offset];
									READ_BITS(verbatim_bits, extra);
									match_offset = position_base[match_offset] - 2 + verbatim_bits;
								}
								else
								{
									match_offset = 1;
								}

								/* update repeated offset LRU queue */
								R2 = R1; R1 = R0; R0 = match_offset;
							}
							else if (match_offset == 0)
							{
								match_offset = R0;
							}
							else if (match_offset == 1)
							{
								match_offset = R1;
								R1 = R0; R0 = match_offset;
							}
							else /* match_offset == 2 */
							{
								match_offset = R2;
								R2 = R0; R0 = match_offset;
							}

							rundest = window + window_posn;
							runsrc  = rundest - match_offset;
							window_posn += match_length;
							this_run -= match_length;

							/* copy any wrapped around source data */
							while ((runsrc < window) && (match_length-- > 0))
							{
								*rundest++ = *(runsrc + window_size); runsrc++;
							}
							/* copy match data - no worries about destination wraps */
							while (match_length-- > 0) *rundest++ = *runsrc++;

						}
					}
					break;

				case LZX_BLOCKTYPE_ALIGNED:
					while (this_run > 0)
					{
						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;

							match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
							if (match_length == LZX_NUM_PRIMARY_LENGTHS)
							{
								READ_HUFFSYM(LENGTH, length_footer);
								match_length += length_footer;
							}
							match_length += LZX_MIN_MATCH;

							match_offset = main_element >> 3;

							if (match_offset > 2)
							{
								/* not repeated offset */
								extra = extra_bits[match_offset];
								match_offset = position_base[match_offset] - 2;
								if (extra > 3)
								{
									/* verbatim and aligned bits */
									extra -= 3;
									READ_BITS(verbatim_bits, extra);
									match_offset += (verbatim_bits << 3);
									READ_HUFFSYM(ALIGNED, aligned_bits);
									match_offset += aligned_bits;
								}
								else if (extra == 3)
								{
									/* aligned bits only */
									READ_HUFFSYM(ALIGNED, aligned_bits);
									match_offset += aligned_bits;
								}
								else if (extra > 0)
								{ /* extra==1, extra==2 */
									/* verbatim bits only */
									READ_BITS(verbatim_bits, extra);
									match_offset += verbatim_bits;
								}
								else /* extra == 0 */
								{
									/* ??? */
									match_offset = 1;
								}

								/* update repeated offset LRU queue */
								R2 = R1; R1 = R0; R0 = match_offset;
							}
							else if (match_offset == 0)
							{
								match_offset = R0;
							}
							else if (match_offset == 1)
							{
								match_offset = R1;
								R1 = R0; R0 = match_offset;
							}
							else /* match_offset == 2 */
							{
								match_offset = R2;
								R2 = R0; R0 = match_offset;
							}

							rundest = window + window_posn;
							runsrc  = rundest - match_offset;
							window_posn += match_length;
							this_run -= match_length;

							/* copy any wrapped around source data */
							while ((runsrc < window) && (match_length-- > 0))
							{
								*rundest++ = *(runsrc + window_size); runsrc++;
							}
							/* copy match data - no worries about destination wraps */
							while (match_length-- > 0) *rundest++ = *runsrc++;

						}
					}
					break;

				case LZX_BLOCKTYPE_UNCOMPRESSED:
					if ((inpos + this_run) > endinp) return DECR_ILLEGALDATA;
					memcpy(window + window_posn, inpos, (size_t) this_run);
					inpos += this_run; window_posn += this_run;
					break;

				default:
					return DECR_ILLEGALDATA; /* might as well */
			}

		}
	}

	if (togo != 0) return DECR_ILLEGALDATA;
	memcpy(outpos, window + ((!window_posn) ? window_size : window_posn) -
		   outlen, (size_t) outlen);

	LZX(window_posn) = window_posn;
	LZX(R0) = R0;
	LZX(R1) = R1;
	LZX(R2) = R2;

	/* intel E8 decoding */
	if ((LZX(frames_read)++ < 32768) && LZX(intel_filesize) != 0)
	{
		if (outlen <= 6 || !LZX(intel_started))
		{
			LZX(intel_curpos) += outlen;
		}
		else
		{
			UBYTE *data    = outpos;
			UBYTE *dataend = data + outlen - 10;
			LONG curpos    = LZX(intel_curpos);
			LONG filesize  = LZX(intel_filesize);
			LONG abs_off, rel_off;

			LZX(intel_curpos) = curpos + outlen;

			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] = (UBYTE) rel_off;
					data[1] = (UBYTE) (rel_off >> 8);
					data[2] = (UBYTE) (rel_off >> 16);
					data[3] = (UBYTE) (rel_off >> 24);
				}
				data += 4;
				curpos += 5;
			}
		}
	}
	return DECR_OK;
}