lzo1x_9x.c

lzo-1.08-src.zip 高效的压缩解压代码

/* lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm

   This file is 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]>
 */



#include <lzoconf.h>
#if !defined(LZO_999_UNSUPPORTED)

#if !defined(LZO1X) && !defined(LZO1Y) && !defined(LZO1Z)
#  define LZO1X
#endif

#if 0
#undef LZO_DEBUG
#define LZO_DEBUG
#endif

#include <stdio.h>
#if defined(LZO1X)
#  include "config1x.h"
#elif defined(LZO1Y)
#  include "config1y.h"
#elif defined(LZO1Z)
#  include "config1z.h"
#endif

#if 0 && !defined(LZO_DEBUG)
#undef NDEBUG
#include <assert.h>
#endif


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

#define N			M4_MAX_OFFSET	/* size of ring buffer */
#define THRESHOLD	    1			/* lower limit for match length */
#define F		     2048			/* upper limit for match length */

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

#if defined(LZO1X)
#  define LZO_COMPRESS_T				lzo1x_999_t
#  define lzo_swd_t						lzo1x_999_swd_t
#elif defined(LZO1Y)
#  define LZO_COMPRESS_T				lzo1y_999_t
#  define lzo_swd_t						lzo1y_999_swd_t
#  define lzo1x_999_compress_internal	lzo1y_999_compress_internal
#  define lzo1x_999_compress_dict		lzo1y_999_compress_dict
#  define lzo1x_999_compress_level		lzo1y_999_compress_level
#  define lzo1x_999_compress			lzo1y_999_compress
#elif defined(LZO1Z)
#  define LZO_COMPRESS_T				lzo1z_999_t
#  define lzo_swd_t						lzo1z_999_swd_t
#  define lzo1x_999_compress_internal	lzo1z_999_compress_internal
#  define lzo1x_999_compress_dict		lzo1z_999_compress_dict
#  define lzo1x_999_compress_level		lzo1z_999_compress_level
#  define lzo1x_999_compress			lzo1z_999_compress
#endif

#if 0
#  define HEAD3(b,p) \
    ((((((lzo_uint32)b[p]<<3)^b[p+1])<<3)^b[p+2]) & (SWD_HSIZE-1))
#endif
#if 0 && defined(LZO_UNALIGNED_OK_4) && (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
#  define HEAD3(b,p) \
    (((* (lzo_uint32p) &b[p]) ^ ((* (lzo_uint32p) &b[p])>>10)) & (SWD_HSIZE-1))
#endif

#include "lzo_mchw.ch"


/* this is a public functions, but there is no prototype in a header file */
LZO_EXTERN(int)
lzo1x_999_compress_internal ( const lzo_byte *in , lzo_uint  in_len,
                                    lzo_byte *out, lzo_uintp out_len,
                                    lzo_voidp wrkmem,
                              const lzo_byte *dict, lzo_uint dict_len,
                                    lzo_progress_callback_t cb,
                                    int try_lazy,
                                    lzo_uint good_length,
                                    lzo_uint max_lazy,
                                    lzo_uint nice_length,
                                    lzo_uint max_chain,
                                    lzo_uint32 flags );


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

static lzo_byte *
code_match ( LZO_COMPRESS_T *c, lzo_byte *op, lzo_uint m_len, lzo_uint m_off )
{
	lzo_uint x_len = m_len;
	lzo_uint x_off = m_off;

	c->match_bytes += m_len;

#if 0
/*
	static lzo_uint last_m_len = 0, last_m_off = 0;
	static lzo_uint prev_m_off[4];
	static int prev_m_off_ptr = 0;
	int i;

	//if (m_len >= 3 && m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
	if (m_len >= 3 && m_len <= M2_MAX_LEN)
	{
	//if (m_len == last_m_len && m_off == last_m_off)
		//printf("last_m_len + last_m_off\n");
	//else
	if (m_off == last_m_off)
		printf("last_m_off\n");
	else
	{
		for (i = 0; i < 4; i++)
			if (m_off == prev_m_off[i])
				printf("prev_m_off %d: %5ld\n",i,(long)m_off);
	}
	}
	last_m_len = m_len;
	last_m_off = prev_m_off[prev_m_off_ptr] = m_off;
	prev_m_off_ptr = (prev_m_off_ptr + 1) & 3;
*/
#endif

	assert(op > c->out);
	if (m_len == 2)
	{
		assert(m_off <= M1_MAX_OFFSET);
		assert(c->r1_lit > 0); assert(c->r1_lit < 4);
		m_off -= 1;
#if defined(LZO1Z)
		*op++ = LZO_BYTE(M1_MARKER | (m_off >> 6));
		*op++ = LZO_BYTE(m_off << 2);
#else
		*op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
		*op++ = LZO_BYTE(m_off >> 2);
#endif
		c->m1a_m++;
	}
#if defined(LZO1Z)
	else if (m_len <= M2_MAX_LEN && (m_off <= M2_MAX_OFFSET || m_off == c->last_m_off))
#else
	else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
#endif
	{
		assert(m_len >= 3);
#if defined(LZO1X)
		m_off -= 1;
		*op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
		*op++ = LZO_BYTE(m_off >> 3);
		assert(op[-2] >= M2_MARKER);
#elif defined(LZO1Y)
		m_off -= 1;
		*op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
		*op++ = LZO_BYTE(m_off >> 2);
		assert(op[-2] >= M2_MARKER);
#elif defined(LZO1Z)
		if (m_off == c->last_m_off)
			*op++ = LZO_BYTE(((m_len - 1) << 5) | (0x700 >> 6));
		else
		{
			m_off -= 1;
			*op++ = LZO_BYTE(((m_len - 1) << 5) | (m_off >> 6));
			*op++ = LZO_BYTE(m_off << 2);
		}
#endif
		c->m2_m++;
	}
	else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4)
	{
		assert(m_len == 3);
		assert(m_off > M2_MAX_OFFSET);
		m_off -= 1 + M2_MAX_OFFSET;
#if defined(LZO1Z)
		*op++ = LZO_BYTE(M1_MARKER | (m_off >> 6));
		*op++ = LZO_BYTE(m_off << 2);
#else
		*op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
		*op++ = LZO_BYTE(m_off >> 2);
#endif
		c->m1b_m++;
	}
	else if (m_off <= M3_MAX_OFFSET)
	{
		assert(m_len >= 3);
		m_off -= 1;
		if (m_len <= M3_MAX_LEN)
			*op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
		else
		{
			m_len -= M3_MAX_LEN;
			*op++ = M3_MARKER | 0;
			while (m_len > 255)
			{
				m_len -= 255;
				*op++ = 0;
			}
			assert(m_len > 0);
			*op++ = LZO_BYTE(m_len);
		}
#if defined(LZO1Z)
		*op++ = LZO_BYTE(m_off >> 6);
		*op++ = LZO_BYTE(m_off << 2);
#else
		*op++ = LZO_BYTE(m_off << 2);
		*op++ = LZO_BYTE(m_off >> 6);
#endif
		c->m3_m++;
	}
	else
	{
		lzo_uint k;

		assert(m_len >= 3);
		assert(m_off > 0x4000); assert(m_off <= 0xbfff);
		m_off -= 0x4000;
		k = (m_off & 0x4000) >> 11;
		if (m_len <= M4_MAX_LEN)
			*op++ = LZO_BYTE(M4_MARKER | k | (m_len - 2));
		else
		{
			m_len -= M4_MAX_LEN;
			*op++ = LZO_BYTE(M4_MARKER | k | 0);
			while (m_len > 255)
			{
				m_len -= 255;
				*op++ = 0;
			}
			assert(m_len > 0);
			*op++ = LZO_BYTE(m_len);
		}
#if defined(LZO1Z)
		*op++ = LZO_BYTE(m_off >> 6);
		*op++ = LZO_BYTE(m_off << 2);
#else
		*op++ = LZO_BYTE(m_off << 2);
		*op++ = LZO_BYTE(m_off >> 6);
#endif
		c->m4_m++;
	}

	c->last_m_len = x_len;
	c->last_m_off = x_off;
	return op;
}


static lzo_byte *
STORE_RUN ( LZO_COMPRESS_T *c, lzo_byte *op, const lzo_byte *ii, lzo_uint t )
{
	c->lit_bytes += t;

	if (op == c->out && t <= 238)
	{
		*op++ = LZO_BYTE(17 + t);
	}
	else if (t <= 3)
	{
#if defined(LZO1Z)
		op[-1] |= LZO_BYTE(t);
#else
		op[-2] |= LZO_BYTE(t);
#endif
		c->lit1_r++;
	}
	else if (t <= 18)
	{
		*op++ = LZO_BYTE(t - 3);
		c->lit2_r++;
	}
	else
	{
		lzo_uint tt = t - 18;

		*op++ = 0;
		while (tt > 255)
		{
			tt -= 255;
			*op++ = 0;
		}
		assert(tt > 0);
		*op++ = LZO_BYTE(tt);
		c->lit3_r++;
	}
	do *op++ = *ii++; while (--t > 0);

	return op;
}


static lzo_byte *
code_run ( LZO_COMPRESS_T *c, lzo_byte *op, const lzo_byte *ii,
           lzo_uint lit, lzo_uint m_len )
{
	if (lit > 0)
	{
		assert(m_len >= 2);
		op = STORE_RUN(c,op,ii,lit);
		c->r1_m_len = m_len;
		c->r1_lit = lit;
	}
	else
	{
		assert(m_len >= 3);
		c->r1_m_len = 0;
		c->r1_lit = 0;
	}

	return op;
}


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

static int
len_of_coded_match ( lzo_uint m_len, lzo_uint m_off, lzo_uint lit )
{
	int n = 4;

	if (m_len < 2)
		return -1;
	if (m_len == 2)
		return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
	if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
		return 2;
	if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
		return 2;
	if (m_off <= M3_MAX_OFFSET)
	{
		if (m_len <= M3_MAX_LEN)
			return 3;
		m_len -= M3_MAX_LEN;
		while (m_len > 255)
		{
			m_len -= 255;
			n++;
		}
		return n;
	}
	if (m_off <= M4_MAX_OFFSET)
	{
		if (m_len <= M4_MAX_LEN)
			return 3;
		m_len -= M4_MAX_LEN;
		while (m_len > 255)
		{
			m_len -= 255;
			n++;
		}
		return n;
	}
	return -1;
}


static lzo_int
min_gain(lzo_uint ahead, lzo_uint lit1, lzo_uint lit2, int l1, int l2, int l3)
{
	lzo_int lazy_match_min_gain = 0;

	assert (ahead >= 1);
	lazy_match_min_gain += ahead;

#if 0
	if (l3 > 0)
		lit2 -= ahead;
#endif

	if (lit1 <= 3)
		lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
	else if (lit1 <= 18)
		lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;

	lazy_match_min_gain += (l2 - l1) * 2;
	if (l3 > 0)
		lazy_match_min_gain -= (ahead - l3) * 2;

	if (lazy_match_min_gain < 0)
		lazy_match_min_gain = 0;

#if 0
	if (l1 == 2)
		if (lazy_match_min_gain == 0)
			lazy_match_min_gain = 1;
#endif

	return lazy_match_min_gain;
}


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

#if !defined(NDEBUG)
static
void assert_match( const lzo_swd_t *swd, lzo_uint m_len, lzo_uint m_off )
{
	const LZO_COMPRESS_T *c = swd->c;
	lzo_uint d_off;

	assert(m_len >= 2);
	if (m_off <= (lzo_uint) (c->bp - c->in))
	{
		assert(c->bp - m_off + m_len < c->ip);
		assert(lzo_memcmp(c->bp, c->bp - m_off, m_len) == 0);
	}
	else
	{
		assert(swd->dict != NULL);
		d_off = m_off - (lzo_uint) (c->bp - c->in);