Reiser4 developers, Andrew,
The patch below is so-called reiser4 LZO compression plugin as extracted
from 2.6.18-rc4-mm3.
I think it is an unauditable piece of shit and thus should not enter
mainline.
--- /dev/null 2006-06-20 03:34:40.298038750 -0700
+++ devel/fs/reiser4/plugin/compress/lzoconf.h 2006-08-26 15:39:12.000000000 -0700
@@ -0,0 +1,420 @@
+/* lzoconf.h -- configuration for the LZO real-time data compression library
+ adopted for reiser4 compression transform plugin.
+
+ This file is part of the LZO real-time data compression library
+ and not included in any proprietary licenses of reiser4.
+
+ Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 1996 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 as
+ published by the Free Software Foundation; either version 2 of
+ the License, or (at your option) any later version.
+
+ 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.,
+ 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+ Markus F.X.J. Oberhumer
+ <[email protected]>
+ http://www.oberhumer.com/opensource/lzo/
+ */
+
+#include <linux/kernel.h> /* for UINT_MAX, ULONG_MAX - edward */
+
+#ifndef __LZOCONF_H
+#define __LZOCONF_H
+
+#define LZO_VERSION 0x1080
+#define LZO_VERSION_STRING "1.08"
+#define LZO_VERSION_DATE "Jul 12 2002"
+
+/* internal Autoconf configuration file - only used when building LZO */
+#if defined(LZO_HAVE_CONFIG_H)
+# include <config.h>
+#endif
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/***********************************************************************
+// LZO requires a conforming <limits.h>
+************************************************************************/
+
+#define CHAR_BIT 8
+#define USHRT_MAX 0xffff
+
+/* workaround a cpp bug under hpux 10.20 */
+#define LZO_0xffffffffL 4294967295ul
+
+/***********************************************************************
+// architecture defines
+************************************************************************/
+
+#if !defined(__LZO_WIN) && !defined(__LZO_DOS) && !defined(__LZO_OS2)
+# if defined(__WINDOWS__) || defined(_WINDOWS) || defined(_Windows)
+# define __LZO_WIN
+# elif defined(__WIN32__) || defined(_WIN32) || defined(WIN32)
+# define __LZO_WIN
+# elif defined(__NT__) || defined(__NT_DLL__) || defined(__WINDOWS_386__)
+# define __LZO_WIN
+# elif defined(__DOS__) || defined(__MSDOS__) || defined(MSDOS)
+# define __LZO_DOS
+# elif defined(__OS2__) || defined(__OS2V2__) || defined(OS2)
+# define __LZO_OS2
+# elif defined(__palmos__)
+# define __LZO_PALMOS
+# elif defined(__TOS__) || defined(__atarist__)
+# define __LZO_TOS
+# endif
+#endif
+
+#if (UINT_MAX < LZO_0xffffffffL)
+# if defined(__LZO_WIN)
+# define __LZO_WIN16
+# elif defined(__LZO_DOS)
+# define __LZO_DOS16
+# elif defined(__LZO_PALMOS)
+# define __LZO_PALMOS16
+# elif defined(__LZO_TOS)
+# define __LZO_TOS16
+# elif defined(__C166__)
+# else
+ /* porting hint: for pure 16-bit architectures try compiling
+ * everything with -D__LZO_STRICT_16BIT */
+# error "16-bit target not supported - contact me for porting hints"
+# endif
+#endif
+
+#if !defined(__LZO_i386)
+# if defined(__LZO_DOS) || defined(__LZO_WIN16)
+# define __LZO_i386
+# elif defined(__i386__) || defined(__386__) || defined(_M_IX86)
+# define __LZO_i386
+# endif
+#endif
+
+#if defined(__LZO_STRICT_16BIT)
+# if (UINT_MAX < LZO_0xffffffffL)
+# include <lzo16bit.h>
+# endif
+#endif
+
+/* memory checkers */
+#if !defined(__LZO_CHECKER)
+# if defined(__BOUNDS_CHECKING_ON)
+# define __LZO_CHECKER
+# elif defined(__CHECKER__)
+# define __LZO_CHECKER
+# elif defined(__INSURE__)
+# define __LZO_CHECKER
+# elif defined(__PURIFY__)
+# define __LZO_CHECKER
+# endif
+#endif
+
+/***********************************************************************
+// integral and pointer types
+************************************************************************/
+
+/* 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
+
+/* lzo_uint is used like size_t */
+#if !defined(LZO_UINT_MAX)
+# if (UINT_MAX >= LZO_0xffffffffL)
+ 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
+
+ typedef int lzo_bool;
+
+/***********************************************************************
+// memory models
+************************************************************************/
+
+/* Memory model for the public code segment. */
+#if !defined(__LZO_CMODEL)
+# if defined(__LZO_DOS16) || defined(__LZO_WIN16)
+# define __LZO_CMODEL __far
+# elif defined(__LZO_i386) && defined(__WATCOMC__)
+# define __LZO_CMODEL __near
+# else
+# define __LZO_CMODEL
+# endif
+#endif
+
+/* Memory model for the public data segment. */
+#if !defined(__LZO_DMODEL)
+# if defined(__LZO_DOS16) || defined(__LZO_WIN16)
+# define __LZO_DMODEL __far
+# elif defined(__LZO_i386) && defined(__WATCOMC__)
+# define __LZO_DMODEL __near
+# else
+# define __LZO_DMODEL
+# endif
+#endif
+
+/* Memory model that allows to access memory at offsets of lzo_uint. */
+#if !defined(__LZO_MMODEL)
+# if (LZO_UINT_MAX <= UINT_MAX)
+# define __LZO_MMODEL
+# elif defined(__LZO_DOS16) || defined(__LZO_WIN16)
+# define __LZO_MMODEL __huge
+# define LZO_999_UNSUPPORTED
+# elif defined(__LZO_PALMOS16) || defined(__LZO_TOS16)
+# define __LZO_MMODEL
+# else
+# error "__LZO_MMODEL"
+# endif
+#endif
+
+/* no typedef here because of const-pointer issues */
+#define lzo_byte unsigned char __LZO_MMODEL
+#define lzo_bytep unsigned char __LZO_MMODEL *
+#define lzo_charp char __LZO_MMODEL *
+#define lzo_voidp void __LZO_MMODEL *
+#define lzo_shortp short __LZO_MMODEL *
+#define lzo_ushortp unsigned short __LZO_MMODEL *
+#define lzo_uint32p lzo_uint32 __LZO_MMODEL *
+#define lzo_int32p lzo_int32 __LZO_MMODEL *
+#define lzo_uintp lzo_uint __LZO_MMODEL *
+#define lzo_intp lzo_int __LZO_MMODEL *
+#define lzo_voidpp lzo_voidp __LZO_MMODEL *
+#define lzo_bytepp lzo_bytep __LZO_MMODEL *
+
+#ifndef lzo_sizeof_dict_t
+# define lzo_sizeof_dict_t sizeof(lzo_bytep)
+#endif
+
+/***********************************************************************
+// calling conventions and function types
+************************************************************************/
+
+/* linkage */
+#if !defined(__LZO_EXTERN_C)
+# ifdef __cplusplus
+# define __LZO_EXTERN_C extern "C"
+# else
+# define __LZO_EXTERN_C extern
+# endif
+#endif
+
+/* calling convention */
+#if !defined(__LZO_CDECL)
+# if defined(__LZO_DOS16) || defined(__LZO_WIN16)
+# define __LZO_CDECL __LZO_CMODEL __cdecl
+# elif defined(__LZO_i386) && defined(_MSC_VER)
+# define __LZO_CDECL __LZO_CMODEL __cdecl
+# elif defined(__LZO_i386) && defined(__WATCOMC__)
+# define __LZO_CDECL __LZO_CMODEL __cdecl
+# else
+# define __LZO_CDECL __LZO_CMODEL
+# endif
+#endif
+#if !defined(__LZO_ENTRY)
+# define __LZO_ENTRY __LZO_CDECL
+#endif
+
+/* C++ exception specification for extern "C" function types */
+#if !defined(__cplusplus)
+# undef LZO_NOTHROW
+# define LZO_NOTHROW
+#elif !defined(LZO_NOTHROW)
+# define LZO_NOTHROW
+#endif
+
+ typedef int
+ (__LZO_ENTRY * lzo_compress_t) (const lzo_byte * src, lzo_uint src_len,
+ lzo_byte * dst, lzo_uintp dst_len,
+ lzo_voidp wrkmem);
+
+ typedef int
+ (__LZO_ENTRY * lzo_decompress_t) (const lzo_byte * src,
+ lzo_uint src_len, lzo_byte * dst,
+ lzo_uintp dst_len, lzo_voidp wrkmem);
+
+ typedef int
+ (__LZO_ENTRY * lzo_optimize_t) (lzo_byte * src, lzo_uint src_len,
+ lzo_byte * dst, lzo_uintp dst_len,
+ lzo_voidp wrkmem);
+
+ typedef int
+ (__LZO_ENTRY * lzo_compress_dict_t) (const lzo_byte * src,
+ lzo_uint src_len, lzo_byte * dst,
+ lzo_uintp dst_len,
+ lzo_voidp wrkmem,
+ const lzo_byte * dict,
+ lzo_uint dict_len);
+
+ typedef int
+ (__LZO_ENTRY * lzo_decompress_dict_t) (const lzo_byte * src,
+ lzo_uint src_len,
+ lzo_byte * dst,
+ lzo_uintp dst_len,
+ lzo_voidp wrkmem,
+ const lzo_byte * dict,
+ lzo_uint dict_len);
+
+/* assembler versions always use __cdecl */
+ typedef int
+ (__LZO_CDECL * lzo_compress_asm_t) (const lzo_byte * src,
+ lzo_uint src_len, lzo_byte * dst,
+ lzo_uintp dst_len,
+ lzo_voidp wrkmem);
+
+ typedef int
+ (__LZO_CDECL * lzo_decompress_asm_t) (const lzo_byte * src,
+ lzo_uint src_len, lzo_byte * dst,
+ lzo_uintp dst_len,
+ lzo_voidp wrkmem);
+
+/* a progress indicator callback function */
+ typedef void (__LZO_ENTRY * lzo_progress_callback_t) (lzo_uint,
+ lzo_uint);
+
+/***********************************************************************
+// export information
+************************************************************************/
+
+/* DLL export information */
+#if !defined(__LZO_EXPORT1)
+# define __LZO_EXPORT1
+#endif
+#if !defined(__LZO_EXPORT2)
+# define __LZO_EXPORT2
+#endif
+
+/* exported calling convention for C functions */
+#if !defined(LZO_PUBLIC)
+# define LZO_PUBLIC(_rettype) \
+ __LZO_EXPORT1 _rettype __LZO_EXPORT2 __LZO_ENTRY
+#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 __LZO_ENTRY
+#endif
+
+/* exported __cdecl calling convention for assembler functions */
+#if !defined(LZO_PUBLIC_CDECL)
+# define LZO_PUBLIC_CDECL(_rettype) \
+ __LZO_EXPORT1 _rettype __LZO_EXPORT2 __LZO_CDECL
+#endif
+#if !defined(LZO_EXTERN_CDECL)
+# define LZO_EXTERN_CDECL(_rettype) __LZO_EXTERN_C LZO_PUBLIC_CDECL(_rettype)
+#endif
+
+/* exported global variables (LZO currently uses no static variables and
+ * is fully thread safe) */
+#if !defined(LZO_PUBLIC_VAR)
+# define LZO_PUBLIC_VAR(_type) \
+ __LZO_EXPORT1 _type __LZO_EXPORT2 __LZO_DMODEL
+#endif
+#if !defined(LZO_EXTERN_VAR)
+# define LZO_EXTERN_VAR(_type) extern LZO_PUBLIC_VAR(_type)
+#endif
+
+/***********************************************************************
+// error codes and prototypes
+************************************************************************/
+
+/* Error codes for the compression/decompression functions. Negative
+ * values are errors, positive values will be used for special but
+ * normal events.
+ */
+#define LZO_E_OK 0
+#define LZO_E_ERROR (-1)
+#define LZO_E_OUT_OF_MEMORY (-2) /* not used right now */
+#define LZO_E_NOT_COMPRESSIBLE (-3) /* not used right now */
+#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)
+
+/* lzo_init() should be the first function you call.
+ * Check the return code !
+ *
+ * lzo_init() is a macro to allow checking that the library and the
+ * compiler's view of various types are consistent.
+ */
+#define lzo_init() __lzo_init2(LZO_VERSION,(int)sizeof(short),(int)sizeof(int),\
+ (int)sizeof(long),(int)sizeof(lzo_uint32),(int)sizeof(lzo_uint),\
+ (int)lzo_sizeof_dict_t,(int)sizeof(char *),(int)sizeof(lzo_voidp),\
+ (int)sizeof(lzo_compress_t))
+ LZO_EXTERN(int) __lzo_init2(unsigned, int, int, int, int, int, int,
+ int, int, int);
+
+/* checksum functions */
+ LZO_EXTERN(lzo_uint32)
+ lzo_crc32(lzo_uint32 _c, const lzo_byte * _buf, lzo_uint _len);
+
+/* misc. */
+ typedef union {
+ lzo_bytep p;
+ lzo_uint u;
+ } __lzo_pu_u;
+ typedef union {
+ lzo_bytep p;
+ lzo_uint32 u32;
+ } __lzo_pu32_u;
+ typedef union {
+ void *vp;
+ lzo_bytep bp;
+ lzo_uint32 u32;
+ long l;
+ } lzo_align_t;
+
+#define LZO_PTR_ALIGN_UP(_ptr,_size) \
+ ((_ptr) + (lzo_uint) __lzo_align_gap((const lzo_voidp)(_ptr),(lzo_uint)(_size)))
+
+/* deprecated - only for backward compatibility */
+#define LZO_ALIGN(_ptr,_size) LZO_PTR_ALIGN_UP(_ptr,_size)
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+#endif /* already included */
--- /dev/null 2006-06-20 03:34:40.298038750 -0700
+++ devel/fs/reiser4/plugin/compress/minilzo.c 2006-08-26 15:39:12.000000000 -0700
@@ -0,0 +1,2155 @@
+/* minilzo.c -- mini subset of the LZO real-time data compression library
+ adopted for reiser4 compression transform plugin.
+
+ This file is part of the LZO real-time data compression library
+ and not included in any proprietary licenses of reiser4.
+
+ Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
+ Copyright (C) 1996 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 as
+ published by the Free Software Foundation; either version 2 of
+ the License, or (at your option) any later version.
+
+ 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.,
+ 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+ Markus F.X.J. Oberhumer
+ <[email protected]>
+ http://www.oberhumer.com/opensource/lzo/
+ */
+
+/*
+ * NOTE:
+ * the full LZO package can be found at
+ * http://www.oberhumer.com/opensource/lzo/
+ */
+
+#include "../../debug.h" /* for reiser4 assert macro -edward */
+
+#define __LZO_IN_MINILZO
+#define LZO_BUILD
+
+#ifdef MINILZO_HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#undef LZO_HAVE_CONFIG_H
+#include "minilzo.h"
+
+#if !defined(MINILZO_VERSION) || (MINILZO_VERSION != 0x1080)
+# error "version mismatch in miniLZO source files"
+#endif
+
+#ifdef MINILZO_HAVE_CONFIG_H
+# define LZO_HAVE_CONFIG_H
+#endif
+
+
+#ifndef __LZO_CONF_H
+#define __LZO_CONF_H
+
+#if !defined(__LZO_IN_MINILZO)
+# ifndef __LZOCONF_H
+# include <lzoconf.h>
+# endif
+#endif
+
+#if defined(__BOUNDS_CHECKING_ON)
+# include <unchecked.h>
+#else
+# define BOUNDS_CHECKING_OFF_DURING(stmt) stmt
+# define BOUNDS_CHECKING_OFF_IN_EXPR(expr) (expr)
+#endif
+
+# define HAVE_MEMCMP
+# define HAVE_MEMCPY
+# define HAVE_MEMMOVE
+# define HAVE_MEMSET
+
+#if defined(__LZO_DOS16) || defined(__LZO_WIN16)
+# define HAVE_MALLOC_H
+# define HAVE_HALLOC
+#endif
+
+#undef NDEBUG
+#if !defined(LZO_DEBUG)
+# define NDEBUG
+#endif
+#if defined(LZO_DEBUG) || !defined(NDEBUG)
+# if !defined(NO_STDIO_H)
+# include <stdio.h>
+# endif
+#endif
+# if 0 /* edward */
+#include <assert.h>
+#endif /* edward */
+
+#if !defined(LZO_COMPILE_TIME_ASSERT)
+# define LZO_COMPILE_TIME_ASSERT(expr) \
+ { typedef int __lzo_compile_time_assert_fail[1 - 2 * !(expr)]; }
+#endif
+
+#if !defined(LZO_UNUSED)
+# if 1
+# define LZO_UNUSED(var) ((void)&var)
+# elif 0
+# define LZO_UNUSED(var) { typedef int __lzo_unused[sizeof(var) ? 2 : 1]; }
+# else
+# define LZO_UNUSED(parm) (parm = parm)
+# endif
+#endif
+
+#if !defined(__inline__) && !defined(__GNUC__)
+# if defined(__cplusplus)
+# define __inline__ inline
+# else
+# define __inline__
+# endif
+#endif
+
+#if defined(NO_MEMCMP)
+# undef HAVE_MEMCMP
+#endif
+
+#if !defined(HAVE_MEMSET)
+# undef memset
+# define memset lzo_memset
+#endif
+
+# define LZO_BYTE(x) ((unsigned char) ((x) & 0xff))
+
+#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)
+
+#define LZO_STYPE_MAX(b) (((1l << (8*(b)-2)) - 1l) + (1l << (8*(b)-2)))
+#define LZO_UTYPE_MAX(b) (((1ul << (8*(b)-1)) - 1ul) + (1ul << (8*(b)-1)))
+
+#if !defined(SIZEOF_UNSIGNED)
+# if (UINT_MAX == 0xffff)
+# define SIZEOF_UNSIGNED 2
+# elif (UINT_MAX == LZO_0xffffffffL)
+# define SIZEOF_UNSIGNED 4
+# elif (UINT_MAX >= LZO_0xffffffffL)
+# define SIZEOF_UNSIGNED 8
+# else
+# error "SIZEOF_UNSIGNED"
+# endif
+#endif
+
+#if !defined(SIZEOF_UNSIGNED_LONG)
+# if (ULONG_MAX == LZO_0xffffffffL)
+# define SIZEOF_UNSIGNED_LONG 4
+# elif (ULONG_MAX >= LZO_0xffffffffL)
+# define SIZEOF_UNSIGNED_LONG 8
+# else
+# error "SIZEOF_UNSIGNED_LONG"
+# endif
+#endif
+
+#if !defined(SIZEOF_SIZE_T)
+# define SIZEOF_SIZE_T SIZEOF_UNSIGNED
+#endif
+#if !defined(SIZE_T_MAX)
+# define SIZE_T_MAX LZO_UTYPE_MAX(SIZEOF_SIZE_T)
+#endif
+
+#if 1 && defined(__LZO_i386) && (UINT_MAX == LZO_0xffffffffL)
+# if !defined(LZO_UNALIGNED_OK_2) && (USHRT_MAX == 0xffff)
+# define LZO_UNALIGNED_OK_2
+# endif
+# if !defined(LZO_UNALIGNED_OK_4) && (LZO_UINT32_MAX == LZO_0xffffffffL)
+# define LZO_UNALIGNED_OK_4
+# endif
+#endif
+
+#if defined(LZO_UNALIGNED_OK_2) || defined(LZO_UNALIGNED_OK_4)
+# if !defined(LZO_UNALIGNED_OK)
+# define LZO_UNALIGNED_OK
+# endif
+#endif
+
+#if defined(__LZO_NO_UNALIGNED)
+# undef LZO_UNALIGNED_OK
+# undef LZO_UNALIGNED_OK_2
+# undef LZO_UNALIGNED_OK_4
+#endif
+
+#if defined(LZO_UNALIGNED_OK_2) && (USHRT_MAX != 0xffff)
+# error "LZO_UNALIGNED_OK_2 must not be defined on this system"
+#endif
+#if defined(LZO_UNALIGNED_OK_4) && (LZO_UINT32_MAX != LZO_0xffffffffL)
+# error "LZO_UNALIGNED_OK_4 must not be defined on this system"
+#endif
+
+#if defined(__LZO_NO_ALIGNED)
+# undef LZO_ALIGNED_OK_4
+#endif
+
+#if defined(LZO_ALIGNED_OK_4) && (LZO_UINT32_MAX != LZO_0xffffffffL)
+# error "LZO_ALIGNED_OK_4 must not be defined on this system"
+#endif
+
+#define LZO_LITTLE_ENDIAN 1234
+#define LZO_BIG_ENDIAN 4321
+#define LZO_PDP_ENDIAN 3412
+
+#if !defined(LZO_BYTE_ORDER)
+# if defined(MFX_BYTE_ORDER)
+# define LZO_BYTE_ORDER MFX_BYTE_ORDER
+# elif defined(__LZO_i386)
+# define LZO_BYTE_ORDER LZO_LITTLE_ENDIAN
+# elif defined(BYTE_ORDER)
+# define LZO_BYTE_ORDER BYTE_ORDER
+# elif defined(__BYTE_ORDER)
+# define LZO_BYTE_ORDER __BYTE_ORDER
+# endif
+#endif
+
+#if defined(LZO_BYTE_ORDER)
+# if (LZO_BYTE_ORDER != LZO_LITTLE_ENDIAN) && \
+ (LZO_BYTE_ORDER != LZO_BIG_ENDIAN)
+# error "invalid LZO_BYTE_ORDER"
+# endif
+#endif
+
+#if defined(LZO_UNALIGNED_OK) && !defined(LZO_BYTE_ORDER)
+# error "LZO_BYTE_ORDER is not defined"
+#endif
+
+#define LZO_OPTIMIZE_GNUC_i386_IS_BUGGY
+
+#if defined(NDEBUG) && !defined(LZO_DEBUG) && !defined(__LZO_CHECKER)
+# if defined(__GNUC__) && defined(__i386__)
+# if !defined(LZO_OPTIMIZE_GNUC_i386_IS_BUGGY)
+# define LZO_OPTIMIZE_GNUC_i386
+# endif
+# endif
+#endif
+
+__LZO_EXTERN_C const lzo_uint32 _lzo_crc32_table[256];
+
+#define _LZO_STRINGIZE(x) #x
+#define _LZO_MEXPAND(x) _LZO_STRINGIZE(x)
+
+#define _LZO_CONCAT2(a,b) a ## b
+#define _LZO_CONCAT3(a,b,c) a ## b ## c
+#define _LZO_CONCAT4(a,b,c,d) a ## b ## c ## d
+#define _LZO_CONCAT5(a,b,c,d,e) a ## b ## c ## d ## e
+
+#define _LZO_ECONCAT2(a,b) _LZO_CONCAT2(a,b)
+#define _LZO_ECONCAT3(a,b,c) _LZO_CONCAT3(a,b,c)
+#define _LZO_ECONCAT4(a,b,c,d) _LZO_CONCAT4(a,b,c,d)
+#define _LZO_ECONCAT5(a,b,c,d,e) _LZO_CONCAT5(a,b,c,d,e)
+
+#ifndef __LZO_PTR_H
+#define __LZO_PTR_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#if defined(__LZO_DOS16) || defined(__LZO_WIN16)
+# include <dos.h>
+# if 1 && defined(__WATCOMC__)
+# include <i86.h>
+ __LZO_EXTERN_C unsigned char _HShift;
+# define __LZO_HShift _HShift
+# elif 1 && defined(_MSC_VER)
+ __LZO_EXTERN_C unsigned short __near _AHSHIFT;
+# define __LZO_HShift ((unsigned) &_AHSHIFT)
+# elif defined(__LZO_WIN16)
+# define __LZO_HShift 3
+# else
+# define __LZO_HShift 12
+# endif
+# if !defined(_FP_SEG) && defined(FP_SEG)
+# define _FP_SEG FP_SEG
+# endif
+# if !defined(_FP_OFF) && defined(FP_OFF)
+# define _FP_OFF FP_OFF
+# endif
+#endif
+
+#if !defined(lzo_ptrdiff_t)
+# if (UINT_MAX >= LZO_0xffffffffL)
+ typedef ptrdiff_t lzo_ptrdiff_t;
+# else
+ typedef long lzo_ptrdiff_t;
+# endif
+#endif
+
+#if !defined(__LZO_HAVE_PTR_T)
+# if defined(lzo_ptr_t)
+# define __LZO_HAVE_PTR_T
+# endif
+#endif
+#if !defined(__LZO_HAVE_PTR_T)
+# if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED_LONG)
+# if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_LONG)
+ typedef unsigned long lzo_ptr_t;
+ typedef long lzo_sptr_t;
+# define __LZO_HAVE_PTR_T
+# endif
+# endif
+#endif
+#if !defined(__LZO_HAVE_PTR_T)
+# if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED)
+# if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED)
+ typedef unsigned int lzo_ptr_t;
+ typedef int lzo_sptr_t;
+# define __LZO_HAVE_PTR_T
+# endif
+# endif
+#endif
+#if !defined(__LZO_HAVE_PTR_T)
+# if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED_SHORT)
+# if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_SHORT)
+ typedef unsigned short lzo_ptr_t;
+ typedef short lzo_sptr_t;
+# define __LZO_HAVE_PTR_T
+# endif
+# endif
+#endif
+#if !defined(__LZO_HAVE_PTR_T)
+# if defined(LZO_HAVE_CONFIG_H) || defined(SIZEOF_CHAR_P)
+# error "no suitable type for lzo_ptr_t"
+# else
+ typedef unsigned long lzo_ptr_t;
+ typedef long lzo_sptr_t;
+# define __LZO_HAVE_PTR_T
+# endif
+#endif
+
+#if defined(__LZO_DOS16) || defined(__LZO_WIN16)
+#define PTR(a) ((lzo_bytep) (a))
+#define PTR_ALIGNED_4(a) ((_FP_OFF(a) & 3) == 0)
+#define PTR_ALIGNED2_4(a,b) (((_FP_OFF(a) | _FP_OFF(b)) & 3) == 0)
+#else
+#define PTR(a) ((lzo_ptr_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) ((lzo_ptrdiff_t) (PTR(a) - PTR(b)))
+#define pd(a,b) ((lzo_uint) ((a)-(b)))
+
+ typedef union {
+ char a_char;
+ unsigned char a_uchar;
+ short a_short;
+ unsigned short a_ushort;
+ int a_int;
+ unsigned int a_uint;
+ long a_long;
+ unsigned long a_ulong;
+ lzo_int a_lzo_int;
+ lzo_uint a_lzo_uint;
+ lzo_int32 a_lzo_int32;
+ lzo_uint32 a_lzo_uint32;
+ ptrdiff_t a_ptrdiff_t;
+ lzo_ptrdiff_t a_lzo_ptrdiff_t;
+ lzo_ptr_t a_lzo_ptr_t;
+ lzo_voidp a_lzo_voidp;
+ void *a_void_p;
+ lzo_bytep a_lzo_bytep;
+ lzo_bytepp a_lzo_bytepp;
+ lzo_uintp a_lzo_uintp;
+ lzo_uint *a_lzo_uint_p;
+ lzo_uint32p a_lzo_uint32p;
+ lzo_uint32 *a_lzo_uint32_p;
+ unsigned char *a_uchar_p;
+ char *a_char_p;
+ } lzo_full_align_t;
+
+#ifdef __cplusplus
+}
+#endif
+#endif
+#define LZO_DETERMINISTIC
+#define LZO_DICT_USE_PTR
+#if defined(__LZO_DOS16) || defined(__LZO_WIN16) || defined(__LZO_STRICT_16BIT)
+# undef LZO_DICT_USE_PTR
+#endif
+#if defined(LZO_DICT_USE_PTR)
+# define lzo_dict_t const lzo_bytep
+# define lzo_dict_p lzo_dict_t __LZO_MMODEL *
+#else
+# define lzo_dict_t lzo_uint
+# define lzo_dict_p lzo_dict_t __LZO_MMODEL *
+#endif
+#if !defined(lzo_moff_t)
+#define lzo_moff_t lzo_uint
+#endif
+#endif
+static lzo_ptr_t __lzo_ptr_linear(const lzo_voidp ptr)
+{
+ lzo_ptr_t p;
+
+#if defined(__LZO_DOS16) || defined(__LZO_WIN16)
+ p = (((lzo_ptr_t) (_FP_SEG(ptr))) << (16 - __LZO_HShift)) +
+ (_FP_OFF(ptr));
+#else
+ p = PTR_LINEAR(ptr);
+#endif
+
+ return p;
+}
+
+static unsigned __lzo_align_gap(const lzo_voidp ptr, lzo_uint size)
+{
+ lzo_ptr_t p, s, n;
+
+ assert("lzo-01", size > 0);
+
+ p = __lzo_ptr_linear(ptr);
+ s = (lzo_ptr_t) (size - 1);
+ n = (((p + s) / size) * size) - p;
+
+ assert("lzo-02", (long)n >= 0);
+ assert("lzo-03", n <= s);
+
+ return (unsigned)n;
+}
+
+#ifndef __LZO_UTIL_H
+#define __LZO_UTIL_H
+
+#ifndef __LZO_CONF_H
+#endif
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#if 1 && defined(HAVE_MEMCPY)
+#if !defined(__LZO_DOS16) && !defined(__LZO_WIN16)
+
+#define MEMCPY8_DS(dest,src,len) \
+ memcpy(dest,src,len); \
+ dest += len; \
+ src += len
+
+#endif
+#endif
+
+#if !defined(MEMCPY8_DS)
+
+#define MEMCPY8_DS(dest,src,len) \
+ { register lzo_uint __l = (len) / 8; \
+ do { \
+ *dest++ = *src++; \
+ *dest++ = *src++; \
+ *dest++ = *src++; \
+ *dest++ = *src++; \
+ *dest++ = *src++; \
+ *dest++ = *src++; \
+ *dest++ = *src++; \
+ *dest++ = *src++; \
+ } while (--__l > 0); }
+
+#endif
+
+#define MEMCPY_DS(dest,src,len) \
+ do *dest++ = *src++; \
+ while (--len > 0)
+
+#define MEMMOVE_DS(dest,src,len) \
+ do *dest++ = *src++; \
+ while (--len > 0)
+
+
+#if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMSET)
+
+#define BZERO8_PTR(s,l,n) memset((s),0,(lzo_uint)(l)*(n))
+
+#else
+
+#define BZERO8_PTR(s,l,n) \
+ lzo_memset((lzo_voidp)(s),0,(lzo_uint)(l)*(n))
+
+#endif
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
+/* If you use the LZO library in a product, you *must* keep this
+ * copyright string in the executable of your product.
+ */
+
+static const lzo_byte __lzo_copyright[] =
+#if !defined(__LZO_IN_MINLZO)
+ LZO_VERSION_STRING;
+#else
+ "\n\n\n"
+ "LZO real-time data compression library.\n"
+ "Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002 Markus Franz Xaver Johannes Oberhumer\n"
+ "<[email protected]>\n"
+ "http://www.oberhumer.com/opensource/lzo/\n"
+ "\n"
+ "LZO version: v" LZO_VERSION_STRING ", " LZO_VERSION_DATE "\n"
+ "LZO build date: " __DATE__ " " __TIME__ "\n\n"
+ "LZO special compilation options:\n"
+#ifdef __cplusplus
+ " __cplusplus\n"
+#endif
+#if defined(__PIC__)
+ " __PIC__\n"
+#elif defined(__pic__)
+ " __pic__\n"
+#endif
+#if (UINT_MAX < LZO_0xffffffffL)
+ " 16BIT\n"
+#endif
+#if defined(__LZO_STRICT_16BIT)
+ " __LZO_STRICT_16BIT\n"
+#endif
+#if (UINT_MAX > LZO_0xffffffffL)
+ " UINT_MAX=" _LZO_MEXPAND(UINT_MAX) "\n"
+#endif
+#if (ULONG_MAX > LZO_0xffffffffL)
+ " ULONG_MAX=" _LZO_MEXPAND(ULONG_MAX) "\n"
+#endif
+#if defined(LZO_BYTE_ORDER)
+ " LZO_BYTE_ORDER=" _LZO_MEXPAND(LZO_BYTE_ORDER) "\n"
+#endif
+#if defined(LZO_UNALIGNED_OK_2)
+ " LZO_UNALIGNED_OK_2\n"
+#endif
+#if defined(LZO_UNALIGNED_OK_4)
+ " LZO_UNALIGNED_OK_4\n"
+#endif
+#if defined(LZO_ALIGNED_OK_4)
+ " LZO_ALIGNED_OK_4\n"
+#endif
+#if defined(LZO_DICT_USE_PTR)
+ " LZO_DICT_USE_PTR\n"
+#endif
+#if defined(__LZO_QUERY_COMPRESS)
+ " __LZO_QUERY_COMPRESS\n"
+#endif
+#if defined(__LZO_QUERY_DECOMPRESS)
+ " __LZO_QUERY_DECOMPRESS\n"
+#endif
+#if defined(__LZO_IN_MINILZO)
+ " __LZO_IN_MINILZO\n"
+#endif
+ "\n\n" "$Id: LZO " LZO_VERSION_STRING " built " __DATE__ " " __TIME__
+#if defined(__GNUC__) && defined(__VERSION__)
+ " by gcc " __VERSION__
+#elif defined(__BORLANDC__)
+ " by Borland C " _LZO_MEXPAND(__BORLANDC__)
+#elif defined(_MSC_VER)
+ " by Microsoft C " _LZO_MEXPAND(_MSC_VER)
+#elif defined(__PUREC__)
+ " by Pure C " _LZO_MEXPAND(__PUREC__)
+#elif defined(__SC__)
+ " by Symantec C " _LZO_MEXPAND(__SC__)
+#elif defined(__TURBOC__)
+ " by Turbo C " _LZO_MEXPAND(__TURBOC__)
+#elif defined(__WATCOMC__)
+ " by Watcom C " _LZO_MEXPAND(__WATCOMC__)
+#endif
+ " $\n"
+ "$Copyright: LZO (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002 Markus Franz Xaver Johannes Oberhumer $\n";
+#endif
+
+#define LZO_BASE 65521u
+#define LZO_NMAX 5552
+
+#define LZO_DO1(buf,i) {s1 += buf[i]; s2 += s1;}
+#define LZO_DO2(buf,i) LZO_DO1(buf,i); LZO_DO1(buf,i+1);
+#define LZO_DO4(buf,i) LZO_DO2(buf,i); LZO_DO2(buf,i+2);
+#define LZO_DO8(buf,i) LZO_DO4(buf,i); LZO_DO4(buf,i+4);
+#define LZO_DO16(buf,i) LZO_DO8(buf,i); LZO_DO8(buf,i+8);
+
+# define IS_SIGNED(type) (((type) (-1)) < ((type) 0))
+# define IS_UNSIGNED(type) (((type) (-1)) > ((type) 0))
+
+#define IS_POWER_OF_2(x) (((x) & ((x) - 1)) == 0)
+
+static lzo_bool schedule_insns_bug(void);
+static lzo_bool strength_reduce_bug(int *);
+
+# define __lzo_assert(x) ((x) ? 1 : 0)
+
+#undef COMPILE_TIME_ASSERT
+
+# define COMPILE_TIME_ASSERT(expr) LZO_COMPILE_TIME_ASSERT(expr)
+
+static lzo_bool basic_integral_check(void)
+{
+ lzo_bool r = 1;
+
+ COMPILE_TIME_ASSERT(CHAR_BIT == 8);
+ COMPILE_TIME_ASSERT(sizeof(char) == 1);
+ COMPILE_TIME_ASSERT(sizeof(short) >= 2);
+ COMPILE_TIME_ASSERT(sizeof(long) >= 4);
+ COMPILE_TIME_ASSERT(sizeof(int) >= sizeof(short));
+ COMPILE_TIME_ASSERT(sizeof(long) >= sizeof(int));
+
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint) == sizeof(lzo_int));
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == sizeof(lzo_int32));
+
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint32) >= 4);
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint32) >= sizeof(unsigned));
+#if defined(__LZO_STRICT_16BIT)
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint) == 2);
+#else
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint) >= 4);
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint) >= sizeof(unsigned));
+#endif
+
+#if (USHRT_MAX == 65535u)
+ COMPILE_TIME_ASSERT(sizeof(short) == 2);
+#elif (USHRT_MAX == LZO_0xffffffffL)
+ COMPILE_TIME_ASSERT(sizeof(short) == 4);
+#elif (USHRT_MAX >= LZO_0xffffffffL)
+ COMPILE_TIME_ASSERT(sizeof(short) > 4);
+#endif
+#if 0 /* to make gcc happy -edward */
+#if (UINT_MAX == 65535u)
+ COMPILE_TIME_ASSERT(sizeof(int) == 2);
+#elif (UINT_MAX == LZO_0xffffffffL)
+ COMPILE_TIME_ASSERT(sizeof(int) == 4);
+#elif (UINT_MAX >= LZO_0xffffffffL)
+ COMPILE_TIME_ASSERT(sizeof(int) > 4);
+#endif
+#if (ULONG_MAX == 65535ul)
+ COMPILE_TIME_ASSERT(sizeof(long) == 2);
+#elif (ULONG_MAX == LZO_0xffffffffL)
+ COMPILE_TIME_ASSERT(sizeof(long) == 4);
+#elif (ULONG_MAX >= LZO_0xffffffffL)
+ COMPILE_TIME_ASSERT(sizeof(long) > 4);
+#endif
+#if defined(SIZEOF_UNSIGNED)
+ COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED == sizeof(unsigned));
+#endif
+#if defined(SIZEOF_UNSIGNED_LONG)
+ COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED_LONG == sizeof(unsigned long));
+#endif
+#if defined(SIZEOF_UNSIGNED_SHORT)
+ COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED_SHORT == sizeof(unsigned short));
+#endif
+#if !defined(__LZO_IN_MINILZO)
+#if defined(SIZEOF_SIZE_T)
+ COMPILE_TIME_ASSERT(SIZEOF_SIZE_T == sizeof(size_t));
+#endif
+#endif
+#endif /* -edward */
+
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned char));
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned short));
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned));
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned long));
+ COMPILE_TIME_ASSERT(IS_SIGNED(short));
+ COMPILE_TIME_ASSERT(IS_SIGNED(int));
+ COMPILE_TIME_ASSERT(IS_SIGNED(long));
+
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_uint32));
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_uint));
+ COMPILE_TIME_ASSERT(IS_SIGNED(lzo_int32));
+ COMPILE_TIME_ASSERT(IS_SIGNED(lzo_int));
+
+ COMPILE_TIME_ASSERT(INT_MAX == LZO_STYPE_MAX(sizeof(int)));
+ COMPILE_TIME_ASSERT(UINT_MAX == LZO_UTYPE_MAX(sizeof(unsigned)));
+ COMPILE_TIME_ASSERT(LONG_MAX == LZO_STYPE_MAX(sizeof(long)));
+ COMPILE_TIME_ASSERT(ULONG_MAX == LZO_UTYPE_MAX(sizeof(unsigned long)));
+ // COMPILE_TIME_ASSERT(SHRT_MAX == LZO_STYPE_MAX(sizeof(short))); /* edward */
+ COMPILE_TIME_ASSERT(USHRT_MAX == LZO_UTYPE_MAX(sizeof(unsigned short)));
+ COMPILE_TIME_ASSERT(LZO_UINT32_MAX ==
+ LZO_UTYPE_MAX(sizeof(lzo_uint32)));
+ COMPILE_TIME_ASSERT(LZO_UINT_MAX == LZO_UTYPE_MAX(sizeof(lzo_uint)));
+#if !defined(__LZO_IN_MINILZO)
+ COMPILE_TIME_ASSERT(SIZE_T_MAX == LZO_UTYPE_MAX(sizeof(size_t)));
+#endif
+
+ r &= __lzo_assert(LZO_BYTE(257) == 1);
+
+ return r;
+}
+
+static lzo_bool basic_ptr_check(void)
+{
+ lzo_bool r = 1;
+
+ COMPILE_TIME_ASSERT(sizeof(char *) >= sizeof(int));
+ COMPILE_TIME_ASSERT(sizeof(lzo_byte *) >= sizeof(char *));
+
+ COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_byte *));
+ COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_voidpp));
+ COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_bytepp));
+ COMPILE_TIME_ASSERT(sizeof(lzo_voidp) >= sizeof(lzo_uint));
+
+ COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) == sizeof(lzo_voidp));
+ COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) == sizeof(lzo_sptr_t));
+ COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) >= sizeof(lzo_uint));
+
+ COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= 4);
+ COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= sizeof(ptrdiff_t));
+
+ COMPILE_TIME_ASSERT(sizeof(ptrdiff_t) >= sizeof(size_t));
+ COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= sizeof(lzo_uint));
+
+#if defined(SIZEOF_CHAR_P)
+ COMPILE_TIME_ASSERT(SIZEOF_CHAR_P == sizeof(char *));
+#endif
+#if defined(SIZEOF_PTRDIFF_T)
+ COMPILE_TIME_ASSERT(SIZEOF_PTRDIFF_T == sizeof(ptrdiff_t));
+#endif
+
+ COMPILE_TIME_ASSERT(IS_SIGNED(ptrdiff_t));
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(size_t));
+ COMPILE_TIME_ASSERT(IS_SIGNED(lzo_ptrdiff_t));
+ COMPILE_TIME_ASSERT(IS_SIGNED(lzo_sptr_t));
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_ptr_t));
+ COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_moff_t));
+
+ return r;
+}
+
+static lzo_bool ptr_check(void)
+{
+ lzo_bool r = 1;
+ int i;
+ char _wrkmem[10 * sizeof(lzo_byte *) + sizeof(lzo_full_align_t)];
+ lzo_bytep wrkmem;
+ lzo_bytepp dict;
+ unsigned char x[4 * sizeof(lzo_full_align_t)];
+ long d;
+ lzo_full_align_t a;
+ lzo_full_align_t u;
+
+ for (i = 0; i < (int)sizeof(x); i++)
+ x[i] = LZO_BYTE(i);
+
+ wrkmem =
+ LZO_PTR_ALIGN_UP((lzo_byte *) _wrkmem, sizeof(lzo_full_align_t));
+
+ u.a_lzo_bytep = wrkmem;
+ dict = u.a_lzo_bytepp;
+
+ d = (long)((const lzo_bytep)dict - (const lzo_bytep)_wrkmem);
+ r &= __lzo_assert(d >= 0);
+ r &= __lzo_assert(d < (long)sizeof(lzo_full_align_t));
+
+ memset(&a, 0, sizeof(a));
+ r &= __lzo_assert(a.a_lzo_voidp == NULL);
+
+ memset(&a, 0xff, sizeof(a));
+ r &= __lzo_assert(a.a_ushort == USHRT_MAX);
+ r &= __lzo_assert(a.a_uint == UINT_MAX);
+ r &= __lzo_assert(a.a_ulong == ULONG_MAX);
+ r &= __lzo_assert(a.a_lzo_uint == LZO_UINT_MAX);
+ r &= __lzo_assert(a.a_lzo_uint32 == LZO_UINT32_MAX);
+
+ if (r == 1) {
+ for (i = 0; i < 8; i++)
+ r &= __lzo_assert((const lzo_voidp)(&dict[i]) ==
+ (const
+ lzo_voidp)(&wrkmem[i *
+ sizeof(lzo_byte
+ *)]));
+ }
+
+ memset(&a, 0, sizeof(a));
+ r &= __lzo_assert(a.a_char_p == NULL);
+ r &= __lzo_assert(a.a_lzo_bytep == NULL);
+ r &= __lzo_assert(NULL == (void *)0);
+ if (r == 1) {
+ for (i = 0; i < 10; i++)
+ dict[i] = wrkmem;
+ BZERO8_PTR(dict + 1, sizeof(dict[0]), 8);
+ r &= __lzo_assert(dict[0] == wrkmem);
+ for (i = 1; i < 9; i++)
+ r &= __lzo_assert(dict[i] == NULL);
+ r &= __lzo_assert(dict[9] == wrkmem);
+ }
+
+ if (r == 1) {
+ unsigned k = 1;
+ const unsigned n = (unsigned)sizeof(lzo_uint32);
+ lzo_byte *p0;
+ lzo_byte *p1;
+
+ k += __lzo_align_gap(&x[k], n);
+ p0 = (lzo_bytep) & x[k];
+#if defined(PTR_LINEAR)
+ r &= __lzo_assert((PTR_LINEAR(p0) & (n - 1)) == 0);
+#else
+ r &= __lzo_assert(n == 4);
+ r &= __lzo_assert(PTR_ALIGNED_4(p0));
+#endif
+
+ r &= __lzo_assert(k >= 1);
+ p1 = (lzo_bytep) & x[1];
+ r &= __lzo_assert(PTR_GE(p0, p1));
+
+ r &= __lzo_assert(k < 1 + n);
+ p1 = (lzo_bytep) & x[1 + n];
+ r &= __lzo_assert(PTR_LT(p0, p1));
+
+ if (r == 1) {
+ lzo_uint32 v0, v1;
+
+ u.a_uchar_p = &x[k];
+ v0 = *u.a_lzo_uint32_p;
+ u.a_uchar_p = &x[k + n];
+ v1 = *u.a_lzo_uint32_p;
+
+ r &= __lzo_assert(v0 > 0);
+ r &= __lzo_assert(v1 > 0);
+ }
+ }
+
+ return r;
+}
+
+static int _lzo_config_check(void)
+{
+ lzo_bool r = 1;
+ int i;
+ union {
+ lzo_uint32 a;
+ unsigned short b;
+ lzo_uint32 aa[4];
+ unsigned char x[4 * sizeof(lzo_full_align_t)];
+ }
+ u;
+
+ COMPILE_TIME_ASSERT((int)((unsigned char)((signed char)-1)) == 255);
+ COMPILE_TIME_ASSERT((((unsigned char)128) << (int)(8 * sizeof(int) - 8))
+ < 0);
+
+ r &= basic_integral_check();
+ r &= basic_ptr_check();
+ if (r != 1)
+ return LZO_E_ERROR;
+
+ u.a = 0;
+ u.b = 0;
+ for (i = 0; i < (int)sizeof(u.x); i++)
+ u.x[i] = LZO_BYTE(i);
+
+#if defined(LZO_BYTE_ORDER)
+ if (r == 1) {
+# if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
+ lzo_uint32 a = (lzo_uint32) (u.a & LZO_0xffffffffL);
+ unsigned short b = (unsigned short)(u.b & 0xffff);
+ r &= __lzo_assert(a == 0x03020100L);
+ r &= __lzo_assert(b == 0x0100);
+# elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
+ lzo_uint32 a = u.a >> (8 * sizeof(u.a) - 32);
+ unsigned short b = u.b >> (8 * sizeof(u.b) - 16);
+ r &= __lzo_assert(a == 0x00010203L);
+ r &= __lzo_assert(b == 0x0001);
+# else
+# error "invalid LZO_BYTE_ORDER"
+# endif
+ }
+#endif
+
+#if defined(LZO_UNALIGNED_OK_2)
+ COMPILE_TIME_ASSERT(sizeof(short) == 2);
+ if (r == 1) {
+ unsigned short b[4];
+
+ for (i = 0; i < 4; i++)
+ b[i] = *(const unsigned short *)&u.x[i];
+
+# if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
+ r &= __lzo_assert(b[0] == 0x0100);
+ r &= __lzo_assert(b[1] == 0x0201);
+ r &= __lzo_assert(b[2] == 0x0302);
+ r &= __lzo_assert(b[3] == 0x0403);
+# elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
+ r &= __lzo_assert(b[0] == 0x0001);
+ r &= __lzo_assert(b[1] == 0x0102);
+ r &= __lzo_assert(b[2] == 0x0203);
+ r &= __lzo_assert(b[3] == 0x0304);
+# endif
+ }
+#endif
+
+#if defined(LZO_UNALIGNED_OK_4)
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == 4);
+ if (r == 1) {
+ lzo_uint32 a[4];
+
+ for (i = 0; i < 4; i++)
+ a[i] = *(const lzo_uint32 *)&u.x[i];
+
+# if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
+ r &= __lzo_assert(a[0] == 0x03020100L);
+ r &= __lzo_assert(a[1] == 0x04030201L);
+ r &= __lzo_assert(a[2] == 0x05040302L);
+ r &= __lzo_assert(a[3] == 0x06050403L);
+# elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
+ r &= __lzo_assert(a[0] == 0x00010203L);
+ r &= __lzo_assert(a[1] == 0x01020304L);
+ r &= __lzo_assert(a[2] == 0x02030405L);
+ r &= __lzo_assert(a[3] == 0x03040506L);
+# endif
+ }
+#endif
+
+#if defined(LZO_ALIGNED_OK_4)
+ COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == 4);
+#endif
+
+ COMPILE_TIME_ASSERT(lzo_sizeof_dict_t == sizeof(lzo_dict_t));
+
+ if (r == 1) {
+ r &= __lzo_assert(!schedule_insns_bug());
+ }
+
+ if (r == 1) {
+ static int x[3];
+ static unsigned xn = 3;
+ register unsigned j;
+
+ for (j = 0; j < xn; j++)
+ x[j] = (int)j - 3;
+ r &= __lzo_assert(!strength_reduce_bug(x));
+ }
+
+ if (r == 1) {
+ r &= ptr_check();
+ }
+
+ return r == 1 ? LZO_E_OK : LZO_E_ERROR;
+}
+
+static lzo_bool schedule_insns_bug(void)
+{
+#if defined(__LZO_CHECKER)
+ return 0;
+#else
+ const int clone[] = { 1, 2, 0 };
+ const int *q;
+ q = clone;
+ return (*q) ? 0 : 1;
+#endif
+}
+
+static lzo_bool strength_reduce_bug(int *x)
+{
+ return x[0] != -3 || x[1] != -2 || x[2] != -1;
+}
+
+#undef COMPILE_TIME_ASSERT
+
+LZO_PUBLIC(int)
+ __lzo_init2(unsigned v, int s1, int s2, int s3, int s4, int s5,
+ int s6, int s7, int s8, int s9)
+{
+ int r;
+
+ if (v == 0)
+ return LZO_E_ERROR;
+
+ r = (s1 == -1 || s1 == (int)sizeof(short)) &&
+ (s2 == -1 || s2 == (int)sizeof(int)) &&
+ (s3 == -1 || s3 == (int)sizeof(long)) &&
+ (s4 == -1 || s4 == (int)sizeof(lzo_uint32)) &&
+ (s5 == -1 || s5 == (int)sizeof(lzo_uint)) &&
+ (s6 == -1 || s6 == (int)lzo_sizeof_dict_t) &&
+ (s7 == -1 || s7 == (int)sizeof(char *)) &&
+ (s8 == -1 || s8 == (int)sizeof(lzo_voidp)) &&
+ (s9 == -1 || s9 == (int)sizeof(lzo_compress_t));
+ if (!r)
+ return LZO_E_ERROR;
+
+ r = _lzo_config_check();
+ if (r != LZO_E_OK)
+ return r;
+
+ return r;
+}
+
+#if !defined(__LZO_IN_MINILZO)
+
+LZO_EXTERN(int)
+ __lzo_init(unsigned v, int s1, int s2, int s3, int s4, int s5, int s6, int s7);
+
+LZO_PUBLIC(int)
+__lzo_init(unsigned v, int s1, int s2, int s3, int s4, int s5, int s6, int s7)
+{
+ if (v == 0 || v > 0x1010)
+ return LZO_E_ERROR;
+ return __lzo_init2(v, s1, s2, s3, s4, s5, -1, -1, s6, s7);
+}
+
+#endif
+
+#define do_compress _lzo1x_1_do_compress
+
+#define LZO_NEED_DICT_H
+#define D_BITS 14
+#define D_INDEX1(d,p) d = DM((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
+
+#if !defined(__LZO_IN_MINILZO)
+#include <lzo1x.h>
+#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
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#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
+
+#if (DL_MIN_LEN == 3)
+# define _DV2_A(p,shift1,shift2) \
+ (((( (lzo_uint32)((p)[0]) << shift1) ^ (p)[1]) << shift2) ^ (p)[2])
+# define _DV2_B(p,shift1,shift2) \
+ (((( (lzo_uint32)((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_uint32)(p[0]) << shift1) ^ p[1])
+# define _DV2_B(p,shift1,shift2) \
+ (( (lzo_uint32)(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_uint32)((p)[2]) << (s2)) + (p)[1]) << (s1)) + (p)[0])
+#define DS2(p,s1,s2) \
+ (((((lzo_uint32)((p)[2]) << (s2)) - (p)[1]) << (s1)) - (p)[0])
+#define DX2(p,s1,s2) \
+ (((((lzo_uint32)((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_uint32)(p[-1]) << (2*5); dv = (((dv) << 5) ^ p[2])
+# define _DINDEX(dv,p) ((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_uint32)(p[2]) << (2*5)))
+# define _DINDEX(dv,p) ((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_uint32 dv, const lzo_byte * p) {
+ lzo_uint32 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 = (lzo_moff_t) (ip - m_pos)) > max_offset)
+
+#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
+ (BOUNDS_CHECKING_OFF_IN_EXPR( \
+ (PTR_LT(m_pos,in) || \
+ (m_off = (lzo_moff_t) 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 = (lzo_moff_t) ((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) \
+ ((lzo_moff_t) ((ip)-(in)) <= m_off || \
+ ((m_off = (lzo_moff_t) ((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
+
+#ifdef __cplusplus
+}
+#endif
+#endif
+#endif
+#endif
+#define DO_COMPRESS lzo1x_1_compress
+static
+lzo_uint do_compress(const lzo_byte * in, lzo_uint in_len,
+ lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
+{
+ register const lzo_byte *ip;
+ lzo_byte *op;
+ const lzo_byte *const in_end = in + in_len;
+ const lzo_byte *const ip_end = in + in_len - M2_MAX_LEN - 5;
+ const lzo_byte *ii;
+ lzo_dict_p const dict = (lzo_dict_p) wrkmem;
+
+ op = out;
+ ip = in;
+ ii = ip;
+
+ ip += 4;
+ for (;;) {
+ register const lzo_byte *m_pos;
+
+ lzo_moff_t 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 1 && 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 (m_pos[2] == ip[2]) {
+ goto match;
+ } else {
+ ;
+ }
+ }
+
+ literal:
+ UPDATE_I(dict, 0, dindex, ip, in);
+ ++ip;
+ if (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("lzo-04", 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("lzo-05", tt > 0);
+ *op++ = LZO_BYTE(tt);
+ }
+ do
+ *op++ = *ii++;
+ while (--t > 0);
+ }
+
+ assert("lzo-06", 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 = ip - ii;
+ assert("lzo-07", m_len >= 3);
+ assert("lzo-08", 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("lzo-09", m_off > 0);
+ assert("lzo-10", 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_byte *end = in_end;
+ const lzo_byte *m = m_pos + M2_MAX_LEN + 1;
+ while (ip < end && *m == *ip)
+ m++, ip++;
+ m_len = (ip - ii);
+ }
+ assert("lzo-11", 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("lzo-12", m_off > 0);
+ assert("lzo-13", 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("lzo-14", m_len > 0);
+ *op++ = LZO_BYTE(m_len);
+ }
+ }
+
+ m3_m4_offset:
+ *op++ = LZO_BYTE((m_off & 63) << 2);
+ *op++ = LZO_BYTE(m_off >> 6);
+ }
+
+ ii = ip;
+ if (ip >= ip_end)
+ break;
+ }
+
+ *out_len = op - out;
+ return pd(in_end, ii);
+}
+
+LZO_PUBLIC(int)
+ DO_COMPRESS(const lzo_byte * in, lzo_uint in_len,
+ lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
+{
+ lzo_byte *op = out;
+ lzo_uint t;
+
+#if defined(__LZO_QUERY_COMPRESS)
+ if (__LZO_IS_COMPRESS_QUERY(in, in_len, out, out_len, wrkmem))
+ return __LZO_QUERY_COMPRESS(in, in_len, out, out_len, wrkmem,
+ D_SIZE, lzo_sizeof(lzo_dict_t));
+#endif
+
+ if (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_byte *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("lzo-15", tt > 0);
+ *op++ = LZO_BYTE(tt);
+ }
+ do
+ *op++ = *ii++;
+ while (--t > 0);
+ }
+
+ *op++ = M4_MARKER | 1;
+ *op++ = 0;
+ *op++ = 0;
+
+ *out_len = op - out;
+ return LZO_E_OK;
+}
+
+#undef do_compress
+#undef DO_COMPRESS
+#undef LZO_HASH
+
+#undef LZO_TEST_DECOMPRESS_OVERRUN
+#undef LZO_TEST_DECOMPRESS_OVERRUN_INPUT
+#undef LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT
+#undef LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND
+#undef DO_DECOMPRESS
+#define DO_DECOMPRESS lzo1x_decompress
+
+#if defined(LZO_TEST_DECOMPRESS_OVERRUN)
+# if !defined(LZO_TEST_DECOMPRESS_OVERRUN_INPUT)
+# define LZO_TEST_DECOMPRESS_OVERRUN_INPUT 2
+# endif
+# if !defined(LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT)
+# define LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT 2
+# endif
+# if !defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
+# define LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND
+# endif
+#endif
+
+#undef TEST_IP
+#undef TEST_OP
+#undef TEST_LOOKBEHIND
+#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_DECOMPRESS_OVERRUN_INPUT)
+# if (LZO_TEST_DECOMPRESS_OVERRUN_INPUT >= 1)
+# define TEST_IP (ip < ip_end)
+# endif
+# if (LZO_TEST_DECOMPRESS_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_DECOMPRESS_OVERRUN_OUTPUT)
+# if (LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT >= 1)
+# define TEST_OP (op <= op_end)
+# endif
+# if (LZO_TEST_DECOMPRESS_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_DECOMPRESS_OVERRUN_LOOKBEHIND)
+# define TEST_LOOKBEHIND(m_pos,out) if (m_pos < out) goto lookbehind_overrun
+#else
+# define TEST_LOOKBEHIND(m_pos,op) ((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_ptr_t)(dst),(lzo_ptr_t)(src))
+#endif
+
+#if defined(DO_DECOMPRESS)
+LZO_PUBLIC(int)
+ DO_DECOMPRESS(const lzo_byte * in, lzo_uint in_len,
+ lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
+#endif
+{
+ register lzo_byte *op;
+ register const lzo_byte *ip;
+ register lzo_uint t;
+#if defined(COPY_DICT)
+ lzo_uint m_off;
+ const lzo_byte *dict_end;
+#else
+ register const lzo_byte *m_pos;
+#endif
+
+ const lzo_byte *const ip_end = in + in_len;
+#if defined(HAVE_ANY_OP)
+ lzo_byte *const op_end = out + *out_len;
+#endif
+#if defined(LZO1Z)
+ lzo_uint last_m_off = 0;
+#endif
+
+ LZO_UNUSED(wrkmem);
+
+#if defined(__LZO_QUERY_DECOMPRESS)
+ if (__LZO_IS_DECOMPRESS_QUERY(in, in_len, out, out_len, wrkmem))
+ return __LZO_QUERY_DECOMPRESS(in, in_len, out, out_len, wrkmem,
+ 0, 0);
+#endif
+
+#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("lzo-16", 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("lzo-17", 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_LOOKBEHIND(m_pos, out);
+ NEED_OP(3);
+ *op++ = *m_pos++;
+ *op++ = *m_pos++;
+ *op++ = *m_pos;
+#endif
+ goto match_done;
+
+ while (TEST_IP && TEST_OP) {
+ 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_LOOKBEHIND(m_pos, out);
+ assert("lzo-18", 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) && (LZO_BYTE_ORDER == LZO_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) && (LZO_BYTE_ORDER == LZO_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 = 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_LOOKBEHIND(m_pos, out);
+ 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_LOOKBEHIND(m_pos, out);
+ assert("lzo-19", 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("lzo-20", t > 0);
+ NEED_OP(t);
+ NEED_IP(t + 1);
+ do
+ *op++ = *ip++;
+ while (--t > 0);
+ t = *ip++;
+ }
+ }
+
+#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
+ *out_len = op - out;
+ return LZO_E_EOF_NOT_FOUND;
+#endif
+
+ eof_found:
+ assert("lzo-21", t == 1);
+ *out_len = 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 = op - out;
+ return LZO_E_INPUT_OVERRUN;
+#endif
+
+#if defined(HAVE_NEED_OP)
+ output_overrun:
+ *out_len = op - out;
+ return LZO_E_OUTPUT_OVERRUN;
+#endif
+
+#if defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
+ lookbehind_overrun:
+ *out_len = op - out;
+ return LZO_E_LOOKBEHIND_OVERRUN;
+#endif
+}
+
+#define LZO_TEST_DECOMPRESS_OVERRUN
+#undef DO_DECOMPRESS
+#define DO_DECOMPRESS lzo1x_decompress_safe
+
+#if defined(LZO_TEST_DECOMPRESS_OVERRUN)
+# if !defined(LZO_TEST_DECOMPRESS_OVERRUN_INPUT)
+# define LZO_TEST_DECOMPRESS_OVERRUN_INPUT 2
+# endif
+# if !defined(LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT)
+# define LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT 2
+# endif
+# if !defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
+# define LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND
+# endif
+#endif
+
+#undef TEST_IP
+#undef TEST_OP
+#undef TEST_LOOKBEHIND
+#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_DECOMPRESS_OVERRUN_INPUT)
+# if (LZO_TEST_DECOMPRESS_OVERRUN_INPUT >= 1)
+# define TEST_IP (ip < ip_end)
+# endif
+# if (LZO_TEST_DECOMPRESS_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_DECOMPRESS_OVERRUN_OUTPUT)
+# if (LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT >= 1)
+# define TEST_OP (op <= op_end)
+# endif
+# if (LZO_TEST_DECOMPRESS_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_DECOMPRESS_OVERRUN_LOOKBEHIND)
+# define TEST_LOOKBEHIND(m_pos,out) if (m_pos < out) goto lookbehind_overrun
+#else
+# define TEST_LOOKBEHIND(m_pos,op) ((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_ptr_t)(dst),(lzo_ptr_t)(src))
+#endif
+
+/***** End of minilzo.c *****/
On Sun, 27 Aug 2006 04:34:26 +0400
Alexey Dobriyan <[email protected]> wrote:
> The patch below is so-called reiser4 LZO compression plugin as extracted
> from 2.6.18-rc4-mm3.
>
> I think it is an unauditable piece of shit and thus should not enter
> mainline.
Like lib/inflate.c (and this new code should arguably be in lib/).
The problem is that if we clean this up, we've diverged very much from the
upstream implementation. So taking in fixes and features from upstream
becomes harder and more error-prone.
I'd suspect that the maturity of these utilities is such that we could
afford to turn them into kernel code in the expectation that any future
changes will be small. But it's not a completely simple call.
(iirc the inflate code had a buffer overrun a while back, which was found
and fixed in the upstream version).
On 8/27/06, Andrew Morton <[email protected]> wrote:
> On Sun, 27 Aug 2006 04:34:26 +0400
> Alexey Dobriyan <[email protected]> wrote:
>
> > The patch below is so-called reiser4 LZO compression plugin as extracted
> > from 2.6.18-rc4-mm3.
> >
> > I think it is an unauditable piece of shit and thus should not enter
> > mainline.
Sheesh.
> Like lib/inflate.c (and this new code should arguably be in lib/).
>
> The problem is that if we clean this up, we've diverged very much from the
> upstream implementation. So taking in fixes and features from upstream
> becomes harder and more error-prone.
Right. How about putting it in as so that everyone can track
divergences, but to not use it for a real compile. Rather, consider it
meta-source, and do mechanical, repeatable transformations only,
starting with something like:
mv minilzo.c minilzo._c
cpp 2>/dev/null -w -P -C -nostdinc -dI minilzo._c >minilzo.c
lindent minilzo.c
to generate a version that can be audited. Doing so on a version of
minilzo.c google found on the web generated something that looked much
like any other stream coder source I've read, so it approaches
readability. Of a sorts. Further cleanups could be done with cpp -D to
rename some of the more bizarre symbols.
Downside is that bugs would have to be fixed in the 'meta-source'
(horrible name, but it's late here), but at least they could be found
(potentially) easier than in the original.
Ray
Andrew Morton wrote:
> On Sun, 27 Aug 2006 04:34:26 +0400
> Alexey Dobriyan <[email protected]> wrote:
>
>> The patch below is so-called reiser4 LZO compression plugin as extracted
>> from 2.6.18-rc4-mm3.
>>
>> I think it is an unauditable piece of shit and thus should not enter
>> mainline.
>
> Like lib/inflate.c (and this new code should arguably be in lib/).
>
> The problem is that if we clean this up, we've diverged very much from the
> upstream implementation. So taking in fixes and features from upstream
> becomes harder and more error-prone.
Well, what kinds of changes have to happen? I doubt upstream would care
about moving some of it to lib/ -- and anyway, reiserfs-list is on the
CC. We are speaking of upstream in the third party in the presence of
upstream, so...
Maybe just ask upstream?
On Sun, 27 August 2006 01:04:28 -0700, Andrew Morton wrote:
>
> Like lib/inflate.c (and this new code should arguably be in lib/).
>
> The problem is that if we clean this up, we've diverged very much from the
> upstream implementation. So taking in fixes and features from upstream
> becomes harder and more error-prone.
I've had an identical argument with Linus about lib/zlib_*. He
decided that he didn't care about diverging, I went ahead and changed
the code. In the process, I merged a couple of outstanding bugfixes
and reduced memory consumption by 25%. Looks like Linus was right on
that one.
> I'd suspect that the maturity of these utilities is such that we could
> afford to turn them into kernel code in the expectation that any future
> changes will be small. But it's not a completely simple call.
>
> (iirc the inflate code had a buffer overrun a while back, which was found
> and fixed in the upstream version).
Dito in lib/zlib_*. lib/inflage.c is only used for the various
in-kernel bootloaders to uncompress a kernel image. Anyone tampering
with the image to cause a buffer overrun already owns the machine
anyway.
Whether any of our experiences with zlib apply to lzo remains a
question, though.
J?rn
--
I've never met a human being who would want to read 17,000 pages of
documentation, and if there was, I'd kill him to get him out of the
gene pool.
-- Joseph Costello
On Sun, 27 Aug 2006 04:42:59 -0500
David Masover <[email protected]> wrote:
> Andrew Morton wrote:
> > On Sun, 27 Aug 2006 04:34:26 +0400
> > Alexey Dobriyan <[email protected]> wrote:
> >
> >> The patch below is so-called reiser4 LZO compression plugin as
> >> extracted from 2.6.18-rc4-mm3.
> >>
> >> I think it is an unauditable piece of shit and thus should not
> >> enter mainline.
> >
> > Like lib/inflate.c (and this new code should arguably be in lib/).
> >
> > The problem is that if we clean this up, we've diverged very much
> > from the upstream implementation. So taking in fixes and features
> > from upstream becomes harder and more error-prone.
>
> Well, what kinds of changes have to happen? I doubt upstream would
> care about moving some of it to lib/ -- and anyway, reiserfs-list is
> on the CC. We are speaking of upstream in the third party in the
> presence of upstream, so...
The ifdef jungle is ugly, and especially the WIN / 16-bit DOS stuff is
completely useless here.
> Maybe just ask upstream?
I am not sure if Mr. Oberhumer still cares about LZO 1.x, AFAIK he now
develops a new compressor under a commercial license.
Regards,
--
Jindrich Makovicka
On Mon, Aug 28, 2006 at 10:06:46AM -0700, Hans Reiser wrote:
> Hmm. LZO is the best compression algorithm for the task as measured by
> the objectives of good compression effectiveness while still having very
> low CPU usage (the best of those written and GPL'd, there is a slightly
> better one which is proprietary and uses more CPU, LZRW if I remember
> right. The gzip code base uses too much CPU, though I think Edward made
I don't think that LZO beats LZF in both speed and compression ratio.
LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
of LZO for the next generation suspend-to-disk code of the Linux kernel.
see: http://www.goof.com/pcg/marc/liblzf.html
--
ciao -
Stefan
Jindrich Makovicka wrote:
> On Sun, 27 Aug 2006 04:42:59 -0500
> David Masover <[email protected]> wrote:
>
>
>>Andrew Morton wrote:
>>
>>>On Sun, 27 Aug 2006 04:34:26 +0400
>>>Alexey Dobriyan <[email protected]> wrote:
>>>
>>>
>>>>The patch below is so-called reiser4 LZO compression plugin as
>>>>extracted from 2.6.18-rc4-mm3.
>>>>
>>>>I think it is an unauditable piece of shit and thus should not
>>>>enter mainline.
>>>
>>>Like lib/inflate.c (and this new code should arguably be in lib/).
>>>
>>>The problem is that if we clean this up, we've diverged very much
>>>from the upstream implementation. So taking in fixes and features
>>>from upstream becomes harder and more error-prone.
>>
>>Well, what kinds of changes have to happen? I doubt upstream would
>>care about moving some of it to lib/ -- and anyway, reiserfs-list is
>>on the CC. We are speaking of upstream in the third party in the
>>presence of upstream, so...
>
>
> The ifdef jungle is ugly, and especially the WIN / 16-bit DOS stuff is
> completely useless here.
>
I agree that it needs some brushing,
putting in todo..
>
>>Maybe just ask upstream?
>
>
> I am not sure if Mr. Oberhumer still cares about LZO 1.x, AFAIK he now
> develops a new compressor under a commercial license.
>
> Regards,
Stefan Traby wrote:
> On Mon, Aug 28, 2006 at 10:06:46AM -0700, Hans Reiser wrote:
>
>
>>Hmm. LZO is the best compression algorithm for the task as measured by
>>the objectives of good compression effectiveness while still having very
>>low CPU usage (the best of those written and GPL'd, there is a slightly
>>better one which is proprietary and uses more CPU, LZRW if I remember
>>right. The gzip code base uses too much CPU, though I think Edward made
>
>
> I don't think that LZO beats LZF in both speed and compression ratio.
>
> LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
> of LZO for the next generation suspend-to-disk code of the Linux kernel.
>
> see: http://www.goof.com/pcg/marc/liblzf.html
>
thanks for the info, we will compare them
Hi.
On Mon, 2006-08-28 at 22:15 +0400, Edward Shishkin wrote:
> Stefan Traby wrote:
> > On Mon, Aug 28, 2006 at 10:06:46AM -0700, Hans Reiser wrote:
> >
> >
> >>Hmm. LZO is the best compression algorithm for the task as measured by
> >>the objectives of good compression effectiveness while still having very
> >>low CPU usage (the best of those written and GPL'd, there is a slightly
> >>better one which is proprietary and uses more CPU, LZRW if I remember
> >>right. The gzip code base uses too much CPU, though I think Edward made
> >
> >
> > I don't think that LZO beats LZF in both speed and compression ratio.
> >
> > LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
> > of LZO for the next generation suspend-to-disk code of the Linux kernel.
> >
> > see: http://www.goof.com/pcg/marc/liblzf.html
> >
>
> thanks for the info, we will compare them
For Suspend2, we ended up converting the LZF support to a cryptoapi
plugin. Is there any chance that you could use cryptoapi modules? We
could then have a hope of sharing the support.
Regards,
Nigel
Nigel Cunningham wrote:
> For Suspend2, we ended up converting the LZF support to a cryptoapi
> plugin. Is there any chance that you could use cryptoapi modules? We
> could then have a hope of sharing the support
It is in principle a good idea, and I hope we will be able to say yes.
However, I have to see the numbers, as we are more performance sensitive
than you folks probably are, and every 10% is a big deal for us.
>> >>Hmm. LZO is the best compression algorithm for the task as measured by
>> >>the objectives of good compression effectiveness while still having very
>> >>low CPU usage (the best of those written and GPL'd, there is a slightly
>> >>better one which is proprietary and uses more CPU, LZRW if I remember
>> >>right. The gzip code base uses too much CPU, though I think Edward made
>> >
>> > I don't think that LZO beats LZF in both speed and compression ratio.
>> >
>> > LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
>> > of LZO for the next generation suspend-to-disk code of the Linux kernel.
>> >
>> > see: http://www.goof.com/pcg/marc/liblzf.html
>>
>> thanks for the info, we will compare them
>
>For Suspend2, we ended up converting the LZF support to a cryptoapi
>plugin. Is there any chance that you could use cryptoapi modules? We
>could then have a hope of sharing the support.
I am throwing in gzip: would it be meaningful to use that instead? The
decoder (inflate.c) is already there.
06:04 shanghai:~/liblzf-1.6 > l configure*
-rwxr-xr-x 1 jengelh users 154894 Mar 3 2005 configure
-rwxr-xr-x 1 jengelh users 26810 Mar 3 2005 configure.bz2
-rw-r--r-- 1 jengelh users 30611 Aug 28 20:32 configure.gz-z9
-rw-r--r-- 1 jengelh users 30693 Aug 28 20:32 configure.gz-z6
-rw-r--r-- 1 jengelh users 53077 Aug 28 20:32 configure.lzf
Jan Engelhardt
--
On Tue, Aug 29, 2006 at 07:48:25AM +1000, Nigel Cunningham wrote:
> For Suspend2, we ended up converting the LZF support to a cryptoapi
> plugin. Is there any chance that you could use cryptoapi modules? We
> could then have a hope of sharing the support.
>
Using cryptoapi plugins for the compression methods is an interesting
approach, there's a few other places in the kernel that could probably
benefit from this as well, such as jffs2 (which at the moment rolls its
own compression subsystem), and the out-of-tree page and swap cache
compression work.
Assuming you were wrapping in to LZF directly prior to the cryptoapi
integration, do you happen to have before and after numbers to determine
how heavyweight the rest of the cryptoapi overhead is? It would be
interesting to profile this and consider migrating the in-tree users,
rather than duplicating the compress/decompress routines all over the
place.
Hi.
On Tue, 2006-08-29 at 06:05 +0200, Jan Engelhardt wrote:
> >> >>Hmm. LZO is the best compression algorithm for the task as measured by
> >> >>the objectives of good compression effectiveness while still having very
> >> >>low CPU usage (the best of those written and GPL'd, there is a slightly
> >> >>better one which is proprietary and uses more CPU, LZRW if I remember
> >> >>right. The gzip code base uses too much CPU, though I think Edward made
> >> >
> >> > I don't think that LZO beats LZF in both speed and compression ratio.
> >> >
> >> > LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
> >> > of LZO for the next generation suspend-to-disk code of the Linux kernel.
> >> >
> >> > see: http://www.goof.com/pcg/marc/liblzf.html
> >>
> >> thanks for the info, we will compare them
> >
> >For Suspend2, we ended up converting the LZF support to a cryptoapi
> >plugin. Is there any chance that you could use cryptoapi modules? We
> >could then have a hope of sharing the support.
>
> I am throwing in gzip: would it be meaningful to use that instead? The
> decoder (inflate.c) is already there.
>
> 06:04 shanghai:~/liblzf-1.6 > l configure*
> -rwxr-xr-x 1 jengelh users 154894 Mar 3 2005 configure
> -rwxr-xr-x 1 jengelh users 26810 Mar 3 2005 configure.bz2
> -rw-r--r-- 1 jengelh users 30611 Aug 28 20:32 configure.gz-z9
> -rw-r--r-- 1 jengelh users 30693 Aug 28 20:32 configure.gz-z6
> -rw-r--r-- 1 jengelh users 53077 Aug 28 20:32 configure.lzf
We used gzip when we first implemented compression support, and found it
to be far too slow. Even with the fastest compression options, we were
only getting a few megabytes per second. Perhaps I did something wrong
in configuring it, but there's not that many things to get wrong!
In contrast, with LZF, we get very high throughput. My current laptop is
an 1.8MHz Turion with a 7200 RPM (PATA) drive. Without LZF compression,
my throughput in writing an image is the maximum the drive & interface
can manage - 38MB/s. With LZF, I get roughly that divided by compression
ratio achieved, so if the compression ratio is ~50%, as it generally is,
I'm reading and writing the image at 75-80MB/s. During this time, all
the computer is doing is compressing pages using LZF and submitting
bios, with the odd message being send to the userspace interface app via
netlink. I realise this is very different to the workload you'll be
doing, but hopefully the numbers are somewhat useful:
nigel@nigel:~$ cat /sys/power/suspend2/debug_info
Suspend2 debugging info:
- SUSPEND core : 2.2.7.4
- Kernel Version : 2.6.18-rc4
- Compiler vers. : 4.1
- Attempt number : 1
- Parameters : 0 32785 0 0 0 0
- Overall expected compression percentage: 0.
- Compressor is 'lzf'.
Compressed 820006912 bytes into 430426371 (47 percent compression).
- Swapwriter active.
Swap available for image: 487964 pages.
- Filewriter inactive.
- I/O speed: Write 74 MB/s, Read 70 MB/s.
- Extra pages : 1913 used/2100.
nigel@nigel:~$
(Modify hibernate.conf to disable compression, suspend again...)
nigel@nigel:~$ cat /sys/power/suspend2/debug_info
Suspend2 debugging info:
- SUSPEND core : 2.2.7.4
- Kernel Version : 2.6.18-rc4
- Compiler vers. : 4.1
- Attempt number : 2
- Parameters : 0 32785 0 0 0 0
- Overall expected compression percentage: 0.
- Swapwriter active.
Swap available for image: 487964 pages.
- Filewriter inactive.
- I/O speed: Write 38 MB/s, Read 39 MB/s.
- Extra pages : 1907 used/2100.
nigel@nigel:~$
Oh, I also have a debugging mode where I can get Suspend2 to just
compress the pages but not actually write anything. If I do that, it
says it can do 80MB/s on my kernel image, so the disk is still the
bottleneck, it seems.
Hope this all helps (and isn't information overload!)
Nigel
Hi.
On Tue, 2006-08-29 at 13:59 +0900, Paul Mundt wrote:
> On Tue, Aug 29, 2006 at 07:48:25AM +1000, Nigel Cunningham wrote:
> > For Suspend2, we ended up converting the LZF support to a cryptoapi
> > plugin. Is there any chance that you could use cryptoapi modules? We
> > could then have a hope of sharing the support.
> >
> Using cryptoapi plugins for the compression methods is an interesting
> approach, there's a few other places in the kernel that could probably
> benefit from this as well, such as jffs2 (which at the moment rolls its
> own compression subsystem), and the out-of-tree page and swap cache
> compression work.
>
> Assuming you were wrapping in to LZF directly prior to the cryptoapi
> integration, do you happen to have before and after numbers to determine
> how heavyweight the rest of the cryptoapi overhead is? It would be
> interesting to profile this and consider migrating the in-tree users,
> rather than duplicating the compress/decompress routines all over the
> place.
I was, but I don't have numbers right now. I'm about to go out, but will
see if I can find them when I get back later. From memory, it wasn't a
huge change in terms of lines of code.
Regards,
Nigel
Nigel Cunningham wrote:
> Hi.
>
> On Tue, 2006-08-29 at 06:05 +0200, Jan Engelhardt wrote:
>>>>>> Hmm. LZO is the best compression algorithm for the task as measured by
>>>>>> the objectives of good compression effectiveness while still having very
>>>>>> low CPU usage (the best of those written and GPL'd, there is a slightly
>>>>>> better one which is proprietary and uses more CPU, LZRW if I remember
>>>>>> right. The gzip code base uses too much CPU, though I think Edward made
>>>>> I don't think that LZO beats LZF in both speed and compression ratio.
>>>>>
>>>>> LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
>>>>> of LZO for the next generation suspend-to-disk code of the Linux kernel.
>>>>>
>>>>> see: http://www.goof.com/pcg/marc/liblzf.html
>>>> thanks for the info, we will compare them
>>> For Suspend2, we ended up converting the LZF support to a cryptoapi
>>> plugin. Is there any chance that you could use cryptoapi modules? We
>>> could then have a hope of sharing the support.
>> I am throwing in gzip: would it be meaningful to use that instead? The
>> decoder (inflate.c) is already there.
>>
>> 06:04 shanghai:~/liblzf-1.6 > l configure*
>> -rwxr-xr-x 1 jengelh users 154894 Mar 3 2005 configure
>> -rwxr-xr-x 1 jengelh users 26810 Mar 3 2005 configure.bz2
>> -rw-r--r-- 1 jengelh users 30611 Aug 28 20:32 configure.gz-z9
>> -rw-r--r-- 1 jengelh users 30693 Aug 28 20:32 configure.gz-z6
>> -rw-r--r-- 1 jengelh users 53077 Aug 28 20:32 configure.lzf
>
> We used gzip when we first implemented compression support, and found it
> to be far too slow. Even with the fastest compression options, we were
> only getting a few megabytes per second. Perhaps I did something wrong
> in configuring it, but there's not that many things to get wrong!
All that comes to mind is the speed/quality setting -- the number from 1
to 9. Recently, I backed up someone's hard drive using -1, and I
believe I was still able to saturate... the _network_. Definitely try
again if you haven't changed this, but I can't imagine I'm the first
persson to think of it.
From what I remember, gzip -1 wasn't faster than the disk. But at
least for (very) repetitive data, I was wrong:
eve:~ sanity$ time bash -c 'dd if=/dev/zero of=test bs=10m count=10; sync'
10+0 records in
10+0 records out
104857600 bytes transferred in 3.261990 secs (32145287 bytes/sec)
real 0m3.746s
user 0m0.005s
sys 0m0.627s
eve:~ sanity$ time bash -c 'dd if=/dev/zero bs=10m count=10 | gzip -v1 >
test; sync'
10+0 records in
10+0 records out
104857600 bytes transferred in 2.404093 secs (43616282 bytes/sec)
99.5%
real 0m2.558s
user 0m1.554s
sys 0m0.680s
eve:~ sanity$
This was on OS X, but I think it's still valid -- this is a slightly
older Powerbook, with a 5400 RPM drive, 1.6 ghz G4.
-1 is still worlds better than nothing. The backup was over 15 gigs,
down to about 6 -- loads of repetitive data, I'm sure, but that's where
you win with compression anyway.
Well, you use cryptoapi anyway, so it should be easy to just let the
user pick a plugin, right?
Nigel Cunningham wrote:
> Hi.
>
> On Mon, 2006-08-28 at 22:15 +0400, Edward Shishkin wrote:
>
>>Stefan Traby wrote:
>>
>>>On Mon, Aug 28, 2006 at 10:06:46AM -0700, Hans Reiser wrote:
>>>
>>>
>>>
>>>>Hmm. LZO is the best compression algorithm for the task as measured by
>>>>the objectives of good compression effectiveness while still having very
>>>>low CPU usage (the best of those written and GPL'd, there is a slightly
>>>>better one which is proprietary and uses more CPU, LZRW if I remember
>>>>right. The gzip code base uses too much CPU, though I think Edward made
>>>
>>>
>>>I don't think that LZO beats LZF in both speed and compression ratio.
>>>
>>>LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
>>>of LZO for the next generation suspend-to-disk code of the Linux kernel.
>>>
>>>see: http://www.goof.com/pcg/marc/liblzf.html
>>>
>>
>>thanks for the info, we will compare them
>
>
> For Suspend2, we ended up converting the LZF support to a cryptoapi
> plugin. Is there any chance that you could use cryptoapi modules? We
> could then have a hope of sharing the support.
>
No problems with using crypto-api. Reiser4 bypasses it, because
currently it supplies the only compression level, which is fairly
bad for compressed file systems.
Edward.
Hi.
On Tue, 2006-08-29 at 03:23 -0500, David Masover wrote:
> Nigel Cunningham wrote:
> > Hi.
> >
> > On Tue, 2006-08-29 at 06:05 +0200, Jan Engelhardt wrote:
> >>>>>> Hmm. LZO is the best compression algorithm for the task as measured by
> >>>>>> the objectives of good compression effectiveness while still having very
> >>>>>> low CPU usage (the best of those written and GPL'd, there is a slightly
> >>>>>> better one which is proprietary and uses more CPU, LZRW if I remember
> >>>>>> right. The gzip code base uses too much CPU, though I think Edward made
> >>>>> I don't think that LZO beats LZF in both speed and compression ratio.
> >>>>>
> >>>>> LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
> >>>>> of LZO for the next generation suspend-to-disk code of the Linux kernel.
> >>>>>
> >>>>> see: http://www.goof.com/pcg/marc/liblzf.html
> >>>> thanks for the info, we will compare them
> >>> For Suspend2, we ended up converting the LZF support to a cryptoapi
> >>> plugin. Is there any chance that you could use cryptoapi modules? We
> >>> could then have a hope of sharing the support.
> >> I am throwing in gzip: would it be meaningful to use that instead? The
> >> decoder (inflate.c) is already there.
> >>
> >> 06:04 shanghai:~/liblzf-1.6 > l configure*
> >> -rwxr-xr-x 1 jengelh users 154894 Mar 3 2005 configure
> >> -rwxr-xr-x 1 jengelh users 26810 Mar 3 2005 configure.bz2
> >> -rw-r--r-- 1 jengelh users 30611 Aug 28 20:32 configure.gz-z9
> >> -rw-r--r-- 1 jengelh users 30693 Aug 28 20:32 configure.gz-z6
> >> -rw-r--r-- 1 jengelh users 53077 Aug 28 20:32 configure.lzf
> >
> > We used gzip when we first implemented compression support, and found it
> > to be far too slow. Even with the fastest compression options, we were
> > only getting a few megabytes per second. Perhaps I did something wrong
> > in configuring it, but there's not that many things to get wrong!
>
> All that comes to mind is the speed/quality setting -- the number from 1
> to 9. Recently, I backed up someone's hard drive using -1, and I
> believe I was still able to saturate... the _network_. Definitely try
> again if you haven't changed this, but I can't imagine I'm the first
> persson to think of it.
>
> From what I remember, gzip -1 wasn't faster than the disk. But at
> least for (very) repetitive data, I was wrong:
>
> eve:~ sanity$ time bash -c 'dd if=/dev/zero of=test bs=10m count=10; sync'
> 10+0 records in
> 10+0 records out
> 104857600 bytes transferred in 3.261990 secs (32145287 bytes/sec)
>
> real 0m3.746s
> user 0m0.005s
> sys 0m0.627s
> eve:~ sanity$ time bash -c 'dd if=/dev/zero bs=10m count=10 | gzip -v1 >
> test; sync'
> 10+0 records in
> 10+0 records out
> 104857600 bytes transferred in 2.404093 secs (43616282 bytes/sec)
> 99.5%
>
> real 0m2.558s
> user 0m1.554s
> sys 0m0.680s
> eve:~ sanity$
>
>
>
> This was on OS X, but I think it's still valid -- this is a slightly
> older Powerbook, with a 5400 RPM drive, 1.6 ghz G4.
>
> -1 is still worlds better than nothing. The backup was over 15 gigs,
> down to about 6 -- loads of repetitive data, I'm sure, but that's where
> you win with compression anyway.
Wow. That's a lot better; I guess I did get something wrong in trying to
tune deflate. That was pre-cryptoapi though; looking at
cryptoapi/deflate.c, I don't see any way of controlling the compression
level. Am I missing anything?
> Well, you use cryptoapi anyway, so it should be easy to just let the
> user pick a plugin, right?
Right. They can already pick deflate if they want to.
Regards,
Nigel
On 8/29/06, Nigel Cunningham <[email protected]> wrote:
> Hi.
> On Tue, 2006-08-29 at 03:23 -0500, David Masover wrote:
> > Nigel Cunningham wrote:
> > > We used gzip when we first implemented compression support, and found it
> > > to be far too slow. Even with the fastest compression options, we were
> > > only getting a few megabytes per second. Perhaps I did something wrong
> > > in configuring it, but there's not that many things to get wrong!
> >
> > All that comes to mind is the speed/quality setting -- the number from 1
> > to 9. Recently, I backed up someone's hard drive using -1, and I
> > believe I was still able to saturate... the _network_. Definitely try
> > again if you haven't changed this, but I can't imagine I'm the first
> > persson to think of it.
> >
> > From what I remember, gzip -1 wasn't faster than the disk. But at
> > least for (very) repetitive data, I was wrong:
> >
> > eve:~ sanity$ time bash -c 'dd if=/dev/zero of=test bs=10m count=10; sync'
> > 10+0 records in
> > 10+0 records out
> > 104857600 bytes transferred in 3.261990 secs (32145287 bytes/sec)
> >
> > real 0m3.746s
> > user 0m0.005s
> > sys 0m0.627s
> > eve:~ sanity$ time bash -c 'dd if=/dev/zero bs=10m count=10 | gzip -v1 >
> > test; sync'
> > 10+0 records in
> > 10+0 records out
> > 104857600 bytes transferred in 2.404093 secs (43616282 bytes/sec)
> > 99.5%
> >
> > real 0m2.558s
> > user 0m1.554s
> > sys 0m0.680s
> > eve:~ sanity$
> >
> >
> >
> > This was on OS X, but I think it's still valid -- this is a slightly
> > older Powerbook, with a 5400 RPM drive, 1.6 ghz G4.
> >
> > -1 is still worlds better than nothing. The backup was over 15 gigs,
> > down to about 6 -- loads of repetitive data, I'm sure, but that's where
> > you win with compression anyway.
>
> Wow. That's a lot better; I guess I did get something wrong in trying to
> tune deflate. That was pre-cryptoapi though; looking at
> cryptoapi/deflate.c, I don't see any way of controlling the compression
> level. Am I missing anything?
Compressing /dev/zero isn't a great test. The timings are really data-dependant:
ray@phoenix:~$ time bash -c 'sudo dd if=/dev/zero bs=8M count=64 |
gzip -v1 >/dev/null'
64+0 records in
64+0 records out
536870912 bytes (537 MB) copied, 7.60817 seconds, 70.6 MB/s
99.6%
real 0m7.652s
user 0m6.581s
sys 0m0.701s
ray@phoenix:~$ time bash -c 'sudo dd if=/dev/mem bs=8M count=64 | gzip
-v1 >/dev/null'
64+0 records in
64+0 records out
536870912 bytes (537 MB) copied, 21.5863 seconds, 24.9 MB/s
70.4%
real 0m21.626s
user 0m18.763s
sys 0m1.762s
This is on an AMD64 laptop.
Ray
Nigel Cunningham wrote:
> Hi.
>
> On Tue, 2006-08-29 at 03:23 -0500, David Masover wrote:
>
>>Nigel Cunningham wrote:
>>
>>>Hi.
>>>
>>>On Tue, 2006-08-29 at 06:05 +0200, Jan Engelhardt wrote:
>>>
>>>>>>>>Hmm. LZO is the best compression algorithm for the task as measured by
>>>>>>>>the objectives of good compression effectiveness while still having very
>>>>>>>>low CPU usage (the best of those written and GPL'd, there is a slightly
>>>>>>>>better one which is proprietary and uses more CPU, LZRW if I remember
>>>>>>>>right. The gzip code base uses too much CPU, though I think Edward made
>>>>>>>
>>>>>>>I don't think that LZO beats LZF in both speed and compression ratio.
>>>>>>>
>>>>>>>LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
>>>>>>>of LZO for the next generation suspend-to-disk code of the Linux kernel.
>>>>>>>
>>>>>>>see: http://www.goof.com/pcg/marc/liblzf.html
>>>>>>
>>>>>>thanks for the info, we will compare them
>>>>>
>>>>>For Suspend2, we ended up converting the LZF support to a cryptoapi
>>>>>plugin. Is there any chance that you could use cryptoapi modules? We
>>>>>could then have a hope of sharing the support.
>>>>
>>>>I am throwing in gzip: would it be meaningful to use that instead? The
>>>>decoder (inflate.c) is already there.
>>>>
>>>>06:04 shanghai:~/liblzf-1.6 > l configure*
>>>>-rwxr-xr-x 1 jengelh users 154894 Mar 3 2005 configure
>>>>-rwxr-xr-x 1 jengelh users 26810 Mar 3 2005 configure.bz2
>>>>-rw-r--r-- 1 jengelh users 30611 Aug 28 20:32 configure.gz-z9
>>>>-rw-r--r-- 1 jengelh users 30693 Aug 28 20:32 configure.gz-z6
>>>>-rw-r--r-- 1 jengelh users 53077 Aug 28 20:32 configure.lzf
>>>
>>>We used gzip when we first implemented compression support, and found it
>>>to be far too slow. Even with the fastest compression options, we were
>>>only getting a few megabytes per second. Perhaps I did something wrong
>>>in configuring it, but there's not that many things to get wrong!
>>
>>All that comes to mind is the speed/quality setting -- the number from 1
>>to 9. Recently, I backed up someone's hard drive using -1, and I
>>believe I was still able to saturate... the _network_. Definitely try
>>again if you haven't changed this, but I can't imagine I'm the first
>>persson to think of it.
>>
>> From what I remember, gzip -1 wasn't faster than the disk. But at
>>least for (very) repetitive data, I was wrong:
>>
>>eve:~ sanity$ time bash -c 'dd if=/dev/zero of=test bs=10m count=10; sync'
>>10+0 records in
>>10+0 records out
>>104857600 bytes transferred in 3.261990 secs (32145287 bytes/sec)
>>
>>real 0m3.746s
>>user 0m0.005s
>>sys 0m0.627s
>>eve:~ sanity$ time bash -c 'dd if=/dev/zero bs=10m count=10 | gzip -v1 >
>>test; sync'
>>10+0 records in
>>10+0 records out
>>104857600 bytes transferred in 2.404093 secs (43616282 bytes/sec)
>> 99.5%
>>
>>real 0m2.558s
>>user 0m1.554s
>>sys 0m0.680s
>>eve:~ sanity$
>>
>>
>>
>>This was on OS X, but I think it's still valid -- this is a slightly
>>older Powerbook, with a 5400 RPM drive, 1.6 ghz G4.
>>
>>-1 is still worlds better than nothing. The backup was over 15 gigs,
>>down to about 6 -- loads of repetitive data, I'm sure, but that's where
>>you win with compression anyway.
>
>
> Wow. That's a lot better; I guess I did get something wrong in trying to
> tune deflate. That was pre-cryptoapi though; looking at
> cryptoapi/deflate.c, I don't see any way of controlling the compression
> level. Am I missing anything?
>
zlib is tunable, not cryptoapi's deflate.
look at zlib_deflateInit2()
>
>>Well, you use cryptoapi anyway, so it should be easy to just let the
>>user pick a plugin, right?
>
>
> Right. They can already pick deflate if they want to.
>
> Regards,
>
> Nigel
>
>
>
Would it be, by any chance, possible to tweak the thing so that reiserfs
plugins become kernel modules, so that the reiserfs core can be put in the
kernel without the plugins slowing down its acceptance ?
(and updating plugins without rebooting would be a nice extra)
>> The patch below is so-called reiser4 LZO compression plugin as extracted
>> from 2.6.18-rc4-mm3.
>>
>> I think it is an unauditable piece of shit and thus should not enter
>> mainline.
>
> Like lib/inflate.c (and this new code should arguably be in lib/).
>
> The problem is that if we clean this up, we've diverged very much from
> the
> upstream implementation. So taking in fixes and features from upstream
> becomes harder and more error-prone.
>
> I'd suspect that the maturity of these utilities is such that we could
> afford to turn them into kernel code in the expectation that any future
> changes will be small. But it's not a completely simple call.
>
> (iirc the inflate code had a buffer overrun a while back, which was found
> and fixed in the upstream version).
>
>
PFC wrote:
>
>
> Would it be, by any chance, possible to tweak the thing so that
> reiserfs plugins become kernel modules, so that the reiserfs core can be
> put in the kernel without the plugins slowing down its acceptance ?
I don't see what this has to do with cryptoapi plugins -- those are not
related to Reiser plugins.
As for the plugins slowing down acceptance, it's actually the concept of
plugins and the plugin API -- in other words, it's the fact that Reiser4
supports plugins -- that is slowing it down, if anything about plugins
is still an issue at all.
Making them modules would make it worse. Last I saw, Linus doesn't
particularly like the idea of plugins because of a few misconceptions,
like the possibility of proprietary (possibly GPL-violating) plugins
distributed as modules -- basically, something like what nVidia and ATI
do with their video drivers.
As it is, a good argument in favor of plugins is that this kind of thing
isn't possible -- we often put "plugins" in quotes because really, it's
just a nice abstraction layer. They aren't any more plugins than
iptables modules or cryptoapi plugins are. If anything, they're less,
because they must be compiled into Reiser4, which means either one huge
monolithic Reiser4 module (including all plugins), or everything
compiled into the kernel image.
> (and updating plugins without rebooting would be a nice extra)
It probably wouldn't be as nice as you think. Remember, if you're using
a certain plugin in your root FS, it's part of the FS, so I don't think
you'd be able to remove that plugin any more than you're able to remove
reiser4.ko if that's your root FS. You'd have to unmount every FS that
uses that plugin.
At this point, you don't really gain much -- if you unmount every last
Reiser4 filesystem, you can then remove reiser4.ko, recompile it, and
load a new one with different plugins enabled.
Also, these things would typically be part of a kernel update anyway,
meaning a reboot anyway.
But suppose you could remove a plugin, what then? What would that mean?
Suppose half your files are compressed and you remove cryptocompress
-- are those files uncompressed when the plugin goes away? Probably
not. The only smart way to handle this that I can think of is to make
those files unavailable, which is probably not what you want -- how do
you update cryptocompress when the new reiser4_cryptocompress.ko is
itself compressed?
That may be an acceptable solution for some plugins, but you'd have to
be extremely careful which ones you remove. The only safe way I can
imagine doing this may not be possible, and if it is, it's extremely
hackish -- load the plugin under another module name, so
r4_cryptocompress would be r4_cryptocompress_init -- have the module,
once loaded, do an atomic switch from the old one to the new one,
effectively in-place.
But that kind of solution is something I've never seen attempted, and
only really heard of in strange environments like Erlang. It would
probably require much more engineering than the Reiser team can handle
right now, especially with their hands full with inclusion.
>>> The patch below is so-called reiser4 LZO compression plugin as extracted
>>> from 2.6.18-rc4-mm3.
>>>
>>> I think it is an unauditable piece of shit and thus should not enter
>>> mainline.
>>
>> Like lib/inflate.c (and this new code should arguably be in lib/).
>>
>> The problem is that if we clean this up, we've diverged very much from
>> the
>> upstream implementation. So taking in fixes and features from upstream
>> becomes harder and more error-prone.
>>
>> I'd suspect that the maturity of these utilities is such that we could
>> afford to turn them into kernel code in the expectation that any future
>> changes will be small. But it's not a completely simple call.
>>
>> (iirc the inflate code had a buffer overrun a while back, which was found
>> and fixed in the upstream version).
>>
>>
>
>
Hi.
On Tue, 2006-08-29 at 15:38 +0400, Edward Shishkin wrote:
> Nigel Cunningham wrote:
> > Hi.
> >
> > On Tue, 2006-08-29 at 03:23 -0500, David Masover wrote:
> >
> >>Nigel Cunningham wrote:
> >>
> >>>Hi.
> >>>
> >>>On Tue, 2006-08-29 at 06:05 +0200, Jan Engelhardt wrote:
> >>>
> >>>>>>>>Hmm. LZO is the best compression algorithm for the task as measured by
> >>>>>>>>the objectives of good compression effectiveness while still having very
> >>>>>>>>low CPU usage (the best of those written and GPL'd, there is a slightly
> >>>>>>>>better one which is proprietary and uses more CPU, LZRW if I remember
> >>>>>>>>right. The gzip code base uses too much CPU, though I think Edward made
> >>>>>>>
> >>>>>>>I don't think that LZO beats LZF in both speed and compression ratio.
> >>>>>>>
> >>>>>>>LZF is also available under GPL (dual-licensed BSD) and was choosen in favor
> >>>>>>>of LZO for the next generation suspend-to-disk code of the Linux kernel.
> >>>>>>>
> >>>>>>>see: http://www.goof.com/pcg/marc/liblzf.html
> >>>>>>
> >>>>>>thanks for the info, we will compare them
> >>>>>
> >>>>>For Suspend2, we ended up converting the LZF support to a cryptoapi
> >>>>>plugin. Is there any chance that you could use cryptoapi modules? We
> >>>>>could then have a hope of sharing the support.
> >>>>
> >>>>I am throwing in gzip: would it be meaningful to use that instead? The
> >>>>decoder (inflate.c) is already there.
> >>>>
> >>>>06:04 shanghai:~/liblzf-1.6 > l configure*
> >>>>-rwxr-xr-x 1 jengelh users 154894 Mar 3 2005 configure
> >>>>-rwxr-xr-x 1 jengelh users 26810 Mar 3 2005 configure.bz2
> >>>>-rw-r--r-- 1 jengelh users 30611 Aug 28 20:32 configure.gz-z9
> >>>>-rw-r--r-- 1 jengelh users 30693 Aug 28 20:32 configure.gz-z6
> >>>>-rw-r--r-- 1 jengelh users 53077 Aug 28 20:32 configure.lzf
> >>>
> >>>We used gzip when we first implemented compression support, and found it
> >>>to be far too slow. Even with the fastest compression options, we were
> >>>only getting a few megabytes per second. Perhaps I did something wrong
> >>>in configuring it, but there's not that many things to get wrong!
> >>
> >>All that comes to mind is the speed/quality setting -- the number from 1
> >>to 9. Recently, I backed up someone's hard drive using -1, and I
> >>believe I was still able to saturate... the _network_. Definitely try
> >>again if you haven't changed this, but I can't imagine I'm the first
> >>persson to think of it.
> >>
> >> From what I remember, gzip -1 wasn't faster than the disk. But at
> >>least for (very) repetitive data, I was wrong:
> >>
> >>eve:~ sanity$ time bash -c 'dd if=/dev/zero of=test bs=10m count=10; sync'
> >>10+0 records in
> >>10+0 records out
> >>104857600 bytes transferred in 3.261990 secs (32145287 bytes/sec)
> >>
> >>real 0m3.746s
> >>user 0m0.005s
> >>sys 0m0.627s
> >>eve:~ sanity$ time bash -c 'dd if=/dev/zero bs=10m count=10 | gzip -v1 >
> >>test; sync'
> >>10+0 records in
> >>10+0 records out
> >>104857600 bytes transferred in 2.404093 secs (43616282 bytes/sec)
> >> 99.5%
> >>
> >>real 0m2.558s
> >>user 0m1.554s
> >>sys 0m0.680s
> >>eve:~ sanity$
> >>
> >>
> >>
> >>This was on OS X, but I think it's still valid -- this is a slightly
> >>older Powerbook, with a 5400 RPM drive, 1.6 ghz G4.
> >>
> >>-1 is still worlds better than nothing. The backup was over 15 gigs,
> >>down to about 6 -- loads of repetitive data, I'm sure, but that's where
> >>you win with compression anyway.
> >
> >
> > Wow. That's a lot better; I guess I did get something wrong in trying to
> > tune deflate. That was pre-cryptoapi though; looking at
> > cryptoapi/deflate.c, I don't see any way of controlling the compression
> > level. Am I missing anything?
> >
>
> zlib is tunable, not cryptoapi's deflate.
> look at zlib_deflateInit2()
Ok; thanks. I wasn't mistaken then :)
Regards,
Nigel