lzo1.c

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

	}

	assert(r_len == 0);
	return op;
}



/***********************************************************************
// LZO1 compress a block of data.
//
// Could be translated into assembly code without too much effort.
//
// I apologize for the spaghetti code, but it really helps the optimizer.
************************************************************************/

static int
do_compress    ( const lzo_byte *in , lzo_uint  in_len,
                       lzo_byte *out, lzo_uintp out_len,
                       lzo_voidp wrkmem )
{
	const lzo_byte *ip;
#if defined(__LZO_HASH_INCREMENTAL)
	lzo_uint32 dv;
#endif
	lzo_byte *op;
	const lzo_byte *m_pos;
	const lzo_byte * const ip_end = in+in_len - DVAL_LEN - MIN_MATCH_LONG;
	const lzo_byte * const in_end = in+in_len - DVAL_LEN;
	const lzo_byte *ii;
	lzo_dict_p const dict = (lzo_dict_p) wrkmem;

#if !defined(NDEBUG)
	const lzo_byte *m_pos_sav;
#endif

	op = out;
	ip = in;
	ii = ip;				/* point to start of literal run */
	if (in_len <= MIN_MATCH_LONG + DVAL_LEN + 1)
		goto the_end;

	/* init dictionary */
#if defined(LZO_DETERMINISTIC)
	BZERO8_PTR(wrkmem,sizeof(lzo_dict_t),D_SIZE);
#endif

	DVAL_FIRST(dv,ip);
	UPDATE_D(dict,0,dv,ip,in);
	ip++;
	DVAL_NEXT(dv,ip);

	do {
		lzo_moff_t m_off;
		lzo_uint dindex;

		DINDEX1(dindex,ip);
		GINDEX(m_pos,m_off,dict,dindex,in);
		if (LZO_CHECK_MPOS(m_pos,m_off,in,ip,MAX_OFFSET))
			goto literal;
		if (m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2])
			goto match;
		DINDEX2(dindex,ip);
		GINDEX(m_pos,m_off,dict,dindex,in);
		if (LZO_CHECK_MPOS(m_pos,m_off,in,ip,MAX_OFFSET))
			goto literal;
		if (m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2])
			goto match;
		goto literal;


literal:
		UPDATE_I(dict,0,dindex,ip,in);
		if (++ip >= ip_end)
			break;
		continue;

match:
		UPDATE_I(dict,0,dindex,ip,in);
#if !defined(NDEBUG) && defined(LZO_DICT_USE_PTR)
		m_pos_sav = m_pos;
#endif
		m_pos += 3;
		{
	/* we have found a match (of at least length 3) */
#if !defined(NDEBUG) && !defined(LZO_DICT_USE_PTR)
			assert((m_pos_sav = ip - m_off) == (m_pos - 3));
#endif
			/* 1) store the current literal run */
		    if (pd(ip,ii) > 0)
			{
			    lzo_uint t = pd(ip,ii);
#if 1
				/* OPTIMIZED: inline the copying of a short run */
				if (t < R0MIN)
				{
					*op++ = LZO_BYTE(t);
					MEMCPY_DS(op, ii, t);
				}
				else
#endif
					op = store_run(op,ii,t);
			}

			/* 2a) compute match len */
			ii = ip;		/* point to start of current match */

			/* we already matched MIN_MATCH bytes,
			 * m_pos also already advanced MIN_MATCH bytes */
			ip += MIN_MATCH;
			assert(m_pos < ip);

			/* try to match another MIN_MATCH_LONG - MIN_MATCH bytes
			 * to see if we get a long match */

#define PS	*m_pos++ != *ip++

#if (MIN_MATCH_LONG - MIN_MATCH == 2)					/* MBITS == 2 */
			if (PS || PS)
#elif (MIN_MATCH_LONG - MIN_MATCH == 6)					/* MBITS == 3 */
			if (PS || PS || PS || PS || PS || PS)
#elif (MIN_MATCH_LONG - MIN_MATCH == 14)				/* MBITS == 4 */
			if (PS || PS || PS || PS || PS || PS || PS ||
			    PS || PS || PS || PS || PS || PS || PS)
#elif (MIN_MATCH_LONG - MIN_MATCH == 30)				/* MBITS == 5 */
			if (PS || PS || PS || PS || PS || PS || PS || PS ||
		    	PS || PS || PS || PS || PS || PS || PS || PS ||
		    	PS || PS || PS || PS || PS || PS || PS || PS ||
		    	PS || PS || PS || PS || PS || PS)
#else
#  error "MBITS not yet implemented"
#endif
			{
				lzo_uint m_len;

			/* 2b) code a short match */
					assert((lzo_moff_t)(ip-m_pos) == m_off);
				--ip;	/* ran one too far, point back to non-match */
				m_len = ip - ii;
					assert(m_len >= MIN_MATCH_SHORT);
					assert(m_len <= MAX_MATCH_SHORT);
					assert(m_off > 0);
					assert(m_off <= MAX_OFFSET);
					assert(ii-m_off == m_pos_sav);
					assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
				--m_off;
				/* code short match len + low offset bits */
				*op++ = LZO_BYTE(((m_len - THRESHOLD) << OBITS) |
				                 (m_off & OMASK));
				/* code high offset bits */
				*op++ = LZO_BYTE(m_off >> OBITS);


			/* 2c) Insert phrases (beginning with ii+1) into the dictionary. */

#define SI		/* nothing */
#define DI		++ii; DVAL_NEXT(dv,ii); UPDATE_D(dict,0,dv,ii,in);
#define XI		assert(ii < ip); ii = ip; DVAL_FIRST(dv,(ip));

#if (CLEVEL == 9) || (CLEVEL >= 7 && MBITS <= 4) || (CLEVEL >= 5 && MBITS <= 3)
			/* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
				++ii;
				do {
					DVAL_NEXT(dv,ii);
					UPDATE_D(dict,0,dv,ii,in);
				} while (++ii < ip);
				DVAL_NEXT(dv,ii);
				assert(ii == ip);
				DVAL_ASSERT(dv,ip);
#elif (CLEVEL >= 3)
				SI   DI DI   XI
#elif (CLEVEL >= 2)
				SI   DI      XI
#else
				             XI
#endif

			}
			else
			{
			/* we've found a long match - see how far we can still go */
				const lzo_byte *end;
				lzo_uint m_len;

				assert(ip <= in_end);
				assert(ii == ip - MIN_MATCH_LONG);

#if defined(__LZO_CHECKER)
				if (in_end - ip <= (MAX_MATCH_LONG - MIN_MATCH_LONG))
#else
				if (in_end <= ip + (MAX_MATCH_LONG - MIN_MATCH_LONG))
#endif
					end = in_end;
				else
				{
					end = ip + (MAX_MATCH_LONG - MIN_MATCH_LONG);
					assert(end < in_end);
				}

				while (ip < end  &&  *m_pos == *ip)
					m_pos++, ip++;
				assert(ip <= in_end);

			/* 2b) code the long match */
				m_len = ip - ii;
					assert(m_len >= MIN_MATCH_LONG);
					assert(m_len <= MAX_MATCH_LONG);
					assert(m_off > 0);
					assert(m_off <= MAX_OFFSET);
					assert(ii-m_off == m_pos_sav);
					assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
					assert((lzo_moff_t)(ip-m_pos) == m_off);
				--m_off;
				/* code long match flag + low offset bits */
				*op++ = LZO_BYTE(((MSIZE - 1) << OBITS) | (m_off & OMASK));
				/* code high offset bits */
				*op++ = LZO_BYTE(m_off >> OBITS);
				/* code match len */
				*op++ = LZO_BYTE(m_len - MIN_MATCH_LONG);


			/* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
#if (CLEVEL == 9)
			/* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
			/* This is not recommended because it is slow. */
				++ii;
				do {
					DVAL_NEXT(dv,ii);
					UPDATE_D(dict,0,dv,ii,in);
				} while (++ii < ip);
				DVAL_NEXT(dv,ii);
				assert(ii == ip);
				DVAL_ASSERT(dv,ip);
#elif (CLEVEL >= 8)
				SI   DI DI DI DI DI DI DI DI   XI
#elif (CLEVEL >= 7)
				SI   DI DI DI DI DI DI DI      XI
#elif (CLEVEL >= 6)
				SI   DI DI DI DI DI DI         XI
#elif (CLEVEL >= 5)
				SI   DI DI DI DI               XI
#elif (CLEVEL >= 4)
				SI   DI DI DI                  XI
#elif (CLEVEL >= 3)
				SI   DI DI                     XI
#elif (CLEVEL >= 2)
				SI   DI                        XI
#else
				                               XI
#endif
			}

			/* ii now points to the start of next literal run */
			assert(ii == ip);
		}
	} while (ip < ip_end);



the_end:
	assert(ip <= in_end);


#if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE)
	/* return -1 if op == out to indicate that we
	 * couldn't compress and didn't copy anything.
	 */
	if (op == out)
	{
		*out_len = 0;
		return LZO_E_NOT_COMPRESSIBLE;
	}
#endif


	/* store the final literal run */
	if (pd(in_end+DVAL_LEN,ii) > 0)
		op = store_run(op,ii,pd(in_end+DVAL_LEN,ii));

	*out_len = op - out;
	return 0;				/* compression went ok */
}


/***********************************************************************
// compress public entry point.
************************************************************************/

LZO_PUBLIC(int)
lzo1_compress ( const lzo_byte *in , lzo_uint  in_len,
                      lzo_byte *out, lzo_uintp out_len,
                      lzo_voidp wrkmem )
{
	int r = LZO_E_OK;

#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,D_SIZE,lzo_sizeof(lzo_dict_t));
#endif

	/* don't try to compress a block that's too short */
	if (in_len <= 0)
		*out_len = 0;
	else if (in_len <= MIN_MATCH_LONG + DVAL_LEN + 1)
	{
#if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE)
		r = LZO_E_NOT_COMPRESSIBLE;
#else
		*out_len = store_run(out,in,in_len) - out;
#endif
	}
	else
		r = do_compress(in,in_len,out,out_len,wrkmem);

	return r;
}


/*
vi:ts=4:et
*/