compr_lzo.c

jffs2源代码基于2。6内核

static 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;
	lzo1x_999_t cc;
	lzo1x_999_t *const c = &cc;
	lzo1x_999_swd_t *const swd = (lzo1x_999_swd_t *) wrkmem;
	int r;

	if (!lzo_assert
	    (LZO1X_999_MEM_COMPRESS >= lzo_sizeof (lzo1x_999_swd_t)))
		return LZO_E_ERROR;

	if (try_lazy < 0)
		try_lazy = 1;

	if (good_length <= 0)
		good_length = 32;

	if (max_lazy <= 0)
		max_lazy = 32;

	if (nice_length <= 0)
		nice_length = 0;

	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;
	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;

		if (lit == 0)
			ii = c->bp;

		if (m_len < 2 ||
		    (m_len == 2
		     && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
		    || (m_len == 2 && op == out) || (op == out && lit == 0))
		{

			m_len = 0;
		}
		else if (m_len == M2_MIN_LEN)
		{

			if (m_off > MX_MAX_OFFSET && lit >= 4)
				m_len = 0;
		}

		if (m_len == 0)
		{

			lit++;
			swd->max_chain = max_chain;
			r = find_match (c, swd, 1, 0);
			continue;
		}

		if (swd->use_best_off)
			better_match (swd, &m_len, &m_off);

		ahead = 0;
		if (try_lazy <= 0 || m_len >= max_lazy)
		{

			l1 = 0;
			max_ahead = 0;
		}
		else
		{

			l1 = len_of_coded_match (m_len, m_off, lit);

			max_ahead = LZO_MIN (try_lazy, l1 - 1);

		}

		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++;

			if (c->m_len < m_len)
				continue;

			if (c->m_len == m_len && c->m_off >= m_off)
				continue;

			if (swd->use_best_off)
				better_match (swd, &c->m_len, &c->m_off);

			l2 = len_of_coded_match (c->m_len, c->m_off,
						 lit + ahead);
			if (l2 < 0)
				continue;

			l3 = (op == out) ? -1 : len_of_coded_match (ahead,
								    m_off,
								    lit);

			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++;

				if (l3 > 0)
				{

					op = code_run (c, op, ii, lit, ahead);
					lit = 0;

					op = code_match (c, op, ahead, m_off);
				}
				else
				{
					lit += ahead;
				}
				goto lazy_match_done;
			}
		}

		op = code_run (c, op, ii, lit, m_len);
		lit = 0;

		op = code_match (c, op, m_len, m_off);
		swd->max_chain = max_chain;
		r = find_match (c, swd, m_len, 1 + ahead);

	      lazy_match_done:;
	}

	if (lit > 0)
		op = STORE_RUN (c, op, ii, lit);

	*op++ = M4_MARKER | 1;
	*op++ = 0;
	*op++ = 0;

	c->codesize = op - out;

	*out_len = op - out;

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

	return LZO_E_OK;
}

static 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},
		{
		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}
	};

	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,
					    0,
					    c[compression_level].max_chain,
					    c[compression_level].flags);
}

static 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);
}

/* minilzo.c */

#ifdef JFFS2_LZO_1
static const lzo_byte __lzo_copyright[] = LZO_VERSION_STRING;

static lzo_uint
_lzo1x_1_do_compress (const lzo_byte * in, lzo_uint in_len,
		      lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
{

	register const lzo_byte *ip;

	lzo_byte *op;
	const lzo_byte *const in_end = in + in_len;
	const lzo_byte *const ip_end = in + in_len - 8 - 5;
	const lzo_byte *ii;
	lzo_dict_p const dict = (lzo_dict_p) wrkmem;

	op = out;
	ip = in;
	ii = ip;

	ip += 4;
	for (;;)
	{
		register const lzo_byte *m_pos;

		lzo_uint m_off;
		lzo_uint m_len;
		lzo_uint dindex;

		DINDEX1 (dindex, ip);
		GINDEX (m_pos, m_off, dict, dindex, in);
		if (LZO_CHECK_MPOS_NON_DET
		    (m_pos, m_off, in, ip, M4_MAX_OFFSET))
			goto literal;

		if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
			goto try_match;
		DINDEX2 (dindex, ip);
		GINDEX (m_pos, m_off, dict, dindex, in);

		if (LZO_CHECK_MPOS_NON_DET
		    (m_pos, m_off, in, ip, M4_MAX_OFFSET))
			goto literal;
		if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
			goto try_match;
		goto literal;

	      try_match:
		if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
		{
		}
		else
		{
			if (m_pos[2] == ip[2])
			{
				goto match;
			}
			else
			{
			}
		}

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

	      match:
		UPDATE_I (dict, 0, dindex, ip, in);

		if (pd (ip, ii) > 0)
		{
			register lzo_uint t = pd (ip, ii);

			if (t <= 3)
			{
				op[-2] |= LZO_BYTE (t);
			}
			else if (t <= 18)
				*op++ = LZO_BYTE (t - 3);
			else
			{
				register lzo_uint tt = t - 18;

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

		ip += 3;
		if (m_pos[3] != *ip++ || m_pos[4] != *ip++
		    || m_pos[5] != *ip++ || m_pos[6] != *ip++
		    || m_pos[7] != *ip++ || m_pos[8] != *ip++)
		{
			--ip;
			m_len = ip - ii;

			if (m_off <= M2_MAX_OFFSET)
			{
				m_off -= 1;

				*op++ = LZO_BYTE (((m_len -
						    1) << 5) | ((m_off & 7) <<
								2));
				*op++ = LZO_BYTE (m_off >> 3);
			}
			else if (m_off <= M3_MAX_OFFSET)
			{
				m_off -= 1;
				*op++ = LZO_BYTE (M3_MARKER | (m_len - 2));
				goto m3_m4_offset;
			}
			else

			{
				m_off -= 0x4000;

				*op++ = LZO_BYTE (M4_MARKER |
						  ((m_off & 0x4000) >> 11) |
						  (m_len - 2));
				goto m3_m4_offset;
			}
		}
		else
		{
			{
				const lzo_byte *end = in_end;
				const lzo_byte *m = m_pos + M2_MAX_LEN + 1;
				while (ip < end && *m == *ip)
					m++, ip++;
				m_len = (ip - ii);
			}


			if (m_off <= M3_MAX_OFFSET)
			{
				m_off -= 1;
				if (m_len <= 33)
					*op++ = LZO_BYTE (M3_MARKER |
							  (m_len - 2));
				else
				{
					m_len -= 33;
					*op++ = M3_MARKER | 0;
					goto m3_m4_len;
				}
			}
			else
			{
				m_off -= 0x4000;

				if (m_len <= M4_MAX_LEN)
					*op++ = LZO_BYTE (M4_MARKER |
							  ((m_off & 0x4000) >>
							   11) | (m_len - 2));

				else
				{
					m_len -= M4_MAX_LEN;
					*op++ = LZO_BYTE (M4_MARKER |
							  ((m_off & 0x4000) >>
							   11));
				      m3_m4_len:
					while (m_len > 255)
					{
						m_len -= 255;
						*op++ = 0;
					}

					*op++ = LZO_BYTE (m_len);
				}
			}

		      m3_m4_offset:
			*op++ = LZO_BYTE ((m_off & 63) << 2);
			*op++ = LZO_BYTE (m_off >> 6);
		}
		ii = ip;
		if (ip >= ip_end)
			break;
	}

	*out_len = op - out;
	return pd (in_end, ii);
}
#endif

#ifdef JFFS2_LZO_1
static int
lzo1x_1_compress (const lzo_byte * in, lzo_uint in_len,
		  lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
{
	lzo_byte *op = out;
	lzo_uint t;

	if (in_len <= M2_MAX_LEN + 5)
		t = in_len;
	else
	{
		t = _lzo1x_1_do_compress (in, in_len, op, out_len, wrkmem);
		op += *out_len;
	}

	if (t > 0)
	{
		const lzo_byte *ii = in + in_len - t;

		if (op == out && t <= 238)
			*op++ = LZO_BYTE (17 + t);
		else if (t <= 3)
			op[-2] |= LZO_BYTE (t);
		else if (t <= 18)
			*op++ = LZO_BYTE (t - 3);
		else
		{
			lzo_uint tt = t - 18;

			*op++ = 0;
			while (tt > 255)
			{
				tt -= 255;
				*op++ = 0;
			}

			*op++ = LZO_BYTE (tt);
		}
		do
			*op++ = *ii++;
		while (--t > 0);
	}

	*op++ = M4_MARKER | 1;
	*op++ = 0;
	*op++ = 0;

	*out_len = op - out;
	return 0;
}
#endif

static int
lzo1x_decompress (const lzo_byte * in, lzo_uint in_len,
		  lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
{
	register lzo_byte *op;
	register const lzo_byte *ip;
	register lzo_uint t;

	register const lzo_byte *m_pos;

	const lzo_byte *const ip_end = in + in_len;
	lzo_byte *const op_end = out + *out_len;

	*out_len = 0;

	op = out;
	ip = in;

	if (*ip > 17)
	{
		t = *ip++ - 17;
		if (t < 4)
			goto match_next;
		NEED_OP (t);
		NEED_IP (t + 1);
		do
			*op++ = *ip++;
		while (--t > 0);
		goto first_literal_run;
	}

	while (TEST_IP && TEST_OP)
	{
		t = *ip++;
		if (t >= 16)
			goto match;
		if (t == 0)
		{
			NEED_IP (1);
			while (*ip == 0)
			{
				t += 255;
				ip++;
				NEED_IP (1);
			}
			t += 15 + *ip++;
		}
		NEED_OP (t + 3);
		NEED_IP (t + 4);
		if (PTR_ALIGNED2_4 (op, ip))
		{
			COPY4 (op, ip);

			op += 4;
			ip += 4;
			if (--t > 0)
			{
				if (t >= 4)
				{
					do
					{
						COPY4 (op, ip);
						op += 4;
						ip += 4;
						t -= 4;
					}
					while (t >= 4);
					if (t > 0)
						do
							*op++ = *ip++;
						while (--t > 0);