compr_lzo.c

jffs2源代码基于2。6内核

	while (len-- > 0)
	{
		key = HEAD3 (s->b, node);
		s->succ3[node] = s_head3 (s, key);
		s->head3[key] = SWD_UINT (node);
		s->best3[node] = SWD_UINT (s->f + 1);
		s->llen3[key]++;

		key = HEAD2 (s->b, node);
		s->head2[key] = SWD_UINT (node);

		node++;
	}
}

static int
swd_init (lzo1x_999_swd_t * s, const lzo_byte * dict, lzo_uint dict_len)
{

	s->n = SWD_N;
	s->f = SWD_F;
	s->threshold = SWD_THRESHOLD;



	s->max_chain = SWD_MAX_CHAIN;
	s->nice_length = SWD_F;
	s->use_best_off = 0;
	s->lazy_insert = 0;

	s->b_size = s->n + s->f;
	if (2 * s->f >= s->n || s->b_size + s->f >= NIL2)
		return LZO_E_ERROR;
	s->b_wrap = s->b + s->b_size;
	s->node_count = s->n;

	memset (s->llen3, 0, sizeof (s->llen3[0]) * SWD_HSIZE);
	memset (s->head2, 0xff, sizeof (s->head2[0]) * 65536L);

	s->ip = 0;
	swd_initdict (s, dict, dict_len);
	s->bp = s->ip;
	s->first_rp = s->ip;

	s->look = (lzo_uint) (s->c->in_end - s->c->ip);
	if (s->look > 0)
	{
		if (s->look > s->f)
			s->look = s->f;
		memcpy (&s->b[s->ip], s->c->ip, s->look);
		s->c->ip += s->look;
		s->ip += s->look;
	}

	if (s->ip == s->b_size)
		s->ip = 0;

	if (s->look >= 2 && s->dict_len > 0)
		swd_insertdict (s, 0, s->dict_len);

	s->rp = s->first_rp;
	if (s->rp >= s->node_count)
		s->rp -= s->node_count;
	else
		s->rp += s->b_size - s->node_count;

	return LZO_E_OK;
}

static __inline__ void
swd_remove_node (lzo1x_999_swd_t * s, lzo_uint node)
{
	if (s->node_count == 0)
	{
		lzo_uint key;

		key = HEAD3 (s->b, node);

		--s->llen3[key];

		key = HEAD2 (s->b, node);

		if ((lzo_uint) s->head2[key] == node)
			s->head2[key] = NIL2;
	}
	else
		--s->node_count;
}

static void
swd_accept (lzo1x_999_swd_t * s, lzo_uint n)
{

	while (n--)
	{
		lzo_uint key;

		swd_remove_node (s, s->rp);

		key = HEAD3 (s->b, s->bp);
		s->succ3[s->bp] = s_head3 (s, key);
		s->head3[key] = SWD_UINT (s->bp);
		s->best3[s->bp] = SWD_UINT (s->f + 1);
		s->llen3[key]++;

		key = HEAD2 (s->b, s->bp);
		s->head2[key] = SWD_UINT (s->bp);;

		swd_getbyte (s);
	}
}

static void
swd_search (lzo1x_999_swd_t * s, lzo_uint node, lzo_uint cnt)
{
	const unsigned char *p1;
	const unsigned char *p2;
	const unsigned char *px;

	lzo_uint m_len = s->m_len;
	const unsigned char *b = s->b;
	const unsigned char *bp = s->b + s->bp;
	const unsigned char *bx = s->b + s->bp + s->look;
	unsigned char scan_end1;

	scan_end1 = bp[m_len - 1];
	for (; cnt-- > 0; node = s->succ3[node])
	{
		p1 = bp;
		p2 = b + node;
		px = bx;

		if (p2[m_len - 1] == scan_end1 &&
		    p2[m_len] == p1[m_len] &&
		    p2[0] == p1[0] && p2[1] == p1[1])
		{
			lzo_uint i;

			p1 += 2;
			p2 += 2;
			do
			{
			}
			while (++p1 < px && *p1 == *++p2);

			i = p1 - bp;

			if (i < SWD_BEST_OFF)
			{
				if (s->best_pos[i] == 0)
					s->best_pos[i] = node + 1;
			}

			if (i > m_len)
			{
				s->m_len = m_len = i;
				s->m_pos = node;
				if (m_len == s->look)
					return;
				if (m_len >= s->nice_length)
					return;
				if (m_len > (lzo_uint) s->best3[node])
					return;
				scan_end1 = bp[m_len - 1];
			}
		}
	}
}

static lzo_bool
swd_search2 (lzo1x_999_swd_t * s)
{
	lzo_uint key;

	key = s->head2[HEAD2 (s->b, s->bp)];
	if (key == NIL2)
		return 0;

	if (s->best_pos[2] == 0)
		s->best_pos[2] = key + 1;

	if (s->m_len < 2)
	{
		s->m_len = 2;
		s->m_pos = key;
	}
	return 1;
}

static void
swd_findbest (lzo1x_999_swd_t * s)
{
	lzo_uint key;
	lzo_uint cnt, node;
	lzo_uint len;

	key = HEAD3 (s->b, s->bp);
	node = s->succ3[s->bp] = s_head3 (s, key);
	cnt = s->llen3[key]++;

	if (cnt > s->max_chain && s->max_chain > 0)
		cnt = s->max_chain;
	s->head3[key] = SWD_UINT (s->bp);

	s->b_char = s->b[s->bp];
	len = s->m_len;
	if (s->m_len >= s->look)
	{
		if (s->look == 0)
			s->b_char = -1;
		s->m_off = 0;
		s->best3[s->bp] = SWD_UINT (s->f + 1);
	}
	else
	{

		if (swd_search2 (s))

			if (s->look >= 3)
				swd_search (s, node, cnt);
		if (s->m_len > len)
			s->m_off = swd_pos2off (s, s->m_pos);
		s->best3[s->bp] = SWD_UINT (s->m_len);

		if (s->use_best_off)
		{
			int i;
			for (i = 2; i < SWD_BEST_OFF; i++)
				if (s->best_pos[i] > 0)
					s->best_off[i] =
						swd_pos2off (s,
							     s->best_pos[i] -
							     1);
				else
					s->best_off[i] = 0;
		}

	}

	swd_remove_node (s, s->rp);

	key = HEAD2 (s->b, s->bp);
	s->head2[key] = SWD_UINT (s->bp);

}

/* lzo_mchw.ch */

static int
init_match (lzo1x_999_t * c, lzo1x_999_swd_t * s,
	    const lzo_byte * dict, lzo_uint dict_len, lzo_uint32 flags)
{
	int r;

	c->init = 1;

	s->c = c;

	c->last_m_len = c->last_m_off = 0;

	c->textsize = c->codesize = c->printcount = 0;
	c->lit_bytes = c->match_bytes = c->rep_bytes = 0;
	c->lazy = 0;

	r = swd_init (s, dict, dict_len);
	if (r != 0)
		return r;

	s->use_best_off = (flags & 1) ? 1 : 0;
	return r;
}

static int
find_match (lzo1x_999_t * c, lzo1x_999_swd_t * s,
	    lzo_uint this_len, lzo_uint skip)
{
	if (skip > 0)
	{
		swd_accept (s, this_len - skip);
		c->textsize += this_len - skip + 1;
	}
	else
	{
		c->textsize += this_len - skip;
	}

	s->m_len = 1;
	s->m_len = 1;

	if (s->use_best_off)
		memset (s->best_pos, 0, sizeof (s->best_pos));

	swd_findbest (s);
	c->m_len = s->m_len;
	c->m_off = s->m_off;

	swd_getbyte (s);

	if (s->b_char < 0)
	{
		c->look = 0;
		c->m_len = 0;
	}
	else
	{
		c->look = s->look + 1;
	}
	c->bp = c->ip - c->look;

	if (c->cb && c->textsize > c->printcount)
	{
		(*c->cb) (c->textsize, c->codesize);
		c->printcount += 1024;
	}

	return LZO_E_OK;
}

/* lzo1x_9x.c */

static lzo_byte *
code_match (lzo1x_999_t * c, lzo_byte * op, lzo_uint m_len, lzo_uint m_off)
{
	lzo_uint x_len = m_len;
	lzo_uint x_off = m_off;

	c->match_bytes += m_len;

	if (m_len == 2)
	{
		m_off -= 1;

		*op++ = LZO_BYTE (M1_MARKER | ((m_off & 3) << 2));
		*op++ = LZO_BYTE (m_off >> 2);

		c->m1a_m++;
	}

	else if (m_len <= M2_MAX_LEN && 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);
		c->m2_m++;
	}
	else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET
		 && c->r1_lit >= 4)
	{
		m_off -= 1 + M2_MAX_OFFSET;

		*op++ = LZO_BYTE (M1_MARKER | ((m_off & 3) << 2));
		*op++ = LZO_BYTE (m_off >> 2);

		c->m1b_m++;
	}
	else if (m_off <= M3_MAX_OFFSET)
	{
		m_off -= 1;
		if (m_len <= M3_MAX_LEN)
			*op++ = LZO_BYTE (M3_MARKER | (m_len - 2));
		else
		{
			m_len -= M3_MAX_LEN;
			*op++ = M3_MARKER | 0;
			while (m_len > 255)
			{
				m_len -= 255;
				*op++ = 0;
			}
			*op++ = LZO_BYTE (m_len);
		}

		*op++ = LZO_BYTE (m_off << 2);
		*op++ = LZO_BYTE (m_off >> 6);

		c->m3_m++;
	}
	else
	{
		lzo_uint k;

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

		*op++ = LZO_BYTE (m_off << 2);
		*op++ = LZO_BYTE (m_off >> 6);

		c->m4_m++;
	}

	c->last_m_len = x_len;
	c->last_m_off = x_off;
	return op;
}

static lzo_byte *
STORE_RUN (lzo1x_999_t * c, lzo_byte * op, const lzo_byte * ii, lzo_uint t)
{
	c->lit_bytes += t;

	if (op == c->out && t <= 238)
	{
		*op++ = LZO_BYTE (17 + t);
	}
	else if (t <= 3)
	{
		op[-2] |= LZO_BYTE (t);

		c->lit1_r++;
	}
	else if (t <= 18)
	{
		*op++ = LZO_BYTE (t - 3);
		c->lit2_r++;
	}
	else
	{
		lzo_uint tt = t - 18;

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

	return op;
}

static lzo_byte *
code_run (lzo1x_999_t * c, lzo_byte * op, const lzo_byte * ii,
	  lzo_uint lit, lzo_uint m_len)
{
	if (lit > 0)
	{
		op = STORE_RUN (c, op, ii, lit);
		c->r1_m_len = m_len;
		c->r1_lit = lit;
	}
	else
	{
		c->r1_m_len = 0;
		c->r1_lit = 0;
	}

	return op;
}

static int
len_of_coded_match (lzo_uint m_len, lzo_uint m_off, lzo_uint lit)
{
	int n = 4;

	if (m_len < 2)
		return -1;
	if (m_len == 2)
		return (m_off <= M1_MAX_OFFSET && lit > 0
			&& lit < 4) ? 2 : -1;
	if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
		return 2;
	if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
		return 2;
	if (m_off <= M3_MAX_OFFSET)
	{
		if (m_len <= M3_MAX_LEN)
			return 3;
		m_len -= M3_MAX_LEN;
		while (m_len > 255)
		{
			m_len -= 255;
			n++;
		}
		return n;
	}
	if (m_off <= M4_MAX_OFFSET)
	{
		if (m_len <= M4_MAX_LEN)
			return 3;
		m_len -= M4_MAX_LEN;
		while (m_len > 255)
		{
			m_len -= 255;
			n++;
		}
		return n;
	}
	return -1;
}

static lzo_int
min_gain (lzo_uint ahead, lzo_uint lit1, lzo_uint lit2, int l1, int l2,
	  int l3)
{
	lzo_int lazy_match_min_gain = 0;

	lazy_match_min_gain += ahead;

	if (lit1 <= 3)
		lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
	else if (lit1 <= 18)
		lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;

	lazy_match_min_gain += (l2 - l1) * 2;
	if (l3 > 0)
		lazy_match_min_gain -= (ahead - l3) * 2;

	if (lazy_match_min_gain < 0)
		lazy_match_min_gain = 0;

	return lazy_match_min_gain;
}

static void
better_match (const lzo1x_999_swd_t * swd, lzo_uint * m_len, lzo_uint * m_off)
{
	if (*m_len <= M2_MIN_LEN)
		return;

	if (*m_off <= M2_MAX_OFFSET)
		return;

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

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

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

}

/* minilzo.c */

static lzo_bool
lzo_assert (int expr)
{
	return (expr) ? 1 : 0;
}

/* lzo1x_9x.c */