- Initial checkin of the freebios2 tree

git-svn-id: svn://svn.coreboot.org/coreboot/trunk@784 2b7e53f0-3cfb-0310-b3e9-8179ed1497e1

2 files changed, 1479 insertions, 0 deletions

diff --git a/util/nrv2b/Makefile b/util/nrv2b/Makefile
new file mode 100644
index 0000000000..e4d6e7bff5
--- /dev/null
+++ b/util/nrv2b/Makefile
@@ -0,0 +1,7 @@
+GCC=gcc
+
+nrv2b:	nrv2b.c
+	$(GCC) -O2 -DENCODE -DDECODE -DMAIN -DVERBOSE -DNDEBUG -DBITSIZE=32 -DENDIAN=0 -o $@ $<
+
+clean:
+	rm -f nrv2b
diff --git a/util/nrv2b/nrv2b.c b/util/nrv2b/nrv2b.c
new file mode 100644
index 0000000000..f12a4f5eb0
--- /dev/null
+++ b/util/nrv2b/nrv2b.c
@@ -0,0 +1,1472 @@
+/**************************************************************
+    Form adapted from lzhuf.c
+    written by Haruyasu Yoshizaki 11/20/1988
+    some minor changes 4/6/1989
+    comments translated by Haruhiko Okumura 4/7/1989
+
+    minor beautifications and adjustments for compiling under Linux
+    by Markus Gutschke <gutschk@math.uni-muenster.de>
+    						1997-01-27
+
+    Modifications to allow use as a filter by Ken Yap
+    <ken_yap@users.sourceforge.net>.
+
+						1997-07-01
+
+    Small mod to cope with running on big-endian machines
+    by Jim Hague <jim.hague@acm.org)
+						1998-02-06
+
+    Make compression statistics report shorter
+    by Ken Yap <ken_yap@users.sourceforge.net>.
+						2001-04-25
+
+    Replaced algorithm with nrv2b from ucl the compression
+    library from upx.  That code is:
+    Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer
+    And is distributed under the terms of the GPL.
+    The conversion was performed 
+    by Eric Biederman <ebiederman@lnxi.com>.
+                                             20 August 2002
+                                                
+**************************************************************/
+#define UCLPACK_COMPAT 0
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <errno.h>
+#include <stdint.h>
+#include <limits.h>
+#include <assert.h>
+#if UCLPACK_COMPAT
+#include <netinet/in.h>
+#endif
+
+#ifndef VERBOSE
+#define Fprintf(x)
+#define wterr     0
+#else
+#define Fprintf(x) fprintf x
+#endif
+
+#ifndef MAIN
+extern
+#endif
+FILE  *infile, *outfile;
+
+#if defined(ENCODE) || defined(DECODE)
+
+#ifndef ENDIAN
+#define ENDIAN   0
+#endif
+#ifndef BITSIZE
+#define BITSIZE 32
+#endif
+
+static __inline__ void Error(char *message)
+{
+	Fprintf((stderr, "\n%s\n", message));
+	exit(EXIT_FAILURE);
+}
+
+/* These will be a complete waste of time on a lo-endian */
+/* system, but it only gets done once so WTF. */
+static unsigned long i86ul_to_host(unsigned long ul)
+{
+	unsigned long res = 0;
+	int i;
+	union
+	{
+		unsigned char c[4];
+		unsigned long ul;
+	} u;
+
+	u.ul = ul;
+	for (i = 3; i >= 0; i--)
+		res = (res << 8) + u.c[i];
+	return res;
+}
+
+static unsigned long host_to_i86ul(unsigned long ul)
+{
+	int i;
+	union
+	{
+		unsigned char c[4];
+		unsigned long ul;
+	} u;
+
+	for (i = 0; i < 4; i++)
+	{
+		u.c[i] = ul & 0xff;
+		ul >>= 8;
+	}
+	return u.ul;
+}
+#endif
+
+
+
+#if UCLPACK_COMPAT
+/* magic file header for compressed files */
+static const unsigned char magic[8] =
+{ 0x00, 0xe9, 0x55, 0x43, 0x4c, 0xff, 0x01, 0x1a };
+
+#endif
+
+#ifdef ENCODE
+/********** NRV2B_99 compression **********/
+
+#define N       (1024*1024ul)       /* size of ring buffer */
+#define THRESHOLD       1           /* lower limit for match length */
+#define F            2048           /* upper limit for match length */
+#define M2_MAX_OFFSET                 0xd00
+
+/* note: to use default values pass -1, i.e. initialize
+ * this struct by a memset(x,0xff,sizeof(x)) */
+struct ucl_compress_config
+{
+	int bb_endian;
+	int bb_size;
+	unsigned int max_offset;
+	unsigned int max_match;
+	int s_level;
+	int h_level;
+	int p_level;
+	int c_flags;
+	unsigned int m_size;
+};
+
+struct ucl_compress
+{
+	int init;
+
+	unsigned int look;          /* bytes in lookahead buffer */
+	
+	unsigned int m_len;
+	unsigned int m_off;
+	
+	unsigned int last_m_len;
+	unsigned int last_m_off;
+	
+	const unsigned char *bp;
+	const unsigned char *ip;
+	const unsigned char *in;
+	const unsigned char *in_end;
+	unsigned char *out;
+	
+	uint32_t bb_b;
+	unsigned bb_k;
+	unsigned bb_c_endian;
+	unsigned bb_c_s;
+	unsigned bb_c_s8;
+	unsigned char *bb_p;
+	unsigned char *bb_op;
+	
+	struct ucl_compress_config conf;
+	unsigned int *result;
+
+	unsigned int textsize;      /* text size counter */
+	unsigned int codesize;      /* code size counter */
+	unsigned int printcount; /* counter for reporting progress every 1K
+				    bytes */
+
+	
+	/* some stats */
+	unsigned long lit_bytes;
+	unsigned long match_bytes;
+	unsigned long rep_bytes;
+	unsigned long lazy;
+};
+
+
+
+#define getbyte(c)  ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
+
+#define UCL_E_OK               0
+#define UCL_E_INVALID_ARGUMENT 1
+#define UCL_E_OUT_OF_MEMORY    2
+#define UCL_E_ERROR            3
+
+/***********************************************************************
+//
+************************************************************************/
+
+#define SWD_HSIZE	16384
+#define SWD_MAX_CHAIN	2048
+
+#define HEAD3(b,p) \
+    (((0x9f5f*(((((uint32_t)b[p]<<5)^b[p+1])<<5)^b[p+2]))>>5) & (SWD_HSIZE-1))
+
+#define HEAD2(b,p)      (b[p] ^ ((unsigned)b[p+1]<<8))
+#define NIL2              UINT_MAX
+
+struct ucl_swd
+{
+/* public - "built-in" */
+	unsigned int n;
+	unsigned int f;
+	unsigned int threshold;
+	
+/* public - configuration */
+	unsigned int max_chain;
+	unsigned int nice_length;
+	int use_best_off;
+	unsigned int lazy_insert;
+	
+/* public - output */
+	unsigned int m_len;
+	unsigned int m_off;
+	unsigned int look;
+	int b_char;
+#if defined(SWD_BEST_OFF)
+	unsigned int best_off[ SWD_BEST_OFF ];
+#endif
+	
+/* semi public */
+	struct ucl_compress *c;
+	unsigned int m_pos;
+#if defined(SWD_BEST_OFF)
+	unsigned int best_pos[ SWD_BEST_OFF ];
+#endif
+	
+/* private */
+	const uint8_t *dict;
+	const uint8_t *dict_end;
+	unsigned int dict_len;
+	
+/* private */
+	unsigned int ip;                /* input pointer (lookahead) */
+	unsigned int bp;                /* buffer pointer */
+	unsigned int rp;                /* remove pointer */
+	unsigned int b_size;
+	
+	unsigned char *b_wrap;
+	
+	unsigned int node_count;
+	unsigned int first_rp;
+
+	unsigned char b [ N + F + F ];
+	unsigned int head3 [ SWD_HSIZE ];
+	unsigned int succ3 [ N + F ];
+	unsigned int best3 [ N + F ];
+	unsigned int llen3 [ SWD_HSIZE ];
+	unsigned int head2 [ 65536U ];
+};
+
+#define s_head3(s,key)        s->head3[key]
+
+
+#if !defined( NDEBUG)
+static void assert_match(const struct ucl_swd * swd, unsigned int m_len,
+	unsigned int m_off )
+
+{
+	const struct ucl_compress *c = swd->c;
+	unsigned int d_off;
+	
+	assert(m_len >= 2);
+	if (m_off <= (unsigned int) (c->bp - c->in))
+	{
+		assert(c->bp - m_off + m_len < c->ip);
+		assert(memcmp(c->bp, c->bp - m_off, m_len) == 0);
+	}
+	else
+	{
+		assert(swd->dict != NULL);
+		d_off = m_off - (unsigned int) (c->bp - c->in);
+		assert(d_off <= swd->dict_len);
+		if (m_len > d_off)
+		{
+			assert(memcmp(c->bp, swd->dict_end - d_off, d_off) ==
+				0);
+
+			assert(c->in + m_len - d_off < c->ip);
+			assert(memcmp(c->bp + d_off, c->in, m_len - d_off) ==
+				0);
+
+		}
+		else
+		{
+			assert(memcmp(c->bp, swd->dict_end - d_off, m_len) ==
+				0);
+
+		}
+	}
+}
+#else
+#  define assert_match(a,b,c)   ((void)0)
+#endif
+
+/***********************************************************************
+//
+************************************************************************/
+
+
+static
+void swd_initdict(struct ucl_swd *s, const uint8_t *dict, unsigned int dict_len)
+
+{
+	s->dict = s->dict_end = NULL;
+	s->dict_len = 0;
+
+	if (!dict || dict_len <= 0)
+		return;
+	if (dict_len > s->n)
+	{
+		dict += dict_len - s->n;
+		dict_len = s->n;
+	}
+
+	s->dict = dict;
+	s->dict_len = dict_len;
+	s->dict_end = dict + dict_len;
+	memcpy(s->b,dict,dict_len);
+	s->ip = dict_len;
+}
+
+
+static
+void swd_insertdict(struct ucl_swd *s, unsigned int node, unsigned int len)
+{
+	unsigned int key;
+
+	s->node_count = s->n - len;
+	s->first_rp = node;
+
+	while (len-- > 0)
+	{
+		key = HEAD3(s->b,node);
+		s->succ3[node] = s_head3(s,key);
+		s->head3[key] = (unsigned int)(node);
+		s->best3[node] = (unsigned int)(s->f + 1);
+		s->llen3[key]++;
+		assert(s->llen3[key] <= s->n);
+
+		key = HEAD2(s->b,node);
+		s->head2[key] = (unsigned int)(node);
+
+		node++;
+	}
+}
+
+/***********************************************************************
+//
+************************************************************************/
+
+
+static
+int swd_init(struct ucl_swd *s, const uint8_t *dict, unsigned int dict_len)
+{
+	unsigned int i = 0;
+	int c = 0;
+
+	if (s->n == 0)
+		s->n = N;
+	if (s->f == 0)
+		s->f = F;
+	s->threshold = THRESHOLD;
+	if (s->n > N || s->f > F)
+		return UCL_E_INVALID_ARGUMENT;
+
+	/* defaults */
+	s->max_chain = SWD_MAX_CHAIN;
+	s->nice_length = s->f;
+	s->use_best_off = 0;
+	s->lazy_insert = 0;
+
+	s->b_size = s->n + s->f;
+	if (s->b_size + s->f >= UINT_MAX)
+		return UCL_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);
+	for (i = 0; i < 65536U; i++)
+		s->head2[i] = NIL2;
+
+	s->ip = 0;
+	swd_initdict(s,dict,dict_len);
+	s->bp = s->ip;
+	s->first_rp = s->ip;
+
+	assert(s->ip + s->f <= s->b_size);
+
+	s->look = (unsigned int) (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;
+
+	/* unused i */
+	/* unused c */
+	return UCL_E_OK;
+}
+
+
+static
+void swd_exit(struct ucl_swd *s)
+{
+	/* unused s */
+
+}
+
+#define swd_pos2off(s,pos) \
+	(s->bp > (pos) ? s->bp - (pos) : s->b_size - ((pos) - s->bp))
+
+/***********************************************************************
+//
+************************************************************************/
+
+static __inline__
+void swd_getbyte(struct ucl_swd *s)
+{
+	int c;
+
+	if ((c = getbyte(*(s->c))) < 0)
+	{
+		if (s->look > 0)
+			--s->look;
+	}
+	else
+	{
+		s->b[s->ip] = (uint8_t)(c);
+		if (s->ip < s->f)
+			s->b_wrap[s->ip] = (uint8_t)(c);
+	}
+	if (++s->ip == s->b_size)
+		s->ip = 0;
+	if (++s->bp == s->b_size)
+		s->bp = 0;
+	if (++s->rp == s->b_size)
+		s->rp = 0;
+}
+/***********************************************************************
+// remove node from lists
+************************************************************************/
+
+static __inline__
+void swd_remove_node(struct ucl_swd *s, unsigned int node)
+{
+	if (s->node_count == 0)
+	{
+		unsigned int key;
+		
+#ifdef UCL_DEBUG
+		if (s->first_rp != UINT_MAX)
+		{
+			if (node != s->first_rp)
+				printf("Remove %5d: %5d %5d %5d %5d %6d %6d\n",
+
+					node, s->rp, s->ip, s->bp, s->first_rp,
+					s->ip - node, s->ip - s->bp);
+			assert(node == s->first_rp);
+			s->first_rp = UINT_MAX;
+		}
+#endif
+		
+		key = HEAD3(s->b,node);
+		assert(s->llen3[key] > 0);
+		--s->llen3[key];
+		
+		key = HEAD2(s->b,node);
+		assert(s->head2[key] != NIL2);
+		if ((unsigned int) s->head2[key] == node)
+			s->head2[key] = NIL2;
+	}
+	else
+		--s->node_count;
+}
+
+
+/***********************************************************************
+//
+************************************************************************/
+
+
+static
+void swd_accept(struct ucl_swd *s, unsigned int n)
+{
+	assert(n <= s->look);
+
+	if (n > 0) do
+	{
+		unsigned int key;
+
+		swd_remove_node(s,s->rp);
+
+		/* add bp into HEAD3 */
+		key = HEAD3(s->b,s->bp);
+		s->succ3[s->bp] = s_head3(s,key);
+		s->head3[key] = (unsigned int)(s->bp);
+		s->best3[s->bp] = (unsigned int)(s->f + 1);
+		s->llen3[key]++;
+		assert(s->llen3[key] <= s->n);
+
+		/* add bp into HEAD2 */
+		key = HEAD2(s->b,s->bp);
+		s->head2[key] = (unsigned int)(s->bp);
+
+		swd_getbyte(s);
+	} while (--n > 0);
+}
+
+/***********************************************************************
+//
+************************************************************************/
+
+static
+void swd_search(struct ucl_swd *s, unsigned int node, unsigned int cnt)
+{
+	const unsigned char *p1;
+	const unsigned char *p2;
+	const unsigned char *px;
+
+	unsigned int 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;
+	
+	assert(s->m_len > 0);
+	
+	scan_end1 = bp[m_len - 1];
+	for ( ; cnt-- > 0; node = s->succ3[node])
+	{
+		p1 = bp;
+		p2 = b + node;
+		px = bx;
+		
+		assert(m_len < s->look);
+		
+		if (
+			p2[m_len - 1] == scan_end1 &&
+			p2[m_len] == p1[m_len] &&
+			p2[0] == p1[0] &&
+			p2[1] == p1[1])
+		{
+			unsigned int i;
+			assert(memcmp(bp,&b[node],3) == 0);
+			
+			p1 += 2; p2 += 2;
+			do {} while (++p1 < px && *p1 == *++p2);
+			i = p1 - bp;
+			
+#ifdef UCL_DEBUG
+			if (memcmp(bp,&b[node],i) != 0)
+				printf("%5ld %5ld %02x%02x %02x%02x\n",
+					(long)s->bp, (long) node,
+					bp[0], bp[1], b[node], b[node+1]);
+#endif
+			assert(memcmp(bp,&b[node],i) == 0);
+			
+#if defined(SWD_BEST_OFF)
+			if (i < SWD_BEST_OFF)
+			{
+				if (s->best_pos[i] == 0)
+					s->best_pos[i] = node + 1;
+			}
+#endif
+			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 > (unsigned int) s->best3[node])
+					return;
+				scan_end1 = bp[m_len - 1];
+			}
+		}
+	}
+}
+
+static int swd_search2(struct ucl_swd *s)
+{
+	unsigned int key;
+	
+	assert(s->look >= 2);
+	assert(s->m_len > 0);
+	
+	key = s->head2[ HEAD2(s->b,s->bp) ];
+	if (key == NIL2)
+		return 0;
+#ifdef UCL_DEBUG
+	if (memcmp(&s->b[s->bp],&s->b[key],2) != 0)
+		printf("%5ld %5ld %02x%02x %02x%02x\n", (long)s->bp, (long)key,
+			s->b[s->bp], s->b[s->bp+1], s->b[key], s->b[key+1]);
+#endif
+	assert(memcmp(&s->b[s->bp],&s->b[key],2) == 0);
+#if defined(SWD_BEST_OFF)
+	if (s->best_pos[2] == 0)
+		s->best_pos[2] = key + 1;
+#endif
+	
+	if (s->m_len < 2)
+	{
+		s->m_len = 2;
+		s->m_pos = key;
+	}
+	return 1;
+}
+
+/***********************************************************************
+//
+************************************************************************/
+
+static
+void swd_findbest(struct ucl_swd *s)
+{
+	unsigned int key;
+	unsigned int cnt, node;
+	unsigned int len;
+
+	assert(s->m_len > 0);
+
+	/* get current head, add bp into HEAD3 */
+	key = HEAD3(s->b,s->bp);
+	node = s->succ3[s->bp] = s_head3(s,key);
+	cnt = s->llen3[key]++;
+	assert(s->llen3[key] <= s->n + s->f);
+	if (cnt > s->max_chain && s->max_chain > 0)
+		cnt = s->max_chain;
+	s->head3[key] = (unsigned int)(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] = (unsigned int)(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] = (unsigned int)(s->m_len);
+
+#if defined(SWD_BEST_OFF)
+		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;
+		}
+#endif
+	}
+
+	swd_remove_node(s,s->rp);
+
+	/* add bp into HEAD2 */
+	key = HEAD2(s->b,s->bp);
+	s->head2[key] = (unsigned int)(s->bp);
+}
+
+
+/***********************************************************************
+//
+************************************************************************/
+
+static int
+init_match ( struct ucl_compress *c, struct ucl_swd *s,
+	const uint8_t *dict, unsigned int dict_len,
+	uint32_t flags )
+{
+	int r;
+	
+	assert(!c->init);
+	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 != UCL_E_OK)
+	{
+		swd_exit(s);
+		return r;
+	}
+	
+	s->use_best_off = (flags & 1) ? 1 : 0;
+	return UCL_E_OK;
+}
+
+static int
+find_match ( struct ucl_compress *c, struct ucl_swd *s,
+	unsigned int this_len, unsigned int skip )
+{
+	assert(c->init);
+	
+	if (skip > 0)
+	{
+		assert(this_len >= skip);
+		swd_accept(s, this_len - skip);
+		c->textsize += this_len - skip + 1;
+	}
+	else
+	{
+		assert(this_len <= 1);
+		c->textsize += this_len - skip;
+	}
+	
+	s->m_len = THRESHOLD;
+#ifdef SWD_BEST_OFF
+	if (s->use_best_off)
+		memset(s->best_pos,0,sizeof(s->best_pos));
+#endif
+	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;
+		swd_exit(s);
+	}
+	else
+	{
+		c->look = s->look + 1;
+	}
+	c->bp = c->ip - c->look;
+	
+#if 0
+	/* brute force match search */
+	if (c->m_len > THRESHOLD && c->m_len + 1 <= c->look)
+	{
+		const uint8_t *ip = c->bp;
+		const uint8_t *m  = c->bp - c->m_off;
+		const uint8_t *in = c->in;
+		
+		if (ip - in > N)
+			in = ip - N;
+		for (;;)
+		{
+			while (*in != *ip)
+				in++;
+			if (in == ip)
+				break;
+			if (in != m)
+				if (memcmp(in,ip,c->m_len+1) == 0)
+					printf("%p %p %p
+%5d\n",in,ip,m,c->m_len);
+
+			in++;
+		}
+	}
+#endif
+	
+	return UCL_E_OK;
+}
+
+
+static int bbConfig(struct ucl_compress *c, int endian, int bitsize)
+{
+	if (endian != -1)
+	{
+		if (endian != 0)
+			return UCL_E_ERROR;
+		c->bb_c_endian = endian;
+	}
+	if (bitsize != -1)
+	{
+		if (bitsize != 8 && bitsize != 16 && bitsize != 32)
+			return UCL_E_ERROR;
+		c->bb_c_s = bitsize;
+		c->bb_c_s8 = bitsize / 8;
+	}
+	c->bb_b = 0; c->bb_k = 0;
+	c->bb_p = NULL;
+	c->bb_op = NULL;
+	return UCL_E_OK;
+}
+
+static void bbWriteBits(struct ucl_compress *c)
+{
+	uint8_t *p = c->bb_p;
+	uint32_t b = c->bb_b;
+
+	p[0] = (uint8_t)(b >>  0);
+	if (c->bb_c_s >= 16)
+	{
+		p[1] = (uint8_t)(b >>  8);
+		if (c->bb_c_s == 32)
+		{
+			p[2] = (uint8_t)(b >> 16);
+			p[3] = (uint8_t)(b >> 24);
+		}
+	}
+}
+
+
+static void bbPutBit(struct ucl_compress *c, unsigned bit)
+{
+	assert(bit == 0 || bit == 1);
+	assert(c->bb_k <= c->bb_c_s);
+
+	if (c->bb_k < c->bb_c_s)
+	{
+		if (c->bb_k == 0)
+		{
+			assert(c->bb_p == NULL);
+			c->bb_p = c->bb_op;
+			c->bb_op += c->bb_c_s8;
+		}
+		assert(c->bb_p != NULL);
+		assert(c->bb_p + c->bb_c_s8 <= c->bb_op);
+
+		c->bb_b = (c->bb_b << 1) + bit;
+		c->bb_k++;
+	}
+	else
+	{
+		assert(c->bb_p != NULL);
+		assert(c->bb_p + c->bb_c_s8 <= c->bb_op);
+
+		bbWriteBits(c);
+		c->bb_p = c->bb_op;
+		c->bb_op += c->bb_c_s8;
+		c->bb_b = bit;
+		c->bb_k = 1;
+	}
+}
+
+
+static void bbPutByte(struct ucl_compress *c, unsigned b)
+{
+	/**printf("putbyte %p %p %x  (%d)\n", op, bb_p, x, bb_k);*/
+	assert(c->bb_p == NULL || c->bb_p + c->bb_c_s8 <= c->bb_op);
+	*c->bb_op++ = (uint8_t)(b);
+}
+
+static void bbFlushBits(struct ucl_compress *c, unsigned filler_bit)
+{
+	if (c->bb_k > 0)
+	{
+		assert(c->bb_k <= c->bb_c_s);
+		while (c->bb_k != c->bb_c_s)
+			bbPutBit(c, filler_bit);
+		bbWriteBits(c);
+		c->bb_k = 0;
+	}
+	c->bb_p = NULL;
+}
+
+
+
+/***********************************************************************
+//
+************************************************************************/
+
+
+static void code_prefix_ss11(struct ucl_compress *c, uint32_t i)
+{
+	if (i >= 2)
+	{
+		uint32_t t = 4;
+		i += 2;
+		do {
+			t <<= 1;
+		} while (i >= t);
+		t >>= 1;
+		do {
+			t >>= 1;
+			bbPutBit(c, (i & t) ? 1 : 0);
+			bbPutBit(c, 0);
+		} while (t > 2);
+	}
+	bbPutBit(c, (unsigned)i & 1);
+	bbPutBit(c, 1);
+}
+
+static void
+code_match(struct ucl_compress *c, unsigned int m_len, const unsigned int m_off)
+
+{
+	while (m_len > c->conf.max_match)
+	{
+		code_match(c, c->conf.max_match - 3, m_off);
+		m_len -= c->conf.max_match - 3;
+	}
+	
+	c->match_bytes += m_len;
+	if (m_len > c->result[3])
+		c->result[3] = m_len;
+	if (m_off > c->result[1])
+		c->result[1] = m_off;
+
+	bbPutBit(c, 0);
+
+	if (m_off == c->last_m_off)
+	{
+		bbPutBit(c, 0);
+		bbPutBit(c, 1);
+	}
+	else
+	{
+		code_prefix_ss11(c, 1 + ((m_off - 1) >> 8));
+		bbPutByte(c, (unsigned)m_off - 1);
+	}
+	m_len = m_len - 1 - (m_off > M2_MAX_OFFSET);
+	if (m_len >= 4)
+	{
+		bbPutBit(c,0);
+		bbPutBit(c,0);
+		code_prefix_ss11(c, m_len - 4);
+	}
+	else
+	{
+		bbPutBit(c, m_len > 1);
+		bbPutBit(c, (unsigned)m_len & 1);
+	}
+
+	c->last_m_off = m_off;
+}
+
+static void
+code_run(struct ucl_compress *c, const uint8_t *ii, unsigned int lit)
+{
+	if (lit == 0)
+		return;
+	c->lit_bytes += lit;
+	if (lit > c->result[5])
+		c->result[5] = lit;
+	do {
+		bbPutBit(c, 1);
+		bbPutByte(c, *ii++);
+	} while (--lit > 0);
+}
+
+/***********************************************************************
+//
+************************************************************************/
+
+static int
+len_of_coded_match(struct ucl_compress *c, unsigned int m_len, unsigned int
+	m_off)
+
+{
+	int b;
+	if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
+		|| m_off > c->conf.max_offset)
+		return -1;
+	assert(m_off > 0);
+	
+	m_len = m_len - 2 - (m_off > M2_MAX_OFFSET);
+	
+	if (m_off == c->last_m_off)
+		b = 1 + 2;
+	else
+	{
+		b = 1 + 10;
+		m_off = (m_off - 1) >> 8;
+		while (m_off > 0)
+		{
+			b += 2;
+			m_off >>= 1;
+		}
+	}
+
+	b += 2;
+	if (m_len < 3)
+		return b;
+	m_len -= 3;
+
+	do {
+		b += 2;
+		m_len >>= 1;
+	} while (m_len > 0);
+
+	return b;
+}
+
+int ucl_nrv2b_99_compress(
+	const uint8_t *in, unsigned long in_len,
+	uint8_t *out, unsigned long *out_len,
+	unsigned int *result)
+{
+	const uint8_t *ii;
+	unsigned int lit;
+	unsigned int m_len, m_off;
+	struct ucl_compress c_buffer;
+	struct ucl_compress * const c = &c_buffer;
+	struct ucl_swd *swd;
+	unsigned int result_buffer[16];
+	int r;
+
+/* max compression */
+#define SC_TRY_LAZY    2
+#define SC_GOOD_LENGTH F
+#define SC_MAX_LAZY    F
+#define SC_NICE_LENGTH F
+#define SC_MAX_CHAIN   4096
+#define SC_FLAGS       1
+#define SC_MAX_OFFSET  N
+	
+	memset(c, 0, sizeof(*c));
+	c->ip = c->in = in;
+	c->in_end = in + in_len;
+	c->out = out;
+	c->result = result ? result : result_buffer;
+	memset(c->result, 0, 16*sizeof(*c->result));
+	c->result[0] = c->result[2] = c->result[4] = UINT_MAX;
+	result = NULL;
+	memset(&c->conf, 0xff, sizeof(c->conf));
+	r = bbConfig(c, ENDIAN, BITSIZE);
+	if (r == 0)
+		r = bbConfig(c, c->conf.bb_endian, c->conf.bb_size);
+	if (r != 0)
+		return UCL_E_INVALID_ARGUMENT;
+	c->bb_op = out;
+	
+	ii = c->ip;             /* point to start of literal run */
+	lit = 0;
+	
+
+	swd = (struct ucl_swd *) malloc(sizeof(*swd));
+	if (!swd)
+		return UCL_E_OUT_OF_MEMORY;
+
+	swd->f = F;
+	swd->n = N;
+	if (in_len >= 256 && in_len < swd->n)
+		swd->n = in_len;
+	if (swd->f < 8 || swd->n < 256)
+		return UCL_E_INVALID_ARGUMENT;
+
+	r = init_match(c,swd,NULL,0, SC_FLAGS);
+	if (r != UCL_E_OK)
+	{
+		free(swd);
+		return r;
+	}
+	if (SC_MAX_CHAIN > 0)
+		swd->max_chain = SC_MAX_CHAIN;
+	if (SC_NICE_LENGTH > 0)
+		swd->nice_length = SC_NICE_LENGTH;
+	if (c->conf.max_match < swd->nice_length)
+		swd->nice_length = c->conf.max_match;
+	
+	c->last_m_off = 1;
+	r = find_match(c,swd,0,0);
+	if (r != UCL_E_OK)
+		return r;
+	while (c->look > 0)
+	{
+		unsigned int ahead;
+		unsigned int max_ahead;
+		int l1, l2;
+		
+		c->codesize = c->bb_op - out;
+		
+		m_len = c->m_len;
+		m_off = c->m_off;
+		
+		assert(c->bp == c->ip - c->look);
+		assert(c->bp >= in);
+		if (lit == 0)
+			ii = c->bp;
+		assert(ii + lit == c->bp);
+		assert(swd->b_char == *(c->bp));
+		
+		if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
+			|| m_off > c->conf.max_offset)
+		{
+			/* a literal */
+			lit++;
+			swd->max_chain = SC_MAX_CHAIN;
+			r = find_match(c,swd,1,0);
+			assert(r == 0);
+			continue;
+		}
+		
+		/* a match */
+		assert_match(swd,m_len,m_off);
+		
+		/* shall we try a lazy match ? */
+		ahead = 0;
+		if (SC_TRY_LAZY <= 0 || m_len >= SC_MAX_LAZY || m_off ==
+			c->last_m_off)
+
+		{
+			/* no */
+			l1 = 0;
+			max_ahead = 0;
+		}
+		else
+		{
+			/* yes, try a lazy match */
+			l1 = len_of_coded_match(c,m_len,m_off);
+			assert(l1 > 0);
+			max_ahead = SC_TRY_LAZY;
+			if ((m_len - 1) < max_ahead) {
+				max_ahead = m_len -1;
+			}
+		}
+		
+		while (ahead < max_ahead && c->look > m_len)
+		{
+			if (m_len >= SC_GOOD_LENGTH)
+				swd->max_chain = SC_MAX_CHAIN >> 2;
+			else
+				swd->max_chain = SC_MAX_CHAIN;
+			r = find_match(c,swd,1,0);
+			ahead++;
+			
+			assert(r == 0);
+			assert(c->look > 0);
+			assert(ii + lit + ahead == c->bp);
+			
+			if (c->m_len < 2)
+				continue;
+			l2 = len_of_coded_match(c,c->m_len,c->m_off);
+			if (l2 < 0)
+				continue;
+			if (l1 + (int)(ahead + c->m_len - m_len) * 5 > l2 +
+				(int)(ahead) * 9)
+			{
+				c->lazy++;
+				assert_match(swd,c->m_len,c->m_off);
+				lit += ahead;
+				assert(ii + lit == c->bp);
+				goto lazy_match_done;
+			}
+		}
+		
+		assert(ii + lit + ahead == c->bp);
+		
+		/* 1 - code run */
+		code_run(c,ii,lit);
+		lit = 0;
+		
+		/* 2 - code match */
+		code_match(c,m_len,m_off);
+		swd->max_chain = SC_MAX_CHAIN;
+		r = find_match(c,swd,m_len,1+ahead);
+		assert(r == 0);
+		
+	lazy_match_done: ;
+	}
+	
+	/* store final run */
+	code_run(c,ii,lit);
+	
+	/* EOF */
+	bbPutBit(c, 0);
+	code_prefix_ss11(c, 0x1000000U);
+	bbPutByte(c, 0xff);
+
+	bbFlushBits(c, 0);
+	
+	assert(c->textsize == in_len);
+	c->codesize = c->bb_op - out;
+	*out_len = c->bb_op - out;
+	
+#if 0
+	printf("%7ld %7ld -> %7ld   %7ld %7ld   %ld  (max: %d %d %d)\n",
+		(long) c->textsize, (long) in_len, (long) c->codesize,
+		c->match_bytes, c->lit_bytes,  c->lazy,
+		c->result[1], c->result[3], c->result[5]);
+#endif
+	assert(c->lit_bytes + c->match_bytes == in_len);
+	
+	swd_exit(swd);
+	free(swd);
+
+	return UCL_E_OK;
+}
+
+
+void Encode(void)  /* compression */
+{
+	uint8_t *in, *out;
+	unsigned long in_len, out_len;
+	uint32_t tw;
+	int r;
+	fseek(infile, 0, SEEK_END);
+	in_len = ftell(infile);
+#ifdef VERBOSE
+	if ((signed long)in_len < 0)
+		Fprintf((stderr, "Errno: %d", errno));
+#endif
+#if UCLPACK_COMPAT
+	{
+		uint8_t byte;
+		if (fwrite(magic, sizeof(magic), 1, outfile) != 1)
+			Error("Can't write.");
+		tw = htonl(0); /* flags */
+		if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
+			Error("Can't write.");
+		byte = 0x2b;		/* method */
+		if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
+			Error("Can't write.");
+		byte = 10;		/* level */
+		if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
+			Error("Can't write.");
+		tw = htonl(256*1024);		/* block_size */
+		if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
+			Error("Can't write.");
+		tw = htonl(in_len);
+		if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
+			Error("Can't write.");	/* output size of text */
+	}
+#else
+	tw = host_to_i86ul(in_len);
+	if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
+		Error("Can't write.");	/* output size of text */
+#endif	
+	if (in_len == 0)
+		return;
+	rewind(infile);
+
+	in = malloc(in_len);
+	out_len = in_len + (in_len/8) + 256;
+	out = malloc(out_len);
+	if (!in || !out) {
+		Error("Can't malloc");
+	}
+	if (fread(in, in_len, 1, infile) != 1) {
+		Error("Can't read");
+	}
+	r = ucl_nrv2b_99_compress(in, in_len, out, &out_len, 0 );
+#if UCLPACK_COMPAT
+	tw = htonl(out_len);
+	if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
+		Error("Can't write.");	/* file size of text */
+
+#endif
+	if (fwrite(out, out_len, 1, outfile) != 1) {
+		Error("Write error\n");
+	}
+#if UCLPACK_COMPAT
+	tw = htonl(0); /* EOF marker */
+	if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
+		Error("Can't write.");
+
+#endif
+
+#ifdef	LONG_REPORT
+	Fprintf((stderr, "input size    %ld bytes\n", in_len));
+	Fprintf((stderr, "output size   %ld bytes\n", out_len));
+	Fprintf((stderr, "input/output  %.3f\n", (double)in_len / out_len));
+#else
+	Fprintf((stderr, "input/output = %ld/%ld = %.3f\n", in_len, out_len,
+		(double)in_len / out_len));
+#endif
+	
+}
+
+#endif
+
+#ifdef DECODE
+
+#define GETBIT_8(bb, src, ilen) \
+    (((bb = bb & 0x7f ? bb*2 : ((unsigned)src[ilen++]*2+1)) >> 8) & 1)
+
+#define GETBIT_LE16(bb, src, ilen) \
+    (bb*=2,bb&0xffff ? (bb>>16)&1 : (ilen+=2,((bb=(src[ilen-2]+src[ilen-1]*256u)*2+1)>>16)&1))
+
+#define GETBIT_LE32(bb, src, ilen) \
+    (bc > 0 ? ((bb>>--bc)&1) : (bc=31,\
+    bb=*(const uint32_t *)((src)+ilen),ilen+=4,(bb>>31)&1))
+
+#if ENDIAN == 0 && BITSIZE == 8
+#define GETBIT(bb, src, ilen) GETBIT_8(bb, src, ilen)
+#endif
+#if ENDIAN == 0 && BITSIZE == 16
+#define GETBIT(bb, src, ilen) GETBIT_LE16(bb, src, ilen)
+#endif
+#if ENDIAN == 0 && BITSIZE == 32
+#define GETBIT(bb, src, ilen) GETBIT_LE32(bb, src, ilen)
+#endif
+
+#ifndef GETBIT
+#error "Bad Combination of ENDIAN and BITSIZE values specified"
+#endif
+
+#undef SAFE
+
+#ifdef SAFE
+#define FAIL(x,r)   if (x) { Error(r); }
+#else
+#define FAIL(x,r)
+#endif
+
+void Decode(void)  /* recover */
+{
+	uint32_t tw;
+	uint8_t *src, *dst;
+	unsigned long max_src_len, src_len, dst_len;
+	unsigned long ilen = 0, olen = 0, last_m_off =  1;
+	uint32_t bb = 0;
+	unsigned bc = 0;
+#if UCLPACK_COMPAT
+	if (fseek(infile, sizeof(magic) + sizeof(tw) + 1 + 1 + sizeof(tw),
+		SEEK_SET) != 0)
+
+		Error("Seek Error");
+	if (fread(&tw, sizeof(tw), 1, infile) < 1)
+		Error("Can't read"); /* read size of text */
+	dst_len = ntohl(tw);
+	if (fread(&tw, sizeof(tw), 1, infile) < 1)
+		Error("Can't read"); /* read size of file */
+	max_src_len = ntohl(tw);
+#else
+	if (fread(&tw, sizeof(tw), 1, infile) < 1)
+		Error("Can't read"); /* read size of text */
+	dst_len = i86ul_to_host(tw);
+	max_src_len = dst_len + (dst_len/8) + 256;
+#endif
+	if (dst_len == 0)
+		return;
+	dst = malloc(dst_len);
+	if (!dst)
+		Error("Can't malloc");
+	src = malloc(max_src_len);
+	if (!src)
+		Error("Can't malloc");
+	src_len = fread(src, 1, max_src_len, infile);
+	if (src_len <= 0) 
+		Error("Can't read");
+
+	for(;;) {
+		unsigned int m_off, m_len;
+		while(GETBIT(bb, src, ilen)) {
+			FAIL(ilen >= src_len, "input overrun");
+			FAIL(olen >= dst_len, "output  overrun");
+			dst[olen++] = src[ilen++];
+		}
+		m_off = 1;
+		do {
+			m_off = m_off*2 + GETBIT(bb, src, ilen);
+			FAIL(ilen >= src_len, "input overrun");
+			FAIL(m_off > 0xffffffU +3, "lookbehind overrun");
+		} while (!GETBIT(bb, src, ilen));
+		if (m_off == 2)
+		{
+			m_off = last_m_off;
+		}
+		else
+		{
+			FAIL(ilen >= src_len, "input overrun");
+			m_off = (m_off - 3)*256 + src[ilen++];
+			if(m_off == 0xffffffffU)
+				break;
+			last_m_off = ++m_off;
+		}
+		m_len = GETBIT(bb, src, ilen);
+		m_len = m_len*2 + GETBIT(bb, src, ilen);
+		if (m_len == 0) 
+		{
+			m_len++;
+			do {
+				m_len = m_len*2 + GETBIT(bb, src, ilen);
+				FAIL(ilen >= src_len, "input overrun");
+				FAIL(m_len >= dst_len, "output overrun");
+			} while(!GETBIT(bb, src, ilen));
+			m_len += 2;
+		}
+		m_len += (m_off > 0xd00);
+		FAIL(olen + m_len > dst_len, "output overrun");
+		FAIL(m_off > olen, "lookbeind overrun");
+		{
+			const uint8_t *m_pos;
+			m_pos = dst + olen - m_off;
+			dst[olen++] = *m_pos++;
+			do {
+				dst[olen++] = *m_pos++;
+			} while(--m_len > 0);
+		}
+	}
+	FAIL(ilen < src_len, "input not consumed");
+	FAIL(ilen > src_len, "input overrun");
+	assert(ilen == src_len);
+	Fprintf((stderr, "%12ld\n", olen));
+	if (dst_len != olen) {
+		fprintf(stderr, "length != expected length\n");
+	}
+	if (fwrite(dst, olen, 1, outfile) != 1)
+		Error("Write error\n");
+	free(src);
+	free(dst);
+}
+#endif
+
+#ifdef MAIN
+int main(int argc, char *argv[])
+{
+	char  *s;
+	FILE  *f;
+	int    c;
+	
+	if (argc == 2) {
+		outfile = stdout;
+		if ((f = tmpfile()) == NULL) {
+			perror("tmpfile");
+			return EXIT_FAILURE;
+		}
+		while ((c = getchar()) != EOF)
+			fputc(c, f);
+		rewind(infile = f);
+	}
+	else if (argc != 4) {
+		Fprintf((stderr, "'lzhuf e file1 file2' encodes file1 into
+file2.\n"
+
+			"'lzhuf d file2 file1' decodes file2 into
+file1.\n"));
+
+		return EXIT_FAILURE;
+	}
+	if (argc == 4) {
+		if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
+			|| (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
+			|| (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
+			Fprintf((stderr, "??? %s\n", s));
+			return EXIT_FAILURE;
+		}
+	}
+	if (toupper(*argv[1]) == 'E')
+		Encode();
+	else
+		Decode();
+	fclose(infile);
+	fclose(outfile);
+	return EXIT_SUCCESS;
+}
+#endif