LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] Add LZO1X compression support to the kernel
@ 2007-05-02  8:56 Richard Purdie
  2007-05-02  9:35 ` Pekka Enberg
                   ` (2 more replies)
  0 siblings, 3 replies; 19+ messages in thread
From: Richard Purdie @ 2007-05-02  8:56 UTC (permalink / raw)
  To: LKML, akpm; +Cc: torvalds, David Woodhouse

Current thinking is that lzo should get merged directly followed by the
subsystem parts through their specific trees. It appears this should
make it onto LKML despite the size so here goes.

Please keep in mind I haven't reformatted the LZO code itself as if I do
so, it will make maintenance of it against any changes in LZO itself
near impossible. In its current form, it should be possible to diff
against upstream. All the bad formatting is confined to a handful of
files in lib/lzo/ and the kernel interface should be clean.

I realise a maze of ifdefs still remain. I've already spent a lot of
time removing a ton of them and going much further might start to affect
diffability of the code - I hoping whats there is a good compromise.

I've asked the LZO author about the comments on lzo_copyright function
but the code is GPLv2 licensed so is suitable for inclusion in the
kernel.



Add LZO1X compression/decompression support to the kernel.

This is based on the standard userspace lzo library, particularly
minilzo with the headers much trimmed down and simplified for kernel
use. Its structured so that it should still diff with the userspace
version for ease of future updating.

Signed-off-by: Richard Purdie <rpurdie@openedhand.com>
---
 include/linux/lzo.h |   63 ++
 lib/Kconfig         |    5 +
 lib/Makefile        |    1 +
 lib/lzo/Makefile    |    3 +
 lib/lzo/lzoconf.h   |  186 ++++++
 lib/lzo/lzodefs.h   |  463 ++++++++++++++
 lib/lzo/lzointf.c   |   37 ++
 lib/lzo/minilzo.c   | 1771 +++++++++++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 2529 insertions(+), 0 deletions(-)

diff --git a/include/linux/lzo.h b/include/linux/lzo.h
new file mode 100644
index 0000000..ef72438
--- /dev/null
+++ b/include/linux/lzo.h
@@ -0,0 +1,63 @@
+/*
+ * LZO Public Kernel Interface
+ * A mini subset of the LZO real-time data compression library
+ *
+ * Copyright (C) 2007 Nokia Corporation. All rights reserved.
+ *
+ * Author: Richard Purdie <rpurdie@openedhand.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 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 General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
+ * 02110-1301 USA
+ *
+ */
+
+#ifndef __LZO_H
+#define __LZO_H
+
+#define LZO1X_MEM_COMPRESS	(16384 * sizeof(unsigned char *))
+#define LZO1X_MEM_DECOMPRESS    (0)
+#define LZO1X_1_MEM_COMPRESS	LZO1X_MEM_COMPRESS
+
+#define lzo1x_worst_compress(x) (x + (x / 64) + 16 + 3)
+
+const unsigned char * lzo_copyright(void);
+
+int lzo1x_1_compress(const unsigned char *src, unsigned long src_len,
+			unsigned char *dst, unsigned long *dst_len,
+			void *wrkmem);
+
+int lzo1x_decompress(const unsigned char *src, unsigned long src_len,
+			unsigned char *dst, unsigned long *dst_len,
+			void *wrkmem /* NOT USED */);
+
+/* safe decompression with overrun testing */
+int lzo1x_decompress_safe(const unsigned char *src, unsigned long src_len,
+			unsigned char *dst, unsigned long *dst_len,
+			void *wrkmem /* NOT USED */);
+
+/*
+ * Return values (< 0 = Error)
+ */
+#define LZO_E_OK                    0
+#define LZO_E_ERROR                 (-1)
+#define LZO_E_OUT_OF_MEMORY         (-2)
+#define LZO_E_NOT_COMPRESSIBLE      (-3)
+#define LZO_E_INPUT_OVERRUN         (-4)
+#define LZO_E_OUTPUT_OVERRUN        (-5)
+#define LZO_E_LOOKBEHIND_OVERRUN    (-6)
+#define LZO_E_EOF_NOT_FOUND         (-7)
+#define LZO_E_INPUT_NOT_CONSUMED    (-8)
+#define LZO_E_NOT_YET_IMPLEMENTED   (-9)
+
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index 3842499..b39d4e5 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -47,6 +47,11 @@ config AUDIT_GENERIC
 	depends on AUDIT && !AUDIT_ARCH
 	default y
 
+config LZO
+	tristate "LZO compressor/decompressor"
+	help
+	  minilzo implementation in kernelspace.
+
 #
 # compression support is select'ed if needed
 #
diff --git a/lib/Makefile b/lib/Makefile
index ae57f35..442c63f 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -48,6 +48,7 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
 obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
 obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
+obj-$(CONFIG_LZO)          += lzo/
 
 obj-$(CONFIG_TEXTSEARCH) += textsearch.o
 obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
diff --git a/lib/lzo/Makefile b/lib/lzo/Makefile
new file mode 100644
index 0000000..cdb4809
--- /dev/null
+++ b/lib/lzo/Makefile
@@ -0,0 +1,3 @@
+lzo-objs := minilzo.o lzointf.o
+
+obj-$(CONFIG_LZO) += lzo.o
diff --git a/lib/lzo/lzoconf.h b/lib/lzo/lzoconf.h
new file mode 100644
index 0000000..428dcb6
--- /dev/null
+++ b/lib/lzo/lzoconf.h
@@ -0,0 +1,186 @@
+/* lzoconf.h -- configuration for the LZO real-time data compression library
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
+   All Rights Reserved.
+
+   The LZO library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License,
+   version 2, as published by the Free Software Foundation.
+
+   The LZO library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with the LZO library; see the file COPYING.
+   If not, write to the Free Software Foundation, Inc.,
+   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+   Markus F.X.J. Oberhumer <markus@oberhumer.com>
+
+   The full LZO package can be found at:
+   http://www.oberhumer.com/opensource/lzo/
+
+   Trimmed for kernel use by:
+   Richard Purdie <rpurdie@openedhand.com>
+ */
+
+
+#ifndef __LZOCONF_H_INCLUDED
+#define __LZOCONF_H_INCLUDED
+
+
+#define LZO_VERSION             0x2020
+#define LZO_VERSION_STRING      "2.02"
+#define LZO_VERSION_DATE        "Oct 17 2005"
+
+#define USHRT_MAX 0xffff
+#define LZO_EXTERN(t) t
+
+#include "lzodefs.h"
+
+
+/***********************************************************************
+// some core defines
+************************************************************************/
+
+#if !defined(LZO_UINT32_C)
+#  if (UINT_MAX < LZO_0xffffffffL)
+#    define LZO_UINT32_C(c)     c ## UL
+#  else
+#    define LZO_UINT32_C(c)     ((c) + 0U)
+#  endif
+#endif
+
+/* memory checkers */
+#if !defined(__LZO_CHECKER)
+#  if defined(__BOUNDS_CHECKING_ON)
+#    define __LZO_CHECKER       1
+#  elif defined(__CHECKER__)
+#    define __LZO_CHECKER       1
+#  elif defined(__INSURE__)
+#    define __LZO_CHECKER       1
+#  elif defined(__PURIFY__)
+#    define __LZO_CHECKER       1
+#  endif
+#endif
+
+
+/***********************************************************************
+// integral and pointer types
+************************************************************************/
+
+/* lzo_uint should match size_t */
+#if !defined(LZO_UINT_MAX)
+#  if defined(LZO_ABI_IP32L64) /* MIPS R5900 */
+     typedef unsigned int       lzo_uint;
+     typedef int                lzo_int;
+#    define LZO_UINT_MAX        UINT_MAX
+#    define LZO_INT_MAX         INT_MAX
+#    define LZO_INT_MIN         INT_MIN
+#  elif (ULONG_MAX >= LZO_0xffffffffL)
+     typedef unsigned long      lzo_uint;
+     typedef long               lzo_int;
+#    define LZO_UINT_MAX        ULONG_MAX
+#    define LZO_INT_MAX         LONG_MAX
+#    define LZO_INT_MIN         LONG_MIN
+#  else
+#    error "lzo_uint"
+#  endif
+#endif
+
+/* Integral types with 32 bits or more. */
+#if !defined(LZO_UINT32_MAX)
+#  if (UINT_MAX >= LZO_0xffffffffL)
+     typedef unsigned int       lzo_uint32;
+     typedef int                lzo_int32;
+#    define LZO_UINT32_MAX      UINT_MAX
+#    define LZO_INT32_MAX       INT_MAX
+#    define LZO_INT32_MIN       INT_MIN
+#  elif (ULONG_MAX >= LZO_0xffffffffL)
+     typedef unsigned long      lzo_uint32;
+     typedef long               lzo_int32;
+#    define LZO_UINT32_MAX      ULONG_MAX
+#    define LZO_INT32_MAX       LONG_MAX
+#    define LZO_INT32_MIN       LONG_MIN
+#  else
+#    error "lzo_uint32"
+#  endif
+#endif
+
+/* The larger type of lzo_uint and lzo_uint32. */
+#if (LZO_UINT_MAX >= LZO_UINT32_MAX)
+#  define lzo_xint              lzo_uint
+#else
+#  define lzo_xint              lzo_uint32
+#endif
+
+/* no typedef here because of const-pointer issues */
+#define lzo_bytep               unsigned char *
+#define lzo_charp               char *
+#define lzo_voidp               void *
+#define lzo_shortp              short *
+#define lzo_ushortp             unsigned short *
+#define lzo_uint32p             lzo_uint32 *
+#define lzo_int32p              lzo_int32 *
+#define lzo_uintp               lzo_uint *
+#define lzo_intp                lzo_int *
+#define lzo_xintp               lzo_xint *
+#define lzo_voidpp              lzo_voidp *
+#define lzo_bytepp              lzo_bytep *
+/* deprecated - use `lzo_bytep' instead of `lzo_byte *' */
+#define lzo_byte                unsigned char
+
+typedef int lzo_bool;
+
+
+/***********************************************************************
+// function types
+************************************************************************/
+
+/* name mangling */
+#define __LZO_EXTERN_C      extern
+
+/* __cdecl calling convention for public C and assembly functions */
+#if !defined(LZO_PUBLIC)
+#  define LZO_PUBLIC(_rettype)  _rettype
+#endif
+#if !defined(LZO_EXTERN)
+#  define LZO_EXTERN(_rettype)  __LZO_EXTERN_C LZO_PUBLIC(_rettype)
+#endif
+#if !defined(LZO_PRIVATE)
+#  define LZO_PRIVATE(_rettype) static _rettype
+#endif
+
+/* function types */
+typedef int
+(*lzo_compress_t)   ( const lzo_bytep src, lzo_uint  src_len,
+                                        lzo_bytep dst, lzo_uintp dst_len,
+                                        lzo_voidp wrkmem );
+
+typedef int
+(*lzo_decompress_t) ( const lzo_bytep src, lzo_uint  src_len,
+                                        lzo_bytep dst, lzo_uintp dst_len,
+                                        lzo_voidp wrkmem );
+
+typedef int
+(*lzo_optimize_t)   (       lzo_bytep src, lzo_uint  src_len,
+                                        lzo_bytep dst, lzo_uintp dst_len,
+                                        lzo_voidp wrkmem );
+
+typedef int
+(*lzo_compress_dict_t)(const lzo_bytep src, lzo_uint  src_len,
+                                         lzo_bytep dst, lzo_uintp dst_len,
+                                         lzo_voidp wrkmem,
+                                   const lzo_bytep dict, lzo_uint dict_len );
+
+typedef int
+(*lzo_decompress_dict_t)(const lzo_bytep src, lzo_uint  src_len,
+                                           lzo_bytep dst, lzo_uintp dst_len,
+                                           lzo_voidp wrkmem,
+                                     const lzo_bytep dict, lzo_uint dict_len );
+
+#endif /* already included */
diff --git a/lib/lzo/lzodefs.h b/lib/lzo/lzodefs.h
new file mode 100644
index 0000000..421b6a0
--- /dev/null
+++ b/lib/lzo/lzodefs.h
@@ -0,0 +1,463 @@
+/* lzodefs.h -- architecture, OS and compiler specific defines
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
+   All Rights Reserved.
+
+   The LZO library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License,
+   version 2, as published by the Free Software Foundation.
+
+   The LZO library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with the LZO library; see the file COPYING.
+   If not, write to the Free Software Foundation, Inc.,
+   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+   Markus F.X.J. Oberhumer <markus@oberhumer.com>
+
+   The full LZO package can be found at:
+   http://www.oberhumer.com/opensource/lzo/
+
+   Trimmed for kernel use by:
+   Richard Purdie <rpurdie@openedhand.com>
+ */
+
+
+#ifndef __LZODEFS_H_INCLUDED
+#define __LZODEFS_H_INCLUDED 1
+
+#if defined(__INTERIX) && defined(__GNUC__) && !defined(_ALL_SOURCE)
+#  define _ALL_SOURCE 1
+#endif
+#if defined(__mips__) && defined(__R5900__)
+#  if !defined(__LONG_MAX__)
+#    define __LONG_MAX__ 9223372036854775807L
+#  endif
+#endif
+#define LZO_0xffffL             65535ul
+#define LZO_0xffffffffL         4294967295ul
+#if (UINT_MAX == LZO_0xffffL)
+#  undef __LZO_RENAME_A
+#  undef __LZO_RENAME_B
+#endif
+#define LZO_CPP_STRINGIZE(x)            #x
+#define LZO_CPP_MACRO_EXPAND(x)         LZO_CPP_STRINGIZE(x)
+#define LZO_CPP_CONCAT2(a,b)            a ## b
+#define LZO_CPP_CONCAT3(a,b,c)          a ## b ## c
+#define LZO_CPP_CONCAT4(a,b,c,d)        a ## b ## c ## d
+#define LZO_CPP_CONCAT5(a,b,c,d,e)      a ## b ## c ## d ## e
+#define LZO_CPP_ECONCAT2(a,b)           LZO_CPP_CONCAT2(a,b)
+#define LZO_CPP_ECONCAT3(a,b,c)         LZO_CPP_CONCAT3(a,b,c)
+#define LZO_CPP_ECONCAT4(a,b,c,d)       LZO_CPP_CONCAT4(a,b,c,d)
+#define LZO_CPP_ECONCAT5(a,b,c,d,e)     LZO_CPP_CONCAT5(a,b,c,d,e)
+#define __LZO_MASK_GEN(o,b)     (((((o) << ((b)-1)) - (o)) << 1) + (o))
+#define LZO_EXTERN_C extern
+#if defined(__GNUC__) && defined(__VERSION__)
+#  if defined(__GNUC_MINOR__) && defined(__GNUC_PATCHLEVEL__)
+#    define LZO_CC_GNUC         (__GNUC__ * 0x10000L + __GNUC_MINOR__ * 0x100 + __GNUC_PATCHLEVEL__)
+#  elif defined(__GNUC_MINOR__)
+#    define LZO_CC_GNUC         (__GNUC__ * 0x10000L + __GNUC_MINOR__ * 0x100)
+#  else
+#    define LZO_CC_GNUC         (__GNUC__ * 0x10000L)
+#  endif
+#else
+#  define LZO_CC_UNKNOWN        1
+#endif
+#if !defined(__LZO_ARCH_OVERRIDE)
+#if defined(LZO_ARCH_GENERIC)
+#elif defined(__alpha__) || defined(__alpha) || defined(_M_ALPHA)
+#  define LZO_ARCH_ALPHA            1
+#elif defined(__amd64__) || defined(__x86_64__) || defined(_M_AMD64)
+#  define LZO_ARCH_AMD64            1
+#elif defined(__thumb__) || (defined(_M_ARM) && defined(_M_THUMB))
+#  define LZO_ARCH_ARM              1
+#  define LZO_ARCH_ARM_THUMB        1
+#elif defined(__arm__) || defined(_M_ARM)
+#  define LZO_ARCH_ARM              1
+#elif (UINT_MAX <= LZO_0xffffL) && defined(__AVR__)
+#  define LZO_ARCH_AVR              1
+#elif defined(__bfin__)
+#  define LZO_ARCH_BLACKFIN         1
+#elif (UINT_MAX == LZO_0xffffL) && defined(__C166__)
+#  define LZO_ARCH_C166             1
+#elif defined(__cris__)
+#  define LZO_ARCH_CRIS             1
+#elif defined(__H8300__) || defined(__H8300H__) || defined(__H8300S__) || defined(__H8300SX__)
+#  define LZO_ARCH_H8300            1
+#elif defined(__hppa__) || defined(__hppa)
+#  define LZO_ARCH_HPPA             1
+#elif defined(__386__) || defined(__i386__) || defined(__i386) || defined(_M_IX86) || defined(_M_I386)
+#  define LZO_ARCH_I386             1
+#  define LZO_ARCH_IA32             1
+#elif defined(__ia64__) || defined(__ia64) || defined(_M_IA64)
+#  define LZO_ARCH_IA64             1
+#elif (UINT_MAX == LZO_0xffffL) && defined(__m32c__)
+#  define LZO_ARCH_M16C             1
+#elif defined(__m32r__)
+#  define LZO_ARCH_M32R             1
+#elif defined(__m68k__) || defined(__m68000__) || defined(__mc68000__) || defined(_M_M68K)
+#  define LZO_ARCH_M68K             1
+#elif (UINT_MAX == LZO_0xffffL) && defined(__C251__)
+#  define LZO_ARCH_MCS251           1
+#elif (UINT_MAX == LZO_0xffffL) && defined(__C51__)
+#  define LZO_ARCH_MCS51            1
+#elif defined(__mips__) || defined(__mips) || defined(_MIPS_ARCH) || defined(_M_MRX000)
+#  define LZO_ARCH_MIPS             1
+#elif (UINT_MAX == LZO_0xffffL) && defined(__MSP430__)
+#  define LZO_ARCH_MSP430           1
+#elif defined(__powerpc__) || defined(__powerpc) || defined(__ppc__) || defined(__PPC__) || defined(_M_PPC)
+#  define LZO_ARCH_POWERPC          1
+#elif defined(__s390__) || defined(__s390) || defined(__s390x__) || defined(__s390x)
+#  define LZO_ARCH_S390             1
+#elif defined(__sh__) || defined(_M_SH)
+#  define LZO_ARCH_SH               1
+#elif defined(__sparc__) || defined(__sparc) || defined(__sparcv8)
+#  define LZO_ARCH_SPARC            1
+#elif (UINT_MAX == LZO_0xffffL) && defined(__z80)
+#  define LZO_ARCH_Z80              1
+#else
+#  define LZO_ARCH_UNKNOWN          1
+#endif
+#endif
+#if defined(LZO_ARCH_ARM_THUMB) && !defined(LZO_ARCH_ARM)
+#  error "this should not happen"
+#endif
+#if defined(LZO_ARCH_I086PM) && !defined(LZO_ARCH_I086)
+#  error "this should not happen"
+#endif
+#if defined(LZO_ARCH_I086)
+#  if (UINT_MAX != LZO_0xffffL)
+#    error "this should not happen"
+#  endif
+#  if (ULONG_MAX != LZO_0xffffffffL)
+#    error "this should not happen"
+#  endif
+#endif
+#if defined(SIZEOF_SHORT)
+#  define LZO_SIZEOF_SHORT          (SIZEOF_SHORT)
+#endif
+#if defined(SIZEOF_INT)
+#  define LZO_SIZEOF_INT            (SIZEOF_INT)
+#endif
+#if defined(SIZEOF_LONG)
+#  define LZO_SIZEOF_LONG           (SIZEOF_LONG)
+#endif
+#if defined(SIZEOF_LONG_LONG)
+#  define LZO_SIZEOF_LONG_LONG      (SIZEOF_LONG_LONG)
+#endif
+#if defined(SIZEOF___INT16)
+#  define LZO_SIZEOF___INT16        (SIZEOF___INT16)
+#endif
+#if defined(SIZEOF___INT32)
+#  define LZO_SIZEOF___INT32        (SIZEOF___INT32)
+#endif
+#if defined(SIZEOF___INT64)
+#  define LZO_SIZEOF___INT64        (SIZEOF___INT64)
+#endif
+#if defined(SIZEOF_VOID_P)
+#  define LZO_SIZEOF_VOID_P         (SIZEOF_VOID_P)
+#endif
+#if defined(SIZEOF_SIZE_T)
+#  define LZO_SIZEOF_SIZE_T         (SIZEOF_SIZE_T)
+#endif
+#if defined(SIZEOF_PTRDIFF_T)
+#  define LZO_SIZEOF_PTRDIFF_T      (SIZEOF_PTRDIFF_T)
+#endif
+#define __LZO_LSR(x,b)    (((x)+0ul) >> (b))
+#if !defined(LZO_SIZEOF_SHORT)
+#  if (USHRT_MAX == LZO_0xffffL)
+#    define LZO_SIZEOF_SHORT        2
+#  elif (__LZO_LSR(USHRT_MAX,7) == 1)
+#    define LZO_SIZEOF_SHORT        1
+#  elif (__LZO_LSR(USHRT_MAX,15) == 1)
+#    define LZO_SIZEOF_SHORT        2
+#  elif (__LZO_LSR(USHRT_MAX,31) == 1)
+#    define LZO_SIZEOF_SHORT        4
+#  elif (__LZO_LSR(USHRT_MAX,63) == 1)
+#    define LZO_SIZEOF_SHORT        8
+#  elif (__LZO_LSR(USHRT_MAX,127) == 1)
+#    define LZO_SIZEOF_SHORT        16
+#  else
+#    error "LZO_SIZEOF_SHORT"
+#  endif
+#endif
+#if !defined(LZO_SIZEOF_INT)
+#  if (UINT_MAX == LZO_0xffffL)
+#    define LZO_SIZEOF_INT          2
+#  elif (UINT_MAX == LZO_0xffffffffL)
+#    define LZO_SIZEOF_INT          4
+#  elif (__LZO_LSR(UINT_MAX,7) == 1)
+#    define LZO_SIZEOF_INT          1
+#  elif (__LZO_LSR(UINT_MAX,15) == 1)
+#    define LZO_SIZEOF_INT          2
+#  elif (__LZO_LSR(UINT_MAX,31) == 1)
+#    define LZO_SIZEOF_INT          4
+#  elif (__LZO_LSR(UINT_MAX,63) == 1)
+#    define LZO_SIZEOF_INT          8
+#  elif (__LZO_LSR(UINT_MAX,127) == 1)
+#    define LZO_SIZEOF_INT          16
+#  else
+#    error "LZO_SIZEOF_INT"
+#  endif
+#endif
+#if !defined(LZO_SIZEOF_LONG)
+#  if (ULONG_MAX == LZO_0xffffffffL)
+#    define LZO_SIZEOF_LONG         4
+#  elif (__LZO_LSR(ULONG_MAX,7) == 1)
+#    define LZO_SIZEOF_LONG         1
+#  elif (__LZO_LSR(ULONG_MAX,15) == 1)
+#    define LZO_SIZEOF_LONG         2
+#  elif (__LZO_LSR(ULONG_MAX,31) == 1)
+#    define LZO_SIZEOF_LONG         4
+#  elif (__LZO_LSR(ULONG_MAX,63) == 1)
+#    define LZO_SIZEOF_LONG         8
+#  elif (__LZO_LSR(ULONG_MAX,127) == 1)
+#    define LZO_SIZEOF_LONG         16
+#  else
+#    error "LZO_SIZEOF_LONG"
+#  endif
+#endif
+#if !defined(LZO_SIZEOF_LONG_LONG) && !defined(LZO_SIZEOF___INT64)
+#if (LZO_SIZEOF_LONG > 0 && LZO_SIZEOF_LONG < 8)
+#  if defined(__LONG_MAX__) && defined(__LONG_LONG_MAX__)
+#    if (LZO_CC_GNUC >= 0x030300ul)
+#      if ((__LONG_MAX__)+0 == (__LONG_LONG_MAX__)+0)
+#        define LZO_SIZEOF_LONG_LONG      LZO_SIZEOF_LONG
+#      endif
+#    endif
+#  endif
+#endif
+#endif
+#if !defined(LZO_SIZEOF_LONG_LONG) && !defined(LZO_SIZEOF___INT64)
+#if (LZO_SIZEOF_LONG > 0 && LZO_SIZEOF_LONG < 8)
+#  define LZO_SIZEOF_LONG_LONG      8
+#endif
+#endif
+#if defined(LZO_CFG_NO_LONG_LONG) || defined(__NO_LONG_LONG)
+#  undef LZO_SIZEOF_LONG_LONG
+#endif
+#if !defined(LZO_SIZEOF_VOID_P)
+#if defined(LZO_ARCH_I086)
+#    define LZO_SIZEOF_VOID_P       4
+#elif defined(LZO_ARCH_AVR) || defined(LZO_ARCH_Z80)
+#  define __LZO_WORDSIZE            1
+#  define LZO_SIZEOF_VOID_P         2
+#elif defined(LZO_ARCH_C166) || defined(LZO_ARCH_MCS51) || defined(LZO_ARCH_MCS251) || defined(LZO_ARCH_MSP430)
+#  define LZO_SIZEOF_VOID_P         2
+#elif defined(LZO_ARCH_H8300)
+#  if defined(__NORMAL_MODE__)
+#    define __LZO_WORDSIZE          4
+#    define LZO_SIZEOF_VOID_P       2
+#  elif defined(__H8300H__) || defined(__H8300S__) || defined(__H8300SX__)
+#    define __LZO_WORDSIZE          4
+#    define LZO_SIZEOF_VOID_P       4
+#  else
+#    define __LZO_WORDSIZE          2
+#    define LZO_SIZEOF_VOID_P       2
+#  endif
+#  if (LZO_CC_GNUC && (LZO_CC_GNUC < 0x040000ul)) && (LZO_SIZEOF_INT == 4)
+#    define LZO_SIZEOF_SIZE_T       LZO_SIZEOF_INT
+#    define LZO_SIZEOF_PTRDIFF_T    LZO_SIZEOF_INT
+#  endif
+#elif defined(LZO_ARCH_M16C)
+#  define __LZO_WORDSIZE            2
+#  if defined(__m32c_cpu__) || defined(__m32cm_cpu__)
+#    define LZO_SIZEOF_VOID_P       4
+#  else
+#    define LZO_SIZEOF_VOID_P       2
+#  endif
+#elif (LZO_SIZEOF_LONG == 8) && ((defined(__mips__) && defined(__R5900__)) || defined(__MIPS_PSX2__))
+#  define __LZO_WORDSIZE            8
+#  define LZO_SIZEOF_VOID_P         4
+#elif defined(__LLP64__) || defined(__LLP64) || defined(_LLP64)
+#  define __LZO_WORDSIZE            8
+#  define LZO_SIZEOF_VOID_P         8
+#elif (defined(__vms) || defined(__VMS)) && (__INITIAL_POINTER_SIZE+0 == 64)
+#  define LZO_SIZEOF_VOID_P         8
+#  define LZO_SIZEOF_SIZE_T         LZO_SIZEOF_LONG
+#  define LZO_SIZEOF_PTRDIFF_T      LZO_SIZEOF_LONG
+#else
+#  define LZO_SIZEOF_VOID_P         LZO_SIZEOF_LONG
+#endif
+#endif
+#if !defined(LZO_WORDSIZE)
+#  if defined(__LZO_WORDSIZE)
+#    define LZO_WORDSIZE            __LZO_WORDSIZE
+#  else
+#    define LZO_WORDSIZE            LZO_SIZEOF_VOID_P
+#  endif
+#endif
+#if !defined(LZO_SIZEOF_SIZE_T)
+#if defined(LZO_ARCH_I086) || defined(LZO_ARCH_M16C)
+#  define LZO_SIZEOF_SIZE_T         2
+#else
+#  define LZO_SIZEOF_SIZE_T         LZO_SIZEOF_VOID_P
+#endif
+#endif
+#if !defined(LZO_SIZEOF_PTRDIFF_T)
+#if defined(LZO_ARCH_I086)
+#  define LZO_SIZEOF_PTRDIFF_T    LZO_SIZEOF_VOID_P
+#else
+#  define LZO_SIZEOF_PTRDIFF_T      LZO_SIZEOF_SIZE_T
+#endif
+#endif
+#if !defined(LZO_ABI_BIG_ENDIAN) && !defined(LZO_ABI_LITTLE_ENDIAN) && !defined(LZO_ABI_NEUTRAL_ENDIAN)
+#if defined(LZO_ARCH_AMD64) || defined(LZO_ARCH_CRIS) || defined(LZO_ARCH_I086) || defined(LZO_ARCH_I386) || defined(LZO_ARCH_MSP430)
+#  define LZO_ABI_LITTLE_ENDIAN     1
+#elif defined(LZO_ARCH_M68K) || defined(LZO_ARCH_S390)
+#  define LZO_ABI_BIG_ENDIAN        1
+#elif 1 && defined(__BIG_ENDIAN__) && !defined(__LITTLE_ENDIAN__)
+#  define LZO_ABI_BIG_ENDIAN        1
+#elif 1 && defined(__LITTLE_ENDIAN__) && !defined(__BIG_ENDIAN__)
+#  define LZO_ABI_LITTLE_ENDIAN     1
+#elif 1 && defined(LZO_ARCH_MIPS) && defined(__MIPSEB__) && !defined(__MIPSEL__)
+#  define LZO_ABI_BIG_ENDIAN        1
+#elif 1 && defined(LZO_ARCH_MIPS) && defined(__MIPSEL__) && !defined(__MIPSEB__)
+#  define LZO_ABI_LITTLE_ENDIAN     1
+#endif
+#endif
+#if defined(LZO_ABI_BIG_ENDIAN) && defined(LZO_ABI_LITTLE_ENDIAN)
+#  error "this should not happen"
+#endif
+#if (LZO_SIZEOF_INT == 1 && LZO_SIZEOF_LONG == 2 && LZO_SIZEOF_VOID_P == 2)
+#  define LZO_ABI_I8LP16         1
+#elif (LZO_SIZEOF_INT == 2 && LZO_SIZEOF_LONG == 2 && LZO_SIZEOF_VOID_P == 2)
+#  define LZO_ABI_ILP16         1
+#elif (LZO_SIZEOF_INT == 4 && LZO_SIZEOF_LONG == 4 && LZO_SIZEOF_VOID_P == 4)
+#  define LZO_ABI_ILP32         1
+#elif (LZO_SIZEOF_INT == 4 && LZO_SIZEOF_LONG == 4 && LZO_SIZEOF_VOID_P == 8 && LZO_SIZEOF_SIZE_T == 8)
+#  define LZO_ABI_LLP64         1
+#elif (LZO_SIZEOF_INT == 4 && LZO_SIZEOF_LONG == 8 && LZO_SIZEOF_VOID_P == 8)
+#  define LZO_ABI_LP64          1
+#elif (LZO_SIZEOF_INT == 8 && LZO_SIZEOF_LONG == 8 && LZO_SIZEOF_VOID_P == 8)
+#  define LZO_ABI_ILP64         1
+#elif (LZO_SIZEOF_INT == 4 && LZO_SIZEOF_LONG == 8 && LZO_SIZEOF_VOID_P == 4)
+#  define LZO_ABI_IP32L64       1
+#endif
+#  define lzo_alignof(e)        __alignof__(e)
+#define __lzo_inline          __inline__
+#if (LZO_CC_GNUC >= 0x030200ul)
+#  define __lzo_forceinline     __inline__ __attribute__((__always_inline__))
+#endif
+#if (LZO_CC_GNUC >= 0x030200ul)
+#  define __lzo_noinline        __attribute__((__noinline__))
+#endif
+#if (defined(__lzo_forceinline) || defined(__lzo_noinline)) && !defined(__lzo_inline)
+#  error "this should not happen"
+#endif
+#if (LZO_CC_GNUC >= 0x020700ul)
+#  define __lzo_noreturn        __attribute__((__noreturn__))
+#endif
+#if (LZO_CC_GNUC >= 0x030400ul)
+#  define __lzo_constructor     __attribute__((__constructor__,__used__))
+#elif (LZO_CC_GNUC >= 0x020700ul)
+#  define __lzo_constructor     __attribute__((__constructor__))
+#endif
+#if (LZO_CC_GNUC >= 0x030400ul)
+#  define __lzo_destructor      __attribute__((__destructor__,__used__))
+#elif (LZO_CC_GNUC >= 0x020700ul)
+#  define __lzo_destructor      __attribute__((__destructor__))
+#endif
+#if defined(__lzo_destructor) && !defined(__lzo_constructor)
+#  error "this should not happen"
+#endif
+#if (LZO_CC_GNUC >= 0x030200ul)
+#  define __lzo_likely(e)       (__builtin_expect(!!(e),1))
+#  define __lzo_unlikely(e)     (__builtin_expect(!!(e),0))
+#else
+#  define __lzo_likely(e)       (e)
+#  define __lzo_unlikely(e)     (e)
+#endif
+#if !defined(LZO_UNUSED)
+#    define LZO_UNUSED(var)         ((void) var)
+#endif
+#if !defined(LZO_UNUSED_FUNC)
+#    define LZO_UNUSED_FUNC(func)   ((void) func)
+#endif
+#if !defined(LZO_UNUSED_LABEL)
+#    define LZO_UNUSED_LABEL(l)     switch(0) case 1:goto l
+#endif
+#if !defined(LZO_COMPILE_TIME_ASSERT_HEADER)
+#    define LZO_COMPILE_TIME_ASSERT_HEADER(e)  extern int __lzo_cta[1-2*!(e)];
+#endif
+#if !defined(LZO_COMPILE_TIME_ASSERT)
+#    define LZO_COMPILE_TIME_ASSERT(e)  {typedef int __lzo_cta_t[1-2*!(e)];}
+#endif
+
+#if defined(LZO_ARCH_ALPHA)
+#  define LZO_OPT_AVOID_UINT_INDEX  1
+#  define LZO_OPT_AVOID_SHORT       1
+#  define LZO_OPT_AVOID_USHORT      1
+#elif defined(LZO_ARCH_AMD64)
+#  define LZO_OPT_AVOID_INT_INDEX   1
+#  define LZO_OPT_AVOID_UINT_INDEX  1
+#  define LZO_OPT_UNALIGNED16       1
+#  define LZO_OPT_UNALIGNED32       1
+#  define LZO_OPT_UNALIGNED64       1
+#elif defined(LZO_ARCH_ARM) && defined(LZO_ARCH_ARM_THUMB)
+#elif defined(LZO_ARCH_ARM)
+#  define LZO_OPT_AVOID_SHORT       1
+#  define LZO_OPT_AVOID_USHORT      1
+#elif defined(LZO_ARCH_CRIS)
+#  define LZO_OPT_UNALIGNED16       1
+#  define LZO_OPT_UNALIGNED32       1
+#elif defined(LZO_ARCH_I386)
+#  define LZO_OPT_UNALIGNED16       1
+#  define LZO_OPT_UNALIGNED32       1
+#elif defined(LZO_ARCH_IA64)
+#  define LZO_OPT_AVOID_INT_INDEX   1
+#  define LZO_OPT_AVOID_UINT_INDEX  1
+#  define LZO_OPT_PREFER_POSTINC    1
+#elif defined(LZO_ARCH_M68K)
+#  define LZO_OPT_PREFER_POSTINC    1
+#  define LZO_OPT_PREFER_PREDEC     1
+#  if defined(__mc68020__) && !defined(__mcoldfire__)
+#    define LZO_OPT_UNALIGNED16     1
+#    define LZO_OPT_UNALIGNED32     1
+#  endif
+#elif defined(LZO_ARCH_MIPS)
+#  define LZO_OPT_AVOID_UINT_INDEX  1
+#elif defined(LZO_ARCH_POWERPC)
+#  define LZO_OPT_PREFER_PREINC     1
+#  define LZO_OPT_PREFER_PREDEC     1
+#  if defined(LZO_ABI_BIG_ENDIAN)
+#    define LZO_OPT_UNALIGNED16     1
+#    define LZO_OPT_UNALIGNED32     1
+#  endif
+#elif defined(LZO_ARCH_S390)
+#  define LZO_OPT_UNALIGNED16       1
+#  define LZO_OPT_UNALIGNED32       1
+#  if (LZO_SIZEOF_SIZE_T == 8)
+#    define LZO_OPT_UNALIGNED64     1
+#  endif
+#elif defined(LZO_ARCH_SH)
+#  define LZO_OPT_PREFER_POSTINC    1
+#  define LZO_OPT_PREFER_PREDEC     1
+#endif
+#if !defined(LZO_CFG_NO_UNALIGNED)
+#if defined(LZO_ABI_NEUTRAL_ENDIAN) || defined(LZO_ARCH_GENERIC)
+#  define LZO_CFG_NO_UNALIGNED 1
+#endif
+#endif
+#if defined(LZO_CFG_NO_UNALIGNED)
+#  undef LZO_OPT_UNALIGNED16
+#  undef LZO_OPT_UNALIGNED32
+#  undef LZO_OPT_UNALIGNED64
+#endif
+#if defined(LZO_CFG_NO_INLINE_ASM)
+#elif defined(LZO_ARCH_I386)
+#  define LZO_ASM_SYNTAX_GNUC 1
+#elif defined(LZO_ARCH_AMD64)
+#  define LZO_ASM_SYNTAX_GNUC 1
+#endif
+#if defined(LZO_ASM_SYNTAX_GNUC)
+#  define __LZO_ASM_CLOBBER         "cc", "memory"
+#endif
+
+#endif /* already included */
diff --git a/lib/lzo/lzointf.c b/lib/lzo/lzointf.c
new file mode 100644
index 0000000..182354b
--- /dev/null
+++ b/lib/lzo/lzointf.c
@@ -0,0 +1,37 @@
+/*
+ * LZO Public Kernel Interface
+ *
+ * Copyright (C) 2007 Nokia Corporation. All rights reserved.
+ *
+ * Author: Richard Purdie <rpurdie@openedhand.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 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 General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
+ * 02110-1301 USA
+ *
+ */
+
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/init.h>
+#include <linux/lzo.h>
+#include "lzoconf.h"
+
+EXPORT_SYMBOL_GPL(lzo_copyright);
+EXPORT_SYMBOL_GPL(lzo1x_1_compress);
+EXPORT_SYMBOL_GPL(lzo1x_decompress);
+EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
+
+MODULE_LICENSE("GPL")
+MODULE_DESCRIPTION("LZO compression library")
+
diff --git a/lib/lzo/minilzo.c b/lib/lzo/minilzo.c
new file mode 100644
index 0000000..c5c07fd
--- /dev/null
+++ b/lib/lzo/minilzo.c
@@ -0,0 +1,1771 @@
+/* minilzo.c -- mini subset of the LZO real-time data compression library
+
+   This file is part of the LZO real-time data compression library.
+
+   Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
+   All Rights Reserved.
+
+   The LZO library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License,
+   version 2, as published by the Free Software Foundation.
+
+   The LZO library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with the LZO library; see the file COPYING.
+   If not, write to the Free Software Foundation, Inc.,
+   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+   Markus F.X.J. Oberhumer <markus@oberhumer.com>
+
+   The full LZO package can be found at:
+   http://www.oberhumer.com/opensource/lzo/
+
+   Trimmed for kernel use by:
+   Richard Purdie <rpurdie@openedhand.com>
+ */
+
+#include <linux/kernel.h>
+#include <linux/limits.h>
+#include <linux/string.h>
+#include <linux/lzo.h>
+#include "lzoconf.h"
+
+#define __MINILZO_H
+
+#define MINILZO_VERSION         0x2020
+#define __LZO_IN_MINILZO
+#define LZO_BUILD
+
+#ifndef __LZO_CONF_H
+#define __LZO_CONF_H
+
+#if defined(LZO_ARCH_I086)
+#  define ACC_PTR_FP_OFF(x)     (((const unsigned __far*)&(x))[0])
+#  define ACC_PTR_FP_SEG(x)     (((const unsigned __far*)&(x))[1])
+#  define ACC_PTR_MK_FP(s,o)    ((void __far*)(((unsigned long)(s)<<16)+(unsigned)(o)))
+#endif
+
+#if !defined(lzo_uintptr_t)
+#  if (LZO_SIZEOF_SIZE_T == LZO_SIZEOF_VOID_P)
+#    define lzo_uintptr_t       size_t
+#  elif (LZO_SIZEOF_LONG == LZO_SIZEOF_VOID_P)
+#    define lzo_uintptr_t       unsigned long
+#  elif (LZO_SIZEOF_INT == LZO_SIZEOF_VOID_P)
+#    define lzo_uintptr_t       unsigned int
+#  elif (LZO_SIZEOF_LONG_LONG == LZO_SIZEOF_VOID_P)
+#    define lzo_uintptr_t       unsigned long long
+#  else
+#    define lzo_uintptr_t       size_t
+#  endif
+#endif
+LZO_COMPILE_TIME_ASSERT_HEADER(sizeof(lzo_uintptr_t) >= sizeof(lzo_voidp))
+
+#define lzo_memcmp(a,b,c)     memcmp(a,b,c)
+#define lzo_memcpy(a,b,c)     memcpy(a,b,c)
+#define lzo_memmove(a,b,c)    memmove(a,b,c)
+#define lzo_memset(a,b,c)     memset(a,b,c)
+
+#undef NDEBUG
+#undef LZO_DEBUG
+#define NDEBUG 1
+#undef assert
+#define assert(e) ((void)0)
+
+#  define BOUNDS_CHECKING_OFF_DURING(stmt)      stmt
+#  define BOUNDS_CHECKING_OFF_IN_EXPR(expr)     (expr)
+
+
+#define LZO_BYTE(x)       ((unsigned char) (x))
+
+#define LZO_MAX(a,b)        ((a) >= (b) ? (a) : (b))
+#define LZO_MIN(a,b)        ((a) <= (b) ? (a) : (b))
+#define LZO_MAX3(a,b,c)     ((a) >= (b) ? LZO_MAX(a,c) : LZO_MAX(b,c))
+#define LZO_MIN3(a,b,c)     ((a) <= (b) ? LZO_MIN(a,c) : LZO_MIN(b,c))
+
+#define lzo_sizeof(type)    ((lzo_uint) (sizeof(type)))
+
+#define LZO_HIGH(array)     ((lzo_uint) (sizeof(array)/sizeof(*(array))))
+
+#define LZO_SIZE(bits)      (1u << (bits))
+#define LZO_MASK(bits)      (LZO_SIZE(bits) - 1)
+
+#define LZO_LSIZE(bits)     (1ul << (bits))
+#define LZO_LMASK(bits)     (LZO_LSIZE(bits) - 1)
+
+#define LZO_USIZE(bits)     ((lzo_uint) 1 << (bits))
+#define LZO_UMASK(bits)     (LZO_USIZE(bits) - 1)
+
+#if !defined(DMUL)
+#define DMUL(a,b) ((lzo_xint) ((a) * (b)))
+#endif
+
+#if !defined(LZO_CFG_NO_UNALIGNED)
+#if defined(LZO_ARCH_AMD64) || defined(LZO_ARCH_I386)
+#  if (LZO_SIZEOF_SHORT == 2)
+#    define LZO_UNALIGNED_OK_2
+#  endif
+#  if (LZO_SIZEOF_INT == 4)
+#    define LZO_UNALIGNED_OK_4
+#  endif
+#endif
+#endif
+
+#if defined(LZO_UNALIGNED_OK_2)
+  LZO_COMPILE_TIME_ASSERT_HEADER(sizeof(short) == 2)
+#endif
+#if defined(LZO_UNALIGNED_OK_4)
+  LZO_COMPILE_TIME_ASSERT_HEADER(sizeof(lzo_uint32) == 4)
+#elif defined(LZO_ALIGNED_OK_4)
+  LZO_COMPILE_TIME_ASSERT_HEADER(sizeof(lzo_uint32) == 4)
+#endif
+
+#define MEMCPY8_DS(dest,src,len) \
+    lzo_memcpy(dest,src,len); dest += len; src += len
+
+#define BZERO8_PTR(s,l,n) \
+    lzo_memset((lzo_voidp)(s),0,(lzo_uint)(l)*(n))
+
+#define MEMCPY_DS(dest,src,len) \
+    do *dest++ = *src++; while (--len > 0)
+
+#ifndef __LZO_PTR_H
+#define __LZO_PTR_H
+
+
+#if !defined(lzo_uintptr_t)
+#    define lzo_uintptr_t   acc_uintptr_t
+#    ifdef __ACC_INTPTR_T_IS_POINTER
+#      define __LZO_UINTPTR_T_IS_POINTER 1
+#    endif
+#endif
+
+#if defined(LZO_ARCH_I086)
+#define PTR(a)              ((lzo_bytep) (a))
+#define PTR_ALIGNED_4(a)    ((ACC_PTR_FP_OFF(a) & 3) == 0)
+#define PTR_ALIGNED2_4(a,b) (((ACC_PTR_FP_OFF(a) | ACC_PTR_FP_OFF(b)) & 3) == 0)
+#else
+#define PTR(a)              ((lzo_uintptr_t) (a))
+#define PTR_LINEAR(a)       PTR(a)
+#define PTR_ALIGNED_4(a)    ((PTR_LINEAR(a) & 3) == 0)
+#define PTR_ALIGNED_8(a)    ((PTR_LINEAR(a) & 7) == 0)
+#define PTR_ALIGNED2_4(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0)
+#define PTR_ALIGNED2_8(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0)
+#endif
+
+#define PTR_LT(a,b)         (PTR(a) < PTR(b))
+#define PTR_GE(a,b)         (PTR(a) >= PTR(b))
+#define PTR_DIFF(a,b)       (PTR(a) - PTR(b))
+#define pd(a,b)             ((lzo_uint) ((a)-(b)))
+
+#endif
+
+#define LZO_DETERMINISTIC
+
+#define LZO_DICT_USE_PTR
+
+#if defined(LZO_DICT_USE_PTR)
+#  define lzo_dict_t    const lzo_bytep
+#  define lzo_dict_p    lzo_dict_t *
+#else
+#  define lzo_dict_t    lzo_uint
+#  define lzo_dict_p    lzo_dict_t *
+#endif
+
+#endif
+
+/* If you use the LZO library in a product, you *must* keep this
+ * copyright string in the executable of your product.
+ */
+
+const char __lzo_copyright[] =
+#if !defined(__LZO_IN_MINLZO)
+    LZO_VERSION_STRING;
+#else
+    "\r\n\n"
+    "LZO data compression library.\n"
+    "$Copyright: LZO (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Markus Franz Xaver Johannes Oberhumer\n"
+    "<markus@oberhumer.com>\n"
+    "http://www.oberhumer.com $\n\n"
+    "$Id: LZO version: v" LZO_VERSION_STRING ", " LZO_VERSION_DATE " $\n"
+    "$Built: " __DATE__ " " __TIME__ " $\n"
+#endif
+
+LZO_PUBLIC(const lzo_bytep)
+lzo_copyright(void)
+{
+    return (const lzo_bytep) __lzo_copyright;
+}
+
+#define LZO_BASE 65521u
+#define LZO_NMAX 5552
+
+#define do_compress         _lzo1x_1_do_compress
+
+#if !defined(MINILZO_CFG_SKIP_LZO1X_1_COMPRESS)
+
+#define LZO_NEED_DICT_H
+#define D_BITS          14
+#define D_INDEX1(d,p)       d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5)
+#define D_INDEX2(d,p)       d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
+
+#ifndef __LZO_CONFIG1X_H
+#define __LZO_CONFIG1X_H
+
+#if !defined(LZO1X) && !defined(LZO1Y) && !defined(LZO1Z)
+#  define LZO1X
+#endif
+
+#define LZO_EOF_CODE
+#undef LZO_DETERMINISTIC
+
+#define M1_MAX_OFFSET   0x0400
+#ifndef M2_MAX_OFFSET
+#define M2_MAX_OFFSET   0x0800
+#endif
+#define M3_MAX_OFFSET   0x4000
+#define M4_MAX_OFFSET   0xbfff
+
+#define MX_MAX_OFFSET   (M1_MAX_OFFSET + M2_MAX_OFFSET)
+
+#define M1_MIN_LEN      2
+#define M1_MAX_LEN      2
+#define M2_MIN_LEN      3
+#ifndef M2_MAX_LEN
+#define M2_MAX_LEN      8
+#endif
+#define M3_MIN_LEN      3
+#define M3_MAX_LEN      33
+#define M4_MIN_LEN      3
+#define M4_MAX_LEN      9
+
+#define M1_MARKER       0
+#define M2_MARKER       64
+#define M3_MARKER       32
+#define M4_MARKER       16
+
+#ifndef MIN_LOOKAHEAD
+#define MIN_LOOKAHEAD       (M2_MAX_LEN + 1)
+#endif
+
+#if defined(LZO_NEED_DICT_H)
+
+#ifndef LZO_HASH
+#define LZO_HASH            LZO_HASH_LZO_INCREMENTAL_B
+#endif
+#define DL_MIN_LEN          M2_MIN_LEN
+
+#ifndef __LZO_DICT_H
+#define __LZO_DICT_H
+
+
+#if !defined(D_BITS) && defined(DBITS)
+#  define D_BITS        DBITS
+#endif
+#if !defined(D_BITS)
+#  error "D_BITS is not defined"
+#endif
+#if (D_BITS < 16)
+#  define D_SIZE        LZO_SIZE(D_BITS)
+#  define D_MASK        LZO_MASK(D_BITS)
+#else
+#  define D_SIZE        LZO_USIZE(D_BITS)
+#  define D_MASK        LZO_UMASK(D_BITS)
+#endif
+#define D_HIGH          ((D_MASK >> 1) + 1)
+
+#if !defined(DD_BITS)
+#  define DD_BITS       0
+#endif
+#define DD_SIZE         LZO_SIZE(DD_BITS)
+#define DD_MASK         LZO_MASK(DD_BITS)
+
+#if !defined(DL_BITS)
+#  define DL_BITS       (D_BITS - DD_BITS)
+#endif
+#if (DL_BITS < 16)
+#  define DL_SIZE       LZO_SIZE(DL_BITS)
+#  define DL_MASK       LZO_MASK(DL_BITS)
+#else
+#  define DL_SIZE       LZO_USIZE(DL_BITS)
+#  define DL_MASK       LZO_UMASK(DL_BITS)
+#endif
+
+#if (D_BITS != DL_BITS + DD_BITS)
+#  error "D_BITS does not match"
+#endif
+#if (D_BITS < 8 || D_BITS > 18)
+#  error "invalid D_BITS"
+#endif
+#if (DL_BITS < 8 || DL_BITS > 20)
+#  error "invalid DL_BITS"
+#endif
+#if (DD_BITS < 0 || DD_BITS > 6)
+#  error "invalid DD_BITS"
+#endif
+
+#if !defined(DL_MIN_LEN)
+#  define DL_MIN_LEN    3
+#endif
+#if !defined(DL_SHIFT)
+#  define DL_SHIFT      ((DL_BITS + (DL_MIN_LEN - 1)) / DL_MIN_LEN)
+#endif
+
+#define LZO_HASH_GZIP                   1
+#define LZO_HASH_GZIP_INCREMENTAL       2
+#define LZO_HASH_LZO_INCREMENTAL_A      3
+#define LZO_HASH_LZO_INCREMENTAL_B      4
+
+#if !defined(LZO_HASH)
+#  error "choose a hashing strategy"
+#endif
+
+#undef DM
+#undef DX
+
+#if (DL_MIN_LEN == 3)
+#  define _DV2_A(p,shift1,shift2) \
+        (((( (lzo_xint)((p)[0]) << shift1) ^ (p)[1]) << shift2) ^ (p)[2])
+#  define _DV2_B(p,shift1,shift2) \
+        (((( (lzo_xint)((p)[2]) << shift1) ^ (p)[1]) << shift2) ^ (p)[0])
+#  define _DV3_B(p,shift1,shift2,shift3) \
+        ((_DV2_B((p)+1,shift1,shift2) << (shift3)) ^ (p)[0])
+#elif (DL_MIN_LEN == 2)
+#  define _DV2_A(p,shift1,shift2) \
+        (( (lzo_xint)(p[0]) << shift1) ^ p[1])
+#  define _DV2_B(p,shift1,shift2) \
+        (( (lzo_xint)(p[1]) << shift1) ^ p[2])
+#else
+#  error "invalid DL_MIN_LEN"
+#endif
+#define _DV_A(p,shift)      _DV2_A(p,shift,shift)
+#define _DV_B(p,shift)      _DV2_B(p,shift,shift)
+#define DA2(p,s1,s2) \
+        (((((lzo_xint)((p)[2]) << (s2)) + (p)[1]) << (s1)) + (p)[0])
+#define DS2(p,s1,s2) \
+        (((((lzo_xint)((p)[2]) << (s2)) - (p)[1]) << (s1)) - (p)[0])
+#define DX2(p,s1,s2) \
+        (((((lzo_xint)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0])
+#define DA3(p,s1,s2,s3) ((DA2((p)+1,s2,s3) << (s1)) + (p)[0])
+#define DS3(p,s1,s2,s3) ((DS2((p)+1,s2,s3) << (s1)) - (p)[0])
+#define DX3(p,s1,s2,s3) ((DX2((p)+1,s2,s3) << (s1)) ^ (p)[0])
+#define DMS(v,s)        ((lzo_uint) (((v) & (D_MASK >> (s))) << (s)))
+#define DM(v)           DMS(v,0)
+
+#if (LZO_HASH == LZO_HASH_GZIP)
+#  define _DINDEX(dv,p)     (_DV_A((p),DL_SHIFT))
+
+#elif (LZO_HASH == LZO_HASH_GZIP_INCREMENTAL)
+#  define __LZO_HASH_INCREMENTAL
+#  define DVAL_FIRST(dv,p)  dv = _DV_A((p),DL_SHIFT)
+#  define DVAL_NEXT(dv,p)   dv = (((dv) << DL_SHIFT) ^ p[2])
+#  define _DINDEX(dv,p)     (dv)
+#  define DVAL_LOOKAHEAD    DL_MIN_LEN
+
+#elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_A)
+#  define __LZO_HASH_INCREMENTAL
+#  define DVAL_FIRST(dv,p)  dv = _DV_A((p),5)
+#  define DVAL_NEXT(dv,p) \
+                dv ^= (lzo_xint)(p[-1]) << (2*5); dv = (((dv) << 5) ^ p[2])
+#  define _DINDEX(dv,p)     ((DMUL(0x9f5f,dv)) >> 5)
+#  define DVAL_LOOKAHEAD    DL_MIN_LEN
+
+#elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_B)
+#  define __LZO_HASH_INCREMENTAL
+#  define DVAL_FIRST(dv,p)  dv = _DV_B((p),5)
+#  define DVAL_NEXT(dv,p) \
+                dv ^= p[-1]; dv = (((dv) >> 5) ^ ((lzo_xint)(p[2]) << (2*5)))
+#  define _DINDEX(dv,p)     ((DMUL(0x9f5f,dv)) >> 5)
+#  define DVAL_LOOKAHEAD    DL_MIN_LEN
+
+#else
+#  error "choose a hashing strategy"
+#endif
+
+#ifndef DINDEX
+#define DINDEX(dv,p)        ((lzo_uint)((_DINDEX(dv,p)) & DL_MASK) << DD_BITS)
+#endif
+#if !defined(DINDEX1) && defined(D_INDEX1)
+#define DINDEX1             D_INDEX1
+#endif
+#if !defined(DINDEX2) && defined(D_INDEX2)
+#define DINDEX2             D_INDEX2
+#endif
+
+#if !defined(__LZO_HASH_INCREMENTAL)
+#  define DVAL_FIRST(dv,p)  ((void) 0)
+#  define DVAL_NEXT(dv,p)   ((void) 0)
+#  define DVAL_LOOKAHEAD    0
+#endif
+
+#if !defined(DVAL_ASSERT)
+#if defined(__LZO_HASH_INCREMENTAL) && !defined(NDEBUG)
+static void DVAL_ASSERT(lzo_xint dv, const lzo_bytep p)
+{
+    lzo_xint df;
+    DVAL_FIRST(df,(p));
+    assert(DINDEX(dv,p) == DINDEX(df,p));
+}
+#else
+#  define DVAL_ASSERT(dv,p) ((void) 0)
+#endif
+#endif
+
+#if defined(LZO_DICT_USE_PTR)
+#  define DENTRY(p,in)                          (p)
+#  define GINDEX(m_pos,m_off,dict,dindex,in)    m_pos = dict[dindex]
+#else
+#  define DENTRY(p,in)                          ((lzo_uint) ((p)-(in)))
+#  define GINDEX(m_pos,m_off,dict,dindex,in)    m_off = dict[dindex]
+#endif
+
+#if (DD_BITS == 0)
+
+#  define UPDATE_D(dict,drun,dv,p,in)       dict[ DINDEX(dv,p) ] = DENTRY(p,in)
+#  define UPDATE_I(dict,drun,index,p,in)    dict[index] = DENTRY(p,in)
+#  define UPDATE_P(ptr,drun,p,in)           (ptr)[0] = DENTRY(p,in)
+
+#else
+
+#  define UPDATE_D(dict,drun,dv,p,in)   \
+        dict[ DINDEX(dv,p) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
+#  define UPDATE_I(dict,drun,index,p,in)    \
+        dict[ (index) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
+#  define UPDATE_P(ptr,drun,p,in)   \
+        (ptr) [ drun++ ] = DENTRY(p,in); drun &= DD_MASK
+
+#endif
+
+#if defined(LZO_DICT_USE_PTR)
+
+#define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
+        (m_pos == NULL || (m_off = pd(ip, m_pos)) > max_offset)
+
+#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
+    (BOUNDS_CHECKING_OFF_IN_EXPR(( \
+        m_pos = ip - (lzo_uint) PTR_DIFF(ip,m_pos), \
+        PTR_LT(m_pos,in) || \
+        (m_off = (lzo_uint) PTR_DIFF(ip,m_pos)) <= 0 || \
+         m_off > max_offset )))
+
+#else
+
+#define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
+        (m_off == 0 || \
+         ((m_off = pd(ip, in) - m_off) > max_offset) || \
+         (m_pos = (ip) - (m_off), 0) )
+
+#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
+        (pd(ip, in) <= m_off || \
+         ((m_off = pd(ip, in) - m_off) > max_offset) || \
+         (m_pos = (ip) - (m_off), 0) )
+
+#endif
+
+#if defined(LZO_DETERMINISTIC)
+#  define LZO_CHECK_MPOS    LZO_CHECK_MPOS_DET
+#else
+#  define LZO_CHECK_MPOS    LZO_CHECK_MPOS_NON_DET
+#endif
+
+
+#endif
+
+#endif
+
+#endif
+
+#define DO_COMPRESS     lzo1x_1_compress
+
+static __lzo_noinline lzo_uint
+do_compress ( const lzo_bytep in , lzo_uint  in_len,
+                    lzo_bytep out, lzo_uintp out_len,
+                    lzo_voidp wrkmem )
+{
+    register const lzo_bytep ip;
+    lzo_bytep op;
+    const lzo_bytep const in_end = in + in_len;
+    const lzo_bytep const ip_end = in + in_len - M2_MAX_LEN - 5;
+    const lzo_bytep ii;
+    lzo_dict_p const dict = (lzo_dict_p) wrkmem;
+
+    op = out;
+    ip = in;
+    ii = ip;
+
+    ip += 4;
+    for (;;)
+    {
+        register const lzo_bytep m_pos;
+        lzo_uint m_off;
+        lzo_uint m_len;
+        lzo_uint dindex;
+
+        DINDEX1(dindex,ip);
+        GINDEX(m_pos,m_off,dict,dindex,in);
+        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
+            goto literal;
+#if 1
+        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
+            goto try_match;
+        DINDEX2(dindex,ip);
+#endif
+        GINDEX(m_pos,m_off,dict,dindex,in);
+        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
+            goto literal;
+        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
+            goto try_match;
+        goto literal;
+
+try_match:
+#if defined(LZO_UNALIGNED_OK_2)
+        if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
+#else
+        if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
+#endif
+        {
+        }
+        else
+        {
+            if __lzo_likely(m_pos[2] == ip[2])
+            {
+#if 0
+                if (m_off <= M2_MAX_OFFSET)
+                    goto match;
+                if (lit <= 3)
+                    goto match;
+                if (lit == 3)
+                {
+                    assert(op - 2 > out); op[-2] |= LZO_BYTE(3);
+                    *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
+                    goto code_match;
+                }
+                if (m_pos[3] == ip[3])
+#endif
+                    goto match;
+            }
+            else
+            {
+#if 0
+#if 0
+                if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3)
+#else
+                if (m_off <= M1_MAX_OFFSET && lit == 3)
+#endif
+                {
+                    register lzo_uint t;
+
+                    t = lit;
+                    assert(op - 2 > out); op[-2] |= LZO_BYTE(t);
+                    do *op++ = *ii++; while (--t > 0);
+                    assert(ii == ip);
+                    m_off -= 1;
+                    *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
+                    *op++ = LZO_BYTE(m_off >> 2);
+                    ip += 2;
+                    goto match_done;
+                }
+#endif
+            }
+        }
+
+literal:
+        UPDATE_I(dict,0,dindex,ip,in);
+        ++ip;
+        if __lzo_unlikely(ip >= ip_end)
+            break;
+        continue;
+
+match:
+        UPDATE_I(dict,0,dindex,ip,in);
+        if (pd(ip,ii) > 0)
+        {
+            register lzo_uint t = pd(ip,ii);
+
+            if (t <= 3)
+            {
+                assert(op - 2 > out);
+                op[-2] |= LZO_BYTE(t);
+            }
+            else if (t <= 18)
+                *op++ = LZO_BYTE(t - 3);
+            else
+            {
+                register lzo_uint tt = t - 18;
+
+                *op++ = 0;
+                while (tt > 255)
+                {
+                    tt -= 255;
+                    *op++ = 0;
+                }
+                assert(tt > 0);
+                *op++ = LZO_BYTE(tt);
+            }
+            do *op++ = *ii++; while (--t > 0);
+        }
+
+        assert(ii == ip);
+        ip += 3;
+        if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ ||
+            m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++
+#ifdef LZO1Y
+            || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++
+            || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++
+#endif
+           )
+        {
+            --ip;
+            m_len = pd(ip, ii);
+            assert(m_len >= 3); assert(m_len <= M2_MAX_LEN);
+
+            if (m_off <= M2_MAX_OFFSET)
+            {
+                m_off -= 1;
+#if defined(LZO1X)
+                *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
+                *op++ = LZO_BYTE(m_off >> 3);
+#elif defined(LZO1Y)
+                *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
+                *op++ = LZO_BYTE(m_off >> 2);
+#endif
+            }
+            else if (m_off <= M3_MAX_OFFSET)
+            {
+                m_off -= 1;
+                *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
+                goto m3_m4_offset;
+            }
+            else
+#if defined(LZO1X)
+            {
+                m_off -= 0x4000;
+                assert(m_off > 0); assert(m_off <= 0x7fff);
+                *op++ = LZO_BYTE(M4_MARKER |
+                                 ((m_off & 0x4000) >> 11) | (m_len - 2));
+                goto m3_m4_offset;
+            }
+#elif defined(LZO1Y)
+                goto m4_match;
+#endif
+        }
+        else
+        {
+            {
+                const lzo_bytep end = in_end;
+                const lzo_bytep m = m_pos + M2_MAX_LEN + 1;
+                while (ip < end && *m == *ip)
+                    m++, ip++;
+                m_len = pd(ip, ii);
+            }
+            assert(m_len > M2_MAX_LEN);
+
+            if (m_off <= M3_MAX_OFFSET)
+            {
+                m_off -= 1;
+                if (m_len <= 33)
+                    *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
+                else
+                {
+                    m_len -= 33;
+                    *op++ = M3_MARKER | 0;
+                    goto m3_m4_len;
+                }
+            }
+            else
+            {
+#if defined(LZO1Y)
+m4_match:
+#endif
+                m_off -= 0x4000;
+                assert(m_off > 0); assert(m_off <= 0x7fff);
+                if (m_len <= M4_MAX_LEN)
+                    *op++ = LZO_BYTE(M4_MARKER |
+                                     ((m_off & 0x4000) >> 11) | (m_len - 2));
+                else
+                {
+                    m_len -= M4_MAX_LEN;
+                    *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11));
+m3_m4_len:
+                    while (m_len > 255)
+                    {
+                        m_len -= 255;
+                        *op++ = 0;
+                    }
+                    assert(m_len > 0);
+                    *op++ = LZO_BYTE(m_len);
+                }
+            }
+
+m3_m4_offset:
+            *op++ = LZO_BYTE((m_off & 63) << 2);
+            *op++ = LZO_BYTE(m_off >> 6);
+        }
+
+#if 0
+match_done:
+#endif
+        ii = ip;
+        if __lzo_unlikely(ip >= ip_end)
+            break;
+    }
+
+    *out_len = pd(op, out);
+    return pd(in_end,ii);
+}
+
+LZO_PUBLIC(int)
+DO_COMPRESS      ( const lzo_bytep in , lzo_uint  in_len,
+                         lzo_bytep out, lzo_uintp out_len,
+                         lzo_voidp wrkmem )
+{
+    lzo_bytep op = out;
+    lzo_uint t;
+
+    if __lzo_unlikely(in_len <= M2_MAX_LEN + 5)
+        t = in_len;
+    else
+    {
+        t = do_compress(in,in_len,op,out_len,wrkmem);
+        op += *out_len;
+    }
+
+    if (t > 0)
+    {
+        const lzo_bytep ii = in + in_len - t;
+
+        if (op == out && t <= 238)
+            *op++ = LZO_BYTE(17 + t);
+        else if (t <= 3)
+            op[-2] |= LZO_BYTE(t);
+        else if (t <= 18)
+            *op++ = LZO_BYTE(t - 3);
+        else
+        {
+            lzo_uint tt = t - 18;
+
+            *op++ = 0;
+            while (tt > 255)
+            {
+                tt -= 255;
+                *op++ = 0;
+            }
+            assert(tt > 0);
+            *op++ = LZO_BYTE(tt);
+        }
+        do *op++ = *ii++; while (--t > 0);
+    }
+
+    *op++ = M4_MARKER | 1;
+    *op++ = 0;
+    *op++ = 0;
+
+    *out_len = pd(op, out);
+    return LZO_E_OK;
+}
+
+#endif
+
+#undef do_compress
+#undef DO_COMPRESS
+#undef LZO_HASH
+
+#undef LZO_TEST_OVERRUN
+#undef DO_DECOMPRESS
+#define DO_DECOMPRESS       lzo1x_decompress
+
+#if !defined(MINILZO_CFG_SKIP_LZO1X_DECOMPRESS)
+
+#if defined(LZO_TEST_OVERRUN)
+#  if !defined(LZO_TEST_OVERRUN_INPUT)
+#    define LZO_TEST_OVERRUN_INPUT       2
+#  endif
+#  if !defined(LZO_TEST_OVERRUN_OUTPUT)
+#    define LZO_TEST_OVERRUN_OUTPUT      2
+#  endif
+#  if !defined(LZO_TEST_OVERRUN_LOOKBEHIND)
+#    define LZO_TEST_OVERRUN_LOOKBEHIND
+#  endif
+#endif
+
+#undef TEST_IP
+#undef TEST_OP
+#undef TEST_LB
+#undef TEST_LBO
+#undef NEED_IP
+#undef NEED_OP
+#undef HAVE_TEST_IP
+#undef HAVE_TEST_OP
+#undef HAVE_NEED_IP
+#undef HAVE_NEED_OP
+#undef HAVE_ANY_IP
+#undef HAVE_ANY_OP
+
+#if defined(LZO_TEST_OVERRUN_INPUT)
+#  if (LZO_TEST_OVERRUN_INPUT >= 1)
+#    define TEST_IP             (ip < ip_end)
+#  endif
+#  if (LZO_TEST_OVERRUN_INPUT >= 2)
+#    define NEED_IP(x) \
+            if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x))  goto input_overrun
+#  endif
+#endif
+
+#if defined(LZO_TEST_OVERRUN_OUTPUT)
+#  if (LZO_TEST_OVERRUN_OUTPUT >= 1)
+#    define TEST_OP             (op <= op_end)
+#  endif
+#  if (LZO_TEST_OVERRUN_OUTPUT >= 2)
+#    undef TEST_OP
+#    define NEED_OP(x) \
+            if ((lzo_uint)(op_end - op) < (lzo_uint)(x))  goto output_overrun
+#  endif
+#endif
+
+#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
+#  define TEST_LB(m_pos)        if (m_pos < out || m_pos >= op) goto lookbehind_overrun
+#  define TEST_LBO(m_pos,o)     if (m_pos < out || m_pos >= op - (o)) goto lookbehind_overrun
+#else
+#  define TEST_LB(m_pos)        ((void) 0)
+#  define TEST_LBO(m_pos,o)     ((void) 0)
+#endif
+
+#if !defined(LZO_EOF_CODE) && !defined(TEST_IP)
+#  define TEST_IP               (ip < ip_end)
+#endif
+
+#if defined(TEST_IP)
+#  define HAVE_TEST_IP
+#else
+#  define TEST_IP               1
+#endif
+#if defined(TEST_OP)
+#  define HAVE_TEST_OP
+#else
+#  define TEST_OP               1
+#endif
+
+#if defined(NEED_IP)
+#  define HAVE_NEED_IP
+#else
+#  define NEED_IP(x)            ((void) 0)
+#endif
+#if defined(NEED_OP)
+#  define HAVE_NEED_OP
+#else
+#  define NEED_OP(x)            ((void) 0)
+#endif
+
+#if defined(HAVE_TEST_IP) || defined(HAVE_NEED_IP)
+#  define HAVE_ANY_IP
+#endif
+#if defined(HAVE_TEST_OP) || defined(HAVE_NEED_OP)
+#  define HAVE_ANY_OP
+#endif
+
+#undef __COPY4
+#define __COPY4(dst,src)    * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
+
+#undef COPY4
+#if defined(LZO_UNALIGNED_OK_4)
+#  define COPY4(dst,src)    __COPY4(dst,src)
+#elif defined(LZO_ALIGNED_OK_4)
+#  define COPY4(dst,src)    __COPY4((lzo_uintptr_t)(dst),(lzo_uintptr_t)(src))
+#endif
+
+#if defined(DO_DECOMPRESS)
+LZO_PUBLIC(int)
+DO_DECOMPRESS  ( const lzo_bytep in , lzo_uint  in_len,
+                       lzo_bytep out, lzo_uintp out_len,
+                       lzo_voidp wrkmem )
+#endif
+{
+    register lzo_bytep op;
+    register const lzo_bytep ip;
+    register lzo_uint t;
+#if defined(COPY_DICT)
+    lzo_uint m_off;
+    const lzo_bytep dict_end;
+#else
+    register const lzo_bytep m_pos;
+#endif
+
+    const lzo_bytep const ip_end = in + in_len;
+#if defined(HAVE_ANY_OP)
+    lzo_bytep const op_end = out + *out_len;
+#endif
+#if defined(LZO1Z)
+    lzo_uint last_m_off = 0;
+#endif
+
+    LZO_UNUSED(wrkmem);
+
+#if defined(COPY_DICT)
+    if (dict)
+    {
+        if (dict_len > M4_MAX_OFFSET)
+        {
+            dict += dict_len - M4_MAX_OFFSET;
+            dict_len = M4_MAX_OFFSET;
+        }
+        dict_end = dict + dict_len;
+    }
+    else
+    {
+        dict_len = 0;
+        dict_end = NULL;
+    }
+#endif
+
+    *out_len = 0;
+
+    op = out;
+    ip = in;
+
+    if (*ip > 17)
+    {
+        t = *ip++ - 17;
+        if (t < 4)
+            goto match_next;
+        assert(t > 0); NEED_OP(t); NEED_IP(t+1);
+        do *op++ = *ip++; while (--t > 0);
+        goto first_literal_run;
+    }
+
+    while (TEST_IP && TEST_OP)
+    {
+        t = *ip++;
+        if (t >= 16)
+            goto match;
+        if (t == 0)
+        {
+            NEED_IP(1);
+	    // VF: BUG HERE
+            while (*ip == 0)
+            {
+                t += 255;
+                ip++;
+                NEED_IP(1);
+            }
+            t += 15 + *ip++;
+        }
+        assert(t > 0); NEED_OP(t+3); NEED_IP(t+4);
+#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
+#if !defined(LZO_UNALIGNED_OK_4)
+        if (PTR_ALIGNED2_4(op,ip))
+        {
+#endif
+        COPY4(op,ip);
+        op += 4; ip += 4;
+        if (--t > 0)
+        {
+            if (t >= 4)
+            {
+                do {
+                    COPY4(op,ip);
+                    op += 4; ip += 4; t -= 4;
+                } while (t >= 4);
+                if (t > 0) do *op++ = *ip++; while (--t > 0);
+            }
+            else
+                do *op++ = *ip++; while (--t > 0);
+        }
+#if !defined(LZO_UNALIGNED_OK_4)
+        }
+        else
+#endif
+#endif
+#if !defined(LZO_UNALIGNED_OK_4)
+        {
+            *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
+            do *op++ = *ip++; while (--t > 0);
+        }
+#endif
+
+first_literal_run:
+
+        t = *ip++;
+        if (t >= 16)
+            goto match;
+#if defined(COPY_DICT)
+#if defined(LZO1Z)
+        m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
+        last_m_off = m_off;
+#else
+        m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
+#endif
+        NEED_OP(3);
+        t = 3; COPY_DICT(t,m_off)
+#else
+#if defined(LZO1Z)
+        t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
+        m_pos = op - t;
+        last_m_off = t;
+#else
+        m_pos = op - (1 + M2_MAX_OFFSET);
+        m_pos -= t >> 2;
+        m_pos -= *ip++ << 2;
+#endif
+        TEST_LB(m_pos); NEED_OP(3);
+        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
+#endif
+        goto match_done;
+
+        do {
+match:
+            if (t >= 64)
+            {
+#if defined(COPY_DICT)
+#if defined(LZO1X)
+                m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
+                t = (t >> 5) - 1;
+#elif defined(LZO1Y)
+                m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
+                t = (t >> 4) - 3;
+#elif defined(LZO1Z)
+                m_off = t & 0x1f;
+                if (m_off >= 0x1c)
+                    m_off = last_m_off;
+                else
+                {
+                    m_off = 1 + (m_off << 6) + (*ip++ >> 2);
+                    last_m_off = m_off;
+                }
+                t = (t >> 5) - 1;
+#endif
+#else
+#if defined(LZO1X)
+                m_pos = op - 1;
+                m_pos -= (t >> 2) & 7;
+                m_pos -= *ip++ << 3;
+                t = (t >> 5) - 1;
+#elif defined(LZO1Y)
+                m_pos = op - 1;
+                m_pos -= (t >> 2) & 3;
+                m_pos -= *ip++ << 2;
+                t = (t >> 4) - 3;
+#elif defined(LZO1Z)
+                {
+                    lzo_uint off = t & 0x1f;
+                    m_pos = op;
+                    if (off >= 0x1c)
+                    {
+                        assert(last_m_off > 0);
+                        m_pos -= last_m_off;
+                    }
+                    else
+                    {
+                        off = 1 + (off << 6) + (*ip++ >> 2);
+                        m_pos -= off;
+                        last_m_off = off;
+                    }
+                }
+                t = (t >> 5) - 1;
+#endif
+                TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
+                goto copy_match;
+#endif
+            }
+            else if (t >= 32)
+            {
+                t &= 31;
+                if (t == 0)
+                {
+                    NEED_IP(1);
+                    while (*ip == 0)
+                    {
+                        t += 255;
+                        ip++;
+                        NEED_IP(1);
+                    }
+                    t += 31 + *ip++;
+                }
+#if defined(COPY_DICT)
+#if defined(LZO1Z)
+                m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
+                last_m_off = m_off;
+#else
+                m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
+#endif
+#else
+#if defined(LZO1Z)
+                {
+                    lzo_uint off = 1 + (ip[0] << 6) + (ip[1] >> 2);
+                    m_pos = op - off;
+                    last_m_off = off;
+                }
+#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
+                m_pos = op - 1;
+                m_pos -= (* (const lzo_ushortp) ip) >> 2;
+#else
+                m_pos = op - 1;
+                m_pos -= (ip[0] >> 2) + (ip[1] << 6);
+#endif
+#endif
+                ip += 2;
+            }
+            else if (t >= 16)
+            {
+#if defined(COPY_DICT)
+                m_off = (t & 8) << 11;
+#else
+                m_pos = op;
+                m_pos -= (t & 8) << 11;
+#endif
+                t &= 7;
+                if (t == 0)
+                {
+                    NEED_IP(1);
+                    while (*ip == 0)
+                    {
+                        t += 255;
+                        ip++;
+                        NEED_IP(1);
+                    }
+                    t += 7 + *ip++;
+                }
+#if defined(COPY_DICT)
+#if defined(LZO1Z)
+                m_off += (ip[0] << 6) + (ip[1] >> 2);
+#else
+                m_off += (ip[0] >> 2) + (ip[1] << 6);
+#endif
+                ip += 2;
+                if (m_off == 0)
+                    goto eof_found;
+                m_off += 0x4000;
+#if defined(LZO1Z)
+                last_m_off = m_off;
+#endif
+#else
+#if defined(LZO1Z)
+                m_pos -= (ip[0] << 6) + (ip[1] >> 2);
+#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
+                m_pos -= (* (const lzo_ushortp) ip) >> 2;
+#else
+                m_pos -= (ip[0] >> 2) + (ip[1] << 6);
+#endif
+                ip += 2;
+                if (m_pos == op)
+                    goto eof_found;
+                m_pos -= 0x4000;
+#if defined(LZO1Z)
+                last_m_off = pd((const lzo_bytep)op, m_pos);
+#endif
+#endif
+            }
+            else
+            {
+#if defined(COPY_DICT)
+#if defined(LZO1Z)
+                m_off = 1 + (t << 6) + (*ip++ >> 2);
+                last_m_off = m_off;
+#else
+                m_off = 1 + (t >> 2) + (*ip++ << 2);
+#endif
+                NEED_OP(2);
+                t = 2; COPY_DICT(t,m_off)
+#else
+#if defined(LZO1Z)
+                t = 1 + (t << 6) + (*ip++ >> 2);
+                m_pos = op - t;
+                last_m_off = t;
+#else
+                m_pos = op - 1;
+                m_pos -= t >> 2;
+                m_pos -= *ip++ << 2;
+#endif
+                TEST_LB(m_pos); NEED_OP(2);
+                *op++ = *m_pos++; *op++ = *m_pos;
+#endif
+                goto match_done;
+            }
+
+#if defined(COPY_DICT)
+
+            NEED_OP(t+3-1);
+            t += 3-1; COPY_DICT(t,m_off)
+
+#else
+
+            TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
+#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
+#if !defined(LZO_UNALIGNED_OK_4)
+            if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos))
+            {
+                assert((op - m_pos) >= 4);
+#else
+            if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
+            {
+#endif
+                COPY4(op,m_pos);
+                op += 4; m_pos += 4; t -= 4 - (3 - 1);
+                do {
+                    COPY4(op,m_pos);
+                    op += 4; m_pos += 4; t -= 4;
+                } while (t >= 4);
+                if (t > 0) do *op++ = *m_pos++; while (--t > 0);
+            }
+            else
+#endif
+            {
+copy_match:
+                *op++ = *m_pos++; *op++ = *m_pos++;
+                do *op++ = *m_pos++; while (--t > 0);
+            }
+
+#endif
+
+match_done:
+#if defined(LZO1Z)
+            t = ip[-1] & 3;
+#else
+            t = ip[-2] & 3;
+#endif
+            if (t == 0)
+                break;
+
+match_next:
+            assert(t > 0); assert(t < 4); NEED_OP(t); NEED_IP(t+1);
+#if 0
+            do *op++ = *ip++; while (--t > 0);
+#else
+            *op++ = *ip++;
+            if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } }
+#endif
+            t = *ip++;
+        } while (TEST_IP && TEST_OP);
+    }
+
+#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
+    *out_len = pd(op, out);
+    return LZO_E_EOF_NOT_FOUND;
+#endif
+
+eof_found:
+    assert(t == 1);
+    *out_len = pd(op, out);
+    return (ip == ip_end ? LZO_E_OK :
+           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
+
+#if defined(HAVE_NEED_IP)
+input_overrun:
+    *out_len = pd(op, out);
+    return LZO_E_INPUT_OVERRUN;
+#endif
+
+#if defined(HAVE_NEED_OP)
+output_overrun:
+    *out_len = pd(op, out);
+    return LZO_E_OUTPUT_OVERRUN;
+#endif
+
+#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
+lookbehind_overrun:
+    *out_len = pd(op, out);
+    return LZO_E_LOOKBEHIND_OVERRUN;
+#endif
+}
+
+#endif
+
+#define LZO_TEST_OVERRUN
+#undef DO_DECOMPRESS
+#define DO_DECOMPRESS       lzo1x_decompress_safe
+
+#if !defined(MINILZO_CFG_SKIP_LZO1X_DECOMPRESS_SAFE)
+
+#if defined(LZO_TEST_OVERRUN)
+#  if !defined(LZO_TEST_OVERRUN_INPUT)
+#    define LZO_TEST_OVERRUN_INPUT       2
+#  endif
+#  if !defined(LZO_TEST_OVERRUN_OUTPUT)
+#    define LZO_TEST_OVERRUN_OUTPUT      2
+#  endif
+#  if !defined(LZO_TEST_OVERRUN_LOOKBEHIND)
+#    define LZO_TEST_OVERRUN_LOOKBEHIND
+#  endif
+#endif
+
+#undef TEST_IP
+#undef TEST_OP
+#undef TEST_LB
+#undef TEST_LBO
+#undef NEED_IP
+#undef NEED_OP
+#undef HAVE_TEST_IP
+#undef HAVE_TEST_OP
+#undef HAVE_NEED_IP
+#undef HAVE_NEED_OP
+#undef HAVE_ANY_IP
+#undef HAVE_ANY_OP
+
+#if defined(LZO_TEST_OVERRUN_INPUT)
+#  if (LZO_TEST_OVERRUN_INPUT >= 1)
+#    define TEST_IP             (ip < ip_end)
+#  endif
+#  if (LZO_TEST_OVERRUN_INPUT >= 2)
+#    define NEED_IP(x) \
+            if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x))  goto input_overrun
+#  endif
+#endif
+
+#if defined(LZO_TEST_OVERRUN_OUTPUT)
+#  if (LZO_TEST_OVERRUN_OUTPUT >= 1)
+#    define TEST_OP             (op <= op_end)
+#  endif
+#  if (LZO_TEST_OVERRUN_OUTPUT >= 2)
+#    undef TEST_OP
+#    define NEED_OP(x) \
+            if ((lzo_uint)(op_end - op) < (lzo_uint)(x))  goto output_overrun
+#  endif
+#endif
+
+#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
+#  define TEST_LB(m_pos)        if (m_pos < out || m_pos >= op) goto lookbehind_overrun
+#  define TEST_LBO(m_pos,o)     if (m_pos < out || m_pos >= op - (o)) goto lookbehind_overrun
+#else
+#  define TEST_LB(m_pos)        ((void) 0)
+#  define TEST_LBO(m_pos,o)     ((void) 0)
+#endif
+
+#if !defined(LZO_EOF_CODE) && !defined(TEST_IP)
+#  define TEST_IP               (ip < ip_end)
+#endif
+
+#if defined(TEST_IP)
+#  define HAVE_TEST_IP
+#else
+#  define TEST_IP               1
+#endif
+#if defined(TEST_OP)
+#  define HAVE_TEST_OP
+#else
+#  define TEST_OP               1
+#endif
+
+#if defined(NEED_IP)
+#  define HAVE_NEED_IP
+#else
+#  define NEED_IP(x)            ((void) 0)
+#endif
+#if defined(NEED_OP)
+#  define HAVE_NEED_OP
+#else
+#  define NEED_OP(x)            ((void) 0)
+#endif
+
+#if defined(HAVE_TEST_IP) || defined(HAVE_NEED_IP)
+#  define HAVE_ANY_IP
+#endif
+#if defined(HAVE_TEST_OP) || defined(HAVE_NEED_OP)
+#  define HAVE_ANY_OP
+#endif
+
+#undef __COPY4
+#define __COPY4(dst,src)    * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
+
+#undef COPY4
+#if defined(LZO_UNALIGNED_OK_4)
+#  define COPY4(dst,src)    __COPY4(dst,src)
+#elif defined(LZO_ALIGNED_OK_4)
+#  define COPY4(dst,src)    __COPY4((lzo_uintptr_t)(dst),(lzo_uintptr_t)(src))
+#endif
+
+#if defined(DO_DECOMPRESS)
+LZO_PUBLIC(int)
+DO_DECOMPRESS  ( const lzo_bytep in , lzo_uint  in_len,
+                       lzo_bytep out, lzo_uintp out_len,
+                       lzo_voidp wrkmem )
+#endif
+{
+    register lzo_bytep op;
+    register const lzo_bytep ip;
+    register lzo_uint t;
+#if defined(COPY_DICT)
+    lzo_uint m_off;
+    const lzo_bytep dict_end;
+#else
+    register const lzo_bytep m_pos;
+#endif
+
+    const lzo_bytep const ip_end = in + in_len;
+#if defined(HAVE_ANY_OP)
+    lzo_bytep const op_end = out + *out_len;
+#endif
+#if defined(LZO1Z)
+    lzo_uint last_m_off = 0;
+#endif
+
+    LZO_UNUSED(wrkmem);
+
+#if defined(COPY_DICT)
+    if (dict)
+    {
+        if (dict_len > M4_MAX_OFFSET)
+        {
+            dict += dict_len - M4_MAX_OFFSET;
+            dict_len = M4_MAX_OFFSET;
+        }
+        dict_end = dict + dict_len;
+    }
+    else
+    {
+        dict_len = 0;
+        dict_end = NULL;
+    }
+#endif
+
+    *out_len = 0;
+
+    op = out;
+    ip = in;
+
+    if (*ip > 17)
+    {
+        t = *ip++ - 17;
+        if (t < 4)
+            goto match_next;
+        assert(t > 0); NEED_OP(t); NEED_IP(t+1);
+        do *op++ = *ip++; while (--t > 0);
+        goto first_literal_run;
+    }
+
+    while (TEST_IP && TEST_OP)
+    {
+        t = *ip++;
+        if (t >= 16)
+            goto match;
+        if (t == 0)
+        {
+            NEED_IP(1);
+            while (*ip == 0)
+            {
+                t += 255;
+                ip++;
+                NEED_IP(1);
+            }
+            t += 15 + *ip++;
+        }
+        assert(t > 0); NEED_OP(t+3); NEED_IP(t+4);
+#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
+#if !defined(LZO_UNALIGNED_OK_4)
+        if (PTR_ALIGNED2_4(op,ip))
+        {
+#endif
+        COPY4(op,ip);
+        op += 4; ip += 4;
+        if (--t > 0)
+        {
+            if (t >= 4)
+            {
+                do {
+                    COPY4(op,ip);
+                    op += 4; ip += 4; t -= 4;
+                } while (t >= 4);
+                if (t > 0) do *op++ = *ip++; while (--t > 0);
+            }
+            else
+                do *op++ = *ip++; while (--t > 0);
+        }
+#if !defined(LZO_UNALIGNED_OK_4)
+        }
+        else
+#endif
+#endif
+#if !defined(LZO_UNALIGNED_OK_4)
+        {
+            *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
+            do *op++ = *ip++; while (--t > 0);
+        }
+#endif
+
+first_literal_run:
+
+        t = *ip++;
+        if (t >= 16)
+            goto match;
+#if defined(COPY_DICT)
+#if defined(LZO1Z)
+        m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
+        last_m_off = m_off;
+#else
+        m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
+#endif
+        NEED_OP(3);
+        t = 3; COPY_DICT(t,m_off)
+#else
+#if defined(LZO1Z)
+        t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
+        m_pos = op - t;
+        last_m_off = t;
+#else
+        m_pos = op - (1 + M2_MAX_OFFSET);
+        m_pos -= t >> 2;
+        m_pos -= *ip++ << 2;
+#endif
+        TEST_LB(m_pos); NEED_OP(3);
+        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
+#endif
+        goto match_done;
+
+        do {
+match:
+            if (t >= 64)
+            {
+#if defined(COPY_DICT)
+#if defined(LZO1X)
+                m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
+                t = (t >> 5) - 1;
+#elif defined(LZO1Y)
+                m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
+                t = (t >> 4) - 3;
+#elif defined(LZO1Z)
+                m_off = t & 0x1f;
+                if (m_off >= 0x1c)
+                    m_off = last_m_off;
+                else
+                {
+                    m_off = 1 + (m_off << 6) + (*ip++ >> 2);
+                    last_m_off = m_off;
+                }
+                t = (t >> 5) - 1;
+#endif
+#else
+#if defined(LZO1X)
+                m_pos = op - 1;
+                m_pos -= (t >> 2) & 7;
+                m_pos -= *ip++ << 3;
+                t = (t >> 5) - 1;
+#elif defined(LZO1Y)
+                m_pos = op - 1;
+                m_pos -= (t >> 2) & 3;
+                m_pos -= *ip++ << 2;
+                t = (t >> 4) - 3;
+#elif defined(LZO1Z)
+                {
+                    lzo_uint off = t & 0x1f;
+                    m_pos = op;
+                    if (off >= 0x1c)
+                    {
+                        assert(last_m_off > 0);
+                        m_pos -= last_m_off;
+                    }
+                    else
+                    {
+                        off = 1 + (off << 6) + (*ip++ >> 2);
+                        m_pos -= off;
+                        last_m_off = off;
+                    }
+                }
+                t = (t >> 5) - 1;
+#endif
+                TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
+                goto copy_match;
+#endif
+            }
+            else if (t >= 32)
+            {
+                t &= 31;
+                if (t == 0)
+                {
+                    NEED_IP(1);
+                    while (*ip == 0)
+                    {
+                        t += 255;
+                        ip++;
+                        NEED_IP(1);
+                    }
+                    t += 31 + *ip++;
+                }
+#if defined(COPY_DICT)
+#if defined(LZO1Z)
+                m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
+                last_m_off = m_off;
+#else
+                m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
+#endif
+#else
+#if defined(LZO1Z)
+                {
+                    lzo_uint off = 1 + (ip[0] << 6) + (ip[1] >> 2);
+                    m_pos = op - off;
+                    last_m_off = off;
+                }
+#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
+                m_pos = op - 1;
+                m_pos -= (* (const lzo_ushortp) ip) >> 2;
+#else
+                m_pos = op - 1;
+                m_pos -= (ip[0] >> 2) + (ip[1] << 6);
+#endif
+#endif
+                ip += 2;
+            }
+            else if (t >= 16)
+            {
+#if defined(COPY_DICT)
+                m_off = (t & 8) << 11;
+#else
+                m_pos = op;
+                m_pos -= (t & 8) << 11;
+#endif
+                t &= 7;
+                if (t == 0)
+                {
+                    NEED_IP(1);
+                    while (*ip == 0)
+                    {
+                        t += 255;
+                        ip++;
+                        NEED_IP(1);
+                    }
+                    t += 7 + *ip++;
+                }
+#if defined(COPY_DICT)
+#if defined(LZO1Z)
+                m_off += (ip[0] << 6) + (ip[1] >> 2);
+#else
+                m_off += (ip[0] >> 2) + (ip[1] << 6);
+#endif
+                ip += 2;
+                if (m_off == 0)
+                    goto eof_found;
+                m_off += 0x4000;
+#if defined(LZO1Z)
+                last_m_off = m_off;
+#endif
+#else
+#if defined(LZO1Z)
+                m_pos -= (ip[0] << 6) + (ip[1] >> 2);
+#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
+                m_pos -= (* (const lzo_ushortp) ip) >> 2;
+#else
+                m_pos -= (ip[0] >> 2) + (ip[1] << 6);
+#endif
+                ip += 2;
+                if (m_pos == op)
+                    goto eof_found;
+                m_pos -= 0x4000;
+#if defined(LZO1Z)
+                last_m_off = pd((const lzo_bytep)op, m_pos);
+#endif
+#endif
+            }
+            else
+            {
+#if defined(COPY_DICT)
+#if defined(LZO1Z)
+                m_off = 1 + (t << 6) + (*ip++ >> 2);
+                last_m_off = m_off;
+#else
+                m_off = 1 + (t >> 2) + (*ip++ << 2);
+#endif
+                NEED_OP(2);
+                t = 2; COPY_DICT(t,m_off)
+#else
+#if defined(LZO1Z)
+                t = 1 + (t << 6) + (*ip++ >> 2);
+                m_pos = op - t;
+                last_m_off = t;
+#else
+                m_pos = op - 1;
+                m_pos -= t >> 2;
+                m_pos -= *ip++ << 2;
+#endif
+                TEST_LB(m_pos); NEED_OP(2);
+                *op++ = *m_pos++; *op++ = *m_pos;
+#endif
+                goto match_done;
+            }
+
+#if defined(COPY_DICT)
+
+            NEED_OP(t+3-1);
+            t += 3-1; COPY_DICT(t,m_off)
+
+#else
+
+            TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
+#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
+#if !defined(LZO_UNALIGNED_OK_4)
+            if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos))
+            {
+                assert((op - m_pos) >= 4);
+#else
+            if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
+            {
+#endif
+                COPY4(op,m_pos);
+                op += 4; m_pos += 4; t -= 4 - (3 - 1);
+                do {
+                    COPY4(op,m_pos);
+                    op += 4; m_pos += 4; t -= 4;
+                } while (t >= 4);
+                if (t > 0) do *op++ = *m_pos++; while (--t > 0);
+            }
+            else
+#endif
+            {
+copy_match:
+                *op++ = *m_pos++; *op++ = *m_pos++;
+                do *op++ = *m_pos++; while (--t > 0);
+            }
+
+#endif
+
+match_done:
+#if defined(LZO1Z)
+            t = ip[-1] & 3;
+#else
+            t = ip[-2] & 3;
+#endif
+            if (t == 0)
+                break;
+
+match_next:
+            assert(t > 0); assert(t < 4); NEED_OP(t); NEED_IP(t+1);
+#if 0
+            do *op++ = *ip++; while (--t > 0);
+#else
+            *op++ = *ip++;
+            if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } }
+#endif
+            t = *ip++;
+        } while (TEST_IP && TEST_OP);
+    }
+
+#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
+    *out_len = pd(op, out);
+    return LZO_E_EOF_NOT_FOUND;
+#endif
+
+eof_found:
+    assert(t == 1);
+    *out_len = pd(op, out);
+    return (ip == ip_end ? LZO_E_OK :
+           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
+
+#if defined(HAVE_NEED_IP)
+input_overrun:
+    *out_len = pd(op, out);
+    return LZO_E_INPUT_OVERRUN;
+#endif
+
+#if defined(HAVE_NEED_OP)
+output_overrun:
+    *out_len = pd(op, out);
+    return LZO_E_OUTPUT_OVERRUN;
+#endif
+
+#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
+lookbehind_overrun:
+    *out_len = pd(op, out);
+    return LZO_E_LOOKBEHIND_OVERRUN;
+#endif
+}
+
+#endif




^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-02  8:56 [PATCH] Add LZO1X compression support to the kernel Richard Purdie
@ 2007-05-02  9:35 ` Pekka Enberg
  2007-05-04 18:28   ` Satyam Sharma
  2007-05-10  6:21 ` Andrew Morton
  2007-05-12 11:17 ` Adrian Bunk
  2 siblings, 1 reply; 19+ messages in thread
From: Pekka Enberg @ 2007-05-02  9:35 UTC (permalink / raw)
  To: Richard Purdie; +Cc: LKML, akpm, torvalds, David Woodhouse

On 5/2/07, Richard Purdie <richard@openedhand.com> wrote:
> I realise a maze of ifdefs still remain. I've already spent a lot of
> time removing a ton of them and going much further might start to affect
> diffability of the code - I hoping whats there is a good compromise.

I really don't think this is suitable for inclusion in the kernel. Any
reason why you don't just fork the code and clean it up properly? Sure
it will take some more work to track the original but how hard can it
be for ~1700 lines of code?

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-02  9:35 ` Pekka Enberg
@ 2007-05-04 18:28   ` Satyam Sharma
  0 siblings, 0 replies; 19+ messages in thread
From: Satyam Sharma @ 2007-05-04 18:28 UTC (permalink / raw)
  To: Pekka Enberg; +Cc: Richard Purdie, LKML, akpm, torvalds, David Woodhouse

Hi Richard, Pekka,

On 5/2/07, Pekka Enberg <penberg@cs.helsinki.fi> wrote:
> On 5/2/07, Richard Purdie <richard@openedhand.com> wrote:
> > I realise a maze of ifdefs still remain. I've already spent a lot of
> > time removing a ton of them and going much further might start to affect
> > diffability of the code - I hoping whats there is a good compromise.
>
> I really don't think this is suitable for inclusion in the kernel. Any
> reason why you don't just fork the code and clean it up properly? Sure
> it will take some more work to track the original but how hard can it
> be for ~1700 lines of code?

I'd have to agree with that. When something gets ported to the kernel
(from some userspace library, or from any other piece of software),
then it _must_ be ported completely and follow the usual kernel style.
In fact I bet you can knock off a cool couple of hundred lines of gunk
from the patch just by doing a proper port and getting rid of those
pointless typedefs, for example.

(On an unrelated note/rant, this was one of the reasons why I
absolutely hate those MODSIGN patches being maintained by Red
Hat/Fedora/etc that port the GNU MPI library to the kernel but don't
do so properly, so that it can be diffed with future GNU MP releases
for easy maintainability -- with the result that the patch ends up
containing arch-specific assembly for platforms that Linux doesn't
even run on! Good to see that at least you've taken the pains to avoid
that kind of brain damage, but a full port would be better)

Thanks,
Satyam

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-02  8:56 [PATCH] Add LZO1X compression support to the kernel Richard Purdie
  2007-05-02  9:35 ` Pekka Enberg
@ 2007-05-10  6:21 ` Andrew Morton
  2007-05-10  8:26   ` David Woodhouse
  2007-05-10 14:30   ` Jan Engelhardt
  2007-05-12 11:17 ` Adrian Bunk
  2 siblings, 2 replies; 19+ messages in thread
From: Andrew Morton @ 2007-05-10  6:21 UTC (permalink / raw)
  To: Richard Purdie; +Cc: LKML, torvalds, David Woodhouse

On Wed, 02 May 2007 09:56:23 +0100 Richard Purdie <richard@openedhand.com> wrote:

> Current thinking is that lzo should get merged directly followed by the
> subsystem parts through their specific trees. It appears this should
> make it onto LKML despite the size so here goes.
> 
> Please keep in mind I haven't reformatted the LZO code itself as if I do
> so, it will make maintenance of it against any changes in LZO itself
> near impossible. In its current form, it should be possible to diff
> against upstream. All the bad formatting is confined to a handful of
> files in lib/lzo/ and the kernel interface should be clean.
> 
> I realise a maze of ifdefs still remain. I've already spent a lot of
> time removing a ton of them and going much further might start to affect
> diffability of the code - I hoping whats there is a good compromise.
> 
> I've asked the LZO author about the comments on lzo_copyright function
> but the code is GPLv2 licensed so is suitable for inclusion in the
> kernel.
> 
> 
> 
> Add LZO1X compression/decompression support to the kernel.
> 
> This is based on the standard userspace lzo library, particularly
> minilzo with the headers much trimmed down and simplified for kernel
> use. Its structured so that it should still diff with the userspace
> version for ease of future updating.

Well that's attractive-looking code.

Why is this needed?  What code plans to use it?

How many buffer overruns are there in it?


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-10  6:21 ` Andrew Morton
@ 2007-05-10  8:26   ` David Woodhouse
  2007-05-10  8:53     ` Richard Purdie
  2007-05-10 14:30   ` Jan Engelhardt
  1 sibling, 1 reply; 19+ messages in thread
From: David Woodhouse @ 2007-05-10  8:26 UTC (permalink / raw)
  To: Andrew Morton; +Cc: Richard Purdie, LKML, torvalds

On Wed, 2007-05-09 at 23:21 -0700, Andrew Morton wrote:
> Well that's attractive-looking code.

It's compression code. I've never seen compression code look nice :)

> Why is this needed?  What code plans to use it?

I'm itching to use it in JFFS2. Richard claims a 10% boot time speedup
and 40% improvement on file read speed, with only a slight drop in the
file compression ratio (when compared to zlib).

> How many buffer overruns are there in it?

That I'm afraid I cannot tell you.

-- 
dwmw2


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-10  8:26   ` David Woodhouse
@ 2007-05-10  8:53     ` Richard Purdie
  0 siblings, 0 replies; 19+ messages in thread
From: Richard Purdie @ 2007-05-10  8:53 UTC (permalink / raw)
  To: David Woodhouse, Andrew Morton; +Cc: LKML, torvalds

On Thu, 2007-05-10 at 09:26 +0100, David Woodhouse wrote:
> On Wed, 2007-05-09 at 23:21 -0700, Andrew Morton wrote:
> > Well that's attractive-looking code.
> 
> It's compression code. I've never seen compression code look nice :)
> 
> > Why is this needed?  What code plans to use it?
> 
> I'm itching to use it in JFFS2. Richard claims a 10% boot time speedup
> and 40% improvement on file read speed, with only a slight drop in the
> file compression ratio (when compared to zlib).

Right, the speed improvement is noticeable and useful. JFFS2 is the
primary use case, I've also implemented a crypto interface for it.

> > How many buffer overruns are there in it?
> 
> That I'm afraid I cannot tell you.

There is a "safe" decompression function which does bounds checking so
its at least been thought about by the author. The code has been around
in userspace for a while so hopefully any issues have been ironed out
before now.

Richard


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-10  6:21 ` Andrew Morton
  2007-05-10  8:26   ` David Woodhouse
@ 2007-05-10 14:30   ` Jan Engelhardt
  1 sibling, 0 replies; 19+ messages in thread
From: Jan Engelhardt @ 2007-05-10 14:30 UTC (permalink / raw)
  To: Andrew Morton; +Cc: Richard Purdie, LKML, torvalds, David Woodhouse


On May 9 2007 23:21, Andrew Morton wrote:
>On Wed, 02 May 2007 09:56:23 +0100 Richard Purdie <richard@openedhand.com> wrote:
>
>> Add LZO1X compression/decompression support to the kernel.
>> 
>> This is based on the standard userspace lzo library, particularly
>> minilzo with the headers much trimmed down and simplified for kernel
>> use. Its structured so that it should still diff with the userspace
>> version for ease of future updating.
>
>Well that's attractive-looking code.
>Why is this needed?  What code plans to use it?

Perhaps squashfs [not included] could use it as an alternative to
zlib or LZMA* [not included either].

* That's floating patches not in the official squashfs AFAICT.


	Jan
-- 

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-02  8:56 [PATCH] Add LZO1X compression support to the kernel Richard Purdie
  2007-05-02  9:35 ` Pekka Enberg
  2007-05-10  6:21 ` Andrew Morton
@ 2007-05-12 11:17 ` Adrian Bunk
  2007-05-12 15:17   ` Richard Purdie
  2 siblings, 1 reply; 19+ messages in thread
From: Adrian Bunk @ 2007-05-12 11:17 UTC (permalink / raw)
  To: Richard Purdie; +Cc: LKML, akpm, torvalds, David Woodhouse

On Wed, May 02, 2007 at 09:56:23AM +0100, Richard Purdie wrote:
>...
> I've asked the LZO author about the comments on lzo_copyright function
> but the code is GPLv2 licensed so is suitable for inclusion in the
> kernel.

This sounds as if LZO is GPL incompatible similar to code under
the 4 clause BSD licence.

>...
> +/* If you use the LZO library in a product, you *must* keep this
> + * copyright string in the executable of your product.
> + */
> +
> +const char __lzo_copyright[] =
> +#if !defined(__LZO_IN_MINLZO)
> +    LZO_VERSION_STRING;
> +#else
> +    "\r\n\n"
> +    "LZO data compression library.\n"
> +    "$Copyright: LZO (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Markus Franz Xaver Johannes Oberhumer\n"
> +    "<markus@oberhumer.com>\n"
> +    "http://www.oberhumer.com $\n\n"
> +    "$Id: LZO version: v" LZO_VERSION_STRING ", " LZO_VERSION_DATE " $\n"
> +    "$Built: " __DATE__ " " __TIME__ " $\n"
> +#endif
>...

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-12 11:17 ` Adrian Bunk
@ 2007-05-12 15:17   ` Richard Purdie
  2007-05-12 16:47     ` Andrew Morton
  0 siblings, 1 reply; 19+ messages in thread
From: Richard Purdie @ 2007-05-12 15:17 UTC (permalink / raw)
  To: Adrian Bunk; +Cc: LKML, akpm, torvalds, David Woodhouse

On Sat, 2007-05-12 at 13:17 +0200, Adrian Bunk wrote:
> On Wed, May 02, 2007 at 09:56:23AM +0100, Richard Purdie wrote:
> >...
> > I've asked the LZO author about the comments on lzo_copyright function
> > but the code is GPLv2 licensed so is suitable for inclusion in the
> > kernel.
> 
> This sounds as if LZO is GPL incompatible similar to code under
> the 4 clause BSD licence.
> 
> >...
> > +/* If you use the LZO library in a product, you *must* keep this
> > + * copyright string in the executable of your product.
> > + */

I've had a reply from the copyright holder/author saying he's going to
change this wording in the next LZO release and that the code *is* GPLv2
licensed as per the headers on the files.

Regards,

Richard




^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-12 15:17   ` Richard Purdie
@ 2007-05-12 16:47     ` Andrew Morton
  2007-05-12 20:56       ` Richard Purdie
  0 siblings, 1 reply; 19+ messages in thread
From: Andrew Morton @ 2007-05-12 16:47 UTC (permalink / raw)
  To: Richard Purdie; +Cc: Adrian Bunk, LKML, torvalds, David Woodhouse

On Sat, 12 May 2007 16:17:35 +0100 Richard Purdie <richard@openedhand.com> wrote:

> On Sat, 2007-05-12 at 13:17 +0200, Adrian Bunk wrote:
> > On Wed, May 02, 2007 at 09:56:23AM +0100, Richard Purdie wrote:
> > >...
> > > I've asked the LZO author about the comments on lzo_copyright function
> > > but the code is GPLv2 licensed so is suitable for inclusion in the
> > > kernel.
> > 
> > This sounds as if LZO is GPL incompatible similar to code under
> > the 4 clause BSD licence.
> > 
> > >...
> > > +/* If you use the LZO library in a product, you *must* keep this
> > > + * copyright string in the executable of your product.
> > > + */
> 
> I've had a reply from the copyright holder/author saying he's going to
> change this wording in the next LZO release and that the code *is* GPLv2
> licensed as per the headers on the files.
> 

It would be ideal if the author of that code could send us a
signed-off-by: as per secton 11 of Documentation/SubmittingPatches.  

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-12 16:47     ` Andrew Morton
@ 2007-05-12 20:56       ` Richard Purdie
  2007-05-13 11:59         ` Markus F.X.J. Oberhumer
  0 siblings, 1 reply; 19+ messages in thread
From: Richard Purdie @ 2007-05-12 20:56 UTC (permalink / raw)
  To: Andrew Morton
  Cc: Adrian Bunk, LKML, torvalds, David Woodhouse, Markus F.X.J. Oberhumer

On Sat, 2007-05-12 at 09:47 -0700, Andrew Morton wrote:
> On Sat, 12 May 2007 16:17:35 +0100 Richard Purdie <richard@openedhand.com> wrote:
> 
> > On Sat, 2007-05-12 at 13:17 +0200, Adrian Bunk wrote:
> > > On Wed, May 02, 2007 at 09:56:23AM +0100, Richard Purdie wrote:
> > > >...
> > > > I've asked the LZO author about the comments on lzo_copyright function
> > > > but the code is GPLv2 licensed so is suitable for inclusion in the
> > > > kernel.
> > > 
> > > This sounds as if LZO is GPL incompatible similar to code under
> > > the 4 clause BSD licence.
> > > 
> > > >...
> > > > +/* If you use the LZO library in a product, you *must* keep this
> > > > + * copyright string in the executable of your product.
> > > > + */
> > 
> > I've had a reply from the copyright holder/author saying he's going to
> > change this wording in the next LZO release and that the code *is* GPLv2
> > licensed as per the headers on the files.
> > 
> 
> It would be ideal if the author of that code could send us a
> signed-off-by: as per secton 11 of Documentation/SubmittingPatches.  

Section 11b says I can submit it but I've asked the author about a
signed off by line (he's cc'd) for the alleviation of any doubt.

Cheers,

Richard



^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-12 20:56       ` Richard Purdie
@ 2007-05-13 11:59         ` Markus F.X.J. Oberhumer
  0 siblings, 0 replies; 19+ messages in thread
From: Markus F.X.J. Oberhumer @ 2007-05-13 11:59 UTC (permalink / raw)
  To: Richard Purdie
  Cc: Andrew Morton, Adrian Bunk, LKML, torvalds, David Woodhouse

Richard Purdie wrote:
> On Sat, 2007-05-12 at 09:47 -0700, Andrew Morton wrote:
>> On Sat, 12 May 2007 16:17:35 +0100 Richard Purdie <richard@openedhand.com> wrote:
>>
>>> On Sat, 2007-05-12 at 13:17 +0200, Adrian Bunk wrote:
>>>> On Wed, May 02, 2007 at 09:56:23AM +0100, Richard Purdie wrote:
>>>>> ...
>>>>> I've asked the LZO author about the comments on lzo_copyright function
>>>>> but the code is GPLv2 licensed so is suitable for inclusion in the
>>>>> kernel.
>>>> This sounds as if LZO is GPL incompatible similar to code under
>>>> the 4 clause BSD licence.
>>>>
>>>>> ...
>>>>> +/* If you use the LZO library in a product, you *must* keep this
>>>>> + * copyright string in the executable of your product.
>>>>> + */
>>> I've had a reply from the copyright holder/author saying he's going to
>>> change this wording in the next LZO release and that the code *is* GPLv2
>>> licensed as per the headers on the files.
>>>
>> It would be ideal if the author of that code could send us a
>> signed-off-by: as per secton 11 of Documentation/SubmittingPatches.  
> 
> Section 11b says I can submit it but I've asked the author about a
> signed off by line (he's cc'd) for the alleviation of any doubt.

I agree that the comment does conflict with the GPL. Just to avoid any doubts, 
LZO _is_ GPL v2, and I will fix that comment for the next version. Please 
accept my signed-off-by for Richard's kernel patch in the meantime.

   Signed-off-by: Markus F.X.J. Oberhumer <markus@oberhumer.com>

~Markus


> 
> Cheers,
> 
> Richard
> 
> 

-- 
Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-12 10:41 devzero
  2007-05-12 11:41 ` Jindrich Makovicka
@ 2007-05-15 16:54 ` Pavel Machek
  1 sibling, 0 replies; 19+ messages in thread
From: Pavel Machek @ 2007-05-15 16:54 UTC (permalink / raw)
  To: devzero; +Cc: akpm, linux-kernel

On Sat 2007-05-12 12:41:03, devzero@web.de wrote:
> oh - and think of linux software suspend.
> take a notebook with 2 GB of ram - that takes a while to write that to disk and read that back again.
> using lzo compression for this may probably halve the time for suspend/resume

suspend.sf.net. We don't need lzo in kernel to do compressed
hibernation.

-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-11 20:48 devzero
@ 2007-05-13 13:06 ` Jindrich Makovicka
  0 siblings, 0 replies; 19+ messages in thread
From: Jindrich Makovicka @ 2007-05-13 13:06 UTC (permalink / raw)
  To: linux-kernel

On Fri, 11 May 2007 22:48:15 +0200
devzero@web.de wrote:

> >Why is this needed?  What code plans to use it?
> 
> it`s pretty useful because it`s and a damn fast and damn cpu friendly
> compression alorithm.
> 
> afaik, there is already a least one linux kernel-feature (under
> development) which is using lzo compression: see compressed caching
> project at http://linux-mm.org/CompressedCaching &
> http://linuxcompressed.sourceforge.net/

Reiser4.1 (still in development) uses LZO compression too and it brings
a significant boost on dual core machines.

-- 
Jindrich Makovicka


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-12 11:41 ` Jindrich Makovicka
@ 2007-05-12 19:51   ` Satyam Sharma
  0 siblings, 0 replies; 19+ messages in thread
From: Satyam Sharma @ 2007-05-12 19:51 UTC (permalink / raw)
  To: Jindrich Makovicka; +Cc: linux-kernel

Hi Jindrich,

On 5/12/07, Jindrich Makovicka <makovick@gmail.com> wrote:
> On Sat, 12 May 2007 12:41:03 +0200
> devzero@web.de wrote:
>
> > oh - and think of linux software suspend.
> > take a notebook with 2 GB of ram - that takes a while to write that
> > to disk and read that back again. using lzo compression for this may
> > probably halve the time for suspend/resume
>
> There were already some attempts on merging of the lzf algorithm:
>
> http://lkml.org/lkml/2006/6/26/215

Hmmm ... that thread had some really neat and simple kernel-compliant
code, but it wanted to bring in a different compression algo :-) LZF, LZO,
LZW are all different.

> Also, ffmpeg/libavcodec contains a much cleaner implementation of LZO

Yeah, I hope the discussion here shifts (after the copyright issues
are resolved,
of course) to the submitted code itself. It's a compression library
also linked to
cryptoapi, so would definitely find users for itself -- this was later
submitted as
a patchset containing the JFFS2 glue code too.

But what I'm not sure about is the suitability of _this_ implementation to be
merged AS IS (~2500 lines of non-kernel-style, and even pointless, code is
no small thing) without a proper conversion / port to the kernel.

The upsides of a proper port would be nice: I suspect ~500 LOC in those
two headers would vanish, and perhaps an equal number in lzo.c (it even
re-invents memset, memcpy, etc for itself!).

The downside, as Richard said, would be that the kernel's LZO is no longer
diff-able with minilzo (the userspace library) which means someone who
takes on maintainership of this will have more work to do. (but how much
more would it be anyway?)

> decompressor, with comparable performance (but no compressor yet I am
> afraid).

Satyam

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
  2007-05-12 10:41 devzero
@ 2007-05-12 11:41 ` Jindrich Makovicka
  2007-05-12 19:51   ` Satyam Sharma
  2007-05-15 16:54 ` Pavel Machek
  1 sibling, 1 reply; 19+ messages in thread
From: Jindrich Makovicka @ 2007-05-12 11:41 UTC (permalink / raw)
  To: linux-kernel

On Sat, 12 May 2007 12:41:03 +0200
devzero@web.de wrote:

> oh - and think of linux software suspend.
> take a notebook with 2 GB of ram - that takes a while to write that
> to disk and read that back again. using lzo compression for this may
> probably halve the time for suspend/resume

There were already some attempts on merging of the lzf algorithm:

http://lkml.org/lkml/2006/6/26/215

Also, ffmpeg/libavcodec contains a much cleaner implementation of LZO
decompressor, with comparable performance (but no compressor yet I am
afraid).

-- 
Jindrich Makovicka


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
@ 2007-05-12 10:41 devzero
  2007-05-12 11:41 ` Jindrich Makovicka
  2007-05-15 16:54 ` Pavel Machek
  0 siblings, 2 replies; 19+ messages in thread
From: devzero @ 2007-05-12 10:41 UTC (permalink / raw)
  To: akpm; +Cc: linux-kernel

oh - and think of linux software suspend.
take a notebook with 2 GB of ram - that takes a while to write that to disk and read that back again.
using lzo compression for this may probably halve the time for suspend/resume

using a fast compression scheme 
> -----Ursprüngliche Nachricht-----
> Von: devzero@web.de
> Gesendet: 11.05.07 22:48:15
> An: akpm@linux-foundation.org
> CC: nitingupta.mail@gmail.com,linux-kernel@vger.kernel.org
> Betreff: Re: [PATCH] Add LZO1X compression support to the kernel


> 
> >Why is this needed?  What code plans to use it?
> 
> it`s pretty useful because it`s and a damn fast and damn cpu friendly compression alorithm.
> 
> afaik, there is already a least one linux kernel-feature (under development) which is using lzo compression: 
> see compressed caching project at http://linux-mm.org/CompressedCaching & http://linuxcompressed.sourceforge.net/
> 
> seems, they have also done porting it to the kernel, so there is probably choice between two implemetations to merge.
> 
> >How many buffer overruns are there in it?
> 
> i don`t know :) 
> but, from a user-perspective,  lzo is really portable and seems to be a rock solid compression scheme.
> i`m sucessfully using it for years (lzop utility) and i know projects which compress gigabytes of data every day with lzop.
> furthermore, i know of at least 40 software projects using lzo compression, so this should have some level of maturity.
> 
> maybe i can add another software integrating lzo compression to the enumeration at http://www.lzop.de ? ;)
> 
> regards
> roland
> 
> 
> List:       linux-kernel
> Subject:    Re: [PATCH] Add LZO1X compression support to the kernel
> From:       Andrew Morton <akpm () linux-foundation ! org>
> Date:       2007-05-10 6:21:29
> Message-ID: 20070509232129.371f49d5.akpm () linux-foundation ! org
> [Download message RAW]
> 
> On Wed, 02 May 2007 09:56:23 +0100 Richard Purdie <richard@openedhand.com> wrote:
> 
> > Current thinking is that lzo should get merged directly followed by the
> > subsystem parts through their specific trees. It appears this should
> > make it onto LKML despite the size so here goes.
> > 
> > Please keep in mind I haven't reformatted the LZO code itself as if I do
> > so, it will make maintenance of it against any changes in LZO itself
> > near impossible. In its current form, it should be possible to diff
> > against upstream. All the bad formatting is confined to a handful of
> > files in lib/lzo/ and the kernel interface should be clean.
> > 
> > I realise a maze of ifdefs still remain. I've already spent a lot of
> > time removing a ton of them and going much further might start to affect
> > diffability of the code - I hoping whats there is a good compromise.
> > 
> > I've asked the LZO author about the comments on lzo_copyright function
> > but the code is GPLv2 licensed so is suitable for inclusion in the
> > kernel.
> > 
> > 
> > 
> > Add LZO1X compression/decompression support to the kernel.
> > 
> > This is based on the standard userspace lzo library, particularly
> > minilzo with the headers much trimmed down and simplified for kernel
> > use. Its structured so that it should still diff with the userspace
> > version for ease of future updating.
> 
> Well that's attractive-looking code.
> 
> Why is this needed?  What code plans to use it?
> 
> How many buffer overruns are there in it?


_____________________________________________________________________
Der WEB.DE SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen!
http://smartsurfer.web.de/?mc=100071&distributionid=000000000066


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
@ 2007-05-11 20:48 devzero
  2007-05-13 13:06 ` Jindrich Makovicka
  0 siblings, 1 reply; 19+ messages in thread
From: devzero @ 2007-05-11 20:48 UTC (permalink / raw)
  To: akpm; +Cc: linux-kernel, nitingupta.mail

>Why is this needed?  What code plans to use it?

it`s pretty useful because it`s and a damn fast and damn cpu friendly compression alorithm.

afaik, there is already a least one linux kernel-feature (under development) which is using lzo compression: 
see compressed caching project at http://linux-mm.org/CompressedCaching & http://linuxcompressed.sourceforge.net/

seems, they have also done porting it to the kernel, so there is probably choice between two implemetations to merge.

>How many buffer overruns are there in it?

i don`t know :) 
but, from a user-perspective,  lzo is really portable and seems to be a rock solid compression scheme.
i`m sucessfully using it for years (lzop utility) and i know projects which compress gigabytes of data every day with lzop.
furthermore, i know of at least 40 software projects using lzo compression, so this should have some level of maturity.

maybe i can add another software integrating lzo compression to the enumeration at http://www.lzop.de ? ;)

regards
roland


List:       linux-kernel
Subject:    Re: [PATCH] Add LZO1X compression support to the kernel
From:       Andrew Morton <akpm () linux-foundation ! org>
Date:       2007-05-10 6:21:29
Message-ID: 20070509232129.371f49d5.akpm () linux-foundation ! org
[Download message RAW]

On Wed, 02 May 2007 09:56:23 +0100 Richard Purdie <richard@openedhand.com> wrote:

> Current thinking is that lzo should get merged directly followed by the
> subsystem parts through their specific trees. It appears this should
> make it onto LKML despite the size so here goes.
> 
> Please keep in mind I haven't reformatted the LZO code itself as if I do
> so, it will make maintenance of it against any changes in LZO itself
> near impossible. In its current form, it should be possible to diff
> against upstream. All the bad formatting is confined to a handful of
> files in lib/lzo/ and the kernel interface should be clean.
> 
> I realise a maze of ifdefs still remain. I've already spent a lot of
> time removing a ton of them and going much further might start to affect
> diffability of the code - I hoping whats there is a good compromise.
> 
> I've asked the LZO author about the comments on lzo_copyright function
> but the code is GPLv2 licensed so is suitable for inclusion in the
> kernel.
> 
> 
> 
> Add LZO1X compression/decompression support to the kernel.
> 
> This is based on the standard userspace lzo library, particularly
> minilzo with the headers much trimmed down and simplified for kernel
> use. Its structured so that it should still diff with the userspace
> version for ease of future updating.

Well that's attractive-looking code.

Why is this needed?  What code plans to use it?

How many buffer overruns are there in it?
_____________________________________________________________________
Der WEB.DE SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen!
http://smartsurfer.web.de/?mc=100071&distributionid=000000000066


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [PATCH] Add LZO1X compression support to the kernel
@ 2007-05-10  8:49 Tomasz Chmielewski
  0 siblings, 0 replies; 19+ messages in thread
From: Tomasz Chmielewski @ 2007-05-10  8:49 UTC (permalink / raw)
  To: linux-kernel

David Woodhouse wrote:

> On Wed, 2007-05-09 at 23:21 -0700, Andrew Morton wrote:
>> Well that's attractive-looking code.
> 
> It's compression code. I've never seen compression code look nice :)
> 
>> Why is this needed?  What code plans to use it?
> 
> I'm itching to use it in JFFS2. Richard claims a 10% boot time speedup
> and 40% improvement on file read speed, with only a slight drop in the
> file compression ratio (when compared to zlib).

Would be interesting to have it as a shared base for 
planned-for-May-2020 "compressed tmpfs" (and, perhaps a filesystem with 
compression, which seems even harder to engineer properly).


-- 
Tomasz Chmielewski


^ permalink raw reply	[flat|nested] 19+ messages in thread

end of thread, other threads:[~2007-05-16 13:36 UTC | newest]

Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-05-02  8:56 [PATCH] Add LZO1X compression support to the kernel Richard Purdie
2007-05-02  9:35 ` Pekka Enberg
2007-05-04 18:28   ` Satyam Sharma
2007-05-10  6:21 ` Andrew Morton
2007-05-10  8:26   ` David Woodhouse
2007-05-10  8:53     ` Richard Purdie
2007-05-10 14:30   ` Jan Engelhardt
2007-05-12 11:17 ` Adrian Bunk
2007-05-12 15:17   ` Richard Purdie
2007-05-12 16:47     ` Andrew Morton
2007-05-12 20:56       ` Richard Purdie
2007-05-13 11:59         ` Markus F.X.J. Oberhumer
2007-05-10  8:49 Tomasz Chmielewski
2007-05-11 20:48 devzero
2007-05-13 13:06 ` Jindrich Makovicka
2007-05-12 10:41 devzero
2007-05-12 11:41 ` Jindrich Makovicka
2007-05-12 19:51   ` Satyam Sharma
2007-05-15 16:54 ` Pavel Machek

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).