nrv2b.c

linux下从网卡远程启动

/**************************************************************
    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 <[e-mail]>
    						1997-01-27

    Modifications to allow use as a filter by Ken Yap
    <[e-mail]>.

						1997-07-01

    Small mod to cope with running on big-endian machines
    by Jim Hague <[e-mail])
						1998-02-06

    Make compression statistics report shorter
    by Ken Yap <[e-mail]>.
						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 <[e-mail]>.
                                             20 August 2002
                                                
**************************************************************/
#define UCLPACK_COMPAT 0
#define NDEBUG 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#ifdef __FreeBSD__
#include <inttypes.h>
#else
#include <stdint.h>
#endif
#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;
	
	uint64_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