xref: /freebsd/contrib/libarchive/libarchive/archive_read_support_format_cab.c (revision 185becb1e1bd2657c156f78aeb52edac05ba5fb5)

/*-
 * Copyright (c) 2010-2012 Michihiro NAKAJIMA
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "archive_platform.h"

#ifdef HAVE_ERRNO_H
#include <errno.h>
#endif
#ifdef HAVE_LIMITS_H
#include <limits.h>
#endif
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#ifdef HAVE_STRING_H
#include <string.h>
#endif
#ifdef HAVE_ZLIB_H
#include <zlib.h>
#endif

#include "archive.h"
#include "archive_entry.h"
#include "archive_entry_locale.h"
#include "archive_private.h"
#include "archive_read_private.h"
#include "archive_endian.h"


/*
 * Huffman coding.
 *
 * Array representation of a Huffman tree for codes of up to 16 bit lengths.
 * Lookups are performed through a direct, expanded lookup table.
 *
 * An expanded table has as many elements as needed to cover all possible
 * indices formable with bit patterns of given lookup_bits length.
 *
 * If less codes exist, these span multiple entries for all possible
 * combinations of following bits.
 *
 * Example of a Huffman tree with len_size = 3, lookup_bits = 2:
 *
 * Symbol | Code
 * -------+-----
 *      A | 0b0
 *      B | 0b10
 *      C | 0b11
 *
 * The bit sequences 0b00 and 0b01 are rightfully not covered by a code,
 * since code 0b0 already maps to symbol A. The table will contain two
 * entries for symbol A instead:
 *
 *  idx | tbl[idx]
 * -----+---------
 * 0b00 |        A
 * 0b01 |        A
 * 0b10 |        B
 * 0b11 |        C
 *
 * By using lookup_bits bits as a lookup, it becomes apparent that 0b00 and
 * 0b01 point to a symbol which actually has the code 0b0. A user of this
 * data structure must check the code bit length of a retrieved symbol after
 * the lookup to properly advance the bit stream:
 *
 * idx | bitlen[idx]
 * ----+------------
 *   A |           1
 *   B |           2
 *   C |           2
 *
 * Thus, a proper code sequence would be:
 *
 * symbol = tbl[read_bits(lookup_bits)]
 * consume_bits(bitlen[symbol])
 */
struct huffman {
	/*
	 * Amount of symbols.
	 *
	 * This implementation keeps track of unused symbols as well,
	 * thus symbols start with 0x0000 up to given symbol amount:
	 * [0..symbol_count)
	 *
	 * Used to construct tbl.
	 */
	uint16_t	 symbol_count;
	/*
	 * Frequency of code bit lengths.
	 *
	 * Represents the amount of occurrences of given bit lengths.
	 * Index 0 is used for "empty" codes (aka unused symbols),
	 * otherwise index represents the bit length
	 * (index 1 is bit length 1 and so on).
	 *
	 * Used to construct tbl.
	 */
	uint16_t	 freq[17];
	/* Map of symbols to their code bit lengths. */
	uint8_t		*bitlen;
	/* Amount of bits to use for lookup (<= tbl_bits). */
	uint8_t		 lookup_bits;
	/*
	 * Code bit length used for allocation (<= 16).
	 *
	 * Used to construct tbl.
	 */
	uint8_t		 tbl_bits;
	/* Direct, expanded lookup table. */
	uint16_t	*tbl;
};

/*
 * Bit stream reader.
 */
struct lzx_br {
#define CACHE_TYPE		uint64_t
#define CACHE_BITS		(8 * sizeof(CACHE_TYPE))
	/* Cache buffer. */
	CACHE_TYPE	 cache_buffer;
	/* Indicates how many bits avail in cache_buffer. */
	size_t		 cache_avail;
	uint8_t		 odd;
	int		 have_odd;
};

struct lzx_pos_tbl {
	uint32_t	 base;
	uint8_t		 footer_bits;
};

struct lzx_dec {
	/* Decoding status. */
	int     		 state;
#define ST_RD_TRANSLATION	0
#define ST_RD_TRANSLATION_SIZE	1
#define ST_RD_BLOCK_TYPE	2
#define ST_RD_BLOCK_SIZE	3
#define ST_RD_ALIGNMENT		4
#define ST_RD_R0		5
#define ST_RD_R1		6
#define ST_RD_R2		7
#define ST_COPY_UNCOMP1		8
#define ST_COPY_UNCOMP2		9
#define ST_RD_ALIGNED_OFFSET	10
#define ST_RD_VERBATIM		11
#define ST_RD_PRE_MAIN_TREE_256	12
#define ST_MAIN_TREE_256	13
#define ST_RD_PRE_MAIN_TREE_REM	14
#define ST_MAIN_TREE_REM	15
#define ST_RD_PRE_LENGTH_TREE	16
#define ST_LENGTH_TREE		17
#define ST_MAIN			18
#define ST_LENGTH		19
#define ST_OFFSET		20
#define ST_REAL_POS		21
#define ST_COPY			22

	/*
	 * Window to see last decoded data, from 32 KiB to 2 MiB.
	 */
	size_t			 w_size;
	size_t			 w_mask;
	/* Window buffer, which is a loop buffer. */
	uint8_t			*w_buff;
	/* The insert position to the window. */
	size_t			 w_pos;
	/* The position where we can copy decoded code from the window. */
	size_t			 copy_pos;
	/* The length how many bytes we can copy decoded code from
	 * the window. */
	size_t			 copy_len;
	/* Translation reversal for x86 processor CALL byte sequence(E8).
	 * This is used for LZX only. */
	int32_t			 translation_size;
	int			 translation;
	uint8_t			 block_type;
#define VERBATIM_BLOCK		1
#define ALIGNED_OFFSET_BLOCK	2
#define UNCOMPRESSED_BLOCK	3
	size_t			 block_size;
	size_t			 block_bytes_avail;
	/* Repeated offset. */
	size_t			 r0, r1, r2;
	uint8_t			 rbytes[4];
	size_t			 rbytes_avail;
	uint8_t			 length_header;
	uint16_t		 position_slot;
	uint8_t			 offset_bits;

	struct lzx_pos_tbl 	*pos_tbl;
	/*
	 * Bit stream reader.
	 */
	struct lzx_br		 br;

	/*
	 * Huffman coding.
	 */
	struct huffman		 at;
	struct huffman		 lt;
	struct huffman		 mt;
	struct huffman		 pt;

	uint16_t		 loop;
	int			 error;
};

static const size_t slots[] = {
	30, 32, 34, 36, 38, 42, 50, 66, 98, 162, 290
};
#define SLOT_BASE	15
#define SLOT_MAX	21/*->25*/

struct lzx_stream {
	const unsigned char	*next_in;
	size_t			 avail_in;
	size_t			 total_in;
	unsigned char		*next_out;
	size_t			 avail_out;
	size_t			 total_out;
	struct lzx_dec		*ds;
};

/*
 * Cabinet file definitions.
 */
/* CFHEADER offset */
#define CFHEADER_signature	0
#define CFHEADER_cbCabinet	8
#define CFHEADER_coffFiles	16
#define CFHEADER_versionMinor	24
#define CFHEADER_versionMajor	25
#define CFHEADER_cFolders	26
#define CFHEADER_cFiles		28
#define CFHEADER_flags		30
#define CFHEADER_setID		32
#define CFHEADER_iCabinet	34
#define CFHEADER_cbCFHeader	36
#define CFHEADER_cbCFFolder	38
#define CFHEADER_cbCFData	39

/* CFFOLDER offset */
#define CFFOLDER_coffCabStart	0
#define CFFOLDER_cCFData	4
#define CFFOLDER_typeCompress	6
#define CFFOLDER_abReserve	8

/* CFFILE offset */
#define CFFILE_cbFile		0
#define CFFILE_uoffFolderStart	4
#define CFFILE_iFolder		8
#define CFFILE_date_time	10
#define CFFILE_attribs		14

/* CFDATA offset */
#define CFDATA_csum		0
#define CFDATA_cbData		4
#define CFDATA_cbUncomp		6

/* Limits */
#define MAX_UNCOMPRESS_SIZE	0x8000
#define MAX_FILE_SIZE		(UINT16_MAX * MAX_UNCOMPRESS_SIZE)
#define MAX_E8_TRANSLATION	(0x8000 * MAX_UNCOMPRESS_SIZE)

static const char * const compression_name[] = {
	"NONE",
	"MSZIP",
	"Quantum",
	"LZX",
};

struct cfdata {
	/* Sum value of this CFDATA. */
	uint32_t		 sum;
	uint16_t		 compressed_size;
	uint16_t		 compressed_bytes_remaining;
	uint16_t		 uncompressed_size;
	uint16_t		 uncompressed_bytes_remaining;
	/* To know how many bytes we have decompressed. */
	uint16_t		 uncompressed_avail;
	/* Offset from the beginning of compressed data of this CFDATA */
	uint16_t		 read_offset;
	int64_t			 unconsumed;
	/* To keep memory image of this CFDATA to compute the sum. */
	size_t			 memimage_size;
	unsigned char		*memimage;
	/* Result of calculation of sum. */
	uint32_t		 sum_calculated;
	unsigned char		 sum_extra[4];
	int			 sum_extra_avail;
	const void		*sum_ptr;
};

struct cffolder {
	uint32_t		 cfdata_offset_in_cab;
	uint16_t		 cfdata_count;
	uint16_t		 comptype;
#define COMPTYPE_NONE		0x0000
#define COMPTYPE_MSZIP		0x0001
#define COMPTYPE_QUANTUM	0x0002
#define COMPTYPE_LZX		0x0003
	uint16_t		 compdata;
	const char		*compname;
	/* At the time reading CFDATA */
	struct cfdata		 cfdata;
	int			 cfdata_index;
	/* Flags to mark progress of decompression. */
	char			 decompress_init;
};

struct cffile {
	uint32_t		 uncompressed_size;
	uint32_t		 offset;
	time_t			 mtime;
	uint16_t	 	 folder;
#define iFoldCONTINUED_FROM_PREV	0xFFFD
#define iFoldCONTINUED_TO_NEXT		0xFFFE
#define iFoldCONTINUED_PREV_AND_NEXT	0xFFFF
	unsigned char		 attr;
#define ATTR_RDONLY		0x01
#define ATTR_NAME_IS_UTF	0x80
	struct archive_string 	 pathname;
};

struct cfheader {
	uint32_t		 files_offset;
	uint16_t		 folder_count;
	uint16_t		 file_count;
	uint16_t		 flags;
#define PREV_CABINET	0x0001
#define NEXT_CABINET	0x0002
#define RESERVE_PRESENT	0x0004
	uint16_t		 cabinet;
	/* Version number. */
	unsigned char		 major;
	unsigned char		 minor;
	unsigned char		 cffolder;
	unsigned char		 cfdata;
	/* All folders in a cabinet. */
	struct cffolder		*folder_array;
	/* All files in a cabinet. */
	struct cffile		*file_array;
	int			 file_index;
};

struct cab {
	/* entry_bytes_remaining is the number of bytes we expect. */
	int64_t			 entry_offset;
	int64_t			 entry_bytes_remaining;
	int64_t			 entry_unconsumed;
	struct cffolder		*entry_cffolder;
	struct cffile		*entry_cffile;
	struct cfdata		*entry_cfdata;

	/* Offset from beginning of a cabinet file. */
	int64_t			 cab_offset;
	struct cfheader		 cfheader;
	struct archive_wstring	 ws;

	/* Flag to mark progress that first header of an archive was read.*/
	char			 found_header;
	char			 end_of_archive;
	char			 end_of_entry;
	char			 end_of_entry_cleanup;
	char			 read_data_invoked;
	int64_t			 bytes_skipped;

	unsigned char		*uncompressed_buffer;
	size_t			 uncompressed_buffer_size;

	int			 init_default_conversion;
	struct archive_string_conv *sconv;
	struct archive_string_conv *sconv_default;
	struct archive_string_conv *sconv_utf8;
	char			 format_name[64];

#ifdef HAVE_ZLIB_H
	z_stream		 stream;
	char			 stream_valid;
#endif
	struct lzx_stream	 xstrm;
};

static int	archive_read_format_cab_bid(struct archive_read *, int);
static int	archive_read_format_cab_options(struct archive_read *,
		    const char *, const char *);
static int	archive_read_format_cab_read_header(struct archive_read *,
		    struct archive_entry *);
static int	archive_read_format_cab_read_data(struct archive_read *,
		    const void **, size_t *, int64_t *);
static int	archive_read_format_cab_read_data_skip(struct archive_read *);
static int	archive_read_format_cab_cleanup(struct archive_read *);

static int	cab_skip_sfx(struct archive_read *);
static time_t	cab_dos_time(const char *);
static int	cab_read_data(struct archive_read *, const void **,
		    size_t *, int64_t *);
static int	cab_read_header(struct archive_read *);
static uint32_t cab_checksum_cfdata_4(const void *, size_t bytes, uint32_t);
static uint32_t cab_checksum_cfdata(const void *, size_t bytes, uint32_t);
static void	cab_checksum_update(struct archive_read *, size_t);
static int	cab_checksum_finish(struct archive_read *);
static int	cab_next_cfdata(struct archive_read *);
static const void *cab_read_ahead_cfdata(struct archive_read *, ssize_t *);
static const void *cab_read_ahead_cfdata_none(struct archive_read *, ssize_t *);
static const void *cab_read_ahead_cfdata_deflate(struct archive_read *,
		    ssize_t *);
static const void *cab_read_ahead_cfdata_lzx(struct archive_read *,
		    ssize_t *);
static int64_t	cab_consume_cfdata(struct archive_read *, int64_t);
static int64_t	cab_minimum_consume_cfdata(struct archive_read *, int64_t);
static int	lzx_decode_init(struct lzx_stream *, int);
static int	lzx_read_blocks(struct lzx_stream *, int);
static int	lzx_decode_blocks(struct lzx_stream *, int);
static void	lzx_decode_free(struct lzx_stream *);
static void	lzx_translation(struct lzx_stream *, unsigned char *, size_t, int32_t);
static void	lzx_cleanup_bitstream(struct lzx_stream *);
static int	lzx_decode(struct lzx_stream *, int);
static int	lzx_read_pre_tree(struct lzx_stream *);
static int	lzx_read_bitlen(struct lzx_stream *, struct huffman *, uint16_t);
static int	lzx_huffman_init(struct huffman *, uint16_t, uint8_t);
static void	lzx_huffman_free(struct huffman *);
static int	lzx_make_huffman_table(struct huffman *);
static uint16_t	lzx_decode_huffman(struct huffman *, uint16_t);


int
archive_read_support_format_cab(struct archive *_a)
{
	struct archive_read *a = (struct archive_read *)_a;
	struct cab *cab;
	int r;

	archive_check_magic(_a, ARCHIVE_READ_MAGIC,
	    ARCHIVE_STATE_NEW, "archive_read_support_format_cab");

	cab = calloc(1, sizeof(*cab));
	if (cab == NULL) {
		archive_set_error(&a->archive, ENOMEM,
		    "Can't allocate CAB data");
		return (ARCHIVE_FATAL);
	}
	archive_string_init(&cab->ws);
	if (archive_wstring_ensure(&cab->ws, 256) == NULL) {
		archive_set_error(&a->archive, ENOMEM,
		    "Can't allocate memory");
		free(cab);
		return (ARCHIVE_FATAL);
	}

	r = __archive_read_register_format(a,
	    cab,
	    "cab",
	    archive_read_format_cab_bid,
	    archive_read_format_cab_options,
	    archive_read_format_cab_read_header,
	    archive_read_format_cab_read_data,
	    archive_read_format_cab_read_data_skip,
	    NULL,
	    archive_read_format_cab_cleanup,
	    NULL,
	    NULL);

	if (r != ARCHIVE_OK) {
		archive_wstring_free(&cab->ws);
		free(cab);
	}
	return (ARCHIVE_OK);
}

static int
find_cab_magic(const char *p)
{
	switch (p[4]) {
	case 0:
		/*
		 * Note: Self-Extraction program has 'MSCF' string in their
		 * program. If we were finding 'MSCF' string only, we got
		 * wrong place for Cabinet header, thus, we have to check
		 * following four bytes which are reserved and must be set
		 * to zero.
		 */
		if (memcmp(p, "MSCF\0\0\0\0", 8) == 0)
			return 0;
		return 5;
	case 'F': return 1;
	case 'C': return 2;
	case 'S': return 3;
	case 'M': return 4;
	default:  return 5;
	}
}

static int
archive_read_format_cab_bid(struct archive_read *a, int best_bid)
{
	const char *p;
	ssize_t bytes_avail, offset, window;

	/* If there's already a better bid than we can ever
	   make, don't bother testing. */
	if (best_bid > 64)
		return (-1);

	if ((p = __archive_read_ahead(a, 8, NULL)) == NULL)
		return (-1);

	if (memcmp(p, "MSCF\0\0\0\0", 8) == 0)
		return (64);

	/*
	 * Attempt to handle self-extracting archives
	 * by noting a PE header and searching forward
	 * up to 128k for an 'MSCF' marker.
	 */
	if (p[0] == 'M' && p[1] == 'Z') {
		offset = 0;
		window = 4096;
		while (offset < (1024 * 128)) {
			const char *h = __archive_read_ahead(a, offset + window,
			    &bytes_avail);
			if (h == NULL) {
				/* Remaining bytes are less than window. */
				window >>= 1;
				if (window < 128)
					return (0);
				continue;
			}
			p = h + offset;
			while (p + 8 < h + bytes_avail) {
				int next;
				if ((next = find_cab_magic(p)) == 0)
					return (64);
				p += next;
			}
			offset = p - h;
		}
	}
	return (0);
}

static int
archive_read_format_cab_options(struct archive_read *a,
    const char *key, const char *val)
{
	struct cab *cab = a->format->data;
	int ret = ARCHIVE_FAILED;

	if (strcmp(key, "hdrcharset")  == 0) {
		if (val == NULL || val[0] == 0)
			archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
			    "cab: hdrcharset option needs a character-set name");
		else {
			cab->sconv = archive_string_conversion_from_charset(
			    &a->archive, val, 0);
			if (cab->sconv != NULL)
				ret = ARCHIVE_OK;
			else
				ret = ARCHIVE_FATAL;
		}
		return (ret);
	}

	/* Note: The "warn" return is just to inform the options
	 * supervisor that we didn't handle it.  It will generate
	 * a suitable error if no one used this option. */
	return (ARCHIVE_WARN);
}

static int
cab_skip_sfx(struct archive_read *a)
{
	const char *p, *q;
	size_t skip;
	ssize_t bytes, window;

	window = 4096;
	for (;;) {
		const char *h = __archive_read_ahead(a, window, &bytes);
		if (h == NULL) {
			/* Remaining size is less than window. */
			window >>= 1;
			if (window < 128) {
				archive_set_error(&a->archive,
				    ARCHIVE_ERRNO_FILE_FORMAT,
				    "Couldn't find out CAB header");
				return (ARCHIVE_FATAL);
			}
			continue;
		}
		p = h;
		q = p + bytes;

		/*
		 * Scan ahead until we find something that looks
		 * like the cab header.
		 */
		while (p + 8 < q) {
			int next;
			if ((next = find_cab_magic(p)) == 0) {
				skip = p - h;
				__archive_read_consume(a, skip);
				return (ARCHIVE_OK);
			}
			p += next;
		}
		skip = p - h;
		__archive_read_consume(a, skip);
	}
}

static int
truncated_error(struct archive_read *a)
{
	archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
	    "Truncated CAB header");
	return (ARCHIVE_FATAL);
}

#ifdef HAVE_STRNLEN
#define cab_strnlen(a,b) strnlen(a,b)
#else
static size_t
cab_strnlen(const char *p, size_t maxlen)
{
	size_t i;

	for (i = 0; i < maxlen; i++) {
		if (p[i] == 0)
			break;
	}
	return (i);
}
#endif

/* Read up to max remaining bytes. */
static const void *
cab_read_ahead_remaining(struct archive_read *a, size_t max, ssize_t *avail)
{
	const void *p = __archive_read_ahead(a, max, avail);

	if (p == NULL && *avail > 0)
		p = __archive_read_ahead(a, *avail, avail);
	if (p != NULL && (size_t)*avail > max)
		*avail = max;

	return (p);
}

/* Convert a path separator '\' -> '/' */
static int
cab_convert_path_separator_1(struct archive_string *fn, unsigned char attr)
{
	size_t i;
	int mb;

	/* Easy check if we have '\' in multi-byte string. */
	mb = 0;
	for (i = 0; i < archive_strlen(fn); i++) {
		if (fn->s[i] == '\\') {
			if (mb) {
				/* This may be second byte of multi-byte
				 * character. */
				break;
			}
			fn->s[i] = '/';
			mb = 0;
		} else if ((fn->s[i] & 0x80) && !(attr & ATTR_NAME_IS_UTF))
			mb = 1;
		else
			mb = 0;
	}
	if (i == archive_strlen(fn))
		return (0);
	return (-1);
}

/*
 * Replace a character '\' with '/' in wide character.
 */
static void
cab_convert_path_separator_2(struct cab *cab, struct archive_entry *entry)
{
	const wchar_t *wp;
	size_t i;

	/* If a conversion to wide character failed, force the replacement. */
	if ((wp = archive_entry_pathname_w(entry)) != NULL) {
		archive_wstrcpy(&(cab->ws), wp);
		for (i = 0; i < archive_strlen(&(cab->ws)); i++) {
			if (cab->ws.s[i] == L'\\')
				cab->ws.s[i] = L'/';
		}
		archive_entry_copy_pathname_w(entry, cab->ws.s);
	}
}

/*
 * Read CFHEADER, CFFOLDER and CFFILE.
 */
static int
cab_read_header(struct archive_read *a)
{
	struct cab *cab = a->format->data;
	const char *p;
	struct cfheader *hd;
	size_t bytes, len, maxlen, used;
	ssize_t avail;
	int64_t skip;
	int err, i;
	int cur_folder, prev_folder;
	uint32_t offset32;

	a->archive.archive_format = ARCHIVE_FORMAT_CAB;
	if (a->archive.archive_format_name == NULL)
		a->archive.archive_format_name = "CAB";

	if ((p = __archive_read_ahead(a, 42, NULL)) == NULL)
		return (truncated_error(a));

	if (cab->found_header == 0 &&
	    p[0] == 'M' && p[1] == 'Z') {
		/* This is an executable?  Must be self-extracting... */
		err = cab_skip_sfx(a);
		if (err < ARCHIVE_WARN)
			return (err);

		/* Re-read header after processing the SFX. */
		if ((p = __archive_read_ahead(a, 42, NULL)) == NULL)
			return (truncated_error(a));
	}

	cab->cab_offset = 0;
	/*
	 * Read CFHEADER.
	 */
	hd = &cab->cfheader;
	if (p[CFHEADER_signature+0] != 'M' || p[CFHEADER_signature+1] != 'S' ||
	    p[CFHEADER_signature+2] != 'C' || p[CFHEADER_signature+3] != 'F') {
		archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
		    "Couldn't find out CAB header");
		return (ARCHIVE_FATAL);
	}
	hd->files_offset = archive_le32dec(p + CFHEADER_coffFiles);
	hd->minor = p[CFHEADER_versionMinor];
	hd->major = p[CFHEADER_versionMajor];
	hd->folder_count = archive_le16dec(p + CFHEADER_cFolders);
	if (hd->folder_count == 0)
		goto invalid;
	hd->file_count = archive_le16dec(p + CFHEADER_cFiles);
	if (hd->file_count == 0)
		goto invalid;
	hd->flags = archive_le16dec(p + CFHEADER_flags);
	hd->cabinet = archive_le16dec(p + CFHEADER_iCabinet);
	used = CFHEADER_iCabinet + 2;
	if (hd->flags & RESERVE_PRESENT) {
		uint16_t cfheader;
		cfheader = archive_le16dec(p + CFHEADER_cbCFHeader);
		if (cfheader > 60000U)
			goto invalid;
		hd->cffolder = p[CFHEADER_cbCFFolder];
		hd->cfdata = p[CFHEADER_cbCFData];
		used += 4;/* cbCFHeader, cbCFFolder and cbCFData */
		used += cfheader;/* abReserve */
	} else
		hd->cffolder = 0;/* Avoid compiling warning. */
	if (hd->flags & PREV_CABINET) {
		/* How many bytes are used for szCabinetPrev. */
		if ((p = cab_read_ahead_remaining(a, used + 256,
		    &avail)) == NULL || (size_t)avail <= used)
			return (truncated_error(a));
		maxlen = avail - used;
		len = cab_strnlen(p + used, maxlen);
		if (len == 0 || len == maxlen) {
			goto invalid;
		}
		used += len + 1;
		/* How many bytes are used for szDiskPrev. */
		if ((p = cab_read_ahead_remaining(a, used + 256,
		    &avail)) == NULL || (size_t)avail <= used)
			return (truncated_error(a));
		maxlen = avail - used;
		len = cab_strnlen(p + used, maxlen);
		if (len == maxlen)
			goto invalid;
		used += len + 1;
	}
	if (hd->flags & NEXT_CABINET) {
		/* How many bytes are used for szCabinetNext. */
		if ((p = cab_read_ahead_remaining(a, used + 256,
		    &avail)) == NULL || (size_t)avail <= used)
			return (truncated_error(a));
		maxlen = avail - used;
		len = cab_strnlen(p + used, maxlen);
		if (len == 0 || len == maxlen)
			goto invalid;
		used += len + 1;
		/* How many bytes are used for szDiskNext. */
		if ((p = cab_read_ahead_remaining(a, used + 256,
		    &avail)) == NULL || (size_t)avail <= used)
			return (truncated_error(a));
		maxlen = avail - used;
		len = cab_strnlen(p + used, maxlen);
		if (len == maxlen)
			goto invalid;
		used += len + 1;
	}
	__archive_read_consume(a, used);
	cab->cab_offset += used;
	used = 0;

	/*
	 * Read CFFOLDER.
	 */
	hd->folder_array = calloc(
	    hd->folder_count, sizeof(struct cffolder));
	if (hd->folder_array == NULL)
		goto nomem;

	bytes = 8;
	if (hd->flags & RESERVE_PRESENT)
		bytes += hd->cffolder;
	bytes *= hd->folder_count;
	if ((p = __archive_read_ahead(a, bytes, NULL)) == NULL)
		return (truncated_error(a));
	offset32 = 0;
	for (i = 0; i < hd->folder_count; i++) {
		struct cffolder *folder = &(hd->folder_array[i]);
		folder->cfdata_offset_in_cab =
		    archive_le32dec(p + CFFOLDER_coffCabStart);
		folder->cfdata_count = archive_le16dec(p+CFFOLDER_cCFData);
		folder->comptype =
		    archive_le16dec(p+CFFOLDER_typeCompress) & 0x0F;
		folder->compdata =
		    archive_le16dec(p+CFFOLDER_typeCompress) >> 8;
		/* Get a compression name. */
		if (folder->comptype <
		    sizeof(compression_name) / sizeof(compression_name[0]))
			folder->compname = compression_name[folder->comptype];
		else
			folder->compname = "UNKNOWN";
		p += 8;
		used += 8;
		if (hd->flags & RESERVE_PRESENT) {
			p += hd->cffolder;/* abReserve */
			used += hd->cffolder;
		}
		/*
		 * Sanity check if each data is acceptable.
		 */
		if (offset32 >= folder->cfdata_offset_in_cab)
			goto invalid;
		offset32 = folder->cfdata_offset_in_cab;

		/* Set a request to initialize zlib for the CFDATA of
		 * this folder. */
		folder->decompress_init = 0;
	}
	__archive_read_consume(a, used);
	cab->cab_offset += used;

	/*
	 * Read CFFILE.
	 */
	/* Seek read pointer to the offset of CFFILE if needed. */
	skip = (int64_t)hd->files_offset - cab->cab_offset;
	if (skip < 0) {
		archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
		    "Invalid offset of CFFILE %jd < %jd",
		    (intmax_t)hd->files_offset, (intmax_t)cab->cab_offset);
		return (ARCHIVE_FATAL);
	}
	if (skip) {
		if (__archive_read_consume(a, skip) < 0)
			return (truncated_error(a));
		cab->cab_offset += skip;
	}
	/* Allocate memory for CFDATA */
	hd->file_array = calloc(
	    hd->file_count, sizeof(struct cffile));
	if (hd->file_array == NULL)
		goto nomem;

	prev_folder = -1;
	for (i = 0; i < hd->file_count; i++) {
		struct cffile *file = &(hd->file_array[i]);

		if ((p = __archive_read_ahead(a, 16, NULL)) == NULL)
			return (truncated_error(a));
		file->uncompressed_size = archive_le32dec(p + CFFILE_cbFile);
		file->offset = archive_le32dec(p + CFFILE_uoffFolderStart);
		file->folder = archive_le16dec(p + CFFILE_iFolder);
		file->mtime = cab_dos_time(p + CFFILE_date_time);
		file->attr = (uint8_t)archive_le16dec(p + CFFILE_attribs);
		__archive_read_consume(a, 16);

		cab->cab_offset += 16;
		if ((p = cab_read_ahead_remaining(a, 256, &avail)) == NULL)
			return (truncated_error(a));
		maxlen = avail;
		len = cab_strnlen(p, maxlen);
		if (len == 0 || len == maxlen)
			goto invalid;

		/* Copy a pathname.  */
		archive_string_init(&(file->pathname));
		archive_strncpy(&(file->pathname), p, len);
		__archive_read_consume(a, len + 1);
		cab->cab_offset += len + 1;

		/*
		 * Sanity check if each data is acceptable.
		 */
		if (file->uncompressed_size > MAX_FILE_SIZE)
			goto invalid;/* Too large */
		if ((int64_t)file->offset + (int64_t)file->uncompressed_size
		    > (int64_t)MAX_FILE_SIZE)
			goto invalid;/* Too large */
		switch (file->folder) {
		case iFoldCONTINUED_TO_NEXT:
			/* This must be last file in a folder. */
			if (i != hd->file_count -1)
				goto invalid;
			cur_folder = hd->folder_count -1;
			break;
		case iFoldCONTINUED_PREV_AND_NEXT:
			/* This must be only one file in a folder. */
			if (hd->file_count != 1)
				goto invalid;
			/* FALL THROUGH */
		case iFoldCONTINUED_FROM_PREV:
			/* This must be first file in a folder. */
			if (i != 0)
				goto invalid;
			prev_folder = cur_folder = 0;
			offset32 = file->offset;
			break;
		default:
			if (file->folder >= hd->folder_count)
				goto invalid;
			cur_folder = file->folder;
			break;
		}
		/* Dot not back track. */
		if (cur_folder < prev_folder)
			goto invalid;
		if (cur_folder != prev_folder)
			offset32 = 0;
		prev_folder = cur_folder;

		/* Make sure there are not any blanks from last file
		 * contents. */
		if (offset32 != file->offset)
			goto invalid;
		offset32 += file->uncompressed_size;

		/* CFDATA is available for file contents. */
		if (file->uncompressed_size > 0 &&
		    hd->folder_array[cur_folder].cfdata_count == 0)
			goto invalid;
	}

	if (hd->cabinet != 0 || hd->flags & (PREV_CABINET | NEXT_CABINET)) {
		archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
		    "Multivolume cabinet file is unsupported");
		return (ARCHIVE_WARN);
	}
	return (ARCHIVE_OK);
invalid:
	archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
	    "Invalid CAB header");
	return (ARCHIVE_FATAL);
nomem:
	archive_set_error(&a->archive, ENOMEM,
	    "Can't allocate memory for CAB data");
	return (ARCHIVE_FATAL);
}

static int
archive_read_format_cab_read_header(struct archive_read *a,
    struct archive_entry *entry)
{
	struct cab *cab = a->format->data;
	struct cfheader *hd;
	struct cffolder *prev_folder;
	struct cffile *file;
	struct archive_string_conv *sconv;
	int err = ARCHIVE_OK, r;

	if (cab->found_header == 0) {
		err = cab_read_header(a);
		if (err < ARCHIVE_WARN)
			return (err);
		/* We've found the header. */
		cab->found_header = 1;
	}
	hd = &cab->cfheader;

	if (hd->file_index >= hd->file_count) {
		cab->end_of_archive = 1;
		return (ARCHIVE_EOF);
	}
	file = &hd->file_array[hd->file_index++];

	cab->end_of_entry = 0;
	cab->end_of_entry_cleanup = 0;
	cab->entry_unconsumed = 0;
	cab->entry_cffile = file;

	/*
	 * Choose a proper folder.
	 */
	prev_folder = cab->entry_cffolder;
	switch (file->folder) {
	case iFoldCONTINUED_FROM_PREV:
	case iFoldCONTINUED_PREV_AND_NEXT:
		cab->entry_cffolder = &hd->folder_array[0];
		break;
	case iFoldCONTINUED_TO_NEXT:
		cab->entry_cffolder = &hd->folder_array[hd->folder_count-1];
		break;
	default:
		cab->entry_cffolder = &hd->folder_array[file->folder];
		break;
	}
	/* If a cffolder of this file is changed, reset a cfdata to read
	 * file contents from next cfdata. */
	if (prev_folder != cab->entry_cffolder)
		cab->entry_cfdata = NULL;

	/* If a pathname is UTF-8, prepare a string conversion object
	 * for UTF-8 and use it. */
	if (file->attr & ATTR_NAME_IS_UTF) {
		if (cab->sconv_utf8 == NULL) {
			cab->sconv_utf8 =
			    archive_string_conversion_from_charset(
				&(a->archive), "UTF-8", 1);
			if (cab->sconv_utf8 == NULL)
				return (ARCHIVE_FATAL);
		}
		sconv = cab->sconv_utf8;
	} else if (cab->sconv != NULL) {
		/* Choose the conversion specified by the option. */
		sconv = cab->sconv;
	} else {
		/* Choose the default conversion. */
		if (!cab->init_default_conversion) {
			cab->sconv_default =
			    archive_string_default_conversion_for_read(
			      &(a->archive));
			cab->init_default_conversion = 1;
		}
		sconv = cab->sconv_default;
	}

	/*
	 * Set a default value and common data
	 */
	r = cab_convert_path_separator_1(&(file->pathname), file->attr);
	if (archive_entry_copy_pathname_l(entry, file->pathname.s,
	    archive_strlen(&(file->pathname)), sconv) != 0) {
		if (errno == ENOMEM) {
			archive_set_error(&a->archive, ENOMEM,
			    "Can't allocate memory for Pathname");
			return (ARCHIVE_FATAL);
		}
		archive_set_error(&a->archive,
		    ARCHIVE_ERRNO_FILE_FORMAT,
		    "Pathname cannot be converted "
		    "from %s to current locale",
		    archive_string_conversion_charset_name(sconv));
		err = ARCHIVE_WARN;
	}
	if (r < 0) {
		/* Convert a path separator '\' -> '/' */
		cab_convert_path_separator_2(cab, entry);
	}

	archive_entry_set_size(entry, file->uncompressed_size);
	if (file->attr & ATTR_RDONLY)
		archive_entry_set_mode(entry, AE_IFREG | 0555);
	else
		archive_entry_set_mode(entry, AE_IFREG | 0666);
	archive_entry_set_mtime(entry, file->mtime, 0);

	cab->entry_bytes_remaining = file->uncompressed_size;
	cab->entry_offset = 0;
	/* We don't need compress data. */
	if (file->uncompressed_size == 0)
		cab->end_of_entry_cleanup = cab->end_of_entry = 1;

	/* Set up a more descriptive format name. */
	snprintf(cab->format_name, sizeof(cab->format_name), "CAB %d.%d (%s)",
	    hd->major, hd->minor, cab->entry_cffolder->compname);
	a->archive.archive_format_name = cab->format_name;

	return (err);
}

static int
archive_read_format_cab_read_data(struct archive_read *a,
    const void **buff, size_t *size, int64_t *offset)
{
	struct cab *cab = a->format->data;
	int r;

	switch (cab->entry_cffile->folder) {
	case iFoldCONTINUED_FROM_PREV:
	case iFoldCONTINUED_TO_NEXT:
	case iFoldCONTINUED_PREV_AND_NEXT:
		*buff = NULL;
		*size = 0;
		*offset = 0;
		archive_clear_error(&a->archive);
		archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
		    "Cannot restore this file split in multivolume");
		return (ARCHIVE_FAILED);
	default:
		break;
	}
	if (cab->read_data_invoked == 0) {
		if (cab->bytes_skipped) {
			if (cab->entry_cfdata == NULL) {
				r = cab_next_cfdata(a);
				if (r < 0)
					return (r);
			}
			if (cab_consume_cfdata(a, cab->bytes_skipped) < 0)
				return (ARCHIVE_FATAL);
			cab->bytes_skipped = 0;
		}
		cab->read_data_invoked = 1;
	}
	if (cab->entry_unconsumed) {
		/* Consume as much as the compressor actually used. */
		r = (int)cab_consume_cfdata(a, cab->entry_unconsumed);
		cab->entry_unconsumed = 0;
		if (r < 0)
			return (r);
	}
	if (cab->end_of_archive || cab->end_of_entry) {
		if (!cab->end_of_entry_cleanup) {
			/* End-of-entry cleanup done. */
			cab->end_of_entry_cleanup = 1;
		}
		*offset = cab->entry_offset;
		*size = 0;
		*buff = NULL;
		return (ARCHIVE_EOF);
	}

	return (cab_read_data(a, buff, size, offset));
}

static uint32_t
cab_checksum_cfdata_4(const void *p, size_t bytes, uint32_t seed)
{
	const unsigned char *b;
	unsigned u32num;
	uint32_t sum;

	u32num = (unsigned)bytes / 4;
	sum = seed;
	b = p;
	for (;u32num > 0; --u32num) {
		sum ^= archive_le32dec(b);
		b += 4;
	}
	return (sum);
}

static uint32_t
cab_checksum_cfdata(const void *p, size_t bytes, uint32_t seed)
{
	const unsigned char *b;
	uint32_t sum;
	uint32_t t;

	sum = cab_checksum_cfdata_4(p, bytes, seed);
	b = p;
	b += bytes & ~3;
	t = 0;
	switch (bytes & 3) {
	case 3:
		t |= ((uint32_t)(*b++)) << 16;
		/* FALL THROUGH */
	case 2:
		t |= ((uint32_t)(*b++)) << 8;
		/* FALL THROUGH */
	case 1:
		t |= *b;
		/* FALL THROUGH */
	default:
		break;
	}
	sum ^= t;

	return (sum);
}

static void
cab_checksum_update(struct archive_read *a, size_t bytes)
{
	struct cab *cab = a->format->data;
	struct cfdata *cfdata = cab->entry_cfdata;
	const unsigned char *p;
	size_t sumbytes;

	if (cfdata->sum == 0 || cfdata->sum_ptr == NULL)
		return;
	/*
	 * Calculate the sum of this CFDATA.
	 * Make sure CFDATA must be calculated in four bytes.
	 */
	p = cfdata->sum_ptr;
	sumbytes = bytes;
	if (cfdata->sum_extra_avail) {
		while (cfdata->sum_extra_avail < 4 && sumbytes > 0) {
			cfdata->sum_extra[
			    cfdata->sum_extra_avail++] = *p++;
			sumbytes--;
		}
		if (cfdata->sum_extra_avail == 4) {
			cfdata->sum_calculated = cab_checksum_cfdata_4(
			    cfdata->sum_extra, 4, cfdata->sum_calculated);
			cfdata->sum_extra_avail = 0;
		}
	}
	if (sumbytes) {
		int odd = sumbytes & 3;
		if ((int)(sumbytes - odd) > 0)
			cfdata->sum_calculated = cab_checksum_cfdata_4(
			    p, sumbytes - odd, cfdata->sum_calculated);
		if (odd)
			memcpy(cfdata->sum_extra, p + sumbytes - odd, odd);
		cfdata->sum_extra_avail = odd;
	}
	cfdata->sum_ptr = NULL;
}

static int
cab_checksum_finish(struct archive_read *a)
{
	struct cab *cab = a->format->data;
	struct cfdata *cfdata = cab->entry_cfdata;
	int l;

	/* Do not need to compute a sum. */
	if (cfdata->sum == 0)
		return (ARCHIVE_OK);

	/*
	 * Calculate the sum of remaining CFDATA.
	 */
	if (cfdata->sum_extra_avail) {
		cfdata->sum_calculated =
		    cab_checksum_cfdata(cfdata->sum_extra,
		       cfdata->sum_extra_avail, cfdata->sum_calculated);
		cfdata->sum_extra_avail = 0;
	}

	l = 4;
	if (cab->cfheader.flags & RESERVE_PRESENT)
		l += cab->cfheader.cfdata;
	if (cfdata->memimage == NULL) {
		return (ARCHIVE_FAILED);
	}
	cfdata->sum_calculated = cab_checksum_cfdata(
	    cfdata->memimage + CFDATA_cbData, l, cfdata->sum_calculated);
	if (cfdata->sum_calculated != cfdata->sum) {
#ifndef DONT_FAIL_ON_CRC_ERROR
		archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
		    "Checksum error CFDATA[%d] %" PRIx32 ":%" PRIx32 " in %d bytes",
		    cab->entry_cffolder->cfdata_index -1,
		    cfdata->sum, cfdata->sum_calculated,
		    cfdata->compressed_size);
		return (ARCHIVE_FAILED);
#endif
	}
	return (ARCHIVE_OK);
}

/*
 * Read CFDATA if needed.
 */
static int
cab_next_cfdata(struct archive_read *a)
{
	struct cab *cab = a->format->data;
	struct cfdata *cfdata = cab->entry_cfdata;

	/* There are remaining bytes in current CFDATA, use it first. */
	if (cfdata != NULL && cfdata->uncompressed_bytes_remaining > 0)
		return (ARCHIVE_OK);

	if (cfdata == NULL) {
		int64_t skip;

		cab->entry_cffolder->cfdata_index = 0;

		/* Seek read pointer to the offset of CFDATA if needed. */
		skip = cab->entry_cffolder->cfdata_offset_in_cab
			- cab->cab_offset;
		if (skip < 0) {
			int folder_index;
			switch (cab->entry_cffile->folder) {
			case iFoldCONTINUED_FROM_PREV:
			case iFoldCONTINUED_PREV_AND_NEXT:
				folder_index = 0;
				break;
			case iFoldCONTINUED_TO_NEXT:
				folder_index = cab->cfheader.folder_count-1;
				break;
			default:
				folder_index = cab->entry_cffile->folder;
				break;
			}
			archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
			    "Invalid offset of CFDATA in folder(%d) %jd < %jd",
			    folder_index,
			    (intmax_t)cab->entry_cffolder->cfdata_offset_in_cab,
			    (intmax_t)cab->cab_offset);
			return (ARCHIVE_FATAL);
		}
		if (skip > 0) {
			if (__archive_read_consume(a, skip) < 0)
				return (ARCHIVE_FATAL);
			cab->cab_offset =
			    cab->entry_cffolder->cfdata_offset_in_cab;
		}
	}

	/*
	 * Read a CFDATA.
	 */
	if (cab->entry_cffolder->cfdata_index <
	    cab->entry_cffolder->cfdata_count) {
		const unsigned char *p;
		int l;

		cfdata = &(cab->entry_cffolder->cfdata);
		cab->entry_cffolder->cfdata_index++;
		cab->entry_cfdata = cfdata;
		cfdata->sum_calculated = 0;
		cfdata->sum_extra_avail = 0;
		cfdata->sum_ptr = NULL;
		l = 8;
		if (cab->cfheader.flags & RESERVE_PRESENT)
			l += cab->cfheader.cfdata;
		if ((p = __archive_read_ahead(a, l, NULL)) == NULL)
			return (truncated_error(a));
		cfdata->sum = archive_le32dec(p + CFDATA_csum);
		cfdata->compressed_size = archive_le16dec(p + CFDATA_cbData);
		cfdata->compressed_bytes_remaining = cfdata->compressed_size;
		cfdata->uncompressed_size =
		    archive_le16dec(p + CFDATA_cbUncomp);
		cfdata->uncompressed_bytes_remaining =
		    cfdata->uncompressed_size;
		cfdata->uncompressed_avail = 0;
		cfdata->read_offset = 0;
		cfdata->unconsumed = 0;

		/*
		 * Sanity check if data size is acceptable.
		 */
		if (cfdata->compressed_size == 0 ||
		    cfdata->compressed_size > (MAX_UNCOMPRESS_SIZE + 6144))
			goto invalid;
		if (cfdata->uncompressed_size > MAX_UNCOMPRESS_SIZE)
			goto invalid;
		if (cfdata->uncompressed_size == 0) {
			switch (cab->entry_cffile->folder) {
			case iFoldCONTINUED_PREV_AND_NEXT:
			case iFoldCONTINUED_TO_NEXT:
				break;
			case iFoldCONTINUED_FROM_PREV:
			default:
				goto invalid;
			}
		}
		/* If CFDATA is not last in a folder, an uncompressed
		 * size must be 0x8000 (32 KiB) */
		if ((cab->entry_cffolder->cfdata_index <
		     cab->entry_cffolder->cfdata_count) &&
		       cfdata->uncompressed_size != MAX_UNCOMPRESS_SIZE)
			goto invalid;

		/* A compressed data size and an uncompressed data size must
		 * be the same in no compression mode. */
		if (cab->entry_cffolder->comptype == COMPTYPE_NONE &&
		    cfdata->compressed_size != cfdata->uncompressed_size)
			goto invalid;

		/*
		 * Save CFDATA image for sum check.
		 */
		if (cfdata->memimage_size < (size_t)l) {
			free(cfdata->memimage);
			cfdata->memimage = malloc(l);
			if (cfdata->memimage == NULL) {
				archive_set_error(&a->archive, ENOMEM,
				    "Can't allocate memory for CAB data");
				return (ARCHIVE_FATAL);
			}
			cfdata->memimage_size = l;
		}
		memcpy(cfdata->memimage, p, l);

		/* Consume bytes as much as we used. */
		__archive_read_consume(a, l);
		cab->cab_offset += l;
	} else if (cab->entry_cffolder->cfdata_count > 0) {
		/* Run out of all CFDATA in a folder. */
		cfdata->compressed_size = 0;
		cfdata->uncompressed_size = 0;
		cfdata->compressed_bytes_remaining = 0;
		cfdata->uncompressed_bytes_remaining = 0;
	} else {
		/* Current folder does not have any CFDATA. */
		cfdata = &(cab->entry_cffolder->cfdata);
		cab->entry_cfdata = cfdata;
		memset(cfdata, 0, sizeof(*cfdata));
	}
	return (ARCHIVE_OK);
invalid:
	archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
	    "Invalid CFDATA");
	return (ARCHIVE_FATAL);
}

/*
 * Read ahead CFDATA.
 */
static const void *
cab_read_ahead_cfdata(struct archive_read *a, ssize_t *avail)
{
	struct cab *cab = a->format->data;
	int err;

	err = cab_next_cfdata(a);
	if (err < ARCHIVE_OK) {
		*avail = err;
		return (NULL);
	}

	switch (cab->entry_cffolder->comptype) {
	case COMPTYPE_NONE:
		return (cab_read_ahead_cfdata_none(a, avail));
	case COMPTYPE_MSZIP:
		return (cab_read_ahead_cfdata_deflate(a, avail));
	case COMPTYPE_LZX:
		return (cab_read_ahead_cfdata_lzx(a, avail));
	default: /* Unsupported compression. */
		archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
		    "Unsupported CAB compression: %s",
		    cab->entry_cffolder->compname);
		*avail = ARCHIVE_FAILED;
		return (NULL);
	}
}

/*
 * Read ahead CFDATA as uncompressed data.
 */
static const void *
cab_read_ahead_cfdata_none(struct archive_read *a, ssize_t *avail)
{
	struct cab *cab = a->format->data;
	struct cfdata *cfdata;
	const void *d;

	cfdata = cab->entry_cfdata;

	/*
	 * Note: '1' here is a performance optimization.
	 * Recall that the decompression layer returns a count of
	 * available bytes; asking for more than that forces the
	 * decompressor to combine reads by copying data.
	 */
	d = __archive_read_ahead(a, 1, avail);
	if (*avail <= 0) {
		*avail = truncated_error(a);
		return (NULL);
	}
	if (*avail > cfdata->uncompressed_bytes_remaining)
		*avail = cfdata->uncompressed_bytes_remaining;
	cfdata->uncompressed_avail = cfdata->uncompressed_size;
	cfdata->unconsumed = *avail;
	cfdata->sum_ptr = d;
	return (d);
}

/*
 * Read ahead CFDATA as deflate data.
 */
#ifdef HAVE_ZLIB_H
static const void *
cab_read_ahead_cfdata_deflate(struct archive_read *a, ssize_t *avail)
{
	struct cab *cab = a->format->data;
	struct cfdata *cfdata;
	const void *d;
	int r, mszip;
	uint16_t uavail;
	char eod = 0;

	cfdata = cab->entry_cfdata;
	/* If the buffer hasn't been allocated, allocate it now. */
	if (cab->uncompressed_buffer == NULL) {
		cab->uncompressed_buffer_size = MAX_UNCOMPRESS_SIZE;
		cab->uncompressed_buffer
		    = malloc(cab->uncompressed_buffer_size);
		if (cab->uncompressed_buffer == NULL) {
			archive_set_error(&a->archive, ENOMEM,
			    "No memory for CAB reader");
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
	}

	uavail = cfdata->uncompressed_avail;
	if (uavail == cfdata->uncompressed_size) {
		d = cab->uncompressed_buffer + cfdata->read_offset;
		*avail = uavail - cfdata->read_offset;
		return (d);
	}

	if (!cab->entry_cffolder->decompress_init) {
		cab->stream.next_in = NULL;
		cab->stream.avail_in = 0;
		cab->stream.total_in = 0;
		cab->stream.next_out = NULL;
		cab->stream.avail_out = 0;
		cab->stream.total_out = 0;
		if (cab->stream_valid)
			r = inflateReset(&cab->stream);
		else
			r = inflateInit2(&cab->stream,
			    -15 /* Don't check for zlib header */);
		if (r != Z_OK) {
			archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
			    "Can't initialize deflate decompression");
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
		/* Stream structure has been set up. */
		cab->stream_valid = 1;
		/* We've initialized decompression for this stream. */
		cab->entry_cffolder->decompress_init = 1;
	}

	if (cfdata->compressed_bytes_remaining == cfdata->compressed_size)
		mszip = 2;
	else
		mszip = 0;
	eod = 0;
	cab->stream.total_out = uavail;
	/*
	 * We always uncompress all data in current CFDATA.
	 */
	while (!eod && cab->stream.total_out < cfdata->uncompressed_size) {
		ssize_t bytes_avail;

		cab->stream.next_out =
		    cab->uncompressed_buffer + cab->stream.total_out;
		cab->stream.avail_out =
		    cfdata->uncompressed_size - cab->stream.total_out;

		d = __archive_read_ahead(a, 1, &bytes_avail);
		if (bytes_avail <= 0) {
			*avail = truncated_error(a);
			return (NULL);
		}
		if (bytes_avail > cfdata->compressed_bytes_remaining)
			bytes_avail = cfdata->compressed_bytes_remaining;
		/*
		 * A bug in zlib.h: stream.next_in should be marked 'const'
		 * but isn't (the library never alters data through the
		 * next_in pointer, only reads it).  The result: this ugly
		 * cast to remove 'const'.
		 */
		cab->stream.next_in = (Bytef *)(uintptr_t)d;
		cab->stream.avail_in = (uInt)bytes_avail;
		cab->stream.total_in = 0;

		/* Cut out a tow-byte MSZIP signature(0x43, 0x4b). */
		if (mszip > 0) {
			if (bytes_avail <= 0)
				goto nomszip;
			if (bytes_avail <= mszip) {
				if (mszip == 2) {
					if (cab->stream.next_in[0] != 0x43)
						goto nomszip;
					if (bytes_avail > 1 &&
					    cab->stream.next_in[1] != 0x4b)
						goto nomszip;
				} else if (cab->stream.next_in[0] != 0x4b)
					goto nomszip;
				cfdata->unconsumed = bytes_avail;
				cfdata->sum_ptr = d;
				if (cab_minimum_consume_cfdata(
				    a, cfdata->unconsumed) < 0) {
					*avail = ARCHIVE_FATAL;
					return (NULL);
				}
				mszip -= (int)bytes_avail;
				continue;
			}
			if (mszip == 1 && cab->stream.next_in[0] != 0x4b)
				goto nomszip;
			else if (mszip == 2 && (cab->stream.next_in[0] != 0x43 ||
			    cab->stream.next_in[1] != 0x4b))
				goto nomszip;
			cab->stream.next_in += mszip;
			cab->stream.avail_in -= mszip;
			cab->stream.total_in += mszip;
			mszip = 0;
		}

		r = inflate(&cab->stream, 0);
		switch (r) {
		case Z_OK:
			break;
		case Z_STREAM_END:
			eod = 1;
			break;
		default:
			goto zlibfailed;
		}
		cfdata->unconsumed = cab->stream.total_in;
		cfdata->sum_ptr = d;
		if (cab_minimum_consume_cfdata(a, cfdata->unconsumed) < 0) {
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
	}
	uavail = (uint16_t)cab->stream.total_out;

	if (uavail < cfdata->uncompressed_size) {
		archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
		    "Invalid uncompressed size (%d < %d)",
		    uavail, cfdata->uncompressed_size);
		*avail = ARCHIVE_FATAL;
		return (NULL);
	}

	/*
	 * Note: I suspect there is a bug in makecab.exe because, in rare
	 * case, compressed bytes are still remaining regardless we have
	 * gotten all uncompressed bytes, which size is recorded in CFDATA,
	 * as much as we need, and we have to use the garbage so as to
	 * correctly compute the sum of CFDATA accordingly.
	 */
	if (cfdata->compressed_bytes_remaining > 0) {
		d = __archive_read_ahead(a, cfdata->compressed_bytes_remaining,
		    NULL);
		if (d == NULL) {
			*avail = truncated_error(a);
			return (NULL);
		}
		cfdata->unconsumed = cfdata->compressed_bytes_remaining;
		cfdata->sum_ptr = d;
		if (cab_minimum_consume_cfdata(a, cfdata->unconsumed) < 0) {
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
	}

	/*
	 * Set dictionary data for decompressing of next CFDATA, which
	 * in the same folder. This is why we always do decompress CFDATA
	 * even if beginning CFDATA or some of CFDATA are not used in
	 * skipping file data.
	 */
	if (cab->entry_cffolder->cfdata_index <
	    cab->entry_cffolder->cfdata_count) {
		r = inflateReset(&cab->stream);
		if (r != Z_OK)
			goto zlibfailed;
		r = inflateSetDictionary(&cab->stream,
		    cab->uncompressed_buffer, cfdata->uncompressed_size);
		if (r != Z_OK)
			goto zlibfailed;
	}

	d = cab->uncompressed_buffer + cfdata->read_offset;
	*avail = uavail - cfdata->read_offset;
	cfdata->uncompressed_avail = uavail;

	return (d);

zlibfailed:
	switch (r) {
	case Z_MEM_ERROR:
		archive_set_error(&a->archive, ENOMEM,
		    "Out of memory for deflate decompression");
		break;
	default:
		archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
		    "Deflate decompression failed (%d)", r);
		break;
	}
	*avail = ARCHIVE_FATAL;
	return (NULL);
nomszip:
	archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
	    "CFDATA incorrect(no MSZIP signature)");
	*avail = ARCHIVE_FATAL;
	return (NULL);
}

#else /* HAVE_ZLIB_H */

static const void *
cab_read_ahead_cfdata_deflate(struct archive_read *a, ssize_t *avail)
{
	*avail = ARCHIVE_FATAL;
	archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
	    "libarchive compiled without deflate support (no libz)");
	return (NULL);
}

#endif /* HAVE_ZLIB_H */

static const void *
cab_read_ahead_cfdata_lzx(struct archive_read *a, ssize_t *avail)
{
	struct cab *cab = a->format->data;
	struct cfdata *cfdata;
	const void *d;
	int r;
	uint16_t uavail;

	cfdata = cab->entry_cfdata;
	/* If the buffer hasn't been allocated, allocate it now. */
	if (cab->uncompressed_buffer == NULL) {
		cab->uncompressed_buffer_size = MAX_UNCOMPRESS_SIZE;
		cab->uncompressed_buffer
		    = malloc(cab->uncompressed_buffer_size);
		if (cab->uncompressed_buffer == NULL) {
			archive_set_error(&a->archive, ENOMEM,
			    "No memory for CAB reader");
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
	}

	uavail = cfdata->uncompressed_avail;
	if (uavail == cfdata->uncompressed_size) {
		d = cab->uncompressed_buffer + cfdata->read_offset;
		*avail = uavail - cfdata->read_offset;
		return (d);
	}

	if (!cab->entry_cffolder->decompress_init) {
		r = lzx_decode_init(&cab->xstrm,
		    cab->entry_cffolder->compdata);
		if (r != ARCHIVE_OK) {
			archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
			    "Can't initialize LZX decompression");
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
		/* We've initialized decompression for this stream. */
		cab->entry_cffolder->decompress_init = 1;
	}

	/* Clean up remaining bits of previous CFDATA. */
	lzx_cleanup_bitstream(&cab->xstrm);
	cab->xstrm.total_out = uavail;
	while (cab->xstrm.total_out < cfdata->uncompressed_size) {
		ssize_t bytes_avail;

		cab->xstrm.next_out =
		    cab->uncompressed_buffer + cab->xstrm.total_out;
		cab->xstrm.avail_out =
		    cfdata->uncompressed_size - cab->xstrm.total_out;

		d = __archive_read_ahead(a, 1, &bytes_avail);
		if (d == NULL) {
			archive_set_error(&a->archive,
			    ARCHIVE_ERRNO_FILE_FORMAT,
			    "Truncated CAB file data");
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
		if (bytes_avail > cfdata->compressed_bytes_remaining)
			bytes_avail = cfdata->compressed_bytes_remaining;

		cab->xstrm.next_in = d;
		cab->xstrm.avail_in = bytes_avail;
		cab->xstrm.total_in = 0;
		r = lzx_decode(&cab->xstrm,
		    cfdata->compressed_bytes_remaining == bytes_avail);
		switch (r) {
		case ARCHIVE_OK:
		case ARCHIVE_EOF:
			break;
		default:
			archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
			    "LZX decompression failed (%d)", r);
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
		cfdata->unconsumed = cab->xstrm.total_in;
		cfdata->sum_ptr = d;
		if (cab_minimum_consume_cfdata(a, cfdata->unconsumed) < 0) {
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
	}

	uavail = (uint16_t)cab->xstrm.total_out;
	/*
	 * Make sure a read pointer advances to next CFDATA.
	 */
	if (cfdata->compressed_bytes_remaining > 0) {
		d = __archive_read_ahead(a, cfdata->compressed_bytes_remaining,
		    NULL);
		if (d == NULL) {
			*avail = truncated_error(a);
			return (NULL);
		}
		cfdata->unconsumed = cfdata->compressed_bytes_remaining;
		cfdata->sum_ptr = d;
		if (cab_minimum_consume_cfdata(a, cfdata->unconsumed) < 0) {
			*avail = ARCHIVE_FATAL;
			return (NULL);
		}
	}

	/*
	 * Translation reversal of x86 processor CALL byte sequence(E8).
	 */
	lzx_translation(&cab->xstrm, cab->uncompressed_buffer,
	    cfdata->uncompressed_size,
	    (cab->entry_cffolder->cfdata_index - 1) * MAX_UNCOMPRESS_SIZE);

	d = cab->uncompressed_buffer + cfdata->read_offset;
	*avail = uavail - cfdata->read_offset;
	cfdata->uncompressed_avail = uavail;

	return (d);
}

/*
 * Consume CFDATA.
 * We always decompress CFDATA to consume CFDATA as much as we need
 * in uncompressed bytes because all CFDATA in a folder are related
 * so we do not skip any CFDATA without decompressing.
 * Note: If the folder of a CFFILE is iFoldCONTINUED_PREV_AND_NEXT or
 * iFoldCONTINUED_FROM_PREV, we won't decompress because a CFDATA for
 * the CFFILE is remaining bytes of previous Multivolume CAB file.
 */
static int64_t
cab_consume_cfdata(struct archive_read *a, int64_t consumed_bytes)
{
	struct cab *cab = a->format->data;
	struct cfdata *cfdata;
	int64_t cbytes, rbytes;
	int err;

	rbytes = cab_minimum_consume_cfdata(a, consumed_bytes);
	if (rbytes < 0)
		return (ARCHIVE_FATAL);

	cfdata = cab->entry_cfdata;
	while (rbytes > 0) {
		ssize_t avail;

		if (cfdata->compressed_size == 0) {
			archive_set_error(&a->archive,
			    ARCHIVE_ERRNO_FILE_FORMAT,
			    "Invalid CFDATA");
			return (ARCHIVE_FATAL);
		}
		cbytes = cfdata->uncompressed_bytes_remaining;
		if (cbytes > rbytes)
			cbytes = rbytes;
		rbytes -= cbytes;

		if (cfdata->uncompressed_avail == 0 &&
		   (cab->entry_cffile->folder == iFoldCONTINUED_PREV_AND_NEXT ||
		    cab->entry_cffile->folder == iFoldCONTINUED_FROM_PREV)) {
			/* We have not read any data yet. */
			if (cbytes == cfdata->uncompressed_bytes_remaining) {
				/* Skip whole current CFDATA. */
				__archive_read_consume(a,
				    cfdata->compressed_size);
				cab->cab_offset += cfdata->compressed_size;
				cfdata->compressed_bytes_remaining = 0;
				cfdata->uncompressed_bytes_remaining = 0;
				err = cab_next_cfdata(a);
				if (err < 0)
					return (err);
				cfdata = cab->entry_cfdata;
				if (cfdata->uncompressed_size == 0) {
					switch (cab->entry_cffile->folder) {
					case iFoldCONTINUED_PREV_AND_NEXT:
					case iFoldCONTINUED_TO_NEXT:
					case iFoldCONTINUED_FROM_PREV:
						rbytes = 0;
						break;
					default:
						break;
					}
				}
				continue;
			}
			cfdata->read_offset += (uint16_t)cbytes;
			cfdata->uncompressed_bytes_remaining -= (uint16_t)cbytes;
			break;
		} else if (cbytes == 0) {
			err = cab_next_cfdata(a);
			if (err < 0)
				return (err);
			cfdata = cab->entry_cfdata;
			if (cfdata->uncompressed_size == 0) {
				switch (cab->entry_cffile->folder) {
				case iFoldCONTINUED_PREV_AND_NEXT:
				case iFoldCONTINUED_TO_NEXT:
				case iFoldCONTINUED_FROM_PREV:
					return (ARCHIVE_FATAL);
				default:
					break;
				}
			}
			continue;
		}
		while (cbytes > 0) {
			(void)cab_read_ahead_cfdata(a, &avail);
			if (avail <= 0)
				return (ARCHIVE_FATAL);
			if (avail > cbytes)
				avail = (ssize_t)cbytes;
			if (cab_minimum_consume_cfdata(a, avail) < 0)
				return (ARCHIVE_FATAL);
			cbytes -= avail;
		}
	}
	return (consumed_bytes);
}

/*
 * Consume CFDATA as much as we have already gotten and
 * compute the sum of CFDATA.
 */
static int64_t
cab_minimum_consume_cfdata(struct archive_read *a, int64_t consumed_bytes)
{
	struct cab *cab = a->format->data;
	struct cfdata *cfdata;
	int64_t cbytes, rbytes;
	int err;

	cfdata = cab->entry_cfdata;
	rbytes = consumed_bytes;
	if (cab->entry_cffolder->comptype == COMPTYPE_NONE) {
		if (consumed_bytes < cfdata->unconsumed)
			cbytes = consumed_bytes;
		else
			cbytes = cfdata->unconsumed;
		rbytes -= cbytes;
		cfdata->read_offset += (uint16_t)cbytes;
		cfdata->uncompressed_bytes_remaining -= (uint16_t)cbytes;
		cfdata->unconsumed -= cbytes;
	} else {
		cbytes = cfdata->uncompressed_avail - cfdata->read_offset;
		if (cbytes > 0) {
			if (consumed_bytes < cbytes)
				cbytes = consumed_bytes;
			rbytes -= cbytes;
			cfdata->read_offset += (uint16_t)cbytes;
			cfdata->uncompressed_bytes_remaining -= (uint16_t)cbytes;
		}

		if (cfdata->unconsumed) {
			cbytes = cfdata->unconsumed;
			cfdata->unconsumed = 0;
		} else
			cbytes = 0;
	}
	if (cbytes) {
		/* Compute the sum. */
		cab_checksum_update(a, (size_t)cbytes);

		/* Consume as much as the compressor actually used. */
		__archive_read_consume(a, cbytes);
		cab->cab_offset += cbytes;
		cfdata->compressed_bytes_remaining -= (uint16_t)cbytes;
		if (cfdata->compressed_bytes_remaining == 0) {
			err = cab_checksum_finish(a);
			if (err < 0)
				return (err);
		}
	}
	return (rbytes);
}

/*
 * Returns ARCHIVE_OK if successful, ARCHIVE_FATAL otherwise, sets
 * cab->end_of_entry if it consumes all of the data.
 */
static int
cab_read_data(struct archive_read *a, const void **buff,
    size_t *size, int64_t *offset)
{
	struct cab *cab = a->format->data;
	ssize_t bytes_avail;

	if (cab->entry_bytes_remaining == 0) {
		*buff = NULL;
		*size = 0;
		*offset = cab->entry_offset;
		cab->end_of_entry = 1;
		return (ARCHIVE_OK);
	}

	*buff = cab_read_ahead_cfdata(a, &bytes_avail);
	if (bytes_avail <= 0) {
		*buff = NULL;
		*size = 0;
		*offset = 0;
		if (bytes_avail == 0 &&
		    cab->entry_cfdata->uncompressed_size == 0) {
			/* All of CFDATA in a folder has been handled. */
			archive_set_error(&a->archive,
			    ARCHIVE_ERRNO_FILE_FORMAT, "Invalid CFDATA");
			return (ARCHIVE_FATAL);
		} else
			return ((int)bytes_avail);
	}
	if (bytes_avail > cab->entry_bytes_remaining)
		bytes_avail = (ssize_t)cab->entry_bytes_remaining;

	*size = bytes_avail;
	*offset = cab->entry_offset;
	cab->entry_offset += bytes_avail;
	cab->entry_bytes_remaining -= bytes_avail;
	if (cab->entry_bytes_remaining == 0)
		cab->end_of_entry = 1;
	cab->entry_unconsumed = bytes_avail;
	if (cab->entry_cffolder->comptype == COMPTYPE_NONE) {
		/* Don't consume more than current entry used. */
		if (cab->entry_cfdata->unconsumed > cab->entry_unconsumed)
			cab->entry_cfdata->unconsumed = cab->entry_unconsumed;
	}
	return (ARCHIVE_OK);
}

static int
archive_read_format_cab_read_data_skip(struct archive_read *a)
{
	struct cab *cab = a->format->data;
	int64_t bytes_skipped;
	int r;

	if (cab->end_of_archive)
		return (ARCHIVE_EOF);

	if (!cab->read_data_invoked) {
		cab->bytes_skipped += cab->entry_bytes_remaining;
		cab->entry_bytes_remaining = 0;
		/* This entry is finished and done. */
		cab->end_of_entry_cleanup = cab->end_of_entry = 1;
		return (ARCHIVE_OK);
	}

	if (cab->entry_unconsumed) {
		/* Consume as much as the compressor actually used. */
		r = (int)cab_consume_cfdata(a, cab->entry_unconsumed);
		cab->entry_unconsumed = 0;
		if (r < 0)
			return (r);
	} else if (cab->entry_cfdata == NULL) {
		r = cab_next_cfdata(a);
		if (r < 0)
			return (r);
	}

	/* if we've already read to end of data, we're done. */
	if (cab->end_of_entry_cleanup)
		return (ARCHIVE_OK);

	/*
	 * If the length is at the beginning, we can skip the
	 * compressed data much more quickly.
	 */
	bytes_skipped = cab_consume_cfdata(a, cab->entry_bytes_remaining);
	if (bytes_skipped < 0)
		return (ARCHIVE_FATAL);

	/* If the compression type is none(uncompressed), we've already
	 * consumed data as much as the current entry size. */
	if (cab->entry_cffolder->comptype == COMPTYPE_NONE &&
	    cab->entry_cfdata != NULL)
		cab->entry_cfdata->unconsumed = 0;

	/* This entry is finished and done. */
	cab->end_of_entry_cleanup = cab->end_of_entry = 1;
	return (ARCHIVE_OK);
}

static int
archive_read_format_cab_cleanup(struct archive_read *a)
{
	struct cab *cab = a->format->data;
	struct cfheader *hd = &cab->cfheader;
	uint16_t i;

	if (hd->folder_array != NULL) {
		for (i = 0; i < hd->folder_count; i++)
			free(hd->folder_array[i].cfdata.memimage);
		free(hd->folder_array);
	}
	if (hd->file_array != NULL) {
		for (i = 0; i < cab->cfheader.file_count; i++)
			archive_string_free(&(hd->file_array[i].pathname));
		free(hd->file_array);
	}
#ifdef HAVE_ZLIB_H
	if (cab->stream_valid)
		inflateEnd(&cab->stream);
#endif
	lzx_decode_free(&cab->xstrm);
	archive_wstring_free(&cab->ws);
	free(cab->uncompressed_buffer);
	free(cab);
	a->format->data = NULL;
	return (ARCHIVE_OK);
}

/* Convert an MSDOS-style date/time into Unix-style time. */
static time_t
cab_dos_time(const char *p)
{
	int msTime, msDate;
	struct tm ts;

	msDate = archive_le16dec(p);
	msTime = archive_le16dec(p+2);

	memset(&ts, 0, sizeof(ts));
	ts.tm_year = ((msDate >> 9) & 0x7f) + 80;   /* Years since 1900. */
	ts.tm_mon = ((msDate >> 5) & 0x0f) - 1;     /* Month number.     */
	ts.tm_mday = msDate & 0x1f;		    /* Day of month.     */
	ts.tm_hour = (msTime >> 11) & 0x1f;
	ts.tm_min = (msTime >> 5) & 0x3f;
	ts.tm_sec = (msTime << 1) & 0x3e;
	ts.tm_isdst = -1;
	return (mktime(&ts));
}

/*****************************************************************
 *
 * LZX decompression code.
 *
 *****************************************************************/

/*
 * Initialize LZX decoder.
 *
 * Returns ARCHIVE_OK if initialization was successful.
 * Returns ARCHIVE_FAILED if w_bits has unsupported value.
 * Returns ARCHIVE_FATAL if initialization failed; memory allocation
 * error occurred.
 */
static int
lzx_decode_init(struct lzx_stream *strm, int w_bits)
{
	int base_inc[18];
	struct lzx_dec *ds;
	uint32_t base;
	uint16_t slot, w_size, w_slot;
	uint8_t footer;

	if (strm->ds == NULL) {
		strm->ds = calloc(1, sizeof(*strm->ds));
		if (strm->ds == NULL)
			return (ARCHIVE_FATAL);
	}
	ds = strm->ds;
	ds->error = ARCHIVE_FAILED;

	/* Allow bits from 15 (32 KiB) up to 21 (2 MiB) */
	if (w_bits < SLOT_BASE || w_bits > SLOT_MAX)
		return (ARCHIVE_FAILED);

	ds->error = ARCHIVE_FATAL;

	/*
	 * Alloc window
	 */
	w_size = ds->w_size;
	w_slot = slots[w_bits - SLOT_BASE];
	ds->w_size = 1U << w_bits;
	ds->w_mask = ds->w_size - 1;
	if (ds->w_buff == NULL || w_size != ds->w_size) {
		free(ds->w_buff);
		ds->w_buff = malloc(ds->w_size);
		if (ds->w_buff == NULL)
			return (ARCHIVE_FATAL);
		free(ds->pos_tbl);
		ds->pos_tbl = malloc(sizeof(ds->pos_tbl[0]) * w_slot);
		if (ds->pos_tbl == NULL)
			return (ARCHIVE_FATAL);
	}

	for (footer = 0; footer < 18; footer++)
		base_inc[footer] = 1 << footer;
	base = footer = 0;
	for (slot = 0; slot < w_slot; slot++) {
		int n;
		if (footer == 0)
			base = slot;
		else
			base += base_inc[footer];
		if (footer < 17) {
			footer = 0;
			for (n = base; n; n >>= 1)
				footer++;
			if (footer <= 2)
				footer = 0;
			else
				footer -= 2;
		}
		ds->pos_tbl[slot].base = base;
		ds->pos_tbl[slot].footer_bits = footer;
	}

	ds->w_pos = 0;
	ds->state = ST_RD_TRANSLATION;
	ds->br.cache_buffer = 0;
	ds->br.cache_avail = 0;
	ds->r0 = ds->r1 = ds->r2 = 1;

	/* Initialize aligned offset tree. */
	if (lzx_huffman_init(&(ds->at), 8, 8) != ARCHIVE_OK)
		return (ARCHIVE_FATAL);

	/* Initialize pre-tree. */
	if (lzx_huffman_init(&(ds->pt), 20, 10) != ARCHIVE_OK)
		return (ARCHIVE_FATAL);

	/* Initialize Main tree. */
	if (lzx_huffman_init(&(ds->mt), 256 + (w_slot << 3), 16)
	    != ARCHIVE_OK)
		return (ARCHIVE_FATAL);

	/* Initialize Length tree. */
	if (lzx_huffman_init(&(ds->lt), 249, 16) != ARCHIVE_OK)
		return (ARCHIVE_FATAL);

	ds->error = 0;

	return (ARCHIVE_OK);
}

/*
 * Release LZX decoder.
 */
static void
lzx_decode_free(struct lzx_stream *strm)
{

	if (strm->ds == NULL)
		return;
	free(strm->ds->w_buff);
	free(strm->ds->pos_tbl);
	lzx_huffman_free(&(strm->ds->at));
	lzx_huffman_free(&(strm->ds->pt));
	lzx_huffman_free(&(strm->ds->mt));
	lzx_huffman_free(&(strm->ds->lt));
	free(strm->ds);
	strm->ds = NULL;
}

/*
 * E8 Call Translation reversal.
 */
static void
lzx_translation(struct lzx_stream *strm, unsigned char *buffer, size_t size,
    int32_t offset)
{
	struct lzx_dec *ds = strm->ds;
	unsigned char *p, *end;

	if (!ds->translation || offset >= MAX_E8_TRANSLATION || size <= 10)
		return;

	p = buffer;
	end = buffer + size - 10;

	while (p < end && (p = memchr(p, 0xE8, end - p)) != NULL) {
		int32_t address, position;

		address = archive_le32dec(p + 1);
		position = offset + (p - buffer);

		if (address >= -position && address < ds->translation_size) {
			uint32_t relative;

			if (address >= 0)
				relative = address - position;
			else
				relative = address + ds->translation_size;

			archive_le32enc(p + 1, relative);
		}

		p += 5;
	}
}

/*
 * Bit stream reader.
 */
/* Check that the cache buffer has enough bits. */
#define lzx_br_has(br, n)	((br)->cache_avail >= n)
/* Get compressed data by bit. */
#define lzx_br_bits(br, n)				\
	(((uint32_t)((br)->cache_buffer >>		\
		((br)->cache_avail - (n)))) & cache_masks[n])
#define lzx_br_bits_forced(br, n)			\
	(((uint32_t)((br)->cache_buffer <<		\
		((n) - (br)->cache_avail))) & cache_masks[n])
/* Read ahead to make sure the cache buffer has enough compressed data we
 * will use.
 *  True  : completed, there is enough data in the cache buffer.
 *  False : we met that strm->next_in is empty, we have to get following
 *          bytes. */
#define lzx_br_read_ahead_0(strm, br, n)	\
	(lzx_br_has((br), (n)) || lzx_br_fillup(strm, br) == ARCHIVE_OK)
/*  True  : the cache buffer has some bits as much as we need.
 *  False : there are no enough bits in the cache buffer to be used,
 *          we have to get following bytes if we could. */
#define lzx_br_read_ahead(strm, br, n)	\
	(lzx_br_read_ahead_0((strm), (br), (n)) || lzx_br_has((br), (n)))

/* Notify how many bits we consumed. */
#define lzx_br_consume(br, n)	((br)->cache_avail -= (n))
#define lzx_br_consume_unaligned_bits(br) ((br)->cache_avail &= ~0x0f)

#define lzx_br_is_unaligned(br)	((br)->cache_avail & 0x0f)

static const uint32_t cache_masks[] = {
	0x00000000, 0x00000001, 0x00000003, 0x00000007,
	0x0000000F, 0x0000001F, 0x0000003F, 0x0000007F,
	0x000000FF, 0x000001FF, 0x000003FF, 0x000007FF,
	0x00000FFF, 0x00001FFF, 0x00003FFF, 0x00007FFF,
	0x0000FFFF, 0x0001FFFF, 0x0003FFFF, 0x0007FFFF,
	0x000FFFFF, 0x001FFFFF, 0x003FFFFF, 0x007FFFFF,
	0x00FFFFFF, 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF,
	0x0FFFFFFF, 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF,
	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
};

/*
 * Shift away used bits in the cache data and fill it up with following bits.
 * Call this when cache buffer does not have enough bits you need.
 *
 * Returns ARCHIVE_OK if the cache buffer is full.
 * Returns ARCHIVE_EOF if the cache buffer is not full; input buffer is empty.
 */
static int
lzx_br_fillup(struct lzx_stream *strm, struct lzx_br *br)
{
/*
 * x86 processor family can read misaligned data without an access error.
 */
	ssize_t n = CACHE_BITS - br->cache_avail;

	for (;;) {
		switch (n >> 4) {
		case 4:
			if (strm->avail_in >= 8) {
				br->cache_buffer =
				    ((uint64_t)strm->next_in[1]) << 56 |
				    ((uint64_t)strm->next_in[0]) << 48 |
				    ((uint64_t)strm->next_in[3]) << 40 |
				    ((uint64_t)strm->next_in[2]) << 32 |
				    ((uint32_t)strm->next_in[5]) << 24 |
				    ((uint32_t)strm->next_in[4]) << 16 |
				    ((uint32_t)strm->next_in[7]) << 8 |
				     (uint32_t)strm->next_in[6];
				strm->next_in += 8;
				strm->avail_in -= 8;
				br->cache_avail += 8 * 8;
				return (ARCHIVE_OK);
			}
			break;
		case 3:
			if (strm->avail_in >= 6) {
				br->cache_buffer =
		 		   (br->cache_buffer << 48) |
				    ((uint64_t)strm->next_in[1]) << 40 |
				    ((uint64_t)strm->next_in[0]) << 32 |
				    ((uint64_t)strm->next_in[3]) << 24 |
				    ((uint64_t)strm->next_in[2]) << 16 |
				    ((uint64_t)strm->next_in[5]) << 8 |
				     (uint64_t)strm->next_in[4];
				strm->next_in += 6;
				strm->avail_in -= 6;
				br->cache_avail += 6 * 8;
				return (ARCHIVE_OK);
			}
			break;
		case 0:
			/* We have enough compressed data in
			 * the cache buffer.*/
			return (ARCHIVE_EOF);
		default:
			break;
		}
		if (strm->avail_in < 2) {
			/* There is not enough compressed data to
			 * fill up the cache buffer. */
			if (strm->avail_in == 1) {
				br->odd = *strm->next_in++;
				strm->avail_in--;
				br->have_odd = 1;
			}
			return (ARCHIVE_EOF);
		}
		br->cache_buffer =
		   (br->cache_buffer << 16) |
		    archive_le16dec(strm->next_in);
		strm->next_in += 2;
		strm->avail_in -= 2;
		br->cache_avail += 16;
		n -= 16;
	}
}

static void
lzx_br_fixup(struct lzx_stream *strm, struct lzx_br *br)
{
	ssize_t n = CACHE_BITS - br->cache_avail;

	if (br->have_odd && n >= 16 && strm->avail_in > 0) {
		br->cache_buffer =
		   (br->cache_buffer << 16) |
		   ((uint16_t)(*strm->next_in)) << 8 | br->odd;
		strm->next_in++;
		strm->avail_in--;
		br->cache_avail += 16;
		br->have_odd = 0;
	}
}

static void
lzx_cleanup_bitstream(struct lzx_stream *strm)
{
	strm->ds->br.cache_avail = 0;
	strm->ds->br.have_odd = 0;
}

/*
 * Decode LZX.
 *
 * 1. Returns ARCHIVE_OK if output buffer or input buffer are empty.
 *    Please set available buffer and call this function again.
 * 2. Returns ARCHIVE_EOF if decompression has been completed.
 * 3. Returns ARCHIVE_FAILED if an error occurred; compressed data
 *    is broken or you do not set 'last' flag properly.
 */
static int
lzx_decode(struct lzx_stream *strm, int last)
{
	struct lzx_dec *ds = strm->ds;
	size_t avail_in;
	int r;

	if (ds->error)
		return (ds->error);

	avail_in = strm->avail_in;
	lzx_br_fixup(strm, &(ds->br));
	do {
		if (ds->state < ST_MAIN)
			r = lzx_read_blocks(strm, last);
		else {
			size_t bytes_written = strm->avail_out;

			r = lzx_decode_blocks(strm, last);
			bytes_written -= strm->avail_out;
			strm->next_out += bytes_written;
			strm->total_out += bytes_written;
		}
	} while (r == 100);
	strm->total_in += avail_in - strm->avail_in;
	return (r);
}

static int
lzx_read_blocks(struct lzx_stream *strm, int last)
{
	struct lzx_dec *ds = strm->ds;
	struct lzx_br *br = &(ds->br);
	int r;
	uint16_t i;

	for (;;) {
		switch (ds->state) {
		case ST_RD_TRANSLATION:
			if (!lzx_br_read_ahead(strm, br, 1)) {
				ds->state = ST_RD_TRANSLATION;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			}
			ds->translation = lzx_br_bits(br, 1);
			lzx_br_consume(br, 1);
			/* FALL THROUGH */
		case ST_RD_TRANSLATION_SIZE:
			if (ds->translation) {
				uint32_t v;

				if (!lzx_br_read_ahead(strm, br, 32)) {
					ds->state = ST_RD_TRANSLATION_SIZE;
					if (last)
						goto failed;
					return (ARCHIVE_OK);
				}
				v = lzx_br_bits(br, 16);
				lzx_br_consume(br, 16);
				v <<= 16;
				v |= lzx_br_bits(br, 16);
				if (v > MAX_FILE_SIZE)
					goto failed;
				ds->translation_size = (int32_t)v;
				lzx_br_consume(br, 16);
			}
			/* FALL THROUGH */
		case ST_RD_BLOCK_TYPE:
			if (!lzx_br_read_ahead(strm, br, 3)) {
				ds->state = ST_RD_BLOCK_TYPE;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			}
			ds->block_type = lzx_br_bits(br, 3);
			lzx_br_consume(br, 3);
			/* Check a block type. */
			switch (ds->block_type) {
			case VERBATIM_BLOCK:
			case ALIGNED_OFFSET_BLOCK:
			case UNCOMPRESSED_BLOCK:
				break;
			default:
				goto failed;/* Invalid */
			}
			/* FALL THROUGH */
		case ST_RD_BLOCK_SIZE:
			if (!lzx_br_read_ahead(strm, br, 24)) {
				ds->state = ST_RD_BLOCK_SIZE;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			}
			ds->block_size = lzx_br_bits(br, 8);
			lzx_br_consume(br, 8);
			ds->block_size <<= 16;
			ds->block_size |= lzx_br_bits(br, 16);
			lzx_br_consume(br, 16);
			if (ds->block_size == 0)
				goto failed;
			ds->block_bytes_avail = ds->block_size;
			if (ds->block_type != UNCOMPRESSED_BLOCK) {
				if (ds->block_type == VERBATIM_BLOCK)
					ds->state = ST_RD_VERBATIM;
				else
					ds->state = ST_RD_ALIGNED_OFFSET;
				break;
			}
			/* FALL THROUGH */
		case ST_RD_ALIGNMENT:
			/*
			 * Handle an Uncompressed Block.
			 */
			/* Skip padding to align following field on
			 * 16-bit boundary. */
			if (lzx_br_is_unaligned(br))
				lzx_br_consume_unaligned_bits(br);
			else {
				if (lzx_br_read_ahead(strm, br, 16))
					lzx_br_consume(br, 16);
				else {
					ds->state = ST_RD_ALIGNMENT;
					if (last)
						goto failed;
					return (ARCHIVE_OK);
				}
			}
			/* Preparation to read repeated offsets R0,R1 and R2. */
			ds->rbytes_avail = 0;
			ds->state = ST_RD_R0;
			/* FALL THROUGH */
		case ST_RD_R0:
		case ST_RD_R1:
		case ST_RD_R2:
			do {
				uint16_t u16;
				/* Drain bits in the cache buffer of
				 * bit-stream. */
				if (lzx_br_has(br, 32)) {
					u16 = lzx_br_bits(br, 16);
					lzx_br_consume(br, 16);
					archive_le16enc(ds->rbytes, u16);
					u16 = lzx_br_bits(br, 16);
					lzx_br_consume(br, 16);
					archive_le16enc(ds->rbytes+2, u16);
					ds->rbytes_avail = 4;
				} else if (lzx_br_has(br, 16)) {
					u16 = lzx_br_bits(br, 16);
					lzx_br_consume(br, 16);
					archive_le16enc(ds->rbytes, u16);
					ds->rbytes_avail = 2;
				}
				if (ds->rbytes_avail < 4 && ds->br.have_odd) {
					ds->rbytes[ds->rbytes_avail++] =
					    ds->br.odd;
					ds->br.have_odd = 0;
				}
				while (ds->rbytes_avail < 4) {
					if (strm->avail_in <= 0) {
						if (last)
							goto failed;
						return (ARCHIVE_OK);
					}
					ds->rbytes[ds->rbytes_avail++] =
					    *strm->next_in++;
					strm->avail_in--;
				}
				ds->rbytes_avail = 0;
				if (ds->state == ST_RD_R0) {
					ds->r0 = archive_le32dec(ds->rbytes);
					if (ds->r0 > (size_t)INT32_MAX)
						goto failed;
					ds->state = ST_RD_R1;
				} else if (ds->state == ST_RD_R1) {
					ds->r1 = archive_le32dec(ds->rbytes);
					if (ds->r1 > (size_t)INT32_MAX)
						goto failed;
					ds->state = ST_RD_R2;
				} else if (ds->state == ST_RD_R2) {
					ds->r2 = archive_le32dec(ds->rbytes);
					if (ds->r2 > (size_t)INT32_MAX)
						goto failed;
					/* We've gotten all repeated offsets. */
					ds->state = ST_COPY_UNCOMP1;
				}
			} while (ds->state != ST_COPY_UNCOMP1);
			/* FALL THROUGH */
		case ST_COPY_UNCOMP1:
			/*
			 * Copy bytes from next_in to next_out directly.
			 */
			while (ds->block_bytes_avail) {
				size_t l;

				if (strm->avail_out <= 0)
					/* Output buffer is empty. */
					return (ARCHIVE_OK);
				if (strm->avail_in <= 0) {
					/* Input buffer is empty. */
					if (last)
						goto failed;
					return (ARCHIVE_OK);
				}
				l = ds->block_bytes_avail;
				if (l > ds->w_size - ds->w_pos)
					l = ds->w_size - ds->w_pos;
				if (l > strm->avail_out)
					l = strm->avail_out;
				if (l > strm->avail_in)
					l = strm->avail_in;
				memcpy(strm->next_out, strm->next_in, l);
				memcpy(&(ds->w_buff[ds->w_pos]),
				    strm->next_in, l);
				strm->next_in += l;
				strm->avail_in -= l;
				strm->next_out += l;
				strm->avail_out -= l;
				strm->total_out += l;
				ds->w_pos = (ds->w_pos + l) & ds->w_mask;
				ds->block_bytes_avail -= l;
			}
			/* FALL THROUGH */
		case ST_COPY_UNCOMP2:
			/* Re-align; skip padding byte. */
			if (ds->block_size & 1) {
				if (strm->avail_in <= 0) {
					/* Input buffer is empty. */
					ds->state = ST_COPY_UNCOMP2;
					if (last)
						goto failed;
					return (ARCHIVE_OK);
				}
				strm->next_in++;
				strm->avail_in --;
			}
			/* This block ended. */
			ds->state = ST_RD_BLOCK_TYPE;
			return (ARCHIVE_EOF);
			/********************/
		case ST_RD_ALIGNED_OFFSET:
			/*
			 * Read Aligned offset tree.
			 */
			if (!lzx_br_read_ahead(strm, br, 3 * ds->at.symbol_count)) {
				ds->state = ST_RD_ALIGNED_OFFSET;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			}
			memset(ds->at.freq, 0, sizeof(ds->at.freq));
			for (i = 0; i < ds->at.symbol_count; i++) {
				ds->at.bitlen[i] = lzx_br_bits(br, 3);
				ds->at.freq[ds->at.bitlen[i]]++;
				lzx_br_consume(br, 3);
			}
			if (lzx_make_huffman_table(&ds->at) < 0)
				goto failed;
			/* FALL THROUGH */
		case ST_RD_VERBATIM:
			ds->loop = 0;
			/* FALL THROUGH */
		case ST_RD_PRE_MAIN_TREE_256:
			/*
			 * Read Pre-tree for first 256 elements of main tree.
			 */
			if (lzx_read_pre_tree(strm) < 0) {
				ds->state = ST_RD_PRE_MAIN_TREE_256;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			}
			if (lzx_make_huffman_table(&ds->pt) < 0)
				goto failed;
			ds->loop = 0;
			/* FALL THROUGH */
		case ST_MAIN_TREE_256:
			/*
			 * Get path lengths of first 256 elements of main tree.
			 */
			r = lzx_read_bitlen(strm, &ds->mt, 256);
			if (r == ARCHIVE_EOF) {
				ds->state = ST_MAIN_TREE_256;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			} else if (r < 0)
				goto failed;
			ds->loop = 0;
			/* FALL THROUGH */
		case ST_RD_PRE_MAIN_TREE_REM:
			/*
			 * Read Pre-tree for remaining elements of main tree.
			 */
			if (lzx_read_pre_tree(strm) < 0) {
				ds->state = ST_RD_PRE_MAIN_TREE_REM;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			}
			if (lzx_make_huffman_table(&ds->pt) < 0)
				goto failed;
			ds->loop = 256;
			/* FALL THROUGH */
		case ST_MAIN_TREE_REM:
			/*
			 * Get path lengths of remaining elements of main tree.
			 */
			r = lzx_read_bitlen(strm, &ds->mt, 0);
			if (r == ARCHIVE_EOF) {
				ds->state = ST_MAIN_TREE_REM;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			} else if (r < 0)
				goto failed;
			if (lzx_make_huffman_table(&ds->mt) < 0)
				goto failed;
			ds->loop = 0;
			/* FALL THROUGH */
		case ST_RD_PRE_LENGTH_TREE:
			/*
			 * Read Pre-tree for remaining elements of main tree.
			 */
			if (lzx_read_pre_tree(strm) < 0) {
				ds->state = ST_RD_PRE_LENGTH_TREE;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			}
			if (lzx_make_huffman_table(&ds->pt) < 0)
				goto failed;
			ds->loop = 0;
			/* FALL THROUGH */
		case ST_LENGTH_TREE:
			/*
			 * Get path lengths of remaining elements of main tree.
			 */
			r = lzx_read_bitlen(strm, &ds->lt, 0);
			if (r == ARCHIVE_EOF) {
				ds->state = ST_LENGTH_TREE;
				if (last)
					goto failed;
				return (ARCHIVE_OK);
			} else if (r < 0)
				goto failed;
			if (lzx_make_huffman_table(&ds->lt) < 0)
				goto failed;
			ds->state = ST_MAIN;
			return (100);
		}
	}
failed:
	return (ds->error = ARCHIVE_FAILED);
}

static int
lzx_decode_blocks(struct lzx_stream *strm, int last)
{
	struct lzx_dec *ds = strm->ds;
	struct lzx_br bre = ds->br;
	struct huffman *at = &(ds->at), *lt = &(ds->lt), *mt = &(ds->mt);
	const struct lzx_pos_tbl *pos_tbl = ds->pos_tbl;
	unsigned char *noutp = strm->next_out;
	unsigned char *endp = noutp + strm->avail_out;
	uint8_t *w_buff = ds->w_buff;
	uint8_t *at_bitlen = at->bitlen;
	uint8_t *lt_bitlen = lt->bitlen;
	uint8_t *mt_bitlen = mt->bitlen;
	size_t block_bytes_avail = ds->block_bytes_avail;
	uint8_t at_lookup_bits = at->lookup_bits;
	uint8_t lt_lookup_bits = lt->lookup_bits;
	uint8_t mt_lookup_bits = mt->lookup_bits;
	size_t copy_len = ds->copy_len, copy_pos = ds->copy_pos;
	size_t w_pos = ds->w_pos, w_mask = ds->w_mask, w_size = ds->w_size;
	uint8_t length_header = ds->length_header;
	uint8_t offset_bits = ds->offset_bits;
	uint16_t position_slot = ds->position_slot;
	size_t r0 = ds->r0, r1 = ds->r1, r2 = ds->r2;
	int state = ds->state;
	uint16_t c;
	uint8_t block_type = ds->block_type;

	for (;;) {
		switch (state) {
		case ST_MAIN:
			for (;;) {
				if (block_bytes_avail == 0) {
					/* This block ended. */
					ds->state = ST_RD_BLOCK_TYPE;
					ds->br = bre;
					ds->block_bytes_avail =
					    block_bytes_avail;
					ds->copy_len = copy_len;
					ds->copy_pos = copy_pos;
					ds->length_header = length_header;
					ds->position_slot = position_slot;
					ds->r0 = r0; ds->r1 = r1; ds->r2 = r2;
					ds->w_pos = w_pos;
					strm->avail_out = endp - noutp;
					return (ARCHIVE_EOF);
				}
				if (noutp >= endp)
					/* Output buffer is empty. */
					goto next_data;

				if (!lzx_br_read_ahead(strm, &bre,
				    mt_lookup_bits)) {
					if (!last)
						goto next_data;
					/* Remaining bits are less than
					 * maximum bits (mt.lookup_bits) but
					 * maybe it still remains as much as we
					 * need, so we should try to use it
					 * with dummy bits. */
					c = lzx_decode_huffman(mt,
					      lzx_br_bits_forced(
					        &bre, mt_lookup_bits));
					if (!lzx_br_has(&bre, mt_bitlen[c]))
						goto failed;/* Over read. */
					lzx_br_consume(&bre, mt_bitlen[c]);
				} else {
					c = lzx_decode_huffman(mt,
					      lzx_br_bits(&bre, mt_lookup_bits));
					lzx_br_consume(&bre, mt_bitlen[c]);
				}
				if (c > UCHAR_MAX)
					break;
				/*
				 * 'c' is exactly literal code.
				 */
				/* Save a decoded code to reference it
				 * afterward. */
				w_buff[w_pos] = c;
				w_pos = (w_pos + 1) & w_mask;
				/* Store the decoded code to output buffer. */
				*noutp++ = c;
				block_bytes_avail--;
			}
			/*
			 * Get a match code, its length and offset.
			 */
			c -= UCHAR_MAX + 1;
			length_header = c & 7;
			position_slot = c >> 3;
			/* FALL THROUGH */
		case ST_LENGTH:
			/*
			 * Get a length.
			 */
			if (length_header == 7) {
				if (!lzx_br_read_ahead(strm, &bre,
				    lt_lookup_bits)) {
					if (!last) {
						state = ST_LENGTH;
						goto next_data;
					}
					c = lzx_decode_huffman(lt,
					      lzx_br_bits_forced(
					        &bre, lt_lookup_bits));
					if (!lzx_br_has(&bre, lt_bitlen[c]))
						goto failed;/* Over read. */
					lzx_br_consume(&bre, lt_bitlen[c]);
				} else {
					c = lzx_decode_huffman(lt,
					    lzx_br_bits(&bre, lt_lookup_bits));
					lzx_br_consume(&bre, lt_bitlen[c]);
				}
				copy_len = c + 7 + 2;
			} else
				copy_len = length_header + 2;
			if (copy_len > block_bytes_avail)
				goto failed;
			/*
			 * Get an offset.
			 */
			switch (position_slot) {
			case 0: /* Use repeated offset 0. */
				copy_pos = r0;
				state = ST_REAL_POS;
				continue;
			case 1: /* Use repeated offset 1. */
				copy_pos = r1;
				/* Swap repeated offset. */
				r1 = r0;
				r0 = copy_pos;
				state = ST_REAL_POS;
				continue;
			case 2: /* Use repeated offset 2. */
				copy_pos = r2;
				/* Swap repeated offset. */
				r2 = r0;
				r0 = copy_pos;
				state = ST_REAL_POS;
				continue;
			default:
				offset_bits =
				    pos_tbl[position_slot].footer_bits;
				break;
			}
			/* FALL THROUGH */
		case ST_OFFSET:
			/*
			 * Get the offset, which is a distance from
			 * current window position.
			 */
			if (block_type == ALIGNED_OFFSET_BLOCK &&
			    offset_bits >= 3) {
				unsigned offbits = offset_bits - 3;

				if (!lzx_br_read_ahead(strm, &bre, offbits)) {
					state = ST_OFFSET;
					if (last)
						goto failed;
					goto next_data;
				}
				copy_pos = lzx_br_bits(&bre, offbits) << 3;

				/* Get an aligned number. */
				if (!lzx_br_read_ahead(strm, &bre,
				    offbits + at_lookup_bits)) {
					if (!last) {
						state = ST_OFFSET;
						goto next_data;
					}
					lzx_br_consume(&bre, offbits);
					c = lzx_decode_huffman(at,
					      lzx_br_bits_forced(&bre,
					        at_lookup_bits));
					if (!lzx_br_has(&bre, at_bitlen[c]))
						goto failed;/* Over read. */
					lzx_br_consume(&bre, at_bitlen[c]);
				} else {
					lzx_br_consume(&bre, offbits);
					c = lzx_decode_huffman(at,
					      lzx_br_bits(&bre, at_lookup_bits));
					lzx_br_consume(&bre, at_bitlen[c]);
				}
				/* Add an aligned number. */
				copy_pos += c;
			} else {
				if (!lzx_br_read_ahead(strm, &bre,
				    offset_bits)) {
					state = ST_OFFSET;
					if (last)
						goto failed;
					goto next_data;
				}
				copy_pos = lzx_br_bits(&bre, offset_bits);
				lzx_br_consume(&bre, offset_bits);
			}
			copy_pos += pos_tbl[position_slot].base - 2;

			/* Update repeated offset LRU queue. */
			r2 = r1;
			r1 = r0;
			r0 = copy_pos;
			/* FALL THROUGH */
		case ST_REAL_POS:
			/*
			 * Compute a real position in window.
			 */
			copy_pos = (w_pos - copy_pos) & w_mask;
			/* FALL THROUGH */
		case ST_COPY:
			/*
			 * Copy several bytes as extracted data from the window
			 * into the output buffer.
			 */
			for (;;) {
				const uint8_t *s;
				size_t l;

				l = copy_len;
				if (copy_pos > w_pos) {
					if (l > w_size - copy_pos)
						l = w_size - copy_pos;
				} else {
					if (l > w_size - w_pos)
						l = w_size - w_pos;
				}
				if (noutp + l >= endp)
					l = endp - noutp;
				s = w_buff + copy_pos;
				if (l >= 8 && ((copy_pos + l < w_pos)
				  || (w_pos + l < copy_pos))) {
					memcpy(w_buff + w_pos, s, l);
					memcpy(noutp, s, l);
				} else {
					uint8_t *d;
					size_t li;

					d = w_buff + w_pos;
					for (li = 0; li < l; li++)
						noutp[li] = d[li] = s[li];
				}
				noutp += l;
				copy_pos = (copy_pos + l) & w_mask;
				w_pos = (w_pos + l) & w_mask;
				block_bytes_avail -= l;
				if (copy_len <= l)
					/* A copy of current pattern ended. */
					break;
				copy_len -= l;
				if (noutp >= endp) {
					/* Output buffer is empty. */
					state = ST_COPY;
					goto next_data;
				}
			}
			state = ST_MAIN;
			break;
		}
	}
failed:
	return (ds->error = ARCHIVE_FAILED);
next_data:
	ds->br = bre;
	ds->block_bytes_avail = block_bytes_avail;
	ds->copy_len = copy_len;
	ds->copy_pos = copy_pos;
	ds->length_header = length_header;
	ds->offset_bits = offset_bits;
	ds->position_slot = position_slot;
	ds->r0 = r0; ds->r1 = r1; ds->r2 = r2;
	ds->state = state;
	ds->w_pos = w_pos;
	strm->avail_out = endp - noutp;
	return (ARCHIVE_OK);
}

static int
lzx_read_pre_tree(struct lzx_stream *strm)
{
	struct lzx_dec *ds = strm->ds;
	struct lzx_br *br = &(ds->br);
	uint16_t i;

	if (ds->loop == 0)
		memset(ds->pt.freq, 0, sizeof(ds->pt.freq));
	for (i = ds->loop; i < ds->pt.symbol_count; i++) {
		if (!lzx_br_read_ahead(strm, br, 4)) {
			ds->loop = i;
			return (ARCHIVE_EOF);
		}
		ds->pt.bitlen[i] = lzx_br_bits(br, 4);
		ds->pt.freq[ds->pt.bitlen[i]]++;
		lzx_br_consume(br, 4);
	}
	ds->loop = i;
	return (ARCHIVE_OK);
}

/*
 * Read a bunch of bit-lengths from pre-tree.
 */
static int
lzx_read_bitlen(struct lzx_stream *strm, struct huffman *d, uint16_t end)
{
	struct lzx_dec *ds = strm->ds;
	struct lzx_br *br = &(ds->br);
	int ret;
	uint16_t c, i, j, rbits, same;

	i = ds->loop;
	if (i == 0)
		memset(d->freq, 0, sizeof(d->freq));
	ret = ARCHIVE_EOF;
	if (end == 0)
		end = d->symbol_count;
	while (i < end) {
		ds->loop = i;
		if (!lzx_br_read_ahead(strm, br, (unsigned)ds->pt.lookup_bits))
			goto getdata;
		rbits = lzx_br_bits(br, ds->pt.lookup_bits);
		c = lzx_decode_huffman(&(ds->pt), rbits);
		switch (c) {
		case 17:/* several zero lengths, from 4 to 19. */
			if (!lzx_br_read_ahead(strm, br, ds->pt.bitlen[c] + 4U))
				goto getdata;
			lzx_br_consume(br, ds->pt.bitlen[c]);
			same = lzx_br_bits(br, 4) + 4;
			if (same > end - i)
				return (ARCHIVE_FATAL);
			lzx_br_consume(br, 4);
			for (j = 0; j < same; j++)
				d->bitlen[i++] = 0;
			break;
		case 18:/* many zero lengths, from 20 to 51. */
			if (!lzx_br_read_ahead(strm, br, ds->pt.bitlen[c] + 5U))
				goto getdata;
			lzx_br_consume(br, ds->pt.bitlen[c]);
			same = lzx_br_bits(br, 5) + 20;
			if (same > end - i)
				return (ARCHIVE_FATAL);
			lzx_br_consume(br, 5);
			memset(d->bitlen + i, 0, same);
			i += same;
			break;
		case 19:/* a few same lengths. */
			if (!lzx_br_read_ahead(strm, br,
			    ds->pt.bitlen[c] + 1U + ds->pt.lookup_bits))
				goto getdata;
			lzx_br_consume(br, ds->pt.bitlen[c]);
			same = lzx_br_bits(br, 1) + 4;
			if (same > end - i)
				return (ARCHIVE_FATAL);
			lzx_br_consume(br, 1);
			rbits = lzx_br_bits(br, ds->pt.lookup_bits);
			c = lzx_decode_huffman(&(ds->pt), rbits);
			lzx_br_consume(br, ds->pt.bitlen[c]);
			if (c > d->bitlen[i] + 17)
				return (ARCHIVE_FATAL);
			c = (d->bitlen[i] + 17 - c) % 17;
			for (j = 0; j < same; j++)
				d->bitlen[i++] = c;
			d->freq[c] += same;
			break;
		default:
			lzx_br_consume(br, ds->pt.bitlen[c]);
			if (c > d->bitlen[i] + 17)
				return (ARCHIVE_FATAL);
			c = (d->bitlen[i] + 17 - c) % 17;
			d->freq[c]++;
			d->bitlen[i++] = c;
			break;
		}
	}
	ret = ARCHIVE_OK;
getdata:
	ds->loop = i;
	return (ret);
}

static int
lzx_huffman_init(struct huffman *hf, uint16_t symbol_count, uint8_t tbl_bits)
{
	size_t tbl_size = (size_t)1 << tbl_bits;

	if (hf->bitlen == NULL || hf->symbol_count != symbol_count) {
		free(hf->bitlen);
		hf->bitlen = calloc(symbol_count, sizeof(hf->bitlen[0]));
		if (hf->bitlen == NULL)
			return (ARCHIVE_FATAL);
		hf->symbol_count = symbol_count;
	} else
		memset(hf->bitlen, 0, symbol_count * sizeof(hf->bitlen[0]));
	if (hf->tbl == NULL) {
		hf->tbl = calloc(tbl_size, sizeof(hf->tbl[0]));
		if (hf->tbl == NULL)
			return (ARCHIVE_FATAL);
		hf->tbl_bits = tbl_bits;
	} else
		memset(hf->tbl, 0, tbl_size * sizeof(hf->bitlen[0]));
	return (ARCHIVE_OK);
}

static void
lzx_huffman_free(struct huffman *hf)
{
	free(hf->bitlen);
	free(hf->tbl);
}

/*
 * Create a direct, expanded Huffman lookup table based on
 * canonical representation.
 */
static int
lzx_make_huffman_table(struct huffman *hf)
{
	uint16_t bitptn[17], weight[17];
	uint16_t *tbl;
	const uint8_t *bitlen;
	uint8_t maxbits = 0;
	uint32_t ptn;
	uint16_t i, symbol_count, w;

	/*
	 * Initialize bit patterns.
	 *
	 * Each bitptn element represents the smallest possible
	 * code sequence allowed. The weight represents the amount
	 * of lookup bit patterns covered by a code of this length.
	 *
	 * Example of a Huffman tree:
	 *
	 * idx | freq[idx]
	 * ----+----------
	 *   1 |         1
	 *   2 |         2
	 *
	 * The result will be:
	 *
	 * idx | bitptn[idx] | weight[idx]
	 * ----+-------------+------------
	 *   1 |      0x0000 |       32768
	 *   2 |      0x8000 |       16384
	 *
	 * This means that a code with bit length 1 will take 32768
	 * possible combinations starting with 0b0. Since one such code exists
	 * (freq[1] = 1), codes with bit length 2 must start with 0b1. Since
	 * two codes with bit length 2 exist (freq[2] = 2), no more codes can
	 * be added.
	 *
	 * In this example, maxbits will be 2 (longest code length is 2).
	 */
	ptn = 0;
	for (i = 1, w = 1 << 15; i <= 16; i++, w >>= 1) {
		bitptn[i] = ptn;
		weight[i] = w;
		if (hf->freq[i]) {
			ptn += hf->freq[i] * w;
			maxbits = i;
		}
	}
	/* Verify Kraft's inequality. */
	if (ptn != 0 && ptn != 0x10000)
		return (ARCHIVE_FATAL);

	/*
	 * Shrink codes to smallest size by removing extra bits after
	 * the actual code sequences as good as possible.
	 *
	 * Continuing the example above:
	 *
	 * idx | bitptn[idx] | weight[idx]
	 * ----+-------------+-------------
	 *   1 |      0x0000 |       32768
	 *   2 |      0x8000 |       16384
	 *
	 * As can be seen, a total of 65536 entries must be created even
	 * though 4 would be sufficient (indices 0b00 to 0b11). Right shift
	 * the pattern and divide weight as much as possible:
	 *
	 * idx | bitptn[idx] | weight[idx]
	 * ----+-------------+-------------
	 *   1 |      0x0000 |           2
	 *   2 |      0x0002 |           1
	 *
	 * Thus, the direct, expanded lookup table only needs 4 entries.
	 */
	if (maxbits < 16) {
		uint8_t ebits = 16 - maxbits;
		for (i = 1; i <= maxbits; i++) {
			bitptn[i] >>= ebits;
			weight[i] >>= ebits;
		}
	}

	/* Grow table if necessary. */
	if (maxbits > hf->tbl_bits) {
		size_t tbl_size;

		hf->tbl_bits = 16;
		tbl_size = (size_t)1 << hf->tbl_bits;

		free(hf->tbl);
		hf->tbl = calloc(tbl_size, sizeof(hf->tbl[0]));
		if (hf->tbl == NULL)
			return (ARCHIVE_FATAL);
	}
	hf->lookup_bits = maxbits;

	/*
	 * Construct the direct, expanded lookup table.
	 *
	 * Store each symbol in table for every possible bit patterns starting
	 * with their code.
	 *
	 * Following the example with len_avail being 4:
	 *
	 * idx | bitlen[idx]
	 * ----+------------
	 *   0 |           0
	 *   1 |           1
	 *   2 |           0
	 *   3 |           2
	 *   4 |           2
	 *
	 * The resulting table contains all used symbols (1, 3, 4) for up to
	 * max_len bit patterns:
	 *
	 *       idx | tbl[idx]
	 * ----------+---------
	 *  0 (0b00) |        1
	 *  1 (0b01) |        1
	 *  2 (0b10) |        3
	 *  3 (0b11) |        4
	 */
	tbl = hf->tbl;
	bitlen = hf->bitlen;
	symbol_count = hf->symbol_count;
	for (i = 0; i < symbol_count; i++) {
		uint16_t *p;
		uint16_t cnt;
		uint8_t len;

		if (bitlen[i] == 0)
			continue;
		/* Get a bit pattern */
		len = bitlen[i];
		if (len > maxbits)
			return (ARCHIVE_FATAL);
		ptn = bitptn[len];
		cnt = weight[len];
		/* Calculate next bit pattern */
		bitptn[len] = ptn + cnt;
		/* Update the table */
		p = tbl + ptn;
		while (cnt-- > 0)
			*p++ = i;
	}
	return (ARCHIVE_OK);
}

static uint16_t
lzx_decode_huffman(struct huffman *hf, uint16_t rbits)
{
	return hf->tbl[rbits];
}