lzo1a.c

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

			assert(m_pos >= in);
			assert(ip < ip_end);

			/* 1) store the current literal run */
		    if (pd(ip,ii) > 0)
			{
			    lzo_uint t = pd(ip,ii);

				if (ip - r1 == MIN_MATCH + 1)
				{
				/* Code a context sensitive R1 match.
				 * This is tricky and somewhat difficult to explain:
				 * multiplex a literal run of length 1 into the previous
				 * short match of length MIN_MATCH.
				 * The key idea is:
				 *  - after a short run a match MUST follow
				 *  - therefore the value m = 000 in the mmmooooo marker is free
				 *  - use 000ooooo to indicate a MIN_MATCH match (this
				 *    is already coded) plus a 1 byte literal
				 */
					assert(t == 1);
					/* modify marker byte */
					assert((op[-2] >> OBITS) == (MIN_MATCH - THRESHOLD));
					op[-2] &= OMASK;
					assert((op[-2] >> OBITS) == 0);
					/* copy 1 literal */
					*op++ = *ii;
					LZO_STATS(lzo_stats->r1_matches++);
					r1 = ip;				/* set new R1 pointer */
				}
				else if (t < R0MIN)
				{
					/* inline the copying of a short run */
#if (LBITS < 8)
					if (t < (1 << (8-LBITS)) && ii - im >= MIN_MATCH_LONG)
					{
					/* Code a very short literal run into the
					 * previous long match length byte.
					 */
						LZO_STATS(lzo_stats->lit_runs_after_long_match++);
						LZO_STATS(lzo_stats->lit_run_after_long_match[t]++);
						assert(ii - im <= MAX_MATCH_LONG);
						assert((op[-1] >> LBITS) == 0);
						op[-1] |= t << LBITS;
						MEMCPY_DS(op, ii, t);
					}
					else
#endif
					{
						LZO_STATS(lzo_stats->lit_runs++);
						LZO_STATS(lzo_stats->lit_run[t]++);
						*op++ = LZO_BYTE(t);
						MEMCPY_DS(op, ii, t);
						r1 = ip;				/* set new R1 pointer */
					}
				}
				else if (t < R0FAST)
				{
					/* inline the copying of a short R0 run */
					LZO_STATS(lzo_stats->r0short_runs++);
					*op++ = 0; *op++ = LZO_BYTE(t - R0MIN);
					MEMCPY_DS(op, ii, t);
					r1 = ip;				/* set new R1 pointer */
				}
				else
					op = store_run(op,ii,t);
			}
#if (LBITS < 8)
			im = ip;
#endif


			/* 2) 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
			{
			/* we've found a short match */
				lzo_uint m_len;

			/* 2a) compute match parameters */
					assert(ip-m_pos == (int)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 >= MIN_OFFSET);
					assert(m_off <= MAX_OFFSET);
					assert(ii-m_off == m_pos_sav);
					assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
				m_off -= MIN_OFFSET;

			/* 2b) code a short match */
				/* 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);


#if defined(LZO_COLLECT_STATS)
				lzo_stats->short_matches++;
				lzo_stats->short_match[m_len]++;
				if (m_off < OSIZE)
					lzo_stats->short_match_offset_osize[m_len]++;
				if (m_off < 256)
					lzo_stats->short_match_offset_256[m_len]++;
				if (m_off < 1024)
					lzo_stats->short_match_offset_1024[m_len]++;
#endif


			/* 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);

			/* 2a) compute match parameters */
				m_len = (ip - ii);
					assert(m_len >= MIN_MATCH_LONG);
					assert(m_len <= MAX_MATCH_LONG);
					assert(m_off >= MIN_OFFSET);
					assert(m_off <= MAX_OFFSET);
					assert(ii-m_off == m_pos_sav);
					assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
					assert(ip-m_pos == (int)m_off);
				m_off -= MIN_OFFSET;

			/* 2b) code the long match */
				/* 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);


#if defined(LZO_COLLECT_STATS)
				lzo_stats->long_matches++;
				lzo_stats->long_match[m_len]++;
#endif


			/* 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 the next literal run */
			assert(ii == ip);
		}

	} while (ip < ip_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 */
}


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

LZO_PUBLIC(int)
lzo1a_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


#if defined(LZO_COLLECT_STATS)
	memset(lzo_stats,0,sizeof(*lzo_stats));
	lzo_stats->rbits  = RBITS;
	lzo_stats->clevel = CLEVEL;
	lzo_stats->dbits  = DBITS;
	lzo_stats->lbits  = LBITS;
	lzo_stats->min_match_short = MIN_MATCH_SHORT;
	lzo_stats->max_match_short = MAX_MATCH_SHORT;
	lzo_stats->min_match_long  = MIN_MATCH_LONG;
	lzo_stats->max_match_long  = MAX_MATCH_LONG;
	lzo_stats->min_offset      = MIN_OFFSET;
	lzo_stats->max_offset      = MAX_OFFSET;
	lzo_stats->r0min  = R0MIN;
	lzo_stats->r0fast = R0FAST;
	lzo_stats->r0max  = R0MAX;
	lzo_stats->in_len = in_len;
#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);


#if defined(LZO_COLLECT_STATS)
	lzo_stats->short_matches -= lzo_stats->r1_matches;
	lzo_stats->short_match[MIN_MATCH] -= lzo_stats->r1_matches;
	lzo_stats->out_len = *out_len;
#endif

	return r;
}


/*
vi:ts=4:et
*/