[evolution-ews] Decompress the oal file and store it.
- From: Chenthill Palanisamy <pchen src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [evolution-ews] Decompress the oal file and store it.
- Date: Wed, 29 Jun 2011 11:57:44 +0000 (UTC)
commit 3678227ba5f92aaa5bbc0c722567d7220ef68e6b
Author: Chenthill Palanisamy <pchenthill novell com>
Date: Wed Jun 29 17:24:37 2011 +0530
Decompress the oal file and store it.
configure.ac | 1 +
src/addressbook/Makefile.am | 5 +-
src/addressbook/e-book-backend-ews-gal.c | 8 +-
src/addressbook/lzx/Makefile.am | 16 +
src/addressbook/lzx/ews-oal-decompress.c | 228 ++++++++++
src/addressbook/lzx/ews-oal-decompress.h | 31 ++
src/addressbook/lzx/lzx.h | 215 +++++++++
src/addressbook/lzx/lzxd.c | 711 ++++++++++++++++++++++++++++++
src/addressbook/lzx/readbits.h | 201 +++++++++
src/addressbook/lzx/readhuff.h | 174 ++++++++
10 files changed, 1586 insertions(+), 4 deletions(-)
---
diff --git a/configure.ac b/configure.ac
index 5329c41..863d784 100644
--- a/configure.ac
+++ b/configure.ac
@@ -268,6 +268,7 @@ src/server/libeews.pc
src/utils/Makefile
src/account-setup-eplugin/Makefile
src/addressbook/Makefile
+src/addressbook/lzx/Makefile
src/calendar/Makefile
src/camel/Makefile
po/Makefile.in
diff --git a/src/addressbook/Makefile.am b/src/addressbook/Makefile.am
index b4324e0..c02a26a 100644
--- a/src/addressbook/Makefile.am
+++ b/src/addressbook/Makefile.am
@@ -1,3 +1,5 @@
+SUBDIRS = lzx .
+
if ENABLE_GTK3
ebook_backend_LTLIBRARIES = libebookbackendews.la
else
@@ -27,9 +29,10 @@ libebookbackendews_la_SOURCES = \
e-book-backend-ews-gal.h \
e-book-backend-ews-factory.c
-libebookbackendews_la_LIBADD = \
+libebookbackendews_la_LIBADD = \
$(top_builddir)/src/server/libeews-1.2.la \
$(top_builddir)/src/utils/libewsutils.la \
+ $(top_builddir)/src/addressbook/lzx/liblzx.la \
$(LIBEBACKEND_LIBS) \
$(LIBEDATASERVER_LIBS) \
$(LIBEDATABOOK_LIBS) \
diff --git a/src/addressbook/e-book-backend-ews-gal.c b/src/addressbook/e-book-backend-ews-gal.c
index 5c75db2..b49bd2f 100644
--- a/src/addressbook/e-book-backend-ews-gal.c
+++ b/src/addressbook/e-book-backend-ews-gal.c
@@ -46,6 +46,7 @@
#include "libedata-book/e-data-book-view.h"
#include "e-book-backend-ews-gal.h"
#include "e-book-backend-sqlitedb.h"
+#include "lzx/ews-oal-decompress.h"
#include "e-ews-message.h"
#include "e-ews-connection.h"
@@ -226,9 +227,10 @@ ews_download_full_gal (EBookBackendEwsGal *cbews, EwsOALDetails *full, GCancella
cache_file = g_strdup_printf ("%s-%d", priv->folder_name, full->ver);
uncompress_file = g_build_filename (cache_dir, cache_file, NULL);
-// if (!ews_decompress_gal (comp_cache_file, uncompress_file, error))
-// goto exit;
-
+ if (!oal_decompress_v4_full_detail_file (comp_cache_file, uncompress_file, error))
+ goto exit;
+
+ g_print ("OAL file decompressed %s \n", uncompress_file);
exit:
if (comp_cache_file)
diff --git a/src/addressbook/lzx/Makefile.am b/src/addressbook/lzx/Makefile.am
new file mode 100644
index 0000000..fab9482
--- /dev/null
+++ b/src/addressbook/lzx/Makefile.am
@@ -0,0 +1,16 @@
+lib_LTLIBRARIES = liblzx.la
+
+liblzx_la_CPPFLAGS = \
+ $(AM_CPPFLAGS) \
+ $(GNOME_PLATFORM_CFLAGS)
+
+liblzx_la_SOURCES = \
+ lzx.h \
+ ews-oal-decompress.h \
+ lzxd.c \
+ ews-oal-decompress.c
+
+liblzx_la_LDFLAGS = $(NO_UNDEFINED)
+
+liblzx_la_LIBADD = \
+ $(GNOME_PLATFORM_LIBS)
diff --git a/src/addressbook/lzx/ews-oal-decompress.c b/src/addressbook/lzx/ews-oal-decompress.c
new file mode 100644
index 0000000..571838a
--- /dev/null
+++ b/src/addressbook/lzx/ews-oal-decompress.c
@@ -0,0 +1,228 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
+
+/* e-book-backend-ews.h - Ews contact backend.
+ *
+ * Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU Lesser General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program 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
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ */
+
+#include <sys/types.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <unistd.h>
+#include <glib.h>
+#include "lzx.h"
+#include "ews-oal-decompress.h"
+
+/* endian-neutral reading of little-endian data */
+#define __egi32(a,n) ( ((((unsigned char *) a)[n+3]) << 24) | \
+ ((((unsigned char *) a)[n+2]) << 16) | \
+ ((((unsigned char *) a)[n+1]) << 8) | \
+ ((((unsigned char *) a)[n+0])))
+#define EndGetI64(a) ((((unsigned long long int) __egi32(a,4)) << 32) | \
+ ((unsigned int) __egi32(a,0)))
+#define EndGetI32(a) __egi32(a,0)
+#define EndGetI16(a) ((((a)[1])<<8)|((a)[0]))
+
+typedef struct {
+ guint32 h_version;
+ guint32 l_version;
+ guint32 max_block_size;
+ guint32 target_size;
+} LzxHeader;
+
+typedef struct {
+ guint32 flags;
+ guint32 comp_size;
+ guint32 ucomp_size;
+} LzxBlockHeader;
+
+static gboolean
+read_uint32 (FILE *input, guint32 *val)
+{
+ gchar buf [4];
+
+ if (fread (buf, 1, 4, input) == 4) {
+ *val = EndGetI32 (buf);
+ return TRUE;
+ } else
+ return FALSE;
+}
+
+static LzxHeader *
+read_headers (FILE *input, GError **error)
+{
+ LzxHeader *lzx_h;
+ gboolean success;
+
+ lzx_h = g_new0 (LzxHeader, 1);
+
+ success = read_uint32 (input, &lzx_h->h_version);
+ if (!success)
+ goto exit;
+ success = read_uint32 (input, &lzx_h->l_version);
+ if (!success)
+ goto exit;
+
+ if (lzx_h->h_version != 0x00000003 || lzx_h->l_version != 0x00000001) {
+ g_free (lzx_h);
+ /* set the right domain later */
+ g_set_error_literal (error, g_quark_from_string ("lzx"), 1, "wrong version header");
+ return NULL;
+ }
+
+ success = read_uint32 (input, &lzx_h->max_block_size);
+ if (!success)
+ goto exit;
+ success = read_uint32 (input, &lzx_h->target_size);
+ if (!success)
+ goto exit;
+
+exit:
+ if (!success) {
+ /* set the right domain later */
+ g_set_error_literal (error, g_quark_from_string ("lzx"), 1, "Unable to read lzx main header");
+
+ g_free (lzx_h);
+ lzx_h = NULL;
+ }
+
+ return lzx_h;
+}
+
+static LzxBlockHeader *
+read_block_header (FILE *input, GError **error)
+{
+ LzxBlockHeader *lzx_b;
+ gboolean success;
+
+ lzx_b = g_new0 (LzxBlockHeader, 1);
+
+ success = read_uint32 (input, &lzx_b->flags);
+ if (!success)
+ goto exit;
+
+ success = read_uint32 (input, &lzx_b->comp_size);
+ if (!success)
+ goto exit;
+
+ success = read_uint32 (input, &lzx_b->ucomp_size);
+ if (!success)
+ goto exit;
+
+exit:
+ if (!success) {
+ /* set the right domain later */
+ g_set_error_literal (error, g_quark_from_string ("lzx"), 1, "Unable to read lzx block header");
+
+ g_free (lzx_b);
+ lzx_b = NULL;
+ }
+
+ return lzx_b;
+}
+
+gboolean
+oal_decompress_v4_full_detail_file (const gchar *filename, const gchar *output_filename, GError **error)
+{
+ LzxHeader *lzx_h;
+ guint total_decomp_size = 0;
+ FILE *input, *output;
+ gboolean ret = TRUE;
+ GError *err = NULL;
+
+ input = fopen (filename, "rb");
+ if (!input) {
+ g_set_error_literal (&err, g_quark_from_string ("lzx"), 1, "unable to open the input file");
+ goto exit;
+ }
+
+ output = fopen (output_filename, "wb");
+ if (!input) {
+ g_set_error_literal (&err, g_quark_from_string ("lzx"), 1, "unable to open the output file");
+ goto exit;
+ }
+
+ lzx_h = read_headers (input, &err);
+ if (!lzx_h)
+ goto exit;
+
+ /* TODO decompressing multiple lzx_blocks has not been tested yet. Will need to get a setup and test it. */
+ do {
+ LzxBlockHeader *lzx_b;
+ struct lzxd_stream *lzs;
+
+ lzx_b = read_block_header (input, &err);
+ if (err)
+ goto exit;
+
+ /* lzx_b points to 1, write it directly to file */
+ if (lzx_b->flags == 0) {
+ gchar *buffer = g_malloc0 (lzx_b->ucomp_size);
+
+ if (!(fread (buffer, 1, lzx_b->ucomp_size, input) == lzx_b->ucomp_size &&
+ fwrite (buffer, 1, lzx_b->ucomp_size, output) == lzx_b->ucomp_size)) {
+ g_set_error_literal (&err, g_quark_from_string ("lzx"), 1, "failed to write data in output file");
+ g_free (buffer);
+ goto exit;
+ }
+ g_free (buffer);
+ } else {
+
+ lzs = lzxd_init (input, output, 17, 0, 16, lzx_b->ucomp_size);
+ if (lzxd_decompress (lzs, lzs->length) != LZX_ERR_OK) {
+ g_set_error_literal (&err, g_quark_from_string ("lzx"), 1, "decompression failed");
+ /* set err */
+ goto exit;
+ }
+ }
+
+ total_decomp_size += lzx_b->ucomp_size;
+ g_free (lzx_b);
+ } while (total_decomp_size < lzx_h->target_size);
+
+exit:
+ if (err) {
+ ret = FALSE;
+ g_propagate_error (error, err);
+ }
+
+ fclose (input);
+ fclose (output);
+ g_free (lzx_h);
+
+ return ret;
+}
+
+/*
+int
+main (int argc, char *argv [])
+{
+ if (argc != 3) {
+ g_print ("Pass an lzx file and an output filename as argument \n");
+ return;
+ }
+ g_type_init ();
+ g_thread_init (NULL);
+
+ if (oal_decompress_v4_full_detail_file (argv [1], argv [2], NULL))
+ g_print ("Successfully decompressed \n");
+ else
+ g_print ("decompression failed \n");
+
+ return 0;
+} */
diff --git a/src/addressbook/lzx/ews-oal-decompress.h b/src/addressbook/lzx/ews-oal-decompress.h
new file mode 100644
index 0000000..cf07b58
--- /dev/null
+++ b/src/addressbook/lzx/ews-oal-decompress.h
@@ -0,0 +1,31 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
+
+/* ews-oal-decompress.h - Ews contact backend.
+ *
+ * Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU Lesser General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program 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
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ */
+
+#ifndef __EWS_OAL_DECOMPRESS_H__
+#define __EWS_OAL_DECOMPRESS_H__
+
+#include <glib.h>
+
+gboolean
+oal_decompress_v4_full_detail_file (const gchar *filename, const gchar *output_filename, GError **error);
+
+#endif
diff --git a/src/addressbook/lzx/lzx.h b/src/addressbook/lzx/lzx.h
new file mode 100644
index 0000000..ac96f5d
--- /dev/null
+++ b/src/addressbook/lzx/lzx.h
@@ -0,0 +1,215 @@
+/* This file is part of libmspack.
+ * (C) 2003-2004 Stuart Caie.
+ *
+ * The LZX method was created by Jonathan Forbes and Tomi Poutanen, adapted
+ * by Microsoft Corporation.
+ *
+ * libmspack is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Lesser General Public License (LGPL) version 2.1
+ *
+ * For further details, see the file COPYING.LIB distributed with libmspack
+ */
+
+#ifndef LZX_H
+#define LZX_H 1
+
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define D(x) do { printf("%s:%d (%s) \n",__FILE__, __LINE__, __func__); \
+ printf x ; fputc('\n', stdout); fflush(stdout);} while (0);
+
+/* LZX compression / decompression definitions */
+
+/* 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) /* table decoding overruns are allowed */
+
+#define LZX_FRAME_SIZE (32768) /* the size of a frame in LZX */
+
+/* --- error codes --------------------------------------------------------- */
+
+/** Error code: no error */
+#define LZX_ERR_OK (0)
+/** Error code: bad arguments to method */
+#define LZX_ERR_ARGS (1)
+/** Error code: error opening file */
+#define LZX_ERR_OPEN (2)
+/** Error code: error reading file */
+#define LZX_ERR_READ (3)
+/** Error code: error writing file */
+#define LZX_ERR_WRITE (4)
+/** Error code: seek error */
+#define LZX_ERR_SEEK (5)
+/** Error code: out of memory */
+#define LZX_ERR_NOMEMORY (6)
+/** Error code: bad "magic id" in file */
+#define LZX_ERR_SIGNATURE (7)
+/** Error code: bad or corrupt file format */
+#define LZX_ERR_DATAFORMAT (8)
+/** Error code: bad checksum or CRC */
+#define LZX_ERR_CHECKSUM (9)
+/** Error code: error during compression */
+#define LZX_ERR_CRUNCH (10)
+/** Error code: error during decompression */
+#define LZX_ERR_DECRUNCH (11)
+
+struct lzxd_stream {
+ FILE *input; /* input file handle */
+ FILE *output; /* output file handle */
+
+ off_t offset; /* number of bytes actually output */
+ off_t length; /* overall decompressed length of stream */
+
+ unsigned char *window; /* decoding window */
+ unsigned int window_size; /* window size */
+ unsigned int window_posn; /* decompression offset within window */
+ unsigned int frame_posn; /* current frame offset within in window */
+ unsigned int frame; /* the number of 32kb frames processed */
+ unsigned int reset_interval; /* which frame do we reset the compressor? */
+
+ unsigned int R0, R1, R2; /* for the LRU offset system */
+ unsigned int block_length; /* uncompressed length of this LZX block */
+ unsigned int block_remaining; /* uncompressed bytes still left to decode */
+
+ signed int intel_filesize; /* magic header value used for transform */
+ signed int intel_curpos; /* current offset in transform space */
+
+ unsigned char intel_started; /* has intel E8 decoding started? */
+ unsigned char block_type; /* type of the current block */
+ unsigned char header_read; /* have we started decoding at all yet? */
+ unsigned char posn_slots; /* how many posn slots in stream? */
+ unsigned char input_end; /* have we reached the end of input? */
+
+ int error;
+
+ /* I/O buffering */
+ unsigned char *inbuf, *i_ptr, *i_end, *o_ptr, *o_end;
+ unsigned int bit_buffer, bits_left, inbuf_size;
+
+ /* huffman code lengths */
+ unsigned char PRETREE_len [LZX_PRETREE_MAXSYMBOLS + LZX_LENTABLE_SAFETY];
+ unsigned char MAINTREE_len [LZX_MAINTREE_MAXSYMBOLS + LZX_LENTABLE_SAFETY];
+ unsigned char LENGTH_len [LZX_LENGTH_MAXSYMBOLS + LZX_LENTABLE_SAFETY];
+ unsigned char ALIGNED_len [LZX_ALIGNED_MAXSYMBOLS + LZX_LENTABLE_SAFETY];
+
+ /* huffman decoding tables */
+ unsigned short PRETREE_table [(1 << LZX_PRETREE_TABLEBITS) +
+ (LZX_PRETREE_MAXSYMBOLS * 2)];
+ unsigned short MAINTREE_table[(1 << LZX_MAINTREE_TABLEBITS) +
+ (LZX_MAINTREE_MAXSYMBOLS * 2)];
+ unsigned short LENGTH_table [(1 << LZX_LENGTH_TABLEBITS) +
+ (LZX_LENGTH_MAXSYMBOLS * 2)];
+ unsigned short ALIGNED_table [(1 << LZX_ALIGNED_TABLEBITS) +
+ (LZX_ALIGNED_MAXSYMBOLS * 2)];
+
+ /* this is used purely for doing the intel E8 transform */
+ unsigned char e8_buf[LZX_FRAME_SIZE];
+};
+
+/**
+ * Allocates and initialises LZX decompression state for decoding an LZX
+ * stream.
+ *
+ * This routine uses malloc() to allocate memory. If memory
+ * allocation fails, or the parameters to this function are invalid,
+ * NULL is returned.
+ *
+ * @param input an input stream with the LZX data.
+ * @param output an output stream to write the decoded data to.
+ * @param window_bits the size of the decoding window, which must be
+ * between 15 and 21 inclusive.
+ * @param reset_interval the interval at which the LZX bitstream is
+ * reset, in multiples of LZX frames (32678
+ * bytes), e.g. a value of 2 indicates the input
+ * stream resets after every 65536 output bytes.
+ * A value of 0 indicates that the bistream never
+ * resets, such as in CAB LZX streams.
+ * @param input_buffer_size the number of bytes to use as an input
+ * bitstream buffer.
+ * @param output_length the length in bytes of the entirely
+ * decompressed output stream, if known in
+ * advance. It is used to correctly perform the
+ * Intel E8 transformation, which must stop 6
+ * bytes before the very end of the
+ * decompressed stream. It is not otherwise used
+ * or adhered to. If the full decompressed
+ * length is known in advance, set it here.
+ * If it is NOT known, use the value 0, and call
+ * lzxd_set_output_length() once it is
+ * known. If never set, 4 of the final 6 bytes
+ * of the output stream may be incorrect.
+ * @return a pointer to an initialised lzxd_stream structure, or NULL if
+ * there was not enough memory or parameters to the function were wrong.
+ */
+extern struct lzxd_stream *lzxd_init(FILE *input,
+ FILE *output,
+ int window_bits,
+ int reset_interval,
+ int input_buffer_size,
+ off_t output_length);
+
+/* see description of output_length in lzxd_init() */
+extern void lzxd_set_output_length(struct lzxd_stream *lzx,
+ off_t output_length);
+
+/**
+ * Decompresses entire or partial LZX streams.
+ *
+ * The number of bytes of data that should be decompressed is given as the
+ * out_bytes parameter. If more bytes are decoded than are needed, they
+ * will be kept over for a later invocation.
+ *
+ * The output bytes will be passed to the write() function given in
+ * lzxd_init(), using the output file handle given in lzxd_init(). More than
+ * one call may be made to write().
+
+ * Input bytes will be read in as necessary using the read()
+ * function given in lzxd_init(), using the input file handle given in
+ * lzxd_init(). This will continue until read() returns 0 bytes,
+ * or an error. Errors will be passed out of the function as
+ * LZX_ERR_READ errors. Input streams should convey an "end of input
+ * stream" by refusing to supply all the bytes that LZX asks for when they
+ * reach the end of the stream, rather than return an error code.
+ *
+ * If any error code other than LZX_ERR_OK is returned, the stream
+ * should be considered unusable and lzxd_decompress() should not be
+ * called again on this stream.
+ *
+ * @param lzx LZX decompression state, as allocated by lzxd_init().
+ * @param out_bytes the number of bytes of data to decompress.
+ * @return an error code, or LZX_ERR_OK if successful
+ */
+extern int lzxd_decompress(struct lzxd_stream *lzx, off_t out_bytes);
+
+/**
+ * Frees all state associated with an LZX data stream. This will call
+ * free().
+ *
+ * @param lzx LZX decompression state to free.
+ */
+void lzxd_free(struct lzxd_stream *lzx);
+
+#endif
diff --git a/src/addressbook/lzx/lzxd.c b/src/addressbook/lzx/lzxd.c
new file mode 100644
index 0000000..19666b6
--- /dev/null
+++ b/src/addressbook/lzx/lzxd.c
@@ -0,0 +1,711 @@
+/* This file is part of libmspack.
+ * (C) 2003-2004 Stuart Caie.
+ *
+ * The LZX method was created by Jonathan Forbes and Tomi Poutanen, adapted
+ * by Microsoft Corporation.
+ *
+ * libmspack is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Lesser General Public License (LGPL) version 2.1
+ *
+ * For further details, see the file COPYING.LIB distributed with libmspack
+ */
+
+/* LZX decompression implementation */
+
+#include "lzx.h"
+
+/* Microsoft's LZX document (in cab-sdk.exe) 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 alignment
+ * 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.
+ *
+ * The errors in LZX documentation appear have been corrected in the
+ * new documentation for the LZX DELTA format.
+ *
+ * http://msdn.microsoft.com/en-us/library/cc483133.aspx
+ *
+ * However, this is a different format, an extension of regular LZX.
+ * I have noticed the following differences, there may be more:
+ *
+ * The maximum window size has increased from 2MB to 32MB. This also
+ * increases the maximum number of position slots, etc.
+ *
+ * The format now allows for "reference data", supplied by the caller.
+ * If match offsets go further back than the number of bytes
+ * decompressed so far, that is them accessing the reference data.
+ */
+
+/* import bit-reading macros and code */
+#define BITS_TYPE struct lzxd_stream
+#define BITS_VAR lzx
+#define BITS_ORDER_MSB
+#define READ_BYTES do { \
+ unsigned char b0, b1; \
+ READ_IF_NEEDED; b0 = *i_ptr++; \
+ READ_IF_NEEDED; b1 = *i_ptr++; \
+ INJECT_BITS((b1 << 8) | b0, 16); \
+} while (0)
+#include "readbits.h"
+
+/* import huffman-reading macros and code */
+#define TABLEBITS(tbl) LZX_##tbl##_TABLEBITS
+#define MAXSYMBOLS(tbl) LZX_##tbl##_MAXSYMBOLS
+#define HUFF_TABLE(tbl,idx) lzx->tbl##_table[idx]
+#define HUFF_LEN(tbl,idx) lzx->tbl##_len[idx]
+#define HUFF_ERROR return lzx->error = LZX_ERR_DECRUNCH
+#include "readhuff.h"
+
+/* BUILD_TABLE(tbl) builds a huffman lookup table from code lengths */
+#define BUILD_TABLE(tbl) \
+ if (make_decode_table(MAXSYMBOLS(tbl), TABLEBITS(tbl), \
+ &HUFF_LEN(tbl,0), &HUFF_TABLE(tbl,0))) \
+ { \
+ D(("failed to build %s table", #tbl)) \
+ return lzx->error = LZX_ERR_DECRUNCH; \
+ }
+
+/* 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 { \
+ STORE_BITS; \
+ if (lzxd_read_lens(lzx, &HUFF_LEN(tbl, 0), (first), \
+ (unsigned int)(last))) return lzx->error; \
+ RESTORE_BITS; \
+} while (0)
+
+static int lzxd_read_lens(struct lzxd_stream *lzx, unsigned char *lens,
+ unsigned int first, unsigned int last)
+{
+ /* bit buffer and huffman symbol decode variables */
+ register unsigned int bit_buffer;
+ register int bits_left, i;
+ register unsigned short sym;
+ unsigned char *i_ptr, *i_end;
+
+ unsigned int x, y;
+ int z;
+
+ RESTORE_BITS;
+
+ /* read lengths for pretree (20 symbols, lengths stored in fixed 4 bits) */
+ for (x = 0; x < 20; x++) {
+ READ_BITS(y, 4);
+ lzx->PRETREE_len[x] = y;
+ }
+ BUILD_TABLE(PRETREE);
+
+ for (x = first; x < last; ) {
+ READ_HUFFSYM(PRETREE, z);
+ if (z == 17) {
+ /* code = 17, run of ([read 4 bits]+4) zeros */
+ READ_BITS(y, 4); y += 4;
+ while (y--) lens[x++] = 0;
+ }
+ else if (z == 18) {
+ /* code = 18, run of ([read 5 bits]+20) zeros */
+ READ_BITS(y, 5); y += 20;
+ while (y--) lens[x++] = 0;
+ }
+ else if (z == 19) {
+ /* code = 19, run of ([read 1 bit]+4) [read huffman symbol] */
+ 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 {
+ /* code = 0 to 16, delta current length entry */
+ z = lens[x] - z; if (z < 0) z += 17;
+ lens[x++] = z;
+ }
+ }
+
+ STORE_BITS;
+
+ return LZX_ERR_OK;
+}
+
+/* LZX static data tables:
+ *
+ * LZX uses 'position slots' to represent match offsets. For every match,
+ * a small 'position slot' number and a small offset from that slot are
+ * encoded instead of one large offset.
+ *
+ * position_base[] is an index to the position slot bases
+ *
+ * extra_bits[] states how many bits of offset-from-base data is needed.
+ *
+ * They are generated like so:
+ * for (i = 0; i < 4; i++) extra_bits[i] = 0;
+ * for (i = 4, j = 0; i < 36; i+=2) extra_bits[i] = extra_bits[i+1] = j++;
+ * for (i = 36; i < 51; i++) extra_bits[i] = 17;
+ * for (i = 0, j = 0; i < 51; j += 1 << extra_bits[i++]) position_base[i] = j;
+ */
+static const unsigned int position_base[51] = {
+ 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256,
+ 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288,
+ 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144,
+ 393216, 524288, 655360, 786432, 917504, 1048576, 1179648, 1310720,
+ 1441792, 1572864, 1703936, 1835008, 1966080, 2097152
+};
+static const unsigned char extra_bits[51] = {
+ 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
+ 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16,
+ 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17
+};
+
+static void lzxd_reset_state(struct lzxd_stream *lzx) {
+ int i;
+
+ lzx->R0 = 1;
+ lzx->R1 = 1;
+ lzx->R2 = 1;
+ lzx->header_read = 0;
+ lzx->block_remaining = 0;
+ lzx->block_type = LZX_BLOCKTYPE_INVALID;
+
+ /* initialise tables to 0 (because deltas will be applied to them) */
+ for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) lzx->MAINTREE_len[i] = 0;
+ for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) lzx->LENGTH_len[i] = 0;
+}
+
+/*-------- main LZX code --------*/
+
+struct lzxd_stream *lzxd_init(FILE *input,
+ FILE *output,
+ int window_bits,
+ int reset_interval,
+ int input_buffer_size,
+ off_t output_length)
+{
+ unsigned int window_size = 1 << window_bits;
+ struct lzxd_stream *lzx;
+
+ /* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */
+ if (window_bits < 15 || window_bits > 21) return NULL;
+
+ input_buffer_size = (input_buffer_size + 1) & -2;
+ if (!input_buffer_size) return NULL;
+
+ /* allocate decompression state */
+ if (!(lzx = malloc(sizeof(struct lzxd_stream)))) {
+ return NULL;
+ }
+
+ /* allocate decompression window and input buffer */
+ lzx->window = malloc((size_t) window_size);
+ lzx->inbuf = malloc((size_t) input_buffer_size);
+ if (!lzx->window || !lzx->inbuf) {
+ free(lzx->window);
+ free(lzx->inbuf);
+ free(lzx);
+ return NULL;
+ }
+
+ /* initialise decompression state */
+ lzx->input = input;
+ lzx->output = output;
+ lzx->offset = 0;
+ lzx->length = output_length;
+
+ lzx->inbuf_size = input_buffer_size;
+ lzx->window_size = 1 << window_bits;
+ lzx->window_posn = 0;
+ lzx->frame_posn = 0;
+ lzx->frame = 0;
+ lzx->reset_interval = reset_interval;
+ lzx->intel_filesize = 0;
+ lzx->intel_curpos = 0;
+ lzx->intel_started = 0;
+ lzx->error = LZX_ERR_OK;
+
+ /* window bits: 15 16 17 18 19 20 21
+ * position slots: 30 32 34 36 38 42 50 */
+ lzx->posn_slots = ((window_bits == 21) ? 50 :
+ ((window_bits == 20) ? 42 : (window_bits << 1)));
+
+ lzx->o_ptr = lzx->o_end = &lzx->e8_buf[0];
+ lzxd_reset_state(lzx);
+ INIT_BITS;
+ return lzx;
+}
+
+void lzxd_set_output_length(struct lzxd_stream *lzx, off_t out_bytes) {
+ if (lzx) lzx->length = out_bytes;
+}
+
+int lzxd_decompress(struct lzxd_stream *lzx, off_t out_bytes) {
+ /* bitstream and huffman reading variables */
+ register unsigned int bit_buffer;
+ register int bits_left, i=0;
+ unsigned char *i_ptr, *i_end;
+ register unsigned short sym;
+
+ int match_length, length_footer, extra, verbatim_bits, bytes_todo;
+ int this_run, main_element, aligned_bits, j;
+ unsigned char *window, *runsrc, *rundest, buf[12];
+ unsigned int frame_size=0, end_frame, match_offset, window_posn;
+ unsigned int R0, R1, R2;
+
+ /* easy answers */
+ if (!lzx || (out_bytes < 0)) return LZX_ERR_ARGS;
+ if (lzx->error) return lzx->error;
+
+ /* flush out any stored-up bytes before we begin */
+ i = lzx->o_end - lzx->o_ptr;
+ if ((off_t) i > out_bytes) i = (int) out_bytes;
+ if (i) {
+ if (fwrite(lzx->o_ptr, 1, i, lzx->output) != i) {
+ return lzx->error = LZX_ERR_WRITE;
+ }
+ lzx->o_ptr += i;
+ lzx->offset += i;
+ out_bytes -= i;
+ }
+ if (out_bytes == 0) return LZX_ERR_OK;
+
+ /* restore local state */
+ RESTORE_BITS;
+ window = lzx->window;
+ window_posn = lzx->window_posn;
+ R0 = lzx->R0;
+ R1 = lzx->R1;
+ R2 = lzx->R2;
+
+ end_frame = (unsigned int)((lzx->offset + out_bytes) / LZX_FRAME_SIZE) + 1;
+
+ while (lzx->frame < end_frame) {
+ /* have we reached the reset interval? (if there is one?) */
+ if (lzx->reset_interval && ((lzx->frame % lzx->reset_interval) == 0)) {
+ if (lzx->block_remaining) {
+ D(("%d bytes remaining at reset interval", lzx->block_remaining))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+
+ /* re-read the intel header and reset the huffman lengths */
+ lzxd_reset_state(lzx);
+ R0 = lzx->R0;
+ R1 = lzx->R1;
+ R2 = lzx->R2;
+ }
+
+ /* LZXD format has the chunk_size. not present in lzx format */
+ READ_BITS (i, 16);
+ D(("chunk size is %d \n", i))
+
+ /* read header if necessary */
+ if (!lzx->header_read) {
+ /* read 1 bit. if bit=0, intel filesize = 0.
+ * if bit=1, read intel filesize (32 bits) */
+ j = 0; READ_BITS(i, 1); if (i) { READ_BITS(i, 16); READ_BITS(j, 16); }
+ lzx->intel_filesize = (i << 16) | j;
+ lzx->header_read = 1;
+ }
+
+ /* calculate size of frame: all frames are 32k except the final frame
+ * which is 32kb or less. this can only be calculated when lzx->length
+ * has been filled in. */
+ frame_size = LZX_FRAME_SIZE;
+ if (lzx->length && (lzx->length - lzx->offset) < (off_t)frame_size) {
+ frame_size = lzx->length - lzx->offset;
+ }
+
+ /* decode until one more frame is available */
+ bytes_todo = lzx->frame_posn + frame_size - window_posn;
+ while (bytes_todo > 0) {
+ /* initialise new block, if one is needed */
+ if (lzx->block_remaining == 0) {
+ /* realign if previous block was an odd-sized UNCOMPRESSED block */
+ if ((lzx->block_type == LZX_BLOCKTYPE_UNCOMPRESSED) &&
+ (lzx->block_length & 1))
+ {
+ READ_IF_NEEDED;
+ i_ptr++;
+ }
+
+ /* read block type (3 bits) and block length (24 bits) */
+ READ_BITS(lzx->block_type, 3);
+ READ_BITS(i, 16); READ_BITS(j, 8);
+ lzx->block_remaining = lzx->block_length = (i << 8) | j;
+ /*D(("new block t%d len %u", lzx->block_type, lzx->block_length))*/
+
+ /* read individual block headers */
+ switch (lzx->block_type) {
+ case LZX_BLOCKTYPE_ALIGNED:
+ /* read lengths of and build aligned huffman decoding tree */
+ for (i = 0; i < 8; i++) { READ_BITS(j, 3); lzx->ALIGNED_len[i] = j; }
+ BUILD_TABLE(ALIGNED);
+ /* no break -- rest of aligned header is same as verbatim */
+ case LZX_BLOCKTYPE_VERBATIM:
+ /* read lengths of and build main huffman decoding tree */
+ READ_LENGTHS(MAINTREE, 0, 256);
+ READ_LENGTHS(MAINTREE, 256, LZX_NUM_CHARS + (lzx->posn_slots << 3));
+ BUILD_TABLE(MAINTREE);
+ /* if the literal 0xE8 is anywhere in the block... */
+ if (lzx->MAINTREE_len[0xE8] != 0) lzx->intel_started = 1;
+ /* read lengths of and build lengths huffman decoding tree */
+ READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS);
+ BUILD_TABLE(LENGTH);
+ break;
+
+ case LZX_BLOCKTYPE_UNCOMPRESSED:
+ /* because we can't assume otherwise */
+ lzx->intel_started = 1;
+
+ /* read 1-16 (not 0-15) bits to align to bytes */
+ ENSURE_BITS(16);
+ if (bits_left > 16) i_ptr -= 2;
+ bits_left = 0; bit_buffer = 0;
+
+ /* read 12 bytes of stored R0 / R1 / R2 values */
+ for (rundest = &buf[0], i = 0; i < 12; i++) {
+ READ_IF_NEEDED;
+ *rundest++ = *i_ptr++;
+ }
+ R0 = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24);
+ R1 = buf[4] | (buf[5] << 8) | (buf[6] << 16) | (buf[7] << 24);
+ R2 = buf[8] | (buf[9] << 8) | (buf[10] << 16) | (buf[11] << 24);
+ break;
+
+ default:
+ D(("bad block type \n"))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+ }
+
+ /* decode more of the block:
+ * run = min(what's available, what's needed) */
+ this_run = lzx->block_remaining;
+ if (this_run > bytes_todo) this_run = bytes_todo;
+
+ /* assume we decode exactly this_run bytes, for now */
+ bytes_todo -= this_run;
+ lzx->block_remaining -= this_run;
+
+ /* decode at least this_run bytes */
+ switch (lzx->block_type) {
+ case LZX_BLOCKTYPE_VERBATIM:
+ while (this_run > 0) {
+ READ_HUFFSYM(MAINTREE, main_element);
+ if (main_element < LZX_NUM_CHARS) {
+ /* literal: 0 to LZX_NUM_CHARS-1 */
+ window[window_posn++] = main_element;
+ this_run--;
+ }
+ else {
+ /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
+ main_element -= LZX_NUM_CHARS;
+
+ /* get match length */
+ match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
+ if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
+ READ_HUFFSYM(LENGTH, length_footer);
+ match_length += length_footer;
+ }
+ match_length += LZX_MIN_MATCH;
+
+ /* get match offset */
+ switch ((match_offset = (main_element >> 3))) {
+ case 0: match_offset = R0; break;
+ case 1: match_offset = R1; R1=R0; R0 = match_offset; break;
+ case 2: match_offset = R2; R2=R0; R0 = match_offset; break;
+ case 3: match_offset = 1; R2=R1; R1=R0; R0 = match_offset; break;
+ default:
+ extra = extra_bits[match_offset];
+ READ_BITS(verbatim_bits, extra);
+ match_offset = position_base[match_offset] - 2 + verbatim_bits;
+ R2 = R1; R1 = R0; R0 = match_offset;
+ }
+
+ if ((window_posn + match_length) > lzx->window_size) {
+ D(("match ran over window wrap"))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+
+ /* copy match */
+ rundest = &window[window_posn];
+ i = match_length;
+ /* does match offset wrap the window? */
+ if (match_offset > window_posn) {
+ /* j = length from match offset to end of window */
+ j = match_offset - window_posn;
+ if (j > (int) lzx->window_size) {
+ D(("match offset beyond window boundaries"))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+ runsrc = &window[lzx->window_size - j];
+ if (j < i) {
+ /* if match goes over the window edge, do two copy runs */
+ i -= j; while (j-- > 0) *rundest++ = *runsrc++;
+ runsrc = window;
+ }
+ while (i-- > 0) *rundest++ = *runsrc++;
+ }
+ else {
+ runsrc = rundest - match_offset;
+ while (i-- > 0) *rundest++ = *runsrc++;
+ }
+
+ this_run -= match_length;
+ window_posn += match_length;
+ }
+ } /* while (this_run > 0) */
+ break;
+
+ case LZX_BLOCKTYPE_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;
+
+ /* get match length */
+ 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;
+
+ /* get match offset */
+ switch ((match_offset = (main_element >> 3))) {
+ case 0: match_offset = R0; break;
+ case 1: match_offset = R1; R1 = R0; R0 = match_offset; break;
+ case 2: match_offset = R2; R2 = R0; R0 = match_offset; break;
+ default:
+ extra = 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 */ {
+ /* ??? not defined in LZX specification! */
+ match_offset = 1;
+ }
+ /* update repeated offset LRU queue */
+ R2 = R1; R1 = R0; R0 = match_offset;
+ }
+
+ if ((window_posn + match_length) > lzx->window_size) {
+ D(("match ran over window wrap"))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+
+ /* copy match */
+ rundest = &window[window_posn];
+ i = match_length;
+ /* does match offset wrap the window? */
+ if (match_offset > window_posn) {
+ /* j = length from match offset to end of window */
+ j = match_offset - window_posn;
+ if (j > (int) lzx->window_size) {
+ D(("match offset beyond window boundaries"))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+ runsrc = &window[lzx->window_size - j];
+ if (j < i) {
+ /* if match goes over the window edge, do two copy runs */
+ i -= j; while (j-- > 0) *rundest++ = *runsrc++;
+ runsrc = window;
+ }
+ while (i-- > 0) *rundest++ = *runsrc++;
+ }
+ else {
+ runsrc = rundest - match_offset;
+ while (i-- > 0) *rundest++ = *runsrc++;
+ }
+
+ this_run -= match_length;
+ window_posn += match_length;
+ }
+ } /* while (this_run > 0) */
+ break;
+
+ case LZX_BLOCKTYPE_UNCOMPRESSED:
+ /* as this_run is limited not to wrap a frame, this also means it
+ * won't wrap the window (as the window is a multiple of 32k) */
+ rundest = &window[window_posn];
+ window_posn += this_run;
+ while (this_run > 0) {
+ if ((i = i_end - i_ptr) == 0) {
+ READ_IF_NEEDED;
+ }
+ else {
+ if (i > this_run) i = this_run;
+ memcpy(rundest, i_ptr, (size_t) i);
+ rundest += i;
+ i_ptr += i;
+ this_run -= i;
+ }
+ }
+ break;
+
+ default:
+ return lzx->error = LZX_ERR_DECRUNCH; /* might as well */
+ }
+
+ /* did the final match overrun our desired this_run length? */
+ if (this_run < 0) {
+ if ((unsigned int)(-this_run) > lzx->block_remaining) {
+ D(("overrun went past end of block by %d (%d remaining)",
+ -this_run, lzx->block_remaining ))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+ lzx->block_remaining -= -this_run;
+ }
+ } /* while (bytes_todo > 0) */
+
+ /* streams don't extend over frame boundaries */
+ if ((window_posn - lzx->frame_posn) != frame_size) {
+ D(("decode beyond output frame limits! %d != %d",
+ window_posn - lzx->frame_posn, frame_size))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+
+ /* re-align input bitstream */
+ if (bits_left > 0) ENSURE_BITS(16);
+ if (bits_left & 15) REMOVE_BITS(bits_left & 15);
+
+ /* check that we've used all of the previous frame first */
+ if (lzx->o_ptr != lzx->o_end) {
+ D(("%d avail bytes, new %d frame", lzx->o_end-lzx->o_ptr, frame_size))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+
+ /* does this intel block _really_ need decoding? */
+ if (lzx->intel_started && lzx->intel_filesize &&
+ (lzx->frame <= 32768) && (frame_size > 10))
+ {
+ unsigned char *data = &lzx->e8_buf[0];
+ unsigned char *dataend = &lzx->e8_buf[frame_size - 10];
+ signed int curpos = lzx->intel_curpos;
+ signed int filesize = lzx->intel_filesize;
+ signed int abs_off, rel_off;
+
+ /* copy e8 block to the e8 buffer and tweak if needed */
+ lzx->o_ptr = data;
+ memcpy(data, &lzx->window[lzx->frame_posn], frame_size);
+
+ while (data < dataend) {
+ if (*data++ != 0xE8) { curpos++; continue; }
+ abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
+ if ((abs_off >= -curpos) && (abs_off < filesize)) {
+ rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
+ data[0] = (unsigned char) rel_off;
+ data[1] = (unsigned char) (rel_off >> 8);
+ data[2] = (unsigned char) (rel_off >> 16);
+ data[3] = (unsigned char) (rel_off >> 24);
+ }
+ data += 4;
+ curpos += 5;
+ }
+ lzx->intel_curpos += frame_size;
+ }
+ else {
+ lzx->o_ptr = &lzx->window[lzx->frame_posn];
+ if (lzx->intel_filesize) lzx->intel_curpos += frame_size;
+ }
+ lzx->o_end = &lzx->o_ptr[frame_size];
+
+ /* write a frame */
+ i = (out_bytes < (off_t)frame_size) ? (unsigned int)out_bytes : frame_size;
+ if (fwrite(lzx->o_ptr, 1, i, lzx->output) != i) {
+ return lzx->error = LZX_ERR_WRITE;
+ }
+ lzx->o_ptr += i;
+ lzx->offset += i;
+ out_bytes -= i;
+
+ /* advance frame start position */
+ lzx->frame_posn += frame_size;
+ lzx->frame++;
+
+ /* wrap window / frame position pointers */
+ if (window_posn == lzx->window_size) window_posn = 0;
+ if (lzx->frame_posn == lzx->window_size) lzx->frame_posn = 0;
+
+ } /* while (lzx->frame < end_frame) */
+
+ if (out_bytes) {
+ D(("bytes left to output"))
+ return lzx->error = LZX_ERR_DECRUNCH;
+ }
+
+ /* store local state */
+ STORE_BITS;
+ lzx->window_posn = window_posn;
+ lzx->R0 = R0;
+ lzx->R1 = R1;
+ lzx->R2 = R2;
+
+ return LZX_ERR_OK;
+}
+
+void lzxd_free(struct lzxd_stream *lzx) {
+ if (lzx) {
+ free(lzx->inbuf);
+ free(lzx->window);
+ free(lzx);
+ }
+}
diff --git a/src/addressbook/lzx/readbits.h b/src/addressbook/lzx/readbits.h
new file mode 100644
index 0000000..0f78142
--- /dev/null
+++ b/src/addressbook/lzx/readbits.h
@@ -0,0 +1,201 @@
+/* This file is part of libmspack.
+ * (C) 2003-2010 Stuart Caie.
+ *
+ * libmspack is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Lesser General Public License (LGPL) version 2.1
+ *
+ * For further details, see the file COPYING.LIB distributed with libmspack
+ */
+
+#ifndef READBITS_H
+#define READBITS_H 1
+
+/* this header defines macros that read data streams by
+ * the individual bits
+ *
+ * INIT_BITS initialises bitstream state in state structure
+ * STORE_BITS stores bitstream state in state structure
+ * RESTORE_BITS restores bitstream state from state structure
+ * ENSURE_BITS(n) ensure there are at least N bits in the bit buffer
+ * READ_BITS(var,n) takes N bits from the buffer and puts them in var
+ * PEEK_BITS(n) extracts without removing N bits from the bit buffer
+ * REMOVE_BITS(n) removes N bits from the bit buffer
+ *
+ * READ_BITS simply calls ENSURE_BITS, PEEK_BITS and REMOVE_BITS,
+ * which means it's limited to reading the number of bits you can
+ * ensure at any one time. It also fails if asked to read zero bits.
+ * If you need to read zero bits, or more bits than can be ensured in
+ * one go, use READ_MANY_BITS instead.
+ *
+ * These macros have variable names baked into them, so to use them
+ * you have to define some macros:
+ * - BITS_TYPE: the type name of your state structure
+ * - BITS_VAR: the variable that points to your state structure
+ * - define BITS_ORDER_MSB if bits are read from the MSB, or
+ * define BITS_ORDER_LSB if bits are read from the LSB
+ * - READ_BYTES: some code that reads more data into the bit buffer,
+ * it should use READ_IF_NEEDED (calls read_input if the byte buffer
+ * is empty), then INJECT_BITS(data,n) to put data from the byte
+ * buffer into the bit buffer.
+ *
+ * You also need to define some variables and structure members:
+ * - unsigned char *i_ptr; // current position in the byte buffer
+ * - unsigned char *i_end; // end of the byte buffer
+ * - unsigned int bit_buffer; // the bit buffer itself
+ * - unsigned int bits_left; // number of bits remaining
+ *
+ * If you use read_input() and READ_IF_NEEDED, they also expect these
+ * structure members:
+ * - unsigned int error; // to record/return read errors
+ * - unsigned char input_end; // to mark reaching the EOF
+ * - unsigned char *inbuf; // the input byte buffer
+ * - unsigned int inbuf_size; // the size of the input byte buffer
+ *
+ * Your READ_BYTES implementation should read data from *i_ptr and
+ * put them in the bit buffer. READ_IF_NEEDED will call read_input()
+ * if i_ptr reaches i_end, and will fill up inbuf and set i_ptr to
+ * the start of inbuf and i_end to the end of inbuf.
+ *
+ * If you're reading in MSB order, the routines work by using the area
+ * beyond the MSB and the LSB of the bit buffer as a free source of
+ * zeroes when shifting. This avoids having to mask any bits. So we
+ * have to know the bit width of the bit buffer variable. We use
+ * <limits.h> and CHAR_BIT to find the size of the bit buffer in bits.
+ *
+ * If you are reading in LSB order, bits need to be masked. Normally
+ * this is done by computing the mask: N bits are masked by the value
+ * (1<<N)-1). However, you can define BITS_LSB_TABLE to use a lookup
+ * table instead of computing this. This adds two new macros,
+ * PEEK_BITS_T and READ_BITS_T which work the same way as PEEK_BITS
+ * and READ_BITS, except they use this lookup table. This is useful if
+ * you need to look up a number of bits that are only known at
+ * runtime, so the bit mask can't be turned into a constant by the
+ * compiler.
+
+ * The bit buffer datatype should be at least 32 bits wide: it must be
+ * possible to ENSURE_BITS(17), so it must be possible to add 16 new bits
+ * to the bit buffer when the bit buffer already has 1 to 15 bits left.
+ */
+
+#ifndef BITS_VAR
+# error "define BITS_VAR as the state structure poiner variable name"
+#endif
+#ifndef BITS_TYPE
+# error "define BITS_TYPE as the state structure type"
+#endif
+#if defined(BITS_ORDER_MSB) && defined(BITS_ORDER_LSB)
+# error "you must define either BITS_ORDER_MSB or BITS_ORDER_LSB"
+#else
+# if !(defined(BITS_ORDER_MSB) || defined(BITS_ORDER_LSB))
+# error "you must define BITS_ORDER_MSB or BITS_ORDER_LSB"
+# endif
+#endif
+
+# include <limits.h>
+
+#define BITBUF_WIDTH (sizeof(bit_buffer) * CHAR_BIT)
+
+#define INIT_BITS do { \
+ BITS_VAR->i_ptr = &BITS_VAR->inbuf[0]; \
+ BITS_VAR->i_end = &BITS_VAR->inbuf[0]; \
+ BITS_VAR->bit_buffer = 0; \
+ BITS_VAR->bits_left = 0; \
+ BITS_VAR->input_end = 0; \
+} while (0)
+
+#define STORE_BITS do { \
+ BITS_VAR->i_ptr = i_ptr; \
+ BITS_VAR->i_end = i_end; \
+ BITS_VAR->bit_buffer = bit_buffer; \
+ BITS_VAR->bits_left = bits_left; \
+} while (0)
+
+#define RESTORE_BITS do { \
+ i_ptr = BITS_VAR->i_ptr; \
+ i_end = BITS_VAR->i_end; \
+ bit_buffer = BITS_VAR->bit_buffer; \
+ bits_left = BITS_VAR->bits_left; \
+} while (0)
+
+#define ENSURE_BITS(nbits) do { \
+ while (bits_left < (nbits)) READ_BYTES; \
+} while (0)
+
+#define READ_BITS(val, nbits) do { \
+ ENSURE_BITS(nbits); \
+ (val) = PEEK_BITS(nbits); \
+ REMOVE_BITS(nbits); \
+} while (0)
+
+#define READ_MANY_BITS(val, bits) do { \
+ unsigned char needed = (bits), bitrun; \
+ (val) = 0; \
+ while (needed > 0) { \
+ if (bits_left <= (BITBUF_WIDTH - 16)) READ_BYTES; \
+ bitrun = (bits_left < needed) ? bits_left : needed; \
+ (val) = ((val) << bitrun) | PEEK_BITS(bitrun); \
+ REMOVE_BITS(bitrun); \
+ needed -= bitrun; \
+ } \
+} while (0)
+
+#ifdef BITS_ORDER_MSB
+# define PEEK_BITS(nbits) (bit_buffer >> (BITBUF_WIDTH - (nbits)))
+# define REMOVE_BITS(nbits) ((bit_buffer <<= (nbits)), (bits_left -= (nbits)))
+# define INJECT_BITS(bitdata,nbits) ((bit_buffer |= \
+ (bitdata) << (BITBUF_WIDTH - (nbits) - bits_left)), (bits_left += (nbits)))
+#else /* BITS_ORDER_LSB */
+# define PEEK_BITS(nbits) (bit_buffer & ((1 << (nbits))-1))
+# define REMOVE_BITS(nbits) ((bit_buffer >>= (nbits)), (bits_left -= (nbits)))
+# define INJECT_BITS(bitdata,nbits) ((bit_buffer |= \
+ (bitdata) << bits_left), (bits_left += (nbits)))
+#endif
+
+#ifdef BITS_LSB_TABLE
+/* lsb_bit_mask[n] = (1 << n) - 1 */
+static const unsigned short lsb_bit_mask[17] = {
+ 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
+ 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
+};
+# define PEEK_BITS_T(nbits) (bit_buffer & lsb_bit_mask[(nbits)])
+# define READ_BITS_T(val, nbits) do { \
+ ENSURE_BITS(nbits); \
+ (val) = PEEK_BITS_T(nbits); \
+ REMOVE_BITS(nbits); \
+} while (0)
+#endif
+
+#ifndef BITS_NO_READ_INPUT
+# define READ_IF_NEEDED do { \
+ if (i_ptr >= i_end) { \
+ if (read_input(BITS_VAR)) \
+ return BITS_VAR->error; \
+ i_ptr = BITS_VAR->i_ptr; \
+ i_end = BITS_VAR->i_end; \
+ } \
+} while (0)
+
+static int read_input(BITS_TYPE *p) {
+ int read = fread(p->inbuf, 1, (int)p->inbuf_size, p->input);
+ if (read < 0) return p->error = LZX_ERR_READ;
+
+ /* we might overrun the input stream by asking for bits we don't use,
+ * so fake 2 more bytes at the end of input */
+ if (read == 0) {
+ if (p->input_end) {
+ return p->error = LZX_ERR_READ;
+ }
+ else {
+ read = 2;
+ p->inbuf[0] = p->inbuf[1] = 0;
+ p->input_end = 1;
+ }
+ }
+
+ /* update i_ptr and i_end */
+ p->i_ptr = &p->inbuf[0];
+ p->i_end = &p->inbuf[read];
+ return LZX_ERR_OK;
+}
+#endif
+#endif
diff --git a/src/addressbook/lzx/readhuff.h b/src/addressbook/lzx/readhuff.h
new file mode 100644
index 0000000..4861530
--- /dev/null
+++ b/src/addressbook/lzx/readhuff.h
@@ -0,0 +1,174 @@
+/* This file is part of libmspack.
+ * (C) 2003-2010 Stuart Caie.
+ *
+ * libmspack is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Lesser General Public License (LGPL) version 2.1
+ *
+ * For further details, see the file COPYING.LIB distributed with libmspack
+ */
+
+#ifndef MSPACK_READHUFF_H
+#define MSPACK_READHUFF_H 1
+
+/* This implements a fast Huffman tree decoding system.
+ */
+
+#if !(defined(BITS_ORDER_MSB) || defined(BITS_ORDER_LSB))
+# error "readhuff.h is used in conjunction with readbits.h, include that first"
+#endif
+#if !(defined(TABLEBITS) && defined(MAXSYMBOLS))
+# error "define TABLEBITS(tbl) and MAXSYMBOLS(tbl) before using readhuff.h"
+#endif
+#if !(defined(HUFF_TABLE) && defined(HUFF_LEN))
+# error "define HUFF_TABLE(tbl) and HUFF_LEN(tbl) before using readhuff.h"
+#endif
+#ifndef HUFF_ERROR
+# error "define HUFF_ERROR before using readhuff.h"
+#endif
+#ifndef HUFF_MAXBITS
+# define HUFF_MAXBITS 16
+#endif
+
+#define READ_HUFFSYM(tbl, var) do { \
+ ENSURE_BITS(HUFF_MAXBITS); \
+ sym = HUFF_TABLE(tbl, PEEK_BITS(TABLEBITS(tbl))); \
+ if (sym >= MAXSYMBOLS(tbl)) HUFF_TRAVERSE(tbl); \
+ (var) = sym; \
+ i = HUFF_LEN(tbl, sym); \
+ REMOVE_BITS(i); \
+} while (0)
+
+#ifdef BITS_ORDER_LSB
+# define HUFF_TRAVERSE(tbl) do { \
+ i = TABLEBITS(tbl) - 1; \
+ do { \
+ if (i++ > HUFF_MAXBITS) HUFF_ERROR; \
+ sym = HUFF_TABLE(tbl, \
+ (sym << 1) | ((bit_buffer >> i) & 1)); \
+ } while (sym >= MAXSYMBOLS(tbl)); \
+} while (0)
+#else
+#define HUFF_TRAVERSE(tbl) do { \
+ i = 1 << (BITBUF_WIDTH - TABLEBITS(tbl)); \
+ do { \
+ if ((i >>= 1) == 0) HUFF_ERROR; \
+ sym = HUFF_TABLE(tbl, \
+ (sym << 1) | ((bit_buffer & i) ? 1 : 0)); \
+ } while (sym >= MAXSYMBOLS(tbl)); \
+} while (0)
+#endif
+
+/* make_decode_table(nsyms, nbits, length[], table[])
+ *
+ * This function was originally coded by David Tritscher.
+ * It builds a fast huffman decoding table from
+ * a canonical huffman code lengths table.
+ *
+ * nsyms = total number of symbols in this huffman tree.
+ * nbits = any symbols with a code length of nbits or less can be decoded
+ * in one lookup of the table.
+ * length = A table to get code lengths from [0 to nsyms-1]
+ * table = The table to fill up with decoded symbols and pointers.
+ * Should be ((1<<nbits) + (nsyms*2)) in length.
+ *
+ * Returns 0 for OK or 1 for error
+ */
+static int make_decode_table(unsigned int nsyms, unsigned int nbits,
+ unsigned char *length, unsigned short *table)
+{
+ register unsigned short sym, next_symbol;
+ register unsigned int leaf, fill;
+#ifdef BITS_ORDER_LSB
+ register unsigned int reverse;
+#endif
+ register unsigned char bit_num;
+ unsigned int pos = 0; /* the current position in the decode table */
+ unsigned int table_mask = 1 << nbits;
+ unsigned int bit_mask = table_mask >> 1; /* don't do 0 length codes */
+
+ /* fill entries for codes short enough for a direct mapping */
+ for (bit_num = 1; bit_num <= nbits; bit_num++) {
+ for (sym = 0; sym < nsyms; sym++) {
+ if (length[sym] != bit_num) continue;
+#ifdef BITS_ORDER_MSB
+ leaf = pos;
+#else
+ /* reverse the significant bits */
+ fill = length[sym]; reverse = pos >> (nbits - fill); leaf = 0;
+ do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill);
+#endif
+
+ if((pos += bit_mask) > table_mask) return 1; /* table overrun */
+
+ /* fill all possible lookups of this symbol with the symbol itself */
+#ifdef BITS_ORDER_MSB
+ for (fill = bit_mask; fill-- > 0;) table[leaf++] = sym;
+#else
+ fill = bit_mask; next_symbol = 1 << bit_num;
+ do { table[leaf] = sym; leaf += next_symbol; } while (--fill);
+#endif
+ }
+ bit_mask >>= 1;
+ }
+
+ /* exit with success if table is now complete */
+ if (pos == table_mask) return 0;
+
+ /* mark all remaining table entries as unused */
+ for (sym = pos; sym < table_mask; sym++) {
+#ifdef BITS_ORDER_MSB
+ table[sym] = 0xFFFF;
+#else
+ reverse = sym; leaf = 0; fill = nbits;
+ do { leaf <<= 1; leaf |= reverse & 1; reverse >>= 1; } while (--fill);
+ table[leaf] = 0xFFFF;
+#endif
+ }
+
+ /* next_symbol = base of allocation for long codes */
+ next_symbol = ((table_mask >> 1) < nsyms) ? nsyms : (table_mask >> 1);
+
+ /* give ourselves room for codes to grow by up to 16 more bits.
+ * codes now start at bit nbits+16 and end at (nbits+16-codelength) */
+ pos <<= 16;
+ table_mask <<= 16;
+ bit_mask = 1 << 15;
+
+ for (bit_num = nbits+1; bit_num <= HUFF_MAXBITS; bit_num++) {
+ for (sym = 0; sym < nsyms; sym++) {
+ if (length[sym] != bit_num) continue;
+
+#ifdef BITS_ORDER_MSB
+ leaf = pos >> 16;
+#else
+ /* leaf = the first nbits of the code, reversed */
+ reverse = pos >> 16; leaf = 0; fill = nbits;
+ do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill);
+#endif
+ for (fill = 0; fill < (bit_num - nbits); fill++) {
+ /* if this path hasn't been taken yet, 'allocate' two entries */
+ if (table[leaf] == 0xFFFF) {
+ table[(next_symbol << 1) ] = 0xFFFF;
+ table[(next_symbol << 1) + 1 ] = 0xFFFF;
+ table[leaf] = next_symbol++;
+ }
+
+ /* follow the path and select either left or right for next bit */
+ leaf = table[leaf] << 1;
+ if ((pos >> (15-fill)) & 1) leaf++;
+ }
+ table[leaf] = sym;
+
+ if ((pos += bit_mask) > table_mask) return 1; /* table overflow */
+ }
+ bit_mask >>= 1;
+ }
+
+ /* full table? */
+ if (pos == table_mask) return 0;
+
+ /* either erroneous table, or all elements are 0 - let's find out. */
+ for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1;
+ return 0;
+}
+#endif
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
