lzo1x_oo.ch

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

/* lzo1x_oo.ch -- LZO1X compressed data optimizer

   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 <stdio.h>
#if 0
#undef NDEBUG
#include <assert.h>
#endif

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

#define NO_LIT		LZO_UINT_MAX


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

static void copy2(lzo_byte *ip, const lzo_byte *m_pos, lzo_ptrdiff_t off)
{
	assert(off > 0);
	ip[0] = m_pos[0];
	if (off == 1)
		ip[1] = m_pos[0];
	else
		ip[1] = m_pos[1];
}


static void copy3(lzo_byte *ip, const lzo_byte *m_pos, lzo_ptrdiff_t off)
{
	assert(off > 0);
	ip[0] = m_pos[0];
	if (off == 1)
	{
		ip[2] = ip[1] = m_pos[0];
	}
	else if (off == 2)
	{
		ip[1] = m_pos[1];
		ip[2] = m_pos[0];
	}
	else
	{
		ip[1] = m_pos[1];
		ip[2] = m_pos[2];
	}
}


/***********************************************************************
// optimize a block of data.
************************************************************************/

LZO_PUBLIC(int)
DO_OPTIMIZE          (       lzo_byte *in , lzo_uint  in_len,
                             lzo_byte *out, lzo_uintp out_len,
                             lzo_voidp wrkmem )
{
	lzo_byte *op;
	lzo_byte *ip;
	lzo_uint t;
	lzo_byte *m_pos;
	lzo_byte * const ip_end = in + in_len;
	lzo_byte * const op_end = out + *out_len;
	lzo_byte *litp = NULL;
	lzo_uint lit = 0;
	lzo_uint next_lit = NO_LIT;
	lzo_uint nl;
	long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0;

	LZO_UNUSED(wrkmem);

#if defined(__LZO_QUERY_OPTIMIZE)
	if (__LZO_IS_OPTIMIZE_QUERY(in,in_len,out,out_len,wrkmem))
		return __LZO_QUERY_OPTIMIZE(in,in_len,out,out_len,wrkmem,0,0);
#endif

	*out_len = 0;

	op = out;
	ip = in;

	assert(in_len >= 3);
	if (*ip > 17)
	{
		t = *ip++ - 17;
		if (t < 4)
			goto match_next;
		goto first_literal_run;
	}
	assert(*ip < 16 || (*ip == 17 && in_len == 3));

	while (TEST_IP && TEST_OP)
	{
		t = *ip++;
		if (t >= 16)
			goto match;
		/* a literal run */
		litp = ip - 1;
		if (t == 0)
		{
			t = 15;
			while (*ip == 0)
				t += 255, ip++;
			t += *ip++;
		}
		lit = t + 3;
		/* copy literals */
copy_literal_run:
		*op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
first_literal_run:
		do *op++ = *ip++; while (--t > 0);


		t = *ip++;

		if (t >= 16)
			goto match;
#if defined(LZO1X)
		m_pos = op - 1 - 0x800;
#elif defined(LZO1Y)
		m_pos = op - 1 - 0x400;
#endif
		m_pos -= t >> 2;
		m_pos -= *ip++ << 2;
		*op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
		lit = 0;
		goto match_done;


		/* handle matches */
		while (TEST_IP && TEST_OP)
		{
			if (t < 16)						/* a M1 match */
			{
				m_pos = op - 1;
				m_pos -= t >> 2;
				m_pos -= *ip++ << 2;

				if (litp == NULL)
					goto copy_m1;

				/* assert that there was a match just before */
				assert(lit >= 1 && lit <= 3);
				assert(litp == ip - 2 - lit - 2);
				assert((lzo_uint)(*litp & 3) == lit);
				nl = ip[-2] & 3;
				/* test if a match follows */
				if (nl == 0 && lit == 1 && ip[0] >= 16)
				{
					next_lit = nl;
					/* adjust length of previous short run */
					lit += 2;
					*litp = LZO_BYTE((*litp & ~3) | lit);
					/* copy over the 2 literals that replace the match */
					copy2(ip-2,m_pos,op-m_pos);
					o_m1_a++;
				}
				/* test if a literal run follows */
				else if (nl == 0 && ip[0] < 16 && ip[0] != 0 &&
						 (lit + 2 + ip[0] < 16))
				{
					t = *ip++;
					/* remove short run */
					*litp &= ~3;
					/* copy over the 2 literals that replace the match */
					copy2(ip-3+1,m_pos,op-m_pos);
					/* move literals 1 byte ahead */
					litp += 2;
					if (lit > 0)
						lzo_memmove(litp+1,litp,lit);
					/* insert new length of long literal run */
					lit += 2 + t + 3; assert(lit <= 18);
					*litp = LZO_BYTE(lit - 3);

					o_m1_b++;
					*op++ = *m_pos++; *op++ = *m_pos++;
					goto copy_literal_run;
				}
copy_m1:
				*op++ = *m_pos++; *op++ = *m_pos++;
			}
			else
			{
match:
				if (t >= 64)				/* a M2 match */
				{
					m_pos = op - 1;
#if defined(LZO1X)
					m_pos -= (t >> 2) & 7;
					m_pos -= *ip++ << 3;
					t = (t >> 5) - 1;
#elif defined(LZO1Y)
					m_pos -= (t >> 2) & 3;
					m_pos -= *ip++ << 2;
					t = (t >> 4) - 3;
#endif
					if (litp == NULL)
						goto copy_m;

					nl = ip[-2] & 3;
					/* test if in beetween two long literal runs */
					if (t == 1 && lit > 3 && nl == 0 &&
					    ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
					{
						assert(*litp == lit - 3);
						t = *ip++;
						/* copy over the 3 literals that replace the match */
						copy3(ip-1-2,m_pos,op-m_pos);
						/* set new length of previous literal run */
						lit += 3 + t + 3; assert(lit <= 18);
						*litp = LZO_BYTE(lit - 3);
						o_m2++;
						*op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
						goto copy_literal_run;
					}
				}
				else
				{
					if (t >= 32)			/* a M3 match */
					{
						t &= 31;
						if (t == 0)
						{
							t = 31;
							while (*ip == 0)
								t += 255, ip++;
							t += *ip++;
						}
						m_pos = op - 1;
						m_pos -= *ip++ >> 2;
						m_pos -= *ip++ << 6;
					}
					else					/* a M4 match */
					{
						m_pos = op;
						m_pos -= (t & 8) << 11;
						t &= 7;
						if (t == 0)
						{
							t = 7;
							while (*ip == 0)
								t += 255, ip++;
							t += *ip++;
						}
						m_pos -= *ip++ >> 2;
						m_pos -= *ip++ << 6;
						if (m_pos == op)
							goto eof_found;
						m_pos -= 0x4000;
					}
					if (litp == NULL)
						goto copy_m;

					nl = ip[-2] & 3;
					/* test if in beetween two matches */
					if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16)
					{
						assert(litp == ip - 3 - lit - 2);
						assert((lzo_uint)(*litp & 3) == lit);
						next_lit = nl;
						/* make a previous short run */
						lit += 3;
						*litp = LZO_BYTE((*litp & ~3) | lit);
						/* copy over the 3 literals that replace the match */
						copy3(ip-3,m_pos,op-m_pos);
						o_m3_a++;
					}
					/* test if a literal run follows */
					else if (t == 1 && lit <= 3 && nl == 0 &&
					         ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
					{
						assert(litp == ip - 3 - lit - 2);
						assert((lzo_uint)(*litp & 3) == lit);
						t = *ip++;
						/* remove short run */
						*litp &= ~3;
						/* copy over the 3 literals that replace the match */
						copy3(ip-4+1,m_pos,op-m_pos);
						/* move literals 1 byte ahead */
						litp += 2;
						if (lit > 0)
							lzo_memmove(litp+1,litp,lit);
						/* insert new length of long literal run */
						lit += 3 + t + 3; assert(lit <= 18);
						*litp = LZO_BYTE(lit - 3);

						o_m3_b++;
						*op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
						goto copy_literal_run;
					}
				}
copy_m:
				*op++ = *m_pos++; *op++ = *m_pos++;
				do *op++ = *m_pos++; while (--t > 0);
			}

match_done:
			if (next_lit == NO_LIT)
			{
				t = ip[-2] & 3;
				lit = t;
				litp = ip - 2;
			}
			else
				t = next_lit;
			assert(t <= 3);
			next_lit = NO_LIT;
			if (t == 0)
				break;
			/* copy literals */
match_next:
			do *op++ = *ip++; while (--t > 0);
			t = *ip++;
		}
	}

	/* no EOF code was found */
	*out_len = op - out;
	return LZO_E_EOF_NOT_FOUND;

eof_found:
	assert(t == 1);
#if 0
	printf("optimize: %lu %lu  %lu  %lu %lu\n",
	       o_m1_a, o_m1_b, o_m2, o_m3_a, o_m3_b);
#endif
	*out_len = op - out;
	return (ip == ip_end ? LZO_E_OK :
	       (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
}


/*
vi:ts=4:et
*/