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