compr_lzo.c

jffs2源代码基于2。6内核

/*
 * JFFS2 -- Journalling Flash File System, Version 2.
 *
 * Copyright (C) 2004 Patrik Kluba,
 *                    University of Szeged, Hungary
 *
 * For licensing information, see the file 'LICENCE' in the
 * jffs2 directory.
 *
 * $Id: compr_lzo.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
 *
 */

/*
   LZO1X-1 (and -999) compression module for jffs2
   based on the original LZO sources
*/

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */

/*
   Original copyright notice follows:

   lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
   lzo_ptr.h -- low-level pointer constructs
   lzo_swd.ch -- sliding window dictionary
   lzoconf.h -- configuration for the LZO real-time data compression library
   lzo_mchw.ch -- matching functions using a window
   minilzo.c -- mini subset of the LZO real-time data compression library
   config1x.h -- configuration for the LZO1X algorithm
   lzo1x.h -- public interface of the LZO1X compression algorithm

   These files are part of the LZO real-time data compression library.

   Copyright (C) 1996-2002 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
   <[e-mail]>
*/

/*

	2004-02-16  pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
				Initial release
					-removed all 16 bit code
					-all sensitive data will be on 4 byte boundary
					-removed check parts for library use
					-removed all but LZO1X-* compression
					
*/

#ifndef __KERNEL__
  #include <sys/types.h>
  #include <stddef.h>
  #include <string.h>
  #include <limits.h>
#else
  #include <linux/kernel.h>
  #include <linux/types.h>
  #include <linux/stddef.h>
  #include <linux/string.h>
  #define USHRT_MAX     65535
  /* #define UINT_MAX      4294967295U */
#endif

/* data type definitions */
#define U32 unsigned long
#define S32 signed long
#define I32 long
#define U16 unsigned short
#define S16 signed short
#define I16 short
#define U8 unsigned char
#define S8 signed char
#define I8 char

/*************************************/

/* lzo_swd.ch */

#define SWD_N				N
#define SWD_F				F
#define SWD_THRESHOLD		THRESHOLD

/* shortest unsigned int that 2 * SWD_F + SWD_N (currently 53248) fits in */
typedef unsigned short swd_uint;
/* upper limit of that data type */
#define SWD_UINT_MAX	USHRT_MAX

/* minilzo.c */

#define LZO_VERSION_DATE	"Jul 12 2002"
#define LZO_VERSION_STRING	"1.08"
#define LZO_VERSION			0x1080

/* lzo_ptr.h */

/* Integral types that have *exactly* the same number of bits as a lzo_voidp */
typedef unsigned long lzo_ptr_t;
typedef long lzo_sptr_t;


/*************************************/

/* config1x.h */

#define M1_MAX_OFFSET	0x0400
#define M2_MAX_OFFSET	0x0800
#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
#define M2_MAX_LEN		8
#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

#define MIN_LOOKAHEAD		(M2_MAX_LEN + 1)

/* minilzo.c */

#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)))

#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)

#define lzo_dict_t    const lzo_bytep
#define lzo_dict_p    lzo_dict_t *
#define lzo_moff_t    lzo_uint

#define MEMCPY8_DS(dest,src,len) \
    memcpy(dest,src,len); \
    dest += len; \
    src += len

#define MEMCPY_DS(dest,src,len) \
    do *dest++ = *src++; \
    while (--len > 0)

#define MEMMOVE_DS(dest,src,len) \
    do *dest++ = *src++; \
    while (--len > 0)

#define BZERO8_PTR(s,l,n)   memset((s),0,(lzo_uint)(l)*(n))

#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)

#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)

#define LZO_HASH            LZO_HASH_LZO_INCREMENTAL_B

#define DL_MIN_LEN          M2_MIN_LEN

#define D_SIZE        LZO_SIZE(D_BITS)
#define D_MASK        LZO_MASK(D_BITS)

#define D_HIGH        ((D_MASK >> 1) + 1)

#define DINDEX1             D_INDEX1
#define DINDEX2             D_INDEX2

#define DX2(p,s1,s2) \
	(((((lzo_uint32)((p)[2]) << (s2)) ^ (p)[1]) << (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)

#define DENTRY(p,in)                          (p)
#define GINDEX(m_pos,m_off,dict,dindex,in)    m_pos = dict[dindex]

#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) ))

#define BOUNDS_CHECKING_OFF_IN_EXPR(expr)     (expr)

#define DD_BITS			0
#define DD_SIZE         LZO_SIZE(DD_BITS)
#define DD_MASK         LZO_MASK(DD_BITS)

#define DL_BITS        (D_BITS - DD_BITS)
#define DL_SIZE        LZO_SIZE(DL_BITS)
#define DL_MASK        LZO_MASK(DL_BITS)

#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)

#define __COPY4(dst,src)  * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
#define COPY4(dst,src)	__COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src))

#define TEST_IP         (ip < ip_end)
#define TEST_OP         (op <= op_end)

#define NEED_IP(x) \
            if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x))  goto input_overrun
#define NEED_OP(x) \
            if ((lzo_uint)(op_end - op) < (lzo_uint)(x))  goto output_overrun
#define TEST_LOOKBEHIND(m_pos,out)    if (m_pos < out) goto lookbehind_overrun

/* lzo1x_9x.c */

#define LZO_UINT_MAX	UINT_MAX
#define N			M4_MAX_OFFSET
#define THRESHOLD	    1
#define F		     2048

#define SWD_BEST_OFF	(LZO_MAX3( M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN ) + 1)

/* ../include/lzoconf.h */

typedef U32 lzo_uint32;
typedef I32 lzo_int32;
typedef U32 lzo_uint;
typedef I32 lzo_int;
typedef int lzo_bool;

#define lzo_byte                U8
#define lzo_bytep               U8 *
#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_voidpp              lzo_voidp *
#define lzo_bytepp              lzo_bytep *
#define lzo_sizeof_dict_t		sizeof(lzo_bytep)

#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)

#define LZO_PTR_ALIGN_UP(_ptr,_size) \
   ((_ptr) + (lzo_uint) __lzo_align_gap((const lzo_voidp)(_ptr),(lzo_uint)(_size)))
#define LZO_ALIGN(_ptr,_size) LZO_PTR_ALIGN_UP(_ptr,_size)

typedef int
	(*lzo_compress_t) (const lzo_byte * src, lzo_uint src_len,
			   lzo_byte * dst, lzo_uintp dst_len,
			   lzo_voidp wrkmem);

typedef int
	(*lzo_decompress_t) (const lzo_byte * src, lzo_uint src_len,
			     lzo_byte * dst, lzo_uintp dst_len,
			     lzo_voidp wrkmem);

typedef int
	(*lzo_optimize_t) (lzo_byte * src, lzo_uint src_len,
			   lzo_byte * dst, lzo_uintp dst_len,
			   lzo_voidp wrkmem);

typedef int
	(*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_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);

typedef int
	(*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_decompress_asm_t) (const lzo_byte * src, lzo_uint src_len,
				 lzo_byte * dst, lzo_uintp dst_len,
				 lzo_voidp wrkmem);

typedef void (*lzo_progress_callback_t) (lzo_uint, lzo_uint);

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;

/* lzo1x.h */

#define LZO1X_1_MEM_COMPRESS    ((lzo_uint32) (16384L * lzo_sizeof_dict_t))
#define LZO1X_999_MEM_COMPRESS  ((lzo_uint32) (14 * 16384L * sizeof(short)))

/* lzo_ptr.h */

#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)
#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 ptrdiff_t lzo_ptrdiff_t;

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;

/* lzo_mchw.ch */

typedef struct
{
	int init;

	lzo_uint look;

	lzo_uint m_len;
	lzo_uint m_off;

	lzo_uint last_m_len;
	lzo_uint last_m_off;

	const lzo_byte *bp;
	const lzo_byte *ip;
	const lzo_byte *in;
	const lzo_byte *in_end;
	lzo_byte *out;

	lzo_progress_callback_t cb;

	lzo_uint textsize;
	lzo_uint codesize;
	lzo_uint printcount;

	unsigned long lit_bytes;
	unsigned long match_bytes;
	unsigned long rep_bytes;
	unsigned long lazy;

	lzo_uint r1_lit;
	lzo_uint r1_m_len;

	unsigned long m1a_m, m1b_m, m2_m, m3_m, m4_m;
	unsigned long lit1_r, lit2_r, lit3_r;
}
lzo1x_999_t;

#define getbyte(c) 	((c).ip < (c).in_end ? *((c).ip)++ : (-1))

/* lzo_swd.ch */

#define SWD_UINT(x)			((swd_uint)(x))
#define SWD_HSIZE			16384
#define SWD_MAX_CHAIN		2048
#define HEAD3(b,p) \
	(((0x9f5f*(((((lzo_uint32)b[p]<<5)^b[p+1])<<5)^b[p+2]))>>5) & (SWD_HSIZE-1))
#define HEAD2(b,p)      (b[p] ^ ((unsigned)b[p+1]<<8))
#define NIL2				SWD_UINT_MAX

typedef struct
{
	lzo_uint n;
	lzo_uint f;
	lzo_uint threshold;

	lzo_uint max_chain;
	lzo_uint nice_length;
	lzo_bool use_best_off;
	lzo_uint lazy_insert;

	lzo_uint m_len;
	lzo_uint m_off;
	lzo_uint look;
	int b_char;

	lzo_uint best_off[SWD_BEST_OFF];

	lzo1x_999_t *c;
	lzo_uint m_pos;

	lzo_uint best_pos[SWD_BEST_OFF];

	const lzo_byte *dict;
	const lzo_byte *dict_end;
	lzo_uint dict_len;

	lzo_uint ip;
	lzo_uint bp;
	lzo_uint rp;
	lzo_uint b_size;

	unsigned char *b_wrap;

	lzo_uint node_count;
	lzo_uint first_rp;

	unsigned char b[SWD_N + SWD_F + SWD_F];
	swd_uint head3[SWD_HSIZE];
	swd_uint succ3[SWD_N + SWD_F];
	swd_uint best3[SWD_N + SWD_F];
	swd_uint llen3[SWD_HSIZE];

	swd_uint head2[65536L];
}
lzo1x_999_swd_t;

#define s_head3(s,key)		s->head3[key]
#define swd_pos2off(s,pos) \
	(s->bp > (pos) ? s->bp - (pos) : s->b_size - ((pos) - s->bp))

static __inline__ void
swd_getbyte (lzo1x_999_swd_t * s)
{
	int c;

	if ((c = getbyte (*(s->c))) < 0)
	{
		if (s->look > 0)
			--s->look;
	}
	else
	{
		s->b[s->ip] = LZO_BYTE (c);
		if (s->ip < s->f)
			s->b_wrap[s->ip] = LZO_BYTE (c);
	}
	if (++s->ip == s->b_size)
		s->ip = 0;
	if (++s->bp == s->b_size)
		s->bp = 0;
	if (++s->rp == s->b_size)
		s->rp = 0;
}

static void
swd_initdict (lzo1x_999_swd_t * s, const lzo_byte * dict, lzo_uint dict_len)
{
	s->dict = s->dict_end = NULL;
	s->dict_len = 0;

	if (!dict || dict_len <= 0)
		return;
	if (dict_len > s->n)
	{
		dict += dict_len - s->n;
		dict_len = s->n;
	}

	s->dict = dict;
	s->dict_len = dict_len;
	s->dict_end = dict + dict_len;
	memcpy (s->b, dict, dict_len);
	s->ip = dict_len;
}

static void
swd_insertdict (lzo1x_999_swd_t * s, lzo_uint node, lzo_uint len)
{
	lzo_uint key;

	s->node_count = s->n - len;
	s->first_rp = node;