lzo1x_9x.c

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

		assert(d_off <= swd->dict_len);
		if (m_len > d_off)
		{
			assert(lzo_memcmp(c->bp, swd->dict_end - d_off, d_off) == 0);
			assert(c->in + m_len - d_off < c->ip);
			assert(lzo_memcmp(c->bp + d_off, c->in, m_len - d_off) == 0);
		}
		else
		{
			assert(lzo_memcmp(c->bp, swd->dict_end - d_off, m_len) == 0);
		}
	}
}
#else
#  define assert_match(a,b,c)	((void)0)
#endif


#if defined(SWD_BEST_OFF)

static void
better_match ( const lzo_swd_t *swd, lzo_uint *m_len, lzo_uint *m_off )
{
#if defined(LZO1Z)
	const LZO_COMPRESS_T *c = swd->c;
#endif

	if (*m_len <= M2_MIN_LEN)
		return;
#if defined(LZO1Z)
	if (*m_off == c->last_m_off && *m_len <= M2_MAX_LEN)
		return;
#if 1
	if (*m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 &&
		c->last_m_off && swd->best_off[*m_len-1] == c->last_m_off)
	{
		*m_len = *m_len - 1;
		*m_off = swd->best_off[*m_len];
		return;
	}
#endif
#endif

	if (*m_off <= M2_MAX_OFFSET)
		return;

#if 1
	/* M3/M4 -> M2 */
	if (*m_off > M2_MAX_OFFSET &&
	    *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 &&
	    swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET)
	{
		*m_len = *m_len - 1;
		*m_off = swd->best_off[*m_len];
		return;
	}
#endif

#if 1
	/* M4 -> M2 */
	if (*m_off > M3_MAX_OFFSET &&
	    *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2 &&
	    swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET)
	{
		*m_len = *m_len - 2;
		*m_off = swd->best_off[*m_len];
		return;
	}
#endif

#if 1
	/* M4 -> M3 */
	if (*m_off > M3_MAX_OFFSET &&
	    *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1 &&
	    swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET)
	{
		*m_len = *m_len - 1;
		*m_off = swd->best_off[*m_len];
	}
#endif
}

#endif


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

LZO_PUBLIC(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 )
{
	lzo_byte *op;
	const lzo_byte *ii;
	lzo_uint lit;
	lzo_uint m_len, m_off;
	LZO_COMPRESS_T cc;
	LZO_COMPRESS_T * const c = &cc;
	lzo_swd_t * const swd = (lzo_swd_t *) wrkmem;
	int r;

#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,1,lzo_sizeof(lzo_swd_t));
#endif

	/* sanity check */
	if (!lzo_assert(LZO1X_999_MEM_COMPRESS >= lzo_sizeof(lzo_swd_t)))
		return LZO_E_ERROR;

/* setup parameter defaults */
	/* number of lazy match tries */
	if (try_lazy < 0)
		try_lazy = 1;
	/* reduce lazy match search if we already have a match with this length */
	if (good_length <= 0)
		good_length = 32;
	/* do not try a lazy match if we already have a match with this length */
	if (max_lazy <= 0)
		max_lazy = 32;
	/* stop searching for longer matches than this one */
	if (nice_length <= 0)
		nice_length = 0;
	/* don't search more positions than this */
	if (max_chain <= 0)
		max_chain = SWD_MAX_CHAIN;

	c->init = 0;
	c->ip = c->in = in;
	c->in_end = in + in_len;
	c->out = out;
	c->cb = cb;
	c->m1a_m = c->m1b_m = c->m2_m = c->m3_m = c->m4_m = 0;
	c->lit1_r = c->lit2_r = c->lit3_r = 0;

	op = out;
	ii = c->ip;				/* point to start of literal run */
	lit = 0;
	c->r1_lit = c->r1_m_len = 0;

	r = init_match(c,swd,dict,dict_len,flags);
	if (r != 0)
		return r;
	if (max_chain > 0)
		swd->max_chain = max_chain;
	if (nice_length > 0)
		swd->nice_length = nice_length;

	r = find_match(c,swd,0,0);
	if (r != 0)
		return r;
	while (c->look > 0)
	{
		lzo_uint ahead;
		lzo_uint max_ahead;
		int l1, l2, l3;

		c->codesize = op - out;

		m_len = c->m_len;
		m_off = c->m_off;

		assert(c->bp == c->ip - c->look);
		assert(c->bp >= in);
		if (lit == 0)
			ii = c->bp;
		assert(ii + lit == c->bp);
		assert(swd->b_char == *(c->bp));

		if ( m_len < 2 ||
		    (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4)) ||
#if 1
			/* Do not accept this match for compressed-data compatibility
			 * with LZO v1.01 and before
			 * [ might be a problem for decompress() and optimize() ]
			 */
		    (m_len == 2 && op == out) ||
#endif
			(op == out && lit == 0))
		{
			/* a literal */
			m_len = 0;
		}
		else if (m_len == M2_MIN_LEN)
		{
			/* compression ratio improves if we code a literal in some cases */
			if (m_off > MX_MAX_OFFSET && lit >= 4)
				m_len = 0;
		}

		if (m_len == 0)
		{
	/* a literal */
			lit++;
			swd->max_chain = max_chain;
			r = find_match(c,swd,1,0);
			assert(r == 0);
			continue;
		}

	/* a match */
#if defined(SWD_BEST_OFF)
		if (swd->use_best_off)
			better_match(swd,&m_len,&m_off);
#endif
		assert_match(swd,m_len,m_off);



		/* shall we try a lazy match ? */
		ahead = 0;
		if (try_lazy <= 0 || m_len >= max_lazy)
		{
			/* no */
			l1 = 0;
			max_ahead = 0;
		}
		else
		{
			/* yes, try a lazy match */
			l1 = len_of_coded_match(m_len,m_off,lit);
			assert(l1 > 0);
#if 1
			max_ahead = LZO_MIN(try_lazy, l1 - 1);
#else
			max_ahead = LZO_MIN3(try_lazy, l1, m_len - 1);
#endif
		}


		while (ahead < max_ahead && c->look > m_len)
		{
			lzo_int lazy_match_min_gain;

			if (m_len >= good_length)
				swd->max_chain = max_chain >> 2;
			else
				swd->max_chain = max_chain;
			r = find_match(c,swd,1,0);
			ahead++;

			assert(r == 0);
			assert(c->look > 0);
			assert(ii + lit + ahead == c->bp);

#if defined(LZO1Z)
			if (m_off == c->last_m_off && c->m_off != c->last_m_off)
				if (m_len >= M2_MIN_LEN && m_len <= M2_MAX_LEN)
					c->m_len = 0;
#endif
			if (c->m_len < m_len)
				continue;
#if 1
			if (c->m_len == m_len && c->m_off >= m_off)
				continue;
#endif
#if defined(SWD_BEST_OFF)
			if (swd->use_best_off)
				better_match(swd,&c->m_len,&c->m_off);
#endif
			l2 = len_of_coded_match(c->m_len,c->m_off,lit+ahead);
			if (l2 < 0)
				continue;
#if 0
			if (c->m_len == m_len && l2 >= l1)
				continue;
#endif


#if 1
			/* compressed-data compatibility [see above] */
			l3 = (op == out) ? -1 : len_of_coded_match(ahead,m_off,lit);
#else
			l3 = len_of_coded_match(ahead,m_off,lit);
#endif

			lazy_match_min_gain = min_gain(ahead,lit,lit+ahead,l1,l2,l3);
			if (c->m_len >= m_len + lazy_match_min_gain)
			{
				c->lazy++;
				assert_match(swd,c->m_len,c->m_off);

				if (l3 > 0)
				{
					/* code previous run */
					op = code_run(c,op,ii,lit,ahead);
					lit = 0;
					/* code shortened match */
					op = code_match(c,op,ahead,m_off);
				}
				else
				{
					lit += ahead;
					assert(ii + lit == c->bp);
				}
				goto lazy_match_done;
			}
		}


		assert(ii + lit + ahead == c->bp);

		/* 1 - code run */
		op = code_run(c,op,ii,lit,m_len);
		lit = 0;

		/* 2 - code match */
		op = code_match(c,op,m_len,m_off);
		swd->max_chain = max_chain;
		r = find_match(c,swd,m_len,1+ahead);
		assert(r == 0);

lazy_match_done: ;
	}


	/* store final run */
	if (lit > 0)
		op = STORE_RUN(c,op,ii,lit);

#if defined(LZO_EOF_CODE)
	*op++ = M4_MARKER | 1;
	*op++ = 0;
	*op++ = 0;
#endif

	c->codesize = op - out;
	assert(c->textsize == in_len);

	*out_len = op - out;

	if (c->cb)
		(*c->cb)(c->textsize,c->codesize);

#if 0
	printf("%ld %ld -> %ld  %ld: %ld %ld %ld %ld %ld  %ld: %ld %ld %ld  %ld\n",
		(long) c->textsize, (long) in_len, (long) c->codesize,
		c->match_bytes, c->m1a_m, c->m1b_m, c->m2_m, c->m3_m, c->m4_m,
		c->lit_bytes, c->lit1_r, c->lit2_r, c->lit3_r, c->lazy);
#endif
	assert(c->lit_bytes + c->match_bytes == in_len);

	return LZO_E_OK;
}


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

LZO_PUBLIC(int)
lzo1x_999_compress_level    ( 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 compression_level )
{
	static const struct
	{
		int try_lazy;
		lzo_uint good_length;
		lzo_uint max_lazy;
		lzo_uint nice_length;
		lzo_uint max_chain;
		lzo_uint32 flags;
	} c[9] = {
		{   0,   0,   0,   8,    4,   0 },		/* faster compression */
		{   0,   0,   0,  16,    8,   0 },
		{   0,   0,   0,  32,   16,   0 },

		{   1,   4,   4,  16,   16,   0 },
		{   1,   8,  16,  32,   32,   0 },
		{   1,   8,  16, 128,  128,   0 },

		{   2,   8,  32, 128,  256,   0 },
		{   2,  32, 128,   F, 2048,   1 },
		{   2,   F,   F,   F, 4096,   1 }		/* max. compression */
	};

	if (compression_level < 1 || compression_level > 9)
		return LZO_E_ERROR;

	compression_level -= 1;
	return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
	                                   dict, dict_len, cb,
	                                   c[compression_level].try_lazy,
	                                   c[compression_level].good_length,
	                                   c[compression_level].max_lazy,
#if 0
	                                   c[compression_level].nice_length,
#else
	                                   0,
#endif
	                                   c[compression_level].max_chain,
	                                   c[compression_level].flags);
}


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

LZO_PUBLIC(int)
lzo1x_999_compress_dict     ( 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 )
{
	return lzo1x_999_compress_level(in, in_len, out, out_len, wrkmem,
	                                dict, dict_len, 0, 8);
}

LZO_PUBLIC(int)
lzo1x_999_compress  ( const lzo_byte *in , lzo_uint  in_len,
                            lzo_byte *out, lzo_uintp out_len,
                            lzo_voidp wrkmem )
{
	return lzo1x_999_compress_level(in, in_len, out, out_len, wrkmem,
	                                NULL, 0, 0, 8);
}


#endif /* !defined(LZO_999_UNSUPPORTED) */

/*
vi:ts=4:et
*/